1//===- MergeFunctions.cpp - Merge identical functions ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass looks for equivalent functions that are mergable and folds them.
10//
11// Order relation is defined on set of functions. It was made through
12// special function comparison procedure that returns
13// 0 when functions are equal,
14// -1 when Left function is less than right function, and
15// 1 for opposite case. We need total-ordering, so we need to maintain
16// four properties on the functions set:
17// a <= a (reflexivity)
18// if a <= b and b <= a then a = b (antisymmetry)
19// if a <= b and b <= c then a <= c (transitivity).
20// for all a and b: a <= b or b <= a (totality).
21//
22// Comparison iterates through each instruction in each basic block.
23// Functions are kept on binary tree. For each new function F we perform
24// lookup in binary tree.
25// In practice it works the following way:
26// -- We define Function* container class with custom "operator<" (FunctionPtr).
27// -- "FunctionPtr" instances are stored in std::set collection, so every
28// std::set::insert operation will give you result in log(N) time.
29//
30// As an optimization, a hash of the function structure is calculated first, and
31// two functions are only compared if they have the same hash. This hash is
32// cheap to compute, and has the property that if function F == G according to
33// the comparison function, then hash(F) == hash(G). This consistency property
34// is critical to ensuring all possible merging opportunities are exploited.
35// Collisions in the hash affect the speed of the pass but not the correctness
36// or determinism of the resulting transformation.
37//
38// When a match is found the functions are folded. If both functions are
39// overridable, we move the functionality into a new internal function and
40// leave two overridable thunks to it.
41//
42//===----------------------------------------------------------------------===//
43//
44// Future work:
45//
46// * virtual functions.
47//
48// Many functions have their address taken by the virtual function table for
49// the object they belong to. However, as long as it's only used for a lookup
50// and call, this is irrelevant, and we'd like to fold such functions.
51//
52// * be smarter about bitcasts.
53//
54// In order to fold functions, we will sometimes add either bitcast instructions
55// or bitcast constant expressions. Unfortunately, this can confound further
56// analysis since the two functions differ where one has a bitcast and the
57// other doesn't. We should learn to look through bitcasts.
58//
59// * Compare complex types with pointer types inside.
60// * Compare cross-reference cases.
61// * Compare complex expressions.
62//
63// All the three issues above could be described as ability to prove that
64// fA == fB == fC == fE == fF == fG in example below:
65//
66// void fA() {
67// fB();
68// }
69// void fB() {
70// fA();
71// }
72//
73// void fE() {
74// fF();
75// }
76// void fF() {
77// fG();
78// }
79// void fG() {
80// fE();
81// }
82//
83// Simplest cross-reference case (fA <--> fB) was implemented in previous
84// versions of MergeFunctions, though it presented only in two function pairs
85// in test-suite (that counts >50k functions)
86// Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A)
87// could cover much more cases.
88//
89//===----------------------------------------------------------------------===//
90
91#include "llvm/Transforms/IPO/MergeFunctions.h"
92#include "llvm/ADT/ArrayRef.h"
93#include "llvm/ADT/SmallVector.h"
94#include "llvm/ADT/Statistic.h"
95#include "llvm/IR/Argument.h"
96#include "llvm/IR/BasicBlock.h"
97#include "llvm/IR/DebugInfoMetadata.h"
98#include "llvm/IR/DebugLoc.h"
99#include "llvm/IR/DerivedTypes.h"
100#include "llvm/IR/Function.h"
101#include "llvm/IR/GlobalValue.h"
102#include "llvm/IR/IRBuilder.h"
103#include "llvm/IR/InstrTypes.h"
104#include "llvm/IR/Instruction.h"
105#include "llvm/IR/Instructions.h"
106#include "llvm/IR/IntrinsicInst.h"
107#include "llvm/IR/Module.h"
108#include "llvm/IR/StructuralHash.h"
109#include "llvm/IR/Type.h"
110#include "llvm/IR/Use.h"
111#include "llvm/IR/User.h"
112#include "llvm/IR/Value.h"
113#include "llvm/IR/ValueHandle.h"
114#include "llvm/Support/Casting.h"
115#include "llvm/Support/CommandLine.h"
116#include "llvm/Support/Debug.h"
117#include "llvm/Support/raw_ostream.h"
118#include "llvm/Transforms/IPO.h"
119#include "llvm/Transforms/Utils/FunctionComparator.h"
120#include "llvm/Transforms/Utils/ModuleUtils.h"
121#include <algorithm>
122#include <cassert>
123#include <iterator>
124#include <set>
125#include <utility>
126#include <vector>
127
128using namespace llvm;
129
130#define DEBUG_TYPE "mergefunc"
131
132STATISTIC(NumFunctionsMerged, "Number of functions merged");
133STATISTIC(NumThunksWritten, "Number of thunks generated");
134STATISTIC(NumAliasesWritten, "Number of aliases generated");
135STATISTIC(NumDoubleWeak, "Number of new functions created");
136
137static cl::opt<unsigned> NumFunctionsForVerificationCheck(
138 "mergefunc-verify",
139 cl::desc("How many functions in a module could be used for "
140 "MergeFunctions to pass a basic correctness check. "
141 "'0' disables this check. Works only with '-debug' key."),
142 cl::init(Val: 0), cl::Hidden);
143
144// Under option -mergefunc-preserve-debug-info we:
145// - Do not create a new function for a thunk.
146// - Retain the debug info for a thunk's parameters (and associated
147// instructions for the debug info) from the entry block.
148// Note: -debug will display the algorithm at work.
149// - Create debug-info for the call (to the shared implementation) made by
150// a thunk and its return value.
151// - Erase the rest of the function, retaining the (minimally sized) entry
152// block to create a thunk.
153// - Preserve a thunk's call site to point to the thunk even when both occur
154// within the same translation unit, to aid debugability. Note that this
155// behaviour differs from the underlying -mergefunc implementation which
156// modifies the thunk's call site to point to the shared implementation
157// when both occur within the same translation unit.
158static cl::opt<bool>
159 MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,
160 cl::init(Val: false),
161 cl::desc("Preserve debug info in thunk when mergefunc "
162 "transformations are made."));
163
164static cl::opt<bool>
165 MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden,
166 cl::init(Val: false),
167 cl::desc("Allow mergefunc to create aliases"));
168
169namespace {
170
171class FunctionNode {
172 mutable AssertingVH<Function> F;
173 stable_hash Hash;
174
175public:
176 // Note the hash is recalculated potentially multiple times, but it is cheap.
177 FunctionNode(Function *F) : F(F), Hash(StructuralHash(F: *F)) {}
178
179 Function *getFunc() const { return F; }
180 stable_hash getHash() const { return Hash; }
181
182 /// Replace the reference to the function F by the function G, assuming their
183 /// implementations are equal.
184 void replaceBy(Function *G) const {
185 F = G;
186 }
187};
188
189/// MergeFunctions finds functions which will generate identical machine code,
190/// by considering all pointer types to be equivalent. Once identified,
191/// MergeFunctions will fold them by replacing a call to one to a call to a
192/// bitcast of the other.
193class MergeFunctions {
194public:
195 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {
196 }
197
198 template <typename FuncContainer> bool run(FuncContainer &Functions);
199 DenseMap<Function *, Function *> runOnFunctions(ArrayRef<Function *> F);
200
201 SmallPtrSet<GlobalValue *, 4> &getUsed();
202
203private:
204 // The function comparison operator is provided here so that FunctionNodes do
205 // not need to become larger with another pointer.
206 class FunctionNodeCmp {
207 GlobalNumberState* GlobalNumbers;
208
209 public:
210 FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
211
212 bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
213 // Order first by hashes, then full function comparison.
214 if (LHS.getHash() != RHS.getHash())
215 return LHS.getHash() < RHS.getHash();
216 FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
217 return FCmp.compare() < 0;
218 }
219 };
220 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
221
222 GlobalNumberState GlobalNumbers;
223
224 /// A work queue of functions that may have been modified and should be
225 /// analyzed again.
226 std::vector<WeakTrackingVH> Deferred;
227
228 /// Set of values marked as used in llvm.used and llvm.compiler.used.
229 SmallPtrSet<GlobalValue *, 4> Used;
230
231#ifndef NDEBUG
232 /// Checks the rules of order relation introduced among functions set.
233 /// Returns true, if check has been passed, and false if failed.
234 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist);
235#endif
236
237 /// Insert a ComparableFunction into the FnTree, or merge it away if it's
238 /// equal to one that's already present.
239 bool insert(Function *NewFunction);
240
241 /// Remove a Function from the FnTree and queue it up for a second sweep of
242 /// analysis.
243 void remove(Function *F);
244
245 /// Find the functions that use this Value and remove them from FnTree and
246 /// queue the functions.
247 void removeUsers(Value *V);
248
249 /// Replace all direct calls of Old with calls of New. Will bitcast New if
250 /// necessary to make types match.
251 void replaceDirectCallers(Function *Old, Function *New);
252
253 /// Merge two equivalent functions. Upon completion, G may be deleted, or may
254 /// be converted into a thunk. In either case, it should never be visited
255 /// again.
256 void mergeTwoFunctions(Function *F, Function *G);
257
258 /// Fill PDIUnrelatedWL with instructions from the entry block that are
259 /// unrelated to parameter related debug info.
260 /// \param PDVRUnrelatedWL The equivalent non-intrinsic debug records.
261 void
262 filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,
263 std::vector<Instruction *> &PDIUnrelatedWL,
264 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL);
265
266 /// Erase the rest of the CFG (i.e. barring the entry block).
267 void eraseTail(Function *G);
268
269 /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
270 /// parameter debug info, from the entry block.
271 /// \param PDVRUnrelatedWL contains the equivalent set of non-instruction
272 /// debug-info records.
273 void
274 eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL,
275 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL);
276
277 /// Replace G with a simple tail call to bitcast(F). Also (unless
278 /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
279 /// delete G.
280 void writeThunk(Function *F, Function *G);
281
282 // Replace G with an alias to F (deleting function G)
283 void writeAlias(Function *F, Function *G);
284
285 // If needed, replace G with an alias to F if possible, or a thunk to F if
286 // profitable. Returns false if neither is the case. If \p G is not needed
287 // (i.e. it is discardable and not used), \p G is removed directly.
288 bool writeThunkOrAliasIfNeeded(Function *F, Function *G);
289
290 /// Replace function F with function G in the function tree.
291 void replaceFunctionInTree(const FunctionNode &FN, Function *G);
292
293 /// The set of all distinct functions. Use the insert() and remove() methods
294 /// to modify it. The map allows efficient lookup and deferring of Functions.
295 FnTreeType FnTree;
296
297 // Map functions to the iterators of the FunctionNode which contains them
298 // in the FnTree. This must be updated carefully whenever the FnTree is
299 // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
300 // dangling iterators into FnTree. The invariant that preserves this is that
301 // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
302 DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
303
304 /// Deleted-New functions mapping
305 DenseMap<Function *, Function *> DelToNewMap;
306};
307} // end anonymous namespace
308
309PreservedAnalyses MergeFunctionsPass::run(Module &M,
310 ModuleAnalysisManager &AM) {
311 if (!MergeFunctionsPass::runOnModule(M))
312 return PreservedAnalyses::all();
313 return PreservedAnalyses::none();
314}
315
316SmallPtrSet<GlobalValue *, 4> &MergeFunctions::getUsed() { return Used; }
317
318bool MergeFunctionsPass::runOnModule(Module &M) {
319 MergeFunctions MF;
320 SmallVector<GlobalValue *, 4> UsedV;
321 collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/false);
322 collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/true);
323 MF.getUsed().insert_range(R&: UsedV);
324 return MF.run(M);
325}
326
327DenseMap<Function *, Function *>
328MergeFunctionsPass::runOnFunctions(ArrayRef<Function *> F) {
329 MergeFunctions MF;
330 return MF.runOnFunctions(F);
331}
332
333#ifndef NDEBUG
334bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) {
335 if (const unsigned Max = NumFunctionsForVerificationCheck) {
336 unsigned TripleNumber = 0;
337 bool Valid = true;
338
339 dbgs() << "MERGEFUNC-VERIFY: Started for first " << Max << " functions.\n";
340
341 unsigned i = 0;
342 for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),
343 E = Worklist.end();
344 I != E && i < Max; ++I, ++i) {
345 unsigned j = i;
346 for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;
347 ++J, ++j) {
348 Function *F1 = cast<Function>(*I);
349 Function *F2 = cast<Function>(*J);
350 int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
351 int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
352
353 // If F1 <= F2, then F2 >= F1, otherwise report failure.
354 if (Res1 != -Res2) {
355 dbgs() << "MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber
356 << "\n";
357 dbgs() << *F1 << '\n' << *F2 << '\n';
358 Valid = false;
359 }
360
361 if (Res1 == 0)
362 continue;
363
364 unsigned k = j;
365 for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;
366 ++k, ++K, ++TripleNumber) {
367 if (K == J)
368 continue;
369
370 Function *F3 = cast<Function>(*K);
371 int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
372 int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();
373
374 bool Transitive = true;
375
376 if (Res1 != 0 && Res1 == Res4) {
377 // F1 > F2, F2 > F3 => F1 > F3
378 Transitive = Res3 == Res1;
379 } else if (Res3 != 0 && Res3 == -Res4) {
380 // F1 > F3, F3 > F2 => F1 > F2
381 Transitive = Res3 == Res1;
382 } else if (Res4 != 0 && -Res3 == Res4) {
383 // F2 > F3, F3 > F1 => F2 > F1
384 Transitive = Res4 == -Res1;
385 }
386
387 if (!Transitive) {
388 dbgs() << "MERGEFUNC-VERIFY: Non-transitive; triple: "
389 << TripleNumber << "\n";
390 dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
391 << Res4 << "\n";
392 dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n';
393 Valid = false;
394 }
395 }
396 }
397 }
398
399 dbgs() << "MERGEFUNC-VERIFY: " << (Valid ? "Passed." : "Failed.") << "\n";
400 return Valid;
401 }
402 return true;
403}
404#endif
405
406/// Check whether \p F has an intrinsic which references
407/// distinct metadata as an operand. The most common
408/// instance of this would be CFI checks for function-local types.
409static bool hasDistinctMetadataIntrinsic(const Function &F) {
410 for (const BasicBlock &BB : F) {
411 for (const Instruction &I : BB) {
412 if (!isa<IntrinsicInst>(Val: &I))
413 continue;
414
415 for (Value *Op : I.operands()) {
416 auto *MDL = dyn_cast<MetadataAsValue>(Val: Op);
417 if (!MDL)
418 continue;
419 if (MDNode *N = dyn_cast<MDNode>(Val: MDL->getMetadata()))
420 if (N->isDistinct())
421 return true;
422 }
423 }
424 }
425 return false;
426}
427
428/// Check whether \p F is eligible for function merging.
429static bool isEligibleForMerging(Function &F) {
430 return !F.isDeclaration() && !F.hasAvailableExternallyLinkage() &&
431 !F.hasFnAttribute(Kind: Attribute::NoIPA) &&
432 !hasDistinctMetadataIntrinsic(F);
433}
434
435inline Function *asPtr(Function *Fn) { return Fn; }
436inline Function *asPtr(Function &Fn) { return &Fn; }
437
438template <typename FuncContainer> bool MergeFunctions::run(FuncContainer &M) {
439 bool Changed = false;
440
441 // All functions in the module, ordered by hash. Functions with a unique
442 // hash value are easily eliminated.
443 std::vector<std::pair<stable_hash, Function *>> HashedFuncs;
444 for (auto &Func : M) {
445 Function *FuncPtr = asPtr(Func);
446 if (isEligibleForMerging(F&: *FuncPtr)) {
447 HashedFuncs.push_back(x: {StructuralHash(F: *FuncPtr), FuncPtr});
448 }
449 }
450
451 llvm::stable_sort(Range&: HashedFuncs, C: less_first());
452
453 auto S = HashedFuncs.begin();
454 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
455 // If the hash value matches the previous value or the next one, we must
456 // consider merging it. Otherwise it is dropped and never considered again.
457 if ((I != S && std::prev(x: I)->first == I->first) ||
458 (std::next(x: I) != IE && std::next(x: I)->first == I->first)) {
459 Deferred.push_back(x: WeakTrackingVH(I->second));
460 }
461 }
462
463 do {
464 std::vector<WeakTrackingVH> Worklist;
465 Deferred.swap(x&: Worklist);
466
467 LLVM_DEBUG(doFunctionalCheck(Worklist));
468
469 LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
470 LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
471
472 // Insert functions and merge them.
473 for (WeakTrackingVH &I : Worklist) {
474 if (!I)
475 continue;
476 Function *F = cast<Function>(Val&: I);
477 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
478 !F->hasFnAttribute(Kind: Attribute::NoIPA)) {
479 Changed |= insert(NewFunction: F);
480 }
481 }
482 LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
483 } while (!Deferred.empty());
484
485 FnTree.clear();
486 FNodesInTree.clear();
487 GlobalNumbers.clear();
488 Used.clear();
489
490 return Changed;
491}
492
493DenseMap<Function *, Function *>
494MergeFunctions::runOnFunctions(ArrayRef<Function *> F) {
495 [[maybe_unused]] bool MergeResult = this->run(M&: F);
496 assert(MergeResult == !DelToNewMap.empty());
497 return this->DelToNewMap;
498}
499
500// Replace direct callers of Old with New.
501void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
502 for (Use &U : make_early_inc_range(Range: Old->uses())) {
503 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
504 if (CB && CB->isCallee(U: &U)) {
505 // Do not copy attributes from the called function to the call-site.
506 // Function comparison ensures that the attributes are the same up to
507 // type congruences in byval(), in which case we need to keep the byval
508 // type of the call-site, not the callee function.
509 remove(F: CB->getFunction());
510 U.set(New);
511 }
512 }
513}
514
515// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
516// parameter debug info, from the entry block.
517void MergeFunctions::eraseInstsUnrelatedToPDI(
518 std::vector<Instruction *> &PDIUnrelatedWL,
519 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
520 LLVM_DEBUG(
521 dbgs() << " Erasing instructions (in reverse order of appearance in "
522 "entry block) unrelated to parameter debug info from entry "
523 "block: {\n");
524 while (!PDIUnrelatedWL.empty()) {
525 Instruction *I = PDIUnrelatedWL.back();
526 LLVM_DEBUG(dbgs() << " Deleting Instruction: ");
527 LLVM_DEBUG(I->print(dbgs()));
528 LLVM_DEBUG(dbgs() << "\n");
529 I->eraseFromParent();
530 PDIUnrelatedWL.pop_back();
531 }
532
533 while (!PDVRUnrelatedWL.empty()) {
534 DbgVariableRecord *DVR = PDVRUnrelatedWL.back();
535 LLVM_DEBUG(dbgs() << " Deleting DbgVariableRecord ");
536 LLVM_DEBUG(DVR->print(dbgs()));
537 LLVM_DEBUG(dbgs() << "\n");
538 DVR->eraseFromParent();
539 PDVRUnrelatedWL.pop_back();
540 }
541
542 LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
543 "debug info from entry block. \n");
544}
545
546// Reduce G to its entry block.
547void MergeFunctions::eraseTail(Function *G) {
548 std::vector<BasicBlock *> WorklistBB;
549 for (BasicBlock &BB : drop_begin(RangeOrContainer&: *G)) {
550 BB.dropAllReferences();
551 WorklistBB.push_back(x: &BB);
552 }
553 while (!WorklistBB.empty()) {
554 BasicBlock *BB = WorklistBB.back();
555 BB->eraseFromParent();
556 WorklistBB.pop_back();
557 }
558}
559
560// We are interested in the following instructions from the entry block as being
561// related to parameter debug info:
562// - @llvm.dbg.declare
563// - stores from the incoming parameters to locations on the stack-frame
564// - allocas that create these locations on the stack-frame
565// - @llvm.dbg.value
566// - the entry block's terminator
567// The rest are unrelated to debug info for the parameters; fill up
568// PDIUnrelatedWL with such instructions.
569void MergeFunctions::filterInstsUnrelatedToPDI(
570 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL,
571 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
572 std::set<Instruction *> PDIRelated;
573 std::set<DbgVariableRecord *> PDVRRelated;
574
575 // Work out whether a dbg.value intrinsic or an equivalent DbgVariableRecord
576 // is a parameter to be preserved.
577 auto ExamineDbgValue = [&PDVRRelated](DbgVariableRecord *DbgVal) {
578 LLVM_DEBUG(dbgs() << " Deciding: ");
579 LLVM_DEBUG(DbgVal->print(dbgs()));
580 LLVM_DEBUG(dbgs() << "\n");
581 DILocalVariable *DILocVar = DbgVal->getVariable();
582 if (DILocVar->isParameter()) {
583 LLVM_DEBUG(dbgs() << " Include (parameter): ");
584 LLVM_DEBUG(DbgVal->print(dbgs()));
585 LLVM_DEBUG(dbgs() << "\n");
586 PDVRRelated.insert(x: DbgVal);
587 } else {
588 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
589 LLVM_DEBUG(DbgVal->print(dbgs()));
590 LLVM_DEBUG(dbgs() << "\n");
591 }
592 };
593
594 auto ExamineDbgDeclare = [&PDIRelated,
595 &PDVRRelated](DbgVariableRecord *DbgDecl) {
596 LLVM_DEBUG(dbgs() << " Deciding: ");
597 LLVM_DEBUG(DbgDecl->print(dbgs()));
598 LLVM_DEBUG(dbgs() << "\n");
599 DILocalVariable *DILocVar = DbgDecl->getVariable();
600 if (DILocVar->isParameter()) {
601 LLVM_DEBUG(dbgs() << " Parameter: ");
602 LLVM_DEBUG(DILocVar->print(dbgs()));
603 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(Val: DbgDecl->getAddress());
604 if (AI) {
605 LLVM_DEBUG(dbgs() << " Processing alloca users: ");
606 LLVM_DEBUG(dbgs() << "\n");
607 for (User *U : AI->users()) {
608 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) {
609 if (Value *Arg = SI->getValueOperand()) {
610 if (isa<Argument>(Val: Arg)) {
611 LLVM_DEBUG(dbgs() << " Include: ");
612 LLVM_DEBUG(AI->print(dbgs()));
613 LLVM_DEBUG(dbgs() << "\n");
614 PDIRelated.insert(x: AI);
615 LLVM_DEBUG(dbgs() << " Include (parameter): ");
616 LLVM_DEBUG(SI->print(dbgs()));
617 LLVM_DEBUG(dbgs() << "\n");
618 PDIRelated.insert(x: SI);
619 LLVM_DEBUG(dbgs() << " Include: ");
620 LLVM_DEBUG(DbgDecl->print(dbgs()));
621 LLVM_DEBUG(dbgs() << "\n");
622 PDVRRelated.insert(x: DbgDecl);
623 } else {
624 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
625 LLVM_DEBUG(SI->print(dbgs()));
626 LLVM_DEBUG(dbgs() << "\n");
627 }
628 }
629 } else {
630 LLVM_DEBUG(dbgs() << " Defer: ");
631 LLVM_DEBUG(U->print(dbgs()));
632 LLVM_DEBUG(dbgs() << "\n");
633 }
634 }
635 } else {
636 LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");
637 LLVM_DEBUG(DbgDecl->print(dbgs()));
638 LLVM_DEBUG(dbgs() << "\n");
639 }
640 } else {
641 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
642 LLVM_DEBUG(DbgDecl->print(dbgs()));
643 LLVM_DEBUG(dbgs() << "\n");
644 }
645 };
646
647 for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
648 BI != BIE; ++BI) {
649 // Examine DbgVariableRecords as they happen "before" the instruction. Are
650 // they connected to parameters?
651 for (DbgVariableRecord &DVR : filterDbgVars(R: BI->getDbgRecordRange())) {
652 if (DVR.isDbgValue() || DVR.isDbgAssign()) {
653 ExamineDbgValue(&DVR);
654 } else {
655 assert(DVR.isDbgDeclare());
656 ExamineDbgDeclare(&DVR);
657 }
658 }
659
660 if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
661 LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
662 LLVM_DEBUG(BI->print(dbgs()));
663 LLVM_DEBUG(dbgs() << "\n");
664 PDIRelated.insert(x: &*BI);
665 } else {
666 LLVM_DEBUG(dbgs() << " Defer: ");
667 LLVM_DEBUG(BI->print(dbgs()));
668 LLVM_DEBUG(dbgs() << "\n");
669 }
670 }
671 LLVM_DEBUG(
672 dbgs()
673 << " Report parameter debug info related/related instructions: {\n");
674
675 auto IsPDIRelated = [](auto *Rec, auto &Container, auto &UnrelatedCont) {
676 if (Container.find(Rec) == Container.end()) {
677 LLVM_DEBUG(dbgs() << " !PDIRelated: ");
678 LLVM_DEBUG(Rec->print(dbgs()));
679 LLVM_DEBUG(dbgs() << "\n");
680 UnrelatedCont.push_back(Rec);
681 } else {
682 LLVM_DEBUG(dbgs() << " PDIRelated: ");
683 LLVM_DEBUG(Rec->print(dbgs()));
684 LLVM_DEBUG(dbgs() << "\n");
685 }
686 };
687
688 // Collect the set of unrelated instructions and debug records.
689 for (Instruction &I : *GEntryBlock) {
690 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange()))
691 IsPDIRelated(&DVR, PDVRRelated, PDVRUnrelatedWL);
692 IsPDIRelated(&I, PDIRelated, PDIUnrelatedWL);
693 }
694 LLVM_DEBUG(dbgs() << " }\n");
695}
696
697/// Whether this function may be replaced by a forwarding thunk.
698static bool canCreateThunkFor(Function *F) {
699 if (F->isVarArg())
700 return false;
701
702 if (F->hasKernelCallingConv())
703 return false;
704
705 // Don't merge tiny functions using a thunk, since it can just end up
706 // making the function larger.
707 if (F->size() == 1) {
708 if (F->front().size() < 2) {
709 LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()
710 << " is too small to bother creating a thunk for\n");
711 return false;
712 }
713 }
714 return true;
715}
716
717/// Copy all metadata of a specific kind from one function to another.
718static void copyMetadataIfPresent(Function *From, Function *To,
719 StringRef Kind) {
720 SmallVector<MDNode *, 4> MDs;
721 From->getMetadata(Kind, MDs);
722 for (MDNode *MD : MDs)
723 To->addMetadata(Kind, MD&: *MD);
724}
725
726// Replace G with a simple tail call to bitcast(F). Also (unless
727// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
728// delete G. Under MergeFunctionsPDI, we use G itself for creating
729// the thunk as we preserve the debug info (and associated instructions)
730// from G's entry block pertaining to G's incoming arguments which are
731// passed on as corresponding arguments in the call that G makes to F.
732// For better debugability, under MergeFunctionsPDI, we do not modify G's
733// call sites to point to F even when within the same translation unit.
734void MergeFunctions::writeThunk(Function *F, Function *G) {
735 BasicBlock *GEntryBlock = nullptr;
736 std::vector<Instruction *> PDIUnrelatedWL;
737 std::vector<DbgVariableRecord *> PDVRUnrelatedWL;
738 BasicBlock *BB = nullptr;
739 Function *NewG = nullptr;
740 if (MergeFunctionsPDI) {
741 LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
742 "function as thunk; retain original: "
743 << G->getName() << "()\n");
744 GEntryBlock = &G->getEntryBlock();
745 LLVM_DEBUG(
746 dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
747 "debug info for "
748 << G->getName() << "() {\n");
749 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL, PDVRUnrelatedWL);
750 GEntryBlock->getTerminator()->eraseFromParent();
751 BB = GEntryBlock;
752 } else {
753 NewG = Function::Create(Ty: G->getFunctionType(), Linkage: G->getLinkage(),
754 AddrSpace: G->getAddressSpace(), N: "", M: G->getParent());
755 NewG->setComdat(G->getComdat());
756 BB = BasicBlock::Create(Context&: F->getContext(), Name: "", Parent: NewG);
757 }
758
759 IRBuilder<> Builder(BB);
760 Function *H = MergeFunctionsPDI ? G : NewG;
761 SmallVector<Value *, 16> Args;
762 unsigned i = 0;
763 FunctionType *FFTy = F->getFunctionType();
764 for (Argument &AI : H->args()) {
765 Args.push_back(Elt: Builder.CreateAggregateCast(V: &AI, DestTy: FFTy->getParamType(i)));
766 ++i;
767 }
768
769 CallInst *CI = Builder.CreateCall(Callee: F, Args);
770 ReturnInst *RI = nullptr;
771 bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail &&
772 G->getCallingConv() == CallingConv::SwiftTail;
773 CI->setTailCallKind(isSwiftTailCall ? CallInst::TCK_MustTail
774 : CallInst::TCK_Tail);
775 CI->setCallingConv(F->getCallingConv());
776 CI->setAttributes(F->getAttributes());
777 if (H->getReturnType()->isVoidTy()) {
778 RI = Builder.CreateRetVoid();
779 } else {
780 RI = Builder.CreateRet(V: Builder.CreateAggregateCast(V: CI, DestTy: H->getReturnType()));
781 }
782
783 if (MergeFunctionsPDI) {
784 DISubprogram *DIS = G->getSubprogram();
785 if (DIS) {
786 DebugLoc CIDbgLoc =
787 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
788 DebugLoc RIDbgLoc =
789 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
790 CI->setDebugLoc(CIDbgLoc);
791 RI->setDebugLoc(RIDbgLoc);
792 } else {
793 LLVM_DEBUG(
794 dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
795 << G->getName() << "()\n");
796 }
797 eraseTail(G);
798 eraseInstsUnrelatedToPDI(PDIUnrelatedWL, PDVRUnrelatedWL);
799 LLVM_DEBUG(
800 dbgs() << "} // End of parameter related debug info filtering for: "
801 << G->getName() << "()\n");
802 } else {
803 NewG->copyAttributesFrom(Src: G);
804 NewG->takeName(V: G);
805 // Ensure CFI type metadata is propagated to the new function.
806 copyMetadataIfPresent(From: G, To: NewG, Kind: "type");
807 copyMetadataIfPresent(From: G, To: NewG, Kind: "kcfi_type");
808 removeUsers(V: G);
809 G->replaceAllUsesWith(V: NewG);
810 G->eraseFromParent();
811 }
812
813 LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
814 ++NumThunksWritten;
815}
816
817// Whether this function may be replaced by an alias
818static bool canCreateAliasFor(Function *F) {
819 if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
820 return false;
821
822 // We should only see linkages supported by aliases here
823 assert(F->hasLocalLinkage() || F->hasExternalLinkage()
824 || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
825 return true;
826}
827
828// Replace G with an alias to F (deleting function G)
829void MergeFunctions::writeAlias(Function *F, Function *G) {
830 PointerType *PtrType = G->getType();
831 auto *GA =
832 GlobalAlias::create(Ty: G->getFunctionType(), AddressSpace: PtrType->getAddressSpace(),
833 Linkage: G->getLinkage(), Name: "", Aliasee: F, Parent: G->getParent());
834
835 const MaybeAlign FAlign = F->getAlign();
836 const MaybeAlign GAlign = G->getAlign();
837 if (FAlign || GAlign)
838 F->setAlignment(std::max(a: FAlign.valueOrOne(), b: GAlign.valueOrOne()));
839 else
840 F->setAlignment(std::nullopt);
841 GA->takeName(V: G);
842 GA->setVisibility(G->getVisibility());
843 GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
844
845 removeUsers(V: G);
846 G->replaceAllUsesWith(V: GA);
847 G->eraseFromParent();
848
849 LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
850 ++NumAliasesWritten;
851}
852
853// If needed, replace G with an alias to F if possible, or a thunk to F if
854// profitable. Returns false if neither is the case. If \p G is not needed (i.e.
855// it is discardable and unused), \p G is removed directly.
856bool MergeFunctions::writeThunkOrAliasIfNeeded(Function *F, Function *G) {
857 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
858 G->eraseFromParent();
859 return true;
860 }
861 if (canCreateAliasFor(F: G)) {
862 writeAlias(F, G);
863 return true;
864 }
865 if (canCreateThunkFor(F)) {
866 writeThunk(F, G);
867 return true;
868 }
869 return false;
870}
871
872/// Returns true if \p F is either weak_odr or linkonce_odr.
873static bool isODR(const Function *F) {
874 return F->hasWeakODRLinkage() || F->hasLinkOnceODRLinkage();
875}
876
877// Merge two equivalent functions. Upon completion, Function G is deleted.
878void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
879
880 // Create a new thunk that both F and G can call, if F cannot call G directly.
881 // That is the case if F is either interposable or if G is either weak_odr or
882 // linkonce_odr.
883 if (F->isInterposable() || (isODR(F) && isODR(F: G))) {
884 assert((!isODR(G) || isODR(F)) &&
885 "if G is ODR, F must also be ODR due to ordering");
886
887 // Both writeThunkOrAliasIfNeeded() calls below must succeed, either because
888 // we can create aliases for G and NewF, or because a thunk for F is
889 // profitable. F here has the same signature as NewF below, so that's what
890 // we check.
891 if (!canCreateThunkFor(F) &&
892 (!canCreateAliasFor(F) || !canCreateAliasFor(F: G)))
893 return;
894
895 // Make them both thunks to the same internal function.
896 Function *NewF = Function::Create(Ty: F->getFunctionType(), Linkage: F->getLinkage(),
897 AddrSpace: F->getAddressSpace(), N: "", M: F->getParent());
898 NewF->copyAttributesFrom(Src: F);
899 NewF->takeName(V: F);
900 NewF->setComdat(F->getComdat());
901 F->setComdat(nullptr);
902 // Ensure CFI type metadata is propagated to the new function.
903 copyMetadataIfPresent(From: F, To: NewF, Kind: "type");
904 copyMetadataIfPresent(From: F, To: NewF, Kind: "kcfi_type");
905 removeUsers(V: F);
906 F->replaceAllUsesWith(V: NewF);
907
908 // If G or NewF are (weak|linkonce)_odr, update all callers to call the
909 // thunk.
910 if (isODR(F: G))
911 replaceDirectCallers(Old: G, New: F);
912 if (isODR(F))
913 replaceDirectCallers(Old: NewF, New: F);
914
915 // We collect alignment before writeThunkOrAliasIfNeeded that overwrites
916 // NewF and G's content.
917 const MaybeAlign NewFAlign = NewF->getAlign();
918 const MaybeAlign GAlign = G->getAlign();
919
920 writeThunkOrAliasIfNeeded(F, G);
921 writeThunkOrAliasIfNeeded(F, G: NewF);
922
923 if (NewFAlign || GAlign)
924 F->setAlignment(std::max(a: NewFAlign.valueOrOne(), b: GAlign.valueOrOne()));
925 else
926 F->setAlignment(std::nullopt);
927 F->setLinkage(GlobalValue::PrivateLinkage);
928 ++NumDoubleWeak;
929 ++NumFunctionsMerged;
930 } else {
931 // For better debugability, under MergeFunctionsPDI, we do not modify G's
932 // call sites to point to F even when within the same translation unit.
933 if (!G->isInterposable() && !MergeFunctionsPDI) {
934 // Functions referred to by llvm.used/llvm.compiler.used are special:
935 // there are uses of the symbol name that are not visible to LLVM,
936 // usually from inline asm.
937 if (G->hasGlobalUnnamedAddr() && !Used.contains(Ptr: G)) {
938 // G might have been a key in our GlobalNumberState, and it's illegal
939 // to replace a key in ValueMap<GlobalValue *> with a non-global.
940 GlobalNumbers.erase(Global: G);
941 // If G's address is not significant, replace it entirely.
942 removeUsers(V: G);
943 G->replaceAllUsesWith(V: F);
944 } else {
945 // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
946 // above).
947 replaceDirectCallers(Old: G, New: F);
948 }
949 }
950
951 // If G was internal then we may have replaced all uses of G with F. If so,
952 // stop here and delete G. There's no need for a thunk. (See note on
953 // MergeFunctionsPDI above).
954 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
955 G->eraseFromParent();
956 ++NumFunctionsMerged;
957 return;
958 }
959
960 if (writeThunkOrAliasIfNeeded(F, G)) {
961 ++NumFunctionsMerged;
962 }
963 }
964}
965
966/// Replace function F by function G.
967void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
968 Function *G) {
969 Function *F = FN.getFunc();
970 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
971 "The two functions must be equal");
972
973 auto I = FNodesInTree.find(Val: F);
974 assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
975 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
976
977 FnTreeType::iterator IterToFNInFnTree = I->second;
978 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
979 // Remove F -> FN and insert G -> FN
980 FNodesInTree.erase(I);
981 FNodesInTree.insert(KV: {G, IterToFNInFnTree});
982 // Replace F with G in FN, which is stored inside the FnTree.
983 FN.replaceBy(G);
984}
985
986// Ordering for functions that are equal under FunctionComparator
987static bool isFuncOrderCorrect(const Function *F, const Function *G) {
988 if (isODR(F) != isODR(F: G)) {
989 // ODR functions before non-ODR functions. A ODR function can call a non-ODR
990 // function if it is not interposable, but not the other way around.
991 return isODR(F: G);
992 }
993
994 if (F->isInterposable() != G->isInterposable()) {
995 // Strong before weak, because the weak function may call the strong
996 // one, but not the other way around.
997 return !F->isInterposable();
998 }
999
1000 if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
1001 // External before local, because we definitely have to keep the external
1002 // function, but may be able to drop the local one.
1003 return !F->hasLocalLinkage();
1004 }
1005
1006 // Impose a total order (by name) on the replacement of functions. This is
1007 // important when operating on more than one module independently to prevent
1008 // cycles of thunks calling each other when the modules are linked together.
1009 return F->getName() <= G->getName();
1010}
1011
1012// Insert a ComparableFunction into the FnTree, or merge it away if equal to one
1013// that was already inserted.
1014bool MergeFunctions::insert(Function *NewFunction) {
1015 std::pair<FnTreeType::iterator, bool> Result =
1016 FnTree.insert(x: FunctionNode(NewFunction));
1017
1018 if (Result.second) {
1019 assert(FNodesInTree.count(NewFunction) == 0);
1020 FNodesInTree.insert(KV: {NewFunction, Result.first});
1021 LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
1022 << '\n');
1023 return false;
1024 }
1025
1026 const FunctionNode &OldF = *Result.first;
1027
1028 if (!isFuncOrderCorrect(F: OldF.getFunc(), G: NewFunction)) {
1029 // Swap the two functions.
1030 Function *F = OldF.getFunc();
1031 replaceFunctionInTree(FN: *Result.first, G: NewFunction);
1032 NewFunction = F;
1033 assert(OldF.getFunc() != F && "Must have swapped the functions.");
1034 }
1035
1036 // Capture the Function pointer before mergeTwoFunctions, which may invalidate
1037 // OldF by erasing it from FnTree via removeUsers().
1038 Function *OldFunc = OldF.getFunc();
1039
1040 LLVM_DEBUG(dbgs() << " " << OldFunc->getName()
1041 << " == " << NewFunction->getName() << '\n');
1042
1043 Function *DeleteF = NewFunction;
1044 mergeTwoFunctions(F: OldFunc, G: DeleteF);
1045 this->DelToNewMap.insert(KV: {DeleteF, OldFunc});
1046 return true;
1047}
1048
1049// Remove a function from FnTree. If it was already in FnTree, add
1050// it to Deferred so that we'll look at it in the next round.
1051void MergeFunctions::remove(Function *F) {
1052 auto I = FNodesInTree.find(Val: F);
1053 if (I != FNodesInTree.end()) {
1054 LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
1055 FnTree.erase(position: I->second);
1056 // I->second has been invalidated, remove it from the FNodesInTree map to
1057 // preserve the invariant.
1058 FNodesInTree.erase(I);
1059 Deferred.emplace_back(args&: F);
1060 }
1061}
1062
1063// For each instruction used by the value, remove() the function that contains
1064// the instruction. This should happen right before a call to RAUW.
1065void MergeFunctions::removeUsers(Value *V) {
1066 for (User *U : V->users())
1067 if (auto *I = dyn_cast<Instruction>(Val: U))
1068 remove(F: I->getFunction());
1069}
1070