[IPO] Opt-in local clones for thinlto imports

[mtrofin]

Summary

ThinLTO imports (which appear as available_externally) that survive
inlining get deleted. With today's inliner that's reasonable, because
the way the function would be inlined into in other modules would be the
same - because of the bottom-up traversal assumption, and the fact that
the inliner doesn't take into account surrounding context [*]. The
ModuleInliner invalidates the first assumption, and the ML inliner the
second.

This patch adds a way to opt-in a module to keep its variant of an
imported function, even if it survived past inlining.

• Almost. Deferred inlining is an exception which can lead to

(empirically) infrequent discrepancies.

[snehasish]

llvm/lib/Transforms/IPO/ElimAvailExtern.cpp

61

Should we teach sample prof [1] about this new suffix too? On the other hand from the comment it seems like reusing the "__uniq" suffix might be another option?

[1] https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/ProfileData/SampleProf.h#L1079-L1083

[mtrofin]

llvm/lib/Transforms/IPO/ElimAvailExtern.cpp

61

The name could have __uniq already; hmm... if we use __uniq here, too, it seems like that's all that'd be needed for teaching sample prof, right?

[snehasish]

llvm/lib/Transforms/IPO/ElimAvailExtern.cpp

61

Yeah, that's my understanding.

[mtrofin]

use __uniq

[tejohnson]

Can we do this during the importing process? E.g. somewhere in FunctionImportGlobalProcessing::processGlobalForThinLTO.

[mtrofin]

In D150148#4335709, @tejohnson wrote:

Can we do this during the importing process? E.g. somewhere in FunctionImportGlobalProcessing::processGlobalForThinLTO.

(capturing discussion offline) I actually had it that way originally, but there are 2 main complications with it. The most important one is about ICP. If we did this before any ICP for a function F, we'd have to remember the association between F and F.__uniq.123 (the latter is the local copy), so that the ICP test would be in terms of F, not F.__uniq.123. With how the pass is currently positioned, that's not an issue, because ICP happened, and the non-CallBase use of F (the value test, in this case) isn't modified. A good way to keep that association (and make it explicit and intentional) is via metadata, but it'd complicate the implementation.

The second (and related) problem is that we'd also need to update the value profile to reference the new GUID instead of the old one (as GUIDs are computed using both name and linkage), which the current implementation doesn't need to do (and I need to add a comment about that.)

We can revisit this later, of course.

[mtrofin]

more comments

[tejohnson]

Just a few minor comments/suggestions

llvm/lib/Transforms/IPO/ElimAvailExtern.cpp

50

In theory we could have a non-thinlto available_externally function, so maybe rename this to something more generic like convertToCopy.

62

Maybe just pass this in from the caller that already has it.

71

Nit: remove braces

74

Incomplete comment?

114

Nit remove braces around single statement if / else bodies

120–121

This tracks the removed functions (per string in STATISTIC). Maybe add a second one for tracking the number of conversions? If you do so, add -stats to your new test and check it.

[mtrofin]

stats

[tejohnson]

lgtm

llvm/test/Transforms/EliminateAvailableExternally/transform-to-local.ll

2

I think you will need to add a "REQUIRES: asserts" to avoid bot failures as stats requires that.

llvm/lib/Transforms/IPO/ElimAvailExtern.cpp

 //===- ElimAvailExtern.cpp - DCE unreachable internal functions -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This transform is designed to eliminate available external global
 // definitions from the program, turning them into declarations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/ElimAvailExtern.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/Constant.h"
+#include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Module.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/GlobalStatus.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "elim-avail-extern"
 
-STATISTIC(NumFunctions, "Number of functions removed");
+cl::opt<bool> ConvertToLocal(
+    "avail-extern-to-local", cl::Hidden,
+    cl::desc("Convert available_externally into locals, renaming them "
+             "to avoid link-time clashes."));
+
+STATISTIC(NumRemovals, "Number of functions removed");
+STATISTIC(NumConversions, "Number of functions converted");
 STATISTIC(NumVariables, "Number of global variables removed");
 
