Add a pass to name anonymous/nameless function

[mehdi_amini]

Summary

For correct handling of alias to nameless
function, we need to be able to refer them through a GUID in the summary.
Here we name them using a hash of the non-private global names in the module.

[george.burgess.iv]

Hi! Just a few comments in passing for you. :)

lib/Transforms/Utils/NameAnonFunctions.cpp

31

Nit: Can this just be folded into if (F.isDeclaration() || F.hasLocalLinkage() || !F.hasName())?

41

And this

59

ISTM this code is making many Twines here, and the lifetimes of all but the top-level Twine will end when we're done constructing Prefix, which is bad. Am I missing something?

[tejohnson]

Perhaps this should be named something more general than NameAnonFunctionPass. This is the naming scheme pcc was proposing for promoted values as well, and eventually it would be good to do any early renaming/promotion of locals here. The moduleHash() facility could also be used during importing to rename/promote imported locals (i.e. invoked from FunctionImportGlobalProcessing), for anything not promoted/renamed during the compile step, so it would also be good to put that into a more general location.

lib/Transforms/Utils/NameAnonFunctions.cpp

59

Right, I think this should just be std::string (although the Twine(count++) below seems fine since it is constructing a function parameter).

64

Another possibility would be to move the Twines here:
Twine("anon.") + ModuleHash + "." + Twine(count++)

[mehdi_amini]

lib/Transforms/Utils/NameAnonFunctions.cpp

31

Thanks, good point, forgot to clean this up...

59

George: I don't see what is the issue here: the Twine are *copied*. The lifetime we have to look at is the lifetime of the underline objects every Twine wraps.

Teresa: this is a good suggestion in general: serializing the prefix once in a string here should be better than doing it multiple time in the loop as part of the name. The catch here is that I don't expect the loop to be large in average (is unnamed function a common thing?), and serializing early means unconditionally (not that I think it matters here...).

64

I believe this is NFC, but loses the "string optimization" you mentioned above.

[tejohnson]

lib/Transforms/Utils/NameAnonFunctions.cpp

59

Reading through http://llvm.org/docs/ProgrammersManual.html#dss-twine, I am not convinced the lifetime of the "anon." temporary will be extended.

If it is legal, why wrap the "anon." part in a Twine and not "."?

We're already doing the expensive part (computation of the ModuleHash string) unconditionally, I'm not sure it is worth trying to optimize this part. Especially since the Twine usage makes me nervous, but I could be missing something...

64

Actually, this could be:
Twine("anon.") + ModuleHash + Twine(".") + Twine(count++)

[mehdi_amini]

lib/Transforms/Utils/NameAnonFunctions.cpp

59

