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