1 //===-- IGNode.h - Represent a node in an interference graph ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file represents a node in an interference graph.
12 // For efficiency, the AdjList is updated only once - ie. we can add but not
13 // remove nodes from AdjList.
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).
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).
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()).
28 //===----------------------------------------------------------------------===//
33 #include "LiveRange.h"
40 //----------------------------------------------------------------------------
43 // Represents a node in an interference graph.
44 //----------------------------------------------------------------------------
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
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.
58 LiveRange *const ParentLR;
61 IGNode(LiveRange *LR, unsigned index) : Index(index), ParentLR(LR) {
64 ParentLR->setUserIGNode(this);
67 inline unsigned int getIndex() const { return Index; }
69 // adjLists must be updated only once. However, the CurDegree can be changed
71 inline void addAdjIGNode(IGNode *AdjNode) { AdjList.push_back(AdjNode); }
73 inline IGNode *getAdjIGNode(unsigned ind) const
74 { assert ( ind < AdjList.size()); return AdjList[ind]; }
76 // delete a node in AdjList - node must be in the list
77 // should not be called often
79 void delAdjIGNode(const IGNode *Node);
81 inline unsigned getNumOfNeighbors() const { return AdjList.size(); }
83 // Get the number of unique neighbors if these two nodes are merged
84 unsigned getCombinedDegree(const IGNode* otherNode) const;
86 inline bool isOnStack() const { return OnStack; }
88 // remove form IG and pushes on to stack (reduce the degree of neighbors)
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
97 inline void setCurDegree() {
98 assert(CurDegree == -1);
99 CurDegree = AdjList.size();
102 inline int getCurDegree() const { return CurDegree; }
104 // called when a neigh is pushed on to stack
106 inline void decCurDegree() { assert(CurDegree > 0); --CurDegree; }
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(); }
114 inline unsigned int getColor() const { return ParentLR->getColor(); }
116 inline void setColor(unsigned Col) { ParentLR->setColor(Col); }
118 inline LiveRange *getParentLR() const { return ParentLR; }
121 } // End llvm namespace