lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp

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