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 IGs ..." << endl;
  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   IGNode *IGNodeSpill, *IGNode;
  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 IGNode with min spill cost
  74     IGNodeSpill = getIGNodeWithMinSpillCost();
  75
  76     //  push IGNode on to stack
  77     IGNodeStack.push( IGNodeSpill );
  78
  79     // set OnStack flag and decrement degree of neighs
  80     IGNode->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
  94 bool  RegClass::pushUnconstrainedIGNodes()
  95 {
  96   // # of LRs for this reg class
  97   unsigned int IGNodeListSize = IG.getIGNodeList().size();
  98   bool pushedall = true;
  99
 100   // a pass over IGNodeList
 101   for( unsigned i =0; i  < IGNodeListSize; i++) {
 102
 103     // get IGNode i from IGNodeList
 104     IGNode *IGNode = IG.getIGNodeList()[i];
 105
 106     if( ! IGNode )                      // can be null due to merging
 107         continue;
 108
 109                                         // if the degree of IGNode is lower
 110     if( (unsigned) IGNode->getCurDegree()  < MRC->getNumOfAvailRegs() ) {
 111       IGNodeStack.push( IGNode );       // push IGNode on to the stack
 112       IGNode->pushOnStack();            // set OnStack and dec deg of neighs
 113
 114       if (DEBUG_RA > 1) {
 115         cout << " pushed un-constrained IGNode " << IGNode->getIndex() ;
 116         cout << " on to stack" << endl;
 117       }
 118     }
 119     else pushedall = false;             // we didn't push all live ranges
 120
 121   } // for
 122
 123   // returns true if we pushed all live ranges - else false
 124   return pushedall;
 125 }
 126
 127
 128
 129
 130 IGNode * RegClass::getIGNodeWithMinSpillCost()
 131 {
 132   IGNode *IGNode=NULL;
 133   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 134
 135   // pass over IGNodeList
 136   for( unsigned int i =0; i  < IGNodeListSize; i++) {
 137     IGNode = IG.getIGNodeList()[i];
 138
 139     if( ! IGNode )                      // can be null due to merging
 140       continue;
 141
 142     // return the first IGNode ########## Change this #######
 143     if( ! IGNode->isOnStack() ) return IGNode;
 144   }
 145
 146   assert(0);
 147   return NULL;
 148 }
 149
 150
 151
 152
 153 void RegClass::colorIGNode(IGNode *const Node)
 154 {
 155
 156   if( ! Node->hasColor() )   {          // not colored as an arg etc.
 157
 158
 159     // init all elements to  false;
 160     for( unsigned  i=0; i < MRC->getNumOfAllRegs(); i++) {
 161       IsColorUsedArr[ i ] = false;
 162     }
 163
 164     // init all reserved_regs to true - we can't use them
 165     for( unsigned i=0; i < ReservedColorList->size() ; i++) {
 166       IsColorUsedArr[ (*ReservedColorList)[i] ] = true;
 167     }
 168
 169     MRC->colorIGNode(Node, IsColorUsedArr);
 170   }
 171   else {
 172     cout << " Node " << Node->getIndex();
 173     cout << " already colored with color " << Node->getColor() << endl;
 174   }
 175
 176
 177   if( !Node->hasColor() ) {
 178     cout << " Node " << Node->getIndex();
 179     cout << " - could not find a color (needs spilling)" << endl;
 180   }
 181
 182 }
 183
 184
 185 #if 0
 186
 187   if( DEBUG_RA) {                       // printing code
 188     /*    cout << " Node " << Node->getIndex();
 189     if( Node->hasColor() ) {
 190       cout << " colored with color " << Node->getColor() <<  " [" ;
 191       cout << SparcFloatRegOrder::getRegName(Node->getColor());
 192       if( Node->getTypeID() == Type::DoubleTyID )
 193         cout << "+" << SparcFloatRegOrder::getRegName(Node->getColor()+1);
 194       cout << "]" << endl;
 195     }
 196     */
 197     // MRC->printReg( Node->getParentLR());
 198     cout << " Node " << Node->getIndex();
 199     if( Node->hasColor() )
 200       cout << " colored with color " << Node->getColor() << endl;
 201
 202 #endif