Index: lib/Transforms/Utils/SimplifyIndVar.cpp =================================================================== --- lib/Transforms/Utils/SimplifyIndVar.cpp +++ lib/Transforms/Utils/SimplifyIndVar.cpp @@ -21,10 +21,12 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -48,6 +50,7 @@ Loop *L; LoopInfo *LI; ScalarEvolution *SE; + const DominatorTree *DT = nullptr; // may be null! SmallVectorImpl &DeadInsts; @@ -55,8 +58,9 @@ public: SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LoopInfo *LI, + const DominatorTree* DT, SmallVectorImpl &Dead, IVUsers *IVU = nullptr) - : L(Loop), LI(LI), SE(SE), DeadInsts(Dead), Changed(false) { + : L(Loop), LI(LI), SE(SE), DT(DT), DeadInsts(Dead), Changed(false) { assert(LI && "IV simplification requires LoopInfo"); } @@ -146,6 +150,53 @@ return IVSrc; } +static bool IsStrictlyIncreasing(ScalarEvolution *SE, + const SCEVAddRecExpr *AddRecS) { + if (SCEV::FlagNSW & AddRecS->getNoWrapFlags()) { + const SCEV *Step = AddRecS->getStepRecurrence(*SE); + if (SE->isKnownPositive(Step)) + return true; + } + return false; +} + +static bool DominatesBackedges(Instruction *I, Loop *L, + const DominatorTree &DT) { + + SmallVector Latches; + L->getLoopLatches(Latches); + + // Verify that this instuction must execute if any backedge does + for (BasicBlock *Latch : Latches) + if (!DT.dominates(I->getParent(), Latch)) { + return false; + } + + return true; +} + +/// Returns true if the given comparison is used by a branch which is known to +/// exit the loop if the value is true, and that branch is known to execute on +/// the first iteration if the loop executes at all. +static bool ControlsExitOnFirstIteration(ICmpInst *ICmp, Loop *L, + const DominatorTree &DT) { + // Avoid walking uses if we can cheaply tell ICmp's uses can't dominate all + // backedges. + if (!DominatesBackedges(ICmp, L, DT)) + return false; + for (User *U : ICmp->users()) { + auto *BI = dyn_cast(U); + if (!BI || BI->isUnconditional()) + continue; + if (L->contains(BI->getSuccessor(0))) + continue; + if (DominatesBackedges(BI, L, DT)) + return true; + } + return false; +} + + /// SimplifyIVUsers helper for eliminating useless /// comparisons against an induction variable. void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { @@ -173,9 +224,38 @@ ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); - else + else if (auto *AddRecS = dyn_cast(S)) { + // If we have a conditional loop exit which is controlled by a SLT or SLE + // comparison on a strictly increasing induction variable, we know that the + // exit must be taken on the first iteration it executes, or not at all. + // This transformation is currently limited to when we can prove that the + // conditional exit executes on the first iteration of the loop so that we + // can convert the guard to a loop invariant one on the entry value of + // induction variable. This results in a guard which is easily unswitched + // by LoopUnswitch. The generalized case requiring loop iteration space + // splitting is handled by IRCE. + // TODO: handle ULT, ULE comparisons + // TODO: extend this to strictly decreasing loops + if ((Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) && + IsStrictlyIncreasing(SE, AddRecS) && + DT && ControlsExitOnFirstIteration(ICmp, L, *DT)) { + const SCEV *Start = AddRecS->getStart(); + assert(SE->isLoopInvariant(Start, L)); + const DataLayout &DL = ICmp->getModule()->getDataLayout(); + SCEVExpander Expander(*SE, DL, "indvarsi"); + Value *V = Expander.expandCodeFor(Start, IVOperand->getType(), + L->getLoopPreheader()->getTerminator()); + DEBUG(dbgs() << "INDVARS: Converting loop variant check " << *ICmp + << " to loop invariant\n"); + ICmp->replaceUsesOfWith(IVOperand, V); + ++NumElimCmp; + Changed = true; + } + // Don't fall through into the code to eliminate the comparison entirely, + // we haven't met it's preconditions. + return; + } else return; - DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); ++NumElimCmp; Changed = true; @@ -466,7 +546,7 @@ if (UseInst == CurrIV) continue; if (V && V->shouldSplitOverflowInstrinsics()) { - UseInst = splitOverflowIntrinsic(UseInst, V->getDomTree()); + UseInst = splitOverflowIntrinsic(UseInst, DT); if (!UseInst) continue; } @@ -518,7 +598,8 @@ SmallVectorImpl &Dead, IVVisitor *V) { LoopInfo *LI = &LPM->getAnalysis().getLoopInfo(); - SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LI, Dead); + const DominatorTree *DT = V ? V->getDomTree() : nullptr; + SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LI, DT, Dead); SIV.simplifyUsers(CurrIV, V); return SIV.hasChanged(); } Index: test/Transforms/IndVarSimplify/strictly-increasing.ll =================================================================== --- /dev/null +++ test/Transforms/IndVarSimplify/strictly-increasing.ll @@ -0,0 +1,132 @@ +; RUN: opt -S -indvars %s | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @test1(i64 %start) { +; CHECK-LABEL: @test1 +entry: + br label %loop + +loop: + %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] + %indvars.iv.next = add nsw i64 %indvars.iv, 1 +; CHECK: %cmp1 = icmp slt i64 %start, -1 + %cmp1 = icmp slt i64 %indvars.iv, -1 + br i1 %cmp1, label %for.end, label %loop + +for.end: ; preds = %if.end, %entry + ret void +} + +define void @test2(i64 %start) { +; CHECK-LABEL: @test2 +entry: + br label %loop + +loop: + %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] + %indvars.iv.next = add nsw i64 %indvars.iv, 1 +; CHECK: %cmp1 = icmp sle i64 %start, -1 + %cmp1 = icmp sle i64 %indvars.iv, -1 + br i1 %cmp1, label %for.end, label %loop + +for.end: ; preds = %if.end, %entry + ret void +} + +; As long as the test dominates the backedge, we're good +define void @test3(i64 %start) { +; CHECK-LABEL: @test3 +entry: + br label %loop + +loop: + %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] + %indvars.iv.next = add nsw i64 %indvars.iv, 1 + %cmp = icmp eq i64 %indvars.iv.next, 25 + br i1 %cmp, label %backedge, label %for.end + +backedge: + ; prevent flattening, needed to make sure we're testing what we intend + call void @foo() +; CHECK: %cmp1 = icmp slt i64 %start, -1 + %cmp1 = icmp slt i64 %indvars.iv, -1 + br i1 %cmp1, label %for.end, label %loop + +for.end: ; preds = %if.end, %entry + ret void +} + +; Negative test - we can't show that the internal branch executes, so we can't +; fold the test to a loop invariant one. +define void @test4_neg(i64 %start) { +; CHECK-LABEL: @test4_neg +entry: + br label %loop + +loop: + %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] + %indvars.iv.next = add nsw i64 %indvars.iv, 1 + %cmp = icmp eq i64 %indvars.iv.next, 25 + br i1 %cmp, label %backedge, label %skip +skip: + ; prevent flattening, needed to make sure we're testing what we intend + call void @foo() +; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 + %cmp1 = icmp slt i64 %indvars.iv, -1 + br i1 %cmp1, label %for.end, label %backedge +backedge: + ; prevent flattening, needed to make sure we're testing what we intend + call void @foo() + br label %loop + +for.end: ; preds = %if.end, %entry + ret void +} + +; Slightly subtle version of @test4 where the icmp dominates the backedge, +; but the exit branch doesn't. +define void @test5_neg(i64 %start) { +; CHECK-LABEL: @test5_neg +entry: + br label %loop + +loop: + %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ] + %indvars.iv.next = add nsw i64 %indvars.iv, 1 + %cmp = icmp eq i64 %indvars.iv.next, 25 +; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 + %cmp1 = icmp slt i64 %indvars.iv, -1 + br i1 %cmp, label %backedge, label %skip +skip: + ; prevent flattening, needed to make sure we're testing what we intend + call void @foo() + br i1 %cmp1, label %for.end, label %backedge +backedge: + ; prevent flattening, needed to make sure we're testing what we intend + call void @foo() + br label %loop + +for.end: ; preds = %if.end, %entry + ret void +} + +; The branch has to exit the loop if the condition is true +define void @test6_neg(i64 %start) { +; CHECK-LABEL: @test6_neg +entry: + br label %loop + +loop: + %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ] + %indvars.iv.next = add nsw i64 %indvars.iv, 1 +; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1 + %cmp1 = icmp slt i64 %indvars.iv, -1 + br i1 %cmp1, label %loop, label %for.end + +for.end: ; preds = %if.end, %entry + ret void +} + + +declare void @foo()