[InstCombine] Propagate nsw flag when negating

[nikic]

Summary

When pushing a sub nsw 0, %x negation into an expression, try to preserve the nsw flag for the cases where this is possible. Do this by passing the flag through recursive Negator::negate() calls.

Proofs: https://alive2.llvm.org/ce/z/oRPNcY

[goldstein.w.n]

All of these except the -1 << X case work for NUW as well: https://alive2.llvm.org/ce/z/zzPZRQ
Maybe instead of a bool pass a bitmask of flags? Would make it easier to add NUW support in a followup.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

261–268

You can have NSW on this mul given that Op1 is a constant.

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

241

Nit: I would rename IsNSW to MayNSW or ParentNSW as that seems to more accurately represent the usage.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

306

Why does freeze kill nsw?

[nikic]

In D158510#4607222, @goldstein.w.n wrote:

All of these except the -1 << X case work for NUW as well: https://alive2.llvm.org/ce/z/zzPZRQ
Maybe instead of a bool pass a bitmask of flags? Would make it easier to add NUW support in a followup.

sub nuw 0, %x is only non-poison when %x is zero. For that reason, it's not really something that occurs in practice, so I don't think it's worth handling.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

261–268

I don't think you can add nsw on the mul if I got this right: https://alive2.llvm.org/ce/z/lSk99J

Though it looks like passing nsw to the negator would be okay: https://alive2.llvm.org/ce/z/MrwT5K

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

306

Hm, looks like it's okay to keep nsw: https://alive2.llvm.org/ce/z/vnYqoi That's quite unexpected to me.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

261–268

You have it right, the idea though is that since Op1 is a constant we can infer when it would be NSW i.e:
https://alive2.llvm.org/ce/z/6JPtJR

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

261–268

edit: Actually you can just propagate the NSW flag i.e:
https://alive2.llvm.org/ce/z/Xw992v

[nikic]

Handle freeze, handle nsw in mul by neg pow 2 fold.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

241

The intention here was that IsNSW refers to whether the negation is nsw.

[nikic]

ping

[goldstein.w.n]

Lgtm

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, /* IsNSW */ 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 = foldUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

#if LLVM_ENABLE_STATS
   ~Negator();
 #endif
 
   using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
                            Value * /*NegatedRoot*/>;
 
   std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
 
-  [[nodiscard]] Value *visitImpl(Value *V, unsigned Depth);
+  [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth);
 
-  [[nodiscard]] Value *negate(Value *V, unsigned Depth);
+  [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth);
 
   /// Recurse depth-first and attempt to sink the negation.
   /// FIXME: use worklist?
-  [[nodiscard]] std::optional<Result> run(Value *Root);
+  [[nodiscard]] std::optional<Result> run(Value *Root, bool IsNSW);
 
   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 IsNSW, 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))
-      return BinaryOperator::CreateMul(
-          NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName());
+    if (Value *NegOp0 =
+            Negator::Negate(/*IsNegation*/ true, HasNSW, Op0, *this)) {
+      auto *Op1C = cast<Constant>(Op1);
+      return replaceInstUsesWith(
+          I, Builder.CreateMul(NegOp0, ConstantExpr::getNeg(Op1C), "",
+                               /* HasNUW */ false,
+                               HasNSW && Op1C->isNotMinSignedValue()));
+    }
 
     // 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:
     // ({z/s}ext X) * (-1<<C) --> (zext (-X)) << C
     const APInt *NegPow2C;

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(Instruction *I) {
   if (I->isCommutative() && InstCombiner::getComplexity(I->getOperand(0)) <
                                 InstCombiner::getComplexity(I->getOperand(1)))
     std::swap(Ops[0], Ops[1]);
   return Ops;
 }
 
 // FIXME: can this be reworked into a worklist-based algorithm while preserving
 // the depth-first, early bailout traversal?
