616 lines · cpp
1//===---- GlobalMergeFunctions.cpp - Global merge functions -------*- C++ -===//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 pass implements the global merge function pass.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/CodeGen/GlobalMergeFunctions.h"14#include "llvm/ADT/Statistic.h"15#include "llvm/Analysis/ModuleSummaryAnalysis.h"16#include "llvm/CGData/CodeGenData.h"17#include "llvm/CGData/CodeGenDataWriter.h"18#include "llvm/CodeGen/Passes.h"19#include "llvm/IR/IRBuilder.h"20#include "llvm/IR/StructuralHash.h"21#include "llvm/InitializePasses.h"22#include "llvm/Support/CommandLine.h"23#include "llvm/Transforms/Utils/ModuleUtils.h"24 25#define DEBUG_TYPE "global-merge-func"26 27using namespace llvm;28using namespace llvm::support;29 30static cl::opt<bool> DisableCGDataForMerging(31 "disable-cgdata-for-merging", cl::Hidden,32 cl::desc("Disable codegen data for function merging. Local "33 "merging is still enabled within a module."),34 cl::init(false));35 36STATISTIC(NumMergedFunctions,37 "Number of functions that are actually merged using function hash");38STATISTIC(NumAnalyzedModues, "Number of modules that are analyzed");39STATISTIC(NumAnalyzedFunctions, "Number of functions that are analyzed");40STATISTIC(NumEligibleFunctions, "Number of functions that are eligible");41 42/// Returns true if the \OpIdx operand of \p CI is the callee operand.43static bool isCalleeOperand(const CallBase *CI, unsigned OpIdx) {44 return &CI->getCalledOperandUse() == &CI->getOperandUse(OpIdx);45}46 47static bool canParameterizeCallOperand(const CallBase *CI, unsigned OpIdx) {48 if (CI->isInlineAsm())49 return false;50 Function *Callee = CI->getCalledOperand()51 ? dyn_cast_or_null<Function>(52 CI->getCalledOperand()->stripPointerCasts())53 : nullptr;54 if (Callee) {55 if (Callee->isIntrinsic())56 return false;57 auto Name = Callee->getName();58 // objc_msgSend stubs must be called, and can't have their address taken.59 if (Name.starts_with("objc_msgSend$"))60 return false;61 // Calls to dtrace probes must generate unique patchpoints.62 if (Name.starts_with("__dtrace"))63 return false;64 }65 if (isCalleeOperand(CI, OpIdx)) {66 // The operand is the callee and it has already been signed. Ignore this67 // because we cannot add another ptrauth bundle to the call instruction.68 if (CI->getOperandBundle(LLVMContext::OB_ptrauth).has_value())69 return false;70 } else {71 // The target of the arc-attached call must be a constant and cannot be72 // parameterized.73 if (CI->isOperandBundleOfType(LLVMContext::OB_clang_arc_attachedcall,74 OpIdx))75 return false;76 }77 return true;78}79 80/// Returns true if function \p F is eligible for merging.81bool isEligibleFunction(Function *F) {82 if (F->isDeclaration())83 return false;84 85 if (F->hasFnAttribute(llvm::Attribute::NoMerge) ||86 F->hasFnAttribute(llvm::Attribute::AlwaysInline))87 return false;88 89 if (F->hasAvailableExternallyLinkage())90 return false;91 92 if (F->getFunctionType()->isVarArg())93 return false;94 95 if (F->getCallingConv() == CallingConv::SwiftTail)96 return false;97 98 // Unnamed functions are skipped for simplicity.99 if (!F->hasName())100 return false;101 102 // If function contains callsites with musttail, if we merge103 // it, the merged function will have the musttail callsite, but104 // the number of parameters can change, thus the parameter count105 // of the callsite will mismatch with the function itself.106 for (const BasicBlock &BB : *F) {107 for (const Instruction &I : BB) {108 const auto *CB = dyn_cast<CallBase>(&I);109 if (CB && CB->isMustTailCall())110 return false;111 }112 }113 114 return true;115}116 117static bool isEligibleInstructionForConstantSharing(const Instruction *I) {118 switch (I->getOpcode()) {119 case Instruction::Load:120 case Instruction::Store:121 case Instruction::Call:122 case Instruction::Invoke:123 return true;124 default:125 return false;126 }127}128 129// This function takes an instruction, \p I, and an operand index, \p OpIdx.130// It returns true if the operand should be ignored in the hash computation.131// If \p OpIdx is out of range based on the other instruction context, it cannot132// be ignored.133static bool ignoreOp(const Instruction *I, unsigned OpIdx) {134 if (OpIdx >= I->getNumOperands())135 return false;136 137 if (!isEligibleInstructionForConstantSharing(I))138 return false;139 140 if (!isa<Constant>(I->getOperand(OpIdx)))141 return false;142 143 if (const auto *CI = dyn_cast<CallBase>(I))144 return canParameterizeCallOperand(CI, OpIdx);145 146 return true;147}148 149void GlobalMergeFunc::analyze(Module &M) {150 ++NumAnalyzedModues;151 for (Function &Func : M) {152 ++NumAnalyzedFunctions;153 if (isEligibleFunction(&Func)) {154 ++NumEligibleFunctions;155 156 auto FI = llvm::StructuralHashWithDifferences(Func, ignoreOp);157 158 // Convert the operand map to a vector for a serialization-friendly159 // format.160 IndexOperandHashVecType IndexOperandHashes;161 for (auto &Pair : *FI.IndexOperandHashMap)162 IndexOperandHashes.emplace_back(Pair);163 164 StableFunction SF(FI.FunctionHash, get_stable_name(Func.getName()).str(),165 M.getModuleIdentifier(), FI.IndexInstruction->size(),166 std::move(IndexOperandHashes));167 168 LocalFunctionMap->insert(SF);169 }170 }171}172 173/// Tuple to hold function info to process merging.174struct FuncMergeInfo {175 StableFunctionMap::StableFunctionEntry *SF;176 Function *F;177 IndexInstrMap *IndexInstruction;178 FuncMergeInfo(StableFunctionMap::StableFunctionEntry *SF, Function *F,179 IndexInstrMap *IndexInstruction)180 : SF(SF), F(F), IndexInstruction(std::move(IndexInstruction)) {}181};182 183// Given the func info, and the parameterized locations, create and return184// a new merged function by replacing the original constants with the new185// parameters.186static Function *createMergedFunction(FuncMergeInfo &FI,187 ArrayRef<Type *> ConstParamTypes,188 const ParamLocsVecTy &ParamLocsVec) {189 // Synthesize a new merged function name by appending ".Tgm" to the root190 // function's name.191 auto *MergedFunc = FI.F;192 std::string NewFunctionName =193 MergedFunc->getName().str() + GlobalMergeFunc::MergingInstanceSuffix;194 auto *M = MergedFunc->getParent();195 assert(!M->getFunction(NewFunctionName));196 197 FunctionType *OrigTy = MergedFunc->getFunctionType();198 // Get the original params' types.199 SmallVector<Type *> ParamTypes(OrigTy->param_begin(), OrigTy->param_end());200 // Append const parameter types that are passed in.201 ParamTypes.append(ConstParamTypes.begin(), ConstParamTypes.end());202 FunctionType *FuncType = FunctionType::get(OrigTy->getReturnType(),203 ParamTypes, /*isVarArg=*/false);204 205 // Declare a new function206 Function *NewFunction =207 Function::Create(FuncType, MergedFunc->getLinkage(), NewFunctionName);208 if (auto *SP = MergedFunc->getSubprogram())209 NewFunction->setSubprogram(SP);210 NewFunction->copyAttributesFrom(MergedFunc);211 NewFunction->setDLLStorageClass(GlobalValue::DefaultStorageClass);212 213 NewFunction->setLinkage(GlobalValue::InternalLinkage);214 NewFunction->addFnAttr(Attribute::NoInline);215 216 // Add the new function before the root function.217 M->getFunctionList().insert(MergedFunc->getIterator(), NewFunction);218 219 // Move the body of MergedFunc into the NewFunction.220 NewFunction->splice(NewFunction->begin(), MergedFunc);221 222 // Update the original args by the new args.223 auto NewArgIter = NewFunction->arg_begin();224 for (Argument &OrigArg : MergedFunc->args()) {225 Argument &NewArg = *NewArgIter++;226 OrigArg.replaceAllUsesWith(&NewArg);227 }228 229 // Replace the original Constants by the new args.230 unsigned NumOrigArgs = MergedFunc->arg_size();231 for (unsigned ParamIdx = 0; ParamIdx < ParamLocsVec.size(); ++ParamIdx) {232 Argument *NewArg = NewFunction->getArg(NumOrigArgs + ParamIdx);233 for (auto [InstIndex, OpndIndex] : ParamLocsVec[ParamIdx]) {234 auto *Inst = FI.IndexInstruction->lookup(InstIndex);235 auto *OrigC = Inst->getOperand(OpndIndex);236 if (OrigC->getType() != NewArg->getType()) {237 IRBuilder<> Builder(Inst->getParent(), Inst->getIterator());238 Inst->setOperand(OpndIndex,239 Builder.CreateAggregateCast(NewArg, OrigC->getType()));240 } else {241 Inst->setOperand(OpndIndex, NewArg);242 }243 }244 }245 246 return NewFunction;247}248 249// Given the original function (Thunk) and the merged function (ToFunc), create250// a thunk to the merged function.251static void createThunk(FuncMergeInfo &FI, ArrayRef<Constant *> Params,252 Function *ToFunc) {253 auto *Thunk = FI.F;254 255 assert(Thunk->arg_size() + Params.size() ==256 ToFunc->getFunctionType()->getNumParams());257 Thunk->dropAllReferences();258 259 BasicBlock *BB = BasicBlock::Create(Thunk->getContext(), "", Thunk);260 IRBuilder<> Builder(BB);261 262 SmallVector<Value *> Args;263 unsigned ParamIdx = 0;264 FunctionType *ToFuncTy = ToFunc->getFunctionType();265 266 // Add arguments which are passed through Thunk.267 for (Argument &AI : Thunk->args()) {268 Args.push_back(269 Builder.CreateAggregateCast(&AI, ToFuncTy->getParamType(ParamIdx)));270 ++ParamIdx;271 }272 273 // Add new arguments defined by Params.274 for (auto *Param : Params) {275 assert(ParamIdx < ToFuncTy->getNumParams());276 Args.push_back(277 Builder.CreateAggregateCast(Param, ToFuncTy->getParamType(ParamIdx)));278 ++ParamIdx;279 }280 281 CallInst *CI = Builder.CreateCall(ToFunc, Args);282 bool isSwiftTailCall = ToFunc->getCallingConv() == CallingConv::SwiftTail &&283 Thunk->getCallingConv() == CallingConv::SwiftTail;284 CI->setTailCallKind(isSwiftTailCall ? llvm::CallInst::TCK_MustTail285 : llvm::CallInst::TCK_Tail);286 CI->setCallingConv(ToFunc->getCallingConv());287 CI->setAttributes(ToFunc->getAttributes());288 if (Thunk->getReturnType()->isVoidTy())289 Builder.CreateRetVoid();290 else291 Builder.CreateRet(Builder.CreateAggregateCast(CI, Thunk->getReturnType()));292}293 294// Check if the old merged/optimized IndexOperandHashMap is compatible with295// the current IndexOperandHashMap. An operand hash may not be stable across296// different builds due to varying modules combined. To address this, we relax297// the hash check condition by comparing Const hash patterns instead of absolute298// hash values. For example, let's assume we have three Consts located at idx1,299// idx3, and idx6, where their corresponding hashes are hash1, hash2, and hash1300// in the old merged map below:301// Old (Merged): [(idx1, hash1), (idx3, hash2), (idx6, hash1)]302// Current: [(idx1, hash1'), (idx3, hash2'), (idx6, hash1')]303// If the current function also has three Consts in the same locations,304// with hash sequences hash1', hash2', and hash1' where the first and third305// are the same as the old hash sequences, we consider them matched.306static bool checkConstHashCompatible(307 const DenseMap<IndexPair, stable_hash> &OldInstOpndIndexToConstHash,308 const DenseMap<IndexPair, stable_hash> &CurrInstOpndIndexToConstHash) {309 310 DenseMap<stable_hash, stable_hash> OldHashToCurrHash;311 for (const auto &[Index, OldHash] : OldInstOpndIndexToConstHash) {312 auto It = CurrInstOpndIndexToConstHash.find(Index);313 if (It == CurrInstOpndIndexToConstHash.end())314 return false;315 316 auto CurrHash = It->second;317 auto J = OldHashToCurrHash.find(OldHash);318 if (J == OldHashToCurrHash.end())319 OldHashToCurrHash.insert({OldHash, CurrHash});320 else if (J->second != CurrHash)321 return false;322 }323 324 return true;325}326 327// Validate the locations pointed by a param has the same hash and Constant.328static bool329checkConstLocationCompatible(const StableFunctionMap::StableFunctionEntry &SF,330 const IndexInstrMap &IndexInstruction,331 const ParamLocsVecTy &ParamLocsVec) {332 for (auto &ParamLocs : ParamLocsVec) {333 std::optional<stable_hash> OldHash;334 std::optional<Constant *> OldConst;335 for (auto &Loc : ParamLocs) {336 assert(SF.IndexOperandHashMap->count(Loc));337 auto CurrHash = SF.IndexOperandHashMap->at(Loc);338 auto [InstIndex, OpndIndex] = Loc;339 assert(InstIndex < IndexInstruction.size());340 const auto *Inst = IndexInstruction.lookup(InstIndex);341 auto *CurrConst = cast<Constant>(Inst->getOperand(OpndIndex));342 if (!OldHash) {343 OldHash = CurrHash;344 OldConst = CurrConst;345 } else if (CurrConst != *OldConst || CurrHash != *OldHash) {346 return false;347 }348 }349 }350 return true;351}352 353static ParamLocsVecTy354computeParamInfo(const StableFunctionMap::StableFunctionEntries &SFS) {355 std::map<std::vector<stable_hash>, ParamLocs> HashSeqToLocs;356 auto &RSF = *SFS[0];357 unsigned StableFunctionCount = SFS.size();358 359 for (auto &[IndexPair, Hash] : *RSF.IndexOperandHashMap) {360 // Const hash sequence across stable functions.361 // We will allocate a parameter per unique hash squence.362 // can't use SmallVector as key363 std::vector<stable_hash> ConstHashSeq;364 ConstHashSeq.push_back(Hash);365 bool Identical = true;366 for (unsigned J = 1; J < StableFunctionCount; ++J) {367 auto &SF = SFS[J];368 auto SHash = SF->IndexOperandHashMap->at(IndexPair);369 if (Hash != SHash)370 Identical = false;371 ConstHashSeq.push_back(SHash);372 }373 374 if (Identical)375 continue;376 377 // For each unique Const hash sequence (parameter), add the locations.378 HashSeqToLocs[ConstHashSeq].push_back(IndexPair);379 }380 381 ParamLocsVecTy ParamLocsVec;382 for (auto &[HashSeq, Locs] : HashSeqToLocs)383 ParamLocsVec.push_back(std::move(Locs));384 385 llvm::sort(ParamLocsVec, [&](const ParamLocs &L, const ParamLocs &R) {386 return L[0] < R[0];387 });388 389 return ParamLocsVec;390}391 392bool GlobalMergeFunc::merge(Module &M, const StableFunctionMap *FunctionMap) {393 bool Changed = false;394 395 // Collect stable functions related to the current module.396 DenseMap<stable_hash, SmallVector<std::pair<Function *, FunctionHashInfo>>>397 HashToFuncs;398 for (auto &F : M) {399 if (!isEligibleFunction(&F))400 continue;401 auto FI = llvm::StructuralHashWithDifferences(F, ignoreOp);402 if (FunctionMap->contains(FI.FunctionHash))403 HashToFuncs[FI.FunctionHash].emplace_back(&F, std::move(FI));404 }405 406 for (auto &[Hash, Funcs] : HashToFuncs) {407 std::optional<ParamLocsVecTy> ParamLocsVec;408 SmallVector<FuncMergeInfo> FuncMergeInfos;409 auto &SFS = FunctionMap->at(Hash);410 assert(!SFS.empty());411 auto &RFS = SFS[0];412 413 // Iterate functions with the same hash.414 for (auto &[F, FI] : Funcs) {415 // Check if the function is compatible with any stable function416 // in terms of the number of instructions and ignored operands.417 if (RFS->InstCount != FI.IndexInstruction->size())418 continue;419 420 auto hasValidSharedConst = [&](StableFunctionMap::StableFunctionEntry *SF,421 FunctionHashInfo &FHI) {422 for (auto &[Index, Hash] : *SF->IndexOperandHashMap) {423 auto [InstIndex, OpndIndex] = Index;424 assert(InstIndex < FHI.IndexInstruction->size());425 auto *Inst = FHI.IndexInstruction->lookup(InstIndex);426 if (!ignoreOp(Inst, OpndIndex))427 return false;428 }429 return true;430 };431 if (!hasValidSharedConst(RFS.get(), FI))432 continue;433 434 for (auto &SF : SFS) {435 assert(SF->InstCount == FI.IndexInstruction->size());436 assert(hasValidSharedConst(SF.get(), FI));437 // Check if there is any stable function that is compatiable with the438 // current one.439 if (!checkConstHashCompatible(*SF->IndexOperandHashMap,440 *FI.IndexOperandHashMap))441 continue;442 if (!ParamLocsVec.has_value()) {443 ParamLocsVec = computeParamInfo(SFS);444 LLVM_DEBUG(dbgs() << "[GlobalMergeFunc] Merging hash: " << Hash445 << " with Params " << ParamLocsVec->size() << "\n");446 }447 if (!checkConstLocationCompatible(*SF, *FI.IndexInstruction,448 *ParamLocsVec))449 continue;450 451 // If a stable function matching the current one is found,452 // create a candidate for merging and proceed to the next function.453 FuncMergeInfos.emplace_back(SF.get(), F, FI.IndexInstruction.get());454 break;455 }456 }457 unsigned FuncMergeInfoSize = FuncMergeInfos.size();458 if (FuncMergeInfoSize == 0)459 continue;460 461 LLVM_DEBUG(dbgs() << "[GlobalMergeFunc] Merging function count "462 << FuncMergeInfoSize << " for hash: " << Hash << "\n");463 464 for (auto &FMI : FuncMergeInfos) {465 Changed = true;466 467 // We've already validated all locations of constant operands pointed by468 // the parameters. Populate parameters pointing to the original constants.469 SmallVector<Constant *> Params;470 SmallVector<Type *> ParamTypes;471 for (auto &ParamLocs : *ParamLocsVec) {472 assert(!ParamLocs.empty());473 auto &[InstIndex, OpndIndex] = ParamLocs[0];474 auto *Inst = FMI.IndexInstruction->lookup(InstIndex);475 auto *Opnd = cast<Constant>(Inst->getOperand(OpndIndex));476 Params.push_back(Opnd);477 ParamTypes.push_back(Opnd->getType());478 }479 480 // Create a merged function derived from the current function.481 Function *MergedFunc =482 createMergedFunction(FMI, ParamTypes, *ParamLocsVec);483 484 LLVM_DEBUG({485 dbgs() << "[GlobalMergeFunc] Merged function (hash:" << FMI.SF->Hash486 << ") " << MergedFunc->getName() << " generated from "487 << FMI.F->getName() << ":\n";488 MergedFunc->dump();489 });490 491 // Transform the current function into a thunk that calls the merged492 // function.493 createThunk(FMI, Params, MergedFunc);494 LLVM_DEBUG({495 dbgs() << "[GlobalMergeFunc] Thunk generated: \n";496 FMI.F->dump();497 });498 ++NumMergedFunctions;499 }500 }501 502 return Changed;503}504 505void GlobalMergeFunc::initializeMergerMode(const Module &M) {506 // Initialize the local function map regardless of the merger mode.507 LocalFunctionMap = std::make_unique<StableFunctionMap>();508 509 // Disable codegen data for merging. The local merge is still enabled.510 if (DisableCGDataForMerging)511 return;512 513 // (Full)LTO module does not have functions added to the index.514 // In this case, we run a local merger without using codegen data.515 if (Index && !Index->hasExportedFunctions(M))516 return;517 518 if (cgdata::emitCGData())519 MergerMode = HashFunctionMode::BuildingHashFuncion;520 else if (cgdata::hasStableFunctionMap())521 MergerMode = HashFunctionMode::UsingHashFunction;522}523 524void GlobalMergeFunc::emitFunctionMap(Module &M) {525 LLVM_DEBUG(dbgs() << "Emit function map. Size: " << LocalFunctionMap->size()526 << "\n");527 // No need to emit the function map if it is empty.528 if (LocalFunctionMap->empty())529 return;530 SmallVector<char> Buf;531 raw_svector_ostream OS(Buf);532 533 std::vector<CGDataPatchItem> PatchItems;534 StableFunctionMapRecord::serialize(OS, LocalFunctionMap.get(), PatchItems);535 CGDataOStream COS(OS);536 COS.patch(PatchItems);537 538 std::unique_ptr<MemoryBuffer> Buffer = MemoryBuffer::getMemBuffer(539 OS.str(), "in-memory stable function map", false);540 541 Triple TT(M.getTargetTriple());542 embedBufferInModule(M, *Buffer,543 getCodeGenDataSectionName(CG_merge, TT.getObjectFormat()),544 Align(4));545}546 547bool GlobalMergeFunc::run(Module &M) {548 initializeMergerMode(M);549 550 const StableFunctionMap *FuncMap;551 if (MergerMode == HashFunctionMode::UsingHashFunction) {552 // Use the prior CG data to optimistically create global merge candidates.553 FuncMap = cgdata::getStableFunctionMap();554 } else {555 analyze(M);556 // Emit the local function map to the custom section, __llvm_merge before557 // finalizing it.558 if (MergerMode == HashFunctionMode::BuildingHashFuncion)559 emitFunctionMap(M);560 LocalFunctionMap->finalize();561 FuncMap = LocalFunctionMap.get();562 }563 564 return merge(M, FuncMap);565}566 567namespace {568 569class GlobalMergeFuncPassWrapper : public ModulePass {570 571public:572 static char ID;573 574 GlobalMergeFuncPassWrapper();575 576 void getAnalysisUsage(AnalysisUsage &AU) const override {577 AU.addUsedIfAvailable<ImmutableModuleSummaryIndexWrapperPass>();578 AU.setPreservesAll();579 ModulePass::getAnalysisUsage(AU);580 }581 582 StringRef getPassName() const override { return "Global Merge Functions"; }583 584 bool runOnModule(Module &M) override;585};586 587} // namespace588 589char GlobalMergeFuncPassWrapper::ID = 0;590INITIALIZE_PASS(GlobalMergeFuncPassWrapper, "global-merge-func",591 "Global merge function pass", false, false)592 593ModulePass *llvm::createGlobalMergeFuncPass() {594 return new GlobalMergeFuncPassWrapper();595}596 597GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() : ModulePass(ID) {598 initializeGlobalMergeFuncPassWrapperPass(599 *llvm::PassRegistry::getPassRegistry());600}601 602bool GlobalMergeFuncPassWrapper::runOnModule(Module &M) {603 const ModuleSummaryIndex *Index = nullptr;604 if (auto *IndexWrapperPass =605 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())606 Index = IndexWrapperPass->getIndex();607 608 return GlobalMergeFunc(Index).run(M);609}610 611PreservedAnalyses GlobalMergeFuncPass::run(Module &M,612 AnalysisManager<Module> &AM) {613 bool Changed = GlobalMergeFunc(ImportSummary).run(M);614 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();615}616