diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -228,6 +228,7 @@ void initializeLocalStackSlotPassPass(PassRegistry&); void initializeLocalizerPass(PassRegistry&); void initializeLoopAccessLegacyAnalysisPass(PassRegistry&); +void initializeLoopEliminateImpliedConditionsLegacyPassPass(PassRegistry &); void initializeLoopDataPrefetchLegacyPassPass(PassRegistry&); void initializeLoopDeletionLegacyPassPass(PassRegistry&); void initializeLoopDistributeLegacyPass(PassRegistry&); diff --git a/llvm/include/llvm/Transforms/Scalar.h b/llvm/include/llvm/Transforms/Scalar.h --- a/llvm/include/llvm/Transforms/Scalar.h +++ b/llvm/include/llvm/Transforms/Scalar.h @@ -147,6 +147,7 @@ // frequency is lower than loop preheader. // Pass *createLoopSinkPass(); +Pass *createLoopEliminateImpliedConditionsPass(); //===----------------------------------------------------------------------===// // diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -3527,8 +3527,8 @@ // flow and the no-overflow bits may not be valid for the expression in any // context. This can be fixed similarly to how these flags are handled for // adds. - SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW - : SCEV::FlagAnyWrap; + SCEV::NoWrapFlags Wrap = + GEP->isInBounds() ? SCEV::FlagNUW : SCEV::FlagAnyWrap; const SCEV *TotalOffset = getZero(IntIdxTy); Type *CurTy = GEP->getType(); diff --git a/llvm/lib/Transforms/Scalar/CMakeLists.txt b/llvm/lib/Transforms/Scalar/CMakeLists.txt --- a/llvm/lib/Transforms/Scalar/CMakeLists.txt +++ b/llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -26,6 +26,7 @@ LoopAccessAnalysisPrinter.cpp LoopSink.cpp LoopDeletion.cpp + LoopEliminateImpliedConditions.cpp LoopDataPrefetch.cpp LoopDistribute.cpp LoopFuse.cpp diff --git a/llvm/lib/Transforms/Scalar/LoopEliminateImpliedConditions.cpp b/llvm/lib/Transforms/Scalar/LoopEliminateImpliedConditions.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Scalar/LoopEliminateImpliedConditions.cpp @@ -0,0 +1,165 @@ +//===-------- LoopEliminateImpliedConditions.cpp - Eliminate Conds --------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file implements a pass to remove conditions inside a loop that can be +// proven to be true/false based on conditions outside the loop. +// +//===----------------------------------------------------------------------===// + +#include "llvm/InitializePasses.h" + +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +using namespace llvm; +using namespace llvm::PatternMatch; + +#define DEBUG_TYPE "loop-eic" + +STATISTIC(EliminatedConditions, "Number eliminated conditions"); + +static bool eliminateImpliedConditons(Loop &L, ScalarEvolution &SE) { + SmallPtrSet KnownTrue; + SmallPtrSet KnownFalse; + + for (BasicBlock *BB : L.blocks()) { + for (Instruction &I : *BB) { + Value *RightVal; + Instruction *LeftI; + CmpInst::Predicate Pred; + if (!match(&I, m_ICmp(Pred, m_Instruction(LeftI), m_Value(RightVal)))) + continue; + + if (!SE.isSCEVable(LeftI->getType())) + continue; + const SCEV *LeftSCEV = SE.getSCEV(LeftI); + const SCEV *RightSCEV = SE.getSCEV(RightVal); + + // Check if we have a condition with one AddRec and one non AddRec + // expression. Normalize LeftSCEV to be the AddRec. + if (!isa(LeftSCEV)) { + if (isa(RightSCEV)) { + std::swap(LeftSCEV, RightSCEV); + Pred = ICmpInst::getSwappedPredicate(Pred); + } else + continue; + } + + if (!SE.isAvailableAtLoopEntry(RightSCEV, &L)) + continue; + + const SCEVAddRecExpr *LeftAR = cast(LeftSCEV); + + // Avoid huge SCEV computations , make sure we only consider AddRecs of + // the current loop. + if (!LeftAR->isAffine() || LeftAR->getLoop() != &L) + continue; + + // Use our own monotonic predicate check, because SCEV currently cannot + // deduce NUW/NSW based on a context instruction. + // TODO: allow ScalarEvolution::isMonotonicPredicate to take a context + // instruction. + auto IsMonotonicPred = [&](Instruction *LeftI, const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred) -> Optional { + switch (Pred) { + default: + return None; // Conservative answer + + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_ULE: + if (!LHS->hasNoUnsignedWrap()) { + bool UB = programUndefinedIfPoison(LeftI); + bool Succ = isGuaranteedToTransferExecutionToSuccessor(LeftI); + if (!isa(LeftI) || + !LeftI->hasNoUnsignedWrap() || !UB || !Succ) + return None; + } + + bool Increasing = + Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE; + return {Increasing}; + } + }; + Optional MaybeMonotonic = IsMonotonicPred(LeftI, LeftAR, Pred); + if (!MaybeMonotonic) + continue; + + const SCEV *BTC = + SE.getBackedgeTakenCount(&L, ScalarEvolution::ConstantMaximum); + if (isa(BTC)) + continue; + const SCEV *FirstIter = LeftAR->evaluateAtIteration( + SE.getConstant(LeftSCEV->getType(), 0), SE); + const SCEV *LastIter = LeftAR->evaluateAtIteration(BTC, SE); + auto *Sub = SE.getMinusSCEV(LastIter, FirstIter, SCEV::FlagNUW); + bool LastIterValueValid = SE.isKnownNonNegative(Sub); + + if (*MaybeMonotonic && + SE.isLoopEntryGuardedByCond(&L, Pred, FirstIter, RightSCEV)) + KnownTrue.insert(&I); + else if (LastIterValueValid && !*MaybeMonotonic && + SE.isLoopEntryGuardedByCond(&L, Pred, LastIter, RightSCEV)) + KnownTrue.insert(&I); + } + } + for (Value *V : KnownTrue) + V->replaceAllUsesWith(ConstantInt::getTrue(L.getHeader()->getContext())); + for (Value *V : KnownFalse) + V->replaceAllUsesWith(ConstantInt::getFalse(L.getHeader()->getContext())); + + EliminatedConditions += KnownTrue.size(); + EliminatedConditions += KnownFalse.size(); + return true; +} +namespace { + +class LoopEliminateImpliedConditionsLegacyPass : public LoopPass { +public: + static char ID; // Pass ID, replacement for typeid + + LoopEliminateImpliedConditionsLegacyPass() : LoopPass(ID) { + initializeLoopEliminateImpliedConditionsLegacyPassPass( + *PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + ScalarEvolution &SE = getAnalysis().getSE(); + return eliminateImpliedConditons(*L, SE); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + getLoopAnalysisUsage(AU); + } +}; + +} // end anonymous namespace + +char LoopEliminateImpliedConditionsLegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(LoopEliminateImpliedConditionsLegacyPass, "loop-eic", + "Simplify instructions in loops", false, false) +INITIALIZE_PASS_DEPENDENCY(LoopPass) +INITIALIZE_PASS_END(LoopEliminateImpliedConditionsLegacyPass, "loop-eic", + "Simplify instructions in loops", false, false) + +Pass *llvm::createLoopEliminateImpliedConditionsPass() { + return new LoopEliminateImpliedConditionsLegacyPass(); +} diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -62,6 +62,7 @@ initializeJumpThreadingPass(Registry); initializeLegacyLICMPassPass(Registry); initializeLegacyLoopSinkPassPass(Registry); + initializeLoopEliminateImpliedConditionsLegacyPassPass(Registry); initializeLoopFuseLegacyPass(Registry); initializeLoopDataPrefetchLegacyPassPass(Registry); initializeLoopDeletionLegacyPassPass(Registry); diff --git a/llvm/test/Transforms/LoopEliminateImpliedConditions/crashes.ll b/llvm/test/Transforms/LoopEliminateImpliedConditions/crashes.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopEliminateImpliedConditions/crashes.ll @@ -0,0 +1,187 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -loop-eic -S %s | FileCheck %s + +define void @not_overflowing_binop1(i8* %Start, i8* %FirstChar) { +; CHECK-LABEL: @not_overflowing_binop1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[POS_ADDR_153:%.*]] = phi i8* [ [[ARRAYIDX13:%.*]], [[LOOP]] ], [ [[START:%.*]], [[ENTRY:%.*]] ] +; CHECK-NEXT: [[ARRAYIDX13]] = getelementptr inbounds i8, i8* [[POS_ADDR_153]], i64 -1 +; CHECK-NEXT: [[CMP25:%.*]] = icmp ugt i8* [[ARRAYIDX13]], [[FIRSTCHAR:%.*]] +; CHECK-NEXT: br i1 [[CMP25]], label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop + +loop: + %Pos.addr.153 = phi i8* [ %arrayidx13, %loop ], [ %Start, %entry ] + %arrayidx13 = getelementptr inbounds i8, i8* %Pos.addr.153, i64 -1 + %cmp25 = icmp ugt i8* %arrayidx13, %FirstChar + br i1 %cmp25, label %exit, label %loop + +exit: ; preds = %entry + ret void +} + +define void @not_overflowing_binop2() { +; CHECK-LABEL: @not_overflowing_binop2( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[IV_MUL:%.*]] = mul i64 [[IV]], 3 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[MUL_TRUNC:%.*]] = trunc i64 [[IV_MUL]] to i32 +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[MUL_TRUNC]], -1 +; CHECK-NEXT: [[COND:%.*]] = icmp ult i32 [[XOR]], undef +; CHECK-NEXT: br i1 [[COND]], label [[BB:%.*]], label [[LOOP_LATCH]] +; CHECK: bb: +; CHECK-NEXT: br label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: [[EXIT_COND:%.*]] = icmp eq i64 [[IV_NEXT]], 30 +; CHECK-NEXT: br i1 [[EXIT_COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop + +loop: ; preds = %for.body626.us, %entry + %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ] + %iv.mul = mul i64 %iv, 3 + %iv.next = add nuw nsw i64 %iv, 1 + %mul.trunc = trunc i64 %iv.mul to i32 + %xor = xor i32 %mul.trunc, -1 + %cond = icmp ult i32 %xor, undef + br i1 %cond, label %bb, label %loop.latch + +bb: + br label %loop.latch + +loop.latch: + %exit.cond = icmp eq i64 %iv.next, 30 + br i1 %exit.cond, label %loop, label %exit + +exit: + ret void +} + +define void @arg_not_scevable_1(<4 x i64> %a) { +; CHECK-LABEL: @arg_not_scevable_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_HEADER]] ] +; CHECK-NEXT: [[B:%.*]] = add nuw <4 x i64> [[A:%.*]], [[A]] +; CHECK-NEXT: [[VEC_COND:%.*]] = icmp ult <4 x i64> [[A]], +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXIT_COND:%.*]] = icmp eq i64 [[IV_NEXT]], 30 +; CHECK-NEXT: br i1 [[EXIT_COND]], label [[EXIT:%.*]], label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.header + +loop.header: + %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.header ] + %b = add nuw <4 x i64> %a, %a + %vec.cond = icmp ult <4 x i64> %a, + %iv.next = add nuw i64 %iv, 1 + %exit.cond = icmp eq i64 %iv.next, 30 + br i1 %exit.cond, label %exit, label %loop.header + +exit: + ret void +} + +define void @arg_not_scevable_2() { +; CHECK-LABEL: @arg_not_scevable_2( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[V:%.*]] = add <4 x i64> undef, undef +; CHECK-NEXT: [[VEC_COND:%.*]] = icmp ult <4 x i64> [[V]], +; CHECK-NEXT: br label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXIT_COND:%.*]] = icmp eq i64 [[IV_NEXT]], 30 +; CHECK-NEXT: br i1 [[EXIT_COND]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop + +loop: ; preds = %if.then28 + %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ] + %v = add <4 x i64> undef, undef + %vec.cond = icmp ult <4 x i64> %v, + br label %loop.latch + +loop.latch: ; preds = %for.inc37, %vector.body.preheader + %iv.next = add nuw i64 %iv, 1 + %exit.cond = icmp eq i64 %iv.next, 30 + br i1 %exit.cond, label %loop, label %exit + +exit: ; preds = %entry + ret void +} + + +define void @scev_could_not_compute() unnamed_addr #0 { +; CHECK-LABEL: @scev_could_not_compute( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[INDVARS_IV604:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT605:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[INDVARS_IV_NEXT605]] = add nuw nsw i64 [[INDVARS_IV604]], 1 +; CHECK-NEXT: [[CMP104:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT605]], undef +; CHECK-NEXT: br label [[LOOP]] +; CHECK: for.end252: +; CHECK-NEXT: ret void +; +entry: + br label %loop + +loop: + %indvars.iv604 = phi i64 [ 0, %entry ], [ %indvars.iv.next605, %loop ] + %indvars.iv.next605 = add nuw nsw i64 %indvars.iv604, 1 + %cmp104 = icmp ult i64 %indvars.iv.next605, undef + br label %loop + +for.end252: ; preds = %entry + ret void +} + +define void @not_available_at_entry(i64* %ptr) { +; CHECK-LABEL: @not_available_at_entry( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_BODY:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ] +; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[LV:%.*]] = load i64, i64* [[PTR:%.*]] +; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], [[LV]] +; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY]], label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.body + +for.body: ; preds = %for.body, %entry + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %lv = load i64, i64* %ptr + %cmp1 = icmp ult i64 %indvars.iv.next, %lv + br i1 %cmp1, label %for.body, label %for.end + +for.end: ; preds = %for.body + ret void +} + diff --git a/llvm/test/Transforms/LoopEliminateImpliedConditions/eliminate-integer-conds-true-nonconst-count.ll b/llvm/test/Transforms/LoopEliminateImpliedConditions/eliminate-integer-conds-true-nonconst-count.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopEliminateImpliedConditions/eliminate-integer-conds-true-nonconst-count.ll @@ -0,0 +1,148 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -loop-eic -S %s | FileCheck %s + +define i32 @test2(i64 %i, i64 %lower.bound, i64 %upper.bound, i64 %count, i32* %ptr) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[END:%.*]] = add nuw i64 [[I:%.*]], [[COUNT:%.*]] +; CHECK-NEXT: [[CMP:%.*]] = icmp uge i64 [[END]], [[UPPER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_TRAP:%.*]], label [[LOOP_HEADER_PREHEADER:%.*]] +; CHECK: loop.header.preheader: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: if.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[RED:%.*]] = phi i32 [ [[RED_NEXT:%.*]], [[LOOP_LATCH]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[C:%.*]] = add nuw i64 [[I]], [[IV]] +; CHECK-NEXT: [[CMP_LOWER:%.*]] = icmp uge i64 [[C]], [[LOWER_BOUND:%.*]] +; CHECK-NEXT: [[CMP_UPPER:%.*]] = icmp ult i64 [[C]], [[UPPER_BOUND]] +; CHECK-NEXT: [[COND_AND:%.*]] = and i1 [[CMP_LOWER]], [[CMP_UPPER]] +; CHECK-NEXT: br i1 [[COND_AND]], label [[LOOP_LATCH]], label [[LOOP_TRAP:%.*]] +; CHECK: loop.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR_I:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i64 [[IV]] +; CHECK-NEXT: [[LV:%.*]] = load i32, i32* [[PTR_I]], align 4 +; CHECK-NEXT: [[RED_NEXT]] = add nsw i32 [[LV]], [[RED]] +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV]], [[COUNT]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_EXIT:%.*]], label [[LOOP_HEADER]] +; CHECK: loop.exit: +; CHECK-NEXT: [[RED_LCSSA:%.*]] = phi i32 [ [[RED_NEXT]], [[LOOP_LATCH]] ] +; CHECK-NEXT: ret i32 [[RED_LCSSA]] +; +entry: + %end = add nuw i64 %i, %count + %cmp = icmp uge i64 %end, %upper.bound + br i1 %cmp, label %if.trap, label %loop.header + +if.trap: + tail call void @llvm.trap() + unreachable + +loop.header: + %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %entry ] + %red = phi i32 [ %red.next, %loop.latch ], [ 0, %entry ] + %c = add nuw i64 %i, %iv + %cmp.lower = icmp uge i64 %c, %lower.bound + %cmp.upper = icmp ult i64 %c, %upper.bound + %cond.and = and i1 %cmp.lower, %cmp.upper + br i1 %cond.and, label %loop.latch, label %loop.trap + +loop.trap: ; preds = %for.body + tail call void @llvm.trap() + unreachable + +loop.latch: ; preds = %for.body + %ptr.i = getelementptr i32, i32* %ptr, i64 %iv + %lv = load i32, i32* %ptr.i, align 4 + %red.next = add nsw i32 %lv, %red + %iv.next = add nuw i64 %iv, 1 + %exitcond = icmp eq i64 %iv, %count + br i1 %exitcond, label %loop.exit, label %loop.header + +loop.exit: ; preds = %if.end16, %for.cond.preheader + %red.lcssa = phi i32 [ %red.next, %loop.latch ] + ret i32 %red.lcssa +} + +define i32 @test3(i64 %i, i64 %lower.bound, i64 %upper.bound, i64 %count, i32* %ptr) { +; CHECK-LABEL: @test3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i64 [[I:%.*]], [[LOWER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_TRAP:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.else: +; CHECK-NEXT: [[END:%.*]] = add nuw i64 [[I]], [[COUNT:%.*]] +; CHECK-NEXT: [[CMP5:%.*]] = icmp uge i64 [[END]], [[UPPER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP5]], label [[IF_TRAP]], label [[LOOP_HEADER_PREHEADER:%.*]] +; CHECK: loop.header.preheader: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: if.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[RED:%.*]] = phi i32 [ [[RED_NEXT:%.*]], [[LOOP_LATCH]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[C:%.*]] = add nuw i64 [[I]], [[IV]] +; CHECK-NEXT: [[CMP_LOWER:%.*]] = icmp uge i64 [[C]], [[LOWER_BOUND]] +; CHECK-NEXT: [[CMP_UPPER:%.*]] = icmp ult i64 [[C]], [[UPPER_BOUND]] +; CHECK-NEXT: [[COND_AND:%.*]] = and i1 true, [[CMP_UPPER]] +; CHECK-NEXT: br i1 [[COND_AND]], label [[LOOP_LATCH]], label [[LOOP_TRAP:%.*]] +; CHECK: loop.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR_I:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i64 [[IV]] +; CHECK-NEXT: [[LV:%.*]] = load i32, i32* [[PTR_I]], align 4 +; CHECK-NEXT: [[RED_NEXT]] = add nsw i32 [[LV]], [[RED]] +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV]], [[COUNT]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_EXIT:%.*]], label [[LOOP_HEADER]] +; CHECK: loop.exit: +; CHECK-NEXT: [[RED_LCSSA:%.*]] = phi i32 [ [[RED_NEXT]], [[LOOP_LATCH]] ] +; CHECK-NEXT: ret i32 [[RED_LCSSA]] +; +entry: + %cmp = icmp ult i64 %i, %lower.bound + br i1 %cmp, label %if.trap, label %if.else + +if.else: + %end = add nuw i64 %i, %count + %cmp5 = icmp uge i64 %end, %upper.bound + br i1 %cmp5, label %if.trap, label %loop.header + + +if.trap: + tail call void @llvm.trap() + unreachable + +loop.header: + %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %if.else ] + %red = phi i32 [ %red.next, %loop.latch ], [ 0, %if.else] + %c = add nuw i64 %i, %iv + %cmp.lower = icmp uge i64 %c, %lower.bound + %cmp.upper = icmp ult i64 %c, %upper.bound + %cond.and = and i1 %cmp.lower, %cmp.upper + br i1 %cond.and, label %loop.latch, label %loop.trap + +loop.trap: ; preds = %for.body + tail call void @llvm.trap() + unreachable + +loop.latch: ; preds = %for.body + %ptr.i = getelementptr i32, i32* %ptr, i64 %iv + %lv = load i32, i32* %ptr.i, align 4 + %red.next = add nsw i32 %lv, %red + %iv.next = add nuw i64 %iv, 1 + %exitcond = icmp eq i64 %iv, %count + br i1 %exitcond, label %loop.exit, label %loop.header + +loop.exit: ; preds = %if.end16, %for.cond.preheader + %red.lcssa = phi i32 [ %red.next, %loop.latch ] + ret i32 %red.lcssa +} + +declare void @llvm.trap() #1 diff --git a/llvm/test/Transforms/LoopEliminateImpliedConditions/eliminate-integer-conds-true-trap.ll b/llvm/test/Transforms/LoopEliminateImpliedConditions/eliminate-integer-conds-true-trap.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopEliminateImpliedConditions/eliminate-integer-conds-true-trap.ll @@ -0,0 +1,214 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -loop-eic -S %s | FileCheck %s + +define i32 @test1(i64 %i, i64 %lower.bound, i64 %upper.bound, i32* %ptr) { +; CHECK-LABEL: @test1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i64 [[I:%.*]], [[LOWER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_TRAP:%.*]], label [[LOOP_HEADER_PREHEADER:%.*]] +; CHECK: loop.header.preheader: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: if.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[RED:%.*]] = phi i32 [ [[RED_NEXT:%.*]], [[LOOP_LATCH]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[C:%.*]] = add nuw i64 [[I]], [[IV]] +; CHECK-NEXT: [[CMP_LOWER:%.*]] = icmp uge i64 [[C]], [[LOWER_BOUND]] +; CHECK-NEXT: [[CMP_UPPER:%.*]] = icmp ult i64 [[C]], [[UPPER_BOUND:%.*]] +; CHECK-NEXT: [[COND_AND:%.*]] = and i1 true, [[CMP_UPPER]] +; CHECK-NEXT: br i1 [[COND_AND]], label [[LOOP_LATCH]], label [[LOOP_TRAP:%.*]] +; CHECK: loop.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR_I:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i64 [[IV]] +; CHECK-NEXT: [[LV:%.*]] = load i32, i32* [[PTR_I]], align 4 +; CHECK-NEXT: [[RED_NEXT]] = add nsw i32 [[LV]], [[RED]] +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 20 +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_EXIT:%.*]], label [[LOOP_HEADER]] +; CHECK: loop.exit: +; CHECK-NEXT: [[RED_LCSSA:%.*]] = phi i32 [ [[RED_NEXT]], [[LOOP_LATCH]] ] +; CHECK-NEXT: ret i32 [[RED_LCSSA]] +; +entry: + %cmp = icmp ult i64 %i, %lower.bound + br i1 %cmp, label %if.trap, label %loop.header + +if.trap: + tail call void @llvm.trap() + unreachable + +loop.header: + %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %entry ] + %red = phi i32 [ %red.next, %loop.latch ], [ 0, %entry ] + %c = add nuw i64 %i, %iv + %cmp.lower = icmp uge i64 %c, %lower.bound + %cmp.upper = icmp ult i64 %c, %upper.bound + %cond.and = and i1 %cmp.lower, %cmp.upper + br i1 %cond.and, label %loop.latch, label %loop.trap + +loop.trap: ; preds = %for.body + tail call void @llvm.trap() + unreachable + +loop.latch: ; preds = %for.body + %ptr.i = getelementptr i32, i32* %ptr, i64 %iv + %lv = load i32, i32* %ptr.i, align 4 + %red.next = add nsw i32 %lv, %red + %iv.next = add nuw i64 %iv, 1 + %exitcond = icmp eq i64 %iv.next, 20 + br i1 %exitcond, label %loop.exit, label %loop.header + +loop.exit: ; preds = %if.end16, %for.cond.preheader + %red.lcssa = phi i32 [ %red.next, %loop.latch ] + ret i32 %red.lcssa +} + +define i32 @test2(i64 %i, i64 %lower.bound, i64 %upper.bound, i32* %ptr) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[END:%.*]] = add nuw i64 [[I:%.*]], 19 +; CHECK-NEXT: [[CMP:%.*]] = icmp uge i64 [[END]], [[UPPER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_TRAP:%.*]], label [[LOOP_HEADER_PREHEADER:%.*]] +; CHECK: loop.header.preheader: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: if.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[RED:%.*]] = phi i32 [ [[RED_NEXT:%.*]], [[LOOP_LATCH]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[C:%.*]] = add nuw i64 [[I]], [[IV]] +; CHECK-NEXT: [[CMP_LOWER:%.*]] = icmp uge i64 [[C]], [[LOWER_BOUND:%.*]] +; CHECK-NEXT: [[CMP_UPPER:%.*]] = icmp ult i64 [[C]], [[UPPER_BOUND]] +; CHECK-NEXT: [[COND_AND:%.*]] = and i1 [[CMP_LOWER]], true +; CHECK-NEXT: br i1 [[COND_AND]], label [[LOOP_LATCH]], label [[LOOP_TRAP:%.*]] +; CHECK: loop.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR_I:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i64 [[IV]] +; CHECK-NEXT: [[LV:%.*]] = load i32, i32* [[PTR_I]], align 4 +; CHECK-NEXT: [[RED_NEXT]] = add nsw i32 [[LV]], [[RED]] +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 20 +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_EXIT:%.*]], label [[LOOP_HEADER]] +; CHECK: loop.exit: +; CHECK-NEXT: [[RED_LCSSA:%.*]] = phi i32 [ [[RED_NEXT]], [[LOOP_LATCH]] ] +; CHECK-NEXT: ret i32 [[RED_LCSSA]] +; +entry: + %end = add nuw i64 %i, 19 + %cmp = icmp uge i64 %end, %upper.bound + br i1 %cmp, label %if.trap, label %loop.header + +if.trap: + tail call void @llvm.trap() + unreachable + +loop.header: + %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %entry ] + %red = phi i32 [ %red.next, %loop.latch ], [ 0, %entry ] + %c = add nuw i64 %i, %iv + %cmp.lower = icmp uge i64 %c, %lower.bound + %cmp.upper = icmp ult i64 %c, %upper.bound + %cond.and = and i1 %cmp.lower, %cmp.upper + br i1 %cond.and, label %loop.latch, label %loop.trap + +loop.trap: ; preds = %for.body + tail call void @llvm.trap() + unreachable + +loop.latch: ; preds = %for.body + %ptr.i = getelementptr i32, i32* %ptr, i64 %iv + %lv = load i32, i32* %ptr.i, align 4 + %red.next = add nsw i32 %lv, %red + %iv.next = add nuw i64 %iv, 1 + %exitcond = icmp eq i64 %iv.next, 20 + br i1 %exitcond, label %loop.exit, label %loop.header + +loop.exit: ; preds = %if.end16, %for.cond.preheader + %red.lcssa = phi i32 [ %red.next, %loop.latch ] + ret i32 %red.lcssa +} + +define i32 @test3(i64 %i, i64 %lower.bound, i64 %upper.bound, i32* %ptr) { +; CHECK-LABEL: @test3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i64 [[I:%.*]], [[LOWER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[IF_TRAP:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.else: +; CHECK-NEXT: [[END:%.*]] = add nuw i64 [[I]], 19 +; CHECK-NEXT: [[CMP5:%.*]] = icmp uge i64 [[END]], [[UPPER_BOUND:%.*]] +; CHECK-NEXT: br i1 [[CMP5]], label [[IF_TRAP]], label [[LOOP_HEADER_PREHEADER:%.*]] +; CHECK: loop.header.preheader: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: if.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[RED:%.*]] = phi i32 [ [[RED_NEXT:%.*]], [[LOOP_LATCH]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[C:%.*]] = add nuw i64 [[I]], [[IV]] +; CHECK-NEXT: [[CMP_LOWER:%.*]] = icmp uge i64 [[C]], [[LOWER_BOUND]] +; CHECK-NEXT: [[CMP_UPPER:%.*]] = icmp ult i64 [[C]], [[UPPER_BOUND]] +; CHECK-NEXT: [[COND_AND:%.*]] = and i1 true, true +; CHECK-NEXT: br i1 [[COND_AND]], label [[LOOP_LATCH]], label [[LOOP_TRAP:%.*]] +; CHECK: loop.trap: +; CHECK-NEXT: tail call void @llvm.trap() +; CHECK-NEXT: unreachable +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR_I:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i64 [[IV]] +; CHECK-NEXT: [[LV:%.*]] = load i32, i32* [[PTR_I]], align 4 +; CHECK-NEXT: [[RED_NEXT]] = add nsw i32 [[LV]], [[RED]] +; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 20 +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_EXIT:%.*]], label [[LOOP_HEADER]] +; CHECK: loop.exit: +; CHECK-NEXT: [[RED_LCSSA:%.*]] = phi i32 [ [[RED_NEXT]], [[LOOP_LATCH]] ] +; CHECK-NEXT: ret i32 [[RED_LCSSA]] +; +entry: + %cmp = icmp ult i64 %i, %lower.bound + br i1 %cmp, label %if.trap, label %if.else + +if.else: + %end = add nuw i64 %i, 19 + %cmp5 = icmp uge i64 %end, %upper.bound + br i1 %cmp5, label %if.trap, label %loop.header + + +if.trap: + tail call void @llvm.trap() + unreachable + +loop.header: + %iv = phi i64 [ %iv.next, %loop.latch ], [ 0, %if.else ] + %red = phi i32 [ %red.next, %loop.latch ], [ 0, %if.else] + %c = add nuw i64 %i, %iv + %cmp.lower = icmp uge i64 %c, %lower.bound + %cmp.upper = icmp ult i64 %c, %upper.bound + %cond.and = and i1 %cmp.lower, %cmp.upper + br i1 %cond.and, label %loop.latch, label %loop.trap + +loop.trap: ; preds = %for.body + tail call void @llvm.trap() + unreachable + +loop.latch: ; preds = %for.body + %ptr.i = getelementptr i32, i32* %ptr, i64 %iv + %lv = load i32, i32* %ptr.i, align 4 + %red.next = add nsw i32 %lv, %red + %iv.next = add nuw i64 %iv, 1 + %exitcond = icmp eq i64 %iv.next, 20 + br i1 %exitcond, label %loop.exit, label %loop.header + +loop.exit: ; preds = %if.end16, %for.cond.preheader + %red.lcssa = phi i32 [ %red.next, %loop.latch ] + ret i32 %red.lcssa +} + +declare void @llvm.trap() #1 diff --git a/llvm/test/Transforms/LoopEliminateImpliedConditions/latch-condition.ll b/llvm/test/Transforms/LoopEliminateImpliedConditions/latch-condition.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopEliminateImpliedConditions/latch-condition.ll @@ -0,0 +1,38 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -loop-eic -S %s | FileCheck %s + + +; Make sure we do not eliminate the latch condition. +define void @test2(i16* %base, i16* %add.ptr, i64 %idx) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ADD_PTR19:%.*]] = getelementptr inbounds i16, i16* [[BASE:%.*]], i64 [[IDX:%.*]] +; CHECK-NEXT: [[CMP2171:%.*]] = icmp ult i16* [[ADD_PTR19]], [[ADD_PTR:%.*]] +; CHECK-NEXT: br i1 [[CMP2171]], label [[FOR_BODY23_PREHEADER:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body23.preheader: +; CHECK-NEXT: br label [[FOR_BODY23:%.*]] +; CHECK: for.body23: +; CHECK-NEXT: [[SP_172:%.*]] = phi i16* [ [[INCDEC_PTR27:%.*]], [[FOR_BODY23]] ], [ [[ADD_PTR19]], [[FOR_BODY23_PREHEADER]] ] +; CHECK-NEXT: [[INCDEC_PTR27]] = getelementptr inbounds i16, i16* [[SP_172]], i64 1 +; CHECK-NEXT: [[CMP21:%.*]] = icmp ult i16* [[INCDEC_PTR27]], [[ADD_PTR]] +; CHECK-NEXT: br i1 [[CMP21]], label [[FOR_BODY23]], label [[FOR_END_LOOPEXIT:%.*]] +; CHECK: for.end.loopexit: +; CHECK-NEXT: br label [[FOR_END]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + %add.ptr19 = getelementptr inbounds i16, i16* %base, i64 %idx + %cmp2171 = icmp ult i16* %add.ptr19, %add.ptr + br i1 %cmp2171, label %for.body23, label %for.end + +for.body23: ; preds = %while.end, %for.body23 + %sp.172 = phi i16* [ %incdec.ptr27, %for.body23 ], [ %add.ptr19, %entry ] + %incdec.ptr27 = getelementptr inbounds i16, i16* %sp.172, i64 1 + %cmp21 = icmp ult i16* %incdec.ptr27, %add.ptr + br i1 %cmp21, label %for.body23, label %for.end + +for.end: ; preds = %for.body23, %while.end +ret void +} +