lib/Target/SparcV9/RegAlloc/RegClass.cpp

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