Teach IndVarSimplify to add nuw and nsw to operations that provably don't overflow.

[sanjoy]

Summary

This patch teaches IndVarSimplify to add nuw and nsw to certain kinds of operations that provably don't overflow. For example, we can prove %civ.inc below does not sign-overflow. With this change, IndVarSimplify changes %civ.inc to an add nsw.

define i32 @foo(i32* %array, i32* %length_ptr, i32 %init) {
 entry:
  %length = load i32* %length_ptr, !range !0
  %len.sub.1 = sub i32 %length, 1
  %upper = icmp slt i32 %init, %len.sub.1
  br i1 %upper, label %loop, label %exit

 loop:
  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
  %civ.inc = add 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 slt i32 %civ.inc, %len.sub.1
  br i1 %check, label %loop, label %break

 break:
  ret i32 %civ.inc

 exit:
  ret i32 42
}

[hfinkel]

We normally don't add otherwise-provable nsw/nuw unless is specifically enables some other optimization where these facts are difficult to prove. As you might know, there are some optimizations that are valid on overflowing operators that are not valid on non-overflowing ones, so adding nsw/nuw is, generally speaking, not a pure win.

That having been said, I don't see this being a particular issue for induction-variable increment operations on canonical loops, and so this likely makes sense as part of the loop canonical form (I can imagine targets taking advantage of these flags during instruction selection, for example). I'd like you to further comment on your motivation for doing this, but LGTM.

[sanjoy]

Hi Hal,

Thank you for the review.

This is the context: http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-December/079885.html This patch tries to fix point (1) as mentioned in the mail

I am not aware of transforms that are valid only on overflowing operators: as far as I can tell, adding nsw / nuw is a strict increase in the amount of information there is available about an instruction. Can you give me some pointers on where to look for examples? Don't bother if you don't have them handy, I'll look for them myself later.

As an aside, I'll be on vacation starting a few hours from now, so I won't be able to check this in before the first week of 2015.

[hfinkel]

• Original Message -----

From: "Sanjoy Das" <[e-mail]>
To: [e-mail], [e-mail], "david majnemer" <[e-mail]>, [e-mail]
Cc: [e-mail]
Sent: Tuesday, December 23, 2014 6:22:31 PM
Subject: Re: [PATCH] Teach IndVarSimplify to add nuw and nsw to operations that provably don't overflow.

Hi Hal,

Thank you for the review.

This is the context:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-December/079885.html
This patch tries to fix point (1) as mentioned in the mail

I am not aware of transforms that are valid only on overflowing
operators: as far as I can tell, adding nsw / nuw is a strict
increase in the amount of information there is available about an
instruction. Can you give me some pointers on where to look for
examples? Don't bother if you don't have them handy, I'll look for
them myself later.

We really need to add this to an FAQ somewhere, it comes up a lot...

For example, see slides 20-31 of http://llvm.org/devmtg/2014-10/Slides/Menendez-Alive.pdf -- shows a reassociation example valid only without the no-wrap flags. There are other examples too that have been discussed on the mailing list.

As an aside, I'll be on vacation starting a few hours from now, so I
won't be able to check this in before the first week of 2015.

Okay; enjoy your vacation!

-Hal

http://reviews.llvm.org/D6748

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

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

public:
     void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);
 
     Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);
 
     bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand);
     void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand,
                               bool IsSigned);
+    bool strengthenOverflowingOperation(BinaryOperator *OBO, Value *IVOperand);
 
     Instruction *splitOverflowIntrinsic(Instruction *IVUser,
                                         const DominatorTree *DT);
   };
 }
 
 /// Fold an IV operand into its use.  This removes increments of an
 /// aligned IV when used by a instruction that ignores the low bits.
bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,
 
   UseInst->replaceAllUsesWith(IVOperand);
   ++NumElimIdentity;
   Changed = true;
   DeadInsts.push_back(UseInst);
   return true;
 }
 
