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