The Program Decision Logic Approach to Predicated ExecutionDavid I. August John W. Sias Jean-Michel Puiatti Scott A. MahlkeyDaniel A. Connors Kevin M. Crozier Wen-mei W. HwuCenter for Reliable and High-Performance ComputingUniversity of IllinoisUrbana-Champaign, IL 61801faugust, [email protected], [email protected], [email protected],fdconnors, crozier, [email protected] compilers must expose sufficient amounts ofInstruction-Level Parallelism (ILP) to achieve the promisedperformance increases of superscalar and VLIW processors.One of the major impediments to achieving this goal has beeninefficient programmatic control flow. Historically, the compilerhas translated the programmer’s original control structuredirectly into assembly code with conditional branch instructions.Eliminating inefficiencies in handling branch instructions andexploiting ILP has been the subject of much research. However,traditional branch handling techniques cannot significantlyalter the program’s inherent control structure. The advent ofpredication as a program control representation has enabledcompilers to manipulate control in a form more closely relatedto the underlying program logic. This work takes full advantageof the predication paradigm by abstracting the program controlflow into a logical form referred to as a program decision logicnetwork. This network is modeled as a Boolean equation andminimized using modified versions of logic synthesis techniques.After minimization, the more efficient version of the program’soriginal control flow is re-expressed in predicated code. Fur-thermore, this paper proposes extensions to the HPL PlayDohpredication model in support of more effective predicate decisionlogic network minimization. Finally, this paper shows the abilityof the mechanisms presented to overcome limits on ILP previouslyimposed by rigid program control structure.1 IntroductionExploiting Instruction-Level Parallelism (ILP) in the presenceof branches has been the subject of much research. The two mostcommonly used techniques are control speculation and predica-tion. Control speculation is most commonly performed in super-scalar processors using a combination of branch prediction and dy-namic scheduling [9][19][23]. Control speculation increases ILPby guessing the outcome of a branch and executing instructions Logic Systems Laboratory (DI-LSL), Swiss Federal Institute of Tech-nology of Lausanne (EPFL), CH-1015 Lausanne, SwitzerlandyHewlett-Packard Laboratories, Hewlett-Packard, Palo Alto, CA 94304along the predicted path. In this manner, control dependences arebroken to execute instructions before the branch outcome is de-termined. Given an instruction set that supports speculative op-erations, control speculation can also be performed statically byan aggressive compile-time scheduler which moves instructionsacross branches [3][12].Predication has become a popular instruction set architecturefeature for expressing program control by conditionally execut-ing instructions [8][16]. A compiler can employ if-conversion toconvert a sequence of code containing branches into an equivalentbranch-free sequence of conditionally executed instructions [2].Predicated execution increases ILP by allowing the compiler toschedule operations from multiple paths of control for simultane-ous execution.One fundamental limitation of most previous branch handlingtechniques is that they do not significantly alter the program’s con-trol flow logic. As the compiler translates high-level language con-trol constructs into assembly-level branches, it does not alter thebasic control structure. Instead, techniques focused on exposingand increasing ILP within a fixed control structure are applied.With control speculation, this is obvious. Control dependences areremoved to enable the motion of instructions above branches. Thebranches themselves are not altered. Likewise, when predication isapplied by the process of if-conversion, branches are transformedinto predicate computations and control dependent instructions arerendered conditional by the addition of guarding predicates. Thisprocess converts control flow and control dependences into dataflow and data dependences, but preserves the original program’scontrol structure.Restricting a compiler to use the program’s unaltered controlstructure is undesirable for several reasons. First, a high-level lan-guage such as C or C++ represents program control flow in an ex-tremely sequential manner through the use of nested if-then-elsestatements, switch statements, and loop constructs. Each controlconstruct is fully evaluated before proceeding to the next. This se-quential computation often defines the program critical paths thatconstrain the available ILP. Second, programmers represent con-trol flow for understandability or for ease of debugging rather thanfor efficient execution on the target architecture. As a result, soft-ware often contains redundant control constructs that are difficultto detect with traditional compiler techniques. These may involveevaluating the same conditions multiple times or evaluating con-To appear in proceedings of ISCA99ditions that partially overlap. An effective ILP compiler should becapable of transforming the program control structure to eliminatethese problems.The ability to restructure code aggressively is a critical featureof an effective ILP compiler. The most obvious situation whereaggressive transformation is regularly applied is on arithmetic ex-pressions. Compilers often completely restructure the program-mer’s arithmetic computations into more parallel forms using a va-riety of transformations. These include expression re-association,tree height reduction [11], and blocked back substitution [17]. Al-though ILP compilers may aggressively restructure computation,they typically preserve the program’s original control structure.This conservative approach can seriously limit the level of effi-ciency as well as the level of ILP achieved in branch-intensiveprograms.Our Approach. Motivated by the potential of aggressive tech-niques for transforming arithmetic expressions, this paper intro-duces a new approach to optimizing program control flow. Thegoal of this work is to develop a systematic methodology for refor-mulating program control flow for more efficient execution on anILP processor. Control expressed in branches and predicate defineinstructions is first extracted and represented as a program decisionlogic