1 /* Title: IGNode.h -*- C++ -*-
2 Author: Ruchira Sasanka
4 Purpose: Represents a node in an interference graph.
7 For efficiency, the AdjList is updated only once - ie. we can add but not
8 remove nodes from AdjList.
10 The removal of nodes from IG is simulated by decrementing the CurDegree.
11 If this node is put on stack (that is removed from IG), the CurDegree of all
12 the neighbors are decremented and this node is marked OnSack. Hence
13 the effective neighbors in the AdjList are the ones that do not have the
14 OnStack flag set (therefore, they are in the IG).
16 The methods that modify/use the CurDegree Must be called only
17 after all modifications to the IG are over (i.e., all neighbors are fixed).
19 The vector representation is the most efficient one for adj list.
20 Though nodes are removed when coalsing is done, we access it in sequence
21 for far many times when coloring (colorNode()).
28 #include "llvm/CodeGen/LiveRange.h"
31 //----------------------------------------------------------------------------
34 // Represents a node in an interference graph.
35 //----------------------------------------------------------------------------
38 const unsigned Index; // index within IGNodeList
39 bool OnStack; // this has been pushed on to stack for coloring
40 std::vector<IGNode *> AdjList;// adjacency list for this live range
44 // set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
45 // all adjacency lists.
46 // Decremented when a neighbor is pushed on to the stack.
47 // After that, never incremented/set again nor used.
49 LiveRange *const ParentLR;
52 IGNode(LiveRange *LR, unsigned index) : Index(index), ParentLR(LR) {
55 ParentLR->setUserIGNode(this);
58 inline unsigned int getIndex() const { return Index; }
60 // adjLists must be updated only once. However, the CurDegree can be changed
62 inline void addAdjIGNode(IGNode *AdjNode) { AdjList.push_back(AdjNode); }
64 inline IGNode *getAdjIGNode(unsigned ind) const
65 { assert ( ind < AdjList.size()); return AdjList[ind]; }
67 // delete a node in AdjList - node must be in the list
68 // should not be called often
70 void delAdjIGNode(const IGNode *Node);
72 inline unsigned getNumOfNeighbors() const { return AdjList.size(); }
74 // Get the number of unique neighbors if these two nodes are merged
75 unsigned getCombinedDegree(const IGNode* otherNode) const;
77 inline bool isOnStack() const { return OnStack; }
79 // remove form IG and pushes on to stack (reduce the degree of neighbors)
83 // CurDegree is the effective number of neighbors when neighbors are
84 // pushed on to the stack during the coloring phase. Must be called
85 // after all modifications to the IG are over (i.e., all neighbors are
88 inline void setCurDegree() {
89 assert(CurDegree == -1);
90 CurDegree = AdjList.size();
93 inline int getCurDegree() const { return CurDegree; }
95 // called when a neigh is pushed on to stack
97 inline void decCurDegree() { assert(CurDegree > 0); --CurDegree; }
100 // The following methods call the methods in ParentLR
101 // They are added to this class for convenience
102 // If many of these are called within a single scope,
103 // consider calling the methods directly on LR
105 inline void setRegClass(RegClass *RC) { ParentLR->setRegClass(RC); }
107 inline RegClass *getRegClass() const { return ParentLR->getRegClass(); }
109 inline bool hasColor() const { return ParentLR->hasColor(); }
111 inline unsigned int getColor() const { return ParentLR->getColor(); }
113 inline void setColor(unsigned Col) { ParentLR->setColor(Col); }
115 inline void markForSpill() { ParentLR->markForSpill(); }
117 inline void markForSaveAcrossCalls() { ParentLR->markForSaveAcrossCalls(); }
119 inline unsigned int isCallInterference() const
120 { return ParentLR->isCallInterference(); }
122 inline LiveRange *getParentLR() const { return ParentLR; }