This is an archive of the discontinued LLVM Phabricator instance.

ThinLTO: special handling for LinkOnce functions
ClosedPublic

Authored by mehdi_amini on Mar 22 2016, 3:06 AM.

Details

Reviewers
tejohnson
Summary

These function can be dropped by the compiler if they are no longer
referenced in the current module. However there is a change that
another module is still referencing them because of the import.

Multiple solutions can be used:

  • Always import LinkOnce when a caller is imported. This ensure that every module with a call to a LinkOnce has the definition and will be able to emit it if it emits the call.
  • Turn the LinkOnce into Weak, so that it is always emitted.
  • Turn all LinkOnce into available_externally and come back after all modules are codegen'ed to emit only one copy of the linkonce, when there is still a reference to it.

This patch implement the second option, with am optimization that
only *one* module will turn the LinkOnce into Weak, while the others
will turn it into available_externally, so that there is exactly one
copy emitted for the whole compilation.

Diff Detail

Event Timeline

mehdi_amini retitled this revision from to ThinLTO: special handling for LinkOnce functions.
mehdi_amini updated this object.
mehdi_amini added a reviewer: tejohnson.
mehdi_amini added a subscriber: llvm-commits.
tejohnson edited edge metadata.Mar 28 2016, 8:29 PM

Always import LinkOnce when a caller is imported. This ensure that every module with a call to a LinkOnce has the definition and will be able to emit it if it emits the call.

Note that this first approach already happens when using the ModuleLinker (as the function import pass does): referenced linkonce are added to the ValuesToLink via a callback. Which is required for correctness if we end up with any linkonce. But this is an optimization to avoid needing to force import those referenced linkonce.

And this patch also reduces the amount of weak functions kept through codegen (summary should probably reflect that it is modifying weak as well).

lib/LTO/ThinLTOCodeGenerator.cpp
121

Routine is handling more than just linkonce but also weak. Name of this routine and the following one needs to change to reflect broader scope. How about something like "ResolveWeakAndLinkOnce"?

161

This block is almost identical to above, fold the cases together and just select the right Weak linkage?

185

Ditto here, this block can be folded with the above, it is identical.

198

Not really for correctness, as the IRMover will pull in any referenced linkonce defs. This is an optimization to reduce required importing though.

Also, they aren't all being converted to weak ODR, only one and the others are available_externally.

208

Yes I think so

306

More explanatory comment needed.

307

Specify in what way.

mehdi_amini added inline comments.Mar 28 2016, 8:51 PM
lib/LTO/ThinLTOCodeGenerator.cpp
208

I'm just not sure how to handled them...

307

Yeah, this was mostly a "note to myself".
This is discussed in the caching patch D18494. I'll remove it from here.

Couple more comments:

  • needs test
  • can this be moved out of LTOCodeGenerator so that it can be invoked from other paths (e.g. gold)? Maybe into FunctionImportUtils.cpp?

I'm surprised you want to use this from the gold plugin, the linker already did the resolution for you. Here I'm using the summary because we don't have an API to interact with the inker.

In D18346#386449, @joker.eph wrote:

I'm surprised you want to use this from the gold plugin, the linker already did the resolution for you. Here I'm using the summary because we don't have an API to interact with the inker.

Right, I forgot about the fact that when the backend threads are launched through the gold plugin that it will already make it weak. Gold isn't marking the others available externally, but that should be a simple change.

Where I will want to do something like this is in the distributed build case, where we don't go through the symbol resolution in gold. However, there I will need to mark the change in the combined index and have the backend actually change the symbol linkage based on what is in the index. In that case I would need to refactor this anyway since we don't have an actual GlobalValue, just the summary entries. I can do that myself when I am ready to leverage it.

Right, I forgot about the fact that when the backend threads are launched through the gold plugin that it will already make it weak.

I didn't write this very clearly. It will already mark the *prevailing copy* weak if it is linkonce.

tejohnson added inline comments.Mar 31 2016, 11:13 AM
lib/LTO/ThinLTOCodeGenerator.cpp
182

Thinking more about this - I don't think it is correct for WeakAny or LinkOnceAny to be converted to AvailableExternally. This could change the program result. The reason is that the selected copy is allowed to have different behavior than the unselected version. This is why WeakAny and LinkOnceAny return true from GlobalValue::mayBeOverridden(), which prevents optimizations such as inlining and therefore ensures that the linker-selected copy is executed. Changing their linkage to AvailableExternally enables the unselected versions to be inlined, and therefore the selected body is not executed at runtime, which can result in different program behavior.

