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

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

Repository
rL LLVM
Build Status
 Buildable 17849 Build 17849: arc lint + arc unit

### 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
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.