[InstCombine] Fix missing nsw flag when fold -(x-y) to y-x

[bcl5980]

Summary

Use CreateNSWSub instead of CreateSub if possible

[nikic]

This is correct if both subs are nsw: https://alive2.llvm.org/ce/z/r6UV8Q But not if only one of them is: https://alive2.llvm.org/ce/z/3_2BDj

[bcl5980]

Only neg is nsw also can createNSWSub
Neg by sub 0 case:
https://alive2.llvm.org/ce/z/KZLr8T
https://alive2.llvm.org/ce/z/lHJc-f
https://alive2.llvm.org/ce/z/pgH3Wd
https://alive2.llvm.org/ce/z/ZwVCtN

Neg by mul -1 case:
https://alive2.llvm.org/ce/z/BwMPtA
https://alive2.llvm.org/ce/z/Vn4pjh
https://alive2.llvm.org/ce/z/rYSowr
https://alive2.llvm.org/ce/z/fA587w

[lebedev.ri]

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

248

CreateSub(I->getOperand(1), I->getOperand(0), I->getName() + ".neg", false, I->hasNoSignedWrap() && HasNSW); ?

[bcl5980]

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013
Maybe we can enable it when IsTrulyNegation ? Abandon is also OK for me.

[lebedev.ri]

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

[bcl5980]

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

Thanks for the detail explaination. So if we really want this work, it should be

bool NSW = I->hasNoSignedWrap() && HasNSW && IsTrulyNegation && Depth == 0;
return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                         I->getName() + ".neg", false, NSW);

or we need to trace every recursive instruction is also NSW, am I right?

[lebedev.ri]

In D122299#3402164, @bcl5980 wrote:

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

Thanks for the detail explaination. So if we really want this work, it should be

bool NSW = I->hasNoSignedWrap() && HasNSW && IsTrulyNegation && Depth == 0;
return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                         I->getName() + ".neg", false, NSW);

or we need to trace every recursive instruction is also NSW, am I right?

I believe that is the idea, yes.

[bcl5980]

Thanks again @lebedev.ri. I will update the code to

bool NSW = I->hasNoSignedWrap() && HasNSW && IsTrulyNegation && Depth == 0;
return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                         I->getName() + ".neg", false, NSW);

but if there is no other comments I prefer to abandon it.

[bcl5980]

only depth == 0 enable nsw flag

[spatel]

I'm fine with abandoning the code change. I just wanted to make sure we were not miscompiling in D122013.

I would commit the tests anyway with some comments or a link back to this review (in case this comes up again in the future in some other context).

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) {
   if (!IsNegation || none_of(I.users(), [&I, Op1](const User *U) {
         const Instruction *UI = dyn_cast<Instruction>(U);
         if (!UI)
           return false;
         return match(UI,
                      m_Select(m_Value(), m_Specific(Op1), m_Specific(&I))) ||
                match(UI, m_Select(m_Value(), m_Specific(&I), m_Specific(Op1)));
       })) {
-    if (Value *NegOp1 = Negator::Negate(IsNegation, Op1, *this))
+    if (Value *NegOp1 =
+            Negator::Negate(IsNegation, I.hasNoSignedWrap(), Op1, *this))
       return BinaryOperator::CreateAdd(NegOp1, Op0);
   }
   if (IsNegation)
     return TryToNarrowDeduceFlags(); // Should have been handled in Negator!
 
   // (A*B)-(A*C) -> A*(B-C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

class Negator final {
   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
   BuilderTy Builder;
 
   const DataLayout &DL;
   AssumptionCache &AC;
   const DominatorTree &DT;
 
   const bool IsTrulyNegation;
+  const bool HasNSW;
 
   SmallDenseMap<Value *, Value *> NegationsCache;
 
   Negator(LLVMContext &C, const DataLayout &DL, AssumptionCache &AC,
-          const DominatorTree &DT, bool IsTrulyNegation);
+          const DominatorTree &DT, bool IsTrulyNegation, bool HasNSW);
 
 #if LLVM_ENABLE_STATS
   unsigned NumValuesVisitedInThisNegator = 0;
   ~Negator();
 #endif
 
   using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
                            Value * /*NegatedRoot*/>;
#endif
   Negator(const Negator &) = delete;
   Negator(Negator &&) = delete;
   Negator &operator=(const Negator &) = delete;
   Negator &operator=(Negator &&) = delete;
 
 public:
   /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
   /// otherwise returns negated value.
-  LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
+  LLVM_NODISCARD static Value *Negate(bool LHSIsZero, bool HasNSW, Value *Root,
                                       InstCombinerImpl &IC);
 };
 
 } // end namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
         return Shl;
       }
     }
   }
 
   if (Op0->hasOneUse() && match(Op1, m_NegatedPower2())) {
     // Interpret  X * (-1<<C)  as  (-X) * (1<<C)  and try to sink the negation.
     // The "* (1<<C)" thus becomes a potential shifting opportunity.
-    if (Value *NegOp0 = Negator::Negate(/*IsNegation*/ true, Op0, *this))
+    if (Value *NegOp0 = Negator::Negate(/*IsNegation*/ true,
+                                        I.hasNoSignedWrap(), Op0, *this))
       return BinaryOperator::CreateMul(
           NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName());
   }
 
   if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
     return FoldedMul;
 
   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

 
 static cl::opt<unsigned>
     NegatorMaxDepth("instcombine-negator-max-depth",
                     cl::init(NegatorDefaultMaxDepth),
                     cl::desc("What is the maximal lookup depth when trying to "
                              "check for viability of negation sinking."));
 
 Negator::Negator(LLVMContext &C, const DataLayout &DL_, AssumptionCache &AC_,
-                 const DominatorTree &DT_, bool IsTrulyNegation_)
+                 const DominatorTree &DT_, bool IsTrulyNegation_, bool HasNSW_)
     : Builder(C, TargetFolder(DL_),
               IRBuilderCallbackInserter([&](Instruction *I) {
                 ++NegatorNumInstructionsCreatedTotal;
                 NewInstructions.push_back(I);
               })),
