Index: llvm/include/llvm/Transforms/Scalar/SimpleLoopBoundSplit.h =================================================================== --- /dev/null +++ llvm/include/llvm/Transforms/Scalar/SimpleLoopBoundSplit.h @@ -0,0 +1,44 @@ +//===- SimpleLoopBoundSplit.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_SIMPLELOOPBOUNDSPLIT_H +#define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPBOUNDSPLIT_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 SimpleLoopBoundSplitPass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPBOUNDSPLIT_H Index: llvm/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/lib/Passes/PassBuilder.cpp +++ llvm/lib/Passes/PassBuilder.cpp @@ -199,6 +199,7 @@ #include "llvm/Transforms/Scalar/ScalarizeMaskedMemIntrin.h" #include "llvm/Transforms/Scalar/Scalarizer.h" #include "llvm/Transforms/Scalar/SeparateConstOffsetFromGEP.h" +#include "llvm/Transforms/Scalar/SimpleLoopBoundSplit.h" #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h" #include "llvm/Transforms/Scalar/SimplifyCFG.h" #include "llvm/Transforms/Scalar/Sink.h" Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -408,6 +408,7 @@ LOOP_PASS("print", LoopCachePrinterPass(dbgs())) LOOP_PASS("loop-predication", LoopPredicationPass()) LOOP_PASS("guard-widening", GuardWideningPass()) +LOOP_PASS("simple-loop-bound-split", SimpleLoopBoundSplitPass()) 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 @@ -68,6 +68,7 @@ Scalarizer.cpp ScalarizeMaskedMemIntrin.cpp SeparateConstOffsetFromGEP.cpp + SimpleLoopBoundSplit.cpp SimpleLoopUnswitch.cpp SimplifyCFGPass.cpp Sink.cpp Index: llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp =================================================================== --- /dev/null +++ llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp @@ -0,0 +1,515 @@ +//===- SimpleLoopBoundSplit.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/SimpleLoopBoundSplit.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 "simple-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; + /// AddRec's step + ConstantInt *StepCI; + /// AddRec's start value + const SCEV *AddRecStartSCEV; + /// Has been swapped LHS and RHS for AddRec and Bound + bool OpsSwapped; + /// Has NSW + bool HasNoSignedWrap; + /// Has NUW + bool HasNoUnsignedWrap; + + ConditionInfo() + : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE), + AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr), + BoundSCEV(nullptr), StepCI(nullptr), AddRecStartSCEV(nullptr), + OpsSwapped(false), HasNoSignedWrap(false), HasNoUnsignedWrap(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 CalculateUpperBoundWithLT = [&L, &SE](ConditionInfo &Cond, + bool IsExitCond) { + // This function calculates upper bound from loop's exit condition and + // non-exit condition. If possible, it tries to canonicalize predicates to + // LT like 'AddRec < Bound'. For non-exit condtion, it tries to convert LE + // to LT. For exit condition, the predicates are inversed normally except EQ + // and then follows same conversion with non-exit condition. EQ is handled a + // bit differently. + + Cond.HasNoSignedWrap = + cast(Cond.AddRecSCEV)->hasNoSignedWrap(); + Cond.HasNoUnsignedWrap = + cast(Cond.AddRecSCEV)->hasNoUnsignedWrap(); + + // Exit condition Range + // AddRec == Bound --> AddRec < Bound + if (IsExitCond && Cond.Pred == ICmpInst::ICMP_EQ) { + Cond.Pred = ICmpInst::ICMP_ULT; + return; + } + + // Inverse exit condtion's pred for bound. + if (IsExitCond) + Cond.Pred = ICmpInst::getInversePredicate(Cond.Pred); + + // 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; + } + } + } + }; + + auto HasProcessableCondition = + [&L, &SE, &AnalyzeICmp, &CalculateUpperBoundWithLT]( + 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. + if (StepCI->isNegative() || StepCI->isZero()) + return false; + + // Allowed step is one when the condition is exit condition and its + // predication is EQ. + if (!StepCI->isOne() && IsExitCond && Cond.Pred == ICmpInst::ICMP_EQ) + return false; + + Cond.StepCI = StepCI; + + // TODO: Support negative step. + + CalculateUpperBoundWithLT(Cond, IsExitCond); + + // Allowed only 'AddRec < Bound' because the pred has been canonicalized + // by CalculateUpperBoundWithLT. + if (Cond.Pred != ICmpInst::ICMP_ULT && Cond.Pred != ICmpInst::ICMP_SLT) + return false; + + return true; + }; + + auto CanSplitLoopBound = [&L, &LI, &DT, + &HasProcessableCondition](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. + ICmpInst::Predicate Pred; + BasicBlock *TrueSucc = nullptr; + BasicBlock *FalseSucc = nullptr; + if (!match(ExitingBI, + m_Br(m_ICmp(Pred, m_Value(), m_Value()), m_BasicBlock(TrueSucc), + m_BasicBlock(FalseSucc)))) + return false; + + if (TrueSucc == FalseSucc) + 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 a split candidate. + bool FoundCandidate = false; + for (auto *BB : L.blocks()) { + // Skip condition of backedge. + if (L.getLoopLatch() == BB) + continue; + + // Skip unconditional branch. + auto *BI = dyn_cast(BB->getTerminator()); + if (!BI || !BI->isConditional() || + match(BI->getCondition(), m_Constant()) || + BI->getSuccessor(0) == BI->getSuccessor(1)) + 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; + + // Assumed same NSW/NUW of AddRec. + if (ExitingCond.HasNoSignedWrap != SplitCandidateCond.HasNoSignedWrap || + ExitingCond.HasNoUnsignedWrap != SplitCandidateCond.HasNoUnsignedWrap) + continue; + + // Assumed same start value of AddRec. + const SCEVAddRecExpr *ExitingAddRecSCEV = + cast(ExitingCond.AddRecSCEV); + const SCEVAddRecExpr *SplitAddRecSCEV = + cast(SplitCandidateCond.AddRecSCEV); + // On latch, the `inc++` is followed by exit condition and it causes exit + // condition's AddRec has 'start = start + step'. Consider it. + const SCEV *ExitingStartValueSCEV = + SE.getMinusSCEV(ExitingAddRecSCEV->getStart(), + ExitingAddRecSCEV->getStepRecurrence(SE)); + const SCEV *SplitStartValueSCEV = SplitAddRecSCEV->getStart(); + if (ExitingStartValueSCEV != SplitStartValueSCEV) + continue; + + // Update ExitingCond's AddRecSCEV for check later. + ExitingCond.AddRecStartSCEV = ExitingStartValueSCEV; + SplitCandidateCond.AddRecStartSCEV = SplitStartValueSCEV; + + SplitCandidateCond.BI = BI; + FoundCandidate = true; + break; + } + + if (!FoundCandidate) + return false; + + // ExitingCond's AddRec should be same with SplitCandidateCond's AddRec. + // Check NSW/NUW of AddRec. + assert(ExitingCond.HasNoSignedWrap == SplitCandidateCond.HasNoSignedWrap && + ExitingCond.HasNoUnsignedWrap == + SplitCandidateCond.HasNoUnsignedWrap && + "Should have same NSW/NUW between ExitingCond and SplitCandidateCond"); + // Check step of AddRec. + assert(ExitingCond.StepCI == SplitCandidateCond.StepCI && + "Should have same step between ExitingCond and SplitCandidateCond"); + // Check start value of AddRec. + assert(ExitingCond.AddRecStartSCEV == SplitCandidateCond.AddRecStartSCEV && + "Should have same start value between ExitingCond and " + "SplitCandidateCond"); + + auto isProfitableToTransform = [&L, &LAI, &DT](BranchInst *BI) { + // If there is conditional branch inside loop, loop vectorizer could try to + // predicate the conditional branch's successors. In this case, if the + // successor to be predicated has load/store instructions and target machine + // does not support masked vector load/store, loop vectorizer assigns big + // cost to the load/store instruction. It causes to block vectorize loop. We + // check the conditional branch's target blocks have load/store instruction. + // If the block has load/store instructions, we consider this transformation + // is profitable. + // + // ToDo: check something more here according to benchmarks' score + for (auto *Succ : BI->successors()) { + // Skip block which do not need predication. + if (DT.dominates(Succ, L.getLoopLatch())) + continue; + if (any_of(*Succ, [](Instruction &Inst) { + if (LoadInst *Load = dyn_cast(&Inst)) { + if (!Load->isVolatile()) + return true; + } + if (StoreInst *Store = dyn_cast(&Inst)) { + if (!Store->isVolatile()) + return true; + } + return false; + })) + return true; + } + return false; + }; + + if (!isProfitableToTransform(SplitCandidateCond.BI)) + return false; + + // Now, we have a split candidate. Let's split loop bound with it as below. + // +--------------------+ + // | preheader | + // | set up newbound1 | + // | newbound2 | + // +--------------------+ + // | /----------------\ + // +--------v----v------+ | + // | header |---\ | + // | conditional branch | | | + // | with true condition| | | + // +--------------------+ x | + // | x | + // +--------v-----------+ x | + // | if.then.BB | | | + // +--------------------+ | | + // | | | + // +--------v-----------<---/ | + // | latch >----------/ + // | with newbound1 | + // +--------------------+ + // | + // +--------v-----------+ + // | preheader2 |--------------\ + // | if (orig bound > | | + // | newbound1) | | + // +--------------------+ | + // | /----------------\ | + // +--------v----v------+ | | + // | header2 |---\ | | + // | iv starts with | | | | + // | newbound1 | | | | + // | conditional branch | | | | + // |with false condition| | | | + // +--------------------+ | | | + // x | | | + // +--------v-----------+ | | | + // | if.then.BB2 | | | | + // +--------------------+ | | | + // | | | | + // +--------v-----------<---/ | | + // | latch2 >----------/ | + // | with newbound2 | | + // +--------v-----------+ | + // | | + // | +---------------+ | + // +--> exit <-------/ + // +---------------+ + SCEVExpander Expander( + SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split"); + BasicBlock *PreHeader = L.getLoopPreheader(); + BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI); + Instruction *InsertPt = SplitLoopPH->getTerminator(); + + // Let's create second loop. + SmallVector SecondLoopBlocks; + Loop *SecondLoop; + ValueToValueMapTy VMap; + SecondLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap, + ".split", &LI, &DT, SecondLoopBlocks); + remapInstructionsInBlocks(SecondLoopBlocks, VMap); + + // Calculate new loop bounds and add them into preheader of first loop which + // is orignial loop. + const SCEV *NewBound1 = + ICmpInst::isSigned(SplitCandidateCond.Pred) + ? SE.getSMinExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV) + : SE.getUMinExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV); + const SCEV *NewBound2 = + ICmpInst::isSigned(SplitCandidateCond.Pred) + ? SE.getSMaxExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV) + : SE.getUMaxExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV); + + Value *NewBound1Value = + Expander.expandCodeFor(NewBound1, NewBound1->getType(), InsertPt); + Value *NewBound2Value = + Expander.expandCodeFor(NewBound2, NewBound2->getType(), InsertPt); + NewBound1Value->setName("new.bound1"); + NewBound2Value->setName("new.bound2"); + + // Add conditional branch to check we can skip second loop in its preheader. + BasicBlock *SecondLoopPreHeader = SecondLoop->getLoopPreheader(); + IRBuilder<> Builder(SecondLoopPreHeader); + Instruction *OrigBI = SecondLoopPreHeader->getTerminator(); + ICmpInst::Predicate Pred = ICmpInst::isSigned(SplitCandidateCond.Pred) + ? ICmpInst::ICMP_SGE + : ICmpInst::ICMP_UGE; + Value *Cond = + Builder.CreateICmp(Pred, NewBound1Value, ExitingCond.BoundValue); + Builder.CreateCondBr(Cond, SecondLoop->getExitBlock(), + SecondLoop->getHeader()); + OrigBI->eraseFromParent(); + + // Replace exiting bound value of first loop, which is original loop, by + // NewBound1. + if (ExitingCond.OpsSwapped) + ExitingCond.ICmp->setOperand(0, NewBound1Value); + else + ExitingCond.ICmp->setOperand(1, NewBound1Value); + + // Replace IV's start value of second loop by NewBound1. + for (PHINode &PN : L.getHeader()->phis()) { + // Find PHI with exiting condition from first loop. + if (isa(SE.getSCEV(&PN))) { + for (Value *Op : PN.incoming_values()) { + if (Op == ExitingCond.AddRecValue) { + // Find cloned PHI for second loop. + PHINode *SecondLoopPN = cast(VMap[&PN]); + SecondLoopPN->setIncomingValueForBlock(SecondLoopPreHeader, + NewBound1Value); + } + } + } + } + + // Replace SplitCandidateCond.BI's condition of first loop, which is original + // loop, by True. + LLVMContext &Context = PreHeader->getContext(); + SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context)); + + // Replace cloned SplitCandidateCond.BI's condition in second loop by False. + BranchInst *ClonedSplitCandidateBI = + cast(VMap[SplitCandidateCond.BI]); + ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context)); + + // Replace exit branch target of first loop, which is original loop, by second + // loop's preheader. + if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0)) + ExitingCond.BI->setSuccessor(0, SecondLoopPreHeader); + else + ExitingCond.BI->setSuccessor(1, SecondLoopPreHeader); + + // Update dominator tree. + DT.changeImmediateDominator(SecondLoopPreHeader, L.getExitingBlock()); + DT.changeImmediateDominator(SecondLoop->getExitBlock(), SecondLoopPreHeader); + + // 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(*SecondLoop, DT, &LI, &SE); + simplifyLoop(SecondLoop, &DT, &LI, &SE, nullptr, nullptr, true); + + // Add new second loop to loop pass manager. + U.addSiblingLoops(SecondLoop); + + return true; +} + +PreservedAnalyses SimpleLoopBoundSplitPass::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/SimpleLoopBoundSplit/simple-loop-bound-split.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/SimpleLoopBoundSplit/simple-loop-bound-split.ll @@ -0,0 +1,369 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=simple-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:%.*]] +; 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 sgt 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 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: [[NEW_BOUND1:%.*]] = call i64 @llvm.smin.i64(i64 [[N:%.*]], i64 [[A:%.*]]) +; CHECK-NEXT: [[NEW_BOUND2:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 [[A]]) +; 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 [[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 eq i64 [[INC]], [[NEW_BOUND1]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP_PH_SPLIT_SPLIT:%.*]], label [[LOOP]] +; CHECK: loop.ph.split.split: +; CHECK-NEXT: [[TMP0:%.*]] = icmp sge i64 [[NEW_BOUND1]], [[N]] +; CHECK-NEXT: br i1 [[TMP0]], label [[EXIT:%.*]], label [[LOOP_SPLIT_PREHEADER:%.*]] +; 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_BOUND1]], [[LOOP_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]] +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], 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 %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 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: [[NEW_BOUND1:%.*]] = call i64 @llvm.smin.i64(i64 [[N:%.*]], i64 [[A:%.*]]) +; CHECK-NEXT: [[NEW_BOUND2:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 [[A]]) +; 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 [[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 sge i64 [[INC]], [[NEW_BOUND1]] +; CHECK-NEXT: br i1 [[COND]], label [[LOOP_PH_SPLIT_SPLIT:%.*]], label [[LOOP]] +; CHECK: loop.ph.split.split: +; CHECK-NEXT: [[TMP0:%.*]] = icmp sge i64 [[NEW_BOUND1]], [[N]] +; CHECK-NEXT: br i1 [[TMP0]], label [[EXIT:%.*]], label [[LOOP_SPLIT_PREHEADER:%.*]] +; 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_BOUND1]], [[LOOP_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]] +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], 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 %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 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:%.*]] +; 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]], 2 +; CHECK-NEXT: [[COND:%.*]] = icmp sgt 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, 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 @@ -79,6 +79,7 @@ "ScalarizeMaskedMemIntrin.cpp", "Scalarizer.cpp", "SeparateConstOffsetFromGEP.cpp", + "SimpleLoopBoundSplit.cpp", "SimpleLoopUnswitch.cpp", "SimplifyCFGPass.cpp", "Sink.cpp",