1 //===-- InterferenceGraph.cpp ---------------------------------------------===//
3 // Interference graph for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/CodeGen/InterferenceGraph.h"
8 #include "llvm/CodeGen/RegAllocCommon.h"
9 #include "Support/STLExtras.h"
13 //-----------------------------------------------------------------------------
14 // Constructor: Records the RegClass and initalizes IGNodeList.
15 // The matrix is NOT yet created by the constructor. Call createGraph()
16 // to create it after adding all IGNodes to the IGNodeList.
17 //-----------------------------------------------------------------------------
18 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
23 if( DEBUG_RA >= RA_DEBUG_Interference) {
24 cerr << "Interference graph created!\n";
29 //-----------------------------------------------------------------------------
30 // destructor. Deletes the bit matrix and all IGNodes
31 //-----------------------------------------------------------------------------
32 InterferenceGraph:: ~InterferenceGraph() {
35 for(unsigned int r=0; r < IGNodeList.size(); ++r)
39 // delete all IGNodes in the IGNodeList
40 for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>);
45 //-----------------------------------------------------------------------------
46 // Creates (dynamically allocates) the bit matrix necessary to hold the
47 // interference graph.
48 //-----------------------------------------------------------------------------
49 void InterferenceGraph::createGraph()
51 Size = IGNodeList.size();
53 for( unsigned int r=0; r < Size; ++r)
54 IG[r] = new char[Size];
57 for(unsigned int i=0; i < Size; i++)
58 for(unsigned int j=0; j < Size; j++)
62 //-----------------------------------------------------------------------------
63 // creates a new IGNode for the given live range and add to IG
64 //-----------------------------------------------------------------------------
65 void InterferenceGraph::addLRToIG(LiveRange *const LR)
67 IGNodeList.push_back(new IGNode(LR, IGNodeList.size()));
71 //-----------------------------------------------------------------------------
72 // set interference for two live ranges
73 // update both the matrix and AdjLists of nodes.
74 // If there is already an interference between LR1 and LR2, adj lists
75 // are not updated. LR1 and LR2 must be distinct since if not, it suggests
76 // that there is some wrong logic in some other method.
77 //-----------------------------------------------------------------------------
78 void InterferenceGraph::setInterference(const LiveRange *const LR1,
79 const LiveRange *const LR2 ) {
82 IGNode *const IGNode1 = LR1->getUserIGNode();
83 IGNode *const IGNode2 = LR2->getUserIGNode();
85 assertIGNode( IGNode1 );
86 assertIGNode( IGNode2 );
88 const unsigned int row = IGNode1->getIndex();
89 const unsigned int col = IGNode2->getIndex();
93 if( DEBUG_RA >= RA_DEBUG_Interference)
94 cerr << "setting intf for: [" << row << "][" << col << "]\n";
96 ( row > col) ? val = &IG[row][col]: val = &IG[col][row];
98 if( ! (*val) ) { // if this interf is not previously set
99 *val = 1; // add edges between nodes
100 IGNode1->addAdjIGNode( IGNode2 );
101 IGNode2->addAdjIGNode( IGNode1 );
107 //----------------------------------------------------------------------------
108 // return whether two live ranges interfere
109 //----------------------------------------------------------------------------
110 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
111 const LiveRange *const LR2 ) const {
114 assertIGNode( LR1->getUserIGNode() );
115 assertIGNode( LR2->getUserIGNode() );
117 const unsigned int row = LR1->getUserIGNode()->getIndex();
118 const unsigned int col = LR2->getUserIGNode()->getIndex();
130 //----------------------------------------------------------------------------
131 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode.
132 // Then the IGNode2L will be deleted. Necessary for coalescing.
133 // IMPORTANT: The live ranges are NOT merged by this method. Use
134 // LiveRangeInfo::unionAndUpdateLRs for that purpose.
135 //----------------------------------------------------------------------------
137 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1,
140 assert( LR1 != LR2); // cannot merge the same live range
142 IGNode *const DestNode = LR1->getUserIGNode();
143 IGNode *SrcNode = LR2->getUserIGNode();
145 assertIGNode( DestNode );
146 assertIGNode( SrcNode );
148 if( DEBUG_RA >= RA_DEBUG_Interference) {
149 cerr << "Merging LRs: \""; printSet(*LR1);
150 cerr << "\" and \""; printSet(*LR2);
154 unsigned SrcDegree = SrcNode->getNumOfNeighbors();
155 const unsigned SrcInd = SrcNode->getIndex();
158 // for all neighs of SrcNode
159 for(unsigned i=0; i < SrcDegree; i++) {
160 IGNode *NeighNode = SrcNode->getAdjIGNode(i);
162 LiveRange *const LROfNeigh = NeighNode->getParentLR();
164 // delete edge between src and neigh - even neigh == dest
165 NeighNode->delAdjIGNode(SrcNode);
167 // set the matrix posn to 0 betn src and neigh - even neigh == dest
168 const unsigned NInd = NeighNode->getIndex();
169 ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ;
172 if( LR1 != LROfNeigh) { // if the neigh != dest
174 // add edge betwn Dest and Neigh - if there is no current edge
175 setInterference(LR1, LROfNeigh );
180 IGNodeList[ SrcInd ] = NULL;
182 // SrcNode is no longer necessary - LR2 must be deleted by the caller
188 //----------------------------------------------------------------------------
189 // must be called after modifications to the graph are over but before
190 // pushing IGNodes on to the stack for coloring.
191 //----------------------------------------------------------------------------
192 void InterferenceGraph::setCurDegreeOfIGNodes()
194 unsigned Size = IGNodeList.size();
196 for( unsigned i=0; i < Size; i++) {
197 IGNode *Node = IGNodeList[i];
199 Node->setCurDegree();
207 //--------------------- debugging (Printing) methods -----------------------
209 //----------------------------------------------------------------------------
211 //----------------------------------------------------------------------------
212 void InterferenceGraph::printIG() const
215 for(unsigned int i=0; i < Size; i++) {
217 const IGNode *const Node = IGNodeList[i];
219 cerr << " [" << i << "] ";
221 for( unsigned int j=0; j < i; j++) {
223 cerr << "(" << i << "," << j << ") ";
230 //----------------------------------------------------------------------------
231 // Print the IGnodes in the IGNode List
232 //----------------------------------------------------------------------------
233 void InterferenceGraph::printIGNodeList() const
235 for(unsigned i=0; i < IGNodeList.size() ; ++i) {
236 const IGNode *const Node = IGNodeList[i];
239 cerr << " [" << Node->getIndex() << "] ";
240 printSet(*Node->getParentLR());
241 //int Deg = Node->getCurDegree();
242 cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n";