[InstCombine] Propagate the nsw for instruction neg-sub

[Allen]

Summary

proofs: https://alive2.llvm.org/ce/z/xndyAv

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2069

I don't think its okay to modify NegOp1 inplace like this. the flag propagation works in the context of the transform at hand but might not be applicable to all users.

Also this desperately needs some comments.

[Allen]

Add condition Op1->hasOneUse() and its related test src_neg_sub_both_nsw_other_use

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2069

Apply your comment, thanks. Also add a new test src_neg_sub_both_nsw_other_use for the new checking Op1->hasOneUse()

[nikic]

You are making assumptions about the transforms Negator can do here -- in particular that a "sub" is only produced when negating another "sub". This is not correct. E.g. you miscompile this case: https://alive2.llvm.org/ce/z/Q_MiP4

You need to either integrate the flag handling into Negator to make sure it is only applied in the cases where it is actually valid, or you need to make this a separate transform.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2069

You don't seem to have test coverage for the nuw case, and it seems pretty useless to boot. sub nuw 0, %x can only be non-poison if %x is zero. This is not a useful case to handle.

[Allen]

address comments
1、don't propagate the nuw because it seems pretty useless to boot (sub nuw 0, %x can only be non-poison if %x is zero)
2、Reconstructed in negation according to suggestions
3、Add the new negative test neg_and_shl_sub

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2069

Thanks, I delete the nuw case.

[nikic]

Negator should not be inspecting users. You need to pass through the nsw flag from the caller to handle it this way.

[Allen]

pass through the nsw flag from the caller to avoid inspecting users according comment

[Allen]

adjust the code style according https://reviews.llvm.org/D156845#inline-1524491

[arsenm]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

235–242

I think checking hasOneUse twice here is somewhat confusing

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

235–242

Thanks @arsenm for your idea.
I double check the hasOneUse because it may be also here when the I->getOperand(0) is a const value.

[nikic]

I'm going to implement this myself. We need something along these lines, just with full proofs and test coverage: https://gist.github.com/nikic/07bfd88af3607cdb4ba84bdaf299b07f

[Allen]

That's great, thanks very much

[nikic]

For the record, here's the new patch: D158510

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

   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))
+    Instruction *UI = dyn_cast<Instruction>(Op1);
+    // Make sure neg-sub sequence
+    bool IsSub = UI && UI->getOpcode() == Instruction::Sub;
+    if (Value *NegOp1 = Negator::Negate(
+            IsNegation, IsSub && 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 = foldUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   if (I.getType()->isIntOrIntVectorTy(1))
     return BinaryOperator::CreateXor(Op0, Op1);
 

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

   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*/>;

   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.
-  [[nodiscard]] static Value *Negate(bool LHSIsZero, Value *Root,
+  [[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

         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, /*HasNSW*/ false, Op0, *this))
       return BinaryOperator::CreateMul(
           NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName());
 
     // Try to convert multiply of extended operand to narrow negate and shift
     // for better analysis.
     // This is valid if the shift amount (trailing zeros in the multiplier
     // constant) clears more high bits than the bitwidth difference between
     // source and destination types:

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

     }
     break;
   }
   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.
-    return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
-                             I->getName() + ".neg");
+    // Propagate flag nsw only when the single use of the I to avoid affecting
+    // other users.
+    bool Flag =
+        I->hasOneUse() && I->hasNoSignedWrap() && IsTrulyNegation && HasNSW;
+    auto *BO = Builder.CreateSub(I->getOperand(1), I->getOperand(0),
+                                 I->getName() + ".neg");
+    auto *NewI = dyn_cast<BinaryOperator>(BO);
+    if (Flag && NewI)
+      NewI->setHasNoSignedWrap();
+    return BO;
   }
 
   // Some other cases, while still don't require recursion,
   // are restricted to the one-use case.
   if (!V->hasOneUse())
     return nullptr;
 
   switch (I->getOpcode()) {

     // endless combine looping.
     for (Instruction *I : llvm::reverse(NewInstructions))
       I->eraseFromParent();
     return std::nullopt;
   }
   return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
 }
 
