Page MenuHomePhabricator

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

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!

Diff Detail

Unit TestsFailed

TimeTest
680 msx64 debian > AddressSanitizer-x86_64-linux.TestCases::strcmp.c
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/strcmp.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxConfig/TestCases/Output/strcmp.c.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. · View Herald TranscriptNov 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)

Rebased and added swapped case:

(~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
1807–1808

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.