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