1 #include "llvm/CodeGen/InterferenceGraph.h"
2 #include "Support/STLExtras.h"
7 //-----------------------------------------------------------------------------
8 // Constructor: Records the RegClass and initalizes IGNodeList.
9 // The matrix is NOT yet created by the constructor. Call createGraph()
10 // to create it after adding all IGNodes to the IGNodeList.
11 //-----------------------------------------------------------------------------
12 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
18 cerr << "Interference graph created!\n";
23 //-----------------------------------------------------------------------------
24 // destructor. Deletes the bit matrix and all IGNodes
25 //-----------------------------------------------------------------------------
26 InterferenceGraph:: ~InterferenceGraph() {
29 for(unsigned int r=0; r < IGNodeList.size(); ++r)
33 // delete all IGNodes in the IGNodeList
34 for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>);
39 //-----------------------------------------------------------------------------
40 // Creates (dynamically allocates) the bit matrix necessary to hold the
41 // interference graph.
42 //-----------------------------------------------------------------------------
43 void InterferenceGraph::createGraph()
45 Size = IGNodeList.size();
47 for( unsigned int r=0; r < Size; ++r)
48 IG[r] = new char[Size];
51 for(unsigned int i=0; i < Size; i++)
52 for(unsigned int j=0; j < Size; j++)
56 //-----------------------------------------------------------------------------
57 // creates a new IGNode for the given live range and add to IG
58 //-----------------------------------------------------------------------------
59 void InterferenceGraph::addLRToIG(LiveRange *const LR)
61 IGNodeList.push_back(new IGNode(LR, IGNodeList.size()));
65 //-----------------------------------------------------------------------------
66 // set interference for two live ranges
67 // update both the matrix and AdjLists of nodes.
68 // If there is already an interference between LR1 and LR2, adj lists
69 // are not updated. LR1 and LR2 must be distinct since if not, it suggests
70 // that there is some wrong logic in some other method.
71 //-----------------------------------------------------------------------------
72 void InterferenceGraph::setInterference(const LiveRange *const LR1,
73 const LiveRange *const LR2 ) {
76 IGNode *const IGNode1 = LR1->getUserIGNode();
77 IGNode *const IGNode2 = LR2->getUserIGNode();
80 assertIGNode( IGNode1 );
81 assertIGNode( IGNode2 );
84 const unsigned int row = IGNode1->getIndex();
85 const unsigned int col = IGNode2->getIndex();
90 cerr << "setting intf for: [" << row << "][" << col << "]\n";
92 ( row > col) ? val = &IG[row][col]: val = &IG[col][row];
94 if( ! (*val) ) { // if this interf is not previously set
95 *val = 1; // add edges between nodes
96 IGNode1->addAdjIGNode( IGNode2 );
97 IGNode2->addAdjIGNode( IGNode1 );
103 //----------------------------------------------------------------------------
104 // return whether two live ranges interfere
105 //----------------------------------------------------------------------------
106 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
107 const LiveRange *const LR2 ) const {
112 assertIGNode( LR1->getUserIGNode() );
113 assertIGNode( LR2->getUserIGNode() );
116 const unsigned int row = LR1->getUserIGNode()->getIndex();
117 const unsigned int col = LR2->getUserIGNode()->getIndex();
129 //----------------------------------------------------------------------------
130 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode.
131 // Then the IGNode2L will be deleted. Necessary for coalescing.
132 // IMPORTANT: The live ranges are NOT merged by this method. Use
133 // LiveRangeInfo::unionAndUpdateLRs for that purpose.
134 //----------------------------------------------------------------------------
136 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *const LR1,
137 LiveRange *const LR2 ) {
139 assert( LR1 != LR2); // cannot merge the same live range
141 IGNode *const DestNode = LR1->getUserIGNode();
142 IGNode *SrcNode = LR2->getUserIGNode();
144 assertIGNode( DestNode );
145 assertIGNode( SrcNode );
148 cerr << "Merging LRs: \""; LR1->printSet();
149 cerr << "\" and \""; LR2->printSet();
153 unsigned SrcDegree = SrcNode->getNumOfNeighbors();
154 const unsigned SrcInd = SrcNode->getIndex();
157 // for all neighs of SrcNode
158 for(unsigned i=0; i < SrcDegree; i++) {
159 IGNode *NeighNode = SrcNode->getAdjIGNode(i);
161 LiveRange *const LROfNeigh = NeighNode->getParentLR();
163 // delete edge between src and neigh - even neigh == dest
164 NeighNode->delAdjIGNode(SrcNode);
166 // set the matrix posn to 0 betn src and neigh - even neigh == dest
167 const unsigned NInd = NeighNode->getIndex();
168 ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ;
171 if( LR1 != LROfNeigh) { // if the neigh != dest
173 // add edge betwn Dest and Neigh - if there is no current edge
174 setInterference(LR1, LROfNeigh );
179 IGNodeList[ SrcInd ] = NULL;
181 // SrcNode is no longer necessary - LR2 must be deleted by the caller
187 //----------------------------------------------------------------------------
188 // must be called after modifications to the graph are over but before
189 // pushing IGNodes on to the stack for coloring.
190 //----------------------------------------------------------------------------
191 void InterferenceGraph::setCurDegreeOfIGNodes()
193 unsigned Size = IGNodeList.size();
195 for( unsigned i=0; i < Size; i++) {
196 IGNode *Node = IGNodeList[i];
198 Node->setCurDegree();
206 //--------------------- debugging (Printing) methods -----------------------
208 //----------------------------------------------------------------------------
210 //----------------------------------------------------------------------------
211 void InterferenceGraph::printIG() const
214 for(unsigned int i=0; i < Size; i++) {
216 const IGNode *const Node = IGNodeList[i];
218 cerr << " [" << i << "] ";
220 for( unsigned int j=0; j < i; j++) {
222 cerr << "(" << i << "," << j << ") ";
229 //----------------------------------------------------------------------------
230 // Print the IGnodes in the IGNode List
231 //----------------------------------------------------------------------------
232 void InterferenceGraph::printIGNodeList() const
234 for(unsigned i=0; i < IGNodeList.size() ; ++i) {
235 const IGNode *const Node = IGNodeList[i];
238 cerr << " [" << Node->getIndex() << "] ";
239 Node->getParentLR()->printSet();
240 //int Deg = Node->getCurDegree();
241 cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n";