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