[WIP] Introduce the "implements" string attribute

[jdoerfert]

Summary

This is a protoype, RFC will follow.

See https://lists.llvm.org/pipermail/llvm-dev/2021-March/149117.html
for a rational.

[jdoerfert]

Add the new files as well ;)

[wsmoses]

Is it worth verifying there isn't more than one implementation for a given function?

[jdoerfert]

In D98516#2622478, @wsmoses wrote:

Is it worth verifying there isn't more than one implementation for a given function?

I guess we can emit a debug message but there is little we can do in the IR wrt. error reporting. The clang part could check though.

[tra]

Nice.

And, also, a bit scary as it can potentially be used to replace an arbitrary function, not just a math intrinsic normally mapped to libcall.
I can see how it may be useful to allow function substitution for uses other than libm on GPUs, but it's also going to be way too easy to make a mess. E.g. if/when someone substitutes @llvm.lifetime.start or some other special purpose intrinsic llvm relies on.

Perhaps it would make sense to only allow whitelisted functions?

llvm/test/Transforms/ImplementsAttrResolver/intrinsic_implementation.ll

6

What happens if the function has different signature than that of the intrinsic?

6

We may want to be able provide different implementations based on fast-math flags.
libdevice has few functions that have distinct fast-math implementations.

[MaskRay]

llvm/lib/Passes/PassBuilder.cpp

283

Omit cl::init(false)

llvm/test/Transforms/ImplementsAttrResolver/intrinsic_implementation.ll

4

This test needs to be ported to ptr now:)

llvm/include/llvm/Transforms/IPO/ImplementsAttrResolver.h

+//===- ImplementsAttrResolver.h - Repl. specification with impls. - 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
+//
+//===----------------------------------------------------------------------===//
+//
+// TODO
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_IMPLEMENTSATTRRESOLVER_H
+#define LLVM_TRANSFORMS_IPO_IMPLEMENTSATTRRESOLVER_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+struct ImplementsAttrResolverPass
+    : public PassInfoMixin<ImplementsAttrResolverPass> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/ElimAvailExtern.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionImport.h"
 #include "llvm/Transforms/IPO/GlobalDCE.h"
 #include "llvm/Transforms/IPO/GlobalOpt.h"
 #include "llvm/Transforms/IPO/GlobalSplit.h"
 #include "llvm/Transforms/IPO/HotColdSplitting.h"
 #include "llvm/Transforms/IPO/IROutliner.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/Internalize.h"
+#include "llvm/Transforms/IPO/ImplementsAttrResolver.h"
 #include "llvm/Transforms/IPO/LoopExtractor.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/MergeFunctions.h"
 #include "llvm/Transforms/IPO/OpenMPOpt.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/SampleProfile.h"
 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
static cl::opt<bool> PerformMandatoryInliningsFirst(
     "mandatory-inlining-first", cl::init(true), cl::Hidden, cl::ZeroOrMore,
     cl::desc("Perform mandatory inlinings module-wide, before performing "
              "inlining."));
 
 static cl::opt<bool> EnableO3NonTrivialUnswitching(
     "enable-npm-O3-nontrivial-unswitch", cl::init(true), cl::Hidden,
     cl::ZeroOrMore, cl::desc("Enable non-trivial loop unswitching for -O3"));
 
+static cl::opt<bool> EnableImplementsAttrResolver(
+    "enable-implements-attr-resolver", cl::init(false), cl::Hidden,
+    cl::ZeroOrMore, cl::desc("Enable the implements attribute resolver"));
+
 PipelineTuningOptions::PipelineTuningOptions() {
   LoopInterleaving = true;
   LoopVectorization = true;
   SLPVectorization = false;
   LoopUnrolling = true;
   ForgetAllSCEVInLoopUnroll = ForgetSCEVInLoopUnroll;
   Coroutines = false;
   LicmMssaOptCap = SetLicmMssaOptCap;
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   // delete control flows that are dead once globals have been folded to
   // constants.
   MPM.addPass(createModuleToFunctionPassAdaptor(PromotePass()));
 
   // Remove any dead arguments exposed by cleanups and constant folding
   // globals.
   MPM.addPass(DeadArgumentEliminationPass());
 
+  // Replace calls to functions specifications with their "implementation".
+  // See the `implements` and `specification` clang attributes and the
+  // `implements` LLVM-IR attribute.
+  if (EnableImplementsAttrResolver)
+    MPM.addPass(ImplementsAttrResolverPass());
+
   // Create a small function pass pipeline to cleanup after all the global
   // optimizations.
   FunctionPassManager GlobalCleanupPM(DebugLogging);
   GlobalCleanupPM.addPass(InstCombinePass());
   invokePeepholeEPCallbacks(GlobalCleanupPM, Level);
 
   GlobalCleanupPM.addPass(SimplifyCFGPass());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(GlobalCleanupPM)));
PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level,
 
   // Use in-range annotations on GEP indices to split globals where beneficial.
   MPM.addPass(GlobalSplitPass());
 
   // Run whole program optimization of virtual call when the list of callees
   // is fixed.
   MPM.addPass(WholeProgramDevirtPass(ExportSummary, nullptr));
 
