[InstCombine] Fold x + (x | -x) to x & (x - 1)

[marcauberer]

Summary

Fixes #57531

This transformation may be particularly useful on x86-64, because x & (x - 1) can be performed by a single blsr instruction.

[RKSimon]

Sorry for the short/blunt comments - running out of time today!

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1403

Use m_Neg()? Also, you need to use m_Deferred() for those later m_Value()

llvm/test/Transforms/InstCombine/add_or_sub.ll

26

vector cases? multiuse cases? negative cases?

[marcauberer]

Improve, format and add tests

[marcauberer]

@RKSimon thanks for the review. I've uploaded improvements. Just one question left ...

llvm/test/Transforms/InstCombine/add_or_sub.ll

26

I just added vector and multi-use cases. How do I do negative cases?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1399–1402

This shows the expected set of commuted variants of the general pattern, but I don't think the match is handling all of them.

You'll want to add tests for each of these variations, and that's going to require some bonus instructions to make the patterns stick until we reach this point in visitAdd().

Here are some tests that I recently added that can serve as templates - note especially the lines with "thwart complexity-based canoinicalization":
d4a4004c0f9d3070

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

26

For each positive condition in the match statement(s), create a test that does not satisfy the requirement.

So for example, we're looking for a negate (sub) of a specific operand in the 'or', then create a test with a negate of a different value:

%sub = sub i8 0, %y  <-- mismatch, so this should not transform
%or = or i8 %sub, %x
%add = add i8 %or, %x

Or maybe the 'sub' isn't a negate; it might be: (1 - x). Change the 'or' to an 'xor', etc.

[marcauberer]

Test all combinations and add negative tests

[marcauberer]

@spatel @RKSimon I now added some more extensive tests, which should cover all relevant cases.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1399–1402

As a matter of fact, it seems like the match is covering all four cases. The first four test cases in the test ref file should cover those. I didn't even need the "thwart complexity based canonicalization instructions"

llvm/test/Transforms/InstCombine/add_or_sub.ll

26

Thanks for the explanation! I've added a few negative tests. Please let me know if something is missing.

[marcauberer]

Rebase

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1399–1402

The patch doesn't transform this example:

define i32 @add_or_sub_comb_i32_variant1(i32 %p) {
  %x = mul i32 %p, %p ; thwart complexity-based canonicalization
  %sub = sub i32 0, %x
  %or = or i32 %x, %sub
  %add = add i32 %or, %x
  ret i32 %add
}

It will be easier to see what's happening if we commit the baseline tests first (and we'll do that anyway), but you should probably create the expected tests for commuted patterns first.

[marcauberer]

Fix bug and fine-tune tests

[marcauberer]

Re-format

[marcauberer]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1399–1402

I think I got now what you mean. I added the "thwart complexity-based canonicalization" to every positive test and fixed the bug in the code. Could you take another look?

The baseline tests are now live here: https://reviews.llvm.org/D133449

[marcauberer]

Rebase and update test file

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

80

Oops - I missed this detail in the pre-commit. Shouldn't the vector constant have zeros rather than -1 to exercise this patch?

102–103

We need to bail out on this pattern, so we don't have extra instructions (ie, this will be a negative test). See matcher for "m_OneUse()".

102–103

We need to bail out on this pattern, so we don't have extra instructions (ie, this will be a negative test). See matcher for "m_OneUse()".

102–103

Can we propagate the no-wrap flags to the new add (ie, is it correct based on Alive2 proofs)?

[marcauberer]

llvm/test/Transforms/InstCombine/add_or_sub.ll

80

Oh yes, you are right! Is a separate change required for this?

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

80

No - it's minor and obvious in hindsight. Just fix it up in this patch.

[marcauberer]

Add oneUse to or inst and fix test mistake

[marcauberer]

llvm/test/Transforms/InstCombine/add_or_sub.ll

102–103

Do we need to propagate the no-wrap flags?

Without propagating the flags: https://alive2.llvm.org/ce/z/3rM4KF
With propagating the flags: https://alive2.llvm.org/ce/z/tWyFm7

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

102–103

If we can propagate/generate flags during the transform, that is best. It saves some potentially expensive (in compile-time) analysis that tries to regenerate the flags or prevents losing information completely.

Note that "nuw" on these patterns is a special-case:
https://alive2.llvm.org/ce/z/h1763a

