1 //===- Loads.cpp - Local load analysis ------------------------------------===// 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 // 10 // This file defines simple local analyses for load instructions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/Loads.h" 15 #include "llvm/Analysis/AliasAnalysis.h" 16 #include "llvm/Analysis/ValueTracking.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/IR/GlobalAlias.h" 19 #include "llvm/IR/GlobalVariable.h" 20 #include "llvm/IR/IntrinsicInst.h" 21 #include "llvm/IR/LLVMContext.h" 22 #include "llvm/IR/Module.h" 23 #include "llvm/IR/Operator.h" 24 using namespace llvm; 25 26 /// \brief Test if A and B will obviously have the same value. 27 /// 28 /// This includes recognizing that %t0 and %t1 will have the same 29 /// value in code like this: 30 /// \code 31 /// %t0 = getelementptr \@a, 0, 3 32 /// store i32 0, i32* %t0 33 /// %t1 = getelementptr \@a, 0, 3 34 /// %t2 = load i32* %t1 35 /// \endcode 36 /// 37 static bool AreEquivalentAddressValues(const Value *A, const Value *B) { 38 // Test if the values are trivially equivalent. 39 if (A == B) 40 return true; 41 42 // Test if the values come from identical arithmetic instructions. 43 // Use isIdenticalToWhenDefined instead of isIdenticalTo because 44 // this function is only used when one address use dominates the 45 // other, which means that they'll always either have the same 46 // value or one of them will have an undefined value. 47 if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) || 48 isa<GetElementPtrInst>(A)) 49 if (const Instruction *BI = dyn_cast<Instruction>(B)) 50 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) 51 return true; 52 53 // Otherwise they may not be equivalent. 54 return false; 55 } 56 57 /// \brief Check if executing a load of this pointer value cannot trap. 58 /// 59 /// If it is not obviously safe to load from the specified pointer, we do 60 /// a quick local scan of the basic block containing \c ScanFrom, to determine 61 /// if the address is already accessed. 62 /// 63 /// This uses the pointee type to determine how many bytes need to be safe to 64 /// load from the pointer. 65 bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom, 66 unsigned Align) { 67 const DataLayout &DL = ScanFrom->getModule()->getDataLayout(); 68 69 // Zero alignment means that the load has the ABI alignment for the target 70 if (Align == 0) 71 Align = DL.getABITypeAlignment(V->getType()->getPointerElementType()); 72 assert(isPowerOf2_32(Align)); 73 74 int64_t ByteOffset = 0; 75 Value *Base = V; 76 Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL); 77 78 if (ByteOffset < 0) // out of bounds 79 return false; 80 81 Type *BaseType = nullptr; 82 unsigned BaseAlign = 0; 83 if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 84 // An alloca is safe to load from as load as it is suitably aligned. 85 BaseType = AI->getAllocatedType(); 86 BaseAlign = AI->getAlignment(); 87 } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 88 // Global variables are not necessarily safe to load from if they are 89 // overridden. Their size may change or they may be weak and require a test 90 // to determine if they were in fact provided. 91 if (!GV->mayBeOverridden()) { 92 BaseType = GV->getType()->getElementType(); 93 BaseAlign = GV->getAlignment(); 94 } 95 } 96 97 PointerType *AddrTy = cast<PointerType>(V->getType()); 98 uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType()); 99 100 // If we found a base allocated type from either an alloca or global variable, 101 // try to see if we are definitively within the allocated region. We need to 102 // know the size of the base type and the loaded type to do anything in this 103 // case. 104 if (BaseType && BaseType->isSized()) { 105 if (BaseAlign == 0) 106 BaseAlign = DL.getPrefTypeAlignment(BaseType); 107 108 if (Align <= BaseAlign) { 109 // Check if the load is within the bounds of the underlying object. 110 if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) && 111 ((ByteOffset % Align) == 0)) 112 return true; 113 } 114 } 115 116 // Otherwise, be a little bit aggressive by scanning the local block where we 117 // want to check to see if the pointer is already being loaded or stored 118 // from/to. If so, the previous load or store would have already trapped, 119 // so there is no harm doing an extra load (also, CSE will later eliminate 120 // the load entirely). 121 BasicBlock::iterator BBI = ScanFrom->getIterator(), 122 E = ScanFrom->getParent()->begin(); 123 124 // We can at least always strip pointer casts even though we can't use the 125 // base here. 126 V = V->stripPointerCasts(); 127 128 while (BBI != E) { 129 --BBI; 130 131 // If we see a free or a call which may write to memory (i.e. which might do 132 // a free) the pointer could be marked invalid. 133 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 134 !isa<DbgInfoIntrinsic>(BBI)) 135 return false; 136 137 Value *AccessedPtr; 138 unsigned AccessedAlign; 139 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 140 AccessedPtr = LI->getPointerOperand(); 141 AccessedAlign = LI->getAlignment(); 142 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 143 AccessedPtr = SI->getPointerOperand(); 144 AccessedAlign = SI->getAlignment(); 145 } else 146 continue; 147 148 Type *AccessedTy = AccessedPtr->getType()->getPointerElementType(); 149 if (AccessedAlign == 0) 150 AccessedAlign = DL.getABITypeAlignment(AccessedTy); 151 if (AccessedAlign < Align) 152 continue; 153 154 // Handle trivial cases. 155 if (AccessedPtr == V) 156 return true; 157 158 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) && 159 LoadSize <= DL.getTypeStoreSize(AccessedTy)) 160 return true; 161 } 162 return false; 163 } 164 165 /// DefMaxInstsToScan - the default number of maximum instructions 166 /// to scan in the block, used by FindAvailableLoadedValue(). 167 /// FindAvailableLoadedValue() was introduced in r60148, to improve jump 168 /// threading in part by eliminating partially redundant loads. 169 /// At that point, the value of MaxInstsToScan was already set to '6' 170 /// without documented explanation. 171 cl::opt<unsigned> 172 llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden, 173 cl::desc("Use this to specify the default maximum number of instructions " 174 "to scan backward from a given instruction, when searching for " 175 "available loaded value")); 176 177 /// \brief Scan the ScanBB block backwards to see if we have the value at the 178 /// memory address *Ptr locally available within a small number of instructions. 179 /// 180 /// The scan starts from \c ScanFrom. \c MaxInstsToScan specifies the maximum 181 /// instructions to scan in the block. If it is set to \c 0, it will scan the whole 182 /// block. 183 /// 184 /// If the value is available, this function returns it. If not, it returns the 185 /// iterator for the last validated instruction that the value would be live 186 /// through. If we scanned the entire block and didn't find something that 187 /// invalidates \c *Ptr or provides it, \c ScanFrom is left at the last 188 /// instruction processed and this returns null. 189 /// 190 /// You can also optionally specify an alias analysis implementation, which 191 /// makes this more precise. 192 /// 193 /// If \c AATags is non-null and a load or store is found, the AA tags from the 194 /// load or store are recorded there. If there are no AA tags or if no access is 195 /// found, it is left unmodified. 196 Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, 197 BasicBlock::iterator &ScanFrom, 198 unsigned MaxInstsToScan, 199 AliasAnalysis *AA, AAMDNodes *AATags) { 200 if (MaxInstsToScan == 0) 201 MaxInstsToScan = ~0U; 202 203 Type *AccessTy = cast<PointerType>(Ptr->getType())->getElementType(); 204 205 const DataLayout &DL = ScanBB->getModule()->getDataLayout(); 206 207 // Try to get the store size for the type. 208 uint64_t AccessSize = DL.getTypeStoreSize(AccessTy); 209 210 Value *StrippedPtr = Ptr->stripPointerCasts(); 211 212 while (ScanFrom != ScanBB->begin()) { 213 // We must ignore debug info directives when counting (otherwise they 214 // would affect codegen). 215 Instruction *Inst = &*--ScanFrom; 216 if (isa<DbgInfoIntrinsic>(Inst)) 217 continue; 218 219 // Restore ScanFrom to expected value in case next test succeeds 220 ScanFrom++; 221 222 // Don't scan huge blocks. 223 if (MaxInstsToScan-- == 0) 224 return nullptr; 225 226 --ScanFrom; 227 // If this is a load of Ptr, the loaded value is available. 228 // (This is true even if the load is volatile or atomic, although 229 // those cases are unlikely.) 230 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 231 if (AreEquivalentAddressValues( 232 LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) && 233 CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) { 234 if (AATags) 235 LI->getAAMetadata(*AATags); 236 return LI; 237 } 238 239 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 240 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); 241 // If this is a store through Ptr, the value is available! 242 // (This is true even if the store is volatile or atomic, although 243 // those cases are unlikely.) 244 if (AreEquivalentAddressValues(StorePtr, StrippedPtr) && 245 CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(), 246 AccessTy, DL)) { 247 if (AATags) 248 SI->getAAMetadata(*AATags); 249 return SI->getOperand(0); 250 } 251 252 // If both StrippedPtr and StorePtr reach all the way to an alloca or 253 // global and they are different, ignore the store. This is a trivial form 254 // of alias analysis that is important for reg2mem'd code. 255 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) && 256 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) && 257 StrippedPtr != StorePtr) 258 continue; 259 260 // If we have alias analysis and it says the store won't modify the loaded 261 // value, ignore the store. 262 if (AA && (AA->getModRefInfo(SI, StrippedPtr, AccessSize) & MRI_Mod) == 0) 263 continue; 264 265 // Otherwise the store that may or may not alias the pointer, bail out. 266 ++ScanFrom; 267 return nullptr; 268 } 269 270 // If this is some other instruction that may clobber Ptr, bail out. 271 if (Inst->mayWriteToMemory()) { 272 // If alias analysis claims that it really won't modify the load, 273 // ignore it. 274 if (AA && 275 (AA->getModRefInfo(Inst, StrippedPtr, AccessSize) & MRI_Mod) == 0) 276 continue; 277 278 // May modify the pointer, bail out. 279 ++ScanFrom; 280 return nullptr; 281 } 282 } 283 284 // Got to the start of the block, we didn't find it, but are done for this 285 // block. 286 return nullptr; 287 } 288
