[LLVM][LTO][LLD] Enable Profile Guided Layout (--call-graph-profile-sort) for FullLTO

[bd1976llvm]

Summary

The CGProfilePass needs to be run during FullLTO compilation at link time to emit the .llvm.call-graph-profile section to the compiled LTO object file. Currently, it is being run only during the initial LTO-prelink compilation stage (to produce the bitcode files to be consumed by the linker) and so the section is not produced.

ThinLTO is not affected because:

• For ThinLTO-prelink compilation the CGProfilePass pass is not run because ThinLTO-prelink passes are added via buildThinLTOPreLinkDefaultPipeline. Normal and FullLTO-prelink passes are both added via buildPerModuleDefaultPipeline which uses the LTOPreLink parameter to customise its behaviour for the FullLTO-prelink pass differences.
• ThinLTO backend compilation phase adds the CGProfilePass (see: buildModuleOptimizationPipeline).

Adjust when the pass is run so that the .llvm.call-graph-profile section is produced correctly for FullLTO.

Fixes #56185

[nikic]

(Not familiar with CGProfilePass and its requirements)

[bd1976llvm]

In D128452#3607209, @nikic wrote:

(Not familiar with CGProfilePass and its requirements)

This change should be relatively simple to understand with a bit more background: For Profile Guided Layout (PGL) the compiler must emit the .llvm.call-graph-profile (SHT_LLVM_CALL_GRAPH_PROFILE) section to the ELF object file that LLD consumes. To do this the CGProfilePass attaches additional metadata recording the weighted call-graph, which is later lowered to the .llvm.call-graph-profile ELF section contents. This currently works for normal compilation and ThinLTO; however, for FullLTO the pass is currently run in the pre-link stage so the weighted callgraph metadata is present in the bitcode input to LLD. Since the metadata is attached too early it does not survive LTO compilation to lowering and the .llvm.call-graph-profile section is not present in the LTO object file. In this change we make the CGProfilePass run at the right point during the LTO object file compilation so that the LTO object file contains the .llvm.call-graph-profile section which LLD can consume to drive PGL.

More background in this talk: https://youtu.be/F-lbgspxv1c

LTO object file = ELF object file created by compiling the bitcode inputs at link time.

[bd1976llvm]

Added some reviewer from D112160 where PGL has recently been made to work for macho LLD. It seems likely (to me!) that macho is also affected by this issue.

[MaskRay]

Please expand uncommon abbreviations: PGL, FLTO, and TLTO.

TLTO is not affected as the passes are added (correctly) via a different path

Be more precise about why ThinLTO is unaffected: buildModuleOptimizationPipeline called by it runs CGProfilePass.
Also mention the LTOPreLink change for ThinLTOPreLink.

llvm/lib/Passes/PassBuilderPipelines.cpp

1273–1274

Perhaps move after GlobalDCEPass/ConstantMergePass similar to buildLTODefaultPipeline.

GlobalDCEPass may discard some functions and these functions don't need to run CGProfilePass. Though the speed-up is almost assuredly negligible.

[MaskRay]

llvm/test/Other/new-pm-defaults.ll

12

CHECK-CGPP isn't clear. Clarify it. Possibly add a comment explaining what it does.

[bd1976llvm]

Addressed review comments.

Also the description and earlier comments have now been expanded and unappreciated acronyms have been removed.

[MaskRay]

Thanks for the updated summary.

https://github.com/llvm/llvm-project/issues/56185

You can use Fix(es)? https://github.com/llvm/llvm-project/issues/56185 (or #56185) so that the pushed commit will close the issue automatically.

Since the body mentions the issue, you can remove (PR #56185) from the subject.

ThinLTO compilation at link time adds the CGProfilePass (see: buildModuleOptimizationPipeline).

at link time is incorrect for distributed ThinLTO which happens at clang -fthinlto-index=... time. You may just say "ThinLTO backend compilation phase"

[bd1976llvm]

llvm/lib/Passes/PassBuilderPipelines.cpp

1273–1274

Seems like a reasonable improvement. It seems to work with the programs I tried it on locally. Thanks!

llvm/test/Other/new-pm-defaults.ll

12

I noticed that I can just use CHECK-DEFAULT (as is used for the similar "RelLookupTableConverterPass" pass) :)

[bd1976llvm]

In D128452#3623184, @MaskRay wrote:

at link time is incorrect for distributed ThinLTO which happens at clang -fthinlto-index=... time. You may just say "ThinLTO backend compilation phase"

Thanks for spotting that. I have adopted your suggestion.

