Lazily Loaded Modules and Linker::LinkOnlyNeeded

Neil_Henning · April 20, 2016, 12:20pm

TL;DR - when linking from a lazily loaded module and using Linker::LinkOnlyNeeded, bodies of used functions aren’t being copied during linking.

Previously on one of our products, we would lazily load our runtime module (around 9000 functions), and link some user module into this (which is in all practical use cases much smaller). Then, post linking, we have a pass that runs over the module and rips out all the un-materialized functions that weren’t being used in the original user module.

I only just noticed that LinkModules has a flags parameter that can take a LinkOnlyNeeded flag, which made me wonder if I could reverse the link order (EG. link from the lazily loaded runtime module into the user module), set the LinkOnlyNeeded flag, and hey presto, we wouldn’t need to have a cleanup pass that ran afterwards ripping out functions that weren’t used.

So I tried it, and it failed. Basically any function that was still to be materialized wasn’t getting its body copied over during linking.

The only line of code that differs when you set LinkOnlyNeeded is in LinkModules.cpp → ModuleLinker::linkIfNeeded:

if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
    return false;

The isDeclaration() for functions has a call to isMaterializable().

Things I’ve tried:

If I don’t pass LinkOnlyNeeded but still link from the lazily loaded runtime module into the user module, it works (albeit it is orders of magnitude slower like we’d expect).
If I don’t lazily load the runtime module, it works (but again, much slower).
I tried doing the linking and then materializing the newly linked module, but the runtime functions were still missing their bodies (which implies the information was lost during linking).
If I hack the LinkModules.cpp code such that it checks if the DGV could be materialized, and if so materialize it, before checking for a declaration again, it works:

if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration())) {
    if (DGV && DGV->isMaterializable())
        DGV->materialize();

    if (!(DGV && DGV->isDeclaration()))
        return false;
}

Even with the extra cost of the hack above - this has resulted in a 2x speedup in our total link time.

So really here I am wondering - is this expected behaviour? A bug? And if so how best to go about fixing the issue would be some grand advice from people more in the know!

Cheers,
-Neil.

mehdi_amini · April 20, 2016, 4:18pm

Hi Neil,

TL;DR - when linking from a lazily loaded module and using Linker::LinkOnlyNeeded, bodies of used functions aren’t being copied during linking.

Previously on one of our products, we would lazily load our runtime module (around 9000 functions), and link some user module into this (which is in all practical use cases much smaller).

It sounds reverse to what I would intuitively do (i.e. load the runtime into my module).

Then, post linking, we have a pass that runs over the module and rips out all the un-materialized functions that weren’t being used in the original user module.

I only just noticed that LinkModules has a flags parameter that can take a LinkOnlyNeeded flag, which made me wonder if I could reverse the link order (EG. link from the lazily loaded runtime module into the user module), set the LinkOnlyNeeded flag, and hey presto, we wouldn’t need to have a cleanup pass that ran afterwards ripping out functions that weren’t used.

So I tried it, and it failed. Basically any function that was still to be materialized wasn’t getting its body copied over during linking.

The only line of code that differs when you set LinkOnlyNeeded is in LinkModules.cpp → ModuleLinker::linkIfNeeded:
if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
    return false;
The isDeclaration() for functions has a call to isMaterializable().

Things I’ve tried:

If I don’t pass LinkOnlyNeeded but still link from the lazily loaded runtime module into the user module, it works (albeit it is orders of magnitude slower like we’d expect).

If I don’t lazily load the runtime module, it works (but again, much slower).

I tried doing the linking and then materializing the newly linked module, but the runtime functions were still missing their bodies (which implies the information was lost during linking).

If I hack the LinkModules.cpp code such that it checks if the DGV could be materialized, and if so materialize it, before checking for a declaration again, it works:
if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration())) {
    if (DGV && DGV->isMaterializable())
        DGV->materialize();

    if (!(DGV && DGV->isDeclaration()))
        return false;
}

DGV is the GlobalValue in the destination Module, it is not clear to me how materializing has an effect on the source Module.
I am probably missing something here…

Even with the extra cost of the hack above - this has resulted in a 2x speedup in our total link time.

So really here I am wondering - is this expected behaviour? A bug? And if so how best to go about fixing the issue would be some grand advice from people more in the know!

