This is an archive of the discontinued LLVM Phabricator instance.

ThinLTO: use the callgraph from the combined index to drive the FunctionImporter
ClosedPublic

Authored by mehdi_amini on Mar 21 2016, 10:34 PM.

Details

Summary

Now that the summary contains the full reference/call graph, we can
replace the existing function importer that loads and inspect the IR
to iteratively walk the call graph by a traversal based purely on the
summary information. Decouple the actual importing decision from any
IR manipulation.

Diff Detail

Event Timeline

mehdi_amini retitled this revision from to ThinLTO: use the callgraph from the combined index to drive the FunctionImporter.
mehdi_amini updated this object.
mehdi_amini added a reviewer: tejohnson.
mehdi_amini added a subscriber: llvm-commits.
tejohnson edited edge metadata.Mar 25 2016, 9:50 AM

Thanks! A few comments/questions below.

include/llvm/Transforms/IPO/FunctionImport.h
51

Need a description of what is in each ImportList entry. Realize this could be deduced by reading ahead to the next comment, but would be good to include here too.

61

s/enty/entry/

62

Outer StringMap has an entry for every Module we are importing to, with an entry for each Module we are importing from, right? Maybe make that clearer by changing the first sentence above to "ImportLists will be populated with an entry for every Module we are importing into."

Might be clearer if you use typedefs for each map.

lib/LTO/ThinLTOCodeGenerator.cpp
374

Initialize these two maps with the module count as done in ThinLTOCodeGenerator::crossModuleImport

lib/Transforms/IPO/FunctionImport.cpp
70
  • Prioritize copies from a module already being imported from (reduces # source modules parsed/linked)
  • Prioritize any that has profile data, although we don't have that info here (not sure how COMDAT profile matching works on llvm, I know on gcc only the selected or any inlined/selected copies would get profile data, may be different on llvm due to single profile database?)
75

I think this can be an assert? We should have a summary for every GlobalValueInfo in the combined map, and presumably it should be a FunctionSummary type since we got here via the GUID of a call graph edge.

132

Give more meaningful message here? Maybe just as simple as "ignored! No qualifying callee with summary found."

149–150

This should be an assert as selectCallee already checked this condition.

165

This only adds the called functions, I think you need to do the same for the refs().

175

Can this be an assert?

177

Extraneous ";"?

274

Comment about ignoring global variables (which should be the only reason this is null?).

276

Isn't this the number of modules being exported from in total? I.e. the size of this will monotonically increase as we invoke ComputeImportForModule across all the modules. Message is confusing - this isn't the number of exports from this module.

277

Use GUID instead of GlobalList.first for consistency/clarity.

316

GlobalsToImport here and in map name since it covers gvars now too.

327

Use your new getGUID() here and in alias handling below too. Also, needs merge as the existing static getGUID() has moved to GlobalValue from Function.

332

Add comment about why this is done?

379

This patch seems to undo the renaming done in r263513.

431

Another renaming that was undone by patch (bad merge?)

458

Note the export lists are not useful at this point since in this case we are already in the back end and we can't communicate this info to the source module which is presumably being compiled in a separate thread or backend process (in the distributed build case). Probably needs a comment about needing to be conservative when function importing being done in the backend and assume for now that all symbols may be exported. To get better about this in the distributed build case we will need to compute this info in the plugin and save it somewhere (in the index?) for consumption by the backends. For the single machine case where gold is the linker it will have to be reworked similar to what you have done in LTOCodeGenerator to do the importing computation ahead of time.

test/Transforms/FunctionImport/adjustable_threshold.ll
7

Why these changes of using .bc instead of .ll? Is it needed or at least independent and can be committed separately?

Thanks, I'll fix all of these comments, a few answers in the meantime.

lib/LTO/ThinLTOCodeGenerator.cpp
374

Yes! I was waiting for my changes on the StringMap to be checked in (committed yesterday).

lib/Transforms/IPO/FunctionImport.cpp
379

Probably an issue when rebasing on top of your changes.

458

You can call ComputeCrossModuleImport and get the same answer in every backend jobs.
By moving this code a few lines above before the renameModuleforThinLTO we'll be able to use the export list to limit the renaming in the source module.

test/Transforms/FunctionImport/adjustable_threshold.ll
7

It is needed: the summary will contains the module path as a string pointing to the .bc.
The importer will not be able to walk the graph because if won't find the modules in the index.

davidxl added inline comments.
lib/Transforms/IPO/FunctionImport.cpp
70

In LLVM, comdat function's profile counters will also be put into comdat, so there should be no need to differentiate based on profile availability.

100

Why not passing a reference of the Edge to 'selectCallee'. We will need to look at profile data in the future.

mehdi_amini added inline comments.Mar 25 2016, 10:44 AM
lib/Transforms/IPO/FunctionImport.cpp
100

I think the profile info will not impact *which* callee you select right? What do you expect to do with this information at this level?

davidxl added inline comments.Mar 25 2016, 10:54 AM
lib/Transforms/IPO/FunctionImport.cpp
100

It will impact importing strategy. For instance increased threshold for hot callsites and reduced threshold for extreme cold ones. The summary Edge can also contain other nice bits (such as has constant argument etc) which will help importing more precisely.

tejohnson added inline comments.Mar 25 2016, 10:57 AM
lib/Transforms/IPO/FunctionImport.cpp
70

Good news!

458

As discussed on IRC, this will work for the time being (assuming all invocations use the same thresholds etc). Longer term, compute this info in the plugin (and serialize out for distributed build backends).

mehdi_amini added inline comments.Mar 25 2016, 10:58 AM
lib/Transforms/IPO/FunctionImport.cpp
100

I agree, it is not clear to me that exposing the "Edge" here is the right abstraction (one could modifying the Threshold at call site to include a PGO bias for instance, even if it is probably not the right thing either).

I think that I can safely leave this for the larger refactoring work that will follow when we will rework the cost model for importing.

davidxl added inline comments.Mar 25 2016, 11:11 AM
lib/Transforms/IPO/FunctionImport.cpp
100

Sounds fine to me.

mehdi_amini marked 31 inline comments as done.
mehdi_amini edited edge metadata.

Address Teresa's comments

Update one comment

mehdi_amini marked an inline comment as done.Mar 25 2016, 3:18 PM
mehdi_amini added inline comments.
include/llvm/Transforms/IPO/FunctionImport.h
62

Typedef solve it all :)

