Page MenuHomePhabricator

[InstCombine] Y - ~X --> X + Y + 1 fold (PR42457)
ClosedPublic

Authored by lebedev.ri on Jul 1 2019, 5:40 AM.

Details

Summary

I *think* we'd want this new variant, because we obviously
have better handling for add as compared to sub/not.

https://rise4fun.com/Alive/WMn

Fixes PR42457

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.Jul 1 2019, 5:40 AM
lebedev.ri edited the summary of this revision. (Show Details)
lebedev.ri retitled this revision from [InstCombine] Y - ~X == X + Y + 1 fold (PR42457) to [InstCombine] Y - ~X --> X + Y + 1 fold (PR42457).
lebedev.ri updated this revision to Diff 207291.Jul 1 2019, 6:52 AM

NFC, fixup comment.

lebedev.ri updated this revision to Diff 207338.Jul 1 2019, 9:01 AM
lebedev.ri edited the summary of this revision. (Show Details)

Rebased over committed regression fix, NFC.

Not sure which way to go here - a 'not' is considered a less complex op than arbitrary xor/add, and 'not' might be better for value tracking and subsequent instcombines. But the adds are reassociable/commutable.

This might warrant a DAGCombiner patch to avoid regressions before we make the IR decision.

x86 scalar looks better with add+inc:

movl	%edi, %eax
notl	%esi
subl	%esi, %eax

vs.

leal	1(%rsi,%rdi), %eax

But AArch64 and PowerPC64LE appear to benefit from the 'not' with vector code:

mvn	v1.16b, v1.16b
sub	v0.4s, v0.4s, v1.4s

vs.

add	v0.4s, v1.4s, v0.4s
movi	v1.4s, #1
add	v0.4s, v0.4s, v1.4s

And PPC:

xxlnor 35, 35, 35
vsubuwm 2, 2, 3

vs.

vspltisw 4, 1
vadduwm 2, 3, 2
vadduwm 2, 2, 4

If we do go in this direction, do we want to increment 1st to reduce the burden on -reassociation? Assuming it will do:
(x + y) + 1 --> (x + 1) + y
...we might as well produce that directly?

cc'ing Eli in case he sees any other motivations to consider.

Yes, we should probably teach DAGCombine to choose the right form for each target/type.

It seems reasonable to prefer x+(y+1) over x-(-1-y), for reassociation etc. It's possible there could be some bad interaction at the interface between logical and arithmetic operations, which makes us miss some important optimization, but that doesn't seem likely to me.

Yes, we should probably teach DAGCombine to choose the right form for each target/type.

It seems reasonable to prefer x+(y+1) over x-(-1-y), for reassociation etc. It's possible there could be some bad interaction at the interface between logical and arithmetic operations, which makes us miss some important optimization, but that doesn't seem likely to me.

Great, thank you for the feedback!
I will look into backend stuff; if there are no other concerns here please feel free to accept,
i'm not going to land until after the backend stuff is done.

Yes, we should probably teach DAGCombine to choose the right form for each target/type.

It seems reasonable to prefer x+(y+1) over x-(-1-y), for reassociation etc. It's possible there could be some bad interaction at the interface between logical and arithmetic operations, which makes us miss some important optimization, but that doesn't seem likely to me.

Great, thank you for the feedback!
I will look into backend stuff; if there are no other concerns here please feel free to accept,
i'm not going to land until after the backend stuff is done.

Produce this:

(x + 1) + y

rather than:

(x + y) + 1

?

Mimic what -reassociate would produce.

spatel accepted this revision.Jul 1 2019, 1:37 PM

LGTM

This revision is now accepted and ready to land.Jul 1 2019, 1:37 PM
lebedev.ri planned changes to this revision.Jul 1 2019, 1:37 PM

Thank you for the review.

@RKSimon encountered https://bugs.llvm.org/show_bug.cgi?id=42486 while trying to write tests, PTAL.

This revision was not accepted when it landed; it landed in state Changes Planned.Jul 3 2019, 2:43 AM
Closed by commit rL365011: [InstCombine] Y - ~X --> X + Y + 1 fold (PR42457) (authored by lebedevri, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.