lib/CodeGen/RegAlloc/RegClass.cpp

   1 //===-- RegClass.cpp -----------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  class RegClass for coloring-based register allocation for LLVM.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "IGNode.h"
  15 #include "RegAllocCommon.h"
  16 #include "RegClass.h"
  17 #include "llvm/Target/TargetRegInfo.h"
  18
  19 //----------------------------------------------------------------------------
  20 // This constructor inits IG. The actual matrix is created by a call to
  21 // createInterferenceGraph() above.
  22 //----------------------------------------------------------------------------
  23 RegClass::RegClass(const Function *M,
  24                    const TargetRegInfo *_MRI_,
  25                    const TargetRegClassInfo *_MRC_)
  26                   :  Meth(M), MRI(_MRI_), MRC(_MRC_),
  27                      RegClassID( _MRC_->getRegClassID() ),
  28                      IG(this), IGNodeStack() {
  29   if (DEBUG_RA >= RA_DEBUG_Interference)
  30     std::cerr << "Created Reg Class: " << RegClassID << "\n";
  31
  32   IsColorUsedArr.resize(MRC->getNumOfAllRegs());
  33 }
  34
  35
  36
  37 //----------------------------------------------------------------------------
  38 // Main entry point for coloring a register class.
  39 //----------------------------------------------------------------------------
  40 void RegClass::colorAllRegs()
  41 {
  42   if (DEBUG_RA >= RA_DEBUG_Coloring)
  43     std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
  44                                         // pre-color IGNodes
  45   pushAllIGNodes();                     // push all IG Nodes
  46
  47   unsigned int StackSize = IGNodeStack.size();
  48   IGNode *CurIGNode;
  49                                         // for all LRs on stack
  50   for (unsigned int IGN=0; IGN < StackSize; IGN++) {
  51     CurIGNode = IGNodeStack.top();      // pop the IGNode on top of stack
  52     IGNodeStack.pop();
  53     colorIGNode (CurIGNode);            // color it
  54   }
  55 }
  56
  57
  58
  59 //----------------------------------------------------------------------------
  60 // The method for pushing all IGNodes on to the stack.
  61 //----------------------------------------------------------------------------
  62 void RegClass::pushAllIGNodes()
  63 {
  64   bool NeedMoreSpills;
  65
  66
  67   IG.setCurDegreeOfIGNodes();           // calculate degree of IGNodes
  68
  69                                         // push non-constrained IGNodes
  70   bool PushedAll  = pushUnconstrainedIGNodes();
  71
  72   if (DEBUG_RA >= RA_DEBUG_Coloring) {
  73     std::cerr << " Puhsed all-unconstrained IGNodes. ";
  74     if( PushedAll ) std::cerr << " No constrained nodes left.";
  75     std::cerr << "\n";
  76   }
  77
  78   if (PushedAll)                       // if NO constrained nodes left
  79     return;
  80
  81
  82   // now, we have constrained nodes. So, push one of them (the one with min
  83   // spill cost) and try to push the others as unConstrained nodes.
  84   // Repeat this.
  85
  86   do {
  87     //get node with min spill cost
  88     IGNode *IGNodeSpill =  getIGNodeWithMinSpillCost();
  89     //  push that node on to stack
  90     IGNodeStack.push(IGNodeSpill);
  91     // set its OnStack flag and decrement degree of neighs
  92     IGNodeSpill->pushOnStack();
  93     // now push NON-constrained ones, if any
  94     NeedMoreSpills = !pushUnconstrainedIGNodes();
  95     if (DEBUG_RA >= RA_DEBUG_Coloring)
  96       std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
  97   } while(NeedMoreSpills);            // repeat until we have pushed all
  98
  99 }
 100
 101
 102
 103
 104 //--------------------------------------------------------------------------
 105 // This method goes thru all IG nodes in the IGNodeList of an IG of a
 106 // register class and push any unconstrained IG node left (that is not
 107 // already pushed)
 108 //--------------------------------------------------------------------------
 109
 110 bool  RegClass::pushUnconstrainedIGNodes()
 111 {
 112   // # of LRs for this reg class
 113   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 114   bool pushedall = true;
 115
 116   // a pass over IGNodeList
 117   for (unsigned i =0; i  < IGNodeListSize; i++) {
 118
 119     // get IGNode i from IGNodeList
 120     IGNode *IGNode = IG.getIGNodeList()[i];
 121
 122     if (!IGNode )                        // can be null due to merging
 123       continue;
 124
 125     // if already pushed on stack, continue. This can happen since this
 126     // method can be called repeatedly until all constrained nodes are
 127     // pushed
 128     if (IGNode->isOnStack() )
 129       continue;
 130                                         // if the degree of IGNode is lower
 131     if ((unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) {
 132       IGNodeStack.push( IGNode );       // push IGNode on to the stack
 133       IGNode->pushOnStack();            // set OnStack and dec deg of neighs
 134
 135       if (DEBUG_RA >= RA_DEBUG_Coloring) {
 136         std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex()
 137                   << " on to stack\n";
 138       }
 139     }
 140     else pushedall = false;             // we didn't push all live ranges
 141
 142   } // for
 143
 144   // returns true if we pushed all live ranges - else false
 145   return pushedall;
 146 }
 147
 148
 149
 150 //----------------------------------------------------------------------------
 151 // Get the IGNode with the minimum spill cost
 152 //----------------------------------------------------------------------------
 153 IGNode * RegClass::getIGNodeWithMinSpillCost() {
 154   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 155   double MinSpillCost = 0;
 156   IGNode *MinCostIGNode = NULL;
 157   bool isFirstNode = true;
 158
 159   // pass over IGNodeList to find the IGNode with minimum spill cost
 160   // among all IGNodes that are not yet pushed on to the stack
 161   for (unsigned int i =0; i  < IGNodeListSize; i++) {
 162     IGNode *IGNode = IG.getIGNodeList()[i];
 163
 164     if (!IGNode)                      // can be null due to merging
 165       continue;
 166
 167     if (!IGNode->isOnStack()) {
 168       double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
 169         (double) (IGNode->getCurDegree() + 1);
 170
 171       if (isFirstNode) {         // for the first IG node
 172         MinSpillCost = SpillCost;
 173         MinCostIGNode = IGNode;
 174         isFirstNode = false;
 175       } else if (MinSpillCost > SpillCost) {
 176         MinSpillCost = SpillCost;
 177         MinCostIGNode = IGNode;
 178       }
 179     }
 180   }
 181
 182   assert (MinCostIGNode && "No IGNode to spill");
 183   return MinCostIGNode;
 184 }
 185
 186
 187 //----------------------------------------------------------------------------
 188 // Color the IGNode using the machine specific code.
 189 //----------------------------------------------------------------------------
 190 void RegClass::colorIGNode(IGNode *const Node) {
 191   if (! Node->hasColor())   {          // not colored as an arg etc.
 192
 193     // init all elements of to  IsColorUsedAr  false;
 194     clearColorsUsed();
 195
 196     // initialize all colors used by neighbors of this node to true
 197     LiveRange *LR = Node->getParentLR();
 198     unsigned NumNeighbors =  Node->getNumOfNeighbors();
 199     for (unsigned n=0; n < NumNeighbors; n++) {
 200       IGNode *NeighIGNode = Node->getAdjIGNode(n);
 201       LiveRange *NeighLR = NeighIGNode->getParentLR();
 202
 203       // Don't use a color if it is in use by the neighbor,
 204       // or is suggested for use by the neighbor,
 205       // markColorsUsed() should be given the color and the reg type for
 206       // LR, not for NeighLR, because it should mark registers used based on
 207       // the type we are looking for, not on the regType for the neighbour.
 208       if (NeighLR->hasColor())
 209         this->markColorsUsed(NeighLR->getColor(),
 210                              MRI->getRegTypeForLR(NeighLR),
 211                              MRI->getRegTypeForLR(LR));  // use LR, not NeighLR
 212       else if (NeighLR->hasSuggestedColor() &&
 213                NeighLR->isSuggestedColorUsable())
 214         this->markColorsUsed(NeighLR->getSuggestedColor(),
 215                              MRI->getRegTypeForLR(NeighLR),
 216                              MRI->getRegTypeForLR(LR));  // use LR, not NeighLR
 217     }
 218
 219     // call the target specific code for coloring
 220     //
 221     MRC->colorIGNode(Node, IsColorUsedArr);
 222   } else {
 223     if (DEBUG_RA >= RA_DEBUG_Coloring) {
 224       std::cerr << " Node " << Node->getIndex();
 225       std::cerr << " already colored with color " << Node->getColor() << "\n";
 226     }
 227   }
 228
 229
 230   if (!Node->hasColor() ) {
 231     if (DEBUG_RA >= RA_DEBUG_Coloring) {
 232       std::cerr << " Node " << Node->getIndex();
 233       std::cerr << " - could not find a color (needs spilling)\n";
 234     }
 235   }
 236 }
 237
 238 void RegClass::printIGNodeList() const {
 239   std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n";
 240   IG.printIGNodeList();
 241 }
 242
 243 void RegClass::printIG() {
 244   std::cerr << "IG for Register Class " << RegClassID << ":" << "\n";
 245   IG.printIG();
 246 }
 247
 248