+/// 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))
+    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 =
+      SE->getConstant(APInt::getSignedMaxValue(IT->getBitWidth()));
+    const SCEV *SignedMin =
+      SE->getConstant(APInt::getSignedMinValue(IT->getBitWidth()));
+
+    // The addition "IVOperand + OtherOp" does not sign-overflow if the result
+    // is sign-representable in 2's complement in the given bit-width.
+    //
+    // If OtherOp is SLT 0, then for an IVOperand in [SignedMin - OtherOp,
+    // SignedMax], "IVOperand + OtherOp" is in [SignedMin, SignedMax + OtherOp].
+    // Everything in [SignedMin, SignedMax + OtherOp] is representable since
+    // SignedMax + OtherOp is at least -1.
+    //
+    // If OtherOp is SGE 0, then for an IVOperand in [SignedMin, SignedMax -
+    // OtherOp], "IVOperand + OtherOp" is in [SignedMin + OtherOp, SignedMax].
+    // Everything in [SignedMin + OtherOp, SignedMax] is representable since
+    // SignedMin + OtherOp is at most -1.
+    //
+    // It follows that for all values of IVOperand in [SignedMin - smin(0,
+    // OtherOp), SignedMax - smax(0, OtherOp)] the result of the add is
+    // representable (i.e. there is no sign-overflow).
+
+    const SCEV *UpperDelta = SE->getSMaxExpr(ZeroSCEV, OtherOpSCEV);
+    const SCEV *UpperLimit = SE->getMinusSCEV(SignedMax, UpperDelta);
+
+    bool NeverSignedOverflows =
+      SE->isKnownPredicate(ICmpInst::ICMP_SLE, IVOpSCEV, UpperLimit);
+
+    if (NeverSignedOverflows) {
+      const SCEV *LowerDelta = SE->getSMinExpr(ZeroSCEV, OtherOpSCEV);
+      const SCEV *LowerLimit = SE->getMinusSCEV(SignedMin, LowerDelta);
+
+      bool NeverSignedUnderflows =
+        SE->isKnownPredicate(ICmpInst::ICMP_SGE, IVOpSCEV, LowerLimit);
+      if (NeverSignedUnderflows) {
+        BO->setHasNoSignedWrap(true);
+        Changed = true;
+      }
+    }
+  }
+
+  if (!BO->hasNoUnsignedWrap()) {
+    // Upgrade the add computing "IVOperand + OtherOp" to an "add nuw" if we can
+    // prove that it will never unsigned-overflow (i.e. the result will always
+    // be representable in the given bit-width).
+    //
+    // "IVOperand + OtherOp" is unsigned-representable in 2's complement iff it
+    // does not produce a carry.  "IVOperand + OtherOp" produces no carry iff
+    // IVOperand ULE (UnsignedMax - OtherOp).
+
+    const SCEV *UnsignedMax =
+      SE->getConstant(APInt::getMaxValue(IT->getBitWidth()));
+    const SCEV *UpperLimit = SE->getMinusSCEV(UnsignedMax, OtherOpSCEV);
+
+    bool NeverUnsignedOverflows =
+        SE->isKnownPredicate(ICmpInst::ICMP_ULE, IVOpSCEV, UpperLimit);
+
+    if (NeverUnsignedOverflows) {
+      BO->setHasNoUnsignedWrap(true);
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
 /// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
 /// analysis and optimization.
 ///
 /// \return A new value representing the non-overflowing add if possible,
 /// otherwise return the original value.
 Instruction *SimplifyIndvar::splitOverflowIntrinsic(Instruction *IVUser,
                                                     const DominatorTree *DT) {
   IntrinsicInst *II = dyn_cast<IntrinsicInst>(IVUser);
while (!SimpleIVUsers.empty()) {
     }
     if (!IVOperand)
       continue;
 
     if (eliminateIVUser(UseOper.first, IVOperand)) {
       pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
       continue;
     }
+
+    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseOper.first)) {
+      if (isa<OverflowingBinaryOperator>(BO) &&
+          strengthenOverflowingOperation(BO, IVOperand)) {
+        // re-queue uses of the now modified binary operator and fall
+        // through to the checks that remain.
+        pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
+      }
+    }
+
     CastInst *Cast = dyn_cast<CastInst>(UseOper.first);
     if (V && Cast) {
       V->visitCast(Cast);
       continue;
     }
     if (isSimpleIVUser(UseOper.first, L, SE)) {
       pushIVUsers(UseOper.first, Simplified, SimpleIVUsers);
     }

llvm/trunk/test/Transforms/BBVectorize/loop1.ll

 ; CHECK-UNRL: %add7 = fadd <2 x double> %add, %mul6
 ; CHECK-UNRL: %mul8 = fmul <2 x double> %3, %3
 ; CHECK-UNRL: %add9 = fadd <2 x double> %2, %2
 ; CHECK-UNRL: %add10 = fadd <2 x double> %add9, %2
 ; CHECK-UNRL: %mul11 = fmul <2 x double> %mul8, %add10
 ; CHECK-UNRL: %add12 = fadd <2 x double> %add7, %mul11
 ; CHECK-UNRL: %4 = bitcast double* %arrayidx14 to <2 x double>*
 ; CHECK-UNRL: store <2 x double> %add12, <2 x double>* %4, align 8
-; CHECK-UNRL: %indvars.iv.next.1 = add i64 %indvars.iv, 2
+; CHECK-UNRL: %indvars.iv.next.1 = add nsw i64 %indvars.iv, 2
 ; CHECK-UNRL: %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32
 ; CHECK-UNRL: %exitcond.1 = icmp eq i32 %lftr.wideiv.1, 10
 ; CHECK-UNRL: br i1 %exitcond.1, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

llvm/trunk/test/Transforms/IndVarSimplify/2011-09-10-widen-nsw.ll

 for.body11:                                       ; preds = %entry
   %shl = shl i32 1, 1
   %shl132 = shl i32 %shl, 1
   br label %for.body153
 
 for.body153:                                      ; preds = %for.body153, %for.body11
   br i1 undef, label %for.body170, label %for.body153
 
-; CHECK: add nsw i64 %indvars.iv, 1
+; CHECK: add nuw nsw i64 %indvars.iv, 1
 ; CHECK: sub nsw i64 %indvars.iv, 2
 ; CHECK: sub nsw i64 4, %indvars.iv
 ; CHECK: mul nsw i64 %indvars.iv, 8
 for.body170:                                      ; preds = %for.body170, %for.body153
   %i2.19 = phi i32 [ %add249, %for.body170 ], [ 0, %for.body153 ]
 
   %add = add nsw i32 %i2.19, 1
   %add.idxprom = sext i32 %add to i64

llvm/trunk/test/Transforms/IndVarSimplify/strengthen-overflow.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+define i32 @test.signed.add.0(i32* %array, i32 %length, i32 %init) {
+; CHECK-LABEL: @test.signed.add.0
+ entry:
+  %upper = icmp slt i32 %init, %length
+  br i1 %upper, label %loop, label %exit
+
+ loop:
+; CHECK-LABEL: loop
+  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
+  %civ.inc = add i32 %civ, 1
+; CHECK: %civ.inc = add 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 slt i32 %civ.inc, %length
+  br i1 %check, label %loop, label %break
+
+ break:
+  ret i32 %civ.inc
+
+ exit:
+  ret i32 42
+}
+
+define i32 @test.signed.add.1(i32* %array, i32 %length, i32 %init) {
+; CHECK-LABEL: @test.signed.add.1
+ entry:
+  %upper = icmp sle i32 %init, %length
+  br i1 %upper, label %loop, label %exit
+
+ loop:
+; CHECK-LABEL: loop
+  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
+  %civ.inc = add i32 %civ, 1
+; CHECK: %civ.inc = add 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 slt 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.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
+  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
+  %civ.inc = add i32 %civ, 1
+; CHECK: %civ.inc = add nuw 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 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.add.1(i32* %array, i32 %length, i32 %init) {
+; CHECK-LABEL: @test.unsigned.add.1
+ entry:
+  %upper = icmp ule i32 %init, %length
+  br i1 %upper, label %loop, label %exit
+
+ loop:
+; CHECK-LABEL: loop
+  %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
+  %civ.inc = add i32 %civ, 1
+; CHECK: %civ.inc = add 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 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.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}