300 lines · cpp
1//===-- StableFunctionMap.cpp ---------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This implements the functionality for the StableFunctionMap class, which10// manages the mapping of stable function hashes to their metadata. It includes11// methods for inserting, merging, and finalizing function entries, as well as12// utilities for handling function names and IDs.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/CGData/StableFunctionMap.h"17#include "llvm/ADT/SmallSet.h"18#include "llvm/CGData/StableFunctionMapRecord.h"19#include "llvm/Support/CommandLine.h"20#include "llvm/Support/Debug.h"21 22#define DEBUG_TYPE "stable-function-map"23 24using namespace llvm;25 26static cl::opt<unsigned>27 GlobalMergingMinMerges("global-merging-min-merges",28 cl::desc("Minimum number of similar functions with "29 "the same hash required for merging."),30 cl::init(2), cl::Hidden);31static cl::opt<unsigned> GlobalMergingMinInstrs(32 "global-merging-min-instrs",33 cl::desc("The minimum instruction count required when merging functions."),34 cl::init(1), cl::Hidden);35static cl::opt<unsigned> GlobalMergingMaxParams(36 "global-merging-max-params",37 cl::desc(38 "The maximum number of parameters allowed when merging functions."),39 cl::init(std::numeric_limits<unsigned>::max()), cl::Hidden);40static cl::opt<bool> GlobalMergingSkipNoParams(41 "global-merging-skip-no-params",42 cl::desc("Skip merging functions with no parameters."), cl::init(true),43 cl::Hidden);44static cl::opt<double> GlobalMergingInstOverhead(45 "global-merging-inst-overhead",46 cl::desc("The overhead cost associated with each instruction when lowering "47 "to machine instruction."),48 cl::init(1.2), cl::Hidden);49static cl::opt<double> GlobalMergingParamOverhead(50 "global-merging-param-overhead",51 cl::desc("The overhead cost associated with each parameter when merging "52 "functions."),53 cl::init(2.0), cl::Hidden);54static cl::opt<double>55 GlobalMergingCallOverhead("global-merging-call-overhead",56 cl::desc("The overhead cost associated with each "57 "function call when merging functions."),58 cl::init(1.0), cl::Hidden);59static cl::opt<double> GlobalMergingExtraThreshold(60 "global-merging-extra-threshold",61 cl::desc("An additional cost threshold that must be exceeded for merging "62 "to be considered beneficial."),63 cl::init(0.0), cl::Hidden);64 65unsigned StableFunctionMap::getIdOrCreateForName(StringRef Name) {66 auto It = NameToId.find(Name);67 if (It != NameToId.end())68 return It->second;69 unsigned Id = IdToName.size();70 assert(Id == NameToId.size() && "ID collision");71 IdToName.emplace_back(Name.str());72 NameToId[IdToName.back()] = Id;73 return Id;74}75 76std::optional<std::string> StableFunctionMap::getNameForId(unsigned Id) const {77 if (Id >= IdToName.size())78 return std::nullopt;79 return IdToName[Id];80}81 82void StableFunctionMap::insert(const StableFunction &Func) {83 assert(!Finalized && "Cannot insert after finalization");84 auto FuncNameId = getIdOrCreateForName(Func.FunctionName);85 auto ModuleNameId = getIdOrCreateForName(Func.ModuleName);86 auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();87 for (auto &[Index, Hash] : Func.IndexOperandHashes)88 (*IndexOperandHashMap)[Index] = Hash;89 auto FuncEntry = std::make_unique<StableFunctionEntry>(90 Func.Hash, FuncNameId, ModuleNameId, Func.InstCount,91 std::move(IndexOperandHashMap));92 insert(std::move(FuncEntry));93}94 95void StableFunctionMap::merge(const StableFunctionMap &OtherMap) {96 assert(!Finalized && "Cannot merge after finalization");97 deserializeLazyLoadingEntries();98 for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {99 auto &ThisFuncs = HashToFuncs[Hash].Entries;100 for (auto &Func : Funcs.Entries) {101 auto FuncNameId =102 getIdOrCreateForName(*OtherMap.getNameForId(Func->FunctionNameId));103 auto ModuleNameId =104 getIdOrCreateForName(*OtherMap.getNameForId(Func->ModuleNameId));105 auto ClonedIndexOperandHashMap =106 std::make_unique<IndexOperandHashMapType>(*Func->IndexOperandHashMap);107 ThisFuncs.emplace_back(std::make_unique<StableFunctionEntry>(108 Func->Hash, FuncNameId, ModuleNameId, Func->InstCount,109 std::move(ClonedIndexOperandHashMap)));110 }111 }112}113 114size_t StableFunctionMap::size(SizeType Type) const {115 switch (Type) {116 case UniqueHashCount:117 return HashToFuncs.size();118 case TotalFunctionCount: {119 deserializeLazyLoadingEntries();120 size_t Count = 0;121 for (auto &Funcs : HashToFuncs)122 Count += Funcs.second.Entries.size();123 return Count;124 }125 case MergeableFunctionCount: {126 deserializeLazyLoadingEntries();127 size_t Count = 0;128 for (auto &[Hash, Funcs] : HashToFuncs)129 if (Funcs.Entries.size() >= 2)130 Count += Funcs.Entries.size();131 return Count;132 }133 }134 llvm_unreachable("Unhandled size type");135}136 137const StableFunctionMap::StableFunctionEntries &138StableFunctionMap::at(HashFuncsMapType::key_type FunctionHash) const {139 auto It = HashToFuncs.find(FunctionHash);140 assert(It != HashToFuncs.end() && "FunctionHash not found!");141 if (isLazilyLoaded())142 deserializeLazyLoadingEntry(It);143 return It->second.Entries;144}145 146void StableFunctionMap::deserializeLazyLoadingEntry(147 HashFuncsMapType::iterator It) const {148 assert(isLazilyLoaded() && "Cannot deserialize non-lazily-loaded map");149 auto &[Hash, Storage] = *It;150 std::call_once(Storage.LazyLoadFlag,151 [this, HashArg = Hash, &StorageArg = Storage]() {152 for (auto Offset : StorageArg.Offsets)153 StableFunctionMapRecord::deserializeEntry(154 reinterpret_cast<const unsigned char *>(Offset),155 HashArg, const_cast<StableFunctionMap *>(this));156 });157}158 159void StableFunctionMap::deserializeLazyLoadingEntries() const {160 if (!isLazilyLoaded())161 return;162 for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It)163 deserializeLazyLoadingEntry(It);164}165 166const StableFunctionMap::HashFuncsMapType &167StableFunctionMap::getFunctionMap() const {168 // Ensure all entries are deserialized before returning the raw map.169 if (isLazilyLoaded())170 deserializeLazyLoadingEntries();171 return HashToFuncs;172}173 174using ParamLocs = SmallVector<IndexPair>;175static void176removeIdenticalIndexPair(StableFunctionMap::StableFunctionEntries &SFS) {177 auto &RSF = SFS[0];178 unsigned StableFunctionCount = SFS.size();179 180 SmallVector<IndexPair> ToDelete;181 for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {182 bool Identical = true;183 for (unsigned J = 1; J < StableFunctionCount; ++J) {184 auto &SF = SFS[J];185 const auto &SHash = SF->IndexOperandHashMap->at(Pair);186 if (Hash != SHash) {187 Identical = false;188 break;189 }190 }191 192 // No need to parameterize them if the hashes are identical across stable193 // functions.194 if (Identical)195 ToDelete.emplace_back(Pair);196 }197 198 for (auto &Pair : ToDelete)199 for (auto &SF : SFS)200 SF->IndexOperandHashMap->erase(Pair);201}202 203static bool isProfitable(const StableFunctionMap::StableFunctionEntries &SFS) {204 unsigned StableFunctionCount = SFS.size();205 if (StableFunctionCount < GlobalMergingMinMerges)206 return false;207 208 unsigned InstCount = SFS[0]->InstCount;209 if (InstCount < GlobalMergingMinInstrs)210 return false;211 212 double Cost = 0.0;213 SmallSet<stable_hash, 8> UniqueHashVals;214 for (auto &SF : SFS) {215 UniqueHashVals.clear();216 for (auto &[IndexPair, Hash] : *SF->IndexOperandHashMap)217 UniqueHashVals.insert(Hash);218 unsigned ParamCount = UniqueHashVals.size();219 if (ParamCount > GlobalMergingMaxParams)220 return false;221 // Theoretically, if ParamCount is 0, it results in identical code folding222 // (ICF), which we can skip merging here since the linker already handles223 // ICF. This pass would otherwise introduce unnecessary thunks that are224 // merely direct jumps. However, enabling this could be beneficial depending225 // on downstream passes, so we provide an option for it.226 if (GlobalMergingSkipNoParams && ParamCount == 0)227 return false;228 Cost += ParamCount * GlobalMergingParamOverhead + GlobalMergingCallOverhead;229 }230 Cost += GlobalMergingExtraThreshold;231 232 double Benefit =233 InstCount * (StableFunctionCount - 1) * GlobalMergingInstOverhead;234 bool Result = Benefit > Cost;235 LLVM_DEBUG(dbgs() << "isProfitable: Hash = " << SFS[0]->Hash << ", "236 << "StableFunctionCount = " << StableFunctionCount237 << ", InstCount = " << InstCount238 << ", Benefit = " << Benefit << ", Cost = " << Cost239 << ", Result = " << (Result ? "true" : "false") << "\n");240 return Result;241}242 243void StableFunctionMap::finalize(bool SkipTrim) {244 deserializeLazyLoadingEntries();245 SmallVector<HashFuncsMapType::iterator> ToDelete;246 for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {247 auto &[StableHash, Storage] = *It;248 auto &SFS = Storage.Entries;249 250 // Group stable functions by ModuleIdentifier.251 llvm::stable_sort(SFS, [&](const std::unique_ptr<StableFunctionEntry> &L,252 const std::unique_ptr<StableFunctionEntry> &R) {253 return *getNameForId(L->ModuleNameId) < *getNameForId(R->ModuleNameId);254 });255 256 // Consider the first function as the root function.257 auto &RSF = SFS[0];258 259 bool Invalid = false;260 unsigned StableFunctionCount = SFS.size();261 for (unsigned I = 1; I < StableFunctionCount; ++I) {262 auto &SF = SFS[I];263 assert(RSF->Hash == SF->Hash);264 if (RSF->InstCount != SF->InstCount) {265 Invalid = true;266 break;267 }268 if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {269 Invalid = true;270 break;271 }272 for (auto &P : *RSF->IndexOperandHashMap) {273 auto &InstOpndIndex = P.first;274 if (!SF->IndexOperandHashMap->count(InstOpndIndex)) {275 Invalid = true;276 break;277 }278 }279 }280 if (Invalid) {281 ToDelete.push_back(It);282 continue;283 }284 285 if (SkipTrim)286 continue;287 288 // Trim the index pair that has the same operand hash across289 // stable functions.290 removeIdenticalIndexPair(SFS);291 292 if (!isProfitable(SFS))293 ToDelete.push_back(It);294 }295 for (auto It : ToDelete)296 HashToFuncs.erase(It);297 298 Finalized = true;299}300