Go to the documentation of this file.
130 using namespace llvm;
132 #define DEBUG_TYPE "mergefunc"
134 STATISTIC(NumFunctionsMerged,
"Number of functions merged");
135 STATISTIC(NumThunksWritten,
"Number of thunks generated");
136 STATISTIC(NumAliasesWritten,
"Number of aliases generated");
137 STATISTIC(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"));
196 class MergeFunctions {
198 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {
201 bool runOnModule(
Module &M);
206 class FunctionNodeCmp {
212 bool operator()(
const FunctionNode &
LHS,
const FunctionNode &
RHS)
const {
214 if (
LHS.getHash() !=
RHS.getHash())
215 return LHS.getHash() <
RHS.getHash();
217 return FCmp.compare() == -1;
220 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
226 std::vector<WeakTrackingVH> Deferred;
231 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist);
244 void removeUsers(
Value *V);
257 void filterInstsUnrelatedToPDI(
BasicBlock *GEntryBlock,
258 std::vector<Instruction *> &PDIUnrelatedWL);
265 void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
280 void replaceFunctionInTree(
const FunctionNode &FN,
Function *
G);
294 class MergeFunctionsLegacyPass :
public ModulePass {
302 bool runOnModule(
Module &M)
override {
307 return MF.runOnModule(M);
315 "Merge Functions",
false,
false)
318 return new MergeFunctionsLegacyPass();
324 if (!MF.runOnModule(
M))
330 bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) {
332 unsigned TripleNumber = 0;
335 dbgs() <<
"MERGEFUNC-VERIFY: Started for first " << Max <<
" functions.\n";
338 for (std::vector<WeakTrackingVH>::iterator
I = Worklist.begin(),
340 I !=
E &&
i < Max; ++
I, ++
i) {
342 for (std::vector<WeakTrackingVH>::iterator J =
I; J !=
E &&
j < Max;
351 dbgs() <<
"MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber
353 dbgs() << *F1 <<
'\n' << *F2 <<
'\n';
361 for (std::vector<WeakTrackingVH>::iterator K = J; K !=
E && k < Max;
362 ++k, ++K, ++TripleNumber) {
370 bool Transitive =
true;
372 if (Res1 != 0 && Res1 == Res4) {
374 Transitive = Res3 == Res1;
375 }
else if (Res3 != 0 && Res3 == -Res4) {
377 Transitive = Res3 == Res1;
378 }
else if (Res4 != 0 && -Res3 == Res4) {
380 Transitive = Res4 == -Res1;
384 dbgs() <<
"MERGEFUNC-VERIFY: Non-transitive; triple: "
385 << TripleNumber <<
"\n";
386 dbgs() <<
"Res1, Res3, Res4: " << Res1 <<
", " << Res3 <<
", "
388 dbgs() << *F1 <<
'\n' << *F2 <<
'\n' << *F3 <<
'\n';
395 dbgs() <<
"MERGEFUNC-VERIFY: " << (Valid ?
"Passed." :
"Failed.") <<
"\n";
404 return !
F.isDeclaration() && !
F.hasAvailableExternallyLinkage();
407 bool MergeFunctions::runOnModule(
Module &M) {
408 bool Changed =
false;
412 std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
422 auto S = HashedFuncs.begin();
423 for (
auto I = HashedFuncs.begin(),
IE = HashedFuncs.end();
I !=
IE; ++
I) {
426 if ((
I !=
S && std::prev(
I)->first ==
I->first) ||
427 (std::next(
I) !=
IE && std::next(
I)->first ==
I->first) ) {
433 std::vector<WeakTrackingVH> Worklist;
434 Deferred.swap(Worklist);
439 LLVM_DEBUG(
dbgs() <<
"size of worklist: " << Worklist.size() <<
'\n');
446 if (!
F->isDeclaration() && !
F->hasAvailableExternallyLinkage()) {
447 Changed |= insert(
F);
450 LLVM_DEBUG(
dbgs() <<
"size of FnTree: " << FnTree.size() <<
'\n');
451 }
while (!Deferred.empty());
454 FNodesInTree.clear();
455 GlobalNumbers.
clear();
464 CallBase *CB = dyn_cast<CallBase>(U.getUser());
497 return Builder.CreateIntToPtr(V, DestTy);
499 return Builder.CreatePtrToInt(V, DestTy);
501 return Builder.CreateBitCast(V, DestTy);
506 void MergeFunctions::eraseInstsUnrelatedToPDI(
507 std::vector<Instruction *> &PDIUnrelatedWL) {
509 dbgs() <<
" Erasing instructions (in reverse order of appearance in "
510 "entry block) unrelated to parameter debug info from entry "
512 while (!PDIUnrelatedWL.empty()) {
517 I->eraseFromParent();
518 PDIUnrelatedWL.pop_back();
520 LLVM_DEBUG(
dbgs() <<
" } // Done erasing instructions unrelated to parameter "
521 "debug info from entry block. \n");
525 void MergeFunctions::eraseTail(
Function *
G) {
526 std::vector<BasicBlock *> WorklistBB;
528 BB.dropAllReferences();
529 WorklistBB.push_back(&
BB);
531 while (!WorklistBB.empty()) {
533 BB->eraseFromParent();
534 WorklistBB.pop_back();
547 void MergeFunctions::filterInstsUnrelatedToPDI(
548 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
549 std::set<Instruction *> PDIRelated;
552 if (
auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
561 PDIRelated.insert(&*BI);
567 }
else if (
auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
575 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
582 if (isa<Argument>(
Arg)) {
586 PDIRelated.insert(AI);
590 PDIRelated.insert(
SI);
594 PDIRelated.insert(&*BI);
617 }
else if (BI->isTerminator() && &*BI == GEntryBlock->
getTerminator()) {
621 PDIRelated.insert(&*BI);
630 <<
" Report parameter debug info related/related instructions: {\n");
632 if (PDIRelated.find(&
I) == PDIRelated.end()) {
636 PDIUnrelatedWL.push_back(&
I);
653 if (
F->size() == 1) {
654 if (
F->front().size() <= 2) {
656 <<
" is too small to bother creating a thunk for\n");
673 std::vector<Instruction *> PDIUnrelatedWL;
677 LLVM_DEBUG(
dbgs() <<
"writeThunk: (MergeFunctionsPDI) Do not create a new "
678 "function as thunk; retain original: "
679 <<
G->getName() <<
"()\n");
680 GEntryBlock = &
G->getEntryBlock();
682 dbgs() <<
"writeThunk: (MergeFunctionsPDI) filter parameter related "
684 <<
G->getName() <<
"() {\n");
685 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
690 G->getAddressSpace(),
"",
G->getParent());
713 if (
H->getReturnType()->isVoidTy()) {
730 dbgs() <<
"writeThunk: (MergeFunctionsPDI) No DISubprogram for "
731 <<
G->getName() <<
"()\n");
734 eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
736 dbgs() <<
"} // End of parameter related debug info filtering for: "
737 <<
G->getName() <<
"()\n");
742 G->replaceAllUsesWith(NewG);
743 G->eraseFromParent();
756 assert(
F->hasLocalLinkage() ||
F->hasExternalLinkage()
757 ||
F->hasWeakLinkage() ||
F->hasLinkOnceLinkage());
766 G->getLinkage(),
"", BitcastF,
G->getParent());
770 GA->setVisibility(
G->getVisibility());
774 G->replaceAllUsesWith(GA);
775 G->eraseFromParent();
797 if (
F->isInterposable()) {
809 F->getAddressSpace(),
"",
F->getParent());
813 F->replaceAllUsesWith(NewF);
817 writeThunkOrAlias(
F,
G);
818 writeThunkOrAlias(
F, NewF);
820 F->setAlignment(MaxAlignment);
823 ++NumFunctionsMerged;
828 if (
G->hasGlobalUnnamedAddr()) {
835 G->replaceAllUsesWith(BitcastF);
839 replaceDirectCallers(
G,
F);
847 G->eraseFromParent();
848 ++NumFunctionsMerged;
852 if (writeThunkOrAlias(
F,
G)) {
853 ++NumFunctionsMerged;
859 void MergeFunctions::replaceFunctionInTree(
const FunctionNode &FN,
863 "The two functions must be equal");
865 auto I = FNodesInTree.find(
F);
866 assert(
I != FNodesInTree.end() &&
"F should be in FNodesInTree");
867 assert(FNodesInTree.count(
G) == 0 &&
"FNodesInTree should not contain G");
869 FnTreeType::iterator IterToFNInFnTree =
I->second;
870 assert(&(*IterToFNInFnTree) == &FN &&
"F should map to FN in FNodesInTree.");
872 FNodesInTree.erase(
I);
873 FNodesInTree.insert({
G, IterToFNInFnTree});
880 if (
F->isInterposable() !=
G->isInterposable()) {
883 return !
F->isInterposable();
885 if (
F->hasLocalLinkage() !=
G->hasLocalLinkage()) {
888 return !
F->hasLocalLinkage();
893 return F->getName() <=
G->getName();
898 bool MergeFunctions::insert(
Function *NewFunction) {
899 std::pair<FnTreeType::iterator, bool>
Result =
900 FnTree.insert(FunctionNode(NewFunction));
903 assert(FNodesInTree.count(NewFunction) == 0);
904 FNodesInTree.insert({NewFunction,
Result.first});
910 const FunctionNode &OldF = *
Result.first;
915 replaceFunctionInTree(*
Result.first, NewFunction);
917 assert(OldF.getFunc() !=
F &&
"Must have swapped the functions.");
921 <<
" == " << NewFunction->
getName() <<
'\n');
924 mergeTwoFunctions(OldF.getFunc(), DeleteF);
931 auto I = FNodesInTree.find(
F);
932 if (
I != FNodesInTree.end()) {
934 FnTree.erase(
I->second);
937 FNodesInTree.erase(
I);
938 Deferred.emplace_back(
F);
944 void MergeFunctions::removeUsers(
Value *V) {
946 if (
auto *
I = dyn_cast<Instruction>(U))
A set of analyses that are preserved following a run of a transformation pass.
This class represents an incoming formal argument to a Function.
GlobalNumberState assigns an integer to each global value in the program, which is used by the compar...
static Value * createCast(IRBuilder<> &Builder, Value *V, Type *DestTy)
void setComdat(Comdat *C)
This is an optimization pass for GlobalISel generic memory operations.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Return a value (possibly void), from a function.
Value handle that is nullable, but tries to track the Value.
InstListType::iterator iterator
Instruction iterators...
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
bool isPointerTy() const
True if this is an instance of PointerType.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void setTailCallKind(TailCallKind TCK)
static bool isEligibleForMerging(Function &F)
Check whether F is eligible for function merging.
unsigned getAddressSpace() const
Return the address space of the Pointer type.
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
ModulePass * createMergeFunctionsPass()
createMergeFunctionsPass - This pass discovers identical functions and collapses them.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
LLVM Basic Block Representation.
static FunctionHash functionHash(Function &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool isFuncOrderCorrect(const Function *F, const Function *G)
Function object to check whether the first component of a std::pair compares less than the first comp...
static bool canCreateAliasFor(Function *F)
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
iterator begin()
Instruction iterator methods.
iterator_range< use_iterator > uses()
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
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)
STATISTIC(NumFunctions, "Total number of functions")
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
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."))
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
unsigned getStructNumElements() const
bool isIntegerTy() const
True if this is an instance of IntegerType.
int compare()
Test whether the two functions have equivalent behaviour.
An instruction for storing to memory.
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Type * getParamType(unsigned i) const
Parameter type accessors.
initializer< Ty > init(const Ty &Val)
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...
Class to represent pointers.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
A Module instance is used to store all the information related to an LLVM module.
static cl::opt< bool > MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden, cl::init(false), cl::desc("Allow mergefunc to create aliases"))
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
Type * getStructElementType(unsigned N) const
Type * getType() const
All values are typed, get the type of this value.
const Function * getFunction() const
Return the function this instruction belongs to.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
INITIALIZE_PASS(MergeFunctionsLegacyPass, "mergefunc", "Merge Functions", false, false) ModulePass *llvm
static bool canCreateThunkFor(Function *F)
Whether this function may be replaced by a forwarding thunk.
StringRef getName() const
Return a constant reference to the value's name.
uint64_t getAlignment() const
FIXME: Remove this function once transition to Align is over.
LLVMContext & getContext() const
void initializeMergeFunctionsLegacyPassPass(PassRegistry &)
void stable_sort(R &&Range)
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...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void erase(GlobalValue *Global)
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
@ PrivateLinkage
Like Internal, but omit from symbol table.
bool isStructTy() const
True if this is an instance of StructType.
@ SwiftTail
SwiftTail - This follows the Swift calling convention in how arguments are passed but guarantees tail...
Value handle that asserts if the Value is deleted.
Align max(MaybeAlign Lhs, Align Rhs)
FunctionComparator - Compares two functions to determine whether or not they will generate machine co...
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...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
PointerType * getType() const
Global values are always pointers.
A container for analyses that lazily runs them and caches their results.
This class represents a function call, abstracting a target machine's calling convention.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
void takeName(Value *V)
Transfer the name from V to this value.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
an instruction to allocate memory on the stack
LLVM Value Representation.
iterator_range< user_iterator > users()
void setCallingConv(CallingConv::ID CC)
Class to represent function types.
A Use represents the edge between a Value definition and its users.