Sparse SSA Algorithm Of Partial Redundancy Elimination

PRE(Partial redundancy elimination) of expression is a very important architecture inde-pendent optimization, which subsumes the classical optimizations of loop invariant hoistingand common subexpression elimination. Due to the safety requirement, classical PRE opti-mization cannot fully eliminate the existed partial redundancies in application, thus cannot getthepotentialspeedup. Itisnecessarytorelaxthissafetyconstraint,andwecallitasspeculativePRE in this thesis.SSA(Static Single Assignment) has inherent use-definition relationship of variable, thusthe corresponding data flow analysis is only dependent on the problem size, rather than theprogram size. Due to the less complexity of data flow analysis, most of the modern compilerchoose SSA form as its intermediate representation during global optimization.In this thesis, we present algorithms for both computationally optimal and lifetime op-timal speculative PRE. Computationally optimality means that the total number of dynamiccomputations for the target expression in the transformed code is minimized. while lifetimeoptimality means the lifetimes of introduced temporary variables are also minimized. Themain contributions of this thesis are as follows:1. We present MC-SSAPRE algorithms, which enable an SSA-based compiler to take fulladvantage of SSA to perform optimal speculative code motion efficiently when an exe-cutionprofileisavailable. OurworkshowsthatitispossibletoformflownetworkoutofSSA graphs, and the minimum cut techniques can be applied equally well on these flownetworks to find the optimal code placement. We also provide rigorous proofs of thecorrectness and computational and lifetime optimality of MC-SSAPRE. We analyze itstime complexity to show its efficiency advantage. We have implemented MC-SSAPREin the open-sourced Path64compiler. Our experimental data based on the full SPEC-CPU2006BenchmarkSuiteshowsthatMC-SSAPREcanfurtherimproveprogramper-formance over traditional SSAPRE, and that our sparse approach to the problem basedon SSA form does result in smaller problem size.2. We present a new algorithm MF-SSAPRE for classical PRE based on maximum flowmodel of flow network. This unified framework to implement classical PRE and spec-ulative PRE optimization, which they shall most of the algorithm steps. Compared to SSAPRE, MF-SSAPRE is simpler and more understandable, thus convenient to engi-neering implementation.