[ThinLTO] Keep available_externally symbols live

[vlad.tsyrklevich]

Summary

This change fixes PR36483. The bug was originally introduced by a change
that marked non-prevailing symbols dead. This broke LowerTypeTests
handling of available_externally functions, which are non-prevailing.
LowerTypeTests uses liveness information to avoid emitting thunks for
unused functions.

Marking available_externally functions dead is incorrect, the functions
are used though the function definitions are not. This change keeps them
live, and lets the EliminateAvailableExternally/GlobalDCE passes remove
them later instead.

I've also enabled EliminateAvailableExternally for all optimization
levels, I believe it being disabled for O1 was an oversight.

[pcc]

This seems like a reasonable fix to me, but I'd like to know what Teresa thinks.

[tejohnson]

Sorry for the delay, I was OOO for awhile and am still catching up.

lib/Transforms/IPO/FunctionImport.cpp

548

Is it possible to have a symbol that is weak in one module and available_externally in another? If so, it would be more correct to return only if none of the copies is available_externally.

lib/Transforms/IPO/PassManagerBuilder.cpp

523 ↗

(On Diff #135683)

Thanks for this fix. Can you commit separately with a test?

[pcc]

lib/Transforms/IPO/FunctionImport.cpp

548

I suppose so. In the situation where we have at least one available-externally we could end up needing a symbol referenced by the available-externally as a result of a backend inlining it into a caller. So we would need to keep them live anyway.

Now that I think about it, this applies to linkonce-odr as well (i.e. we could convert them to available-externally as a result of non-prevailing, and then inline them in the backend and thus end up needing a symbol that was referenced by the available-externally but not necessarily by the prevailing copy of the global). But that's somewhat of an orthogonal problem to this.

[vlad.tsyrklevich]

lib/Transforms/IPO/FunctionImport.cpp

548

As I mentioned to @pcc, his example would not be true for ThinLTO as of D42107 because it deletes dead symbols in lto::thinBackend. I'm not sure if it's possible to reach that case with regular LTO.

@tejohnson I think that case is technically possible; however, it would re-introduce the same bug that D42107 originally tried to fix: https://bugs.llvm.org/show_bug.cgi?id=35938

Give that, I'm not sure if there's a way to reconcile that change with this one. I'm not sure if marking individual symbols live/not-live is feasible?

[vlad.tsyrklevich]

• Change the logic to set symbols live to match what Teresa suggested
• Remove PassManagerBuilder change

[llvm-commits]

• msg-28320-371.txt162 BDownload

[tejohnson]

LGTM with fixes noted below.

lib/Transforms/IPO/FunctionImport.cpp

557

else if can be used here.

558

This is only used in the assert, so I suspect you will need to guard with #ifndef NDEBUG to avoid a warning about unused variable.

[vlad.tsyrklevich]

Address Teresa's comments

[twoh]

Hello, I wonder if we need to keep linkonce_odr symbols live here as well. I observe a case that a vtable for template class initiated has linkonce_odr linkage and marked dead here, which results compiler crash at WholeProgramDevirt because the global variable for vtable doesn't have initializer (https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/WholeProgramDevirt.cpp#L676 assumes that GV has the initializer). Thanks!

[mehdi_amini]

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

550 ↗

(On Diff #137617)

This explanation is not clear to me. I understand that this is fixing a bug (crash), but it isn't clear as of *why* this is the right fix?
I'm not sure why would the simple fact that a function is defined somewhere as "available eternally" would be enough to make them "live" if we don't have any reference anywhere to make them live for another reason?

[vlad.tsyrklevich]

In D43690#1201965, @twoh wrote:

Hello, I wonder if we need to keep linkonce_odr symbols live here as well. I observe a case that a vtable for template class initiated has linkonce_odr linkage and marked dead here, which results compiler crash at WholeProgramDevirt because the global variable for vtable doesn't have initializer (https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/WholeProgramDevirt.cpp#L676 assumes that GV has the initializer). Thanks!

I'm not sure why a linkonce_odr GV would be marked non-prevailing. Do you have a minimized example to look at?

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

550 ↗

(On Diff #137617)

I believe the logic here is actually different. https://reviews.llvm.org/D42107 changed the live root analysis to mark non-prevailing symbols as not live even if they are reachable. I changed the logic here to continue to mark available_externally symbols live only if they're reachable.

[mehdi_amini]

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

550 ↗

(On Diff #137617)

OK, if so then I misunderstood what's going on, but I'm also a bit lost with why are these symbols special with respect to liveness. I.e. why is it OK to make other "non-prevailing" symbols not live but not these ones? The comment just says "to not-live breaks downstreams users of liveness information", which falls a bit short for me to really understand the "why" here.

[mehdi_amini]

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

550 ↗

(On Diff #137617)

The "mark non-prevailing symbols as not live even if they are reachable" isn't clear to me either, but at this point I'm probably not up-to-date on the subtleties of "prevailing" vs "live" concept (Apple does not use "prevailing" as a concept)

[trentxintong]

In D43690#1206049, @vlad.tsyrklevich wrote:

In D43690#1201965, @twoh wrote:

Hello, I wonder if we need to keep linkonce_odr symbols live here as well. I observe a case that a vtable for template class initiated has linkonce_odr linkage and marked dead here, which results compiler crash at WholeProgramDevirt because the global variable for vtable doesn't have initializer (https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/WholeProgramDevirt.cpp#L676 assumes that GV has the initializer). Thanks!

I'm not sure why a linkonce_odr GV would be marked non-prevailing. Do you have a minimized example to look at?

Hi @vlad.tsyrklevich, @twoh

I am working on creating a reduced test case. Will get back to you.
Thanks

In D43690#1206049, @vlad.tsyrklevich wrote:

In D43690#1201965, @twoh wrote:

Hello, I wonder if we need to keep linkonce_odr symbols live here as well. I observe a case that a vtable for template class initiated has linkonce_odr linkage and marked dead here, which results compiler crash at WholeProgramDevirt because the global variable for vtable doesn't have initializer (https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/WholeProgramDevirt.cpp#L676 assumes that GV has the initializer). Thanks!

I'm not sure why a linkonce_odr GV would be marked non-prevailing. Do you have a minimized example to look at?

[vlad.tsyrklevich]

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

550 ↗

(On Diff #137617)

Prevailing is used to describe which definition of a symbol (e.g. with interposable linkage where multiple definition are available) is to be included in the final link. If you look at D42107 it's fixing https://bugs.llvm.org/show_bug.cgi?id=35938: when LTO marked the ELF symbol as prevailing, previously the ThinLTO symbol would still be marked live and internalized. D42107 was meant to address that; however, available_externally symbols are never prevailing--they are never meant to be included in the final build output. This means that even if one is called it would not have been marked live, and downstream passes like LowerTypeTests would not know that that symbol is actually used and emit jumptable entries for that symbol. We add special handling for available_externally because as far as I'm aware it should be the only linkage type that could hit this edge case (it's not prevailing but references to it are live, they are just replaced with references to a DSO instead.)

[trentxintong]

In D43690#1206134, @trentxintong wrote:

In D43690#1206049, @vlad.tsyrklevich wrote:

In D43690#1201965, @twoh wrote:

Hello, I wonder if we need to keep linkonce_odr symbols live here as well. I observe a case that a vtable for template class initiated has linkonce_odr linkage and marked dead here, which results compiler crash at WholeProgramDevirt because the global variable for vtable doesn't have initializer (https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/WholeProgramDevirt.cpp#L676 assumes that GV has the initializer). Thanks!

I'm not sure why a linkonce_odr GV would be marked non-prevailing. Do you have a minimized example to look at?

Hi @vlad.tsyrklevich, @twoh

I am working on creating a reduced test case. Will get back to you.
Thanks

In D43690#1206049, @vlad.tsyrklevich wrote:

In D43690#1201965, @twoh wrote:

Hello, I wonder if we need to keep linkonce_odr symbols live here as well. I observe a case that a vtable for template class initiated has linkonce_odr linkage and marked dead here, which results compiler crash at WholeProgramDevirt because the global variable for vtable doesn't have initializer (https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/WholeProgramDevirt.cpp#L676 assumes that GV has the initializer). Thanks!

I'm not sure why a linkonce_odr GV would be marked non-prevailing. Do you have a minimized example to look at?

Hi @vlad.tsyrklevich @twoh

I file this bug report here. I would like to fix this bug. Can you help me ? In the bug, we have a file (main.cpp) that gets compiled to ELF directly, and (unknown.cpp) that gets compiled to IR object file. At link stage, the vtable for class B in the ELF file is the prevailing one and the one in the IR object files does not get picked and linked into Composite by the IRMover. WMD expects the the vtable to be a definition with initializer (we have a declaration for it after IR linking).
As for the solution, I wonder whether we should/could change the linkage info in the GV summary information here since we changed the GV's linkage. https://github.com/llvm-mirror/llvm/blob/master/lib/LTO/LTO.cpp#L664

https://bugs.llvm.org/show_bug.cgi?id=38672

Thanks

lib/Transforms/IPO/FunctionImport.cpp

auto visit = [&](ValueInfo VI) {
     // to functions marked dead are skipped.
     VI = updateValueInfoForIndirectCalls(Index, VI);
     if (!VI)
       return;
     for (auto &S : VI.getSummaryList())
       if (S->isLive())
         return;
 
-    // We do not keep live symbols that are known to be non-prevailing.
-    if (isPrevailing(VI.getGUID()) == PrevailingType::No)
+    // We only keep live symbols that are known to be non-prevailing if any are
+    // available_externally. Those symbols are discarded later in the
+    // EliminateAvailableExternally pass and setting them to not-live breaks
+    // downstreams users of liveness information (PR36483).
+    if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
+      bool AvailableExternally = false;
+      bool Interposable = false;
+      for (auto &S : VI.getSummaryList()) {
+        if (S->linkage() == GlobalValue::AvailableExternallyLinkage)
+          AvailableExternally = true;
+        if (GlobalValue::isInterposableLinkage(S->linkage()))
+          Interposable = true;
+      }
+
+      if (!AvailableExternally)
         return;
 
+      assert(!Interposable && "Interposable and available_externally symbol");
+    }
+
     for (auto &S : VI.getSummaryList())
       S->setLive(true);
     ++LiveSymbols;
     Worklist.push_back(VI);
   };
 
   while (!Worklist.empty()) {
     auto VI = Worklist.pop_back_val();

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 run %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 %t1.bc,_live_available_externally_func,l \
 ; RUN:   -r %t2.bc,_baz,pl \
 ; RUN:   -r %t2.bc,_boo,pl \
 ; RUN:   -r %t2.bc,_dead_func,l \
 ; RUN:   -r %t2.bc,_another_dead_func,pl
 ; RUN: llvm-dis < %t.out.1.3.import.bc | FileCheck %s --check-prefix=LTO2
 ; RUN: llvm-dis < %t.out.2.3.import.bc | FileCheck %s --check-prefix=LTO2-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, dso_local, Internal
 ; COMBINED-DAG: <COMBINED {{.*}} op2=119
 ; Live, dso_local, Internal
 ; COMBINED-DAG: <COMBINED {{.*}} op2=103
+; Live, Local, AvailableExternally
+; COMBINED-DAG: <COMBINED {{.*}} op2=97
 ; Live, Local, External
 ; COMBINED-DAG: <COMBINED {{.*}} op2=96
 ; COMBINED-DAG: <COMBINED {{.*}} op2=96
 ; COMBINED-DAG: <COMBINED {{.*}} op2=96
 ; Local, (Dead)
 ; COMBINED-DAG: <COMBINED {{.*}} op2=64
 ; COMBINED-DAG: <COMBINED {{.*}} op2=64
 ; COMBINED-DAG: <COMBINED {{.*}} op2=64

 ; and it shouldn't be internalized.
 ; RUN: opt %p/Inputs/deadstrip.ll -o %t3.bc
 ; RUN: llvm-lto2 run %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 %t1.bc,_live_available_externally_func,l \
 ; RUN:   -r %t3.bc,_baz,pl \
 ; RUN:   -r %t3.bc,_boo,pl \
 ; RUN:   -r %t3.bc,_dead_func,l \
 ; 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

 
 define void @dead_func() {
     call void @bar()
     call void @baz()
     call void @bar_internal()
     ret void
 }
 
+define available_externally void @live_available_externally_func() {
+    ret void
+}
+
 define void @main() {
     call void @bar()
     call void @bar_internal()
+    call void @live_available_externally_func()
     ret void
 }

test/Transforms/FunctionImport/Inputs/not-prevailing.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define weak i32 @foo() {
+  ret i32 0
+}

test/Transforms/FunctionImport/not-prevailing.ll

+; RUN: opt -module-summary %s -o %t1.bc
+; RUN: opt -module-summary -o %t2.bc %S/Inputs/not-prevailing.ll
+; RUN: not --crash llvm-lto2 run -o %t3.bc %t1.bc %t2.bc -r %t1.bc,bar,px \
+; RUN:     -r %t1.bc,foo,x -r %t2.bc,foo,x -save-temps 2>&1 | FileCheck %s
+
+; CHECK: Assertion `!Interposable
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define available_externally i32 @foo() {
+  ret i32 1
+}
+
+define i32 @bar() {
+  %1 = call i32 @foo()
+  ret i32 %1
+}