lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp

   1 #include "llvm/CodeGen/InterferenceGraph.h"
   2
   3 //-----------------------------------------------------------------------------
   4 // Constructor: Records the RegClass and initalizes IGNodeList.
   5 // The matrix is NOT yet created by the constructor. Call createGraph()
   6 // to create it after adding all IGNodes to the IGNodeList.
   7 //-----------------------------------------------------------------------------
   8 InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC),
   9                                                            IGNodeList()
  10 {
  11   IG = NULL;
  12   Size = 0;
  13   if( DEBUG_RA) {
  14     cout << "Interference graph created!" << endl;
  15   }
  16 }
  17
  18
  19 //-----------------------------------------------------------------------------
  20 // destructor. Deletes the bit matrix and all IGNodes
  21 //-----------------------------------------------------------------------------
  22 InterferenceGraph:: ~InterferenceGraph() {
  23
  24   // delete the matrix
  25   //
  26   if( IG )
  27     delete []IG;
  28
  29   // delete all IGNodes in the IGNodeList
  30   //
  31   vector<IGNode *>::const_iterator IGIt = IGNodeList.begin();
  32   for(unsigned i=0; i < IGNodeList.size() ; ++i) {
  33
  34     const IGNode *const Node = IGNodeList[i];
  35     if( Node ) delete Node;
  36   }
  37
  38 }
  39
  40
  41
  42 //-----------------------------------------------------------------------------
  43 // Creates (dynamically allocates) the bit matrix necessary to hold the
  44 // interference graph.
  45 //-----------------------------------------------------------------------------
  46 void InterferenceGraph::createGraph()
  47 {
  48     Size = IGNodeList.size();
  49     IG = (char **) new char *[Size];
  50     for( unsigned int r=0; r < Size; ++r)
  51       IG[r] = new char[Size];
  52
  53     // init IG matrix
  54     for(unsigned int i=0; i < Size; i++)
  55       for( unsigned int j=0; j < Size ; j++)
  56         IG[i][j] = 0;
  57 }
  58
  59 //-----------------------------------------------------------------------------
  60 // creates a new IGNode for the given live range and add to IG
  61 //-----------------------------------------------------------------------------
  62 void InterferenceGraph::addLRToIG(LiveRange *const LR)
  63 {
  64   IGNode *Node = new IGNode(LR,  IGNodeList.size() );
  65   IGNodeList.push_back( Node );
  66
  67 }
  68
  69
  70 //-----------------------------------------------------------------------------
  71 // set interference for two live ranges
  72 // update both the matrix and AdjLists of nodes.
  73 // If there is already an interference between LR1 and LR2, adj lists
  74 // are not updated. LR1 and LR2 must be distinct since if not, it suggests
  75 // that there is some wrong logic in some other method.
  76 //-----------------------------------------------------------------------------
  77 void InterferenceGraph::setInterference(const LiveRange *const LR1,
  78                                         const LiveRange *const LR2 ) {
  79   assert(LR1 != LR2);
  80
  81   IGNode *const IGNode1 = LR1->getUserIGNode();
  82   IGNode *const IGNode2 = LR2->getUserIGNode();
  83
  84   if( DEBUG_RA) {
  85     assertIGNode( IGNode1 );
  86     assertIGNode( IGNode2 );
  87   }
  88
  89   const unsigned int row = IGNode1->getIndex();
  90   const unsigned int col = IGNode2->getIndex();
  91
  92   char *val;
  93
  94   if( DEBUG_RA > 1)
  95     cout << "setting intf for: [" << row << "][" <<  col << "]" << endl;
  96
  97   ( row > col) ?  val = &IG[row][col]: val = &IG[col][row];
  98
  99   if( ! (*val) ) {                      // if this interf is not previously set
 100
 101     *val = 1;                           // add edges between nodes
 102     IGNode1->addAdjIGNode( IGNode2 );
 103     IGNode2->addAdjIGNode( IGNode1 );
 104   }
 105
 106 }
 107
 108
 109 //----------------------------------------------------------------------------
 110 // return whether two live ranges interfere
 111 //----------------------------------------------------------------------------
 112 unsigned InterferenceGraph::getInterference(const LiveRange *const LR1,
 113                                            const LiveRange *const LR2 ) const {
 114
 115   assert(LR1 != LR2);
 116
 117   if( DEBUG_RA) {
 118     assertIGNode( LR1->getUserIGNode() );
 119     assertIGNode( LR2->getUserIGNode() );
 120   }
 121
 122   const unsigned int row = LR1->getUserIGNode()->getIndex();
 123   const unsigned int col = LR2->getUserIGNode()->getIndex();
 124
 125   char ret;
 126   ( row > col) ?  (ret = IG[row][col]) : (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 *const LR1,
 140                                           LiveRange *const 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( DestNode );
 148   assertIGNode( SrcNode );
 149
 150   if( DEBUG_RA > 1) {
 151     cout << "Merging LRs: \""; LR1->printSet();
 152     cout << "\" and \""; LR2->printSet();
 153     cout << "\"" << endl;
 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 {
 216
 217   for(unsigned int i=0; i < Size; i++) {
 218
 219     const IGNode *const Node = IGNodeList[i];
 220     if( ! Node )
 221       continue;                         // skip empty rows
 222
 223     cout << " [" << i << "] ";
 224
 225       for( unsigned int j=0; j < Size; j++) {
 226         if( j >= i) break;
 227         if( IG[i][j] ) cout << "(" << i << "," << j << ") ";
 228       }
 229       cout << endl;
 230     }
 231 }
 232
 233 //----------------------------------------------------------------------------
 234 // Print the IGnodes in the IGNode List
 235 //----------------------------------------------------------------------------
 236 void InterferenceGraph::printIGNodeList() const
 237 {
 238   vector<IGNode *>::const_iterator IGIt = IGNodeList.begin(); // hash map iter
 239
 240   for(unsigned i=0; i < IGNodeList.size() ; ++i) {
 241
 242     const IGNode *const Node = IGNodeList[i];
 243
 244     if( ! Node )
 245       continue;
 246
 247     cout << " [" << Node->getIndex() << "] ";
 248     (Node->getParentLR())->printSet();
 249     //int Deg = Node->getCurDegree();
 250     cout << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">" << endl;
 251
 252   }
 253 }
 254
 255