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 <functional>
  13 #include <string>
  14
  15 class Function;
  16 class CallInst;
  17 class Value;
  18 class GlobalValue;
  19 class Type;
  20
  21 class DSNode;                  // Each node in the graph
  22 class DSGraph;                 // A graph for a function
  23 class DSNodeIterator;          // Data structure graph traversal iterator
  24
  25 namespace DS {
  26   extern const unsigned PointerShift;  // 64bit ptrs = 3, 32 bit ptrs = 2
  27 };
  28
  29 //===----------------------------------------------------------------------===//
  30 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care
  31 /// of all of the add/un'refing of the node to prevent the backpointers in the
  32 /// graph from getting out of date.  This class represents a "pointer" in the
  33 /// graph, whose destination is an indexed offset into a node.
  34 ///
  35 /// Note: some functions that are marked as inline in DSNodeHandle are actually
  36 /// defined in DSNode.h because they need knowledge of DSNode operation. Putting
  37 /// them in a CPP file wouldn't help making them inlined and keeping DSNode and
  38 /// DSNodeHandle (and friends) in one file complicates things.
  39 ///
  40 class DSNodeHandle {
  41   DSNode *N;
  42   unsigned Offset;
  43 public:
  44   // Allow construction, destruction, and assignment...
  45   DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
  46     setNode(n);
  47   }
  48   DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); }
  49   ~DSNodeHandle() { setNode((DSNode*)0); }
  50   DSNodeHandle &operator=(const DSNodeHandle &H) {
  51     setNode(H.N); Offset = H.Offset;
  52     return *this;
  53   }
  54
  55   bool operator<(const DSNodeHandle &H) const {  // Allow sorting
  56     return N < H.N || (N == H.N && Offset < H.Offset);
  57   }
  58   bool operator>(const DSNodeHandle &H) const { return H < *this; }
  59   bool operator==(const DSNodeHandle &H) const { // Allow comparison
  60     return N == H.N && Offset == H.Offset;
  61   }
  62   bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
  63
  64   // Allow explicit conversion to DSNode...
  65   DSNode *getNode() const { return N; }
  66   unsigned getOffset() const { return Offset; }
  67
  68   inline void setNode(DSNode *N);  // Defined inline later...
  69   void setOffset(unsigned O) { Offset = O; }
  70
  71   void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
  72   void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
  73
  74   /// mergeWith - Merge the logical node pointed to by 'this' with the node
  75   /// pointed to by 'N'.
  76   ///
  77   void mergeWith(const DSNodeHandle &N);
  78
  79   // hasLink - Return true if there is a link at the specified offset...
  80   inline bool hasLink(unsigned Num) const;
  81
  82   /// getLink - Treat this current node pointer as a pointer to a structure of
  83   /// some sort.  This method will return the pointer a mem[this+Num]
  84   ///
  85   inline const DSNodeHandle &getLink(unsigned Num) const;
  86   inline DSNodeHandle &getLink(unsigned Num);
  87
  88   inline void setLink(unsigned Num, const DSNodeHandle &NH);
  89 };
  90
  91
  92 //===----------------------------------------------------------------------===//
  93 /// DSTypeRec - This structure is used to represent a single type that is held
  94 /// in a DSNode.
  95 ///
  96 struct DSTypeRec {
  97   const Type *Ty;                 // The type itself...
  98   bool isArray;                   // Have we accessed an array of elements?
  99
 100   DSTypeRec(const Type *T = 0, bool A = false)
 101     : Ty(T), isArray(A) {}
 102 };
 103
 104
 105
 106 //===----------------------------------------------------------------------===//
 107 /// DSCallSite - Representation of a call site via its call instruction,
 108 /// the DSNode handle for the callee function (or function pointer), and
 109 /// the DSNode handles for the function arguments.
 110 ///
 111 /// One unusual aspect of this callsite record is the ResolvingCaller member.
 112 /// If this is non-null, then it indicates the function that allowed a call-site
 113 /// to finally be resolved.  Because of indirect calls, this function may not
 114 /// actually be the function that contains the Call instruction itself.  This is
 115 /// used by the BU and TD passes to communicate.
 116 ///
 117 class DSCallSite {
 118   CallInst    *Inst;                    // Actual call site
 119   DSNodeHandle RetVal;                  // Returned value
 120   DSNodeHandle Callee;                  // The function node called
 121   std::vector<DSNodeHandle> CallArgs;   // The pointer arguments
 122   Function    *ResolvingCaller;         // See comments above
 123
 124   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
 125                      const std::map<const DSNode*, DSNode*> &NodeMap) {
 126     if (DSNode *N = Src.getNode()) {
 127       std::map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
 128       assert(I != NodeMap.end() && "Not not in mapping!");
 129
 130       NH.setOffset(Src.getOffset());
 131       NH.setNode(I->second);
 132     }
 133   }
 134
 135   static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
 136                      const std::map<const DSNode*, DSNodeHandle> &NodeMap) {
 137     if (DSNode *N = Src.getNode()) {
 138       std::map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
 139       assert(I != NodeMap.end() && "Not not in mapping!");
 140
 141       NH.setOffset(Src.getOffset()+I->second.getOffset());
 142       NH.setNode(I->second.getNode());
 143     }
 144   }
 145
 146   DSCallSite();                         // DO NOT IMPLEMENT
 147 public:
 148   /// Constructor.  Note - This ctor destroys the argument vector passed in.  On
 149   /// exit, the argument vector is empty.
 150   ///
 151   DSCallSite(CallInst &inst, const DSNodeHandle &rv, const DSNodeHandle &callee,
 152              std::vector<DSNodeHandle> &Args)
 153     : Inst(&inst), RetVal(rv), Callee(callee), ResolvingCaller(0) {
 154     Args.swap(CallArgs);
 155   }
 156
 157   DSCallSite(const DSCallSite &DSCS)   // Simple copy ctor
 158     : Inst(DSCS.Inst), RetVal(DSCS.RetVal),
 159       Callee(DSCS.Callee), CallArgs(DSCS.CallArgs),
 160       ResolvingCaller(DSCS.ResolvingCaller) {}
 161
 162   /// Mapping copy constructor - This constructor takes a preexisting call site
 163   /// to copy plus a map that specifies how the links should be transformed.
 164   /// This is useful when moving a call site from one graph to another.
 165   ///
 166   template<typename MapTy>
 167   DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) {
 168     Inst = FromCall.Inst;
 169     InitNH(RetVal, FromCall.RetVal, NodeMap);
 170     InitNH(Callee, FromCall.Callee, NodeMap);
 171
 172     CallArgs.resize(FromCall.CallArgs.size());
 173     for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
 174       InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
 175     ResolvingCaller = FromCall.ResolvingCaller;
 176   }
 177
 178   // Accessor functions...
 179   Function           &getCaller()     const;
 180   CallInst           &getCallInst()   const { return *Inst; }
 181         DSNodeHandle &getRetVal()           { return RetVal; }
 182         DSNodeHandle &getCallee()           { return Callee; }
 183   const DSNodeHandle &getRetVal()     const { return RetVal; }
 184   const DSNodeHandle &getCallee()     const { return Callee; }
 185   void setCallee(const DSNodeHandle &H) { Callee = H; }
 186
 187   unsigned            getNumPtrArgs() const { return CallArgs.size(); }
 188
 189   Function           *getResolvingCaller() const { return ResolvingCaller; }
 190   void setResolvingCaller(Function *F) { ResolvingCaller = F; }
 191
 192   DSNodeHandle &getPtrArg(unsigned i) {
 193     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 194     return CallArgs[i];
 195   }
 196   const DSNodeHandle &getPtrArg(unsigned i) const {
 197     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 198     return CallArgs[i];
 199   }
 200
 201   bool operator<(const DSCallSite &CS) const {
 202     if (RetVal < CS.RetVal) return true;
 203     if (RetVal > CS.RetVal) return false;
 204     if (Callee < CS.Callee) return true;
 205     if (Callee > CS.Callee) return false;
 206     return CallArgs < CS.CallArgs;
 207   }
 208
 209   bool operator==(const DSCallSite &CS) const {
 210     return RetVal == CS.RetVal && Callee == CS.Callee &&
 211            CallArgs == CS.CallArgs;
 212   }
 213 };
 214
 215
 216 #endif