From ed0d1bcf3093603937a15faecceca254f0adf470 Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Tue, 10 Sep 2019 21:33:53 +0000 Subject: [PATCH] [Loads] Move generic code out of vectorizer into a location it might be reused [NFC] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@371558 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Loads.h | 13 +++++ lib/Analysis/Loads.cpp | 50 ++++++++++++++++++ .../Vectorize/LoopVectorizationLegality.cpp | 51 ------------------- 3 files changed, 63 insertions(+), 51 deletions(-) diff --git a/include/llvm/Analysis/Loads.h b/include/llvm/Analysis/Loads.h index 5df6bb02308..b5884acf3b0 100644 --- a/include/llvm/Analysis/Loads.h +++ b/include/llvm/Analysis/Loads.h @@ -20,7 +20,9 @@ namespace llvm { class DataLayout; +class Loop; class MDNode; +class ScalarEvolution; /// Return true if this is always a dereferenceable pointer. If the context /// instruction is specified perform context-sensitive analysis and return true @@ -61,6 +63,17 @@ bool isSafeToLoadUnconditionally(Value *V, unsigned Align, APInt &Size, Instruction *ScanFrom = nullptr, const DominatorTree *DT = nullptr); +/// Return true if we can prove that the given load (which is assumed to be +/// within the specified loop) would access only dereferenceable memory, and +/// be properly aligned on every iteration of the specified loop regardless of +/// its placement within the loop. (i.e. does not require predication beyond +/// that required by the the header itself and could be hoisted into the header +/// if desired.) This is more powerful than the variants above when the +/// address loaded from is analyzeable by SCEV. +bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, + ScalarEvolution &SE, + DominatorTree &DT); + /// Return true if we know that executing a load from this value cannot trap. /// /// If DT and ScanFrom are specified this method performs context-sensitive diff --git a/lib/Analysis/Loads.cpp b/lib/Analysis/Loads.cpp index e74df9c69d7..ea98ca915c6 100644 --- a/lib/Analysis/Loads.cpp +++ b/lib/Analysis/Loads.cpp @@ -12,6 +12,9 @@ #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/GlobalAlias.h" @@ -190,6 +193,53 @@ static bool AreEquivalentAddressValues(const Value *A, const Value *B) { return false; } +bool llvm::isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, + ScalarEvolution &SE, + DominatorTree &DT) { + auto &DL = LI->getModule()->getDataLayout(); + Value *Ptr = LI->getPointerOperand(); + auto *AddRec = dyn_cast(SE.getSCEV(Ptr)); + if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine()) + return false; + auto* Step = dyn_cast(AddRec->getStepRecurrence(SE)); + if (!Step) + return false; + APInt StepC = Step->getAPInt(); + APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()), + DL.getTypeStoreSize(LI->getType())); + // TODO: generalize to access patterns which have gaps + // TODO: handle uniform addresses (if not already handled by LICM) + if (StepC != EltSize) + return false; + + // TODO: If the symbolic trip count has a small bound (max count), we might + // be able to prove safety. + auto TC = SE.getSmallConstantTripCount(L); + if (!TC) + return false; + + const APInt AccessSize = TC * EltSize; + + auto *StartS = dyn_cast(AddRec->getStart()); + if (!StartS) + return false; + assert(SE.isLoopInvariant(StartS, L) && "implied by addrec definition"); + Value *Base = StartS->getValue(); + + Instruction *HeaderFirstNonPHI = L->getHeader()->getFirstNonPHI(); + + unsigned Align = LI->getAlignment(); + if (Align == 0) + Align = DL.getABITypeAlignment(LI->getType()); + // For the moment, restrict ourselves to the case where the access size is a + // multiple of the requested alignment and the base is aligned. + // TODO: generalize if a case found which warrants + if (EltSize.urem(Align) != 0) + return false; + return isDereferenceableAndAlignedPointer(Base, Align, AccessSize, + DL, HeaderFirstNonPHI, &DT); +} + /// Check if executing a load of this pointer value cannot trap. /// /// If DT and ScanFrom are specified this method performs context-sensitive diff --git a/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp b/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp index 3b3e055f01c..61406c97fd0 100644 --- a/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp +++ b/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp @@ -918,57 +918,6 @@ bool LoopVectorizationLegality::blockCanBePredicated( return true; } -/// Return true if we can prove that the given load would access only -/// dereferenceable memory, and be properly aligned on every iteration. -/// (i.e. does not require predication beyond that required by the the header -/// itself) TODO: Move to Loads.h/cpp in a separate change -static bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, - ScalarEvolution &SE, - DominatorTree &DT) { - auto &DL = LI->getModule()->getDataLayout(); - Value *Ptr = LI->getPointerOperand(); - auto *AddRec = dyn_cast(SE.getSCEV(Ptr)); - if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine()) - return false; - auto* Step = dyn_cast(AddRec->getStepRecurrence(SE)); - if (!Step) - return false; - APInt StepC = Step->getAPInt(); - APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()), - DL.getTypeStoreSize(LI->getType())); - // TODO: generalize to access patterns which have gaps - // TODO: handle uniform addresses (if not already handled by LICM) - if (StepC != EltSize) - return false; - - // TODO: If the symbolic trip count has a small bound (max count), we might - // be able to prove safety. - auto TC = SE.getSmallConstantTripCount(L); - if (!TC) - return false; - - const APInt AccessSize = TC * EltSize; - - auto *StartS = dyn_cast(AddRec->getStart()); - if (!StartS) - return false; - assert(SE.isLoopInvariant(StartS, L) && "implied by addrec definition"); - Value *Base = StartS->getValue(); - - Instruction *HeaderFirstNonPHI = L->getHeader()->getFirstNonPHI(); - - unsigned Align = LI->getAlignment(); - if (Align == 0) - Align = DL.getABITypeAlignment(LI->getType()); - // For the moment, restrict ourselves to the case where the access size is a - // multiple of the requested alignment and the base is aligned. - // TODO: generalize if a case found which warrants - if (EltSize.urem(Align) != 0) - return false; - return isDereferenceableAndAlignedPointer(Base, Align, AccessSize, - DL, HeaderFirstNonPHI, &DT); -} - bool LoopVectorizationLegality::canVectorizeWithIfConvert() { if (!EnableIfConversion) { reportVectorizationFailure("If-conversion is disabled", -- 2.40.0