Move summary dead stripping before regular LTO and record results in the combined summary

[eugenis]

Summary

Add a bit to GVFlags to tell ThinLTO backends which values are dead.
Ignored by backends for now.

[pcc]

Can we repurpose the LiveRoot bit to mean Live?

It would also be nice to change computeDeadSymbols to use the Live bit instead of creating a set, but I guess that can be done separately.

[eugenis]

In D33615#766324, @pcc wrote:

Can we repurpose the LiveRoot bit to mean Live?

As in give it a different meaning in combined summary? Looks like we can do that. We'll still need to increase the version number because existing objects have LiveRoot==false for most symbols.

[pcc]

In D33615#766340, @eugenis wrote:

In D33615#766324, @pcc wrote:

Can we repurpose the LiveRoot bit to mean Live?

As in give it a different meaning in combined summary? Looks like we can do that. We'll still need to increase the version number because existing objects have LiveRoot==false for most symbols.

Right, and upgrade old summaries to Live == true.

[mehdi_amini]

Add a bit to GVFlags to tell ThinLTO backends which values are dead.

Why?

[pcc]

In D33615#766505, @mehdi_amini wrote:

Add a bit to GVFlags to tell ThinLTO backends which values are dead.

Why?

See Evgeniy's RFC thread, in particular
http://lists.llvm.org/pipermail/llvm-dev/2017-May/113298.html

[mehdi_amini]

In D33615#766506, @pcc wrote:

In D33615#766505, @mehdi_amini wrote:

Add a bit to GVFlags to tell ThinLTO backends which values are dead.

Why?

See Evgeniy's RFC thread, in particular
http://lists.llvm.org/pipermail/llvm-dev/2017-May/113298.html

I see in this thread why you want to run the dead-stripping before regular LTO, but I don't immediately understand why you're adding these to the combined index and the serialization of it?

[eugenis]

Ouch. Thank you for bringing this to my attention.
Looking at the current cfi-icall patch, this combined summary / serialization code is dead indeed.
The patch somehow evolved to make the isLive() check in ThinLTO backend redundant without me noticing.
I'll revert the summary parts of this change, probably next week.

[eugenis]

In fact, we already have a bit in GVFlags that's not used in ThinLTO backend: LiveRoot, and we need a way to pass this data to RegularLTO pass anyway, so let's use that. I've renamed it to just "Live"; in per-module summaries it is used to mark liveroot globals, and in combined summary it marks all live globals.

It does not have to be serialized, but since we serialize LiveRoot already, there is no regression. I can remove serialization in a separate change, but that would create a situation where part of GVFlags is lost when passed through bitcode, and it could be confusing. Perhaps that should be part of a larger refactoring that would separate data that must be passed from thin link to thin backend from module summary data.

WDYT?

[mehdi_amini]

include/llvm/IR/ModuleSummaryIndex.h

141 ↗

