Common Subexpression Elimination

This optimization feature involves enhancing recurring algebraic expressions in a program. However, these are no longer static expressions that can be simplified by various manipulations. In this case, the compiler searches for recurring subexpressions in a program section. If the variables used for computation purposes are unchanged, explicit recomputation can be skipped by reusing the result of the first computation. In other words, this technique necessitates a search for frequently used or common subexpressions, some of which can be eliminated in order to optimize program code. Not surprisingly, the technique is known as common subexpression elimination.7 The technique is best illustrated by reference to the following short example:

The recurring expression is obviously x*y. An analysis of program execution (usually referred to as program flow analysis in technical documents and research papers) reveals that this expression must be evaluated at least twice. The scanf statement reads the value for x from the console — that is, users

7To be strictly accurate, there are two different versions of this elimination technique. Which is used depends on whether the goal of optimization is to shorten execution time or to reduce code size — each option employs different algorithms.

can type in any value they want. The reason for using this unwieldy method instead of just assigning a specific value to the x variable is simple. If the value of x is fixed, a further optimization feature can be applied (called dead code elimination, as described in the next section). This would change the code so that the optimization feature discussed here would no longer be needed.

When a value is assigned to z, the program distinguishes two cases that depend on the size of the value stored in x. What is common to both cases is that the expression x*y is used in the assignment and, as can be confirmed easily by humans, but with extreme difficulty by compilers, the variables used in both branches of program flow do not change. The value previously computed as the assignment value for p can therefore be reused. Again, the difficulty with this optimization feature lies not in the actual technical replacement but in finding expressions that remain unchanged in all possible execution variants.

Continue reading here: Dead Code Elimination

Was this article helpful?

0 0