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

599–600

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

198–231

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

198–231

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

198–231

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

226

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

test/Transforms/InstCombine/reassociate-nuw.ll

1

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

338–344

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 {
   if (!From->isIntegerTy() || !To->isIntegerTy())
     return false;
 
   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 hasNoUnsignedWrap(BinaryOperator &I) {
   OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(&I);
   return OBO && OBO->hasNoUnsignedWrap();
 }
 
 /// 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.
 
           bool IsNUW = hasNoUnsignedWrap(I);
           bool IsNSW = MaintainNoSignedWrap(I, B, C);
 
           ClearSubclassDataAfterReassociation(I);
 
           if (IsNUW && hasNoUnsignedWrap(*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.setHasNoSignedWrap(true);
           }
 
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
         const APInt *CInt;
         if (TopLevelOpcode == Instruction::Add &&
             InnerOpcode == Instruction::Mul)
-          if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue())
+          if (match(V, m_APInt(CInt))) {
+            if (!CInt->isMinSignedValue())
               BO->setHasNoSignedWrap(HasNSW);
+            BO->setHasNoUnsignedWrap(HasNUW);
+          }
       }
     }
   }
   return SimplifiedInst;
 }
 
 /// This tries to simplify binary operations which some other binary operation
 /// distributes over either by factorizing out common terms

test/Transforms/InstCombine/reassociate-nuw.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S %s | FileCheck %s
 
 define i32 @reassoc_add_nuw(i32 %x) {
 ; CHECK-LABEL: @reassoc_add_nuw(
 ; CHECK-NEXT:    [[ADD1:%.*]] = add nuw i32 [[X:%.*]], 68
 ; CHECK-NEXT:    ret i32 [[ADD1]]
 ;
   %add0 = add nuw i32 %x, 4
;
   %sub0 = sub nuw i32 %x, 4
   %sub1 = sub nuw i32 %y, 8
   %sub2 = sub nuw i32 %sub0, %sub1
   ret i32 %sub2
 }
 
 define i32 @tryFactorization_add_nuw_mul_nuw(i32 %x) {
 ; CHECK-LABEL: @tryFactorization_add_nuw_mul_nuw(
-; CHECK-NEXT:    [[ADD2:%.*]] = shl i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[ADD2:%.*]] = shl nuw i32 [[X:%.*]], 2
 ; CHECK-NEXT:    ret i32 [[ADD2]]
 ;
   %mul1 = mul nuw i32 %x, 3
   %add2 = add nuw i32 %mul1, %x
   ret i32 %add2
 }
 
 define i32 @tryFactorization_add_nuw_mul_nuw_int_max(i32 %x) {
 ; CHECK-LABEL: @tryFactorization_add_nuw_mul_nuw_int_max(
-; CHECK-NEXT:    [[ADD2:%.*]] = shl i32 [[X:%.*]], 31
+; CHECK-NEXT:    [[ADD2:%.*]] = shl nuw i32 [[X:%.*]], 31
 ; CHECK-NEXT:    ret i32 [[ADD2]]
 ;
   %mul1 = mul nuw i32 %x, 2147483647
   %add2 = add nuw i32 %mul1, %x
   ret i32 %add2
 }
 
 define i32 @tryFactorization_add_mul_nuw(i32 %x) {