(On Diff #100769)

Still unsure why do we need this? How does it relate to the need to move the dead-stripping earlier in the process?

[eugenis]

To recap: this needs to be in combined summary, because that's the only way to pass information to LowerTypeTests in regularLTO.

Serialization is extra; I can remove it, or rather, make LiveRoot in bitcode always 0. This can be done without bumping bitcode version. Or even remove LiveRoot from bitcode and bump the version number.

[mehdi_amini]

In D33615#768262, @eugenis wrote:

To recap: this needs to be in combined summary, because that's the only way to pass information to LowerTypeTests in regularLTO.

Well you can also pass it as a set just like it is done elsewhere with DeadSymbols.
However, if we go the route of "caching" this analysis result in the summaries, then we should likely kill DeadSymbols because ComputeCrossModuleImport should be able to use the information from the summary directly.

[eugenis]

I've killed DeadSymbols.
ComputeCrossModuleImport may be called w/o computeDeadSymbols. In that case most of the symbols will be marked as dead (at that stage Live works like LiveRoot). I've added a flag in ModuleSummaryIndex to detect this situation.

This flag is not serialized. We don't need it to be serialized, but that same is true for Live / LiveRoot. Actually, LiveRoot serialization was added in D23488 along with bitcode version bump, and, as far as I can see, it was unused from the start. I can kill the whole thing, and maybe even downgrade the version, if no one minds.

[pcc]

lib/Transforms/IPO/FunctionImport.cpp

454 ↗

(On Diff #100920)

Do we need the LiveSymbols set any more? Can we use isLive and setLive to mark summaries as live as we go?

[mehdi_amini]

In D33615#769259, @eugenis wrote:

This flag is not serialized. We don't need it to be serialized, but that same is true for Live / LiveRoot. Actually, LiveRoot serialization was added in D23488 along with bitcode version bump, and, as far as I can see, it was unused from the start. I can kill the whole thing, and maybe even downgrade the version, if no one minds.

I'm not sure I understand this? LiveRoot was added to track things like globals marked as "llvm.used", how would this work without serialization from the compile phase to the thinlink?

[mehdi_amini]

include/llvm/IR/ModuleSummaryIndex.h

536 ↗

(On Diff #100920)

Do not use "GC": let's not switch terminology between multiple places I think we used "Dead-Stripping" till now.

561 ↗

(On Diff #100920)

If you want to go this route of making the index explicitly modal, then GlobalValueSummary::isLive() should be private and the ModuleSummaryIndex can be friended.

lib/LTO/LTO.cpp

636 ↗

(On Diff #100920)

We reached a point where this patch is complex enough that I rather see it split between the change to make the live flags in the summary replacing all the sets (NFC changes) and actually moving the place where it is performed.

[eugenis]

Rebased on (NFC) D33743. Added YAML serialization of GVFlags for use in tests. Added use of new flags in LowerTypeTests and WholeProgramDevirt.

[mehdi_amini]

Thanks for splitting out a large part of the refactoring!

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

The addition of Linkage and NotEligibleToImport are unrelated to this change right? I feel you could commit them separately now.
(even the serialization of "Live" here isn't clear to me if it isn't something that could just be split out).

[pcc]

It looks like you

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

Would we be using Linkage and NotEligibleToImport for anything though? It seems a little odd to add fields here without any test coverage. (That's not to say that we shouldn't add the fields eventually, but I think it should be accompanied by tests, i.e. we should add a JSON summary dumper to llvm-lto2 or something and convert some tests over to use it.)

I think the serialization of Live was part of D33702, and I'd prefer it to be done as part of that change.

[pcc]

In D33615#770592, @pcc wrote:

It looks like you

(sorry, disregard)

[mehdi_amini]

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

Would we be using Linkage and NotEligibleToImport for anything though? It seems a little odd to add fields here without any test coverage.

What are we using the Yaml serialization for? I thought it was intended to be the "primary textual way of dumping summaries"? My comment was in this context: I was seeing this change as "fix missing serialization" and nothing else.

(That's not to say that we shouldn't add the fields eventually, but I think it should be accompanied by tests, i.e. we should add a JSON summary dumper to llvm-lto2 or something and convert some tests over to use it.)

Of course I expect a test for these, but don't we have a test for yaml dump? I was just thinking about using opt to generate a bitcode file with summaries and pretty-print to yaml. (haven't looked at the existing testing right now)

[eugenis]

Let's start with a simpler change. We don't need YAML at all to move dead stripping before regular lto and test it.

[pcc]

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

What are we using the Yaml serialization for? I thought it was intended to be the "primary textual way of dumping summaries"?

That is indeed the end goal, but right now it is only used as a mechanism to test that the lowertypetests and wholeprogramdevirt passes manipulate the summary index correctly.

Of course I expect a test for these, but don't we have a test for yaml dump? I was just thinking about using opt to generate a bitcode file with summaries and pretty-print to yaml. (haven't looked at the existing testing right now)

There's nothing right now that reads bitcode files and then dumps their summaries as YAML. We'd have to add it somewhere, e.g. to llvm-lto2.

[eugenis]

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

There's nothing right now that reads bitcode files and then dumps their summaries as YAML. We'd have to add it somewhere, e.g. to llvm-lto2

Or llvm-bcanalyzer.

Do you want me to remove serialization of Linkage and NotEligibleToImport? It just feels strange to serialize only part of GVFlags. When this serialization is added later, it will require updating all the same tests once again.

[pcc]

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

Do you want me to remove serialization of Linkage and NotEligibleToImport?

I'm fine with leaving it in.

[pcc]

LGTM

[mehdi_amini]

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

FWIW: I disagree with mixing changes that are unrelated with each other: like changing the serialization and moving the position of where we run a pass.

[pcc]

include/llvm/IR/ModuleSummaryIndexYAML.h

132 ↗

(On Diff #101094)

The serialization changes were moved to D33702, but it looks like they were never reverted from this patch. @eugenis can you please take care of that before committing?

[eugenis]

There are no serialization changes here. Are you looking at an older diff by any chance?

[pcc]

In D33615#770978, @eugenis wrote:

There are no serialization changes here. Are you looking at an older diff by any chance?

Sorry, yes, it must have been an older diff.

llvm/trunk/lib/LTO/LTO.cpp

 }
 
 unsigned LTO::getMaxTasks() const {
   CalledGetMaxTasks = true;
   return RegularLTO.ParallelCodeGenParallelismLevel + ThinLTO.ModuleMap.size();
 }
 
 Error LTO::run(AddStreamFn AddStream, NativeObjectCache Cache) {
+  // 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(
+          GlobalValue::dropLLVMManglingEscape(Res.second.IRName)));
+  }
+
+  computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
+
   // Save the status of having a regularLTO combined module, as
   // this is needed for generating the ThinLTO Task ID, and
   // the CombinedModule will be moved at the end of runRegularLTO.
   bool HasRegularLTO = RegularLTO.CombinedModule != nullptr;
   // Invoke regular LTO if there was a regular LTO module to start with.
   if (HasRegularLTO)
     if (auto E = runRegularLTO(AddStream))
       return E;
Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
 
   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) {
-    // 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(
-            GlobalValue::dropLLVMManglingEscape(Res.second.IRName)));
-    }
-
-    computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
-
     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
                              ImportLists, ExportLists);
 
     std::set<GlobalValue::GUID> ExportedGUIDs;
     for (auto &Res : GlobalResolutions) {
       // First check if the symbol was flagged as having external references.
       if (Res.second.Partition != GlobalResolution::External)
         continue;

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

 ; 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
 
+; RUN: llvm-bcanalyzer -dump %t.out.index.bc | FileCheck %s --check-prefix=COMBINED
+; Live, NotEligibleForImport, Internal
+; COMBINED-DAG: <COMBINED {{.*}} op2=55
+; Live, Internal
+; COMBINED-DAG: <COMBINED {{.*}} op2=39
+; Live, External
+; COMBINED-DAG: <COMBINED {{.*}} op2=32
+; COMBINED-DAG: <COMBINED {{.*}} op2=32
+; COMBINED-DAG: <COMBINED {{.*}} op2=32
+; (Dead)
+; COMBINED-DAG: <COMBINED {{.*}} op2=0
+; COMBINED-DAG: <COMBINED {{.*}} op2=0
+; COMBINED-DAG: <COMBINED {{.*}} op2=0
+
 ; 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
+; We should have eventually removed @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