[bd1976llvm]

Committed in: https://github.com/llvm/llvm-project/commit/325e7e8b87423f83ba9fc53b9486ce67329d486c.

clang/test/CodeGen/thinlto-distributed-newpm.ll

 ; CHECK-O: Running pass: LoopSimplifyPass on main
 ; CHECK-O: Running pass: LCSSAPass on main
 ; CHECK-O: Running pass: LICMPass on Loop at depth 1 containing: %b
 ; CHECK-O: Running pass: AlignmentFromAssumptionsPass on main
 ; CHECK-O: Running pass: LoopSinkPass on main
 ; CHECK-O: Running pass: InstSimplifyPass on main
 ; CHECK-O: Running pass: DivRemPairsPass on main
 ; CHECK-O: Running pass: SimplifyCFGPass on main
-; CHECK-O: Running pass: CGProfilePass
 ; CHECK-O: Running pass: GlobalDCEPass
 ; CHECK-O: Running pass: ConstantMergePass
+; CHECK-O: Running pass: CGProfilePass
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-grtev4-linux-gnu"
 
 define i32 @main() {
   br label %b
 b:
   br label %b
   ret i32 0
 }

llvm/lib/Passes/PassBuilderPipelines.cpp

PassBuilder::buildModuleOptimizationPipeline(OptimizationLevel Level,
   // the size of the program, we extract the regions, a deduplicate the
   // structurally similar regions.
   if (EnableIROutliner)
     MPM.addPass(IROutlinerPass());
 
   // Merge functions if requested.
   if (PTO.MergeFunctions)
     MPM.addPass(MergeFunctionsPass());
 
-  if (PTO.CallGraphProfile)
-    MPM.addPass(CGProfilePass());
-
   // Now we need to do some global optimization transforms.
   // FIXME: It would seem like these should come first in the optimization
   // pipeline and maybe be the bottom of the canonicalization pipeline? Weird
   // ordering here.
   MPM.addPass(GlobalDCEPass());
   MPM.addPass(ConstantMergePass());
 
+  if (PTO.CallGraphProfile && !LTOPreLink)
+    MPM.addPass(CGProfilePass());
+
   // TODO: Relative look table converter pass caused an issue when full lto is
   // enabled. See https://reviews.llvm.org/D94355 for more details.
   // Until the issue fixed, disable this pass during pre-linking phase.
   if (!LTOPreLink)
     MPM.addPass(RelLookupTableConverterPass());
 
   return MPM;
 }
PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level,
   MPM.addPass(EliminateAvailableExternallyPass());
 
   // Now that we have optimized the program, discard unreachable functions.
   MPM.addPass(GlobalDCEPass());
 
   if (PTO.MergeFunctions)
     MPM.addPass(MergeFunctionsPass());
 
+  if (PTO.CallGraphProfile)
+    MPM.addPass(CGProfilePass());
+
   for (auto &C : FullLinkTimeOptimizationLastEPCallbacks)
     C(MPM, Level);
 
   // Emit annotation remarks.
   addAnnotationRemarksPass(MPM);
 
   return MPM;
 }

llvm/test/Other/new-pm-defaults.ll

 ; The IR below was crafted so as:
 ; 1) To have a loop, so we create a loop pass manager
 ; 2) To be "immutable" in the sense that no pass in the standard
 ;    pipeline will modify it.
 ; Since no transformations take place, we don't expect any analyses
 ; to be invalidated.
 ; Any invalidation that shows up here is a bug, unless we started modifying
 ; the IR, in which case we need to make it immutable harder.
 
 ; RUN: opt -disable-verify -verify-cfg-preserved=0 -eagerly-invalidate-analyses=0 -debug-pass-manager \
 ; RUN:     -passes='default<O1>' -S %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK-O,CHECK-DEFAULT,CHECK-O1,%llvmcheckext
 ; RUN: opt -disable-verify -verify-cfg-preserved=0 -eagerly-invalidate-analyses=0 -debug-pass-manager \
 ; RUN:     -passes='default<O2>' -S  %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK-O,CHECK-DEFAULT,CHECK-O2,CHECK-O23SZ,%llvmcheckext
 ; RUN: opt -disable-verify -verify-cfg-preserved=0 -eagerly-invalidate-analyses=0 -debug-pass-manager \
 ; RUN:     -passes='default<O3>' -S  %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK-O,CHECK-DEFAULT,CHECK-O3,CHECK-O23SZ,%llvmcheckext
 ; RUN: opt -disable-verify -verify-cfg-preserved=0 -eagerly-invalidate-analyses=0 -debug-pass-manager \
 ; RUN:     -passes='default<Os>' -S %s 2>&1 \

 ; CHECK-O-NEXT: Running pass: InstSimplifyPass
 ; CHECK-O-NEXT: Running pass: DivRemPairsPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-EP-OPTIMIZER-LAST: Running pass: NoOpModulePass
 ; CHECK-HOT-COLD-SPLIT-NEXT: Running pass: HotColdSplittingPass
 ; CHECK-IR-OUTLINER-NEXT: Running pass: IROutlinerPass
 ; CHECK-IR-OUTLINER-NEXT: Running analysis: IRSimilarityAnalysis
 ; CHECK-MERGE-FUNCS-NEXT: Running pass: MergeFunctionsPass
