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