-#include "llvm/CodeGen/InterferenceGraph.h"
-
+//===-- InterferenceGraph.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.
+//
+//===----------------------------------------------------------------------===//
+//
+// Interference graph for coloring-based register allocation for LLVM.
+//
+//===----------------------------------------------------------------------===//
+
+#include "IGNode.h"
+#include "InterferenceGraph.h"
+#include "RegAllocCommon.h"
+#include "Support/STLExtras.h"
+#include <algorithm>
+
+// for asserting this IG node is infact in the IGNodeList of this class
+inline static void assertIGNode(const InterferenceGraph *IG,
+ const IGNode *Node) {
+ assert(IG->getIGNodeList()[Node->getIndex()] == Node);
+}
-InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
- IGNodeList()
-{
+//-----------------------------------------------------------------------------
+// Constructor: Records the RegClass and initalizes IGNodeList.
+// The matrix is NOT yet created by the constructor. Call createGraph()
+// to create it after adding all IGNodes to the IGNodeList.
+//-----------------------------------------------------------------------------
+InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC) {
IG = NULL;
Size = 0;
- if( DEBUG_RA) {
- cout << "Interference graph created!" << endl;
- }
+ if( DEBUG_RA >= RA_DEBUG_Interference)
+ std::cerr << "Interference graph created!\n";
}
-InterferenceGraph:: ~InterferenceGraph() { // destructor
- if( IG )
- delete []IG;
- }
+//-----------------------------------------------------------------------------
+// destructor. Deletes the bit matrix and all IGNodes
+//-----------------------------------------------------------------------------
+InterferenceGraph:: ~InterferenceGraph() {
+ // delete the matrix
+ for(unsigned int r=0; r < IGNodeList.size(); ++r)
+ delete[] IG[r];
+ delete[] IG;
+ // delete all IGNodes in the IGNodeList
+ for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>);
+}
+
+//-----------------------------------------------------------------------------
+// Creates (dynamically allocates) the bit matrix necessary to hold the
+// interference graph.
+//-----------------------------------------------------------------------------
void InterferenceGraph::createGraph()
{
Size = IGNodeList.size();
- IG = (char **) new char *[Size];
+ IG = new char*[Size];
for( unsigned int r=0; r < Size; ++r)
IG[r] = new char[Size];
// init IG matrix
for(unsigned int i=0; i < Size; i++)
- for( unsigned int j=0; j < Size ; j++)
+ for(unsigned int j=0; j < Size; j++)
IG[i][j] = 0;
}
-
-
+//-----------------------------------------------------------------------------
+// creates a new IGNode for the given live range and add to IG
+//-----------------------------------------------------------------------------
void InterferenceGraph::addLRToIG(LiveRange *const LR)
{
- IGNode *Node = new IGNode(LR, IGNodeList.size() );
- IGNodeList.push_back( Node );
- //Node->setRegClass( RegCl );
+ IGNodeList.push_back(new IGNode(LR, IGNodeList.size()));
}
+//-----------------------------------------------------------------------------
+// set interference for two live ranges
// update both the matrix and AdjLists of nodes.
// If there is already an interference between LR1 and LR2, adj lists
// are not updated. LR1 and LR2 must be distinct since if not, it suggests
// that there is some wrong logic in some other method.
-
+//-----------------------------------------------------------------------------
void InterferenceGraph::setInterference(const LiveRange *const LR1,
const LiveRange *const LR2 ) {
assert(LR1 != LR2);
- IGNode *const IGNode1 = LR1->getUserIGNode();
- IGNode *const IGNode2 = LR2->getUserIGNode();
+ IGNode *IGNode1 = LR1->getUserIGNode();
+ IGNode *IGNode2 = LR2->getUserIGNode();
- if( DEBUG_RA) {
- assertIGNode( IGNode1 );
- assertIGNode( IGNode2 );
- }
+ assertIGNode(this, IGNode1);
+ assertIGNode(this, IGNode2);
- const unsigned int row = IGNode1->getIndex();
- const unsigned int col = IGNode2->getIndex();
+ unsigned row = IGNode1->getIndex();
+ unsigned col = IGNode2->getIndex();
char *val;
- if( DEBUG_RA > 1)
- cout << "setting intf for: [" << row << "][" << col << "]" << endl;
+ if( DEBUG_RA >= RA_DEBUG_Interference)
+ std::cerr << "setting intf for: [" << row << "][" << col << "]\n";
( row > col) ? val = &IG[row][col]: val = &IG[col][row];
if( ! (*val) ) { // if this interf is not previously set
-
*val = 1; // add edges between nodes
IGNode1->addAdjIGNode( IGNode2 );
IGNode2->addAdjIGNode( IGNode1 );
}
-
+//----------------------------------------------------------------------------
+// return whether two live ranges interfere
+//----------------------------------------------------------------------------
unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
- const LiveRange *const LR2 ) const {
-
+ const LiveRange *const LR2) const {
assert(LR1 != LR2);
-
- if( DEBUG_RA) {
- assertIGNode( LR1->getUserIGNode() );
- assertIGNode( LR2->getUserIGNode() );
- }
+ assertIGNode(this, LR1->getUserIGNode());
+ assertIGNode(this, LR2->getUserIGNode());
const unsigned int row = LR1->getUserIGNode()->getIndex();
const unsigned int col = LR2->getUserIGNode()->getIndex();
char ret;
- ( row > col) ? (ret = IG[row][col]) : (ret = IG[col][row]) ;
+ if (row > col)
+ ret = IG[row][col];
+ else
+ ret = IG[col][row];
return ret;
}
-
+//----------------------------------------------------------------------------
// Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode.
// Then the IGNode2L will be deleted. Necessary for coalescing.
// IMPORTANT: The live ranges are NOT merged by this method. Use
// LiveRangeInfo::unionAndUpdateLRs for that purpose.
+//----------------------------------------------------------------------------
-void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *const LR1,
- LiveRange *const LR2 ) {
+void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1,
+ LiveRange *LR2) {
assert( LR1 != LR2); // cannot merge the same live range
IGNode *const DestNode = LR1->getUserIGNode();
IGNode *SrcNode = LR2->getUserIGNode();
- assertIGNode( DestNode );
- assertIGNode( SrcNode );
+ assertIGNode(this, DestNode);
+ assertIGNode(this, SrcNode);
- if( DEBUG_RA > 1) {
- cout << "Merging LRs: \""; LR1->printSet();
- cout << "\" and \""; LR2->printSet();
- cout << "\"" << endl;
+ if( DEBUG_RA >= RA_DEBUG_Interference) {
+ std::cerr << "Merging LRs: \""; printSet(*LR1);
+ std::cerr << "\" and \""; printSet(*LR2);
+ std::cerr << "\"\n";
}
unsigned SrcDegree = SrcNode->getNumOfNeighbors();
setInterference(LR1, LROfNeigh );
}
- //cout<< " #Neighs - Neigh: ["<< NeighNode->getIndex()<< "] ";
- //cout << NeighNode->getNumOfNeighbors();
- //cout << " Dest: [" << DestNode->getIndex() << "] ";
- //cout << DestNode->getNumOfNeighbors() << endl;
-
}
IGNodeList[ SrcInd ] = NULL;
}
-
+//----------------------------------------------------------------------------
// must be called after modifications to the graph are over but before
// pushing IGNodes on to the stack for coloring.
-
+//----------------------------------------------------------------------------
void InterferenceGraph::setCurDegreeOfIGNodes()
{
unsigned Size = IGNodeList.size();
//--------------------- debugging (Printing) methods -----------------------
-
-void InterferenceGraph::printIG() const
-{
-
- for(unsigned int i=0; i < Size; i++) {
-
+//----------------------------------------------------------------------------
+// Print the IGnodes
+//----------------------------------------------------------------------------
+void InterferenceGraph::printIG() const {
+ for(unsigned i=0; i < Size; i++) {
const IGNode *const Node = IGNodeList[i];
- if( ! Node )
- continue; // skip empty rows
-
- cout << " [" << i << "] ";
+ if(Node) {
+ std::cerr << " [" << i << "] ";
- for( unsigned int j=0; j < Size; j++) {
- if( j >= i) break;
- if( IG[i][j] ) cout << "(" << i << "," << j << ") ";
- }
- cout << endl;
+ for( unsigned int j=0; j < Size; j++)
+ if(IG[i][j])
+ std::cerr << "(" << i << "," << j << ") ";
+ std::cerr << "\n";
}
+ }
}
-
-void InterferenceGraph::printIGNodeList() const
-{
- vector<IGNode *>::const_iterator IGIt = IGNodeList.begin(); // hash map iter
-
+//----------------------------------------------------------------------------
+// Print the IGnodes in the IGNode List
+//----------------------------------------------------------------------------
+void InterferenceGraph::printIGNodeList() const {
for(unsigned i=0; i < IGNodeList.size() ; ++i) {
-
const IGNode *const Node = IGNodeList[i];
- if( ! Node )
- continue;
-
- cout << " [" << Node->getIndex() << "] ";
- (Node->getParentLR())->printSet();
- //int Deg = Node->getCurDegree();
- cout << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">" << endl;
-
+ if (Node) {
+ std::cerr << " [" << Node->getIndex() << "] ";
+ printSet(*Node->getParentLR());
+ //int Deg = Node->getCurDegree();
+ std::cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n";
+ }
}
}
-
-
projects / oota-llvm.git / blobdiff