Turning Predicate Information to Advantage to Improve Compiler Scheduling and Branch Prediction

Architectural support for predicated execution has been proposed as a manner of attacking performance bottlenecks resulting from modern processor pipeline design. Predication is the process of removing control flow in a program and replacing it with predicate define data flow. Predication has the potential to reduce performance penalties from mispredicted branches and to make greater use of functional unit resources. However, this potential can be squandered or even turned into a performance loss if both the compiler producing the predicated code and the hardware executing the predicated code are not cognizant of the relationships between and values expressed by the predicates. In this dissertation we expose the importance of utilizing predicate information in both the compiler, for scheduling predicated code, and in the architecture for maintaining branch prediction accuracy in the face of predicated code. For the compiler, we define Predicated Static Single Assignment (PSSA). PSSA is a compiler-internal representation which maintains full-path information about predicates and their relationships. This complete information enables us to implement predicate-sensitive scheduling optimizations like predicated speculation and control height reduction that are not possible with less-complete predicate knowledge systems. In the hardware, we show the negative impact that predicate region formation can have on the predictability of branches in the program. We specifically evaluate the impact of misprediction migration -- the problem of increased mispredictions from branches located within predicated regions. We evaluate several predicate update branch prediction architectures targeted at both local and global prediction schemes with a goal of utilizing available predicate define information to restore high branch prediction accuracies.Pre-2018 CSE ID: CS2001-069