llvm dev - Apr 2016 - Lazily Loaded Modules and Linker::LinkOnlyNeeded

+cc Artem, who added the LinkOnlyNeeded flag.

On Wed, Apr 20, 2016 at 9:18 AM, Mehdi Amini via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi Neil,
>
> On Apr 20, 2016, at 5:20 AM, Neil Henning via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> 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
>
> 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.
>
> --
> Mehdi
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>

-- 
Teresa Johnson |  Software Engineer |  tejohnson at google.com |  408-460-2413
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/5b65e1a5/attachment.html>

> On Apr 20, 2016, at 11:02 AM, Teresa Johnson <tejohnson at
google.com> wrote:
> 
> 
> +cc Artem, who added the LinkOnlyNeeded flag.
> 
> On Wed, Apr 20, 2016 at 9:18 AM, Mehdi Amini via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> Hi Neil,
> 
>> On Apr 20, 2016, at 5:20 AM, Neil Henning via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> 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.
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?
> 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.
Oh I thought only function definition could be materializable, not declaration?
> Not sure that this usage mode of lazy loading has been tested before. As
Mehdi says, Rafael may have more insight.
Even materializing functions from the source module on the fly isn't
supported right now, is it?

-- 
Mehdi

> 
> Teresa
> 
>> 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.
> 
> -- 
> Mehdi
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> 
> 
> -- 
> Teresa Johnson |	 Software Engineer |	 tejohnson at google.com
<mailto:tejohnson at google.com> |	 408-460-2413
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/e63641c3/attachment.html>

>
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/8a762cfa/attachment.html>