15-745 Optimizing Compilers

Spring 2006

Available Expressions in Task 1

One of the optimizations you are asked to implement for Task 1 is common-subexpression elimination (CSE), which is usually based on an available-expressions (AE) analysis. In the lecture notes on Classical Dataflow Optimizations, I've provided an explanation of what is AE analysis and a sketch of how it might be used to perform CSE.

In the L3 compilers we have provided to you, IR expressions are kept in tree form, even in the most linearized version of the IR. This is in contrast to the 3-address form shown in the lecture notes. The tree form is nice for some purposes, such as algebraic simplification of address arithmetic (assuming that such arithmetic expressions are marked, perhaps by comments). And for dead code elimination, constant folding, and constant propagation, having trees or 3-address code doesn't really matter too much.

However, for AE, In my view it is much easier to deal just with 3-address code. One reason is that having smaller (2-operand) expressions are easier to manage and match, and if you want to get fancy with matching modulo commutativity of operands (for operations like + and *), reassociation is eliminated as a concern.

I therefore advise you, in your implementation of AE, to begin with an implementation of an IR transformation that takes linearized IR trees and flattens all of the expression trees. This would involve creating more temps.

Let's look at a simple example. Suppose we have a linearized IR form like this:

 MOVE(TEMP(11), BINOP(PLUS, BINOP(PLUS, TEMP(14), TEMP(13)), TEMP(12)))

We can transform it into something like this:

 MOVE(TEMP(90), BINOP(PLUS, TEMP(14), TEMP(13)))
 MOVE(TEMP(11), BINOP(PLUS, TEMP(90), TEMP(12)))

in which all of the expressions have been flattened into 3-address form. This transformation is very easy. An even easier transformation would go like this:

 MOVE(TEMP(90), BINOP(PLUS, TEMP(14), TEMP(13)))
 MOVE(TEMP(91), TEMP(12))
 MOVE(TEMP(92), BINOP(PLUS, TEMP(90), TEMP(91)))
 MOVE(TEMP(11), TEMP(92))

Notice that while the latter transformation introduces spurious copies, we would assume that copy propagation and/or register coalescing would remove these copies automatically. The register allocators we have provided in the L3 compilers all perform register coalescing already.

So, at this point, you are now ready to perform AE, just as described in lecture. Good luck!

The bottom line is to make sure that every expression has only temp or constant arguments. Once this is done, then each expression in the available expressions analysis can be named by its label and associated with the left-hand-side variable.