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
  38 Register allocation is done using machine instructions. The constructor
  39 to the class takes a pointer to a method, a target machine description and
  40 a live variable information for the method.
  41
  42 The preconditions are:
  43
  44 1. Instruction selection is complete (i.e., machine instructions are
  45    generated) for the method before the live variable analysis
  46
  47 2. Phi elimination is complete.
  48
  49
  50 5. Assumptions
  51 ==============
  52
  53
  54
  55
  56 6. Overall Design
  57 =================
  58 There are sperate reigster classes - e.g., Int, Float,
  59 IntConditionCode, FloatConditionCode register classes for Sparc.
  60
  61 Registerallocation consists of the following main steps:
  62
  63   1. Construct Live-ranges & Suggest colors (machine specific) if required
  64   2. Create Interference graphs
  65   3. Coalescing live ranges
  66   4. Color all live ranges in each RegClass using graph coloring algo
  67   5. Insert additional (machine specific) code for calls/returns/incoming args
  68   6. Update instruction stream and insert spill code
  69
  70 All the above methods are called from  PhyRegAlloc::allocateRegisters().
  71
  72
  73 6.1. Construct Live-ranges & Suggest colors (machine specific) if required
  74 --------------------------------------------------------------------------
  75 Live range construction is done using machine instructions. Since there must
  76 be at least one definition for each variable in the machine instruction, we
  77 consider only definitions in creating live ranges. After live range
  78 construction is complete, there is a live range for all variables defined in
  79 the instruction stream. Note however that, live ranges are not constructed for
  80 constants which are not defined in the instruction stream.
  81
  82 A LiveRange is a set of Values (only defs) in that live range. Live range
  83 construction is done in combination for all register classes. All the live
  84 ranges for a method are entered to a LiveRangeMap which can be accessed using
  85 any Value in the LiveRange.
  86
  87 After live ranges have been constructed, we call machine specific code to
  88 suggest colors for speical live ranges. For instance, incoming args, call args,
  89 return values must be placed in special registers for most architectures. By
  90 suggesting colors for such special live ranges before we do the actual register
  91 allocation using graph coloring, the graph coloring can try its best to assign
  92 the required color for such special live ranges. This will reduce unnecessary
  93 copy instructions needed to move values to special registers. However, there
  94 is no guarantee that a live range will receive its suggested color. If the
  95 live range does not receive the suggested color, we have to insert explicit
  96 copy instructions to move the value into requred registers and its done in
  97 step 5 above.
  98
  99 See LiveRange.h, LiveRangeInfo.h (and  LiveRange.cpp, LiveRangeInfo.cpp) for
 100 algorithms and details. See SparcRegInfo.cpp for suggesting colors for
 101 incoming/call arguments and return values.
 102
 103
 104 6.2. Create Interference graphs
 105 -------------------------------
 106 Once live ranges are constructed, we can build interference graphs for each
 107 register class. Though each register class must have a seperate interference
 108 graph, building all interference graphs is performed in one pass. Also, the
 109 adjacency list for each live range is built in this phase. Consequently, each
 110 register class has an interference graph (which is a bit matrix) and each
 111 LiveRange has an adjacency list to record its neighbors. Live variable info
 112 is used for finding the interferences.
 113
 114 See IGNode.h, InterferenceGraph.h (and IGNode.h, InterferenceGraph.h) for
 115 data structures and PhyRegAlloc::createIGNodeListsAndIGs() for the starting
 116 point for interference graph construction.
 117
 118
 119 6.3. Coalescing live ranges
 120 ---------------------------
 121 We coalesce live ranges to reduce the number of live ranges.
 122
 123 See  LiveRangeInfo.h (and LiveRangeInfo.cpp). The entire algorithm for
 124 coalesing is given in LiveRangeInfo::coalesceLRs().
 125
 126
 127 6.4. Color all live ranges in each RegClass using graph coloring algo
 128 ---------------------------------------------------------------------
 129 Each register class is colored seperately using the graph coloring algo. When
 130 assigning colors, preference is given to live ranges with suggested colors
 131 so that if such a live range receives a color (i.e., not spilled), then
 132 we try to assign the color suggested for that live range. When this phase
 133 is complete it is possible that some live ranges do not have colors (i.e.,
 134 those that must be spilled).
 135
 136
 137 6.5. Insert additional (machine specific) code for calls/returns/incoming args
 138 ------------------------------------------------------------------------------
 139 This code is machine specific. Currently, the code for Sparc is implemented
 140 in SparcRegInfo.cpp. This code is more complex because of the complex
 141 requirements of assigning some values to special registers. When a special
 142 value as an incoming argument receives a color through the graph coloring
 143 alogorithm, we have to make sure that it received the correct color (for
 144 instance the first incoming int argument must be colored to %i0 on Sparc). If
 145 it didn't receive the correct color, we have to insert instruction to to move
 146 the value to the required register. Also, this phase produces the caller
 147 saving code. All adition code produced is kept seperately until the last
 148 phase (see 6.6)
 149
 150
 151 6.6. Update instruction stream  and insert spill code
 152 -----------------------------------------------------
 153 After we have assigned registers for all values and after we have produced
 154 additional code to be inserted before some instructions, we update the
 155 machine instruction stream. While we are updating the machine instruction
 156 stream, if an instruction referes to a spilled value, we insert spill
 157 instructions before/after that instruction. Also, we prepend/append additonal
 158 instructions that have been produced for that instruction by the register
 159 allocation (e.g., caller saving code)
 160
 161