The linker was written before Module was lazy loaded I think. Many pieces in LLVM assume things their working on are materialized.
On a side note (a bit off-topic), I wonder if isDeclaration() should return false for materializable function?

CC Rafael, who knows this code better.

teresajohnson · April 20, 2016, 6:02pm

+cc Artem, who added the LinkOnlyNeeded flag.

Hi Neil,

TL;DR - when linking from a lazily loaded module and using
Linker::LinkOnlyNeeded, bodies of used functions aren't being copied during
linking.

Previously on one of our products, we would lazily load our runtime module
(around 9000 functions), and link some user module into this (which is in
all practical use cases much smaller).

It sounds reverse to what I would intuitively do (i.e. load the runtime
into my module).

Then, post linking, we have a pass that runs over the module and rips out
all the un-materialized functions that weren't being used in the original
user module.

I only just noticed that LinkModules has a flags parameter that can take a
LinkOnlyNeeded flag, which made me wonder if I could reverse the link order
(EG. link from the lazily loaded runtime module into the user module), set
the LinkOnlyNeeded flag, and hey presto, we wouldn't need to have a cleanup
pass that ran afterwards ripping out functions that weren't used.

So I tried it, and it failed. Basically any function that was still to be
materialized wasn't getting its body copied over during linking.

The only line of code that differs when you set LinkOnlyNeeded is in
LinkModules.cpp -> ModuleLinker::linkIfNeeded:

if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
    return false;

The isDeclaration() for functions has a call to isMaterializable().

Things I've tried:

   - If I don't pass LinkOnlyNeeded but still link from the lazily loaded
   runtime module into the user module, it works (albeit it is orders of
   magnitude slower like we'd expect).
   - If I don't lazily load the runtime module, it works (but again, much
   slower).
   - I tried doing the linking and then materializing the newly linked
   module, but the runtime functions were still missing their bodies (which
   implies the information was lost during linking).
   - If I hack the LinkModules.cpp code such that it checks if the DGV
   could be materialized, and if so materialize it, before checking for a
   declaration again, it works:

if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration())) {
    if (DGV && DGV->isMaterializable())
        DGV->materialize();

    if (!(DGV && DGV->isDeclaration()))
        return false;
}

DGV is the GlobalValue in the *destination* Module, it is not clear to me
how materializing has an effect on the *source* Module.
I am probably missing something here...

I think the difference here is that the destination module is being lazy
loaded, whereas I typically see the source modules being lazily loaded. So
it sounds like the issue is that DGV has not *yet* been materialized in the
dest module, and therefore DGV->isDeclaration() is returning false, leading
the linkIfNeeded to return false, despite the fact that if we did
materialize DGV it would be a declaration and would decide to link in SGV.

Not sure that this usage mode of lazy loading has been tested before. As
Mehdi says, Rafael may have more insight.

Teresa

mehdi_amini · April 20, 2016, 6:07pm

I understood from his description that he reversed the destination and source so that destination is the user code.
I assumed it was not lazy loaded, but that would explain the question then

Neil: can you clarify? If Teresa is right, why aren’t you materializing the destination module entirely?

Oh I thought only function definition could be materializable, not declaration?

Even materializing functions from the source module on the fly isn’t supported right now, is it?

Rafael_Avila_de_Espi · April 20, 2016, 7:28pm

I understood from his description that he reversed the destination and
source so that destination is the user code.
I assumed it was not lazy loaded, but that would explain the question then

Neil: can you clarify? If Teresa is right, why aren't you materializing
the destination module entirely?

I don't think it has ever been tried to use a lazy destination. Having said
that, I don't think isMaterializable should return true for a declaration.

Even materializing functions from the source module on the fly isn't
supported right now, is it?

It is.

Neil, the flag is linked to llvm-link's -only-needed command line option.
At least for simple cases it seems to be working. Given

declare void @g()
define void @f() {
call void @g()
ret void
}

and

define void @g() {
ret void
}
define void @h() {
ret void
}

linking with "llvm-link -only-needed test1.bc test2.bc" will bring in g,
but not h. Can you write a testcase showing what you were expecting it to
do but it is not?

Cheers,
Rafael

teresajohnson · April 20, 2016, 7:39pm

I understood from his description that he reversed the destination and
source so that destination is the user code.
I assumed it was not lazy loaded, but that would explain the question
then

Neil: can you clarify? If Teresa is right, why aren't you materializing
the destination module entirely?

