docs/RegisterAllocatorInfo.txt

   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 ==========================
  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
  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
  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
  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
  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
 120 register class. Though each register class must have a separate interference
 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 ---------------------------------------------------------------------
 142 Each register class is colored separately using the graph coloring algo. When
 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
 160 saving code. All adition code produced is kept separately until the last
 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
 175 7. Furture work
 176 ===============
 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
 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