Effective Compiler Support for Predicated Execution Using the Hyperblock Scott A. Mahlke David C. Lin’ William Y. Chen Richard E. Hank Roger A. Bringmann Center for Reliable and High-Performance Computing University of Illinois Urbana-Champaign, IL 61801 Abstract Predicated execution is an effective technique for dealing with conditional branches in application programs. How- ever, there are several problems associated with conventional compiler support for predicated execution. First, all paths of control are combined into a single path regardless of their execution frequency and size with conventional if-conversion techniques. Second, speculative execution is difficult to com- bine with predicated execution. In this paper, we propose the use of a new structure, referred to as the hyperblock, to overcome these problems. The hyperblock is an efficient structure to utilize predicated execution for both compile- time optimization and scheduling. Preliminary experimen- tal results show that the hyperblock is highly effective for a wide range of superscalar and VLIW processors. 1 Introduction Superscalar and VLIW processors can potentially provide large performance improvements over their scalar predeces- sors by providing multiple data paths and function units. In order to effectively utilize the resources, superscalar and VLIW compilers must expose increasing amounts of instruc- tion level parallelism (ILP). Typically, global optimization and scheduling techniques are utilized by the compiler to find sufficient ILP. A common problem all global optimiza- tion and scheduling strategies must resolve is conditional branches in the target application. Predicated execution is an efficient method to handle conditional branches. Predi- cated or guarded execution refers to the conditional execu- tion of instructions based on the value of a boolean source operand, referred to as the predicate. When the predicate has value T, the instruction is executed normally and when the predicate has value F, the instruction is treated as a no_op. With predicated execution support provided in the architecture, the compiler can eliminate many of the condi- tional branches in an application. The process of eliminating conditional branches from a program to utilize predicated execution support is referred to as if-conversion [l] [2] [3]. If-conversion was initially pro- posed to assist automatic vectorization techniques for loops with conditional branches. If-conversion basically replaces conditional branches in the code with comparison instruc- tions which set a predicate. Instructions control dependent *David Lin is now with Amdahl Corporation, Sunnyvale, CA. O-8186-3175-9/92 $3.00 0 1992 IEEE on the branch are then converted to predicated instructions dependent on the value of the corresponding predicate. In this manner, control dependences are converted to data de- pendences in the code. If-conversion can eliminate all non- loop backward branches from a program. Predicated execution support has been used effectively for scheduling both numeric and non-numeric applications. For numeric code, overlapping the execution of multiple loop it- erations using software pipeline scheduling can achieve high- performance on superscalar and VLIW processors [4] [5] [6]. With the abiity to remove branches with predicated exe- cution support, more compact schedules and reduced code expansion are achieved with software pipelining. Software pipelining taking advantage of predicated execution sup- port is productized in the Cydra 5 compiler [7] [8]. For non-numeric applications, decision tree scheduling utilizes guarded instructions to achieve large performance improve- ments on deeply pipelined processors as well as multiple- instruction-issue processors [9]. Guarded instructions allow concurrent execution along multiple paths of control and ex- ecution of instructions before the branches they depend on may be resolved. There are two problems, though, associated with utiliz- ing conventional compiler support for predicated execution. First, if-conversion combines all execution paths in a region (typically an inner loop body) into a single block. There- fore, instructions from the entire region must be examined each time a particular path through the region is entered. When a.ll execution paths are approximately the same size and have the same frequency, this method is very effective. However, the size and frequency of different execution paths typically varies in an inner loop. Infrequently executed paths and execution paths with comparatively larger number of instructions often limit performance of the resultant predi- cated block. Also, execution paths with subroutine calls or unresolvable memory accesses can restrict optimization and scheduling within the predicated block. The second problem is that speculative execution does not fit in conveniently with predicated execution. Speculative or eager execution refers to the execution of an instruction before it is certain its execution is required. With predicated instructions, speculative execution refers to the execution of an instruction before its predicate is calculated. Speculative execution is an important source of ILP for superscalar and VLIW processors by allowing long latency instructions to be initiated much earlier in the schedule. 45In this paper, we propose the use of a structure, referred to as the hyperblock, to overcome these two problems. A hyperblock is a set of predicated basic blocks in which con- trol may only enter from the top, but may exit from one or more locations. Hyperblocks are formed using a modi- fied version of if-conversion. Basic blocks are included in a hyperblock based on their execution frequency, size, and in- struction characteristics. Speculative execution is provided by