Research Of If-conversion Techniques Based On IA-64 Predicated Execution

Branch instructions lead to control dependence, which is a barrier of exploiting instruction lever parallelism (ILP). In order to increase available ILP, the limitations imposed by branch instructions must be overcome. Predicated execution can effectively delete branch instructions in instruction stream, thus be helpful for the exploitation of more ILP.IA-64 is a kind of Explicitly Parallel Instruction Computing (EPIC) architectures, supporting full predicated execution, which provides new means and opportunities for more ILP. However, effective utilization of hardware support for predicated execution requires advanced compiler support. If-conversion is a compilation technique that takes advantage of predicated execution provided by modern processors to promote the performance of programs. There are many benefits from if-conversion. Firstly, if-conversion can convert branch instructions in program to sequential predicated execution instructions, thus control dependence be turned into data dependence, and instructions in multiple paths can be merged into a basic block after if-conversion, which increases ILP in basic blocks by making basic blocks contain more instructions and extending instruction scheduling space. On the other hand, because of the reduction of branch instructions and simplicity in hardware design, performance loss due to branch mispredication is reduced as well.First we introduce theories in predicated execution and if-conversion, and analyze the characteristics of predicated execution in IA-64 architecture. The importance of if-conversion and the effect of if-conversion on program performance are pointed out, and then two key questions are discussed: what should be if-converted and when the if-conversion should be applied.With theory research before, we pay attention to the implementation of if-conversion in GCC on IA-64 architecture, and give the frame of if-conversion in GCC. At last we analyze the advantage and existing problem of GCC if-conversion, and provide an amended algorithm based on critical path length, resource usage height, misprediction rate, misprediction cost and instruction number, which applies if-conversion selectively. The experiment results show that the amended algorithm can improve the effectivity of if-conversion and promote the performance of programs.