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