[SimplifyIndvar] Replace the srem used by IV if we can prove both of its operands are non-negative

[etherzhhb]

Summary

Since now SCEV can handle 'urem', an 'urem' is a better canonical form than an 'srem' because it has well-defined behavior

This is a follow up of D34598

[sanjoy]

lib/Transforms/Utils/SimplifyIndVar.cpp

306 ↗

(On Diff #115954)

Instead of creating another function this way, I thin a cleaner design would be to create a couple of small functions for the "i % n --> i if i is in [0,n).", "i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n)." cases and this case, and call them from SimplifyIndvar::eliminateIVRemainder.

[etherzhhb]

Update patch to address reviewer's request

[etherzhhb]

Update comment

[etherzhhb]

Update comment

[sanjoy]

This is looking close; only some nitpicky comments inline

lib/Transforms/Utils/SimplifyIndVar.cpp

340 ↗

(On Diff #115974)

Can we share this work amongst the three helpers? Something like:

• Pass in NumeratorNonNegative and DenominatorNonNegative bools to this function, and only NumeratorNonNegative to the other two.
• Compute these bools in simplifyIVRemainder as needed

373 ↗

(On Diff #115974)

This specific function doesn't add much IMHO -- I'd just inline it out.

402 ↗

(On Diff #115974)

Let's keep calling these N and D -- perhaps you could differentiate the Value * and the SCEV * by a suffix (N vs NValue)?

410 ↗

(On Diff #115974)

s/By/With/ in the names

417 ↗

(On Diff #115974)

Going by the other function names, how about calling this replaceSRemWithURem?

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

340 ↗

(On Diff #115974)

Sure, I will do this. I think this whole simplifyIVRemainder will not process if NumeratorNonNegative is false, is that correct?

[sanjoy]

lib/Transforms/Utils/SimplifyIndVar.cpp

340 ↗

(On Diff #115974)

Yes, but I think it may be cleaner to pass it in to the helpers; that way the dependency of the transform is clearer. And just returning from the helpers if it isn't set seems fine.

[etherzhhb]

update patch based on the comments

[etherzhhb]

Update comment

[sanjoy]

LGTM with comments addressed.

lib/Transforms/Utils/SimplifyIndVar.cpp

344 ↗

(On Diff #116189)

I'd prefer to give this a more specific name -- how about "iv.rem"? The exact name does not matter as long as folks can grep the symbol name in LLVM and find this file.

366 ↗

(On Diff #116189)

Minor thing: I'd have written this as:

const SCEV *N = SE->getSCEVAtScope(SE->getSCEV(NValue), ICmpLoop);

// Later, after the check on !UsedAsNumerator && !IsSigned
const SCEV *D = SE->getSCEVAtScope(SE->getSCEV(DValue), ICmpLoop);

401 ↗

(On Diff #116189)

I'm not sure if this is safe -- it seems like Changed is piped all the way through to IndVarSimplify's return value to the pass manager (if nothing changed, it will tell the PM that all analyses are preserved).

Even if this is safe, I suspect you'll need to do Changed |= UsedAsNumerator. In this case, please add a one liner on why this is safe.

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

401 ↗

(On Diff #116189)

Thanks for you reminder on this, I have a feeling that this may not be safe as well. Let me have a closer look

[etherzhhb]

address comments from the reviewer

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

 #define DEBUG_TYPE "indvars"
 
 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
 STATISTIC(NumElimRem     , "Number of IV remainder operations eliminated");
 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 {
   /// This is a utility for simplifying induction variables
   /// based on ScalarEvolution. It is the primary instrument of the
   /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
   /// other loop passes that preserve SCEV.
   class SimplifyIndvar {
public:
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);
 
     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,
+    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);
   };
 }
 
 /// Fold an IV operand into its use.  This removes increments of an
 /// aligned IV when used by a instruction that ignores the low bits.
if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
     Changed = true;
     DeadInsts.push_back(SDiv);
     return true;
   }
 
   return false;
 }
 
-/// SimplifyIVUsers helper for eliminating useless
-/// remainder operations operating on an induction variable.
-void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
-                                      Value *IVOperand,
+// 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)
 
-    if (!SE->isKnownPredicate(IsSigned ?
-                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
-                              LessOne, X))
+  const SCEV *D = SE->getSCEV(DValue);
+  D = SE->getSCEVAtScope(D, ICmpLoop);
+
+  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) {
   auto *F = CI->getCalledFunction();
   if (!F)
     return false;
 
   typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
                                      Instruction *IVOperand) {
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
     eliminateIVComparison(ICmp, IVOperand);
     return true;
   }
   if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
     bool IsSRem = Bin->getOpcode() == Instruction::SRem;
     if (IsSRem || Bin->getOpcode() == Instruction::URem) {
-      eliminateIVRemainder(Bin, IVOperand, IsSRem);
+      simplifyIVRemainder(Bin, IVOperand, IsSRem);
       return true;
     }
 
     if (Bin->getOpcode() == Instruction::SDiv)
       return eliminateSDiv(Bin);
   }
 
   if (auto *CI = dyn_cast<CallInst>(UseInst))

llvm/trunk/test/Transforms/IndVarSimplify/eliminate-rem.ll

bb11:                                             ; preds = %bb5
   br label %bb12
 
 bb12:                                             ; preds = %bb11, %bb
   ret void
 }
 
 ; 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 {
 bb:
   %t = icmp sgt i64 %arg1, 0                      ; <i1> [#uses=1]
   br i1 %t, label %bb4, label %bb54
 
 bb4:                                              ; preds = %bb

llvm/trunk/test/Transforms/IndVarSimplify/replace-srem-by-urem.ll

+; 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
+}
+