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
21 class DSNode; // Each node in the graph
22 class DSGraph; // A graph for a function
23 class DSNodeIterator; // Data structure graph traversal iterator
25 //===----------------------------------------------------------------------===//
26 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care
27 /// of all of the add/un'refing of the node to prevent the backpointers in the
28 /// graph from getting out of date. This class represents a "pointer" in the
29 /// graph, whose destination is an indexed offset into a node.
35 // Allow construction, destruction, and assignment...
36 DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
39 DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); }
40 ~DSNodeHandle() { setNode((DSNode*)0); }
41 DSNodeHandle &operator=(const DSNodeHandle &H) {
42 setNode(H.N); Offset = H.Offset;
46 bool operator<(const DSNodeHandle &H) const { // Allow sorting
47 return N < H.N || (N == H.N && Offset < H.Offset);
49 bool operator>(const DSNodeHandle &H) const { return H < *this; }
50 bool operator==(const DSNodeHandle &H) const { // Allow comparison
51 return N == H.N && Offset == H.Offset;
53 bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
55 // Allow explicit conversion to DSNode...
56 DSNode *getNode() const { return N; }
57 unsigned getOffset() const { return Offset; }
59 inline void setNode(DSNode *N); // Defined inline later...
60 void setOffset(unsigned O) { Offset = O; }
62 void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
63 void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
65 /// mergeWith - Merge the logical node pointed to by 'this' with the node
66 /// pointed to by 'N'.
68 void mergeWith(const DSNodeHandle &N);
70 // hasLink - Return true if there is a link at the specified offset...
71 inline bool hasLink(unsigned Num) const;
73 /// getLink - Treat this current node pointer as a pointer to a structure of
74 /// some sort. This method will return the pointer a mem[this+Num]
76 inline const DSNodeHandle *getLink(unsigned Num) const;
77 inline DSNodeHandle *getLink(unsigned Num);
79 inline void setLink(unsigned Num, const DSNodeHandle &NH);
83 //===----------------------------------------------------------------------===//
84 /// DSTypeRec - This structure is used to represent a single type that is held
88 const Type *Ty; // The type itself...
89 unsigned Offset; // The offset in the node
90 bool isArray; // Have we accessed an array of elements?
92 DSTypeRec() : Ty(0), Offset(0), isArray(false) {}
93 DSTypeRec(const Type *T, unsigned O) : Ty(T), Offset(O), isArray(false) {}
95 bool operator<(const DSTypeRec &TR) const {
96 // Sort first by offset!
97 return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty);
99 bool operator==(const DSTypeRec &TR) const {
100 return Ty == TR.Ty && Offset == TR.Offset;
102 bool operator!=(const DSTypeRec &TR) const { return !operator==(TR); }
109 //===----------------------------------------------------------------------===//
110 /// DSCallSite - Representation of a call site via its call instruction,
111 /// the DSNode handle for the callee function (or function pointer), and
112 /// the DSNode handles for the function arguments.
114 /// One unusual aspect of this callsite record is the ResolvingCaller member.
115 /// If this is non-null, then it indicates the function that allowed a call-site
116 /// to finally be resolved. Because of indirect calls, this function may not
117 /// actually be the function that contains the Call instruction itself. This is
118 /// used by the BU and TD passes to communicate.
121 CallInst *Inst; // Actual call site
122 DSNodeHandle RetVal; // Returned value
123 DSNodeHandle Callee; // The function node called
124 std::vector<DSNodeHandle> CallArgs; // The pointer arguments
125 Function *ResolvingCaller; // See comments above
127 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
128 const std::map<const DSNode*, DSNode*> &NodeMap) {
129 if (DSNode *N = Src.getNode()) {
130 std::map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
131 assert(I != NodeMap.end() && "Not not in mapping!");
133 NH.setOffset(Src.getOffset());
134 NH.setNode(I->second);
138 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
139 const std::map<const DSNode*, DSNodeHandle> &NodeMap) {
140 if (DSNode *N = Src.getNode()) {
141 std::map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
142 assert(I != NodeMap.end() && "Not not in mapping!");
144 NH.setOffset(Src.getOffset()+I->second.getOffset());
145 NH.setNode(I->second.getNode());
149 DSCallSite(); // DO NOT IMPLEMENT
151 /// Constructor. Note - This ctor destroys the argument vector passed in. On
152 /// exit, the argument vector is empty.
154 DSCallSite(CallInst &inst, const DSNodeHandle &rv, const DSNodeHandle &callee,
155 std::vector<DSNodeHandle> &Args)
156 : Inst(&inst), RetVal(rv), Callee(callee), ResolvingCaller(0) {
160 DSCallSite(const DSCallSite &DSCS) // Simple copy ctor
161 : Inst(DSCS.Inst), RetVal(DSCS.RetVal),
162 Callee(DSCS.Callee), CallArgs(DSCS.CallArgs),
163 ResolvingCaller(DSCS.ResolvingCaller) {}
165 /// Mapping copy constructor - This constructor takes a preexisting call site
166 /// to copy plus a map that specifies how the links should be transformed.
167 /// This is useful when moving a call site from one graph to another.
169 template<typename MapTy>
170 DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) {
171 Inst = FromCall.Inst;
172 InitNH(RetVal, FromCall.RetVal, NodeMap);
173 InitNH(Callee, FromCall.Callee, NodeMap);
175 CallArgs.resize(FromCall.CallArgs.size());
176 for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
177 InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
178 ResolvingCaller = FromCall.ResolvingCaller;
181 // Accessor functions...
182 Function &getCaller() const;
183 CallInst &getCallInst() const { return *Inst; }
184 DSNodeHandle &getRetVal() { return RetVal; }
185 DSNodeHandle &getCallee() { return Callee; }
186 const DSNodeHandle &getRetVal() const { return RetVal; }
187 const DSNodeHandle &getCallee() const { return Callee; }
188 void setCallee(const DSNodeHandle &H) { Callee = H; }
190 unsigned getNumPtrArgs() const { return CallArgs.size(); }
192 Function *getResolvingCaller() const { return ResolvingCaller; }
193 void setResolvingCaller(Function *F) { ResolvingCaller = F; }
195 DSNodeHandle &getPtrArg(unsigned i) {
196 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
199 const DSNodeHandle &getPtrArg(unsigned i) const {
200 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
204 bool operator<(const DSCallSite &CS) const {
205 if (RetVal < CS.RetVal) return true;
206 if (RetVal > CS.RetVal) return false;
207 if (Callee < CS.Callee) return true;
208 if (Callee > CS.Callee) return false;
209 return CallArgs < CS.CallArgs;
212 bool operator==(const DSCallSite &CS) const {
213 return RetVal == CS.RetVal && Callee == CS.Callee &&
214 CallArgs == CS.CallArgs;