You're asking why "anon." is wrapped in a Twine and not ".", this is because otherwise RHS would not operate on Twine at all. And you don't need to wrap "." in a Twine, because it is already implicitly done by the compiler! (here is the clang-ast if you're interested: http://snag.gy/HtMMD.jpg )

That said, with another look at it, George is right: the problem is not the lifetime of the "anon." temporary, the problem is the lifetime of the intermediate Twine objects.

The expression I wrote is conceptually the same as:

Twine Prefix;
{
  auto TwineAnon = Twine("anon.");
  auto TwineModuleHash = Twine(ModuleHash);
  auto TwineAnonAndModuleHash = TwineAnon + TwineModuleHash;
  auto TwineDot = Twine(".");
  Prefix = TwineAnonAndModuleHash + TwineDot;`
}
// at scope exit the intermediate Twine are dead but Prefix keeps pointers to them
// the underlying objects "anon.", ModuleHash, and "." are still valid.

59

(Also we may not want to compute the hash unconditionally)

64

There is no difference with your previous suggestion (the Twine is implicit for ".").

[george.burgess.iv]

lib/Transforms/Utils/NameAnonFunctions.cpp

59

George: I don't see what is the issue here: the Twine are *copied*. The lifetime we have to look at is the lifetime of the underline objects every Twine wraps.

I agree with Teresa, because when hooking a Twine up to another Twine, we call Twine::concat, which stores the this pointer (and the pointer to the concat argument) in the newly-created Twine. Given that a single Twine can only hook two things together, we'll need at least two of them here to hook all three parts of this string together.

[mehdi_amini]

Address comment (style + Twine bugfix + lazy compute hash).

[mehdi_amini]

Somehow only one of my previous inline comment went through?

lib/Transforms/Utils/NameAnonFunctions.cpp

59

You're asking why "anon." is wrapped in a Twine and not ".", this is because otherwise RHS would not operate on Twine at all. And you don't need to wrap "." in a Twine, because it is already implicitly done by the compiler! (here is the clang-ast if you're interested: http://snag.gy/HtMMD.jpg )

That said, with another look at it, George is right: the problem is not the lifetime of the "anon." temporary, the problem is the lifetime of the intermediate Twine objects.

The expression I wrote is conceptually the same as:

Twine Prefix;
{
  auto TwineAnon = Twine("anon.");
  auto TwineModuleHash = Twine(ModuleHash);
  auto TwineAnonAndModuleHash = TwineAnon + TwineModuleHash;
  auto TwineDot = Twine(".");
  Prefix = TwineAnonAndModuleHash + TwineDot;`
}
// at scope exit the intermediate Twine are dead but Prefix keeps pointers to them
// the underlying objects "anon.", ModuleHash, and "." are still valid.

[mehdi_amini]

Ping? I think I addressed all the comments so far?

[tejohnson]

In D18883#395368, @tejohnson wrote:

Perhaps this should be named something more general than NameAnonFunctionPass. This is the naming scheme pcc was proposing for promoted values as well, and eventually it would be good to do any early renaming/promotion of locals here. The moduleHash() facility could also be used during importing to rename/promote imported locals (i.e. invoked from FunctionImportGlobalProcessing), for anything not promoted/renamed during the compile step, so it would also be good to put that into a more general location.

I had the above comment. However, I don't have strong objections to putting this in as-is. It could be refactored or renamed later to use the same naming facility for early promotion/renaming.

[mehdi_amini]

I missed this comment originally.

So the pass itself is really intended to be targeting nameless functions. The ModuleHash computation could be refactored though (I'll leave it for when needed).
I'm not sure how to write the llvm::nameUnamedFunctions() to be reusable though. It should be easier to figure out when the exact need will be there.

[tejohnson]

In D18883#399035, @joker.eph wrote:

I missed this comment originally.

So the pass itself is really intended to be targeting nameless functions. The ModuleHash computation could be refactored though (I'll leave it for when needed).
I'm not sure how to write the llvm::nameUnamedFunctions() to be reusable though. It should be easier to figure out when the exact need will be there.

Sounds good.

[ovyalov]

It seems this CL is breaking LLDB Windows builder - http://lab.llvm.org:8011/builders/lldb-windows7-android/builds/5228, could you take a look?

[llvm-commits]

It should already be fixed with r266151

[mehdi_amini]

r266132

include/llvm/InitializePasses.h

 void initializeMemDerefPrinterPass(PassRegistry&);
 void initializeMemoryDependenceWrapperPassPass(PassRegistry&);
 void initializeMemorySSALazyPass(PassRegistry&);
 void initializeMemorySSAPrinterPassPass(PassRegistry&);
 void initializeMergedLoadStoreMotionPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
+void initializeNameAnonFunctionPass(PassRegistry &);
 void initializeNaryReassociatePass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializePAEvalPass(PassRegistry &);

include/llvm/Transforms/Scalar.h

 FunctionPass *createLoopVersioningPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopDataPrefetch - Perform data prefetching in loops.
 //
 FunctionPass *createLoopDataPrefetchPass();
 
+///===---------------------------------------------------------------------===//
+ModulePass *createNameAnonFunctionPass();
+
 } // End llvm namespace
 
 #endif

include/llvm/Transforms/Utils/ModuleUtils.h

 /// \brief Creates sanitizer constructor function, and calls sanitizer's init
 /// function from it.
 /// \return Returns pair of pointers to constructor, and init functions
 /// respectively.
 std::pair<Function *, Function *> createSanitizerCtorAndInitFunctions(
     Module &M, StringRef CtorName, StringRef InitName,
     ArrayRef<Type *> InitArgTypes, ArrayRef<Value *> InitArgs,
     StringRef VersionCheckName = StringRef());
+
+/// Rename all the anon functions in the module using a hash computed from
+/// the list of public globals in the module.
+bool nameUnamedFunctions(Module &M);
+
 } // End llvm namespace
 
 #endif //  LLVM_TRANSFORMS_UTILS_MODULEUTILS_H

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   addExtensionsToPM(EP_Peephole, MPM);
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
   if (PrepareForThinLTO) {
     MPM.add(createAggressiveDCEPass());        // Delete dead instructions
     addInstructionCombiningPass(MPM);          // Combine silly seq's
+    // Rename anon function to export them
+    MPM.add(createNameAnonFunctionPass());
     return;
   }
   // Rotate Loop - disable header duplication at -Oz
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createCFGSimplificationPass());
   addInstructionCombiningPass(MPM);

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LoopUtils.cpp
   LoopVersioning.cpp
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MemorySSA.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
+  NameAnonFunctions.cpp
   PromoteMemoryToRegister.cpp
   SSAUpdater.cpp
   SanitizerStats.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp
   SimplifyLibCalls.cpp
   SplitModule.cpp

