InstCombine: Preserve nuw when reassociating nuw ops [1/3]

[arsenm]

Summary

Alive says this is OK

[nlopes]

This patch LGTM, except for the changes in tryFactorization(). It seems there's some code missing.

https://rise4fun.com/Alive/L2c

lib/Transforms/InstCombine/InstructionCombining.cpp

633

This variable is never used. It's defined over the next few lines, but never used to set NUW on the instruction.

[arsenm]

Fix tryFactorization and fix missing test. Surprisingly there seem to be no restriction on the constant value for nuw, like nsw has?

Note for the tryFactorization part, alive times out without a specific type: https://rise4fun.com/Alive/7QM
It works if I specify i8: https://rise4fun.com/Alive/Thy

[arsenm]

ping

[arsenm]

ping

[lebedev.ri]

lib/Transforms/InstCombine/InstructionCombining.cpp

179–215

Why does MaintainNoSignedWrap() need all that logic to prove that no overflow happens,
but MaintainNoUnsignedWrap() does nothing of sorts?

[arsenm]

lib/Transforms/InstCombine/InstructionCombining.cpp

179–215

I'm not really sure why MaintainNoSignedWrap has all of those checks. It seems to me like it's looking an overflow that was already illegal?

[lebedev.ri]

This consists of 3 separate changes, it would be easier to review them separately.

lib/Transforms/InstCombine/InstructionCombining.cpp

179–215

https://rise4fun.com/Alive/8V9

207

Maintain is the wrong term then, has NUW flag or something

test/Transforms/InstCombine/reassociate-nuw.ll

2

Can you please precommit using utils/update_test_checks.py ?

[lebedev.ri]

I think this has the wrong diff, this one is identical to D63528.

[lebedev.ri]

(just marking as reviewed)

[arsenm]

Correct diff

[lebedev.ri]

Okay, this looks good to me.
Thanks!

lib/Transforms/InstCombine/InstructionCombining.cpp

322–328

I would still recomment

bool IsNUW = hasNoUnsignedWrap(I) && hasNoUnsignedWrap(*Op0);
bool IsNSW = MaintainNoSignedWrap(I, B, C);

ClearSubclassDataAfterReassociation(I);

if (IsNUW)
  I.setHasNoUnsignedWrap(true);

[arsenm]

r364233

lib/Transforms/InstCombine/InstructionCombining.cpp

 bool InstCombiner::shouldChangeType(Type *From, Type *To) const {
   assert(From->isIntegerTy() && To->isIntegerTy());
 
   unsigned FromWidth = From->getPrimitiveSizeInBits();
   unsigned ToWidth = To->getPrimitiveSizeInBits();
   return shouldChangeType(FromWidth, ToWidth);
 }
 
 // Return true, if No Signed Wrap should be maintained for I.
 // The No Signed Wrap flag can be kept if the operation "B (I.getOpcode) C",
 // where both B and C should be ConstantInts, results in a constant that does
 // not overflow. This function only handles the Add and Sub opcodes. For
 // all other opcodes, the function conservatively returns false.
 static bool MaintainNoSignedWrap(BinaryOperator &I, Value *B, Value *C) {
   OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(&I);
   if (!OBO || !OBO->hasNoSignedWrap())
     return false;
 
   // We reason about Add and Sub Only.
   Instruction::BinaryOps Opcode = I.getOpcode();
   if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
     return false;
 
   const APInt *BVal, *CVal;
   if (!match(B, m_APInt(BVal)) || !match(C, m_APInt(CVal)))
     return false;
 
   bool Overflow = false;
   if (Opcode == Instruction::Add)
     (void)BVal->sadd_ov(*CVal, Overflow);
   else
     (void)BVal->ssub_ov(*CVal, Overflow);
 
   return !Overflow;
 }
 
