Index: llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp +++ llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -39,6 +39,9 @@ STATISTIC( NumSimplifiedSDiv, "Number of IV signed division operations converted to unsigned division"); +STATISTIC( + NumSimplifiedSRem, + "Number of IV signed remainder operations converted to unsigned remainder"); STATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); namespace { @@ -77,8 +80,11 @@ bool eliminateOverflowIntrinsic(CallInst *CI); bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand); void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand); - void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand, - bool IsSigned); + void simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand, + bool IsSigned); + void replaceRemWithNumerator(BinaryOperator *Rem); + void replaceRemWithNumeratorOrZero(BinaryOperator *Rem); + void replaceSRemWithURem(BinaryOperator *Rem); bool eliminateSDiv(BinaryOperator *SDiv); bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand); bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand); @@ -309,54 +315,90 @@ return false; } -/// SimplifyIVUsers helper for eliminating useless -/// remainder operations operating on an induction variable. -void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem, - Value *IVOperand, - bool IsSigned) { +// i %s n -> i %u n if i >= 0 and n >= 0 +void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) { + auto *N = Rem->getOperand(0), *D = Rem->getOperand(1); + auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D, + Rem->getName() + ".urem", Rem); + Rem->replaceAllUsesWith(URem); + DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n'); + ++NumSimplifiedSRem; + DeadInsts.emplace_back(Rem); +} + +// i % n --> i if i is in [0,n). +void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) { + Rem->replaceAllUsesWith(Rem->getOperand(0)); + DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); + ++NumElimRem; + Changed = true; + DeadInsts.emplace_back(Rem); +} + +// (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). +void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) { + auto *T = Rem->getType(); + auto *N = Rem->getOperand(0), *D = Rem->getOperand(1); + ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, N, D); + SelectInst *Sel = + SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem); + Rem->replaceAllUsesWith(Sel); + DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); + ++NumElimRem; + Changed = true; + DeadInsts.emplace_back(Rem); +} + +/// SimplifyIVUsers helper for eliminating useless remainder operations +/// operating on an induction variable or replacing srem by urem. +void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem, Value *IVOperand, + bool IsSigned) { + auto *NValue = Rem->getOperand(0); + auto *DValue = Rem->getOperand(1); // We're only interested in the case where we know something about - // the numerator. - if (IVOperand != Rem->getOperand(0)) + // the numerator, unless it is a srem, because we want to replace srem by urem + // in general. + bool UsedAsNumerator = IVOperand == NValue; + if (!UsedAsNumerator && !IsSigned) return; - // Get the SCEVs for the ICmp operands. - const SCEV *S = SE->getSCEV(Rem->getOperand(0)); - const SCEV *X = SE->getSCEV(Rem->getOperand(1)); + const SCEV *N = SE->getSCEV(NValue); // Simplify unnecessary loops away. const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); - S = SE->getSCEVAtScope(S, ICmpLoop); - X = SE->getSCEVAtScope(X, ICmpLoop); + N = SE->getSCEVAtScope(N, ICmpLoop); - // i % n --> i if i is in [0,n). - if ((!IsSigned || SE->isKnownNonNegative(S)) && - SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, - S, X)) - Rem->replaceAllUsesWith(Rem->getOperand(0)); - else { - // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). - const SCEV *LessOne = SE->getMinusSCEV(S, SE->getOne(S->getType())); - if (IsSigned && !SE->isKnownNonNegative(LessOne)) - return; + bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N); + + // Do not proceed if the Numerator may be negative + if (!IsNumeratorNonNegative) + return; + + const SCEV *D = SE->getSCEV(DValue); + D = SE->getSCEVAtScope(D, ICmpLoop); - if (!SE->isKnownPredicate(IsSigned ? - ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, - LessOne, X)) + if (UsedAsNumerator) { + auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; + if (SE->isKnownPredicate(LT, N, D)) { + replaceRemWithNumerator(Rem); return; + } - ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, - Rem->getOperand(0), Rem->getOperand(1)); - SelectInst *Sel = - SelectInst::Create(ICmp, - ConstantInt::get(Rem->getType(), 0), - Rem->getOperand(0), "tmp", Rem); - Rem->replaceAllUsesWith(Sel); + auto *T = Rem->getType(); + const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T)); + if (SE->isKnownPredicate(LT, NLessOne, D)) { + replaceRemWithNumeratorOrZero(Rem); + return; + } } - DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); - ++NumElimRem; + // Try to replace SRem with URem, if both N and D are known non-negative. + // Since we had already check N, we only need to check D now + if (!IsSigned || !SE->isKnownNonNegative(D)) + return; + + replaceSRemWithURem(Rem); Changed = true; - DeadInsts.emplace_back(Rem); } bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) { @@ -474,7 +516,7 @@ if (BinaryOperator *Bin = dyn_cast(UseInst)) { bool IsSRem = Bin->getOpcode() == Instruction::SRem; if (IsSRem || Bin->getOpcode() == Instruction::URem) { - eliminateIVRemainder(Bin, IVOperand, IsSRem); + simplifyIVRemainder(Bin, IVOperand, IsSRem); return true; } Index: llvm/trunk/test/Transforms/IndVarSimplify/eliminate-rem.ll =================================================================== --- llvm/trunk/test/Transforms/IndVarSimplify/eliminate-rem.ll +++ llvm/trunk/test/Transforms/IndVarSimplify/eliminate-rem.ll @@ -33,9 +33,9 @@ ; Indvars should be able to eliminate the (i+1)%n. ; CHECK-LABEL: @f( -; CHECK-NOT: rem -; CHECK: rem -; CHECK-NOT: rem +; CHECK-NOT: {{[us]}}rem +; CHECK: {{[us]}}rem +; CHECK-NOT: {{[us]}}rem ; CHECK: ret define i32 @f(i64* %arg, i64 %arg1, i64 %arg2, i64 %arg3) nounwind { Index: llvm/trunk/test/Transforms/IndVarSimplify/replace-srem-by-urem.ll =================================================================== --- llvm/trunk/test/Transforms/IndVarSimplify/replace-srem-by-urem.ll +++ llvm/trunk/test/Transforms/IndVarSimplify/replace-srem-by-urem.ll @@ -0,0 +1,109 @@ +; RUN: opt < %s -indvars -S | FileCheck %s + +define void @test0(i32* %a) { +; CHECK-LABEL: @test0( +entry: + br label %for.body + +for.body: ; preds = %entry, %for.body + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %rem = srem i32 %i.01, 2 +; CHECK-NOT: srem +; CHECK: urem + %idxprom = sext i32 %rem to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom + store i32 %i.01, i32* %arrayidx, align 4 + %inc = add nsw i32 %i.01, 1 + %cmp = icmp slt i32 %inc, 64 + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body + ret void +} + +define void @test2(i32* %a, i32 %d) { +; CHECK-LABEL: @test2( +entry: + br label %for.body + +for.body: ; preds = %entry, %for.body + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %mul = mul nsw i32 %i.01, 64 + %rem = srem i32 %mul, %d +; CHECK-NOT: urem + %idxprom = sext i32 %rem to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom + store i32 %i.01, i32* %arrayidx, align 4 + %inc = add nsw i32 %i.01, 1 + %cmp = icmp slt i32 %inc, 64 + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body + ret void +} + +define void @test3(i32* %a) { +; CHECK-LABEL: @test3( +entry: + br label %for.body + +for.body: ; preds = %entry, %for.body + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %rem = srem i32 2048, %i.01 +; CHECK: urem +; CHECK-NOT: srem + %idxprom = sext i32 %rem to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom + store i32 %i.01, i32* %arrayidx, align 4 + %inc = add nsw i32 %i.01, 1 + %cmp = icmp slt i32 %inc, 64 + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body + ret void +} + +define void @test4(i32* %a) { +; CHECK-LABEL: @test4( +entry: + br label %for.body + +for.body: ; preds = %entry, %for.body + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %mul = mul nsw i32 %i.01, 64 + %rem = srem i32 %mul, 8 +; CHECK: urem +; CHECK-NOT: srem + %idxprom = sext i32 %rem to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom + store i32 %i.01, i32* %arrayidx, align 4 + %inc = add nsw i32 %i.01, 1 + %cmp = icmp slt i32 %inc, 64 + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body + ret void +} + +define void @test5(i32* %a) { +; CHECK-LABEL: @test5( +entry: + br label %for.body + +for.body: ; preds = %entry, %for.body + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %mul = mul nsw i32 %i.01, 64 + %rem = srem i32 %mul, 6 +; CHECK: urem +; CHECK-NOT: srem + %idxprom = sext i32 %rem to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom + store i32 %i.01, i32* %arrayidx, align 4 + %inc = add nsw i32 %i.01, 1 + %cmp = icmp slt i32 %inc, 64 + br i1 %cmp, label %for.body, label %for.end + +for.end: ; preds = %for.body + ret void +} +