llvm dev - Jun 2013 - [LLVMdev] RFC - Profile Guided Optimization in LLVM

On 2013-06-15 14:18 , Evan Cheng wrote:
> Apple folks are also gearing up to push on the PGO front. We are 
> primarily interested in using instrumentation, rather than sampling, 
> to collect profile info. However, I suspect the way profile ended up 
> being used in the various optimization and codegen passes would be 
> largely similar.
>
Excellent!  We are initially interested in instrumentation, as well.  
This is where we draw most of our performance with GCC. Sampling is 
showing a lot of promise, however.  And it really is not much different 
than instrumentation.  Most of what changes is the source of profile data.
> There is also some interests in pursuing profile directed 
> specialization. But that can wait. I think it makes sense for us to 
> get together and discuss our plans to make sure there won't be 
> duplication of efforts.
Sure. My initial plan is fairly simple.  Triage the existing 
instrumentation code and see what needs fixing.  I'm starting this in 
the next week or so.  What are your plans?


Diego.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130617/df923727/attachment.html>

On Jun 17, 2013, at 6:54 AM, Diego Novillo <dnovillo at google.com> wrote:
> On 2013-06-15 14:18 , Evan Cheng wrote:
>> Apple folks are also gearing up to push on the PGO front. We are
primarily interested in using instrumentation, rather than sampling, to collect
profile info. However, I suspect the way profile ended up being used in the
various optimization and codegen passes would be largely similar.
>> 
> 
> Excellent!  We are initially interested in instrumentation, as well.  This
is where we draw most of our performance with GCC. Sampling is showing a lot of
promise, however.  And it really is not much different than instrumentation. 
Most of what changes is the source of profile data.
> 
>> There is also some interests in pursuing profile directed
specialization. But that can wait. I think it makes sense for us to get together
and discuss our plans to make sure there won't be duplication of efforts.
> 
> Sure. My initial plan is fairly simple.  Triage the existing
instrumentation code and see what needs fixing.  I'm starting this in the
next week or so.  What are your plans?
Your short term plan sounds great. We have some tentative plans build / improve
the instrumentation tools and start to enhancing various passes to use profile
data. Beyond that, our plan is still vague. Bob, comments?

Evan
> 
> 
> Diego.

On Jun 17, 2013, at 6:54 AM, Diego Novillo <dnovillo at google.com> wrote:
> On 2013-06-15 14:18 , Evan Cheng wrote:
>> Apple folks are also gearing up to push on the PGO front. We are
primarily interested in using instrumentation, rather than sampling, to collect
profile info. However, I suspect the way profile ended up being used in the
various optimization and codegen passes would be largely similar.
>> 
> 
> Excellent!  We are initially interested in instrumentation, as well.  This
is where we draw most of our performance with GCC. Sampling is showing a lot of
promise, however.  And it really is not much different than instrumentation. 
Most of what changes is the source of profile data.
> 
>> There is also some interests in pursuing profile directed
specialization. But that can wait. I think it makes sense for us to get together
and discuss our plans to make sure there won't be duplication of efforts.
> 
> Sure. My initial plan is fairly simple.  Triage the existing
instrumentation code and see what needs fixing.  I'm starting this in the
next week or so.  What are your plans?
I've been working on prototyping a new approach to instrumentation for both
PGO and code coverage testing.  I want to use the same data for both of those
uses, and for code coverage we really need to have accurate source location
info, including column positions and the starting and ending locations for every
block of code.  Working backward from the debug info to find source locations
hasn't worked very well.  The debug info just doesn't have enough
detailed information. Instead, I am planning to insert the instrumentation code
in the front-end.  The raw profile data in this scheme is tied to source
locations.  One disadvantage is that it conflicts with the goal of having
graceful degradation.  Simply adding a blank line invalidates all the following
source locations.  My plan is to ignore any profile data whenever the source
changes in any way.  We had some discussions about this, and it is easy to come
up with cases where even a trivial change to the source, e.g., enabling a
debugging flag, causes massive changes in the profile data.  I don't think
graceful degradation should even be a goal.  It is too hard to sort out
insignificant changes from those that should invalidate all the profile data.

I am still at least a few weeks away from having any details to share about this
new instrumentation scheme.  I want to convince myself that it is viable before
making a proposal to add it to LLVM.

I don't know if this new kind of instrumentation will fit everyone's
needs for PGO.  I hope that it will, but regardless the most important thing is
that we standardize on the representation of profile data in the IR.  We have a
good start on that already with the branch probability metadata.  The missing
piece is adding per-function metadata to record the execution counts.  We had
planned to add that along with the branch probabilities but haven't gotten
it done yet.  You can see the lack of it in BlockFrequency::getEntryFrequency(),
which just returns a constant value.  We will want that to allow comparing
profile data across different functions, which you can't easily get from the
branch probabilities alone.  I don't think anyone has yet come up with a 
specific proposal for that.

As long as we agree on the canonical metadata, there should be no problem with
supporting different kinds of profile generators, including things like Auto
FDO.

I also agree about the importance of getting inlining to use the PGO data. 
Chandler had looked into that and found that it was really difficult to do it
properly with the current pass manager.  Has any progress been made on that
front?

