# [InstCombine] (~a & b & c) | ~(a | b | c) -> ~(a | (b ^ c))ClosedPublicActions

Authored by rampitec on Nov 1 2021, 3:27 PM.

# Details

Summary

Transform

`(~a & b & c) | ~(a | b | c) -> ~(a | (b ^ c))`

And swapped case:

`(~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)`
```----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
%or1 = or i4 %b, %a
%or2 = or i4 %or1, %c
%not1 = xor i4 %or2, 15
%not2 = xor i4 %a, 15
%and1 = and i4 %b, %not2
%and2 = and i4 %and1, %c
%or3 = or i4 %and2, %not1
ret i4 %or3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
%1 = xor i4 %c, %b
%2 = or i4 %1, %a
%or3 = xor i4 %2, 15
ret i4 %or3
}
Transformation seems to be correct!```
```----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
%and1 = and i4 %b, %a
%and2 = and i4 %and1, %c
%not1 = xor i4 %and2, 15
%not2 = xor i4 %a, 15
%or1 = or i4 %not2, %b
%or2 = or i4 %or1, %c
%and3 = and i4 %or2, %not1
ret i4 %and3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
%xor = xor i4 %b, %c
%not = xor i4 %a, 15
%or = or i4 %xor, %not
ret i4 %or
}
Transformation seems to be correct!```

# Unit TestsFailedView All

TimeTest
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -shared-libasan -g -Wno-deprecated-declarations /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/exitcode.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxDynamicConfig/TestCases/Output/exitcode.cpp.tmp
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -g -Wno-deprecated-declarations /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/exitcode.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxConfig/TestCases/Output/exitcode.cpp.tmp

### Event Timeline

rampitec created this revision.Nov 1 2021, 3:27 PM
rampitec requested review of this revision.Nov 1 2021, 3:27 PM
Herald added a project: Restricted Project. Nov 1 2021, 3:27 PM
rampitec planned changes to this revision.Nov 10 2021, 12:48 PM

In the light of D113526 this needs to be rebased and handle inverted pattern:

`(~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)`
```----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
%and1 = and i4 %b, %a
%and2 = and i4 %and1, %c
%not1 = xor i4 %and2, 15
%not2 = xor i4 %a, 15
%or1 = or i4 %not2, %b
%or2 = or i4 %or1, %c
%and3 = and i4 %or2, %not1
ret i4 %and3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
%xor = xor i4 %b, %c
%not = xor i4 %a, 15
%or = or i4 %xor, %not
ret i4 %or
}
Transformation seems to be correct!```
rampitec updated this revision to Diff 386901.Nov 12 2021, 11:39 AM
rampitec edited the summary of this revision. (Show Details)

`(~a | b | c) & ~(a & b & c) -> ~a | (b ^ c)`
rampitec updated this revision to Diff 386924.Nov 12 2021, 12:35 PM

Capture ~A from the original expression to reuse.

spatel accepted this revision.Dec 9 2021, 5:30 AM

LGTM - admittedly, I didn't try to line up all of the possible patterns with the tests because there are so many combinations.
So this is at the limit of what we can do in instcombine pattern-matching, but I don't see any way to reduce the complexity.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1798–1799

Comment seems truncated from the similar code comment above here.

This revision is now accepted and ready to land.Dec 9 2021, 5:30 AM
rampitec updated this revision to Diff 393201.Dec 9 2021, 9:23 AM
rampitec marked an inline comment as done.

Updated comment.

This revision was landed with ongoing or failed builds.Dec 9 2021, 9:51 AM
This revision was automatically updated to reflect the committed changes.