LLVM  mainline
PtrUseVisitor.h
Go to the documentation of this file.
00001 //===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 /// \file
00010 /// This file provides a collection of visitors which walk the (instruction)
00011 /// uses of a pointer. These visitors all provide the same essential behavior
00012 /// as an InstVisitor with similar template-based flexibility and
00013 /// implementation strategies.
00014 ///
00015 /// These can be used, for example, to quickly analyze the uses of an alloca,
00016 /// global variable, or function argument.
00017 ///
00018 /// FIXME: Provide a variant which doesn't track offsets and is cheaper.
00019 ///
00020 //===----------------------------------------------------------------------===//
00021 
00022 #ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H
00023 #define LLVM_ANALYSIS_PTRUSEVISITOR_H
00024 
00025 #include "llvm/ADT/APInt.h"
00026 #include "llvm/ADT/SmallPtrSet.h"
00027 #include "llvm/ADT/SmallVector.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/InstVisitor.h"
00030 #include "llvm/IR/IntrinsicInst.h"
00031 #include "llvm/Support/Compiler.h"
00032 
00033 namespace llvm {
00034 
00035 namespace detail {
00036 /// \brief Implementation of non-dependent functionality for \c PtrUseVisitor.
00037 ///
00038 /// See \c PtrUseVisitor for the public interface and detailed comments about
00039 /// usage. This class is just a helper base class which is not templated and
00040 /// contains all common code to be shared between different instantiations of
00041 /// PtrUseVisitor.
00042 class PtrUseVisitorBase {
00043 public:
00044   /// \brief This class provides information about the result of a visit.
00045   ///
00046   /// After walking all the users (recursively) of a pointer, the basic
00047   /// infrastructure records some commonly useful information such as escape
00048   /// analysis and whether the visit completed or aborted early.
00049   class PtrInfo {
00050   public:
00051     PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {}
00052 
00053     /// \brief Reset the pointer info, clearing all state.
00054     void reset() {
00055       AbortedInfo.setPointer(nullptr);
00056       AbortedInfo.setInt(false);
00057       EscapedInfo.setPointer(nullptr);
00058       EscapedInfo.setInt(false);
00059     }
00060 
00061     /// \brief Did we abort the visit early?
00062     bool isAborted() const { return AbortedInfo.getInt(); }
00063 
00064     /// \brief Is the pointer escaped at some point?
00065     bool isEscaped() const { return EscapedInfo.getInt(); }
00066 
00067     /// \brief Get the instruction causing the visit to abort.
00068     /// \returns a pointer to the instruction causing the abort if one is
00069     /// available; otherwise returns null.
00070     Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); }
00071 
00072     /// \brief Get the instruction causing the pointer to escape.
00073     /// \returns a pointer to the instruction which escapes the pointer if one
00074     /// is available; otherwise returns null.
00075     Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); }
00076 
00077     /// \brief Mark the visit as aborted. Intended for use in a void return.
00078     /// \param I The instruction which caused the visit to abort, if available.
00079     void setAborted(Instruction *I = nullptr) {
00080       AbortedInfo.setInt(true);
00081       AbortedInfo.setPointer(I);
00082     }
00083 
00084     /// \brief Mark the pointer as escaped. Intended for use in a void return.
00085     /// \param I The instruction which escapes the pointer, if available.
00086     void setEscaped(Instruction *I = nullptr) {
00087       EscapedInfo.setInt(true);
00088       EscapedInfo.setPointer(I);
00089     }
00090 
00091     /// \brief Mark the pointer as escaped, and the visit as aborted. Intended
00092     /// for use in a void return.
00093     /// \param I The instruction which both escapes the pointer and aborts the
00094     /// visit, if available.
00095     void setEscapedAndAborted(Instruction *I = nullptr) {
00096       setEscaped(I);
00097       setAborted(I);
00098     }
00099 
00100   private:
00101     PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
00102   };
00103 
00104 protected:
00105   const DataLayout &DL;
00106 
00107   /// \name Visitation infrastructure
00108   /// @{
00109 
00110   /// \brief The info collected about the pointer being visited thus far.
00111   PtrInfo PI;
00112 
00113   /// \brief A struct of the data needed to visit a particular use.
00114   ///
00115   /// This is used to maintain a worklist fo to-visit uses. This is used to
00116   /// make the visit be iterative rather than recursive.
00117   struct UseToVisit {
00118     typedef PointerIntPair<Use *, 1, bool> UseAndIsOffsetKnownPair;
00119     UseAndIsOffsetKnownPair UseAndIsOffsetKnown;
00120     APInt Offset;
00121   };
00122 
00123   /// \brief The worklist of to-visit uses.
00124   SmallVector<UseToVisit, 8> Worklist;
00125 
00126   /// \brief A set of visited uses to break cycles in unreachable code.
00127   SmallPtrSet<Use *, 8> VisitedUses;
00128 
00129   /// @}
00130 
00131 
00132   /// \name Per-visit state
00133   /// This state is reset for each instruction visited.
00134   /// @{
00135 
00136   /// \brief The use currently being visited.
00137   Use *U;
00138 
00139   /// \brief True if we have a known constant offset for the use currently
00140   /// being visited.
00141   bool IsOffsetKnown;
00142 
00143   /// \brief The constant offset of the use if that is known.
00144   APInt Offset;
00145 
00146   /// @}
00147 
00148 
00149   /// Note that the constructor is protected because this class must be a base
00150   /// class, we can't create instances directly of this class.
00151   PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
00152 
00153   /// \brief Enqueue the users of this instruction in the visit worklist.
00154   ///
00155   /// This will visit the users with the same offset of the current visit
00156   /// (including an unknown offset if that is the current state).
00157   void enqueueUsers(Instruction &I);
00158 
00159   /// \brief Walk the operands of a GEP and adjust the offset as appropriate.
00160   ///
00161   /// This routine does the heavy lifting of the pointer walk by computing
00162   /// offsets and looking through GEPs.
00163   bool adjustOffsetForGEP(GetElementPtrInst &GEPI);
00164 };
00165 } // end namespace detail
00166 
00167 /// \brief A base class for visitors over the uses of a pointer value.
00168 ///
00169 /// Once constructed, a user can call \c visit on a pointer value, and this
00170 /// will walk its uses and visit each instruction using an InstVisitor. It also
00171 /// provides visit methods which will recurse through any pointer-to-pointer
00172 /// transformations such as GEPs and bitcasts.
00173 ///
00174 /// During the visit, the current Use* being visited is available to the
00175 /// subclass, as well as the current offset from the original base pointer if
00176 /// known.
00177 ///
00178 /// The recursive visit of uses is accomplished with a worklist, so the only
00179 /// ordering guarantee is that an instruction is visited before any uses of it
00180 /// are visited. Note that this does *not* mean before any of its users are
00181 /// visited! This is because users can be visited multiple times due to
00182 /// multiple, different uses of pointers derived from the same base.
00183 ///
00184 /// A particular Use will only be visited once, but a User may be visited
00185 /// multiple times, once per Use. This visits may notably have different
00186 /// offsets.
00187 ///
00188 /// All visit methods on the underlying InstVisitor return a boolean. This
00189 /// return short-circuits the visit, stopping it immediately.
00190 ///
00191 /// FIXME: Generalize this for all values rather than just instructions.
00192 template <typename DerivedT>
00193 class PtrUseVisitor : protected InstVisitor<DerivedT>,
00194                       public detail::PtrUseVisitorBase {
00195   friend class InstVisitor<DerivedT>;
00196   typedef InstVisitor<DerivedT> Base;
00197 
00198 public:
00199   PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {}
00200 
00201   /// \brief Recursively visit the uses of the given pointer.
00202   /// \returns An info struct about the pointer. See \c PtrInfo for details.
00203   PtrInfo visitPtr(Instruction &I) {
00204     // This must be a pointer type. Get an integer type suitable to hold
00205     // offsets on this pointer.
00206     // FIXME: Support a vector of pointers.
00207     assert(I.getType()->isPointerTy());
00208     IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
00209     IsOffsetKnown = true;
00210     Offset = APInt(IntPtrTy->getBitWidth(), 0);
00211     PI.reset();
00212 
00213     // Enqueue the uses of this pointer.
00214     enqueueUsers(I);
00215 
00216     // Visit all the uses off the worklist until it is empty.
00217     while (!Worklist.empty()) {
00218       UseToVisit ToVisit = Worklist.pop_back_val();
00219       U = ToVisit.UseAndIsOffsetKnown.getPointer();
00220       IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
00221       if (IsOffsetKnown)
00222         Offset = std::move(ToVisit.Offset);
00223 
00224       Instruction *I = cast<Instruction>(U->getUser());
00225       static_cast<DerivedT*>(this)->visit(I);
00226       if (PI.isAborted())
00227         break;
00228     }
00229     return PI;
00230   }
00231 
00232 protected:
00233   void visitStoreInst(StoreInst &SI) {
00234     if (SI.getValueOperand() == U->get())
00235       PI.setEscaped(&SI);
00236   }
00237 
00238   void visitBitCastInst(BitCastInst &BC) {
00239     enqueueUsers(BC);
00240   }
00241 
00242   void visitPtrToIntInst(PtrToIntInst &I) {
00243     PI.setEscaped(&I);
00244   }
00245 
00246   void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
00247     if (GEPI.use_empty())
00248       return;
00249 
00250     // If we can't walk the GEP, clear the offset.
00251     if (!adjustOffsetForGEP(GEPI)) {
00252       IsOffsetKnown = false;
00253       Offset = APInt();
00254     }
00255 
00256     // Enqueue the users now that the offset has been adjusted.
00257     enqueueUsers(GEPI);
00258   }
00259 
00260   // No-op intrinsics which we know don't escape the pointer to to logic in
00261   // some other function.
00262   void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {}
00263   void visitMemIntrinsic(MemIntrinsic &I) {}
00264   void visitIntrinsicInst(IntrinsicInst &II) {
00265     switch (II.getIntrinsicID()) {
00266     default:
00267       return Base::visitIntrinsicInst(II);
00268 
00269     case Intrinsic::lifetime_start:
00270     case Intrinsic::lifetime_end:
00271       return; // No-op intrinsics.
00272     }
00273   }
00274 
00275   // Generically, arguments to calls and invokes escape the pointer to some
00276   // other function. Mark that.
00277   void visitCallSite(CallSite CS) {
00278     PI.setEscaped(CS.getInstruction());
00279     Base::visitCallSite(CS);
00280   }
00281 };
00282 
00283 }
00284 
00285 #endif