[Reassociate] Better preserve NSW/NUW flags. (PR12985)

[mcrosier]

Summary

This change better preserves the NSW/NUW flags in the reassociation pass.

Part of PR12985.

[majnemer]

This transform is not safe for nsw shl, it will transform %shl = shl nsw i32 %a, 31 into %shl = mul nsw i32 %a, -2147483648

If %a is -1, %shl should hold INT_MIN. Instead, it will transform it into poison.

However, I think it's fine to turn a nuw shl into an nuw mul in all cases.
I think you can also turn an nuw nsw shl into an nuw nsw mul.

test/Transforms/Reassociate/wrap-flags.ll

16–27

This transform isn't sound if %y is INT_MIN, %add would be transformed from something valid into poison.

[mcrosier]

Addressed David's comments.

[majnemer]

lib/Transforms/Scalar/Reassociate.cpp

1050–1056

Shouldn't this be:

if (NSW && NUW)

?

[mcrosier]

lib/Transforms/Scalar/Reassociate.cpp

1050–1056

The logic is the same, but in the case that NSW is false it will avoid the call to the ineffectual setHasNoSignedWrap.

I'll fix this.. thanks!

[mcrosier]

Minor tweak to avoid unnecessary call to setter.

[majnemer]

LGTM with tweaks.

lib/Transforms/Scalar/Reassociate.cpp

1056

This can just be Mul->setHasNoSignedWrap(true);

[mcrosier]

Thanks, David! Committed in r221555.

lib/Transforms/Scalar/Reassociate.cpp

static BinaryOperator *BreakUpSubtract(Instruction *Sub) {
   Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op.
   Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op.
   New->takeName(Sub);
 
   // Everyone now refers to the add instruction.
   Sub->replaceAllUsesWith(New);
   New->setDebugLoc(Sub->getDebugLoc());
 
+  // Preserve NSW/NUW flags.
+  if (Sub->getOpcode() == Instruction::Sub) {
+    bool NSW = cast<BinaryOperator>(Sub)->hasNoSignedWrap();
+    bool NUW = cast<BinaryOperator>(Sub)->hasNoUnsignedWrap();
+    New->setHasNoSignedWrap(NSW);
+    New->setHasNoUnsignedWrap(NUW);
+    if (BinaryOperator *NegBO = dyn_cast<BinaryOperator>(NegVal)) {
+      NegBO->setHasNoSignedWrap(NSW);
+      NegBO->setHasNoUnsignedWrap(NUW);
+    }
+  }
   DEBUG(dbgs() << "Negated: " << *New << '\n');
   return New;
 }
 
 /// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used
 /// by one, change this into a multiply by a constant to assist with further
 /// reassociation.
 static BinaryOperator *ConvertShiftToMul(Instruction *Shl) {
   Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
   MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1)));
 
   BinaryOperator *Mul =
     BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
   Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op.
   Mul->takeName(Shl);
+
+  // Everyone now refers to the mul instruction.
   Shl->replaceAllUsesWith(Mul);
   Mul->setDebugLoc(Shl->getDebugLoc());
+
+  // Preserve NSW/NUW flags.
+  Mul->setHasNoSignedWrap(cast<BinaryOperator>(Shl)->hasNoSignedWrap());
+  Mul->setHasNoUnsignedWrap(cast<BinaryOperator>(Shl)->hasNoUnsignedWrap());
   return Mul;
 }
 
 /// FindInOperandList - Scan backwards and forwards among values with the same
 /// rank as element i to see if X exists.  If X does not exist, return i.  This
 /// is useful when scanning for 'x' when we see '-x' because they both get the
 /// same rank.
 static unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i,
                                   Value *X) {
   unsigned XRank = Ops[i].Rank;
   unsigned e = Ops.size();
   for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {

test/Transforms/Reassociate/wrap-flags.ll

+; RUN: opt < %s -reassociate -dce -S | FileCheck %s
+; PR12985
+
+; Verify the nsw flag is preserved when converting shl to mul.
+; CHECK-LABEL: @shl_to_mul(
+; CHECK: %mul = mul nsw i32 %i, 4
+; CHECK: %mul2 = add nsw i32 %mul, 1
+
+define i32 @shl_to_mul(i32 %i) {
+entry:
+  %mul = shl nsw i32 %i, 2
+  %mul2 = add nsw i32 %mul, 1
+  ret i32 %mul2
+}
+
+; Verify the nsw flag is preserved when converting (X-Y)->(X+(0-Y)).
+; CHECK-LABEL: @breakup_sub(
+; CHECK: %y.neg = sub nsw i32 0, %y
+; CHECK: %sub = add nsw i32 %y.neg, %x
+; CHECK: %add = add nsw i32 %sub, %z
+
+define i32 @breakup_sub(i32 %x, i32 %y, i32 %z) {
+entry:
+  %sub = sub nsw i32 %x, %y
+  %add = add nsw i32 %sub, %z
+  ret i32 %add
+}