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