LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

InterferenceGraph.cpp

Go to the documentation of this file.
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