Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -48,6 +48,7 @@ class LoopInfo; class Operator; class SCEVUnknown; + class SCEVAddRecExpr; class SCEV; template<> struct FoldingSetTrait; @@ -578,6 +579,22 @@ bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, const Loop *L); + /// Is the predicate "LHS `Pred` X" monotonically increasing (going from + /// false to true) or monotonically decreasing (going from true to false) + /// for all X? + /// + /// In other words, if isMonotonicPredicate returns true then for all + /// (loop-invariant) X then: + /// + /// Increasing is true -> Once LHS `Pred` X is true then it remains true + /// for all future iterations + /// + /// Increasing is false -> Once LHS `Pred` X is false then it remains + /// false for all future iterations + /// + bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred, bool &Increasing); + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -899,6 +916,15 @@ bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// Can the predicate LHS `Pred` RHS be rewritten into a predicate that is + /// loop invariant? If so, return true and set Invariant{Pred|LHS|RHS} to + /// that predicate. + bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS, const Loop *L, + ICmpInst::Predicate &InvariantPred, + const SCEV *&InvariantLHS, + const SCEV *&InvariantRHS); + /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with /// predicate Pred. Return true iff any changes were made. If the /// operands are provably equal or unequal, LHS and RHS are set to Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -6616,6 +6616,103 @@ return isKnownPredicateWithRanges(Pred, LHS, RHS); } +bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred, + bool &Increasing) { + switch (Pred) { + default: + break; + + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: + if (LHS->getNoWrapFlags(SCEV::FlagNUW) && + isKnownNonNegative(LHS->getStepRecurrence(*this))) { + Increasing = true; + return true; + } + break; + + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_SGE: + if (LHS->getNoWrapFlags(SCEV::FlagNSW)) { + if (isKnownNonNegative(LHS->getStepRecurrence(*this))) { + Increasing = true; + return true; + } + if (isKnownNonPositive(LHS->getStepRecurrence(*this))) { + Increasing = false; + return true; + } + } + break; + + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_SLE: + if (LHS->getNoWrapFlags(SCEV::FlagNSW)) { + if (isKnownNonPositive(LHS->getStepRecurrence(*this))) { + Increasing = true; + return true; + } + if (isKnownNonNegative(LHS->getStepRecurrence(*this))) { + Increasing = false; + return true; + } + } + break; + } + + return false; // Conservative answer +} + +bool ScalarEvolution::isLoopInvariantPredicate( + ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, + ICmpInst::Predicate &InvariantPred, const SCEV *&InvariantLHS, + const SCEV *&InvariantRHS) { + + // If there is a loop-invariant, force it into the RHS, otherwise bail out. + if (!isLoopInvariant(RHS, L)) { + if (!isLoopInvariant(LHS, L)) + return false; + + std::swap(LHS, RHS); + Pred = ICmpInst::getSwappedPredicate(Pred); + } + + const SCEVAddRecExpr *ArLHS = dyn_cast(LHS); + if (!ArLHS || ArLHS->getLoop() != L) + return false; + + bool Increasing; + if (isMonotonicPredicate(ArLHS, Pred, Increasing)) { + // If the predicate "ArLHS `Pred` RHS" monotonically increases from false to + // true as the loop iterates, and the backedge is control dependent on + // "ArLHS `Pred` RHS" == true then we can reason as follows: + // + // * if the predicate was false in the first iteration then the predicate + // is never evaluated again, since the loop exits without taking the + // backedge. + // * if the predicate was true in the first iteration then it will + // continue to be true for all future iterations since it is + // monotonically increasing. + // + // For both the above possibilities, we can replace the loop varying + // predicate with its value on the first iteration of the loop (which is + // loop invariant). + // + // A similar reasoning applies for a monotonically decreasing predicate. + + auto P = Increasing ? Pred : ICmpInst::getInversePredicate(Pred); + if (isLoopBackedgeGuardedByCond(L, P, LHS, RHS)) { + InvariantPred = Pred; + InvariantLHS = ArLHS->getStart(); + InvariantRHS = RHS; + return true; + } + } + + return false; +} + bool ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { Index: lib/Transforms/Utils/SimplifyIndVar.cpp =================================================================== --- lib/Transforms/Utils/SimplifyIndVar.cpp +++ lib/Transforms/Utils/SimplifyIndVar.cpp @@ -166,19 +166,63 @@ S = SE->getSCEVAtScope(S, ICmpLoop); X = SE->getSCEVAtScope(X, ICmpLoop); + ICmpInst::Predicate InvariantPredicate; + const SCEV *InvariantLHS, *InvariantRHS; + + const char *Verb = nullptr; + // If the condition is always true or always false, replace it with // a constant value. - if (SE->isKnownPredicate(Pred, S, X)) + if (SE->isKnownPredicate(Pred, S, X)) { ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); - else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) + DeadInsts.emplace_back(ICmp); + Verb = "Eliminated"; + } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) { ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); - else + DeadInsts.emplace_back(ICmp); + Verb = "Eliminated"; + } else if (isa(IVOperand) && + SE->isLoopInvariantPredicate(Pred, S, X, ICmpLoop, + InvariantPredicate, InvariantLHS, + InvariantRHS)) { + + // Rewrite the comparision to a loop invariant comparision if it can be done + // cheaply, where cheaply means "we don't need to emit any new + // instructions". + + Value *NewLHS = nullptr, *NewRHS = nullptr; + + if (S == InvariantLHS || X == InvariantLHS) + NewLHS = + ICmp->getOperand(S == InvariantLHS ? IVOperIdx : (1 - IVOperIdx)); + + if (S == InvariantRHS || X == InvariantRHS) + NewRHS = + ICmp->getOperand(S == InvariantRHS ? IVOperIdx : (1 - IVOperIdx)); + + for (Value *Incoming : cast(IVOperand)->incoming_values()) { + if (!NewLHS && SE->getSCEV(Incoming) == InvariantLHS) + NewLHS = Incoming; + if (!NewRHS && SE->getSCEV(Incoming) == InvariantRHS) + NewRHS = Incoming; + } + + if (!NewLHS || !NewRHS) + // We could not find an existing value to replace either LHS or RHS. + // Generating new instructions has subtler tradeoffs, so avoid doing that + // for now. + return; + + Verb = "Simplified"; + ICmp->setPredicate(InvariantPredicate); + ICmp->setOperand(0, NewLHS); + ICmp->setOperand(1, NewRHS); + } else return; - DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); + DEBUG(dbgs() << "INDVARS: " << Verb << " comparison: " << *ICmp << '\n'); ++NumElimCmp; Changed = true; - DeadInsts.emplace_back(ICmp); } /// SimplifyIVUsers helper for eliminating useless Index: test/Transforms/IndVarSimplify/loop-invariant-conditions.ll =================================================================== --- /dev/null +++ test/Transforms/IndVarSimplify/loop-invariant-conditions.ll @@ -0,0 +1,178 @@ +; 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 +} + +define void @test4(i64 %start) { +; CHECK-LABEL: @test4 +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 sgt i64 %start, -1 + %cmp1 = icmp sgt i64 %indvars.iv, -1 + br i1 %cmp1, label %loop, label %for.end + +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 @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 + 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 @test6_neg(i64 %start) { +; CHECK-LABEL: @test6_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 @test7_neg(i64 %start) { +; CHECK-LABEL: @test7_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 +} + +define void @test8_neg(i64 %start) { +; CHECK-LABEL: @test8_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 %for.end + +backedge: + ; prevent flattening, needed to make sure we're testing what we intend + call void @foo() +; CHECK: %cmp1 = icmp sgt i64 %indvars.iv, -1 + %cmp1 = icmp sgt i64 %indvars.iv, -1 + +; %cmp1 can be made loop invariant only if the branch below goes to +; %the header when %cmp1 is true. + br i1 %cmp1, label %for.end, label %loop + +for.end: ; preds = %if.end, %entry + ret void +} + +declare void @foo()