-[[nodiscard]] Value *Negator::visitImpl(Value *V, unsigned Depth) {
+[[nodiscard]] Value *Negator::visitImpl(Value *V, bool IsNSW, unsigned Depth) {
   // -(undef) -> undef.
   if (match(V, m_Undef()))
     return V;
 
   // In i1, negation can simply be ignored.
   if (V->getType()->isIntOrIntVectorTy(1))
     return V;
 
[[nodiscard]] Value *Negator::visitImpl(Value *V, bool IsNSW, unsigned Depth) {
   }
 
   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");
+                             I->getName() + ".neg", /* HasNUW */ false,
+                             IsNSW && I->hasNoSignedWrap());
   }
 
   // Some other cases, while still don't require recursion,
   // are restricted to the one-use case.
   if (!V->hasOneUse())
     return nullptr;
 
   switch (I->getOpcode()) {
LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
                       << *V << ". Giving up.\n");
     ++NegatorTimesDepthLimitReached;
     return nullptr;
   }
 
   switch (I->getOpcode()) {
   case Instruction::Freeze: {
     // `freeze` is negatible if its operand is negatible.
-    Value *NegOp = negate(I->getOperand(0), Depth + 1);
+    Value *NegOp = negate(I->getOperand(0), IsNSW, Depth + 1);
     if (!NegOp) // Early return.
       return nullptr;
     return Builder.CreateFreeze(NegOp, I->getName() + ".neg");
   }
   case Instruction::PHI: {
     // `phi` is negatible if all the incoming values are negatible.
     auto *PHI = cast<PHINode>(I);
     SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
     for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
       if (!(std::get<1>(I) =
-                negate(std::get<0>(I), Depth + 1))) // Early return.
+                negate(std::get<0>(I), IsNSW, Depth + 1))) // Early return.
         return nullptr;
     }
     // All incoming values are indeed negatible. Create negated PHI node.
     PHINode *NegatedPHI = Builder.CreatePHI(
         PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");
     for (auto I : zip(NegatedIncomingValues, PHI->blocks()))
       NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));
     return NegatedPHI;
   }
   case Instruction::Select: {
     if (isKnownNegation(I->getOperand(1), I->getOperand(2))) {
       // Of one hand of select is known to be negation of another hand,
       // just swap the hands around.
       auto *NewSelect = cast<SelectInst>(I->clone());
       // Just swap the operands of the select.
       NewSelect->swapValues();
       // Don't swap prof metadata, we didn't change the branch behavior.
       NewSelect->setName(I->getName() + ".neg");
       Builder.Insert(NewSelect);
       return NewSelect;
     }
     // `select` is negatible if both hands of `select` are negatible.
-    Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
+    Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);
     if (!NegOp1) // Early return.
       return nullptr;
-    Value *NegOp2 = negate(I->getOperand(2), Depth + 1);
+    Value *NegOp2 = negate(I->getOperand(2), IsNSW, Depth + 1);
     if (!NegOp2)
       return nullptr;
     // Do preserve the metadata!
     return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
                                 I->getName() + ".neg", /*MDFrom=*/I);
   }
   case Instruction::ShuffleVector: {
     // `shufflevector` is negatible if both operands are negatible.
     auto *Shuf = cast<ShuffleVectorInst>(I);
-    Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
+    Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1);
     if (!NegOp0) // Early return.
       return nullptr;
