Optimization Of Region-based Compilation And Stack Register

In order to improve instruction level parallelism,compilers tend to adopt more aggressive and complex optimization algorithms. But too complex and aggressive optimization algorithm will cost much compilation time and resources. In order to reduce compilation time and provide researchers a flexible research platform, on the meanwhile, prove the compilation performance,we proposed a flexible region formation infrastructure. In order to solve this problem that RSE cost is very serious for some programs, we proposed a effective algorithm to reduce RSE cost and improve overall execution performance.The main contributions of thesis are:1 We propose a new region formation infrastructure. This region formation infrastructure is hierarchical. Size and shape of regions could be controlled flexibly by setting specific parameters. Every basic block in the control flow is contained by at least one region. Regions are organized in a tree.2 We propose a Single Entry Multiple Exits region formation algorithm with max tail duplicate ratio and min exit probability constraints. Experiments show this algorithm is very effective in forming regions which could provide enough optimization opportunities for different optimization phases.3 We propose the attributes of region. Region attributes could be set,observed,maintained and deleted across different optimization phases. These attributes are very important for guarantee of the optimization effects.4 We propose a RSE cost model, and based on this cost model, we proposed the inter-procedural stacked register quota assignment problem.5 We propose a inter-procedural stacked register allocation algorithm,and it is implemented in ORC compiler.This algorithm could reduce the overall spill-to-memory access time so as to improve the program execution performance. This algorithm is based on the cost model proposed by us.6 We propose a method to decide whether allocating a stacked register to rematerializable live ranges. For a rematerializable live ranges, if the total execution frequency of the basic blocks where it is defined is greater then the total execution frequency of the basic blocks where it is used, then we need not allocate a register to it because spill could move those define to the basic blocks where it is used,therefore reduce the execution frequency of loads.