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