-[[nodiscard]] Value *Negator::Negate(bool LHSIsZero, Value *Root,
+[[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);
   std::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/abs-intrinsic.ll

 
 ; https://alive2.llvm.org/ce/z/BSM6UR
 define i32 @sub_abs_sgeT_swap(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_sgeT_swap(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp slt i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub nsw i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp sge i32 %y, %x   ; swap the operands
   br i1 %cmp, label %cond.true, label %cond.end

 
 ; https://alive2.llvm.org/ce/z/BSM6UR
 define i32 @sub_abs_sgeT_false(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_sgeT_false(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT_NOT:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT_NOT]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.false:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub nsw i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp.not = icmp sge i32 %x, %y
   br i1 %cmp.not, label %cond.end, label %cond.false

 }
 
 define i32 @sub_abs_lt(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_lt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub nsw i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp slt i32 %x, %y
   br i1 %cmp, label %cond.true, label %cond.end

 
 ; https://alive2.llvm.org/ce/z/9wQo6G
 define i32 @sub_abs_sle(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_sle(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub nsw i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp sle i32 %x, %y
   br i1 %cmp, label %cond.true, label %cond.end

 }
 
 define i8 @sub_abs_sleT(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sub_abs_sleT(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i8 [[Y]], [[X]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub nsw i8 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
 entry:
   %cmp = icmp sle i8 %x, %y
   br i1 %cmp, label %cond.true, label %cond.end

llvm/test/Transforms/InstCombine/nsw.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
+declare void @foo(i32)
+
 define i32 @sub1(i32 %x) {
 ; CHECK-LABEL: @sub1(
 ; CHECK-NEXT:    [[Y:%.*]] = sub i32 0, [[X:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = sdiv i32 [[Y]], 337
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %y = sub i32 0, %x
   %z = sdiv i32 %y, 337
;
   %t3 = mul <vscale x 2 x i64> %shuf, %xx
   ret <vscale x 2 x i64> %t3
 }
 
 ; This could propagate nsw.
 
 define i32 @neg_sub0_sub_nsw_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: @neg_sub0_sub_nsw_nsw(
-; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; 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
 }
 
+; Negative test: more than one use, https://alive2.llvm.org/ce/z/4QqC-i
+define i32 @neg_sub_both_nsw_other_use(i32 %x, i32 %y) {
+; CHECK-LABEL: @neg_sub_both_nsw_other_use(
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i32 0, [[SUB]]
+; CHECK-NEXT:    call void @foo(i32 [[SUB]])
+; CHECK-NEXT:    ret i32 [[NEG]]
+;
+  %sub = sub nsw i32 %x, %y
+  %neg = sub nsw i32 0, %sub
+  call void @foo (i32 %sub)
+  ret i32 %neg
+}
+
+; Negative test: only process neg sub sequences, https://alive2.llvm.org/ce/z/Q_MiP4
+define i32 @neg_and_shl_sub(i32 %x, i32 %y) {
+; CHECK-LABEL: @neg_and_shl_sub(
+; CHECK-NEXT:    [[NEG:%.*]] = sub i32 0, [[X:%.*]]
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i32 -1, [[NEG]]
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[SHL_NEG]], [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[SUB_NEG]]
+;
+  %neg = sub i32 0, %x
+  %shl = shl i32 1, %neg
+  %sub = add nsw i32 %shl, %y
+  %neg2 = sub nsw i32 0, %sub
+  ret i32 %neg2
+}
+
 ; Must not propagate nsw.
 
 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 nsw i32 0, %c
   ret i32 %d
 }
 
 ; This could propagate nsw.
 
 define i32 @neg_mul_sub_nsw_nsw(i32 %a, i32 %b) {
 ; CHECK-LABEL: @neg_mul_sub_nsw_nsw(
-; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; 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
 }
 
 ; Must not propagate nsw.