1 //===- DSSupport.h - Support for datastructure graphs -----------*- C++ -*-===//
3 // Support for graph nodes, call sites, and types.
5 //===----------------------------------------------------------------------===//
7 #ifndef LLVM_ANALYSIS_DSSUPPORT_H
8 #define LLVM_ANALYSIS_DSSUPPORT_H
13 #include "Support/HashExtras.h"
14 #include "Support/hash_set"
22 class DSNode; // Each node in the graph
23 class DSGraph; // A graph for a function
25 namespace DS { // FIXME: After the paper, this should get cleaned up
26 enum { PointerShift = 3, // 64bit ptrs = 3, 32 bit ptrs = 2
27 PointerSize = 1 << PointerShift
30 // isPointerType - Return true if this first class type is big enough to hold
33 bool isPointerType(const Type *Ty);
36 //===----------------------------------------------------------------------===//
37 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care
38 /// of all of the add/un'refing of the node to prevent the backpointers in the
39 /// graph from getting out of date. This class represents a "pointer" in the
40 /// graph, whose destination is an indexed offset into a node.
42 /// Note: some functions that are marked as inline in DSNodeHandle are actually
43 /// defined in DSNode.h because they need knowledge of DSNode operation. Putting
44 /// them in a CPP file wouldn't help making them inlined and keeping DSNode and
45 /// DSNodeHandle (and friends) in one file complicates things.
50 void operator==(const DSNode *N); // DISALLOW, use to promote N to nodehandle
52 // Allow construction, destruction, and assignment...
53 DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
56 DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); }
57 ~DSNodeHandle() { setNode((DSNode*)0); }
58 DSNodeHandle &operator=(const DSNodeHandle &H) {
59 setNode(H.N); Offset = H.Offset;
63 bool operator<(const DSNodeHandle &H) const { // Allow sorting
64 return N < H.N || (N == H.N && Offset < H.Offset);
66 bool operator>(const DSNodeHandle &H) const { return H < *this; }
67 bool operator==(const DSNodeHandle &H) const { // Allow comparison
68 return N == H.N && Offset == H.Offset;
70 bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
72 inline void swap(DSNodeHandle &H);
74 // Allow explicit conversion to DSNode...
75 DSNode *getNode() const { return N; }
76 unsigned getOffset() const { return Offset; }
78 inline void setNode(DSNode *N); // Defined inline later...
79 void setOffset(unsigned O) { Offset = O; }
81 void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
82 void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
84 /// mergeWith - Merge the logical node pointed to by 'this' with the node
85 /// pointed to by 'N'.
87 void mergeWith(const DSNodeHandle &N);
89 // hasLink - Return true if there is a link at the specified offset...
90 inline bool hasLink(unsigned Num) const;
92 /// getLink - Treat this current node pointer as a pointer to a structure of
93 /// some sort. This method will return the pointer a mem[this+Num]
95 inline const DSNodeHandle &getLink(unsigned Num) const;
96 inline DSNodeHandle &getLink(unsigned Num);
98 inline void setLink(unsigned Num, const DSNodeHandle &NH);
101 inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); }
103 //===----------------------------------------------------------------------===//
104 /// DSCallSite - Representation of a call site via its call instruction,
105 /// the DSNode handle for the callee function (or function pointer), and
106 /// the DSNode handles for the function arguments.
109 CallInst *Inst; // Actual call site
110 Function *CalleeF; // The function called (direct call)
111 DSNodeHandle CalleeN; // The function node called (indirect call)
112 DSNodeHandle RetVal; // Returned value
113 std::vector<DSNodeHandle> CallArgs;// The pointer arguments
115 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
116 const hash_map<const DSNode*, DSNode*> &NodeMap) {
117 if (DSNode *N = Src.getNode()) {
118 hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
119 assert(I != NodeMap.end() && "Not not in mapping!");
121 NH.setOffset(Src.getOffset());
122 NH.setNode(I->second);
126 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
127 const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
128 if (DSNode *N = Src.getNode()) {
129 hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
130 assert(I != NodeMap.end() && "Not not in mapping!");
132 NH.setOffset(Src.getOffset()+I->second.getOffset());
133 NH.setNode(I->second.getNode());
137 DSCallSite(); // DO NOT IMPLEMENT
139 /// Constructor. Note - This ctor destroys the argument vector passed in. On
140 /// exit, the argument vector is empty.
142 DSCallSite(CallInst &inst, const DSNodeHandle &rv, DSNode *Callee,
143 std::vector<DSNodeHandle> &Args)
144 : Inst(&inst), CalleeF(0), CalleeN(Callee), RetVal(rv) {
145 assert(Callee && "Null callee node specified for call site!");
148 DSCallSite(CallInst &inst, const DSNodeHandle &rv, Function *Callee,
149 std::vector<DSNodeHandle> &Args)
150 : Inst(&inst), CalleeF(Callee), RetVal(rv) {
151 assert(Callee && "Null callee function specified for call site!");
155 DSCallSite(const DSCallSite &DSCS) // Simple copy ctor
156 : Inst(DSCS.Inst), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN),
157 RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {}
159 /// Mapping copy constructor - This constructor takes a preexisting call site
160 /// to copy plus a map that specifies how the links should be transformed.
161 /// This is useful when moving a call site from one graph to another.
163 template<typename MapTy>
164 DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) {
165 Inst = FromCall.Inst;
166 InitNH(RetVal, FromCall.RetVal, NodeMap);
167 InitNH(CalleeN, FromCall.CalleeN, NodeMap);
168 CalleeF = FromCall.CalleeF;
170 CallArgs.resize(FromCall.CallArgs.size());
171 for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
172 InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
175 /// isDirectCall - Return true if this call site is a direct call of the
176 /// function specified by getCalleeFunc. If not, it is an indirect call to
177 /// the node specified by getCalleeNode.
179 bool isDirectCall() const { return CalleeF != 0; }
180 bool isIndirectCall() const { return !isDirectCall(); }
183 // Accessor functions...
184 Function &getCaller() const;
185 CallInst &getCallInst() const { return *Inst; }
186 DSNodeHandle &getRetVal() { return RetVal; }
187 const DSNodeHandle &getRetVal() const { return RetVal; }
189 DSNode *getCalleeNode() const {
190 assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode();
192 Function *getCalleeFunc() const {
193 assert(!CalleeN.getNode() && CalleeF); return CalleeF;
196 unsigned getNumPtrArgs() const { return CallArgs.size(); }
198 DSNodeHandle &getPtrArg(unsigned i) {
199 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
202 const DSNodeHandle &getPtrArg(unsigned i) const {
203 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
207 void swap(DSCallSite &CS) {
209 std::swap(Inst, CS.Inst);
210 std::swap(RetVal, CS.RetVal);
211 std::swap(CalleeN, CS.CalleeN);
212 std::swap(CalleeF, CS.CalleeF);
213 std::swap(CallArgs, CS.CallArgs);
217 // MergeWith - Merge the return value and parameters of the these two call
219 void mergeWith(DSCallSite &CS) {
220 getRetVal().mergeWith(CS.getRetVal());
221 unsigned MinArgs = getNumPtrArgs();
222 if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
224 for (unsigned a = 0; a != MinArgs; ++a)
225 getPtrArg(a).mergeWith(CS.getPtrArg(a));
228 /// markReachableNodes - This method recursively traverses the specified
229 /// DSNodes, marking any nodes which are reachable. All reachable nodes it
230 /// adds to the set, which allows it to only traverse visited nodes once.
232 void markReachableNodes(hash_set<DSNode*> &Nodes);
234 bool operator<(const DSCallSite &CS) const {
235 if (isDirectCall()) { // This must sort by callee first!
236 if (CS.isIndirectCall()) return true;
237 if (CalleeF < CS.CalleeF) return true;
238 if (CalleeF > CS.CalleeF) return false;
240 if (CS.isDirectCall()) return false;
241 if (CalleeN < CS.CalleeN) return true;
242 if (CalleeN > CS.CalleeN) return false;
244 if (RetVal < CS.RetVal) return true;
245 if (RetVal > CS.RetVal) return false;
246 return CallArgs < CS.CallArgs;
249 bool operator==(const DSCallSite &CS) const {
250 return RetVal == CS.RetVal && CalleeN == CS.CalleeN &&
251 CalleeF == CS.CalleeF && CallArgs == CS.CallArgs;
255 inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); }