On Tue, Jun 18, 2013 at 11:19 AM, Bob Wilson <bob.wilson at apple.com>
wrote:
>
> On Jun 17, 2013, at 6:54 AM, Diego Novillo <dnovillo at google.com>
wrote:
>
>> On 2013-06-15 14:18 , Evan Cheng wrote:
>>> Apple folks are also gearing up to push on the PGO front. We are
primarily interested in using instrumentation, rather than sampling, to collect
profile info. However, I suspect the way profile ended up being used in the
various optimization and codegen passes would be largely similar.
>>>
>>
>> Excellent!  We are initially interested in instrumentation, as well. 
This is where we draw most of our performance with GCC. Sampling is showing a
lot of promise, however.  And it really is not much different than
instrumentation.  Most of what changes is the source of profile data.
>>
>>> There is also some interests in pursuing profile directed
specialization. But that can wait. I think it makes sense for us to get together
and discuss our plans to make sure there won't be duplication of efforts.
>>
>> Sure. My initial plan is fairly simple.  Triage the existing
instrumentation code and see what needs fixing.  I'm starting this in the
next week or so.  What are your plans?
>
> I've been working on prototyping a new approach to instrumentation for
both PGO and code coverage testing.  I want to use the same data for both of
those uses, and for code coverage we really need to have accurate source
location info, including column positions and the starting and ending locations
for every block of code.  Working backward from the debug info to find source
locations hasn't worked very well.  The debug info just doesn't have
enough detailed information.
I'm curious what problems you've had. You've surely not mentioned
them
before. Note that I'm not saying that I think this is the best method,
but I'm curious what problems you've had and what you're running
into.
> Instead, I am planning to insert the instrumentation code in the front-end.
The raw profile data in this scheme is tied to source locations.  One
disadvantage is that it conflicts with the goal of having graceful degradation. 
Simply adding a blank line invalidates all the following source locations.  My
plan is to ignore any profile data whenever the source changes in any way.  We
had some discussions about this, and it is easy to come up with cases where even
a trivial change to the source, e.g., enablin!
>  g a debugging flag, causes massive changes in the profile data.  I
don't think graceful degradation should even be a goal.  It is too hard to
sort out insignificant changes from those that should invalidate all the profile
data.
>
Even a comment?

-eric

On Jun 18, 2013, at 11:19 AM, Bob Wilson <bob.wilson at apple.com> wrote:
> The missing piece is adding per-function metadata to record the execution
counts.  We had planned to add that along with the branch probabilities but
haven't gotten it done yet.  You can see the lack of it in
BlockFrequency::getEntryFrequency(), which just returns a constant value.  We
will want that to allow comparing profile data across different functions, which
you can't easily get from the branch probabilities alone.
Our 64-bit fixpoint representation of block frequencies doesn’t have the dynamic
range to do that. See PR16402.

/jakob

On Jun 18, 2013, at 11:19 AM, Bob Wilson <bob.wilson at apple.com> wrote:
> 
> On Jun 17, 2013, at 6:54 AM, Diego Novillo <dnovillo at google.com>
wrote:
> 
>> On 2013-06-15 14:18 , Evan Cheng wrote:
>>> Apple folks are also gearing up to push on the PGO front. We are
primarily interested in using instrumentation, rather than sampling, to collect
profile info. However, I suspect the way profile ended up being used in the
various optimization and codegen passes would be largely similar.
>>> 
>> 
>> Excellent!  We are initially interested in instrumentation, as well. 
This is where we draw most of our performance with GCC. Sampling is showing a
lot of promise, however.  And it really is not much different than
instrumentation.  Most of what changes is the source of profile data.
>> 
>>> There is also some interests in pursuing profile directed
specialization. But that can wait. I think it makes sense for us to get together
and discuss our plans to make sure there won't be duplication of efforts.
>> 
>> Sure. My initial plan is fairly simple.  Triage the existing
instrumentation code and see what needs fixing.  I'm starting this in the
next week or so.  What are your plans?
> 
> I've been working on prototyping a new approach to instrumentation for
both PGO and code coverage testing.  I want to use the same data for both of
those uses, and for code coverage we really need to have accurate source
location info, including column positions and the starting and ending locations
for every block of code.  Working backward from the debug info to find source
locations hasn't worked very well.  The debug info just doesn't have
enough detailed information. Instead, I am planning to insert the
instrumentation code in the front-end.  The raw profile data in this scheme is
tied to source locations.  One disadvantage is that it conflicts with the goal
of having graceful degradation.  Simply adding a blank line invalidates all the
following source locations.  My plan is to ignore any profile data whenever the
source changes in any way.  We had some discussions about this, and it is easy
to come up with cases where even a trivial change to the source, e.g., enabling
a debugging flag, causes massive changes in the profile data.  I don't think
graceful degradation should even be a goal.  It is too hard to sort out
insignificant changes from those that should invalidate all the profile data.
> 
> I am still at least a few weeks away from having any details to share about
this new instrumentation scheme.  I want to convince myself that it is viable
before making a proposal to add it to LLVM.
> 
> I don't know if this new kind of instrumentation will fit
everyone's needs for PGO.  I hope that it will, but regardless the most
important thing is that we standardize on the representation of profile data in
the IR.  We have a good start on that already with the branch probability
metadata.  The missing piece is adding per-function metadata to record the
execution counts.  We had planned to add that along with the branch
probabilities but haven't gotten it done yet.  You can see the lack of it in
BlockFrequency::getEntryFrequency(), which just returns a constant value.  We
will want that to allow comparing profile data across different functions, which
you can't easily get from the branch probabilities alone.  I don't think
anyone has yet come up with a  specific proposal for that.
> 
> As long as we agree on the canonical metadata, there should be no problem
with supporting different kinds of profile generators, including things like
Auto FDO.
> 
> I also agree about the importance of getting inlining to use the PGO data. 
Chandler had looked into that and found that it was really difficult to do it
properly with the current pass manager.  Has any progress been made on that
front?
Well, it took me much longer than a few weeks, and I completely abandoned the
idea to tie the data to specific source locations and require it to be
regenerated for any source change at all, but I finally have a proposal for
doing PGO with instrumentation.  Because that proposal is to do the
instrumentation and the metadata generation in the front-end, so I've sent
it to the cfe-dev list.  Please have a look if you're interested.