[CallGraphSection] Introduce CGSectionFuncComdatCreator pass

[necipfazil]

Summary

Create comdats for functions whose symbols will be referenced from the
call graph section. These comdats are used to create the call graph
sections, so that, the sections can get discarded by the linker if the
functions get removed.

Original RFC: https://lists.llvm.org/pipermail/llvm-dev/2021-June/151044.html
Updated RFC: https://lists.llvm.org/pipermail/llvm-dev/2021-July/151739.html

[morehouse]

Are comdats needed? Can we get proper dead stripping with just SHF_LINK_ORDER?

@MaskRay recently updated the documentation for associated metadata to imply that our symbol doesn't need to share a comdat with its associated function when the function doesn't have a comdat.

Also, @MaskRay: Can adding comdats like this change the final code in the fully-linked binary?

[necipfazil]

In D105911#2878345, @morehouse wrote:

Are comdats needed? Can we get proper dead stripping with just SHF_LINK_ORDER?

It looks like we can. I am abandoning this revision. I will shortly push the changes to related revisions for not using comdats.

@MaskRay recently updated the documentation for associated metadata to imply that our symbol doesn't need to share a comdat with its associated function when the function doesn't have a comdat.

Also, @MaskRay: Can adding comdats like this change the final code in the fully-linked binary?

[MaskRay]

clang/lib/CodeGen/BackendUtil.cpp

1420

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

llvm/lib/Transforms/Utils/CGSectionFuncComdatCreator.cpp

64

clang-format prefers /*IgnoreCallbackUses=*/true

91

delete braces

llvm/test/Transforms/Util/create-function-comdats.ll

1

This should be within a call-graph-section specific directory.

Use test/Instrumentation/InstrProfiling/comdat.ll as a reference

clang/lib/CodeGen/BackendUtil.cpp

 #include "llvm/Transforms/Instrumentation/SanitizerCoverage.h"
 #include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/LowerMatrixIntrinsics.h"
 #include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/CGSectionFuncComdatCreator.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/Debugify.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/NameAnonGlobals.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include <memory>
 using namespace clang;
 using namespace llvm;
if (!CodeGenOpts.DisableLLVMPasses) {
     } else {
       MPM = PB.buildPerModuleDefaultPipeline(Level);
     }
 
     if (!CodeGenOpts.MemoryProfileOutput.empty()) {
       MPM.addPass(createModuleToFunctionPassAdaptor(MemProfilerPass()));
       MPM.addPass(ModuleMemProfilerPass());
     }
+
+    if (CodeGenOpts.CallGraphSection) {
+      MPM.addPass(CGSectionFuncComdatCreatorPass());
+    }
   }
 
   // FIXME: We still use the legacy pass manager to do code generation. We
   // create that pass manager here and use it as needed below.
   legacy::PassManager CodeGenPasses;
   bool NeedCodeGen = false;
   std::unique_ptr<llvm::ToolOutputFile> ThinLinkOS, DwoOS;
 

llvm/include/llvm/Transforms/Utils/CGSectionFuncComdatCreator.h

+//===-- CGSectionFuncComdatCreator.h - CG func comdat creator ---*- C++ -*-===//
+//
+// 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 pass creates comdats for functions whose symbols will be referenced
+// from the call graph section. These comdats are used to create the call graph
+// sections, so that, the sections can get discarded by the linker if the
+// functions get removed.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CGSECTIONFUNCCOMDATCREATOR_H
+#define LLVM_TRANSFORMS_UTILS_CGSECTIONFUNCCOMDATCREATOR_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class CGSectionFuncComdatCreatorPass
+    : public PassInfoMixin<CGSectionFuncComdatCreatorPass> {
+public:
+  PreservedAnalyses run(Module &, ModuleAnalysisManager &);
+};
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CGSECTIONFUNCCOMDATCREATOR_H
+

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/StraightLineStrengthReduce.h"
 #include "llvm/Transforms/Scalar/StructurizeCFG.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
+#include "llvm/Transforms/Utils/CGSectionFuncComdatCreator.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/FixIrreducible.h"
 #include "llvm/Transforms/Utils/HelloWorld.h"
 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
 #include "llvm/Transforms/Utils/InstructionNamer.h"
 #include "llvm/Transforms/Utils/LCSSA.h"

llvm/lib/Passes/PassRegistry.def

 
 #ifndef MODULE_PASS
 #define MODULE_PASS(NAME, CREATE_PASS)
 #endif
 MODULE_PASS("always-inline", AlwaysInlinerPass())
 MODULE_PASS("attributor", AttributorPass())
 MODULE_PASS("annotation2metadata", Annotation2MetadataPass())
 MODULE_PASS("openmp-opt", OpenMPOptPass())
