lib/Target/SparcV9/RegAlloc/IGNode.h

   1 /* Title:   IGNode.h                      -*- C++ -*-
   2    Author:  Ruchira Sasanka
   3    Date:    July 25, 01
   4    Purpose: Represents a node in an interference graph.
   5    Notes:
   6
   7    For efficiency, the AdjList is updated only once - ie. we can add but not
   8    remove nodes from AdjList.
   9
  10    The removal of nodes from IG is simulated by decrementing the CurDegree.
  11    If this node is put on stack (that is removed from IG), the CurDegree of all
  12    the neighbors are decremented and this node is marked OnSack. Hence
  13    the effective neighbors in the AdjList are the ones that do not have the
  14    OnStack flag set (therefore, they are in the IG).
  15
  16    The methods that modify/use the CurDegree Must be called only
  17    after all modifications to the IG are over (i.e., all neighbors are fixed).
  18
  19    The vector representation is the most efficient one for adj list.
  20    Though nodes are removed when coalsing is done, we access it in sequence
  21    for far many times when coloring (colorNode()).
  22
  23 */
  24
  25 #ifndef IG_NODE_H
  26 #define IG_NODE_H
  27
  28
  29 #include "llvm/CodeGen/RegAllocCommon.h"
  30 #include "llvm/CodeGen/LiveRange.h"
  31
  32
  33
  34 //----------------------------------------------------------------------------
  35 // Class IGNode
  36 //
  37 // Represents a node in an interference graph.
  38 //----------------------------------------------------------------------------
  39
  40 class IGNode
  41 {
  42  private:
  43
  44   const int Index;            // index within IGNodeList
  45
  46   bool OnStack;               // this has been pushed on to stack for coloring
  47
  48   vector<IGNode *> AdjList;   // adjacency list for this live range
  49
  50   int CurDegree;
  51   //
  52   // set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
  53   // all adjacency lists.
  54   // Decremented when a neighbor is pushed on to the stack.
  55   // After that, never incremented/set again nor used.
  56
  57
  58   LiveRange *const ParentLR;  // parent LR (cannot be a const)
  59
  60
  61  public:
  62
  63   // constructor
  64   //
  65   IGNode(LiveRange *const LR, unsigned int index);
  66
  67   // an empty destructor
  68   //
  69   ~IGNode() { }
  70
  71
  72   inline unsigned int getIndex() const
  73     { return Index; }
  74
  75   // adjLists must be updated only once.  However, the CurDegree can be changed
  76   //
  77   inline void addAdjIGNode( IGNode *const AdjNode)
  78     { AdjList.push_back(AdjNode);  }
  79
  80   inline IGNode * getAdjIGNode(unsigned int ind) const
  81     { assert ( ind < AdjList.size()); return AdjList[ ind ]; }
  82
  83   // delete a node in AdjList - node must be in the list
  84   // should not be called often
  85   //
  86   void delAdjIGNode(const IGNode *const Node);
  87
  88   inline unsigned int getNumOfNeighbors() const
  89     { return AdjList.size() ; }
  90
  91
  92   inline bool isOnStack() const
  93     { return OnStack; }
  94
  95   // remove form IG and pushes on to stack (reduce the degree of neighbors)
  96   //
  97   void pushOnStack();
  98
  99   // CurDegree is the effective number of neighbors when neighbors are
 100   // pushed on to the stack during the coloring phase. Must be called
 101   // after all modifications to the IG are over (i.e., all neighbors are
 102   // fixed).
 103   //
 104   inline void setCurDegree()
 105     { assert( CurDegree == -1);   CurDegree = AdjList.size(); }
 106
 107   inline int getCurDegree() const
 108     { return CurDegree; }
 109
 110   // called when a neigh is pushed on to stack
 111   //
 112   inline void decCurDegree()
 113     { assert( CurDegree > 0 ); --CurDegree; }
 114
 115
 116   // The following methods call the methods in ParentLR
 117   // They are added to this class for convenience
 118   // If many of these are called within a single scope,
 119   // consider calling the methods directly on LR
 120
 121
 122   inline void setRegClass(RegClass *const RC)
 123     { ParentLR->setRegClass(RC);  }
 124
 125   inline RegClass *const getRegClass() const
 126     { return ParentLR->getRegClass(); }
 127
 128   inline bool hasColor() const
 129     { return ParentLR->hasColor();  }
 130
 131   inline unsigned int getColor() const
 132     { return ParentLR->getColor();  }
 133
 134   inline void setColor(unsigned int Col)
 135     { ParentLR->setColor(Col);  }
 136
 137   inline void markForSpill()
 138     { ParentLR->markForSpill();  }
 139
 140   inline void markForSaveAcrossCalls()
 141     { ParentLR->markForSaveAcrossCalls();  }
 142
 143   inline unsigned int isCallInterference() const
 144   { return ParentLR->isCallInterference(); }
 145
 146   inline LiveRange *getParentLR() const
 147     { return ParentLR; }
 148
 149   inline Type::PrimitiveID getTypeID() const
 150     { return ParentLR->getTypeID(); }
 151
 152
 153 };
 154
 155
 156
 157
 158
 159
 160
 161 #endif