1 //===- Loads.h - Local load analysis --------------------------------------===// 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 // This file declares simple local analyses for load instructions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_LOADS_H 14 #define LLVM_ANALYSIS_LOADS_H 15 16 #include "llvm/IR/BasicBlock.h" 17 #include "llvm/Support/CommandLine.h" 18 19 namespace llvm { 20 21 class BatchAAResults; 22 class AssumptionCache; 23 class DataLayout; 24 class DominatorTree; 25 class Instruction; 26 class LoadInst; 27 class Loop; 28 class MemoryLocation; 29 class ScalarEvolution; 30 class SCEVPredicate; 31 template <typename T> class SmallVectorImpl; 32 class TargetLibraryInfo; 33 34 /// Return true if this is always a dereferenceable pointer. If the context 35 /// instruction is specified perform context-sensitive analysis and return true 36 /// if the pointer is dereferenceable at the specified instruction. 37 bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, 38 const Instruction *CtxI = nullptr, 39 AssumptionCache *AC = nullptr, 40 const DominatorTree *DT = nullptr, 41 const TargetLibraryInfo *TLI = nullptr); 42 43 /// Returns true if V is always a dereferenceable pointer with alignment 44 /// greater or equal than requested. If the context instruction is specified 45 /// performs context-sensitive analysis and returns true if the pointer is 46 /// dereferenceable at the specified instruction. 47 bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, 48 Align Alignment, const DataLayout &DL, 49 const Instruction *CtxI = nullptr, 50 AssumptionCache *AC = nullptr, 51 const DominatorTree *DT = nullptr, 52 const TargetLibraryInfo *TLI = nullptr); 53 54 /// Returns true if V is always dereferenceable for Size byte with alignment 55 /// greater or equal than requested. If the context instruction is specified 56 /// performs context-sensitive analysis and returns true if the pointer is 57 /// dereferenceable at the specified instruction. 58 bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, 59 const APInt &Size, const DataLayout &DL, 60 const Instruction *CtxI = nullptr, 61 AssumptionCache *AC = nullptr, 62 const DominatorTree *DT = nullptr, 63 const TargetLibraryInfo *TLI = nullptr); 64 65 /// Return true if we know that executing a load from this value cannot trap. 66 /// 67 /// If DT and ScanFrom are specified this method performs context-sensitive 68 /// analysis and returns true if it is safe to load immediately before ScanFrom. 69 /// 70 /// If it is not obviously safe to load from the specified pointer, we do a 71 /// quick local scan of the basic block containing ScanFrom, to determine if 72 /// the address is already accessed. 73 bool isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size, 74 const DataLayout &DL, Instruction *ScanFrom, 75 AssumptionCache *AC = nullptr, 76 const DominatorTree *DT = nullptr, 77 const TargetLibraryInfo *TLI = nullptr); 78 79 /// Return true if we can prove that the given load (which is assumed to be 80 /// within the specified loop) would access only dereferenceable memory, and 81 /// be properly aligned on every iteration of the specified loop regardless of 82 /// its placement within the loop. (i.e. does not require predication beyond 83 /// that required by the header itself and could be hoisted into the header 84 /// if desired.) This is more powerful than the variants above when the 85 /// address loaded from is analyzeable by SCEV. 86 bool isDereferenceableAndAlignedInLoop( 87 LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, 88 AssumptionCache *AC = nullptr, 89 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr); 90 91 /// Return true if the loop \p L cannot fault on any iteration and only 92 /// contains read-only memory accesses. 93 bool isDereferenceableReadOnlyLoop( 94 Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, 95 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr); 96 97 /// Return true if we know that executing a load from this value cannot trap. 98 /// 99 /// If DT and ScanFrom are specified this method performs context-sensitive 100 /// analysis and returns true if it is safe to load immediately before ScanFrom. 101 /// 102 /// If it is not obviously safe to load from the specified pointer, we do a 103 /// quick local scan of the basic block containing ScanFrom, to determine if 104 /// the address is already accessed. 105 bool isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment, 106 const DataLayout &DL, Instruction *ScanFrom, 107 AssumptionCache *AC = nullptr, 108 const DominatorTree *DT = nullptr, 109 const TargetLibraryInfo *TLI = nullptr); 110 111 /// Return true if speculation of the given load must be suppressed to avoid 112 /// ordering or interfering with an active sanitizer. If not suppressed, 113 /// dereferenceability and alignment must be proven separately. Note: This 114 /// is only needed for raw reasoning; if you use the interface below 115 /// (isSafeToSpeculativelyExecute), this is handled internally. 116 bool mustSuppressSpeculation(const LoadInst &LI); 117 118 /// The default number of maximum instructions to scan in the block, used by 119 /// FindAvailableLoadedValue(). 120 extern cl::opt<unsigned> DefMaxInstsToScan; 121 122 /// Scan backwards to see if we have the value of the given load available 123 /// locally within a small number of instructions. 124 /// 125 /// You can use this function to scan across multiple blocks: after you call 126 /// this function, if ScanFrom points at the beginning of the block, it's safe 127 /// to continue scanning the predecessors. 128 /// 129 /// Note that performing load CSE requires special care to make sure the 130 /// metadata is set appropriately. In particular, aliasing metadata needs 131 /// to be merged. (This doesn't matter for store-to-load forwarding because 132 /// the only relevant load gets deleted.) 133 /// 134 /// \param Load The load we want to replace. 135 /// \param ScanBB The basic block to scan. 136 /// \param [in,out] ScanFrom The location to start scanning from. When this 137 /// function returns, it points at the last instruction scanned. 138 /// \param MaxInstsToScan The maximum number of instructions to scan. If this 139 /// is zero, the whole block will be scanned. 140 /// \param AA Optional pointer to alias analysis, to make the scan more 141 /// precise. 142 /// \param [out] IsLoadCSE Whether the returned value is a load from the same 143 /// location in memory, as opposed to the value operand of a store. 144 /// 145 /// \returns The found value, or nullptr if no value is found. 146 Value *FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, 147 BasicBlock::iterator &ScanFrom, 148 unsigned MaxInstsToScan = DefMaxInstsToScan, 149 BatchAAResults *AA = nullptr, 150 bool *IsLoadCSE = nullptr, 151 unsigned *NumScanedInst = nullptr); 152 153 /// This overload provides a more efficient implementation of 154 /// FindAvailableLoadedValue() for the case where we are not interested in 155 /// finding the closest clobbering instruction if no available load is found. 156 /// This overload cannot be used to scan across multiple blocks. 157 Value *FindAvailableLoadedValue(LoadInst *Load, BatchAAResults &AA, 158 bool *IsLoadCSE, 159 unsigned MaxInstsToScan = DefMaxInstsToScan); 160 161 /// Scan backwards to see if we have the value of the given pointer available 162 /// locally within a small number of instructions. 163 /// 164 /// You can use this function to scan across multiple blocks: after you call 165 /// this function, if ScanFrom points at the beginning of the block, it's safe 166 /// to continue scanning the predecessors. 167 /// 168 /// \param Loc The location we want the load and store to originate from. 169 /// \param AccessTy The access type of the pointer. 170 /// \param AtLeastAtomic Are we looking for at-least an atomic load/store ? In 171 /// case it is false, we can return an atomic or non-atomic load or store. In 172 /// case it is true, we need to return an atomic load or store. 173 /// \param ScanBB The basic block to scan. 174 /// \param [in,out] ScanFrom The location to start scanning from. When this 175 /// function returns, it points at the last instruction scanned. 176 /// \param MaxInstsToScan The maximum number of instructions to scan. If this 177 /// is zero, the whole block will be scanned. 178 /// \param AA Optional pointer to alias analysis, to make the scan more 179 /// precise. 180 /// \param [out] IsLoadCSE Whether the returned value is a load from the same 181 /// location in memory, as opposed to the value operand of a store. 182 /// 183 /// \returns The found value, or nullptr if no value is found. 184 Value *findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, 185 bool AtLeastAtomic, BasicBlock *ScanBB, 186 BasicBlock::iterator &ScanFrom, 187 unsigned MaxInstsToScan, BatchAAResults *AA, 188 bool *IsLoadCSE, unsigned *NumScanedInst); 189 190 /// Returns true if a pointer value \p From can be replaced with another pointer 191 /// value \To if they are deemed equal through some means (e.g. information from 192 /// conditions). 193 /// NOTE: The current implementation allows replacement in Icmp and PtrToInt 194 /// instructions, as well as when we are replacing with a null pointer. 195 /// Additionally it also allows replacement of pointers when both pointers have 196 /// the same underlying object. 197 bool canReplacePointersIfEqual(const Value *From, const Value *To, 198 const DataLayout &DL); 199 bool canReplacePointersInUseIfEqual(const Use &U, const Value *To, 200 const DataLayout &DL); 201 } 202 203 #endif 204