Region-based register allocation for epic architectures

Instruction-level parallelism (ILP) refers to a family of processor and compiler design techniques that speed up execution by allowing individual machine operations to execute in parallel. Explicitly Parallel Instruction computing (EPIC) processors evolved in an attempt to achieve high levels of ILP without significant hardware complexity. To take advantage of higher level of ILP in EPIC, the ILP compiler must use aggressive and expensive optimization techniques leading to increased compilation time. If the size and shape of the compilation unit is limited, the compilation time can be reduced. But this limited scope of compilation may restrict the scope of the optimization, thus limiting the amount of performance improvement that can be achieved. As a result, the compiler may generate less efficient code. Region-based compilation has been proposed as an approach for coping with this problem, namely that is containing compilation cost while not compromising execution performance. In region-based compilation, execution frequencies are used to guide compiler optimizations, with more attention given to the regions of the program with a higher frequency of execution, thus achieving greater overall performance improvements for the same compilation cost. In this thesis, we address the problem of the compilation time and execution performance trade-off in region-based compilation, within the context of the key optimization of register allocation. We demonstrate that schemes designed for region-based allocation perform as well as or even better than schemes designed for global register allocation while having much smaller compilation time. To achieve this goal, we innovated novel techniques which form the core of this thesis. We show compilation time savings of 40% on the average with comparable execution time performance by synthesizing our techniques in a region-based register allocation. We also explore the relation between the performance of the register allocation and the region size and quantify it. Our research shows that selecting the right sized region has impact on the performance of register allocation. Based on this observation, we proposed the concept of restructuring the regions based on register pressure, and develop techniques for estimating the register pressure in order to improve compilation time while maintaining the execution time.