lib/CodeGen/RegAlloc/InterferenceGraph.cpp

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