[PGO] context sensitive PGO

[xur]

Summary

Current PGO profile counts are not context sensitive. The branch probabilities for the inlined functions are kept the same for all call-sites, and they might be very different from the actual branch probabilities. These suboptimal profile can greatly affect some downstream optimizations, in particular for machine basic block placement optimization.

In this patch, we propose to have a post-inline PGO instrumentation/use pass, which we called Context Sensitive PGO (CSPGO). For the users who want the best possible performance, they can perform a second round of PGO instrument/use on the top of the regular PGO. They will have two sets of profile counts. The first pass profile will be manly for inline, indirect-call promotion, and CGSCC simplification pass optimizations. The second pass profile is for post-inline optimizations and code-gen optimizations.

The typical usage models are:
// Regular PGO instrumentation and generate pass1 profile.

> clang -O2 -fprofile-generate source.c -o gen
> ./gen
> llvm-profdata merge default.*profraw -o pass1.profdata

// CSPGO instrumentation.

> clang -O2 -fprofile-use=pass1.profdata -fcs-profile-generate -o gen2
> ./gen2

// Merge two sets of profiles

> llvm-profdata merge default.*profraw pass1.profdata -o profile.profdata

// Use the combined profile. Pass manager will invoke two PGO use passes.

> clang -O2 -fprofile-use=profile.profdata -o use

The major changes are the following:

• bump index profile version to indicate if there are context-sensitive counts.
• change the FuncHash and reserve bits for context-sensitive counts.
• change the ProfileSummary interface as we might have two sets of profile summaries.
• change pass-manager (legacy and new)
• change llvm-profdata to handle two kind of profiles.
• change instrprofiling lowing for more aggressive register promotion for CSPGO.

Note that other than the FuncHash change, there is no effect on existing PGO pass.

This patches is functional tested using SPEC2006, with the various combinations of the following:

• legacy-pass manager
• new pass manager
• thin-lto (through gold plugin)
• thin-lto (though driver command line)
• lto (through plugin)
• non-lto

We performance-tested this patch with a few large Google benchmarks and saw good performance improvements.

I did not include any tests in this patch. I will add tests once the interfaces are decided in the code review.

[tejohnson]

lib/Passes/PassBuilder.cpp

777 ↗

