Predicate Compiler Technology And Deep Code Optimization

Instruction-level parallelism has greatly accelerated the development and improvement of computer architecture; likewise, the performance of computer has been enhanced by a large step. From the beginning, instruction-level parallelism has been a hot research area for compilation technologies for a long time and a lot of achievements have been achieved. A limit study on instruction-level parallelism【Wall91】indicated that an ideal instruction-level parallelism could reach 5 IPC(instructions per cycle) for most of programs. However, compilers for real machines have difficulties in generating code with that high IPC. The design of computer architecture aims to support more compiler optimizations to exploit higher Instruction-level Parallelism; predication support offers opportunities for Instruction-level Parallelism but presents challenges for compiler. The thesis focuses on the research of predication technologies and elaborates its application in compiler optimization and impact on computer architecture, in the meantime, the thesis studies EPIC-dependent optimizations and achieves following achievements:1. Introduce a cost model for if conversion to take those branches with high miss prediction rates into account, and simulate the resources scheduling with prediction. The IF Conversion phase builds a precise decision technique to convert control flow in order to eliminate branches and help predicates analysis technique with each other.2. Introduce a predicate analysis technique based on regions to build a Predicate Relation DataBase (PRDB). On improving and evaluating PRDB, the thesis made various experiments in IA-64 Open Research Compiler (ORC) to examine the performance impact of predication technology. In the end, the thesis proves the overall status of predication in IA-64.3. Handle multiple reaching definitions in predicate analysis while avoiding SSA form. There are no SSA representations in Code Generator of ORC backend, so the flexible application and accurate computation of predicate analysis demonstrates the technique handling multiple reaching definitions to be efficient.4. Introduce and implement predicate-aware data flow analysis in ORC, resolve conditional definition and reference problem of predicated instructions in conventional data flow analysis. Predicate-aware data flow analysis builds the flow information both for program data dependence analysis and for variables'live range analysis in and between basic blocks. Predicate-aware data flow analysis is different from the impact of predication in Instruction Scheduling and Register Allocation, in that it reflects the essential behavior of predication in program.5. Introduce a control flow path sensitive code optimization technique. There are conventional optimizations, such as removing branches, reducing critical paths,...