Demand-driven PRE Using Profile Information

Partial redundancy elimination (PRE) eliminates redundant expressions that repeatedly compute the same values. Following redundancy elimination, the application of copy propagation reveals additional redundancy, known as second-order effects. Eliminating this type of redundancy requires the iterative application of PRE and copy propagation. To eliminate many second-order effects within a short analysis time, demand-driven PRE (DDPRE) has been proposed. However, existing DDPREs assume that all expressions are executed an equal number of times, potentially resulting in spending analysis time on expressions with limited impact even after redundancy elimination and generating spills in register allocation that reduce the effects of redundancy elimination. This study proposes a novel type of DDPRE called profile-guided DDPRE (PDPRE) that utilizes runtime information to selectively apply DDPRE to areas where redundancy elimination is effective. Additionally, to eliminate second-order effects without executing a combination of redundancy elimination and copy propagation, PDPRE initially applies global value numbering. Subsequently, it visits expressions in the order of high execution counts, and then analyzes the redundancy of each expression. To evaluate the effectiveness of PDPRE, we applied PDPRE and existing DDPREs to the programs of the SPEC CPU2000 benchmark. We found that PDPRE both achieves shorter analysis times compared to the existing DDPREs and yields better execution times in many programs compared to existing DDPREs.