lib/Target/SparcV9/RegAlloc/RegClass.cpp

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