Page MenuHomePhabricator

[InstCombine] Negator - sink sinkable negations
Needs ReviewPublic

Authored by lebedev.ri on Oct 3 2019, 10:27 AM.

Details

Summary

As we have discussed previously (e.g. in D63992 / D64090 / PR42457), sub instruction
can almost be considered non-canonical. While we do convert sub %x, C -> add %x, -C,
we sparsely do that for non-constants. But we should.

Here, i propose to interpret sub %x, %y as add (sub 0, %y), %x IFF the negation can be sinked into the %y
My main motivation here is the @t7, which is from PR42412 / PR42389.

We know that neg is free if:

Diff Detail

Event Timeline

lebedev.ri created this revision.Oct 3 2019, 10:27 AM
lebedev.ri edited the summary of this revision. (Show Details)Oct 3 2019, 10:28 AM
lebedev.ri edited the summary of this revision. (Show Details)Oct 3 2019, 10:33 AM
lebedev.ri updated this revision to Diff 223181.Oct 4 2019, 3:10 AM

Actually, sub can be freely negated.

This *is* unusual. Is this too ugly to live?

I'd prefer to actually transform the operation tree at the point we decide it's profitable, to make it clear we can't end up in an infinite loop or something like that. As it is, you're depending on some other transforms happening in a particular order, and it's not clear that will happen consistently. (Yes, it's a little more code, but I think that's okay.)

This *is* unusual. Is this too ugly to live?

I'd prefer to actually transform the operation tree at the point we decide it's profitable, to make it clear we can't end up in an infinite loop or something like that. As it is, you're depending on some other transforms happening in a particular order, and it's not clear that will happen consistently. (Yes, it's a little more code, but I think that's okay.)

Actually, that's presicely why i believed this may be the best approach - we both avoid lot's of code duplication,
and if there are missing folds this *will* shake them loose - if they don't happen it'll "be caught" as a deadlock.

I'm not really sure how more direct approach would look..

lebedev.ri updated this revision to Diff 223385.Oct 5 2019, 3:02 PM
lebedev.ri retitled this revision from [InstCombine] Unfold `sub %x, %y` -> `add (sub 0, %y), %x` IFF `%y` can be freely negated to [InstCombine] Negator - sink sinkable negations.
lebedev.ri edited the summary of this revision. (Show Details)

This *is* unusual. Is this too ugly to live?

I'd prefer to actually transform the operation tree at the point we decide it's profitable, to make it clear we can't end up in an infinite loop or something like that. As it is, you're depending on some other transforms happening in a particular order, and it's not clear that will happen consistently. (Yes, it's a little more code, but I think that's okay.)

I'm not really sure how more direct approach would look..

Okay so this is nowhere near polished-enough, but how about this?

lebedev.ri updated this revision to Diff 223412.Oct 6 2019, 4:42 AM

Give more thought as to whether the new instructions should be inserted or not, and actually succeed in building test-suite.

@efriedma any high-level feedback on this?

Hmm, that's a bit more complicated than I hoped it would be... but I don't see any obvious way to simplify it.

It looks like this speculatively creates new instructions, then erases them on failure?

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp
1

InstCombineAddSub.cpp?

Hmm, that's a bit more complicated than I hoped it would be... but I don't see any obvious way to simplify it.

The one big missing thing is to use an actual worklist instead of recursion, but i'm not sure how to do that yet.

It looks like this speculatively creates new instructions, then erases them on failure?

Yes. More specifically, while speculatively creating them, it inserts them internal worklist
and in their proper places in basic blocks. If we succeed to negate the entire tree,
that worklist is then propagated to instcombine itself.
If that doesn't happen, then they are 'trivially' dead and deleted.

lebedev.ri marked an inline comment as done.
lebedev.ri edited the summary of this revision. (Show Details)

Thank you for taking a look!
Also handle trunc, fix comments.

If that doesn't happen, then they are 'trivially' dead and deleted.

Deleted where, exactly? If you're expecting the instcombine main loop to delete them, you'll force instcombine into an infinite loop, I think.

If that doesn't happen, then they are 'trivially' dead and deleted.

Deleted where, exactly? If you're expecting the instcombine main loop to delete them, you'll force instcombine into an infinite loop, I think.

Hmm, they are not added to the instcombine's worklist unless we succeed in negating
the entire tree, and this passes test-suite with no infinite looping.

You are saying that we should instead DCE instructions in *our* worklist if we fail, correct?

Erase newly-created/inserted instruction if negation failed.

@efriedma - do you want to continue reviewing?

I've just pointed out a few nits for now.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h
959

typo: attempt

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp
169

it's -> its

183

it's -> its

193

negatible one -> negatible if one

193

it's -> its

244

typo: temporarily

llvm/test/Transforms/InstCombine/sub-of-negatible.ll
159–160

I didn't follow the diffs here - was one of these tests redundant? The code comment didn't match before, but it still doesn't?

271–272

Add these tests with baseline results as pre-commit?

351

it's -> its

lebedev.ri updated this revision to Diff 232090.Dec 4 2019, 5:00 AM
lebedev.ri marked 10 inline comments as done.

@efriedma - do you want to continue reviewing?

I've just pointed out a few nits for now.

Nits addressed.

There are some more patterns that aren't handled here.
The idea is to ideally move them all here.

llvm/test/Transforms/InstCombine/sub-of-negatible.ll
159–160

The test was too complicated, was checking more than the minimal pattern - subtraction can be freely negated by swapping its operands.

spatel added a comment.Dec 4 2019, 9:11 AM

Do you have stats on how often this fires? Impact on compile-time?

Remove more specific pattern-matching from InstCombiner::visitSub() simultaneously with adding this more general functionality, so we don't have redundancy (and limit compile-time impact)?

lebedev.ri updated this revision to Diff 232222.Dec 4 2019, 3:09 PM

NOT READY FOR REVIEW

Remove more specific pattern-matching from InstCombiner::visitSub() simultaneously with adding this more general functionality, so we don't have redundancy (and limit compile-time impact)?

I was hoping to do that in steps, but i guess that's one way to boost those stats :))
I think i have moved everything relevant from InstCombiner::visitSub() now.
Observations:

  • There's an artificial one-use restriction that needs to go away (when Depth=0 and we are looking at sub 0, %x)
  • We loose/do not propagate no wrap flags
  • InstCombiner::visitAdd() change is needed because of how good we are get at sinking negations - else there are two opposite folds. It should be done beforehand, separately.
  • Same with InstCombiner::foldAddWithConstant() change, not entirely related to the diff.
  • There are some other regressions.

Rebased, slightly better, but not there yet still.

lebedev.ri updated this revision to Diff 232532.Dec 6 2019, 4:25 AM

Still not for review

Some more unreachable code removed from InstCombiner::visitSub()

Maybe you can change title to [WIP] or [NOT READY FOR REVIEW] ?

xbolva00 added inline comments.Dec 6 2019, 4:41 AM
llvm/test/Transforms/InstCombine/sub.ll
1183 ↗(On Diff #232532)

Remove FIXME?