Register allocation and code scheduling for load/store architectures
Wei‐Chung Hsu · Minds at UW (University of Wisconsin) · 1987
To achieve high performance, the structure of on-chip memory in a single-chip computer must be appropriate, and it must be allocated effectively to minimize off-chip communication. Since the off-chip memory bandwidth of single-chip computers is severely limited, data caches that exploit spatial locality to achieve high hit rates are not appropriate. A register file, which can be managed by compilers, might be more effective than a data cache as an on-chip memory structure. With a load/store architecture, compilers can separate operand fetches from their use by scheduling code, thus achieving high hit rates without increasing memory traffic. Register allocation also exploits temporal locality better than a data cache does. This thesis investigates how effective register allocation could be and studies the interdependency problem between register allocation and code scheduling. A model of perfect register allocation is explored. An algorithm for optimal local register allocation is then developed. Since the optimal algorithm needs exponential time in the worst case, a heuristic algorithm which has near-optimal performance is proposed and compared with other existing heuristic algorithms. Through trace simulation, the perfect register allocation model is shown to be much more effective in reducing off-chip memory traffic than cache memory of the same size. Code scheduling interferes with register allocation, especially for large basic blocks. Two methods are proposed to solve this interference: (1) an integrated code scheduling technique; and (2) a DAG-driven register allocator. The integrated code scheduling method combines two scheduling techniques--one to reduce pipeline delays and the other to minimize register usage--into a single phase. By keeping track of the number of available registers, the scheduler can choose the appropriate scheduling technique to schedule a better code sequence. The DAG-driven register allocator uses the Dependency DAG to assist in assigning registers; it introduces much less extra dependency than does an ordinary register allocator. Both approaches are shown to generate more efficient code sequences than conventional techniques in the simulations.