include/llvm/Analysis/PtrUseVisitor.h

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