-      DL(DL_), AC(AC_), DT(DT_), IsTrulyNegation(IsTrulyNegation_) {}
+      DL(DL_), AC(AC_), DT(DT_), IsTrulyNegation(IsTrulyNegation_),
+      HasNSW(HasNSW_) {}
 
 #if LLVM_ENABLE_STATS
 Negator::~Negator() {
   NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
 }
 #endif
 
 // Due to the InstCombine's worklist management, there are no guarantees that
default:
     break; // Other instructions require recursive reasoning.
   }
 
   if (I->getOpcode() == Instruction::Sub &&
       (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
     // `sub` is always negatible.
     // However, only do this either if the old `sub` doesn't stick around, or
     // it was subtracting from a constant. Otherwise, this isn't profitable.
+    if (I->hasNoSignedWrap() && HasNSW)
+      return Builder.CreateNSWSub(I->getOperand(1), I->getOperand(0),
+                                  I->getName() + ".neg");
     return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                              I->getName() + ".neg");
   }
 
   // Some other cases, while still don't require recursion,
   // are restricted to the one-use case.
   if (!V->hasOneUse())
     return nullptr;
 
   switch (I->getOpcode()) {
   case Instruction::And: {
     Constant *ShAmt;
if (!Negated) {
     // endless combine looping.
     for (Instruction *I : llvm::reverse(NewInstructions))
       I->eraseFromParent();
     return llvm::None;
   }
   return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
 }
 
-LLVM_NODISCARD Value *Negator::Negate(bool LHSIsZero, Value *Root,
+LLVM_NODISCARD Value *Negator::Negate(bool LHSIsZero, bool HasNSW, Value *Root,
                                       InstCombinerImpl &IC) {
   ++NegatorTotalNegationsAttempted;
   LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
                     << "\n");
 
   if (!NegatorEnabled || !DebugCounter::shouldExecute(NegatorCounter))
     return nullptr;
 
   Negator N(Root->getContext(), IC.getDataLayout(), IC.getAssumptionCache(),
-            IC.getDominatorTree(), LHSIsZero);
+            IC.getDominatorTree(), LHSIsZero, HasNSW);
   Optional<Result> Res = N.run(Root);
   if (!Res) { // Negation failed.
     LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
                       << "\n");
     return nullptr;
   }
 
   LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root

llvm/test/Transforms/InstCombine/nsw.ll

 ; CHECK-NEXT:    [[T3:%.*]] = mul <vscale x 2 x i64> [[XX]], shufflevector (<vscale x 2 x i64> insertelement (<vscale x 2 x i64> undef, i64 3, i32 0), <vscale x 2 x i64> zeroinitializer, <vscale x 2 x i32> zeroinitializer)
 ; CHECK-NEXT:    ret <vscale x 2 x i64> [[T3]]
 ;
   %xx = zext <vscale x 2 x i8> %z to <vscale x 2 x i64>
   %shuf = shufflevector <vscale x 2 x i64> insertelement (<vscale x 2 x i64> undef, i64 3, i32 0), <vscale x 2 x i64> zeroinitializer, <vscale x 2 x i32> zeroinitializer
   %t3 = mul <vscale x 2 x i64> %shuf, %xx
   ret <vscale x 2 x i64> %t3
 }
+
+define i32 @neg_sub0_sub_nsw_nsw(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_sub0_sub_nsw_nsw(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub nsw i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = sub nsw i32 0, %c
+  ret i32 %d
+}
+
+define i32 @neg_sub_sub_nsw0(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_sub_sub_nsw0(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = sub i32 0, %c
+  ret i32 %d
+}
+
+define i32 @neg_sub_sub_nsw1(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_sub_sub_nsw1(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub i32 %a, %b
+  %d = sub nsw i32 0, %c
+  ret i32 %d
+}
+
+define i32 @neg_sub_sub(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_sub_sub(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = sub i32 0, %c
+  ret i32 %d
+}
+
+define i32 @neg_mul_sub_nsw_nsw(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_mul_sub_nsw_nsw(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub nsw i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = mul nsw i32 -1, %c
+  ret i32 %d
+}
+
+define i32 @neg_mul_sub_nsw0(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_mul_sub_nsw0(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = mul i32 -1, %c
+  ret i32 %d
+}
+
+define i32 @neg_mul_sub_nsw1(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_mul_sub_nsw1(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub i32 %a, %b
+  %d = mul nsw i32 -1, %c
+  ret i32 %d
+}
+
+define i32 @neg_mul_sub(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_mul_sub(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = mul i32 -1, %c
+  ret i32 %d
+}