The Research And Implementation Of Predicated Execution

Instruction level parallel processing is the key technology to improve the performance of current processors, while the control dependences caused by braches become bottlenecks of exploiting ILP. Therefore, the instruction sets of recent VLIW DSPs offer support for branch-free execution of conditional statements in the form of so-called conditional instructions. In order to exert the advantages of such kind instructions, this paper, aiming at improving ILP as high as possible, does a deep research on Predicated Execution, making main contributions as follows:1.A compiler framework for Predicated Execution is designed and implemented. Based on the region of hyperblock, the framework resolves problems caused by full if-conversion, and supports DSPs conditional instructions effectively, and provides larger space for scheduling and optimizing modules to improve ILP.2.Predicate-specific analysis and optimizations are presented. In order to do optimization, scheduling and register allocation on the predicated code more efficiently, we first introduce Predicate Analysis System (PAS) based on Binary Decision Diagram, which is proposed by John W.Sias etc, and the method of data flow analysis using Predicate Flow Graph. And then, a procedure of predicate optimization is put forward, which incorporates the architecture characteristics of VLIW DSP. The procedure uses the relations among predicates provided by PAS to simplify predicate expressions, such that the control logic becomes simpler, and the number of used predicated registers becomes smaller.3.A new register allocation algorithm for predicated code is proposed. In order to relieve the pressure of register requirement brought by predicated execution, we modify the step of constructing interference graph of traditional register allocation algorithm, and according to relations among predicates, we present a new algorithm for constructing refined interference graph. As a result, register allocation for predicated code is more rational and the cases of register spilling are reduced.The results of experiment demonstrate higher ILP is exploited, and code execution time is shortened obviously. So the compiler performance is improved greatly.