133#define DEBUG_TYPE "mergefunc"
135STATISTIC(NumFunctionsMerged,
"Number of functions merged");
136STATISTIC(NumThunksWritten,
"Number of thunks generated");
137STATISTIC(NumAliasesWritten,
"Number of aliases generated");
138STATISTIC(NumDoubleWeak,
"Number of new functions created");
142 cl::desc(
"How many functions in a module could be used for "
143 "MergeFunctions to pass a basic correctness check. "
144 "'0' disables this check. Works only with '-debug' key."),
164 cl::desc(
"Preserve debug info in thunk when mergefunc "
165 "transformations are made."));
170 cl::desc(
"Allow mergefunc to create aliases"));
197class MergeFunctions {
199 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {
202 bool runOnModule(
Module &M);
207 class FunctionNodeCmp {
213 bool operator()(
const FunctionNode &LHS,
const FunctionNode &RHS)
const {
215 if (
LHS.getHash() !=
RHS.getHash())
216 return LHS.getHash() <
RHS.getHash();
218 return FCmp.compare() < 0;
221 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
227 std::vector<WeakTrackingVH> Deferred;
235 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist);
248 void removeUsers(
Value *V);
261 void filterInstsUnrelatedToPDI(
BasicBlock *GEntryBlock,
262 std::vector<Instruction *> &PDIUnrelatedWL);
269 void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
284 void replaceFunctionInTree(
const FunctionNode &FN,
Function *
G);
302 if (!MF.runOnModule(M))
308bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) {
310 unsigned TripleNumber = 0;
313 dbgs() <<
"MERGEFUNC-VERIFY: Started for first " << Max <<
" functions.\n";
316 for (std::vector<WeakTrackingVH>::iterator
I = Worklist.begin(),
318 I !=
E && i < Max; ++
I, ++i) {
320 for (std::vector<WeakTrackingVH>::iterator J =
I; J !=
E && j < Max;
329 dbgs() <<
"MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber
331 dbgs() << *F1 <<
'\n' << *F2 <<
'\n';
339 for (std::vector<WeakTrackingVH>::iterator K = J; K !=
E && k < Max;
340 ++k, ++K, ++TripleNumber) {
348 bool Transitive =
true;
350 if (Res1 != 0 && Res1 == Res4) {
352 Transitive = Res3 == Res1;
353 }
else if (Res3 != 0 && Res3 == -Res4) {
355 Transitive = Res3 == Res1;
356 }
else if (Res4 != 0 && -Res3 == Res4) {
358 Transitive = Res4 == -Res1;
362 dbgs() <<
"MERGEFUNC-VERIFY: Non-transitive; triple: "
363 << TripleNumber <<
"\n";
364 dbgs() <<
"Res1, Res3, Res4: " << Res1 <<
", " << Res3 <<
", "
366 dbgs() << *F1 <<
'\n' << *F2 <<
'\n' << *F3 <<
'\n';
373 dbgs() <<
"MERGEFUNC-VERIFY: " << (Valid ?
"Passed." :
"Failed.") <<
"\n";
382 return !
F.isDeclaration() && !
F.hasAvailableExternallyLinkage();
385bool MergeFunctions::runOnModule(
Module &M) {
386 bool Changed =
false;
395 std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
405 auto S = HashedFuncs.begin();
406 for (
auto I = HashedFuncs.begin(), IE = HashedFuncs.end();
I != IE; ++
I) {
409 if ((
I != S && std::prev(
I)->first ==
I->first) ||
410 (std::next(
I) != IE && std::next(
I)->first ==
I->first) ) {
416 std::vector<WeakTrackingVH> Worklist;
417 Deferred.swap(Worklist);
422 LLVM_DEBUG(
dbgs() <<
"size of worklist: " << Worklist.size() <<
'\n');
429 if (!
F->isDeclaration() && !
F->hasAvailableExternallyLinkage()) {
430 Changed |= insert(
F);
433 LLVM_DEBUG(
dbgs() <<
"size of FnTree: " << FnTree.size() <<
'\n');
434 }
while (!Deferred.empty());
437 FNodesInTree.clear();
438 GlobalNumbers.
clear();
448 CallBase *CB = dyn_cast<CallBase>(
U.getUser());
464 Type *SrcTy = V->getType();
480 return Builder.CreateIntToPtr(V, DestTy);
482 return Builder.CreatePtrToInt(V, DestTy);
484 return Builder.CreateBitCast(V, DestTy);
489void MergeFunctions::eraseInstsUnrelatedToPDI(
490 std::vector<Instruction *> &PDIUnrelatedWL) {
492 dbgs() <<
" Erasing instructions (in reverse order of appearance in "
493 "entry block) unrelated to parameter debug info from entry "
495 while (!PDIUnrelatedWL.empty()) {
500 I->eraseFromParent();
501 PDIUnrelatedWL.pop_back();
503 LLVM_DEBUG(
dbgs() <<
" } // Done erasing instructions unrelated to parameter "
504 "debug info from entry block. \n");
508void MergeFunctions::eraseTail(
Function *
G) {
509 std::vector<BasicBlock *> WorklistBB;
511 BB.dropAllReferences();
512 WorklistBB.push_back(&BB);
514 while (!WorklistBB.empty()) {
530void MergeFunctions::filterInstsUnrelatedToPDI(
531 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
532 std::set<Instruction *> PDIRelated;
535 if (
auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
544 PDIRelated.insert(&*BI);
550 }
else if (
auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
558 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
563 if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
565 if (isa<Argument>(
Arg)) {
569 PDIRelated.insert(AI);
573 PDIRelated.insert(SI);
577 PDIRelated.insert(&*BI);
600 }
else if (BI->isTerminator() && &*BI == GEntryBlock->
getTerminator()) {
604 PDIRelated.insert(&*BI);
613 <<
" Report parameter debug info related/related instructions: {\n");
615 if (PDIRelated.find(&
I) == PDIRelated.end()) {
619 PDIUnrelatedWL.push_back(&
I);
636 if (
F->size() == 1) {
637 if (
F->front().size() <= 2) {
639 <<
" is too small to bother creating a thunk for\n");
656 std::vector<Instruction *> PDIUnrelatedWL;
660 LLVM_DEBUG(
dbgs() <<
"writeThunk: (MergeFunctionsPDI) Do not create a new "
661 "function as thunk; retain original: "
662 <<
G->getName() <<
"()\n");
663 GEntryBlock = &
G->getEntryBlock();
665 dbgs() <<
"writeThunk: (MergeFunctionsPDI) filter parameter related "
667 <<
G->getName() <<
"() {\n");
668 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
673 G->getAddressSpace(),
"",
G->getParent());
696 if (
H->getReturnType()->isVoidTy()) {
713 dbgs() <<
"writeThunk: (MergeFunctionsPDI) No DISubprogram for "
714 <<
G->getName() <<
"()\n");
717 eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
719 dbgs() <<
"} // End of parameter related debug info filtering for: "
720 <<
G->getName() <<
"()\n");
725 G->replaceAllUsesWith(NewG);
726 G->eraseFromParent();
739 assert(
F->hasLocalLinkage() ||
F->hasExternalLinkage()
740 ||
F->hasWeakLinkage() ||
F->hasLinkOnceLinkage());
749 G->getLinkage(),
"", BitcastF,
G->getParent());
753 if (FAlign || GAlign)
756 F->setAlignment(std::nullopt);
758 GA->setVisibility(
G->getVisibility());
762 G->replaceAllUsesWith(GA);
763 G->eraseFromParent();
785 if (
F->isInterposable()) {
797 F->getAddressSpace(),
"",
F->getParent());
801 F->replaceAllUsesWith(NewF);
808 writeThunkOrAlias(
F,
G);
809 writeThunkOrAlias(
F, NewF);
811 if (NewFAlign || GAlign)
814 F->setAlignment(std::nullopt);
817 ++NumFunctionsMerged;
825 if (
G->hasGlobalUnnamedAddr() && !
Used.contains(
G)) {
832 G->replaceAllUsesWith(BitcastF);
836 replaceDirectCallers(
G,
F);
844 G->eraseFromParent();
845 ++NumFunctionsMerged;
849 if (writeThunkOrAlias(
F,
G)) {
850 ++NumFunctionsMerged;
856void MergeFunctions::replaceFunctionInTree(
const FunctionNode &FN,
860 "The two functions must be equal");
862 auto I = FNodesInTree.find(
F);
863 assert(
I != FNodesInTree.end() &&
"F should be in FNodesInTree");
864 assert(FNodesInTree.count(
G) == 0 &&
"FNodesInTree should not contain G");
866 FnTreeType::iterator IterToFNInFnTree =
I->second;
867 assert(&(*IterToFNInFnTree) == &FN &&
"F should map to FN in FNodesInTree.");
869 FNodesInTree.erase(
I);
870 FNodesInTree.insert({
G, IterToFNInFnTree});
877 if (
F->isInterposable() !=
G->isInterposable()) {
880 return !
F->isInterposable();
882 if (
F->hasLocalLinkage() !=
G->hasLocalLinkage()) {
885 return !
F->hasLocalLinkage();
890 return F->getName() <=
G->getName();
895bool MergeFunctions::insert(
Function *NewFunction) {
896 std::pair<FnTreeType::iterator, bool>
Result =
897 FnTree.insert(FunctionNode(NewFunction));
900 assert(FNodesInTree.count(NewFunction) == 0);
901 FNodesInTree.insert({NewFunction,
Result.first});
907 const FunctionNode &OldF = *
Result.first;
912 replaceFunctionInTree(*
Result.first, NewFunction);
914 assert(OldF.getFunc() !=
F &&
"Must have swapped the functions.");
918 <<
" == " << NewFunction->
getName() <<
'\n');
921 mergeTwoFunctions(OldF.getFunc(), DeleteF);
927void MergeFunctions::remove(
Function *
F) {
928 auto I = FNodesInTree.find(
F);
929 if (
I != FNodesInTree.end()) {
931 FnTree.erase(
I->second);
934 FNodesInTree.erase(
I);
935 Deferred.emplace_back(
F);
941void MergeFunctions::removeUsers(
Value *V) {
942 for (
User *U :
V->users())
943 if (
auto *
I = dyn_cast<Instruction>(U))
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool canCreateAliasFor(Function *F)
static bool isEligibleForMerging(Function &F)
Check whether F is eligible for function merging.
static cl::opt< unsigned > NumFunctionsForVerificationCheck("mergefunc-verify", cl::desc("How many functions in a module could be used for " "MergeFunctions to pass a basic correctness check. " "'0' disables this check. Works only with '-debug' key."), cl::init(0), cl::Hidden)
static bool canCreateThunkFor(Function *F)
Whether this function may be replaced by a forwarding thunk.
static cl::opt< bool > MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden, cl::init(false), cl::desc("Preserve debug info in thunk when mergefunc " "transformations are made."))
static Value * createCast(IRBuilder<> &Builder, Value *V, Type *DestTy)
static cl::opt< bool > MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden, cl::init(false), cl::desc("Allow mergefunc to create aliases"))
static bool isFuncOrderCorrect(const Function *F, const Function *G)
Module.h This file contains the declarations for the Module class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
an instruction to allocate memory on the stack
A container for analyses that lazily runs them and caches their results.
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),...
Value handle that asserts if the Value is deleted.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
const Instruction & back() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void setCallingConv(CallingConv::ID CC)
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
This class represents a function call, abstracting a target machine's calling convention.
void setTailCallKind(TailCallKind TCK)
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is an important base class in LLVM.
FunctionComparator - Compares two functions to determine whether or not they will generate machine co...
int compare()
Test whether the two functions have equivalent behaviour.
static FunctionHash functionHash(Function &)
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
static GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
GlobalNumberState assigns an integer to each global value in the program, which is used by the compar...
void erase(GlobalValue *Global)
MaybeAlign getAlign() const
Returns the alignment of the given variable or function.
void setComdat(Comdat *C)
PointerType * getType() const
Global values are always pointers.
@ PrivateLinkage
Like Internal, but omit from symbol table.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
const Function * getFunction() const
Return the function this instruction belongs to.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
LLVMContext & getContext() const
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
A Module instance is used to store all the information related to an LLVM module.
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.
Return a value (possibly void), from a function.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
The instances of the Type class are immutable: once they are created, they are never changed.
Type * getStructElementType(unsigned N) const
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.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
iterator_range< user_iterator > users()
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
Value handle that is nullable, but tries to track the Value.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ SwiftTail
This follows the Swift calling convention in how arguments are passed but guarantees tail calls will ...
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
initializer< Ty > init(const Ty &Val)
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallVectorImpl< GlobalValue * > &Vec, bool CompilerUsed)
Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Function object to check whether the first component of a container supported by std::get (like std::...