+  // Replace calls to functions specifications with their "implementation".
+  // See the `implements` and `specification` clang attributes and the
+  // `implements` LLVM-IR attribute.
+  if (EnableImplementsAttrResolver)
+    MPM.addPass(ImplementsAttrResolverPass());
+
   // Stop here at -O1.
   if (Level == OptimizationLevel::O1) {
     // The LowerTypeTestsPass needs to run to lower type metadata and the
     // type.test intrinsics. The pass does nothing if CFI is disabled.
     MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
     // Run a second time to clean up any type tests left behind by WPD for use
     // in ICP (which is performed earlier than this in the regular LTO
     // pipeline).
ModulePassManager PassBuilder::buildO0DefaultPipeline(OptimizationLevel Level,
   // which is just that always inlining occurs. Further, disable generating
   // lifetime intrinsics to avoid enabling further optimizations during
   // code generation.
   // However, we need to insert lifetime intrinsics to avoid invalid access
   // caused by multithreaded coroutines.
   MPM.addPass(AlwaysInlinerPass(
       /*InsertLifetimeIntrinsics=*/PTO.Coroutines));
 
+  // Replace calls to functions specifications with their "implementation".
+  // See the `implements` and `specification` clang attributes and the
+  // `implements` LLVM-IR attribute.
+  if (EnableImplementsAttrResolver)
+    MPM.addPass(ImplementsAttrResolverPass());
+
   if (PTO.MergeFunctions)
     MPM.addPass(MergeFunctionsPass());
 
   if (EnableMatrix)
     MPM.addPass(
         createModuleToFunctionPassAdaptor(LowerMatrixIntrinsicsPass(true)));
 
   if (!CGSCCOptimizerLateEPCallbacks.empty()) {

llvm/lib/Passes/PassRegistry.def

MODULE_PASS("inliner-wrapper-no-mandatory-first", ModuleInlinerWrapperPass(
   getInlineParams(), 
   DebugLogging, 
   false))
 MODULE_PASS("insert-gcov-profiling", GCOVProfilerPass())
 MODULE_PASS("instrorderfile", InstrOrderFilePass())
 MODULE_PASS("instrprof", InstrProfiling())
 MODULE_PASS("internalize", InternalizePass())
 MODULE_PASS("invalidate<all>", InvalidateAllAnalysesPass())
+MODULE_PASS("implements-attr-resolver", ImplementsAttrResolverPass())
 MODULE_PASS("ipsccp", IPSCCPPass())
 MODULE_PASS("iroutliner", IROutlinerPass())
 MODULE_PASS("print-ir-similarity", IRSimilarityAnalysisPrinterPass(dbgs()))
 MODULE_PASS("loop-extract", LoopExtractorPass())
 MODULE_PASS("lowertypetests", LowerTypeTestsPass())
 MODULE_PASS("metarenamer", MetaRenamerPass())
 MODULE_PASS("mergefunc", MergeFunctionsPass())
 MODULE_PASS("name-anon-globals", NameAnonGlobalPass())

llvm/lib/Transforms/IPO/CMakeLists.txt

add_llvm_component_library(LLVMipo
   GlobalSplit.cpp
   HotColdSplitting.cpp
   IPO.cpp
   IROutliner.cpp
   InferFunctionAttrs.cpp
   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp
+  ImplementsAttrResolver.cpp
   LoopExtractor.cpp
   LowerTypeTests.cpp
   MergeFunctions.cpp
   OpenMPOpt.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleContextTracker.cpp

llvm/lib/Transforms/IPO/ImplementsAttrResolver.cpp

+//===- ImplementsAttrResolver.cpp - Repl. specifications w implemenations -===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// TODO
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/ImplementsAttrResolver.h"
+
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/PassInstrumentation.h"
+
+#define DEBUG_TYPE "implements-attr-resolver"
+
+using namespace llvm;
+
+PreservedAnalyses ImplementsAttrResolverPass::run(Module &M,
+                                                  ModuleAnalysisManager &) {
+  for (Function &Impl : M) {
+    const Attribute &A = Impl.getFnAttribute("implements");
+    if (!A.isValid())
+      continue;
+
+    const StringRef SpecificationName = A.getValueAsString();
+    Function *Specification = M.getFunction(SpecificationName);
+    if (!Specification) {
+      LLVM_DEBUG(dbgs() << "Found implementation '" << Impl.getName()
+                        << "' but no matching specification with name '"
+                        << SpecificationName
+                        << "', potentially inlined and/or eliminated.\n");
+      continue;
+    }
+    LLVM_DEBUG(dbgs() << "Replace specification '" << Specification->getName()
+                      << "' with implementation '" << Impl.getName() << "'\n");
+    Specification->replaceAllUsesWith(
+        ConstantExpr::getBitCast(&Impl, Specification->getType()));
+  }
+  return PreservedAnalyses::all();
+}

llvm/test/Transforms/ImplementsAttrResolver/intrinsic_implementation.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=implements-attr-resolver -S | FileCheck %s
+
[e-mail] = appending global [2 x i8*] [i8* bitcast (float (float)* @my_sin to i8*), i8* bitcast (float (float)* @my_cos_type_mismatch to i8*)], section "llvm.metadata"
+
+define internal float @my_sin(float %d) "implements"="llvm.sin.f32" {
+; CHECK-LABEL: @my_sin(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float [[D:%.*]]
+;
+entry:
+  ret float %d
+}
+
+define internal float @my_cos_type_mismatch(float %d) "implements"="llvm.cos.f64" {
+; CHECK-LABEL: @my_cos_type_mismatch(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float [[D:%.*]]
+;
+entry:
+  ret float %d
+}
+
+define double @foo(double %d, float %f) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = tail call fast float @my_sin(float [[F:%.*]])
+; CHECK-NEXT:    [[TMP1:%.*]] = tail call fast double bitcast (float (float)* @my_cos_type_mismatch to double (double)*)(double [[D:%.*]])
+; CHECK-NEXT:    ret double [[TMP1]]
+;
+entry:
+  %0 = tail call fast float @llvm.sin.f32(float %f)
+  %1 = tail call fast double @llvm.cos.f64(double %d)
+  ret double %1
+}
+
+declare float @llvm.sin.f32(float)
+declare double @llvm.cos.f64(double)