[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

328

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

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

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

402

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

410

s/By/With/ in the names

417

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

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

340

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

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

351

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.

403

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);

423

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

423

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

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,
+    bool replaceRemByNumerator(BinaryOperator *Rem, const SCEV *SN,
+                               const SCEV *SD, bool IsSigned);
+    bool replaceRemByNumeratorOrZero(BinaryOperator *Rem, const SCEV *SN,
+                                     const SCEV *SD, bool IsSigned);
     bool eliminateSDiv(BinaryOperator *SDiv);
+    bool eliminateSRem(BinaryOperator *Rem, const SCEV *SN, const SCEV *SD);
     bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
     bool strengthenRightShift(BinaryOperator *BO, Value *IVOperand);
+
+    /// Return true if LHS in [0, RHS), we will choose SLT or ULT depending on
+    /// the value of IsSigned
+    bool isAlwaysLessThanAndNonNegative(const SCEV *LHS, const SCEV *RHS,
+                                        bool IsSigned);
   };
 }
 
 /// Fold an IV operand into its use.  This removes increments of an
 /// aligned IV when used by a instruction that ignores the low bits.
 ///
 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
 ///
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,
+bool SimplifyIndvar::isAlwaysLessThanAndNonNegative(const SCEV *LHS,
+                                                    const SCEV *RHS,
+                                                    bool IsSigned) {
+  // Check if LHS is non negative, if the 'IsSigned' is true, we ASSUME it
+  // to be non negative
+  if (IsSigned && !SE->isKnownNonNegative(LHS))
+    return false;
+
+  return SE->isKnownPredicate(
+      IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, LHS, RHS);
+}
+
+// i %s n -> i %u n if i >= 0 and n >= 0
+bool SimplifyIndvar::eliminateSRem(BinaryOperator *Rem, const SCEV *SN,
+                                   const SCEV *SD) {
+  if (!SE->isKnownNonNegative(SN) || !SE->isKnownNonNegative(SD))
+    return false;
+
+  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);
+  return true;
+}
+
+// i % n  -->  i  if i is in [0,n).
+bool SimplifyIndvar::replaceRemByNumerator(BinaryOperator *Rem, const SCEV *SN,
+                                           const SCEV *SD, bool IsSigned) {
+  if (!isAlwaysLessThanAndNonNegative(SN, SD, IsSigned))
+    return false;
+
+  Rem->replaceAllUsesWith(Rem->getOperand(0));
+  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
+  ++NumElimRem;
+  Changed = true;
+  DeadInsts.emplace_back(Rem);
+  return true;
+}
+
+// (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
+bool SimplifyIndvar::replaceRemByNumeratorOrZero(BinaryOperator *Rem,
+                                                 const SCEV *SN, const SCEV *SD,
                                                  bool IsSigned) {
+  auto *T = Rem->getType();
+  const auto *LessOne = SE->getMinusSCEV(SN, SE->getOne(T));
+  if (!isAlwaysLessThanAndNonNegative(LessOne, SD, IsSigned))
+    return false;
+
+  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, "tmp", Rem);
+  Rem->replaceAllUsesWith(Sel);
+  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
+  ++NumElimRem;
+  Changed = true;
+  DeadInsts.emplace_back(Rem);
+  return true;
+}
+
+/// 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 *N = Rem->getOperand(0), *D = 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 == N;
+  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 *S = SE->getSCEV(N);
+  const SCEV *X = SE->getSCEV(D);
 
   // Simplify unnecessary loops away.
   const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
   S = SE->getSCEVAtScope(S, ICmpLoop);
   X = SE->getSCEVAtScope(X, 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))
+  if (UsedAsNumerator) {
+    if (replaceRemByNumerator(Rem, S, X, IsSigned))
       return;
 
-    if (!SE->isKnownPredicate(IsSigned ?
-                              ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
-                              LessOne, X))
+    if (replaceRemByNumeratorOrZero(Rem, S, X, IsSigned))
       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);
   }
 
-  DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
-  ++NumElimRem;
-  Changed = true;
-  DeadInsts.emplace_back(Rem);
+  if (IsSigned && eliminateSRem(Rem, S, X))
+    // Only propagate the change if IVOperand is used as numerator
+    Changed = UsedAsNumerator;
 }
 
 bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
   auto *F = CI->getCalledFunction();
   if (!F)
     return false;
 
   typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
       const SCEV *, const SCEV *, SCEV::NoWrapFlags, unsigned);
   typedef const SCEV *(ScalarEvolution::*ExtensionFunctionTy)(
       const SCEV *, Type *, unsigned);
 
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))

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