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