I have no idea if that pattern occurs in the real world, but we don't seem to get the optimal result with or without this patch.

It's a small change to the Builder.CreateAdd() call to propagate flags from "I", so we should do that. Please add tests with "nsw" alone and "nuw" alone to verify that we do the right thing in all cases.

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

102–103

On 2nd thought, just add no-wrap flags to some of the adds in the existing tests, and that will more efficiently verify that we are behaving correctly. We don't really need explicit tests just to show flag propagation. You can add a code comment above the test or modify the test function name to explain the intent.

[marcauberer]

Better handling for nuw and nsw flags in tests

[marcauberer]

Code cleanup

[marcauberer]

llvm/test/Transforms/InstCombine/add_or_sub.ll

102–103

Done, but the positive tests including nuw behave differently, like you mentioned. Do we leave it like this?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1406

Nit: use CamelCase for variable names, so HasNuw or HasNUW (similar for the others)...or just roll those values anonymously into the CreateAdd() line and let clang-format wrap the long line as it likes.

llvm/test/Transforms/InstCombine/add_or_sub.ll

102–103

I think it's ok since we have plenty of tests covering all of the code paths. The tests with 'nuw' demonstrate that we can chain together 2 or more transforms. If we ever implement the ideal nuw-specific transform after this patch, those tests can confirm if the folds are in the right order to get the best result.

[marcauberer]

Code cleanup

[marcauberer]

llvm/test/Transforms/InstCombine/add_or_sub.ll

102–103

Okay, perfect.

[spatel]

Thanks for iterating on this! LGTM

[marcauberer]

Update test ref

[marcauberer]

@spatel sorry, forgot to refresh the test ref. Now the change is ready for the final review ...

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
                           m_c_And(m_Deferred(A), m_Deferred(B))))) {
     // Replacing operands in-place to preserve nuw/nsw flags.
     replaceOperand(I, 0, A);
     replaceOperand(I, 1, B);
     return &I;
   }
 
