-#include "llvm/CodeGen/RegClass.h"
-
-
+//===-- RegClass.cpp -----------------------------------------------------===//
+//
+// class RegClass for coloring-based register allocation for LLVM.
+//
+//===----------------------------------------------------------------------===//
-RegClass::RegClass(const Method *const M,
- const MachineRegClassInfo *const Mrc,
- const ReservedColorListType *const RCL)
+#include "llvm/CodeGen/RegClass.h"
+#include "llvm/CodeGen/RegAllocCommon.h"
+#include "llvm/CodeGen/IGNode.h"
+using std::cerr;
+
+//----------------------------------------------------------------------------
+// This constructor inits IG. The actual matrix is created by a call to
+// createInterferenceGraph() above.
+//----------------------------------------------------------------------------
+RegClass::RegClass(const Function *M,
+ const MachineRegClassInfo *Mrc,
+ const ReservedColorListType *RCL)
: Meth(M), MRC(Mrc), RegClassID( Mrc->getRegClassID() ),
- IG(this), IGNodeStack(), ReservedColorList(RCL)
-{
- if( DEBUG_RA)
- cout << "Created Reg Class: " << RegClassID << endl;
+ IG(this), IGNodeStack(), ReservedColorList(RCL) {
+ if( DEBUG_RA >= RA_DEBUG_Interference)
+ cerr << "Created Reg Class: " << RegClassID << "\n";
- // This constructor inits IG. The actual matrix is created by a call to
- // createInterferenceGraph() above.
-
- IsColorUsedArr = new bool[ Mrc->getNumOfAllRegs() ];
+ IsColorUsedArr.resize(Mrc->getNumOfAllRegs());
}
+//----------------------------------------------------------------------------
+// Main entry point for coloring a register class.
+//----------------------------------------------------------------------------
void RegClass::colorAllRegs()
{
- if(DEBUG_RA) cout << "Coloring IGs ..." << endl;
+ if(DEBUG_RA >= RA_DEBUG_Coloring)
+ cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
- //preColorIGNodes(); // pre-color IGNodes
+ // pre-color IGNodes
pushAllIGNodes(); // push all IG Nodes
unsigned int StackSize = IGNodeStack.size();
IGNode *CurIGNode;
- // for all LRs on stack
+ // for all LRs on stack
for( unsigned int IGN=0; IGN < StackSize; IGN++) {
CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack
colorIGNode (CurIGNode); // color it
}
-
- // InsertSpillCode; ********* TODO ********
-
}
+//----------------------------------------------------------------------------
+// The method for pushing all IGNodes on to the stack.
+//----------------------------------------------------------------------------
void RegClass::pushAllIGNodes()
{
bool NeedMoreSpills;
- IGNode *IGNodeSpill, *IGNode;
+
IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes
- // push non-constrained IGNodes
+ // push non-constrained IGNodes
bool PushedAll = pushUnconstrainedIGNodes();
- if( DEBUG_RA) {
- cout << " Puhsed all-unconstrained IGNodes. ";
- if( PushedAll ) cout << " No constrained nodes left.";
- cout << endl;
+ if( DEBUG_RA >= RA_DEBUG_Coloring) {
+ cerr << " Puhsed all-unconstrained IGNodes. ";
+ if( PushedAll ) cerr << " No constrained nodes left.";
+ cerr << "\n";
}
if( PushedAll ) // if NO constrained nodes left
// spill cost) and try to push the others as unConstrained nodes.
// Repeat this.
- do{
-
- //get IGNode with min spill cost
- IGNodeSpill = getIGNodeWithMinSpillCost();
-
- // push IGNode on to stack
- IGNodeStack.push( IGNodeSpill );
+ do {
+ //get node with min spill cost
+ //
+ IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
+
+ // push that node on to stack
+ //
+ IGNodeStack.push(IGNodeSpill);
- // set OnStack flag and decrement degree of neighs
- IGNode->pushOnStack();
+ // set its OnStack flag and decrement degree of neighs
+ //
+ IGNodeSpill->pushOnStack();
// now push NON-constrined ones, if any
- NeedMoreSpills = ! pushUnconstrainedIGNodes();
+ //
+ NeedMoreSpills = !pushUnconstrainedIGNodes();
- } while( NeedMoreSpills ); // repeat until we have pushed all
+ if (DEBUG_RA >= RA_DEBUG_Coloring)
+ 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()
{
// get IGNode i from IGNodeList
IGNode *IGNode = IG.getIGNodeList()[i];
- if( ! IGNode ) // can be null due to merging
- continue;
-
+ 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 > 1) {
- cout << " pushed un-constrained IGNode " << IGNode->getIndex() ;
- cout << " on to stack" << endl;
+ if (DEBUG_RA >= RA_DEBUG_Coloring) {
+ cerr << " pushed un-constrained IGNode " << IGNode->getIndex() ;
+ cerr << " on to stack\n";
}
}
else pushedall = false; // we didn't push all live ranges
-
+//----------------------------------------------------------------------------
+// Get the IGNode withe the minimum spill cost
+//----------------------------------------------------------------------------
IGNode * RegClass::getIGNodeWithMinSpillCost()
{
- IGNode *IGNode=NULL;
+
unsigned int IGNodeListSize = IG.getIGNodeList().size();
+ double MinSpillCost = 0;
+ IGNode *MinCostIGNode = NULL;
+ bool isFirstNode = true;
- // pass over IGNodeList
+ // 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 = IG.getIGNodeList()[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);
- // return the first IGNode ########## Change this #######
- if( ! IGNode->isOnStack() ) return IGNode;
+ if( isFirstNode ) { // for the first IG node
+ MinSpillCost = SpillCost;
+ MinCostIGNode = IGNode;
+ isFirstNode = false;
+ }
+
+ else if( MinSpillCost > SpillCost) {
+ MinSpillCost = SpillCost;
+ MinCostIGNode = IGNode;
+ }
+
+ }
}
- assert(0);
- return NULL;
+ 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 to false;
- for( unsigned i=0; i < MRC->getNumOfAllRegs(); i++) {
- IsColorUsedArr[ i ] = false;
- }
+ // init all elements of to IsColorUsedAr false;
+ //
+ for (unsigned i=0; i < MRC->getNumOfAllRegs(); i++)
+ IsColorUsedArr[i] = false;
// init all reserved_regs to true - we can't use them
+ //
for( unsigned i=0; i < ReservedColorList->size() ; i++) {
- IsColorUsedArr[ (*ReservedColorList)[i] ] = true;
+ IsColorUsedArr[(*ReservedColorList)[i]] = true;
}
+ // 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();
+
+ if (NeighLR->hasColor()) { // if has a color
+ IsColorUsedArr[NeighLR->getColor()] = true; // mark color as used
+ } else if (NeighLR->hasSuggestedColor() &&
+ NeighLR->isSuggestedColorUsable()) {
+ // this color is suggested for the neighbour, so don't use it
+ IsColorUsedArr[NeighLR->getSuggestedColor()] = true;
+ }
+ }
+
+ // call the target specific code for coloring
+ //
MRC->colorIGNode(Node, IsColorUsedArr);
}
else {
- cout << " Node " << Node->getIndex();
- cout << " already colored with color " << Node->getColor() << endl;
+ if( DEBUG_RA >= RA_DEBUG_Coloring) {
+ cerr << " Node " << Node->getIndex();
+ cerr << " already colored with color " << Node->getColor() << "\n";
+ }
}
if( !Node->hasColor() ) {
- cout << " Node " << Node->getIndex();
- cout << " - could not find a color (needs spilling)" << endl;
+ if( DEBUG_RA >= RA_DEBUG_Coloring) {
+ cerr << " Node " << Node->getIndex();
+ 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();
+}
-#if 0
- if( DEBUG_RA) { // printing code
- /* cout << " Node " << Node->getIndex();
- if( Node->hasColor() ) {
- cout << " colored with color " << Node->getColor() << " [" ;
- cout << SparcFloatRegOrder::getRegName(Node->getColor());
- if( Node->getTypeID() == Type::DoubleTyID )
- cout << "+" << SparcFloatRegOrder::getRegName(Node->getColor()+1);
- cout << "]" << endl;
- }
- */
- // MRC->printReg( Node->getParentLR());
- cout << " Node " << Node->getIndex();
- if( Node->hasColor() )
- cout << " colored with color " << Node->getColor() << endl;
-
-#endif