llvm dev - Aug 2018 - Regarding basic block layout/code placement optimizations of profile guided optimization (PGO)

Hi,

I would like to learn the details regarding what exactly PGO does for basic
block layout/code placement optimizations in llvm. Could you please point
me to some descriptions? Is it close to this paper (Karl Pettis and Robert
C. Hansen. 1990. Profile guided code positioning.  PLDI'90)
http://perso.ensta-paristech.fr/~bmonsuez/Cours/B6-4/Articles/papers15.pdf?
Whether it is purely intra-procedural or include inter-procedural
optimizations?

Thank you so much!

Best regards,
Xiaowan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180807/8107df7a/attachment.html>

On Tue, Aug 7, 2018 at 11:53 AM Xiaowan Dong via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi,
>
> I would like to learn the details regarding what exactly PGO does for basic
block layout/code placement optimizations in llvm. Could you please point me to
some descriptions? Is it close to this paper (Karl Pettis and Robert C. Hansen.
1990. Profile guided code positioning.  PLDI'90)
http://perso.ensta-paristech.fr/~bmonsuez/Cours/B6-4/Articles/papers15.pdf?
Whether it is purely intra-procedural or include inter-procedural optimizations?
>
> Thank you so much!
>
lld implements C^3 which is basically a variation of Pettis-Hansen.
The CGO 17 paper describes the approach with a great level of detail
https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf?
(the algorithm per-se is fairly straightforward).
Pointers to the code at https://reviews.llvm.org/D36351
You can also find the details in Michael's original RFC
http://lists.llvm.org/pipermail/llvm-dev/2017-June/114178.html

There's also a pass in the backend (codegen) to perform profile-driven
Machine BB placement (CodeGen/MachineBlockPlacement.cpp).

--
Davide

Thank you so much for your prompt reply, Davide!

On Tue, Aug 7, 2018 at 5:14 PM, Davide Italiano <davide at freebsd.org>
wrote:
> On Tue, Aug 7, 2018 at 11:53 AM Xiaowan Dong via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> > Hi,
> >
> > I would like to learn the details regarding what exactly PGO does for
> basic block layout/code placement optimizations in llvm. Could you please
> point me to some descriptions? Is it close to this paper (Karl Pettis and
> Robert C. Hansen. 1990. Profile guided code positioning.  PLDI'90)
> https://urldefense.proofpoint.com/v2/url?u=http-3A__perso.
>
ensta-2Dparistech.fr_-7Ebmonsuez_Cours_B6-2D4_Articles_papers15.pdf-3F&d>
DwIFaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r>
9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=Hbba3m9Gul1G8YndUAW1N9qQpS3nHs
> 9DA7c0CJVNebg&e= Whether it is purely intra-procedural or include
> inter-procedural optimizations?
> >
> > Thank you so much!
> >
>
> lld implements C^3 which is basically a variation of Pettis-Hansen.
> The CGO 17 paper describes the approach with a great level of detail
> https://urldefense.proofpoint.com/v2/url?u=https-3A__
> research.fb.com_wp-2Dcontent_uploads_2017_01_cgo2017-
> 2Dhfsort-2Dfinal1.pdf-3F&d=DwIFaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9
>
EI2eaqQZhHbOU&r=9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=pIdMmcvpHh75XIH29J98lMchoSRMHF
> 4PjYjsw5fWV2c&e> (the algorithm per-se is fairly straightforward).
> Pointers to the code at https://urldefense.proofpoint.
> com/v2/url?u=https-3A__reviews.llvm.org_D36351&d=DwIFaQ&c>
kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r>
9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=zyCFsKdWzhdEH2AAV0y8itEL3f3MCq
> _97koJeZEBsGY&e> You can also find the details in Michael's
original RFC
> https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.
>
llvm.org_pipermail_llvm-2Ddev_2017-2DJune_114178.html&d=DwIFaQ&c>
kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r>
9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=DGrA_unYXo8wrHhtd-
> cK2GiyQOfsYqvIz016-wcV4iU&e>
> There's also a pass in the backend (codegen) to perform profile-driven
> Machine BB placement (CodeGen/MachineBlockPlacement.cpp).
>
> --
> Davide
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180807/e4ac4656/attachment.html>

Dear Davide,

We noticed that C^3 will only be available for the upcoming versions of
LLVM. I was wondering what it is like in LLVM 6.0.1?

Thank you so much!

Best regards,
Xiaowan

On Tue, Aug 7, 2018 at 5:14 PM, Davide Italiano <davide at freebsd.org>
wrote:
> On Tue, Aug 7, 2018 at 11:53 AM Xiaowan Dong via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> > Hi,
> >
> > I would like to learn the details regarding what exactly PGO does for
> basic block layout/code placement optimizations in llvm. Could you please
> point me to some descriptions? Is it close to this paper (Karl Pettis and
> Robert C. Hansen. 1990. Profile guided code positioning.  PLDI'90)
> https://urldefense.proofpoint.com/v2/url?u=http-3A__perso.
>
ensta-2Dparistech.fr_-7Ebmonsuez_Cours_B6-2D4_Articles_papers15.pdf-3F&d>
DwIFaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r>
9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=Hbba3m9Gul1G8YndUAW1N9qQpS3nHs
> 9DA7c0CJVNebg&e= Whether it is purely intra-procedural or include
> inter-procedural optimizations?
> >
> > Thank you so much!
> >
>
> lld implements C^3 which is basically a variation of Pettis-Hansen.
> The CGO 17 paper describes the approach with a great level of detail
> https://urldefense.proofpoint.com/v2/url?u=https-3A__
> research.fb.com_wp-2Dcontent_uploads_2017_01_cgo2017-
> 2Dhfsort-2Dfinal1.pdf-3F&d=DwIFaQ&c=kbmfwr1Yojg42sGEpaQh5ofMHBeTl9
>
EI2eaqQZhHbOU&r=9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=pIdMmcvpHh75XIH29J98lMchoSRMHF
> 4PjYjsw5fWV2c&e> (the algorithm per-se is fairly straightforward).
> Pointers to the code at https://urldefense.proofpoint.
> com/v2/url?u=https-3A__reviews.llvm.org_D36351&d=DwIFaQ&c>
kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r>
9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=zyCFsKdWzhdEH2AAV0y8itEL3f3MCq
> _97koJeZEBsGY&e> You can also find the details in Michael's
original RFC
> https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.
>
llvm.org_pipermail_llvm-2Ddev_2017-2DJune_114178.html&d=DwIFaQ&c>
kbmfwr1Yojg42sGEpaQh5ofMHBeTl9EI2eaqQZhHbOU&r>
9lVsUv0m4rDQCgSupIkpgbizkVWsSr2-oDgbaUgY_C0&m=YPozo_Hjjg-
> 5VCjvXCWDF1LsHc3pKWNWySkv3nXqSFc&s=DGrA_unYXo8wrHhtd-
> cK2GiyQOfsYqvIz016-wcV4iU&e>
> There's also a pass in the backend (codegen) to perform profile-driven
> Machine BB placement (CodeGen/MachineBlockPlacement.cpp).
>
> --
> Davide
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180809/99031ddc/attachment.html>