llvm/lib/CGData/StableFunctionMap.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This implements the functionality for the StableFunctionMap class, which
  10 // manages the mapping of stable function hashes to their metadata. It includes
  11 // methods for inserting, merging, and finalizing function entries, as well as
  12 // 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/Support/CommandLine.h"
  19 #include "llvm/Support/Debug.h"
  20
  21 #define DEBUG_TYPE "stable-function-map"
  22
  23 using namespace llvm;
  24
  25 static cl::opt<unsigned>
  26     GlobalMergingMinMerges("global-merging-min-merges",
  27                            cl::desc("Minimum number of similar functions with "
  28                                     "the same hash required for merging."),
  29                            cl::init(2), cl::Hidden);
  30 static cl::opt<unsigned> GlobalMergingMinInstrs(
  31     "global-merging-min-instrs",
  32     cl::desc("The minimum instruction count required when merging functions."),
  33     cl::init(1), cl::Hidden);
  34 static cl::opt<unsigned> GlobalMergingMaxParams(
  35     "global-merging-max-params",
  36     cl::desc(
  37         "The maximum number of parameters allowed when merging functions."),
  38     cl::init(std::numeric_limits<unsigned>::max()), cl::Hidden);
  39 static cl::opt<bool> GlobalMergingSkipNoParams(
  40     "global-merging-skip-no-params",
  41     cl::desc("Skip merging functions with no parameters."), cl::init(true),
  42     cl::Hidden);
  43 static cl::opt<double> GlobalMergingInstOverhead(
  44     "global-merging-inst-overhead",
  45     cl::desc("The overhead cost associated with each instruction when lowering "
  46              "to machine instruction."),
  47     cl::init(1.2), cl::Hidden);
  48 static cl::opt<double> GlobalMergingParamOverhead(
  49     "global-merging-param-overhead",
  50     cl::desc("The overhead cost associated with each parameter when merging "
  51              "functions."),
  52     cl::init(2.0), cl::Hidden);
  53 static cl::opt<double>
  54     GlobalMergingCallOverhead("global-merging-call-overhead",
  55                               cl::desc("The overhead cost associated with each "
  56                                        "function call when merging functions."),
  57                               cl::init(1.0), cl::Hidden);
  58 static cl::opt<double> GlobalMergingExtraThreshold(
  59     "global-merging-extra-threshold",
  60     cl::desc("An additional cost threshold that must be exceeded for merging "
  61              "to be considered beneficial."),
  62     cl::init(0.0), cl::Hidden);
  63
  64 unsigned StableFunctionMap::getIdOrCreateForName(StringRef Name) {
  65   auto It = NameToId.find(Name);
  66   if (It != NameToId.end())
  67     return It->second;
  68   unsigned Id = IdToName.size();
  69   assert(Id == NameToId.size() && "ID collision");
  70   IdToName.emplace_back(Name.str());
  71   NameToId[IdToName.back()] = Id;
  72   return Id;
  73 }
  74
  75 std::optional<std::string> StableFunctionMap::getNameForId(unsigned Id) const {
  76   if (Id >= IdToName.size())
  77     return std::nullopt;
  78   return IdToName[Id];
  79 }
  80
  81 void StableFunctionMap::insert(const StableFunction &Func) {
  82   assert(!Finalized && "Cannot insert after finalization");
  83   auto FuncNameId = getIdOrCreateForName(Func.FunctionName);
  84   auto ModuleNameId = getIdOrCreateForName(Func.ModuleName);
  85   auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
  86   for (auto &[Index, Hash] : Func.IndexOperandHashes)
  87     (*IndexOperandHashMap)[Index] = Hash;
  88   auto FuncEntry = std::make_unique<StableFunctionEntry>(
  89       Func.Hash, FuncNameId, ModuleNameId, Func.InstCount,
  90       std::move(IndexOperandHashMap));
  91   insert(std::move(FuncEntry));
  92 }
  93
  94 void StableFunctionMap::merge(const StableFunctionMap &OtherMap) {
  95   assert(!Finalized && "Cannot merge after finalization");
  96   for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {
  97     auto &ThisFuncs = HashToFuncs[Hash];
  98     for (auto &Func : Funcs) {
  99       auto FuncNameId =
 100           getIdOrCreateForName(*OtherMap.getNameForId(Func->FunctionNameId));
 101       auto ModuleNameId =
 102           getIdOrCreateForName(*OtherMap.getNameForId(Func->ModuleNameId));
 103       auto ClonedIndexOperandHashMap =
 104           std::make_unique<IndexOperandHashMapType>(*Func->IndexOperandHashMap);
 105       ThisFuncs.emplace_back(std::make_unique<StableFunctionEntry>(
 106           Func->Hash, FuncNameId, ModuleNameId, Func->InstCount,
 107           std::move(ClonedIndexOperandHashMap)));
 108     }
 109   }
 110 }
 111
 112 size_t StableFunctionMap::size(SizeType Type) const {
 113   switch (Type) {
 114   case UniqueHashCount:
 115     return HashToFuncs.size();
 116   case TotalFunctionCount: {
 117     size_t Count = 0;
 118     for (auto &Funcs : HashToFuncs)
 119       Count += Funcs.second.size();
 120     return Count;
 121   }
 122   case MergeableFunctionCount: {
 123     size_t Count = 0;
 124     for (auto &[Hash, Funcs] : HashToFuncs)
 125       if (Funcs.size() >= 2)
 126         Count += Funcs.size();
 127     return Count;
 128   }
 129   }
 130   llvm_unreachable("Unhandled size type");
 131 }
 132
 133 using ParamLocs = SmallVector<IndexPair>;
 134 static void removeIdenticalIndexPair(
 135     SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>> &SFS) {
 136   auto &RSF = SFS[0];
 137   unsigned StableFunctionCount = SFS.size();
 138
 139   SmallVector<IndexPair> ToDelete;
 140   for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {
 141     bool Identical = true;
 142     for (unsigned J = 1; J < StableFunctionCount; ++J) {
 143       auto &SF = SFS[J];
 144       const auto &SHash = SF->IndexOperandHashMap->at(Pair);
 145       if (Hash != SHash) {
 146         Identical = false;
 147         break;
 148       }
 149     }
 150
 151     // No need to parameterize them if the hashes are identical across stable
 152     // functions.
 153     if (Identical)
 154       ToDelete.emplace_back(Pair);
 155   }
 156
 157   for (auto &Pair : ToDelete)
 158     for (auto &SF : SFS)
 159       SF->IndexOperandHashMap->erase(Pair);
 160 }
 161
 162 static bool isProfitable(
 163     const SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>>
 164         &SFS) {
 165   unsigned StableFunctionCount = SFS.size();
 166   if (StableFunctionCount < GlobalMergingMinMerges)
 167     return false;
 168
 169   unsigned InstCount = SFS[0]->InstCount;
 170   if (InstCount < GlobalMergingMinInstrs)
 171     return false;
 172
 173   double Cost = 0.0;
 174   SmallSet<stable_hash, 8> UniqueHashVals;
 175   for (auto &SF : SFS) {
 176     UniqueHashVals.clear();
 177     for (auto &[IndexPair, Hash] : *SF->IndexOperandHashMap)
 178       UniqueHashVals.insert(Hash);
 179     unsigned ParamCount = UniqueHashVals.size();
 180     if (ParamCount > GlobalMergingMaxParams)
 181       return false;
 182     // Theoretically, if ParamCount is 0, it results in identical code folding
 183     // (ICF), which we can skip merging here since the linker already handles
 184     // ICF. This pass would otherwise introduce unnecessary thunks that are
 185     // merely direct jumps. However, enabling this could be beneficial depending
 186     // on downstream passes, so we provide an option for it.
 187     if (GlobalMergingSkipNoParams && ParamCount == 0)
 188       return false;
 189     Cost += ParamCount * GlobalMergingParamOverhead + GlobalMergingCallOverhead;
 190   }
 191   Cost += GlobalMergingExtraThreshold;
 192
 193   double Benefit =
 194       InstCount * (StableFunctionCount - 1) * GlobalMergingInstOverhead;
 195   bool Result = Benefit > Cost;
 196   LLVM_DEBUG(dbgs() << "isProfitable: Hash = " << SFS[0]->Hash << ", "
 197                     << "StableFunctionCount = " << StableFunctionCount
 198                     << ", InstCount = " << InstCount
 199                     << ", Benefit = " << Benefit << ", Cost = " << Cost
 200                     << ", Result = " << (Result ? "true" : "false") << "\n");
 201   return Result;
 202 }
 203
 204 void StableFunctionMap::finalize(bool SkipTrim) {
 205   for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {
 206     auto &[StableHash, SFS] = *It;
 207
 208     // Group stable functions by ModuleIdentifier.
 209     std::stable_sort(SFS.begin(), SFS.end(),
 210                      [&](const std::unique_ptr<StableFunctionEntry> &L,
 211                          const std::unique_ptr<StableFunctionEntry> &R) {
 212                        return *getNameForId(L->ModuleNameId) <
 213                               *getNameForId(R->ModuleNameId);
 214                      });
 215
 216     // Consider the first function as the root function.
 217     auto &RSF = SFS[0];
 218
 219     bool Invalid = false;
 220     unsigned StableFunctionCount = SFS.size();
 221     for (unsigned I = 1; I < StableFunctionCount; ++I) {
 222       auto &SF = SFS[I];
 223       assert(RSF->Hash == SF->Hash);
 224       if (RSF->InstCount != SF->InstCount) {
 225         Invalid = true;
 226         break;
 227       }
 228       if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {
 229         Invalid = true;
 230         break;
 231       }
 232       for (auto &P : *RSF->IndexOperandHashMap) {
 233         auto &InstOpndIndex = P.first;
 234         if (!SF->IndexOperandHashMap->count(InstOpndIndex)) {
 235           Invalid = true;
 236           break;
 237         }
 238       }
 239     }
 240     if (Invalid) {
 241       HashToFuncs.erase(It);
 242       continue;
 243     }
 244
 245     if (SkipTrim)
 246       continue;
 247
 248     // Trim the index pair that has the same operand hash across
 249     // stable functions.
 250     removeIdenticalIndexPair(SFS);
 251
 252     if (!isProfitable(SFS))
 253       HashToFuncs.erase(It);
 254   }
 255
 256   Finalized = true;
 257 }