This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] fold xor logic of 2 variables
ClosedPublic

Authored by spatel on Nov 23 2021, 11:03 AM.

Details

Summary

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

I was looking for a shortcut to reduce some of the complex logic folds that are currently up for review (D113216 and others in that stack), and I found this missing from instcombine/instsimplify.

There is a trade-off in putting it into instsimplify: because we can't create new values here, we need a strict 'not' op (no undef elements). Otherwise, the fold is not valid:
https://alive2.llvm.org/ce/z/k_AGGj

If this was in instcombine instead, we could create the proper 'not'. But having the fold here benefits other passes like GVN that use instsimplify as an analysis. If I'm seeing it correctly, this is enough to catch the cases in D113216 at -O2 without needing to add more pattern matching to instcombine.

Diff Detail

Event Timeline

spatel created this revision.Nov 23 2021, 11:03 AM
spatel requested review of this revision.Nov 23 2021, 11:03 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 23 2021, 11:03 AM

Note: we miss the sibling with swapped and/or too, and it doesn't need a 'not' op, so it would clearly be best placed in instsimplify:
https://alive2.llvm.org/ce/z/7LbWeV

rampitec accepted this revision.Nov 23 2021, 11:31 AM

LGTM.

Thanks Sanjay! This really helps D113216 with -O3, but then not a more complex version of it which needs demorganing and reassociation:

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

define i32 @not_and_not_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @not_and_not_and_or_not_or_or(
; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
; CHECK-NEXT:    ret i32 [[NOT2]]
;
  %or1 = or i32 %b, %c
  %or2 = or i32 %or1, %a
  %not1 = xor i32 %or2, -1
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %and1 = and i32 %nota, %notb
  %and2 = and i32 %and1, %c
  %or4 = or i32 %and2, %not1
  call void @use(i32 %nota)
  call void @use(i32 %notb)
  ret i32 %or4
}

declare void @use(i32)

In this case reassociation is blocked by uses, so I was looking into extending LHS match in D113216 to catch (~a & ~b & c) in addition to (~(a | b) & c). I still need to look into that, but this is clearly LGTM.

This revision is now accepted and ready to land.Nov 23 2021, 11:31 AM

LGTM.

Thanks Sanjay! This really helps D113216 with -O3, but then not a more complex version of it which needs demorganing and reassociation:

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

define i32 @not_and_not_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @not_and_not_and_or_not_or_or(
; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
; CHECK-NEXT:    ret i32 [[NOT2]]
;
  %or1 = or i32 %b, %c
  %or2 = or i32 %or1, %a
  %not1 = xor i32 %or2, -1
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %and1 = and i32 %nota, %notb
  %and2 = and i32 %and1, %c
  %or4 = or i32 %and2, %not1
  call void @use(i32 %nota)
  call void @use(i32 %notb)
  ret i32 %or4
}

declare void @use(i32)

In this case reassociation is blocked by uses, so I was looking into extending LHS match in D113216 to catch (~a & ~b & c) in addition to (~(a | b) & c). I still need to look into that, but this is clearly LGTM.

Thanks!
Yes, I think we'll always be able to find cracks in the logic folds that allow some cases to get through.
If we can find a few more of these simplifications/combines though, I wonder if that will be enough to handle all of the patterns in the source example that you showed in D112276?

Thanks!
Yes, I think we'll always be able to find cracks in the logic folds that allow some cases to get through.
If we can find a few more of these simplifications/combines though, I wonder if that will be enough to handle all of the patterns in the source example that you showed in D112276?

I just have to say I have tried.
JBTW, cases pre-commited for D113216 probably need to move into pass pipeline after this.

This revision was landed with ongoing or failed builds.Nov 23 2021, 1:51 PM
This revision was automatically updated to reflect the committed changes.