+static bool MaintainNoUnsignedWrap(BinaryOperator &I) {
+  OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(&I);
+  if (!OBO || !OBO->hasNoUnsignedWrap())
+    return false;
+
+  return true;
+}
+
 /// Conservatively clears subclassOptionalData after a reassociation or
 /// commutation. We preserve fast-math flags when applicable as they can be
 /// preserved.
 static void ClearSubclassDataAfterReassociation(BinaryOperator &I) {
   FPMathOperator *FPMO = dyn_cast<FPMathOperator>(&I);
   if (!FPMO) {
     I.clearSubclassOptionalData();
     return;
   }
if (I.isAssociative()) {
 
         // Does "B op C" simplify?
         if (Value *V = SimplifyBinOp(Opcode, B, C, SQ.getWithInstruction(&I))) {
           // It simplifies to V.  Form "A op V".
           I.setOperand(0, A);
           I.setOperand(1, V);
           // Conservatively clear the optional flags, since they may not be
           // preserved by the reassociation.
-          if (MaintainNoSignedWrap(I, B, C) &&
+
+          bool IsNUW = MaintainNoUnsignedWrap(I);
+          bool IsNSW = MaintainNoSignedWrap(I, B, C);
+
+          ClearSubclassDataAfterReassociation(I);
+
+          if (IsNUW && MaintainNoUnsignedWrap(*Op0))
+            I.setHasNoUnsignedWrap(true);
+
+          if (IsNSW &&
               (!Op0 || (isa<BinaryOperator>(Op0) && Op0->hasNoSignedWrap()))) {
             // Note: this is only valid because SimplifyBinOp doesn't look at
             // the operands to Op0.
-            I.clearSubclassOptionalData();
             I.setHasNoSignedWrap(true);
-          } else {
-            ClearSubclassDataAfterReassociation(I);
           }
 
           Changed = true;
           ++NumReassoc;
           continue;
         }
       }
 
if (I.isAssociative() && I.isCommutative()) {
           isa<Constant>(Op0->getOperand(1)) &&
           isa<Constant>(Op1->getOperand(1)) &&
           Op0->hasOneUse() && Op1->hasOneUse()) {
         Value *A = Op0->getOperand(0);
         Constant *C1 = cast<Constant>(Op0->getOperand(1));
         Value *B = Op1->getOperand(0);
         Constant *C2 = cast<Constant>(Op1->getOperand(1));
 
+         bool IsNUW = MaintainNoUnsignedWrap(I) &&
+           MaintainNoUnsignedWrap(*Op0) &&
+           MaintainNoUnsignedWrap(*Op1);
+
+         BinaryOperator *New = (IsNUW && Opcode == Instruction::Add) ?
+           BinaryOperator::CreateNUW(Opcode, A, B) :
+           BinaryOperator::Create(Opcode, A, B);
+
         Constant *Folded = ConstantExpr::get(Opcode, C1, C2);
-        BinaryOperator *New = BinaryOperator::Create(Opcode, A, B);
         if (isa<FPMathOperator>(New)) {
           FastMathFlags Flags = I.getFastMathFlags();
           Flags &= Op0->getFastMathFlags();
           Flags &= Op1->getFastMathFlags();
           New->setFastMathFlags(Flags);
         }
         InsertNewInstWith(New, I);
         New->takeName(Op1);
         I.setOperand(0, New);
         I.setOperand(1, Folded);
         // Conservatively clear the optional flags, since they may not be
         // preserved by the reassociation.
         ClearSubclassDataAfterReassociation(I);
+        if (IsNUW)
+          I.setHasNoUnsignedWrap(true);
 
         Changed = true;
         continue;
       }
     }
 
     // No further simplifications.
     return Changed;
if (SimplifiedInst) {
     ++NumFactor;
     SimplifiedInst->takeName(&I);
 
     // Check if we can add NSW flag to SimplifiedInst. If so, set NSW flag.
     // TODO: Check for NUW.
     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SimplifiedInst)) {
       if (isa<OverflowingBinaryOperator>(SimplifiedInst)) {
         bool HasNSW = false;
-        if (isa<OverflowingBinaryOperator>(&I))
+        bool HasNUW = false;
+        if (isa<OverflowingBinaryOperator>(&I)) {
           HasNSW = I.hasNoSignedWrap();
+          HasNUW = I.hasNoUnsignedWrap();
+        }
 
-        if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS))
+        if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) {
           HasNSW &= LOBO->hasNoSignedWrap();
+          HasNUW &= LOBO->hasNoUnsignedWrap();
+        }
 