I don't think it has ever been tried to use a lazy destination. Having
said that, I don't think isMaterializable should return true for a
declaration.

Looking at isMaterializable, I'm now a little confused about Neil's case -
the materializable bit is set to true only when the MODULE_CODE_FUNCTION
indicated that it was !isproto, which means it should have a definition in
that module. So I agree with you that isMaterializable shouldn't be
returning true when the symbol is only available as a declaration.

Neil - what case are you trying to handle here? If there is a
materializable definition in the dest module, wouldn't you want to use that
instead of linking one in from the source module?

Teresa

Neil_Henning · April 21, 2016, 9:18am

Hey all,

For LinkModules, dest is a fully materialized module, src is a lazily loaded module.

From what I understood, getLinkedToGlobal() is finding the function in src that matches some function declaration in dest, and given that src is lazily loaded it could be un-materialized.

The functions I need brought in from src into dest are always declarations in dest. The problem is that (for some reason) the combination of Linker::LinkOnlyNeeded and a function that is not materialized will not copy the function body from src into dest.

Cheers,
-Neil.

Neil_Henning · April 21, 2016, 10:40am

So (post morning-coffee) - I did some more digging.

It seems that it will correctly bring over a function from src that is explicitly called in dest, but it won’t bring over any functions that are called by a src function from another src function.

I may have dug too deep in the rabbit hole when blaming lazily loaded modules for the fault - is it perhaps as simple as LinkOnlyNeeded does not work when importing a function that calls another function?

-Neil.

teresajohnson · April 21, 2016, 12:57pm

Hey all,

For LinkModules, *dest* is a fully materialized module, *src* is a lazily
loaded module.

It's not clear to me then why your change to materialize the dest copy is
helping then.

From what I understood, getLinkedToGlobal() is finding the function in
*src* that matches some function declaration in *dest*, and given that
*src* is lazily loaded it could be un-materialized.

It does the reverse (finds function in dest that matches function in src):

  /// Given a global in the source module, return the global in the
  /// destination module that is being linked to, if any.
  GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {

The functions I need brought in from *src* into *dest* are always

declarations in *dest*. The problem is that (for some reason) the
combination of Linker::LinkOnlyNeeded and a function that is not
materialized will not copy the function body from *src* into *dest*.

From your subsequent email:
So (post morning-coffee) - I did some more digging.

It seems that it will correctly bring over a function from *src* that is

explicitly called in *dest*, but it won't bring over any functions

that are called by a *src* function from another *src *function.
I may have dug too deep in the rabbit hole when blaming lazily loaded

modules for the fault - is it perhaps as simple as

LinkOnlyNeeded does not work when importing a function that calls another

function?

So in that case linkIfNeeded will return false since you have
LinkOnlyNeeded and there is no declaration in the dest module (it isn't
needed by the dest module). I'm not completely sure what should happen here
with LinkOnlyNeeded. There is handling in the IRMover to lazily add
references to link that are encountered when copying over bodies, however,
this only happens when the reference value is LinkOnce (since it could be
discarded in the source module). It may be that in the case LinkOnlyNeeded
is designed for this functionality wasn't needed - it was specific to a
special situation in linking CUDA, see http://reviews.llvm.org/D12459. I'm
guessing to handle your case you would want to change
ModuleLinker::addLazyFor() to be more aggressive in the LinkOnlyNeeded case.

Teresa

Rafael_Avila_de_Espi · April 21, 2016, 2:29pm

I can reproduce that. Taking a look.

Cheers,
Rafael

Rafael_Avila_de_Espi · April 21, 2016, 3:06pm

So in that case linkIfNeeded will return false since you have LinkOnlyNeeded and there is no declaration in the dest module (it isn't needed by the dest module). I'm not completely sure what should happen here with LinkOnlyNeeded. There is handling in the IRMover to lazily add references to link that are encountered when copying over bodies, however, this only happens when the reference value is LinkOnce (since it could be discarded in the source module). It may be that in the case LinkOnlyNeeded is designed for this functionality wasn't needed - it was specific to a special situation in linking CUDA, see http://reviews.llvm.org/D12459. I'm guessing to handle your case you would want to change ModuleLinker::addLazyFor() to be more aggressive in the LinkOnlyNeeded case.

Yes, that was the problem.

Fixed in r266995. Neil, can you give that a try?

Cheers,
Rafael