+void deleteFunction(Function &F) {
+  // This will set the linkage to external
+  F.deleteBody();
+  ++NumRemovals;
+}
+
+/// Create a copy of the thinlto import, mark it local, and redirect direct
+/// calls to the copy. Only direct calls are replaced, so that e.g. indirect
+/// call function pointer tests would use the global identity of the function.
+///
+/// Currently, Value Profiling ("VP") MD_prof data isn't updated to refer to the
+/// clone's GUID (which will be different, because the name and linkage is
+/// different), under the assumption that the last consumer of this data is
+/// upstream the pipeline (e.g. ICP).
+static void convertToLocalCopy(Module &M, Function &F) {
+  assert(F.hasAvailableExternallyLinkage());
+  assert(!F.isDeclaration());
+  // If we can't find a single use that's a call, just delete the function.
+  if (F.uses().end() == llvm::find_if(F.uses(), [&](Use &U) {
+        return isa<CallBase>(U.getUser());
+      }))
+    return deleteFunction(F);
+
+  auto OrigName = F.getName().str();
+  // Build a new name. We still need the old name (see below).
+  // We could just rely on internal linking allowing 2 modules have internal
+  // functions with the same name, but that just creates more trouble than
+  // necessary e.g. distinguishing profiles or debugging. Instead, we append the
+  // module identifier.
+  auto NewName = OrigName + ".__uniq" + getUniqueModuleId(&M);
+  F.setName(NewName);
+  if (auto *SP = F.getSubprogram())
+    SP->replaceLinkageName(MDString::get(F.getParent()->getContext(), NewName));
+
+  F.setLinkage(GlobalValue::InternalLinkage);
+  // Now make a declaration for the old name. We'll use it if there are non-call
+  // uses. For those, it would be incorrect to replace them with the local copy:
+  // for example, one such use could be taking the address of the function and
+  // passing it to an external function, which, in turn, might compare the
+  // function pointer to the original (non-local) function pointer, e.g. as part
+  // of indirect call promotion.
+  auto *Decl =
+      Function::Create(F.getFunctionType(), GlobalValue::ExternalLinkage,
+                       F.getAddressSpace(), OrigName, F.getParent());
+  F.replaceUsesWithIf(Decl,
+                      [&](Use &U) { return !isa<CallBase>(U.getUser()); });
+  ++NumConversions;
+}
+
 static bool eliminateAvailableExternally(Module &M) {
   bool Changed = false;
 
   // Drop initializers of available externally global variables.
   for (GlobalVariable &GV : M.globals()) {
     if (!GV.hasAvailableExternallyLinkage())
       continue;
     if (GV.hasInitializer()) {
       Constant *Init = GV.getInitializer();
       GV.setInitializer(nullptr);
       if (isSafeToDestroyConstant(Init))
         Init->destroyConstant();
     }
     GV.removeDeadConstantUsers();
     GV.setLinkage(GlobalValue::ExternalLinkage);
-    NumVariables++;
+    ++NumVariables;
     Changed = true;
   }
 
   // Drop the bodies of available externally functions.
-  for (Function &F : M) {
-    if (!F.hasAvailableExternallyLinkage())
+  for (Function &F : llvm::make_early_inc_range(M)) {
+    if (F.isDeclaration() || !F.hasAvailableExternallyLinkage())
       continue;
-    if (!F.isDeclaration())
-      // This will set the linkage to external
-      F.deleteBody();
+
+    if (ConvertToLocal)
+      convertToLocalCopy(M, F);
+    else
+      deleteFunction(F);
+
     F.removeDeadConstantUsers();
-    NumFunctions++;
     Changed = true;
   }
 
   return Changed;
 }
 
 PreservedAnalyses
 EliminateAvailableExternallyPass::run(Module &M, ModuleAnalysisManager &) {
   if (!eliminateAvailableExternally(M))
     return PreservedAnalyses::all();
   return PreservedAnalyses::none();
 }

llvm/test/Transforms/EliminateAvailableExternally/transform-to-local.ll

+; REQUIRES: asserts
+; RUN: opt -passes=elim-avail-extern -avail-extern-to-local -stats -S 2>&1 < %s | FileCheck %s
+
+
+declare void @call_out(ptr %fct)
+
+define available_externally hidden void @f() {
+  ret void
+}
+
+define available_externally hidden void @g() {
+  ret void
+}
+
+define void @hello(ptr %g) {
+  call void @f()
+  %f = load ptr, ptr @f
+  call void @call_out(ptr %f)
+  ret void
+}
+
+; CHECK: define internal void @f.__uniq.{{[0-9|a-f]*}}()
+; CHECK: declare hidden void @g()
+; CHECK: call void @f.__uniq.{{[0-9|a-f]*}}()
+; CHECK-NEXT: load ptr, ptr @f
+; CHECK-NEXT: call void @call_out(ptr %f)
+; CHECK: Statistics Collected
+; CHECK: 1 elim-avail-extern - Number of functions converted
+; CHECK: 1 elim-avail-extern - Number of functions removed
 No newline at end of file