-    Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
+    Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);
     if (!NegOp1)
       return nullptr;
     return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
                                        I->getName() + ".neg");
   }
   case Instruction::ExtractElement: {
     // `extractelement` is negatible if source operand is negatible.
     auto *EEI = cast<ExtractElementInst>(I);
-    Value *NegVector = negate(EEI->getVectorOperand(), Depth + 1);
+    Value *NegVector = negate(EEI->getVectorOperand(), IsNSW, Depth + 1);
     if (!NegVector) // Early return.
       return nullptr;
     return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
                                         I->getName() + ".neg");
   }
   case Instruction::InsertElement: {
     // `insertelement` is negatible if both the source vector and
     // element-to-be-inserted are negatible.
     auto *IEI = cast<InsertElementInst>(I);
-    Value *NegVector = negate(IEI->getOperand(0), Depth + 1);
+    Value *NegVector = negate(IEI->getOperand(0), IsNSW, Depth + 1);
     if (!NegVector) // Early return.
       return nullptr;
-    Value *NegNewElt = negate(IEI->getOperand(1), Depth + 1);
+    Value *NegNewElt = negate(IEI->getOperand(1), IsNSW, Depth + 1);
     if (!NegNewElt) // Early return.
       return nullptr;
     return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
                                        I->getName() + ".neg");
   }
   case Instruction::Trunc: {
     // `trunc` is negatible if its operand is negatible.
-    Value *NegOp = negate(I->getOperand(0), Depth + 1);
+    Value *NegOp = negate(I->getOperand(0), /* IsNSW */ false, Depth + 1);
     if (!NegOp) // Early return.
       return nullptr;
     return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
   }
   case Instruction::Shl: {
     // `shl` is negatible if the first operand is negatible.
-    if (Value *NegOp0 = negate(I->getOperand(0), Depth + 1))
-      return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg");
+    IsNSW &= I->hasNoSignedWrap();
+    if (Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1))
+      return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg",
+                               /* HasNUW */ false, IsNSW);
     // Otherwise, `shl %x, C` can be interpreted as `mul %x, 1<<C`.
     auto *Op1C = dyn_cast<Constant>(I->getOperand(1));
     if (!Op1C || !IsTrulyNegation)
       return nullptr;
     return Builder.CreateMul(
         I->getOperand(0),
         ConstantExpr::getShl(Constant::getAllOnesValue(Op1C->getType()), Op1C),
-        I->getName() + ".neg");
+        I->getName() + ".neg", /* HasNUW */ false, IsNSW);
   }
   case Instruction::Or: {
     if (!haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1), DL, &AC, I,
                              &DT))
       return nullptr; // Don't know how to handle `or` in general.
     std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
     // `or`/`add` are interchangeable when operands have no common bits set.
     // `inc` is always negatible.
     if (match(Ops[1], m_One()))
       return Builder.CreateNot(Ops[0], I->getName() + ".neg");
     // Else, just defer to Instruction::Add handling.
     [[fallthrough]];
   }
   case Instruction::Add: {
     // `add` is negatible if both of its operands are negatible.
     SmallVector<Value *, 2> NegatedOps, NonNegatedOps;
     for (Value *Op : I->operands()) {
       // Can we sink the negation into this operand?
-      if (Value *NegOp = negate(Op, Depth + 1)) {
+      if (Value *NegOp = negate(Op, /* IsNSW */ false, Depth + 1)) {
         NegatedOps.emplace_back(NegOp); // Successfully negated operand!
         continue;
       }
       // Failed to sink negation into this operand. IFF we started from negation
       // and we manage to sink negation into one operand, we can still do this.
       if (!IsTrulyNegation)
         return nullptr;
       NonNegatedOps.emplace_back(Op); // Just record which operand that was.
case Instruction::Xor: {
     return nullptr;
   }
   case Instruction::Mul: {
     std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);
     // `mul` is negatible if one of its operands is negatible.
     Value *NegatedOp, *OtherOp;
     // First try the second operand, in case it's a constant it will be best to
     // just invert it instead of sinking the `neg` deeper.
-    if (Value *NegOp1 = negate(Ops[1], Depth + 1)) {
+    if (Value *NegOp1 = negate(Ops[1], /* IsNSW */ false, Depth + 1)) {
       NegatedOp = NegOp1;
       OtherOp = Ops[0];
-    } else if (Value *NegOp0 = negate(Ops[0], Depth + 1)) {
+    } else if (Value *NegOp0 = negate(Ops[0], /* IsNSW */ false, Depth + 1)) {
       NegatedOp = NegOp0;
       OtherOp = Ops[1];
     } else
       // Can't negate either of them.
       return nullptr;
-    return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg");
+    return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg",
+                             /* HasNUW */ false, IsNSW && I->hasNoSignedWrap());
   }
   default:
     return nullptr; // Don't know, likely not negatible for free.
   }
 
   llvm_unreachable("Can't get here. We always return from switch.");
 }
 
