include/llvm/Analysis/DSSupport.h

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