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

[etherzhhb]

Summary

Since there is no sdiv in SCEV, an 'udiv' is a better canonical form than an 'sdiv' as the user of induction variable

[etherzhhb]

lib/Transforms/Utils/SimplifyIndVar.cpp

291–293

maybe I should also copy the 'exact' flag?

[grosser]

Hi Hongbin,

I am not sure what you are trying to achieve here. This kernel is already optimized by -instcombine to

define void @test(i32* %a) {
entry:
  br label %for.body

for.body:                                         ; preds = %for.body, %entry
  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %div = shl nsw i32 %i.01, 5
  %idxprom = sext i32 %div 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 %i.01, 63
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body
  ret void
}

So the sdiv is replaced by a lsh, taking into account the information that sdiv is working on unsigned inputs only.

If you divide by a non-power-of-two, instcombine does not change the code and leaves the sdiv in. However, if you would like to move to an sdiv even in this case this should probably be added to instcombine.

I would also be interested to learn why an 'udiv' is a better canonical form than an 'sdiv'. Is it faster to execute (non-power-of-two) udivs on FPGAs than sdivs?

[etherzhhb]

Hi Tobias

In D31488#713840, @grosser wrote:

Hi Hongbin,

I am not sure what you are trying to achieve here. This kernel is already optimized by -instcombine to

This is based on the discussion in https://groups.google.com/d/topic/llvm-dev/HKK9ffG-dIU/discussion

define void @test(i32* %a) {
entry:
  br label %for.body

for.body:                                         ; preds = %for.body, %entry
  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %div = shl nsw i32 %i.01, 5
  %idxprom = sext i32 %div 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 %i.01, 63
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body
  ret void
}

So the sdiv is replaced by a lsh, taking into account the information that sdiv is working on unsigned inputs only.

If you divide by a non-power-of-two, instcombine does not change the code and leaves the sdiv in. However, if you would like to move to an sdiv even in this case this should probably be added to instcombine.

Yes, see below.

I would also be interested to learn why an 'udiv' is a better canonical form than an 'sdiv'. Is it faster to execute (non-power-of-two) udivs on FPGAs than sdivs?

I am focusing on the induction variable and its users here. I am trying to get an AddRec from arrayidx.
However, there is no sdiv in SCEV, and SCEV will give up when it see a sdiv. From this perspective udiv is better then sdiv. I think I should explicitly explain this in the summary

Let me also look at instcombine, the original motivation to put it here is mainly because SimplifyIndVar use SCEV, which provide better range knowledge about induction variables.

[grosser]

The relevant function is visitSDiv in InstCombineMulDivRem.cpp. Maybe we have indeed insufficient information in instcombine.

[etherzhhb]

Add more testcases

[etherzhhb]

test/Transforms/IndVarSimplify/replace-sdiv-by-udiv.ll

11

instcombine (which use computeKnownBits) is not able to prove the status of the signbit of %i.01 here

[sanjoy]

Comments inline.

You can also do this same rewrite within SCEV. That is, try to have getSCEV(sdiv instruction) return a SCEVUDivExpr if legal. However, given that udiv is more canonical, this patch is good too if it solves your problem.

lib/Transforms/Utils/SimplifyIndVar.cpp

38

s/eliminated/converted to unsigned division/

277

This seems unnecessary - why do you not care about optimizing

%val = sdiv <non-iv-known-positive>, <iv>

281

Use auto *.

286

I'd use N and D instead of S and X.

291

Use auto *.

299

Why not push_back?

[etherzhhb]

address sanjoy 's comment

[sanjoy]

lgtm with minor comments

lib/Transforms/Utils/SimplifyIndVar.cpp

39

s/NumElimSDiv/NumSimplifiedSDiv/

275

Comment is wrong.

I'd actually just drop the comment. It is obvious enough what the code is doing here.

[etherzhhb]

In D31488#714492, @sanjoy wrote:

Comments inline.

You can also do this same rewrite within SCEV. That is, try to have getSCEV(sdiv instruction) return a SCEVUDivExpr if legal.

This also sounds reasonable and I can also look at that after this.
Just a quick question: are we suppose to use getSCEVAtScope in getSCEV?

However, given that udiv is more canonical, this patch is good too if it solves your problem.

[etherzhhb]

