Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 1 | =================== |
| 2 | Register Allocation |
| 3 | =================== |
| 4 | |
| 5 | |
| 6 | 1. Introduction |
| 7 | =============== |
| 8 | |
| 9 | Purpose: This file contains implementation information about register |
| 10 | allocation. |
| 11 | Author : Ruchira Sasanka |
| 12 | Date : Dec 8, 2001 |
| 13 | |
| 14 | |
| 15 | 2. Entry Point |
| 16 | ============== |
| 17 | class PhyRegAlloc (PhyRegAlloc.h) is the main class for the register |
| 18 | allocation. PhyRegAlloc::allocateRegisters() starts the register allocation |
| 19 | and contains the major steps for register allocation. |
| 20 | |
| 21 | 2. Usage |
| 22 | ======== |
| 23 | Register allocation must be done as: |
| 24 | |
| 25 | MethodLiveVarInfo LVI(*MethodI ); // compute LV info |
| 26 | LVI.analyze(); |
| 27 | |
| 28 | TargetMachine &target = .... // target description |
| 29 | |
| 30 | |
| 31 | PhyRegAlloc PRA(*MethodI, target, &LVI); // allocate regs |
| 32 | PRA.allocateRegisters(); |
| 33 | |
| 34 | |
| 35 | 4. Input and Preconditions |
| 36 | ========================== |
Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 37 | Register allocation is done using machine instructions. The constructor |
| 38 | to the class takes a pointer to a method, a target machine description and |
| 39 | a live variable information for the method. |
| 40 | |
| 41 | The preconditions are: |
| 42 | |
| 43 | 1. Instruction selection is complete (i.e., machine instructions are |
| 44 | generated) for the method before the live variable analysis |
| 45 | |
| 46 | 2. Phi elimination is complete. |
| 47 | |
| 48 | |
| 49 | 5. Assumptions |
| 50 | ============== |
| 51 | |
Ruchira Sasanka | 42bd177 | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 52 | All variables (llvm Values) are defined before they are used. However, a |
| 53 | constant may not be defined in the machine instruction stream if it can be |
| 54 | used as an immediate value within a machine instruction. However, register |
| 55 | allocation does not have to worry about immediate constants since they |
| 56 | do not require registers. |
| 57 | |
| 58 | Since an llvm Value has a list of uses associated, it is sufficient to |
| 59 | record only the defs in a Live Range. |
| 60 | |
Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 61 | |
| 62 | |
| 63 | |
| 64 | 6. Overall Design |
| 65 | ================= |
| 66 | There are sperate reigster classes - e.g., Int, Float, |
| 67 | IntConditionCode, FloatConditionCode register classes for Sparc. |
| 68 | |
| 69 | Registerallocation consists of the following main steps: |
| 70 | |
| 71 | 1. Construct Live-ranges & Suggest colors (machine specific) if required |
| 72 | 2. Create Interference graphs |
| 73 | 3. Coalescing live ranges |
| 74 | 4. Color all live ranges in each RegClass using graph coloring algo |
| 75 | 5. Insert additional (machine specific) code for calls/returns/incoming args |
| 76 | 6. Update instruction stream and insert spill code |
| 77 | |
| 78 | All the above methods are called from PhyRegAlloc::allocateRegisters(). |
| 79 | |
Ruchira Sasanka | 42bd177 | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 80 | All steps above except step 5 and suggesting colors in step 1 are indepenedent |
| 81 | of a particular target architecture. Targer independent code is availble in |
| 82 | ../lib/CodeGen/RegAlloc. Target specific code for Sparc is available in |
| 83 | ../lib/Target/Sparc. |
| 84 | |
Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 85 | |
| 86 | 6.1. Construct Live-ranges & Suggest colors (machine specific) if required |
| 87 | -------------------------------------------------------------------------- |
| 88 | Live range construction is done using machine instructions. Since there must |
| 89 | be at least one definition for each variable in the machine instruction, we |
| 90 | consider only definitions in creating live ranges. After live range |
| 91 | construction is complete, there is a live range for all variables defined in |
| 92 | the instruction stream. Note however that, live ranges are not constructed for |
| 93 | constants which are not defined in the instruction stream. |
| 94 | |
| 95 | A LiveRange is a set of Values (only defs) in that live range. Live range |
| 96 | construction is done in combination for all register classes. All the live |
| 97 | ranges for a method are entered to a LiveRangeMap which can be accessed using |
| 98 | any Value in the LiveRange. |
| 99 | |
| 100 | After live ranges have been constructed, we call machine specific code to |
| 101 | suggest colors for speical live ranges. For instance, incoming args, call args, |
| 102 | return values must be placed in special registers for most architectures. By |
| 103 | suggesting colors for such special live ranges before we do the actual register |
| 104 | allocation using graph coloring, the graph coloring can try its best to assign |
| 105 | the required color for such special live ranges. This will reduce unnecessary |
| 106 | copy instructions needed to move values to special registers. However, there |
| 107 | is no guarantee that a live range will receive its suggested color. If the |
| 108 | live range does not receive the suggested color, we have to insert explicit |
| 109 | copy instructions to move the value into requred registers and its done in |
| 110 | step 5 above. |
| 111 | |
| 112 | See LiveRange.h, LiveRangeInfo.h (and LiveRange.cpp, LiveRangeInfo.cpp) for |
| 113 | algorithms and details. See SparcRegInfo.cpp for suggesting colors for |
| 114 | incoming/call arguments and return values. |
| 115 | |
| 116 | |
| 117 | 6.2. Create Interference graphs |
| 118 | ------------------------------- |
| 119 | Once live ranges are constructed, we can build interference graphs for each |
Misha Brukman | bc0e998 | 2003-07-14 17:20:40 +0000 | [diff] [blame] | 120 | register class. Though each register class must have a separate interference |
Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 121 | graph, building all interference graphs is performed in one pass. Also, the |
| 122 | adjacency list for each live range is built in this phase. Consequently, each |
| 123 | register class has an interference graph (which is a bit matrix) and each |
| 124 | LiveRange has an adjacency list to record its neighbors. Live variable info |
| 125 | is used for finding the interferences. |
| 126 | |
| 127 | See IGNode.h, InterferenceGraph.h (and IGNode.h, InterferenceGraph.h) for |
| 128 | data structures and PhyRegAlloc::createIGNodeListsAndIGs() for the starting |
| 129 | point for interference graph construction. |
| 130 | |
| 131 | |
| 132 | 6.3. Coalescing live ranges |
| 133 | --------------------------- |
| 134 | We coalesce live ranges to reduce the number of live ranges. |
| 135 | |
| 136 | See LiveRangeInfo.h (and LiveRangeInfo.cpp). The entire algorithm for |
| 137 | coalesing is given in LiveRangeInfo::coalesceLRs(). |
| 138 | |
| 139 | |
| 140 | 6.4. Color all live ranges in each RegClass using graph coloring algo |
| 141 | --------------------------------------------------------------------- |
Misha Brukman | bc0e998 | 2003-07-14 17:20:40 +0000 | [diff] [blame] | 142 | Each register class is colored separately using the graph coloring algo. When |
Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 143 | assigning colors, preference is given to live ranges with suggested colors |
| 144 | so that if such a live range receives a color (i.e., not spilled), then |
| 145 | we try to assign the color suggested for that live range. When this phase |
| 146 | is complete it is possible that some live ranges do not have colors (i.e., |
| 147 | those that must be spilled). |
| 148 | |
| 149 | |
| 150 | 6.5. Insert additional (machine specific) code for calls/returns/incoming args |
| 151 | ------------------------------------------------------------------------------ |
| 152 | This code is machine specific. Currently, the code for Sparc is implemented |
| 153 | in SparcRegInfo.cpp. This code is more complex because of the complex |
| 154 | requirements of assigning some values to special registers. When a special |
| 155 | value as an incoming argument receives a color through the graph coloring |
| 156 | alogorithm, we have to make sure that it received the correct color (for |
| 157 | instance the first incoming int argument must be colored to %i0 on Sparc). If |
| 158 | it didn't receive the correct color, we have to insert instruction to to move |
| 159 | the value to the required register. Also, this phase produces the caller |
Misha Brukman | bc0e998 | 2003-07-14 17:20:40 +0000 | [diff] [blame] | 160 | saving code. All adition code produced is kept separately until the last |
Ruchira Sasanka | 299f6a9 | 2001-12-09 20:21:49 +0000 | [diff] [blame] | 161 | phase (see 6.6) |
| 162 | |
| 163 | |
| 164 | 6.6. Update instruction stream and insert spill code |
| 165 | ----------------------------------------------------- |
| 166 | After we have assigned registers for all values and after we have produced |
| 167 | additional code to be inserted before some instructions, we update the |
| 168 | machine instruction stream. While we are updating the machine instruction |
| 169 | stream, if an instruction referes to a spilled value, we insert spill |
| 170 | instructions before/after that instruction. Also, we prepend/append additonal |
| 171 | instructions that have been produced for that instruction by the register |
| 172 | allocation (e.g., caller saving code) |
| 173 | |
| 174 | |
Ruchira Sasanka | 42bd177 | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 175 | 7. Furture work |
Ruchira Sasanka | 304e707 | 2002-01-08 16:31:28 +0000 | [diff] [blame] | 176 | =============== |
Ruchira Sasanka | 42bd177 | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 177 | If it is necessary to port the register allocator to another architecture |
| 178 | than Sparc, only the target specific code in ../lib/Target/Sparc needs to |
| 179 | be rewritten. Methods defined in class MachineRegInfo must be provided for |
| 180 | the new architecure. |
| 181 | |
Ruchira Sasanka | 304e707 | 2002-01-08 16:31:28 +0000 | [diff] [blame] | 182 | 7.1 Using ReservedColorList in RegClass |
| 183 | ---------------------------------------- |
| 184 | The register allocator allows reserving a set of registers - i.e. the reserved |
| 185 | registers are not used by the register allocator. Currently, there are no |
| 186 | reserved registers. It it is necessary to make some registers unavailable to |
| 187 | a particular method, this feature will become handy. To do that, the reserved |
| 188 | register list must be passed to the register allocator. See PhyRegAlloc.cpp |
| 189 | |
| 190 | |
| 191 | 7.2 %g registers on Sparc |
| 192 | ------------------------- |
| 193 | Currently, %g registers are not allocated on Sparc. If it is necessary to |
| 194 | allocate these %g registers, the enumeration of registers in SparcIntRegClass |
| 195 | in SparcRegClassInfo.h must be changed. %g registers can be easily added as |
| 196 | volatile registers just by moving them above in the eneumeration - see |
| 197 | SparcRegClassInfo.h |