lib/Target/SparcV9/RegAlloc/IGNode.h

   1 //===-- IGNode.h - Represent a node in an interference graph ----*- C++ -*-===//
   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 // This file represents a node in an interference graph.
  11 //
  12 // For efficiency, the AdjList is updated only once - ie. we can add but not
  13 // remove nodes from AdjList.
  14 //
  15 // The removal of nodes from IG is simulated by decrementing the CurDegree.
  16 // If this node is put on stack (that is removed from IG), the CurDegree of all
  17 // the neighbors are decremented and this node is marked OnStack. Hence
  18 // the effective neighbors in the AdjList are the ones that do not have the
  19 // OnStack flag set (therefore, they are in the IG).
  20 //
  21 // The methods that modify/use the CurDegree must be called only
  22 // after all modifications to the IG are over (i.e., all neighbors are fixed).
  23 //
  24 // The vector representation is the most efficient one for adj list.
  25 // Though nodes are removed when coalescing is done, we access it in sequence
  26 // for far many times when coloring (colorNode()).
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #ifndef IGNODE_H
  31 #define IGNODE_H
  32
  33 #include "LiveRange.h"
  34 #include <vector>
  35 class RegClass;
  36
  37 //----------------------------------------------------------------------------
  38 // Class IGNode
  39 //
  40 // Represents a node in an interference graph.
  41 //----------------------------------------------------------------------------
  42
  43 class IGNode {
  44   const unsigned Index;         // index within IGNodeList
  45   bool OnStack;                 // this has been pushed on to stack for coloring
  46   std::vector<IGNode *> AdjList;// adjacency list for this live range
  47
  48   int CurDegree;
  49   //
  50   // set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
  51   // all adjacency lists.
  52   // Decremented when a neighbor is pushed on to the stack.
  53   // After that, never incremented/set again nor used.
  54
  55   LiveRange *const ParentLR;
  56 public:
  57
  58   IGNode(LiveRange *LR, unsigned index) : Index(index), ParentLR(LR) {
  59     OnStack = false;
  60     CurDegree = -1;
  61     ParentLR->setUserIGNode(this);
  62   }
  63
  64   inline unsigned int getIndex() const { return Index; }
  65
  66   // adjLists must be updated only once.  However, the CurDegree can be changed
  67   //
  68   inline void addAdjIGNode(IGNode *AdjNode) { AdjList.push_back(AdjNode);  }
  69
  70   inline IGNode *getAdjIGNode(unsigned ind) const
  71     { assert ( ind < AdjList.size()); return AdjList[ind]; }
  72
  73   // delete a node in AdjList - node must be in the list
  74   // should not be called often
  75   //
  76   void delAdjIGNode(const IGNode *Node);
  77
  78   inline unsigned getNumOfNeighbors() const { return AdjList.size(); }
  79
  80   // Get the number of unique neighbors if these two nodes are merged
  81   unsigned getCombinedDegree(const IGNode* otherNode) const;
  82
  83   inline bool isOnStack() const { return OnStack; }
  84
  85   // remove form IG and pushes on to stack (reduce the degree of neighbors)
  86   //
  87   void pushOnStack();
  88
  89   // CurDegree is the effective number of neighbors when neighbors are
  90   // pushed on to the stack during the coloring phase. Must be called
  91   // after all modifications to the IG are over (i.e., all neighbors are
  92   // fixed).
  93   //
  94   inline void setCurDegree() {
  95     assert(CurDegree == -1);
  96     CurDegree = AdjList.size();
  97   }
  98
  99   inline int getCurDegree() const { return CurDegree; }
 100
 101   // called when a neigh is pushed on to stack
 102   //
 103   inline void decCurDegree() { assert(CurDegree > 0); --CurDegree; }
 104
 105   // The following methods call the methods in ParentLR
 106   // They are added to this class for convenience
 107   // If many of these are called within a single scope,
 108   // consider calling the methods directly on LR
 109   inline bool hasColor() const { return ParentLR->hasColor();  }
 110
 111   inline unsigned int getColor() const { return ParentLR->getColor();  }
 112
 113   inline void setColor(unsigned Col) { ParentLR->setColor(Col);  }
 114
 115   inline LiveRange *getParentLR() const { return ParentLR; }
 116 };
 117
 118 #endif