Index: llvm/include/llvm/Transforms/Scalar/LoopBoundSplit.h =================================================================== --- /dev/null +++ llvm/include/llvm/Transforms/Scalar/LoopBoundSplit.h @@ -0,0 +1,44 @@ +//===------- LoopBoundSplit.h - Split Loop Bound ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPBOUNDSPLIT_H +#define LLVM_TRANSFORMS_SCALAR_LOOPBOUNDSPLIT_H + +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// This pass transforms loops that contain a conditional branch with induction +/// variable. In order to make this pass as simple as possible, it handles +/// a condition which is mainly "AddRec < Bound" and its variants. For example, +/// it transforms left code to right code: +/// +/// newbound1 = min(n, c) +/// newbound2 = max(n, c) +/// while (iv < n) { while(iv < newbound1) { +/// A A +/// if (iv < c) B +/// B C +/// C } +/// } iv = newbound1 +/// while (iv < newbound2) { +/// A +/// C +/// } +class LoopBoundSplitPass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPBOUNDSPLIT_H Index: llvm/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/lib/Passes/PassBuilder.cpp +++ llvm/lib/Passes/PassBuilder.cpp @@ -159,6 +159,7 @@ #include "llvm/Transforms/Scalar/JumpThreading.h" #include "llvm/Transforms/Scalar/LICM.h" #include "llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h" +#include "llvm/Transforms/Scalar/LoopBoundSplit.h" #include "llvm/Transforms/Scalar/LoopDataPrefetch.h" #include "llvm/Transforms/Scalar/LoopDeletion.h" #include "llvm/Transforms/Scalar/LoopDistribute.h" Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -407,6 +407,7 @@ LOOP_PASS("print", LoopCachePrinterPass(dbgs())) LOOP_PASS("loop-predication", LoopPredicationPass()) LOOP_PASS("guard-widening", GuardWideningPass()) +LOOP_PASS("loop-bound-split", LoopBoundSplitPass()) LOOP_PASS("simple-loop-unswitch", SimpleLoopUnswitchPass()) LOOP_PASS("loop-reroll", LoopRerollPass()) LOOP_PASS("loop-versioning-licm", LoopVersioningLICMPass()) Index: llvm/lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- llvm/lib/Transforms/Scalar/CMakeLists.txt +++ llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -25,6 +25,7 @@ JumpThreading.cpp LICM.cpp LoopAccessAnalysisPrinter.cpp + LoopBoundSplit.cpp LoopSink.cpp LoopDeletion.cpp LoopDataPrefetch.cpp Index: llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp =================================================================== --- /dev/null +++ llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp @@ -0,0 +1,447 @@ +//===------- LoopBoundSplit.cpp - Split Loop Bound --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/LoopBoundSplit.h" +#include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopIterator.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/MemorySSAUpdater.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" + +#define DEBUG_TYPE "loop-bound-split" + +using namespace llvm; +using namespace llvm::PatternMatch; + +struct ConditionInfo { + /// Branch instruction with this condition + BranchInst *BI; + /// ICmp instruction with this condition + ICmpInst *ICmp; + /// Preciate info + ICmpInst::Predicate Pred; + /// AddRec llvm value + Value *AddRecValue; + /// Bound llvm value + Value *BoundValue; + /// AddRec SCEV + const SCEV *AddRecSCEV; + /// Bound SCEV + const SCEV *BoundSCEV; + /// Has been swapped LHS and RHS for AddRec and Bound + bool OpsSwapped; + + ConditionInfo() + : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE), + AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr), + BoundSCEV(nullptr), OpsSwapped(false) {} +}; + +static bool splitLoopBound(Loop &L, const LoopAccessInfo &LAI, + DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, + AAResults &AA, TargetTransformInfo &TTI, + ScalarEvolution &SE, LPMUpdater &U) { + auto AnalyzeICmp = [&SE](ICmpInst *ICmp, ConditionInfo &Cond) { + Cond.ICmp = ICmp; + if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue), + m_Value(Cond.BoundValue)))) { + Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue); + Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue); + // Locate AddRec in LHSSCEV and Bound in RHSSCEV. + if (isa(Cond.BoundSCEV) && + !isa(Cond.AddRecSCEV)) { + std::swap(Cond.AddRecValue, Cond.BoundValue); + std::swap(Cond.AddRecSCEV, Cond.BoundSCEV); + Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred); + Cond.OpsSwapped = true; + } + } + }; + + auto CalculateUpperBound = [&L, &SE](ConditionInfo &Cond, bool IsExitCond) { + if (IsExitCond) { + const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent()); + if (isa(ExitCount)) + return false; + + Cond.BoundSCEV = ExitCount; + return true; + } + + // For non-exit condtion, if pred is LT, keep existing bound. + if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT) + return true; + + // For non-exit condition, if pre is LE, try to convert it to LT. + // Range Range + // AddRec <= Bound --> AddRec < Bound + 1 + if (Cond.Pred == ICmpInst::ICMP_ULE || Cond.Pred == ICmpInst::ICMP_SLE) { + if (IntegerType *BoundSCEVIntType = + dyn_cast(Cond.BoundSCEV->getType())) { + unsigned BitWidth = BoundSCEVIntType->getBitWidth(); + const SCEV *BoundPlusOneSCEV = + SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType)); + APInt Max = ICmpInst::isSigned(Cond.Pred) + ? APInt::getSignedMaxValue(BitWidth) + : APInt::getMaxValue(BitWidth); + const SCEV *MaxSCEV = SE.getConstant(Max); + // Check Bound < INT_MAX + ICmpInst::Predicate Pred = ICmpInst::isSigned(Cond.Pred) + ? ICmpInst::ICMP_SLT + : ICmpInst::ICMP_ULT; + if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) { + Cond.BoundSCEV = BoundPlusOneSCEV; + Cond.Pred = Pred; + return true; + } + } + } + return false; + }; + + auto HasProcessableCondition = [&L, &SE, &AnalyzeICmp, &CalculateUpperBound]( + ICmpInst *ICmp, ConditionInfo &Cond, + bool IsExitCond) { + AnalyzeICmp(ICmp, Cond); + + // The BoundSCEV should be evaluated at loop entry. + if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L)) + return false; + + const SCEVAddRecExpr *AddRecSCEV = + dyn_cast(Cond.AddRecSCEV); + // Allowed AddRec as induction variable. + if (!AddRecSCEV) + return false; + + if (!AddRecSCEV->isAffine()) + return false; + + const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE); + // Allowed constant step. + if (!isa(StepRecSCEV)) + return false; + + ConstantInt *StepCI = cast(StepRecSCEV)->getValue(); + // Allowed positive step for now. + // TODO: Support negative step. + if (StepCI->isNegative() || StepCI->isZero()) + return false; + + // Calculate upper bound. + if (!CalculateUpperBound(Cond, IsExitCond)) + return false; + + return true; + }; + + auto IsProcessableCondBI = [](BranchInst *BI) { + ICmpInst::Predicate Pred; + BasicBlock *TrueSucc = nullptr; + BasicBlock *FalseSucc = nullptr; + if (!match(BI, m_Br(m_ICmp(Pred, m_Value(), m_Value()), + m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) + return false; + + if (TrueSucc == FalseSucc) + return false; + + return true; + }; + + auto CanSplitLoopBound = [&L, &LI, &DT, &SE, &HasProcessableCondition, + &IsProcessableCondBI](ConditionInfo &Cond) { + // Skip function with optsize. + if (L.getHeader()->getParent()->hasOptSize()) + return false; + + // Split only innermost loop. + if (!L.isInnermost()) + return false; + + // Check loop is in simplified form. + if (!L.isLoopSimplifyForm()) + return false; + + // Check loop is in LCSSA form. + if (!L.isLCSSAForm(DT)) + return false; + + // Skip loop that cannot be cloned. + if (!L.isSafeToClone()) + return false; + + BasicBlock *ExitingBB = L.getExitingBlock(); + // Assumed only one exiting block. + if (!ExitingBB) + return false; + + BranchInst *ExitingBI = dyn_cast(ExitingBB->getTerminator()); + if (!ExitingBI) + return false; + + // Allowed only conditional branch with ICmp. + if (!IsProcessableCondBI(ExitingBI)) + return false; + + // Check the condition is processable. + ICmpInst *ICmp = dyn_cast(ExitingBI->getCondition()); + if (!HasProcessableCondition(ICmp, Cond, /*IsExitCond*/ true)) + return false; + + Cond.BI = ExitingBI; + return true; + }; + + ConditionInfo ExitingCond; + ConditionInfo SplitCandidateCond; + + // Check we can split this loop's bound. + if (!CanSplitLoopBound(ExitingCond)) + return false; + + // Find split candidates. + bool FoundCandidate = false; + for (auto *BB : L.blocks()) { + // Skip condition of backedge. + if (L.getLoopLatch() == BB) + continue; + + auto *BI = dyn_cast(BB->getTerminator()); + if (!BI) + continue; + + // Check conditional branch with ICmp. + if (!IsProcessableCondBI(BI)) + continue; + + // Skip loop invariant condition. + if (L.isLoopInvariant(BI->getCondition())) + continue; + + // Allowed ICmp. + ICmpInst *ICmp = dyn_cast(BI->getCondition()); + if (!ICmp || !isa(ICmp->getOperand(0)->getType())) + continue; + + // Check the condition is processable. + if (!HasProcessableCondition(ICmp, SplitCandidateCond, + /*IsExitCond*/ false)) + continue; + + if (ExitingCond.BoundSCEV->getType() != + SplitCandidateCond.BoundSCEV->getType()) + continue; + + SplitCandidateCond.BI = BI; + FoundCandidate = true; + break; + } + + if (!FoundCandidate) + return false; + + auto IsProfitableToTransform = [&L, &LAI, &DT](BranchInst *BI) { + // If the conditional branch splits a loop into two halves, we could + // generally say it is profitable. + + // Check this branch is in loop header. + if (BI->getParent() != L.getHeader()) + return false; + + // Check this branch causes diamond CFG. + BasicBlock *Succ0 = BI->getSuccessor(0); + BasicBlock *Succ1 = BI->getSuccessor(1); + + if (!Succ0->getSinglePredecessor()) + return false; + if (!Succ1->getSinglePredecessor()) + return false; + + BasicBlock *Succ0Succ = Succ0->getSingleSuccessor(); + BasicBlock *Succ1Succ = Succ1->getSingleSuccessor(); + if (Succ0Succ != Succ1Succ) + return false; + + // Check join point is loop latch. + if (Succ0Succ != L.getLoopLatch()) + return false; + + // ToDo: Calculate each successor's instruction cost. + + return true; + }; + + if (!IsProfitableToTransform(SplitCandidateCond.BI)) + return false; + + // Now, we have a split candidate. Let's build a form as below. + // +--------------------+ + // | preheader | + // | set up newbound | + // +--------------------+ + // | /----------------\ + // +--------v----v------+ | + // | header |---\ | + // +--------------------+ | | + // | | | + // +--------v-----------+ | | + // | if.then.BB | | | + // | with true condition| | | + // +--------------------+ | | + // | | | + // +--------v-----------<---/ | + // | latch >----------/ + // | with newbound | + // +--------------------+ + // | + // +--------v-----------+ + // | preheader2 |--------------\ + // | if (AddRec i > | | + // | org bound) | | + // +--------------------+ | + // | /----------------\ | + // +--------v----v------+ | | + // | header2 |---\ | | + // +--------------------+ | | | + // | | | | + // +--------v-----------+ | | | + // | if.then.BB2 | | | | + // | conditional branch | | | | + // |with false condition| | | | + // +--------------------+ | | | + // | | | | + // +--------v-----------<---/ | | + // | latch2 >----------/ | + // | with org bound | | + // +--------v-----------+ | + // | | + // | +---------------+ | + // +--> exit <-------/ + // +---------------+ + + // Let's create post loop. + SmallVector PostLoopBlocks; + Loop *PostLoop; + ValueToValueMapTy VMap; + BasicBlock *PreHeader = L.getLoopPreheader(); + BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI); + PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap, + ".split", &LI, &DT, PostLoopBlocks); + remapInstructionsInBlocks(PostLoopBlocks, VMap); + + // Add conditional branch to check we can skip post-loop in its preheader. + BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader(); + IRBuilder<> Builder(PostLoopPreHeader); + Instruction *OrigBI = PostLoopPreHeader->getTerminator(); + ICmpInst::Predicate Pred = ICmpInst::ICMP_NE; + Value *Cond = + Builder.CreateICmp(Pred, ExitingCond.AddRecValue, ExitingCond.BoundValue); + Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock()); + OrigBI->eraseFromParent(); + + // Create new loop bound and add it into preheader of pre-loop. + const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV; + const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV; + NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred) + ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV) + : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV); + + SCEVExpander Expander( + SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split"); + Instruction *InsertPt = SplitLoopPH->getTerminator(); + Value *NewBoundValue = + Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt); + NewBoundValue->setName("new.bound"); + + // Replace exiting bound value of pre-loop NewBound. + if (ExitingCond.OpsSwapped) + ExitingCond.ICmp->setOperand(0, NewBoundValue); + else + ExitingCond.ICmp->setOperand(1, NewBoundValue); + + // Replace IV's start value of post-loop by NewBound. + for (PHINode &PN : L.getHeader()->phis()) { + // Find PHI with exiting condition from pre-loop. + if (isa(SE.getSCEV(&PN))) { + for (Value *Op : PN.incoming_values()) { + if (Op == ExitingCond.AddRecValue) { + // Find cloned PHI for post-loop. + PHINode *PostLoopPN = cast(VMap[&PN]); + PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, + NewBoundValue); + } + } + } + } + + // Replace SplitCandidateCond.BI's condition of pre-loop by True. + LLVMContext &Context = PreHeader->getContext(); + SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context)); + + // Replace cloned SplitCandidateCond.BI's condition in post-loop by False. + BranchInst *ClonedSplitCandidateBI = + cast(VMap[SplitCandidateCond.BI]); + ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context)); + + // Replace exit branch target of pre-loop by post-loop's preheader. + if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0)) + ExitingCond.BI->setSuccessor(0, PostLoopPreHeader); + else + ExitingCond.BI->setSuccessor(1, PostLoopPreHeader); + + // Update dominator tree. + DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock()); + DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader); + + // Invalidate cached SE information. + SE.forgetLoop(&L); + + // Canonicalize loops. + // TODO: Try to update LCSSA information according to above change. + formLCSSA(L, DT, &LI, &SE); + simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true); + formLCSSA(*PostLoop, DT, &LI, &SE); + simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true); + + + // Add new post-loop to loop pass manager. + U.addSiblingLoops(PostLoop); + + return true; +} + +PreservedAnalyses LoopBoundSplitPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + Function &F = *L.getHeader()->getParent(); + (void)F; + + LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L + << "\n"); + + const LoopAccessInfo &LAI = AM.getResult(L, AR); + + if (!splitLoopBound(L, LAI, AR.DT, AR.LI, AR.AC, AR.AA, AR.TTI, AR.SE, U)) + return PreservedAnalyses::all(); + + assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast)); + AR.LI.verify(AR.DT); + + return getLoopPassPreservedAnalyses(); +} Index: llvm/test/Transforms/LoopBoundSplit/loop-bound-split.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopBoundSplit/loop-bound-split.ll @@ -0,0 +1,453 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=loop-bound-split -S < %s | FileCheck %s + +define void @split_loop_bound_inc_with_sgt(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_inc_with_sgt( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP_PH_SPLIT:%.*]] +; CHECK: loop.ph.split: +; CHECK-NEXT: [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N:%.*]], i64 0) +; CHECK-NEXT: [[NEW_BOUND:%.*]] = call i64 @llvm.smin.i64(i64 [[A:%.*]], i64 [[SMAX]]) +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH_SPLIT]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]] +; CHECK-NEXT: br i1 true, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: if.else: +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[COND:%.*]] = icmp sgt i64 [[INC]], [[NEW_BOUND]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP_PH_SPLIT_SPLIT:%.*]], label [[LOOP]] +; CHECK: loop.ph.split.split: +; CHECK-NEXT: [[INC_LCSSA:%.*]] = phi i64 [ [[INC]], [[FOR_INC]] ] +; CHECK-NEXT: [[TMP0:%.*]] = icmp ne i64 [[INC_LCSSA]], [[N]] +; CHECK-NEXT: br i1 [[TMP0]], label [[LOOP_SPLIT_PREHEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.split.preheader: +; CHECK-NEXT: br label [[LOOP_SPLIT:%.*]] +; CHECK: loop.split: +; CHECK-NEXT: [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND]], [[LOOP_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]] +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[IF_ELSE_SPLIT:%.*]] +; CHECK: if.else.split: +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: if.then.split: +; CHECK-NEXT: [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]] +; CHECK-NEXT: [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]] +; CHECK-NEXT: store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: for.inc.split: +; CHECK-NEXT: [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 1 +; CHECK-NEXT: [[COND_SPLIT:%.*]] = icmp sgt i64 [[INC_SPLIT]], [[N]] +; CHECK-NEXT: br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]] +; CHECK: exit.loopexit: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %if.else + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.inc + +if.else: + br label %for.inc + +for.inc: + %inc = add nuw nsw i64 %iv, 1 + %cond = icmp sgt i64 %inc, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + +define void @split_loop_bound_inc_with_eq(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_inc_with_eq( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP_PH_SPLIT:%.*]] +; CHECK: loop.ph.split: +; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[N:%.*]], -1 +; CHECK-NEXT: [[NEW_BOUND:%.*]] = call i64 @llvm.umin.i64(i64 [[A:%.*]], i64 [[TMP0]]) +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH_SPLIT]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]] +; CHECK-NEXT: br i1 true, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: if.else: +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[COND:%.*]] = icmp eq i64 [[INC]], [[NEW_BOUND]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP_PH_SPLIT_SPLIT:%.*]], label [[LOOP]] +; CHECK: loop.ph.split.split: +; CHECK-NEXT: [[INC_LCSSA:%.*]] = phi i64 [ [[INC]], [[FOR_INC]] ] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i64 [[INC_LCSSA]], [[N]] +; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_SPLIT_PREHEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.split.preheader: +; CHECK-NEXT: br label [[LOOP_SPLIT:%.*]] +; CHECK: loop.split: +; CHECK-NEXT: [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND]], [[LOOP_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]] +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[IF_ELSE_SPLIT:%.*]] +; CHECK: if.else.split: +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: if.then.split: +; CHECK-NEXT: [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]] +; CHECK-NEXT: [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]] +; CHECK-NEXT: store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: for.inc.split: +; CHECK-NEXT: [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 1 +; CHECK-NEXT: [[COND_SPLIT:%.*]] = icmp eq i64 [[INC_SPLIT]], [[N]] +; CHECK-NEXT: br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]] +; CHECK: exit.loopexit: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %if.else + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.inc + +if.else: + br label %for.inc + +for.inc: + %inc = add nuw nsw i64 %iv, 1 + %cond = icmp eq i64 %inc, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + +define void @split_loop_bound_inc_with_sge(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_inc_with_sge( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP_PH_SPLIT:%.*]] +; CHECK: loop.ph.split: +; CHECK-NEXT: [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N:%.*]], i64 1) +; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 [[SMAX]], -1 +; CHECK-NEXT: [[NEW_BOUND:%.*]] = call i64 @llvm.smin.i64(i64 [[A:%.*]], i64 [[TMP0]]) +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH_SPLIT]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]] +; CHECK-NEXT: br i1 true, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: if.else: +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[COND:%.*]] = icmp sge i64 [[INC]], [[NEW_BOUND]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP_PH_SPLIT_SPLIT:%.*]], label [[LOOP]] +; CHECK: loop.ph.split.split: +; CHECK-NEXT: [[INC_LCSSA:%.*]] = phi i64 [ [[INC]], [[FOR_INC]] ] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i64 [[INC_LCSSA]], [[N]] +; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_SPLIT_PREHEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.split.preheader: +; CHECK-NEXT: br label [[LOOP_SPLIT:%.*]] +; CHECK: loop.split: +; CHECK-NEXT: [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND]], [[LOOP_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]] +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[IF_ELSE_SPLIT:%.*]] +; CHECK: if.else.split: +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: if.then.split: +; CHECK-NEXT: [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]] +; CHECK-NEXT: [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]] +; CHECK-NEXT: store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: for.inc.split: +; CHECK-NEXT: [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 1 +; CHECK-NEXT: [[COND_SPLIT:%.*]] = icmp sge i64 [[INC_SPLIT]], [[N]] +; CHECK-NEXT: br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]] +; CHECK: exit.loopexit: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %if.else + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.inc + +if.else: + br label %for.inc + +for.inc: + %inc = add nuw nsw i64 %iv, 1 + %cond = icmp sge i64 %inc, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + +define void @split_loop_bound_inc_with_step_is_not_one(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_inc_with_step_is_not_one( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP_PH_SPLIT:%.*]] +; CHECK: loop.ph.split: +; CHECK-NEXT: [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N:%.*]], i64 1) +; CHECK-NEXT: [[TMP0:%.*]] = lshr i64 [[SMAX]], 1 +; CHECK-NEXT: [[NEW_BOUND:%.*]] = call i64 @llvm.smin.i64(i64 [[A:%.*]], i64 [[TMP0]]) +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH_SPLIT]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]] +; CHECK-NEXT: br i1 true, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: if.else: +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[IV]], 2 +; CHECK-NEXT: [[COND:%.*]] = icmp sgt i64 [[INC]], [[NEW_BOUND]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP_PH_SPLIT_SPLIT:%.*]], label [[LOOP]] +; CHECK: loop.ph.split.split: +; CHECK-NEXT: [[INC_LCSSA:%.*]] = phi i64 [ [[INC]], [[FOR_INC]] ] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i64 [[INC_LCSSA]], [[N]] +; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_SPLIT_PREHEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.split.preheader: +; CHECK-NEXT: br label [[LOOP_SPLIT:%.*]] +; CHECK: loop.split: +; CHECK-NEXT: [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND]], [[LOOP_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]] +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[IF_ELSE_SPLIT:%.*]] +; CHECK: if.else.split: +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: if.then.split: +; CHECK-NEXT: [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]] +; CHECK-NEXT: [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]] +; CHECK-NEXT: store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4 +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: for.inc.split: +; CHECK-NEXT: [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 2 +; CHECK-NEXT: [[COND_SPLIT:%.*]] = icmp sgt i64 [[INC_SPLIT]], [[N]] +; CHECK-NEXT: br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]] +; CHECK: exit.loopexit: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %if.else + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.inc + +if.else: + br label %for.inc + +for.inc: + %inc = add nuw nsw i64 %iv, 2 + %cond = icmp sgt i64 %inc, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + +define void @split_loop_bound_inc_with_ne(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_inc_with_ne( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_INC]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[COND:%.*]] = icmp ne i64 [[INC]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %for.inc + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.inc + +for.inc: + %inc = add nuw nsw i64 %iv, 1 + %cond = icmp ne i64 %inc, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + +define void @split_loop_bound_dec_with_slt(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_dec_with_slt( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[DEC:%.*]], [[FOR_DEC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_DEC]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_DEC]] +; CHECK: for.dec: +; CHECK-NEXT: [[DEC]] = sub nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[COND:%.*]] = icmp slt i64 [[DEC]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %dec, %for.dec ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %for.dec + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.dec + +for.dec: + %dec = sub nuw nsw i64 %iv, 1 + %cond = icmp slt i64 %dec, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + +define void @split_loop_bound_dec_with_sle(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) { +; CHECK-LABEL: @split_loop_bound_dec_with_sle( +; CHECK-NEXT: loop.ph: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[DEC:%.*]], [[FOR_DEC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_DEC]] +; CHECK: if.then: +; CHECK-NEXT: [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]] +; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4 +; CHECK-NEXT: [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]] +; CHECK-NEXT: store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[FOR_DEC]] +; CHECK: for.dec: +; CHECK-NEXT: [[DEC]] = sub nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[COND:%.*]] = icmp sle i64 [[DEC]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +loop.ph: + br label %loop + +loop: + %iv = phi i64 [ %dec, %for.dec ], [ 0, %loop.ph ] + %cmp = icmp slt i64 %iv, %a + br i1 %cmp, label %if.then, label %for.dec + +if.then: + %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv + %val = load i64, i64* %src.arrayidx + %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv + store i64 %val, i64* %dst.arrayidx + br label %for.dec + +for.dec: + %dec = sub nuw nsw i64 %iv, 1 + %cond = icmp sle i64 %dec, %n + br i1 %cond, label %exit, label %loop + +exit: + ret void +} + + Index: llvm/utils/gn/secondary/llvm/lib/Transforms/Scalar/BUILD.gn =================================================================== --- llvm/utils/gn/secondary/llvm/lib/Transforms/Scalar/BUILD.gn +++ llvm/utils/gn/secondary/llvm/lib/Transforms/Scalar/BUILD.gn @@ -36,6 +36,7 @@ "JumpThreading.cpp", "LICM.cpp", "LoopAccessAnalysisPrinter.cpp", + "LoopBoundSplit.cpp", "LoopDataPrefetch.cpp", "LoopDeletion.cpp", "LoopDistribute.cpp",