lib/Target/SparcV9/RegAlloc/RegClass.cpp

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