Implement a "union-findy" version of DS-Analysis, which eliminates the
[oota-llvm.git] / include / llvm / Analysis / DataStructure / DSSupport.h
1 //===- DSSupport.h - Support for datastructure graphs -----------*- C++ -*-===//
2 //
3 // Support for graph nodes, call sites, and types.
4 //
5 //===----------------------------------------------------------------------===//
6
7 #ifndef LLVM_ANALYSIS_DSSUPPORT_H
8 #define LLVM_ANALYSIS_DSSUPPORT_H
9
10 #include <vector>
11 #include <functional>
12 #include <string>
13 #include "Support/HashExtras.h"
14 #include "Support/hash_set"
15
16 class Function;
17 class CallInst;
18 class Value;
19 class GlobalValue;
20 class Type;
21
22 class DSNode;                  // Each node in the graph
23 class DSGraph;                 // A graph for a function
24
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
28   };
29
30   // isPointerType - Return true if this first class type is big enough to hold
31   // a pointer.
32   //
33   bool isPointerType(const Type *Ty);
34 };
35
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.
41 ///
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.
46 ///
47 class DSNodeHandle {
48   mutable DSNode *N;
49   mutable unsigned Offset;
50   void operator==(const DSNode *N);  // DISALLOW, use to promote N to nodehandle
51 public:
52   // Allow construction, destruction, and assignment...
53   DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
54     setNode(n);
55   }
56   DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) {
57     setNode(H.getNode());
58     Offset = H.Offset;      // Must read offset AFTER the getNode()
59   }
60   ~DSNodeHandle() { setNode((DSNode*)0); }
61   DSNodeHandle &operator=(const DSNodeHandle &H) {
62     Offset = 0; setNode(H.getNode()); Offset = H.Offset;
63     return *this;
64   }
65
66   bool operator<(const DSNodeHandle &H) const {  // Allow sorting
67     return getNode() < H.getNode() || (N == H.N && Offset < H.Offset);
68   }
69   bool operator>(const DSNodeHandle &H) const { return H < *this; }
70   bool operator==(const DSNodeHandle &H) const { // Allow comparison
71     return getNode() == H.getNode() && Offset == H.Offset;
72   }
73   bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
74
75   inline void swap(DSNodeHandle &NH) {
76     std::swap(Offset, NH.Offset);
77     std::swap(N, NH.N);
78   }
79
80   /// isNull - Check to see if getNode() == 0, without going through the trouble
81   /// of checking to see if we are forwarding...
82   bool isNull() const { return N == 0; }
83
84   // Allow explicit conversion to DSNode...
85   inline DSNode *getNode() const;  // Defined inline in DSNode.h
86   unsigned getOffset() const { return Offset; }
87
88   inline void setNode(DSNode *N);  // Defined inline in DSNode.h
89   void setOffset(unsigned O) {
90     //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
91     //       !N->ForwardNH.isNull()) && "Node handle offset out of range!");
92     //assert((!N || O < N->Size || (N->Size == 0 && O == 0) ||
93     //       !N->ForwardNH.isNull()) && "Node handle offset out of range!");
94     Offset = O;
95   }
96
97   void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
98   void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
99
100   /// mergeWith - Merge the logical node pointed to by 'this' with the node
101   /// pointed to by 'N'.
102   ///
103   void mergeWith(const DSNodeHandle &N);
104
105   // hasLink - Return true if there is a link at the specified offset...
106   inline bool hasLink(unsigned Num) const;
107
108   /// getLink - Treat this current node pointer as a pointer to a structure of
109   /// some sort.  This method will return the pointer a mem[this+Num]
110   ///
111   inline const DSNodeHandle &getLink(unsigned Num) const;
112   inline DSNodeHandle &getLink(unsigned Num);
113
114   inline void setLink(unsigned Num, const DSNodeHandle &NH);
115 };
116
117 namespace std {
118   inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); }
119 }
120
121 //===----------------------------------------------------------------------===//
122 /// DSCallSite - Representation of a call site via its call instruction,
123 /// the DSNode handle for the callee function (or function pointer), and
124 /// the DSNode handles for the function arguments.
125 /// 
126 class DSCallSite {
127   CallInst    *Inst;                 // Actual call site
128   Function    *CalleeF;              // The function called (direct call)
129   DSNodeHandle CalleeN;              // The function node called (indirect call)
130   DSNodeHandle RetVal;               // Returned value
131   std::vector<DSNodeHandle> CallArgs;// The pointer arguments
132
133   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
134                      const hash_map<const DSNode*, DSNode*> &NodeMap) {
135     if (DSNode *N = Src.getNode()) {
136       hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
137       assert(I != NodeMap.end() && "Not not in mapping!");
138
139       NH.setOffset(Src.getOffset());
140       NH.setNode(I->second);
141     }
142   }
143
144   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
145                      const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
146     if (DSNode *N = Src.getNode()) {
147       hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
148       assert(I != NodeMap.end() && "Not not in mapping!");
149
150       NH.setOffset(Src.getOffset()+I->second.getOffset());
151       NH.setNode(I->second.getNode());
152     }
153   }
154
155   DSCallSite();                         // DO NOT IMPLEMENT
156 public:
157   /// Constructor.  Note - This ctor destroys the argument vector passed in.  On
158   /// exit, the argument vector is empty.
159   ///
160   DSCallSite(CallInst &inst, const DSNodeHandle &rv, DSNode *Callee,
161              std::vector<DSNodeHandle> &Args)
162     : Inst(&inst), CalleeF(0), CalleeN(Callee), RetVal(rv) {
163     assert(Callee && "Null callee node specified for call site!");
164     Args.swap(CallArgs);
165   }
166   DSCallSite(CallInst &inst, const DSNodeHandle &rv, Function *Callee,
167              std::vector<DSNodeHandle> &Args)
168     : Inst(&inst), CalleeF(Callee), RetVal(rv) {
169     assert(Callee && "Null callee function specified for call site!");
170     Args.swap(CallArgs);
171   }
172
173   DSCallSite(const DSCallSite &DSCS)   // Simple copy ctor
174     : Inst(DSCS.Inst), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN),
175       RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {}
176
177   /// Mapping copy constructor - This constructor takes a preexisting call site
178   /// to copy plus a map that specifies how the links should be transformed.
179   /// This is useful when moving a call site from one graph to another.
180   ///
181   template<typename MapTy>
182   DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) {
183     Inst = FromCall.Inst;
184     InitNH(RetVal, FromCall.RetVal, NodeMap);
185     InitNH(CalleeN, FromCall.CalleeN, NodeMap);
186     CalleeF = FromCall.CalleeF;
187
188     CallArgs.resize(FromCall.CallArgs.size());
189     for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
190       InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
191   }
192
193   /// isDirectCall - Return true if this call site is a direct call of the
194   /// function specified by getCalleeFunc.  If not, it is an indirect call to
195   /// the node specified by getCalleeNode.
196   ///
197   bool isDirectCall() const { return CalleeF != 0; }
198   bool isIndirectCall() const { return !isDirectCall(); }
199
200
201   // Accessor functions...
202   Function           &getCaller()     const;
203   CallInst           &getCallInst()   const { return *Inst; }
204         DSNodeHandle &getRetVal()           { return RetVal; }
205   const DSNodeHandle &getRetVal()     const { return RetVal; }
206
207   DSNode *getCalleeNode() const {
208     assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode();
209   }
210   Function *getCalleeFunc() const {
211     assert(!CalleeN.getNode() && CalleeF); return CalleeF;
212   }
213
214   unsigned            getNumPtrArgs() const { return CallArgs.size(); }
215
216   DSNodeHandle &getPtrArg(unsigned i) {
217     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
218     return CallArgs[i];
219   }
220   const DSNodeHandle &getPtrArg(unsigned i) const {
221     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
222     return CallArgs[i];
223   }
224
225   void swap(DSCallSite &CS) {
226     if (this != &CS) {
227       std::swap(Inst, CS.Inst);
228       std::swap(RetVal, CS.RetVal);
229       std::swap(CalleeN, CS.CalleeN);
230       std::swap(CalleeF, CS.CalleeF);
231       std::swap(CallArgs, CS.CallArgs);
232     }
233   }
234
235   // MergeWith - Merge the return value and parameters of the these two call
236   // sites.
237   void mergeWith(DSCallSite &CS) {
238     getRetVal().mergeWith(CS.getRetVal());
239     unsigned MinArgs = getNumPtrArgs();
240     if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
241
242     for (unsigned a = 0; a != MinArgs; ++a)
243       getPtrArg(a).mergeWith(CS.getPtrArg(a));
244   }
245
246   /// markReachableNodes - This method recursively traverses the specified
247   /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
248   /// adds to the set, which allows it to only traverse visited nodes once.
249   ///
250   void markReachableNodes(hash_set<DSNode*> &Nodes);
251
252   bool operator<(const DSCallSite &CS) const {
253     if (isDirectCall()) {      // This must sort by callee first!
254       if (CS.isIndirectCall()) return true;
255       if (CalleeF < CS.CalleeF) return true;
256       if (CalleeF > CS.CalleeF) return false;
257     } else {
258       if (CS.isDirectCall()) return false;
259       if (CalleeN < CS.CalleeN) return true;
260       if (CalleeN > CS.CalleeN) return false;
261     }
262     if (RetVal < CS.RetVal) return true;
263     if (RetVal > CS.RetVal) return false;
264     return CallArgs < CS.CallArgs;
265   }
266
267   bool operator==(const DSCallSite &CS) const {
268     return RetVal == CS.RetVal && CalleeN == CS.CalleeN &&
269            CalleeF == CS.CalleeF && CallArgs == CS.CallArgs;
270   }
271 };
272
273 namespace std {
274   inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); }
275 }
276 #endif