| =================== |
| 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 seperate 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 seperately 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 seperately 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 |