Compilers: Principles and Practice

10.4 Structural Optimization

In this category of optimization methods, the overall structure of the code is analyzed. Generally, such optimization results in reduction of both Time and Space. For the best optimization, a full IR in the form of AST is required.

10.4.1 Redundant Sub-expressions

Also called Elimination of common sub-expressions, this method does a pattern analysis of the IR and searches for expressions which are used repeatedly. They need to be computed only once and then the result is utilized wherever they are used later. For example, a * b + a * b. The 4-tuple matrix is:

i: LD   a   T1  −−
   MUL  b   T1  T2
   LD   a   T3	−−
   MUL  b   T3	T4
   ADD  T2  T4	T5

and can be reduced to:

i: LD   a   T1  −−
   MUL  b   T1  T2
   ADD  T2  T2  T3

Here, the common sub-expression ...