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