LLVM API Documentation

IGNode.h

Go to the documentation of this file.
00001 //===-- IGNode.h - Represent a node in an interference graph ----*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file represents a node in an interference graph.
00011 //
00012 // For efficiency, the AdjList is updated only once - ie. we can add but not
00013 // remove nodes from AdjList.
00014 //
00015 // The removal of nodes from IG is simulated by decrementing the CurDegree.
00016 // If this node is put on stack (that is removed from IG), the CurDegree of all
00017 // the neighbors are decremented and this node is marked OnStack. Hence
00018 // the effective neighbors in the AdjList are the ones that do not have the
00019 // OnStack flag set (therefore, they are in the IG).
00020 //
00021 // The methods that modify/use the CurDegree must be called only
00022 // after all modifications to the IG are over (i.e., all neighbors are fixed).
00023 //
00024 // The vector representation is the most efficient one for adj list.
00025 // Though nodes are removed when coalescing is done, we access it in sequence
00026 // for far many times when coloring (colorNode()).
00027 //
00028 //===----------------------------------------------------------------------===//
00029 
00030 #ifndef IGNODE_H
00031 #define IGNODE_H
00032 
00033 #include "LiveRange.h"
00034 #include <vector>
00035 
00036 namespace llvm {
00037 
00038 class RegClass;
00039 
00040 //----------------------------------------------------------------------------
00041 // Class IGNode
00042 //
00043 // Represents a node in an interference graph.
00044 //----------------------------------------------------------------------------
00045 
00046 class IGNode {
00047   const unsigned Index;         // index within IGNodeList
00048   bool OnStack;                 // this has been pushed on to stack for coloring
00049   std::vector<IGNode *> AdjList;// adjacency list for this live range
00050 
00051   int CurDegree;
00052   //
00053   // set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
00054   // all adjacency lists.
00055   // Decremented when a neighbor is pushed on to the stack.
00056   // After that, never incremented/set again nor used.
00057 
00058   V9LiveRange *const ParentLR;
00059 public:
00060 
00061   IGNode(V9LiveRange *LR, unsigned index) : Index(index), ParentLR(LR) {
00062     OnStack = false;
00063     CurDegree = -1;
00064     ParentLR->setUserIGNode(this);
00065   }
00066 
00067   inline unsigned int getIndex() const { return Index; }
00068 
00069   // adjLists must be updated only once.  However, the CurDegree can be changed
00070   //
00071   inline void addAdjIGNode(IGNode *AdjNode) { AdjList.push_back(AdjNode);  }
00072 
00073   inline IGNode *getAdjIGNode(unsigned ind) const
00074     { assert ( ind < AdjList.size()); return AdjList[ind]; }
00075 
00076   // delete a node in AdjList - node must be in the list
00077   // should not be called often
00078   //
00079   void delAdjIGNode(const IGNode *Node);
00080 
00081   inline unsigned getNumOfNeighbors() const { return AdjList.size(); }
00082 
00083   // Get the number of unique neighbors if these two nodes are merged
00084   unsigned getCombinedDegree(const IGNode* otherNode) const;
00085 
00086   inline bool isOnStack() const { return OnStack; }
00087 
00088   // remove form IG and pushes on to stack (reduce the degree of neighbors)
00089   //
00090   void pushOnStack();
00091 
00092   // CurDegree is the effective number of neighbors when neighbors are
00093   // pushed on to the stack during the coloring phase. Must be called
00094   // after all modifications to the IG are over (i.e., all neighbors are
00095   // fixed).
00096   //
00097   inline void setCurDegree() {
00098     assert(CurDegree == -1);
00099     CurDegree = AdjList.size();
00100   }
00101 
00102   inline int getCurDegree() const { return CurDegree; }
00103 
00104   // called when a neigh is pushed on to stack
00105   //
00106   inline void decCurDegree() { assert(CurDegree > 0); --CurDegree; }
00107 
00108   // The following methods call the methods in ParentLR
00109   // They are added to this class for convenience
00110   // If many of these are called within a single scope,
00111   // consider calling the methods directly on LR
00112   inline bool hasColor() const { return ParentLR->hasColor();  }
00113 
00114   inline unsigned int getColor() const { return ParentLR->getColor();  }
00115 
00116   inline void setColor(unsigned Col) { ParentLR->setColor(Col);  }
00117 
00118   inline V9LiveRange *getParentLR() const { return ParentLR; }
00119 };
00120 
00121 } // End llvm namespace
00122 
00123 #endif