thr3ads.net - llvm dev - [llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO [Aug 2021]

If this information is useful, please help other people find it:
Share via:

Teresa Johnson via llvm-dev

2021-Jul-27 15:00 UTC

[llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO

I can answer questions from the ThinLTO standpoint. Missed the earlier
emails on this, but I just skimmed the other llvm-dev email and the patch.
I have a high level question and can give some thoughts on the approach
from a ThinLTO standpoint.

One important thing to note is that we import functions with
available_externally linkage, because they still live in their original
translation unit. The intention is to make them available for inlining, and
then they get dropped. But specialization presumably mainly benefits the
out of line copy, I think? So I'm not sure that the approach of allowing
the specialization candidates to get imported will ultimately do what you
want. It probably would be better to allow the necessary info to be
propagated via the index back to the original TU so that it can be
specialized in its original location.

Agree with others that the solution should be prototyped so you can show
some results in terms of not only the benefit, but also the cost. I.e.
adding information about all of the function arguments will increase the
size of the index - how significant is that increase? We want to ensure
that the thin link portion of the ThinLTO build stays efficient as that is
the only monolithic, serial portion of a ThinLTO build. That being said, I
think it is a great idea to try to extend function specialization to
ThinLTO if it is giving good benefits with regular LTO.

Teresa

On Tue, Jul 27, 2021 at 5:56 AM Sjoerd Meijer via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> The motivation for this work was getting this working ThinLTO, which I
> know very little about that, so that's why I recommended getting buy in
> from ThinLTO folks for the general direction.
>
> This general direction is that we change the cost-model, import more
> functions as a result, so that we can do more transformations. The
> questions that need answering are: what is this going to cost in
> compile-times, and what is the performance benefit?
>
> To have a more efficient discussion on this, I think it is best if you
> prototype your proposal. This makes things more concrete and also allows to
> get some first costs and benefits of the approach to test the whole idea.
> Without this, it all just remains a bit abstract.
>
> Regarding https://reviews.llvm.org/D105524, yes it is NFC and harmless,
> but it is not important. I.e., it is trivial and I'm sure we can get it
> approved in no-time, but more important are the bigger questions that needs
> answers first. It's also better to avoid unnecessary churn if things
turns
> out to be different.
>
> My 2 cents.
> Sjoerd.
> ------------------------------
> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
> chuanqi.xcq via llvm-dev <llvm-dev at lists.llvm.org>
> *Sent:* 26 July 2021 07:30
> *To:* llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <
> florian_hahn at apple.com>
> *Subject:* Re: [llvm-dev] [ThinLTO] Import functions to enable function
> specialization in ThinLTO
>
> gentle ping~
>
> ------------------------------------------------------------------
> From:llvm-dev <llvm-dev at lists.llvm.org>
> Send Time:2021年7月15日(星期四) 17:23
> To:llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <
> florian_hahn at apple.com>
> Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
> specialization in ThinLTO
>
> Hi Florian,
>
> Thanks for looking into this!
>
> > I’d try to summarise the heuristics you propose to add, rather than
> focusing on the implementation details to start with.
>
> Thanks. I agree with it. The direction are more important than details.
>
> > You should also be able to collect and provide date on the
> effectiveness of those heuristics, like the number of additional functions
> imported, compared to the number of additionally specialised  functions.
>
> If I understand right, you mean that I could collect these numbers after
> we summarised the heuristics we decide to use instead of collecting now.
> Collecting the numbers may not make sense to me. Since I think we should
> do statistics after we decided the direction.
>
> > Also, the scope/focus on function specialisation seems a bit narrow
for
> substantially increasing the number of imported functions.
>
> I think there are two apsects.
> - It depends on how much we could get from function specialization.
> - It depends the cost model to import more functions.
>
> For the first aspects, I think function specialization is potential
> because ipa-cp plays an important role in gcc.
> And the interprocedural value range propogation based on function
> specialization seems very potential to me.
> That's the reason that I want to look into function specialization.
>
> For the second aspects, I think we need more time to tuning it. Or in
> another words, we need to decide the heuristics first.
> I know it's hard to **decide**  heuristics without measuring. But the
work
> process  I imaged maybe:
> ```
> Get a set of heuristics -> Tuning the cost model to decrease the
overhead
> -> if succed, we got it -> else go back to the first step.
> ```
>
> > Do you think the proposed heuristics would also benefit other
> optimisations, like regular IPSCCP?
>
> Yes, I think regular IPSCCP could benefit from the proposed heuristics.
> Out of curiousty, I guess we could replace regular IPSCCP
> once the function specialization pass is strong enough. What's your
> opinion?
>
> Finally, let me clarify the intention of this mail. I don't ask to get
a
> solution right now. I know it is hard for every one.
> The intention is that if we could get a consensus that it is valuable that
> importing functions by heuristics for function specialization.
> If yes, we could continue the review process for
> https://reviews.llvm.org/D105524, which extract the analysis part from
> function
> specialization pass. I believe this patch should be NFC and harmless.
>
> Of course, it could much much better that we could discuss the heuristics
> and the cost model.
> Let me introduce the heuristics and the cost model I proposed simply.
> The heuristics are:
>
>    - Specialize Function Cost. An unsigned number, which is an estimation
>    for the cost to clone one function.
>    - Base Bonus for specializing specific argument. A map from ArgNo to
>    the corresponding base bonus. Here the base bonus means the bonus we
could
>    calculate by visiting the function body itself only (in other words,
>    doesn't need to see the call site).
>    - ArgUsage. A map from ArgNo to the extra bonus for each call site.
>    The extra bonus means the bonus we could calculate for specific call
site.
>    For example, if we passed a function in the call, we could calculate the
>    possibility that the function could get inlined at the specific call
site
>    only.
>
> And the cost model are the same with function specialization pass right
> now and we could adjust it in the future.
> The first one `Specialize Function Cost` is the number of instruction in
> a function multiplies a factor.
> The second one `Base Bonus` is calculated by how many possible loads for
> this argument and its alias now.
> I plan to add more situations for example:
> ```
> int foo(bool cond) {
>    if (cond) { // We could get more base bonus by the average instruction
> count in the branches.
>    } else {
>    }
> }
> ```
> Or
> ```
> int foo(int cond) {
>    if (cond > 10) { // We could get the condition if cond is constant,
so
> we could get more bonus.
>    } else {
>    }
> }
> ```
> The third one `ArgUsage`, which describes the infomation in callsites and
> we could use it to calculate the extra bonus.
> Now it only contains the instruction count if the corresponding parameter
> is a function. Then we could get extra bonus
> from the potential inlining.
>
> Thanks,
> Chuanqi
>
> ------------------------------------------------------------------
> From:Florian Hahn <florian_hahn at apple.com>
> Send Time:2021年7月14日(星期三) 19:39
> To:chuanqi.xcq <yedeng.yd at linux.alibaba.com>; llvm-dev <
> llvm-dev at lists.llvm.org>
> Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
> specialization in ThinLTO
>
>
>
> On 14 Jul 2021, at 09:38, chuanqi.xcq via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hi all,
>
> Before I sent a mail to ask the opinion to how to import functions to
> enable function specialization in ThinLTO.
> Maybe the question is too empty or the function specialization pass
> didn't get checked in at that time. So I didn't get responses.
>
> Then now, the function specialization passes got checked in and I also
> made it a version in the downstream.
> So I tried to update my patches. The first patch is to extract the
> analysis part of function specialization as an analysis pass.
> (https://reviews.llvm.org/D105524).
>
> And @sjoerd.meijer suggests that it may be better that I ping this thread
> with more infomation to make us confident we are
> in the right direction.
>
> Then I updated this one: https://reviews.llvm.org/D105966, which contains
> the detailed description and numbers.
> Response in this thread or in that review page is fine to me either.
>
>
>
> I’d try to summarise the heuristics you propose to add, rather than
> focusing on the implementation details to start with. I think it might be
> helpful to motivate a set of heuristics first. You should also be able to
> collect and provide date on the effectiveness of those heuristics, like the
> number of additional functions imported, compared to the number of
> additionally specialised  functions.
>
> Also, the scope/focus on function specialisation seems a bit narrow for
> substantially increasing the number of imported functions. Do you think the
> proposed heuristics would also benefit other optimisations, like regular
> IPSCCP?
>
> Cheers,
> Florian
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

-- 
Teresa Johnson |  Software Engineer |  tejohnson at google.com |
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210727/3b6f5a25/attachment.html>

Sjoerd Meijer via llvm-dev

2021-Jul-28 10:56 UTC

head link

[llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO

Many thanks for commenting on the ThinLTO part and the suggestions how to
approach this!
I also think that specialisation benefits the out of line copy.

Cheers,
Sjoerd.
________________________________
From: Teresa Johnson <tejohnson at google.com>
Sent: 27 July 2021 16:00
To: Sjoerd Meijer <Sjoerd.Meijer at arm.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <florian_hahn
at apple.com>; chuanqi.xcq <yedeng.yd at linux.alibaba.com>
Subject: Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

I can answer questions from the ThinLTO standpoint. Missed the earlier emails on
this, but I just skimmed the other llvm-dev email and the patch. I have a high
level question and can give some thoughts on the approach from a ThinLTO
standpoint.

One important thing to note is that we import functions with
available_externally linkage, because they still live in their original
translation unit. The intention is to make them available for inlining, and then
they get dropped. But specialization presumably mainly benefits the out of line
copy, I think? So I'm not sure that the approach of allowing the
specialization candidates to get imported will ultimately do what you want. It
probably would be better to allow the necessary info to be propagated via the
index back to the original TU so that it can be specialized in its original
location.

Agree with others that the solution should be prototyped so you can show some
results in terms of not only the benefit, but also the cost. I.e. adding
information about all of the function arguments will increase the size of the
index - how significant is that increase? We want to ensure that the thin link
portion of the ThinLTO build stays efficient as that is the only monolithic,
serial portion of a ThinLTO build. That being said, I think it is a great idea
to try to extend function specialization to ThinLTO if it is giving good
benefits with regular LTO.

Teresa

On Tue, Jul 27, 2021 at 5:56 AM Sjoerd Meijer via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
The motivation for this work was getting this working ThinLTO, which I know very
little about that, so that's why I recommended getting buy in from ThinLTO
folks for the general direction.

This general direction is that we change the cost-model, import more functions
as a result, so that we can do more transformations. The questions that need
answering are: what is this going to cost in compile-times, and what is the
performance benefit?

To have a more efficient discussion on this, I think it is best if you prototype
your proposal. This makes things more concrete and also allows to get some first
costs and benefits of the approach to test the whole idea. Without this, it all
just remains a bit abstract.

Regarding https://reviews.llvm.org/D105524, yes it is NFC and harmless, but it
is not important. I.e., it is trivial and I'm sure we can get it approved in
no-time, but more important are the bigger questions that needs answers first.
It's also better to avoid unnecessary churn if things turns out to be
different.

My 2 cents.
Sjoerd.
________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> on behalf of chuanqi.xcq via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Sent: 26 July 2021 07:30
To: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Florian Hahn <florian_hahn at
apple.com<mailto:florian_hahn at apple.com>>
Subject: Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

gentle ping~
------------------------------------------------------------------
From:llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Send Time:2021年7月15日(星期四) 17:23
To:llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Florian Hahn <florian_hahn at
apple.com<mailto:florian_hahn at apple.com>>
Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

Hi Florian,

Thanks for looking into this!
> I’d try to summarise the heuristics you propose to add, rather than
focusing on the implementation details to start with.
Thanks. I agree with it. The direction are more important than details.
> You should also be able to collect and provide date on the effectiveness of
those heuristics, like the number of additional functions imported, compared to
the number of additionally specialised  functions.
If I understand right, you mean that I could collect these numbers after we
summarised the heuristics we decide to use instead of collecting now.
Collecting the numbers may not make sense to me. Since I think we should do
statistics after we decided the direction.
> Also, the scope/focus on function specialisation seems a bit narrow for
substantially increasing the number of imported functions.
I think there are two apsects.
- It depends on how much we could get from function specialization.
- It depends the cost model to import more functions.

For the first aspects, I think function specialization is potential because
ipa-cp plays an important role in gcc.
And the interprocedural value range propogation based on function specialization
seems very potential to me.
That's the reason that I want to look into function specialization.

For the second aspects, I think we need more time to tuning it. Or in another
words, we need to decide the heuristics first.
I know it's hard to **decide**  heuristics without measuring. But the work
process  I imaged maybe:
```
Get a set of heuristics -> Tuning the cost model to decrease the overhead
-> if succed, we got it -> else go back to the first step.
```
> Do you think the proposed heuristics would also benefit other
optimisations, like regular IPSCCP?
Yes, I think regular IPSCCP could benefit from the proposed heuristics. Out of
curiousty, I guess we could replace regular IPSCCP
once the function specialization pass is strong enough. What's your opinion?

Finally, let me clarify the intention of this mail. I don't ask to get a
solution right now. I know it is hard for every one.
The intention is that if we could get a consensus that it is valuable that
importing functions by heuristics for function specialization.
If yes, we could continue the review process for
https://reviews.llvm.org/D105524, which extract the analysis part from function
specialization pass. I believe this patch should be NFC and harmless.

Of course, it could much much better that we could discuss the heuristics and
the cost model.
Let me introduce the heuristics and the cost model I proposed simply.
The heuristics are:

  *   Specialize Function Cost. An unsigned number, which is an estimation for
the cost to clone one function.
  *   Base Bonus for specializing specific argument. A map from ArgNo to the
corresponding base bonus. Here the base bonus means the bonus we could calculate
by visiting the function body itself only (in other words, doesn't need to
see the call site).
  *   ArgUsage. A map from ArgNo to the extra bonus for each call site. The
extra bonus means the bonus we could calculate for specific call site. For
example, if we passed a function in the call, we could calculate the possibility
that the function could get inlined at the specific call site only.

And the cost model are the same with function specialization pass right now and
we could adjust it in the future.
The first one `Specialize Function Cost` is the number of instruction in a
function multiplies a factor.
The second one `Base Bonus` is calculated by how many possible loads for this
argument and its alias now.
I plan to add more situations for example:
```
int foo(bool cond) {
   if (cond) { // We could get more base bonus by the average instruction count
in the branches.
   } else {
   }
}
```
Or
```
int foo(int cond) {
   if (cond > 10) { // We could get the condition if cond is constant, so we
could get more bonus.
   } else {
   }
}
```
The third one `ArgUsage`, which describes the infomation in callsites and we
could use it to calculate the extra bonus.
Now it only contains the instruction count if the corresponding parameter is a
function. Then we could get extra bonus
from the potential inlining.

Thanks,
Chuanqi

------------------------------------------------------------------
From:Florian Hahn <florian_hahn at apple.com<mailto:florian_hahn at
apple.com>>
Send Time:2021年7月14日(星期三) 19:39
To:chuanqi.xcq <yedeng.yd at linux.alibaba.com<mailto:yedeng.yd at
linux.alibaba.com>>; llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

On 14 Jul 2021, at 09:38, chuanqi.xcq via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi all,

Before I sent a mail to ask the opinion to how to import functions to enable
function specialization in ThinLTO.
Maybe the question is too empty or the function specialization pass didn't
get checked in at that time. So I didn't get responses.

Then now, the function specialization passes got checked in and I also made it a
version in the downstream.
So I tried to update my patches. The first patch is to extract the analysis part
of function specialization as an analysis pass.
(https://reviews.llvm.org/D105524).

And @sjoerd.meijer suggests that it may be better that I ping this thread with
more infomation to make us confident we are
in the right direction.

Then I updated this one: https://reviews.llvm.org/D105966, which contains the
detailed description and numbers.
Response in this thread or in that review page is fine to me either.

I’d try to summarise the heuristics you propose to add, rather than focusing on
the implementation details to start with. I think it might be helpful to
motivate a set of heuristics first. You should also be able to collect and
provide date on the effectiveness of those heuristics, like the number of
additional functions imported, compared to the number of additionally
specialised  functions.

Also, the scope/focus on function specialisation seems a bit narrow for
substantially increasing the number of imported functions. Do you think the
proposed heuristics would also benefit other optimisations, like regular IPSCCP?

Cheers,
Florian

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
Teresa Johnson |         Software Engineer |     tejohnson at
google.com<mailto:tejohnson at google.com> |
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210728/e6808eac/attachment-0001.html>

chuanqi.xcq via llvm-dev

2021-Aug-12 04:00 UTC

head link

[llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO

Sorry for the late reply. Thanks everyone for looking into this!
> To Sjoerd Meijer:
>> This general direction is that we change the cost-model, import more
functions as a result, so that we can do more transformations. The questions
that need answering are: what is this going to cost in  compile-times, and what
is the performance benefit?
For the cost and beneift, I marked them in `https://reviews.llvm.org/D105966`.
Simply, for compile-time, there is no significant change except 502.gcc_r
increased 30%. For code-size, the average increasement is 6.7%. And the maximum
is 19%. For the performance benefit, the ThinLTO for function specialization
version gains all the benefit from FullLTO version.
Obiviously, the number are not so satisfying and this is the reason I marked
that patch as WIP. The things I want to say is:
- The increasement for compile-time and code-size mainly comes the newly
imported functions been specialized. Instead of calculating and storing the
extra heuristics.
- The main purpose of this mail is to make sure we are on the right direction.
In other words, ThinLTO for function specialization is pursued.
> To Sjoerd Meijer:
>> To have a more efficient discussion on this, I think it is best if you
prototype your proposal. This makes things more concrete and also allows to get
some first costs and benefits of the approach to test the whole idea. Without
this, it all just remains a bit abstract.
Yeah, I thought I made the proposal in D105524, D105966 and D107136.  Since the
codes for function specialization changes relatively fast. It may not be applied
directly. I would try to rebase it recently.
Another way to measure it is to `git reset --hard
d4840175c95f6edcba21baae411589468`.
> To Sjoerd Meijer:
>> Regarding https://reviews.llvm.org/D105524, yes it is NFC and harmless,
but it is not important. I.e., it is trivial and I'm sure we can get it
approved in no-time
The problem is that function specialization gets changed fast. So that this
patch couldn't be approved directly. It may be an extra cost. If we decide
the ThinLTO for function specialization is a long-term direction, we should
check it in first to avoid extra cost.
> To Teresa Johnson:
>> One important thing to note is that we import functions with
available_externally linkage, because they still live in their original
translation unit. The intention is to make them available for inlining, and then
they get dropped. But specialization presumably mainly benefits the out of line
copy, I think? So I'm not sure that the approach of allowing the
specialization candidates to get imported will ultimately do what you want.
For imported functions with available_externally linkage, the strategy now is
that if we decide to specialize it, we would copy the importanted function and
change the linkage for cloned to local so that it wouldn't affect other
translation unit. It looks fine to me.  Correct me if there is any problems.
Since linking is really magic.
> To Teresa Johnson:
>> It probably would be better to allow the necessary info to be
propagated via the index back to the original TU so that it can be specialized
in its original location.
It looks hard to do. I think the key point is that we make decision to
specialize functions in the process of ThinLTO compiling, which is pararrel to
other compilation unit. It looks like we need to do synchronization for ThinLTO,
which sounds like to violate the design principles for ThinLTO.
> To Teresa Johnson:
> Agree with others that the solution should be prototyped so you can show
some results in terms of not only the benefit, but also the cost. I.e. adding
information about all of the function arguments will increase the size of the
index - how significant is that increase? We want to ensure that the thin link
portion of the ThinLTO build stays efficient as that is the only monolithic,
serial portion of a ThinLTO build.
It's a great point to measure the size increased for index. I forget to
measure it before. Then here are the numbers for SPEC2017 int. The method I used
to measure the size for index is to compile the sizefor the `.o` objects
compiled by `-flto=thin`. Correct me if the measurement is not precise.
The results shows that for SPEC2017 intrate, the overall increased size is about
2.8%. More precisely,

| benchamrk       | size change for all the .o files |
|-----------------|--------|
| 500.perlbench_r | +1.9%  |
| 502.gcc_r       | +3.8%  |
| 505.mcf_r       | +3%    |
| 520.omnetpp_r | +12% |
| 525.x264_r | +2.9% |
| 531.deepsjeng_r | +1.4% |
| 541.leela_r | +2% |

The size changes less than 1% are omitted.
> To Teresa Johnson:
>> That being said, I think it is a great idea to try to extend function
specialization to ThinLTO if it is giving good benefits with regular LTO.
Thanks for your approval for the direction very much!

Thanks,
Chuanqi

------------------------------------------------------------------
From:Sjoerd Meijer <Sjoerd.Meijer at arm.com>
Send Time:2021年7月28日(星期三) 18:57
To:Teresa Johnson <tejohnson at google.com>
Cc:llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <florian_hahn at
apple.com>; chuanqi.xcq <yedeng.yd at linux.alibaba.com>
Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

 Many thanks for commenting on the ThinLTO part and the suggestions how to
approach this!
 I also think that specialisation benefits the out of line copy. 

 Cheers,
 Sjoerd.

From: Teresa Johnson <tejohnson at google.com>
Sent: 27 July 2021 16:00
To: Sjoerd Meijer <Sjoerd.Meijer at arm.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <florian_hahn
at apple.com>; chuanqi.xcq <yedeng.yd at linux.alibaba.com>
Subject: Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO
I can answer questions from the ThinLTO standpoint. Missed the earlier emails on
this, but I just skimmed the other llvm-dev email and the patch. I have a high
level question and can give some thoughts on the approach from a ThinLTO
standpoint.

One important thing to note is that we import functions with
available_externally linkage, because they still live in their original
translation unit. The intention is to make them available for inlining, and then
they get dropped. But specialization presumably mainly benefits the out of line
copy, I think? So I'm not sure that the approach of allowing the
specialization candidates to get imported will ultimately do what you want. It
probably would be better to allow the necessary info to be propagated via the
index back to the original TU so that it can be specialized in its original
location.

Agree with others that the solution should be prototyped so you can show some
results in terms of not only the benefit, but also the cost. I.e. adding
information about all of the function arguments will increase the size of the
index - how significant is that increase? We want to ensure that the thin link
portion of the ThinLTO build stays efficient as that is the only monolithic,
serial portion of a ThinLTO build. That being said, I think it is a great idea
to try to extend function specialization to ThinLTO if it is giving good
benefits with regular LTO.

Teresa
On Tue, Jul 27, 2021 at 5:56 AM Sjoerd Meijer via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
 The motivation for this work was getting this working ThinLTO, which I know
very little about that, so that's why I recommended getting buy in from
ThinLTO folks for the general direction.

 This general direction is that we change the cost-model, import more functions
as a result, so that we can do more transformations. The questions that need
answering are: what is this going to cost in compile-times, and what is the
performance benefit?

 To have a more efficient discussion on this, I think it is best if you
prototype your proposal. This makes things more concrete and also allows to get
some first costs and benefits of the approach to test the whole idea. Without
this, it all just remains a bit abstract.

Regarding https://reviews.llvm.org/D105524, yes it is NFC and harmless, but it
is not important. I.e., it is trivial and I'm sure we can get it approved in
no-time, but more important are the bigger questions that needs answers first.
It's also better to avoid unnecessary churn if things turns out to be
different.

My 2 cents.
Sjoerd.

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
chuanqi.xcq via llvm-dev <llvm-dev at lists.llvm.org>
Sent: 26 July 2021 07:30
To: llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <florian_hahn
at apple.com>
Subject: Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO
gentle ping~
------------------------------------------------------------------
From:llvm-dev <llvm-dev at lists.llvm.org>
Send Time:2021年7月15日(星期四) 17:23
To:llvm-dev <llvm-dev at lists.llvm.org>; Florian Hahn <florian_hahn at
apple.com>
Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

Hi Florian,

Thanks for looking into this!
> I’d try to summarise the heuristics you propose to add, rather than
focusing on the implementation details to start with.
Thanks. I agree with it. The direction are more important than details.
> You should also be able to collect and provide date on the effectiveness of
those heuristics, like the number of additional functions imported, compared to
the number of additionally specialised  functions.
If I understand right, you mean that I could collect these numbers after we
summarised the heuristics we decide to use instead of collecting now.
Collecting the numbers may not make sense to me. Since I think we should do
statistics after we decided the direction.
> Also, the scope/focus on function specialisation seems a bit narrow for
substantially increasing the number of imported functions.
I think there are two apsects.
- It depends on how much we could get from function specialization.
- It depends the cost model to import more functions.

For the first aspects, I think function specialization is potential because
ipa-cp plays an important role in gcc.
And the interprocedural value range propogation based on function specialization
seems very potential to me.
That's the reason that I want to look into function specialization.

For the second aspects, I think we need more time to tuning it. Or in another
words, we need to decide the heuristics first.
I know it's hard to **decide**  heuristics without measuring. But the work
process  I imaged maybe:
```
Get a set of heuristics -> Tuning the cost model to decrease the overhead
-> if succed, we got it -> else go back to the first step.
```
> Do you think the proposed heuristics would also benefit other
optimisations, like regular IPSCCP?
Yes, I think regular IPSCCP could benefit from the proposed heuristics. Out of
curiousty, I guess we could replace regular IPSCCP
once the function specialization pass is strong enough. What's your opinion?

Finally, let me clarify the intention of this mail. I don't ask to get a
solution right now. I know it is hard for every one.
The intention is that if we could get a consensus that it is valuable that
importing functions by heuristics for function specialization.
If yes, we could continue the review process for
https://reviews.llvm.org/D105524, which extract the analysis part from function
specialization pass. I believe this patch should be NFC and harmless.

Of course, it could much much better that we could discuss the heuristics and
the cost model.
Let me introduce the heuristics and the cost model I proposed simply.
The heuristics are:

Specialize Function Cost. An unsigned number, which is an estimation for the
cost to clone one function.
Base Bonus for specializing specific argument. A map from ArgNo to the
corresponding base bonus. Here the base bonus means the bonus we could calculate
by visiting the function body itself only (in other words, doesn't need to
see the call site).
ArgUsage. A map from ArgNo to the extra bonus for each call site. The extra
bonus means the bonus we could calculate for specific call site. For example, if
we passed a function in the call, we could calculate the possibility that the
function could get inlined at the specific call site only.
And the cost model are the same with function specialization pass right now and
we could adjust it in the future.
The first one `Specialize Function Cost` is the number of instruction in a
function multiplies a factor.
The second one `Base Bonus` is calculated by how many possible loads for this
argument and its alias now.
I plan to add more situations for example:
```
int foo(bool cond) {
   if (cond) { // We could get more base bonus by the average instruction count
in the branches.
   } else {
   }
}
```
Or
```
int foo(int cond) {
   if (cond > 10) { // We could get the condition if cond is constant, so we
could get more bonus.
   } else {
   }
}
```
The third one `ArgUsage`, which describes the infomation in callsites and we
could use it to calculate the extra bonus.
Now it only contains the instruction count if the corresponding parameter is a
function. Then we could get extra bonus
from the potential inlining.

Thanks,
Chuanqi

------------------------------------------------------------------
From:Florian Hahn <florian_hahn at apple.com>
Send Time:2021年7月14日(星期三) 19:39
To:chuanqi.xcq <yedeng.yd at linux.alibaba.com>; llvm-dev <llvm-dev at
lists.llvm.org>
Subject:Re: [llvm-dev] [ThinLTO] Import functions to enable function
specialization in ThinLTO

On 14 Jul 2021, at 09:38, chuanqi.xcq via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
Hi all,

Before I sent a mail to ask the opinion to how to import functions to enable
function specialization in ThinLTO.
Maybe the question is too empty or the function specialization pass didn't
get checked in at that time. So I didn't get responses.

Then now, the function specialization passes got checked in and I also made it a
version in the downstream.
So I tried to update my patches. The first patch is to extract the analysis part
of function specialization as an analysis pass.
(https://reviews.llvm.org/D105524).

And  @sjoerd.meijer suggests that it may be better that I ping this thread with
more infomation to make us confident we are
in the right direction.

Then I updated this one: https://reviews.llvm.org/D105966, which contains the
detailed description and numbers.
Response in this thread or in that review page is fine to me either.

I’d try to summarise the heuristics you propose to add, rather than focusing on
the implementation details to start with. I think it might be helpful to
motivate a set of heuristics first. You should also be able to collect and
provide date on the effectiveness of those heuristics, like the number of
additional functions imported, compared to the number of additionally
specialised  functions.

Also, the scope/focus on function specialisation seems a bit narrow for
substantially increasing the number of imported functions. Do you think the
proposed heuristics would also benefit other optimisations, like regular IPSCCP?

Cheers,
Florian

 _______________________________________________
 LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

 -- 

	Teresa Johnson |	 Software Engineer |	tejohnson at google.com |	

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210812/d6662d91/attachment-0001.html>

llvm dev - Aug 2021 - [ThinLTO] Import functions to enable function specialization in ThinLTO

[llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO

[llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO

[llvm-dev] [ThinLTO] Import functions to enable function specialization in ThinLTO