lib/CodeGen/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     cerr << "\nConstrained IG Node found !@!" <<  IGNodeSpill->getIndex();
  86
  87   } while( NeedMoreSpills );            // repeat until we have pushed all
  88
  89 }
  90
  91
  92
  93
  94 //--------------------------------------------------------------------------
  95 // This method goes thru all IG nodes in the IGNodeList of an IG of a
  96 // register class and push any unconstrained IG node left (that is not
  97 // already pushed)
  98 //--------------------------------------------------------------------------
  99
 100 bool  RegClass::pushUnconstrainedIGNodes()
 101 {
 102   // # of LRs for this reg class
 103   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 104   bool pushedall = true;
 105
 106   // a pass over IGNodeList
 107   for( unsigned i =0; i  < IGNodeListSize; i++) {
 108
 109     // get IGNode i from IGNodeList
 110     IGNode *IGNode = IG.getIGNodeList()[i];
 111
 112     if( !IGNode )                        // can be null due to merging
 113       continue;
 114
 115     // if already pushed on stack, continue. This can happen since this
 116     // method can be called repeatedly until all constrained nodes are
 117     // pushed
 118     if( IGNode->isOnStack() )
 119       continue;
 120                                         // if the degree of IGNode is lower
 121     if( (unsigned) IGNode->getCurDegree()  < MRC->getNumOfAvailRegs() ) {
 122       IGNodeStack.push( IGNode );       // push IGNode on to the stack
 123       IGNode->pushOnStack();            // set OnStack and dec deg of neighs
 124
 125       if (DEBUG_RA > 1) {
 126         cout << " pushed un-constrained IGNode " << IGNode->getIndex() ;
 127         cout << " on to stack" << endl;
 128       }
 129     }
 130     else pushedall = false;             // we didn't push all live ranges
 131
 132   } // for
 133
 134   // returns true if we pushed all live ranges - else false
 135   return pushedall;
 136 }
 137
 138
 139
 140
 141 IGNode * RegClass::getIGNodeWithMinSpillCost()
 142 {
 143   IGNode *IGNode=NULL;
 144   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 145
 146   // pass over IGNodeList
 147   for( unsigned int i =0; i  < IGNodeListSize; i++) {
 148     IGNode = IG.getIGNodeList()[i];
 149
 150     if( ! IGNode )                      // can be null due to merging
 151       continue;
 152
 153     // return the first IGNode ########## Change this #######
 154     if( ! IGNode->isOnStack() ) return IGNode;
 155   }
 156
 157   assert(0);
 158   return NULL;
 159 }
 160
 161
 162
 163
 164 void RegClass::colorIGNode(IGNode *const Node)
 165 {
 166
 167   if( ! Node->hasColor() )   {          // not colored as an arg etc.
 168
 169
 170     // init all elements to  false;
 171     for( unsigned  i=0; i < MRC->getNumOfAllRegs(); i++) {
 172       IsColorUsedArr[ i ] = false;
 173     }
 174
 175     // init all reserved_regs to true - we can't use them
 176     for( unsigned i=0; i < ReservedColorList->size() ; i++) {
 177       IsColorUsedArr[ (*ReservedColorList)[i] ] = true;
 178     }
 179
 180     MRC->colorIGNode(Node, IsColorUsedArr);
 181   }
 182   else {
 183     if( DEBUG_RA ) {
 184       cout << " Node " << Node->getIndex();
 185       cout << " already colored with color " << Node->getColor() << endl;
 186     }
 187   }
 188
 189
 190   if( !Node->hasColor() ) {
 191     if( DEBUG_RA ) {
 192       cout << " Node " << Node->getIndex();
 193       cout << " - could not find a color (needs spilling)" << endl;
 194     }
 195   }
 196
 197 }
 198
 199
 200