include/llvm/Analysis/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 <map>
  12 #include <set>
  13 #include <functional>
  14 #include <string>
  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   DSNode *N;
  49   unsigned Offset;
  50 public:
  51   // Allow construction, destruction, and assignment...
  52   DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
  53     setNode(n);
  54   }
  55   DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); }
  56   ~DSNodeHandle() { setNode((DSNode*)0); }
  57   DSNodeHandle &operator=(const DSNodeHandle &H) {
  58     setNode(H.N); Offset = H.Offset;
  59     return *this;
  60   }
  61
  62   bool operator<(const DSNodeHandle &H) const {  // Allow sorting
  63     return N < H.N || (N == H.N && Offset < H.Offset);
  64   }
  65   bool operator>(const DSNodeHandle &H) const { return H < *this; }
  66   bool operator==(const DSNodeHandle &H) const { // Allow comparison
  67     return N == H.N && Offset == H.Offset;
  68   }
  69   bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
  70
  71   inline void swap(DSNodeHandle &H);
  72
  73   // Allow explicit conversion to DSNode...
  74   DSNode *getNode() const { return N; }
  75   unsigned getOffset() const { return Offset; }
  76
  77   inline void setNode(DSNode *N);  // Defined inline later...
  78   void setOffset(unsigned O) { Offset = O; }
  79
  80   void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
  81   void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
  82
  83   /// mergeWith - Merge the logical node pointed to by 'this' with the node
  84   /// pointed to by 'N'.
  85   ///
  86   void mergeWith(const DSNodeHandle &N);
  87
  88   // hasLink - Return true if there is a link at the specified offset...
  89   inline bool hasLink(unsigned Num) const;
  90
  91   /// getLink - Treat this current node pointer as a pointer to a structure of
  92   /// some sort.  This method will return the pointer a mem[this+Num]
  93   ///
  94   inline const DSNodeHandle &getLink(unsigned Num) const;
  95   inline DSNodeHandle &getLink(unsigned Num);
  96
  97   inline void setLink(unsigned Num, const DSNodeHandle &NH);
  98 };
  99
 100 inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); }
 101
 102 //===----------------------------------------------------------------------===//
 103 /// DSCallSite - Representation of a call site via its call instruction,
 104 /// the DSNode handle for the callee function (or function pointer), and
 105 /// the DSNode handles for the function arguments.
 106 ///
 107 /// One unusual aspect of this callsite record is the ResolvingCaller member.
 108 /// If this is non-null, then it indicates the function that allowed a call-site
 109 /// to finally be resolved.  Because of indirect calls, this function may not
 110 /// actually be the function that contains the Call instruction itself.  This is
 111 /// used by the BU and TD passes to communicate.
 112 ///
 113 class DSCallSite {
 114   CallInst    *Inst;                    // Actual call site
 115   DSNodeHandle RetVal;                  // Returned value
 116   DSNodeHandle Callee;                  // The function node called
 117   std::vector<DSNodeHandle> CallArgs;   // The pointer arguments
 118   Function    *ResolvingCaller;         // See comments above
 119
 120   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
 121                      const std::map<const DSNode*, DSNode*> &NodeMap) {
 122     if (DSNode *N = Src.getNode()) {
 123       std::map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
 124       assert(I != NodeMap.end() && "Not not in mapping!");
 125
 126       NH.setOffset(Src.getOffset());
 127       NH.setNode(I->second);
 128     }
 129   }
 130
 131   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
 132                      const std::map<const DSNode*, DSNodeHandle> &NodeMap) {
 133     if (DSNode *N = Src.getNode()) {
 134       std::map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
 135       assert(I != NodeMap.end() && "Not not in mapping!");
 136
 137       NH.setOffset(Src.getOffset()+I->second.getOffset());
 138       NH.setNode(I->second.getNode());
 139     }
 140   }
 141
 142   DSCallSite();                         // DO NOT IMPLEMENT
 143 public:
 144   /// Constructor.  Note - This ctor destroys the argument vector passed in.  On
 145   /// exit, the argument vector is empty.
 146   ///
 147   DSCallSite(CallInst &inst, const DSNodeHandle &rv, const DSNodeHandle &callee,
 148              std::vector<DSNodeHandle> &Args)
 149     : Inst(&inst), RetVal(rv), Callee(callee), ResolvingCaller(0) {
 150     Args.swap(CallArgs);
 151   }
 152
 153   DSCallSite(const DSCallSite &DSCS)   // Simple copy ctor
 154     : Inst(DSCS.Inst), RetVal(DSCS.RetVal),
 155       Callee(DSCS.Callee), CallArgs(DSCS.CallArgs),
 156       ResolvingCaller(DSCS.ResolvingCaller) {}
 157
 158   /// Mapping copy constructor - This constructor takes a preexisting call site
 159   /// to copy plus a map that specifies how the links should be transformed.
 160   /// This is useful when moving a call site from one graph to another.
 161   ///
 162   template<typename MapTy>
 163   DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) {
 164     Inst = FromCall.Inst;
 165     InitNH(RetVal, FromCall.RetVal, NodeMap);
 166     InitNH(Callee, FromCall.Callee, NodeMap);
 167
 168     CallArgs.resize(FromCall.CallArgs.size());
 169     for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
 170       InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
 171     ResolvingCaller = FromCall.ResolvingCaller;
 172   }
 173
 174   // Accessor functions...
 175   Function           &getCaller()     const;
 176   CallInst           &getCallInst()   const { return *Inst; }
 177         DSNodeHandle &getRetVal()           { return RetVal; }
 178         DSNodeHandle &getCallee()           { return Callee; }
 179   const DSNodeHandle &getRetVal()     const { return RetVal; }
 180   const DSNodeHandle &getCallee()     const { return Callee; }
 181   void setCallee(const DSNodeHandle &H) { Callee = H; }
 182
 183   unsigned            getNumPtrArgs() const { return CallArgs.size(); }
 184
 185   Function           *getResolvingCaller() const { return ResolvingCaller; }
 186   void setResolvingCaller(Function *F) { ResolvingCaller = F; }
 187
 188   DSNodeHandle &getPtrArg(unsigned i) {
 189     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 190     return CallArgs[i];
 191   }
 192   const DSNodeHandle &getPtrArg(unsigned i) const {
 193     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 194     return CallArgs[i];
 195   }
 196
 197   void swap(DSCallSite &CS) {
 198     if (this != &CS) {
 199       std::swap(Inst, CS.Inst);
 200       std::swap(RetVal, CS.RetVal);
 201       std::swap(Callee, CS.Callee);
 202       std::swap(CallArgs, CS.CallArgs);
 203       std::swap(ResolvingCaller, CS.ResolvingCaller);
 204     }
 205   }
 206
 207   // MergeWith - Merge the return value and parameters of the these two call
 208   // sites.
 209   void mergeWith(DSCallSite &CS) {
 210     getRetVal().mergeWith(CS.getRetVal());
 211     unsigned MinArgs = getNumPtrArgs();
 212     if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
 213
 214     for (unsigned a = 0; a != MinArgs; ++a)
 215       getPtrArg(a).mergeWith(CS.getPtrArg(a));
 216   }
 217
 218   /// markReachableNodes - This method recursively traverses the specified
 219   /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
 220   /// adds to the set, which allows it to only traverse visited nodes once.
 221   ///
 222   void markReachableNodes(std::set<DSNode*> &Nodes);
 223
 224   bool operator<(const DSCallSite &CS) const {
 225     if (Callee < CS.Callee) return true;   // This must sort by callee first!
 226     if (Callee > CS.Callee) return false;
 227     if (RetVal < CS.RetVal) return true;
 228     if (RetVal > CS.RetVal) return false;
 229     return CallArgs < CS.CallArgs;
 230   }
 231
 232   bool operator==(const DSCallSite &CS) const {
 233     return RetVal == CS.RetVal && Callee == CS.Callee &&
 234            CallArgs == CS.CallArgs;
 235   }
 236 };
 237
 238 inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); }
 239
 240 #endif