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