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"))
74 if (
F->isDeclaration())
77 if (
F->hasFnAttribute(llvm::Attribute::NoMerge) ||
78 F->hasFnAttribute(llvm::Attribute::AlwaysInline))
81 if (
F->hasAvailableExternallyLinkage())
84 if (
F->getFunctionType()->isVarArg())
96 const auto *CB = dyn_cast<CallBase>(&
I);
97 if (CB && CB->isMustTailCall())
106 switch (
I->getOpcode()) {
107 case Instruction::Load:
108 case Instruction::Store:
109 case Instruction::Call:
110 case Instruction::Invoke:
122 if (OpIdx >=
I->getNumOperands())
128 if (!isa<Constant>(
I->getOperand(OpIdx)))
131 if (
const auto *CI = dyn_cast<CallBase>(
I))
138 Type *SrcTy = V->getType();
153 if (
auto *SrcAT = dyn_cast<ArrayType>(SrcTy)) {
154 auto *DestAT = dyn_cast<ArrayType>(DestTy);
156 assert(SrcAT->getNumElements() == DestAT->getNumElements());
158 for (
unsigned int I = 0, E = SrcAT->getNumElements();
I < E; ++
I) {
161 DestAT->getElementType());
178 ++NumAnalyzedFunctions;
180 ++NumEligibleFunctions;
187 for (
auto &Pair : *FI.IndexOperandHashMap)
191 M.getModuleIdentifier(), FI.IndexInstruction->size(),
192 std::move(IndexOperandHashes));
194 LocalFunctionMap->insert(SF);
206 : SF(SF),
F(
F), IndexInstruction(
std::
move(IndexInstruction)) {}
217 auto *MergedFunc = FI.
F;
218 std::string NewFunctionName =
220 auto *M = MergedFunc->getParent();
221 assert(!M->getFunction(NewFunctionName));
227 ParamTypes.
append(ConstParamTypes.
begin(), ConstParamTypes.
end());
234 if (
auto *SP = MergedFunc->getSubprogram())
240 NewFunction->
addFnAttr(Attribute::NoInline);
243 M->getFunctionList().insert(MergedFunc->getIterator(), NewFunction);
246 NewFunction->
splice(NewFunction->
begin(), MergedFunc);
249 auto NewArgIter = NewFunction->
arg_begin();
250 for (
Argument &OrigArg : MergedFunc->args()) {
256 unsigned NumOrigArgs = MergedFunc->arg_size();
257 for (
unsigned ParamIdx = 0; ParamIdx < ParamLocsVec.
size(); ++ParamIdx) {
259 for (
auto [InstIndex, OpndIndex] : ParamLocsVec[ParamIdx]) {
261 auto *OrigC = Inst->getOperand(OpndIndex);
262 if (OrigC->getType() != NewArg->
getType()) {
263 IRBuilder<> Builder(Inst->getParent(), Inst->getIterator());
264 Inst->setOperand(OpndIndex,
267 Inst->setOperand(OpndIndex, NewArg);
283 Thunk->dropAllReferences();
289 unsigned ParamIdx = 0;
293 for (
Argument &AI : Thunk->args()) {
294 Args.push_back(
createCast(Builder, &AI, ToFuncTy->getParamType(ParamIdx)));
299 for (
auto *Param : Params) {
300 assert(ParamIdx < ToFuncTy->getNumParams());
302 createCast(Builder, Param, ToFuncTy->getParamType(ParamIdx)));
313 if (Thunk->getReturnType()->isVoidTy())
336 for (
const auto &[Index, OldHash] : OldInstOpndIndexToConstHash) {
337 auto It = CurrInstOpndIndexToConstHash.
find(Index);
338 if (It == CurrInstOpndIndexToConstHash.
end())
341 auto CurrHash = It->second;
342 auto J = OldHashToCurrHash.
find(OldHash);
343 if (J == OldHashToCurrHash.
end())
344 OldHashToCurrHash.
insert({OldHash, CurrHash});
345 else if (J->second != CurrHash)
358 std::optional<stable_hash> OldHash;
359 std::optional<Constant *> OldConst;
363 auto [InstIndex, OpndIndex] = Loc;
365 const auto *Inst = IndexInstruction.
lookup(InstIndex);
366 auto *CurrConst = cast<Constant>(Inst->getOperand(OpndIndex));
369 OldConst = CurrConst;
370 }
else if (CurrConst != *OldConst || CurrHash != *OldHash) {
379 const SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>>
381 std::map<std::vector<stable_hash>,
ParamLocs> HashSeqToLocs;
383 unsigned StableFunctionCount = SFS.
size();
385 for (
auto &[
IndexPair, Hash] : *RSF.IndexOperandHashMap) {
389 std::vector<stable_hash> ConstHashSeq;
390 ConstHashSeq.push_back(Hash);
391 bool Identical =
true;
392 for (
unsigned J = 1; J < StableFunctionCount; ++J) {
394 auto SHash = SF->IndexOperandHashMap->at(
IndexPair);
397 ConstHashSeq.push_back(SHash);
404 HashSeqToLocs[ConstHashSeq].push_back(
IndexPair);
408 for (
auto &[HashSeq, Locs] : HashSeqToLocs)
419 bool Changed =
false;
429 if (Maps.contains(FI.FunctionHash))
430 HashToFuncs[FI.FunctionHash].emplace_back(&
F, std::move(FI));
433 for (
auto &[Hash, Funcs] : HashToFuncs) {
434 std::optional<ParamLocsVecTy> ParamLocsVec;
436 auto &SFS = Maps.at(Hash);
441 for (
auto &[
F, FI] : Funcs) {
444 if (RFS->InstCount != FI.IndexInstruction->size())
450 auto [InstIndex, OpndIndex] = Index;
451 assert(InstIndex < FHI.IndexInstruction->
size());
452 auto *Inst = FHI.IndexInstruction->lookup(InstIndex);
458 if (!hasValidSharedConst(RFS.get(), FI))
461 for (
auto &SF : SFS) {
463 assert(hasValidSharedConst(SF.get(), FI));
467 *FI.IndexOperandHashMap))
469 if (!ParamLocsVec.has_value()) {
472 <<
" with Params " << ParamLocsVec->size() <<
"\n");
480 FuncMergeInfos.
emplace_back(SF.get(),
F, FI.IndexInstruction.get());
484 unsigned FuncMergeInfoSize = FuncMergeInfos.
size();
485 if (FuncMergeInfoSize == 0)
489 << FuncMergeInfoSize <<
" for hash: " << Hash <<
"\n");
491 for (
auto &FMI : FuncMergeInfos) {
500 auto &[InstIndex, OpndIndex] =
ParamLocs[0];
501 auto *Inst = FMI.IndexInstruction->lookup(InstIndex);
502 auto *Opnd = cast<Constant>(Inst->getOperand(OpndIndex));
512 dbgs() <<
"[GlobalMergeFunc] Merged function (hash:" << FMI.SF->Hash
513 <<
") " << MergedFunc->
getName() <<
" generated from "
514 << FMI.F->getName() <<
":\n";
522 dbgs() <<
"[GlobalMergeFunc] Thunk generated: \n";
525 ++NumMergedFunctions;
534 LocalFunctionMap = std::make_unique<StableFunctionMap>();
546 MergerMode = HashFunctionMode::BuildingHashFuncion;
548 MergerMode = HashFunctionMode::UsingHashFunction;
552 LLVM_DEBUG(
dbgs() <<
"Emit function map. Size: " << LocalFunctionMap->size()
555 if (LocalFunctionMap->empty())
563 OS.str(),
"in-memory stable function map",
false);
565 Triple TT(M.getTargetTriple());
575 if (MergerMode == HashFunctionMode::UsingHashFunction) {
582 if (MergerMode == HashFunctionMode::BuildingHashFuncion)
584 LocalFunctionMap->finalize();
585 FuncMap = LocalFunctionMap.get();
588 return merge(M, FuncMap);
593class GlobalMergeFuncPassWrapper :
public ModulePass {
598 GlobalMergeFuncPassWrapper();
603 ModulePass::getAnalysisUsage(AU);
606 StringRef getPassName()
const override {
return "Global Merge Functions"; }
608 bool runOnModule(
Module &M)
override;
613char GlobalMergeFuncPassWrapper::ID = 0;
615 "Global merge function pass",
false,
false)
621 return new GlobalMergeFuncPassWrapper();
625GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() :
ModulePass(
ID) {
630bool GlobalMergeFuncPassWrapper::runOnModule(
Module &M) {
632 if (
auto *IndexWrapperPass =
633 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
634 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)
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.
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...