+MODULE_PASS("cg-section-func-comdat-creator", CGSectionFuncComdatCreatorPass())
 MODULE_PASS("called-value-propagation", CalledValuePropagationPass())
 MODULE_PASS("canonicalize-aliases", CanonicalizeAliasesPass())
 MODULE_PASS("cg-profile", CGProfilePass())
 MODULE_PASS("constmerge", ConstantMergePass())
 MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass())
 MODULE_PASS("deadargelim", DeadArgumentEliminationPass())
 MODULE_PASS("elim-avail-extern", EliminateAvailableExternallyPass())
 MODULE_PASS("extract-blocks", BlockExtractorPass())

llvm/lib/Transforms/Utils/CGSectionFuncComdatCreator.cpp

+//===-- CGSectionFuncComdatCreator.cpp - CG section func comdat creator ---===//
+//
+// 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 pass creates comdats for functions whose symbols will be referenced
+// from the call graph section. These comdats are used to create the call graph
+// sections, so that, the sections can get discarded by the linker if the
+// functions get removed.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CGSectionFuncComdatCreator.h"
+
+#include "llvm/ADT/Triple.h"
+#include "llvm/IR/Instructions.h"
+
+namespace llvm {
+
+namespace {
+class ModuleCGSectionFuncComdatCreator {
+public:
+  bool instrumentModule(Module &);
+
+private:
+  bool createFunctionComdat(Function &F, const Triple &T) const;
+  bool hasIndirectCalls(const Function &F) const;
+  bool isTargetToIndirectCalls(const Function &F) const;
+};
+
+bool ModuleCGSectionFuncComdatCreator::createFunctionComdat(
+    Function &F, const Triple &T) const {
+  if (auto *Comdat = F.getComdat())
+    return false;
+  assert(F.hasName());
+  Module *M = F.getParent();
+
+  // Make a new comdat for the function. Use the "no duplicates" selection kind
+  // if the object file format supports it. For COFF we restrict it to non-weak
+  // symbols.
+  Comdat *C = M->getOrInsertComdat(F.getName());
+  if (T.isOSBinFormatELF() || (T.isOSBinFormatCOFF() && !F.isWeakForLinker()))
+    C->setSelectionKind(Comdat::NoDuplicates);
+  F.setComdat(C);
+  return true;
+}
+
+bool ModuleCGSectionFuncComdatCreator::hasIndirectCalls(
+    const Function &F) const {
+  for (const auto &I : F)
+    if (const CallInst *CI = dyn_cast<CallInst>(&I))
+      if (CI->isIndirectCall())
+        return true;
+  return false;
+}
+
+bool ModuleCGSectionFuncComdatCreator::isTargetToIndirectCalls(
+    const Function &F) const {
+  return !F.hasLocalLinkage() ||
+         F.hasAddressTaken(nullptr,
+                           /* IgnoreCallbackUses */ true,
+                           /* IgnoreAssumeLikeCalls */ true,
+                           /* IgnoreLLVMUsed */ false);
+}
+
+bool ModuleCGSectionFuncComdatCreator::instrumentModule(Module &M) {
+  Triple TargetTriple = Triple(M.getTargetTriple());
+
+  bool CreatedComdats = false;
+
+  for (Function &F : M) {
+    if (isTargetToIndirectCalls(F) || hasIndirectCalls(F)) {
+      if (TargetTriple.supportsCOMDAT() && !F.isInterposable() &&
+          !F.isDeclarationForLinker()) {
+        CreatedComdats |= createFunctionComdat(F, TargetTriple);
+      }
+    }
+  }
+
+  return CreatedComdats;
+}
+
+} // namespace
+
+PreservedAnalyses
+CGSectionFuncComdatCreatorPass::run(Module &M, ModuleAnalysisManager &AM) {
+  ModuleCGSectionFuncComdatCreator ModuleCG;
+  if (ModuleCG.instrumentModule(M)) {
+    return PreservedAnalyses::none();
+  }
+  return PreservedAnalyses::all();
+}
+
+} // namespace llvm
+

llvm/lib/Transforms/Utils/CMakeLists.txt

 add_llvm_component_library(LLVMTransformUtils
   AddDiscriminators.cpp
   AMDGPUEmitPrintf.cpp
   ASanStackFrameLayout.cpp
   AssumeBundleBuilder.cpp
   BasicBlockUtils.cpp
   BreakCriticalEdges.cpp
   BuildLibCalls.cpp
   BypassSlowDivision.cpp
+  CGSectionFuncComdatCreator.cpp
   CallPromotionUtils.cpp
   CallGraphUpdater.cpp
   CanonicalizeAliases.cpp
   CanonicalizeFreezeInLoops.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
   CodeMoverUtils.cpp

llvm/test/Transforms/Util/create-function-comdats.ll

+; Tests that we create function comdats properly and only for those with no
+; comdats.
+
+; RUN: opt -passes='cg-section-func-comdat-creator' -S %s | FileCheck %s
+
+; CHECK: $f = comdat noduplicates
+; CHECK: $g = comdat any
+$g = comdat any
+
+; CHECK: define dso_local void @f() comdat {
+define dso_local void @f() {
+entry:
+  ret void
+}
+
+; CHECK: define dso_local void @g() comdat {
+define dso_local void @g() comdat {
+entry:
+  ret void
+}
+