lib/Target/SparcV9/RegAlloc/RegClass.cpp

   1 //===-- RegClass.cpp -----------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  class RegClass for coloring-based register allocation for LLVM.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "RegClass.h"
  15 #include "RegAllocCommon.h"
  16 #include "IGNode.h"
  17 #include "llvm/Target/TargetRegInfo.h"
  18
  19 //----------------------------------------------------------------------------
  20 // This constructor inits IG. The actual matrix is created by a call to
  21 // createInterferenceGraph() above.
  22 //----------------------------------------------------------------------------
  23 RegClass::RegClass(const Function *M,
  24                    const TargetRegInfo *_MRI_,
  25                    const TargetRegClassInfo *_MRC_)
  26                   :  Meth(M), MRI(_MRI_), MRC(_MRC_),
  27                      RegClassID( _MRC_->getRegClassID() ),
  28                      IG(this), IGNodeStack() {
  29   if( DEBUG_RA >= RA_DEBUG_Interference)
  30     std::cerr << "Created Reg Class: " << RegClassID << "\n";
  31
  32   IsColorUsedArr.resize(MRC->getNumOfAllRegs());
  33 }
  34
  35
  36
  37 //----------------------------------------------------------------------------
  38 // Main entry point for coloring a register class.
  39 //----------------------------------------------------------------------------
  40 void RegClass::colorAllRegs()
  41 {
  42   if(DEBUG_RA >= RA_DEBUG_Coloring)
  43     std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
  44
  45                                         // pre-color IGNodes
  46   pushAllIGNodes();                     // push all IG Nodes
  47
  48   unsigned int StackSize = IGNodeStack.size();
  49   IGNode *CurIGNode;
  50
  51                                         // for all LRs on stack
  52   for( unsigned int IGN=0; IGN < StackSize; IGN++) {
  53
  54     CurIGNode = IGNodeStack.top();      // pop the IGNode on top of stack
  55     IGNodeStack.pop();
  56     colorIGNode (CurIGNode);            // color it
  57   }
  58
  59 }
  60
  61
  62
  63 //----------------------------------------------------------------------------
  64 // The method for pushing all IGNodes on to the stack.
  65 //----------------------------------------------------------------------------
  66 void RegClass::pushAllIGNodes()
  67 {
  68   bool NeedMoreSpills;
  69
  70
  71   IG.setCurDegreeOfIGNodes();           // calculate degree of IGNodes
  72
  73                                         // push non-constrained IGNodes
  74   bool PushedAll  = pushUnconstrainedIGNodes();
  75
  76   if( DEBUG_RA >= RA_DEBUG_Coloring) {
  77     std::cerr << " Puhsed all-unconstrained IGNodes. ";
  78     if( PushedAll ) std::cerr << " No constrained nodes left.";
  79     std::cerr << "\n";
  80   }
  81
  82   if( PushedAll )                       // if NO constrained nodes left
  83     return;
  84
  85
  86   // now, we have constrained nodes. So, push one of them (the one with min
  87   // spill cost) and try to push the others as unConstrained nodes.
  88   // Repeat this.
  89
  90   do {
  91     //get node with min spill cost
  92     //
  93     IGNode *IGNodeSpill =  getIGNodeWithMinSpillCost();
  94
  95     //  push that node on to stack
  96     //
  97     IGNodeStack.push(IGNodeSpill);
  98
  99     // set its OnStack flag and decrement degree of neighs
 100     //
 101     IGNodeSpill->pushOnStack();
 102
 103     // now push NON-constrained ones, if any
 104     //
 105     NeedMoreSpills = !pushUnconstrainedIGNodes();
 106
 107     if (DEBUG_RA >= RA_DEBUG_Coloring)
 108       std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
 109
 110   } while(NeedMoreSpills);            // repeat until we have pushed all
 111
 112 }
 113
 114
 115
 116
 117 //--------------------------------------------------------------------------
 118 // This method goes thru all IG nodes in the IGNodeList of an IG of a
 119 // register class and push any unconstrained IG node left (that is not
 120 // already pushed)
 121 //--------------------------------------------------------------------------
 122
 123 bool  RegClass::pushUnconstrainedIGNodes()
 124 {
 125   // # of LRs for this reg class
 126   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 127   bool pushedall = true;
 128
 129   // a pass over IGNodeList
 130   for( unsigned i =0; i  < IGNodeListSize; i++) {
 131
 132     // get IGNode i from IGNodeList
 133     IGNode *IGNode = IG.getIGNodeList()[i];
 134
 135     if( !IGNode )                        // can be null due to merging
 136       continue;
 137
 138     // if already pushed on stack, continue. This can happen since this
 139     // method can be called repeatedly until all constrained nodes are
 140     // pushed
 141     if( IGNode->isOnStack() )
 142       continue;
 143                                         // if the degree of IGNode is lower
 144     if( (unsigned) IGNode->getCurDegree()  < MRC->getNumOfAvailRegs()) {
 145       IGNodeStack.push( IGNode );       // push IGNode on to the stack
 146       IGNode->pushOnStack();            // set OnStack and dec deg of neighs
 147
 148       if (DEBUG_RA >= RA_DEBUG_Coloring) {
 149         std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex()
 150                   << " on to stack\n";
 151       }
 152     }
 153     else pushedall = false;             // we didn't push all live ranges
 154
 155   } // for
 156
 157   // returns true if we pushed all live ranges - else false
 158   return pushedall;
 159 }
 160
 161
 162
 163 //----------------------------------------------------------------------------
 164 // Get the IGNode with the minimum spill cost
 165 //----------------------------------------------------------------------------
 166 IGNode * RegClass::getIGNodeWithMinSpillCost()
 167 {
 168
 169   unsigned int IGNodeListSize = IG.getIGNodeList().size();
 170   double MinSpillCost = 0;
 171   IGNode *MinCostIGNode = NULL;
 172   bool isFirstNode = true;
 173
 174   // pass over IGNodeList to find the IGNode with minimum spill cost
 175   // among all IGNodes that are not yet pushed on to the stack
 176   //
 177   for( unsigned int i =0; i  < IGNodeListSize; i++) {
 178     IGNode *IGNode = IG.getIGNodeList()[i];
 179
 180     if( ! IGNode )                      // can be null due to merging
 181       continue;
 182
 183     if( ! IGNode->isOnStack() ) {
 184
 185       double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
 186         (double) (IGNode->getCurDegree() + 1);
 187
 188       if( isFirstNode ) {         // for the first IG node
 189         MinSpillCost = SpillCost;
 190         MinCostIGNode = IGNode;
 191         isFirstNode = false;
 192       }
 193
 194       else if( MinSpillCost > SpillCost) {
 195         MinSpillCost = SpillCost;
 196         MinCostIGNode = IGNode;
 197       }
 198
 199     }
 200   }
 201
 202   assert( MinCostIGNode && "No IGNode to spill");
 203   return MinCostIGNode;
 204 }
 205
 206
 207
 208 //----------------------------------------------------------------------------
 209 // Color the IGNode using the machine specific code.
 210 //----------------------------------------------------------------------------
 211 void RegClass::colorIGNode(IGNode *const Node)
 212 {
 213
 214   if( ! Node->hasColor() )   {          // not colored as an arg etc.
 215
 216     // init all elements of to  IsColorUsedAr  false;
 217     clearColorsUsed();
 218
 219     // initialize all colors used by neighbors of this node to true
 220     LiveRange *LR = Node->getParentLR();
 221     unsigned NumNeighbors =  Node->getNumOfNeighbors();
 222     for (unsigned n=0; n < NumNeighbors; n++) {
 223       IGNode *NeighIGNode = Node->getAdjIGNode(n);
 224       LiveRange *NeighLR = NeighIGNode->getParentLR();
 225
 226       // Don't use a color if it is in use by the neighbor,
 227       // or is suggested for use by the neighbor,
 228       // markColorsUsed() should be given the color and the reg type for
 229       // LR, not for NeighLR, because it should mark registers used based on
 230       // the type we are looking for, not on the regType for the neighbour.
 231       if (NeighLR->hasColor())
 232         this->markColorsUsed(NeighLR->getColor(),
 233                              MRI->getRegTypeForLR(NeighLR),
 234                              MRI->getRegTypeForLR(LR));  // use LR, not NeighLR
 235       else if (NeighLR->hasSuggestedColor() &&
 236                NeighLR->isSuggestedColorUsable())
 237         this->markColorsUsed(NeighLR->getSuggestedColor(),
 238                              MRI->getRegTypeForLR(NeighLR),
 239                              MRI->getRegTypeForLR(LR));  // use LR, not NeighLR
 240     }
 241
 242     // call the target specific code for coloring
 243     //
 244     MRC->colorIGNode(Node, IsColorUsedArr);
 245   }
 246   else {
 247     if( DEBUG_RA >= RA_DEBUG_Coloring) {
 248       std::cerr << " Node " << Node->getIndex();
 249       std::cerr << " already colored with color " << Node->getColor() << "\n";
 250     }
 251   }
 252
 253
 254   if( !Node->hasColor() ) {
 255     if( DEBUG_RA >= RA_DEBUG_Coloring) {
 256       std::cerr << " Node " << Node->getIndex();
 257       std::cerr << " - could not find a color (needs spilling)\n";
 258     }
 259   }
 260
 261 }
 262
 263 void RegClass::printIGNodeList() const {
 264   std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n";
 265   IG.printIGNodeList();
 266 }
 267
 268 void RegClass::printIG() {
 269   std::cerr << "IG for Register Class " << RegClassID << ":" << "\n";
 270   IG.printIG();
 271 }
 272
 273