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