[GlobalOpt] Introduce and prevent elimination of implementedby metadata

[wsmoses]

Summary

Introduce implementedby metadata, which will be used to represent a function whose implementation
will be replaced by the corresponding implementation. In addition to introducing this metadata, this patch
modifies globalopt to prevent removal of the requisite implementation and user.

[wsmoses]

Restore accidental debug info removal

[lebedev.ri]

This needs an LangRef patch, and a RFC to llvm-dev.

[wsmoses]

@lebedev.ri you're quite right on the LangRef modification.

Also please forgive me for not having included a link to the previous discussion of this topic on llvm-dev (see here for the most recent proposal https://lists.llvm.org/pipermail/llvm-dev/2021-April/150265.html).

llvm/include/llvm/IR/FixedMetadataKinds.def

 LLVM_FIXED_MD_KIND(MD_callees, "callees", 23)
 LLVM_FIXED_MD_KIND(MD_irr_loop, "irr_loop", 24)
 LLVM_FIXED_MD_KIND(MD_access_group, "llvm.access.group", 25)
 LLVM_FIXED_MD_KIND(MD_callback, "callback", 26)
 LLVM_FIXED_MD_KIND(MD_preserve_access_index, "llvm.preserve.access.index", 27)
 LLVM_FIXED_MD_KIND(MD_vcall_visibility, "vcall_visibility", 28)
 LLVM_FIXED_MD_KIND(MD_noundef, "noundef", 29)
 LLVM_FIXED_MD_KIND(MD_annotation, "annotation", 30)
+LLVM_FIXED_MD_KIND(MD_implementedby, "implementedby", 31)
 No newline at end of file

llvm/lib/Transforms/IPO/GlobalOpt.cpp

 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
OptimizeFunctions(Module &M,
                   function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                   function_ref<TargetTransformInfo &(Function &)> GetTTI,
                   function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                   function_ref<DominatorTree &(Function &)> LookupDomTree,
                   SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
 
   bool Changed = false;
 
+  SmallPtrSet<Function *, 4> ImplementedByUses;
   std::vector<Function *> AllCallsCold;
   for (Module::iterator FI = M.begin(), E = M.end(); FI != E;) {
     Function *F = &*FI++;
     if (hasOnlyColdCalls(*F, GetBFI))
       AllCallsCold.push_back(F);
+
+    auto MD = F->getMetadata(LLVMContext::MD_implementedby);
+    if (MD) {
+      ImplementedByUses.insert(F);
+      auto Impl =
+          cast<ValueAsMetadata>(cast<MDTuple>(MD)->getOperand(0))->getValue();
+      if (auto F2 = dyn_cast<Function>(Impl))
+        ImplementedByUses.insert(F2);
+    }
   }
 
   // Optimize functions.
   for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
     Function *F = &*FI++;
 
+    // Don't perform global opt on functions used within implemented by
+    // we neither want theses functions deleted, nor with a different
+    // calling convention.
+    if (ImplementedByUses.count(F))
+      continue;
+
     // Don't perform global opt pass on naked functions; we don't want fast
     // calling conventions for naked functions.
     if (F->hasFnAttribute(Attribute::Naked))
       continue;
 
     // Functions without names cannot be referenced outside this module.
     if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
       F->setLinkage(GlobalValue::InternalLinkage);

llvm/test/Transforms/GlobalOpt/implemented_by.ll

+; RUN: opt < %s -globalopt -S | FileCheck %s
+
+declare !implementedby !0 double @llvm.sin.f64(double)
+; CHECK: declare !implementedby [[sinimpl:.+]] double @llvm.sin.f64
+declare double @sin(double)
+
+define internal double @mycos(double %x) {
+  ret double %x
+}
+; Calling convention is not changed
+; CHECK: define internal double @mycos(double %x)
+
+declare !implementedby !1 double @llvm.cos.f64(double)
+; CHECK: declare !implementedby [[cosimpl:.+]] double @llvm.cos.f64
+
+define double @cos(double %x) !implementedby !1 {
+  ret double %x
+}
+; CHECK: define double @cos{{.+}} !implementedby [[cosimpl]] {
+
+!0 = !{double(double)* @sin}
+!1 = !{double(double)* @mycos}
+
+; CHECK: [[sinimpl]] = !{double (double)* @sin}
+; CHECK: [[cosimpl]] = !{double (double)* @mycos}
+