Page MenuHomePhabricator

[SCEVExpander] Try to create ASHR instr for expanded SCEV expr.
Changes PlannedPublic

Authored by fhahn on Apr 18 2021, 4:30 AM.

Details

Summary

ec54867df5e7 updated SCEV to epxand ASHR instructions to an
equivalent SCEV expression. This has the side effect that expanding
expressions based on ASHR instructions now expand to substantially
larger IR than before, which means the IndVarSimplify for example can
add a substantial amount of extra instructions when re-writing exit
conditions. This is causing ~5% regressions in some Geekbench
benchmarks.

This patch tries to match the SCEV expression created for ASHR during
expansion and emit an ASHR instruction directly. Note that currently
this pattern is not completely correct, because we have no way of
differentiating exact and non-exact UDivs in SCEV (see
the no_ashr_due_to_missing_exact_udiv test case, which generates ashr
incorrectly)! This needs to be resolved first and I'd appreciate any
feedback on the preferred direction.

Should we just add a flag to SCEVUDivExpr? Or mark UDivs as exact in a
separate table?

Note that there are other places using SCEVExpander where this likely
pessimizes the generated IR, e.g. when generating runtime checks for LV.

Diff Detail

Event Timeline

fhahn created this revision.Apr 18 2021, 4:30 AM
fhahn requested review of this revision.Apr 18 2021, 4:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 18 2021, 4:30 AM
nikic added a comment.Apr 18 2021, 5:05 AM

Should we just add a flag to SCEVUDivExpr? Or mark UDivs as exact in a
separate table?

Due to SCEV unification, it is not possible to transfer poison-generating flags from IR to SCEV expressions, without proving that a poison result would always cause UB in any scope for which the SCEV expression is valid. For non-addrecs this is only possible in very narrow situations (instruction in loop header, based on addrec in that loop, poison causes UB), so it's not really useful in this situation. Certainly wouldn't cover your examples.

I would recommend reverting rGec54867df5e7f20e12146e628af34f0384308bcb.

fhahn added a comment.Apr 18 2021, 5:45 AM

Should we just add a flag to SCEVUDivExpr? Or mark UDivs as exact in a
separate table?

Due to SCEV unification, it is not possible to transfer poison-generating flags from IR to SCEV expressions, without proving that a poison result would always cause UB in any scope for which the SCEV expression is valid. For non-addrecs this is only possible in very narrow situations (instruction in loop header, based on addrec in that loop, poison causes UB), so it's not really useful in this situation. Certainly wouldn't cover your examples.

In the examples, wouldn't overflow of the ASHR be UB in all scopes, as each path from the ashr to the exit needs to go through a branch which compares the result of the ashr? (ignoring fact that branch on undef/poison is not yet considered UB by ValueTracking)

I would recommend reverting rGec54867df5e7f20e12146e628af34f0384308bcb.

That's certainly a good way forward for now IMO, as I definitely agree that the improved modeling would be a lot of work and even then it is not clear how feasible this would be for real-world cases.

@ebedev.ri Given that ec54867df5e7 can have a noticeable negative impact on performance, WDYT about a revert?

lebedev.ri added a subscriber: craig.topper.EditedApr 18 2021, 6:16 AM

revert

+1

If you don't mind me asking, i forgot when was the last time
i have seen any (coherent?) message longer than two phrases from you;
all recent comments are simply non-comments flippantly reiterating
the last point made in whatever thread.
What's up with that?

I would recommend reverting rGec54867df5e7f20e12146e628af34f0384308bcb.

That's certainly a good way forward for now IMO, as I definitely agree that the improved modeling would be a lot of work and even then it is not clear how feasible this would be for real-world cases.

@lebedev.ri Given that ec54867df5e7 can have a noticeable negative impact on performance, WDYT about a revert?

Hmm, so the problem is that we *can't* reconstruct ashr/ashr exact from it's SCEV model:

$ ./alive-tv /tmp/test.ll --bidirectional

----------------------------------------
define i8 @src(i8 %x) {
%0:
  %r = ashr exact i8 %x, 4
  ret i8 %r
}
=>
define i8 @tgt(i8 %x) {
%0:
  %abs_x = abs i8 %x, 0
  %div = udiv exact i8 %abs_x, 16
  %t0 = smax i8 %x, 255
  %t1 = smin i8 %t0, 1
  %r = mul nsw i8 %div, %t1
  ret i8 %r
}
Transformation seems to be correct!

These functions seem to be equivalent!
$ ./alive-tv /tmp/test.ll --bidirectional

