lib/Target/SparcV9/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/RegAllocCommon.h"
   9 #include "Support/STLExtras.h"
  10 #include <algorithm>
  11 using std::cerr;
  12
  13 //-----------------------------------------------------------------------------
  14 // Constructor: Records the RegClass and initalizes IGNodeList.
  15 // The matrix is NOT yet created by the constructor. Call createGraph()
  16 // to create it after adding all IGNodes to the IGNodeList.
  17 //-----------------------------------------------------------------------------
  18 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
  19                                                            IGNodeList()
  20 {
  21   IG = NULL;
  22   Size = 0;
  23   if( DEBUG_RA >= RA_DEBUG_Interference) {
  24     cerr << "Interference graph created!\n";
  25   }
  26 }
  27
  28
  29 //-----------------------------------------------------------------------------
  30 // destructor. Deletes the bit matrix and all IGNodes
  31 //-----------------------------------------------------------------------------
  32 InterferenceGraph:: ~InterferenceGraph() {
  33
  34   // delete the matrix
  35   for(unsigned int r=0; r < IGNodeList.size(); ++r)
  36     delete[] IG[r];
  37   delete[] IG;
  38
  39   // delete all IGNodes in the IGNodeList
  40   for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>);
  41 }
  42
  43
  44
  45 //-----------------------------------------------------------------------------
  46 // Creates (dynamically allocates) the bit matrix necessary to hold the
  47 // interference graph.
  48 //-----------------------------------------------------------------------------
  49 void InterferenceGraph::createGraph()
  50 {
  51     Size = IGNodeList.size();
  52     IG = new char*[Size];
  53     for( unsigned int r=0; r < Size; ++r)
  54       IG[r] = new char[Size];
  55
  56     // init IG matrix
  57     for(unsigned int i=0; i < Size; i++)
  58       for(unsigned int j=0; j < Size; j++)
  59         IG[i][j] = 0;
  60 }
  61
  62 //-----------------------------------------------------------------------------
  63 // creates a new IGNode for the given live range and add to IG
  64 //-----------------------------------------------------------------------------
  65 void InterferenceGraph::addLRToIG(LiveRange *const LR)
  66 {
  67   IGNodeList.push_back(new IGNode(LR, IGNodeList.size()));
  68 }
  69
  70
  71 //-----------------------------------------------------------------------------
  72 // set interference for two live ranges
  73 // update both the matrix and AdjLists of nodes.
  74 // If there is already an interference between LR1 and LR2, adj lists
  75 // are not updated. LR1 and LR2 must be distinct since if not, it suggests
  76 // that there is some wrong logic in some other method.
  77 //-----------------------------------------------------------------------------
  78 void InterferenceGraph::setInterference(const LiveRange *const LR1,
  79                                         const LiveRange *const LR2 ) {
  80   assert(LR1 != LR2);
  81
  82   IGNode *const IGNode1 = LR1->getUserIGNode();
  83   IGNode *const IGNode2 = LR2->getUserIGNode();
  84
  85   assertIGNode( IGNode1 );
  86   assertIGNode( IGNode2 );
  87
  88   const unsigned int row = IGNode1->getIndex();
  89   const unsigned int col = IGNode2->getIndex();
  90
  91   char *val;
  92
  93   if( DEBUG_RA >= RA_DEBUG_Interference)
  94     cerr << "setting intf for: [" << row << "][" <<  col << "]\n";
  95
  96   ( row > col) ?  val = &IG[row][col]: val = &IG[col][row];
  97
  98   if( ! (*val) ) {                      // if this interf is not previously set
  99     *val = 1;                           // add edges between nodes
 100     IGNode1->addAdjIGNode( IGNode2 );
 101     IGNode2->addAdjIGNode( IGNode1 );
 102   }
 103
 104 }
 105
 106
 107 //----------------------------------------------------------------------------
 108 // return whether two live ranges interfere
 109 //----------------------------------------------------------------------------
 110 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
 111                                            const LiveRange *const LR2 ) const {
 112
 113   assert(LR1 != LR2);
 114   assertIGNode( LR1->getUserIGNode() );
 115   assertIGNode( LR2->getUserIGNode() );
 116
 117   const unsigned int row = LR1->getUserIGNode()->getIndex();
 118   const unsigned int col = LR2->getUserIGNode()->getIndex();
 119
 120   char ret;
 121   if (row > col)
 122     ret = IG[row][col];
 123   else
 124     ret = IG[col][row];
 125   return ret;
 126
 127 }
 128
 129
 130 //----------------------------------------------------------------------------
 131 // Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode.
 132 // Then the IGNode2L  will be deleted. Necessary for coalescing.
 133 // IMPORTANT: The live ranges are NOT merged by this method. Use
 134 //            LiveRangeInfo::unionAndUpdateLRs for that purpose.
 135 //----------------------------------------------------------------------------
 136
 137 void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1,
 138                                           LiveRange *LR2) {
 139
 140   assert( LR1 != LR2);                  // cannot merge the same live range
 141
 142   IGNode *const DestNode = LR1->getUserIGNode();
 143   IGNode *SrcNode = LR2->getUserIGNode();
 144
 145   assertIGNode( DestNode );
 146   assertIGNode( SrcNode );
 147
 148   if( DEBUG_RA >= RA_DEBUG_Interference) {
 149     cerr << "Merging LRs: \""; printSet(*LR1);
 150     cerr << "\" and \""; printSet(*LR2);
 151     cerr << "\"\n";
 152   }
 153
 154   unsigned SrcDegree = SrcNode->getNumOfNeighbors();
 155   const unsigned SrcInd = SrcNode->getIndex();
 156
 157
 158   // for all neighs of SrcNode
 159   for(unsigned i=0; i < SrcDegree; i++) {
 160     IGNode *NeighNode = SrcNode->getAdjIGNode(i);
 161
 162     LiveRange *const LROfNeigh = NeighNode->getParentLR();
 163
 164     // delete edge between src and neigh - even neigh == dest
 165     NeighNode->delAdjIGNode(SrcNode);
 166
 167     // set the matrix posn to 0 betn src and neigh - even neigh == dest
 168     const unsigned NInd = NeighNode->getIndex();
 169     ( SrcInd > NInd) ?  (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ;
 170
 171
 172     if( LR1 != LROfNeigh) {             // if the neigh != dest
 173
 174       // add edge betwn Dest and Neigh - if there is no current edge
 175       setInterference(LR1, LROfNeigh );
 176     }
 177
 178   }
 179
 180   IGNodeList[ SrcInd ] = NULL;
 181
 182   // SrcNode is no longer necessary - LR2 must be deleted by the caller
 183   delete( SrcNode );
 184
 185 }
 186
 187
 188 //----------------------------------------------------------------------------
 189 // must be called after modifications to the graph are over but before
 190 // pushing IGNodes on to the stack for coloring.
 191 //----------------------------------------------------------------------------
 192 void InterferenceGraph::setCurDegreeOfIGNodes()
 193 {
 194   unsigned Size = IGNodeList.size();
 195
 196   for( unsigned i=0; i < Size; i++) {
 197     IGNode *Node = IGNodeList[i];
 198     if( Node )
 199       Node->setCurDegree();
 200   }
 201 }
 202
 203
 204
 205
 206
 207 //--------------------- debugging (Printing) methods -----------------------
 208
 209 //----------------------------------------------------------------------------
 210 // Print the IGnodes
 211 //----------------------------------------------------------------------------
 212 void InterferenceGraph::printIG() const
 213 {
 214
 215   for(unsigned int i=0; i < Size; i++) {
 216
 217     const IGNode *const Node = IGNodeList[i];
 218     if(Node) {
 219       cerr << " [" << i << "] ";
 220
 221       for( unsigned int j=0; j < i; j++) {
 222         if(IG[i][j])
 223           cerr << "(" << i << "," << j << ") ";
 224       }
 225       cerr << "\n";
 226     }
 227   }
 228 }
 229
 230 //----------------------------------------------------------------------------
 231 // Print the IGnodes in the IGNode List
 232 //----------------------------------------------------------------------------
 233 void InterferenceGraph::printIGNodeList() const
 234 {
 235   for(unsigned i=0; i < IGNodeList.size() ; ++i) {
 236     const IGNode *const Node = IGNodeList[i];
 237
 238     if (Node) {
 239       cerr << " [" << Node->getIndex() << "] ";
 240       printSet(*Node->getParentLR());
 241       //int Deg = Node->getCurDegree();
 242       cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n";
 243     }
 244   }
 245 }