fix the last few things before pushing the commit

[sanjoy]

In D31488#714672, @etherzhhb wrote:

In D31488#714492, @sanjoy wrote:

Comments inline.

You can also do this same rewrite within SCEV. That is, try to have getSCEV(sdiv instruction) return a SCEVUDivExpr if legal.

This also sounds reasonable and I can also look at that after this.
Just a quick question: are we suppose to use getSCEVAtScope in getSCEV?

Not in general. The SCEV expressions you return from getSCEV need to be context insensitive.

However, given that udiv is more canonical, this patch is good too if it solves your problem.

lib/Transforms/Utils/SimplifyIndVar.cpp

 
 using namespace llvm;
 
 #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(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:
 
     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);
+    bool eliminateSDiv(BinaryOperator *SDiv);
     bool strengthenOverflowingOperation(BinaryOperator *OBO, 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.
 ///
 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
#endif
     ICmp->setOperand(1, NewRHS);
   } else
     return;
 
   ++NumElimCmp;
   Changed = true;
 }
 
+bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {
+  // Get the SCEVs for the ICmp operands.
+  auto *N = SE->getSCEV(SDiv->getOperand(0));
+  auto *D = SE->getSCEV(SDiv->getOperand(1));
+
+  // Simplify unnecessary loops away.
+  const Loop *L = LI->getLoopFor(SDiv->getParent());
+  N = SE->getSCEVAtScope(N, L);
+  D = SE->getSCEVAtScope(D, L);
+
+  // Replace sdiv by udiv if both of the operands are non-negative
+  if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
+    auto *UDiv = BinaryOperator::Create(
+        BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
+        SDiv->getName() + ".udiv", SDiv);
+    UDiv->setIsExact(SDiv->isExact());
+    SDiv->replaceAllUsesWith(UDiv);
+    DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');
+    ++NumSimplifiedSDiv;
+    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 IsSigned) {
   // We're only interested in the case where we know something about
   // the numerator.
   if (IVOperand != Rem->getOperand(0))
     return;

 /// side-effect given the range of IV values.  IVOperand is guaranteed SCEVable,
 /// but UseInst may not be.
 bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
                                      Instruction *IVOperand) {
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
     eliminateIVComparison(ICmp, IVOperand);
     return true;
   }
-  if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) {
-    bool IsSigned = Rem->getOpcode() == Instruction::SRem;
-    if (IsSigned || Rem->getOpcode() == Instruction::URem) {
-      eliminateIVRemainder(Rem, IVOperand, IsSigned);
+  if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {
+    bool IsSRem = Bin->getOpcode() == Instruction::SRem;
+    if (IsSRem || Bin->getOpcode() == Instruction::URem) {
+      eliminateIVRemainder(Bin, IVOperand, IsSRem);
       return true;
     }
+
+    if (Bin->getOpcode() == Instruction::SDiv)
+      return eliminateSDiv(Bin);
   }
 
   if (auto *CI = dyn_cast<CallInst>(UseInst))
     if (eliminateOverflowIntrinsic(CI))
       return true;
 
   if (eliminateIdentitySCEV(UseInst, IVOperand))
     return true;

test/Transforms/IndVarSimplify/replace-sdiv-by-udiv.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 ]
+  %div = sdiv i32 %i.01, 2
+; CHECK-NOT: sdiv
+; CHECK:     udiv
+  %idxprom = sext i32 %div 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 @test1(i32* %a) {
+; CHECK-LABEL: @test1(
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %div = sdiv exact i32 %i.01, 2
+; CHECK-NOT: sdiv
+; CHECK:     udiv exact
+  %idxprom = sext i32 %div 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
+  %div = sdiv i32 %mul, %d
+; CHECK-NOT: udiv
+  %idxprom = sext i32 %div 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 ]
+  %div = sdiv i32 2048, %i.01
+; CHECK:     udiv
+; CHECK-NOT: sdiv
+  %idxprom = sext i32 %div 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
+  %div = sdiv i32 %mul, 8
+; CHECK:     udiv
+; CHECK-NOT: sdiv
+  %idxprom = sext i32 %div 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
+  %div = sdiv i32 %mul, 6
+; CHECK:     udiv
+; CHECK-NOT: sdiv
+  %idxprom = sext i32 %div 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
+}
+