(On Diff #181595)

document const parameter (here and in below call)

1022 ↗

(On Diff #181595)

document const parameter

1145 ↗

(On Diff #181595)

document const parameter (here and below call)

lib/ProfileData/InstrProf.cpp

1045 ↗

(On Diff #181595)

nit - in createProfileNameVar the linkage initially set to weak any, then reset to external if supports comdat. Here you do the opposite - suggest making the logic the same in both places for consistency

lib/ProfileData/InstrProfReader.cpp

815 ↗

(On Diff #181595)

document const parameter here and in below call

lib/Transforms/IPO/PassManagerBuilder.cpp

537 ↗

(On Diff #181595)

s/proifle/profile/

538 ↗

(On Diff #181595)

Can you add a better explanation about linker issue - i.e. the linker wants to see all variables before the LTO link since it needs to resolve symbols/comdats.

575 ↗

(On Diff #181595)

document const parameter (here and below)

lib/Transforms/Instrumentation/InstrProfiling.cpp

276 ↗

(On Diff #181595)

document rationale for this equation

998 ↗

(On Diff #181595)

Comment needed

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

410 ↗

(On Diff #181595)

document

435 ↗

(On Diff #181595)

document

554 ↗

(On Diff #181595)

document

666 ↗

(On Diff #181595)

Probably needs a slight expansion on why that other info shouldn't affect function hash.

678 ↗

(On Diff #181595)

why reorder this?

1459 ↗

(On Diff #181595)

document const parameter. also add comment for why this is not needed when IsCS

1507 ↗

(On Diff #181595)

I don't see where the new parameter PSI is getting used.

1642 ↗

(On Diff #181595)

Here and below, needs comment about why PSI when IsCS. But see comment in annotateAllFunctions - I don't see it getting used there?

tools/llvm-profdata/llvm-profdata.cpp

716 ↗

(On Diff #181595)

How about replace these 4 lines with just:

if (FuncIsCS != ShowCS)

continue;

tools/opt/NewPMDriver.cpp

116 ↗

(On Diff #181595)

Can you do something similar to D56749 (moving and consolidating these opts between PMs)?

249 ↗

(On Diff #181595)

Is this still TODO? I see handling further below.

284 ↗

(On Diff #181595)

As an aside - theoretically someone might want to do CS profiling without regular PGO. Is it worth supporting that combination?

unittests/ProfileData/InstrProfTest.cpp

179 ↗

(On Diff #181595)

document const param

805 ↗

(On Diff #181595)

ditto

[xur]

cmake/modules/HandleLLVMOptions.cmake

816 ↗

(On Diff #181595)

Fixed the typo.

I think currently -profile-instr-use flag is only added to CMAKE_CXX_FLAGS and CMAKE_C_FLAGS. I need them to pass to linker and shared linker also. Since there is no flag for CSIR use build. I have to pass them unconditionally. For regular PGO, the flag is void operation.

I'll remove the line of CMAKE_CXX_FLAGS and CMAKE_C_FLAGS

826 ↗

(On Diff #181595)

Moved the change to
https://reviews.llvm.org/D57068

include/llvm/Passes/PassBuilder.h

45 ↗

(On Diff #181595)

Make sense. I will change this part.

lib/Passes/PassBuilder.cpp

523 ↗

(On Diff #181595)

This is for the early inline. We skip the early inline if for optimization for size.
For CS, we will not do early inline either.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

666 ↗

(On Diff #181595)

This change actually will affect function hash -- if an old profile is passed here, an non-cs record could be recognized as CS profile. But that will most likely result in a CFG hash mismatch where the user will get a warning.

678 ↗

(On Diff #181595)

not intentionally. I will revert this change.

1507 ↗

(On Diff #181595)

Good catch! This is from my other changes that fixes BB profile count. They should be removed.

1642 ↗

(On Diff #181595)

Fixed. PSI is not used here.

tools/llvm-profdata/llvm-profdata.cpp

716 ↗

(On Diff #181595)

Yes!

tools/opt/NewPMDriver.cpp

249 ↗

(On Diff #181595)

Yes. we should remove this TODO.

284 ↗

(On Diff #181595)

Since both CSprofile and non-CS-profile are merged into one profile. I think it's earlier to assume regular PGO is enabled for CSPGO. If there is a need for support the other way, I will add later.

[xur]

Integrated Teresa's review comments.

Also fixed a bug that can cause mismatch in new pass manager -- some optimization passes are under guard of PGOOptions::IRUse. LTOBackend sets PGOAction to NOAction for CSIRInstr (because regular profile is not passed down for CSIRInstr). This leads to different IR for CSIRInstr and CSIRUse.

This patch sets the PGOAction to IRUSE for CSIRInstr.

[xur]

Fixed a pass ordering issue in legacy pass manager for ThinLTO: Need to place CS Instrumentation after EliminateAvailableExternallyPass. This can cause duplicate profile variables that leads to bad profile for online profile merge.

Also synced the trunk and fixed a merge issue.

[tejohnson]

Mostly minor comments inline. But still missing tests. Needs testing via new gold-plugin and opt options. Should also add options to llvm-lto2 to enable testing the LTOBackend path without needing gold or any other specific linker.

include/llvm/Passes/PassBuilder.h

55 ↗

(On Diff #183899)

Should we also have IRUse when CSAction is CSIRInstr?

include/llvm/ProfileData/InstrProfReader.h

438 ↗

(On Diff #181595)

The same change should be done elsewhere in this class (document and change to UseCS). There are a couple other interfaces with the same option.

include/llvm/ProfileData/InstrProfWriter.h

77 ↗

(On Diff #183899)

Document new parameter (there is currently nowhere in the file that indicates CS means context sensitive).

include/llvm/Transforms/Instrumentation.h

91 ↗

(On Diff #183899)

Document new parameter here and further down in createInstrProfilingLegacyPass (there is currently nowhere in the file that indicates CS means context sensitive).

lib/Passes/PassBuilder.cpp

523 ↗

(On Diff #181595)

Please add comment to that effect.

lib/Transforms/IPO/PassManagerBuilder.cpp

283 ↗

(On Diff #183899)

Similar suggestion to the one I had for new PM (add comment about now not when IsCS).

lib/Transforms/Instrumentation/InstrProfiling.cpp

999 ↗

(On Diff #183899)

typo in instrumentation (missing n in the middle).

tools/opt/opt.cpp

290 ↗

(On Diff #183899)

The reason I suggested moving this here was to use the same set of options to set up CSPGO for the old PM. But it doesn't seem like it is being set up when invoked via opt. I'd expect something down in AddOptimizationPasses like where it sets up regular IR PGO PassManagerBuilder options.

[davidxl]

Please also add a profile dumping/reading round trip test with isCS flag (there are existing similar test for llvm-profdata)

text-format --> index-format-> text-format : diff text-format

include/llvm/ProfileData/InstrProfWriter.h

91 ↗

(On Diff #183899)

What is this (promotion)'s use case?

include/llvm/Transforms/Instrumentation/PGOInstrumentation.h

31 ↗

(On Diff #183899)

Add documentation for the new class. Also explain why it needs to be created in a pass.

lib/Analysis/ProfileSummaryInfo.cpp

89 ↗

(On Diff #183899)

This is confusing. It is better to just pass 'IsCS' flag to getProfileSummary method.

lib/ProfileData/InstrProf.cpp

1015 ↗

(On Diff #183899)

nit: createProfileFileNameVar.

Can this one be split out as a NFC change?

tools/llvm-profdata/llvm-profdata.cpp

909 ↗

(On Diff #183899)

New option needs to be documented in command line guide.

[xur]

Integrated the review comments from Teresa and David.
Added unit tests for
(1) llvm-profdata
(2) context-sensitive profile summary
(3) opt new options and passes
(4) gold plugin
(5) using lto2 to test csgen and csuse.

[davidxl]

include/llvm/ProfileData/InstrProfWriter.h

91 ↗

(On Diff #183899)

Can you explain the 'promotion' case here (as comments)?

lib/Analysis/ProfileSummaryInfo.cpp

89 ↗

(On Diff #183899)

how about this comment?

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

497 ↗

(On Diff #185907)

Remove this.

[xur]

Fixed the missing changes David mentioned.

include/llvm/Passes/PassBuilder.h

55 ↗

(On Diff #183899)

CSIRInstr can run without IRUSE. CSIRUse needs to IRUse (the only reason is they share the profile).

include/llvm/ProfileData/InstrProfWriter.h

91 ↗

(On Diff #183899)

when merging a non-cs profile with cs profile, the result is cs profile.

lib/ProfileData/InstrProf.cpp

1015 ↗

(On Diff #183899)

split the change to nfc r353230.

tools/opt/opt.cpp

290 ↗

(On Diff #183899)

OK. Got it.

[xur]

Forgot to include one more test:
A test/Other/cspgo-O2-pipeline.ll

[xur]

Removed the unrelated instructions (comments) from the tests.

[tejohnson]

LGTM, but wait for @davidxl to do final approval since I'm not sure his last comments addressed.

[davidxl]

lgtm

[ABataev]

llvm/trunk/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h

41

Seems to me, it breaks the build with the shared libraries. Could you take a look at this?
lib/Passes/CMakeFiles/LLVMPasses.dir/PassBuilder.cpp.o: In function `llvm::PGOInstrumentationGenCreateVar::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)':
/build/llvm/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h:42: undefined reference to `llvm::createProfileFileNameVar(llvm::Module&, llvm::StringRef)'
/build/llvm/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h:43: undefined reference to `llvm::createIRLevelProfileFlagVar(llvm::Module&, bool)'

[rupprecht]

llvm/trunk/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h

41

Not OP, but I also hit this. rL355346 should fix it.

[ABataev]

llvm/trunk/include/llvm/Transforms/Instrumentation/PGOInstrumentation.h

41

Thanks for the fix!

[hctim]

Looks like this commit has broken the clang-hexagon-elf#23291: build. PTAL :)

FAIL: LLVM :: Transforms/PGOProfile/thinlto_cspgo_gen.ll (41188 of 44167)
******************** TEST 'LLVM :: Transforms/PGOProfile/thinlto_cspgo_gen.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/opt -module-summary /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/thinlto_cspgo_gen.ll -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc
: 'RUN: at line 2';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/opt -module-summary /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/Inputs/thinlto_cspgo_bar_gen.ll -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc
: 'RUN: at line 3';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/llvm-lto2 run -lto-cspgo-profile-file=alloc -lto-cspgo-gen -save-temps -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc,foo,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc,bar,l    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc,main,plx    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc,__llvm_profile_filename,plx    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp1.bc,__llvm_profile_raw_version,plx    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc,bar,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc,odd,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc,even,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc,__llvm_profile_filename,x    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp2.bc,__llvm_profile_raw_version,x
: 'RUN: at line 14';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/llvm-dis /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_gen.ll.tmp.1.4.opt.bc -o - | /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/FileCheck /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/thinlto_cspgo_gen.ll --check-prefix=CSGEN
--
Exit Code: 1

Command Output (stderr):
--
llvm-lto2: LTO::run failed: No available targets are compatible with triple "x86_64-unknown-linux-gnu"

--

********************
PASS: LLVM :: Transforms/PartiallyInlineLibCalls/nobuiltin.ll (41189 of 44167)
PASS: LLVM :: Transforms/PartiallyInlineLibCalls/bad-prototype.ll (41190 of 44167)
PASS: LLVM :: Transforms/PGOProfile/memop_size_annotation.ll (41191 of 44167)
PASS: LLVM :: Transforms/PGOProfile/loop1.ll (41192 of 44167)
PASS: LLVM :: Transforms/PhaseOrdering/2010-03-22-empty-baseclass.ll (41193 of 44167)
PASS: LLVM :: Transforms/PGOProfile/loop2.ll (41194 of 44167)
FAIL: LLVM :: Transforms/PGOProfile/thinlto_cspgo_use.ll (41195 of 44167)
******************** TEST 'LLVM :: Transforms/PGOProfile/thinlto_cspgo_use.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/opt -module-summary /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/thinlto_cspgo_use.ll -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp1.bc
: 'RUN: at line 2';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/opt -module-summary /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/Inputs/thinlto_cspgo_bar_use.ll -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp2.bc
: 'RUN: at line 3';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/llvm-profdata merge /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/Inputs/thinlto_cs.proftext -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp3.profdata
: 'RUN: at line 4';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/llvm-lto2 run -lto-cspgo-profile-file=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp3.profdata -save-temps -o /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp1.bc /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp2.bc    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp1.bc,foo,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp1.bc,bar,l    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp1.bc,main,plx    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp2.bc,bar,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp2.bc,odd,pl    -r=/var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp2.bc,even,pl
: 'RUN: at line 11';   /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/llvm-dis /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/test/Transforms/PGOProfile/Output/thinlto_cspgo_use.ll.tmp.1.4.opt.bc -o - | /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/stage1/bin/FileCheck /var/lib/buildbot/slaves/hexagon-build-03/clang-hexagon-elf/llvm/test/Transforms/PGOProfile/thinlto_cspgo_use.ll --check-prefix=CSUSE
--
Exit Code: 1

Command Output (stderr):
--
llvm-lto2: LTO::run failed: No available targets are compatible with triple "x86_64-unknown-linux-gnu"

--

********************

[pcc]

llvm/trunk/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

673

Hi Rong, I discovered a problem with this line of code. If the number of select instructions when the profile was collected differs by a multiple of 16 from the number when the profile is used, we get a hash collision which results in us hitting an assertion here:
http://llvm-cs.pcc.me.uk/lib/Transforms/Instrumentation/PGOInstrumentation.cpp#1042

Granted, the same problem seems to have already existed for differences that are multiples of 256, but this seems to make the problem more likely to occur.

[xur]

llvm/trunk/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

673

I sent this patch for review.

https://reviews.llvm.org/D60154