From 4343534a670f74e87841c0ca03d3189b72c04b1d Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Mon, 1 May 2023 10:16:32 -0700 Subject: [PATCH] [LAA] Rework overflow checking in getPtrStride [nfc] The previous code structure and comments were exceedingly confusing. I have multiple times looked at this code and suspected a bug. This time, I decided to take the time to reflow the code and comment out why it is correct. The only suspect (to me) case left is that an underaligned access with a unit stride (in terms of the access type) might miss the undefined null pointer when wrapping. This is unlikely to be an issue for C/C++ code with real page sizes, so I'm not bothering to fully convince myself whether that case is correct or not. --- llvm/include/llvm/Analysis/LoopAccessAnalysis.h | 4 ++ llvm/lib/Analysis/LoopAccessAnalysis.cpp | 84 +++++++++++-------------- 2 files changed, 39 insertions(+), 49 deletions(-) diff --git a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h index 7596193..fae22d4 100644 --- a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h @@ -730,6 +730,10 @@ const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, /// to \p PtrToStride and therefore add further predicates to \p PSE. /// The \p Assume parameter indicates if we are allowed to make additional /// run-time assumptions. +/// +/// Note that the analysis results are defined if-and-only-if the original +/// memory access was defined. If that access was dead, or UB, then the +/// result of this function is undefined. std::optional getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp index 2707d0e..c2cdd3c 100644 --- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -1312,20 +1312,18 @@ void AccessAnalysis::processMemAccesses() { } } -static bool isInBoundsGep(Value *Ptr) { - if (GetElementPtrInst *GEP = dyn_cast(Ptr)) - return GEP->isInBounds(); - return false; -} - /// Return true if an AddRec pointer \p Ptr is unsigned non-wrapping, /// i.e. monotonically increasing/decreasing. static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR, PredicatedScalarEvolution &PSE, const Loop *L) { + // FIXME: This should probably only return true for NUW. if (AR->getNoWrapFlags(SCEV::NoWrapMask)) return true; + if (PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW)) + return true; + // Scalar evolution does not propagate the non-wrapping flags to values that // are derived from a non-wrapping induction variable because non-wrapping // could be flow-sensitive. @@ -1400,35 +1398,6 @@ std::optional llvm::getPtrStride(PredicatedScalarEvolution &PSE, return std::nullopt; } - // The address calculation must not wrap. Otherwise, a dependence could be - // inverted. - // An inbounds getelementptr that is a AddRec with a unit stride - // cannot wrap per definition. The unit stride requirement is checked later. - // An getelementptr without an inbounds attribute and unit stride would have - // to access the pointer value "0" which is undefined behavior in address - // space 0, therefore we can also vectorize this case. - unsigned AddrSpace = Ty->getPointerAddressSpace(); - bool IsInBoundsGEP = isInBoundsGep(Ptr); - bool IsNoWrapAddRec = !ShouldCheckWrap || - PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) || - isNoWrapAddRec(Ptr, AR, PSE, Lp); - if (!IsNoWrapAddRec && !IsInBoundsGEP && - NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace)) { - if (!Assume) { - LLVM_DEBUG( - dbgs() << "LAA: Bad stride - Pointer may wrap in the address space " - << *Ptr << " SCEV: " << *AR << "\n"); - return std::nullopt; - } - - PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW); - IsNoWrapAddRec = true; - LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap in the address space:\n" - << "LAA: Pointer: " << *Ptr << "\n" - << "LAA: SCEV: " << *AR << "\n" - << "LAA: Added an overflow assumption\n"); - } - // Check the step is constant. const SCEV *Step = AR->getStepRecurrence(*PSE.getSE()); @@ -1457,25 +1426,42 @@ std::optional llvm::getPtrStride(PredicatedScalarEvolution &PSE, if (Rem) return std::nullopt; - // If the SCEV could wrap but we have an inbounds gep with a unit stride we - // know we can't "wrap around the address space". In case of address space - // zero we know that this won't happen without triggering undefined behavior. - if (!IsNoWrapAddRec && Stride != 1 && Stride != -1 && - (IsInBoundsGEP || !NullPointerIsDefined(Lp->getHeader()->getParent(), - AddrSpace))) { - if (!Assume) - return std::nullopt; + if (!ShouldCheckWrap) + return Stride; + + // The address calculation must not wrap. Otherwise, a dependence could be + // inverted. + if (isNoWrapAddRec(Ptr, AR, PSE, Lp)) + return Stride; + + // An inbounds getelementptr that is a AddRec with a unit stride + // cannot wrap per definition. If it did, the result would be poison + // and any memory access dependent on it would be immediate UB + // when executed. + if (auto *GEP = dyn_cast(Ptr); + GEP && GEP->isInBounds() && (Stride == 1 || Stride == -1)) + return Stride; + + // If the null pointer is undefined, then a access sequence which would + // otherwise access it can be assumed not to unsigned wrap. Note that this + // assumes the object in memory is aligned to the natural alignment. + unsigned AddrSpace = Ty->getPointerAddressSpace(); + if (!NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace) && + (Stride == 1 || Stride == -1)) + return Stride; - // We can avoid this case by adding a run-time check. - LLVM_DEBUG(dbgs() << "LAA: Non unit strided pointer which is not either " - << "inbounds or in address space 0 may wrap:\n" + if (Assume) { + PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW); + LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap:\n" << "LAA: Pointer: " << *Ptr << "\n" << "LAA: SCEV: " << *AR << "\n" << "LAA: Added an overflow assumption\n"); - PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW); + return Stride; } - - return Stride; + LLVM_DEBUG( + dbgs() << "LAA: Bad stride - Pointer may wrap in the address space " + << *Ptr << " SCEV: " << *AR << "\n"); + return std::nullopt; } std::optional llvm::getPointersDiff(Type *ElemTyA, Value *PtrA, -- 2.7.4