Question

What is algebraic transformation in compiler designing?

Answer 1

Algebraic transformations and re-ordering

- Remove/simplify operations like

. Multiplication by 1

. Multiplication by 0

. Addition with 0

- Reorder instructions based on

. Commutative properties of operators

. For example x+y is same as y+x (always?)

Instruction selection

- Addressing mode selection

- Opcode selection

- Peephole optimization

Some of the different optimization methods are :

1) Constant Folding - replacing y= 5+7 with y=12 or y=x*0 with y=0

2) Dead Code Elimination - e.g.,

If (false)

a = 1;

else

a = 2;

with a = 2;

3) Peephole Optimization - a machine-dependent optimization that makes a pass through low-level assembly-like instruction sequences of the program( called a peephole), and replacing them with a faster (usually shorter) sequences by removing redundant register loads and stores if possible.

4) Flow of Control Optimizations

5) Strength Reduction - replacing more expensive expressions with cheaper ones - like pow(x,2) with x*x

6) Common Sub expression elimination - like a = b*c, f= b*c*d with temp = b*c, a= temp, f= temp*d;