Put "built-in" function definitions in global Used list, for LTO. (fix bug 34169)

[cmtice]

Summary

When building with LTO, builtin functions that are defined but whose calls have not been inserted yet, get internalized. The Global Dead Code Elimination phase in the new LTO implementation then removes these function definitions. Later optimizations add calls to those functions, and the linker then dies complaining that there are no definitions. This CL fixes the new LTO implementation to check if a function is builtin, and if so, to not internalize (and later DCE) the function. As part of this fix I needed to move the RuntimeLibcalls.{def,h} files from the CodeGen subidrectory to the IR subdirectory. I have updated all the files that accessed those two files to access their new location.

Fixes PR34169

[tejohnson]

lib/Transforms/IPO/GlobalOpt.cpp

2929

I'm not sure if this is the right place to do this, since it doesn't need to be done iteratively, only once. I.e. this code is executed "while (LocalChange)".

Wondering if other reviewers have thoughts on where the right place to add these to the used is.

test/ThinLTO/X86/builtin-nostrip.ll

1

You will probably need to add a line like:
; REQUIRES: x86-registered-target

to prevent non-x86 bot failures.

15

Need to add an llvm-nm invocation on the correct object file emitted by llvm-lto2. Otherwise you aren't doing any checking like you are for llvm-lto above.

22

This llvm-lto2 invocation is exactly the same as the prior one - I don't think you should do this twice?

51

Needs some kind of FileCheck on one of the output files, similar to my earlier comment on the first llvm-lto2 invocation.

[pcc]

I don't think that globalopt is the right place for this because there is no guarantee that the pass is run. If we wanted to do something about this, it seems like a better place would be in lib/Analysis/ModuleSummaryAnalysis.cpp where we decide which functions are GC roots.

Also this is only a subset of the functions that the code generator can generate calls to. There is a list of runtime functions in llvm/include/llvm/CodeGen/RuntimeLibcalls.def, but as far as I know it isn't 100% comprehensive. Using that list would probably be better than just 3 functions though.

[cmtice]

pcc@ Originally I tried to make the change in ModuleSummaryAnalysis.cpp, but it turns out that this is not allowed in LLVM: I am not supposed to make changes to the IR in the Analysis layer of LLVM. I need to find some place in the Transform layer to make the change. Hence my first guess as to a location: GlobalOpt.cpp. I would be happy to make the change in some other location instead, but it must be someplace in the Transform layer.

[pcc]

You wouldn't be making changes to the IR, only the summary. I was thinking that you might add code to http://llvm-cs.pcc.me.uk/lib/Analysis/ModuleSummaryAnalysis.cpp#534 that would effectively do:

if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID("memcpy")))
    for (auto &Summary : VI.getSummaryList())
      Summary->setLive(true);
if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID("memmove")))
    for (auto &Summary : VI.getSummaryList())
      Summary->setLive(true);
// etc.

[tejohnson]

In D49434#1165612, @pcc wrote:

You wouldn't be making changes to the IR, only the summary. I was thinking that you might add code to http://llvm-cs.pcc.me.uk/lib/Analysis/ModuleSummaryAnalysis.cpp#534 that would effectively do:

if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID("memcpy")))
    for (auto &Summary : VI.getSummaryList())
      Summary->setLive(true);
if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID("memmove")))
    for (auto &Summary : VI.getSummaryList())
      Summary->setLive(true);
// etc.

If I recall correctly it wasn't the LTO dead code elimination that was removing them. Caroline, I forget what was happening in the original case - were they being internalized by LTO and then eliminated by GlobalDCE? If so, then Peter's approach should fix the issue by preventing them from being internalized (at least by ThinLTO, not sure about regular LTO).

[echristo]

In D49434#1165381, @pcc wrote:

I don't think that globalopt is the right place for this because there is no guarantee that the pass is run. If we wanted to do something about this, it seems like a better place would be in lib/Analysis/ModuleSummaryAnalysis.cpp where we decide which functions are GC roots.

Also this is only a subset of the functions that the code generator can generate calls to. There is a list of runtime functions in llvm/include/llvm/CodeGen/RuntimeLibcalls.def, but as far as I know it isn't 100% comprehensive. Using that list would probably be better than just 3 functions though.

