1dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman//===- Loads.cpp - Local load analysis ------------------------------------===// 2dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// 3dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// The LLVM Compiler Infrastructure 4dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// 5dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// This file is distributed under the University of Illinois Open Source 6dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// License. See LICENSE.TXT for details. 7dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// 8dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman//===----------------------------------------------------------------------===// 9dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// 10dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// This file defines simple local analyses for load instructions. 11dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman// 12dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman//===----------------------------------------------------------------------===// 13dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 14dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman#include "llvm/Analysis/Loads.h" 15dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 161ef05b1a2a8eb8b9f0f5b7b04df9856f43de5855Nuno Lopes#include "llvm/Analysis/ValueTracking.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalAlias.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Module.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 24de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Statepoint.h" 25de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 26dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohmanusing namespace llvm; 27dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 28de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool isAligned(const Value *Base, const APInt &Offset, unsigned Align, 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DataLayout &DL) { 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt BaseAlign(Offset.getBitWidth(), Base->getPointerAlignment(DL)); 31de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 32de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!BaseAlign) { 33de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *Ty = Base->getType()->getPointerElementType(); 34de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Ty->isSized()) 35de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 36de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BaseAlign = DL.getABITypeAlignment(Ty); 37de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 38de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt Alignment(Offset.getBitWidth(), Align); 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(Alignment.isPowerOf2() && "must be a power of 2!"); 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1)); 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) { 46de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *Ty = Base->getType(); 47de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(Ty->isSized() && "must be sized"); 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0); 49de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isAligned(Base, Offset, Align, DL); 50de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 52de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Test if V is always a pointer to allocated and suitably aligned memory for 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// a simple load or store. 54de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool isDereferenceableAndAlignedPointer( 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Value *V, unsigned Align, const APInt &Size, const DataLayout &DL, 56de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Instruction *CtxI, const DominatorTree *DT, 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSetImpl<const Value *> &Visited) { 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Note that it is not safe to speculate into a malloc'd region because 59de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // malloc may return null. 60de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 61de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // bitcast instructions are no-ops as far as dereferenceability is concerned. 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) 63de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size, 64de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL, CtxI, DT, Visited); 65de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool CheckForNonNull = false; 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt KnownDerefBytes(Size.getBitWidth(), 68de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar V->getPointerDereferenceableBytes(DL, CheckForNonNull)); 69de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (KnownDerefBytes.getBoolValue()) { 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (KnownDerefBytes.uge(Size)) 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!CheckForNonNull || isKnownNonNullAt(V, CtxI, DT)) 72de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isAligned(V, Align, DL); 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 75de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // For GEPs, determine if the indexing lands within the allocated object. 76de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Value *Base = GEP->getPointerOperand(); 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt Offset(DL.getPointerTypeSizeInBits(GEP->getType()), 0); 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() || 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar !Offset.urem(APInt(Offset.getBitWidth(), Align)).isMinValue()) 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 83de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If the base pointer is dereferenceable for Offset+Size bytes, then the 85de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base 86de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // pointer is aligned to Align bytes, and the Offset is divisible by Align 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // aligned to Align bytes. 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Visited.insert(Base).second && 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar isDereferenceableAndAlignedPointer(Base, Align, Offset + Size, DL, 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CtxI, DT, Visited); 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // For gc.relocate, look through relocations 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V)) 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isDereferenceableAndAlignedPointer( 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited); 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V)) 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size, 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL, CtxI, DT, Visited); 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 104de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (auto CS = ImmutableCallSite(V)) 105de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (const Value *RV = CS.getReturnedArgOperand()) 106de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isDereferenceableAndAlignedPointer(RV, Align, Size, DL, CtxI, DT, 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Visited); 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If we don't know, assume the worst. 110de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 111de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align, 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DataLayout &DL, 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Instruction *CtxI, 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DominatorTree *DT) { 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // When dereferenceability information is provided by a dereferenceable 118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // attribute, we know exactly how many bytes are dereferenceable. If we can 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // determine the exact offset to the attributed variable, we can use that 120de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // information here. 121de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *VTy = V->getType(); 122de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *Ty = VTy->getPointerElementType(); 123de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 124de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Require ABI alignment for loads without alignment specification 125de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Align == 0) 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Align = DL.getABITypeAlignment(Ty); 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Ty->isSized()) 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSet<const Value *, 32> Visited; 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return ::isDereferenceableAndAlignedPointer( 133de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar V, Align, APInt(DL.getTypeSizeInBits(VTy), DL.getTypeStoreSize(Ty)), DL, 134de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CtxI, DT, Visited); 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 137de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL, 138de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Instruction *CtxI, 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DominatorTree *DT) { 140de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT); 141de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 142de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 14337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \brief Test if A and B will obviously have the same value. 14437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// 14537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// This includes recognizing that %t0 and %t1 will have the same 146dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman/// value in code like this: 14737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \code 148dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman/// %t0 = getelementptr \@a, 0, 3 149dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman/// store i32 0, i32* %t0 150dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman/// %t1 = getelementptr \@a, 0, 3 151dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman/// %t2 = load i32* %t1 15237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \endcode 153dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman/// 154dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohmanstatic bool AreEquivalentAddressValues(const Value *A, const Value *B) { 155dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Test if the values are trivially equivalent. 15637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (A == B) 15737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 15868df608fd1eeb7f7fb6f7de49ff8cd6382654f79Hans Wennborg 159dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Test if the values come from identical arithmetic instructions. 160dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Use isIdenticalToWhenDefined instead of isIdenticalTo because 161dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // this function is only used when one address use dominates the 162dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // other, which means that they'll always either have the same 163dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // value or one of them will have an undefined value. 16437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) || 16537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines isa<GetElementPtrInst>(A)) 166dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (const Instruction *BI = dyn_cast<Instruction>(B)) 167dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) 168dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return true; 16968df608fd1eeb7f7fb6f7de49ff8cd6382654f79Hans Wennborg 170dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Otherwise they may not be equivalent. 171dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return false; 172dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman} 173dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 17437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \brief Check if executing a load of this pointer value cannot trap. 17537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// 176de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// If DT and ScanFrom are specified this method performs context-sensitive 177de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// analysis and returns true if it is safe to load immediately before ScanFrom. 178de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// 17937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// If it is not obviously safe to load from the specified pointer, we do 18037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// a quick local scan of the basic block containing \c ScanFrom, to determine 18137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// if the address is already accessed. 18237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// 18337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// This uses the pointee type to determine how many bytes need to be safe to 18437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// load from the pointer. 185de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align, 186de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DataLayout &DL, 187de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *ScanFrom, 188de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DominatorTree *DT) { 189f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Zero alignment means that the load has the ABI alignment for the target 190f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Align == 0) 191f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Align = DL.getABITypeAlignment(V->getType()->getPointerElementType()); 192f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(isPowerOf2_32(Align)); 193f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 194de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If DT is not specified we can't make context-sensitive query 195de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Instruction* CtxI = DT ? ScanFrom : nullptr; 196de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT)) 197de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 198de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1991ef05b1a2a8eb8b9f0f5b7b04df9856f43de5855Nuno Lopes int64_t ByteOffset = 0; 200dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman Value *Base = V; 20137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL); 2021ef05b1a2a8eb8b9f0f5b7b04df9856f43de5855Nuno Lopes 2031ef05b1a2a8eb8b9f0f5b7b04df9856f43de5855Nuno Lopes if (ByteOffset < 0) // out of bounds 2041ef05b1a2a8eb8b9f0f5b7b04df9856f43de5855Nuno Lopes return false; 205dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Type *BaseType = nullptr; 207dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman unsigned BaseAlign = 0; 208dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 209dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // An alloca is safe to load from as load as it is suitably aligned. 210dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman BaseType = AI->getAllocatedType(); 211dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman BaseAlign = AI->getAlignment(); 2121ef05b1a2a8eb8b9f0f5b7b04df9856f43de5855Nuno Lopes } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 21337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Global variables are not necessarily safe to load from if they are 214de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // interposed arbitrarily. Their size may change or they may be weak and 215de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // require a test to determine if they were in fact provided. 216de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!GV->isInterposable()) { 217dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman BaseType = GV->getType()->getElementType(); 218dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman BaseAlign = GV->getAlignment(); 219dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 220dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 221dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 22237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PointerType *AddrTy = cast<PointerType>(V->getType()); 2234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType()); 224dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 22537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // If we found a base allocated type from either an alloca or global variable, 22637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // try to see if we are definitively within the allocated region. We need to 22737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // know the size of the base type and the loaded type to do anything in this 2284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // case. 2294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (BaseType && BaseType->isSized()) { 23037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (BaseAlign == 0) 2314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar BaseAlign = DL.getPrefTypeAlignment(BaseType); 232dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 23337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Align <= BaseAlign) { 234dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Check if the load is within the bounds of the underlying object. 2354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) && 236f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ((ByteOffset % Align) == 0)) 237dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return true; 238dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 239dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 240dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 241de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!ScanFrom) 242de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 243de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 244dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Otherwise, be a little bit aggressive by scanning the local block where we 245dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // want to check to see if the pointer is already being loaded or stored 246dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // from/to. If so, the previous load or store would have already trapped, 247dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // so there is no harm doing an extra load (also, CSE will later eliminate 248dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // the load entirely). 249f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BasicBlock::iterator BBI = ScanFrom->getIterator(), 250f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar E = ScanFrom->getParent()->begin(); 251dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 25237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // We can at least always strip pointer casts even though we can't use the 25337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // base here. 25437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines V = V->stripPointerCasts(); 25537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 256dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman while (BBI != E) { 257dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman --BBI; 258dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 259dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // If we see a free or a call which may write to memory (i.e. which might do 260dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // a free) the pointer could be marked invalid. 261dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 262dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman !isa<DbgInfoIntrinsic>(BBI)) 263dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return false; 264dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 26537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *AccessedPtr; 266f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned AccessedAlign; 267f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 26837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AccessedPtr = LI->getPointerOperand(); 269f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AccessedAlign = LI->getAlignment(); 270f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 27137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AccessedPtr = SI->getPointerOperand(); 272f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AccessedAlign = SI->getAlignment(); 273f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } else 274f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar continue; 275f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 276f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Type *AccessedTy = AccessedPtr->getType()->getPointerElementType(); 277f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AccessedAlign == 0) 278f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AccessedAlign = DL.getABITypeAlignment(AccessedTy); 279f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AccessedAlign < Align) 28037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines continue; 28137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Handle trivial cases. 28337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AccessedPtr == V) 28437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 28537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 28637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) && 287f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LoadSize <= DL.getTypeStoreSize(AccessedTy)) 28837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 289dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 290dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return false; 291dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman} 292dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 293f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// DefMaxInstsToScan - the default number of maximum instructions 294f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// to scan in the block, used by FindAvailableLoadedValue(). 295f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// FindAvailableLoadedValue() was introduced in r60148, to improve jump 296f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// threading in part by eliminating partially redundant loads. 297f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// At that point, the value of MaxInstsToScan was already set to '6' 298f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// without documented explanation. 299f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarcl::opt<unsigned> 300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarllvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden, 301f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar cl::desc("Use this to specify the default maximum number of instructions " 302f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "to scan backward from a given instruction, when searching for " 303f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "available loaded value")); 304f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 305de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarValue *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, 306dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman BasicBlock::iterator &ScanFrom, 307dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman unsigned MaxInstsToScan, 308de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AliasAnalysis *AA, AAMDNodes *AATags, 309de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool *IsLoadCSE) { 31037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (MaxInstsToScan == 0) 31137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MaxInstsToScan = ~0U; 31237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 313de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Ptr = Load->getPointerOperand(); 314de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *AccessTy = Load->getType(); 315de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 316de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We can never remove a volatile load 317de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Load->isVolatile()) 318de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return nullptr; 319de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 320de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Anything stronger than unordered is currently unimplemented. 321de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Load->isUnordered()) 322de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return nullptr; 323dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 3244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const DataLayout &DL = ScanBB->getModule()->getDataLayout(); 325ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 326ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Try to get the store size for the type. 3274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar uint64_t AccessSize = DL.getTypeStoreSize(AccessTy); 32837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 32937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *StrippedPtr = Ptr->stripPointerCasts(); 33037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 331dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman while (ScanFrom != ScanBB->begin()) { 332dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // We must ignore debug info directives when counting (otherwise they 333dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // would affect codegen). 334f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Instruction *Inst = &*--ScanFrom; 335dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (isa<DbgInfoIntrinsic>(Inst)) 336dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman continue; 337dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman 338dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Restore ScanFrom to expected value in case next test succeeds 339dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman ScanFrom++; 34037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 341dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Don't scan huge blocks. 34237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (MaxInstsToScan-- == 0) 34337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 34437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 345dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman --ScanFrom; 346dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // If this is a load of Ptr, the loaded value is available. 347c869b4397aa7c45bfcd71951a1f15e6e7228be79Eli Friedman // (This is true even if the load is volatile or atomic, although 348c869b4397aa7c45bfcd71951a1f15e6e7228be79Eli Friedman // those cases are unlikely.) 349dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 35037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AreEquivalentAddressValues( 35137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) && 352ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) { 353de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 354de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We can value forward from an atomic to a non-atomic, but not the 355de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // other way around. 356de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LI->isAtomic() < Load->isAtomic()) 357de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return nullptr; 358de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 35937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AATags) 36037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LI->getAAMetadata(*AATags); 361de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (IsLoadCSE) 362de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar *IsLoadCSE = true; 363dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return LI; 3645161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner } 36537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 366dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 36737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); 368dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // If this is a store through Ptr, the value is available! 369c869b4397aa7c45bfcd71951a1f15e6e7228be79Eli Friedman // (This is true even if the store is volatile or atomic, although 370c869b4397aa7c45bfcd71951a1f15e6e7228be79Eli Friedman // those cases are unlikely.) 37137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AreEquivalentAddressValues(StorePtr, StrippedPtr) && 372ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(), 373ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AccessTy, DL)) { 374de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 375de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We can value forward from an atomic to a non-atomic, but not the 376de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // other way around. 377de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SI->isAtomic() < Load->isAtomic()) 378de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return nullptr; 379de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 38037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AATags) 38137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI->getAAMetadata(*AATags); 382dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman return SI->getOperand(0); 3835161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner } 38437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // If both StrippedPtr and StorePtr reach all the way to an alloca or 38637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // global and they are different, ignore the store. This is a trivial form 38737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // of alias analysis that is important for reg2mem'd code. 38837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) && 38937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) && 39037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines StrippedPtr != StorePtr) 391dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman continue; 39237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 393dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // If we have alias analysis and it says the store won't modify the loaded 394dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // value, ignore the store. 395f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AA && (AA->getModRefInfo(SI, StrippedPtr, AccessSize) & MRI_Mod) == 0) 396dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman continue; 39737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 398dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Otherwise the store that may or may not alias the pointer, bail out. 399dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman ++ScanFrom; 400dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 401dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 40237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 403dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // If this is some other instruction that may clobber Ptr, bail out. 404dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (Inst->mayWriteToMemory()) { 405dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // If alias analysis claims that it really won't modify the load, 406dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // ignore it. 407dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman if (AA && 408f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar (AA->getModRefInfo(Inst, StrippedPtr, AccessSize) & MRI_Mod) == 0) 409dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman continue; 41037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 411dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // May modify the pointer, bail out. 412dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman ++ScanFrom; 413dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 414dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 415dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman } 41637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 417dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // Got to the start of the block, we didn't find it, but are done for this 418dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman // block. 419dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 420dd9344f3face8f1978a7f9f393c31b628144d1f6Dan Gohman} 421