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