This is an archive of the discontinued LLVM Phabricator instance.

[ThinLTO] Perform profile-guided indirect call promotion
ClosedPublic

Authored by tejohnson on Jul 1 2016, 11:02 AM.

Details

Summary

To enable profile-guided indirect call promotion in ThinLTO mode, we
simply add call graph edges for each profitable target from the profile
to the summaries, then the summary-guided importing will consider the
callee for importing as usual.

Also we need to enable the indirect call promotion pass creation in the
PassManagerBuilder when PerformThinLTO=true (we are in the ThinLTO
backend), so that the newly imported functions are considered for
promotion in the backends.

A couple of other changes:

  • Refactored the profitability analysis out of the IC promotion pass and into lib/Analysis so that it can be accessed by the summary index builder.
  • The IC promotion profiles refer to callees by GUID, which required adding GUIDs to the per-module VST in bitcode (and assigning them valueIds similar to how they are assigned valueIds in the combined index).

Diff Detail

Repository
rL LLVM

Event Timeline

tejohnson updated this revision to Diff 62512.Jul 1 2016, 11:02 AM
tejohnson retitled this revision from to [ThinLTO] Perform profile-guided indirect call promotion.
tejohnson updated this object.
tejohnson added reviewers: mehdi_amini, xur.
tejohnson added subscribers: llvm-commits, davidxl.

Can you split the refactor code into a separate patch?

Can you split the refactor code into a separate patch?

I moved the refactoring into D22182.
(I haven't updated this to rebase it on top of that one yet, will try to do that later tonight)

tejohnson updated this revision to Diff 63369.Jul 8 2016, 6:37 PM

Rebase on top of D22182.

Hmm, the rebase didn't quite work as expected - I still see the diffs that I moved to D22182. Will try to figure out later.

tejohnson updated this revision to Diff 63383.Jul 8 2016, 8:13 PM

I think this should properly rebase on top of D22182.

davidxl added inline comments.Jul 11 2016, 10:44 AM
include/llvm/IR/ModuleSummaryIndex.h
265 ↗(On Diff #63383)

This is a duplicate.

lib/Analysis/ModuleSummaryAnalysis.cpp
99 ↗(On Diff #63383)

When getCalledValue() returns constant, should it be covered above (i.e., CalledFunction is not null)?

104 ↗(On Diff #63383)

See the comment in the dependent patch -- the icall analysis needs to return set of targets also 'legal'.

lib/Bitcode/Writer/BitcodeWriter.cpp
151 ↗(On Diff #63383)

Add one line comment before each 'for' -- kind of hard to read a loop deep nested without some background.

mehdi_amini added inline comments.Jul 11 2016, 1:38 PM
lib/Bitcode/Writer/BitcodeWriter.cpp
151 ↗(On Diff #63383)

Alternatively, using explicit name for iterator variable can help.

lib/Transforms/IPO/PassManagerBuilder.cpp
366 ↗(On Diff #63383)

Is this totally related to this patch or is it already an existing mistake? (I.e. could be committed separately?)

Also remove braces for the if block.

tejohnson added inline comments.Jul 11 2016, 5:11 PM
include/llvm/IR/ModuleSummaryIndex.h
265 ↗(On Diff #63383)

No, this is new (the other one takes a map of Value* this takes a map of GUID

lib/Analysis/ModuleSummaryAnalysis.cpp
99 ↗(On Diff #63383)

This was modeled on the checking in PGOIndirectCallSiteVisitor::visitCallSite, which checks if the value is constant after the early return when getCalledFunction() is not-null.

104 ↗(On Diff #63383)

As noted there, we can't check legality in the refactored code since we don't have access to the called function yet.

lib/Bitcode/Writer/BitcodeWriter.cpp
151 ↗(On Diff #63383)

Ok, add some comments or use a more explicit name.

lib/Transforms/IPO/PassManagerBuilder.cpp
366 ↗(On Diff #63383)

It could be committed earlier but would be a no-op without the rest of this patch (unless we happened to import a function that was called directly but also happened to be called indirectly).

Will remove braces.

mehdi_amini added inline comments.Jul 11 2016, 5:17 PM
lib/Transforms/IPO/PassManagerBuilder.cpp
366 ↗(On Diff #63383)

I see, it also runs during the compile phase so it'll only apply to imported function here. That's fine as-is then.

tejohnson updated this revision to Diff 63701.Jul 12 2016, 11:31 AM
  • Add comments and variable names to nested for loop.
mehdi_amini added inline comments.Jul 12 2016, 3:39 PM
lib/Analysis/ModuleSummaryAnalysis.cpp
97 ↗(On Diff #63701)

Add a one line comment for this code block?

test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll
3–4 ↗(On Diff #63701)

I'm not sure why you need this definition?

mehdi_amini accepted this revision.Jul 16 2016, 11:47 AM
mehdi_amini edited edge metadata.

LGTM with the two comments I made previously.

This revision is now accepted and ready to land.Jul 16 2016, 11:47 AM

LGTM with the two comments I made previously.

Thanks. Somehow I completely missed the last set of comments you added!

lib/Analysis/ModuleSummaryAnalysis.cpp
97 ↗(On Diff #63701)

Will do.

test/Transforms/PGOProfile/Inputs/thinlto_indirect_call_promotion.ll
3–4 ↗(On Diff #63701)

You're right, this is unnecessary. Removed.

tejohnson updated this revision to Diff 64254.Jul 17 2016, 7:22 AM
tejohnson edited edge metadata.
  • Address latest comments.
This revision was automatically updated to reflect the committed changes.
Prazek added a subscriber: Prazek.Jul 17 2016, 5:52 PM
Prazek added inline comments.
llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp
150

early exit here will reduce indentation

151–161

I think that you should use braces here. It will be more readable and it will be harder to make mistake modifying it.

295–297

I guess you could use .at() member here, so you won't have to check if it's there with assert.

2858–2862

This code seems a little suspicious because you clear the NameVals vector every time you push it.
You could just create new vector with thouse 2 values and move it to Stream.EmitRecord.

Thanks for the review. Responses below.

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp
150

ok

151–161

I've always been asked to remove braces when not necessary, so I will leave this as-is unless other reviewers concur.

295–297

True, but for efficiency I prefer to keep the check only in the debug builds. I will add an assertion message though, which should be here.

2858–2862

The clear is needed before using it on the subsequent iteration. This is consistent with the rest of BitcodeWriter.cpp, that uses a single SmallVector per routine, clearing after each EmitRecord call.

I believe this is for efficiency (SmallVector is good for small numbers of vals, has efficient push/pop, but is larger and less efficient to allocate). According to http://llvm.org/docs/ProgrammersManual.html#vector:
"std::vector is well loved and respected. It is useful when SmallVector isn’t: when the size of the vector is often large"

mehdi_amini added inline comments.Jul 18 2016, 1:16 PM
llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp
151–161

Agree with Teresa: I believe the LLVM usual coding style is to not add braces unless ambiguity (if/else nested inside an if).
(I agree that it's harder to make a mistake by keeping braces all the time, but that's not the usual LLVM style)

2858–2862

Agree as well: this is a common pattern in LLVM.