Go to the documentation of this file.
133 using namespace llvm;
135 #define DEBUG_TYPE "mergefunc"
137 STATISTIC(NumFunctionsMerged,
"Number of functions merged");
138 STATISTIC(NumThunksWritten,
"Number of thunks generated");
139 STATISTIC(NumAliasesWritten,
"Number of aliases generated");
140 STATISTIC(NumDoubleWeak,
"Number of new functions created");
144 cl::desc(
"How many functions in module could be used for "
145 "MergeFunctions pass sanity check. "
146 "'0' disables this check. Works only with '-debug' key."),
166 cl::desc(
"Preserve debug info in thunk when mergefunc "
167 "transformations are made."));
172 cl::desc(
"Allow mergefunc to create aliases"));
199 class MergeFunctions {
201 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {
204 bool runOnModule(
Module &M);
209 class FunctionNodeCmp {
215 bool operator()(
const FunctionNode &LHS,
const FunctionNode &RHS)
const {
217 if (LHS.getHash() != RHS.getHash())
218 return LHS.getHash() < RHS.getHash();
220 return FCmp.compare() == -1;
223 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
229 std::vector<WeakTrackingVH> Deferred;
234 bool doSanityCheck(std::vector<WeakTrackingVH> &Worklist);
247 void removeUsers(
Value *V);
260 void filterInstsUnrelatedToPDI(
BasicBlock *GEntryBlock,
261 std::vector<Instruction *> &PDIUnrelatedWL);
268 void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
283 void replaceFunctionInTree(
const FunctionNode &FN,
Function *
G);
297 class MergeFunctionsLegacyPass :
public ModulePass {
305 bool runOnModule(
Module &M)
override {
310 return MF.runOnModule(M);
318 "Merge Functions",
false,
false)
321 return new MergeFunctionsLegacyPass();
327 if (!MF.runOnModule(
M))
333 bool MergeFunctions::doSanityCheck(std::vector<WeakTrackingVH> &Worklist) {
335 unsigned TripleNumber = 0;
338 dbgs() <<
"MERGEFUNC-SANITY: Started for first " << Max <<
" functions.\n";
341 for (std::vector<WeakTrackingVH>::iterator
I = Worklist.begin(),
343 I !=
E &&
i < Max; ++
I, ++
i) {
345 for (std::vector<WeakTrackingVH>::iterator J =
I; J !=
E &&
j < Max;
354 dbgs() <<
"MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
356 dbgs() << *F1 <<
'\n' << *F2 <<
'\n';
364 for (std::vector<WeakTrackingVH>::iterator K = J; K !=
E && k < Max;
365 ++k, ++K, ++TripleNumber) {
373 bool Transitive =
true;
375 if (Res1 != 0 && Res1 == Res4) {
377 Transitive = Res3 == Res1;
378 }
else if (Res3 != 0 && Res3 == -Res4) {
380 Transitive = Res3 == Res1;
381 }
else if (Res4 != 0 && -Res3 == Res4) {
383 Transitive = Res4 == -Res1;
387 dbgs() <<
"MERGEFUNC-SANITY: Non-transitive; triple: "
388 << TripleNumber <<
"\n";
389 dbgs() <<
"Res1, Res3, Res4: " << Res1 <<
", " << Res3 <<
", "
391 dbgs() << *F1 <<
'\n' << *F2 <<
'\n' << *F3 <<
'\n';
398 dbgs() <<
"MERGEFUNC-SANITY: " << (Valid ?
"Passed." :
"Failed.") <<
"\n";
407 return !
F.isDeclaration() && !
F.hasAvailableExternallyLinkage();
410 bool MergeFunctions::runOnModule(
Module &M) {
411 bool Changed =
false;
415 std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
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();
469 CallBase *CB = dyn_cast<CallBase>(U->getUser());
502 return Builder.CreateIntToPtr(V, DestTy);
504 return Builder.CreatePtrToInt(V, DestTy);
506 return Builder.CreateBitCast(V, DestTy);
511 void MergeFunctions::eraseInstsUnrelatedToPDI(
512 std::vector<Instruction *> &PDIUnrelatedWL) {
514 dbgs() <<
" Erasing instructions (in reverse order of appearance in "
515 "entry block) unrelated to parameter debug info from entry "
517 while (!PDIUnrelatedWL.empty()) {
522 I->eraseFromParent();
523 PDIUnrelatedWL.pop_back();
525 LLVM_DEBUG(
dbgs() <<
" } // Done erasing instructions unrelated to parameter "
526 "debug info from entry block. \n");
530 void MergeFunctions::eraseTail(
Function *
G) {
531 std::vector<BasicBlock *> WorklistBB;
533 BB.dropAllReferences();
534 WorklistBB.push_back(&
BB);
536 while (!WorklistBB.empty()) {
538 BB->eraseFromParent();
539 WorklistBB.pop_back();
552 void MergeFunctions::filterInstsUnrelatedToPDI(
553 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
554 std::set<Instruction *> PDIRelated;
557 if (
auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
566 PDIRelated.insert(&*BI);
572 }
else if (
auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
580 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
587 if (isa<Argument>(
Arg)) {
591 PDIRelated.insert(AI);
595 PDIRelated.insert(
SI);
599 PDIRelated.insert(&*BI);
622 }
else if (BI->isTerminator() && &*BI == GEntryBlock->
getTerminator()) {
626 PDIRelated.insert(&*BI);
635 <<
" Report parameter debug info related/related instructions: {\n");
637 if (PDIRelated.find(&
I) == PDIRelated.end()) {
641 PDIUnrelatedWL.push_back(&
I);
658 if (
F->size() == 1) {
659 if (
F->front().size() <= 2) {
661 <<
" is too small to bother creating a thunk for\n");
678 std::vector<Instruction *> PDIUnrelatedWL;
682 LLVM_DEBUG(
dbgs() <<
"writeThunk: (MergeFunctionsPDI) Do not create a new "
683 "function as thunk; retain original: "
684 <<
G->getName() <<
"()\n");
685 GEntryBlock = &
G->getEntryBlock();
687 dbgs() <<
"writeThunk: (MergeFunctionsPDI) filter parameter related "
689 <<
G->getName() <<
"() {\n");
690 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
695 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());
769 G->getLinkage(),
"", BitcastF,
G->getParent());
773 GA->setVisibility(
G->getVisibility());
777 G->replaceAllUsesWith(GA);
778 G->eraseFromParent();
800 if (
F->isInterposable()) {
812 F->getAddressSpace(),
"",
F->getParent());
816 F->replaceAllUsesWith(NewF);
820 writeThunkOrAlias(
F,
G);
821 writeThunkOrAlias(
F, NewF);
823 F->setAlignment(MaxAlignment);
826 ++NumFunctionsMerged;
831 if (
G->hasGlobalUnnamedAddr()) {
838 G->replaceAllUsesWith(BitcastF);
842 replaceDirectCallers(
G,
F);
850 G->eraseFromParent();
851 ++NumFunctionsMerged;
855 if (writeThunkOrAlias(
F,
G)) {
856 ++NumFunctionsMerged;
862 void MergeFunctions::replaceFunctionInTree(
const FunctionNode &FN,
866 "The two functions must be equal");
868 auto I = FNodesInTree.find(
F);
869 assert(
I != FNodesInTree.end() &&
"F should be in FNodesInTree");
870 assert(FNodesInTree.count(
G) == 0 &&
"FNodesInTree should not contain G");
872 FnTreeType::iterator IterToFNInFnTree =
I->second;
873 assert(&(*IterToFNInFnTree) == &FN &&
"F should map to FN in FNodesInTree.");
875 FNodesInTree.erase(
I);
876 FNodesInTree.insert({
G, IterToFNInFnTree});
883 if (
F->isInterposable() !=
G->isInterposable()) {
886 return !
F->isInterposable();
888 if (
F->hasLocalLinkage() !=
G->hasLocalLinkage()) {
891 return !
F->hasLocalLinkage();
896 return F->getName() <=
G->getName();
901 bool MergeFunctions::insert(
Function *NewFunction) {
902 std::pair<FnTreeType::iterator, bool>
Result =
903 FnTree.insert(FunctionNode(NewFunction));
906 assert(FNodesInTree.count(NewFunction) == 0);
907 FNodesInTree.insert({NewFunction,
Result.first});
913 const FunctionNode &OldF = *
Result.first;
918 replaceFunctionInTree(*
Result.first, NewFunction);
920 assert(OldF.getFunc() !=
F &&
"Must have swapped the functions.");
924 <<
" == " << NewFunction->
getName() <<
'\n');
927 mergeTwoFunctions(OldF.getFunc(), DeleteF);
934 auto I = FNodesInTree.find(
F);
935 if (
I != FNodesInTree.end()) {
937 FnTree.erase(
I->second);
940 FNodesInTree.erase(
I);
941 Deferred.emplace_back(
F);
947 void MergeFunctions::removeUsers(
Value *V) {
949 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)
This class represents lattice values for constants.
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.
void setTailCall(bool IsTc=true)
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.
Type * getElementType() const
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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.
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
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 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.
void setComdat(Comdat *C)
initializer< Ty > init(const Ty &Val)
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 cl::opt< unsigned > NumFunctionsForSanityCheck("mergefunc-sanity", cl::desc("How many functions in module could be used for " "MergeFunctions pass sanity check. " "'0' disables this check. Works only with '-debug' key."), cl::init(0), cl::Hidden)
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
unsigned getAlignment() const
FIXME: Remove this function once transition to Align is over.
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.
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...
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.
uint64_t FunctionHash
Hash a function.
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...
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.