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 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 PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {} 66 67 /// \brief 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 /// \brief Did we abort the visit early? 76 bool isAborted() const { return AbortedInfo.getInt(); } 77 78 /// \brief Is the pointer escaped at some point? 79 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 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 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 AbortedInfo.setInt(true); 95 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 EscapedInfo.setInt(true); 102 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 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 /// \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 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 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 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 /// \brief 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 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 304