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