How to simplify a C-style arithmetical expression containing variables during code generation?

Question

I am trying to optimize expression evaluation in a compiler.

The arithmetical expressions are all C-style, and they may contain variables. I hope to simplify the expressions as much as possible.

For example, (3+100*A*B+100)*3+100 may be simplified to 409+300*A*B.

It mainly depends on the distributive law, the associative law and the commutative law.

The main difficulty I encounter is how to combine these arithmetical laws and traditional stack-scan evaluating algorithms.

Can anyone share experiences related to this or similar problems in the context of compiler building?

Answer 1

Compilers usually have some internal normalization rules like "constants to the left". This means a + 3 would be transformed into 3 + a, but not vice versa.

In your example, (3+100*A*B+100)*3+100 would be normalized into (3+100+(100*A*B))*3+100. Now it is clear to optimize 3+100.

Another transformation might be a*C1+C2 into (a+(C2/C1))*C1 under the condition that C1 and C2 are constants. Intuitively, this normalizes "add before multiply".

Those normalizations are not optimizations. The intention is mostly to group constants together, so constant folding is more effective.