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