lib/Target/SparcV9/RegAlloc/InterferenceGraph.cpp

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