In many ways, modern superscalar, VLIW, and EPIC architectures are becoming increasingly dependent on the sophistication of compilers. As processor issue widths increase, the compiler's ability to utilize available resources by exposing sufficient Instruction-Level Parallelism (ILP) becomes critical in realizing a system's performance potential. One major impediment to a compiler's ability to expose ILP has been inefficient programmatic control flow. Historically, the compiler has translated the programmer's original control structure directly into assembly code with conditional branch instructions. Inefficiencies in this structure limit ILP, and much research have been dedicated to reducing branch control height and to reducing the cost of branch computation. Traditional branch handling techniques, however, are limited by the fact that they cannot significantly alter the program's original control structure.

The use of predication as a compiler intermediate representation has enabled compilers to manipulate program control flow in a form more closely related to the underlying program logic, creating opportunities for more general restructuring. This talk presents a technique that leverages the properties of the predicated representation to overcome limits on ILP previously imposed by rigid program control structure. The method developed abstracts the program control flow into a logical form referred to as a program decision logic network. This network, which can be viewed as a set of Boolean equations, is minimized using adapted versions of logic synthesis techniques. Further network optimization is performed using knowledge of implications between the condition evaluations, which is discerned using a value range analysis mechanism. After minimization, the more efficient version of the program's original control flow is re-expressed as predicated assembly code. This general restructuring of program control reduces height and complexity in ways that far exceed the capabilities of previous techniques.

About David August

David August is an Assistant Professor in the Department of Computer Science at Princeton University. He received the B.S. in Electrical Engineering from Rensselaer Polytechnic Institute in 1993, and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1995 and 2000, respectively. At Illinois, he was a member of IMPACT architecture and research compiler group and his research focussed on research focused on advanced predicate optimization and new compiler frameworks leveraging predication. He has received an Intel Foundation Fellowship, an Office of Naval Research Graduate Fellowship, and the University of Illinois Koehler Fellowship. He is a member of IEEE, ACM, Eta Kappa Nu, Tau Beta Pi, and Phi Kappa Phi.