1 //===-- InterferenceGraph.cpp ---------------------------------------------===//
3 // Interference graph for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/CodeGen/InterferenceGraph.h"
8 #include "llvm/CodeGen/IGNode.h"
9 #include "llvm/CodeGen/RegAllocCommon.h"
10 #include "Support/STLExtras.h"
14 // for asserting this IG node is infact in the IGNodeList of this class
15 inline static void assertIGNode(const InterferenceGraph *IG,
17 assert(IG->getIGNodeList()[Node->getIndex()] == Node);
20 //-----------------------------------------------------------------------------
21 // Constructor: Records the RegClass and initalizes IGNodeList.
22 // The matrix is NOT yet created by the constructor. Call createGraph()
23 // to create it after adding all IGNodes to the IGNodeList.
24 //-----------------------------------------------------------------------------
25 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
30 if( DEBUG_RA >= RA_DEBUG_Interference) {
31 cerr << "Interference graph created!\n";
36 //-----------------------------------------------------------------------------
37 // destructor. Deletes the bit matrix and all IGNodes
38 //-----------------------------------------------------------------------------
39 InterferenceGraph:: ~InterferenceGraph() {
42 for(unsigned int r=0; r < IGNodeList.size(); ++r)
46 // delete all IGNodes in the IGNodeList
47 for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>);
52 //-----------------------------------------------------------------------------
53 // Creates (dynamically allocates) the bit matrix necessary to hold the
54 // interference graph.
55 //-----------------------------------------------------------------------------
56 void InterferenceGraph::createGraph()
58 Size = IGNodeList.size();
60 for( unsigned int r=0; r < Size; ++r)
61 IG[r] = new char[Size];
64 for(unsigned int i=0; i < Size; i++)
65 for(unsigned int j=0; j < Size; j++)
69 //-----------------------------------------------------------------------------
70 // creates a new IGNode for the given live range and add to IG
71 //-----------------------------------------------------------------------------
72 void InterferenceGraph::addLRToIG(LiveRange *const LR)
74 IGNodeList.push_back(new IGNode(LR, IGNodeList.size()));
78 //-----------------------------------------------------------------------------
79 // set interference for two live ranges
80 // update both the matrix and AdjLists of nodes.
81 // If there is already an interference between LR1 and LR2, adj lists
82 // are not updated. LR1 and LR2 must be distinct since if not, it suggests
83 // that there is some wrong logic in some other method.
84 //-----------------------------------------------------------------------------
85 void InterferenceGraph::setInterference(const LiveRange *const LR1,
86 const LiveRange *const LR2 ) {
89 IGNode *IGNode1 = LR1->getUserIGNode();
90 IGNode *IGNode2 = LR2->getUserIGNode();
92 assertIGNode(this, IGNode1);
93 assertIGNode(this, IGNode2);
95 unsigned row = IGNode1->getIndex();
96 unsigned col = IGNode2->getIndex();
100 if( DEBUG_RA >= RA_DEBUG_Interference)
101 cerr << "setting intf for: [" << row << "][" << col << "]\n";
103 ( row > col) ? val = &IG[row][col]: val = &IG[col][row];
105 if( ! (*val) ) { // if this interf is not previously set
106 *val = 1; // add edges between nodes
107 IGNode1->addAdjIGNode( IGNode2 );
108 IGNode2->addAdjIGNode( IGNode1 );
114 //----------------------------------------------------------------------------
115 // return whether two live ranges interfere
116 //----------------------------------------------------------------------------
117 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
118 const LiveRange *const LR2 ) const {
121 assertIGNode(this, LR1->getUserIGNode());
122 assertIGNode(this, LR2->getUserIGNode());
124 const unsigned int row = LR1->getUserIGNode()->getIndex();
125 const unsigned int col = LR2->getUserIGNode()->getIndex();
137 //----------------------------------------------------------------------------
138 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode.
139 // Then the IGNode2L will be deleted. Necessary for coalescing.
140 // IMPORTANT: The live ranges are NOT merged by this method. Use
141 // LiveRangeInfo::unionAndUpdateLRs for that purpose.
142 //----------------------------------------------------------------------------
144 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1,
147 assert( LR1 != LR2); // cannot merge the same live range
149 IGNode *const DestNode = LR1->getUserIGNode();
150 IGNode *SrcNode = LR2->getUserIGNode();
152 assertIGNode(this, DestNode);
153 assertIGNode(this, SrcNode);
155 if( DEBUG_RA >= RA_DEBUG_Interference) {
156 cerr << "Merging LRs: \""; printSet(*LR1);
157 cerr << "\" and \""; printSet(*LR2);
161 unsigned SrcDegree = SrcNode->getNumOfNeighbors();
162 const unsigned SrcInd = SrcNode->getIndex();
165 // for all neighs of SrcNode
166 for(unsigned i=0; i < SrcDegree; i++) {
167 IGNode *NeighNode = SrcNode->getAdjIGNode(i);
169 LiveRange *const LROfNeigh = NeighNode->getParentLR();
171 // delete edge between src and neigh - even neigh == dest
172 NeighNode->delAdjIGNode(SrcNode);
174 // set the matrix posn to 0 betn src and neigh - even neigh == dest
175 const unsigned NInd = NeighNode->getIndex();
176 ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ;
179 if( LR1 != LROfNeigh) { // if the neigh != dest
181 // add edge betwn Dest and Neigh - if there is no current edge
182 setInterference(LR1, LROfNeigh );
187 IGNodeList[ SrcInd ] = NULL;
189 // SrcNode is no longer necessary - LR2 must be deleted by the caller
195 //----------------------------------------------------------------------------
196 // must be called after modifications to the graph are over but before
197 // pushing IGNodes on to the stack for coloring.
198 //----------------------------------------------------------------------------
199 void InterferenceGraph::setCurDegreeOfIGNodes()
201 unsigned Size = IGNodeList.size();
203 for( unsigned i=0; i < Size; i++) {
204 IGNode *Node = IGNodeList[i];
206 Node->setCurDegree();
214 //--------------------- debugging (Printing) methods -----------------------
216 //----------------------------------------------------------------------------
218 //----------------------------------------------------------------------------
219 void InterferenceGraph::printIG() const
222 for(unsigned int i=0; i < Size; i++) {
224 const IGNode *const Node = IGNodeList[i];
226 cerr << " [" << i << "] ";
228 for( unsigned int j=0; j < i; j++) {
230 cerr << "(" << i << "," << j << ") ";
237 //----------------------------------------------------------------------------
238 // Print the IGnodes in the IGNode List
239 //----------------------------------------------------------------------------
240 void InterferenceGraph::printIGNodeList() const
242 for(unsigned i=0; i < IGNodeList.size() ; ++i) {
243 const IGNode *const Node = IGNodeList[i];
246 cerr << " [" << Node->getIndex() << "] ";
247 printSet(*Node->getParentLR());
248 //int Deg = Node->getCurDegree();
249 cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n";