In this project we have undertaken a new approach to PRE. Instead of inserting the expression in paths along which the expression is not computed, and worrying about down-safety, we take a completely different approach. We transform the flow graph in such a way as to change partial redundancy to full redundancy. We have two options for implementing this - one, we can keep track of the dynamic path the program execution takes by computing the predicates along which the expression is computed. Thus, at a point where an expression is needed, but is only partial available, we check the dynamic path to see if the expression has been pre-computed. If so, it is eliminated. This can be done by associating a predicate with each expression at every program point. The predicate specifies whether the expression has been computed or not. Second, we can use another approach whereby we duplicate nodes along the path from where an expression becomes partially available to the point where it is used/anticipated. The paths along which the expression is fully available will be directed to this newly created duplicate path. Now, all expressions in this path can be eliminated.
During the implementation of our path detection algorithm, we discovered that the path detection approach will not work for cyclic graphs. The main reason for this is that the predicates we associate have no context of time - hence, mixing a predicates from different iterations can give wrong results. On the other hand, the node-duplicating solution will work for any graph. The disadvantage, however, is code explosion.
The challenge we were facing was to combine the two solutions: an efficient solution that works only for acyclic graphs and an expensive general one. We decided to take the following approach - we use the node-duplicating solution for loops (cyclic graphs), and the dynamic path based solution for acyclic graphs (all nodes outside loops). Our algorithm is to first apply the node-duplicating approach for loops, then annotate the loop nodes, remove the back edges and insert some meaningful predicates at the exits of the loops that summarize the information about partial/fully available expressions at that point. With this information, we could run the path detection algorithm on the acyclic graph obtained, ignore the loop nodes, but use the predicates at the exits of the loops in order to compute dynamic paths information required for each expression.