ThinLTO: add early "dead-stripping" on the Index

[tejohnson]

Summary

Using the linker-supplied list of "preserved" symbols, we can compute
the list of "dead" symbols, i.e. the one that are not reachable from
a "preserved" symbol transitively on the reference graph.
Right now we are using this information to mark these functions as
non-eligible for import.

The impact is two folds:

• Reduction of compile time: we don't import these functions anywhere or import the function these symbols are calling.
• The limited number of import/export leads to better internalization.

[tejohnson]

include/llvm/Transforms/IPO/FunctionImport.h

98 ↗

(On Diff #67971)

Please also add this handling to LTO.cpp so that the optimization is available for all client linkers. As a bonus, then DeadSymbols doesn't need ot be optional. For LTO.cpp, the set of preserved GUIDs is currently computed just below the call to ComputeCrossModuleImport as ExportedGUIDs, and can simply be moved up so that it can be passed to computeDeadSymbols.

Alternatively, do we want to instead pass in the set of preserved GUIDs to ComputeCrossModuleImport and invoke computeDeadSymbols there, or do we anticipate that there will be other uses outside of ComptueCrossModuleImport? If not, then I think it is cleaner to do the dead symbol computation there.

lib/LTO/ThinLTOCodeGenerator.cpp

529 ↗

(On Diff #67971)

There are now a bunch of duplicated copies of the same sequence in this source file: collectDefinedGVSummariesPerModule, computeGUIDPreservedSymbols, computeDeadSymbols, ComputeCrossModuleImport. Probably time to refactor this sequence into a helper? Ok as a follow-on patch if you prefer though.

lib/Transforms/IPO/FunctionImport.cpp

467 ↗

(On Diff #67971)

Do you mean we should only make the prevailing copy's references live here?

This should be pretty straightforward, just pull out the detection of prevailing copies from resolveWeakForLinkerInIndex and pass in a callback. For LTO.cpp, the isPrevailing lambda definition is just below the call to ComputeCrossModuleImport and could be moved up. Ok as a follow on patch though.

473 ↗

(On Diff #67971)

Why emit the referenced GUID twice here and in the below loop, rather than just once with the default type (which is already uint64_t so first cast unnecessary).

test/ThinLTO/X86/deadstrip.ll

15 ↗

(On Diff #67971)

Might want to add that bar* are dead because they should have been inlined into main.

[mehdi_amini]

Add support in the new LTO API

[mehdi_amini]

include/llvm/Transforms/IPO/FunctionImport.h

98 ↗

(On Diff #68788)

I tried moved the computation to ComputeCrossModuleImport. But if you look at LTO.cpp runThinLTO() we reuse the DeadSymbols set for the lambda isExported used as a callback for thinLTOInternalizeAndPromoteInIndex

lib/LTO/ThinLTOCodeGenerator.cpp

529 ↗

(On Diff #68788)

The move to the new API should fix it!

lib/Transforms/IPO/FunctionImport.cpp

467 ↗

(On Diff #68788)

I tried to do it, but figure it'll be easy after the ThinLTOCodeGenerator is moved the new API, so I don't have multiple call sites to convert to pass a lambda, so I'll leave it for a future patch :)

473 ↗

(On Diff #68788)

That was just debugging.

[mehdi_amini]

Address comments

[mehdi_amini]

clang-format

[tejohnson]

lib/LTO/LTO.cpp

200 ↗

(On Diff #68868)

This should be:

GlobalRes.VisibleToRegularObj |= Res.VisibleToRegularObj;

with that fix the gold tests pass.

201 ↗

(On Diff #68868)

New braces around else block not needed

603 ↗

(On Diff #68868)

If a symbol is in ExportedGUIDs, wouldn't it necessarily also be in GUIDPreservedSymbols and therefore not dead (if it is VisibleToRegularObj the partition would also have been set to External). So do we even need the ExportedGUIDs check here? And if not, do we need to compute it?

test/ThinLTO/X86/deadstrip.ll

18 ↗

(On Diff #68868)

Should be %t.out.1.3.import.bc

[tejohnson]

3 of the spec cpu2006 benchmarks also fail due to undefined refs.

[mehdi_amini]

Address comments, thanks!

[mehdi_amini]

Forgot to commit the test fix...

[tejohnson]

Unfortunately the spec linking failures were with the fix to VisibleInRegularObj, so will still need to dig into those.

lib/LTO/LTO.cpp

673 ↗

(On Diff #69198)

Think this is dead now.

[tejohnson]

Taking this over as discussed last week on IRC. Have an updated patch and some analysis to add to it.

[tejohnson]

Updated patch.
All invocations of IsExported should check that:

(!DeadSymbols.count(GUID) && ExportedGUIDs.count(GUID))

I had earlier suggested that we only needed to check that !DeadSymbols,
but this is wrong and was detected when I fixed the llvm-lto2 based
test (which was previously not actually checking the output).
I also updated the IsExported lambdas in ThinLTOCodeGenerator.cpp
to use the same test, so that DeadSymbols are filtered out, otherwise
the benefit would not be seen there.

There are still correctness issues, which I will send an update on shortly.

[tejohnson]

This is getting undefined references in the link of the SPEC C++ apps. Looking at one of the cases, it is caused by incorrectly determining that some references are dead when in fact they have a reference via the llvm.global_ctors variable. The index correctly reflects the chain of references starting at the llvm.global_ctors variable.

However, this symbol is never processed by the symbol resolution handling because it is skipped when looking for symbols in InputFile::Symbol::shouldSkip() - this is because while it is flagged as SF_Global, it is also flagged as SF_FormatSpecific (anything starting with "llvm." is in ModuleSymbolTable::getSymbolFlags (this is not new logic, although it was moved here recently). (Changing the InputFile to not skip this causes issues because the linker doesn't know the semantics of this special appending variable and complains about dup symbols.)

It seems like we need to add anything referenced from at least some of these "FormatSpecific" values as they are potential roots in the dead symbol analysis. The best way I can think of off the top of my head is to write a special InputFile symbol walker that finds these, then somehow cache them so we can tell LTO about them (the symbols are walked in gold when we first look at each file to see if we want to claim it, whereas LTO is not constructed until the linker has analyzed all symbols).

[mehdi_amini]

As an alternative, have you considered having a bit "used" (or "do not dead strip") that would express in the summary exactly what we want?

[tejohnson]

In D23488#627135, @mehdi_amini wrote:

As an alternative, have you considered having a bit "used" (or "do not dead strip") that would express in the summary exactly what we want?

Yes, that would be another alternative, I thought about that but was hoping it could be avoided, but maybe not easily. The bit would probably need to be set for any variable that starts with "llvm." to be safely conservative (e.g. we should also consider anything in llvm.used or llvm.compiler.used as potentially live).

[pcc]

This information will probably need to be encoded in the summary somehow once we're at the point where we no longer need to load the module during symbol resolution.

I think at this point we just need to collect a set of GC roots in add{Regular,Thin}LTO in the same way that we collect the set of used variables with collectUsedGlobalVariables.

[tejohnson]

In D23488#627154, @pcc wrote:

This information will probably need to be encoded in the summary somehow once we're at the point where we no longer need to load the module during symbol resolution.

At that point we will have a separately loadable symbol table in the bitcode file, but there again I guess we will not know anything about these llvm.* symbols in the table, right?

I think at this point we just need to collect a set of GC roots in add{Regular,Thin}LTO in the same way that we collect the set of used variables with collectUsedGlobalVariables.

Presumably using a new flag added to the summary, right? Or did you have a different approach in mind for now?

Right now the patch uses the set of preserved GUIDs computed from the GlobalResolution info as the roots in runThinLTO (see invocation of computeDeadSymbols). So probably we would just use the summary flag in computeDeadSymbols to add to the set of preserved GUIDs passed in. I.e. not in addThinLTO (this is for index-based internalization/dead stripping, so I don't think regular LTO comes into play).

[mehdi_amini]

In D23488#627136, @tejohnson wrote:

In D23488#627135, @mehdi_amini wrote:

As an alternative, have you considered having a bit "used" (or "do not dead strip") that would express in the summary exactly what we want?

Yes, that would be another alternative, I thought about that but was hoping it could be avoided, but maybe not easily. The bit would probably need to be set for any variable that starts with "llvm." to be safely conservative (e.g. we should also consider anything in llvm.used or llvm.compiler.used as potentially live).

llvm.used is definitely a must-be root, llvm.compiler.used are supposed to be able to be dead-stripped at link-time.

[pcc]

In D23488#627164, @tejohnson wrote:

In D23488#627154, @pcc wrote:

This information will probably need to be encoded in the summary somehow once we're at the point where we no longer need to load the module during symbol resolution.

At that point we will have a separately loadable symbol table in the bitcode file, but there again I guess we will not know anything about these llvm.* symbols in the table, right?

I was envisioning that the live bits in the global summary wouldn't be applied to the llvm.* symbols themselves but to the globals referenced by them.

I think at this point we just need to collect a set of GC roots in add{Regular,Thin}LTO in the same way that we collect the set of used variables with collectUsedGlobalVariables.

Presumably using a new flag added to the summary, right? Or did you have a different approach in mind for now?

Yes, it could be done in the summary. I was also thinking you could have a function called something like collectGCRoots that does something like this:

void collectGCRoots(Module *M, SmallSet<GlobalValue *> &GCRoots) {
  collectUsedGlobalVariables(M, GCRoots, true);
  collectUsedGlobalVariables(M, GCRoots, false);
  // similarly for llvm.global_ctors and llvm.global_dtors
}

then use GCRoots to decide whether to set the bit in GlobalResolution. But now that I think about it, I think I prefer the approach of setting live bits in the summary, for example it would seem to make it much simpler to pull the live lists of type identifiers out of the combined summary for CFI/devirtualization.

Also think about how this interacts with regular LTO. You probably also want anything referenced from the regular LTO module to be treated as a GC root.

Right now the patch uses the set of preserved GUIDs computed from the GlobalResolution info as the roots in runThinLTO (see invocation of computeDeadSymbols). So probably we would just use the summary flag in computeDeadSymbols to add to the set of preserved GUIDs passed in. I.e. not in addThinLTO (this is for index-based internalization/dead stripping, so I don't think regular LTO comes into play).

Yes, or change the computeDeadSymbols function to be implemented only in terms of the live bits. Then adding the GC roots from the linker (i.e. symbols referenced from regular objects or a regular LTO module) would be implemented by setting live bits on the roots.

[pcc]

In D23488#627201, @mehdi_amini wrote:

In D23488#627136, @tejohnson wrote:

In D23488#627135, @mehdi_amini wrote:

As an alternative, have you considered having a bit "used" (or "do not dead strip") that would express in the summary exactly what we want?

Yes, that would be another alternative, I thought about that but was hoping it could be avoided, but maybe not easily. The bit would probably need to be set for any variable that starts with "llvm." to be safely conservative (e.g. we should also consider anything in llvm.used or llvm.compiler.used as potentially live).

llvm.used is definitely a must-be root, llvm.compiler.used are supposed to be able to be dead-stripped at link-time.

I think we will need logic for removing entries from llvm.compiler.used then. Consider this scenario:

module A:

@llvm.compiler.used = [@f]

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

declare void @g()

module B:

define void @g() {
  ret void
}

In this case we can't dead strip f by internalizing as that would end up keeping the reference to the dead function g, we need to actually remove it.

[tejohnson]

In D23488#627212, @pcc wrote:

In D23488#627201, @mehdi_amini wrote:

In D23488#627136, @tejohnson wrote:

In D23488#627135, @mehdi_amini wrote:

As an alternative, have you considered having a bit "used" (or "do not dead strip") that would express in the summary exactly what we want?

Yes, that would be another alternative, I thought about that but was hoping it could be avoided, but maybe not easily. The bit would probably need to be set for any variable that starts with "llvm." to be safely conservative (e.g. we should also consider anything in llvm.used or llvm.compiler.used as potentially live).

llvm.used is definitely a must-be root, llvm.compiler.used are supposed to be able to be dead-stripped at link-time.

I think we will need logic for removing entries from llvm.compiler.used then. Consider this scenario:

module A:

@llvm.compiler.used = [@f]

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

declare void @g()

module B:

define void @g() {
  ret void
}

In this case we can't dead strip f by internalizing as that would end up keeping the reference to the dead function g, we need to actually remove it.

Yes. And since the llvm.compiler.used symbols aren't supposed to be touched by the compiler, I'm not sure what the legality is of removing from there for this optimization done in the thin link + thinlto backend. Probably not worth special casing llvm.compiler.used - just treat it conservatively (as gc roots).

[tejohnson]

In D23488#627205, @pcc wrote:

In D23488#627164, @tejohnson wrote:

In D23488#627154, @pcc wrote:

This information will probably need to be encoded in the summary somehow once we're at the point where we no longer need to load the module during symbol resolution.

At that point we will have a separately loadable symbol table in the bitcode file, but there again I guess we will not know anything about these llvm.* symbols in the table, right?

I was envisioning that the live bits in the global summary wouldn't be applied to the llvm.* symbols themselves but to the globals referenced by them.

Either one works for the index-based dead stripping. But my point was we need something to flag this in the summary because these symbols won't be in the bitcode symbol table (essentially the situation we're running into here).

I think at this point we just need to collect a set of GC roots in add{Regular,Thin}LTO in the same way that we collect the set of used variables with collectUsedGlobalVariables.

Presumably using a new flag added to the summary, right? Or did you have a different approach in mind for now?

Yes, it could be done in the summary. I was also thinking you could have a function called something like collectGCRoots that does something like this:

void collectGCRoots(Module *M, SmallSet<GlobalValue *> &GCRoots) {
  collectUsedGlobalVariables(M, GCRoots, true);
  collectUsedGlobalVariables(M, GCRoots, false);
  // similarly for llvm.global_ctors and llvm.global_dtors
}

then use GCRoots to decide whether to set the bit in GlobalResolution. But now that I think about it, I think I prefer the approach of setting live bits in the summary, for example it would seem to make it much simpler to pull the live lists of type identifiers out of the combined summary for CFI/devirtualization.

We don't want to parse the module and invoke collectUsedGlobalVariables when we do the thin link, which is where we need this info. Oh - I see that we are currently doing this. ISTR that this is only temporary (I hope - we don't want to have to parse the IR in the ThinLink!). So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

Also think about how this interacts with regular LTO. You probably also want anything referenced from the regular LTO module to be treated as a GC root.

Good point - I think we would miss those right now with this patch.

Right now the patch uses the set of preserved GUIDs computed from the GlobalResolution info as the roots in runThinLTO (see invocation of computeDeadSymbols). So probably we would just use the summary flag in computeDeadSymbols to add to the set of preserved GUIDs passed in. I.e. not in addThinLTO (this is for index-based internalization/dead stripping, so I don't think regular LTO comes into play).

Yes, or change the computeDeadSymbols function to be implemented only in terms of the live bits. Then adding the GC roots from the linker (i.e. symbols referenced from regular objects or a regular LTO module) would be implemented by setting live bits on the roots.

[tejohnson]

In D23488#627220, @tejohnson wrote:

We don't want to parse the module and invoke collectUsedGlobalVariables when we do the thin link, which is where we need this info. Oh - I see that we are currently doing this. ISTR that this is only temporary (I hope - we don't want to have to parse the IR in the ThinLink!).

Actually, looking at how this info is used right now, it seems like what I am talking about doing here will allow us to remove the build of the module and invocation of collectUsedGlobalVariables from addThinLTO. It is currently being used to help identify exported GUIDs to prevent internalization, but by marking these as live roots in the summary we can do the same thing: treating the flagged live roots as potentially exported and not dead.

So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

To do what I describe above (use the summary flagging to obviate the collectUsedGlobalVariables invocation from the thin link), we'll need to flag the references of the llvm.* variables.

[pcc]

In D23488#627220, @tejohnson wrote:

In D23488#627205, @pcc wrote:

In D23488#627164, @tejohnson wrote:

In D23488#627154, @pcc wrote:

This information will probably need to be encoded in the summary somehow once we're at the point where we no longer need to load the module during symbol resolution.

At that point we will have a separately loadable symbol table in the bitcode file, but there again I guess we will not know anything about these llvm.* symbols in the table, right?

I was envisioning that the live bits in the global summary wouldn't be applied to the llvm.* symbols themselves but to the globals referenced by them.

Either one works for the index-based dead stripping. But my point was we need something to flag this in the summary because these symbols won't be in the bitcode symbol table (essentially the situation we're running into here).

Sure, that makes sense. I was thinking about whether we'd also need a separate "used" bit in the bitcode symbol table, so that we can apply the right semantics to those symbols in both regular and thin LTO. In that case we'd actually want to mark the globals referenced by llvm.used rather than just marking llvm.used itself (because the refs wouldn't be available in the BC symtab). But I think that's probably best dealt with orthogonally.

I think at this point we just need to collect a set of GC roots in add{Regular,Thin}LTO in the same way that we collect the set of used variables with collectUsedGlobalVariables.

Presumably using a new flag added to the summary, right? Or did you have a different approach in mind for now?

Yes, it could be done in the summary. I was also thinking you could have a function called something like collectGCRoots that does something like this:

void collectGCRoots(Module *M, SmallSet<GlobalValue *> &GCRoots) {
  collectUsedGlobalVariables(M, GCRoots, true);
  collectUsedGlobalVariables(M, GCRoots, false);
  // similarly for llvm.global_ctors and llvm.global_dtors
}

then use GCRoots to decide whether to set the bit in GlobalResolution. But now that I think about it, I think I prefer the approach of setting live bits in the summary, for example it would seem to make it much simpler to pull the live lists of type identifiers out of the combined summary for CFI/devirtualization.

We don't want to parse the module and invoke collectUsedGlobalVariables when we do the thin link, which is where we need this info. Oh - I see that we are currently doing this. ISTR that this is only temporary (I hope - we don't want to have to parse the IR in the ThinLink!).

Right, this is the thing we want to avoid doing with the bitcode symbol table.

So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

Works for me.

[pcc]

In D23488#627223, @tejohnson wrote:

In D23488#627220, @tejohnson wrote:

We don't want to parse the module and invoke collectUsedGlobalVariables when we do the thin link, which is where we need this info. Oh - I see that we are currently doing this. ISTR that this is only temporary (I hope - we don't want to have to parse the IR in the ThinLink!).

Actually, looking at how this info is used right now, it seems like what I am talking about doing here will allow us to remove the build of the module and invocation of collectUsedGlobalVariables from addThinLTO. It is currently being used to help identify exported GUIDs to prevent internalization, but by marking these as live roots in the summary we can do the same thing: treating the flagged live roots as potentially exported and not dead.

I don't think that just removing the call to collectUsedGlobalVariables would be sufficient to avoid creating the module. We currently still need the module to create symbol names and compute module flags for the LTO client.

So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

To do what I describe above (use the summary flagging to obviate the collectUsedGlobalVariables invocation from the thin link), we'll need to flag the references of the llvm.* variables.

Aren't the llvm.* variables and their references available in the summary? Presumably even once we move to the bitcode symbol table we could treat llvm.* as GC roots by following their references, no?

[tejohnson]

In D23488#627265, @pcc wrote:

In D23488#627223, @tejohnson wrote:

In D23488#627220, @tejohnson wrote:

We don't want to parse the module and invoke collectUsedGlobalVariables when we do the thin link, which is where we need this info. Oh - I see that we are currently doing this. ISTR that this is only temporary (I hope - we don't want to have to parse the IR in the ThinLink!).

Actually, looking at how this info is used right now, it seems like what I am talking about doing here will allow us to remove the build of the module and invocation of collectUsedGlobalVariables from addThinLTO. It is currently being used to help identify exported GUIDs to prevent internalization, but by marking these as live roots in the summary we can do the same thing: treating the flagged live roots as potentially exported and not dead.

I don't think that just removing the call to collectUsedGlobalVariables would be sufficient to avoid creating the module. We currently still need the module to create symbol names and compute module flags for the LTO client.

The symbol name creation is down in the InputFile and will go away with the new bitcode symbol table, right?
Where are the module flags needed?

So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

To do what I describe above (use the summary flagging to obviate the collectUsedGlobalVariables invocation from the thin link), we'll need to flag the references of the llvm.* variables.

Aren't the llvm.* variables and their references available in the summary?

Yes

Presumably even once we move to the bitcode symbol table we could treat llvm.* as GC roots by following their references, no?

For the computeDeadSymbols this works. But what that doesn't get us is treating those as external (subsuming the handling of the Used variables in addSymbolToGlobalRes), so that they aren't internalized.

[pcc]

In D23488#627314, @tejohnson wrote:

In D23488#627265, @pcc wrote:

In D23488#627223, @tejohnson wrote:

In D23488#627220, @tejohnson wrote:

We don't want to parse the module and invoke collectUsedGlobalVariables when we do the thin link, which is where we need this info. Oh - I see that we are currently doing this. ISTR that this is only temporary (I hope - we don't want to have to parse the IR in the ThinLink!).

Actually, looking at how this info is used right now, it seems like what I am talking about doing here will allow us to remove the build of the module and invocation of collectUsedGlobalVariables from addThinLTO. It is currently being used to help identify exported GUIDs to prevent internalization, but by marking these as live roots in the summary we can do the same thing: treating the flagged live roots as potentially exported and not dead.

I don't think that just removing the call to collectUsedGlobalVariables would be sufficient to avoid creating the module. We currently still need the module to create symbol names and compute module flags for the LTO client.

The symbol name creation is down in the InputFile and will go away with the new bitcode symbol table, right?

Right.

Where are the module flags needed?

Sorry, I meant the symbol flags (i.e. ModuleSymbolTable::getSymbolFlags).

So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

To do what I describe above (use the summary flagging to obviate the collectUsedGlobalVariables invocation from the thin link), we'll need to flag the references of the llvm.* variables.

Aren't the llvm.* variables and their references available in the summary?

Yes

Presumably even once we move to the bitcode symbol table we could treat llvm.* as GC roots by following their references, no?

For the computeDeadSymbols this works. But what that doesn't get us is treating those as external (subsuming the handling of the Used variables in addSymbolToGlobalRes), so that they aren't internalized.

Sure, that's what I was thinking about here:

I was thinking about whether we'd also need a separate "used" bit in the bitcode symbol table, so that we can apply the right semantics to those symbols in both regular and thin LTO. In that case we'd actually want to mark the globals referenced by llvm.used rather than just marking llvm.used itself (because the refs wouldn't be available in the BC symtab). But I think that's probably best dealt with orthogonally.

[mehdi_amini]

In D23488#627220, @tejohnson wrote:

So it would have to be done during the compile step (where we could do what you suggest above). And then we put it in the summary. Although like I mentioned above, we can just flag the llvm.* variables as the live roots, that's simpler than walking all of their references and flagging them.

We could also leave the llvm.* entirely out of the summary, and just flag their reference as "used".
Another alternative is to leave the summary unchanged, and have the computeDeadSymbols to add to the roots getGUID('llvm.used'); getGUID('llvm.global_ctors'); etc (just get the same list as the global-dce pass.

lib/Transforms/IPO/FunctionImport.cpp

337 ↗

(On Diff #81995)

Is this intended?

[mehdi_amini]

In D23488#627212, @pcc wrote:

[...]
In this case we can't dead strip f by internalizing as that would end up keeping the reference to the dead function g, we need to actually remove it.

Right, it's probably not worth it in practice. There is likely not commonly enough compiler.used cases. We can always reconsider later.

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

337 ↗

(On Diff #81995)

Looks like it snuck in with your early version of the patch. I'll remove it.

[tejohnson]

Added flag to the summary to enable flagging llvm.* values as live,
and add those to the live worklist when doing index-based dead value
analysis. With this change all SPEC cpu2006 C/C++ benchmarks pass.

[mehdi_amini]

lib/Analysis/ModuleSummaryAnalysis.cpp

197 ↗

(On Diff #82304)

s/std::string/StringRef/

305 ↗

(On Diff #82304)

Not sure about this after reading the comment above, Also, any values used but not defined within module level asm should be listed on the llvm.used or llvm.compiler.used global and marked as referenced from there.

lib/Bitcode/Reader/BitcodeReader.cpp

792 ↗

(On Diff #82304)

One line comment for the Version < 3 (it makes sense to me now, but I'm not sure I'll see it immediately if I have to touch this in a few months).

lib/LTO/LTO.cpp

847 ↗

(On Diff #82304)

What if Res.second.VisibleToRegularObj && Res.second.IRName.empty()? Should we assert instead?

603 ↗

(On Diff #68868)

What is the answer to your question here?

[tejohnson]

In D23488#627220, @tejohnson wrote:

In D23488#627205, @pcc wrote:

Also think about how this interacts with regular LTO. You probably also want anything referenced from the regular LTO module to be treated as a GC root.

Good point - I think we would miss those right now with this patch.

I just realized I haven't addressed this yet. Looks like it requires adding a new flag into the SymbolResolution, since we can't currently distinguish between a value referenced between different ThinLTO partitions and the case where we have a reference between a ThinLTO partition and the regular LTO partition - in both cases the resulting GlobalResolution Partition will be External. I'll probably have to add a VisibleToRegularLTOPartition flag onto the SymbolResolution and set it when the Partition == External and we have seen a reference from Partition 0. I'll do that and add a test.

lib/Analysis/ModuleSummaryAnalysis.cpp

197 ↗

(On Diff #82304)

Fixed

305 ↗

(On Diff #82304)

Note that part of the comment is referring to "values used but not defined" within the module level asm. Whereas we are creating a summary here for something defined within module level asm. To be conservatively correct these should be marked live.

lib/Bitcode/Reader/BitcodeReader.cpp

792 ↗

(On Diff #82304)

Done.

lib/LTO/LTO.cpp

847 ↗

(On Diff #82304)

Looking at the code in addSymbolToGlobalRes, IRName is set when the GV is marked as prevailing. So I guess "Res.second.VisibleToRegularObj && Res.second.IRName.empty()" would mean a symbol that is visible to a regular object but not the prevailing copy. In that case, it shouldn't need to be preserved.

603 ↗

(On Diff #68868)

I realized when revisiting the patch that my logic was flawed. It can be exported and dead (in fact, that's one thing we are specifically trying to catch with this patch). Additionally, it can be live (not in DeadSymbols) and not be exported. So your original check was correct. We want to treat as exported when internalizing if it was a) original exported to another module and b) it isn't dead per the index based deadness analysis.

[tejohnson]

In D23488#629783, @tejohnson wrote:

I just realized I haven't addressed this yet. Looks like it requires adding a new flag into the SymbolResolution, since we can't currently distinguish between a value referenced between different ThinLTO partitions and the case where we have a reference between a ThinLTO partition and the regular LTO partition - in both cases the resulting GlobalResolution Partition will be External. I'll probably have to add a VisibleToRegularLTOPartition flag onto the SymbolResolution and set it when the Partition == External and we have seen a reference from Partition 0. I'll do that and add a test.

Correction: the new flag will go into the GlobalResolution not the SymbolResolution!

[tejohnson]

Address review comments, add handling/test for use in regular LTO partition.

[mehdi_amini]

lib/LTO/LTO.cpp

847 ↗

(On Diff #82304)

The fact that you had to look at addSymbolToGlobalRes to provide the explanation is a good indication that a comment would be welcome here.

335 ↗

(On Diff #82352)

Can you add a comment that explains the test (and both branches)

341 ↗

(On Diff #82352)

It is not clear to me how the VisibleToRegularLTOPartition is computed here, it seems that for partition to be 0 (RegularLTO) the symbol has to be used or defined in LTO but not used or defined in ThinLTO?

[tejohnson]

lib/LTO/LTO.cpp

847 ↗

(On Diff #82304)

Ok will do

335 ↗

(On Diff #82352)

Will do

341 ↗

(On Diff #82352)

This will be called for each partition it is referenced from. Partition 0 is always regular LTO, ThinLTO modules are partitions 1 and higher. So if this is ever called for Partition 0 then we have a reference in regular LTO. See the callsites in add*LTO

[mehdi_amini]

lib/LTO/LTO.cpp

341 ↗

(On Diff #82352)

I misread the assignment as = instead of |=.

[mehdi_amini]

lib/LTO/LTO.cpp

341 ↗

(On Diff #82352)

Also technically to be only "visible" to the RegularLTO partition, it should be referenced from LTO but not defined there with a prevailing resolution.

[pcc]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

Don't you just need one flag: VisibleOutsideThinLTO (or something).

[mehdi_amini]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

I think one flag should be enough, but shouldn't we have the same flag for LTO internalization?

[pcc]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

Wouldn't that be redundant with Partition == 0?

[tejohnson]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

You're right, we only need one flag (forgot that the VisibleToRegularObj flag was added to GlobalResolutions for this patch). I will combine them as suggested.

lib/LTO/LTO.cpp

341 ↗

(On Diff #82352)

I'm using the term "visible" loosely here - if it is defined in the regular LTO partition it is essentially also visible there.

[mehdi_amini]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

You're right!
So do we need to record every ThinLTO module as an individual partition? When do we use this?
We could have enum partition { Unkown, Global, LTO, ThinLTO }?

[tejohnson]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

So do we need to record every ThinLTO module as an individual partition? When do we use this?

To detect when symbols are used by multiple ThinLTO modules (i.e. exported). E.g. it transitions from Unknown -> partition1 when first called with Partition=partition1, then from partition1 -> External if invoked again for the same symbol with a different partition2.

[tejohnson]

Address comments

[mehdi_amini]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

To detect when symbols are used by multiple ThinLTO modules (i.e. exported). E.g. it transitions from Unknown -> partition1 when first called with Partition=partition1, then from partition1 -> External if invoked again for the same symbol with a different partition2.

The way partitions are handled and the flag VisibleOutsideThinLTO is still not clear to me, we know when symbols are exported from the index itself why do we need partitions for that?

[tejohnson]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

The way partitions are handled and the flag VisibleOutsideThinLTO is still not clear to me, we know when symbols are exported from the index itself why do we need partitions for that?

At some point we have to collate that information to be able to look up which guid are exported from their modules (for creating the ExportedGUIDs set for internalization). We could detect cross module references among ThinLTO modules by walking the index, but since we have the information here already, it seems more efficient to just keep track of it. Otherwise we need to walk the whole index, comparing module paths, etc.

[mehdi_amini]

Forgot to ask, did you collect any statistics?
I'd be interested in things like (for let say clang itself):

• ThinLink time
• Link time
• Number of imported function
• Number of imported module
• Number of internalization
• Whatever else you think about :)

[mehdi_amini]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

At some point we have to collate that information to be able to look up which guid are exported from their modules (for creating the ExportedGUIDs set for internalization). We could detect cross module references among ThinLTO modules by walking the index, but since we have the information here already, it seems more efficient to just keep track of it. Otherwise we need to walk the whole index, comparing module paths, etc.

Do we have an example that would cover the following case:

// main.cpp
void bar1();
void bar2();
void baz();
void foo1() {
  bar1();
}
void foo2() {
  bar2();
}
int main() {
  baz()
}
`

And

`
// bar.cpp
void bar1() {
}
void bar2() {
  foo2(); // The cycle shouldn't prevent dead-stripping.
}
void baz() {
   // Adding a call to bar() here should not prevent internalization.
}
`

With only main exported by the linker, I expect us to be able to:

1. dead-strip from the index foo() and bar()
2. "internalize" (drop) foo() and bar() eagerly from the IR

I think the current logic should be OK. But I still find the partition thing and the ExportedGUIDs confusing.

lib/LTO/LTO.cpp

879 ↗

(On Diff #82365)

Could we *not* add DeadSymbols to ExportedGUIDs here and remove the DeadSymbols.count(GUID) from the test below?

[tejohnson]

In D23488#630029, @mehdi_amini wrote:

Forgot to ask, did you collect any statistics?
I'd be interested in things like (for let say clang itself):

• ThinLink time
• Link time
• Number of imported function
• Number of imported module
• Number of internalization
• Whatever else you think about :)

No, I can collect some stats next week after the holiday. The compile time data may take a bit longer to get (have to run when my machine is otherwise mostly idle).

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

Do we have an example that would cover the following case:

// main.cpp
void bar1();
void bar2();
void baz();
void foo1() {
  bar1();
}
void foo2() {
  bar2();
}
int main() {
  baz()
}
`

And

`
// bar.cpp
void bar1() {
}
void bar2() {
  foo2(); // The cycle shouldn't prevent dead-stripping.
}
void baz() {
   // Adding a call to bar() here should not prevent internalization.

bar1 or bar2? Adding a call to bar2 would prevent its dead stripping and prevent internalization. Adding a call to bar1 should not prevent its internalization.

}

`

With only main exported by the linker, I expect us to be able to:

1) dead-strip from the index foo() and bar()

I don't have a cycle case like foo2/bar2, will add. The existing test case covers the foo1/bar1 case. Although note if calls to either bar2 or bar1 are added to baz as you suggest above, it will prevent their dead stripping.

2. "internalize" (drop) foo() and bar() eagerly from the IR

Yes the existing test case ensures we internalize where appropriate, even when there were cross-module references (but where both caller/callee were dead per new index-based analysis), and that we remove them as appropriate. Other than the cycle case, which I'll add, the above cases are covered by the new test case in the patch.

I think the current logic should be OK. But I still find the partition thing and the ExportedGUIDs confusing.

lib/LTO/LTO.cpp

879 ↗

(On Diff #82365)

Good idea.

lib/LTO/ThinLTOCodeGenerator.cpp

727 ↗

(On Diff #82365)

Actually, in ThinLTOCodeGenerator checks here and elsewhere it looks like this test can just be !DeadSymbols.count(GUID) rather than (!DeadSymbols.count(GUID) && GUIDPreservedSymbols.count(GUID)). Here the same GUIDPreservedSymbols set was passed computeDeadSymbols, so they would already be excluded from the DeadSymbol set. ThinLTOCodeGenerator does not seem to distinguish between references outside of ThinLTO vs cross-references between ThinLTO modules, which in fact means that the dead analysis will be conservative here...

[mehdi_amini]

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

bar1 or bar2? Adding a call to bar2 would prevent its dead stripping and prevent internalization. Adding a call to bar1 should not prevent its internalization.

Sorry, bar1() (I wrote the comment before adding bar2(), and yes we should only internalize bar1() when called from baz().

lib/LTO/ThinLTOCodeGenerator.cpp

727 ↗

(On Diff #82365)

I think the expectation is that GUIDPreservedSymbols is only supposed to contain symbols visible outside of the ThinLTO partition.

From the header:

/// Set of symbols that need to be preserved outside of the set of bitcode
/// files.
StringSet<> PreservedSymbols;

Even though in the current impl. file:

void ThinLTOCodeGenerator::crossReferenceSymbol(StringRef Name) {
  // FIXME: At the moment, we don't take advantage of this extra information,
  // we're conservatively considering cross-references as preserved.
  //  CrossReferencedSymbols.insert(Name);
  PreservedSymbols.insert(Name);
}

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

727 ↗

(On Diff #82365)

Even though in the current impl. file:

Right, that's what I was referring to. Any reason crossReferenceSymbol() doesn't add to a different set (the commented out CrossReferencedSymbols?) - although the isExported checks here and elsewhere in ThinLTOCodeGenerator would need to change if that happened. Maybe better to just switch this to the new LTO API?

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

727 ↗

(On Diff #82365)

Switching to the new LTO API is one reason I haven't fixed this yet.

[mehdi_amini]

In D23488#630116, @tejohnson wrote:

No, I can collect some stats next week after the holiday. The compile time data may take a bit longer to get (have to run when my machine is otherwise mostly idle).

To clarify: I'm not saying it is blocking in order to land this patch. I just think it'll be interesting data that to have and it'd be nice if you can collect them at some point :)

[tejohnson]

Here are some stats for ThinLTO linking clang:

644 function-import              - Number of dead stripped symbols in index

155102 function-import - Number of live symbols in index

(the patch I will upload in a minute contains these new stats)

The number of functions imported dropped only a very small amount (from 62889 to 62815), and the number of modules imported from went from 24470 to 24449. The number of internalizations was unchanged.

I measured the full ThinLink+BE+link time for clang and there was no consistent change across 3 runs each (stripping enabled/disabled).

So at least for clang, this didn't find much opportunity. I can try for larger internal apps later when it is integrated.

include/llvm/LTO/LTO.h

389 ↗

(On Diff #82352)

Added the circular dependence case to the new test.

lib/LTO/LTO.cpp

879 ↗

(On Diff #82365)

Done.

lib/LTO/ThinLTOCodeGenerator.cpp

727 ↗

(On Diff #82365)

Actually, in ThinLTOCodeGenerator checks here and elsewhere it looks like this test can just be !DeadSymbols.count(GUID) rather than (!DeadSymbols.count(GUID) && GUIDPreservedSymbols.count(GUID)). Here the same GUIDPreservedSymbols set was passed computeDeadSymbols, so they would already be excluded from the DeadSymbol set. ThinLTOCodeGenerator does not seem to distinguish between references outside of ThinLTO vs cross-references between ThinLTO modules, which in fact means that the dead analysis will be conservative here...

I had this backwards: because DeadSymbols was computed from GUIDPreservedSymbols, we only need to check GUIDPreservedSymbols here (anything in GUIDPreservedSymbols will necessarily not be in DeadSymbols). I've made that change here and elsewhere in this file (which basically puts us back to your original version of the patch for these checks...now I know why the isExported lambda checks didn't change here originally...).

[tejohnson]

Address comments, add stats and an option.

[mehdi_amini]

I'm surprised by how little we find in clang, that seems fishy to me, I'll investigate on OSX when the patch lands.

[tejohnson]

Ping. Any more comments?

[mehdi_amini]

LGTM.

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

struct GVFlags {
     /// In the future this will be used to update and optimize linkage
     /// types based on global summary-based analysis.
     unsigned Linkage : 4;
 
     /// Indicate if the global value cannot be imported (e.g. it cannot
     /// be renamed or references something that can't be renamed).
     unsigned NotEligibleToImport : 1;
 
+    /// Indicate that the global value must be considered a live root for
+    /// index-based liveness analysis. Used for special LLVM values such as
+    /// llvm.global_ctors that the linker does not know about.
+    unsigned LiveRoot : 1;
+
     /// Convenience Constructors
     explicit GVFlags(GlobalValue::LinkageTypes Linkage,
-                     bool NotEligibleToImport)
-        : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport) {}
+                     bool NotEligibleToImport, bool LiveRoot)
+        : Linkage(Linkage), NotEligibleToImport(NotEligibleToImport),
+          LiveRoot(LiveRoot) {}
   };
 
 private:
   /// Kind of summary for use in dyn_cast<> et al.
   SummaryKind Kind;
 
   GVFlags Flags;
 
public:
   /// optimization. Will be applied in the ThinLTO backends.
   void setLinkage(GlobalValue::LinkageTypes Linkage) {
     Flags.Linkage = Linkage;
   }
 
   /// Return true if this global value can't be imported.
   bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
 
+  /// Return true if this global value must be considered a root for live
+  /// value analysis on the index.
+  bool liveRoot() const { return Flags.LiveRoot; }
+
+  /// Flag that this global value must be considered a root for live
+  /// value analysis on the index.
+  void setLiveRoot() { Flags.LiveRoot = true; }
+
   /// Flag that this global value cannot be imported.
   void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
 
   /// Return the list of values referenced by this global value definition.
   ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
 };
 
 /// \brief Alias summary information.
private:
   // YAML I/O support.
   friend yaml::MappingTraits<ModuleSummaryIndex>;
 
 public:
   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
   gvsummary_iterator end() { return GlobalValueMap.end(); }
   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
+  size_t size() const { return GlobalValueMap.size(); }
 
   /// Get the list of global value summary objects for a given value name.
   const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {
     return GlobalValueMap[GlobalValue::getGUID(ValueName)];
   }
 
   /// Get the list of global value summary objects for a given value name.
   const const_gvsummary_iterator

llvm/trunk/include/llvm/IR/ModuleSummaryIndexYAML.h

static void inputOne(IO &io, StringRef Key, GlobalValueSummaryMapTy &V) {
     io.mapRequired(Key.str().c_str(), FSums);
     uint64_t KeyInt;
     if (Key.getAsInteger(0, KeyInt)) {
       io.setError("key not an integer");
       return;
     }
     auto &Elem = V[KeyInt];
     for (auto &FSum : FSums) {
-      GlobalValueSummary::GVFlags GVFlags(GlobalValue::ExternalLinkage, false);
+      GlobalValueSummary::GVFlags GVFlags(GlobalValue::ExternalLinkage, false,
+                                          false);
       Elem.push_back(llvm::make_unique<FunctionSummary>(
           GVFlags, 0, ArrayRef<ValueInfo>{},
           ArrayRef<FunctionSummary::EdgeTy>{}, std::move(FSum.TypeTests)));
     }
   }
   static void output(IO &io, GlobalValueSummaryMapTy &V) {
     for (auto &P : V) {
       std::vector<FunctionSummaryYaml> FSums;

llvm/trunk/include/llvm/LTO/LTO.h

private:
   // cannot make any final internalization decisions until all input files have
   // been added and the client has called run(). During run() we apply
   // internalization decisions either directly to the module (for regular LTO)
   // or to the combined index (for ThinLTO).
   struct GlobalResolution {
     /// The unmangled name of the global.
     std::string IRName;
 
+    /// Keep track if the symbol is visible outside of ThinLTO (i.e. in
+    /// either a regular object or the regular LTO partition).
+    bool VisibleOutsideThinLTO = false;
+
     bool UnnamedAddr = true;
 
     /// This field keeps track of the partition number of this global. The
     /// regular LTO object is partition 0, while each ThinLTO object has its own
     /// partition number from 1 onwards.
     ///
     /// Any global that is defined or used by more than one partition, or that
     /// is referenced externally, may not be internalized.
     ///
     /// Partitions generally have a one-to-one correspondence with tasks, except
     /// that we use partition 0 for all parallel LTO code generation partitions.
     /// Any partitioning of the combined LTO object is done internally by the
     /// LTO backend.
     unsigned Partition = Unknown;
 
     /// Special partition numbers.
     enum : unsigned {
       /// A partition number has not yet been assigned to this global.
       Unknown = -1u,
 
       /// This global is either used by more than one partition or has an
       /// external reference, and therefore cannot be internalized.
       External = -2u,
+
+      /// The RegularLTO partition
+      RegularLTO = 0,
     };
   };
 
   // Global mapping from mangled symbol names to resolutions.
   StringMap<GlobalResolution> GlobalResolutions;
 
   void addSymbolToGlobalRes(SmallPtrSet<GlobalValue *, 8> &Used,
                             const InputFile::Symbol &Sym, SymbolResolution Res,

llvm/trunk/include/llvm/Transforms/IPO/FunctionImport.h

 ///
 /// \p ImportLists will be populated with an entry for every Module we are
 /// importing into. This entry is itself a map that can be passed to
 /// FunctionImporter::importFunctions() above (see description there).
 ///
 /// \p ExportLists contains for each Module the set of globals (GUID) that will
 /// be imported by another module, or referenced by such a function. I.e. this
 /// is the set of globals that need to be promoted/renamed appropriately.
+///
+/// \p DeadSymbols (optional) contains a list of GUID that are deemed "dead" and
+/// will be ignored for the purpose of importing.
 void ComputeCrossModuleImport(
     const ModuleSummaryIndex &Index,
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
-    StringMap<FunctionImporter::ExportSetTy> &ExportLists);
+    StringMap<FunctionImporter::ExportSetTy> &ExportLists,
+    const DenseSet<GlobalValue::GUID> *DeadSymbols = nullptr);
 
 /// Compute all the imports for the given module using the Index.
 ///
 /// \p ImportList will be populated with a map that can be passed to
 /// FunctionImporter::importFunctions() above (see description there).
 void ComputeCrossModuleImportForModule(
     StringRef ModulePath, const ModuleSummaryIndex &Index,
     FunctionImporter::ImportMapTy &ImportList);
 
+/// 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.
+DenseSet<GlobalValue::GUID>
+computeDeadSymbols(const ModuleSummaryIndex &Index,
+                   const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
+
 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 /// \p ModulePath.
 //
 /// This includes summaries from that module (in case any global summary based
 /// optimizations were recorded) and from any definitions in other modules that
 /// should be imported.
 //
 /// \p ModuleToSummariesForIndex will be populated with the needed summaries

llvm/trunk/lib/Analysis/ModuleSummaryAnalysis.cpp

for (const BasicBlock &BB : F)
     }
 
   bool NonRenamableLocal = isNonRenamableLocal(F);
   bool NotEligibleForImport =
       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
       // Inliner doesn't handle variadic functions.
       // FIXME: refactor this to use the same code that inliner is using.
       F.isVarArg();
-  GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport);
+  GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
+                                    /* LiveRoot = */ false);
   auto FuncSummary = llvm::make_unique<FunctionSummary>(
       Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
       TypeTests.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(F.getGUID());
   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
 
 static void
 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
   SetVector<ValueInfo> RefEdges;
   SmallPtrSet<const User *, 8> Visited;
   findRefEdges(&V, RefEdges, Visited);
   bool NonRenamableLocal = isNonRenamableLocal(V);
-  GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal);
+  GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
+                                    /* LiveRoot = */ false);
   auto GVarSummary =
       llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(V.getGUID());
   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
 }
 
 static void
 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
   bool NonRenamableLocal = isNonRenamableLocal(A);
-  GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal);
+  GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
+                                    /* LiveRoot = */ false);
   auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
   auto *Aliasee = A.getBaseObject();
   auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
   assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
   AS->setAliasee(AliaseeSummary);
   if (NonRenamableLocal)
     CantBePromoted.insert(A.getGUID());
   Index.addGlobalValueSummary(A.getName(), std::move(AS));
 }
 
+// Set LiveRoot flag on entries matching the given value name.
+static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
+  auto SummaryList =
+      Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name));
+  if (SummaryList == Index.end())
+    return;
+  for (auto &Summary : SummaryList->second)
+    Summary->setLiveRoot();
+}
+
 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
     const Module &M,
     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
     ProfileSummaryInfo *PSI) {
   ModuleSummaryIndex Index;
 
   // Identify the local values in the llvm.used and llvm.compiler.used sets,
   // which should not be exported as they would then require renaming and
for (const GlobalAlias &A : M.aliases())
     computeAliasSummary(Index, A, CantBePromoted);
 
   for (auto *V : LocalsUsed) {
     auto *Summary = Index.getGlobalValueSummary(*V);
     assert(Summary && "Missing summary for global value");
     Summary->setNotEligibleToImport();
   }
 
+  // The linker doesn't know about these LLVM produced values, so we need
+  // to flag them as live in the index to ensure index-based dead value
+  // analysis treats them as live roots of the analysis.
+  setLiveRoot(Index, "llvm.used");
+  setLiveRoot(Index, "llvm.compiler.used");
+  setLiveRoot(Index, "llvm.global_ctors");
+  setLiveRoot(Index, "llvm.global_dtors");
+  setLiveRoot(Index, "llvm.global.annotations");
+
   if (!M.getModuleInlineAsm().empty()) {
     // Collect the local values defined by module level asm, and set up
     // summaries for these symbols so that they can be marked as NoRename,
     // to prevent export of any use of them in regular IR that would require
     // renaming within the module level asm. Note we don't need to create a
     // summary for weak or global defs, as they don't need to be flagged as
     // NoRename, and defs in module level asm can't be imported anyway.
     // Also, any values used but not defined within module level asm should
     // be listed on the llvm.used or llvm.compiler.used global and marked as
     // referenced from there.
     ModuleSymbolTable::CollectAsmSymbols(
         Triple(M.getTargetTriple()), M.getModuleInlineAsm(),
         [&M, &Index, &CantBePromoted](StringRef Name,
                                       object::BasicSymbolRef::Flags Flags) {
           // Symbols not marked as Weak or Global are local definitions.
           if (Flags & (object::BasicSymbolRef::SF_Weak |
                        object::BasicSymbolRef::SF_Global))
             return;
           GlobalValue *GV = M.getNamedValue(Name);
           if (!GV)
             return;
           assert(GV->isDeclaration() && "Def in module asm already has definition");
           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
-                                              /* NotEligibleToImport */ true);
+                                              /* NotEligibleToImport */ true,
+                                              /* LiveRoot */ true);
           CantBePromoted.insert(GlobalValue::getGUID(Name));
           // Create the appropriate summary type.
           if (isa<Function>(GV)) {
             std::unique_ptr<FunctionSummary> Summary =
                 llvm::make_unique<FunctionSummary>(
                     GVFlags, 0, ArrayRef<ValueInfo>{},
                     ArrayRef<FunctionSummary::EdgeTy>{},
                     ArrayRef<GlobalValue::GUID>{});

llvm/trunk/lib/Bitcode/Reader/BitcodeReader.cpp

 static GlobalValueSummary::GVFlags getDecodedGVSummaryFlags(uint64_t RawFlags,
                                                             uint64_t Version) {
   // Summary were not emitted before LLVM 3.9, we don't need to upgrade Linkage
   // like getDecodedLinkage() above. Any future change to the linkage enum and
   // to getDecodedLinkage() will need to be taken into account here as above.
   auto Linkage = GlobalValue::LinkageTypes(RawFlags & 0xF); // 4 bits
   RawFlags = RawFlags >> 4;
   bool NotEligibleToImport = (RawFlags & 0x1) || Version < 3;
-  return GlobalValueSummary::GVFlags(Linkage, NotEligibleToImport);
+  // The LiveRoot flag wasn't introduced until version 3. For dead stripping
+  // to work correctly on earlier versions, we must conservatively treat all
+  // values as live.
+  bool LiveRoot = (RawFlags & 0x2) || Version < 3;
+  return GlobalValueSummary::GVFlags(Linkage, NotEligibleToImport, LiveRoot);
 }
 
 static GlobalValue::VisibilityTypes getDecodedVisibility(unsigned Val) {
   switch (Val) {
   default: // Map unknown visibilities to default.
   case 0: return GlobalValue::DefaultVisibility;
   case 1: return GlobalValue::HiddenVisibility;
   case 2: return GlobalValue::ProtectedVisibility;

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

static unsigned getEncodedLinkage(const GlobalValue &GV) {
   return getEncodedLinkage(GV.getLinkage());
 }
 
 // Decode the flags for GlobalValue in the summary
 static uint64_t getEncodedGVSummaryFlags(GlobalValueSummary::GVFlags Flags) {
   uint64_t RawFlags = 0;
 
   RawFlags |= Flags.NotEligibleToImport; // bool
+  RawFlags |= (Flags.LiveRoot << 1);
   // Linkage don't need to be remapped at that time for the summary. Any future
   // change to the getEncodedLinkage() function will need to be taken into
   // account here as well.
   RawFlags = (RawFlags << 4) | Flags.Linkage; // 4 bits
 
   return RawFlags;
 }
 

llvm/trunk/lib/LTO/LTO.cpp

void LTO::addSymbolToGlobalRes(SmallPtrSet<GlobalValue *, 8> &Used,
   GlobalValue *GV = Sym.isGV() ? Sym.getGV() : nullptr;
 
   auto &GlobalRes = GlobalResolutions[Sym.getName()];
   if (GV) {
     GlobalRes.UnnamedAddr &= GV->hasGlobalUnnamedAddr();
     if (Res.Prevailing)
       GlobalRes.IRName = GV->getName();
   }
+  // Set the partition to external if we know it is used elsewhere, e.g.
+  // it is visible to a regular object, is referenced from llvm.compiler_used,
+  // or was already recorded as being referenced from a different partition.
   if (Res.VisibleToRegularObj || (GV && Used.count(GV)) ||
       (GlobalRes.Partition != GlobalResolution::Unknown &&
-       GlobalRes.Partition != Partition))
+       GlobalRes.Partition != Partition)) {
     GlobalRes.Partition = GlobalResolution::External;
-  else
+  } else
+    // First recorded reference, save the current partition.
     GlobalRes.Partition = Partition;
+
+  // Flag as visible outside of ThinLTO if visible from a regular object or
+  // if this is a reference in the regular LTO partition.
+  GlobalRes.VisibleOutsideThinLTO |=
+      (Res.VisibleToRegularObj || (Partition == GlobalResolution::RegularLTO));
 }
 
 static void writeToResolutionFile(raw_ostream &OS, InputFile *Input,
                                   ArrayRef<SymbolResolution> Res) {
   StringRef Path = Input->getName();
   OS << Path << '\n';
   auto ResI = Res.begin();
   for (const InputFile::Symbol &Sym : Input->symbols()) {
Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
   // uses that couldn't be promoted/renamed on export). This is so
   // InProcessThinBackend::start can still launch a backend thread, which
   // is passed the map of summaries for the module, without any special
   // handling for this case.
   for (auto &Mod : ThinLTO.ModuleMap)
     if (!ModuleToDefinedGVSummaries.count(Mod.first))
       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
 
+  // Compute "dead" symbols, we don't want to import/export these!
+  DenseSet<GlobalValue::GUID> GUIDPreservedSymbols;
+  for (auto &Res : GlobalResolutions) {
+    if (Res.second.VisibleOutsideThinLTO &&
+        // IRName will be defined if we have seen the prevailing copy of
+        // this value. If not, no need to preserve any ThinLTO copies.
+        !Res.second.IRName.empty())
+      GUIDPreservedSymbols.insert(GlobalValue::getGUID(Res.second.IRName));
+  }
+
+  auto DeadSymbols =
+      computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
+
   StringMap<FunctionImporter::ImportMapTy> ImportLists(
       ThinLTO.ModuleMap.size());
   StringMap<FunctionImporter::ExportSetTy> ExportLists(
       ThinLTO.ModuleMap.size());
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 
   if (Conf.OptLevel > 0) {
     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
-                             ImportLists, ExportLists);
+                             ImportLists, ExportLists, &DeadSymbols);
 
     std::set<GlobalValue::GUID> ExportedGUIDs;
     for (auto &Res : GlobalResolutions) {
-      if (!Res.second.IRName.empty() &&
-          Res.second.Partition == GlobalResolution::External)
+      // First check if the symbol was flagged as having external references.
+      if (Res.second.Partition != GlobalResolution::External)
+        continue;
+      // IRName will be defined if we have seen the prevailing copy of
+      // this value. If not, no need to mark as exported from a ThinLTO
+      // partition (and we can't get the GUID).
+      if (Res.second.IRName.empty())
+        continue;
+      auto GUID = GlobalValue::getGUID(Res.second.IRName);
+      // Mark exported unless index-based analysis determined it to be dead.
+      if (!DeadSymbols.count(GUID))
         ExportedGUIDs.insert(GlobalValue::getGUID(Res.second.IRName));
     }
 
     auto isPrevailing = [&](GlobalValue::GUID GUID,
                             const GlobalValueSummary *S) {
       return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath();
     };
     auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {

llvm/trunk/lib/LTO/ThinLTOCodeGenerator.cpp

void ThinLTOCodeGenerator::promote(Module &TheModule,
                                    ModuleSummaryIndex &Index) {
   auto ModuleCount = Index.modulePaths().size();
   auto ModuleIdentifier = TheModule.getModuleIdentifier();
 
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries;
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
+  // Convert the preserved symbols set from string to GUID
+  auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
+      PreservedSymbols, Triple(TheModule.getTargetTriple()));
+
+  // Compute "dead" symbols, we don't want to import/export these!
+  auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols);
+
   // Generate import/export list
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
-                           ExportLists);
+                           ExportLists, &DeadSymbols);
 
   // Resolve LinkOnce/Weak symbols.
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
   resolveWeakForLinkerInIndex(Index, ResolvedODR);
 
   thinLTOResolveWeakForLinkerModule(
       TheModule, ModuleToDefinedGVSummaries[ModuleIdentifier]);
 
-  // Convert the preserved symbols set from string to GUID
-  auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
-      PreservedSymbols, Triple(TheModule.getTargetTriple()));
-
   // Promote the exported values in the index, so that they are promoted
   // in the module.
   auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
     const auto &ExportList = ExportLists.find(ModuleIdentifier);
     return (ExportList != ExportLists.end() &&
             ExportList->second.count(GUID)) ||
            GUIDPreservedSymbols.count(GUID);
   };
void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
                                              ModuleSummaryIndex &Index) {
   auto ModuleMap = generateModuleMap(Modules);
   auto ModuleCount = Index.modulePaths().size();
 
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
+  // Convert the preserved symbols set from string to GUID
+  auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
+      PreservedSymbols, Triple(TheModule.getTargetTriple()));
+
+  // Compute "dead" symbols, we don't want to import/export these!
+  auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols);
+
   // Generate import/export list
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
-                           ExportLists);
+                           ExportLists, &DeadSymbols);
   auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
 
   crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 }
 
 /**
  * Compute the list of summaries needed for importing into module.
  */
void ThinLTOCodeGenerator::internalize(Module &TheModule,
   // Convert the preserved symbols set from string to GUID
   auto GUIDPreservedSymbols =
       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
 
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
+  // Compute "dead" symbols, we don't want to import/export these!
+  auto DeadSymbols = computeDeadSymbols(Index, GUIDPreservedSymbols);
+
   // Generate import/export list
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
-                           ExportLists);
+                           ExportLists, &DeadSymbols);
   auto &ExportList = ExportLists[ModuleIdentifier];
 
   // Be friendly and don't nuke totally the module when the client didn't
   // supply anything to preserve.
   if (ExportList.empty() && GUIDPreservedSymbols.empty())
     return;
 
   // Internalization
void ThinLTOCodeGenerator::run() {
   // Prepare the module map.
   auto ModuleMap = generateModuleMap(Modules);
   auto ModuleCount = Modules.size();
 
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
   Index->collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
+  // Convert the preserved symbols set from string to GUID, this is needed for
+  // computing the caching hash and the internalization.
+  auto GUIDPreservedSymbols =
+      computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
+
+  // Compute "dead" symbols, we don't want to import/export these!
+  auto DeadSymbols = computeDeadSymbols(*Index, GUIDPreservedSymbols);
+
   // Collect the import/export lists for all modules from the call-graph in the
   // combined index.
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists,
-                           ExportLists);
-
-  // Convert the preserved symbols set from string to GUID, this is needed for
-  // computing the caching hash and the internalization.
-  auto GUIDPreservedSymbols =
-      computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
+                           ExportLists, &DeadSymbols);
 
   // We use a std::map here to be able to have a defined ordering when
   // producing a hash for the cache entry.
   // FIXME: we should be able to compute the caching hash for the entry based
   // on the index, and nuke this map.
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 
   // Resolve LinkOnce/Weak symbols, this has to be computed early because it

llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp

 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
 
 #define DEBUG_TYPE "function-import"
 
 using namespace llvm;
 
-STATISTIC(NumImported, "Number of functions imported");
+STATISTIC(NumImportedFunctions, "Number of functions imported");
+STATISTIC(NumImportedModules, "Number of modules imported from");
+STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
+STATISTIC(NumLiveSymbols, "Number of live symbols in index");
 
 /// Limit on instruction count of imported functions.
 static cl::opt<unsigned> ImportInstrLimit(
     "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
     cl::desc("Only import functions with less than N instructions"));
 
 static cl::opt<float>
     ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),

 // FIXME: This multiplier was not really tuned up.
 static cl::opt<float> ImportColdMultiplier(
     "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),
     cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
 
 static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
                                   cl::desc("Print imported functions"));
 
+static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,
+                                 cl::desc("Compute dead symbols"));
+
 // Temporary allows the function import pass to disable always linking
 // referenced discardable symbols.
 static cl::opt<bool>
     DontForceImportReferencedDiscardableSymbols("disable-force-link-odr",
                                                 cl::init(false), cl::Hidden);
 
 static cl::opt<bool> EnableImportMetadata(
     "enable-import-metadata", cl::init(

 }
 
 /// Given the list of globals defined in a module, compute the list of imports
 /// as well as the list of "exports", i.e. the list of symbols referenced from
 /// another module (that may require promotion).
 static void ComputeImportForModule(
     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
     FunctionImporter::ImportMapTy &ImportList,
-    StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
+    StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr,
+    const DenseSet<GlobalValue::GUID> *DeadSymbols = nullptr) {
   // Worklist contains the list of function imported in this module, for which
   // we will analyse the callees and may import further down the callgraph.
   SmallVector<EdgeInfo, 128> Worklist;
 
   // Populate the worklist with the import for the functions in the current
   // module
   for (auto &GVSummary : DefinedGVSummaries) {
+    if (DeadSymbols && DeadSymbols->count(GVSummary.first)) {
+      DEBUG(dbgs() << "Ignores Dead GUID: " << GVSummary.first << "\n");
+      continue;
+    }
     auto *Summary = GVSummary.second;
     if (auto *AS = dyn_cast<AliasSummary>(Summary))
       Summary = &AS->getAliasee();
     auto *FuncSummary = dyn_cast<FunctionSummary>(Summary);
     if (!FuncSummary)
       // Skip import for global variables
       continue;
     DEBUG(dbgs() << "Initalize import for " << GVSummary.first << "\n");

 
 } // anonymous namespace
 
 /// Compute all the import and export for every module using the Index.
 void llvm::ComputeCrossModuleImport(
     const ModuleSummaryIndex &Index,
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
-    StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
+    StringMap<FunctionImporter::ExportSetTy> &ExportLists,
+    const DenseSet<GlobalValue::GUID> *DeadSymbols) {
   // For each module that has function defined, compute the import/export lists.
   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
     auto &ImportList = ImportLists[DefinedGVSummaries.first()];
     DEBUG(dbgs() << "Computing import for Module '"
                  << DefinedGVSummaries.first() << "'\n");
     ComputeImportForModule(DefinedGVSummaries.second, Index, ImportList,
-                           &ExportLists);
+                           &ExportLists, DeadSymbols);
   }
 
   // When computing imports we added all GUIDs referenced by anything
   // imported from the module to its ExportList. Now we prune each ExportList
   // of any not defined in that module. This is more efficient than checking
   // while computing imports because some of the summary lists may be long
   // due to linkonce (comdat) copies.
   for (auto &ELI : ExportLists) {
#ifndef NDEBUG
   for (auto &Src : ImportList) {
     auto SrcModName = Src.first();
     DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
                  << SrcModName << "\n");
   }
 #endif
 }
 
+DenseSet<GlobalValue::GUID> llvm::computeDeadSymbols(
+    const ModuleSummaryIndex &Index,
+    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
+  if (!ComputeDead)
+    return DenseSet<GlobalValue::GUID>();
+  if (GUIDPreservedSymbols.empty())
+    // Don't do anything when nothing is live, this is friendly with tests.
+    return DenseSet<GlobalValue::GUID>();
+  DenseSet<GlobalValue::GUID> LiveSymbols = GUIDPreservedSymbols;
+  SmallVector<GlobalValue::GUID, 128> Worklist;
+  Worklist.reserve(LiveSymbols.size() * 2);
+  for (auto GUID : LiveSymbols) {
+    DEBUG(dbgs() << "Live root: " << GUID << "\n");
+    Worklist.push_back(GUID);
+  }
+  // Add values flagged in the index as live roots to the worklist.
+  for (const auto &Entry : Index) {
+    bool IsLiveRoot = llvm::any_of(
+        Entry.second,
+        [&](const std::unique_ptr<llvm::GlobalValueSummary> &Summary) {
+          return Summary->liveRoot();
+        });
+    if (!IsLiveRoot)
+      continue;
+    DEBUG(dbgs() << "Live root (summary): " << Entry.first << "\n");
+    Worklist.push_back(Entry.first);
+  }
+
+  while (!Worklist.empty()) {
+    auto GUID = Worklist.pop_back_val();
+    auto It = Index.findGlobalValueSummaryList(GUID);
+    if (It == Index.end()) {
+      DEBUG(dbgs() << "Not in index: " << GUID << "\n");
+      continue;
+    }
+
+    // FIXME: we should only make the prevailing copy live here
+    for (auto &Summary : It->second) {
+      for (auto Ref : Summary->refs()) {
+        auto RefGUID = Ref.getGUID();
+        if (LiveSymbols.insert(RefGUID).second) {
+          DEBUG(dbgs() << "Marking live (ref): " << RefGUID << "\n");
+          Worklist.push_back(RefGUID);
+        }
+      }
+      if (auto *FS = dyn_cast<FunctionSummary>(Summary.get())) {
+        for (auto Call : FS->calls()) {
+          auto CallGUID = Call.first.getGUID();
+          if (LiveSymbols.insert(CallGUID).second) {
+            DEBUG(dbgs() << "Marking live (call): " << CallGUID << "\n");
+            Worklist.push_back(CallGUID);
+          }
+        }
+      }
+      if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {
+        auto AliaseeGUID = AS->getAliasee().getOriginalName();
+        if (LiveSymbols.insert(AliaseeGUID).second) {
+          DEBUG(dbgs() << "Marking live (alias): " << AliaseeGUID << "\n");
+          Worklist.push_back(AliaseeGUID);
+        }
+      }
+    }
+  }
+  DenseSet<GlobalValue::GUID> DeadSymbols;
+  DeadSymbols.reserve(
+      std::min(Index.size(), Index.size() - LiveSymbols.size()));
+  for (auto &Entry : Index) {
+    auto GUID = Entry.first;
+    if (!LiveSymbols.count(GUID)) {
+      DEBUG(dbgs() << "Marking dead: " << GUID << "\n");
+      DeadSymbols.insert(GUID);
+    }
+  }
+  DEBUG(dbgs() << LiveSymbols.size() << " symbols Live, and "
+               << DeadSymbols.size() << " symbols Dead \n");
+  NumDeadSymbols += DeadSymbols.size();
+  NumLiveSymbols += LiveSymbols.size();
+  return DeadSymbols;
+}
+
 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 /// \p ModulePath.
 void llvm::gatherImportedSummariesForModule(
     StringRef ModulePath,
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     const FunctionImporter::ImportMapTy &ImportList,
     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
   // Include all summaries from the importing module.
#endif
     unsigned Flags = Linker::Flags::None;
     if (!ForceImportReferencedDiscardableSymbols)
       Flags |= Linker::Flags::DontForceLinkLinkonceODR;
 
     if (TheLinker.linkInModule(std::move(SrcModule), Flags, &GlobalsToImport))
       report_fatal_error("Function Import: link error");
 
     ImportedCount += GlobalsToImport.size();
+    NumImportedModules++;
   }
 
-  NumImported += ImportedCount;
+  NumImportedFunctions += ImportedCount;
 
   DEBUG(dbgs() << "Imported " << ImportedCount << " functions for Module "
                << DestModule.getModuleIdentifier() << "\n");
   return ImportedCount;
 }
 
 /// Summary file to use for function importing when using -function-import from
 /// the command line.

llvm/trunk/test/ThinLTO/X86/Inputs/deadstrip.ll

+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+declare void @dead_func()
+
+; Called from a @dead_func() in the other file, should not be imported there
+; Ensure the cycle formed by calling @dead_func doesn't prevent stripping.
+define void @baz() {
+    call void @dead_func()
+    ret void
+}
+
+; Called via llvm.global_ctors, should be detected as live via the
+; marking of llvm.global_ctors as a live root in the index.
+define void @boo() {
+  ret void
+}
+
+define void @another_dead_func() {
+    call void @dead_func()
+    ret void
+}

llvm/trunk/test/ThinLTO/X86/deadstrip.ll

+; RUN: opt -module-summary %s -o %t1.bc
+; RUN: opt -module-summary %p/Inputs/deadstrip.ll -o %t2.bc
+; RUN: llvm-lto -thinlto-action=thinlink -o %t.index.bc %t1.bc %t2.bc
+
+; RUN: llvm-lto -exported-symbol=_main -thinlto-action=promote %t1.bc -thinlto-index=%t.index.bc -o - | llvm-lto -exported-symbol=_main -thinlto-action=internalize -thinlto-index %t.index.bc -thinlto-module-id=%t1.bc - -o - | llvm-dis -o - | FileCheck %s
+; RUN: llvm-lto -exported-symbol=_main -thinlto-action=promote %t2.bc -thinlto-index=%t.index.bc -o - | llvm-lto -exported-symbol=_main -thinlto-action=internalize -thinlto-index %t.index.bc -thinlto-module-id=%t2.bc - -o - | llvm-dis -o - | FileCheck %s --check-prefix=CHECK2
+
+; RUN: llvm-lto -exported-symbol=_main -thinlto-action=run %t1.bc %t2.bc
+; RUN: llvm-nm %t1.bc.thinlto.o | FileCheck %s --check-prefix=CHECK-NM
+
+; RUN: llvm-lto2 %t1.bc %t2.bc -o %t.out -save-temps \
+; RUN:   -r %t1.bc,_main,plx \
+; RUN:   -r %t1.bc,_bar,pl \
+; RUN:   -r %t1.bc,_dead_func,pl \
+; RUN:   -r %t1.bc,_baz,l \
+; RUN:   -r %t1.bc,_boo,l \
+; RUN:   -r %t2.bc,_baz,pl \
+; RUN:   -r %t2.bc,_boo,pl \
+; RUN:   -r %t2.bc,_dead_func,pl \
+; RUN:   -r %t2.bc,_another_dead_func,pl
+; RUN: llvm-dis < %t.out.0.3.import.bc | FileCheck %s
+; RUN: llvm-dis < %t.out.1.3.import.bc | FileCheck %s --check-prefix=CHECK2
+; RUN: llvm-nm %t.out.1 | FileCheck %s --check-prefix=CHECK2-NM
+
+; Dead-stripping on the index allows to internalize these,
+; and limit the import of @baz thanks to early pruning.
+; CHECK-NOT: available_externally {{.*}} @baz()
+; CHECK: @llvm.global_ctors =
+; CHECK: define internal void @_GLOBAL__I_a()
+; CHECK: define internal void @bar() {
+; CHECK: define internal void @bar_internal()
+; CHECK: define internal void @dead_func() {
+; CHECK-NOT: available_externally {{.*}} @baz()
+
+; Make sure we didn't internalize @boo, which is reachable via
+; llvm.global_ctors
+; CHECK2: define void @boo()
+; We should have eventually revoved @baz since it was internalized and unused
+; CHECK2-NM-NOT: _baz
+
+; The final binary should not contain any of the dead functions,
+; only main is expected because bar is expected to be inlined and stripped out.
+; CHECK-NM-NOT: bar
+; CHECK-NM-NOT: dead
+; CHECK-NM: T _main
+; CHECK-NM-NOT: bar
+; CHECK-NM-NOT: dead
+
+; Next test the case where Inputs/deadstrip.ll does not get a module index,
+; which will cause it to be handled by regular LTO in the new LTO API.
+; In that case there are uses of @dead_func in the regular LTO partition
+; and it shouldn't be internalized.
+; RUN: opt %p/Inputs/deadstrip.ll -o %t3.bc
+; RUN: llvm-lto2 %t1.bc %t3.bc -o %t4.out -save-temps \
+; RUN:   -r %t1.bc,_main,plx \
+; RUN:   -r %t1.bc,_bar,pl \
+; RUN:   -r %t1.bc,_dead_func,pl \
+; RUN:   -r %t1.bc,_baz,l \
+; RUN:   -r %t1.bc,_boo,l \
+; RUN:   -r %t3.bc,_baz,pl \
+; RUN:   -r %t3.bc,_boo,pl \
+; RUN:   -r %t3.bc,_dead_func,pl \
+; RUN:   -r %t3.bc,_another_dead_func,pl
+; RUN: llvm-dis < %t4.out.1.3.import.bc | FileCheck %s --check-prefix=CHECK-NOTDEAD
+; RUN: llvm-nm %t4.out.0 | FileCheck %s --check-prefix=CHECK-NM-NOTDEAD
+
+; We can't internalize @dead_func because of the use in the regular LTO
+; partition.
+; CHECK-NOTDEAD: define void @dead_func()
+; We also can't eliminate @baz because it is in the regular LTO partition
+; and called from @dead_func.
+; CHECK-NM-NOTDEAD: T _baz
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+
[e-mail]_ctors = appending global [1 x { i32, void ()* }] [{ i32, void ()* } { i32 65535, void ()* @_GLOBAL__I_a }]
+
+declare void @baz()
+
+declare void @boo()
+
+define internal void @_GLOBAL__I_a() #1 section "__TEXT,__StaticInit,regular,pure_instructions" {
+entry:
+    call void @boo()
+    ret void
+}
+
+define void @bar() {
+    ret void
+}
+
+define internal void @bar_internal() {
+    ret void
+}
+
+define void @dead_func() {
+    call void @bar()
+    call void @baz()
+    call void @bar_internal()
+    ret void
+}
+
+define void @main() {
+    call void @bar()
+    call void @bar_internal()
+    ret void
+}