[InstCombine] Negator - sink sinkable negations

[lebedev.ri]

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

This has some potential to cause endless combine loops (either around PHI's, or if there are some opposite transforms).
For former there's -instcombine-negator-max-depth option to mitigate it, should this expose any such issues
For latter, if there are still any such opposing folds, we'd need to remove the colliding fold.
In any case, reproducers welcomed!

[lebedev.ri]

Actually, sub can be freely negated.

[efriedma]

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.)

[lebedev.ri]

In D68408#1695357, @efriedma wrote:

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]

In D68408#1695399, @lebedev.ri wrote:

In D68408#1695357, @efriedma wrote:

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]

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

[lebedev.ri]

@efriedma any high-level feedback on this?

[efriedma]

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 ↗

(On Diff #223412)

InstCombineAddSub.cpp?

[lebedev.ri]

In D68408#1708655, @efriedma wrote:

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]

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

[efriedma]

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.

[lebedev.ri]

In D68408#1710214, @efriedma wrote:

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?

[lebedev.ri]

Erase newly-created/inserted instruction if negation failed.

[lebedev.ri]

Bump

[lebedev.ri]

bump

[lebedev.ri]

Ping

[spatel]

@efriedma - do you want to continue reviewing?

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

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

1007

typo: attempt

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

168 ↗

