LLVM API Documentation

DSSupport.h

Go to the documentation of this file.
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