-[[nodiscard]] Value *Negator::negate(Value *V, unsigned Depth) {
+[[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) {
   NegatorMaxDepthVisited.updateMax(Depth);
   ++NegatorNumValuesVisited;
 
 #if LLVM_ENABLE_STATS
   ++NumValuesVisitedInThisNegator;
 #endif
 
 #ifndef NDEBUG

 #ifndef NDEBUG
   // We did not find a cached result for negation of V. While there,
   // let's temporairly cache a placeholder value, with the idea that if later
   // during negation we fetch it from cache, we'll know we're in a cycle.
   NegationsCache[V] = Placeholder;
 #endif
 
   // No luck. Try negating it for real.
-  Value *NegatedV = visitImpl(V, Depth);
+  Value *NegatedV = visitImpl(V, IsNSW, Depth);
   // And cache the (real) result for the future.
   NegationsCache[V] = NegatedV;
 
   return NegatedV;
 }
 
-[[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root) {
-  Value *Negated = negate(Root, /*Depth=*/0);
+[[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root,
+                                                          bool IsNSW) {
+  Value *Negated = negate(Root, IsNSW, /*Depth=*/0);
   if (!Negated) {
     // We must cleanup newly-inserted instructions, to avoid any potential
     // 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 IsNSW, 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);
-  std::optional<Result> Res = N.run(Root);
+  std::optional<Result> Res = N.run(Root, IsNSW);
   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
                     << "\n         NEW: " << *Res->second << "\n");

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/mul.ll

 ;
   %sub = sub <2 x i32> <i32 16, i32 32>, %a0
   %mul = mul <2 x i32> %sub, <i32 -4, i32 undef>
   ret <2 x i32> %mul
 }
 
 define i8 @mulsub_nsw(i8 %a1, i8 %a2) {
 ; CHECK-LABEL: @mulsub_nsw(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
-; CHECK-NEXT:    [[MUL:%.*]] = shl i8 [[A_NEG]], 1
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[MUL:%.*]] = shl nsw i8 [[A_NEG]], 1
 ; CHECK-NEXT:    ret i8 [[MUL]]
 ;
   %a = sub nsw i8 %a1, %a2
   %mul = mul nsw i8 %a, -2
   ret i8 %mul
 }
 
+; It would be safe to keep the nsw on the shl here, but only because the mul
+; to shl transform happens to replace undef with 0.
 define <2 x i8> @mulsub_nsw_undef(<2 x i8> %a1, <2 x i8> %a2) {
 ; CHECK-LABEL: @mulsub_nsw_undef(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub <2 x i8> [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
 ; CHECK-NEXT:    [[MUL:%.*]] = shl <2 x i8> [[A_NEG]], <i8 1, i8 0>
 ; CHECK-NEXT:    ret <2 x i8> [[MUL]]
 ;
   %a = sub nsw <2 x i8> %a1, %a2
   %mul = mul nsw <2 x i8> %a, <i8 -2, i8 undef>
   ret <2 x i8> %mul
 }
 

llvm/test/Transforms/InstCombine/nsw.ll

;
   %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
 }
 
 ; Must not propagate nsw.
;
   %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.

 ;
   %s1 = sub nsw i32 %a, %b
   %s2 = sub nsw i32 %c, %s1
   ret i32 %s2
 }
 
 define i8 @neg_nsw_freeze(i8 %a1, i8 %a2) {
 ; CHECK-LABEL: @neg_nsw_freeze(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
 ; CHECK-NEXT:    [[FR_NEG:%.*]] = freeze i8 [[A_NEG]]
 ; CHECK-NEXT:    ret i8 [[FR_NEG]]
 ;
   %a = sub nsw i8 %a1, %a2
   %fr = freeze i8 %a
   %neg = sub nsw i8 0, %fr
   ret i8 %neg
 }
 
 define i8 @neg_nsw_phi(i1 %c, i8 %a1, i8 %a2, i8 %b1, i8 %b2) {
 ; CHECK-LABEL: @neg_nsw_phi(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
 ; CHECK-NEXT:    br label [[JOIN:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    [[B_NEG:%.*]] = sub i8 [[B2:%.*]], [[B1:%.*]]
+; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw i8 [[B2:%.*]], [[B1:%.*]]
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
 ; CHECK-NEXT:    [[PHI_NEG:%.*]] = phi i8 [ [[A_NEG]], [[IF]] ], [ [[B_NEG]], [[ELSE]] ]
 ; CHECK-NEXT:    ret i8 [[PHI_NEG]]
 ;
   br i1 %c, label %if, label %else
 
 if:
   %a = sub nsw i8 %a1, %a2
   br label %join
 
 else:
   %b = sub nsw i8 %b1, %b2
   br label %join
 
 join:
   %phi = phi i8 [ %a, %if ], [ %b, %else ]
   %neg = sub nsw i8 0, %phi
   ret i8 %neg
 }
 
 define i8 @neg_nsw_select(i1 %c, i8 %a1, i8 %a2, i8 %b1, i8 %b2) {
 ; CHECK-LABEL: @neg_nsw_select(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
-; CHECK-NEXT:    [[B_NEG:%.*]] = sub i8 [[B2:%.*]], [[B1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw i8 [[B2:%.*]], [[B1:%.*]]
 ; CHECK-NEXT:    [[SEL_NEG:%.*]] = select i1 [[C:%.*]], i8 [[A_NEG]], i8 [[B_NEG]]
 ; CHECK-NEXT:    ret i8 [[SEL_NEG]]
 ;
   %a = sub nsw i8 %a1, %a2
   %b = sub nsw i8 %b1, %b2
   %sel = select i1 %c, i8 %a, i8 %b
   %neg = sub nsw i8 0, %sel
   ret i8 %neg
 }
 
 define <4 x i8> @neg_nsw_shufflevector(<2 x i8> %a1, <2 x i8> %a2, <2 x i8> %b1, <2 x i8> %b2) {
 ; CHECK-LABEL: @neg_nsw_shufflevector(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub <2 x i8> [[A2:%.*]], [[A1:%.*]]
-; CHECK-NEXT:    [[B_NEG:%.*]] = sub <2 x i8> [[B2:%.*]], [[B1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw <2 x i8> [[B2:%.*]], [[B1:%.*]]
 ; CHECK-NEXT:    [[SHUF_NEG:%.*]] = shufflevector <2 x i8> [[A_NEG]], <2 x i8> [[B_NEG]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
 ; CHECK-NEXT:    ret <4 x i8> [[SHUF_NEG]]
 ;
   %a = sub nsw <2 x i8> %a1, %a2
   %b = sub nsw <2 x i8> %b1, %b2
   %shuf = shufflevector <2 x i8> %a, <2 x i8> %b, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
   %neg = sub nsw <4 x i8> zeroinitializer, %shuf
   ret <4 x i8> %neg
 }
 
 define i8 @neg_nsw_extractelement(<2 x i8> %a1, <2 x i8> %a2) {
 ; CHECK-LABEL: @neg_nsw_extractelement(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub <2 x i8> [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
 ; CHECK-NEXT:    [[EXTR_NEG:%.*]] = extractelement <2 x i8> [[A_NEG]], i64 0
 ; CHECK-NEXT:    ret i8 [[EXTR_NEG]]
 ;
   %a = sub nsw <2 x i8> %a1, %a2
   %extr = extractelement <2 x i8> %a, i32 0
   %neg = sub nsw i8 0, %extr
   ret i8 %neg
 }
 
 define <2 x i8> @neg_nsw_insertelement(<2 x i8> %a1, <2 x i8> %a2, i8 %b1, i8 %b2) {
 ; CHECK-LABEL: @neg_nsw_insertelement(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub <2 x i8> [[A2:%.*]], [[A1:%.*]]
-; CHECK-NEXT:    [[B_NEG:%.*]] = sub i8 [[B2:%.*]], [[B1:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw i8 [[B2:%.*]], [[B1:%.*]]
 ; CHECK-NEXT:    [[INSERT_NEG:%.*]] = insertelement <2 x i8> [[A_NEG]], i8 [[B_NEG]], i64 0
 ; CHECK-NEXT:    ret <2 x i8> [[INSERT_NEG]]
 ;
   %a = sub nsw <2 x i8> %a1, %a2
   %b = sub nsw i8 %b1, %b2
   %insert  = insertelement <2 x i8> %a, i8 %b, i32 0
   %neg = sub nsw <2 x i8> zeroinitializer, %insert
   ret <2 x i8> %neg
 }
 
 define i8 @neg_nsw_shl(i8 %a1, i8 %a2, i8 %b) {
 ; CHECK-LABEL: @neg_nsw_shl(
-; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
-; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i8 [[A_NEG]], [[B:%.*]]
+; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl nsw i8 [[A_NEG]], [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[SHL_NEG]]
 ;
   %a = sub nsw i8 %a1, %a2
   %shl = shl nsw i8 %a, %b
   %neg = sub nsw i8 0, %shl
   ret i8 %neg
 }
 
 define i8 @neg_nsw_shl_missing_nsw_on_shl(i8 %a1, i8 %a2, i8 %b) {
 ; CHECK-LABEL: @neg_nsw_shl_missing_nsw_on_shl(
 ; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
 ; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i8 [[A_NEG]], [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[SHL_NEG]]
 ;
   %a = sub nsw i8 %a1, %a2
   %shl = shl i8 %a, %b
   %neg = sub nsw i8 0, %shl
   ret i8 %neg
 }
 
 define i8 @neg_nsw_shl_to_mul(i8 %a, i8 %b) {
 ; CHECK-LABEL: @neg_nsw_shl_to_mul(
-; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul nsw i8 [[A:%.*]], -2
 ; CHECK-NEXT:    ret i8 [[SHL_NEG]]
 ;
   %shl = shl nsw i8 %a, 1
   %neg = sub nsw i8 0, %shl
   ret i8 %neg
 }
 
 define i8 @neg_nsw_shl_to_mul_missing_nsw_on_shl(i8 %a, i8 %b) {
 ; CHECK-LABEL: @neg_nsw_shl_to_mul_missing_nsw_on_shl(
 ; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul i8 [[A:%.*]], -2
 ; CHECK-NEXT:    ret i8 [[SHL_NEG]]
 ;
   %shl = shl i8 %a, 1
   %neg = sub nsw i8 0, %shl
   ret i8 %neg
 }
 
 define i8 @neg_nsw_mul(i8 %a1, i8 %a2, i8 %b) {
 ; CHECK-LABEL: @neg_nsw_mul(
 ; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
-; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul i8 [[A_NEG]], [[B:%.*]]
+; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul nsw i8 [[A_NEG]], [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[SHL_NEG]]
 ;
   %a = sub nsw i8 %a1, %a2
   %shl = mul nsw i8 %a, %b
   %neg = sub nsw i8 0, %shl
   ret i8 %neg
 }