(On Diff #225184)

it's -> its

182 ↗

(On Diff #225184)

it's -> its

192 ↗

(On Diff #225184)

negatible one -> negatible if one

192 ↗

(On Diff #225184)

it's -> its

243 ↗

(On Diff #225184)

typo: temporarily

llvm/test/Transforms/InstCombine/sub-of-negatible.ll

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?

294–295

Add these tests with baseline results as pre-commit?

374

it's -> its

[lebedev.ri]

In D68408#1767626, @spatel wrote:

@efriedma - do you want to continue reviewing?

In D68408#1767626, @spatel wrote:

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

160

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

[spatel]

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]

NOT READY FOR REVIEW

In D68408#1769213, @spatel wrote:

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.

[lebedev.ri]

Rebased, slightly better, but not there yet still.

[lebedev.ri]

Still not for review

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

[xbolva00]

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

[xbolva00]

llvm/test/Transforms/InstCombine/sub.ll

1183 ↗

(On Diff #232532)

Remove FIXME?

[lebedev.ri]

Rebased.

Finally understood the interfering transforms - this fundamentally interferes with D48754.
Yes, i see the PhaseOrdering regressions if we revert that.
Not yet sure how to deal with this, i see 3 options:

1. don't do such canonicalization (what i've done here)
2. don't implement Negator
3. add Abs IR instruction (i think not)
4. Don't try to sink negation when it's used by abs/nabs pattern

This doesn't hang check-llvm/test-suite.

[lebedev.ri]

Handle PHI's, too.
Strangely, i distinctively recall seeing some preexisting test
causing an endless cycle, but i'm no longer observing that problem.

[xbolva00]

llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll

39 ↗

(On Diff #256801)

Regression

[lebedev.ri]

And solve potential endless combine cycle by not trying to sink negations
if that instruction has an user that looks like abs/nabs.

I think this is it for now, so review is welcomed..

llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll

39 ↗

(On Diff #256801)

https://reviews.llvm.org/D68408#1976039

[spatel]

In D68408#1976039, @lebedev.ri wrote:

1. add Abs IR instruction (i think not)

Is the answer the same for an intrinsic? The more we see these kinds of problems, the more I wish we had created intrinsics for abs/smin/smax/umin/umax long ago. We keep trying to work around this limitation in IR, but it doesn't seem worth it. We have abs() functions in source and an abs node in codegen, so we're creating intermediate ops that don't exist on either side of IR.

[lebedev.ri]

In D68408#1976790, @spatel wrote:

In D68408#1976039, @lebedev.ri wrote:

1. add Abs IR instruction (i think not)

Is the answer the same for an intrinsic?

Ack, i meant instruction/intrinsic interchangeably here.

The more we see these kinds of problems, the more I wish we had created intrinsics for abs/smin/smax/umin/umax long ago. We keep trying to work around this limitation in IR, but it doesn't seem worth it. We have abs() functions in source and an abs node in codegen, so we're creating intermediate ops that don't exist on either side of IR.

Note that we similarly don't have saturating multiplication, overflowing/saturating left-shift.

[spatel]

In D68408#1976807, @lebedev.ri wrote:

In D68408#1976790, @spatel wrote:

In D68408#1976039, @lebedev.ri wrote:

1. add Abs IR instruction (i think not)

Is the answer the same for an intrinsic?

Ack, i meant instruction/intrinsic interchangeably here.

We have grown more accepting of intrinsics (overflow, saturating, funnel, etc.) recently, so I'm not sure if the old arguments against an abs intrinsic still hold. Is there anything in particular about abs() that makes it different?

The more we see these kinds of problems, the more I wish we had created intrinsics for abs/smin/smax/umin/umax long ago. We keep trying to work around this limitation in IR, but it doesn't seem worth it. We have abs() functions in source and an abs node in codegen, so we're creating intermediate ops that don't exist on either side of IR.

Note that we similarly don't have saturating multiplication, overflowing/saturating left-shift.

Yes, there's no clear line that I know of. It's like IR canonicalization - we make the rules up as we go along and adapt the surrounding logic to work with the current format. I think we've overcome the limitation for this patch, so we don't need to gate this patch on a decision, but I think we still have the problem. The clearest sign is that -- within instcombine -- we have bailouts for otherwise accepted canonicalizations only if we "matchSelectPattern()".

[nikic]

In D68408#1977656, @spatel wrote:

Yes, there's no clear line that I know of. It's like IR canonicalization - we make the rules up as we go along and adapt the surrounding logic to work with the current format. I think we've overcome the limitation for this patch, so we don't need to gate this patch on a decision, but I think we still have the problem. The clearest sign is that -- within instcombine -- we have bailouts for otherwise accepted canonicalizations only if we "matchSelectPattern()".

FWIW I agree that we need to reevaluate this decision and at least introduce min/max intrinsics. These are special-cased in too many places for the current treatment as a simple compare and select to still make sense. Especially when we take into account that there seems to be a new min/max related infinite loop every other month, and that the icmp/select representation has ill-defined behavior when it comes to undef. I expect the effort for introducing these intrinsics will be pretty similar to saturating add/sub, and would be happy to chip in...

[xbolva00]

+1 for new abs/min/max intrinsics

[lebedev.ri]

It'd be great if we could separate the new intrinsics disscussion from this patch..

In D68408#1977656, @spatel wrote:

In D68408#1976807, @lebedev.ri wrote:

In D68408#1976790, @spatel wrote:

In D68408#1976039, @lebedev.ri wrote:

1. add Abs IR instruction (i think not)

Is the answer the same for an intrinsic?

Ack, i meant instruction/intrinsic interchangeably here.

We have grown more accepting of intrinsics (overflow, saturating, funnel, etc.) recently, so I'm not sure if the old arguments against an abs intrinsic still hold. Is there anything in particular about abs() that makes it different?

No, i just don't want to condition this patch on introduction of whole new set of intrinsics :]

[spatel]

In D68408#1978925, @nikic wrote:

In D68408#1977656, @spatel wrote:

Yes, there's no clear line that I know of. It's like IR canonicalization - we make the rules up as we go along and adapt the surrounding logic to work with the current format. I think we've overcome the limitation for this patch, so we don't need to gate this patch on a decision, but I think we still have the problem. The clearest sign is that -- within instcombine -- we have bailouts for otherwise accepted canonicalizations only if we "matchSelectPattern()".

FWIW I agree that we need to reevaluate this decision and at least introduce min/max intrinsics. These are special-cased in too many places for the current treatment as a simple compare and select to still make sense. Especially when we take into account that there seems to be a new min/max related infinite loop every other month, and that the icmp/select representation has ill-defined behavior when it comes to undef. I expect the effort for introducing these intrinsics will be pretty similar to saturating add/sub, and would be happy to chip in...

Sounds like general agreement for the people on this review (and sorry for going off-topic for this specific patch). I'll post something to llvm-dev after trying to dig up the earlier discussions for those intrinsics.

And looks like we have this month's infinite loop here :) -
https://bugs.llvm.org/show_bug.cgi?id=45539

[lebedev.ri]

In D68408#1981910, @spatel wrote:

In D68408#1978925, @nikic wrote:

In D68408#1977656, @spatel wrote:

Yes, there's no clear line that I know of. It's like IR canonicalization - we make the rules up as we go along and adapt the surrounding logic to work with the current format. I think we've overcome the limitation for this patch, so we don't need to gate this patch on a decision, but I think we still have the problem. The clearest sign is that -- within instcombine -- we have bailouts for otherwise accepted canonicalizations only if we "matchSelectPattern()".

FWIW I agree that we need to reevaluate this decision and at least introduce min/max intrinsics. These are special-cased in too many places for the current treatment as a simple compare and select to still make sense. Especially when we take into account that there seems to be a new min/max related infinite loop every other month, and that the icmp/select representation has ill-defined behavior when it comes to undef. I expect the effort for introducing these intrinsics will be pretty similar to saturating add/sub, and would be happy to chip in...

Sounds like general agreement for the people on this review (and sorry for going off-topic for this specific patch). I'll post something to llvm-dev after trying to dig up the earlier discussions for those intrinsics.

Note that i've posted https://github.com/AliveToolkit/alive2/pull/353 with my vision of their modelling.
Notably, i don't think we should have nabs, and i believe abs should be similar to the cttz/ctlz
in the sense that it should take a second param - i1 NSW.

In D68408#1978925, @nikic wrote:

In D68408#1977656, @spatel wrote:

Yes, there's no clear line that I know of. It's like IR canonicalization - we make the rules up as we go along and adapt the surrounding logic to work with the current format. I think we've overcome the limitation for this patch, so we don't need to gate this patch on a decision, but I think we still have the problem. The clearest sign is that -- within instcombine -- we have bailouts for otherwise accepted canonicalizations only if we "matchSelectPattern()".

FWIW I agree that we need to reevaluate this decision and at least introduce min/max intrinsics. These are special-cased in too many places for the current treatment as a simple compare and select to still make sense. Especially when we take into account that there seems to be a new min/max related infinite loop every other month, and that the icmp/select representation has ill-defined behavior when it comes to undef. I expect the effort for introducing these intrinsics will be pretty similar to saturating add/sub, and would be happy to chip in...

I think i'd like to try to handle that, since out of the people in this disscussion
only i (well, and @xbolva00) haven't dealt with that before, may be good to spread the knowledge.

[lebedev.ri]

Ping. What would it take to get this moving? :)

[nikic]

Compile-time numbers look good: http://llvm-compile-time-tracker.com/compare.php?from=f52e0507574b4fd84dc4674536f5dfbab396c0f6&to=0a009b654793dee8e335c053eb043e297071e0d1&stat=instructions

Change does not seem to have cost above noise, apart from a -0.6% improvement on tramp3d-v4. There's a corresponding -0.74% reducing in code-size, so this transform is clearly doing (or enabling) something big there. It might be interesting (but not necessary) to take a quick look at what happens there.

[lebedev.ri]

In D68408#1991910, @nikic wrote:

Compile-time numbers look good: http://llvm-compile-time-tracker.com/compare.php?from=f52e0507574b4fd84dc4674536f5dfbab396c0f6&to=0a009b654793dee8e335c053eb043e297071e0d1&stat=instructions

I was actually trying to get that info, and i'm not sure what step i'm missing other than pushing the [[ https://github.com/LebedevRI/llvm-project/tree/perf/instcombine-negator | perf/* ]] branch?

Change does not seem to have cost above noise, apart from a -0.6% improvement on tramp3d-v4. There's a corresponding -0.74% reducing in code-size, so this transform is clearly doing (or enabling) something big there. It might be interesting (but not necessary) to take a quick look at what happens there.

Ah, interesting.
I actually expected this to have measurable negative(bad) cost,
so it's a pleasant surprise to see beneficial numbers here :)

[nikic]

In D68408#1991930, @lebedev.ri wrote:

In D68408#1991910, @nikic wrote:

Compile-time numbers look good: http://llvm-compile-time-tracker.com/compare.php?from=f52e0507574b4fd84dc4674536f5dfbab396c0f6&to=0a009b654793dee8e335c053eb043e297071e0d1&stat=instructions

I was actually trying to get that info, and i'm not sure what step i'm missing other than pushing the [[ https://github.com/LebedevRI/llvm-project/tree/perf/instcombine-negator | perf/* ]] branch?

I need to manually add your fork as a remote first, so branches get picked up (too many forks to listen to all of them). I've done that now.

[spatel]

In D68408#1991910, @nikic wrote:

Compile-time numbers look good: http://llvm-compile-time-tracker.com/compare.php?from=f52e0507574b4fd84dc4674536f5dfbab396c0f6&to=0a009b654793dee8e335c053eb043e297071e0d1&stat=instructions

Change does not seem to have cost above noise, apart from a -0.6% improvement on tramp3d-v4. There's a corresponding -0.74% reducing in code-size, so this transform is clearly doing (or enabling) something big there. It might be interesting (but not necessary) to take a quick look at what happens there.

Yes, it would be good to derive a regression test from that benchmark and/or invent some larger tests that show the greater optimization power of the new code. Unless I missed it, all of the current test diffs show that we do no harm, but if we can show that the added code/complexity buys us something immediately, that makes the benefit clear.

[lebedev.ri]

In D68408#1992227, @spatel wrote:

In D68408#1991910, @nikic wrote:

Compile-time numbers look good: http://llvm-compile-time-tracker.com/compare.php?from=f52e0507574b4fd84dc4674536f5dfbab396c0f6&to=0a009b654793dee8e335c053eb043e297071e0d1&stat=instructions

Change does not seem to have cost above noise, apart from a -0.6% improvement on tramp3d-v4. There's a corresponding -0.74% reducing in code-size, so this transform is clearly doing (or enabling) something big there.
It might be interesting (but not necessary) to take a quick look at what happens there.

Yes, it would be good to derive a regression test from that benchmark

old.ll.xz853 KBDownload

new.ll.xz846 KBDownload

The impact there is quite noticeable as per llvm-diff, which almost immediately crashes.
It appears, a lot more inlining happens (functions now-missing in new.ll),
and some more function 'specialization' (functions now-appearing in new.ll).
I'm not sure i can distill/filter that to make any reasonable test case..

In D68408#1992227, @spatel wrote:

and/or invent some larger tests that show the greater optimization power of the new code.
Unless I missed it, all of the current test diffs show that we do no harm, but if we can show that the added code/complexity buys us something immediately, that makes the benefit clear.

The claim i'm making in the patch's description is that we almost consider sub instruction
non-canonical, and we should be trying to fold it away as much as possible.
These test cases show the common patters, that we miss currently, where we can get rid of it.

This approach is what was requested in

In D68408#1695357, @efriedma wrote:

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.)

[spatel]

Given that we have compile-time data now, LGTM.
The implementation goes beyond my normal casual C++ usage (eg, I'd never seen 'zip' before), so if someone else can take a 2nd/final look too, that would be great.

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

133 ↗

(On Diff #256855)

Remove/update comment.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

180 ↗

(On Diff #256855)

Noticed while looking through the tramp3d-v4 diff: This should be behind a one-use check, to avoid duplicating expensive division instructions.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1938

Just wondering if we could use some better name for this lambda than “cleanup”.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1938

I couldn't come up with a better one, any suggestions?
TryToNarrowDeduceFlags()?
This is where goto might make sense, but somehow i don't want to use it..

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1938

Your idea is fine I think.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

180 ↗

(On Diff #256855)

I was hesitant about this one indeed, it isn't a typo that one-use check has gone away here,
because we generally consider only instruction count.

@spatel thoughts?

But the main, bigger question this touches is:
"but what if all the uses would get negated by us?
In future, can we somehow sanely model the whole negatible tree,
not giving up at non-single-use instructions,
but defer that to after we've finished building new tree?"

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

180 ↗

(On Diff #256855)

I missed that logic difference, and I'm not getting a reviewable diff of the attached files with llvm-diff or other apps. Can you create an IR example/regression test for that?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

180 ↗

(On Diff #256855)

@spatel
To be clear, the "bigger question" is pretty rhetorical, or at least not for this review.

The actual question here is whether we should consider sdiv special,
and even if we can negate it without increasing instruction count,
we should only do so if there are no other uses of old sdiv.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

180 ↗

(On Diff #256855)

There is precedence for this kind of special treatment. In other words, not all opcodes are equal in terms of analysis (and secondary concern of codegen), and we will even increase instruction count to avoid some like div/rem (although those transforms are probably currently not safe with respect to poison).

If it would be NFC-ish to keep the one-use check, then we should do that. Then, remove the limitation as a follow-up if that can be shown useful?

[lebedev.ri]

Updated: adjust comments, lambda name, guard sdiv with an artificial one-use-check.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

180 ↗

(On Diff #256855)

Alright, i'll add one-use check just to get this moving :)

[kcc]

Hi,

This change causes a performance regression in tsan, as detected on our LLVM buildbot:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/49850/steps/tsan%20analyze/logs/stdio

The script that comes with tsan checks the number of PUSH, etc in some of the key tsan functions,
where each extra PUSH cases tsan to be slower.

With this change, the number of PUSHes went from 3 to 4.

Please take a look, this might be a performance regression for a wider set of targets.

Before your change:

read1 tot 484; size 1830; rsp 1; push 3; pop 15; call 2; load 24; store  9; sh  46; mov 106; lea   2; cmp  76

After your change:

read1 tot 515; size 1980; rsp 1; push 4; pop 4; call 2; load 24; store  9; sh  46; mov 113; lea   2; cmp  90

Script to reproduce (in the llvm-project root dir, with "build" subdir)

#!/bin/bash

compile() {

clang -c -O2  compiler-rt/lib/tsan/rtl/tsan_rtl.cpp -I compiler-rt/lib -Wall -std=c++14 -Wno-unused-parameter -O2 -g -DNDEBUG    -m64 -fno-lto -fPIC -fno-builtin -fno-exceptions -fomit-frame-pointer -funwind-tables -fno-stack-protector -fno-sanitize=safe-stack -fvisibility=hidden -fno-lto -O3 -gline-tables-only -Wno-gnu -Wno-variadic-macros -Wno-c99-extensions -Wno-non-virtual-dtor -fPIE -fno-rtti -msse3 -Wframe-larger-than=530 -Wglobal-constructors

}

git checkout a13dce1d90cba6c55252dee0a2600eab37ffbc44
(cd build; ninja clang 2> /dev/null)
compile
compiler-rt/lib/tsan/analyze_libtsan.sh tsan_rtl.o | grep read1

git checkout 352fef3f11f5ccb2ddc8e16cecb7302a54721e9f
(cd build; ninja clang 2> /dev/null)
compile
compiler-rt/lib/tsan/analyze_libtsan.sh tsan_rtl.o | grep read1

[lebedev.ri]

In D68408#1998112, @kcc wrote:

Hi,

Hi.

This change causes a performance regression in tsan, as detected on our LLVM buildbot:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/49850/steps/tsan%20analyze/logs/stdio

Looks like the build was red already: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/49808
That explains why i didn't see the new failure: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/49809

The script that comes with tsan checks the number of PUSH, etc in some of the key tsan functions,
where each extra PUSH cases tsan to be slower.

With this change, the number of PUSHes went from 3 to 4.

Please take a look, this might be a performance regression for a wider set of targets.

Before your change:

read1 tot 484; size 1830; rsp 1; push 3; pop 15; call 2; load 24; store  9; sh  46; mov 106; lea   2; cmp  76

After your change:

read1 tot 515; size 1980; rsp 1; push 4; pop 4; call 2; load 24; store  9; sh  46; mov 113; lea   2; cmp  90

Interesting. Not very unexpected, there's always possibility of an avalanche effect with IR changes.

Unhelpful answer: wow how things have regressed since rL342092 / D51985

Script to reproduce (in the llvm-project root dir, with "build" subdir)

#!/bin/bash

compile() {

clang -c -O2  compiler-rt/lib/tsan/rtl/tsan_rtl.cpp -I compiler-rt/lib -Wall -std=c++14 -Wno-unused-parameter -O2 -g -DNDEBUG    -m64 -fno-lto -fPIC -fno-builtin -fno-exceptions -fomit-frame-pointer -funwind-tables -fno-stack-protector -fno-sanitize=safe-stack -fvisibility=hidden -fno-lto -O3 -gline-tables-only -Wno-gnu -Wno-variadic-macros -Wno-c99-extensions -Wno-non-virtual-dtor -fPIE -fno-rtti -msse3 -Wframe-larger-than=530 -Wglobal-constructors

}

git checkout a13dce1d90cba6c55252dee0a2600eab37ffbc44
(cd build; ninja clang 2> /dev/null)
compile
compiler-rt/lib/tsan/analyze_libtsan.sh tsan_rtl.o | grep read1

git checkout 352fef3f11f5ccb2ddc8e16cecb7302a54721e9f
(cd build; ninja clang 2> /dev/null)
compile
compiler-rt/lib/tsan/analyze_libtsan.sh tsan_rtl.o | grep read1

old.ll1 MBDownload

old.o84 KBDownload

new.ll1 MBDownload

new.o85 KBDownload

llvm-diff report is pretty large, IR instruction-wise, this appears to be a win overall (-639 +609 instructions).
Visually, i think can spot only two IR patterns that we now fail to fold:

in function _ZN6__tsan10InitializeEPNS_11ThreadStateE:
  in block %if.then88.i:
    >   %22 = xor i64 %xor.i.i.i, -17592186044417
    >   %mul.i.i194.neg.i = add i64 %22, 1
    >   %sub.i = add i64 %mul.i.i194.neg.i, %mul.i.i203.i
    <   %mul.i.i194.i = xor i64 %xor.i.i.i, 17592186044416
    <   %sub.i = sub i64 %mul.i.i203.i, %mul.i.i194.i
  in block %if.then88.1.i:
    >   %35 = xor i64 %xor.i.i.1.i, -17592186044417
    >   %mul.i.i194.neg.1.i = or i64 %mul.i.i203.1.i, 1
    >   %sub.1.i = add i64 %mul.i.i194.neg.1.i, %35
    <   %mul.i.i194.1.i = xor i64 %xor.i.i.1.i, 17592186044416
    <   %sub.1.i = sub i64 %mul.i.i203.1.i, %mul.i.i194.1.i

Filed https://bugs.llvm.org/show_bug.cgi?id=45647

But i believe, i'm supposed to look at the @__tsan_read1 function, right?
Then the relevant diff is:

in function __tsan_read1:
  in block %if.then.i1390.i.i.i:
    >   %sub.neg.i1385.i.i.i = sub nsw i64 %and.i19.i1382.i.i.i, %and.i.i1380.i.i.i
    >   %sub.neg.highbits.i1388.i.i.i = lshr i64 %sub.neg.i1385.i.i.i, %and.i.i.i1387.i.i.i
    >   %cmp7.i1389.i.i.i = icmp ne i64 %sub.neg.highbits.i1388.i.i.i, 0
    <   %sub6.i1387.i.i.i = sub nsw i64 0, %sub.i1383.i.i.i
    <   %sub6.highbits.i1388.i.i.i = lshr i64 %sub6.i1387.i.i.i, %and.i.i.i1386.i.i.i
    <   %cmp7.i1389.i.i.i = icmp ne i64 %sub6.highbits.i1388.i.i.i, 0
        %cmp.i1378.i.i.i = icmp ult i64 %xor.i1422.i.i.i, 1125899906842624
    >   %or.cond.i.i.i = or i1 %cmp.i1378.i.i.i, %cmp7.i1389.i.i.i
    >   br i1 %or.cond.i.i.i, label %do.body226.i.i.i, label %if.end86.i.i.i
    <   %or.cond.i.i.i = or i1 %cmp.i1378.i.i.i, %cmp7.i1389.i.i.i
    <   br i1 %or.cond.i.i.i, label %do.body226.i.i.i, label %if.end86.i.i.i

So we've traded 0 - %sub.i1383.i.i.i for %and.i19.i1382.i.i.i - %and.i.i1380.i.i.i
That's it, [un]fortunately, there is nothing else going on..
But thankfully, that explains the problem well.
Pushed rG5a159ed2a8e5a9a6ced73f78e4c64b01d76d3493.
Thanks.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
     // --> (A < 0) ? -A : A
     Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
     // Copy the nuw/nsw flags from the sub to the negate.
     Value *Neg = Builder.CreateNeg(A, "", I.hasNoUnsignedWrap(),
                                    I.hasNoSignedWrap());
     return SelectInst::Create(Cmp, Neg, A);
   }
 
+  // Now that we know we have failed to fold this `sub a, b`, iff `a != 0`,
+  // let's see if it's worth exploding it into `add a, (sub 0, b)`.
+  // It is worth doing if the negation can be sunk into `b`.
+  if (!match(Op0, m_Zero()) && isFreeToNegate(Op1)) {
+    // While this does temporairly increase instruction count, we have ensured
+    // that this `neg` will get absorbed into Op1, so this is ok.
+    Instruction *NegOp1 =
+        BinaryOperator::CreateNeg(Op1, Op1->getName() + ".neg");
+    Instruction *NewAdd = BinaryOperator::CreateAdd(NegOp1, Op0);
+    // Normally, the `neg` would have been added to InstCombine's WorkList
+    // first, and then the `add`. So we'd first revisit `add`, but we just made
+    // it so that one of the `add`s operands is `neg`, so it would hoist that
+    // `neg` and recreate subtraction, and we'll endlessly loop...
+    // Instead, let's manually first add the `add` and *then* `neg`, this way
+    // we will first visit the `neg`, and go on folding it into it's operand.
+    Worklist.Add(NewAdd);
+    Worklist.Add(NegOp1);
+    Builder.Insert(NegOp1);
+    return NewAdd;
+  }
+
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoUnsignedWrap(true);
   }
 
   return Changed ? &I : nullptr;
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.
 static Instruction *foldFNegIntoConstant(Instruction &I) {
   Value *X;
   Constant *C;
 
   // Fold negation into constant operand. This is limited with one-use because

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

for (User *U : V->users()) {
     default:
       return false; // Don't know, likely not freely invertible.
     }
     // So far all users were free to invert...
   }
   return true; // Can freely invert all users!
 }
 
+/// Return true if the specified value is free to negate (subtract from 0).
+/// This happens in cases where the 0 can be eliminated.
+/// For instructions, this is limited to single-use instructions.
+/// The analysis is recursive.
+static inline bool isFreeToNegate(Value *V, unsigned Depth = 0) {
+  // -(-(X)) -> X.
+  if (match(V, m_Neg(m_Value())))
+    return true;
+
+  // Constants can be considered to be negated values.
+  if (match(V, m_AnyIntegralConstant()))
+    return true;
+
+  // Rest of the checking is recursive, so time to pessimistically bailout.
+  if (Depth > 6)
+    return false;
+
+  // If we have a non-instruction, and it's not a constant, then give up.
+  if (!isa<Instruction>(V))
+    return false;
+  // The instruction-in-question must be one-use.
+  if (!V->hasOneUse())
+    return false;
+
+  auto *I = cast<Instruction>(V);
+  switch (I->getOpcode()) {
+  case Instruction::Select:
+    // `select` is negatible if both hands of select are negatible.
+    return isFreeToNegate(I->getOperand(1), Depth + 1) &&
+           isFreeToNegate(I->getOperand(2), Depth + 1);
+  case Instruction::Shl:
+  case Instruction::Sub:
+    // `shl`, `sub` are negatible if their first operand is negatible.
+    return isFreeToNegate(I->getOperand(0), Depth + 1);
+  case Instruction::Add:
+    // `add` is negatible if both of it's operands are negatible.
+    return isFreeToNegate(I->getOperand(0), Depth + 1) &&
+           isFreeToNegate(I->getOperand(1), Depth + 1);
+  case Instruction::Mul:
+    // `mul` is negatible one of it's operands is negatible.
+    return isFreeToNegate(I->getOperand(0), Depth + 1) ||
+           isFreeToNegate(I->getOperand(1), Depth + 1);
+  default:
+    return false; // Don't know, likely not negatible for free.
+  }
+
+  return false;
+}
+
 /// Some binary operators require special handling to avoid poison and undefined
 /// behavior. If a constant vector has undef elements, replace those undefs with
 /// identity constants if possible because those are always safe to execute.
 /// If no identity constant exists, replace undef with some other safe constant.
 static inline Constant *getSafeVectorConstantForBinop(
       BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant) {
   assert(In->getType()->isVectorTy() && "Not expecting scalars here");
 
private:
   ///
   /// If the multiplication is known not to overflow then NoSignedWrap is set.
   Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
 };
 
 } // end namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H

llvm/test/Transforms/InstCombine/sub-of-negatible.ll

;
   call void @use8(i8 %t0)
   %t1 = sub i8 %x, %t0
   ret i8 %t1
 }
 
 ; Shift-left can be negated if all uses can be updated
 define i8 @t2(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t2(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 -42, [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 42, [[Y:%.*]]
+; CHECK-NEXT:    [[T1:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = shl i8 -42, %y
   %t1 = sub i8 %x, %t0
   ret i8 %t1
 }
 define i8 @n2(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n2(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i8 -42, [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = shl i8 -42, %y
   call void @use8(i8 %t0)
   %t1 = sub i8 %x, %t0
   ret i8 %t1
 }
 define i8 @t3(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @t3(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = shl i8 [[T0]], [[Y:%.*]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[Z]], [[Y:%.*]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = sub i8 0, %z
   call void @use8(i8 %t0)
   %t1 = shl i8 %t0, %y
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
;
   call void @use8(i8 %t1)
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
 
 ; Select can be negated if all it's operands can be negated and all the users of select can be updated
 define i8 @t4(i8 %x, i1 %y) {
 ; CHECK-LABEL: @t4(
-; CHECK-NEXT:    [[T0:%.*]] = select i1 [[Y:%.*]], i8 -42, i8 44
-; CHECK-NEXT:    [[T1:%.*]] = sub i8 [[X:%.*]], [[T0]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 42, i8 -44
+; CHECK-NEXT:    [[T1:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = select i1 %y, i8 -42, i8 44
   %t1 = sub i8 %x, %t0
   ret i8 %t1
 }
 define i8 @n4(i8 %x, i1 %y) {
 ; CHECK-LABEL: @n4(
;
   %t0 = select i1 %y, i8 -42, i8 %z
   %t1 = sub i8 %x, %t0
   ret i8 %t1
 }
 define i8 @t6(i8 %x, i1 %y, i8 %z) {
 ; CHECK-LABEL: @t6(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[Y:%.*]], i8 -42, i8 [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 42, i8 [[Z]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = sub i8 0, %z
   call void @use8(i8 %t0)
   %t1 = select i1 %y, i8 -42, i8 %t0
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
 define i8 @t7(i8 %x, i1 %y, i8 %z) {
 ; CHECK-LABEL: @t7(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[Z:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
+; CHECK-NEXT:    [[T0_OP:%.*]] = shl i8 -1, [[Z:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0_OP]]
+; CHECK-NEXT:    [[T2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = shl i8 1, %z
   %t1 = select i1 %y, i8 0, i8 %t0
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
 define i8 @n8(i8 %x, i1 %y, i8 %z) {
 ; CHECK-LABEL: @n8(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[Z:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
 ; CHECK-NEXT:    [[T1:%.*]] = select i1 [[Y:%.*]], i8 0, i8 [[T0]]
 ; CHECK-NEXT:    [[T2:%.*]] = sub i8 [[X:%.*]], [[T1]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = shl i8 1, %z
   call void @use8(i8 %t0)
   %t1 = select i1 %y, i8 0, i8 %t0
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
 
 ; Subtraction can be negated if the first operand can be negated
 ; x - (y - z) -> x - y + z -> x + (-y) + z
 define i8 @t9(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @t9(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 0, [[Z:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
 ; CHECK-NEXT:    [[T11:%.*]] = add i8 [[Y:%.*]], [[Z]]
 ; CHECK-NEXT:    [[T2:%.*]] = add i8 [[T11]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[T2]]
 ;
   %t0 = sub i8 0, %z

 ;
   %t0 = sub i8 0, %y
   call void @use8(i8 %t0)
   %t1 = mul i8 %t0, %z
   call void @use8(i8 %t1)
   %t2 = sub i8 %x, %t1
   ret i8 %t2
 }
+
+; We shouldn't try to convert -b into 0+(-b)
+define i32 @dont_touch_negation_itself(i32 %x, i32 %y) {
+  %a = mul i32 %y, 3
+  %b = mul i32 %a, %x
+  %mul = sub i32 0, %b
+  ret i32 %mul
+}