llvm dev - Jul 2021 - [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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210714/92e3e7de/attachment.html>

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

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