FWIW I agree. Having a more central place that these functions are gotten will help avoid a "just this function, and this one" set of patches in the future.

[steven_wu]

In D49434#1165761, @tejohnson wrote:

In D49434#1165612, @pcc wrote:

You wouldn't be making changes to the IR, only the summary. I was thinking that you might add code to http://llvm-cs.pcc.me.uk/lib/Analysis/ModuleSummaryAnalysis.cpp#534 that would effectively do:

if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID("memcpy")))
    for (auto &Summary : VI.getSummaryList())
      Summary->setLive(true);
if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID("memmove")))
    for (auto &Summary : VI.getSummaryList())
      Summary->setLive(true);
// etc.

If I recall correctly it wasn't the LTO dead code elimination that was removing them. Caroline, I forget what was happening in the original case - were they being internalized by LTO and then eliminated by GlobalDCE? If so, then Peter's approach should fix the issue by preventing them from being internalized (at least by ThinLTO, not sure about regular LTO).

The legacy LTOCodeGenerator has a preserve list which you can declare symbols to preserve (which is essentially the same mechanism as this implementation). Not sure what is the equivalent for the C++ API but I guess you can just reuse that?

[cmtice]

pcc's original suggested fix did not work, because the real issue was the function definitions being initially internalized by LTO and later DCE'd. Peter's suggestion did not prevent them from being internalized. I consulted with him offline and we came up with this alternative solution. It fixes the issue for the new LTO implemention. The old LTO implementation still internalizes the function definitions, but they do not get Dead Code Eliminated. I have also fixed the test case, and have generalized the code to check for all builtin functions (as requested).

[tejohnson]

In D49434#1168858, @cmtice wrote:

The old LTO implementation still internalizes the function definitions, but they do not get Dead Code Eliminated.

Quick clarification based on our discussion earlier - the old LTO implementation internalizes but does not eliminate with regular LTO. The old LTO implementation with ThinLTO is still broken (hence that part of the test is currently disabled).

[pcc]

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

28 ↗

