lib/Target/SparcV9/RegAlloc/IGNode.h

   1 /* Title:   IGNode.h
   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    fter all modifications to the IG are over (i.e., all neighbors are fixed).
  18
  19    The vector representation 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 class IGNode
  33 {
  34  private:
  35
  36   const int Index;            // index within IGNodeList
  37
  38   bool OnStack;               // this has been pushed on to stack for coloring
  39
  40   vector<IGNode *> AdjList;   // adjacency list for this live range
  41
  42
  43   // set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
  44   // all adjacency lists.
  45   // Decremented when a neighbor is pushed on to the stack.
  46   // After that, never incremented/set again nor used.
  47   int CurDegree;
  48
  49   LiveRange *const ParentLR;            // parent LR (cannot be a const)
  50
  51
  52  public:
  53
  54   inline unsigned int getIndex() const
  55     { return Index; }
  56
  57   // adjLists must be updated only once.  However, the CurDegree can be changed
  58   inline void addAdjIGNode( IGNode *const AdjNode)
  59     { AdjList.push_back(AdjNode);  }
  60
  61   inline IGNode * getAdjIGNode(unsigned int ind) const
  62     { assert ( ind < AdjList.size()); return AdjList[ ind ]; }
  63
  64   // delete a node in AdjList - node must be in the list
  65   // should not be called often
  66   void delAdjIGNode(const IGNode *const Node);
  67
  68   inline unsigned int getNumOfNeighbors() const
  69     { return AdjList.size() ; }
  70
  71
  72   inline bool isOnStack() const
  73     { return OnStack; }
  74
  75   // remove form IG and pushes on to stack (reduce the degree of neighbors)
  76   void pushOnStack();
  77
  78   // CurDegree is the effective number of neighbors when neighbors are
  79   // pushed on to the stack during the coloring phase. Must be called
  80   // after all modifications to the IG are over (i.e., all neighbors are
  81   // fixed).
  82
  83   inline void setCurDegree()
  84     { assert( CurDegree == -1);   CurDegree = AdjList.size(); }
  85
  86   inline int getCurDegree() const
  87     { return CurDegree; }
  88
  89   // called when a neigh is pushed on to stack
  90   inline void decCurDegree()
  91     { assert( CurDegree > 0 ); --CurDegree; }
  92
  93
  94   // The following methods call the methods in ParentLR
  95   // They are added to this class for convenience
  96   // If many of these are called within a single scope,
  97   // consider calling the methods directly on LR
  98
  99
 100   inline void setRegClass(RegClass *const RC)
 101     { ParentLR->setRegClass(RC);  }
 102
 103   inline RegClass *const getRegClass() const
 104     { return ParentLR->getRegClass(); }
 105
 106   inline bool hasColor() const
 107     { return ParentLR->hasColor();  }
 108
 109   inline unsigned int getColor() const
 110     { return ParentLR->getColor();  }
 111
 112   inline void setColor(unsigned int Col)
 113     { ParentLR->setColor(Col);  }
 114
 115   inline void markForSpill()
 116     { ParentLR->markForSpill();  }
 117
 118   inline void markForSaveAcrossCalls()
 119     { ParentLR->markForSaveAcrossCalls();  }
 120
 121   // inline void markForLoadFromStack()
 122   //  { ParentLR->markForLoadFromStack();  }
 123
 124
 125   inline unsigned int getNumOfCallInterferences() const
 126     { return ParentLR->getNumOfCallInterferences(); }
 127
 128   inline LiveRange *getParentLR() const
 129     { return ParentLR; }
 130
 131   inline Type::PrimitiveID getTypeID() const
 132     { return ParentLR->getTypeID(); }
 133
 134
 135
 136   //---- constructor and destructor ----
 137
 138
 139   IGNode(LiveRange *const LR, unsigned int index);
 140
 141   ~IGNode() { }                         // an empty destructor
 142
 143
 144 };
 145
 146
 147
 148
 149
 150
 151
 152 #endif