[GSoC] Improve inlining using inter-procedural analysis or profile

Project Infrastructure LLVM Dev List Archives
1

To Whom it May Concern,

I am Liqiang Tao, a graduate student in the Graduate School of Arts and Sciences of the University of Tokyo.

First, I would like to talk about my interests here. When I saw the Open Projects page, I was attracted by this area.

Moreover, we want to explore the case that is helpful to group strongly related functions together and optimize them as a group instead of displaying them individually. I consider whether it is possible to inline some related methods to improve performance.

Then I found a paper[1]. In this paper, the methods are inlined by clusters rather than individuals. The profile and IR size are applied to decide inline or not. I also noticed that the profile directed inlining, as a todo item, also appears in the Open Projects page. It might be a nice start, right?

Besides, if possible, I am also interested in applying inter-procedural analysis or static analysis to guide inlining. Unfortunately, I didn’t find any paper about this idea. Could you please provide me with some suggestions about this? Is there any process related to these ideas in LLVM?

As for my background relevant to this project:

  • I am participating in porting V8 to RISC-V from July, 2020.
    https://github.com/v8-riscv/v8
  • Recently, I began learning the inliner code in LLVM. And I also tried to create my own pass to be familiar with LLVM infrastructure.

Looking forward to more discussions,

Best Wishes,
Liqiang Tao

[1] An Optimization-Driven Incremental Inline Substitution Algorithm for Just-In-Time Compilers
https://dl.acm.org/doi/10.5555/3314872.3314893

2

Hi Liqiang,

Here are some papers that may be loosely related to the problem you described, without any particular order:

  1. Automatic construction of inlining heuristics using machine learning, Sameer Kulkarni et al., 2013 https://dl.acm.org/doi/10.1109/CGO.2013.6495004
  2. Adaptive online context-sensitive inlining, Kim Hazelwood, David Grove, 2003 http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/hazelwood-cgo03.pdf
  3. An Adaptive Strategy for Inline Substitution, Keith Cooper et al., 2008 https://link.springer.com/chapter/10.1007/978-3-540-78791-4_5
  4. Automatic Tuning of Inlining Heuristics, John Cavazos, Michael F.P. O’Boyle, 2005 https://www.eecis.udel.edu/~cavazos/cpc-2006.pdf
  5. Towards Better Inlining Decisions Using Inlining Trials, Jeffrey Dean, Craig Chambers, 1994 https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.1043&rep=rep1&type=pdf
  6. Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling, Glenn Ammons et al., 1997 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.2010
  7. Boosting Inlining Heuristics, Nuno Lopes, 2010 https://web.ist.utl.pt/nuno.lopes/pubs/inline-stats10.pdf

-Jakub

3

Hi Liqiang,

Jakub’s recommendations are great and they reminded me of one of the talks we gave in the last LLVM conf: https://youtu.be/I4Iv-HefknA?t=1081
In this part about inlining, in the end I have a “further reading” section that you might find interesting (note that slides are available in the YT comments).
Some of the papers that Jakub mentioned are there and some more that you may find useful.

Hopefully, the rest of the part will help you understand LLVM’s inlining a little better too. Unfortunately, when I was preparing this part, a lot of content had to be thrown
out as the part ended up being a talk by itself. The reason I’m mentioning that is to motivate you to please ask questions if you want! There is a lot of content

about inlining in LLVM that has not been presented anywhere and although I’m no expert on inlining, I’ll try to help. And I hope the rest of the community will do too.

Best,
Stefanos

Στις Δευ, 8 Φεβ 2021 στις 9:58 μ.μ., ο/η Jakub (Kuba) Kuderski via llvm-dev <llvm-dev@lists.llvm.org> έγραψε:

4

Hi Liqiang,

Jakub’s recommendations are great and they reminded me of one of the talks we gave in the last LLVM conf: https://youtu.be/I4Iv-HefknA?t=1081
In this part about inlining, in the end I have a “further reading” section that you might find interesting (note that slides are available in the YT comments).
Some of the papers that Jakub mentioned are there and some more that you may find useful.

Hopefully, the rest of the part will help you understand LLVM’s inlining a little better too. Unfortunately, when I was preparing this part, a lot of content had to be thrown
out as the part ended up being a talk by itself. The reason I’m mentioning that is to motivate you to please ask questions if you want! There is a lot of content

about inlining in LLVM that has not been presented anywhere and although I’m no expert on inlining, I’ll try to help. And I hope the rest of the community will do too.

Best,
Stefanos

Στις Δευ, 8 Φεβ 2021 στις 9:58 μ.μ., ο/η Jakub (Kuba) Kuderski via llvm-dev <llvm-dev@lists.llvm.org> έγραψε:

Hi Liqiang,

Here are some papers that may be loosely related to the problem you described, without any particular order:

  1. Automatic construction of inlining heuristics using machine learning, Sameer Kulkarni et al., 2013 https://dl.acm.org/doi/10.1109/CGO.2013.6495004
  2. Adaptive online context-sensitive inlining, Kim Hazelwood, David Grove, 2003 http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/hazelwood-cgo03.pdf
  3. An Adaptive Strategy for Inline Substitution, Keith Cooper et al., 2008 https://link.springer.com/chapter/10.1007/978-3-540-78791-4_5
  4. Automatic Tuning of Inlining Heuristics, John Cavazos, Michael F.P. O’Boyle, 2005 https://www.eecis.udel.edu/~cavazos/cpc-2006.pdf
  5. Towards Better Inlining Decisions Using Inlining Trials, Jeffrey Dean, Craig Chambers, 1994 https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.1043&rep=rep1&type=pdf
  6. Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling, Glenn Ammons et al., 1997 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.2010
  7. Boosting Inlining Heuristics, Nuno Lopes, 2010 https://web.ist.utl.pt/nuno.lopes/pubs/inline-stats10.pdf

-Jakub

To Whom it May Concern,

I am Liqiang Tao, a graduate student in the Graduate School of Arts and Sciences of the University of Tokyo.

First, I would like to talk about my interests here. When I saw the Open Projects page, I was attracted by this area.

Moreover, we want to explore the case that is helpful to group strongly related functions together and optimize them as a group instead of displaying them individually. I consider whether it is possible to inline some related methods to improve performance.

Then I found a paper[1]. In this paper, the methods are inlined by clusters rather than individuals. The profile and IR size are applied to decide inline or not. I also noticed that the profile directed inlining, as a todo item, also appears in the Open Projects page. It might be a nice start, right?

(Not sure I follow) could you link the Open Projects page? Asking because the LLVM inliner is profile - driven (hence my confusion)

Besides, if possible, I am also interested in applying inter-procedural analysis or static analysis to guide inlining. Unfortunately, I didn’t find any paper about this idea. Could you please provide me with some suggestions about this? Is there any process related to these ideas in LLVM?

In some sense, today’s inliner does perform some inter-procedural analysis (other than the caller/callee of the call site being probed) - see the “shouldInline” method in lib/Analysis/InlineAdvisor.cpp. One possibility would be to extend the subgraph analyzed there.