# [InstCombine] Generalize complex OR patterns to ANDClosedPublic

Authored by rampitec on Nov 9 2021, 4:00 PM.

# Details

Reviewers
 spatel lebedev.ri
Commits
rG6d3db2808826: [InstCombine] Generalize complex OR patterns to AND
Summary

For every pattern with only NOT, OR, and AND operations there is
always a symmetrical pattern with AND and OR swapped.

This adds 2 transformations:

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

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

# Diff Detail

### Event Timeline

rampitec created this revision.Nov 9 2021, 4:00 PM
Herald added a subscriber: hiraditya. Nov 9 2021, 4:00 PM
rampitec requested review of this revision.Nov 9 2021, 4:00 PM
Herald added a project: Restricted Project. Nov 9 2021, 4:00 PM

A gentle ping.

spatel accepted this revision.Nov 17 2021, 5:33 AM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1733

Typo: the left (first/inner) opcode should match the right (last/outer) opcode:
// (~(A & B) | C) & ... --> ...

This revision is now accepted and ready to land.Nov 17 2021, 5:33 AM
rampitec updated this revision to Diff 387980.Nov 17 2021, 10:28 AM
rampitec marked an inline comment as done.

Fixed comment typo.

This revision was landed with ongoing or failed builds.Nov 17 2021, 10:47 AM
This revision was automatically updated to reflect the committed changes.