Page MenuHomePhabricator

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

Authored by rampitec on Nov 4 2021, 2:48 PM.

Details

Reviewers
spatel
Summary

This handles expressions:

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

and swapped case:

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

The expression (~(a | b) & c) | ~((a | b) | c) is just an
(~x & c) | ~(x | c) and will be simplified without this
patch but two cases above need reassociation.

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

Diff Detail

Event Timeline

rampitec created this revision.Nov 4 2021, 2:48 PM
rampitec requested review of this revision.Nov 4 2021, 2:48 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 4 2021, 2:48 PM
rampitec planned changes to this revision.Nov 10 2021, 12:42 PM

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

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

Added swapped case

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

As discussed in D114462, I noticed a pair of missing 'xor' simplifications based on these patterns, so I added those with:
892648b18a8c
b326c058146f

So we probably want to add some or all of these tests under "test/Transforms/PhaseOrdering" to see if these are reduced with the default -O2/-O3 pipelines or some combination of specific passes (-reassociate, -gvn, -instcombine).

This patch could also be moved to -instsimplify if it is still needed. But I think that would really be covering up a shortcoming of -reassociate. That pass should find the common 'or' or 'and' value in these patterns?

rampitec abandoned this revision.Nov 24 2021, 1:05 PM

As discussed in D114462, I noticed a pair of missing 'xor' simplifications based on these patterns, so I added those with:
892648b18a8c
b326c058146f

So we probably want to add some or all of these tests under "test/Transforms/PhaseOrdering" to see if these are reduced with the default -O2/-O3 pipelines or some combination of specific passes (-reassociate, -gvn, -instcombine).

I have moved these tests into new Transforms/PhaseOrdering/reassociate-gvn-bdce.ll. That is a combination of -reassociate -gvn -bdce which now handles it.

This patch could also be moved to -instsimplify if it is still needed. But I think that would really be covering up a shortcoming of -reassociate. That pass should find the common 'or' or 'and' value in these patterns?

I am dropping it, these cases are already handled by your D114462. The case (~A & ~B & C) | ~(A | B | C) --> ~(A | B) is not, but just reassociation will not help, it needs to be combined with demorganing and use analysis. It will need a separate patch, however.