LLVM API Documentation
00001 //===-- InterferenceGraph.cpp ---------------------------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Interference graph for coloring-based register allocation for LLVM. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "IGNode.h" 00015 #include "InterferenceGraph.h" 00016 #include "RegAllocCommon.h" 00017 #include "llvm/ADT/STLExtras.h" 00018 #include <algorithm> 00019 #include <iostream> 00020 00021 namespace llvm { 00022 00023 // for asserting this IG node is infact in the IGNodeList of this class 00024 inline static void assertIGNode(const InterferenceGraph *IG, 00025 const IGNode *Node) { 00026 assert(IG->getIGNodeList()[Node->getIndex()] == Node); 00027 } 00028 00029 //----------------------------------------------------------------------------- 00030 // Constructor: Records the RegClass and initalizes IGNodeList. 00031 // The matrix is NOT yet created by the constructor. Call createGraph() 00032 // to create it after adding all IGNodes to the IGNodeList. 00033 //----------------------------------------------------------------------------- 00034 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC) { 00035 IG = NULL; 00036 Size = 0; 00037 if( DEBUG_RA >= RA_DEBUG_Interference) 00038 std::cerr << "Interference graph created!\n"; 00039 } 00040 00041 00042 //----------------------------------------------------------------------------- 00043 // destructor. Deletes the bit matrix and all IGNodes 00044 //----------------------------------------------------------------------------- 00045 InterferenceGraph:: ~InterferenceGraph() { 00046 // delete the matrix 00047 for(unsigned int r=0; r < IGNodeList.size(); ++r) 00048 delete[] IG[r]; 00049 delete[] IG; 00050 00051 // delete all IGNodes in the IGNodeList 00052 for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>); 00053 } 00054 00055 00056 00057 //----------------------------------------------------------------------------- 00058 // Creates (dynamically allocates) the bit matrix necessary to hold the 00059 // interference graph. 00060 //----------------------------------------------------------------------------- 00061 void InterferenceGraph::createGraph() 00062 { 00063 Size = IGNodeList.size(); 00064 IG = new char*[Size]; 00065 for( unsigned int r=0; r < Size; ++r) 00066 IG[r] = new char[Size]; 00067 00068 // init IG matrix 00069 for(unsigned int i=0; i < Size; i++) 00070 for(unsigned int j=0; j < Size; j++) 00071 IG[i][j] = 0; 00072 } 00073 00074 //----------------------------------------------------------------------------- 00075 // creates a new IGNode for the given live range and add to IG 00076 //----------------------------------------------------------------------------- 00077 void InterferenceGraph::addLRToIG(LiveRange *const LR) 00078 { 00079 IGNodeList.push_back(new IGNode(LR, IGNodeList.size())); 00080 } 00081 00082 00083 //----------------------------------------------------------------------------- 00084 // set interference for two live ranges 00085 // update both the matrix and AdjLists of nodes. 00086 // If there is already an interference between LR1 and LR2, adj lists 00087 // are not updated. LR1 and LR2 must be distinct since if not, it suggests 00088 // that there is some wrong logic in some other method. 00089 //----------------------------------------------------------------------------- 00090 void InterferenceGraph::setInterference(const LiveRange *const LR1, 00091 const LiveRange *const LR2 ) { 00092 assert(LR1 != LR2); 00093 00094 IGNode *IGNode1 = LR1->getUserIGNode(); 00095 IGNode *IGNode2 = LR2->getUserIGNode(); 00096 00097 assertIGNode(this, IGNode1); 00098 assertIGNode(this, IGNode2); 00099 00100 unsigned row = IGNode1->getIndex(); 00101 unsigned col = IGNode2->getIndex(); 00102 00103 char *val; 00104 00105 if( DEBUG_RA >= RA_DEBUG_Interference) 00106 std::cerr << "setting intf for: [" << row << "][" << col << "]\n"; 00107 00108 ( row > col) ? val = &IG[row][col]: val = &IG[col][row]; 00109 00110 if( ! (*val) ) { // if this interf is not previously set 00111 *val = 1; // add edges between nodes 00112 IGNode1->addAdjIGNode( IGNode2 ); 00113 IGNode2->addAdjIGNode( IGNode1 ); 00114 } 00115 00116 } 00117 00118 00119 //---------------------------------------------------------------------------- 00120 // return whether two live ranges interfere 00121 //---------------------------------------------------------------------------- 00122 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1, 00123 const LiveRange *const LR2) const { 00124 assert(LR1 != LR2); 00125 assertIGNode(this, LR1->getUserIGNode()); 00126 assertIGNode(this, LR2->getUserIGNode()); 00127 00128 const unsigned int row = LR1->getUserIGNode()->getIndex(); 00129 const unsigned int col = LR2->getUserIGNode()->getIndex(); 00130 00131 char ret; 00132 if (row > col) 00133 ret = IG[row][col]; 00134 else 00135 ret = IG[col][row]; 00136 return ret; 00137 00138 } 00139 00140 00141 //---------------------------------------------------------------------------- 00142 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode. 00143 // Then the IGNode2L will be deleted. Necessary for coalescing. 00144 // IMPORTANT: The live ranges are NOT merged by this method. Use 00145 // LiveRangeInfo::unionAndUpdateLRs for that purpose. 00146 //---------------------------------------------------------------------------- 00147 00148 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1, 00149 LiveRange *LR2) { 00150 00151 assert( LR1 != LR2); // cannot merge the same live range 00152 00153 IGNode *const DestNode = LR1->getUserIGNode(); 00154 IGNode *SrcNode = LR2->getUserIGNode(); 00155 00156 assertIGNode(this, DestNode); 00157 assertIGNode(this, SrcNode); 00158 00159 if( DEBUG_RA >= RA_DEBUG_Interference) { 00160 std::cerr << "Merging LRs: \"" << *LR1 << "\" and \"" << *LR2 << "\"\n"; 00161 } 00162 00163 unsigned SrcDegree = SrcNode->getNumOfNeighbors(); 00164 const unsigned SrcInd = SrcNode->getIndex(); 00165 00166 00167 // for all neighs of SrcNode 00168 for(unsigned i=0; i < SrcDegree; i++) { 00169 IGNode *NeighNode = SrcNode->getAdjIGNode(i); 00170 00171 LiveRange *const LROfNeigh = NeighNode->getParentLR(); 00172 00173 // delete edge between src and neigh - even neigh == dest 00174 NeighNode->delAdjIGNode(SrcNode); 00175 00176 // set the matrix posn to 0 betn src and neigh - even neigh == dest 00177 const unsigned NInd = NeighNode->getIndex(); 00178 ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ; 00179 00180 00181 if( LR1 != LROfNeigh) { // if the neigh != dest 00182 00183 // add edge betwn Dest and Neigh - if there is no current edge 00184 setInterference(LR1, LROfNeigh ); 00185 } 00186 00187 } 00188 00189 IGNodeList[ SrcInd ] = NULL; 00190 00191 // SrcNode is no longer necessary - LR2 must be deleted by the caller 00192 delete( SrcNode ); 00193 00194 } 00195 00196 00197 //---------------------------------------------------------------------------- 00198 // must be called after modifications to the graph are over but before 00199 // pushing IGNodes on to the stack for coloring. 00200 //---------------------------------------------------------------------------- 00201 void InterferenceGraph::setCurDegreeOfIGNodes() 00202 { 00203 unsigned Size = IGNodeList.size(); 00204 00205 for( unsigned i=0; i < Size; i++) { 00206 IGNode *Node = IGNodeList[i]; 00207 if( Node ) 00208 Node->setCurDegree(); 00209 } 00210 } 00211 00212 00213 00214 00215 00216 //--------------------- debugging (Printing) methods ----------------------- 00217 00218 //---------------------------------------------------------------------------- 00219 // Print the IGnodes 00220 //---------------------------------------------------------------------------- 00221 void InterferenceGraph::printIG() const { 00222 for(unsigned i=0; i < Size; i++) { 00223 const IGNode *const Node = IGNodeList[i]; 00224 if(Node) { 00225 std::cerr << " [" << i << "] "; 00226 00227 for( unsigned int j=0; j < Size; j++) 00228 if(IG[i][j]) 00229 std::cerr << "(" << i << "," << j << ") "; 00230 std::cerr << "\n"; 00231 } 00232 } 00233 } 00234 00235 //---------------------------------------------------------------------------- 00236 // Print the IGnodes in the IGNode List 00237 //---------------------------------------------------------------------------- 00238 void InterferenceGraph::printIGNodeList() const { 00239 for(unsigned i=0; i < IGNodeList.size() ; ++i) { 00240 const IGNode *const Node = IGNodeList[i]; 00241 if (Node) 00242 std::cerr << " [" << Node->getIndex() << "] " << *Node->getParentLR() 00243 << "\t <# of Neighbors: " << Node->getNumOfNeighbors() << ">\n"; 00244 } 00245 } 00246 00247 } // End llvm namespace