Hucheng Zhou, Wenguang Chen, and Fred C. Chow
4 June 2011
To derive maximum optimization beneﬁts from partial redundancy elimination (PRE), it is necessary to go beyond its safety constraint. Algorithms for optimal speculative code motion have been developed based on the application of minimum cut to ﬂow networks formed out of the control ﬂow graph. These previous techniques did not take advantage of the SSA form, which is a popular program representation widely used in modern-day compilers. We have developed the MC-SSAPRE algorithm that enables an SSA-based compiler to take full advantage of SSA to perform optimal speculative code motion efﬁciently when an execution proﬁle is available. Our work shows that it is possible to form ﬂow networks out of SSA graphs, and the min-cut technique can be applied equally well on these ﬂow networks to ﬁnd the optimal code placement. We provide proofs of the correctness and computational and lifetime optimality of MC-SSAPRE. We analyze its time complexity to show its efﬁciency advantage. We have implemented MC-SSAPRE in the opensourced Path64 compiler. Our experimental data based on the full SPEC CPU2006 Benchmark Suite show that MC-SSAPRE can further improve program performance over traditional SSAPRE, and that our sparse approach to the problem does result in smaller problem sizes.