25#define DEBUG_TYPE "global-merge-func"
32 cl::desc(
"Disable codegen data for function merging. Local "
33 "merging is still enabled within a module."),
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");
51 ? dyn_cast_or_null<Function>(
55 if (Callee->isIntrinsic())
57 auto Name = Callee->getName();
59 if (
Name.starts_with(
"objc_msgSend$"))
62 if (
Name.starts_with(
"__dtrace"))
82 if (
F->isDeclaration())
85 if (
F->hasFnAttribute(llvm::Attribute::NoMerge) ||
86 F->hasFnAttribute(llvm::Attribute::AlwaysInline))
89 if (
F->hasAvailableExternallyLinkage())
92 if (
F->getFunctionType()->isVarArg())
108 const auto *CB = dyn_cast<CallBase>(&
I);
109 if (CB && CB->isMustTailCall())
118 switch (
I->getOpcode()) {
119 case Instruction::Load:
120 case Instruction::Store:
121 case Instruction::Call:
122 case Instruction::Invoke:
134 if (
OpIdx >=
I->getNumOperands())
140 if (!isa<Constant>(
I->getOperand(
OpIdx)))
143 if (
const auto *CI = dyn_cast<CallBase>(
I))
152 ++NumAnalyzedFunctions;
154 ++NumEligibleFunctions;
161 for (
auto &Pair : *FI.IndexOperandHashMap)
165 M.getModuleIdentifier(), FI.IndexInstruction->size(),
166 std::move(IndexOperandHashes));
168 LocalFunctionMap->insert(SF);
180 : SF(SF),
F(
F), IndexInstruction(
std::
move(IndexInstruction)) {}
191 auto *MergedFunc = FI.
F;
192 std::string NewFunctionName =
194 auto *M = MergedFunc->getParent();
195 assert(!M->getFunction(NewFunctionName));
201 ParamTypes.
append(ConstParamTypes.
begin(), ConstParamTypes.
end());
208 if (
auto *SP = MergedFunc->getSubprogram())
214 NewFunction->
addFnAttr(Attribute::NoInline);
217 M->getFunctionList().insert(MergedFunc->getIterator(), NewFunction);
220 NewFunction->
splice(NewFunction->
begin(), MergedFunc);
223 auto NewArgIter = NewFunction->
arg_begin();
224 for (
Argument &OrigArg : MergedFunc->args()) {
230 unsigned NumOrigArgs = MergedFunc->arg_size();
231 for (
unsigned ParamIdx = 0; ParamIdx < ParamLocsVec.
size(); ++ParamIdx) {
233 for (
auto [InstIndex, OpndIndex] : ParamLocsVec[ParamIdx]) {
235 auto *OrigC = Inst->getOperand(OpndIndex);
236 if (OrigC->getType() != NewArg->
getType()) {
237 IRBuilder<> Builder(Inst->getParent(), Inst->getIterator());
238 Inst->setOperand(OpndIndex,
241 Inst->setOperand(OpndIndex, NewArg);
257 Thunk->dropAllReferences();
263 unsigned ParamIdx = 0;
267 for (
Argument &AI : Thunk->args()) {
274 for (
auto *Param : Params) {
275 assert(ParamIdx < ToFuncTy->getNumParams());
288 if (Thunk->getReturnType()->isVoidTy())
311 for (
const auto &[Index, OldHash] : OldInstOpndIndexToConstHash) {
312 auto It = CurrInstOpndIndexToConstHash.
find(Index);
313 if (It == CurrInstOpndIndexToConstHash.
end())
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)
333 std::optional<stable_hash> OldHash;
334 std::optional<Constant *> OldConst;
338 auto [InstIndex, OpndIndex] = Loc;
340 const auto *Inst = IndexInstruction.
lookup(InstIndex);
341 auto *CurrConst = cast<Constant>(Inst->getOperand(OpndIndex));
344 OldConst = CurrConst;
345 }
else if (CurrConst != *OldConst || CurrHash != *OldHash) {
355 std::map<std::vector<stable_hash>,
ParamLocs> HashSeqToLocs;
357 unsigned StableFunctionCount = SFS.
size();
359 for (
auto &[
IndexPair, Hash] : *RSF.IndexOperandHashMap) {
363 std::vector<stable_hash> ConstHashSeq;
364 ConstHashSeq.push_back(Hash);
365 bool Identical =
true;
366 for (
unsigned J = 1; J < StableFunctionCount; ++J) {
368 auto SHash = SF->IndexOperandHashMap->at(
IndexPair);
371 ConstHashSeq.push_back(SHash);
378 HashSeqToLocs[ConstHashSeq].push_back(
IndexPair);
382 for (
auto &[HashSeq, Locs] : HashSeqToLocs)
393 bool Changed =
false;
402 if (FunctionMap->
contains(FI.FunctionHash))
403 HashToFuncs[FI.FunctionHash].emplace_back(&
F, std::move(FI));
406 for (
auto &[Hash, Funcs] : HashToFuncs) {
407 std::optional<ParamLocsVecTy> ParamLocsVec;
409 auto &SFS = FunctionMap->
at(Hash);
414 for (
auto &[
F, FI] : Funcs) {
417 if (RFS->InstCount != FI.IndexInstruction->size())
423 auto [InstIndex, OpndIndex] = Index;
424 assert(InstIndex < FHI.IndexInstruction->
size());
425 auto *Inst = FHI.IndexInstruction->lookup(InstIndex);
431 if (!hasValidSharedConst(RFS.get(), FI))
434 for (
auto &SF : SFS) {
436 assert(hasValidSharedConst(SF.get(), FI));
440 *FI.IndexOperandHashMap))
442 if (!ParamLocsVec.has_value()) {
445 <<
" with Params " << ParamLocsVec->size() <<
"\n");
453 FuncMergeInfos.
emplace_back(SF.get(),
F, FI.IndexInstruction.get());
457 unsigned FuncMergeInfoSize = FuncMergeInfos.
size();
458 if (FuncMergeInfoSize == 0)
462 << FuncMergeInfoSize <<
" for hash: " << Hash <<
"\n");
464 for (
auto &FMI : FuncMergeInfos) {
473 auto &[InstIndex, OpndIndex] =
ParamLocs[0];
474 auto *Inst = FMI.IndexInstruction->lookup(InstIndex);
475 auto *Opnd = cast<Constant>(Inst->getOperand(OpndIndex));
485 dbgs() <<
"[GlobalMergeFunc] Merged function (hash:" << FMI.SF->Hash
486 <<
") " << MergedFunc->
getName() <<
" generated from "
487 << FMI.F->getName() <<
":\n";
495 dbgs() <<
"[GlobalMergeFunc] Thunk generated: \n";
498 ++NumMergedFunctions;
507 LocalFunctionMap = std::make_unique<StableFunctionMap>();
519 MergerMode = HashFunctionMode::BuildingHashFuncion;
521 MergerMode = HashFunctionMode::UsingHashFunction;
525 LLVM_DEBUG(
dbgs() <<
"Emit function map. Size: " << LocalFunctionMap->size()
528 if (LocalFunctionMap->empty())
533 std::vector<CGDataPatchItem> PatchItems;
536 COS.
patch(PatchItems);
539 OS.str(),
"in-memory stable function map",
false);
541 Triple TT(M.getTargetTriple());
551 if (MergerMode == HashFunctionMode::UsingHashFunction) {
558 if (MergerMode == HashFunctionMode::BuildingHashFuncion)
560 LocalFunctionMap->finalize();
561 FuncMap = LocalFunctionMap.get();
564 return merge(M, FuncMap);
569class GlobalMergeFuncPassWrapper :
public ModulePass {
574 GlobalMergeFuncPassWrapper();
579 ModulePass::getAnalysisUsage(AU);
582 StringRef getPassName()
const override {
return "Global Merge Functions"; }
584 bool runOnModule(
Module &M)
override;
589char GlobalMergeFuncPassWrapper::ID = 0;
591 "Global merge function pass",
false,
false)
597 return new GlobalMergeFuncPassWrapper();
601GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() :
ModulePass(
ID) {
606bool GlobalMergeFuncPassWrapper::runOnModule(
Module &M) {
608 if (
auto *IndexWrapperPass =
609 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
610 Index = IndexWrapperPass->getIndex();
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Performs the initial survey of the specified function
static bool checkConstHashCompatible(const DenseMap< IndexPair, stable_hash > &OldInstOpndIndexToConstHash, const DenseMap< IndexPair, stable_hash > &CurrInstOpndIndexToConstHash)
static ParamLocsVecTy computeParamInfo(const StableFunctionMap::StableFunctionEntries &SFS)
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 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)
This is the interface to build a ModuleSummaryIndex for a module.
MachineInstr unsigned OpIdx
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A container for analyses that lazily runs them and caches their results.
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.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
LLVM Basic Block Representation.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
A wrapper class to abstract writer stream with support of bytes back patching.
LLVM_ABI void patch(ArrayRef< CGDataPatchItem > P)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
bool isInlineAsm() const
Check if this call is an inline asm statement.
void setCallingConv(CallingConv::ID CC)
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.
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Value * getCalledOperand() const
const Use & getCalledOperandUse() const
void setAttributes(AttributeList A)
Set the attributes for this call.
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)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
static LLVM_ABI 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.
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
void splice(Function::iterator ToIt, Function *FromF)
Transfer all blocks from FromF to this function at ToIt.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
CallingConv::ID getCallingConv() const
getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...
AttributeList getAttributes() const
Return the attribute list for this Function.
Argument * getArg(unsigned i) const
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
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)
void setLinkage(LinkageTypes LT)
@ InternalLinkage
Rename collisions when linking (static functions).
LLVM_ABI Value * CreateAggregateCast(Value *V, Type *DestTy)
Cast between aggregate types that must have identical structure but may differ in their leaf types.
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
ReturnInst * CreateRetVoid()
Create a 'ret void' instruction.
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args={}, const Twine &Name="", MDNode *FPMathTag=nullptr)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Legacy wrapper pass to provide the ModuleSummaryIndex object.
@ OB_clang_arc_attachedcall
This class implements a map that also provides access to all stored values in a deterministic order.
ValueT lookup(const KeyT &Key) const
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...
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.
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
reference emplace_back(ArgTypes &&... Args)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
StringRef - Represent a constant reference to a string, i.e.
std::string str() const
str - Get the contents as an std::string.
Triple - Helper class for working with autoconf configuration names.
const Use & getOperandUse(unsigned i) const
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void dump() const
Support for debugging, callable in GDB: V->dump()
A raw_ostream that writes to an SmallVector or SmallString.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ SwiftTail
This follows the Swift calling convention in how arguments are passed but guarantees tail calls will ...
bool hasStableFunctionMap()
const StableFunctionMap * getStableFunctionMap()
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
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.
LLVM_ABI ModulePass * createGlobalMergeFuncPass()
This pass performs merging similar functions globally.
LLVM_ABI 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)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
StringRef get_stable_name(StringRef Name)
@ Global
Append to llvm.global_dtors.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI std::string getCodeGenDataSectionName(CGDataSectKind CGSK, Triple::ObjectFormatType OF, bool AddSegmentInfo=true)
Implement std::hash so that hash_code can be used in STL containers.
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.
PreservedAnalyses run(Module &M, AnalysisManager< Module > &)
const ModuleSummaryIndex * ImportSummary
static LLVM_ABI void serialize(raw_ostream &OS, const StableFunctionMap *FunctionMap, std::vector< CGDataPatchItem > &PatchItems)
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 StableFunctionEntries & at(HashFuncsMapType::key_type FunctionHash) const
bool contains(HashFuncsMapType::key_type FunctionHash) const
A stable function is a function with a stable hash while tracking the locations of ignored operands a...