132#define DEBUG_TYPE "mergefunc"
134STATISTIC(NumFunctionsMerged,
"Number of functions merged");
135STATISTIC(NumThunksWritten,
"Number of thunks generated");
136STATISTIC(NumAliasesWritten,
"Number of aliases generated");
137STATISTIC(NumDoubleWeak,
"Number of new functions created");
141 cl::desc(
"How many functions in a module could be used for "
142 "MergeFunctions to pass a basic correctness check. "
143 "'0' disables this check. Works only with '-debug' key."),
163 cl::desc(
"Preserve debug info in thunk when mergefunc "
164 "transformations are made."));
169 cl::desc(
"Allow mergefunc to create aliases"));
182 IRHash getHash()
const {
return Hash; }
195class MergeFunctions {
197 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {
200 bool runOnModule(
Module &M);
205 class FunctionNodeCmp {
211 bool operator()(
const FunctionNode &LHS,
const FunctionNode &RHS)
const {
213 if (
LHS.getHash() !=
RHS.getHash())
214 return LHS.getHash() <
RHS.getHash();
216 return FCmp.compare() < 0;
219 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
225 std::vector<WeakTrackingVH> Deferred;
233 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist);
246 void removeUsers(
Value *V);
259 void filterInstsUnrelatedToPDI(
BasicBlock *GEntryBlock,
260 std::vector<Instruction *> &PDIUnrelatedWL);
267 void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
282 void replaceFunctionInTree(
const FunctionNode &FN,
Function *
G);
300 if (!MF.runOnModule(M))
306bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) {
308 unsigned TripleNumber = 0;
311 dbgs() <<
"MERGEFUNC-VERIFY: Started for first " << Max <<
" functions.\n";
314 for (std::vector<WeakTrackingVH>::iterator
I = Worklist.begin(),
316 I !=
E && i < Max; ++
I, ++i) {
318 for (std::vector<WeakTrackingVH>::iterator J =
I; J !=
E && j < Max;
327 dbgs() <<
"MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber
329 dbgs() << *F1 <<
'\n' << *F2 <<
'\n';
337 for (std::vector<WeakTrackingVH>::iterator K = J; K !=
E && k < Max;
338 ++k, ++K, ++TripleNumber) {
346 bool Transitive =
true;
348 if (Res1 != 0 && Res1 == Res4) {
350 Transitive = Res3 == Res1;
351 }
else if (Res3 != 0 && Res3 == -Res4) {
353 Transitive = Res3 == Res1;
354 }
else if (Res4 != 0 && -Res3 == Res4) {
356 Transitive = Res4 == -Res1;
360 dbgs() <<
"MERGEFUNC-VERIFY: Non-transitive; triple: "
361 << TripleNumber <<
"\n";
362 dbgs() <<
"Res1, Res3, Res4: " << Res1 <<
", " << Res3 <<
", "
364 dbgs() << *F1 <<
'\n' << *F2 <<
'\n' << *F3 <<
'\n';
371 dbgs() <<
"MERGEFUNC-VERIFY: " << (Valid ?
"Passed." :
"Failed.") <<
"\n";
383 for (
const Instruction &
I : BB.instructionsWithoutDebug()) {
384 if (!isa<IntrinsicInst>(&
I))
388 auto *MDL = dyn_cast<MetadataAsValue>(
Op);
391 if (
MDNode *
N = dyn_cast<MDNode>(MDL->getMetadata()))
402 return !
F.isDeclaration() && !
F.hasAvailableExternallyLinkage() &&
406bool MergeFunctions::runOnModule(
Module &M) {
407 bool Changed =
false;
416 std::vector<std::pair<IRHash, Function *>> HashedFuncs;
425 auto S = HashedFuncs.begin();
426 for (
auto I = HashedFuncs.begin(), IE = HashedFuncs.end();
I != IE; ++
I) {
429 if ((
I != S && std::prev(
I)->first ==
I->first) ||
430 (std::next(
I) != IE && std::next(
I)->first ==
I->first) ) {
436 std::vector<WeakTrackingVH> Worklist;
437 Deferred.swap(Worklist);
442 LLVM_DEBUG(
dbgs() <<
"size of worklist: " << Worklist.size() <<
'\n');
449 if (!
F->isDeclaration() && !
F->hasAvailableExternallyLinkage()) {
450 Changed |= insert(
F);
453 LLVM_DEBUG(
dbgs() <<
"size of FnTree: " << FnTree.size() <<
'\n');
454 }
while (!Deferred.empty());
457 FNodesInTree.clear();
458 GlobalNumbers.
clear();
467 CallBase *CB = dyn_cast<CallBase>(
U.getUser());
483 Type *SrcTy = V->getType();
499 return Builder.CreateIntToPtr(V, DestTy);
501 return Builder.CreatePtrToInt(V, DestTy);
503 return Builder.CreateBitCast(V, DestTy);
508void MergeFunctions::eraseInstsUnrelatedToPDI(
509 std::vector<Instruction *> &PDIUnrelatedWL) {
511 dbgs() <<
" Erasing instructions (in reverse order of appearance in "
512 "entry block) unrelated to parameter debug info from entry "
514 while (!PDIUnrelatedWL.empty()) {
519 I->eraseFromParent();
520 PDIUnrelatedWL.pop_back();
522 LLVM_DEBUG(
dbgs() <<
" } // Done erasing instructions unrelated to parameter "
523 "debug info from entry block. \n");
527void MergeFunctions::eraseTail(
Function *
G) {
528 std::vector<BasicBlock *> WorklistBB;
530 BB.dropAllReferences();
531 WorklistBB.push_back(&BB);
533 while (!WorklistBB.empty()) {
549void MergeFunctions::filterInstsUnrelatedToPDI(
550 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
551 std::set<Instruction *> PDIRelated;
554 if (
auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
563 PDIRelated.insert(&*BI);
569 }
else if (
auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
577 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
582 if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
583 if (
Value *Arg =
SI->getValueOperand()) {
584 if (isa<Argument>(Arg)) {
588 PDIRelated.insert(AI);
592 PDIRelated.insert(SI);
596 PDIRelated.insert(&*BI);
619 }
else if (BI->isTerminator() && &*BI == GEntryBlock->
getTerminator()) {
623 PDIRelated.insert(&*BI);
632 <<
" Report parameter debug info related/related instructions: {\n");
634 if (PDIRelated.find(&
I) == PDIRelated.end()) {
638 PDIUnrelatedWL.push_back(&
I);
655 if (
F->size() == 1) {
656 if (
F->front().size() <= 2) {
658 <<
" is too small to bother creating a thunk for\n");
675 std::vector<Instruction *> PDIUnrelatedWL;
679 LLVM_DEBUG(
dbgs() <<
"writeThunk: (MergeFunctionsPDI) Do not create a new "
680 "function as thunk; retain original: "
681 <<
G->getName() <<
"()\n");
682 GEntryBlock = &
G->getEntryBlock();
684 dbgs() <<
"writeThunk: (MergeFunctionsPDI) filter parameter related "
686 <<
G->getName() <<
"() {\n");
687 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
692 G->getAddressSpace(),
"",
G->getParent());
715 if (
H->getReturnType()->isVoidTy()) {
732 dbgs() <<
"writeThunk: (MergeFunctionsPDI) No DISubprogram for "
733 <<
G->getName() <<
"()\n");
736 eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
738 dbgs() <<
"} // End of parameter related debug info filtering for: "
739 <<
G->getName() <<
"()\n");
744 G->replaceAllUsesWith(NewG);
745 G->eraseFromParent();
758 assert(
F->hasLocalLinkage() ||
F->hasExternalLinkage()
759 ||
F->hasWeakLinkage() ||
F->hasLinkOnceLinkage());
767 G->getLinkage(),
"",
F,
G->getParent());
771 if (FAlign || GAlign)
774 F->setAlignment(std::nullopt);
776 GA->setVisibility(
G->getVisibility());
780 G->replaceAllUsesWith(GA);
781 G->eraseFromParent();
803 if (
F->isInterposable()) {
815 F->getAddressSpace(),
"",
F->getParent());
819 F->replaceAllUsesWith(NewF);
826 writeThunkOrAlias(
F,
G);
827 writeThunkOrAlias(
F, NewF);
829 if (NewFAlign || GAlign)
832 F->setAlignment(std::nullopt);
835 ++NumFunctionsMerged;
843 if (
G->hasGlobalUnnamedAddr() && !
Used.contains(
G)) {
849 G->replaceAllUsesWith(
F);
853 replaceDirectCallers(
G,
F);
861 G->eraseFromParent();
862 ++NumFunctionsMerged;
866 if (writeThunkOrAlias(
F,
G)) {
867 ++NumFunctionsMerged;
873void MergeFunctions::replaceFunctionInTree(
const FunctionNode &FN,
877 "The two functions must be equal");
879 auto I = FNodesInTree.find(
F);
880 assert(
I != FNodesInTree.end() &&
"F should be in FNodesInTree");
881 assert(FNodesInTree.count(
G) == 0 &&
"FNodesInTree should not contain G");
883 FnTreeType::iterator IterToFNInFnTree =
I->second;
884 assert(&(*IterToFNInFnTree) == &FN &&
"F should map to FN in FNodesInTree.");
886 FNodesInTree.erase(
I);
887 FNodesInTree.insert({
G, IterToFNInFnTree});
894 if (
F->isInterposable() !=
G->isInterposable()) {
897 return !
F->isInterposable();
899 if (
F->hasLocalLinkage() !=
G->hasLocalLinkage()) {
902 return !
F->hasLocalLinkage();
907 return F->getName() <=
G->getName();
912bool MergeFunctions::insert(
Function *NewFunction) {
913 std::pair<FnTreeType::iterator, bool>
Result =
914 FnTree.insert(FunctionNode(NewFunction));
917 assert(FNodesInTree.count(NewFunction) == 0);
918 FNodesInTree.insert({NewFunction,
Result.first});
924 const FunctionNode &OldF = *
Result.first;
929 replaceFunctionInTree(*
Result.first, NewFunction);
931 assert(OldF.getFunc() !=
F &&
"Must have swapped the functions.");
935 <<
" == " << NewFunction->
getName() <<
'\n');
938 mergeTwoFunctions(OldF.getFunc(), DeleteF);
944void MergeFunctions::remove(
Function *
F) {
945 auto I = FNodesInTree.find(
F);
946 if (
I != FNodesInTree.end()) {
948 FnTree.erase(
I->second);
951 FNodesInTree.erase(
I);
952 Deferred.emplace_back(
F);
958void MergeFunctions::removeUsers(
Value *V) {
959 for (
User *U :
V->users())
960 if (
auto *
I = dyn_cast<Instruction>(U))
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 bool hasDistinctMetadataIntrinsic(const Function &F)
Check whether F has an intrinsic which references distinct metadata as an operand.
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)
This class represents an Operation in the Expression.
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 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)
@ 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)
NodeAddr< FuncNode * > Func
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...
IRHash StructuralHash(const Function &F, bool DetailedHash=false)
Returns a hash of the function F.
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::...