Register Allocation For Machines With Connected And Partitioned Register Banks

Register allocation (RA) is a major phase in the compiler backend, which has deep effect on the optimization results of other phases in the backend and hence the performance of processors. To support multicore, multithread, asynchronous I/O and to reduce the port number of register files, some processors are equipped with connected and partitioned register banks. Register allocation on this kind of processors is a big challenge for compilers. We have studied the register allocation problems on this kind of processors. The work described in this thesis has following contributions:1. Propose a register allocation framework for machines with connected and partitioned register banks. Different register banks (classes) are created in the traditional general purpose CPUs for different data types. They are mainly independent such that operands of a certain instruction can only come from one register bank. Therefore, we can apply Chaitin's approach to each register bank independently. But for those processors with connected and partitioned register banks, each bank is in the same word-length and can hold the same value. In such way, operands of an instruction can be placed in multiple register banks. Then, there come new problems for register allocation, that is, we have to identify the register bank attributes for variables and resolve the potential conflicts between register banks, which makes Chaitin's approach can not be applied directly. In this thesis, the concept of register bank partition graph is introduced. Then we show how to attack these problems by building, simplify and split the graph.2. Propose three approaches to solving the two source operand conflict problem. We know that the access speed of a register file is inversely proportional to its port number. To improve the speed of a register file, some processors demand that the two source operands of its instruction reside in different register banks, which in turn requires the register allocator to both assign register banks and allocate registers accordingly to variables. We introduce the concept of conflict graph and divide the register allocation problem under such two-source-operand constraints into two sub problems: the bank assignment subproblem and the register allocation subproblem. The former is attacked by 2-coloring the conflict graph and the latter is attacked by K-coloring the interference graph. According to the phase ordering of solving these two subproblems, three approaches are proposed: Pre-RA bank assignment, Post-RA bank assignment and Combined-RA bank assignment.3. Propose a register allocation framework with aggressive live range splitting and optimistic coalescing. A drawback of Chaitin's approach is that it will spill a live range totally when it is spilled. Our idea is to split live ranges aggressively before allocation. During allocation, we optimistically and aggressively coalesce the splitted live ranges. If an aggregate live range will be spilled, we try to re-split at the cracks and color each split independently. In such way, we gain the option to spill a live range totally, partially or avoid spill by using copy instructions.