23#define DEBUG_TYPE "global-merge-func"
30 cl::desc(
"Disable codegen data for function merging. Local "
31 "merging is still enabled within a module."),
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");
49 ? dyn_cast_or_null<Function>(
53 if (Callee->isIntrinsic())
55 auto Name = Callee->getName();
57 if (
Name.starts_with(
"objc_msgSend$"))
60 if (
Name.starts_with(
"__dtrace"))
80 if (
F->isDeclaration())
83 if (
F->hasFnAttribute(llvm::Attribute::NoMerge) ||
84 F->hasFnAttribute(llvm::Attribute::AlwaysInline))
87 if (
F->hasAvailableExternallyLinkage())
90 if (
F->getFunctionType()->isVarArg())
102 const auto *CB = dyn_cast<CallBase>(&
I);
103 if (CB && CB->isMustTailCall())
112 switch (
I->getOpcode()) {
113 case Instruction::Load:
114 case Instruction::Store:
115 case Instruction::Call:
116 case Instruction::Invoke:
128 if (OpIdx >=
I->getNumOperands())
134 if (!isa<Constant>(
I->getOperand(OpIdx)))
137 if (
const auto *CI = dyn_cast<CallBase>(
I))
144 Type *SrcTy = V->getType();
159 if (
auto *SrcAT = dyn_cast<ArrayType>(SrcTy)) {
160 auto *DestAT = dyn_cast<ArrayType>(DestTy);
162 assert(SrcAT->getNumElements() == DestAT->getNumElements());
164 for (
unsigned int I = 0, E = SrcAT->getNumElements();
I < E; ++
I) {
167 DestAT->getElementType());
184 ++NumAnalyzedFunctions;
186 ++NumEligibleFunctions;
193 for (
auto &Pair : *FI.IndexOperandHashMap)
197 M.getModuleIdentifier(), FI.IndexInstruction->size(),
198 std::move(IndexOperandHashes));
200 LocalFunctionMap->insert(SF);
212 : SF(SF),
F(
F), IndexInstruction(
std::
move(IndexInstruction)) {}
223 auto *MergedFunc = FI.
F;
224 std::string NewFunctionName =
226 auto *M = MergedFunc->getParent();
227 assert(!M->getFunction(NewFunctionName));
233 ParamTypes.
append(ConstParamTypes.
begin(), ConstParamTypes.
end());
240 if (
auto *SP = MergedFunc->getSubprogram())
246 NewFunction->
addFnAttr(Attribute::NoInline);
249 M->getFunctionList().insert(MergedFunc->getIterator(), NewFunction);
252 NewFunction->
splice(NewFunction->
begin(), MergedFunc);
255 auto NewArgIter = NewFunction->
arg_begin();
256 for (
Argument &OrigArg : MergedFunc->args()) {
262 unsigned NumOrigArgs = MergedFunc->arg_size();
263 for (
unsigned ParamIdx = 0; ParamIdx < ParamLocsVec.
size(); ++ParamIdx) {
265 for (
auto [InstIndex, OpndIndex] : ParamLocsVec[ParamIdx]) {
267 auto *OrigC = Inst->getOperand(OpndIndex);
268 if (OrigC->getType() != NewArg->
getType()) {
269 IRBuilder<> Builder(Inst->getParent(), Inst->getIterator());
270 Inst->setOperand(OpndIndex,
273 Inst->setOperand(OpndIndex, NewArg);
289 Thunk->dropAllReferences();
295 unsigned ParamIdx = 0;
299 for (
Argument &AI : Thunk->args()) {
300 Args.push_back(
createCast(Builder, &AI, ToFuncTy->getParamType(ParamIdx)));
305 for (
auto *Param : Params) {
306 assert(ParamIdx < ToFuncTy->getNumParams());
308 createCast(Builder, Param, ToFuncTy->getParamType(ParamIdx)));
319 if (Thunk->getReturnType()->isVoidTy())
342 for (
const auto &[Index, OldHash] : OldInstOpndIndexToConstHash) {
343 auto It = CurrInstOpndIndexToConstHash.
find(Index);
344 if (It == CurrInstOpndIndexToConstHash.
end())
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)
364 std::optional<stable_hash> OldHash;
365 std::optional<Constant *> OldConst;
369 auto [InstIndex, OpndIndex] = Loc;
371 const auto *Inst = IndexInstruction.
lookup(InstIndex);
372 auto *CurrConst = cast<Constant>(Inst->getOperand(OpndIndex));
375 OldConst = CurrConst;
376 }
else if (CurrConst != *OldConst || CurrHash != *OldHash) {
385 const SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>>
387 std::map<std::vector<stable_hash>,
ParamLocs> HashSeqToLocs;
389 unsigned StableFunctionCount = SFS.
size();
391 for (
auto &[
IndexPair, Hash] : *RSF.IndexOperandHashMap) {
395 std::vector<stable_hash> ConstHashSeq;
396 ConstHashSeq.push_back(Hash);
397 bool Identical =
true;
398 for (
unsigned J = 1; J < StableFunctionCount; ++J) {
400 auto SHash = SF->IndexOperandHashMap->at(
IndexPair);
403 ConstHashSeq.push_back(SHash);
410 HashSeqToLocs[ConstHashSeq].push_back(
IndexPair);
414 for (
auto &[HashSeq, Locs] : HashSeqToLocs)
425 bool Changed =
false;
435 if (Maps.contains(FI.FunctionHash))
436 HashToFuncs[FI.FunctionHash].emplace_back(&
F, std::move(FI));
439 for (
auto &[Hash, Funcs] : HashToFuncs) {
440 std::optional<ParamLocsVecTy> ParamLocsVec;
442 auto &SFS = Maps.at(Hash);
447 for (
auto &[
F, FI] : Funcs) {
450 if (RFS->InstCount != FI.IndexInstruction->size())
456 auto [InstIndex, OpndIndex] = Index;
457 assert(InstIndex < FHI.IndexInstruction->
size());
458 auto *Inst = FHI.IndexInstruction->lookup(InstIndex);
464 if (!hasValidSharedConst(RFS.get(), FI))
467 for (
auto &SF : SFS) {
469 assert(hasValidSharedConst(SF.get(), FI));
473 *FI.IndexOperandHashMap))
475 if (!ParamLocsVec.has_value()) {
478 <<
" with Params " << ParamLocsVec->size() <<
"\n");
486 FuncMergeInfos.
emplace_back(SF.get(),
F, FI.IndexInstruction.get());
490 unsigned FuncMergeInfoSize = FuncMergeInfos.
size();
491 if (FuncMergeInfoSize == 0)
495 << FuncMergeInfoSize <<
" for hash: " << Hash <<
"\n");
497 for (
auto &FMI : FuncMergeInfos) {
506 auto &[InstIndex, OpndIndex] =
ParamLocs[0];
507 auto *Inst = FMI.IndexInstruction->lookup(InstIndex);
508 auto *Opnd = cast<Constant>(Inst->getOperand(OpndIndex));
518 dbgs() <<
"[GlobalMergeFunc] Merged function (hash:" << FMI.SF->Hash
519 <<
") " << MergedFunc->
getName() <<
" generated from "
520 << FMI.F->getName() <<
":\n";
528 dbgs() <<
"[GlobalMergeFunc] Thunk generated: \n";
531 ++NumMergedFunctions;
540 LocalFunctionMap = std::make_unique<StableFunctionMap>();
552 MergerMode = HashFunctionMode::BuildingHashFuncion;
554 MergerMode = HashFunctionMode::UsingHashFunction;
558 LLVM_DEBUG(
dbgs() <<
"Emit function map. Size: " << LocalFunctionMap->size()
561 if (LocalFunctionMap->empty())
569 OS.str(),
"in-memory stable function map",
false);
571 Triple TT(M.getTargetTriple());
581 if (MergerMode == HashFunctionMode::UsingHashFunction) {
588 if (MergerMode == HashFunctionMode::BuildingHashFuncion)
590 LocalFunctionMap->finalize();
591 FuncMap = LocalFunctionMap.get();
594 return merge(M, FuncMap);
599class GlobalMergeFuncPassWrapper :
public ModulePass {
604 GlobalMergeFuncPassWrapper();
609 ModulePass::getAnalysisUsage(AU);
612 StringRef getPassName()
const override {
return "Global Merge Functions"; }
614 bool runOnModule(
Module &M)
override;
619char GlobalMergeFuncPassWrapper::ID = 0;
621 "Global merge function pass",
false,
false)
627 return new GlobalMergeFuncPassWrapper();
631GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() :
ModulePass(
ID) {
636bool GlobalMergeFuncPassWrapper::runOnModule(
Module &M) {
638 if (
auto *IndexWrapperPass =
639 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
640 Index = IndexWrapperPass->getIndex();
Performs the initial survey of the specified function
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)
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)
This is the interface to build a ModuleSummaryIndex for a module.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
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 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).
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Value * CreateIntToPtr(Value *V, Type *DestTy, const Twine &Name="")
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
ReturnInst * CreateRetVoid()
Create a 'ret void' instruction.
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
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 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.
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.
The instances of the Type class are immutable: once they are created, they are never changed.
Type * getStructElementType(unsigned N) const
bool isArrayTy() const
True if this is an instance of ArrayType.
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getStructNumElements() const
bool isStructTy() const
True if this is an instance of StructType.
bool isIntegerTy() const
True if this is an instance of IntegerType.
const Use & getOperandUse(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
StringRef getName() const
Return a constant reference to the value's name.
void dump() const
Support for debugging, callable in GDB: V->dump()
A raw_ostream that writes to an SmallVector or SmallString.
@ SwiftTail
This follows the Swift calling convention in how arguments are passed but guarantees tail calls will ...
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
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.
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)
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.
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.
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.
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 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...