mehdi_amini added inline comments.Mar 31 2016, 1:00 PM
lib/LTO/ThinLTOCodeGenerator.cpp
182

Yeah that's a very good catch.

It lead me to a more interesting point: if we know which copy the linker will select, we should turn it into a strong definition and *eliminate* all the other. This way the strong one will be imported and could be inlined where it usually can't. I imagine gold is already doing that in LTO.

182

Maybe we can't turn a weak into a strong, because the dynamic loader can override it with another symbol in another library?

tejohnson added inline comments.Mar 31 2016, 1:33 PM
lib/LTO/ThinLTOCodeGenerator.cpp
182

In LTO mode gold will simply internalize the prevailing copy and the rest get dropped during merging.

What you can do in the non-ODR case is to keep (via weak linkage as you are here) the first copy, and drop the definitions for the other copies (instead of converting them to avail externally). That way the remaining weak copy can still be overridden if necessary by a strong def in another library.

See D18674 for related gold changes.

mehdi_amini added inline comments.Mar 31 2016, 1:44 PM
lib/LTO/ThinLTOCodeGenerator.cpp
182

Makes me think: Is there any interest in importing a weak def somewhere else?
If it is the prevailing copy and we can turn it to a strong def, then yes, otherwise there is not much interest.

tejohnson added inline comments.Mar 31 2016, 1:48 PM
lib/LTO/ThinLTOCodeGenerator.cpp
182

I'm not sure how common or hot non-overridden weak symbols are in practice. But yes, if we knew it was prevailing (as gold does) then I believe this could be done. But you need the linker to tell you it is the prevailing copy (not just select the first one seen as here).

mehdi_amini added inline comments.Mar 31 2016, 1:51 PM
lib/LTO/ThinLTOCodeGenerator.cpp
182

I don't know the exact definition of a "prevailing copy"?
If it is only the copy that the linker will put in the final binary, then I don't think it is enough for a weak, because you also need to be sure it can't be overridden by a strong definition by the dynamic loader.

tejohnson added inline comments.Mar 31 2016, 2:02 PM
lib/LTO/ThinLTOCodeGenerator.cpp
182

I'm not a gold expert, however, given the fact that for LTO the gold-plugin is internalizing the prevailing copy, I would assume that is a guarantee that it will not be overridden elsewhere.

mehdi_amini updated this revision to Diff 52338.Apr 1 2016, 2:02 AM
mehdi_amini edited edge metadata.

Address comment, add a test.

In D18346#389223, @joker.eph wrote:

Address comment, add a test.

I don't see test, can you try to add again?

lib/LTO/ThinLTOCodeGenerator.cpp
174

Clang format

306

and WeakODR

Submitted comments too early - here is the other one...

lib/LTO/ThinLTOCodeGenerator.cpp
217

Alias cannot be available_externally (see GlobalAlias::isValidLinkage), so I think for those you while you should do the change of the first copy to weak, the rest need to be left as-is.

Also, it just occurred to me that this is going to be an issue for the aliasee - since aliases must point to a definition, an aliasee cannot become available_externally either. You might have to do some analysis first to see which GV are aliasees and skip the available_externally part for those too.

You can include these cases in your test.

Update disable the optimization for aliases

I still don't see the test, can you update a new patch with that included?

lib/LTO/ThinLTOCodeGenerator.cpp
176

s/in a/into a/

190

You can still do the conversion of linkonceodr -> weakodr for the first definition, including for aliases themselves. So you could instead continue to call ResolveODR but pass in the new set and just skip the available externally resetting (you'd have to add the aliases themselves to the set as well).

"git add test/" before commit

mehdi_amini added inline comments.Apr 1 2016, 12:38 PM
lib/LTO/ThinLTOCodeGenerator.cpp
190

Yeah, but I'd prefer to have the "real" solution we discussed instead of an intermediate one, keeping a limited/conservative behavior in presence of aliases for now.

tejohnson accepted this revision.Apr 1 2016, 12:51 PM
tejohnson edited edge metadata.
tejohnson added inline comments.
lib/LTO/ThinLTOCodeGenerator.cpp
190

Ok, that's fine. Note as an aside that the gold plugin is already doing the linkonce->weak transformation for the prevailing copy, but was motivated by correctness reasons (see D16173 - the preempted copies will get dropped, and since this isn't full LTO the backend doesn't see all references and may otherwise drop the prevailing linkonce copy). Note also that in the future you could do linkonce(any)->weak(any), just not the avail externally part for the non-odr.

This revision is now accepted and ready to land.Apr 1 2016, 12:51 PM
mehdi_amini closed this revision.Apr 1 2016, 8:44 PM