+//===-- RegClass.cpp -----------------------------------------------------===//
+//
+// class RegClass for coloring-based register allocation for LLVM.
+//
+//===----------------------------------------------------------------------===//
+
#include "llvm/CodeGen/RegClass.h"
-#include <iostream>
+#include "llvm/CodeGen/RegAllocCommon.h"
+#include "llvm/CodeGen/IGNode.h"
using std::cerr;
//----------------------------------------------------------------------------
const ReservedColorListType *RCL)
: Meth(M), MRC(Mrc), RegClassID( Mrc->getRegClassID() ),
IG(this), IGNodeStack(), ReservedColorList(RCL) {
- if( DEBUG_RA)
+ if( DEBUG_RA >= RA_DEBUG_Interference)
cerr << "Created Reg Class: " << RegClassID << "\n";
- IsColorUsedArr = new bool[ Mrc->getNumOfAllRegs() ];
+ IsColorUsedArr.resize(Mrc->getNumOfAllRegs());
}
//----------------------------------------------------------------------------
void RegClass::colorAllRegs()
{
- if(DEBUG_RA) cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
+ if(DEBUG_RA >= RA_DEBUG_Coloring)
+ cerr << "Coloring IG of reg class " << RegClassID << " ...\n";
// pre-color IGNodes
pushAllIGNodes(); // push all IG Nodes
// push non-constrained IGNodes
bool PushedAll = pushUnconstrainedIGNodes();
- if( DEBUG_RA) {
+ if( DEBUG_RA >= RA_DEBUG_Coloring) {
cerr << " Puhsed all-unconstrained IGNodes. ";
if( PushedAll ) cerr << " No constrained nodes left.";
cerr << "\n";
// spill cost) and try to push the others as unConstrained nodes.
// Repeat this.
- do{
-
+ do {
//get node with min spill cost
//
IGNode *IGNodeSpill = getIGNodeWithMinSpillCost();
// push that node on to stack
//
- IGNodeStack.push( IGNodeSpill );
+ IGNodeStack.push(IGNodeSpill);
// set its OnStack flag and decrement degree of neighs
//
// now push NON-constrined ones, if any
//
- NeedMoreSpills = ! pushUnconstrainedIGNodes();
+ NeedMoreSpills = !pushUnconstrainedIGNodes();
- cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
+ if (DEBUG_RA >= RA_DEBUG_Coloring)
+ cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex();
- } while( NeedMoreSpills ); // repeat until we have pushed all
+ } while(NeedMoreSpills); // repeat until we have pushed all
}
IGNodeStack.push( IGNode ); // push IGNode on to the stack
IGNode->pushOnStack(); // set OnStack and dec deg of neighs
- if (DEBUG_RA > 1) {
+ if (DEBUG_RA >= RA_DEBUG_Coloring) {
cerr << " pushed un-constrained IGNode " << IGNode->getIndex() ;
cerr << " on to stack\n";
}
{
unsigned int IGNodeListSize = IG.getIGNodeList().size();
- double MinSpillCost;
+ double MinSpillCost = 0;
IGNode *MinCostIGNode = NULL;
bool isFirstNode = true;
// init all elements of to IsColorUsedAr false;
//
- for( unsigned i=0; i < MRC->getNumOfAllRegs(); i++) {
- IsColorUsedArr[ i ] = 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 {
- if( DEBUG_RA ) {
+ if( DEBUG_RA >= RA_DEBUG_Coloring) {
cerr << " Node " << Node->getIndex();
cerr << " already colored with color " << Node->getColor() << "\n";
}
if( !Node->hasColor() ) {
- if( DEBUG_RA ) {
+ 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();
+}