LLVM 20.0.0git
GlobalMergeFunctions.cpp
Go to the documentation of this file.
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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass implements the global merge function pass.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/Statistic.h"
17#include "llvm/IR/IRBuilder.h"
22
23#define DEBUG_TYPE "global-merge-func"
24
25using namespace llvm;
26using namespace llvm::support;
27
29 "disable-cgdata-for-merging", cl::Hidden,
30 cl::desc("Disable codegen data for function merging. Local "
31 "merging is still enabled within a module."),
32 cl::init(false));
33
34STATISTIC(NumMergedFunctions,
35 "Number of functions that are actually merged using function hash");
36STATISTIC(NumAnalyzedModues, "Number of modules that are analyzed");
37STATISTIC(NumAnalyzedFunctions, "Number of functions that are analyzed");
38STATISTIC(NumEligibleFunctions, "Number of functions that are eligible");
39
40/// Returns true if the \OpIdx operand of \p CI is the callee operand.
41static bool isCalleeOperand(const CallBase *CI, unsigned OpIdx) {
42 return &CI->getCalledOperandUse() == &CI->getOperandUse(OpIdx);
43}
44
45static bool canParameterizeCallOperand(const CallBase *CI, unsigned OpIdx) {
46 if (CI->isInlineAsm())
47 return false;
48 Function *Callee = CI->getCalledOperand()
49 ? dyn_cast_or_null<Function>(
51 : nullptr;
52 if (Callee) {
53 if (Callee->isIntrinsic())
54 return false;
55 auto Name = Callee->getName();
56 // objc_msgSend stubs must be called, and can't have their address taken.
57 if (Name.starts_with("objc_msgSend$"))
58 return false;
59 // Calls to dtrace probes must generate unique patchpoints.
60 if (Name.starts_with("__dtrace"))
61 return false;
62 }
63 if (isCalleeOperand(CI, OpIdx)) {
64 // The operand is the callee and it has already been signed. Ignore this
65 // because we cannot add another ptrauth bundle to the call instruction.
66 if (CI->getOperandBundle(LLVMContext::OB_ptrauth).has_value())
67 return false;
68 } else {
69 // The target of the arc-attached call must be a constant and cannot be
70 // parameterized.
72 OpIdx))
73 return false;
74 }
75 return true;
76}
77
78/// Returns true if function \p F is eligible for merging.
80 if (F->isDeclaration())
81 return false;
82
83 if (F->hasFnAttribute(llvm::Attribute::NoMerge) ||
84 F->hasFnAttribute(llvm::Attribute::AlwaysInline))
85 return false;
86
87 if (F->hasAvailableExternallyLinkage())
88 return false;
89
90 if (F->getFunctionType()->isVarArg())
91 return false;
92
93 if (F->getCallingConv() == CallingConv::SwiftTail)
94 return false;
95
96 // If function contains callsites with musttail, if we merge
97 // it, the merged function will have the musttail callsite, but
98 // the number of parameters can change, thus the parameter count
99 // of the callsite will mismatch with the function itself.
100 for (const BasicBlock &BB : *F) {
101 for (const Instruction &I : BB) {
102 const auto *CB = dyn_cast<CallBase>(&I);
103 if (CB && CB->isMustTailCall())
104 return false;
105 }
106 }
107
108 return true;
109}
110
112 switch (I->getOpcode()) {
113 case Instruction::Load:
114 case Instruction::Store:
115 case Instruction::Call:
116 case Instruction::Invoke:
117 return true;
118 default:
119 return false;
120 }
121}
122
123// This function takes an instruction, \p I, and an operand index, \p OpIdx.
124// It returns true if the operand should be ignored in the hash computation.
125// If \p OpIdx is out of range based on the other instruction context, it cannot
126// be ignored.
127static bool ignoreOp(const Instruction *I, unsigned OpIdx) {
128 if (OpIdx >= I->getNumOperands())
129 return false;
130
132 return false;
133
134 if (!isa<Constant>(I->getOperand(OpIdx)))
135 return false;
136
137 if (const auto *CI = dyn_cast<CallBase>(I))
138 return canParameterizeCallOperand(CI, OpIdx);
139
140 return true;
141}
142
143static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) {
144 Type *SrcTy = V->getType();
145 if (SrcTy->isStructTy()) {
146 assert(DestTy->isStructTy());
147 assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
148 Value *Result = PoisonValue::get(DestTy);
149 for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
150 Value *Element =
151 createCast(Builder, Builder.CreateExtractValue(V, ArrayRef(I)),
152 DestTy->getStructElementType(I));
153
154 Result = Builder.CreateInsertValue(Result, Element, ArrayRef(I));
155 }
156 return Result;
157 }
158 assert(!DestTy->isStructTy());
159 if (auto *SrcAT = dyn_cast<ArrayType>(SrcTy)) {
160 auto *DestAT = dyn_cast<ArrayType>(DestTy);
161 assert(DestAT);
162 assert(SrcAT->getNumElements() == DestAT->getNumElements());
163 Value *Result = PoisonValue::get(DestTy);
164 for (unsigned int I = 0, E = SrcAT->getNumElements(); I < E; ++I) {
165 Value *Element =
166 createCast(Builder, Builder.CreateExtractValue(V, ArrayRef(I)),
167 DestAT->getElementType());
168
169 Result = Builder.CreateInsertValue(Result, Element, ArrayRef(I));
170 }
171 return Result;
172 }
173 assert(!DestTy->isArrayTy());
174 if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
175 return Builder.CreateIntToPtr(V, DestTy);
176 if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
177 return Builder.CreatePtrToInt(V, DestTy);
178 return Builder.CreateBitCast(V, DestTy);
179}
180
182 ++NumAnalyzedModues;
183 for (Function &Func : M) {
184 ++NumAnalyzedFunctions;
185 if (isEligibleFunction(&Func)) {
186 ++NumEligibleFunctions;
187
189
190 // Convert the operand map to a vector for a serialization-friendly
191 // format.
192 IndexOperandHashVecType IndexOperandHashes;
193 for (auto &Pair : *FI.IndexOperandHashMap)
194 IndexOperandHashes.emplace_back(Pair);
195
196 StableFunction SF(FI.FunctionHash, get_stable_name(Func.getName()).str(),
197 M.getModuleIdentifier(), FI.IndexInstruction->size(),
198 std::move(IndexOperandHashes));
199
200 LocalFunctionMap->insert(SF);
201 }
202 }
203}
204
205/// Tuple to hold function info to process merging.
211 IndexInstrMap *IndexInstruction)
212 : SF(SF), F(F), IndexInstruction(std::move(IndexInstruction)) {}
213};
214
215// Given the func info, and the parameterized locations, create and return
216// a new merged function by replacing the original constants with the new
217// parameters.
219 ArrayRef<Type *> ConstParamTypes,
220 const ParamLocsVecTy &ParamLocsVec) {
221 // Synthesize a new merged function name by appending ".Tgm" to the root
222 // function's name.
223 auto *MergedFunc = FI.F;
224 std::string NewFunctionName =
226 auto *M = MergedFunc->getParent();
227 assert(!M->getFunction(NewFunctionName));
228
229 FunctionType *OrigTy = MergedFunc->getFunctionType();
230 // Get the original params' types.
231 SmallVector<Type *> ParamTypes(OrigTy->param_begin(), OrigTy->param_end());
232 // Append const parameter types that are passed in.
233 ParamTypes.append(ConstParamTypes.begin(), ConstParamTypes.end());
234 FunctionType *FuncType = FunctionType::get(OrigTy->getReturnType(),
235 ParamTypes, /*isVarArg=*/false);
236
237 // Declare a new function
238 Function *NewFunction =
239 Function::Create(FuncType, MergedFunc->getLinkage(), NewFunctionName);
240 if (auto *SP = MergedFunc->getSubprogram())
241 NewFunction->setSubprogram(SP);
242 NewFunction->copyAttributesFrom(MergedFunc);
244
246 NewFunction->addFnAttr(Attribute::NoInline);
247
248 // Add the new function before the root function.
249 M->getFunctionList().insert(MergedFunc->getIterator(), NewFunction);
250
251 // Move the body of MergedFunc into the NewFunction.
252 NewFunction->splice(NewFunction->begin(), MergedFunc);
253
254 // Update the original args by the new args.
255 auto NewArgIter = NewFunction->arg_begin();
256 for (Argument &OrigArg : MergedFunc->args()) {
257 Argument &NewArg = *NewArgIter++;
258 OrigArg.replaceAllUsesWith(&NewArg);
259 }
260
261 // Replace the original Constants by the new args.
262 unsigned NumOrigArgs = MergedFunc->arg_size();
263 for (unsigned ParamIdx = 0; ParamIdx < ParamLocsVec.size(); ++ParamIdx) {
264 Argument *NewArg = NewFunction->getArg(NumOrigArgs + ParamIdx);
265 for (auto [InstIndex, OpndIndex] : ParamLocsVec[ParamIdx]) {
266 auto *Inst = FI.IndexInstruction->lookup(InstIndex);
267 auto *OrigC = Inst->getOperand(OpndIndex);
268 if (OrigC->getType() != NewArg->getType()) {
269 IRBuilder<> Builder(Inst->getParent(), Inst->getIterator());
270 Inst->setOperand(OpndIndex,
271 createCast(Builder, NewArg, OrigC->getType()));
272 } else {
273 Inst->setOperand(OpndIndex, NewArg);
274 }
275 }
276 }
277
278 return NewFunction;
279}
280
281// Given the original function (Thunk) and the merged function (ToFunc), create
282// a thunk to the merged function.
284 Function *ToFunc) {
285 auto *Thunk = FI.F;
286
287 assert(Thunk->arg_size() + Params.size() ==
288 ToFunc->getFunctionType()->getNumParams());
289 Thunk->dropAllReferences();
290
291 BasicBlock *BB = BasicBlock::Create(Thunk->getContext(), "", Thunk);
292 IRBuilder<> Builder(BB);
293
295 unsigned ParamIdx = 0;
296 FunctionType *ToFuncTy = ToFunc->getFunctionType();
297
298 // Add arguments which are passed through Thunk.
299 for (Argument &AI : Thunk->args()) {
300 Args.push_back(createCast(Builder, &AI, ToFuncTy->getParamType(ParamIdx)));
301 ++ParamIdx;
302 }
303
304 // Add new arguments defined by Params.
305 for (auto *Param : Params) {
306 assert(ParamIdx < ToFuncTy->getNumParams());
307 Args.push_back(
308 createCast(Builder, Param, ToFuncTy->getParamType(ParamIdx)));
309 ++ParamIdx;
310 }
311
312 CallInst *CI = Builder.CreateCall(ToFunc, Args);
313 bool isSwiftTailCall = ToFunc->getCallingConv() == CallingConv::SwiftTail &&
314 Thunk->getCallingConv() == CallingConv::SwiftTail;
317 CI->setCallingConv(ToFunc->getCallingConv());
318 CI->setAttributes(ToFunc->getAttributes());
319 if (Thunk->getReturnType()->isVoidTy())
320 Builder.CreateRetVoid();
321 else
322 Builder.CreateRet(createCast(Builder, CI, Thunk->getReturnType()));
323}
324
325// Check if the old merged/optimized IndexOperandHashMap is compatible with
326// the current IndexOperandHashMap. An operand hash may not be stable across
327// different builds due to varying modules combined. To address this, we relax
328// the hash check condition by comparing Const hash patterns instead of absolute
329// hash values. For example, let's assume we have three Consts located at idx1,
330// idx3, and idx6, where their corresponding hashes are hash1, hash2, and hash1
331// in the old merged map below:
332// Old (Merged): [(idx1, hash1), (idx3, hash2), (idx6, hash1)]
333// Current: [(idx1, hash1'), (idx3, hash2'), (idx6, hash1')]
334// If the current function also has three Consts in the same locations,
335// with hash sequences hash1', hash2', and hash1' where the first and third
336// are the same as the old hash sequences, we consider them matched.
338 const DenseMap<IndexPair, stable_hash> &OldInstOpndIndexToConstHash,
339 const DenseMap<IndexPair, stable_hash> &CurrInstOpndIndexToConstHash) {
340
341 DenseMap<stable_hash, stable_hash> OldHashToCurrHash;
342 for (const auto &[Index, OldHash] : OldInstOpndIndexToConstHash) {
343 auto It = CurrInstOpndIndexToConstHash.find(Index);
344 if (It == CurrInstOpndIndexToConstHash.end())
345 return false;
346
347 auto CurrHash = It->second;
348 auto J = OldHashToCurrHash.find(OldHash);
349 if (J == OldHashToCurrHash.end())
350 OldHashToCurrHash.insert({OldHash, CurrHash});
351 else if (J->second != CurrHash)
352 return false;
353 }
354
355 return true;
356}
357
358// Validate the locations pointed by a param has the same hash and Constant.
359static bool
361 const IndexInstrMap &IndexInstruction,
362 const ParamLocsVecTy &ParamLocsVec) {
363 for (auto &ParamLocs : ParamLocsVec) {
364 std::optional<stable_hash> OldHash;
365 std::optional<Constant *> OldConst;
366 for (auto &Loc : ParamLocs) {
367 assert(SF.IndexOperandHashMap->count(Loc));
368 auto CurrHash = SF.IndexOperandHashMap.get()->at(Loc);
369 auto [InstIndex, OpndIndex] = Loc;
370 assert(InstIndex < IndexInstruction.size());
371 const auto *Inst = IndexInstruction.lookup(InstIndex);
372 auto *CurrConst = cast<Constant>(Inst->getOperand(OpndIndex));
373 if (!OldHash) {
374 OldHash = CurrHash;
375 OldConst = CurrConst;
376 } else if (CurrConst != *OldConst || CurrHash != *OldHash) {
377 return false;
378 }
379 }
380 }
381 return true;
382}
383
385 const SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>>
386 &SFS) {
387 std::map<std::vector<stable_hash>, ParamLocs> HashSeqToLocs;
388 auto &RSF = *SFS[0];
389 unsigned StableFunctionCount = SFS.size();
390
391 for (auto &[IndexPair, Hash] : *RSF.IndexOperandHashMap) {
392 // Const hash sequence across stable functions.
393 // We will allocate a parameter per unique hash squence.
394 // can't use SmallVector as key
395 std::vector<stable_hash> ConstHashSeq;
396 ConstHashSeq.push_back(Hash);
397 bool Identical = true;
398 for (unsigned J = 1; J < StableFunctionCount; ++J) {
399 auto &SF = SFS[J];
400 auto SHash = SF->IndexOperandHashMap->at(IndexPair);
401 if (Hash != SHash)
402 Identical = false;
403 ConstHashSeq.push_back(SHash);
404 }
405
406 if (Identical)
407 continue;
408
409 // For each unique Const hash sequence (parameter), add the locations.
410 HashSeqToLocs[ConstHashSeq].push_back(IndexPair);
411 }
412
413 ParamLocsVecTy ParamLocsVec;
414 for (auto &[HashSeq, Locs] : HashSeqToLocs)
415 ParamLocsVec.push_back(std::move(Locs));
416
417 llvm::sort(ParamLocsVec, [&](const ParamLocs &L, const ParamLocs &R) {
418 return L[0] < R[0];
419 });
420
421 return ParamLocsVec;
422}
423
424bool GlobalMergeFunc::merge(Module &M, const StableFunctionMap *FunctionMap) {
425 bool Changed = false;
426
427 // Collect stable functions related to the current module.
429 HashToFuncs;
430 auto &Maps = FunctionMap->getFunctionMap();
431 for (auto &F : M) {
432 if (!isEligibleFunction(&F))
433 continue;
435 if (Maps.contains(FI.FunctionHash))
436 HashToFuncs[FI.FunctionHash].emplace_back(&F, std::move(FI));
437 }
438
439 for (auto &[Hash, Funcs] : HashToFuncs) {
440 std::optional<ParamLocsVecTy> ParamLocsVec;
441 SmallVector<FuncMergeInfo> FuncMergeInfos;
442 auto &SFS = Maps.at(Hash);
443 assert(!SFS.empty());
444 auto &RFS = SFS[0];
445
446 // Iterate functions with the same hash.
447 for (auto &[F, FI] : Funcs) {
448 // Check if the function is compatible with any stable function
449 // in terms of the number of instructions and ignored operands.
450 if (RFS->InstCount != FI.IndexInstruction->size())
451 continue;
452
453 auto hasValidSharedConst = [&](StableFunctionMap::StableFunctionEntry *SF,
454 FunctionHashInfo &FHI) {
455 for (auto &[Index, Hash] : *SF->IndexOperandHashMap) {
456 auto [InstIndex, OpndIndex] = Index;
457 assert(InstIndex < FHI.IndexInstruction->size());
458 auto *Inst = FHI.IndexInstruction->lookup(InstIndex);
459 if (!ignoreOp(Inst, OpndIndex))
460 return false;
461 }
462 return true;
463 };
464 if (!hasValidSharedConst(RFS.get(), FI))
465 continue;
466
467 for (auto &SF : SFS) {
468 assert(SF->InstCount == FI.IndexInstruction->size());
469 assert(hasValidSharedConst(SF.get(), FI));
470 // Check if there is any stable function that is compatiable with the
471 // current one.
473 *FI.IndexOperandHashMap))
474 continue;
475 if (!ParamLocsVec.has_value()) {
476 ParamLocsVec = computeParamInfo(SFS);
477 LLVM_DEBUG(dbgs() << "[GlobalMergeFunc] Merging hash: " << Hash
478 << " with Params " << ParamLocsVec->size() << "\n");
479 }
480 if (!checkConstLocationCompatible(*SF, *FI.IndexInstruction,
481 *ParamLocsVec))
482 continue;
483
484 // If a stable function matching the current one is found,
485 // create a candidate for merging and proceed to the next function.
486 FuncMergeInfos.emplace_back(SF.get(), F, FI.IndexInstruction.get());
487 break;
488 }
489 }
490 unsigned FuncMergeInfoSize = FuncMergeInfos.size();
491 if (FuncMergeInfoSize == 0)
492 continue;
493
494 LLVM_DEBUG(dbgs() << "[GlobalMergeFunc] Merging function count "
495 << FuncMergeInfoSize << " for hash: " << Hash << "\n");
496
497 for (auto &FMI : FuncMergeInfos) {
498 Changed = true;
499
500 // We've already validated all locations of constant operands pointed by
501 // the parameters. Populate parameters pointing to the original constants.
503 SmallVector<Type *> ParamTypes;
504 for (auto &ParamLocs : *ParamLocsVec) {
506 auto &[InstIndex, OpndIndex] = ParamLocs[0];
507 auto *Inst = FMI.IndexInstruction->lookup(InstIndex);
508 auto *Opnd = cast<Constant>(Inst->getOperand(OpndIndex));
509 Params.push_back(Opnd);
510 ParamTypes.push_back(Opnd->getType());
511 }
512
513 // Create a merged function derived from the current function.
514 Function *MergedFunc =
515 createMergedFunction(FMI, ParamTypes, *ParamLocsVec);
516
517 LLVM_DEBUG({
518 dbgs() << "[GlobalMergeFunc] Merged function (hash:" << FMI.SF->Hash
519 << ") " << MergedFunc->getName() << " generated from "
520 << FMI.F->getName() << ":\n";
521 MergedFunc->dump();
522 });
523
524 // Transform the current function into a thunk that calls the merged
525 // function.
526 createThunk(FMI, Params, MergedFunc);
527 LLVM_DEBUG({
528 dbgs() << "[GlobalMergeFunc] Thunk generated: \n";
529 FMI.F->dump();
530 });
531 ++NumMergedFunctions;
532 }
533 }
534
535 return Changed;
536}
537
539 // Initialize the local function map regardless of the merger mode.
540 LocalFunctionMap = std::make_unique<StableFunctionMap>();
541
542 // Disable codegen data for merging. The local merge is still enabled.
544 return;
545
546 // (Full)LTO module does not have functions added to the index.
547 // In this case, we run a local merger without using codegen data.
548 if (Index && !Index->hasExportedFunctions(M))
549 return;
550
551 if (cgdata::emitCGData())
552 MergerMode = HashFunctionMode::BuildingHashFuncion;
554 MergerMode = HashFunctionMode::UsingHashFunction;
555}
556
558 LLVM_DEBUG(dbgs() << "Emit function map. Size: " << LocalFunctionMap->size()
559 << "\n");
560 // No need to emit the function map if it is empty.
561 if (LocalFunctionMap->empty())
562 return;
565
566 StableFunctionMapRecord::serialize(OS, LocalFunctionMap.get());
567
568 std::unique_ptr<MemoryBuffer> Buffer = MemoryBuffer::getMemBuffer(
569 OS.str(), "in-memory stable function map", false);
570
571 Triple TT(M.getTargetTriple());
572 embedBufferInModule(M, *Buffer.get(),
573 getCodeGenDataSectionName(CG_merge, TT.getObjectFormat()),
574 Align(4));
575}
576
579
580 const StableFunctionMap *FuncMap;
581 if (MergerMode == HashFunctionMode::UsingHashFunction) {
582 // Use the prior CG data to optimistically create global merge candidates.
584 } else {
585 analyze(M);
586 // Emit the local function map to the custom section, __llvm_merge before
587 // finalizing it.
588 if (MergerMode == HashFunctionMode::BuildingHashFuncion)
590 LocalFunctionMap->finalize();
591 FuncMap = LocalFunctionMap.get();
592 }
593
594 return merge(M, FuncMap);
595}
596
597namespace {
598
599class GlobalMergeFuncPassWrapper : public ModulePass {
600
601public:
602 static char ID;
603
604 GlobalMergeFuncPassWrapper();
605
606 void getAnalysisUsage(AnalysisUsage &AU) const override {
608 AU.setPreservesAll();
609 ModulePass::getAnalysisUsage(AU);
610 }
611
612 StringRef getPassName() const override { return "Global Merge Functions"; }
613
614 bool runOnModule(Module &M) override;
615};
616
617} // namespace
618
619char GlobalMergeFuncPassWrapper::ID = 0;
620INITIALIZE_PASS_BEGIN(GlobalMergeFuncPassWrapper, "global-merge-func",
621 "Global merge function pass", false, false)
622INITIALIZE_PASS_END(GlobalMergeFuncPassWrapper, "global-merge-func",
624
625namespace llvm {
627 return new GlobalMergeFuncPassWrapper();
628}
629} // namespace llvm
630
631GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() : ModulePass(ID) {
634}
635
636bool GlobalMergeFuncPassWrapper::runOnModule(Module &M) {
637 const ModuleSummaryIndex *Index = nullptr;
638 if (auto *IndexWrapperPass =
639 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
640 Index = IndexWrapperPass->getIndex();
641
642 return GlobalMergeFunc(Index).run(M);
643}
644
647 bool Changed = GlobalMergeFunc(ImportSummary).run(M);
648 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
649}
Performs the initial survey of the specified function
#define LLVM_DEBUG(...)
Definition: Debug.h:106
std::string Name
static ParamLocsVecTy computeParamInfo(const SmallVector< std::unique_ptr< StableFunctionMap::StableFunctionEntry > > &SFS)
static bool checkConstHashCompatible(const DenseMap< IndexPair, stable_hash > &OldInstOpndIndexToConstHash, const DenseMap< IndexPair, stable_hash > &CurrInstOpndIndexToConstHash)
global merge func
static cl::opt< bool > DisableCGDataForMerging("disable-cgdata-for-merging", cl::Hidden, cl::desc("Disable codegen data for function merging. Local " "merging is still enabled within a module."), cl::init(false))
static bool canParameterizeCallOperand(const CallBase *CI, unsigned OpIdx)
static Function * createMergedFunction(FuncMergeInfo &FI, ArrayRef< Type * > ConstParamTypes, const ParamLocsVecTy &ParamLocsVec)
static void createThunk(FuncMergeInfo &FI, ArrayRef< Constant * > Params, Function *ToFunc)
global merge Global merge function pass
static Value * createCast(IRBuilder<> &Builder, Value *V, Type *DestTy)
static bool isEligibleInstructionForConstantSharing(const Instruction *I)
static bool ignoreOp(const Instruction *I, unsigned OpIdx)
bool isEligibleFunction(Function *F)
Returns true if function F is eligible for merging.
static bool checkConstLocationCompatible(const StableFunctionMap::StableFunctionEntry &SF, const IndexInstrMap &IndexInstruction, const ParamLocsVecTy &ParamLocsVec)
static bool isCalleeOperand(const CallBase *CI, unsigned OpIdx)
Returns true if the \OpIdx operand of CI is the callee operand.
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This is the interface to build a ModuleSummaryIndex for a module.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:57
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
Represent the analysis usage information of a pass.
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
This class represents an incoming formal argument to a Function.
Definition: Argument.h:31
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:157
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:168
iterator begin() const
Definition: ArrayRef.h:156
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1120
bool isInlineAsm() const
Check if this call is an inline asm statement.
Definition: InstrTypes.h:1416
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1411
bool isOperandBundleOfType(uint32_t ID, unsigned Idx) const
Return true if the operand at index Idx is a bundle operand that has tag ID ID.
Definition: InstrTypes.h:1991
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2051
Value * getCalledOperand() const
Definition: InstrTypes.h:1342
const Use & getCalledOperandUse() const
Definition: InstrTypes.h:1344
void setAttributes(AttributeList A)
Set the attributes for this call.
Definition: InstrTypes.h:1428
This class represents a function call, abstracting a target machine's calling convention.
void setTailCallKind(TailCallKind TCK)
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:156
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:144
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.cpp:641
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1870
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:173
void splice(Function::iterator ToIt, Function *FromF)
Transfer all blocks from FromF to this function at ToIt.
Definition: Function.h:761
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:216
CallingConv::ID getCallingConv() const
getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...
Definition: Function.h:277
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:353
iterator begin()
Definition: Function.h:853
arg_iterator arg_begin()
Definition: Function.h:868
Argument * getArg(unsigned i) const
Definition: Function.h:886
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:860
GlobalMergeFunc is a ModulePass that implements a function merging mechanism using stable function ha...
void analyze(Module &M)
Analyze module to create stable function into LocalFunctionMap.
void initializeMergerMode(const Module &M)
bool merge(Module &M, const StableFunctionMap *FunctionMap)
Merge functions in the module using the given function map.
void emitFunctionMap(Module &M)
Emit LocalFunctionMap into __llvm_merge section.
static constexpr const char MergingInstanceSuffix[]
The suffix used to identify the merged function that parameterizes the constant values.
void setDLLStorageClass(DLLStorageClassTypes C)
Definition: GlobalValue.h:284
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:537
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:59
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:2556
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:2549
Value * CreateIntToPtr(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2141
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
Definition: IRBuilder.h:1133
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2146
ReturnInst * CreateRetVoid()
Create a 'ret void' instruction.
Definition: IRBuilder.h:1128
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2136
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args={}, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2443
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2699
Legacy wrapper pass to provide the ModuleSummaryIndex object.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
ValueT lookup(const KeyT &Key) const
Definition: MapVector.h:110
size_type size() const
Definition: MapVector.h:60
static std::unique_ptr< MemoryBuffer > getMemBuffer(StringRef InputData, StringRef BufferName="", bool RequiresNullTerminator=true)
Open the specified memory range as a MemoryBuffer.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:251
Class to hold module path string table and global value map, and encapsulate methods for operating on...
bool hasExportedFunctions(const Module &M) const
Check if the given Module has any functions available for exporting in the index.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1878
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:114
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
bool empty() const
Definition: SmallVector.h:81
size_t size() const
Definition: SmallVector.h:78
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:683
void push_back(const T &Elt)
Definition: SmallVector.h:413
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:229
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:44
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Type * getStructElementType(unsigned N) const
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:261
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:264
unsigned getStructNumElements() const
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:258
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:237
const Use & getOperandUse(unsigned i) const
Definition: User.h:241
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:694
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:5304
A raw_ostream that writes to an SmallVector or SmallString.
Definition: raw_ostream.h:691
@ SwiftTail
This follows the Swift calling convention in how arguments are passed but guarantees tail calls will ...
Definition: CallingConv.h:87
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
bool hasStableFunctionMap()
Definition: CodeGenData.h:175
bool emitCGData()
Definition: CodeGenData.h:187
const StableFunctionMap * getStableFunctionMap()
Definition: CodeGenData.h:183
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1697
ModulePass * createGlobalMergeFuncPass()
This pass performs merging similar functions globally.
FunctionHashInfo StructuralHashWithDifferences(const Function &F, IgnoreOperandFunc IgnoreOp)
Computes a structural hash of a given function, considering the structure and content of the function...
std::pair< unsigned, unsigned > IndexPair
The pair of an instruction index and a operand index.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
StringRef get_stable_name(StringRef Name)
Definition: StableHashing.h:55
@ Global
Append to llvm.global_dtors.
void initializeGlobalMergeFuncPassWrapperPass(PassRegistry &)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1873
void embedBufferInModule(Module &M, MemoryBufferRef Buf, StringRef SectionName, Align Alignment=Align(1))
Embed the memory buffer Buf into the module M as a global using the specified section name.
std::string getCodeGenDataSectionName(CGDataSectKind CGSK, Triple::ObjectFormatType OF, bool AddSegmentInfo=true)
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
Tuple to hold function info to process merging.
FuncMergeInfo(StableFunctionMap::StableFunctionEntry *SF, Function *F, IndexInstrMap *IndexInstruction)
StableFunctionMap::StableFunctionEntry * SF
IndexInstrMap * IndexInstruction
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
PreservedAnalyses run(Module &M, AnalysisManager< Module > &)
const ModuleSummaryIndex * ImportSummary
static void serialize(raw_ostream &OS, const StableFunctionMap *FunctionMap)
A static helper function to serialize the stable function map without owning the stable function map.
An efficient form of StableFunction for fast look-up.
std::unique_ptr< IndexOperandHashMapType > IndexOperandHashMap
A map from an IndexPair to a stable_hash which was skipped.
unsigned InstCount
The number of instructions.
const HashFuncsMapType & getFunctionMap() const
Get the HashToFuncs map for serialization.
A stable function is a function with a stable hash while tracking the locations of ignored operands a...