LLVM API Documentation
00001 //===- DSSupport.h - Support for datastructure graphs -----------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Support for graph nodes, call sites, and types. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ANALYSIS_DSSUPPORT_H 00015 #define LLVM_ANALYSIS_DSSUPPORT_H 00016 00017 #include <functional> 00018 #include "llvm/ADT/hash_map" 00019 #include "llvm/ADT/hash_set" 00020 #include "llvm/Support/CallSite.h" 00021 00022 namespace llvm { 00023 00024 class Function; 00025 class CallInst; 00026 class Value; 00027 class GlobalValue; 00028 class Type; 00029 00030 class DSNode; // Each node in the graph 00031 class DSGraph; // A graph for a function 00032 class ReachabilityCloner; 00033 00034 namespace DS { // FIXME: After the paper, this should get cleaned up 00035 enum { PointerShift = 2, // 64bit ptrs = 3, 32 bit ptrs = 2 00036 PointerSize = 1 << PointerShift 00037 }; 00038 00039 /// isPointerType - Return true if this first class type is big enough to hold 00040 /// a pointer. 00041 /// 00042 bool isPointerType(const Type *Ty); 00043 } 00044 00045 //===----------------------------------------------------------------------===// 00046 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care 00047 /// of all of the add/un'refing of the node to prevent the backpointers in the 00048 /// graph from getting out of date. This class represents a "pointer" in the 00049 /// graph, whose destination is an indexed offset into a node. 00050 /// 00051 /// Note: some functions that are marked as inline in DSNodeHandle are actually 00052 /// defined in DSNode.h because they need knowledge of DSNode operation. Putting 00053 /// them in a CPP file wouldn't help making them inlined and keeping DSNode and 00054 /// DSNodeHandle (and friends) in one file complicates things. 00055 /// 00056 class DSNodeHandle { 00057 mutable DSNode *N; 00058 mutable unsigned Offset; 00059 void operator==(const DSNode *N); // DISALLOW, use to promote N to nodehandle 00060 public: 00061 // Allow construction, destruction, and assignment... 00062 DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(0) { 00063 setTo(n, offs); 00064 } 00065 DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) { 00066 DSNode *NN = H.getNode(); 00067 setTo(NN, H.Offset); // Must read offset AFTER the getNode() 00068 } 00069 ~DSNodeHandle() { setTo(0, 0); } 00070 DSNodeHandle &operator=(const DSNodeHandle &H) { 00071 if (&H == this) return *this; // Don't set offset to 0 if self assigning. 00072 DSNode *NN = H.getNode(); // Call getNode() before .Offset 00073 setTo(NN, H.Offset); 00074 return *this; 00075 } 00076 00077 bool operator<(const DSNodeHandle &H) const { // Allow sorting 00078 return getNode() < H.getNode() || (N == H.N && Offset < H.Offset); 00079 } 00080 bool operator>(const DSNodeHandle &H) const { return H < *this; } 00081 bool operator==(const DSNodeHandle &H) const { // Allow comparison 00082 // getNode can change the offset, so we must call getNode() first. 00083 return getNode() == H.getNode() && Offset == H.Offset; 00084 } 00085 bool operator!=(const DSNodeHandle &H) const { return !operator==(H); } 00086 00087 inline void swap(DSNodeHandle &NH) { 00088 std::swap(Offset, NH.Offset); 00089 std::swap(N, NH.N); 00090 } 00091 00092 /// isNull - Check to see if getNode() == 0, without going through the trouble 00093 /// of checking to see if we are forwarding... 00094 /// 00095 bool isNull() const { return N == 0; } 00096 00097 // Allow explicit conversion to DSNode... 00098 inline DSNode *getNode() const; // Defined inline in DSNode.h 00099 unsigned getOffset() const { 00100 assert(!isForwarding() && "This is a forwarding NH, call getNode() first!"); 00101 return Offset; 00102 } 00103 00104 void setOffset(unsigned O) { 00105 assert(!isForwarding() && "This is a forwarding NH, call getNode() first!"); 00106 //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || 00107 // !N->ForwardNH.isNull()) && "Node handle offset out of range!"); 00108 //assert((!N || O < N->Size || (N->Size == 0 && O == 0) || 00109 // !N->ForwardNH.isNull()) && "Node handle offset out of range!"); 00110 Offset = O; 00111 } 00112 00113 inline void setTo(DSNode *N, unsigned O) const; // Defined inline in DSNode.h 00114 00115 void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N); 00116 void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); } 00117 00118 /// mergeWith - Merge the logical node pointed to by 'this' with the node 00119 /// pointed to by 'N'. 00120 /// 00121 void mergeWith(const DSNodeHandle &N) const; 00122 00123 /// hasLink - Return true if there is a link at the specified offset... 00124 /// 00125 inline bool hasLink(unsigned Num) const; 00126 00127 /// getLink - Treat this current node pointer as a pointer to a structure of 00128 /// some sort. This method will return the pointer a mem[this+Num] 00129 /// 00130 inline const DSNodeHandle &getLink(unsigned Num) const; 00131 inline DSNodeHandle &getLink(unsigned Num); 00132 00133 inline void setLink(unsigned Num, const DSNodeHandle &NH); 00134 private: 00135 DSNode *HandleForwarding() const; 00136 00137 /// isForwarding - Return true if this NodeHandle is forwarding to another 00138 /// one. 00139 bool isForwarding() const; 00140 }; 00141 00142 } // End llvm namespace 00143 00144 namespace std { 00145 template<> 00146 inline void swap<llvm::DSNodeHandle>(llvm::DSNodeHandle &NH1, llvm::DSNodeHandle &NH2) { NH1.swap(NH2); } 00147 } 00148 00149 namespace HASH_NAMESPACE { 00150 // Provide a hash function for arbitrary pointers... 00151 template <> struct hash<llvm::DSNodeHandle> { 00152 inline size_t operator()(const llvm::DSNodeHandle &Val) const { 00153 return hash<void*>()(Val.getNode()) ^ Val.getOffset(); 00154 } 00155 }; 00156 } 00157 00158 namespace llvm { 00159 00160 //===----------------------------------------------------------------------===// 00161 /// DSCallSite - Representation of a call site via its call instruction, 00162 /// the DSNode handle for the callee function (or function pointer), and 00163 /// the DSNode handles for the function arguments. 00164 /// 00165 class DSCallSite { 00166 CallSite Site; // Actual call site 00167 Function *CalleeF; // The function called (direct call) 00168 DSNodeHandle CalleeN; // The function node called (indirect call) 00169 DSNodeHandle RetVal; // Returned value 00170 std::vector<DSNodeHandle> CallArgs;// The pointer arguments 00171 00172 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, 00173 const hash_map<const DSNode*, DSNode*> &NodeMap) { 00174 if (DSNode *N = Src.getNode()) { 00175 hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N); 00176 assert(I != NodeMap.end() && "Node not in mapping!"); 00177 NH.setTo(I->second, Src.getOffset()); 00178 } 00179 } 00180 00181 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, 00182 const hash_map<const DSNode*, DSNodeHandle> &NodeMap) { 00183 if (DSNode *N = Src.getNode()) { 00184 hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N); 00185 assert(I != NodeMap.end() && "Node not in mapping!"); 00186 00187 DSNode *NN = I->second.getNode(); // Call getNode before getOffset() 00188 NH.setTo(NN, Src.getOffset()+I->second.getOffset()); 00189 } 00190 } 00191 00192 static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, 00193 ReachabilityCloner &RC); 00194 00195 00196 DSCallSite(); // DO NOT IMPLEMENT 00197 public: 00198 /// Constructor. Note - This ctor destroys the argument vector passed in. On 00199 /// exit, the argument vector is empty. 00200 /// 00201 DSCallSite(CallSite CS, const DSNodeHandle &rv, DSNode *Callee, 00202 std::vector<DSNodeHandle> &Args) 00203 : Site(CS), CalleeF(0), CalleeN(Callee), RetVal(rv) { 00204 assert(Callee && "Null callee node specified for call site!"); 00205 Args.swap(CallArgs); 00206 } 00207 DSCallSite(CallSite CS, const DSNodeHandle &rv, Function *Callee, 00208 std::vector<DSNodeHandle> &Args) 00209 : Site(CS), CalleeF(Callee), RetVal(rv) { 00210 assert(Callee && "Null callee function specified for call site!"); 00211 Args.swap(CallArgs); 00212 } 00213 00214 DSCallSite(const DSCallSite &DSCS) // Simple copy ctor 00215 : Site(DSCS.Site), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN), 00216 RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {} 00217 00218 /// Mapping copy constructor - This constructor takes a preexisting call site 00219 /// to copy plus a map that specifies how the links should be transformed. 00220 /// This is useful when moving a call site from one graph to another. 00221 /// 00222 template<typename MapTy> 00223 DSCallSite(const DSCallSite &FromCall, MapTy &NodeMap) { 00224 Site = FromCall.Site; 00225 InitNH(RetVal, FromCall.RetVal, NodeMap); 00226 InitNH(CalleeN, FromCall.CalleeN, NodeMap); 00227 CalleeF = FromCall.CalleeF; 00228 00229 CallArgs.resize(FromCall.CallArgs.size()); 00230 for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i) 00231 InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap); 00232 } 00233 00234 const DSCallSite &operator=(const DSCallSite &RHS) { 00235 Site = RHS.Site; 00236 CalleeF = RHS.CalleeF; 00237 CalleeN = RHS.CalleeN; 00238 RetVal = RHS.RetVal; 00239 CallArgs = RHS.CallArgs; 00240 return *this; 00241 } 00242 00243 /// isDirectCall - Return true if this call site is a direct call of the 00244 /// function specified by getCalleeFunc. If not, it is an indirect call to 00245 /// the node specified by getCalleeNode. 00246 /// 00247 bool isDirectCall() const { return CalleeF != 0; } 00248 bool isIndirectCall() const { return !isDirectCall(); } 00249 00250 00251 // Accessor functions... 00252 Function &getCaller() const; 00253 CallSite getCallSite() const { return Site; } 00254 DSNodeHandle &getRetVal() { return RetVal; } 00255 const DSNodeHandle &getRetVal() const { return RetVal; } 00256 00257 DSNode *getCalleeNode() const { 00258 assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode(); 00259 } 00260 Function *getCalleeFunc() const { 00261 assert(!CalleeN.getNode() && CalleeF); return CalleeF; 00262 } 00263 00264 unsigned getNumPtrArgs() const { return CallArgs.size(); } 00265 00266 DSNodeHandle &getPtrArg(unsigned i) { 00267 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!"); 00268 return CallArgs[i]; 00269 } 00270 const DSNodeHandle &getPtrArg(unsigned i) const { 00271 assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!"); 00272 return CallArgs[i]; 00273 } 00274 00275 void addPtrArg(const DSNodeHandle &NH) { 00276 CallArgs.push_back(NH); 00277 } 00278 00279 void swap(DSCallSite &CS) { 00280 if (this != &CS) { 00281 std::swap(Site, CS.Site); 00282 std::swap(RetVal, CS.RetVal); 00283 std::swap(CalleeN, CS.CalleeN); 00284 std::swap(CalleeF, CS.CalleeF); 00285 std::swap(CallArgs, CS.CallArgs); 00286 } 00287 } 00288 00289 /// mergeWith - Merge the return value and parameters of the these two call 00290 /// sites. 00291 /// 00292 void mergeWith(DSCallSite &CS) { 00293 getRetVal().mergeWith(CS.getRetVal()); 00294 unsigned MinArgs = getNumPtrArgs(); 00295 if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs(); 00296 00297 for (unsigned a = 0; a != MinArgs; ++a) 00298 getPtrArg(a).mergeWith(CS.getPtrArg(a)); 00299 00300 for (unsigned a = MinArgs, e = CS.getNumPtrArgs(); a != e; ++a) 00301 CallArgs.push_back(CS.getPtrArg(a)); 00302 } 00303 00304 /// markReachableNodes - This method recursively traverses the specified 00305 /// DSNodes, marking any nodes which are reachable. All reachable nodes it 00306 /// adds to the set, which allows it to only traverse visited nodes once. 00307 /// 00308 void markReachableNodes(hash_set<const DSNode*> &Nodes) const; 00309 00310 bool operator<(const DSCallSite &CS) const { 00311 if (isDirectCall()) { // This must sort by callee first! 00312 if (CS.isIndirectCall()) return true; 00313 if (CalleeF < CS.CalleeF) return true; 00314 if (CalleeF > CS.CalleeF) return false; 00315 } else { 00316 if (CS.isDirectCall()) return false; 00317 if (CalleeN < CS.CalleeN) return true; 00318 if (CalleeN > CS.CalleeN) return false; 00319 } 00320 if (RetVal < CS.RetVal) return true; 00321 if (RetVal > CS.RetVal) return false; 00322 return CallArgs < CS.CallArgs; 00323 } 00324 00325 bool operator==(const DSCallSite &CS) const { 00326 return CalleeF == CS.CalleeF && CalleeN == CS.CalleeN && 00327 RetVal == CS.RetVal && CallArgs == CS.CallArgs; 00328 } 00329 }; 00330 00331 } // End llvm namespace 00332 00333 namespace std { 00334 template<> 00335 inline void swap<llvm::DSCallSite>(llvm::DSCallSite &CS1, 00336 llvm::DSCallSite &CS2) { CS1.swap(CS2); } 00337 } 00338 #endif