This is an archive of the discontinued LLVM Phabricator instance.

FunctionImporter: implement bulk function importing for efficiency
ClosedPublic

Authored by mehdi_amini on Dec 2 2015, 11:16 PM.

Details

Summary

The current importing scheme is processing one function at a time,
loading the source Module, linking the function in the destination
module, and destroying the source Module before repeating with the
next function to import (potentially from the same Module).

Ideally we would keep the source Module alive and import the next
Function needed from this Module. Unfortunately this is not possible
because the linker does not leave it in a usable state.

However we can do better by first computing the list of all candidates
per Module, and only then load the source Module and import all the
function we need for it.

The trick to process callees is to materialize function in the source
module when building the list of function to import, and inspect them
in their source module, collecting the list of callees for each
callee.

When we move the the actual import, we will import from each source
module exactly once. Each source module is loaded exactly once.
The only drawback it that it requires to have all the lazy-loaded
source Module in memory at the same time.

Currently this patch already improves considerably the link time,
a multithreaded link of llvm-dis on my laptop was:

real  1m12.175s  user  6m32.430s sys  0m10.529s

and is now:

real  0m40.697s  user  2m10.237s sys  0m4.375s

Note: this is the full link time (linker+Import+Optimizer+CodeGen)

Diff Detail

Event Timeline

mehdi_amini retitled this revision from to FunctionImporter: implement bulk function importing for efficiency.
mehdi_amini updated this object.
mehdi_amini added a reviewer: tejohnson.
mehdi_amini added subscribers: dexonsmith, llvm-commits.

Supersede D15176

Note: this is still a wip (there are a few functions that are no longer imported, I need to figure out why) but the bulk of the changes should be there.

tejohnson edited edge metadata.Dec 3 2015, 8:18 AM

With this approach we consider a function for importing exactly once, and I'm concerned that this will lose opportunities where we might decide to import it after other imports are done (e.g. exposing more hot calls to it). Perhaps when we decide not to import it in the worklist iteration in GetImportList it should also be removed from the CalledFunctions set so that it can be reconsidered when new calls to it are seen.

What was the memory overhead difference with and without this patch? I guess having the materialized functions on all the source modules before importing is ok since they will all eventually be moved into the dest module during linking anyway. But there will still be overhead of keeping all the source modules which have some other overhead.

lib/Transforms/IPO/FunctionImport.cpp
242

How do you ensure that F is materialized in the lazy-loaded SrcModule? With the current code at HEAD it is the dest copy we walk, which was materialized in the source and then copied over during module linking.

Another issue with using the source copy here - the local functions haven't been renamed/promoted, so there may be apparent duplicates in CalledFunctions due to same-named local functions from other modules.

mehdi_amini updated this revision to Diff 41820.Dec 3 2015, 4:02 PM
mehdi_amini edited edge metadata.

Fix materialization and renaming for internal functions

mehdi_amini updated this revision to Diff 41984.Dec 4 2015, 9:58 PM

Use an ordered std::map for reproducibility

Thanks for working on this. Some more comments/questions below.

lib/Transforms/IPO/FunctionImport.cpp
59

Remove

92

Maybe "...internal function calls imported from..."? I.e. at this point we have only imported the call.

126

We reach here if the function is already in the CalledFunctions set, so do we want to issue a message that we are ignoring it? It seems misleading, i.e. it sounds like we decided not to import.

138

Why is this under #ifndef NDEBUG?

275–284

I don't see anything called ProcessImportWorklist? Do you mean GetImportList? Each iteration of what?

279

Comment reads funny: "helps required by"

mehdi_amini updated this revision to Diff 42210.Dec 8 2015, 1:10 PM

Update following Teresa's comments

mehdi_amini updated this revision to Diff 42234.Dec 8 2015, 3:05 PM
mehdi_amini marked 7 inline comments as done.

Rebase on trunk

mehdi_amini updated this revision to Diff 42236.Dec 8 2015, 3:09 PM

Remove spurious NDEBUG

tejohnson accepted this revision.Dec 8 2015, 3:41 PM
tejohnson edited edge metadata.

Looks like it needs another rebase given your most recent changes, but otherwise lgtm. Thanks!

This revision is now accepted and ready to land.Dec 8 2015, 3:41 PM

One small post-commit suggestion for a TODO.

lib/Transforms/IPO/FunctionImport.cpp
121

We will never reconsider a function after initially deciding it isn't profitable to import. Currently the only profitability decision is based on the number of instructions, which won't change with importing. But perhaps we should add a TODO down where we have those checks to remove any callees from the CalledFunctions list if they fail a profitability check that may be affected by additional importing decisions.