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