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