Path Profile Guided Partial Redundancy Elimination Using Speculation

While programs contain a large number of paths, a very small fraction of these paths are typically exercised during program execution. Thus, optimization algorithms should be designed to trade off the performance of less frequently executed paths in favor of more frequently executed paths. However, traditional formulations to code optimizations are incapable of performing such a trade-off. We present a path profile guided partial redundancy elimination algorithm that uses speculation to enable the removal of redundancy along more frequently executed paths at the expense of introducing additional expression evaluations along less frequently executed paths. We describe cost-benefit data flow analysis that uses path profiling information to determine the profitability of using speculation. The cost of enabling speculation of an expression at a conditional is determined by identifying paths along which an additional evaluation of the expression is introduced. The benefit of enabling speculation is determined by identifying paths along which additional redundancy elimination is enabled by speculation. The results of this analysis are incorporated in a speculative expression hoisting framework for partial redundancy elimination.