1249259Sdim//===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- C++ -*-===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim/// \file 10249259Sdim/// This file provides a collection of visitors which walk the (instruction) 11249259Sdim/// uses of a pointer. These visitors all provide the same essential behavior 12249259Sdim/// as an InstVisitor with similar template-based flexibility and 13249259Sdim/// implementation strategies. 14249259Sdim/// 15249259Sdim/// These can be used, for example, to quickly analyze the uses of an alloca, 16249259Sdim/// global variable, or function argument. 17249259Sdim/// 18249259Sdim/// FIXME: Provide a variant which doesn't track offsets and is cheaper. 19249259Sdim/// 20249259Sdim//===----------------------------------------------------------------------===// 21249259Sdim 22249259Sdim#ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H 23249259Sdim#define LLVM_ANALYSIS_PTRUSEVISITOR_H 24249259Sdim 25249259Sdim#include "llvm/ADT/APInt.h" 26249259Sdim#include "llvm/ADT/SmallPtrSet.h" 27249259Sdim#include "llvm/ADT/SmallVector.h" 28249259Sdim#include "llvm/IR/DataLayout.h" 29249259Sdim#include "llvm/IR/IntrinsicInst.h" 30249259Sdim#include "llvm/InstVisitor.h" 31249259Sdim#include "llvm/Support/Compiler.h" 32249259Sdim 33249259Sdimnamespace llvm { 34249259Sdim 35249259Sdimnamespace detail { 36249259Sdim/// \brief Implementation of non-dependent functionality for \c PtrUseVisitor. 37249259Sdim/// 38249259Sdim/// See \c PtrUseVisitor for the public interface and detailed comments about 39249259Sdim/// usage. This class is just a helper base class which is not templated and 40249259Sdim/// contains all common code to be shared between different instantiations of 41249259Sdim/// PtrUseVisitor. 42249259Sdimclass PtrUseVisitorBase { 43249259Sdimpublic: 44249259Sdim /// \brief This class provides information about the result of a visit. 45249259Sdim /// 46249259Sdim /// After walking all the users (recursively) of a pointer, the basic 47249259Sdim /// infrastructure records some commonly useful information such as escape 48249259Sdim /// analysis and whether the visit completed or aborted early. 49249259Sdim class PtrInfo { 50249259Sdim public: 51249259Sdim PtrInfo() : AbortedInfo(0, false), EscapedInfo(0, false) {} 52249259Sdim 53249259Sdim /// \brief Reset the pointer info, clearing all state. 54249259Sdim void reset() { 55249259Sdim AbortedInfo.setPointer(0); 56249259Sdim AbortedInfo.setInt(false); 57249259Sdim EscapedInfo.setPointer(0); 58249259Sdim EscapedInfo.setInt(false); 59249259Sdim } 60249259Sdim 61249259Sdim /// \brief Did we abort the visit early? 62249259Sdim bool isAborted() const { return AbortedInfo.getInt(); } 63249259Sdim 64249259Sdim /// \brief Is the pointer escaped at some point? 65249259Sdim bool isEscaped() const { return EscapedInfo.getInt(); } 66249259Sdim 67249259Sdim /// \brief Get the instruction causing the visit to abort. 68249259Sdim /// \returns a pointer to the instruction causing the abort if one is 69249259Sdim /// available; otherwise returns null. 70249259Sdim Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); } 71249259Sdim 72249259Sdim /// \brief Get the instruction causing the pointer to escape. 73249259Sdim /// \returns a pointer to the instruction which escapes the pointer if one 74249259Sdim /// is available; otherwise returns null. 75249259Sdim Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); } 76249259Sdim 77249259Sdim /// \brief Mark the visit as aborted. Intended for use in a void return. 78249259Sdim /// \param I The instruction which caused the visit to abort, if available. 79249259Sdim void setAborted(Instruction *I = 0) { 80249259Sdim AbortedInfo.setInt(true); 81249259Sdim AbortedInfo.setPointer(I); 82249259Sdim } 83249259Sdim 84249259Sdim /// \brief Mark the pointer as escaped. Intended for use in a void return. 85249259Sdim /// \param I The instruction which escapes the pointer, if available. 86249259Sdim void setEscaped(Instruction *I = 0) { 87249259Sdim EscapedInfo.setInt(true); 88249259Sdim EscapedInfo.setPointer(I); 89249259Sdim } 90249259Sdim 91249259Sdim /// \brief Mark the pointer as escaped, and the visit as aborted. Intended 92249259Sdim /// for use in a void return. 93249259Sdim /// \param I The instruction which both escapes the pointer and aborts the 94249259Sdim /// visit, if available. 95249259Sdim void setEscapedAndAborted(Instruction *I = 0) { 96249259Sdim setEscaped(I); 97249259Sdim setAborted(I); 98249259Sdim } 99249259Sdim 100249259Sdim private: 101249259Sdim PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo; 102249259Sdim }; 103249259Sdim 104249259Sdimprotected: 105249259Sdim const DataLayout &DL; 106249259Sdim 107249259Sdim /// \name Visitation infrastructure 108249259Sdim /// @{ 109249259Sdim 110249259Sdim /// \brief The info collected about the pointer being visited thus far. 111249259Sdim PtrInfo PI; 112249259Sdim 113249259Sdim /// \brief A struct of the data needed to visit a particular use. 114249259Sdim /// 115249259Sdim /// This is used to maintain a worklist fo to-visit uses. This is used to 116249259Sdim /// make the visit be iterative rather than recursive. 117249259Sdim struct UseToVisit { 118249259Sdim typedef PointerIntPair<Use *, 1, bool> UseAndIsOffsetKnownPair; 119249259Sdim UseAndIsOffsetKnownPair UseAndIsOffsetKnown; 120249259Sdim APInt Offset; 121249259Sdim }; 122249259Sdim 123249259Sdim /// \brief The worklist of to-visit uses. 124249259Sdim SmallVector<UseToVisit, 8> Worklist; 125249259Sdim 126249259Sdim /// \brief A set of visited uses to break cycles in unreachable code. 127249259Sdim SmallPtrSet<Use *, 8> VisitedUses; 128249259Sdim 129249259Sdim /// @} 130249259Sdim 131249259Sdim 132249259Sdim /// \name Per-visit state 133249259Sdim /// This state is reset for each instruction visited. 134249259Sdim /// @{ 135249259Sdim 136249259Sdim /// \brief The use currently being visited. 137249259Sdim Use *U; 138249259Sdim 139249259Sdim /// \brief True if we have a known constant offset for the use currently 140249259Sdim /// being visited. 141249259Sdim bool IsOffsetKnown; 142249259Sdim 143249259Sdim /// \brief The constant offset of the use if that is known. 144249259Sdim APInt Offset; 145249259Sdim 146249259Sdim /// @} 147249259Sdim 148249259Sdim 149249259Sdim /// Note that the constructor is protected because this class must be a base 150249259Sdim /// class, we can't create instances directly of this class. 151249259Sdim PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {} 152249259Sdim 153249259Sdim /// \brief Enqueue the users of this instruction in the visit worklist. 154249259Sdim /// 155249259Sdim /// This will visit the users with the same offset of the current visit 156249259Sdim /// (including an unknown offset if that is the current state). 157249259Sdim void enqueueUsers(Instruction &I); 158249259Sdim 159249259Sdim /// \brief Walk the operands of a GEP and adjust the offset as appropriate. 160249259Sdim /// 161249259Sdim /// This routine does the heavy lifting of the pointer walk by computing 162249259Sdim /// offsets and looking through GEPs. 163249259Sdim bool adjustOffsetForGEP(GetElementPtrInst &GEPI); 164249259Sdim}; 165249259Sdim} // end namespace detail 166249259Sdim 167249259Sdim/// \brief A base class for visitors over the uses of a pointer value. 168249259Sdim/// 169249259Sdim/// Once constructed, a user can call \c visit on a pointer value, and this 170249259Sdim/// will walk its uses and visit each instruction using an InstVisitor. It also 171249259Sdim/// provides visit methods which will recurse through any pointer-to-pointer 172249259Sdim/// transformations such as GEPs and bitcasts. 173249259Sdim/// 174249259Sdim/// During the visit, the current Use* being visited is available to the 175249259Sdim/// subclass, as well as the current offset from the original base pointer if 176249259Sdim/// known. 177249259Sdim/// 178249259Sdim/// The recursive visit of uses is accomplished with a worklist, so the only 179249259Sdim/// ordering guarantee is that an instruction is visited before any uses of it 180249259Sdim/// are visited. Note that this does *not* mean before any of its users are 181249259Sdim/// visited! This is because users can be visited multiple times due to 182249259Sdim/// multiple, different uses of pointers derived from the same base. 183249259Sdim/// 184249259Sdim/// A particular Use will only be visited once, but a User may be visited 185249259Sdim/// multiple times, once per Use. This visits may notably have different 186249259Sdim/// offsets. 187249259Sdim/// 188249259Sdim/// All visit methods on the underlying InstVisitor return a boolean. This 189249259Sdim/// return short-circuits the visit, stopping it immediately. 190249259Sdim/// 191249259Sdim/// FIXME: Generalize this for all values rather than just instructions. 192249259Sdimtemplate <typename DerivedT> 193249259Sdimclass PtrUseVisitor : protected InstVisitor<DerivedT>, 194249259Sdim public detail::PtrUseVisitorBase { 195249259Sdim friend class InstVisitor<DerivedT>; 196249259Sdim typedef InstVisitor<DerivedT> Base; 197249259Sdim 198249259Sdimpublic: 199249259Sdim PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {} 200249259Sdim 201249259Sdim /// \brief Recursively visit the uses of the given pointer. 202249259Sdim /// \returns An info struct about the pointer. See \c PtrInfo for details. 203249259Sdim PtrInfo visitPtr(Instruction &I) { 204249259Sdim // This must be a pointer type. Get an integer type suitable to hold 205249259Sdim // offsets on this pointer. 206249259Sdim // FIXME: Support a vector of pointers. 207249259Sdim assert(I.getType()->isPointerTy()); 208249259Sdim IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType())); 209249259Sdim IsOffsetKnown = true; 210249259Sdim Offset = APInt(IntPtrTy->getBitWidth(), 0); 211249259Sdim PI.reset(); 212249259Sdim 213249259Sdim // Enqueue the uses of this pointer. 214249259Sdim enqueueUsers(I); 215249259Sdim 216249259Sdim // Visit all the uses off the worklist until it is empty. 217249259Sdim while (!Worklist.empty()) { 218249259Sdim UseToVisit ToVisit = Worklist.pop_back_val(); 219249259Sdim U = ToVisit.UseAndIsOffsetKnown.getPointer(); 220249259Sdim IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt(); 221249259Sdim if (IsOffsetKnown) 222249259Sdim Offset = llvm_move(ToVisit.Offset); 223249259Sdim 224249259Sdim Instruction *I = cast<Instruction>(U->getUser()); 225249259Sdim static_cast<DerivedT*>(this)->visit(I); 226249259Sdim if (PI.isAborted()) 227249259Sdim break; 228249259Sdim } 229249259Sdim return PI; 230249259Sdim } 231249259Sdim 232249259Sdimprotected: 233249259Sdim void visitStoreInst(StoreInst &SI) { 234249259Sdim if (SI.getValueOperand() == U->get()) 235249259Sdim PI.setEscaped(&SI); 236249259Sdim } 237249259Sdim 238249259Sdim void visitBitCastInst(BitCastInst &BC) { 239249259Sdim enqueueUsers(BC); 240249259Sdim } 241249259Sdim 242249259Sdim void visitPtrToIntInst(PtrToIntInst &I) { 243249259Sdim PI.setEscaped(&I); 244249259Sdim } 245249259Sdim 246249259Sdim void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 247249259Sdim if (GEPI.use_empty()) 248249259Sdim return; 249249259Sdim 250249259Sdim // If we can't walk the GEP, clear the offset. 251249259Sdim if (!adjustOffsetForGEP(GEPI)) { 252249259Sdim IsOffsetKnown = false; 253249259Sdim Offset = APInt(); 254249259Sdim } 255249259Sdim 256249259Sdim // Enqueue the users now that the offset has been adjusted. 257249259Sdim enqueueUsers(GEPI); 258249259Sdim } 259249259Sdim 260249259Sdim // No-op intrinsics which we know don't escape the pointer to to logic in 261249259Sdim // some other function. 262249259Sdim void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {} 263249259Sdim void visitMemIntrinsic(MemIntrinsic &I) {} 264249259Sdim void visitIntrinsicInst(IntrinsicInst &II) { 265249259Sdim switch (II.getIntrinsicID()) { 266249259Sdim default: 267249259Sdim return Base::visitIntrinsicInst(II); 268249259Sdim 269249259Sdim case Intrinsic::lifetime_start: 270249259Sdim case Intrinsic::lifetime_end: 271249259Sdim return; // No-op intrinsics. 272249259Sdim } 273249259Sdim } 274249259Sdim 275249259Sdim // Generically, arguments to calls and invokes escape the pointer to some 276249259Sdim // other function. Mark that. 277249259Sdim void visitCallSite(CallSite CS) { 278249259Sdim PI.setEscaped(CS.getInstruction()); 279249259Sdim Base::visitCallSite(CS); 280249259Sdim } 281249259Sdim}; 282249259Sdim 283249259Sdim} 284249259Sdim 285249259Sdim#endif 286