LLVM API Documentation
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