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