(On Diff #156360)

I don't think we should move RuntimeLibcalls.h (because it references CodeGen internals), just RuntimeLibcalls.def.

lib/Object/IRSymtab.cpp

26 ↗

(On Diff #156360)

With my suggestion for the array you shouldn't need to include this header.

46 ↗

(On Diff #156360)

I think this can just be a statically initialized array. You can use something like:

static const char *LibcallRoutineNames[] = {
#define HANDLE_LIBCALL(code, name) name,
#include "llvm/IR/RuntimeLibcalls.def"
};

239 ↗

(On Diff #156360)

Use CamelCase to match the surrounding style.

241 ↗

(On Diff #156360)

Use a range for loop to enumerate this array.

[cmtice]

I've made Peter's suggested changes.

[pcc]

lib/Object/IRSymtab.cpp

235 ↗

(On Diff #156500)

IsBuiltinFunc

237 ↗

(On Diff #156500)

I don't think we need this FIXME. As far as I know, this problem is already "solved" in the old LTO API by the client providing an appropriate preserve list.

241 ↗

(On Diff #156500)

LibcallName

test/ThinLTO/X86/builtin-nostrip.ll

2

A lot of this test case can be removed I think.

• You just need one libcall function, testing more than one wouldn't give you additional coverage.
• A lot of the test input (including the second input file) is irrelevant to what you're trying to test. Basically I think this test just needs two functions, both with resolution p, one which is a libcall and one which isn't, and you would test that the first one is kept and the second one isn't.
• Remove the parts about the old LTO API because the problem is solved in a different way there.

[tejohnson]

lib/Object/IRSymtab.cpp

237 ↗

(On Diff #156500)

I disagree regarding the old LTO API - just as we are solving it here for all clients of the new LTO API, I think it would be nice to be consistent and user-friendly to solve it in a similar way in the old LTO API. However, I don't believe the FIXME belongs here. I would just move it to the new test case above the llvm-lto line that has the commented out llvm-nm check.

[cmtice]

Made requested fixes.

[steven_wu]

For the old API, I don't think it is reasonable to expect user or linker to pass in the correct preserve list. There is likely no knowledge outside the LTO modules that these lib funcs are needed.

In D49434#1168948, @tejohnson wrote:

In D49434#1168858, @cmtice wrote:

The old LTO implementation still internalizes the function definitions, but they do not get Dead Code Eliminated.

Quick clarification based on our discussion earlier - the old LTO implementation internalizes but does not eliminate with regular LTO. The old LTO implementation with ThinLTO is still broken (hence that part of the test is currently disabled).

This also sounds pretty fragile (not just LTO, but in general). If you have a module with implementation of memcpy and all you have is memcpy builtin function, DCE might just cause linker failure. I wonder the problem should be solved in a lower level.
People who actually implement libfunc in the module are probably working on some embedded environment and code size is probably a big concern. It would be good if those libfuncs can be eliminated when it is safe to do so.

[pcc]

In D49434#1170189, @steven_wu wrote:

For the old API, I don't think it is reasonable to expect user or linker to pass in the correct preserve list. There is likely no knowledge outside the LTO modules that these lib funcs are needed.

I was under the impression that that was how things worked already on Apple platforms but given that it isn't, I agree.

In D49434#1168948, @tejohnson wrote:

In D49434#1168858, @cmtice wrote:

The old LTO implementation still internalizes the function definitions, but they do not get Dead Code Eliminated.

Quick clarification based on our discussion earlier - the old LTO implementation internalizes but does not eliminate with regular LTO. The old LTO implementation with ThinLTO is still broken (hence that part of the test is currently disabled).

This also sounds pretty fragile (not just LTO, but in general). If you have a module with implementation of memcpy and all you have is memcpy builtin function, DCE might just cause linker failure. I wonder the problem should be solved in a lower level.
People who actually implement libfunc in the module are probably working on some embedded environment and code size is probably a big concern. It would be good if those libfuncs can be eliminated when it is safe to do so.

I would imagine that folks who care about code size would be linking with --gc-sections (or -dead_strip in ld64) so the library functions would end up being dropped if they aren't actually needed.

[steven_wu]

In D49434#1170267, @pcc wrote:

I would imagine that folks who care about code size would be linking with --gc-sections (or -dead_strip in ld64) so the library functions would end up being dropped if they aren't actually needed.

This is true.

This also sounds pretty fragile (not just LTO, but in general). If you have a module with implementation of memcpy and all you have is memcpy builtin function, DCE might just cause linker failure. I wonder the problem should be solved in a lower level.

Now I think again, it seems this is LTO specific because I can't think of any other condition that those function can be internal.

In D49434#1170267, @pcc wrote:

In D49434#1170189, @steven_wu wrote:

For the old API, I don't think it is reasonable to expect user or linker to pass in the correct preserve list. There is likely no knowledge outside the LTO modules that these lib funcs are needed.

I was under the impression that that was how things worked already on Apple platforms but given that it isn't, I agree.

No, it doesn't work. I think it just happens that regularLTO from old API doesn't actually drop them. I think it would be better to update the Internalize pass used by regularLTO C API to not internalize those function to be safe (it already has an exception for stack protector symbols) just in case. The thinLTO C API shouldn't be that hard to fix as well. I am ok to fix them with a separate commits.

[cmtice]

I just realized that my patch did not contain the actual move of RuntimeLibcalls.def from CodeGen to IR. This update includes that move.

[pcc]

test/ThinLTO/X86/builtin-nostrip.ll

2

Can you simplify the test case as I suggested? I think the first two bullet points should still apply.

[cmtice]

Simplify test case, as requested by Peter.

I *think* this takes care of all the changes I was requested to make. Have I missed any?

[pcc]

LGTM

test/ThinLTO/X86/builtin-nostrip.ll

41

Comment should refer to __stack_chk_fail.

[tejohnson]

Hi Caroline, I was looking at this patch as I needed to reference it in another discussion, and realized there was no test committed with the patch. Looks like old review comments exist for a test/ThinLTO/X86/builtin-nostrip.ll on a prior version of the patch, but that seems to have disappeared on the version that got committed (probably just a mistake during the commit process since it was a new file). Can you grab that test off the prior diff and commit it now?

[cmtice]

Test case has been committed, as of revision 357409.

lib/Transforms/IPO/GlobalOpt.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/CtorUtils.h"
 #include "llvm/Transforms/Utils/Evaluator.h"
 #include "llvm/Transforms/Utils/GlobalStatus.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <cassert>
 #include <cstdint>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "globalopt"
static bool optimizeGlobalsInModule(
   while (LocalChange) {
     LocalChange = false;
 
     NotDiscardableComdats.clear();
     for (const GlobalVariable &GV : M.globals())
       if (const Comdat *C = GV.getComdat())
         if (!GV.isDiscardableIfUnused() || !GV.use_empty())
           NotDiscardableComdats.insert(C);
-    for (Function &F : M)
+    for (Function &F : M) {
+      if (F.getName() == "__stack_chk_fail" ||
+          F.getName() == "memcpy" ||
+          F.getName() == "memmove") {
+        appendToUsed(M, &F);
+      }
       if (const Comdat *C = F.getComdat())
         if (!F.isDefTriviallyDead())
           NotDiscardableComdats.insert(C);
+    }
     for (GlobalAlias &GA : M.aliases())
       if (const Comdat *C = GA.getComdat())
         if (!GA.isDiscardableIfUnused() || !GA.use_empty())
           NotDiscardableComdats.insert(C);
 
     // Delete functions that are trivially dead, ccc -> fastcc
     LocalChange |= OptimizeFunctions(M, TLI, GetTTI, GetBFI, LookupDomTree,
                                      NotDiscardableComdats);

test/ThinLTO/X86/Inputs/builtin-nostrip.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+
+; 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
+}

test/ThinLTO/X86/builtin-nostrip.ll

+; RUN: opt -module-summary %s -o %t1.bc
+; RUN: opt -module-summary %p/Inputs/builtin-nostrip.ll -o %t2.bc
+
+; 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,boo,l \
+; RUN:   -r %t1.bc,live_available_externally_func,l \
+; RUN:   -r %t1.bc,__stack_chk_fail,pl \
+; RUN:   -r %t1.bc,memmove,pl \
+; RUN:   -r %t1.bc,memcpy,pl \
+; RUN:   -r %t2.bc,boo,pl
+
+; The final binary should not contain any of the dead functions;
+; make sure _stack_chk_fail is there.
+; CHECK-NM-NOT: bar
+; CHECK-NM: t __stack_chk_fail
+
+; 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,boo,l \
+; RUN:   -r %t1.bc,live_available_externally_func,l \
+; RUN:   -r %t1.bc,__stack_chk_fail,pl \
+; RUN:   -r %t1.bc,memmove,pl \
+; RUN:   -r %t1.bc,memcpy,pl \
+; RUN:   -r %t2.bc,boo,pl
+
+; The final binary should not contain any of the dead functions;
+; make sure memmove and memcpy are there.
+; CHECK-NM-NOT: bar
+; CHECK-NM: t memcpy
+; CHECK-NM: t memmove
+
+; Next test the case where Inputs/builtin-nostrip.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/builtin-nostrip.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,boo,l \
+; RUN:   -r %t1.bc,live_available_externally_func,l \
+; RUN:   -r %t1.bc,__stack_chk_fail,pl \
+; RUN:   -r %t1.bc,memmove,pl \
+; RUN:   -r %t1.bc,memcpy,pl \
+; RUN:   -r %t3.bc,boo,pl 
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+
[e-mail]_ctors = appending global [1 x { i32, void ()* }] [{ i32, void ()* } { i32 65535, void ()* @_GLOBAL__I_a }]
+
+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 void @__stack_chk_fail() {
+    ret void
+}
+
+define void @memmove() {
+    ret void
+}
+
+define void @memcpy() {
+    ret void
+}
+
+define available_externally void @live_available_externally_func() {
+    ret void
+}
+
+define void @main() {
+    call void @bar()
+    call void @live_available_externally_func()
+    ret void
+}