lib/Target/SparcV9/RegAlloc/RegClass.cpp

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