Page MenuHomePhabricator

[InstCombine] Apply SimplifyUsingDistributiveLaws to associative/commutative cases.
Needs ReviewPublic

Authored by yamauchi on May 8 2018, 11:58 AM.

Details

Reviewers
davidxl
Summary

Apply SimplifyUsingDistributiveLaws to the associative/commutative cases. For
example, if we have "(A op B) op C", we try to transform it to "A op (B op C)"
and try to simplify the "(B op C)" part (even when "(B op C)" doesn't fold to a
constant).

A motivation example is a bit-check combining simplification like

((A & 1) == 0) && ((A & 2) == 0) && ((A & 4) == 0) &&
((B & 1) == 0) && ((B & 2) == 0) && ((B & 4) == 0)

-->

((A & 7) == 0) && ((B & 7) == 0)

which didn't fully happen previously.

Diff Detail

Event Timeline

yamauchi created this revision.May 8 2018, 11:58 AM

This is a simpler, but limited version of D46336. Note the test @bit-check-combine-256() doesn't get folded as simple as in D46336.

After -instcombine with D46336

define i1 @bit-check-combine-256(i32* %bits0, i32* %bits1, i32* %bits2, i32* %bits3, i32* %bits4, i32* %bits5, i32* %bits6, i32* %bits7) {
entry:
  %0 = load i32, i32* %bits0, align 4
  %1 = icmp eq i32 %0, -2145382392
  %2 = load i32, i32* %bits1, align 4
  %3 = load i32, i32* %bits2, align 4
  %4 = load i32, i32* %bits3, align 4
  %5 = or i32 %3, %4
  %6 = and i32 %5, 2147483647
  %7 = or i32 %2, %6
  %8 = or i32 %3, %4
  %9 = and i32 %8, -2147483648
  %10 = or i32 %9, %7
  %11 = load i32, i32* %bits4, align 4
  %12 = load i32, i32* %bits5, align 4
  %13 = or i32 %11, %12
  %14 = and i32 %13, 2147483647
  %15 = or i32 %10, %14
  %16 = or i32 %11, %12
  %17 = and i32 %16, -2147483648
  %18 = or i32 %17, %15
  %19 = load i32, i32* %bits6, align 4
  %20 = load i32, i32* %bits7, align 4
  %21 = or i32 %19, %20
  %22 = and i32 %21, 2147483647
  %23 = or i32 %18, %22
  %24 = or i32 %19, %20
  %25 = and i32 %24, -2147483648
  %26 = or i32 %25, %23
  %27 = icmp eq i32 %26, 0
  %28 = and i1 %27, %1
  ret i1 %28
}

After -instcombine -gvn -instcombine with D46336

define i1 @bit-check-combine-256(i32* %bits0, i32* %bits1, i32* %bits2, i32* %bits3, i32* %bits4, i32* %bits5, i32* %bits6, i32* %bits7) {
entry:
  %0 = load i32, i32* %bits0, align 4
  %1 = icmp eq i32 %0, -2145382392
  %2 = load i32, i32* %bits1, align 4
  %3 = load i32, i32* %bits2, align 4
  %4 = load i32, i32* %bits3, align 4
  %5 = or i32 %3, %4
  %6 = load i32, i32* %bits4, align 4
  %7 = load i32, i32* %bits5, align 4
  %8 = or i32 %6, %7
  %9 = or i32 %5, %8
  %10 = load i32, i32* %bits6, align 4
  %11 = load i32, i32* %bits7, align 4
  %12 = or i32 %10, %11
  %13 = or i32 %9, %12
  %14 = or i32 %2, %13
  %15 = icmp eq i32 %14, 0
  %16 = and i1 %15, %1
  ret i1 %16
}

After -instcombine (or -instcombine -gvn -instcombine) with this patch

define i1 @bit-check-combine-256(i32* %bits0, i32* %bits1, i32* %bits2, i32* %bits3, i32* %bits4, i32* %bits5, i32* %bits6, i32* %bits7) {
entry:
  %0 = load i32, i32* %bits0, align 4
  %1 = icmp eq i32 %0, -2145382392
  %2 = load i32, i32* %bits1, align 4
  %3 = load i32, i32* %bits2, align 4
  %4 = and i32 %3, 2147483647
  %5 = or i32 %2, %4
  %6 = icmp eq i32 %5, 0
  %7 = and i1 %6, %1
  %cmp.i3259 = icmp sgt i32 %3, -1
  %and3752918 = and i1 %7, %cmp.i3259
  %8 = load i32, i32* %bits3, align 4
  %9 = load i32, i32* %bits4, align 4
  %10 = and i32 %9, 2147483647
  %11 = or i32 %8, %10
  %12 = icmp eq i32 %11, 0
  %13 = and i1 %12, %and3752918
  %cmp.i3381 = icmp sgt i32 %9, -1
  %and6312982 = and i1 %13, %cmp.i3381
  %14 = load i32, i32* %bits5, align 4
  %15 = load i32, i32* %bits6, align 4
  %16 = and i32 %15, 2147483647
  %17 = or i32 %14, %16
  %18 = icmp eq i32 %17, 0
  %19 = and i1 %18, %and6312982
  %cmp.i3503 = icmp sgt i32 %15, -1
  %and8873046 = and i1 %19, %cmp.i3503
  %20 = load i32, i32* %bits7, align 4
  %21 = icmp eq i32 %20, 0
  %22 = and i1 %21, %and8873046
  ret i1 %22
}
spatel added a subscriber: spatel.May 9 2018, 6:21 AM
spatel added inline comments.May 9 2018, 7:41 AM
test/Transforms/InstCombine/bit-check-combine.ll
3

The general direction is still under discussion, but I want to point out some test changes that would make this easier to understand:

  1. Unless there's some exceptional circumstance, we shouldn't have regression tests for anything but instcombine here. If you want to check more than that, you might add something under tests/PhaseOrdering.
  1. I'm having a hard time seeing the motivating patterns for these tests. The 2nd and 3rd tests are already canonicalized by instcombine to the asserted forms shown in the CHECK lines? The 1st test gets reduced significantly. The 4th test should not require 8 params, loads, etc.
yamauchi added inline comments.May 9 2018, 10:49 AM
test/Transforms/InstCombine/bit-check-combine.ll
3

Acknowledged.

Yes, the second and third ones are fine, I put there to contrast. The 4th one is from real code, I'll try to see if I can reduce it further.