=================== Register Allocation =================== 1. Introduction =============== Purpose: This file contains implementation information about register allocation. Author : Ruchira Sasanka Date : Dec 8, 2001 2. Entry Point ============== class PhyRegAlloc (PhyRegAlloc.h) is the main class for the register allocation. PhyRegAlloc::allocateRegisters() starts the register allocation and contains the major steps for register allocation. 2. Usage ======== Register allocation must be done as: MethodLiveVarInfo LVI(*MethodI ); // compute LV info LVI.analyze(); TargetMachine &target = .... // target description PhyRegAlloc PRA(*MethodI, target, &LVI); // allocate regs PRA.allocateRegisters(); 4. Input and Preconditions ========================== Register allocation is done using machine instructions. The constructor to the class takes a pointer to a method, a target machine description and a live variable information for the method. The preconditions are: 1. Instruction selection is complete (i.e., machine instructions are generated) for the method before the live variable analysis 2. Phi elimination is complete. 5. Assumptions ============== All variables (llvm Values) are defined before they are used. However, a constant may not be defined in the machine instruction stream if it can be used as an immediate value within a machine instruction. However, register allocation does not have to worry about immediate constants since they do not require registers. Since an llvm Value has a list of uses associated, it is sufficient to record only the defs in a Live Range. 6. Overall Design ================= There are sperate reigster classes - e.g., Int, Float, IntConditionCode, FloatConditionCode register classes for Sparc. Registerallocation consists of the following main steps: 1. Construct Live-ranges & Suggest colors (machine specific) if required 2. Create Interference graphs 3. Coalescing live ranges 4. Color all live ranges in each RegClass using graph coloring algo 5. Insert additional (machine specific) code for calls/returns/incoming args 6. Update instruction stream and insert spill code All the above methods are called from PhyRegAlloc::allocateRegisters(). All steps above except step 5 and suggesting colors in step 1 are indepenedent of a particular target architecture. Targer independent code is availble in ../lib/CodeGen/RegAlloc. Target specific code for Sparc is available in ../lib/Target/Sparc. 6.1. Construct Live-ranges & Suggest colors (machine specific) if required -------------------------------------------------------------------------- Live range construction is done using machine instructions. Since there must be at least one definition for each variable in the machine instruction, we consider only definitions in creating live ranges. After live range construction is complete, there is a live range for all variables defined in the instruction stream. Note however that, live ranges are not constructed for constants which are not defined in the instruction stream. A LiveRange is a set of Values (only defs) in that live range. Live range construction is done in combination for all register classes. All the live ranges for a method are entered to a LiveRangeMap which can be accessed using any Value in the LiveRange. After live ranges have been constructed, we call machine specific code to suggest colors for speical live ranges. For instance, incoming args, call args, return values must be placed in special registers for most architectures. By suggesting colors for such special live ranges before we do the actual register allocation using graph coloring, the graph coloring can try its best to assign the required color for such special live ranges. This will reduce unnecessary copy instructions needed to move values to special registers. However, there is no guarantee that a live range will receive its suggested color. If the live range does not receive the suggested color, we have to insert explicit copy instructions to move the value into requred registers and its done in step 5 above. See LiveRange.h, LiveRangeInfo.h (and LiveRange.cpp, LiveRangeInfo.cpp) for algorithms and details. See SparcRegInfo.cpp for suggesting colors for incoming/call arguments and return values. 6.2. Create Interference graphs ------------------------------- Once live ranges are constructed, we can build interference graphs for each register class. Though each register class must have a separate interference graph, building all interference graphs is performed in one pass. Also, the adjacency list for each live range is built in this phase. Consequently, each register class has an interference graph (which is a bit matrix) and each LiveRange has an adjacency list to record its neighbors. Live variable info is used for finding the interferences. See IGNode.h, InterferenceGraph.h (and IGNode.h, InterferenceGraph.h) for data structures and PhyRegAlloc::createIGNodeListsAndIGs() for the starting point for interference graph construction. 6.3. Coalescing live ranges --------------------------- We coalesce live ranges to reduce the number of live ranges. See LiveRangeInfo.h (and LiveRangeInfo.cpp). The entire algorithm for coalesing is given in LiveRangeInfo::coalesceLRs(). 6.4. Color all live ranges in each RegClass using graph coloring algo --------------------------------------------------------------------- Each register class is colored separately using the graph coloring algo. When assigning colors, preference is given to live ranges with suggested colors so that if such a live range receives a color (i.e., not spilled), then we try to assign the color suggested for that live range. When this phase is complete it is possible that some live ranges do not have colors (i.e., those that must be spilled). 6.5. Insert additional (machine specific) code for calls/returns/incoming args ------------------------------------------------------------------------------ This code is machine specific. Currently, the code for Sparc is implemented in SparcRegInfo.cpp. This code is more complex because of the complex requirements of assigning some values to special registers. When a special value as an incoming argument receives a color through the graph coloring alogorithm, we have to make sure that it received the correct color (for instance the first incoming int argument must be colored to %i0 on Sparc). If it didn't receive the correct color, we have to insert instruction to to move the value to the required register. Also, this phase produces the caller saving code. All adition code produced is kept separately until the last phase (see 6.6) 6.6. Update instruction stream and insert spill code ----------------------------------------------------- After we have assigned registers for all values and after we have produced additional code to be inserted before some instructions, we update the machine instruction stream. While we are updating the machine instruction stream, if an instruction referes to a spilled value, we insert spill instructions before/after that instruction. Also, we prepend/append additonal instructions that have been produced for that instruction by the register allocation (e.g., caller saving code) 7. Furture work =============== If it is necessary to port the register allocator to another architecture than Sparc, only the target specific code in ../lib/Target/Sparc needs to be rewritten. Methods defined in class MachineRegInfo must be provided for the new architecure. 7.1 Using ReservedColorList in RegClass ---------------------------------------- The register allocator allows reserving a set of registers - i.e. the reserved registers are not used by the register allocator. Currently, there are no reserved registers. It it is necessary to make some registers unavailable to a particular method, this feature will become handy. To do that, the reserved register list must be passed to the register allocator. See PhyRegAlloc.cpp 7.2 %g registers on Sparc ------------------------- Currently, %g registers are not allocated on Sparc. If it is necessary to allocate these %g registers, the enumeration of registers in SparcIntRegClass in SparcRegClassInfo.h must be changed. %g registers can be easily added as volatile registers just by moving them above in the eneumeration - see SparcRegClassInfo.h