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

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
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160422/c28a56bd/attachment.html>

As I recall, the reason we chose to emit this via an intrinsic from Clang
rather than directly as profile information was to catch cases where the
builtin is *not* the immediate operand of a control flow construct, but
would be after some simple optimization. For instance:

  bool b = __builtin_expect(n > 5, true);
  if (b) { ... }
  // ...
  if (b) { ... }

or

  if (x && __builtin_expect(y, true)) { ... }

It sounds like subsequent changes to LLVM have already made most of these
cases not work, so some of the motivation for the current approach may have
evaporated. What optimizations do we still perform before lowering the
expect intrinsics?

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/20160422/082a1c30/attachment.html>

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/20160422/e47f05c5/attachment.html>

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 <mailto: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
<mailto: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
<mailto: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
<mailto: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 <mailto: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
<https://marc.info/?l=llvm-commits&m=130997676129580&w=4>
&m=130997676129580&w=4

 

 

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org <mailto: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 <mailto: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/20160422/109220ec/attachment.html>