diff options
Diffstat (limited to 'lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp')
| -rw-r--r-- | lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp | 248 |
1 files changed, 0 insertions, 248 deletions
diff --git a/lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp b/lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp deleted file mode 100644 index 4b5bffce03..0000000000 --- a/lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp +++ /dev/null @@ -1,248 +0,0 @@ -//===-- 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 "llvm/ADT/STLExtras.h" -#include <algorithm> -#include <iostream> - -namespace llvm { - -// 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); -} - -//----------------------------------------------------------------------------- -// 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 >= RA_DEBUG_Interference) - std::cerr << "Interference graph created!\n"; -} - - -//----------------------------------------------------------------------------- -// 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 = 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++) - IG[i][j] = 0; -} - -//----------------------------------------------------------------------------- -// creates a new IGNode for the given live range and add to IG -//----------------------------------------------------------------------------- -void InterferenceGraph::addLRToIG(V9LiveRange *const LR) -{ - 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 V9LiveRange *const LR1, - const V9LiveRange *const LR2 ) { - assert(LR1 != LR2); - - IGNode *IGNode1 = LR1->getUserIGNode(); - IGNode *IGNode2 = LR2->getUserIGNode(); - - assertIGNode(this, IGNode1); - assertIGNode(this, IGNode2); - - unsigned row = IGNode1->getIndex(); - unsigned col = IGNode2->getIndex(); - - char *val; - - 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 V9LiveRange *const LR1, - const V9LiveRange *const LR2) - const { - assert(LR1 != LR2); - assertIGNode(this, LR1->getUserIGNode()); - assertIGNode(this, LR2->getUserIGNode()); - - const unsigned int row = LR1->getUserIGNode()->getIndex(); - const unsigned int col = LR2->getUserIGNode()->getIndex(); - - char ret; - 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 V9LiveRange *LR1, - V9LiveRange *LR2) { - - assert( LR1 != LR2); // cannot merge the same live range - - IGNode *const DestNode = LR1->getUserIGNode(); - IGNode *SrcNode = LR2->getUserIGNode(); - - assertIGNode(this, DestNode); - assertIGNode(this, SrcNode); - - if( DEBUG_RA >= RA_DEBUG_Interference) { - std::cerr << "Merging LRs: \"" << *LR1 << "\" and \"" << *LR2 << "\"\n"; - } - - unsigned SrcDegree = SrcNode->getNumOfNeighbors(); - const unsigned SrcInd = SrcNode->getIndex(); - - - // for all neighs of SrcNode - for(unsigned i=0; i < SrcDegree; i++) { - IGNode *NeighNode = SrcNode->getAdjIGNode(i); - - V9LiveRange *const LROfNeigh = NeighNode->getParentLR(); - - // delete edge between src and neigh - even neigh == dest - NeighNode->delAdjIGNode(SrcNode); - - // set the matrix posn to 0 betn src and neigh - even neigh == dest - const unsigned NInd = NeighNode->getIndex(); - ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ; - - - if( LR1 != LROfNeigh) { // if the neigh != dest - - // add edge betwn Dest and Neigh - if there is no current edge - setInterference(LR1, LROfNeigh ); - } - - } - - IGNodeList[ SrcInd ] = NULL; - - // SrcNode is no longer necessary - LR2 must be deleted by the caller - delete( SrcNode ); - -} - - -//---------------------------------------------------------------------------- -// 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(); - - for( unsigned i=0; i < Size; i++) { - IGNode *Node = IGNodeList[i]; - if( Node ) - Node->setCurDegree(); - } -} - - - - - -//--------------------- debugging (Printing) methods ----------------------- - -//---------------------------------------------------------------------------- -// Print the IGnodes -//---------------------------------------------------------------------------- -void InterferenceGraph::printIG() const { - for(unsigned i=0; i < Size; i++) { - const IGNode *const Node = IGNodeList[i]; - if(Node) { - std::cerr << " [" << i << "] "; - - for( unsigned int j=0; j < Size; j++) - if(IG[i][j]) - std::cerr << "(" << i << "," << j << ") "; - std::cerr << "\n"; - } - } -} - -//---------------------------------------------------------------------------- -// 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) - std::cerr << " [" << Node->getIndex() << "] " << *Node->getParentLR() - << "\t <# of Neighbors: " << Node->getNumOfNeighbors() << ">\n"; - } -} - -} // End llvm namespace |