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