[InstCombine] Baseline tests for folding x + (x | -x) to x & (x - 1)

[marcauberer]

Summary

Baseline tests for https://reviews.llvm.org/D133362

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

11

This isn't the pattern you intended - notice the 'or' operands were commuted. For this test only, we don't want any extra 'thwart' instruction.

32–33

This is a fun example. In order, for x to be op0 of the 'add', it must be a binop or other instruction with high complexity. But for x to be op1 of the 'or', it must be equal or lower complexity than a negate - which is treated as a special-case (lower complexity than a binop).

Therefore, the intended pattern is impossible given the current weights. Let's just leave this test as-is in case the weightings ever change.

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

89

Replace undef with poison. We're moving away from undef as a value in IR, so we don't want to add new tests with undef.

[marcauberer]

Remove extra 'thwart' instruction for the first test

[marcauberer]

Replace undef with poison in tests

[spatel]

llvm/test/Transforms/InstCombine/add_or_sub.ll

93

This looks good, but there should be 3 of these multi-use tests:

1. Extra use of the sub only.
2. Extra use of the or only.
3. Extra use of both sub and or (that's what we have currently).

The general rule for instcombine transforms is that we don't want to end up with more instructions than we started with, so it can get a bit tricky, but we'll sort that out in the code patch.

[marcauberer]

Add additional multiuse test cases

[marcauberer]

llvm/test/Transforms/InstCombine/add_or_sub.ll

93

Done 👍

[spatel]

LGTM - the tests are often harder to get right than the code. :)
If you don't have commit access, please post name+email to receive the proper author citation.

[marcauberer]

Thanks!

I do not have commit access, so here is my data:

Name: Marc Auberer
Username: marcauberer
Email: [e-mail]

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]]
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+  %sub = sub i32 0, %x
+  %or = or i32 %sub, %x
+  %add = add i32 %or, %x
+  ret i32 %add
+}
+
+define i8 @add_or_sub_comb_i8_commuted2(i8 %p) {
+; CHECK-LABEL: @add_or_sub_comb_i8_commuted2(
+; 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]]
+;
+  %x = mul i8 %p, %p ; thwart complexity-based canonicalization
+  %sub = sub i8 0, %x
+  %or = or i8 %sub, %x
+  %add = add i8 %x, %or
+  ret i8 %add
+}
+
+define i128 @add_or_sub_comb_i128_commuted3(i128 %p) {
+; CHECK-LABEL: @add_or_sub_comb_i128_commuted3(
+; 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]]
+;
+  %x = mul i128 %p, %p ; thwart complexity-based canonicalization
+  %sub = sub i128 0, %x
+  %or = or i128 %x, %sub
+  %add = add 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:    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:    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:    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
+  %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:    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(
+; 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(
+; 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(
+; 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(
+; 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(
+; 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
+}