I'll probably commit a subsequent cleanup to make GUID a typedef as well.

lib/Transforms/IPO/FunctionImport.cpp
70

Updated the comment.

75

I think this was originally an assert and I figured later it was a legit case. Can't remember, will turn back into an assert for now.

100

Great, thanks David!

165

This was intentional, comment added.

332

I have no idea, I remember copying it from what I was tracking in the ModuleLinker/IRMover. But can't retrieve it now, we want to import an alias to a global variable, should we import the global as well if it is link once?

mehdi_amini marked an inline comment as done.

Fix typedefs

tejohnson added inline comments.Mar 25 2016, 9:02 PM
include/llvm/Transforms/IPO/FunctionImport.h
28

s/function/functions
s/. each/. Each/

35

Incomplete sentence "The value for"

39–40

s/functions/function/
Actually, this needs to hold global variables that are exported as well, right? Maybe say "for every global value the module exports".

Also, not a map. So maybe ExportSetTy in addition to comment fix?

lib/Transforms/IPO/FunctionImport.cpp
165

True that we don't import globals, but we do export references to them if they are referenced from a function that is imported elsewhere. So presumably those references should be added to the export list as they may need to be promoted/renamed.

333

Oh, I know why. We can't have an alias to an available_externally def, since that is actually a declaration for the linker, and most imported defs are given available_externally linkage (except linkonce which stays the same linkage). This is the same logic as in FunctionImportGlobalProcessing::doImportAsDefinition(). I think there might have been more comments around that at one point but they gotten lost when the code moved around.

mehdi_amini marked 11 inline comments as done.

Update for Teresa's comments

Thanks, good catch here. Updated!

lib/Transforms/IPO/FunctionImport.cpp
165

Oh, good point, my previous answer was totally wrong, I thought we were looking at the "import" list here. When I wrote the original code I intended Summary->edge() to iterate over both calls() and refs(). Fixed!

333

Updated comment

tejohnson accepted this revision.Mar 25 2016, 10:15 PM
tejohnson edited edge metadata.

LGTM, just a couple nits below. Thanks!

lib/Transforms/IPO/FunctionImport.cpp
122

Nit: unneeded braces

176

Maybe "Mark all functions and globals referenced by this function as exported to the outside if they are defined in the same source module."?

This revision is now accepted and ready to land.Mar 25 2016, 10:15 PM
mehdi_amini edited edge metadata.

Update before commit

tejohnson added inline comments.Mar 25 2016, 10:28 PM
lib/Transforms/IPO/FunctionImport.cpp
139

This can be removed now.

Even more cleanup :)