From d23c5c2d6566fce4380cfa31d438422db19fbce9 Mon Sep 17 00:00:00 2001 From: Kyungwoo Lee Date: Wed, 13 Nov 2024 17:34:07 -0800 Subject: [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. --- llvm/lib/CGData/StableFunctionMap.cpp | 71 ++++++++++++++++++++++++++++++++++- 1 file changed, 70 insertions(+), 1 deletion(-) (limited to 'llvm/lib/CGData/StableFunctionMap.cpp') 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 + 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 GlobalMergingMinInstrs( + "global-merging-min-instrs", + cl::desc("The minimum instruction count required when merging functions."), + cl::init(1), cl::Hidden); +static cl::opt GlobalMergingMaxParams( + "global-merging-max-params", + cl::desc( + "The maximum number of parameters allowed when merging functions."), + cl::init(std::numeric_limits::max()), cl::Hidden); +static cl::opt 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 + 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 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> + &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; -- cgit v1.1