This is an archive of the discontinued LLVM Phabricator instance.

[ThinLTO] - Stop internalizing and drop non-prevailing symbols.
ClosedPublic

Authored by grimar on Jan 16 2018, 7:48 AM.

Details

Summary

Implementation marks non-prevailing symbols as not live in the summary.
Then them are dropped in backends.

Diff Detail

Repository
rL LLVM

Event Timeline

grimar created this revision.Jan 16 2018, 7:48 AM

@grimar Can't internalization be skipped during backend processing rather than changing linkage in summary index?. At the very first glance it is possible to check if def is prevailing or not in MustPreserveGV (see thinLTOInternalizeModule)

grimar planned changes to this revision.Jan 17 2018, 8:28 AM

@grimar Can't internalization be skipped during backend processing rather than changing linkage in summary index?. At the very first glance it is possible to check if def is prevailing or not in MustPreserveGV (see thinLTOInternalizeModule)

Investigating this. Hope to update patch tomorrow.

@grimar Can't internalization be skipped during backend processing rather than changing linkage in summary index?. At the very first glance it is possible to check if def is prevailing or not in MustPreserveGV (see thinLTOInternalizeModule)

We don't have linker info in the backends, so that code is just looking at what was recorded in the index during the thin link (where we have the linker info).

lib/LTO/LTO.cpp
337 ↗(On Diff #129955)

We also need to change importing to not allow import of a non-prevailing symbol. Then this patch should be changed to assert if it was non-prevailing but exported.

@tejohnson Can't we use ThinLTO.PrevailingModuleForGUID in the backend?

@tejohnson Can't we use ThinLTO.PrevailingModuleForGUID in the backend?

No - we communicate via the index to support distributed ThinLTO backends.

To drop non-prevailing symbols completely in the backends, as discussed in D41988, we will need to either add a bit to the summary flags, or possibly we can utilize the isLive flag (which currently is only used to communicate from the compile step through the thin link (to perform whole program DCE). Right now we mark dead symbols in the index with internal linkage and rely on the back end to update the linkage (in the code you were looking at) and then GlobalDCE to remove them. We can handle the dropping of non-prevailing and globally dead symbols the same way perhaps - mark as not live in the summary and have a mechanism to just drop them without going through internalization etc.

To drop non-prevailing symbols completely in the backends, as discussed in D41988, we will need to either add a bit to the summary flags, or possibly we can utilize the isLive flag (which currently is only used to communicate from the compile step through the thin link (to perform whole program DCE). Right now we mark dead symbols in the index with internal linkage and rely on the back end to update the linkage (in the code you were looking at) and then GlobalDCE to remove them. We can handle the dropping of non-prevailing and globally dead symbols the same way perhaps - mark as not live in the summary and have a mechanism to just drop them without going through internalization etc.

I am trying to implement this (hope I am doing right thing).
This approach looks better atm, though patch is not yet finished, I have 3 testcases failing atm, working on them:

LLVM :: LTO/Resolution/X86/comdat-mixed-lto.ll
LLVM :: LTO/Resolution/X86/lowertypetests.ll
LLVM :: LTO/Resolution/X86/setting-dso-local.ll

Going to upload current WIP version I have in a few minutes and continue tomorrow.

grimar updated this revision to Diff 130424.Jan 18 2018, 8:52 AM
  • WIP version that tries to leave non-prevealing symbols as dead and then drop them in backend.
grimar planned changes to this revision.Jan 18 2018, 8:53 AM

Not finished, so planning update after fixing tests.

grimar updated this revision to Diff 130612.Jan 19 2018, 6:57 AM
grimar retitled this revision from [ThinLTO] - Stop internalizing non-prevailing symbols. to [ThinLTO] - Stop internalizing and drop non-prevailing symbols..
grimar edited the summary of this revision. (Show Details)
  • Finished implementation. Now all LLD\LTO and llvm\test\LTO tests pass.

Implementation marks non-prevailing symbols as "dead" in the summary.
And then drops them in backend.

tejohnson added inline comments.Jan 19 2018, 9:59 AM
include/llvm/Transforms/IPO/FunctionImport.h
113 ↗(On Diff #130612)

s/isPrevaling/isPrevailing/

113 ↗(On Diff #130612)

Clarify that non-prevailing means that the prevailing copy is not anywhere in IR. I.e as opposed to the non-prevailing copy which has a prevailing copy in another bitcode module. In that case we won't drop, which is fine for the purposes of this bug.

116 ↗(On Diff #130612)

s/isPrevaling/isPrevailing/

lib/LTO/ThinLTOCodeGenerator.cpp
626 ↗(On Diff #130612)

I guess this is because we don't have linker resolution info. Not sure what ld64 does if it has the same situation. Maybe add a comment that this interface can't do any better in the case where the prevailing symbol is in a native object because it doesn't provide linker info?

649 ↗(On Diff #130612)

suggest keeping the original name, which should be fine since it will just get overloaded. it matches the comment and the behavior better.

lib/Transforms/IPO/FunctionImport.cpp
501 ↗(On Diff #130612)

s/isPrevaling/isPrevailing/

501 ↗(On Diff #130612)

Add comment about what bool represents.

546 ↗(On Diff #130612)

s/isPrevaling/isPrevailing/

546 ↗(On Diff #130612)

Unclear to me what is going on here and why IsLiveRoot needs to be tracked and passed down (its more like "is this reached via a live root", so maybe ReachedByLiveRoot?). What does it mean for something to be a live root but not prevailing, which seems to be the case requiring these changes?

564 ↗(On Diff #130612)

Interesting - is this a bug that was there before? It seems like an oversight not to have done this before. Or is it necessitated by your changes? If a separate bug, would be better to commit this separately.

565 ↗(On Diff #130612)

Don't even need to check if Summary is an alias. Just set Base live unconditionally - either it is the aliasee or equal to Summary.

631 ↗(On Diff #130612)

I think this is a hole. I.e. if the non-prevailing symbol is an alias, we can still do the incorrect internalization/inlining, right? Ok to fix in a follow-on patch though.

grimar updated this revision to Diff 130915.Jan 22 2018, 9:22 AM
grimar marked 12 inline comments as done.
  • Addressed review comments.
lib/LTO/ThinLTOCodeGenerator.cpp
626 ↗(On Diff #130612)

Yes, we do not have resolution info. It is consistent with:
https://github.com/llvm-mirror/llvm/blob/master/lib/LTO/ThinLTOCodeGenerator.cpp#L500
code, which also do assumptions about resolution.

Updated the comment.

649 ↗(On Diff #130612)

It needs either defining new static helper in llvm namespace too (where main computeDeadSymbols lives),
so it would overload it, or using ::computeDeadSymbols syntax for calls.
I did latter in this diff, though I am not sure it looks nice/consistent with usual LLVM code.

May be we could rename the helper to something like stripDeadSymbols or doSummaryBasedGC
or computeDeadSymbolsInSummary instead ?

lib/Transforms/IPO/FunctionImport.cpp
501 ↗(On Diff #130612)

Updated comment for computeDeadSymbols with description of isPrevailing return value.

546 ↗(On Diff #130612)

Yes, ReachedByLiveRoot describes the intention better. I did it for comdat-mixed-lto.ll case:
https://github.com/llvm-mirror/llvm/blob/master/test/LTO/Resolution/X86/comdat-mixed-lto.ll

Otherwise it would drop __cxx_global_var_init which is @llvm.global_ctors.
Linker does not know about these symbols and I had to preserve them somehow.
It seems simple solution which should work for now, what do you think ?

564 ↗(On Diff #130612)

Bug was before, currently Aliasee does not get Live flag, while Alias does.
But does not seem there is some logic broken because of that.

For example following code used to compute imports:
https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/FunctionImport.cpp#L354
And I can observe for example how isGlobalValueLive skips GV which should be live,
but anyways it proccessed because it's alias is in the list too.
At the same time isGlobalValueLive checks Live flag of alias GVS, find it was set and then use getBaseObject to
continue work with aliasee right below.
I tried to create some test case to show where current logic is broken, but had no success.

I was need this change because introduced dropDeadSymbols which iterates over DefinedGlobals and can drop aliasee
which was not marked as live. It happens in lowertypetests.ll testcase.

631 ↗(On Diff #130612)

I'll investigate this case separatelly.

tejohnson accepted this revision.Jan 22 2018, 5:07 PM

LGTM. Just a few minor suggestions below.

include/llvm/Transforms/IPO/FunctionImport.h
112 ↗(On Diff #130915)

s/anywere/anywhere/

114 ↗(On Diff #130915)

s/has no any/has no/

lib/LTO/ThinLTOCodeGenerator.cpp
649 ↗(On Diff #130612)

I see. Maybe computeDeadSymbolsInIndex then.

lib/Transforms/IPO/FunctionImport.cpp
501 ↗(On Diff #130612)

I meant on the declaration of Worklist (the bool in the pair). It would be good to have a comment there indicating what the bool represents (i.e. whether it was reached by a value marked as a live root in the summary).

546 ↗(On Diff #130612)

Ok, just add a comment that values already marked as live roots in the summary are typically llvm internal global values that the linker doesn't know about, therefore we can't look at whether the linker decided it was prevailing.

564 ↗(On Diff #130612)

Ok, I think I can see why that wouldn't manifest as an issue before.

This revision is now accepted and ready to land.Jan 22 2018, 5:07 PM
grimar planned changes to this revision.Jan 23 2018, 1:32 AM
grimar marked 2 inline comments as done.

Thanks for your comments, Teresa !
I am sorry, unfortunately I was not aware that ThinLTO has testcases in llvm/test/ThinLTO,
and not only in llvm/test/LTO. After running check-llvm I see few more testcases
failtures and going to investigate them now.

grimar updated this revision to Diff 131223.Jan 24 2018, 4:46 AM
  • Addressed comments.
  • Updated patch to fix previously broken tests.

Now both check-llvm, and check-llvm-tools-gold pass.

Main change to fix testcases was following.
I had to check isDSOLocal in computeDeadSymbols and keep DSOLocal
symbols to be live. An example where it needed:
\test\ThinLTO\X86\deadstrip.ll
(https://github.com/llvm-mirror/llvm/blob/master/test/ThinLTO/X86/deadstrip.ll#L116)
it has bar_internal which is reachable but not prevailing. Linker does not see them.

Comments on other testcases changes:

  1. \test\ThinLTO\X86\deadstrip.ll: define was changed to declare because dead_func is dead, was dropped and converted to declaration.
  2. \test\ThinLTO\X86\internalize.ll: bar and linkonce_func were unreachable and were dropped. Made them be reachable.
  3. test\tools\gold\X86\global_with_section.ll: changes caused by converting dead dropped things to declarations.
This revision is now accepted and ready to land.Jan 24 2018, 4:46 AM
grimar requested review of this revision.Jan 24 2018, 4:46 AM
grimar updated this revision to Diff 131416.Jan 25 2018, 4:33 AM
  • Changed implementation as suggested (introduced enum for prevailing status).
grimar updated this revision to Diff 131447.Jan 25 2018, 7:13 AM
  • Fixed broken comment.
tejohnson accepted this revision.Jan 25 2018, 7:54 AM

LGTM with minor comment nit and missing change noted below.
Thanks - this looks cleaner using the enum!

include/llvm/Transforms/IPO/FunctionImport.h
117 ↗(On Diff #131447)

Suggest changing "that are not anywhere in IR are normally dead" to something like "are symbols without a prevailing copy anywhere in IR and are normally dead". I.e. a non-prevailing symbol here can have a def in IR, it is just not prevailing.

lib/Transforms/IPO/FunctionImport.cpp
501 ↗(On Diff #131447)

I think you lost the corresponding change to the header declaration in this version of the patch.

This revision is now accepted and ready to land.Jan 25 2018, 7:54 AM
grimar updated this revision to Diff 131473.Jan 25 2018, 10:03 AM
grimar marked an inline comment as done.

Thanks, Teresa !

Addressed last comments, rebased after rL323444,
and going to commit this in my tomorrow
(want to watch for bots to ensure all of them are happy).

include/llvm/Transforms/IPO/FunctionImport.h
117 ↗(On Diff #131447)

Done.

lib/Transforms/IPO/FunctionImport.cpp
501 ↗(On Diff #131447)

I think it is still there, right below text change you suggested :)

/// Compute all the symbols that are "dead": i.e these that can't be reached
/// in the graph from any of the given symbols listed in
/// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a
/// prevailing copy anywhere in IR and are normally dead, \p isPrevailing
/// predicate returns status of symbol.

I removed comment done on the declaration of Worklist though, because after introducing enum
that part of code was reverted to original and there is no more pair with bool.

(Note that the change to the declaration of computeDeadSymbols in ModuleSummaryIndex.h is still missing from the uploaded version of the patch)

(Note that the change to the declaration of computeDeadSymbols in ModuleSummaryIndex.h is still missing from the uploaded version of the patch)

Ah, now I see what you mean. It was eliminated earlier in rL323415.

grimar updated this revision to Diff 131584.Jan 26 2018, 7:12 AM
  • Fixed issue with symbols from "module asm" blocks.

No worries - I have done the same thing myself (broken lld bots with LTO changes since I don't always run them before commit).

lib/LTO/LTO.cpp
430 ↗(On Diff #131584)

This assumes that the non-prevailing asm symbol with the name is seen here before the prevailing symbol without a name (which does always seem to currently be the case). Otherwise, the non-prevailing symbol would come along and fill in the name since it will be empty. Suggest moving this block up above the previous one that sets the Prevailing flag, then add an assert that if !Sym.getIRName.empty() that Res.Prevailing is not already true. I.e. that we don't overwrite the IRName when we already set it from the Prevailing copy.

grimar added inline comments.Jan 27 2018, 1:44 AM
lib/LTO/LTO.cpp
430 ↗(On Diff #131584)

Yes, currently in a single module asm symbols looks always placed before IR ones seems.
But unfortunately asserting would also be not enough for case when we have multiple modules.

If we have 2 modules, where

  • Module A has both asm and IR symbol foo:
    1. Prevailing, IRName="" (asm)
    2. Non-prevailing, IRName="foo" (IR)
  • Module B with non-prevailing, IRName="foo".

it would not work, because handing of resolution from module B would trigger assertion failture.
I extended LLD testcase to catch this case too in rL323584.

Seems what we can do is never update IRName if symbol is already known to be prevailing (so always prefer IR name of prevailing symbol).
Will update patch with such change.

grimar updated this revision to Diff 131680.Jan 27 2018, 1:47 AM
  • Updated in according to latest comments.
tejohnson accepted this revision.Jan 27 2018, 7:45 AM

LGTM with 2 minor suggestions.

lib/LTO/LTO.cpp
432 ↗(On Diff #131680)

add something like "Otherwise, if we haven't seen a prevailing symbol, set the name so that we can later use it to check if there is any prevailing copy in IR."

433 ↗(On Diff #131680)

merge this into the else if condition

This revision was automatically updated to reflect the committed changes.