aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAlloc/RegClass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/RegAlloc/RegClass.cpp')
-rw-r--r--lib/CodeGen/RegAlloc/RegClass.cpp250
1 files changed, 0 insertions, 250 deletions
diff --git a/lib/CodeGen/RegAlloc/RegClass.cpp b/lib/CodeGen/RegAlloc/RegClass.cpp
deleted file mode 100644
index 9af87ba0e8..0000000000
--- a/lib/CodeGen/RegAlloc/RegClass.cpp
+++ /dev/null
@@ -1,250 +0,0 @@
-//===-- 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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-30 08:03:04 +0000