LCOV - code coverage report
Current view: top level - include/llvm/Analysis - PtrUseVisitor.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 49 49 100.0 %
Date: 2017-09-14 15:23:50 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : /// \brief 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      511960 : class PtrUseVisitorBase {
      57             : public:
      58             :   /// \brief 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      383970 :     PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {}
      66             : 
      67             :     /// \brief Reset the pointer info, clearing all state.
      68             :     void reset() {
      69      255980 :       AbortedInfo.setPointer(nullptr);
      70      255980 :       AbortedInfo.setInt(false);
      71      255980 :       EscapedInfo.setPointer(nullptr);
      72      255980 :       EscapedInfo.setInt(false);
      73             :     }
      74             : 
      75             :     /// \brief Did we abort the visit early?
      76     1105286 :     bool isAborted() const { return AbortedInfo.getInt(); }
      77             : 
      78             :     /// \brief Is the pointer escaped at some point?
      79      255980 :     bool isEscaped() const { return EscapedInfo.getInt(); }
      80             : 
      81             :     /// \brief 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         746 :     Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); }
      85             : 
      86             :     /// \brief 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       87010 :     Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); }
      90             : 
      91             :     /// \brief 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       86992 :       AbortedInfo.setInt(true);
      95       86992 :       AbortedInfo.setPointer(I);
      96             :     }
      97             : 
      98             :     /// \brief 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       86268 :       EscapedInfo.setInt(true);
     102       86268 :       EscapedInfo.setPointer(I);
     103             :     }
     104             : 
     105             :     /// \brief 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         320 :       setEscaped(I);
     111         320 :       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             :   /// \brief The info collected about the pointer being visited thus far.
     125             :   PtrInfo PI;
     126             : 
     127             :   /// \brief 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     5867820 :   struct UseToVisit {
     132             :     using UseAndIsOffsetKnownPair = PointerIntPair<Use *, 1, bool>;
     133             : 
     134             :     UseAndIsOffsetKnownPair UseAndIsOffsetKnown;
     135             :     APInt Offset;
     136             :   };
     137             : 
     138             :   /// \brief The worklist of to-visit uses.
     139             :   SmallVector<UseToVisit, 8> Worklist;
     140             : 
     141             :   /// \brief 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             :   /// \brief The use currently being visited.
     151             :   Use *U;
     152             : 
     153             :   /// \brief True if we have a known constant offset for the use currently
     154             :   /// being visited.
     155             :   bool IsOffsetKnown;
     156             : 
     157             :   /// \brief 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      639950 :   PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
     165             : 
     166             :   /// \brief 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             :   /// \brief 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             : /// \brief 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      127990 : class PtrUseVisitor : protected InstVisitor<DerivedT>,
     208             :                       public detail::PtrUseVisitorBase {
     209             :   friend class InstVisitor<DerivedT>;
     210             : 
     211             :   using Base = InstVisitor<DerivedT>;
     212             : 
     213             : public:
     214      255980 :   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             :   /// \brief Recursively visit the uses of the given pointer.
     220             :   /// \returns An info struct about the pointer. See \c PtrInfo for details.
     221      127990 :   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      255980 :     IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
     227      127990 :     IsOffsetKnown = true;
     228      511960 :     Offset = APInt(IntPtrTy->getBitWidth(), 0);
     229      255980 :     PI.reset();
     230             : 
     231             :     // Enqueue the uses of this pointer.
     232      127990 :     enqueueUsers(I);
     233             : 
     234             :     // Visit all the uses off the worklist until it is empty.
     235      552279 :     while (!Worklist.empty()) {
     236     1359859 :       UseToVisit ToVisit = Worklist.pop_back_val();
     237      467785 :       U = ToVisit.UseAndIsOffsetKnown.getPointer();
     238      467785 :       IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
     239      467785 :       if (IsOffsetKnown)
     240      467450 :         Offset = std::move(ToVisit.Offset);
     241             : 
     242      935570 :       Instruction *I = cast<Instruction>(U->getUser());
     243      467785 :       static_cast<DerivedT*>(this)->visit(I);
     244      935570 :       if (PI.isAborted())
     245             :         break;
     246             :     }
     247      127990 :     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       62134 :     enqueueUsers(BC);
     258             :   }
     259             : 
     260             :   void visitPtrToIntInst(PtrToIntInst &I) {
     261          30 :     PI.setEscaped(&I);
     262             :   }
     263             : 
     264       20846 :   void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
     265       41692 :     if (GEPI.use_empty())
     266             :       return;
     267             : 
     268             :     // If we can't walk the GEP, clear the offset.
     269       20846 :     if (!adjustOffsetForGEP(GEPI)) {
     270         328 :       IsOffsetKnown = false;
     271         984 :       Offset = APInt();
     272             :     }
     273             : 
     274             :     // Enqueue the users now that the offset has been adjusted.
     275       20846 :     enqueueUsers(GEPI);
     276             :   }
     277             : 
     278             :   // No-op intrinsics which we know don't escape the pointer to to logic in
     279             :   // some other function.
     280             :   void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {}
     281             :   void visitMemIntrinsic(MemIntrinsic &I) {}
     282          42 :   void visitIntrinsicInst(IntrinsicInst &II) {
     283          42 :     switch (II.getIntrinsicID()) {
     284          42 :     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      128397 :     PI.setEscaped(CS.getInstruction());
     297       42799 :     Base::visitCallSite(CS);
     298             :   }
     299             : };
     300             : 
     301             : } // end namespace llvm
     302             : 
     303             : #endif // LLVM_ANALYSIS_PTRUSEVISITOR_H

Generated by: LCOV version 1.13