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