[llvm-dev] [cfe-dev] [RFC] remove the llvm.expect intrinsic

Fri Apr 29 14:48:51 PDT 2016

A linkfest summary of the current state of __builtin_expect()...

Abandoned:
http://reviews.llvm.org/D19299
http://reviews.llvm.org/D19300

Committed:
http://reviews.llvm.org/D19435
http://reviews.llvm.org/D19488

The motivating bug for all of the above is resolved fixed:
https://llvm.org/bugs/show_bug.cgi?id=27344

The failing examples that I noted in this thread and elsewhere are open:
https://llvm.org/bugs/show_bug.cgi?id=27541
https://llvm.org/bugs/show_bug.cgi?id=27542

I also linked this existing bug to the above:
https://llvm.org/bugs/show_bug.cgi?id=19230

And we still need to fix places in the optimizer where we drop branch
weight metadata, eg:
http://reviews.llvm.org/rL267624
http://reviews.llvm.org/rL267813

On Fri, Apr 22, 2016 at 4:57 PM, Martin J. O'Riordan <
martin.oriordan at movidius.com> wrote:

> Thanks for the clarification Sanjay - I had somehow misunderstood the
> intent, but your response clear this up.
>
>
>
> Sorry for the confusion,
>
>
>
>             MartinO
>
>
>
> *From:* Sanjay Patel [mailto:spatel at rotateright.com]
> *Sent:* 22 April 2016 23:46
> *To:* Martin.ORiordan at movidius.com
> *Cc:* Xinliang David Li <xinliangli at gmail.com>; llvm-dev <
> llvm-dev at lists.llvm.org>; David Li <davidxl at google.com>; Nick Lewycky <
> nicholas at mxc.ca>; cfe-dev <cfe-dev at lists.llvm.org>
>
> *Subject:* Re: [cfe-dev] [llvm-dev] [RFC] remove the llvm.expect intrinsic
>
>
>
> Hi Martin -
>
> 1. Nobody is proposing to remove __builtin_expect(); we're just debating
> the best way to lower that programmer hint. The question is whether we need
> an *llvm.expect* intrinsic or if some kind of metadata will be adequate.
>
> 2. The fact that using __builtin_expect() improved perf regardless of
> whether you chose the right or wrong prediction isn't too far-fetched IMO -
> it means that a branch (and HW prediction) was the better choice in that
> situation versus a select / conditional move. The compiler generated the
> branch, and the HW branch predictor did the rest.
>
> 3. The original motivation for this proposed cleanup is a bug where
> __builtin_expect() is being ignored:
> https://llvm.org/bugs/show_bug.cgi?id=27344
>
>
>
>
>
> On Fri, Apr 22, 2016 at 4:18 PM, Martin J. O'Riordan <
> martin.oriordan at movidius.com> wrote:
>
> Sorry for jumping in so late into this discussion, but I genuinely believe
> that removing this is a bad idea.
>
>
>
> My reason for saying this is going to sound very strange, but I think that
> we need to understand a bit more about how this is being handled.
>
>
>
> A while back one of my customers asked me if there was a method for
> advising the compiler how an *if-statement* was likely to resolve, and I
> said “sure” and told them to use ‘__builtin_expect’.
>
>
>
> At the time I thought that the compiler was probably predicting a higher
> probability or true/false than was actually the case for a particular
> instance, as my customer was telling me that the compiler was optimising in
> favour of the less probable case (something the customer knew, but the
> information could not be determined from the code).
>
>
>
> This was fair enough, these things happen and the customer (or profile
> directed feedback) has more knowledge than the default inferences in the
> compiler.
>
>
>
> They added the ‘__builtin_expect’ to provide their domain specific expert
> knowledge, and the performance did indeed improve as expected, with the
> compiler preferring the most likely branch that the programmer had
> indicated.
>
>
>
> The surprise though, was when we experimentally changed the outcome of the
> ‘__builtin_expect’ to say the exact opposite of what the actual case
> was.  That is, to invert the truth.  The program was more performant with
> the “wrong” truth than it was with no statement of truth.  When we told the
> compiler that a particular outcome was more probable than when in fact it
> was less, the performance was better than when we said nothing.  And when
> we told it the actual probable outcome, it was more performance still.  So
> telling the outcome of the branch as being more likely true, or more likely
> false, was better than not telling the compiler anything at all.
>
>
>
> I must admit, this was a considerable surprise for me, but it does mean
> that there is something changing in that area of the code that responds
> differently when ‘__builtin_expect’ is used versus the inferred
> probabilities.
>
>
>
> It is not something that I have investigated further as it is not a
> specific area that I can prioritise my efforts, but I think that it is
> something I have to raise awareness off in the context of this thread where
> removing this builtin is being proposed.  At the moment I have a lot of
> programs that are benefitting from the explicit use of this builtin, even
> when the programmer directed outcome is wrong.  So before we can remove
> this builtin, we need to explain why there is a difference on behaviour
> when it is present and stating a particular outcome versus it being omitted
> and the inferred outcome being the same.
>
>
>
>             MartinO
>
>
>
> *From:* cfe-dev [mailto:cfe-dev-bounces at lists.llvm.org] *On Behalf Of *Xinliang
> David Li via cfe-dev
> *Sent:* 22 April 2016 22:49
> *To:* Sanjay Patel <spatel at rotateright.com>
> *Cc:* llvm-dev <llvm-dev at lists.llvm.org>; cfe-dev <cfe-dev at lists.llvm.org>;
> David Li <davidxl at google.com>; Nick Lewycky <nicholas at mxc.ca>
> *Subject:* Re: [cfe-dev] [llvm-dev] [RFC] remove the llvm.expect intrinsic
>
>
>
> Your patch does make the handling of __builtin_unpredictable and
> __builtin_expect 'unified' in some way.
>
>
>
> However given the point brought up by Reid, and the rationale by Richard,
> as well as consideration of the easiness for enhancement in the future, I
> think keep the current mechanism is a better approach.
>
>
>
> The test cases from Richard are broken with current lowering, but it is
> just bugs to be fixed.
>
>
>
> David
>
>
>
> On Fri, Apr 22, 2016 at 1:50 PM, Sanjay Patel via cfe-dev <
> cfe-dev at lists.llvm.org> wrote:
>
> I, of course, thought the ~100 lines added by D19299 was a reasonable
> trade for the ~800 lines removed in D19300.
>
>
> David Li (and anyone else following along), do you still like those
> patches after hearing this objection or should I abandon?
>
>
>
> On Fri, Apr 22, 2016 at 11:55 AM, Reid Kleckner <rnk at google.com> wrote:
>
> Sorry, I didn't realize that was the clang side.
>
>
>
> I think it's kind of ugly that the frontend has to pattern match and lower
> this intrinsic in three places: if, switch, and general case. The existing
> intrinsic is nice because it directly represents what the user can write,
> and lets the optimizer decide how to best represent it. As David Li
> mentioned, we may want to do value profiling in the future, and if we
> remove this intrinsic, we will have to come and revisit this code.
>
> I think a single early pass to lower this intrinsic is a low cost to pay
> for that simplicity.
>
>
>
> On Fri, Apr 22, 2016 at 10:39 AM, Sanjay Patel <spatel at rotateright.com>
> wrote:
>
> Hi Reid -
>
> The intent of D19299 is to remove all Clang refs to llvm.expect. Do you
> see any holes after applying that patch?
>
>
>
> On Fri, Apr 22, 2016 at 11:36 AM, Reid Kleckner <rnk at google.com> wrote:
>
> Clang still appears to use llvm.expect. I think if you can show that it's
> trivial to update clang with a patch, then yeah, moving back down to one
> representation for this sounds reasonable.
>
>
>
> On Fri, Apr 22, 2016 at 9:20 AM, Sanjay Patel via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> I've proposed removing the llvm.expect intrinsic:
> http://reviews.llvm.org/D19300
>
> The motivation for this change is in:
> http://reviews.llvm.org/D19299
>
> For reference:
> 1. We created an intrinsic that's only reason for existing is to improve
> perf, but the intrinsic can harm optimization by interfering with
> transforms in other passes.
>
> 2. To solve that, we created a pass to always transform the intrinsic into
> metadata at a very early stage in LLVM. But now every program is paying a
> compile-time tax (running the LowerExpectIntrinsic pass) for a feature that
> is rarely used.
>
> A possible front-end replacement transformation for a source-level
> "builtin_expect()" is in D19299: I think a front-end can always directly
> create metadata for this kind of programmer hint rather than using an
> intermediate representation (the intrinsic). Likewise, if there's some
> out-of-tree IR pass that is creating an llvm.expect, it should be able to
> create branch weight metadata directly instead.
>
> Please let me know if you see any problems with this proposal or the
> patches.
>
> For reference, here's the original post-commit review thread for
> llvm.expect:
> https://marc.info/?l=llvm-commits&m=130997676129580&w=4
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
>
>
>
>
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160429/98ae025e/attachment.html>