lib/CodeGen/RegAlloc/InterferenceGraph.cpp

   1 //===-- InterferenceGraph.cpp ---------------------------------------------===//
   2 //
   3 //  Interference graph for coloring-based register allocation for LLVM.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/CodeGen/InterferenceGraph.h"
   8 #include "llvm/CodeGen/IGNode.h"
   9 #include "llvm/CodeGen/RegAllocCommon.h"
  10 #include "Support/STLExtras.h"
  11 #include <algorithm>
  12 using std::cerr;
  13
  14 // for asserting this IG node is infact in the IGNodeList of this class
  15 inline static void assertIGNode(const InterferenceGraph *IG,
  16                                 const IGNode *Node) {
  17   assert(IG->getIGNodeList()[Node->getIndex()] == Node);
  18 }
  19
  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),
  26                                                            IGNodeList()
  27 {
  28   IG = NULL;
  29   Size = 0;
  30   if( DEBUG_RA >= RA_DEBUG_Interference) {
  31     cerr << "Interference graph created!\n";
  32   }
  33 }
  34
  35
  36 //-----------------------------------------------------------------------------
  37 // destructor. Deletes the bit matrix and all IGNodes
  38 //-----------------------------------------------------------------------------
  39 InterferenceGraph:: ~InterferenceGraph() {
  40
  41   // delete the matrix
  42   for(unsigned int r=0; r < IGNodeList.size(); ++r)
  43     delete[] IG[r];
  44   delete[] IG;
  45
  46   // delete all IGNodes in the IGNodeList
  47   for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>);
  48 }
  49
  50
  51
  52 //-----------------------------------------------------------------------------
  53 // Creates (dynamically allocates) the bit matrix necessary to hold the
  54 // interference graph.
  55 //-----------------------------------------------------------------------------
  56 void InterferenceGraph::createGraph()
  57 {
  58     Size = IGNodeList.size();
  59     IG = new char*[Size];
  60     for( unsigned int r=0; r < Size; ++r)
  61       IG[r] = new char[Size];
  62
  63     // init IG matrix
  64     for(unsigned int i=0; i < Size; i++)
  65       for(unsigned int j=0; j < Size; j++)
  66         IG[i][j] = 0;
  67 }
  68
  69 //-----------------------------------------------------------------------------
  70 // creates a new IGNode for the given live range and add to IG
  71 //-----------------------------------------------------------------------------
  72 void InterferenceGraph::addLRToIG(LiveRange *const LR)
  73 {
  74   IGNodeList.push_back(new IGNode(LR, IGNodeList.size()));
  75 }
  76
  77
  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 ) {
  87   assert(LR1 != LR2);
  88
  89   IGNode *IGNode1 = LR1->getUserIGNode();
  90   IGNode *IGNode2 = LR2->getUserIGNode();
  91
  92   assertIGNode(this, IGNode1);
  93   assertIGNode(this, IGNode2);
  94
  95   unsigned row = IGNode1->getIndex();
  96   unsigned col = IGNode2->getIndex();
  97
  98   char *val;
  99
 100   if( DEBUG_RA >= RA_DEBUG_Interference)
 101     cerr << "setting intf for: [" << row << "][" <<  col << "]\n";
 102
 103   ( row > col) ?  val = &IG[row][col]: val = &IG[col][row];
 104
 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 );
 109   }
 110
 111 }
 112
 113
 114 //----------------------------------------------------------------------------
 115 // return whether two live ranges interfere
 116 //----------------------------------------------------------------------------
 117 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
 118                                            const LiveRange *const LR2 ) const {
 119
 120   assert(LR1 != LR2);
 121   assertIGNode(this, LR1->getUserIGNode());
 122   assertIGNode(this, LR2->getUserIGNode());
 123
 124   const unsigned int row = LR1->getUserIGNode()->getIndex();
 125   const unsigned int col = LR2->getUserIGNode()->getIndex();
 126
 127   char ret;
 128   if (row > col)
 129     ret = IG[row][col];
 130   else
 131     ret = IG[col][row];
 132   return ret;
 133
 134 }
 135
 136
 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 //----------------------------------------------------------------------------
 143
 144 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1,
 145                                           LiveRange *LR2) {
 146
 147   assert( LR1 != LR2);                  // cannot merge the same live range
 148
 149   IGNode *const DestNode = LR1->getUserIGNode();
 150   IGNode *SrcNode = LR2->getUserIGNode();
 151
 152   assertIGNode(this, DestNode);
 153   assertIGNode(this, SrcNode);
 154
 155   if( DEBUG_RA >= RA_DEBUG_Interference) {
 156     cerr << "Merging LRs: \""; printSet(*LR1);
 157     cerr << "\" and \""; printSet(*LR2);
 158     cerr << "\"\n";
 159   }
 160
 161   unsigned SrcDegree = SrcNode->getNumOfNeighbors();
 162   const unsigned SrcInd = SrcNode->getIndex();
 163
 164
 165   // for all neighs of SrcNode
 166   for(unsigned i=0; i < SrcDegree; i++) {
 167     IGNode *NeighNode = SrcNode->getAdjIGNode(i);
 168
 169     LiveRange *const LROfNeigh = NeighNode->getParentLR();
 170
 171     // delete edge between src and neigh - even neigh == dest
 172     NeighNode->delAdjIGNode(SrcNode);
 173
 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) ;
 177
 178
 179     if( LR1 != LROfNeigh) {             // if the neigh != dest
 180
 181       // add edge betwn Dest and Neigh - if there is no current edge
 182       setInterference(LR1, LROfNeigh );
 183     }
 184
 185   }
 186
 187   IGNodeList[ SrcInd ] = NULL;
 188
 189   // SrcNode is no longer necessary - LR2 must be deleted by the caller
 190   delete( SrcNode );
 191
 192 }
 193
 194
 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()
 200 {
 201   unsigned Size = IGNodeList.size();
 202
 203   for( unsigned i=0; i < Size; i++) {
 204     IGNode *Node = IGNodeList[i];
 205     if( Node )
 206       Node->setCurDegree();
 207   }
 208 }
 209
 210
 211
 212
 213
 214 //--------------------- debugging (Printing) methods -----------------------
 215
 216 //----------------------------------------------------------------------------
 217 // Print the IGnodes
 218 //----------------------------------------------------------------------------
 219 void InterferenceGraph::printIG() const
 220 {
 221
 222   for(unsigned int i=0; i < Size; i++) {
 223
 224     const IGNode *const Node = IGNodeList[i];
 225     if(Node) {
 226       cerr << " [" << i << "] ";
 227
 228       for( unsigned int j=0; j < i; j++) {
 229         if(IG[i][j])
 230           cerr << "(" << i << "," << j << ") ";
 231       }
 232       cerr << "\n";
 233     }
 234   }
 235 }
 236
 237 //----------------------------------------------------------------------------
 238 // Print the IGnodes in the IGNode List
 239 //----------------------------------------------------------------------------
 240 void InterferenceGraph::printIGNodeList() const
 241 {
 242   for(unsigned i=0; i < IGNodeList.size() ; ++i) {
 243     const IGNode *const Node = IGNodeList[i];
 244
 245     if (Node) {
 246       cerr << " [" << Node->getIndex() << "] ";
 247       printSet(*Node->getParentLR());
 248       //int Deg = Node->getCurDegree();
 249       cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n";
 250     }
 251   }
 252 }