+  // (add A (or A, -A)) --> (and (add A, -1) A)
+  // (add A (or -A, A)) --> (and (add A, -1) A)
+  // (add (or A, -A) A) --> (and (add A, -1) A)
+  // (add (or -A, A) A) --> (and (add A, -1) A)
+  if (match(&I, m_c_BinOp(m_Value(A), m_OneUse(m_c_Or(m_Neg(m_Deferred(A)),
+                                                      m_Deferred(A)))))) {
+    Value *Add =
+        Builder.CreateAdd(A, Constant::getAllOnesValue(A->getType()), "",
+                          I.hasNoSignedWrap(), I.hasNoSignedWrap());
+    return BinaryOperator::CreateAnd(Add, A);
+  }
+
   // Canonicalize ((A & -A) - 1) --> ((A - 1) & ~A)
   // Forms all commutable operations, and simplifies ctpop -> cttz folds.
   if (match(&I,
             m_Add(m_OneUse(m_c_And(m_Value(A), m_OneUse(m_Neg(m_Deferred(A))))),
                   m_AllOnes()))) {
     Constant *AllOnes = ConstantInt::getAllOnesValue(RHS->getType());
     Value *Dec = Builder.CreateAdd(A, AllOnes);
     Value *Not = Builder.CreateXor(A, AllOnes);

llvm/test/Transforms/InstCombine/add_or_sub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use19(i19)
 declare void @use12(i12)
 declare void @use2(i2)
 
-define i32 @add_or_sub_comb_i32_commuted1(i32 %x) {
-; CHECK-LABEL: @add_or_sub_comb_i32_commuted1(
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SUB]], [[X]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[OR]], [[X]]
+define i32 @add_or_sub_comb_i32_commuted1_nuw(i32 %x) {
+; CHECK-LABEL: @add_or_sub_comb_i32_commuted1_nuw(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = and i32 [[TMP1]], [[X]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %sub = sub i32 0, %x
   %or = or i32 %sub, %x
-  %add = add i32 %or, %x
+  %add = add nuw i32 %or, %x
   ret i32 %add
 }
 
-define i8 @add_or_sub_comb_i8_commuted2(i8 %p) {
-; CHECK-LABEL: @add_or_sub_comb_i8_commuted2(
+define i8 @add_or_sub_comb_i8_commuted2_nsw(i8 %p) {
+; CHECK-LABEL: @add_or_sub_comb_i8_commuted2_nsw(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i8 0, [[X]]
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[X]], [[SUB]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[X]], [[OR]]
-; CHECK-NEXT:    ret i8 [[ADD]]
+; CHECK-NEXT:    ret i8 [[X]]
 ;
   %x = mul i8 %p, %p ; thwart complexity-based canonicalization
   %sub = sub i8 0, %x
   %or = or i8 %sub, %x
-  %add = add i8 %x, %or
+  %add = add nsw i8 %x, %or
   ret i8 %add
 }
 
-define i128 @add_or_sub_comb_i128_commuted3(i128 %p) {
-; CHECK-LABEL: @add_or_sub_comb_i128_commuted3(
+define i128 @add_or_sub_comb_i128_commuted3_nuw_nsw(i128 %p) {
+; CHECK-LABEL: @add_or_sub_comb_i128_commuted3_nuw_nsw(
 ; CHECK-NEXT:    [[X:%.*]] = mul i128 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i128 0, [[X]]
-; CHECK-NEXT:    [[OR:%.*]] = or i128 [[X]], [[SUB]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i128 [[OR]], [[X]]
-; CHECK-NEXT:    ret i128 [[ADD]]
+; CHECK-NEXT:    ret i128 [[X]]
 ;
   %x = mul i128 %p, %p ; thwart complexity-based canonicalization
   %sub = sub i128 0, %x
   %or = or i128 %x, %sub
-  %add = add i128 %or, %x
+  %add = add nuw nsw i128 %or, %x
   ret i128 %add
 }
 
 define i64 @add_or_sub_comb_i64_commuted4(i64 %p) {
 ; CHECK-LABEL: @add_or_sub_comb_i64_commuted4(
 ; CHECK-NEXT:    [[X:%.*]] = mul i64 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 0, [[X]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[X]], [[SUB]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[X]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[X]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = and i64 [[TMP1]], [[X]]
 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
   %x = mul i64 %p, %p ; thwart complexity-based canonicalization
   %sub = sub i64 0, %x
   %or = or i64 %x, %sub
   %add = add i64 %x, %or
   ret i64 %add
 }
 
 define <3 x i32> @add_or_sub_comb_i32vec(<3 x i32> %p) {
 ; CHECK-LABEL: @add_or_sub_comb_i32vec(
 ; CHECK-NEXT:    [[X:%.*]] = mul <3 x i32> [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub <3 x i32> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[OR:%.*]] = or <3 x i32> [[X]], [[SUB]]
-; CHECK-NEXT:    [[ADD:%.*]] = add <3 x i32> [[OR]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add <3 x i32> [[X]], <i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[ADD:%.*]] = and <3 x i32> [[TMP1]], [[X]]
 ; CHECK-NEXT:    ret <3 x i32> [[ADD]]
 ;
   %x = mul <3 x i32> %p, %p ; thwart complexity-based canonicalization
   %sub = sub <3 x i32> <i32 0, i32 0, i32 0>, %x
   %or = or <3 x i32> %sub, %x
   %add = add <3 x i32> %or, %x
   ret <3 x i32> %add
 }
 
 define <4 x i16> @add_or_sub_comb_i32vec_poison(<4 x i16> %p) {
 ; CHECK-LABEL: @add_or_sub_comb_i32vec_poison(
 ; CHECK-NEXT:    [[X:%.*]] = mul <4 x i16> [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[ADD:%.*]] = add <4 x i16> [[X]], <i16 -1, i16 -1, i16 -1, i16 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = add <4 x i16> [[X]], <i16 -1, i16 -1, i16 -1, i16 -1>
+; CHECK-NEXT:    [[ADD:%.*]] = and <4 x i16> [[TMP1]], [[X]]
 ; CHECK-NEXT:    ret <4 x i16> [[ADD]]
 ;
   %x = mul <4 x i16> %p, %p ; thwart complexity-based canonicalization
-  %sub = sub <4 x i16> <i16 -1, i16 poison, i16 poison, i16 -1>, %x
+  %sub = sub <4 x i16> <i16 0, i16 poison, i16 poison, i16 0>, %x
   %or = or <4 x i16> %sub, %x
   %add = add <4 x i16> %or, %x
   ret <4 x i16> %add
 }
 
 define i12 @add_or_sub_comb_i12_multiuse_only_sub(i12 %p) {
 ; CHECK-LABEL: @add_or_sub_comb_i12_multiuse_only_sub(
 ; CHECK-NEXT:    [[X:%.*]] = mul i12 [[P:%.*]], [[P]]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i12 0, [[X]]
 ; CHECK-NEXT:    call void @use12(i12 [[SUB]])
-; CHECK-NEXT:    [[OR:%.*]] = or i12 [[X]], [[SUB]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i12 [[OR]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i12 [[X]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = and i12 [[TMP1]], [[X]]
 ; CHECK-NEXT:    ret i12 [[ADD]]
 ;
   %x = mul i12 %p, %p ; thwart complexity-based canonicalization
   %sub = sub i12 0, %x
   call void @use12(i12 %sub) ; extra use of sub
   %or = or i12 %sub, %x
   %add = add i12 %or, %x
   ret i12 %add
 }
 
-define i2 @add_or_sub_comb_i2_multiuse_only_or(i2 %p) {
-; CHECK-LABEL: @add_or_sub_comb_i2_multiuse_only_or(
-; CHECK-NEXT:    [[X:%.*]] = mul i2 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i2 0, [[X]]
-; CHECK-NEXT:    [[OR:%.*]] = or i2 [[X]], [[SUB]]
-; CHECK-NEXT:    call void @use2(i2 [[OR]])
-; CHECK-NEXT:    [[ADD:%.*]] = add i2 [[OR]], [[X]]
-; CHECK-NEXT:    ret i2 [[ADD]]
-;
-  %x = mul i2 %p, %p ; thwart complexity-based canonicalization
-  %sub = sub i2 0, %x
-  %or = or i2 %sub, %x
-  call void @use2(i2 %or) ; extra use of or
-  %add = add i2 %or, %x
-  ret i2 %add
-}
-
-define i19 @add_or_sub_comb_i19_multiuse_both(i19 %p) {
-; CHECK-LABEL: @add_or_sub_comb_i19_multiuse_both(
-; CHECK-NEXT:    [[X:%.*]] = mul i19 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i19 0, [[X]]
-; CHECK-NEXT:    call void @use19(i19 [[SUB]])
-; CHECK-NEXT:    [[OR:%.*]] = or i19 [[X]], [[SUB]]
-; CHECK-NEXT:    call void @use19(i19 [[OR]])
-; CHECK-NEXT:    [[ADD:%.*]] = add i19 [[OR]], [[X]]
-; CHECK-NEXT:    ret i19 [[ADD]]
-;
-  %x = mul i19 %p, %p ; thwart complexity-based canonicalization
-  %sub = sub i19 0, %x
-  call void @use19(i19 %sub) ; extra use of sub
-  %or = or i19 %sub, %x
-  call void @use19(i19 %or) ; extra use of or
-  %add = add i19 %or, %x
-  ret i19 %add
-}
-
-define i10 @add_or_sub_comb_i10_nsw_nuw(i10 %p) {
-; CHECK-LABEL: @add_or_sub_comb_i10_nsw_nuw(
-; CHECK-NEXT:    [[X:%.*]] = mul i10 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i10 0, [[X]]
-; CHECK-NEXT:    [[OR:%.*]] = or i10 [[X]], [[SUB]]
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i10 [[OR]], [[X]]
-; CHECK-NEXT:    ret i10 [[ADD]]
-;
-  %x = mul i10 %p, %p ; thwart complexity-based canonicalization
-  %sub = sub i10 0, %x
-  %or = or i10 %sub, %x
-  %add = add nsw nuw i10 %or, %x
-  ret i10 %add
-}
-
-define i8 @add_or_sub_comb_i8_negative1(i8 %x, i8 %y) {
-; CHECK-LABEL: @add_or_sub_comb_i8_negative1(
+define i8 @add_or_sub_comb_i8_negative_y_sub(i8 %x, i8 %y) {
+; CHECK-LABEL: @add_or_sub_comb_i8_negative_y_sub(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 0, [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = or i8 [[SUB]], [[X:%.*]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[OR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %sub = sub i8 0, %y ; mismatch: y instead of x
   %or = or i8 %sub, %x
   %add = add i8 %or, %x
   ret i8 %add
 }
 
-define i8 @add_or_sub_comb_i8_negative2(i8 %x, i8 %y) {
-; CHECK-LABEL: @add_or_sub_comb_i8_negative2(
+define i8 @add_or_sub_comb_i8_negative_y_or(i8 %x, i8 %y) {
+; CHECK-LABEL: @add_or_sub_comb_i8_negative_y_or(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 0, [[X:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = or i8 [[SUB]], [[Y:%.*]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[OR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %sub = sub i8 0, %x
   %or = or i8 %sub, %y ; mismatch: y instead of x
   %add = add i8 %or, %x
   ret i8 %add
 }
 
-define i8 @add_or_sub_comb_i8_negative3(i8 %x, i8 %y) {
-; CHECK-LABEL: @add_or_sub_comb_i8_negative3(
+define i8 @add_or_sub_comb_i8_negative_y_add(i8 %x, i8 %y) {
+; CHECK-LABEL: @add_or_sub_comb_i8_negative_y_add(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 0, [[X:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = or i8 [[SUB]], [[X]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[OR]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %sub = sub i8 0, %x
   %or = or i8 %sub, %x
   %add = add i8 %or, %y ; mismatch: y instead of x
   ret i8 %add
 }
 
-define i8 @add_or_sub_comb_i8_negative4(i8 %x) {
-; CHECK-LABEL: @add_or_sub_comb_i8_negative4(
+define i8 @add_or_sub_comb_i8_negative_xor_instead_or(i8 %x) {
+; CHECK-LABEL: @add_or_sub_comb_i8_negative_xor_instead_or(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 0, [[X:%.*]]
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[SUB]], [[X]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[XOR]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %sub = sub i8 0, %x
   %xor = xor i8 %sub, %x ; mismatch: xor instead of or
   %add = add i8 %xor, %x
   ret i8 %add
 }
 
 
-define i16 @add_or_sub_comb_i16_negative5(i16 %x) {
-; CHECK-LABEL: @add_or_sub_comb_i16_negative5(
+define i16 @add_or_sub_comb_i16_negative_sub_no_negate(i16 %x) {
+; CHECK-LABEL: @add_or_sub_comb_i16_negative_sub_no_negate(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i16 1, [[X:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = or i16 [[SUB]], [[X]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add i16 [[OR]], [[X]]
 ; CHECK-NEXT:    ret i16 [[ADD]]
 ;
   %sub = sub i16 1, %x ; mismatch: sub isn't a negate
   %or = or i16 %sub, %x
   %add = add i16 %or, %x
   ret i16 %add
 }
+
+define i2 @add_or_sub_comb_i2_negative_multiuse_only_or(i2 %p) {
+; CHECK-LABEL: @add_or_sub_comb_i2_negative_multiuse_only_or(
+; CHECK-NEXT:    [[X:%.*]] = mul i2 [[P:%.*]], [[P]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i2 0, [[X]]
+; CHECK-NEXT:    [[OR:%.*]] = or i2 [[X]], [[SUB]]
+; CHECK-NEXT:    call void @use2(i2 [[OR]])
+; CHECK-NEXT:    [[ADD:%.*]] = add i2 [[OR]], [[X]]
+; CHECK-NEXT:    ret i2 [[ADD]]
+;
+  %x = mul i2 %p, %p ; thwart complexity-based canonicalization
+  %sub = sub i2 0, %x
+  %or = or i2 %sub, %x
+  call void @use2(i2 %or) ; extra use of or
+  %add = add i2 %or, %x
+  ret i2 %add
+}
+
+define i19 @add_or_sub_comb_i19_negative_multiuse_both(i19 %p) {
+; CHECK-LABEL: @add_or_sub_comb_i19_negative_multiuse_both(
+; CHECK-NEXT:    [[X:%.*]] = mul i19 [[P:%.*]], [[P]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i19 0, [[X]]
+; CHECK-NEXT:    call void @use19(i19 [[SUB]])
+; CHECK-NEXT:    [[OR:%.*]] = or i19 [[X]], [[SUB]]
+; CHECK-NEXT:    call void @use19(i19 [[OR]])
+; CHECK-NEXT:    [[ADD:%.*]] = add i19 [[OR]], [[X]]
+; CHECK-NEXT:    ret i19 [[ADD]]
+;
+  %x = mul i19 %p, %p ; thwart complexity-based canonicalization
+  %sub = sub i19 0, %x
+  call void @use19(i19 %sub) ; extra use of sub
+  %or = or i19 %sub, %x
+  call void @use19(i19 %or) ; extra use of or
+  %add = add i19 %or, %x
+  ret i19 %add
+}