Path analysis and renaming for predicated instruction scheduling

Increases in instruction level parallelism are needed to exploit the potent ial parallelism available in future wide issue architectures. Predicated ex ecution is an architectural mechanism that increases instruction level para llelism by removing branches and allowing simultaneous execution of multipl e paths of control, only committing instructions from the correct path. In order for the complier to expose and use such parallelism, traditional comp iler data-flow and path analysis needs to be extended to predicated code. I n this paper, we motivate the need for renaming and for predicates that ref lect path information. We present Predicated Static Single Assignment (PSSA ) which uses renaming and introduces Full-Path Predicates to remove false d ependences and enable aggressive predicated optimization and instruction sc heduling We demonstrate the usefulness of PSSA for Predicated Speculation a nd Control Height Reduction. These two predicated code optimizations used d uring instruction scheduling reduce the dependence length of the critical p aths through a predicated region. Our results show that using PSSA to enabl e speculation and control height reduction reduces execution time from 12 t o 68%. Increases in instruction level parallelism are needed to exploit the potential parallelism available in future wide issue architectures. Predic ated execution is an architectural mechanism that increases instruction lev el parallelism by removing branches and allowing simultaneous execution of multiple paths of control, only committing instructions from the correct pa th. In order for the complier to expose and use such parallelism, tradition al compiler data-flow and path analysis needs to be extended to predicated code. In this paper, we motivate the need for renaming and for predicates t hat reflect path information. We present Predicated Static Single Assignmen t (PSSA) which uses renaming and introduces Full-Path Predicates to remove false dependences and enable aggressive predicated optimization and instruc tion scheduling We demonstrate the usefulness of PSSA for Predicated Specul ation and Control Height Reduction. These two predicated code optimizations used during instruction scheduling reduce the dependence length of the cri tical paths through a predicated region. Our results show that using PSSA t o enable speculation and control height reduction reduces execution time fr om 12 to 68%.