1 #include "llvm/CodeGen/InterferenceGraph.h"
4 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
10 cout << "Interference graph created!" << endl;
14 InterferenceGraph:: ~InterferenceGraph() { // destructor
22 void InterferenceGraph::createGraph()
24 Size = IGNodeList.size();
25 IG = (char **) new char *[Size];
26 for( unsigned int r=0; r < Size; ++r)
27 IG[r] = new char[Size];
30 for(unsigned int i=0; i < Size; i++)
31 for( unsigned int j=0; j < Size ; j++)
37 void InterferenceGraph::addLRToIG(LiveRange *const LR)
39 IGNode *Node = new IGNode(LR, IGNodeList.size() );
40 IGNodeList.push_back( Node );
41 //Node->setRegClass( RegCl );
45 // update both the matrix and AdjLists of nodes.
46 // If there is already an interference between LR1 and LR2, adj lists
47 // are not updated. LR1 and LR2 must be distinct since if not, it suggests
48 // that there is some wrong logic in some other method.
50 void InterferenceGraph::setInterference(const LiveRange *const LR1,
51 const LiveRange *const LR2 ) {
54 IGNode *const IGNode1 = LR1->getUserIGNode();
55 IGNode *const IGNode2 = LR2->getUserIGNode();
58 assertIGNode( IGNode1 );
59 assertIGNode( IGNode2 );
62 const unsigned int row = IGNode1->getIndex();
63 const unsigned int col = IGNode2->getIndex();
68 cout << "setting intf for: [" << row << "][" << col << "]" << endl;
70 ( row > col) ? val = &IG[row][col]: val = &IG[col][row];
72 if( ! (*val) ) { // if this interf is not previously set
74 *val = 1; // add edges between nodes
75 IGNode1->addAdjIGNode( IGNode2 );
76 IGNode2->addAdjIGNode( IGNode1 );
83 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
84 const LiveRange *const LR2 ) const {
89 assertIGNode( LR1->getUserIGNode() );
90 assertIGNode( LR2->getUserIGNode() );
93 const unsigned int row = LR1->getUserIGNode()->getIndex();
94 const unsigned int col = LR2->getUserIGNode()->getIndex();
97 ( row > col) ? (ret = IG[row][col]) : (ret = IG[col][row]) ;
104 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode.
105 // Then the IGNode2L will be deleted. Necessary for coalescing.
106 // IMPORTANT: The live ranges are NOT merged by this method. Use
107 // LiveRangeInfo::unionAndUpdateLRs for that purpose.
109 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *const LR1,
110 LiveRange *const LR2 ) {
112 assert( LR1 != LR2); // cannot merge the same live range
114 IGNode *const DestNode = LR1->getUserIGNode();
115 IGNode *SrcNode = LR2->getUserIGNode();
117 assertIGNode( DestNode );
118 assertIGNode( SrcNode );
121 cout << "Merging LRs: \""; LR1->printSet();
122 cout << "\" and \""; LR2->printSet();
123 cout << "\"" << endl;
126 unsigned SrcDegree = SrcNode->getNumOfNeighbors();
127 const unsigned SrcInd = SrcNode->getIndex();
130 // for all neighs of SrcNode
131 for(unsigned i=0; i < SrcDegree; i++) {
132 IGNode *NeighNode = SrcNode->getAdjIGNode(i);
134 LiveRange *const LROfNeigh = NeighNode->getParentLR();
136 // delete edge between src and neigh - even neigh == dest
137 NeighNode->delAdjIGNode(SrcNode);
139 // set the matrix posn to 0 betn src and neigh - even neigh == dest
140 const unsigned NInd = NeighNode->getIndex();
141 ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ;
144 if( LR1 != LROfNeigh) { // if the neigh != dest
146 // add edge betwn Dest and Neigh - if there is no current edge
147 setInterference(LR1, LROfNeigh );
150 //cout<< " #Neighs - Neigh: ["<< NeighNode->getIndex()<< "] ";
151 //cout << NeighNode->getNumOfNeighbors();
152 //cout << " Dest: [" << DestNode->getIndex() << "] ";
153 //cout << DestNode->getNumOfNeighbors() << endl;
157 IGNodeList[ SrcInd ] = NULL;
159 // SrcNode is no longer necessary - LR2 must be deleted by the caller
166 // must be called after modifications to the graph are over but before
167 // pushing IGNodes on to the stack for coloring.
169 void InterferenceGraph::setCurDegreeOfIGNodes()
171 unsigned Size = IGNodeList.size();
173 for( unsigned i=0; i < Size; i++) {
174 IGNode *Node = IGNodeList[i];
176 Node->setCurDegree();
184 //--------------------- debugging (Printing) methods -----------------------
187 void InterferenceGraph::printIG() const
190 for(unsigned int i=0; i < Size; i++) {
192 const IGNode *const Node = IGNodeList[i];
194 continue; // skip empty rows
196 cout << " [" << i << "] ";
198 for( unsigned int j=0; j < Size; j++) {
200 if( IG[i][j] ) cout << "(" << i << "," << j << ") ";
207 void InterferenceGraph::printIGNodeList() const
209 vector<IGNode *>::const_iterator IGIt = IGNodeList.begin(); // hash map iter
211 for(unsigned i=0; i < IGNodeList.size() ; ++i) {
213 const IGNode *const Node = IGNodeList[i];
218 cout << " [" << Node->getIndex() << "] ";
219 (Node->getParentLR())->printSet();
220 //int Deg = Node->getCurDegree();
221 cout << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">" << endl;