Index: llvm/include/llvm/Analysis/LoopAccessAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/LoopAccessAnalysis.h +++ llvm/include/llvm/Analysis/LoopAccessAnalysis.h @@ -48,6 +48,13 @@ /// \When performing memory disambiguation checks at runtime do not /// make more than this number of comparisons. static unsigned RuntimeMemoryCheckThreshold; + + // When creating runtime checks for nested loops, where possible try to + // write the checks in a form that allows them to be easily hoisted out of + // the outermost loop. For example, we can do this by expanding the range of + // addresses considered to include the entire nested loop so that they are + // loop invariant. + static bool HoistRuntimeChecks; }; /// Checks memory dependences among accesses to the same underlying Index: llvm/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -524,7 +524,7 @@ Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl &PointerChecks, - SCEVExpander &Expander); + SCEVExpander &Expander, bool HoistRuntimeChecks = false); Value *addDiffRuntimeChecks( Instruction *Loc, ArrayRef Checks, SCEVExpander &Expander, Index: llvm/lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -142,6 +142,13 @@ cl::desc("Speculate that non-constant strides are unit in LAA"), cl::init(true)); +static cl::opt HoistRuntimeChecks( + "hoist-runtime-checks", cl::Hidden, + cl::desc( + "Hoist inner loop runtime memory checks to outer loop if possible"), + cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(false)); +bool VectorizerParams::HoistRuntimeChecks; + bool VectorizerParams::isInterleaveForced() { return ::VectorizationInterleave.getNumOccurrences() > 0; } @@ -331,6 +338,29 @@ CanUseDiffCheck = false; return; } + + const Loop *InnerLoop = SrcAR->getLoop(); + // If the start values for both Src and Sink also vary according to an outer + // loop, then it's probably better to avoid creating diff checks because + // they may not be hoisted. We should instead let llvm::addRuntimeChecks + // do the expanded full range overlap checks, which can be hoisted. + if (HoistRuntimeChecks && InnerLoop->getParentLoop() && + isa(SinkStartInt) && isa(SrcStartInt)) { + auto *SrcStartAR = cast(SrcStartInt); + auto *SinkStartAR = cast(SinkStartInt); + const Loop *StartARLoop = SrcStartAR->getLoop(); + if (StartARLoop == SinkStartAR->getLoop() && + StartARLoop == InnerLoop->getParentLoop()) { + LLVM_DEBUG(dbgs() << "LAA: Not creating diff runtime check, since these " + "cannot be hoisted out of the outer loop\n"); + CanUseDiffCheck = false; + return; + } + } + + LLVM_DEBUG(dbgs() << "LAA: Creating diff runtime check for:\n" + << "SrcStart: " << *SrcStartInt << '\n' + << "SinkStartInt: " << *SinkStartInt << '\n'); DiffChecks.emplace_back(SrcStartInt, SinkStartInt, AllocSize, Src->NeedsFreeze || Sink->NeedsFreeze); } Index: llvm/lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/LoopUtils.cpp +++ llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1632,42 +1632,92 @@ struct PointerBounds { TrackingVH Start; TrackingVH End; + Value *StrideToCheck; }; /// Expand code for the lower and upper bound of the pointer group \p CG /// in \p TheLoop. \return the values for the bounds. static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, Loop *TheLoop, Instruction *Loc, - SCEVExpander &Exp) { + SCEVExpander &Exp, bool HoistRuntimeChecks) { LLVMContext &Ctx = Loc->getContext(); Type *PtrArithTy = Type::getInt8PtrTy(Ctx, CG->AddressSpace); Value *Start = nullptr, *End = nullptr; LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n"); - Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc); - End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc); + const SCEV *Low = CG->Low, *High = CG->High, *Stride = nullptr; + + // If the Low and High values are themselves loop-variant, then we may want + // to expand the range to include those covered by the outer loop as well. + // There is a trade-off here with the advantage being that creating checks + // using the expanded range permits the runtime memory checks to be hoisted + // out of the outer loop. This reduces the cost of entering the inner loop, + // which can be significant for low trip counts. The disadvantage is that + // there is a chance we may now never enter the vectorized inner loop, + // whereas using a restricted range check could have allowed us to enter at + // least once. This is why the behaviour is not currently the default and is + // controlled by the parameter 'HoistRuntimeChecks'. + if (HoistRuntimeChecks && TheLoop->getParentLoop() && + isa(High) && isa(Low)) { + auto *HighAR = cast(High); + auto *LowAR = cast(Low); + const Loop *OuterLoop = TheLoop->getParentLoop(); + const SCEV *Recur = LowAR->getStepRecurrence(*Exp.getSE()); + if (Recur == HighAR->getStepRecurrence(*Exp.getSE()) && + HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) { + BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); + const SCEV *OuterExitCount = + Exp.getSE()->getExitCount(OuterLoop, OuterLoopLatch); + if (!isa(OuterExitCount) && + OuterExitCount->getType()->isIntegerTy()) { + const SCEV *NewHigh = cast(High)->evaluateAtIteration( + OuterExitCount, *Exp.getSE()); + if (!isa(NewHigh)) { + LLVM_DEBUG(dbgs() << "LAA: Expanded RT check for range to include " + "outer loop in order to permit hoisting\n"); + High = NewHigh; + Low = cast(Low)->getStart(); + // If there is a possibility that the stride is negative then we have + // to generate extra checks to ensure the stride is positive. + if (!Exp.getSE()->isKnownNonNegative(Recur)) { + Stride = Recur; + LLVM_DEBUG(dbgs() << "LAA: ... but need to check stride is " + "positive: " + << *Stride << '\n'); + } + } + } + } + } + + Start = Exp.expandCodeFor(Low, PtrArithTy, Loc); + End = Exp.expandCodeFor(High, PtrArithTy, Loc); if (CG->NeedsFreeze) { IRBuilder<> Builder(Loc); Start = Builder.CreateFreeze(Start, Start->getName() + ".fr"); End = Builder.CreateFreeze(End, End->getName() + ".fr"); } - LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High << "\n"); - return {Start, End}; + Value *StrideVal = + Stride ? Exp.expandCodeFor(Stride, Type::getInt64Ty(Ctx), Loc) : nullptr; + LLVM_DEBUG(dbgs() << "Start: " << *Low << " End: " << *High << "\n"); + return {Start, End, StrideVal}; } /// Turns a collection of checks into a collection of expanded upper and /// lower bounds for both pointers in the check. static SmallVector, 4> expandBounds(const SmallVectorImpl &PointerChecks, Loop *L, - Instruction *Loc, SCEVExpander &Exp) { + Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks) { SmallVector, 4> ChecksWithBounds; // Here we're relying on the SCEV Expander's cache to only emit code for the // same bounds once. transform(PointerChecks, std::back_inserter(ChecksWithBounds), [&](const RuntimePointerCheck &Check) { - PointerBounds First = expandBounds(Check.first, L, Loc, Exp), - Second = expandBounds(Check.second, L, Loc, Exp); + PointerBounds First = expandBounds(Check.first, L, Loc, Exp, + HoistRuntimeChecks), + Second = expandBounds(Check.second, L, Loc, Exp, + HoistRuntimeChecks); return std::make_pair(First, Second); }); @@ -1677,10 +1727,11 @@ Value *llvm::addRuntimeChecks( Instruction *Loc, Loop *TheLoop, const SmallVectorImpl &PointerChecks, - SCEVExpander &Exp) { + SCEVExpander &Exp, bool HoistRuntimeChecks) { // TODO: Move noalias annotation code from LoopVersioning here and share with LV if possible. // TODO: Pass RtPtrChecking instead of PointerChecks and SE separately, if possible - auto ExpandedChecks = expandBounds(PointerChecks, TheLoop, Loc, Exp); + auto ExpandedChecks = + expandBounds(PointerChecks, TheLoop, Loc, Exp, HoistRuntimeChecks); LLVMContext &Ctx = Loc->getContext(); IRBuilder ChkBuilder(Ctx, @@ -1719,6 +1770,16 @@ Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0"); Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1"); Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict"); + if (A.StrideToCheck) { + Value *IsPositiveStride = ChkBuilder.CreateICmpSLT( + A.StrideToCheck, ConstantInt::get(A.StrideToCheck->getType(), 0)); + IsConflict = ChkBuilder.CreateOr(IsConflict, IsPositiveStride); + } + if (B.StrideToCheck) { + Value *IsPositiveStride = ChkBuilder.CreateICmpSLT( + B.StrideToCheck, ConstantInt::get(B.StrideToCheck->getType(), 0)); + IsConflict = ChkBuilder.CreateOr(IsConflict, IsPositiveStride); + } if (MemoryRuntimeCheck) { IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx"); Index: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1990,9 +1990,9 @@ }, IC); } else { - MemRuntimeCheckCond = - addRuntimeChecks(MemCheckBlock->getTerminator(), L, - RtPtrChecking.getChecks(), MemCheckExp); + MemRuntimeCheckCond = addRuntimeChecks( + MemCheckBlock->getTerminator(), L, RtPtrChecking.getChecks(), + MemCheckExp, VectorizerParams::HoistRuntimeChecks); } assert(MemRuntimeCheckCond && "no RT checks generated although RtPtrChecking " Index: llvm/test/Transforms/LoopVectorize/runtime-checks-hoist.ll =================================================================== --- llvm/test/Transforms/LoopVectorize/runtime-checks-hoist.ll +++ llvm/test/Transforms/LoopVectorize/runtime-checks-hoist.ll @@ -1,6 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2 ; REQUIRES: asserts -; RUN: opt < %s -p 'loop-vectorize' -force-vector-interleave=1 -S \ +; RUN: opt < %s -hoist-runtime-checks -p 'loop-vectorize' -force-vector-interleave=1 -S \ ; RUN: -force-vector-width=4 -debug-only=loop-accesses,loop-vectorize,loop-utils 2> %t | FileCheck %s ; RUN: cat %t | FileCheck %s --check-prefix=DEBUG @@ -17,54 +17,66 @@ ; '(i * (n + 1))' vs '(i * n)'. ; DEBUG-LABEL: LAA: Found a loop in diff_checks: -; DEBUG-NOT: LAA: Adding RT check for range: +; DEBUG: LAA: Not creating diff runtime check, since these cannot be hoisted out of the outer loop +; DEBUG: LAA: Adding RT check for range: +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 (1 + %n) to i64)) +; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %n to i64)) + (4 * (sext i32 (1 + %n) to i64) * (-1 + (zext i32 %m to i64))) + %dst) +; DEBUG-NEXT: LAA: Adding RT check for range: +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src) -define void @diff_checks(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) #0 { +define void @diff_checks(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) { ; CHECK-LABEL: define void @diff_checks ; CHECK-SAME: (ptr nocapture noundef writeonly [[DST:%.*]], ptr nocapture noundef readonly [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) { ; CHECK-NEXT: entry: -; CHECK-NEXT: [[SRC2:%.*]] = ptrtoint ptr [[SRC]] to i64 -; CHECK-NEXT: [[DST1:%.*]] = ptrtoint ptr [[DST]] to i64 ; CHECK-NEXT: [[ADD5:%.*]] = add nuw i32 [[N]], 1 ; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64 ; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[ADD5]] to i64 ; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64 ; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64 -; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2 -; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[WIDE_N]], 2 +; CHECK-NEXT: [[TMP2:%.*]] = add nsw i64 [[WIDE_M]], -1 +; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], [[TMP1]] +; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 2 +; CHECK-NEXT: [[TMP5:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2 +; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP4]], [[TMP5]] +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP6]] +; CHECK-NEXT: [[TMP7:%.*]] = shl nsw i64 [[TMP1]], 2 +; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]] +; CHECK-NEXT: [[TMP9:%.*]] = shl i64 [[TMP8]], 2 +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP9]] ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[INNER_EXIT:%.*]] ] -; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP2]], [[IV_OUTER]] -; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[DST1]], [[TMP4]] -; CHECK-NEXT: [[TMP6:%.*]] = mul i64 [[TMP3]], [[IV_OUTER]] -; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[SRC2]], [[TMP6]] -; CHECK-NEXT: [[TMP8:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]] -; CHECK-NEXT: [[TMP9:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP1]] +; CHECK-NEXT: [[TMP10:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]] +; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP1]] ; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: -; CHECK-NEXT: [[TMP10:%.*]] = sub i64 [[TMP5]], [[TMP7]] -; CHECK-NEXT: [[DIFF_CHECK:%.*]] = icmp ult i64 [[TMP10]], 16 -; CHECK-NEXT: br i1 [[DIFF_CHECK]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] +; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]] +; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] +; CHECK-NEXT: [[TMP12:%.*]] = icmp slt i64 [[TMP7]], 0 +; CHECK-NEXT: [[TMP13:%.*]] = or i1 [[FOUND_CONFLICT]], [[TMP12]] +; CHECK-NEXT: br i1 [[TMP13]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: ; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_N]], 4 ; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]] ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK: vector.body: ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] -; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP12:%.*]] = add nuw nsw i64 [[TMP11]], [[TMP8]] -; CHECK-NEXT: [[TMP13:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP12]] -; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[TMP13]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP14]], align 4 -; CHECK-NEXT: [[TMP15:%.*]] = add nsw i64 [[TMP11]], [[TMP9]] -; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP15]] +; CHECK-NEXT: [[TMP14:%.*]] = add i64 [[INDEX]], 0 +; CHECK-NEXT: [[TMP15:%.*]] = add nuw nsw i64 [[TMP14]], [[TMP10]] +; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]] ; CHECK-NEXT: [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[TMP16]], i32 0 -; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP17]], align 4 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP17]], align 4, !alias.scope !0 +; CHECK-NEXT: [[TMP18:%.*]] = add nsw i64 [[TMP14]], [[TMP11]] +; CHECK-NEXT: [[TMP19:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP18]] +; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[TMP19]], i32 0 +; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP20]], align 4, !alias.scope !3, !noalias !0 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 -; CHECK-NEXT: [[TMP18:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP18]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]] +; CHECK-NEXT: [[TMP21:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] +; CHECK-NEXT: br i1 [[TMP21]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]] @@ -73,15 +85,15 @@ ; CHECK-NEXT: br label [[INNER_LOOP:%.*]] ; CHECK: inner.loop: ; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ] -; CHECK-NEXT: [[TMP19:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP8]] -; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]] -; CHECK-NEXT: [[TMP20:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 -; CHECK-NEXT: [[TMP21:%.*]] = add nsw i64 [[IV_INNER]], [[TMP9]] -; CHECK-NEXT: [[ARRAYIDX9_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP21]] -; CHECK-NEXT: store i32 [[TMP20]], ptr [[ARRAYIDX9_US]], align 4 +; CHECK-NEXT: [[TMP22:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP10]] +; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP22]] +; CHECK-NEXT: [[TMP23:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 +; CHECK-NEXT: [[TMP24:%.*]] = add nsw i64 [[IV_INNER]], [[TMP11]] +; CHECK-NEXT: [[ARRAYIDX9_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP24]] +; CHECK-NEXT: store i32 [[TMP23]], ptr [[ARRAYIDX9_US]], align 4 ; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1 ; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]] -; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP3:![0-9]+]] +; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP8:![0-9]+]] ; CHECK: inner.exit: ; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1 ; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]] @@ -137,35 +149,34 @@ ; the additional load of 'dst[(i * n) + j]' in the loop. ; DEBUG-LABEL: LAA: Found a loop in full_checks: +; DEBUG-NOT: LAA: Creating diff runtime check for: ; DEBUG: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%dst,+,(4 * (zext i32 %n to i64))}<%outer.loop> End: {((4 * (zext i32 %n to i64)) + %dst),+,(4 * (zext i32 %n to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %dst) ; DEBUG-NEXT: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%src,+,(4 * (zext i32 %n to i64))}<%outer.loop> End: {((4 * (zext i32 %n to i64)) + %src),+,(4 * (zext i32 %n to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src) -define void @full_checks(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) #0 { +define void @full_checks(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) { ; CHECK-LABEL: define void @full_checks ; CHECK-SAME: (ptr nocapture noundef [[DST:%.*]], ptr nocapture noundef readonly [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) { ; CHECK-NEXT: entry: ; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64 ; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64 ; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64 -; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[WIDE_N]], 2 -; CHECK-NEXT: [[TMP2:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2 +; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]] +; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2 +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP2]] +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP2]] ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_EXIT:%.*]] ] -; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP1]], [[OUTER_IV]] -; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP3]] -; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP2]], [[TMP3]] -; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]] -; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP3]] -; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP4]] -; CHECK-NEXT: [[TMP5:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]] +; CHECK-NEXT: [[TMP3:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]] ; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: -; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]] -; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]] ; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] ; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: @@ -174,19 +185,19 @@ ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK: vector.body: ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] -; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP7:%.*]] = add nuw nsw i64 [[TMP6]], [[TMP5]] -; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP7]] +; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[INDEX]], 0 +; CHECK-NEXT: [[TMP5:%.*]] = add nuw nsw i64 [[TMP4]], [[TMP3]] +; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP5]] +; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[TMP6]], i32 0 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP7]], align 4, !alias.scope !9 +; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP5]] ; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[TMP8]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope !4 -; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP7]] -; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i32, ptr [[TMP10]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP11]], align 4, !alias.scope !7, !noalias !4 -; CHECK-NEXT: [[TMP12:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]] -; CHECK-NEXT: store <4 x i32> [[TMP12]], ptr [[TMP11]], align 4, !alias.scope !7, !noalias !4 +; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope !12, !noalias !9 +; CHECK-NEXT: [[TMP10:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]] +; CHECK-NEXT: store <4 x i32> [[TMP10]], ptr [[TMP9]], align 4, !alias.scope !12, !noalias !9 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 -; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP13]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP9:![0-9]+]] +; CHECK-NEXT: [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] +; CHECK-NEXT: br i1 [[TMP11]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP14:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]] @@ -195,16 +206,16 @@ ; CHECK-NEXT: br label [[INNER_LOOP:%.*]] ; CHECK: inner.loop: ; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ] -; CHECK-NEXT: [[TMP14:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP5]] -; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP14]] -; CHECK-NEXT: [[TMP15:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 -; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP14]] -; CHECK-NEXT: [[TMP16:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4 -; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP16]], [[TMP15]] +; CHECK-NEXT: [[TMP12:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP3]] +; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP12]] +; CHECK-NEXT: [[TMP13:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 +; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP12]] +; CHECK-NEXT: [[TMP14:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4 +; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP14]], [[TMP13]] ; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4 ; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1 ; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]] -; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP10:![0-9]+]] +; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP15:![0-9]+]] ; CHECK: inner.exit: ; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1 ; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_M]] @@ -261,32 +272,32 @@ ; runtime checks will vary for each outer loop iteration. ; DEBUG-LABEL: LAA: Found a loop in full_checks_diff_strides: -; DEBUG: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%dst,+,(4 + (4 * (zext i32 %n to i64)))}<%outer.loop> End: {((4 * (zext i32 %n to i64)) + %dst),+,(4 + (4 * (zext i32 %n to i64)))}<%outer.loop> +; DEBUG-NOT: LAA: Creating diff runtime check for: +; DEBUG: LAA: Adding RT check for range: +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %n to i64)) + ((4 + (4 * (zext i32 %n to i64))) * (-1 + (zext i32 %m to i64))) + %dst) ; DEBUG-NEXT: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%src,+,(4 * (zext i32 %n to i64))}<%outer.loop> End: {((4 * (zext i32 %n to i64)) + %src),+,(4 * (zext i32 %n to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src) - -define void @full_checks_diff_strides(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) #0 { +define void @full_checks_diff_strides(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) { ; CHECK-LABEL: define void @full_checks_diff_strides ; CHECK-SAME: (ptr nocapture noundef [[DST:%.*]], ptr nocapture noundef readonly [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) { ; CHECK-NEXT: entry: ; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64 ; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64 -; CHECK-NEXT: [[TMP0:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2 -; CHECK-NEXT: [[TMP1:%.*]] = add nuw nsw i64 [[TMP0]], 4 -; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[WIDE_N]], 2 +; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 [[WIDE_M]], -1 +; CHECK-NEXT: [[TMP1:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2 +; CHECK-NEXT: [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 4 +; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP0]], [[TMP2]] +; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP3]], [[TMP1]] +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]] +; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]] +; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2 +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP6]] ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_EXIT:%.*]] ] -; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP1]], [[OUTER_IV]] -; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP3]] -; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP0]], [[TMP3]] -; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]] -; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP2]], [[OUTER_IV]] -; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]] -; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP0]], [[TMP5]] -; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP6]] ; CHECK-NEXT: [[NPLUS1:%.*]] = add nuw nsw i32 [[N]], 1 ; CHECK-NEXT: [[WIDE_NPLUS1:%.*]] = zext i32 [[NPLUS1]] to i64 ; CHECK-NEXT: [[TMP7:%.*]] = mul nsw i64 [[OUTER_IV]], [[WIDE_N]] @@ -294,8 +305,8 @@ ; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: -; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]] -; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]] ; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] ; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: @@ -308,16 +319,16 @@ ; CHECK-NEXT: [[TMP10:%.*]] = add nuw nsw i64 [[TMP9]], [[TMP7]] ; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP10]] ; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[TMP11]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP12]], align 4, !alias.scope !11 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP12]], align 4, !alias.scope !16 ; CHECK-NEXT: [[TMP13:%.*]] = add nuw nsw i64 [[TMP9]], [[TMP8]] ; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP13]] ; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[TMP14]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope !14, !noalias !11 -; CHECK-NEXT: [[TMP16:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]] -; CHECK-NEXT: store <4 x i32> [[TMP16]], ptr [[TMP15]], align 4, !alias.scope !14, !noalias !11 +; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope !19, !noalias !16 +; CHECK-NEXT: [[TMP16:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]] +; CHECK-NEXT: store <4 x i32> [[TMP16]], ptr [[TMP15]], align 4, !alias.scope !19, !noalias !16 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 ; CHECK-NEXT: [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP17]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP16:![0-9]+]] +; CHECK-NEXT: br i1 [[TMP17]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP21:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]] @@ -336,7 +347,7 @@ ; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4 ; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1 ; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]] -; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP17:![0-9]+]] +; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP22:![0-9]+]] ; CHECK: inner.exit: ; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1 ; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_M]] @@ -391,6 +402,7 @@ ; } ; DEBUG-LABEL: LAA: Found a loop in diff_checks_src_start_invariant: +; DEBUG-NOT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting define void @diff_checks_src_start_invariant(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) { ; CHECK-LABEL: define void @diff_checks_src_start_invariant @@ -430,7 +442,7 @@ ; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP11]], align 4 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 ; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP12]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP18:![0-9]+]] +; CHECK-NEXT: br i1 [[TMP12]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP23:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]] @@ -446,7 +458,7 @@ ; CHECK-NEXT: store i32 [[TMP13]], ptr [[ARRAYIDX6_US]], align 4 ; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1 ; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]] -; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP19:![0-9]+]] +; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP24:![0-9]+]] ; CHECK: inner.loop.exit: ; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1 ; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]] @@ -497,7 +509,8 @@ ; DEBUG-LABEL: LAA: Found a loop in full_checks_src_start_invariant: ; DEBUG: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%dst,+,(4 * (zext i32 %n to i64))}<%outer.loop> End: {((4 * (zext i32 %n to i64)) + %dst),+,(4 * (zext i32 %n to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %dst) ; DEBUG-NEXT: LAA: Adding RT check for range: ; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %n to i64)) + %src) @@ -508,22 +521,20 @@ ; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64 ; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64 ; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64 -; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[WIDE_N]], 2 -; CHECK-NEXT: [[TMP2:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2 -; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP2]] +; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]] +; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2 +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP2]] +; CHECK-NEXT: [[TMP3:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2 +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP3]] ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ] -; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP1]], [[IV_OUTER]] -; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP3]] -; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP2]], [[TMP3]] -; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]] -; CHECK-NEXT: [[TMP5:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]] +; CHECK-NEXT: [[TMP4:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]] ; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: -; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP2]] -; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]] ; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] ; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: @@ -532,19 +543,19 @@ ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK: vector.body: ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] -; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP6]] -; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[TMP7]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP8]], align 4, !alias.scope !20 -; CHECK-NEXT: [[TMP9:%.*]] = add nuw nsw i64 [[TMP6]], [[TMP5]] -; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP9]] -; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i32, ptr [[TMP10]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP11]], align 4, !alias.scope !23, !noalias !20 -; CHECK-NEXT: [[TMP12:%.*]] = add nsw <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]] -; CHECK-NEXT: store <4 x i32> [[TMP12]], ptr [[TMP11]], align 4, !alias.scope !23, !noalias !20 +; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[INDEX]], 0 +; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP5]] +; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[TMP6]], i32 0 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP7]], align 4, !alias.scope !25 +; CHECK-NEXT: [[TMP8:%.*]] = add nuw nsw i64 [[TMP5]], [[TMP4]] +; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP8]] +; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[TMP9]], i32 0 +; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope !28, !noalias !25 +; CHECK-NEXT: [[TMP11:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]] +; CHECK-NEXT: store <4 x i32> [[TMP11]], ptr [[TMP10]], align 4, !alias.scope !28, !noalias !25 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 -; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP13]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP25:![0-9]+]] +; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] +; CHECK-NEXT: br i1 [[TMP12]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP30:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]] @@ -554,15 +565,15 @@ ; CHECK: inner.loop: ; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ] ; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IV_INNER]] -; CHECK-NEXT: [[TMP14:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 -; CHECK-NEXT: [[TMP15:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP5]] -; CHECK-NEXT: [[ARRAYIDX6_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP15]] -; CHECK-NEXT: [[TMP16:%.*]] = load i32, ptr [[ARRAYIDX6_US]], align 4 -; CHECK-NEXT: [[ADD7_US:%.*]] = add nsw i32 [[TMP16]], [[TMP14]] +; CHECK-NEXT: [[TMP13:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 +; CHECK-NEXT: [[TMP14:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP4]] +; CHECK-NEXT: [[ARRAYIDX6_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP14]] +; CHECK-NEXT: [[TMP15:%.*]] = load i32, ptr [[ARRAYIDX6_US]], align 4 +; CHECK-NEXT: [[ADD7_US:%.*]] = add nsw i32 [[TMP15]], [[TMP13]] ; CHECK-NEXT: store i32 [[ADD7_US]], ptr [[ARRAYIDX6_US]], align 4 ; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1 ; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]] -; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP26:![0-9]+]] +; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP31:![0-9]+]] ; CHECK: inner.loop.exit: ; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1 ; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]] @@ -614,11 +625,14 @@ ; } ; } ; } - +; The 'src' access varies with the outermost loop, rather than the parent of the +; innermost loop. Hence we don't expand `src`, although in theory we could do. ; DEBUG-LABEL: LAA: Found a loop in triple_nested_loop_mixed_access: +; DEBUG-NOT: LAA: Creating diff runtime check for: ; DEBUG: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {{[{][{]}}%dst,+,(4 * (zext i32 (1 + %o) to i64) * (zext i32 %n to i64))}<%outer.outer.loop>,+,(4 * (zext i32 %o to i64))}<%outer.loop> End: {{[{][{]}}((4 * (zext i32 %o to i64)) + %dst),+,(4 * (zext i32 (1 + %o) to i64) * (zext i32 %n to i64))}<%outer.outer.loop>,+,(4 * (zext i32 %o to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: Start: {%dst,+,(4 * (zext i32 (1 + %o) to i64) * (zext i32 %n to i64))}<%outer.outer.loop> End: {((4 * (zext i32 %n to i64) * (zext i32 %o to i64)) + %dst),+,(4 * (zext i32 (1 + %o) to i64) * (zext i32 %n to i64))}<%outer.outer.loop> ; DEBUG-NEXT: LAA: Adding RT check for range: ; DEBUG-NEXT: Start: {%src,+,(4 * (zext i32 %n to i64) * (zext i32 %o to i64))}<%outer.outer.loop> End: {((4 * (zext i32 %o to i64)) + %src),+,(4 * (zext i32 %n to i64) * (zext i32 %o to i64))}<%outer.outer.loop> @@ -635,32 +649,30 @@ ; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[O]] to i64 ; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP1]], [[TMP2]] ; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 2 -; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[WIDE_TRIP_COUNT]], 2 -; CHECK-NEXT: [[TMP6:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2 +; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[TMP1]] +; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2 ; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[TMP1]] ; CHECK-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 2 +; CHECK-NEXT: [[TMP9:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2 ; CHECK-NEXT: br label [[OUTER_OUTER_LOOP:%.*]] ; CHECK: outer.outer.loop: ; CHECK-NEXT: [[OUTER_OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_OUTER_IV_NEXT:%.*]], [[OUTER_LOOP_END:%.*]] ] -; CHECK-NEXT: [[TMP9:%.*]] = mul i64 [[TMP4]], [[OUTER_OUTER_IV]] -; CHECK-NEXT: [[TMP10:%.*]] = add i64 [[TMP6]], [[TMP9]] -; CHECK-NEXT: [[TMP11:%.*]] = mul i64 [[TMP8]], [[OUTER_OUTER_IV]] -; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP11]] -; CHECK-NEXT: [[TMP12:%.*]] = add i64 [[TMP6]], [[TMP11]] -; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP12]] -; CHECK-NEXT: [[TMP13:%.*]] = mul nsw i64 [[OUTER_OUTER_IV]], [[TMP1]] -; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[TMP13]], [[TMP0]] -; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[TMP13]], [[TMP2]] +; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP4]], [[OUTER_OUTER_IV]] +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP10]] +; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[TMP6]], [[TMP10]] +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP11]] +; CHECK-NEXT: [[TMP12:%.*]] = mul i64 [[TMP8]], [[OUTER_OUTER_IV]] +; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP12]] +; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP9]], [[TMP12]] +; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]] +; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[OUTER_OUTER_IV]], [[TMP1]] +; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[TMP14]], [[TMP0]] +; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[TMP14]], [[TMP2]] ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_END:%.*]] ], [ 0, [[OUTER_OUTER_LOOP]] ] -; CHECK-NEXT: [[TMP16:%.*]] = mul i64 [[TMP5]], [[OUTER_IV]] -; CHECK-NEXT: [[TMP17:%.*]] = add i64 [[TMP9]], [[TMP16]] -; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP17]] -; CHECK-NEXT: [[TMP18:%.*]] = add i64 [[TMP10]], [[TMP16]] -; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP18]] -; CHECK-NEXT: [[TMP19:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]] -; CHECK-NEXT: [[TMP20:%.*]] = add nuw nsw i64 [[TMP19]], [[TMP15]] +; CHECK-NEXT: [[TMP17:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]] +; CHECK-NEXT: [[TMP18:%.*]] = add nuw nsw i64 [[TMP17]], [[TMP16]] ; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: @@ -674,20 +686,20 @@ ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK: vector.body: ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] -; CHECK-NEXT: [[TMP21:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP22:%.*]] = add nuw nsw i64 [[TMP21]], [[TMP14]] -; CHECK-NEXT: [[TMP23:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP22]] -; CHECK-NEXT: [[TMP24:%.*]] = getelementptr inbounds i32, ptr [[TMP23]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP24]], align 4, !alias.scope !27 -; CHECK-NEXT: [[TMP25:%.*]] = add nuw nsw i64 [[TMP20]], [[TMP21]] -; CHECK-NEXT: [[TMP26:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP25]] -; CHECK-NEXT: [[TMP27:%.*]] = getelementptr inbounds i32, ptr [[TMP26]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP27]], align 4, !alias.scope !30, !noalias !27 -; CHECK-NEXT: [[TMP28:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]] -; CHECK-NEXT: store <4 x i32> [[TMP28]], ptr [[TMP27]], align 4, !alias.scope !30, !noalias !27 +; CHECK-NEXT: [[TMP19:%.*]] = add i64 [[INDEX]], 0 +; CHECK-NEXT: [[TMP20:%.*]] = add nuw nsw i64 [[TMP19]], [[TMP15]] +; CHECK-NEXT: [[TMP21:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP20]] +; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[TMP21]], i32 0 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP22]], align 4, !alias.scope !32 +; CHECK-NEXT: [[TMP23:%.*]] = add nuw nsw i64 [[TMP18]], [[TMP19]] +; CHECK-NEXT: [[TMP24:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP23]] +; CHECK-NEXT: [[TMP25:%.*]] = getelementptr inbounds i32, ptr [[TMP24]], i32 0 +; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP25]], align 4, !alias.scope !35, !noalias !32 +; CHECK-NEXT: [[TMP26:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]] +; CHECK-NEXT: store <4 x i32> [[TMP26]], ptr [[TMP25]], align 4, !alias.scope !35, !noalias !32 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 -; CHECK-NEXT: [[TMP29:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP29]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP32:![0-9]+]] +; CHECK-NEXT: [[TMP27:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] +; CHECK-NEXT: br i1 [[TMP27]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP37:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_END]], label [[SCALAR_PH]] @@ -696,17 +708,17 @@ ; CHECK-NEXT: br label [[INNER_LOOP:%.*]] ; CHECK: inner.loop: ; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ] -; CHECK-NEXT: [[TMP30:%.*]] = add nuw nsw i64 [[INNER_IV]], [[TMP14]] -; CHECK-NEXT: [[ARRAYIDX_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP30]] -; CHECK-NEXT: [[TMP31:%.*]] = load i32, ptr [[ARRAYIDX_US_US_US]], align 4 -; CHECK-NEXT: [[TMP32:%.*]] = add nuw nsw i64 [[TMP20]], [[INNER_IV]] -; CHECK-NEXT: [[ARRAYIDX17_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP32]] -; CHECK-NEXT: [[TMP33:%.*]] = load i32, ptr [[ARRAYIDX17_US_US_US]], align 4 -; CHECK-NEXT: [[ADD18_US_US_US:%.*]] = add nsw i32 [[TMP33]], [[TMP31]] +; CHECK-NEXT: [[TMP28:%.*]] = add nuw nsw i64 [[INNER_IV]], [[TMP15]] +; CHECK-NEXT: [[ARRAYIDX_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP28]] +; CHECK-NEXT: [[TMP29:%.*]] = load i32, ptr [[ARRAYIDX_US_US_US]], align 4 +; CHECK-NEXT: [[TMP30:%.*]] = add nuw nsw i64 [[TMP18]], [[INNER_IV]] +; CHECK-NEXT: [[ARRAYIDX17_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP30]] +; CHECK-NEXT: [[TMP31:%.*]] = load i32, ptr [[ARRAYIDX17_US_US_US]], align 4 +; CHECK-NEXT: [[ADD18_US_US_US:%.*]] = add nsw i32 [[TMP31]], [[TMP29]] ; CHECK-NEXT: store i32 [[ADD18_US_US_US]], ptr [[ARRAYIDX17_US_US_US]], align 4 ; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1 ; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]] -; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_END]], label [[INNER_LOOP]], !llvm.loop [[LOOP33:![0-9]+]] +; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_END]], label [[INNER_LOOP]], !llvm.loop [[LOOP38:![0-9]+]] ; CHECK: inner.loop.end: ; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1 ; CHECK-NEXT: [[EXIT_OUTER:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT60]] @@ -780,6 +792,7 @@ ; i++; ; } ; } +; Outer loop trip count is uncomputable so we shouldn't expand the ranges. ; DEBUG-LABEL: LAA: Found a loop in uncomputable_outer_tc: ; DEBUG: LAA: Adding RT check for range: @@ -834,16 +847,16 @@ ; CHECK-NEXT: [[TMP13:%.*]] = add nsw i64 [[TMP12]], [[TMP10]] ; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP13]] ; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[TMP14]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope !34 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope !39 ; CHECK-NEXT: [[TMP16:%.*]] = add nsw i64 [[TMP12]], [[TMP11]] ; CHECK-NEXT: [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP16]] ; CHECK-NEXT: [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[TMP17]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP18]], align 4, !alias.scope !37, !noalias !34 +; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP18]], align 4, !alias.scope !42, !noalias !39 ; CHECK-NEXT: [[TMP19:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]] -; CHECK-NEXT: store <4 x i32> [[TMP19]], ptr [[TMP18]], align 4, !alias.scope !37, !noalias !34 +; CHECK-NEXT: store <4 x i32> [[TMP19]], ptr [[TMP18]], align 4, !alias.scope !42, !noalias !39 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 ; CHECK-NEXT: [[TMP20:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP20]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP39:![0-9]+]] +; CHECK-NEXT: br i1 [[TMP20]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP44:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]] @@ -862,7 +875,7 @@ ; CHECK-NEXT: store i32 [[ADD11_US]], ptr [[ARRAYIDX10_US]], align 4 ; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1 ; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]] -; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP40:![0-9]+]] +; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP45:![0-9]+]] ; CHECK: inner.loop.exit: ; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1 ; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i8, ptr [[STR]], i64 [[OUTER_IV_NEXT]] @@ -928,12 +941,18 @@ ; } ; } ; } +; Inner IV is decreasing, but this isn't a problem and we can still expand the +; runtime checks correctly to cover the whole loop. ; DEBUG-LABEL: LAA: Found a loop in decreasing_inner_iv: ; DEBUG: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%dst,+,(4 * (sext i32 %stride1 to i64))}<%outer.loop> End: {(4 + (4 * (zext i32 %n to i64)) + %dst),+,(4 * (sext i32 %stride1 to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 %stride1 to i64)) +; DEBUG-NEXT: Start: %dst End: (4 + (4 * (zext i32 %n to i64)) + (4 * (sext i32 %stride1 to i64) * (-1 + (zext i32 %m to i64))) + %dst) ; DEBUG-NEXT: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {%src,+,(4 * (sext i32 %stride2 to i64))}<%outer.loop> End: {(4 + (4 * (zext i32 %n to i64)) + %src),+,(4 * (sext i32 %stride2 to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 %stride2 to i64)) +; DEBUG-NEXT: Start: %src End: (4 + (4 * (zext i32 %n to i64)) + (4 * (sext i32 %stride2 to i64) * (-1 + (zext i32 %m to i64))) + %src) define void @decreasing_inner_iv(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %stride1, i32 noundef %stride2, i32 noundef %m, i32 noundef %n) { ; CHECK-LABEL: define void @decreasing_inner_iv @@ -948,77 +967,83 @@ ; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[STRIDE2]] to i64 ; CHECK-NEXT: [[TMP2:%.*]] = sext i32 [[STRIDE1]] to i64 ; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M]] to i64 -; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2 -; CHECK-NEXT: [[TMP4:%.*]] = shl nuw nsw i64 [[TMP0]], 2 -; CHECK-NEXT: [[TMP5:%.*]] = add nuw nsw i64 [[TMP4]], 4 -; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP1]], 2 -; CHECK-NEXT: [[TMP7:%.*]] = add nuw nsw i64 [[TMP0]], 1 +; CHECK-NEXT: [[TMP3:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1 +; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP3]], [[TMP2]] +; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[TMP4]], 2 +; CHECK-NEXT: [[TMP6:%.*]] = shl nuw nsw i64 [[TMP0]], 2 +; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP5]], [[TMP6]] +; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP7]], 4 +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]] +; CHECK-NEXT: [[TMP9:%.*]] = shl nsw i64 [[TMP2]], 2 +; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP3]], [[TMP1]] +; CHECK-NEXT: [[TMP11:%.*]] = shl i64 [[TMP10]], 2 +; CHECK-NEXT: [[TMP12:%.*]] = add i64 [[TMP11]], [[TMP6]] +; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP12]], 4 +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]] +; CHECK-NEXT: [[TMP14:%.*]] = shl nsw i64 [[TMP1]], 2 +; CHECK-NEXT: [[TMP15:%.*]] = add nuw nsw i64 [[TMP0]], 1 ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ] -; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[TMP3]], [[OUTER_IV]] -; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]] -; CHECK-NEXT: [[TMP9:%.*]] = add i64 [[TMP5]], [[TMP8]] -; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP9]] -; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP6]], [[OUTER_IV]] -; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP10]] -; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[TMP5]], [[TMP10]] -; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP11]] -; CHECK-NEXT: [[TMP12:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP1]] -; CHECK-NEXT: [[TMP13:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]] -; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP7]], 4 +; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP1]] +; CHECK-NEXT: [[TMP17:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]] +; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP15]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: -; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]] -; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]] +; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]] ; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] -; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] +; CHECK-NEXT: [[TMP18:%.*]] = icmp slt i64 [[TMP9]], 0 +; CHECK-NEXT: [[TMP19:%.*]] = or i1 [[FOUND_CONFLICT]], [[TMP18]] +; CHECK-NEXT: [[TMP20:%.*]] = icmp slt i64 [[TMP14]], 0 +; CHECK-NEXT: [[TMP21:%.*]] = or i1 [[TMP19]], [[TMP20]] +; CHECK-NEXT: br i1 [[TMP21]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: -; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[TMP7]], 4 -; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP7]], [[N_MOD_VF]] +; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[TMP15]], 4 +; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP15]], [[N_MOD_VF]] ; CHECK-NEXT: [[IND_END:%.*]] = sub i64 [[TMP0]], [[N_VEC]] ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK: vector.body: ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] ; CHECK-NEXT: [[OFFSET_IDX:%.*]] = sub i64 [[TMP0]], [[INDEX]] -; CHECK-NEXT: [[TMP14:%.*]] = add i64 [[OFFSET_IDX]], 0 -; CHECK-NEXT: [[TMP15:%.*]] = add nsw i64 [[TMP14]], [[TMP12]] -; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]] -; CHECK-NEXT: [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[TMP16]], i32 0 -; CHECK-NEXT: [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[TMP17]], i32 -3 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP18]], align 4, !alias.scope !41 +; CHECK-NEXT: [[TMP22:%.*]] = add i64 [[OFFSET_IDX]], 0 +; CHECK-NEXT: [[TMP23:%.*]] = add nsw i64 [[TMP22]], [[TMP16]] +; CHECK-NEXT: [[TMP24:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP23]] +; CHECK-NEXT: [[TMP25:%.*]] = getelementptr inbounds i32, ptr [[TMP24]], i32 0 +; CHECK-NEXT: [[TMP26:%.*]] = getelementptr inbounds i32, ptr [[TMP25]], i32 -3 +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP26]], align 4, !alias.scope !46 ; CHECK-NEXT: [[REVERSE:%.*]] = shufflevector <4 x i32> [[WIDE_LOAD]], <4 x i32> poison, <4 x i32> -; CHECK-NEXT: [[TMP19:%.*]] = add nsw i64 [[TMP14]], [[TMP13]] -; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP19]] -; CHECK-NEXT: [[TMP21:%.*]] = getelementptr inbounds i32, ptr [[TMP20]], i32 0 -; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[TMP21]], i32 -3 -; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP22]], align 4, !alias.scope !44, !noalias !41 -; CHECK-NEXT: [[REVERSE5:%.*]] = shufflevector <4 x i32> [[WIDE_LOAD4]], <4 x i32> poison, <4 x i32> -; CHECK-NEXT: [[TMP23:%.*]] = add nsw <4 x i32> [[REVERSE5]], [[REVERSE]] -; CHECK-NEXT: [[REVERSE6:%.*]] = shufflevector <4 x i32> [[TMP23]], <4 x i32> poison, <4 x i32> -; CHECK-NEXT: store <4 x i32> [[REVERSE6]], ptr [[TMP22]], align 4, !alias.scope !44, !noalias !41 +; CHECK-NEXT: [[TMP27:%.*]] = add nsw i64 [[TMP22]], [[TMP17]] +; CHECK-NEXT: [[TMP28:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP27]] +; CHECK-NEXT: [[TMP29:%.*]] = getelementptr inbounds i32, ptr [[TMP28]], i32 0 +; CHECK-NEXT: [[TMP30:%.*]] = getelementptr inbounds i32, ptr [[TMP29]], i32 -3 +; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP30]], align 4, !alias.scope !49, !noalias !46 +; CHECK-NEXT: [[REVERSE3:%.*]] = shufflevector <4 x i32> [[WIDE_LOAD2]], <4 x i32> poison, <4 x i32> +; CHECK-NEXT: [[TMP31:%.*]] = add nsw <4 x i32> [[REVERSE3]], [[REVERSE]] +; CHECK-NEXT: [[REVERSE4:%.*]] = shufflevector <4 x i32> [[TMP31]], <4 x i32> poison, <4 x i32> +; CHECK-NEXT: store <4 x i32> [[REVERSE4]], ptr [[TMP30]], align 4, !alias.scope !49, !noalias !46 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 -; CHECK-NEXT: [[TMP24:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP24]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP46:![0-9]+]] +; CHECK-NEXT: [[TMP32:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] +; CHECK-NEXT: br i1 [[TMP32]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP51:![0-9]+]] ; CHECK: middle.block: -; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP7]], [[N_VEC]] +; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP15]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]] ; CHECK: scalar.ph: ; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ [[TMP0]], [[OUTER_LOOP]] ], [ [[TMP0]], [[VECTOR_MEMCHECK]] ] ; CHECK-NEXT: br label [[INNER_LOOP:%.*]] ; CHECK: inner.loop: ; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ] -; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[INNER_IV]], [[TMP12]] -; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP25]] -; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 -; CHECK-NEXT: [[TMP27:%.*]] = add nsw i64 [[INNER_IV]], [[TMP13]] -; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP27]] -; CHECK-NEXT: [[TMP28:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4 -; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP28]], [[TMP26]] +; CHECK-NEXT: [[TMP33:%.*]] = add nsw i64 [[INNER_IV]], [[TMP16]] +; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP33]] +; CHECK-NEXT: [[TMP34:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4 +; CHECK-NEXT: [[TMP35:%.*]] = add nsw i64 [[INNER_IV]], [[TMP17]] +; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP35]] +; CHECK-NEXT: [[TMP36:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4 +; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP36]], [[TMP34]] ; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4 ; CHECK-NEXT: [[INNER_IV_NEXT]] = add nsw i64 [[INNER_IV]], -1 ; CHECK-NEXT: [[CMP2_US:%.*]] = icmp sgt i64 [[INNER_IV]], 0 -; CHECK-NEXT: br i1 [[CMP2_US]], label [[INNER_LOOP]], label [[INNER_LOOP_EXIT]], !llvm.loop [[LOOP47:![0-9]+]] +; CHECK-NEXT: br i1 [[CMP2_US]], label [[INNER_LOOP]], label [[INNER_LOOP_EXIT]], !llvm.loop [[LOOP52:![0-9]+]] ; CHECK: inner.loop.exit: ; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1 ; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT]] @@ -1082,12 +1107,18 @@ ; } ; } ; } +; Outer IV is decreasing, but the direction of memory accesses also depends +; upon the signedness of stride1. ; DEBUG-LABEL: LAA: Found a loop in decreasing_outer_iv: ; DEBUG: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {((4 * (zext i32 %m to i64) * (sext i32 %stride1 to i64)) + %dst),+,(-4 * (sext i32 %stride1 to i64))}<%outer.loop> End: {((4 * (zext i32 (1 + %n) to i64)) + (4 * (zext i32 %m to i64) * (sext i32 %stride1 to i64)) + %dst),+,(-4 * (sext i32 %stride1 to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: LAA: ... but need to check stride is positive: (-4 * (sext i32 %stride1 to i64)) +; DEBUG-NEXT: Start: ((4 * (zext i32 %m to i64) * (sext i32 %stride1 to i64)) + %dst) End: ((4 * (zext i32 (1 + %n) to i64)) + (4 * (sext i32 %stride1 to i64)) + %dst) ; DEBUG-NEXT: LAA: Adding RT check for range: -; DEBUG-NEXT: Start: {((4 * (zext i32 %m to i64) * (sext i32 %stride2 to i64)) + %src),+,(-4 * (sext i32 %stride2 to i64))}<%outer.loop> End: {((4 * (zext i32 (1 + %n) to i64)) + (4 * (zext i32 %m to i64) * (sext i32 %stride2 to i64)) + %src),+,(-4 * (sext i32 %stride2 to i64))}<%outer.loop> +; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting +; DEBUG-NEXT: LAA: ... but need to check stride is positive: (-4 * (sext i32 %stride2 to i64)) +; DEBUG-NEXT: Start: ((4 * (zext i32 %m to i64) * (sext i32 %stride2 to i64)) + %src) End: ((4 * (zext i32 (1 + %n) to i64)) + (4 * (sext i32 %stride2 to i64)) + %src) define void @decreasing_outer_iv(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %stride1, i32 noundef %stride2, i32 noundef %m, i32 noundef %n) { ; CHECK-LABEL: define void @decreasing_outer_iv @@ -1105,37 +1136,36 @@ ; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64 ; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP2]], [[TMP1]] ; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[TMP4]], 2 -; CHECK-NEXT: [[TMP6:%.*]] = mul i64 [[TMP2]], -4 +; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]] +; CHECK-NEXT: [[TMP6:%.*]] = shl nsw i64 [[TMP2]], 2 ; CHECK-NEXT: [[TMP7:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2 -; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP5]], [[TMP7]] -; CHECK-NEXT: [[TMP9:%.*]] = mul i64 [[TMP3]], [[TMP1]] -; CHECK-NEXT: [[TMP10:%.*]] = shl i64 [[TMP9]], 2 -; CHECK-NEXT: [[TMP11:%.*]] = mul i64 [[TMP3]], -4 -; CHECK-NEXT: [[TMP12:%.*]] = add i64 [[TMP10]], [[TMP7]] +; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP6]], [[TMP7]] +; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]] +; CHECK-NEXT: [[TMP9:%.*]] = mul nsw i64 [[TMP2]], -4 +; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP3]], [[TMP1]] +; CHECK-NEXT: [[TMP11:%.*]] = shl i64 [[TMP10]], 2 +; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP11]] +; CHECK-NEXT: [[TMP12:%.*]] = shl nsw i64 [[TMP3]], 2 +; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP12]], [[TMP7]] +; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]] +; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[TMP3]], -4 ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: -; CHECK-NEXT: [[INDVAR:%.*]] = phi i64 [ [[INDVAR_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ], [ 0, [[OUTER_LOOP_PRE]] ] -; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[TMP1]], [[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT]] ] -; CHECK-NEXT: [[TMP13:%.*]] = mul i64 [[TMP6]], [[INDVAR]] -; CHECK-NEXT: [[TMP14:%.*]] = add i64 [[TMP5]], [[TMP13]] -; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP14]] -; CHECK-NEXT: [[TMP15:%.*]] = add i64 [[TMP8]], [[TMP13]] -; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP15]] -; CHECK-NEXT: [[TMP16:%.*]] = mul i64 [[TMP11]], [[INDVAR]] -; CHECK-NEXT: [[TMP17:%.*]] = add i64 [[TMP10]], [[TMP16]] -; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP17]] -; CHECK-NEXT: [[TMP18:%.*]] = add i64 [[TMP12]], [[TMP16]] -; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP18]] +; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[TMP1]], [[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ] ; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nsw i64 [[OUTER_IV]], -1 -; CHECK-NEXT: [[TMP19:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP3]] -; CHECK-NEXT: [[TMP20:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]] +; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP3]] +; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]] ; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4 ; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]] ; CHECK: vector.memcheck: ; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]] ; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]] ; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]] -; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] +; CHECK-NEXT: [[TMP17:%.*]] = icmp slt i64 [[TMP9]], 0 +; CHECK-NEXT: [[TMP18:%.*]] = or i1 [[FOUND_CONFLICT]], [[TMP17]] +; CHECK-NEXT: [[TMP19:%.*]] = icmp slt i64 [[TMP14]], 0 +; CHECK-NEXT: [[TMP20:%.*]] = or i1 [[TMP18]], [[TMP19]] +; CHECK-NEXT: br i1 [[TMP20]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]] ; CHECK: vector.ph: ; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4 ; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]] @@ -1143,19 +1173,19 @@ ; CHECK: vector.body: ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] ; CHECK-NEXT: [[TMP21:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP22:%.*]] = add nsw i64 [[TMP21]], [[TMP19]] +; CHECK-NEXT: [[TMP22:%.*]] = add nsw i64 [[TMP21]], [[TMP15]] ; CHECK-NEXT: [[TMP23:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP22]] ; CHECK-NEXT: [[TMP24:%.*]] = getelementptr inbounds i32, ptr [[TMP23]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP24]], align 4, !alias.scope !48 -; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[TMP21]], [[TMP20]] +; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP24]], align 4, !alias.scope !53 +; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[TMP21]], [[TMP16]] ; CHECK-NEXT: [[TMP26:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP25]] ; CHECK-NEXT: [[TMP27:%.*]] = getelementptr inbounds i32, ptr [[TMP26]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP27]], align 4, !alias.scope !51, !noalias !48 +; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP27]], align 4, !alias.scope !56, !noalias !53 ; CHECK-NEXT: [[TMP28:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]] -; CHECK-NEXT: store <4 x i32> [[TMP28]], ptr [[TMP27]], align 4, !alias.scope !51, !noalias !48 +; CHECK-NEXT: store <4 x i32> [[TMP28]], ptr [[TMP27]], align 4, !alias.scope !56, !noalias !53 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4 ; CHECK-NEXT: [[TMP29:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP29]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP53:![0-9]+]] +; CHECK-NEXT: br i1 [[TMP29]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP58:![0-9]+]] ; CHECK: middle.block: ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]] @@ -1164,20 +1194,19 @@ ; CHECK-NEXT: br label [[INNER_LOOP:%.*]] ; CHECK: inner.loop: ; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ] -; CHECK-NEXT: [[TMP30:%.*]] = add nsw i64 [[INNER_IV]], [[TMP19]] +; CHECK-NEXT: [[TMP30:%.*]] = add nsw i64 [[INNER_IV]], [[TMP15]] ; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP30]] ; CHECK-NEXT: [[TMP31:%.*]] = load i32, ptr [[ARRAYIDX]], align 4 -; CHECK-NEXT: [[TMP32:%.*]] = add nsw i64 [[INNER_IV]], [[TMP20]] +; CHECK-NEXT: [[TMP32:%.*]] = add nsw i64 [[INNER_IV]], [[TMP16]] ; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP32]] ; CHECK-NEXT: [[TMP33:%.*]] = load i32, ptr [[ARRAYIDX8]], align 4 ; CHECK-NEXT: [[ADD9:%.*]] = add nsw i32 [[TMP33]], [[TMP31]] ; CHECK-NEXT: store i32 [[ADD9]], ptr [[ARRAYIDX8]], align 4 ; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1 ; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]] -; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP54:![0-9]+]] +; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP59:![0-9]+]] ; CHECK: inner.loop.exit: ; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i64 [[OUTER_IV]], 1 -; CHECK-NEXT: [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1 ; CHECK-NEXT: br i1 [[CMP]], label [[OUTER_LOOP]], label [[OUTER_LOOP_EXIT:%.*]] ; CHECK: outer.loop.exit: ; CHECK-NEXT: br label [[EXIT]]