1 //===- DSSupport.h - Support for datastructure graphs -----------*- 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 // Support for graph nodes, call sites, and types.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_DSSUPPORT_H
15 #define LLVM_ANALYSIS_DSSUPPORT_H
18 #include "llvm/ADT/hash_map"
19 #include "llvm/ADT/hash_set"
20 #include "llvm/Support/CallSite.h"
30 class DSNode; // Each node in the graph
31 class DSGraph; // A graph for a function
32 class ReachabilityCloner;
34 namespace DS { // FIXME: After the paper, this should get cleaned up
35 enum { PointerShift = 2, // 64bit ptrs = 3, 32 bit ptrs = 2
36 PointerSize = 1 << PointerShift
39 /// isPointerType - Return true if this first class type is big enough to hold
42 bool isPointerType(const Type *Ty);
45 //===----------------------------------------------------------------------===//
46 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care
47 /// of all of the add/un'refing of the node to prevent the backpointers in the
48 /// graph from getting out of date. This class represents a "pointer" in the
49 /// graph, whose destination is an indexed offset into a node.
51 /// Note: some functions that are marked as inline in DSNodeHandle are actually
52 /// defined in DSNode.h because they need knowledge of DSNode operation. Putting
53 /// them in a CPP file wouldn't help making them inlined and keeping DSNode and
54 /// DSNodeHandle (and friends) in one file complicates things.
58 mutable unsigned Offset;
59 void operator==(const DSNode *N); // DISALLOW, use to promote N to nodehandle
61 // Allow construction, destruction, and assignment...
62 DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(0) {
65 DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) {
66 DSNode *NN = H.getNode();
67 setTo(NN, H.Offset); // Must read offset AFTER the getNode()
69 ~DSNodeHandle() { setTo(0, 0); }
70 DSNodeHandle &operator=(const DSNodeHandle &H) {
71 if (&H == this) return *this; // Don't set offset to 0 if self assigning.
72 DSNode *NN = H.getNode(); // Call getNode() before .Offset
77 bool operator<(const DSNodeHandle &H) const { // Allow sorting
78 return getNode() < H.getNode() || (N == H.N && Offset < H.Offset);
80 bool operator>(const DSNodeHandle &H) const { return H < *this; }
81 bool operator==(const DSNodeHandle &H) const { // Allow comparison
82 // getNode can change the offset, so we must call getNode() first.
83 return getNode() == H.getNode() && Offset == H.Offset;
85 bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
87 inline void swap(DSNodeHandle &NH) {
88 std::swap(Offset, NH.Offset);
92 /// isNull - Check to see if getNode() == 0, without going through the trouble
93 /// of checking to see if we are forwarding...
95 bool isNull() const { return N == 0; }
97 // Allow explicit conversion to DSNode...
98 inline DSNode *getNode() const; // Defined inline in DSNode.h
99 unsigned getOffset() const {
100 assert(!isForwarding() && "This is a forwarding NH, call getNode() first!");
104 void setOffset(unsigned O) {
105 assert(!isForwarding() && "This is a forwarding NH, call getNode() first!");
106 //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
107 // !N->ForwardNH.isNull()) && "Node handle offset out of range!");
108 //assert((!N || O < N->Size || (N->Size == 0 && O == 0) ||
109 // !N->ForwardNH.isNull()) && "Node handle offset out of range!");
113 inline void setTo(DSNode *N, unsigned O) const; // Defined inline in DSNode.h
115 void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
116 void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
118 /// mergeWith - Merge the logical node pointed to by 'this' with the node
119 /// pointed to by 'N'.
121 void mergeWith(const DSNodeHandle &N) const;
123 /// hasLink - Return true if there is a link at the specified offset...
125 inline bool hasLink(unsigned Num) const;
127 /// getLink - Treat this current node pointer as a pointer to a structure of
128 /// some sort. This method will return the pointer a mem[this+Num]
130 inline const DSNodeHandle &getLink(unsigned Num) const;
131 inline DSNodeHandle &getLink(unsigned Num);
133 inline void setLink(unsigned Num, const DSNodeHandle &NH);
135 DSNode *HandleForwarding() const;
137 /// isForwarding - Return true if this NodeHandle is forwarding to another
139 bool isForwarding() const;
142 } // End llvm namespace
146 inline void swap<llvm::DSNodeHandle>(llvm::DSNodeHandle &NH1, llvm::DSNodeHandle &NH2) { NH1.swap(NH2); }
149 namespace HASH_NAMESPACE {
150 // Provide a hash function for arbitrary pointers...
151 template <> struct hash<llvm::DSNodeHandle> {
152 inline size_t operator()(const llvm::DSNodeHandle &Val) const {
153 return hash<void*>()(Val.getNode()) ^ Val.getOffset();
160 //===----------------------------------------------------------------------===//
161 /// DSCallSite - Representation of a call site via its call instruction,
162 /// the DSNode handle for the callee function (or function pointer), and
163 /// the DSNode handles for the function arguments.
166 CallSite Site; // Actual call site
167 Function *CalleeF; // The function called (direct call)
168 DSNodeHandle CalleeN; // The function node called (indirect call)
169 DSNodeHandle RetVal; // Returned value
170 std::vector<DSNodeHandle> CallArgs;// The pointer arguments
172 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
173 const hash_map<const DSNode*, DSNode*> &NodeMap) {
174 if (DSNode *N = Src.getNode()) {
175 hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
176 assert(I != NodeMap.end() && "Node not in mapping!");
177 NH.setTo(I->second, Src.getOffset());
181 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
182 const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
183 if (DSNode *N = Src.getNode()) {
184 hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
185 assert(I != NodeMap.end() && "Node not in mapping!");
187 DSNode *NN = I->second.getNode(); // Call getNode before getOffset()
188 NH.setTo(NN, Src.getOffset()+I->second.getOffset());
192 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
193 ReachabilityCloner &RC);
196 DSCallSite(); // DO NOT IMPLEMENT
198 /// Constructor. Note - This ctor destroys the argument vector passed in. On
199 /// exit, the argument vector is empty.
201 DSCallSite(CallSite CS, const DSNodeHandle &rv, DSNode *Callee,
202 std::vector<DSNodeHandle> &Args)
203 : Site(CS), CalleeF(0), CalleeN(Callee), RetVal(rv) {
204 assert(Callee && "Null callee node specified for call site!");
207 DSCallSite(CallSite CS, const DSNodeHandle &rv, Function *Callee,
208 std::vector<DSNodeHandle> &Args)
209 : Site(CS), CalleeF(Callee), RetVal(rv) {
210 assert(Callee && "Null callee function specified for call site!");
214 DSCallSite(const DSCallSite &DSCS) // Simple copy ctor
215 : Site(DSCS.Site), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN),
216 RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {}
218 /// Mapping copy constructor - This constructor takes a preexisting call site
219 /// to copy plus a map that specifies how the links should be transformed.
220 /// This is useful when moving a call site from one graph to another.
222 template<typename MapTy>
223 DSCallSite(const DSCallSite &FromCall, MapTy &NodeMap) {
224 Site = FromCall.Site;
225 InitNH(RetVal, FromCall.RetVal, NodeMap);
226 InitNH(CalleeN, FromCall.CalleeN, NodeMap);
227 CalleeF = FromCall.CalleeF;
229 CallArgs.resize(FromCall.CallArgs.size());
230 for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
231 InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
234 const DSCallSite &operator=(const DSCallSite &RHS) {
236 CalleeF = RHS.CalleeF;
237 CalleeN = RHS.CalleeN;
239 CallArgs = RHS.CallArgs;
243 /// isDirectCall - Return true if this call site is a direct call of the
244 /// function specified by getCalleeFunc. If not, it is an indirect call to
245 /// the node specified by getCalleeNode.
247 bool isDirectCall() const { return CalleeF != 0; }
248 bool isIndirectCall() const { return !isDirectCall(); }
251 // Accessor functions...
252 Function &getCaller() const;
253 CallSite getCallSite() const { return Site; }
254 DSNodeHandle &getRetVal() { return RetVal; }
255 const DSNodeHandle &getRetVal() const { return RetVal; }
257 DSNode *getCalleeNode() const {
258 assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode();
260 Function *getCalleeFunc() const {
261 assert(!CalleeN.getNode() && CalleeF); return CalleeF;
264 unsigned getNumPtrArgs() const { return CallArgs.size(); }
266 DSNodeHandle &getPtrArg(unsigned i) {
267 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
270 const DSNodeHandle &getPtrArg(unsigned i) const {
271 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
275 void addPtrArg(const DSNodeHandle &NH) {
276 CallArgs.push_back(NH);
279 void swap(DSCallSite &CS) {
281 std::swap(Site, CS.Site);
282 std::swap(RetVal, CS.RetVal);
283 std::swap(CalleeN, CS.CalleeN);
284 std::swap(CalleeF, CS.CalleeF);
285 std::swap(CallArgs, CS.CallArgs);
289 /// mergeWith - Merge the return value and parameters of the these two call
292 void mergeWith(DSCallSite &CS) {
293 getRetVal().mergeWith(CS.getRetVal());
294 unsigned MinArgs = getNumPtrArgs();
295 if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
297 for (unsigned a = 0; a != MinArgs; ++a)
298 getPtrArg(a).mergeWith(CS.getPtrArg(a));
300 for (unsigned a = MinArgs, e = CS.getNumPtrArgs(); a != e; ++a)
301 CallArgs.push_back(CS.getPtrArg(a));
304 /// markReachableNodes - This method recursively traverses the specified
305 /// DSNodes, marking any nodes which are reachable. All reachable nodes it
306 /// adds to the set, which allows it to only traverse visited nodes once.
308 void markReachableNodes(hash_set<const DSNode*> &Nodes) const;
310 bool operator<(const DSCallSite &CS) const {
311 if (isDirectCall()) { // This must sort by callee first!
312 if (CS.isIndirectCall()) return true;
313 if (CalleeF < CS.CalleeF) return true;
314 if (CalleeF > CS.CalleeF) return false;
316 if (CS.isDirectCall()) return false;
317 if (CalleeN < CS.CalleeN) return true;
318 if (CalleeN > CS.CalleeN) return false;
320 if (RetVal < CS.RetVal) return true;
321 if (RetVal > CS.RetVal) return false;
322 return CallArgs < CS.CallArgs;
325 bool operator==(const DSCallSite &CS) const {
326 return CalleeF == CS.CalleeF && CalleeN == CS.CalleeN &&
327 RetVal == CS.RetVal && CallArgs == CS.CallArgs;
331 } // End llvm namespace
335 inline void swap<llvm::DSCallSite>(llvm::DSCallSite &CS1,
336 llvm::DSCallSite &CS2) { CS1.swap(CS2); }