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 fter all modifications to the IG are over (i.e., all neighbors are fixed).
19 The vector representation 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()).
29 #include "llvm/CodeGen/RegAllocCommon.h"
30 #include "llvm/CodeGen/LiveRange.h"
36 const int Index; // index within IGNodeList
38 bool OnStack; // this has been pushed on to stack for coloring
40 vector<IGNode *> AdjList; // adjacency list for this live range
43 // set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
44 // all adjacency lists.
45 // Decremented when a neighbor is pushed on to the stack.
46 // After that, never incremented/set again nor used.
49 LiveRange *const ParentLR; // parent LR (cannot be a const)
54 inline unsigned int getIndex() const
57 // adjLists must be updated only once. However, the CurDegree can be changed
58 inline void addAdjIGNode( IGNode *const AdjNode)
59 { AdjList.push_back(AdjNode); }
61 inline IGNode * getAdjIGNode(unsigned int ind) const
62 { assert ( ind < AdjList.size()); return AdjList[ ind ]; }
64 // delete a node in AdjList - node must be in the list
65 // should not be called often
66 void delAdjIGNode(const IGNode *const Node);
68 inline unsigned int getNumOfNeighbors() const
69 { return AdjList.size() ; }
72 inline bool isOnStack() const
75 // remove form IG and pushes on to stack (reduce the degree of neighbors)
78 // CurDegree is the effective number of neighbors when neighbors are
79 // pushed on to the stack during the coloring phase. Must be called
80 // after all modifications to the IG are over (i.e., all neighbors are
83 inline void setCurDegree()
84 { assert( CurDegree == -1); CurDegree = AdjList.size(); }
86 inline int getCurDegree() const
89 // called when a neigh is pushed on to stack
90 inline void decCurDegree()
91 { assert( CurDegree > 0 ); --CurDegree; }
94 // The following methods call the methods in ParentLR
95 // They are added to this class for convenience
96 // If many of these are called within a single scope,
97 // consider calling the methods directly on LR
100 inline void setRegClass(RegClass *const RC)
101 { ParentLR->setRegClass(RC); }
103 inline RegClass *const getRegClass() const
104 { return ParentLR->getRegClass(); }
106 inline bool hasColor() const
107 { return ParentLR->hasColor(); }
109 inline unsigned int getColor() const
110 { return ParentLR->getColor(); }
112 inline void setColor(unsigned int Col)
113 { ParentLR->setColor(Col); }
115 inline void markForSpill()
116 { ParentLR->markForSpill(); }
118 inline void markForSaveAcrossCalls()
119 { ParentLR->markForSaveAcrossCalls(); }
121 // inline void markForLoadFromStack()
122 // { ParentLR->markForLoadFromStack(); }
125 inline unsigned int isCallInterference() const
126 { return ParentLR->isCallInterference(); }
128 inline LiveRange *getParentLR() const
131 inline Type::PrimitiveID getTypeID() const
132 { return ParentLR->getTypeID(); }
136 //---- constructor and destructor ----
139 IGNode(LiveRange *const LR, unsigned int index);
141 ~IGNode() { } // an empty destructor