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 /* Title:   IGNode.h                      -*- C++ -*-
  11    Author:  Ruchira Sasanka
  12    Date:    July 25, 01
  13    Purpose: Represents a node in an interference graph.
  14    Notes:
  15
  16    For efficiency, the AdjList is updated only once - ie. we can add but not
  17    remove nodes from AdjList.
  18
  19    The removal of nodes from IG is simulated by decrementing the CurDegree.
  20    If this node is put on stack (that is removed from IG), the CurDegree of all
  21    the neighbors are decremented and this node is marked OnStack. Hence
  22    the effective neighbors in the AdjList are the ones that do not have the
  23    OnStack flag set (therefore, they are in the IG).
  24
  25    The methods that modify/use the CurDegree must be called only
  26    after all modifications to the IG are over (i.e., all neighbors are fixed).
  27
  28    The vector representation is the most efficient one for adj list.
  29    Though nodes are removed when coalescing is done, we access it in sequence
  30    for far many times when coloring (colorNode()).
  31 */
  32
  33 #ifndef IGNODE_H
  34 #define IGNODE_H
  35
  36 #include "LiveRange.h"
  37 #include <vector>
  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 #endif