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(V9LiveRange *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 V9LiveRange *const LR1, 00091 const V9LiveRange *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 V9LiveRange *const LR1, 00123 const V9LiveRange *const LR2) 00124 const { 00125 assert(LR1 != LR2); 00126 assertIGNode(this, LR1->getUserIGNode()); 00127 assertIGNode(this, LR2->getUserIGNode()); 00128 00129 const unsigned int row = LR1->getUserIGNode()->getIndex(); 00130 const unsigned int col = LR2->getUserIGNode()->getIndex(); 00131 00132 char ret; 00133 if (row > col) 00134 ret = IG[row][col]; 00135 else 00136 ret = IG[col][row]; 00137 return ret; 00138 00139 } 00140 00141 00142 //---------------------------------------------------------------------------- 00143 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode. 00144 // Then the IGNode2L will be deleted. Necessary for coalescing. 00145 // IMPORTANT: The live ranges are NOT merged by this method. Use 00146 // LiveRangeInfo::unionAndUpdateLRs for that purpose. 00147 //---------------------------------------------------------------------------- 00148 00149 void InterferenceGraph::mergeIGNodesOfLRs(const V9LiveRange *LR1, 00150 V9LiveRange *LR2) { 00151 00152 assert( LR1 != LR2); // cannot merge the same live range 00153 00154 IGNode *const DestNode = LR1->getUserIGNode(); 00155 IGNode *SrcNode = LR2->getUserIGNode(); 00156 00157 assertIGNode(this, DestNode); 00158 assertIGNode(this, SrcNode); 00159 00160 if( DEBUG_RA >= RA_DEBUG_Interference) { 00161 std::cerr << "Merging LRs: \"" << *LR1 << "\" and \"" << *LR2 << "\"\n"; 00162 } 00163 00164 unsigned SrcDegree = SrcNode->getNumOfNeighbors(); 00165 const unsigned SrcInd = SrcNode->getIndex(); 00166 00167 00168 // for all neighs of SrcNode 00169 for(unsigned i=0; i < SrcDegree; i++) { 00170 IGNode *NeighNode = SrcNode->getAdjIGNode(i); 00171 00172 V9LiveRange *const LROfNeigh = NeighNode->getParentLR(); 00173 00174 // delete edge between src and neigh - even neigh == dest 00175 NeighNode->delAdjIGNode(SrcNode); 00176 00177 // set the matrix posn to 0 betn src and neigh - even neigh == dest 00178 const unsigned NInd = NeighNode->getIndex(); 00179 ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ; 00180 00181 00182 if( LR1 != LROfNeigh) { // if the neigh != dest 00183 00184 // add edge betwn Dest and Neigh - if there is no current edge 00185 setInterference(LR1, LROfNeigh ); 00186 } 00187 00188 } 00189 00190 IGNodeList[ SrcInd ] = NULL; 00191 00192 // SrcNode is no longer necessary - LR2 must be deleted by the caller 00193 delete( SrcNode ); 00194 00195 } 00196 00197 00198 //---------------------------------------------------------------------------- 00199 // must be called after modifications to the graph are over but before 00200 // pushing IGNodes on to the stack for coloring. 00201 //---------------------------------------------------------------------------- 00202 void InterferenceGraph::setCurDegreeOfIGNodes() 00203 { 00204 unsigned Size = IGNodeList.size(); 00205 00206 for( unsigned i=0; i < Size; i++) { 00207 IGNode *Node = IGNodeList[i]; 00208 if( Node ) 00209 Node->setCurDegree(); 00210 } 00211 } 00212 00213 00214 00215 00216 00217 //--------------------- debugging (Printing) methods ----------------------- 00218 00219 //---------------------------------------------------------------------------- 00220 // Print the IGnodes 00221 //---------------------------------------------------------------------------- 00222 void InterferenceGraph::printIG() const { 00223 for(unsigned i=0; i < Size; i++) { 00224 const IGNode *const Node = IGNodeList[i]; 00225 if(Node) { 00226 std::cerr << " [" << i << "] "; 00227 00228 for( unsigned int j=0; j < Size; j++) 00229 if(IG[i][j]) 00230 std::cerr << "(" << i << "," << j << ") "; 00231 std::cerr << "\n"; 00232 } 00233 } 00234 } 00235 00236 //---------------------------------------------------------------------------- 00237 // Print the IGnodes in the IGNode List 00238 //---------------------------------------------------------------------------- 00239 void InterferenceGraph::printIGNodeList() const { 00240 for(unsigned i=0; i < IGNodeList.size() ; ++i) { 00241 const IGNode *const Node = IGNodeList[i]; 00242 if (Node) 00243 std::cerr << " [" << Node->getIndex() << "] " << *Node->getParentLR() 00244 << "\t <# of Neighbors: " << Node->getNumOfNeighbors() << ">\n"; 00245 } 00246 } 00247 00248 } // End llvm namespace