-        if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS))
+        if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) {
           HasNSW &= ROBO->hasNoSignedWrap();
+          HasNUW &= ROBO->hasNoUnsignedWrap();
+        }
 
         // We can propagate 'nsw' if we know that
         //  %Y = mul nsw i16 %X, C
         //  %Z = add nsw i16 %Y, %X
         // =>
         //  %Z = mul nsw i16 %X, C+1
         //
         // iff C+1 isn't INT_MIN

test/Transforms/InstCombine/reassociate-nuw.ll

+; RUN: opt -instcombine -S %s | FileCheck %s
+
+; CHECK-LABEL: @reassoc_add_nuw(
+; CHECK-NEXT: add nuw i32 %x, 68
+define i32 @reassoc_add_nuw(i32 %x) {
+  %add0 = add nuw i32 %x, 4
+  %add1 = add nuw i32 %add0, 64
+  ret i32 %add1
+}
+
+; This does the wrong thing because the sub is turned into an add of a
+; negative constant first which drops the nuw.
+
+; CHECK-LABEL: @reassoc_sub_nuw(
+; CHECK-NEXT: add i32 %x, -68
+define i32 @reassoc_sub_nuw(i32 %x) {
+  %sub0 = sub nuw i32 %x, 4
+  %sub1 = sub nuw i32 %sub0, 64
+  ret i32 %sub1
+}
+
+; CHECK-LABEL: @reassoc_mul_nuw(
+; CHECK-NEXT: mul nuw i32 %x, 260
+define i32 @reassoc_mul_nuw(i32 %x) {
+  %mul0 = mul nuw i32 %x, 4
+  %mul1 = mul nuw i32 %mul0, 65
+  ret i32 %mul1
+}
+
+; CHECK-LABEL: @no_reassoc_add_nuw_none(
+; CHECK-NEXT: add i32 %x, 68
+define i32 @no_reassoc_add_nuw_none(i32 %x) {
+  %add0 = add i32 %x, 4
+  %add1 = add nuw i32 %add0, 64
+  ret i32 %add1
+}
+
+; CHECK-LABEL: @no_reassoc_add_none_nuw(
+; CHECK-NEXT: add i32 %x, 68
+define i32 @no_reassoc_add_none_nuw(i32 %x) {
+  %add0 = add nuw i32 %x, 4
+  %add1 = add i32 %add0, 64
+  ret i32 %add1
+}
+
+; CHECK-LABEL: @reassoc_x2_add_nuw(
+; CHECK-NEXT: add nuw i32 %x, %y
+; CHECK-NEXT: add nuw i32 %add1, 12
+define i32 @reassoc_x2_add_nuw(i32 %x, i32 %y) {
+  %add0 = add nuw i32 %x, 4
+  %add1 = add nuw i32 %y, 8
+  %add2 = add nuw i32 %add0, %add1
+  ret i32 %add2
+}
+
+; CHECK-LABEL: @reassoc_x2_mul_nuw(
+; CHECK-NEXT: %mul1 = mul i32 %x, %y
+; CHECK-NEXT: %mul2 = mul nuw i32 %mul1, 45
+define i32 @reassoc_x2_mul_nuw(i32 %x, i32 %y) {
+  %mul0 = mul nuw i32 %x, 5
+  %mul1 = mul nuw i32 %y, 9
+  %mul2 = mul nuw i32 %mul0, %mul1
+  ret i32 %mul2
+}
+
+; CHECK-LABEL: @reassoc_x2_sub_nuw(
+; CHECK-NEXT: %sub0 = add i32 %x, -4
+; CHECK-NEXT: %sub1 = add i32 %y, -8
+; CHECK-NEXT: %sub2 = sub nuw i32 %sub0, %sub1
+define i32 @reassoc_x2_sub_nuw(i32 %x, i32 %y) {
+  %sub0 = sub nuw i32 %x, 4
+  %sub1 = sub nuw i32 %y, 8
+  %sub2 = sub nuw i32 %sub0, %sub1
+  ret i32 %sub2
+}

test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll

 ; PROLOG-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[XTRAITER]], 0
 ; PROLOG-NEXT:    br i1 [[TMP1]], label %loop_header.prol.loopexit, label %loop_header.prol.preheader
 ; PROLOG:  loop_header:
 ; PROLOG-NEXT:     %iv = phi i64 [ %iv.unr, %entry.new ], [ %iv_next.7, %loop_latch.7 ]
 ; PROLOG-NEXT:     %sum = phi i64 [ %sum.unr, %entry.new ], [ %sum.next.7, %loop_latch.7 ]
 ; PROLOG:  loop_exiting_bb1.7:
 ; PROLOG-NEXT:     switch i64 %sum.next.6, label %loop_latch.7
 ; PROLOG:  loop_latch.7:
-; PROLOG-NEXT:     %iv_next.7 = add nsw i64 %iv, 8
+; PROLOG-NEXT:     %iv_next.7 = add nuw nsw i64 %iv, 8
 ; PROLOG-NEXT:     %sum.next.7 = add i64 %sum.next.6, %add
 ; PROLOG-NEXT:     %cmp.7 = icmp eq i64 %iv_next.7, %trip
 ; PROLOG-NEXT:     br i1 %cmp.7, label %exit2.loopexit.unr-lcssa, label %loop_header
 entry:
   br label %loop_header
 
 loop_header:
   %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]

 ; PROLOG-NEXT:      br label %exit1
 ; PROLOG:   exit1.loopexit1:
 ; PROLOG-NEXT:      %ivy.prol = add i64 %iv.prol, %add
 ; PROLOG-NEXT:      br label %exit1
 ; PROLOG:   exit1:
 ; PROLOG-NEXT:      %result = phi i64 [ %result.ph, %exit1.loopexit ], [ %ivy.prol, %exit1.loopexit1 ]
 ; PROLOG-NEXT:      ret i64 %result
 ; PROLOG:   loop_latch.7:
-; PROLOG:      %iv_next.7 = add nsw i64 %iv, 8
+; PROLOG:      %iv_next.7 = add nuw nsw i64 %iv, 8
 entry:
   br label %loop_header
 
 loop_header:
   %iv = phi i64 [ 0, %entry ], [ %iv_next, %loop_latch ]
   %sum = phi i64 [ 0, %entry ], [ %sum.next, %loop_latch ]
   br i1 %cond, label %loop_latch, label %loop_exiting
 

  ret i32 %shft
 
 loopexit1:                                             ; preds = %header
   %sext3 = phi i32 [ %shft, %header ]
   ret i32 %sext3
 }
 
 ; Nested loop and inner loop is unrolled
-; FIXME: we cannot unroll with epilog remainder currently, because 
+; FIXME: we cannot unroll with epilog remainder currently, because
 ; the outer loop does not contain the epilog preheader and epilog exit (while
 ; infact it should). This causes us to choke up on LCSSA form being incorrect in
 ; outer loop. However, the exit block where LCSSA fails, is infact still within
 ; the outer loop. For now, we just bail out in presence of outer loop and epilog
 ; loop is generated.
 ; The outer loop header is the preheader for the inner loop and the inner header
 ; branches back to the outer loop.
 define void @test8() {
 ; EPILOG: test8(
 ; EPILOG-NOT: niter
 
 ; PROLOG: test8(
 ; PROLOG: outerloop:
 ; PROLOG-NEXT: phi i64 [ 3, %bb ], [ 0, %outerloop.loopexit ]
 ; PROLOG:      %lcmp.mod = icmp eq i64
 ; PROLOG-NEXT: br i1 %lcmp.mod, label %innerH.prol.loopexit, label %innerH.prol.preheader
 ; PROLOG: latch.6:
-; PROLOG-NEXT: %tmp4.7 = add nsw i64 %tmp3, 8
+; PROLOG-NEXT: %tmp4.7 = add nuw nsw i64 %tmp3, 8
 ; PROLOG-NEXT: br i1 false, label %outerloop.loopexit.loopexit, label %latch.7
 ; PROLOG: latch.7
 ; PROLOG-NEXT: %tmp6.7 = icmp ult i64 %tmp4.7, 100
 ; PROLOG-NEXT: br i1 %tmp6.7, label %innerH, label %exit.unr-lcssa
 bb:
   br label %outerloop
 
 outerloop:                                              ; preds = %innerH, %bb