Fix PR22222

[sanjoy]

Summary

The bug was introduced in r225282. r225282 assumed that sub X, Y is the same as add X, -Y. This is not correct if we are going to upgrade the sub to sub nuw. This change fixes the issue by making the optimization ignore sub instructions.

[majnemer]

LGTM.

Out of curiosity, why isn't this implemented like the code here:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp?revision=222213&view=markup#l1733

[sanjoy]

In D6979#108906, @majnemer wrote:

LGTM.

Out of curiosity, why isn't this implemented like the code here:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp?revision=222213&view=markup#l1733

In retrospect, that would have been the right way to do it. Directly checking zext(A + B) == zext(A) + zext(B) does not catch test.unsigned.add.0 (in the test file), but I think that is fixable.

Moreover, the approach you pointed out can be easily generalized to subtraction. I don't think you can easily generalize it to multiplication (since checking for BitWidth + 1 may not be sufficient in that case); but we're not handling multiplication anyway.

I'll try to implement the approach LinearFunctionTestReplace and send in a patch for review sometime this week.

[sanjoy]

In D6979#108906, @majnemer wrote:

LGTM.

Out of curiosity, why isn't this implemented like the code here:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp?revision=222213&view=markup#l1733

Done: http://reviews.llvm.org/D7981

lib/Transforms/Utils/SimplifyIndVar.cpp

 }
 
 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
 /// unsigned-overflow.  Returns true if anything changed, false otherwise.
 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
                                                     Value *IVOperand) {
 
   // Currently we only handle instructions of the form "add <indvar> <value>"
-  // and "sub <indvar> <value>".
   unsigned Op = BO->getOpcode();
-  if (!(Op == Instruction::Add || Op == Instruction::Sub))
+  if (Op != Instruction::Add)
     return false;
 
   // If BO is already both nuw and nsw then there is nothing left to do
   if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
     return false;
 
   IntegerType *IT = cast<IntegerType>(IVOperand->getType());
   Value *OtherOperand = nullptr;
   int OtherOperandIdx = -1;
   if (BO->getOperand(0) == IVOperand) {
     OtherOperand = BO->getOperand(1);
     OtherOperandIdx = 1;
   } else {
     assert(BO->getOperand(1) == IVOperand && "only other use!");
     OtherOperand = BO->getOperand(0);
     OtherOperandIdx = 0;
   }
 
   bool Changed = false;
   const SCEV *OtherOpSCEV = SE->getSCEV(OtherOperand);
   if (OtherOpSCEV == SE->getCouldNotCompute())
     return false;
 
-  if (Op == Instruction::Sub) {
-    // If the subtraction is of the form "sub <indvar>, <op>", then pretend it
-    // is "add <indvar>, -<op>" and continue, else bail out.
-    if (OtherOperandIdx != 1)
-      return false;
-
-    OtherOpSCEV = SE->getNegativeSCEV(OtherOpSCEV);
-  }
-
   const SCEV *IVOpSCEV = SE->getSCEV(IVOperand);
   const SCEV *ZeroSCEV = SE->getConstant(IVOpSCEV->getType(), 0);
 
   if (!BO->hasNoSignedWrap()) {
     // Upgrade the add to an "add nsw" if we can prove that it will never
     // sign-overflow or sign-underflow.
 
     const SCEV *SignedMax =

test/Transforms/IndVarSimplify/pr22222.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+@b = common global i32 0, align 4
+@c = common global i32 0, align 4
+@a = common global i32 0, align 4
+
+declare void @abort() #1
+
+; Function Attrs: nounwind ssp uwtable
+define i32 @main() {
+entry:
+  %a.promoted13 = load i32* @a, align 4
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.end
+  %or.lcssa14 = phi i32 [ %a.promoted13, %entry ], [ %or.lcssa, %for.end ]
+  %d.010 = phi i32 [ 1, %entry ], [ 0, %for.end ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
+  %inc12 = phi i32 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %or11 = phi i32 [ %or.lcssa14, %for.cond1.preheader ], [ %or, %for.body3 ]
+; CHECK-NOT: sub nuw i32 %inc12, %d.010
+; CHECK: sub i32 %inc12, %d.010
+  %add = sub i32 %inc12, %d.010
+  %or = or i32 %or11, %add
+  %inc = add i32 %inc12, 1
+  br i1 false, label %for.body3, label %for.end
+
+for.end:                                          ; preds = %for.body3
+  %or.lcssa = phi i32 [ %or, %for.body3 ]
+  br i1 false, label %for.cond1.preheader, label %for.end6
+
+for.end6:                                         ; preds = %for.end
+  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.end ]
+  store i32 %or.lcssa.lcssa, i32* @a, align 4
+  %cmp7 = icmp eq i32 %or.lcssa.lcssa, -1
+  br i1 %cmp7, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.end6
+  tail call void @abort() #2
+  unreachable
+
+if.end:                                           ; preds = %for.end6
+  ret i32 0
+}

test/Transforms/IndVarSimplify/strengthen-overflow.ll

 
  break:
   ret i32 %civ.inc
 
  exit:
   ret i32 42
 }
 
-define i32 @test.signed.sub.0(i32* %array, i32 %length, i32 %init) {
-; CHECK-LABEL: @test.signed.sub.0
- entry:
-  %upper = icmp sgt i32 %init, %length
-  br i1 %upper, label %loop, label %exit
-
- loop:
-; CHECK-LABEL: loop
-  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
-  %civ.inc = sub i32 %civ, 1
-; CHECK: %civ.inc = sub nsw i32 %civ, 1
-  %cmp = icmp slt i32 %civ.inc, %length
-  br i1 %cmp, label %latch, label %break
-
- latch:
-  store i32 0, i32* %array
-  %check = icmp sgt i32 %civ.inc, %length
-  br i1 %check, label %loop, label %break
-
- break:
-  ret i32 %civ.inc
-
- exit:
-  ret i32 42
-}
-
-define i32 @test.signed.sub.1(i32* %array, i32 %length, i32 %init) {
-; CHECK-LABEL: @test.signed.sub.1
- entry:
-  %upper = icmp sgt i32 %init, %length
-  br i1 %upper, label %loop, label %exit
-
- loop:
-; CHECK-LABEL: loop
-  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
-  %civ.inc = sub i32 %civ, 1
-; CHECK: %civ.inc = sub i32 %civ, 1
-  %cmp = icmp slt i32 %civ.inc, %length
-  br i1 %cmp, label %latch, label %break
-
- latch:
-  store i32 0, i32* %array
-  %check = icmp sge i32 %civ.inc, %length
-  br i1 %check, label %loop, label %break
-
- break:
-  ret i32 %civ.inc
-
- exit:
-  ret i32 42
-}
-
 define i32 @test.unsigned.add.0(i32* %array, i32 %length, i32 %init) {
 ; CHECK-LABEL: @test.unsigned.add.0
  entry:
   %upper = icmp ult i32 %init, %length
   br i1 %upper, label %loop, label %exit
 
  loop:
 ; CHECK-LABEL: loop

 
  break:
   ret i32 %civ.inc
 
  exit:
   ret i32 42
 }
 
-define i32 @test.unsigned.sub.0(i32* %array, i32* %length_ptr, i32 %init) {
-; CHECK-LABEL: @test.unsigned.sub.0
- entry:
-  %length = load i32* %length_ptr, !range !0
-  %upper = icmp ult i32 %init, %length
-  br i1 %upper, label %loop, label %exit
-
- loop:
-; CHECK-LABEL: loop
-  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
-  %civ.inc = sub i32 %civ, 2
-; CHECK: %civ.inc = sub nuw i32 %civ, 2
-  %cmp = icmp slt i32 %civ.inc, %length
-  br i1 %cmp, label %latch, label %break
-
- latch:
-  store i32 0, i32* %array
-  %check = icmp ult i32 %civ.inc, %length
-  br i1 %check, label %loop, label %break
-
- break:
-  ret i32 %civ.inc
-
- exit:
-  ret i32 42
-}
-
-define i32 @test.unsigned.sub.1(i32* %array, i32* %length_ptr, i32 %init) {
-; CHECK-LABEL: @test.unsigned.sub.1
- entry:
-  %length = load i32* %length_ptr, !range !1
-  %upper = icmp ult i32 %init, %length
-  br i1 %upper, label %loop, label %exit
-
- loop:
-; CHECK-LABEL: loop
-  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
-  %civ.inc = sub i32 %civ, 2
-; CHECK: %civ.inc = sub i32 %civ, 2
-  %cmp = icmp slt i32 %civ.inc, %length
-  br i1 %cmp, label %latch, label %break
-
- latch:
-  store i32 0, i32* %array
-  %check = icmp ult i32 %civ.inc, %length
-  br i1 %check, label %loop, label %break
-
- break:
-  ret i32 %civ.inc
-
- exit:
-  ret i32 42
-}
-
 !0 = !{i32 0, i32 2}
 !1 = !{i32 0, i32 42}