Redundancy elimination [4] includes several optimizations such as: common-subexpression elimination (locate and eliminate redundant computations on a given execution path), loop-invariant code motion (find computations that are invariant inside a loop and move them outside the body of the loop), partial redundancy elimination (moves partially redundant computations on paths where they are not computed in order to make them fully redundant and then eliminate the redundant computations). Partial redundancy elimination is the most general form of redundancy elimination, that encompasses both common-subexpression elimination and loop-invariant code motion.
Several approaches have been taken to solve the problem of partial redundancy elimination. The first algorithm originated in 1979 [1] and formulates the problems as a bi-directional data flow analysis. The algorithm is conservative in inserting expressions only when they are anticipated and using a heuristic in order to find the "optimum place" where to insert expressions. Its primary limitation comes from the placement heuristic used, causing the algorithm to miss some eliminations or do some useless moves. A modern algorithm [2], is based on the idea of splitting critical edges (edges that connect a node with two or more predecessors with one with two or more successors) and introducing a new block on each such edge. More recently, an efficient algorithm based on the SSA form has been designed in [3]. Its efficiency comes from using a sparse representation (SSA) instead of the expensive bit-vector representation.
In this paper, we propose a simple but novel approach to partial redundancy elimination based on data flow analysis. We examine basic blocks where an expression is partially available (along some paths) and is locally anticipated (that is, it is computed within the block, and is upwards exposed). Our idea is to duplicate such a block into two identical basic blocks. We direct the paths along which the expression is available to one block, and all other paths to the other block. The expression computation in the first block is eliminated, but is retained in the second block. The outgoing edges from these two blocks will then meet at each successor of the original block. After having transformed the graph in this way, we might create new opportunities for other expressions, so we keep iterating the procedure until we do not find any blocks that could be duplicated.
To determine which paths contain the expression, we use dynamic path detection. The idea is to record the chain of predicates that brought the control to the current point. Since we know where the expression was first defined, we determine the predicates for the paths along which the expression is available, and direct these paths to the optimized block. More details in the next section.
Our algorithm is flexible in that we could only deal with some subset of the expressions computed in the program that could intuitively produce the biggest benefit (for example, the expressions that are computed inside loops). We are also planning to find some heuristics for duplicating the blocks in the graph in order to avoid an exponential increase in the number of nodes in the control flow graph.
This approach is elegant in that it transforms the control flow graph based on the context. In addition, unlike problems with other PRE approaches, it will find all eliminations, and since we don't insert the expression along paths that don't compute it, there is no need for complex bidirectional analysis to determine this insertion.