lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp

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