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 #include "llvm/IR/Statepoint.h" 25 26 using namespace llvm; 27 28 static bool isAligned(const Value *Base, const APInt &Offset, unsigned Align, 29 const DataLayout &DL) { 30 APInt BaseAlign(Offset.getBitWidth(), Base->getPointerAlignment(DL)); 31 32 if (!BaseAlign) { 33 Type *Ty = Base->getType()->getPointerElementType(); 34 if (!Ty->isSized()) 35 return false; 36 BaseAlign = DL.getABITypeAlignment(Ty); 37 } 38 39 APInt Alignment(Offset.getBitWidth(), Align); 40 41 assert(Alignment.isPowerOf2() && "must be a power of 2!"); 42 return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1)); 43 } 44 45 static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) { 46 Type *Ty = Base->getType(); 47 assert(Ty->isSized() && "must be sized"); 48 APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0); 49 return isAligned(Base, Offset, Align, DL); 50 } 51 52 /// Test if V is always a pointer to allocated and suitably aligned memory for 53 /// a simple load or store. 54 static bool isDereferenceableAndAlignedPointer( 55 const Value *V, unsigned Align, const APInt &Size, const DataLayout &DL, 56 const Instruction *CtxI, const DominatorTree *DT, 57 SmallPtrSetImpl<const Value *> &Visited) { 58 // Already visited? Bail out, we've likely hit unreachable code. 59 if (!Visited.insert(V).second) 60 return false; 61 62 // Note that it is not safe to speculate into a malloc'd region because 63 // malloc may return null. 64 65 // bitcast instructions are no-ops as far as dereferenceability is concerned. 66 if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) 67 return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size, 68 DL, CtxI, DT, Visited); 69 70 bool CheckForNonNull = false; 71 APInt KnownDerefBytes(Size.getBitWidth(), 72 V->getPointerDereferenceableBytes(DL, CheckForNonNull)); 73 if (KnownDerefBytes.getBoolValue()) { 74 if (KnownDerefBytes.uge(Size)) 75 if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) 76 return isAligned(V, Align, DL); 77 } 78 79 // For GEPs, determine if the indexing lands within the allocated object. 80 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 81 const Value *Base = GEP->getPointerOperand(); 82 83 APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0); 84 if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() || 85 !Offset.urem(APInt(Offset.getBitWidth(), Align)).isMinValue()) 86 return false; 87 88 // If the base pointer is dereferenceable for Offset+Size bytes, then the 89 // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base 90 // pointer is aligned to Align bytes, and the Offset is divisible by Align 91 // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also 92 // aligned to Align bytes. 93 94 // Offset and Size may have different bit widths if we have visited an 95 // addrspacecast, so we can't do arithmetic directly on the APInt values. 96 return isDereferenceableAndAlignedPointer( 97 Base, Align, Offset + Size.sextOrTrunc(Offset.getBitWidth()), 98 DL, CtxI, DT, Visited); 99 } 100 101 // For gc.relocate, look through relocations 102 if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V)) 103 return isDereferenceableAndAlignedPointer( 104 RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited); 105 106 if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V)) 107 return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size, 108 DL, CtxI, DT, Visited); 109 110 if (auto CS = ImmutableCallSite(V)) 111 if (auto *RP = getArgumentAliasingToReturnedPointer(CS)) 112 return isDereferenceableAndAlignedPointer(RP, Align, Size, DL, CtxI, DT, 113 Visited); 114 115 // If we don't know, assume the worst. 116 return false; 117 } 118 119 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align, 120 const APInt &Size, 121 const DataLayout &DL, 122 const Instruction *CtxI, 123 const DominatorTree *DT) { 124 SmallPtrSet<const Value *, 32> Visited; 125 return ::isDereferenceableAndAlignedPointer(V, Align, Size, DL, CtxI, DT, 126 Visited); 127 } 128 129 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align, 130 const DataLayout &DL, 131 const Instruction *CtxI, 132 const DominatorTree *DT) { 133 // When dereferenceability information is provided by a dereferenceable 134 // attribute, we know exactly how many bytes are dereferenceable. If we can 135 // determine the exact offset to the attributed variable, we can use that 136 // information here. 137 Type *VTy = V->getType(); 138 Type *Ty = VTy->getPointerElementType(); 139 140 // Require ABI alignment for loads without alignment specification 141 if (Align == 0) 142 Align = DL.getABITypeAlignment(Ty); 143 144 if (!Ty->isSized()) 145 return false; 146 147 SmallPtrSet<const Value *, 32> Visited; 148 return ::isDereferenceableAndAlignedPointer( 149 V, Align, APInt(DL.getIndexTypeSizeInBits(VTy), DL.getTypeStoreSize(Ty)), DL, 150 CtxI, DT, Visited); 151 } 152 153 bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL, 154 const Instruction *CtxI, 155 const DominatorTree *DT) { 156 return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT); 157 } 158 159 /// Test if A and B will obviously have the same value. 160 /// 161 /// This includes recognizing that %t0 and %t1 will have the same 162 /// value in code like this: 163 /// \code 164 /// %t0 = getelementptr \@a, 0, 3 165 /// store i32 0, i32* %t0 166 /// %t1 = getelementptr \@a, 0, 3 167 /// %t2 = load i32* %t1 168 /// \endcode 169 /// 170 static bool AreEquivalentAddressValues(const Value *A, const Value *B) { 171 // Test if the values are trivially equivalent. 172 if (A == B) 173 return true; 174 175 // Test if the values come from identical arithmetic instructions. 176 // Use isIdenticalToWhenDefined instead of isIdenticalTo because 177 // this function is only used when one address use dominates the 178 // other, which means that they'll always either have the same 179 // value or one of them will have an undefined value. 180 if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) || 181 isa<GetElementPtrInst>(A)) 182 if (const Instruction *BI = dyn_cast<Instruction>(B)) 183 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) 184 return true; 185 186 // Otherwise they may not be equivalent. 187 return false; 188 } 189 190 /// Check if executing a load of this pointer value cannot trap. 191 /// 192 /// If DT and ScanFrom are specified this method performs context-sensitive 193 /// analysis and returns true if it is safe to load immediately before ScanFrom. 194 /// 195 /// If it is not obviously safe to load from the specified pointer, we do 196 /// a quick local scan of the basic block containing \c ScanFrom, to determine 197 /// if the address is already accessed. 198 /// 199 /// This uses the pointee type to determine how many bytes need to be safe to 200 /// load from the pointer. 201 bool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align, 202 const DataLayout &DL, 203 Instruction *ScanFrom, 204 const DominatorTree *DT) { 205 // Zero alignment means that the load has the ABI alignment for the target 206 if (Align == 0) 207 Align = DL.getABITypeAlignment(V->getType()->getPointerElementType()); 208 assert(isPowerOf2_32(Align)); 209 210 // If DT is not specified we can't make context-sensitive query 211 const Instruction* CtxI = DT ? ScanFrom : nullptr; 212 if (isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT)) 213 return true; 214 215 int64_t ByteOffset = 0; 216 Value *Base = V; 217 Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL); 218 219 if (ByteOffset < 0) // out of bounds 220 return false; 221 222 Type *BaseType = nullptr; 223 unsigned BaseAlign = 0; 224 if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 225 // An alloca is safe to load from as load as it is suitably aligned. 226 BaseType = AI->getAllocatedType(); 227 BaseAlign = AI->getAlignment(); 228 } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 229 // Global variables are not necessarily safe to load from if they are 230 // interposed arbitrarily. Their size may change or they may be weak and 231 // require a test to determine if they were in fact provided. 232 if (!GV->isInterposable()) { 233 BaseType = GV->getType()->getElementType(); 234 BaseAlign = GV->getAlignment(); 235 } 236 } 237 238 PointerType *AddrTy = cast<PointerType>(V->getType()); 239 uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType()); 240 241 // If we found a base allocated type from either an alloca or global variable, 242 // try to see if we are definitively within the allocated region. We need to 243 // know the size of the base type and the loaded type to do anything in this 244 // case. 245 if (BaseType && BaseType->isSized()) { 246 if (BaseAlign == 0) 247 BaseAlign = DL.getPrefTypeAlignment(BaseType); 248 249 if (Align <= BaseAlign) { 250 // Check if the load is within the bounds of the underlying object. 251 if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) && 252 ((ByteOffset % Align) == 0)) 253 return true; 254 } 255 } 256 257 if (!ScanFrom) 258 return false; 259 260 // Otherwise, be a little bit aggressive by scanning the local block where we 261 // want to check to see if the pointer is already being loaded or stored 262 // from/to. If so, the previous load or store would have already trapped, 263 // so there is no harm doing an extra load (also, CSE will later eliminate 264 // the load entirely). 265 BasicBlock::iterator BBI = ScanFrom->getIterator(), 266 E = ScanFrom->getParent()->begin(); 267 268 // We can at least always strip pointer casts even though we can't use the 269 // base here. 270 V = V->stripPointerCasts(); 271 272 while (BBI != E) { 273 --BBI; 274 275 // If we see a free or a call which may write to memory (i.e. which might do 276 // a free) the pointer could be marked invalid. 277 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 278 !isa<DbgInfoIntrinsic>(BBI)) 279 return false; 280 281 Value *AccessedPtr; 282 unsigned AccessedAlign; 283 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 284 AccessedPtr = LI->getPointerOperand(); 285 AccessedAlign = LI->getAlignment(); 286 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 287 AccessedPtr = SI->getPointerOperand(); 288 AccessedAlign = SI->getAlignment(); 289 } else 290 continue; 291 292 Type *AccessedTy = AccessedPtr->getType()->getPointerElementType(); 293 if (AccessedAlign == 0) 294 AccessedAlign = DL.getABITypeAlignment(AccessedTy); 295 if (AccessedAlign < Align) 296 continue; 297 298 // Handle trivial cases. 299 if (AccessedPtr == V) 300 return true; 301 302 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) && 303 LoadSize <= DL.getTypeStoreSize(AccessedTy)) 304 return true; 305 } 306 return false; 307 } 308 309 /// DefMaxInstsToScan - the default number of maximum instructions 310 /// to scan in the block, used by FindAvailableLoadedValue(). 311 /// FindAvailableLoadedValue() was introduced in r60148, to improve jump 312 /// threading in part by eliminating partially redundant loads. 313 /// At that point, the value of MaxInstsToScan was already set to '6' 314 /// without documented explanation. 315 cl::opt<unsigned> 316 llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden, 317 cl::desc("Use this to specify the default maximum number of instructions " 318 "to scan backward from a given instruction, when searching for " 319 "available loaded value")); 320 321 Value *llvm::FindAvailableLoadedValue(LoadInst *Load, 322 BasicBlock *ScanBB, 323 BasicBlock::iterator &ScanFrom, 324 unsigned MaxInstsToScan, 325 AliasAnalysis *AA, bool *IsLoad, 326 unsigned *NumScanedInst) { 327 // Don't CSE load that is volatile or anything stronger than unordered. 328 if (!Load->isUnordered()) 329 return nullptr; 330 331 return FindAvailablePtrLoadStore( 332 Load->getPointerOperand(), Load->getType(), Load->isAtomic(), ScanBB, 333 ScanFrom, MaxInstsToScan, AA, IsLoad, NumScanedInst); 334 } 335 336 Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy, 337 bool AtLeastAtomic, BasicBlock *ScanBB, 338 BasicBlock::iterator &ScanFrom, 339 unsigned MaxInstsToScan, 340 AliasAnalysis *AA, bool *IsLoadCSE, 341 unsigned *NumScanedInst) { 342 if (MaxInstsToScan == 0) 343 MaxInstsToScan = ~0U; 344 345 const DataLayout &DL = ScanBB->getModule()->getDataLayout(); 346 347 // Try to get the store size for the type. 348 uint64_t AccessSize = DL.getTypeStoreSize(AccessTy); 349 350 Value *StrippedPtr = Ptr->stripPointerCasts(); 351 352 while (ScanFrom != ScanBB->begin()) { 353 // We must ignore debug info directives when counting (otherwise they 354 // would affect codegen). 355 Instruction *Inst = &*--ScanFrom; 356 if (isa<DbgInfoIntrinsic>(Inst)) 357 continue; 358 359 // Restore ScanFrom to expected value in case next test succeeds 360 ScanFrom++; 361 362 if (NumScanedInst) 363 ++(*NumScanedInst); 364 365 // Don't scan huge blocks. 366 if (MaxInstsToScan-- == 0) 367 return nullptr; 368 369 --ScanFrom; 370 // If this is a load of Ptr, the loaded value is available. 371 // (This is true even if the load is volatile or atomic, although 372 // those cases are unlikely.) 373 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 374 if (AreEquivalentAddressValues( 375 LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) && 376 CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) { 377 378 // We can value forward from an atomic to a non-atomic, but not the 379 // other way around. 380 if (LI->isAtomic() < AtLeastAtomic) 381 return nullptr; 382 383 if (IsLoadCSE) 384 *IsLoadCSE = true; 385 return LI; 386 } 387 388 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 389 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); 390 // If this is a store through Ptr, the value is available! 391 // (This is true even if the store is volatile or atomic, although 392 // those cases are unlikely.) 393 if (AreEquivalentAddressValues(StorePtr, StrippedPtr) && 394 CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(), 395 AccessTy, DL)) { 396 397 // We can value forward from an atomic to a non-atomic, but not the 398 // other way around. 399 if (SI->isAtomic() < AtLeastAtomic) 400 return nullptr; 401 402 if (IsLoadCSE) 403 *IsLoadCSE = false; 404 return SI->getOperand(0); 405 } 406 407 // If both StrippedPtr and StorePtr reach all the way to an alloca or 408 // global and they are different, ignore the store. This is a trivial form 409 // of alias analysis that is important for reg2mem'd code. 410 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) && 411 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) && 412 StrippedPtr != StorePtr) 413 continue; 414 415 // If we have alias analysis and it says the store won't modify the loaded 416 // value, ignore the store. 417 if (AA && !isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize))) 418 continue; 419 420 // Otherwise the store that may or may not alias the pointer, bail out. 421 ++ScanFrom; 422 return nullptr; 423 } 424 425 // If this is some other instruction that may clobber Ptr, bail out. 426 if (Inst->mayWriteToMemory()) { 427 // If alias analysis claims that it really won't modify the load, 428 // ignore it. 429 if (AA && !isModSet(AA->getModRefInfo(Inst, StrippedPtr, AccessSize))) 430 continue; 431 432 // May modify the pointer, bail out. 433 ++ScanFrom; 434 return nullptr; 435 } 436 } 437 438 // Got to the start of the block, we didn't find it, but are done for this 439 // block. 440 return nullptr; 441 } 442