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 <functional>
  12 #include <string>
  13 #include <assert.h>
  14 #include "Support/HashExtras.h"
  15 #include "Support/hash_set"
  16
  17 class Function;
  18 class CallInst;
  19 class Value;
  20 class GlobalValue;
  21 class Type;
  22
  23 class DSNode;                  // Each node in the graph
  24 class DSGraph;                 // A graph for a function
  25
  26 namespace DS { // FIXME: After the paper, this should get cleaned up
  27   enum { PointerShift = 3,     // 64bit ptrs = 3, 32 bit ptrs = 2
  28          PointerSize = 1 << PointerShift
  29   };
  30
  31   // isPointerType - Return true if this first class type is big enough to hold
  32   // a pointer.
  33   //
  34   bool isPointerType(const Type *Ty);
  35 };
  36
  37 //===----------------------------------------------------------------------===//
  38 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care
  39 /// of all of the add/un'refing of the node to prevent the backpointers in the
  40 /// graph from getting out of date.  This class represents a "pointer" in the
  41 /// graph, whose destination is an indexed offset into a node.
  42 ///
  43 /// Note: some functions that are marked as inline in DSNodeHandle are actually
  44 /// defined in DSNode.h because they need knowledge of DSNode operation. Putting
  45 /// them in a CPP file wouldn't help making them inlined and keeping DSNode and
  46 /// DSNodeHandle (and friends) in one file complicates things.
  47 ///
  48 class DSNodeHandle {
  49   mutable DSNode *N;
  50   mutable unsigned Offset;
  51   void operator==(const DSNode *N);  // DISALLOW, use to promote N to nodehandle
  52 public:
  53   // Allow construction, destruction, and assignment...
  54   DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
  55     setNode(n);
  56   }
  57   DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) {
  58     setNode(H.getNode());
  59     Offset = H.Offset;      // Must read offset AFTER the getNode()
  60   }
  61   ~DSNodeHandle() { setNode((DSNode*)0); }
  62   DSNodeHandle &operator=(const DSNodeHandle &H) {
  63     if (&H == this) return *this;  // Don't set offset to 0 if self assigning.
  64     Offset = 0; setNode(H.getNode()); Offset = H.Offset;
  65     return *this;
  66   }
  67
  68   bool operator<(const DSNodeHandle &H) const {  // Allow sorting
  69     return getNode() < H.getNode() || (N == H.N && Offset < H.Offset);
  70   }
  71   bool operator>(const DSNodeHandle &H) const { return H < *this; }
  72   bool operator==(const DSNodeHandle &H) const { // Allow comparison
  73     return getNode() == H.getNode() && Offset == H.Offset;
  74   }
  75   bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
  76
  77   inline void swap(DSNodeHandle &NH) {
  78     std::swap(Offset, NH.Offset);
  79     std::swap(N, NH.N);
  80   }
  81
  82   /// isNull - Check to see if getNode() == 0, without going through the trouble
  83   /// of checking to see if we are forwarding...
  84   bool isNull() const { return N == 0; }
  85
  86   // Allow explicit conversion to DSNode...
  87   inline DSNode *getNode() const;  // Defined inline in DSNode.h
  88   unsigned getOffset() const { return Offset; }
  89
  90   inline void setNode(DSNode *N);  // Defined inline in DSNode.h
  91   void setOffset(unsigned O) {
  92     //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
  93     //       !N->ForwardNH.isNull()) && "Node handle offset out of range!");
  94     //assert((!N || O < N->Size || (N->Size == 0 && O == 0) ||
  95     //       !N->ForwardNH.isNull()) && "Node handle offset out of range!");
  96     Offset = O;
  97   }
  98
  99   void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
 100   void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
 101
 102   /// mergeWith - Merge the logical node pointed to by 'this' with the node
 103   /// pointed to by 'N'.
 104   ///
 105   void mergeWith(const DSNodeHandle &N);
 106
 107   // hasLink - Return true if there is a link at the specified offset...
 108   inline bool hasLink(unsigned Num) const;
 109
 110   /// getLink - Treat this current node pointer as a pointer to a structure of
 111   /// some sort.  This method will return the pointer a mem[this+Num]
 112   ///
 113   inline const DSNodeHandle &getLink(unsigned Num) const;
 114   inline DSNodeHandle &getLink(unsigned Num);
 115
 116   inline void setLink(unsigned Num, const DSNodeHandle &NH);
 117 private:
 118   DSNode *HandleForwarding() const;
 119 };
 120
 121 namespace std {
 122   inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); }
 123 }
 124
 125 //===----------------------------------------------------------------------===//
 126 /// DSCallSite - Representation of a call site via its call instruction,
 127 /// the DSNode handle for the callee function (or function pointer), and
 128 /// the DSNode handles for the function arguments.
 129 ///
 130 class DSCallSite {
 131   CallInst    *Inst;                 // Actual call site
 132   Function    *CalleeF;              // The function called (direct call)
 133   DSNodeHandle CalleeN;              // The function node called (indirect call)
 134   DSNodeHandle RetVal;               // Returned value
 135   std::vector<DSNodeHandle> CallArgs;// The pointer arguments
 136
 137   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
 138                      const hash_map<const DSNode*, DSNode*> &NodeMap) {
 139     if (DSNode *N = Src.getNode()) {
 140       hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
 141       assert(I != NodeMap.end() && "Not not in mapping!");
 142
 143       NH.setOffset(Src.getOffset());
 144       NH.setNode(I->second);
 145     }
 146   }
 147
 148   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
 149                      const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
 150     if (DSNode *N = Src.getNode()) {
 151       hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
 152       assert(I != NodeMap.end() && "Not not in mapping!");
 153
 154       NH.setOffset(Src.getOffset()+I->second.getOffset());
 155       NH.setNode(I->second.getNode());
 156     }
 157   }
 158
 159   DSCallSite();                         // DO NOT IMPLEMENT
 160 public:
 161   /// Constructor.  Note - This ctor destroys the argument vector passed in.  On
 162   /// exit, the argument vector is empty.
 163   ///
 164   DSCallSite(CallInst &inst, const DSNodeHandle &rv, DSNode *Callee,
 165              std::vector<DSNodeHandle> &Args)
 166     : Inst(&inst), CalleeF(0), CalleeN(Callee), RetVal(rv) {
 167     assert(Callee && "Null callee node specified for call site!");
 168     Args.swap(CallArgs);
 169   }
 170   DSCallSite(CallInst &inst, const DSNodeHandle &rv, Function *Callee,
 171              std::vector<DSNodeHandle> &Args)
 172     : Inst(&inst), CalleeF(Callee), RetVal(rv) {
 173     assert(Callee && "Null callee function specified for call site!");
 174     Args.swap(CallArgs);
 175   }
 176
 177   DSCallSite(const DSCallSite &DSCS)   // Simple copy ctor
 178     : Inst(DSCS.Inst), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN),
 179       RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {}
 180
 181   /// Mapping copy constructor - This constructor takes a preexisting call site
 182   /// to copy plus a map that specifies how the links should be transformed.
 183   /// This is useful when moving a call site from one graph to another.
 184   ///
 185   template<typename MapTy>
 186   DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) {
 187     Inst = FromCall.Inst;
 188     InitNH(RetVal, FromCall.RetVal, NodeMap);
 189     InitNH(CalleeN, FromCall.CalleeN, NodeMap);
 190     CalleeF = FromCall.CalleeF;
 191
 192     CallArgs.resize(FromCall.CallArgs.size());
 193     for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
 194       InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
 195   }
 196
 197   const DSCallSite &operator=(const DSCallSite &RHS) {
 198     Inst     = RHS.Inst;
 199     CalleeF  = RHS.CalleeF;
 200     CalleeN  = RHS.CalleeN;
 201     RetVal   = RHS.RetVal;
 202     CallArgs = RHS.CallArgs;
 203     return *this;
 204   }
 205
 206   /// isDirectCall - Return true if this call site is a direct call of the
 207   /// function specified by getCalleeFunc.  If not, it is an indirect call to
 208   /// the node specified by getCalleeNode.
 209   ///
 210   bool isDirectCall() const { return CalleeF != 0; }
 211   bool isIndirectCall() const { return !isDirectCall(); }
 212
 213
 214   // Accessor functions...
 215   Function           &getCaller()     const;
 216   CallInst           &getCallInst()   const { return *Inst; }
 217         DSNodeHandle &getRetVal()           { return RetVal; }
 218   const DSNodeHandle &getRetVal()     const { return RetVal; }
 219
 220   DSNode *getCalleeNode() const {
 221     assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode();
 222   }
 223   Function *getCalleeFunc() const {
 224     assert(!CalleeN.getNode() && CalleeF); return CalleeF;
 225   }
 226
 227   unsigned            getNumPtrArgs() const { return CallArgs.size(); }
 228
 229   DSNodeHandle &getPtrArg(unsigned i) {
 230     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 231     return CallArgs[i];
 232   }
 233   const DSNodeHandle &getPtrArg(unsigned i) const {
 234     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 235     return CallArgs[i];
 236   }
 237
 238   void swap(DSCallSite &CS) {
 239     if (this != &CS) {
 240       std::swap(Inst, CS.Inst);
 241       std::swap(RetVal, CS.RetVal);
 242       std::swap(CalleeN, CS.CalleeN);
 243       std::swap(CalleeF, CS.CalleeF);
 244       std::swap(CallArgs, CS.CallArgs);
 245     }
 246   }
 247
 248   // MergeWith - Merge the return value and parameters of the these two call
 249   // sites.
 250   void mergeWith(DSCallSite &CS) {
 251     getRetVal().mergeWith(CS.getRetVal());
 252     unsigned MinArgs = getNumPtrArgs();
 253     if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
 254
 255     for (unsigned a = 0; a != MinArgs; ++a)
 256       getPtrArg(a).mergeWith(CS.getPtrArg(a));
 257   }
 258
 259   /// markReachableNodes - This method recursively traverses the specified
 260   /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
 261   /// adds to the set, which allows it to only traverse visited nodes once.
 262   ///
 263   void markReachableNodes(hash_set<DSNode*> &Nodes);
 264
 265   bool operator<(const DSCallSite &CS) const {
 266     if (isDirectCall()) {      // This must sort by callee first!
 267       if (CS.isIndirectCall()) return true;
 268       if (CalleeF < CS.CalleeF) return true;
 269       if (CalleeF > CS.CalleeF) return false;
 270     } else {
 271       if (CS.isDirectCall()) return false;
 272       if (CalleeN < CS.CalleeN) return true;
 273       if (CalleeN > CS.CalleeN) return false;
 274     }
 275     if (RetVal < CS.RetVal) return true;
 276     if (RetVal > CS.RetVal) return false;
 277     return CallArgs < CS.CallArgs;
 278   }
 279
 280   bool operator==(const DSCallSite &CS) const {
 281     return RetVal == CS.RetVal && CalleeN == CS.CalleeN &&
 282            CalleeF == CS.CalleeF && CallArgs == CS.CallArgs;
 283   }
 284 };
 285
 286 namespace std {
 287   inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); }
 288 }
 289 #endif