----------------------------------------
define i8 @src(i8 %x) {
%0:
  %abs_x = abs i8 %x, 0
  %div = udiv i8 %abs_x, 16
  %t0 = smax i8 %x, 255
  %t1 = smin i8 %t0, 1
  %r = mul nsw i8 %div, %t1
  ret i8 %r
}
=>
define i8 @tgt(i8 %x) {
%0:
  %r = ashr i8 %x, 4
  ret i8 %r
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
i8 %x = #xc8 (200, -56)

Source:
i8 %abs_x = #x38 (56)
i8 %div = #x03 (3)
i8 %t0 = #xff (255, -1)
i8 %t1 = #xff (255, -1)
i8 %r = #xfd (253, -3)

Target:
i8 %r = #xfc (252, -4)
Source value: #xfd (253, -3)
Target value: #xfc (252, -4)

I don't recall my thoughts on that back then, but it's clearly bad.
That being said we really should model ashr exact in SCEV,
that comes up all the time you want to compute the distance between to pointers e.g.

So i'll revert for now, thanks!

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
828–829

i think this matcher should be ,

xbolva00 added a comment.EditedApr 18 2021, 6:48 AM

If you don't mind me asking, i forgot when was the last time
i have seen any (coherent?) message longer than two phrases from you;

  1. Here I just agree with Florian and Nikita. Florian shared good motivation for revert (regressions and pessimized IR) and I think the revert is reasonable solution (as the problem is not so easy to solve other way), so my "+1".
  1. Please avoid words like these. Really. Last warning.

I would accept if you said "hey, you wrote +1 but why do you think so? Same concerns like florian or nikita or something else?" as a productive criticism but now it looks like an aggressive tone from you.

  • We have a freedom of speech and my comment "+1" cannot offend you.

all recent comments are simply non-comments flippantly reiterating the last point made in whatever thread.

Stop lying - https://reviews.llvm.org/p/xbolva00/.

Bluh, and are you stalking me and checking all my comments? Do you count number of sentences in my messages on phab? Why do you even judge my messages on Phab?

I dont think my comments are somehow bad or inappropriate, others can check them:
https://reviews.llvm.org/p/xbolva00/

Casual reminder that english isn't everyone's native language,
and tone/intent doesn't translate well.

If you don't mind me asking, i forgot when was the last time
i have seen any (coherent?) message longer than two phrases from you;

  1. Here I just agree with Florian and Nikita. Florian shared good motivation for revert (regressions and pessimized IR) and I think the revert is reasonable solution (as the problem is not so easy to solve other way), so my "+1".
  1. Please avoid words like these. Really. Last warning.

I would accept if you said "hey, you wrote +1 but why do you think so? Same concerns like florian or nikita or something else?" as a productive criticism but now it looks like an aggressive tone from you.

Hm, how was that aggressive? I may be missing context here.

  • We have a freedom of speech and my comment "+1" cannot offend you.

Please do not tell other what can and what can not offend them.

  • And are you stalking me? Do you count number of sentences in my messages on phab? Why do you judge my messages on Phab?

*You*? Nope.
All mails to -commits/-dev - yep, absolutely, simply because i read those emails.

I guess we may have different definitions for the word "judge" here,
because i'm not casting a judgment on *you*, the person,
i'm only being a bit vary of the review feedback posted.

all recent comments are simply non-comments flippantly reiterating the last point made in whatever thread.

Stop lying - https://reviews.llvm.org/p/xbolva00/.

Again, i haven't actually gone and reread every comment,
i'm simply voicing my potentially-faulty observation from the reviews i have seen.

Bluh, and are you stalking me and checking all my comments? Do you count number of sentences in my messages on phab? Why do you even judge my messages on Phab?

I dont think my comments are somehow bad or inappropriate, others can check it:
https://reviews.llvm.org/p/xbolva00/

Again, i never said that. I only said that they mostly only reiterate the last point made, but not frequently make a new point.

xbolva00 added a comment.EditedApr 18 2021, 7:31 AM

Again, i never said that. I only said that they mostly only reiterate the last point made, but not frequently make a new point.

Sorry, but.... is it wrong? Am I breaking some community rules? If so, tell me, if not, then ... :)

Is it bad to respond on new comments or new patch revisions? No, I consider it OK. Is there any problem that I do "not frequently make a new point"? I dont think so. I comment what I want. I can ask (nobody is obligatory to answer me), I can request some change in a patch and also it is fine to thank if my feedback was addressed. I can send one patch per day and also I can send one patch per year - OK too. We do (and some of us in our free time) what we can to improve this project.

Hm, how was that aggressive?

I took it something like "Your comments are well.. to be honest a trash. Usually few words/sentences, nothing new, just reaction on the last point on phab reviews. I cant remember anything good/new points from you".

Example of regression:

uint64_t sum(std::vector<uint64_t>& data){
    uint64_t total = 0;
    for (size_t i = 0, e = data.size(); i < e; i++) {
        total += data.at(i);
    }
    return total;
}

https://godbolt.org/z/zTMfazoao

fhahn planned changes to this revision.Apr 19 2021, 2:47 AM

I'm dropping this for a bit, as the commit introducing the perf regression has been reverted for now.

mkazantsev added inline comments.Apr 19 2021, 2:52 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
813

I think there is a bug here for Abs->getOperand(0) == Abs->getOperand(1) == SINT_MIN.

Matt added a subscriber: Matt.Apr 19 2021, 4:56 AM