| //===-- RegClass.cpp -----------------------------------------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // class RegClass for coloring-based register allocation for LLVM. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "IGNode.h" |
| #include "RegAllocCommon.h" |
| #include "RegClass.h" |
| #include "llvm/Target/TargetRegInfo.h" |
| |
| namespace llvm { |
| |
| //---------------------------------------------------------------------------- |
| // This constructor inits IG. The actual matrix is created by a call to |
| // createInterferenceGraph() above. |
| //---------------------------------------------------------------------------- |
| RegClass::RegClass(const Function *M, |
| const TargetRegInfo *_MRI_, |
| const TargetRegClassInfo *_MRC_) |
| : Meth(M), MRI(_MRI_), MRC(_MRC_), |
| RegClassID( _MRC_->getRegClassID() ), |
| IG(this), IGNodeStack() { |
| if (DEBUG_RA >= RA_DEBUG_Interference) |
| std::cerr << "Created Reg Class: " << RegClassID << "\n"; |
| |
| IsColorUsedArr.resize(MRC->getNumOfAllRegs()); |
| } |
| |
| |
| |
| //---------------------------------------------------------------------------- |
| // Main entry point for coloring a register class. |
| //---------------------------------------------------------------------------- |
| void RegClass::colorAllRegs() |
| { |
| if (DEBUG_RA >= RA_DEBUG_Coloring) |
| std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n"; |
| // pre-color IGNodes |
| pushAllIGNodes(); // push all IG Nodes |
| |
| unsigned int StackSize = IGNodeStack.size(); |
| IGNode *CurIGNode; |
| // for all LRs on stack |
| for (unsigned int IGN=0; IGN < StackSize; IGN++) { |
| CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack |
| IGNodeStack.pop(); |
| colorIGNode (CurIGNode); // color it |
| } |
| } |
| |
| |
| |
| //---------------------------------------------------------------------------- |
| // The method for pushing all IGNodes on to the stack. |
| //---------------------------------------------------------------------------- |
| void RegClass::pushAllIGNodes() |
| { |
| bool NeedMoreSpills; |
| |
| |
| IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes |
| |
| // push non-constrained IGNodes |
| bool PushedAll = pushUnconstrainedIGNodes(); |
| |
| if (DEBUG_RA >= RA_DEBUG_Coloring) { |
| std::cerr << " Puhsed all-unconstrained IGNodes. "; |
| if( PushedAll ) std::cerr << " No constrained nodes left."; |
| std::cerr << "\n"; |
| } |
| |
| if (PushedAll) // if NO constrained nodes left |
| return; |
| |
| |
| // now, we have constrained nodes. So, push one of them (the one with min |
| // spill cost) and try to push the others as unConstrained nodes. |
| // Repeat this. |
| |
| do { |
| //get node with min spill cost |
| IGNode *IGNodeSpill = getIGNodeWithMinSpillCost(); |
| // push that node on to stack |
| IGNodeStack.push(IGNodeSpill); |
| // set its OnStack flag and decrement degree of neighs |
| IGNodeSpill->pushOnStack(); |
| // now push NON-constrained ones, if any |
| NeedMoreSpills = !pushUnconstrainedIGNodes(); |
| if (DEBUG_RA >= RA_DEBUG_Coloring) |
| std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex(); |
| } while(NeedMoreSpills); // repeat until we have pushed all |
| |
| } |
| |
| |
| |
| |
| //-------------------------------------------------------------------------- |
| // This method goes thru all IG nodes in the IGNodeList of an IG of a |
| // register class and push any unconstrained IG node left (that is not |
| // already pushed) |
| //-------------------------------------------------------------------------- |
| |
| bool RegClass::pushUnconstrainedIGNodes() |
| { |
| // # of LRs for this reg class |
| unsigned int IGNodeListSize = IG.getIGNodeList().size(); |
| bool pushedall = true; |
| |
| // a pass over IGNodeList |
| for (unsigned i =0; i < IGNodeListSize; i++) { |
| |
| // get IGNode i from IGNodeList |
| IGNode *IGNode = IG.getIGNodeList()[i]; |
| |
| if (!IGNode ) // can be null due to merging |
| continue; |
| |
| // if already pushed on stack, continue. This can happen since this |
| // method can be called repeatedly until all constrained nodes are |
| // pushed |
| if (IGNode->isOnStack() ) |
| continue; |
| // if the degree of IGNode is lower |
| if ((unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) { |
| IGNodeStack.push( IGNode ); // push IGNode on to the stack |
| IGNode->pushOnStack(); // set OnStack and dec deg of neighs |
| |
| if (DEBUG_RA >= RA_DEBUG_Coloring) { |
| std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex() |
| << " on to stack\n"; |
| } |
| } |
| else pushedall = false; // we didn't push all live ranges |
| |
| } // for |
| |
| // returns true if we pushed all live ranges - else false |
| return pushedall; |
| } |
| |
| |
| |
| //---------------------------------------------------------------------------- |
| // Get the IGNode with the minimum spill cost |
| //---------------------------------------------------------------------------- |
| IGNode * RegClass::getIGNodeWithMinSpillCost() { |
| unsigned int IGNodeListSize = IG.getIGNodeList().size(); |
| double MinSpillCost = 0; |
| IGNode *MinCostIGNode = NULL; |
| bool isFirstNode = true; |
| |
| // pass over IGNodeList to find the IGNode with minimum spill cost |
| // among all IGNodes that are not yet pushed on to the stack |
| for (unsigned int i =0; i < IGNodeListSize; i++) { |
| IGNode *IGNode = IG.getIGNodeList()[i]; |
| |
| if (!IGNode) // can be null due to merging |
| continue; |
| |
| if (!IGNode->isOnStack()) { |
| double SpillCost = (double) IGNode->getParentLR()->getSpillCost() / |
| (double) (IGNode->getCurDegree() + 1); |
| |
| if (isFirstNode) { // for the first IG node |
| MinSpillCost = SpillCost; |
| MinCostIGNode = IGNode; |
| isFirstNode = false; |
| } else if (MinSpillCost > SpillCost) { |
| MinSpillCost = SpillCost; |
| MinCostIGNode = IGNode; |
| } |
| } |
| } |
| |
| assert (MinCostIGNode && "No IGNode to spill"); |
| return MinCostIGNode; |
| } |
| |
| |
| //---------------------------------------------------------------------------- |
| // Color the IGNode using the machine specific code. |
| //---------------------------------------------------------------------------- |
| void RegClass::colorIGNode(IGNode *const Node) { |
| if (! Node->hasColor()) { // not colored as an arg etc. |
| |
| // init all elements of to IsColorUsedAr false; |
| clearColorsUsed(); |
| |
| // initialize all colors used by neighbors of this node to true |
| LiveRange *LR = Node->getParentLR(); |
| unsigned NumNeighbors = Node->getNumOfNeighbors(); |
| for (unsigned n=0; n < NumNeighbors; n++) { |
| IGNode *NeighIGNode = Node->getAdjIGNode(n); |
| LiveRange *NeighLR = NeighIGNode->getParentLR(); |
| |
| // Don't use a color if it is in use by the neighbor, |
| // or is suggested for use by the neighbor, |
| // markColorsUsed() should be given the color and the reg type for |
| // LR, not for NeighLR, because it should mark registers used based on |
| // the type we are looking for, not on the regType for the neighbour. |
| if (NeighLR->hasColor()) |
| this->markColorsUsed(NeighLR->getColor(), |
| MRI->getRegTypeForLR(NeighLR), |
| MRI->getRegTypeForLR(LR)); // use LR, not NeighLR |
| else if (NeighLR->hasSuggestedColor() && |
| NeighLR->isSuggestedColorUsable()) |
| this->markColorsUsed(NeighLR->getSuggestedColor(), |
| MRI->getRegTypeForLR(NeighLR), |
| MRI->getRegTypeForLR(LR)); // use LR, not NeighLR |
| } |
| |
| // call the target specific code for coloring |
| // |
| MRC->colorIGNode(Node, IsColorUsedArr); |
| } else { |
| if (DEBUG_RA >= RA_DEBUG_Coloring) { |
| std::cerr << " Node " << Node->getIndex(); |
| std::cerr << " already colored with color " << Node->getColor() << "\n"; |
| } |
| } |
| |
| |
| if (!Node->hasColor() ) { |
| if (DEBUG_RA >= RA_DEBUG_Coloring) { |
| std::cerr << " Node " << Node->getIndex(); |
| std::cerr << " - could not find a color (needs spilling)\n"; |
| } |
| } |
| } |
| |
| void RegClass::printIGNodeList() const { |
| std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n"; |
| IG.printIGNodeList(); |
| } |
| |
| void RegClass::printIG() { |
| std::cerr << "IG for Register Class " << RegClassID << ":" << "\n"; |
| IG.printIG(); |
| } |
| |
| } // End llvm namespace |