include/llvm/Analysis/PtrUseVisitor.h

   1 //===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 /// This file provides a collection of visitors which walk the (instruction)
  11 /// uses of a pointer. These visitors all provide the same essential behavior
  12 /// as an InstVisitor with similar template-based flexibility and
  13 /// implementation strategies.
  14 ///
  15 /// These can be used, for example, to quickly analyze the uses of an alloca,
  16 /// global variable, or function argument.
  17 ///
  18 /// FIXME: Provide a variant which doesn't track offsets and is cheaper.
  19 ///
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H
  23 #define LLVM_ANALYSIS_PTRUSEVISITOR_H
  24
  25 #include "llvm/ADT/APInt.h"
  26 #include "llvm/ADT/SmallPtrSet.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include "llvm/DataLayout.h"
  29 #include "llvm/InstVisitor.h"
  30 #include "llvm/IntrinsicInst.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/Support/GetElementPtrTypeIterator.h"
  33
  34 namespace llvm {
  35
  36 namespace detail {
  37 /// \brief Implementation of non-dependent functionality for \c PtrUseVisitor.
  38 ///
  39 /// See \c PtrUseVisitor for the public interface and detailed comments about
  40 /// usage. This class is just a helper base class which is not templated and
  41 /// contains all common code to be shared between different instantiations of
  42 /// PtrUseVisitor.
  43 class PtrUseVisitorBase {
  44 public:
  45   /// \brief This class provides information about the result of a visit.
  46   ///
  47   /// After walking all the users (recursively) of a pointer, the basic
  48   /// infrastructure records some commonly useful information such as escape
  49   /// analysis and whether the visit completed or aborted early.
  50   class PtrInfo {
  51   public:
  52     PtrInfo() : AbortedInfo(0, false), EscapedInfo(0, false) {}
  53
  54     /// \brief Reset the pointer info, clearing all state.
  55     void reset() {
  56       AbortedInfo.setPointer(0);
  57       AbortedInfo.setInt(false);
  58       EscapedInfo.setPointer(0);
  59       EscapedInfo.setInt(false);
  60     }
  61
  62     /// \brief Did we abort the visit early?
  63     bool isAborted() const { return AbortedInfo.getInt(); }
  64
  65     /// \brief Is the pointer escaped at some point?
  66     bool isEscaped() const { return EscapedInfo.getInt(); }
  67
  68     /// \brief Get the instruction causing the visit to abort.
  69     /// \returns a pointer to the instruction causing the abort if one is
  70     /// available; otherwise returns null.
  71     Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); }
  72
  73     /// \brief Get the instruction causing the pointer to escape.
  74     /// \returns a pointer to the instruction which escapes the pointer if one
  75     /// is available; otherwise returns null.
  76     Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); }
  77
  78     /// \brief Mark the visit as aborted. Intended for use in a void return.
  79     /// \param I The instruction which caused the visit to abort, if available.
  80     void setAborted(Instruction *I = 0) {
  81       AbortedInfo.setInt(true);
  82       AbortedInfo.setPointer(I);
  83     }
  84
  85     /// \brief Mark the pointer as escaped. Intended for use in a void return.
  86     /// \param I The instruction which escapes the pointer, if available.
  87     void setEscaped(Instruction *I = 0) {
  88       EscapedInfo.setInt(true);
  89       EscapedInfo.setPointer(I);
  90     }
  91
  92     /// \brief Mark the pointer as escaped, and the visit as aborted. Intended
  93     /// for use in a void return.
  94     /// \param I The instruction which both escapes the pointer and aborts the
  95     /// visit, if available.
  96     void setEscapedAndAborted(Instruction *I = 0) {
  97       setEscaped(I);
  98       setAborted(I);
  99     }
 100
 101   private:
 102     PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
 103   };
 104
 105 protected:
 106   const DataLayout &DL;
 107
 108   /// \name Visitation infrastructure
 109   /// @{
 110
 111   /// \brief The info collected about the pointer being visited thus far.
 112   PtrInfo PI;
 113
 114   /// \brief A struct of the data needed to visit a particular use.
 115   ///
 116   /// This is used to maintain a worklist fo to-visit uses. This is used to
 117   /// make the visit be iterative rather than recursive.
 118   struct UseToVisit {
 119     typedef PointerIntPair<Use *, 1, bool> UseAndIsOffsetKnownPair;
 120     UseAndIsOffsetKnownPair UseAndIsOffsetKnown;
 121     APInt Offset;
 122   };
 123
 124   /// \brief The worklist of to-visit uses.
 125   SmallVector<UseToVisit, 8> Worklist;
 126
 127   /// \brief A set of visited uses to break cycles in unreachable code.
 128   SmallPtrSet<Use *, 8> VisitedUses;
 129
 130   /// @}
 131
 132
 133   /// \name Per-visit state
 134   /// This state is reset for each instruction visited.
 135   /// @{
 136
 137   /// \brief The use currently being visited.
 138   Use *U;
 139
 140   /// \brief True if we have a known constant offset for the use currently
 141   /// being visited.
 142   bool IsOffsetKnown;
 143
 144   /// \brief The constant offset of the use if that is known.
 145   APInt Offset;
 146
 147   /// @}
 148
 149
 150   /// Note that the constructor is protected because this class must be a base
 151   /// class, we can't create instances directly of this class.
 152   PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
 153
 154   /// \brief Enqueue the users of this instruction in the visit worklist.
 155   ///
 156   /// This will visit the users with the same offset of the current visit
 157   /// (including an unknown offset if that is the current state).
 158   void enqueueUsers(Instruction &I);
 159
 160   /// \brief Walk the operands of a GEP and adjust the offset as appropriate.
 161   ///
 162   /// This routine does the heavy lifting of the pointer walk by computing
 163   /// offsets and looking through GEPs.
 164   bool adjustOffsetForGEP(GetElementPtrInst &GEPI);
 165 };
 166 } // end namespace detail
 167
 168 /// \brief A base class for visitors over the uses of a pointer value.
 169 ///
 170 /// Once constructed, a user can call \c visit on a pointer value, and this
 171 /// will walk its uses and visit each instruction using an InstVisitor. It also
 172 /// provides visit methods which will recurse through any pointer-to-pointer
 173 /// transformations such as GEPs and bitcasts.
 174 ///
 175 /// During the visit, the current Use* being visited is available to the
 176 /// subclass, as well as the current offset from the original base pointer if
 177 /// known.
 178 ///
 179 /// The recursive visit of uses is accomplished with a worklist, so the only
 180 /// ordering guarantee is that an instruction is visited before any uses of it
 181 /// are visited. Note that this does *not* mean before any of its users are
 182 /// visited! This is because users can be visited multiple times due to
 183 /// multiple, different uses of pointers derived from the same base.
 184 ///
 185 /// A particular Use will only be visited once, but a User may be visited
 186 /// multiple times, once per Use. This visits may notably have different
 187 /// offsets.
 188 ///
 189 /// All visit methods on the underlying InstVisitor return a boolean. This
 190 /// return short-circuits the visit, stopping it immediately.
 191 ///
 192 /// FIXME: Generalize this for all values rather than just instructions.
 193 template <typename DerivedT>
 194 class PtrUseVisitor : protected InstVisitor<DerivedT>,
 195                       public detail::PtrUseVisitorBase {
 196   friend class InstVisitor<DerivedT>;
 197   typedef InstVisitor<DerivedT> Base;
 198
 199 public:
 200   PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {}
 201
 202   /// \brief Recursively visit the uses of the given pointer.
 203   /// \returns An info struct about the pointer. See \c PtrInfo for details.
 204   PtrInfo visitPtr(Instruction &I) {
 205     // This must be a pointer type. Get an integer type suitable to hold
 206     // offsets on this pointer.
 207     // FIXME: Support a vector of pointers.
 208     assert(I.getType()->isPointerTy());
 209     IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
 210     IsOffsetKnown = true;
 211     Offset = APInt(IntPtrTy->getBitWidth(), 0);
 212     PI.reset();
 213
 214     // Enqueue the uses of this pointer.
 215     enqueueUsers(I);
 216
 217     // Visit all the uses off the worklist until it is empty.
 218     while (!Worklist.empty()) {
 219       UseToVisit ToVisit = Worklist.pop_back_val();
 220       U = ToVisit.UseAndIsOffsetKnown.getPointer();
 221       IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
 222       if (IsOffsetKnown)
 223         Offset = llvm_move(ToVisit.Offset);
 224
 225       Instruction *I = cast<Instruction>(U->getUser());
 226       static_cast<DerivedT*>(this)->visit(I);
 227       if (PI.isAborted())
 228         break;
 229     }
 230     return PI;
 231   }
 232
 233 protected:
 234   void visitStoreInst(StoreInst &SI) {
 235     if (SI.getValueOperand() == U->get())
 236       PI.setEscaped(&SI);
 237   }
 238
 239   void visitBitCastInst(BitCastInst &BC) {
 240     enqueueUsers(BC);
 241   }
 242
 243   void visitPtrToIntInst(PtrToIntInst &I) {
 244     PI.setEscaped(&I);
 245   }
 246
 247   void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
 248     if (GEPI.use_empty())
 249       return;
 250
 251     // If we can't walk the GEP, clear the offset.
 252     if (!adjustOffsetForGEP(GEPI)) {
 253       IsOffsetKnown = false;
 254       Offset = APInt();
 255     }
 256
 257     // Enqueue the users now that the offset has been adjusted.
 258     enqueueUsers(GEPI);
 259   }
 260
 261   // No-op intrinsics which we know don't escape the pointer to to logic in
 262   // some other function.
 263   void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {}
 264   void visitMemIntrinsic(MemIntrinsic &I) {}
 265   void visitIntrinsicInst(IntrinsicInst &II) {
 266     switch (II.getIntrinsicID()) {
 267     default:
 268       return Base::visitIntrinsicInst(II);
 269
 270     case Intrinsic::lifetime_start:
 271     case Intrinsic::lifetime_end:
 272       return; // No-op intrinsics.
 273     }
 274   }
 275
 276   // Generically, arguments to calls and invokes escape the pointer to some
 277   // other function. Mark that.
 278   void visitCallSite(CallSite CS) {
 279     PI.setEscaped(CS.getInstruction());
 280     Base::visitCallSite(CS);
 281   }
 282 };
 283
 284 }
 285
 286 #endif