[CGData] Global Merge Functions (#112671)

This implements a global function merging pass. Unlike traditional
function merging passes that use IR comparators, this pass employs a
structurally stable hash to identify similar functions while ignoring
certain constant operands. These ignored constants are tracked and
encoded into a stable function summary. When merging, instead of
explicitly folding similar functions and their call sites, we form a
merging instance by supplying different parameters via thunks. The
actual size reduction occurs when identically created merging instances
are folded by the linker.

Currently, this pass is wired to a pre-codegen pass, enabled by the
`-enable-global-merge-func` flag.
In a local merging mode, the analysis and merging steps occur
sequentially within a module:
- `analyze`: Collects stable function hashes and tracks locations of
ignored constant operands.
- `finalize`: Identifies merge candidates with matching hashes and
computes the set of parameters that point to different constants.
- `merge`: Uses the stable function map to optimistically create a
merged function.

We can enable a global merging mode similar to the global function
outliner
(https://discourse.llvm.org/t/rfc-enhanced-machine-outliner-part-2-thinlto-nolto/78753/),
which will perform the above steps separately.
- `-codegen-data-generate`: During the first round of code generation,
we analyze local merging instances and publish their summaries.
- Offline using `llvm-cgdata` or at link-time, we can finalize all these
merging summaries that are combined to determine parameters.
- `-codegen-data-use`: During the second round of code generation, we
optimistically create merging instances within each module, and finally,
the linker folds identically created merging instances.

Depends on #112664
This is a patch for
https://discourse.llvm.org/t/rfc-global-function-merging/82608.

1 files changed, 70 insertions, 1 deletions

diff --git a/llvm/lib/CGData/StableFunctionMap.cpp b/llvm/lib/CGData/StableFunctionMap.cpp
index cfef5b2..fe7be0c 100644
--- a/llvm/lib/CGData/StableFunctionMap.cpp
+++ b/llvm/lib/CGData/StableFunctionMap.cpp
@@ -14,11 +14,43 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CGData/StableFunctionMap.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "stable-function-map"
 
 using namespace llvm;
 
+static cl::opt<unsigned>
+    GlobalMergingMinMerges("global-merging-min-merges",
+                           cl::desc("Minimum number of similar functions with "
+                                    "the same hash required for merging."),
+                           cl::init(2), cl::Hidden);
+static cl::opt<unsigned> GlobalMergingMinInstrs(
+    "global-merging-min-instrs",
+    cl::desc("The minimum instruction count required when merging functions."),
+    cl::init(1), cl::Hidden);
+static cl::opt<unsigned> GlobalMergingMaxParams(
+    "global-merging-max-params",
+    cl::desc(
+        "The maximum number of parameters allowed when merging functions."),
+    cl::init(std::numeric_limits<unsigned>::max()), cl::Hidden);
+static cl::opt<unsigned> GlobalMergingParamOverhead(
+    "global-merging-param-overhead",
+    cl::desc("The overhead cost associated with each parameter when merging "
+             "functions."),
+    cl::init(2), cl::Hidden);
+static cl::opt<unsigned>
+    GlobalMergingCallOverhead("global-merging-call-overhead",
+                              cl::desc("The overhead cost associated with each "
+                                       "function call when merging functions."),
+                              cl::init(1), cl::Hidden);
+static cl::opt<unsigned> GlobalMergingExtraThreshold(
+    "global-merging-extra-threshold",
+    cl::desc("An additional cost threshold that must be exceeded for merging "
+             "to be considered beneficial."),
+    cl::init(0), cl::Hidden);
+
 unsigned StableFunctionMap::getIdOrCreateForName(StringRef Name) {
   auto It = NameToId.find(Name);
   if (It != NameToId.end())
@@ -117,7 +149,38 @@ static void removeIdenticalIndexPair(
       SF->IndexOperandHashMap->erase(Pair);
 }
 
-void StableFunctionMap::finalize() {
+static bool isProfitable(
+    const SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>>
+        &SFS) {
+  unsigned StableFunctionCount = SFS.size();
+  if (StableFunctionCount < GlobalMergingMinMerges)
+    return false;
+
+  unsigned InstCount = SFS[0]->InstCount;
+  if (InstCount < GlobalMergingMinInstrs)
+    return false;
+
+  unsigned ParamCount = SFS[0]->IndexOperandHashMap->size();
+  if (ParamCount > GlobalMergingMaxParams)
+    return false;
+
+  unsigned Benefit = InstCount * (StableFunctionCount - 1);
+  unsigned Cost =
+      (GlobalMergingParamOverhead * ParamCount + GlobalMergingCallOverhead) *
+          StableFunctionCount +
+      GlobalMergingExtraThreshold;
+
+  bool Result = Benefit > Cost;
+  LLVM_DEBUG(dbgs() << "isProfitable: Hash = " << SFS[0]->Hash << ", "
+                    << "StableFunctionCount = " << StableFunctionCount
+                    << ", InstCount = " << InstCount
+                    << ", ParamCount = " << ParamCount
+                    << ", Benefit = " << Benefit << ", Cost = " << Cost
+                    << ", Result = " << (Result ? "true" : "false") << "\n");
+  return Result;
+}
+
+void StableFunctionMap::finalize(bool SkipTrim) {
   for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {
     auto &[StableHash, SFS] = *It;
 
@@ -158,9 +221,15 @@ void StableFunctionMap::finalize() {
       continue;
     }
 
+    if (SkipTrim)
+      continue;
+
     // Trim the index pair that has the same operand hash across
     // stable functions.
     removeIdenticalIndexPair(SFS);
+
+    if (!isProfitable(SFS))
+      HashToFuncs.erase(It);
   }
 
   Finalized = true;