lib/Transforms/Utils/NameAnonFunctions.cpp

+//===- NameAnonFunctions.cpp - ThinLTO Summary-based Function Import ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements naming anonymous function to make sure they can be
+// refered to by ThinLTO.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallString.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/MD5.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+
+using namespace llvm;
+
+// Compute a "unique" hash for the module based on the name of the public
+// functions.
+static std::string moduleHash(Module &M) {
+  MD5 Hasher;
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    if (F.hasLocalLinkage())
+      continue;
+    if (!F.hasName())
+      continue;
+    auto Name = F.getName();
+    Hasher.update(Name);
+  }
+  for (auto &GV : M.globals()) {
+    if (GV.isDeclaration())
+      continue;
+    if (GV.hasLocalLinkage())
+      continue;
+    if (!GV.hasName())
+      continue;
+    auto Name = GV.getName();
+    Hasher.update(Name);
+  }
+
+  // Now return the result.
+  MD5::MD5Result Hash;
+  Hasher.final(Hash);
+  SmallString<32> Result;
+  MD5::stringifyResult(Hash, Result);
+  return Result.str();
+}
+
+// Rename all the anon functions in the module
+bool llvm::nameUnamedFunctions(Module &M) {
+  bool Changed = false;
+  auto ModuleHash = moduleHash(M);
+  Twine Prefix = Twine("anon.") + ModuleHash + ".";
+  int count = 0;
+  for (auto &F : M) {
+    if (F.hasName())
+      continue;
+    F.setName(Prefix + Twine(count++));
+    Changed = true;
+  }
+  return Changed;
+}
+
+namespace {
+
+// Simple pass that provides a name to every anon function.
+class NameAnonFunction : public ModulePass {
+
+public:
+  /// Pass identification, replacement for typeid
+  static char ID;
+
+  /// Specify pass name for debug output
+  const char *getPassName() const override { return "Name Anon Functions"; }
+
+  explicit NameAnonFunction() : ModulePass(ID) {}
+
+  bool runOnModule(Module &M) override { return nameUnamedFunctions(M); }
+};
+char NameAnonFunction::ID = 0;
+
+} // anonymous namespace
+
+INITIALIZE_PASS_BEGIN(NameAnonFunction, "name-anon-functions",
+                      "Provide a name to nameless functions", false, false)
+INITIALIZE_PASS_END(NameAnonFunction, "name-anon-functions",
+                    "Provide a name to nameless functions", false, false)
+
+namespace llvm {
+Pass *createNameAnonFunctionPass() { return new NameAnonFunction(); }
+}

lib/Transforms/Utils/Utils.cpp

 void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializeAddDiscriminatorsPass(Registry);
   initializeBreakCriticalEdgesPass(Registry);
   initializeInstNamerPass(Registry);
   initializeLCSSAPass(Registry);
   initializeLoopSimplifyPass(Registry);
   initializeLowerInvokePass(Registry);
   initializeLowerSwitchPass(Registry);
+  initializeNameAnonFunctionPass(Registry);
   initializePromotePassPass(Registry);
   initializeUnifyFunctionExitNodesPass(Registry);
   initializeInstSimplifierPass(Registry);
   initializeMetaRenamerPass(Registry);
   initializeMemorySSALazyPass(Registry);
   initializeMemorySSAPrinterPassPass(Registry);
 }
 
 /// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
 void LLVMInitializeTransformUtils(LLVMPassRegistryRef R) {
   initializeTransformUtils(*unwrap(R));
 }

test/Transforms/NameAnonFunctions/rename.ll

+; RUN: opt -S -name-anon-functions < %s | FileCheck %s
+
+
+; foo contribute to the unique hash for the module
+define void @foo() {
+    ret void
+}
+
+; bar is internal, and does not contribute to the unique hash for the module
+define internal void @bar() {
+    ret void
+}
+
+; CHECK: define void @anon.acbd18db4cc2f85cedef654fccc4a4d8.0()
+; CHECK: define void @anon.acbd18db4cc2f85cedef654fccc4a4d8.1()
+; CHECK: define void @anon.acbd18db4cc2f85cedef654fccc4a4d8.2()
+
+define void @0() {
+    ret void
+}
+define void @1() {
+    ret void
+}
+define void @2() {
+    ret void
+}
+