-; CHECK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-O-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O-NEXT: Running pass: ConstantMergePass
+; CHECK-DEFAULT-NEXT: Running pass: CGProfilePass
 ; CHECK-DEFAULT-NEXT: Running pass: RelLookupTableConverterPass
 ; CHECK-LTO-NOT: Running pass: RelLookupTableConverterPass
 ; CHECK-O-NEXT: Running pass: AnnotationRemarksPass on foo
 ; CHECK-LTO-NEXT: Running pass: CanonicalizeAliasesPass
 ; CHECK-LTO-NEXT: Running pass: NameAnonGlobalPass
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 ;
 ; Make sure we get the IR back out without changes when we print the module.

llvm/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O23SZ-NEXT: Running pass: InstCombinePass on foo
 ; CHECK-EP-Peephole-NEXT: Running pass: NoOpFunctionPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O23SZ-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O23SZ-NEXT: Running pass: EliminateAvailableExternallyPass
 ; CHECK-O23SZ-NEXT: Running pass: GlobalDCEPass
+; CHECK-O23SZ-NEXT: Running pass: CGProfilePass
 ; CHECK-EP-NEXT: Running pass: NoOpModulePass
 ; CHECK-O-NEXT: Running pass: AnnotationRemarksPass on foo
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr {
 ; CHECK-O-NEXT: entry:
 ; CHECK-O-NEXT:   br label %loop

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-POSTLINK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: LICMPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: AlignmentFromAssumptionsPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: LoopSinkPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: InstSimplifyPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: DivRemPairsPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: SimplifyCFGPass
-; CHECK-POSTLINK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-POSTLINK-O-NEXT: Running pass: GlobalDCEPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: ConstantMergePass
+; CHECK-POSTLINK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-POSTLINK-O-NEXT: Running pass: RelLookupTableConverterPass
 ; CHECK-O-NEXT:          Running pass: AnnotationRemarksPass on foo
 ; CHECK-PRELINK-O-NEXT: Running pass: CanonicalizeAliasesPass
 ; CHECK-PRELINK-O-NEXT: Running pass: NameAnonGlobalPass
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr {

llvm/test/Other/new-pm-thinlto-postlink-pgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running pass: LICMPass
 ; CHECK-O-NEXT: Running pass: AlignmentFromAssumptionsPass
 ; CHECK-O-NEXT: Running pass: LoopSinkPass
 ; CHECK-O-NEXT: Running pass: InstSimplifyPass
 ; CHECK-O-NEXT: Running pass: DivRemPairsPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
-; CHECK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-O-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O-NEXT: Running pass: ConstantMergePass
+; CHECK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-O-NEXT: Running pass: RelLookupTableConverterPass
 ; CHECK-O-NEXT: Running pass: AnnotationRemarksPass on foo
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr {
 ; CHECK-O-NEXT: entry:
 ; CHECK-O-NEXT:   br label %loop

llvm/test/Other/new-pm-thinlto-postlink-samplepgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running pass: LICMPass
 ; CHECK-O-NEXT: Running pass: AlignmentFromAssumptionsPass
 ; CHECK-O-NEXT: Running pass: LoopSinkPass
 ; CHECK-O-NEXT: Running pass: InstSimplifyPass
 ; CHECK-O-NEXT: Running pass: DivRemPairsPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
-; CHECK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-O-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O-NEXT: Running pass: ConstantMergePass
+; CHECK-O-NEXT: Running pass: CGProfilePass
 ; CHECK-O-NEXT: Running pass: RelLookupTableConverterPass
 ; CHECK-O-NEXT: Running pass: AnnotationRemarksPass on foo
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr
 ; CHECK-O-NEXT: entry:
 ; CHECK-O-NEXT:   br label %loop