lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp

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