[MergeFuncs] Generate alias instead of thunk if possible (default disabled)

[nikic]

Summary

The MergeFunctions pass was originally intended to emit aliases
instead of thunks where possible (unnamed_addr). However, for a
long time this functionality was behind a flag hardcoded to false,
bitrotted and was eventually removed in
https://github.com/llvm-mirror/llvm/commit/f9f40b539b1dc44b10184684aa3f72e1192c454f.

Originally the functionality was first disabled in
https://github.com/llvm-mirror/llvm/commit/664040a03c17f432a127a35013eeb6b6a26e41fb
due to lack of support for aliases in Mach-O. I believe that this
is no longer the case nowadays, but not really familiar with this
area.

In the interest of being conservative, this patch reintroduces the
aliasing functionality (with some fixes) behind a default disabled
-mergefunc-use-aliases flag.

[whitequark]

lib/Transforms/IPO/MergeFunctions.cpp

803 ↗

(On Diff #169682)

Can you explain this logic a bit? It's not clear to me why the condition should be written like that (two canCreateAliasFor` calls).

[nikic]

lib/Transforms/IPO/MergeFunctions.cpp

803 ↗

(On Diff #169682)

The idea here is that we need both of the writeThunkOrAlias calls below to succeed, otherwise we might be leaving behind functions in a partially rewired state. Both calls will succeed if either both G and H below can be converted to aliases (are global unnamed addr) or if a thunk for F below is profitable.

The renaming that is going on here makes it slightly confusing, in that H below corresponds to F here for the purpose of the (signature-based) alias check and F below corresponds to F here for the purpose of the (body-based) thunk-profitability check.

[whitequark]

lib/Transforms/IPO/MergeFunctions.cpp

803 ↗

(On Diff #169682)

Right. Do you think you can add this as a comment?

[nikic]

Added comment about thunk/alias checks for the weak-weak case. Also renamed the function H to NewF, because I think this makes it slightly more obvious what is going on in that case.

[nikic]

As I don't have commit rights, could you please commit D53262, D53271 and this revision?

[nikic]

Ping

[whitequark]

As I don't have commit rights, could you please commit D53262, D53271 and this revision?

Committed D53262 and D53271 but this one doesn't seem to apply.

[nikic]

Rebase patch to current master.

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

 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mergefunc"
 
 STATISTIC(NumFunctionsMerged, "Number of functions merged");
 STATISTIC(NumThunksWritten, "Number of thunks generated");
+STATISTIC(NumAliasesWritten, "Number of aliases generated");
 STATISTIC(NumDoubleWeak, "Number of new functions created");
 
 static cl::opt<unsigned> NumFunctionsForSanityCheck(
     "mergefunc-sanity",
     cl::desc("How many functions in module could be used for "
              "MergeFunctions pass sanity check. "
              "'0' disables this check. Works only with '-debug' key."),
     cl::init(0), cl::Hidden);

 //   modifies the thunk's call site to point to the shared implementation
 //   when both occur within the same translation unit.
 static cl::opt<bool>
     MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,
                       cl::init(false),
                       cl::desc("Preserve debug info in thunk when mergefunc "
                                "transformations are made."));
 
+static cl::opt<bool>
+    MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden,
+                          cl::init(false),
+                          cl::desc("Allow mergefunc to create aliases"));
+
 namespace {
 
 class FunctionNode {
   mutable AssertingVH<Function> F;
   FunctionComparator::FunctionHash Hash;
 
 public:
   // Note the hash is recalculated potentially multiple times, but it is cheap.
#endif
   /// parameter debug info, from the entry block.
   void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
 
   /// Replace G with a simple tail call to bitcast(F). Also (unless
   /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
   /// delete G.
   void writeThunk(Function *F, Function *G);
 
+  // Replace G with an alias to F (deleting function G)
+  void writeAlias(Function *F, Function *G);
+
+  // Replace G with an alias to F if possible, or a thunk to F if
+  // profitable. Returns false if neither is the case.
+  bool writeThunkOrAlias(Function *F, Function *G);
+
   /// Replace function F with function G in the function tree.
   void replaceFunctionInTree(const FunctionNode &FN, Function *G);
 
   /// The set of all distinct functions. Use the insert() and remove() methods
   /// to modify it. The map allows efficient lookup and deferring of Functions.
   FnTreeType FnTree;
 
   // Map functions to the iterators of the FunctionNode which contains them
if (MergeFunctionsPDI) {
     G->replaceAllUsesWith(NewG);
     G->eraseFromParent();
   }
 
   LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
   ++NumThunksWritten;
 }
 
+// Whether this function may be replaced by an alias
+static bool canCreateAliasFor(Function *F) {
+  if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
+    return false;
+
+  // We should only see linkages supported by aliases here
+  assert(F->hasLocalLinkage() || F->hasExternalLinkage()
+      || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
+  return true;
+}
+
+// Replace G with an alias to F (deleting function G)
+void MergeFunctions::writeAlias(Function *F, Function *G) {
+  Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
+  PointerType *PtrType = G->getType();
+  auto *GA = GlobalAlias::create(
+      PtrType->getElementType(), PtrType->getAddressSpace(),
+      G->getLinkage(), "", BitcastF, G->getParent());
+
+  F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
+  GA->takeName(G);
+  GA->setVisibility(G->getVisibility());
+  GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
+
+  removeUsers(G);
+  G->replaceAllUsesWith(GA);
+  G->eraseFromParent();
+
+  LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
+  ++NumAliasesWritten;
+}
+
+// Replace G with an alias to F if possible, or a thunk to F if
+// profitable. Returns false if neither is the case.
+bool MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
+  if (canCreateAliasFor(G)) {
+    writeAlias(F, G);
+    return true;
+  }
+  if (isThunkProfitable(F)) {
+    writeThunk(F, G);
+    return true;
+  }
+  return false;
+}
+
 // Merge two equivalent functions. Upon completion, Function G is deleted.
 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
   if (F->isInterposable()) {
     assert(G->isInterposable());
 
-    if (!isThunkProfitable(F)) {
+    // Both writeThunkOrAlias() calls below must succeed, either because we can
+    // create aliases for G and NewF, or because a thunk for F is profitable.
+    // F here has the same signature as NewF below, so that's what we check.
+    if (!isThunkProfitable(F) && (!canCreateAliasFor(F) || !canCreateAliasFor(G))) {
       return;
     }
 
     // Make them both thunks to the same internal function.
-    Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
+    Function *NewF = Function::Create(F->getFunctionType(), F->getLinkage(), "",
                                       F->getParent());
-    H->copyAttributesFrom(F);
-    H->takeName(F);
+    NewF->copyAttributesFrom(F);
+    NewF->takeName(F);
     removeUsers(F);
-    F->replaceAllUsesWith(H);
+    F->replaceAllUsesWith(NewF);
 
-    unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
+    unsigned MaxAlignment = std::max(G->getAlignment(), NewF->getAlignment());
 
-    writeThunk(F, G);
-    writeThunk(F, H);
+    writeThunkOrAlias(F, G);
+    writeThunkOrAlias(F, NewF);
 
     F->setAlignment(MaxAlignment);
     F->setLinkage(GlobalValue::PrivateLinkage);
     ++NumDoubleWeak;
     ++NumFunctionsMerged;
   } else {
     // For better debugability, under MergeFunctionsPDI, we do not modify G's
     // call sites to point to F even when within the same translation unit.
if (F->isInterposable()) {
     // stop here and delete G. There's no need for a thunk. (See note on
     // MergeFunctionsPDI above).
     if (G->hasLocalLinkage() && G->use_empty() && !MergeFunctionsPDI) {
       G->eraseFromParent();
       ++NumFunctionsMerged;
       return;
     }
 
-    if (!isThunkProfitable(F)) {
-      return;
-    }
-
-    writeThunk(F, G);
+    if (writeThunkOrAlias(F, G)) {
       ++NumFunctionsMerged;
     }
   }
+}
 
 /// Replace function F by function G.
 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
                                            Function *G) {
   Function *F = FN.getFunc();
   assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
          "The two functions must be equal");
 

llvm/trunk/test/Transforms/MergeFunc/alias.ll

+; RUN: opt -S -mergefunc -mergefunc-use-aliases < %s | FileCheck %s
+
+; Aliases should always be created for the weak functions, and
+; for external functions if there is no local function
+
+; CHECK: @external_external_2 = unnamed_addr alias void (float*), bitcast (void (i32*)* @external_external_1 to void (float*)*)
+; CHECK: @weak_weak_2 = weak unnamed_addr alias void (float*), bitcast (void (i32*)* @0 to void (float*)*)
+; CHECK: @weak_weak_1 = weak unnamed_addr alias void (i32*), void (i32*)* @0
+; CHECK: @weak_external_1 = weak unnamed_addr alias void (i32*), bitcast (void (float*)* @weak_external_2 to void (i32*)*)
+; CHECK: @external_weak_2 = weak unnamed_addr alias void (float*), bitcast (void (i32*)* @external_weak_1 to void (float*)*)
+; CHECK: @weak_internal_1 = weak unnamed_addr alias void (i32*), bitcast (void (float*)* @weak_internal_2 to void (i32*)*)
+; CHECK: @internal_weak_2 = weak unnamed_addr alias void (float*), bitcast (void (i32*)* @internal_weak_1 to void (float*)*)
+
+; A strong backing function had to be created for the weak-weak pair
+
+; CHECK: define private void @0(i32* %a) unnamed_addr
+; CHECK_NEXT: call void @dummy4()
+
+; These internal functions are dropped in favor of the external ones
+
+; CHECK-NOT: define internal void @external_internal_2(float *%a) unnamed_addr
+; CHECK-NOT: define internal void @internal_external_1(i32 *%a) unnamed_addr
+; CHECK-NOT: define internal void @internal_external_1(i32 *%a) unnamed_addr
+; CHECK-NOT: define internal void @internal_external_2(float *%a) unnamed_addr
+
+; Only used to mark which functions should be merged.
+declare void @dummy1()
+declare void @dummy2()
+declare void @dummy3()
+declare void @dummy4()
+declare void @dummy5()
+declare void @dummy6()
+declare void @dummy7()
+declare void @dummy8()
+declare void @dummy9()
+
+define void @external_external_1(i32 *%a) unnamed_addr {
+  call void @dummy1()
+  ret void
+}
+define void @external_external_2(float *%a) unnamed_addr {
+  call void @dummy1()
+  ret void
+}
+
+define void @external_internal_1(i32 *%a) unnamed_addr {
+  call void @dummy2()
+  ret void
+}
+define internal void @external_internal_2(float *%a) unnamed_addr {
+  call void @dummy2()
+  ret void
+}
+
+define internal void @internal_external_1(i32 *%a) unnamed_addr {
+  call void @dummy3()
+  ret void
+}
+define void @internal_external_2(float *%a) unnamed_addr {
+  call void @dummy3()
+  ret void
+}
+
+define weak void @weak_weak_1(i32 *%a) unnamed_addr {
+  call void @dummy4()
+  ret void
+}
+define weak void @weak_weak_2(float *%a) unnamed_addr {
+  call void @dummy4()
+  ret void
+}
+
+define weak void @weak_external_1(i32 *%a) unnamed_addr {
+  call void @dummy5()
+  ret void
+}
+define external void @weak_external_2(float *%a) unnamed_addr {
+  call void @dummy5()
+  ret void
+}
+
+define external void @external_weak_1(i32 *%a) unnamed_addr {
+  call void @dummy6()
+  ret void
+}
+define weak void @external_weak_2(float *%a) unnamed_addr {
+  call void @dummy6()
+  ret void
+}
+
+define weak void @weak_internal_1(i32 *%a) unnamed_addr {
+  call void @dummy7()
+  ret void
+}
+define internal void @weak_internal_2(float *%a) unnamed_addr {
+  call void @dummy7()
+  ret void
+}
+
+define internal void @internal_weak_1(i32 *%a) unnamed_addr {
+  call void @dummy8()
+  ret void
+}
+define weak void @internal_weak_2(float *%a) unnamed_addr {
+  call void @dummy8()
+  ret void
+}
+
+define internal void @internal_internal_1(i32 *%a) unnamed_addr {
+  call void @dummy9()
+  ret void
+}
+define internal void @internal_internal_2(float *%a) unnamed_addr {
+  call void @dummy9()
+  ret void
+}