LLVM API Documentation

RegClass.cpp

Go to the documentation of this file.
00001 //===-- RegClass.cpp -----------------------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //  class RegClass for coloring-based register allocation for LLVM.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "IGNode.h"
00015 #include "RegAllocCommon.h"
00016 #include "RegClass.h"
00017 #include "../SparcV9RegInfo.h"
00018 #include <iostream>
00019 
00020 namespace llvm {
00021 
00022 //----------------------------------------------------------------------------
00023 // This constructor inits IG. The actual matrix is created by a call to
00024 // createInterferenceGraph() above.
00025 //----------------------------------------------------------------------------
00026 RegClass::RegClass(const Function *M,
00027                    const SparcV9RegInfo *_MRI_,
00028                    const TargetRegClassInfo *_MRC_)
00029                   :  Meth(M), MRI(_MRI_), MRC(_MRC_),
00030                      RegClassID( _MRC_->getRegClassID() ),
00031                      IG(this), IGNodeStack() {
00032   if (DEBUG_RA >= RA_DEBUG_Interference)
00033     std::cerr << "Created Reg Class: " << RegClassID << "\n";
00034 
00035   IsColorUsedArr.resize(MRC->getNumOfAllRegs());
00036 }
00037 
00038 
00039 
00040 //----------------------------------------------------------------------------
00041 // Main entry point for coloring a register class.
00042 //----------------------------------------------------------------------------
00043 void RegClass::colorAllRegs()
00044 {
00045   if (DEBUG_RA >= RA_DEBUG_Coloring)
00046     std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
00047                                         // pre-color IGNodes
00048   pushAllIGNodes();                     // push all IG Nodes
00049 
00050   unsigned int StackSize = IGNodeStack.size();
00051   IGNode *CurIGNode;
00052                                         // for all LRs on stack
00053   for (unsigned int IGN=0; IGN < StackSize; IGN++) {
00054     CurIGNode = IGNodeStack.top();      // pop the IGNode on top of stack
00055     IGNodeStack.pop();
00056     colorIGNode (CurIGNode);            // color it
00057   }
00058 }
00059 
00060 
00061 
00062 //----------------------------------------------------------------------------
00063 // The method for pushing all IGNodes on to the stack.
00064 //----------------------------------------------------------------------------
00065 void RegClass::pushAllIGNodes()
00066 {
00067   bool NeedMoreSpills;
00068 
00069 
00070   IG.setCurDegreeOfIGNodes();           // calculate degree of IGNodes
00071 
00072                                         // push non-constrained IGNodes
00073   bool PushedAll  = pushUnconstrainedIGNodes();
00074 
00075   if (DEBUG_RA >= RA_DEBUG_Coloring) {
00076     std::cerr << " Puhsed all-unconstrained IGNodes. ";
00077     if( PushedAll ) std::cerr << " No constrained nodes left.";
00078     std::cerr << "\n";
00079   }
00080 
00081   if (PushedAll)                       // if NO constrained nodes left
00082     return;
00083 
00084 
00085   // now, we have constrained nodes. So, push one of them (the one with min
00086   // spill cost) and try to push the others as unConstrained nodes.
00087   // Repeat this.
00088 
00089   do {
00090     //get node with min spill cost
00091     IGNode *IGNodeSpill =  getIGNodeWithMinSpillCost();
00092     //  push that node on to stack
00093     IGNodeStack.push(IGNodeSpill);
00094     // set its OnStack flag and decrement degree of neighs
00095     IGNodeSpill->pushOnStack();
00096     // now push NON-constrained ones, if any
00097     NeedMoreSpills = !pushUnconstrainedIGNodes();
00098     if (DEBUG_RA >= RA_DEBUG_Coloring)
00099       std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
00100   } while(NeedMoreSpills);            // repeat until we have pushed all
00101 
00102 }
00103 
00104 
00105 
00106 
00107 //--------------------------------------------------------------------------
00108 // This method goes thru all IG nodes in the IGNodeList of an IG of a
00109 // register class and push any unconstrained IG node left (that is not
00110 // already pushed)
00111 //--------------------------------------------------------------------------
00112 
00113 bool  RegClass::pushUnconstrainedIGNodes()
00114 {
00115   // # of LRs for this reg class
00116   unsigned int IGNodeListSize = IG.getIGNodeList().size();
00117   bool pushedall = true;
00118 
00119   // a pass over IGNodeList
00120   for (unsigned i =0; i  < IGNodeListSize; i++) {
00121 
00122     // get IGNode i from IGNodeList
00123     IGNode *IGNode = IG.getIGNodeList()[i];
00124 
00125     if (!IGNode )                        // can be null due to merging
00126       continue;
00127 
00128     // if already pushed on stack, continue. This can happen since this
00129     // method can be called repeatedly until all constrained nodes are
00130     // pushed
00131     if (IGNode->isOnStack() )
00132       continue;
00133                                         // if the degree of IGNode is lower
00134     if ((unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) {
00135       IGNodeStack.push( IGNode );       // push IGNode on to the stack
00136       IGNode->pushOnStack();            // set OnStack and dec deg of neighs
00137 
00138       if (DEBUG_RA >= RA_DEBUG_Coloring) {
00139         std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex()
00140                   << " on to stack\n";
00141       }
00142     }
00143     else pushedall = false;             // we didn't push all live ranges
00144 
00145   } // for
00146 
00147   // returns true if we pushed all live ranges - else false
00148   return pushedall;
00149 }
00150 
00151 
00152 
00153 //----------------------------------------------------------------------------
00154 // Get the IGNode with the minimum spill cost
00155 //----------------------------------------------------------------------------
00156 IGNode * RegClass::getIGNodeWithMinSpillCost() {
00157   unsigned int IGNodeListSize = IG.getIGNodeList().size();
00158   double MinSpillCost = 0;
00159   IGNode *MinCostIGNode = NULL;
00160   bool isFirstNode = true;
00161 
00162   // pass over IGNodeList to find the IGNode with minimum spill cost
00163   // among all IGNodes that are not yet pushed on to the stack
00164   for (unsigned int i =0; i  < IGNodeListSize; i++) {
00165     IGNode *IGNode = IG.getIGNodeList()[i];
00166 
00167     if (!IGNode)                      // can be null due to merging
00168       continue;
00169 
00170     if (!IGNode->isOnStack()) {
00171       double SpillCost = (double) IGNode->getParentLR()->getSpillCost() /
00172         (double) (IGNode->getCurDegree() + 1);
00173 
00174       if (isFirstNode) {         // for the first IG node
00175         MinSpillCost = SpillCost;
00176         MinCostIGNode = IGNode;
00177         isFirstNode = false;
00178       } else if (MinSpillCost > SpillCost) {
00179         MinSpillCost = SpillCost;
00180         MinCostIGNode = IGNode;
00181       }
00182     }
00183   }
00184 
00185   assert (MinCostIGNode && "No IGNode to spill");
00186   return MinCostIGNode;
00187 }
00188 
00189 
00190 //----------------------------------------------------------------------------
00191 // Color the IGNode using the machine specific code.
00192 //----------------------------------------------------------------------------
00193 void RegClass::colorIGNode(IGNode *const Node) {
00194   if (! Node->hasColor())   {          // not colored as an arg etc.
00195 
00196     // init all elements of to  IsColorUsedAr  false;
00197     clearColorsUsed();
00198 
00199     // initialize all colors used by neighbors of this node to true
00200     V9LiveRange *LR = Node->getParentLR();
00201     unsigned NumNeighbors =  Node->getNumOfNeighbors();
00202     for (unsigned n=0; n < NumNeighbors; n++) {
00203       IGNode *NeighIGNode = Node->getAdjIGNode(n);
00204       V9LiveRange *NeighLR = NeighIGNode->getParentLR();
00205 
00206       // Don't use a color if it is in use by the neighbor,
00207       // or is suggested for use by the neighbor,
00208       // markColorsUsed() should be given the color and the reg type for
00209       // LR, not for NeighLR, because it should mark registers used based on
00210       // the type we are looking for, not on the regType for the neighbour.
00211       if (NeighLR->hasColor())
00212         this->markColorsUsed(NeighLR->getColor(),
00213                              MRI->getRegTypeForLR(NeighLR),
00214                              MRI->getRegTypeForLR(LR));  // use LR, not NeighLR
00215       else if (NeighLR->hasSuggestedColor() &&
00216                NeighLR->isSuggestedColorUsable())
00217         this->markColorsUsed(NeighLR->getSuggestedColor(),
00218                              MRI->getRegTypeForLR(NeighLR),
00219                              MRI->getRegTypeForLR(LR));  // use LR, not NeighLR
00220     }
00221 
00222     // call the target specific code for coloring
00223     //
00224     MRC->colorIGNode(Node, IsColorUsedArr);
00225   } else {
00226     if (DEBUG_RA >= RA_DEBUG_Coloring) {
00227       std::cerr << " Node " << Node->getIndex();
00228       std::cerr << " already colored with color " << Node->getColor() << "\n";
00229     }
00230   }
00231 
00232 
00233   if (!Node->hasColor() ) {
00234     if (DEBUG_RA >= RA_DEBUG_Coloring) {
00235       std::cerr << " Node " << Node->getIndex();
00236       std::cerr << " - could not find a color (needs spilling)\n";
00237     }
00238   }
00239 }
00240 
00241 void RegClass::printIGNodeList() const {
00242   std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n";
00243   IG.printIGNodeList();
00244 }
00245 
00246 void RegClass::printIG() {
00247   std::cerr << "IG for Register Class " << RegClassID << ":" << "\n";
00248   IG.printIG();
00249 }
00250 
00251 } // End llvm namespace