Current Status

We have implemented the following analysis required for performing the program transformation:

1. Partial Availability of Expressions: This is a dataflow pass that computes the partially available expressions at the entry/exit of basic blocks.

2. Full Availability of Expressions: This is a dataflow pass that computes the fully available expressions at the entry/exit of basic blocks.

3. Path Detection: This pass generates a predicate for each partially available expression at every program point. The predicate specifies the dynamic path the program execution should have taken, if the expression is to be available at the specified program point. The pass works only for acyclic graphs.

4. Loops: Inside a loop, we are duplicating every node where an expression is partially available and not anticipated. This is a simple pass that does not use the dynamic path information, but uses the results of the partial and full availability passes.