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.instructionsWithoutDebug()) {
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 !hasDistinctMetadataIntrinsic(F);
432}
433
434inline Function *asPtr(Function *Fn) { return Fn; }
435inline Function *asPtr(Function &Fn) { return &Fn; }
436
437template <typename FuncContainer> bool MergeFunctions::run(FuncContainer &M) {
438 bool Changed = false;
439
440 // All functions in the module, ordered by hash. Functions with a unique
441 // hash value are easily eliminated.
442 std::vector<std::pair<stable_hash, Function *>> HashedFuncs;
443 for (auto &Func : M) {
444 Function *FuncPtr = asPtr(Func);
445 if (isEligibleForMerging(F&: *FuncPtr)) {
446 HashedFuncs.push_back(x: {StructuralHash(F: *FuncPtr), FuncPtr});
447 }
448 }
449
450 llvm::stable_sort(Range&: HashedFuncs, C: less_first());
451
452 auto S = HashedFuncs.begin();
453 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
454 // If the hash value matches the previous value or the next one, we must
455 // consider merging it. Otherwise it is dropped and never considered again.
456 if ((I != S && std::prev(x: I)->first == I->first) ||
457 (std::next(x: I) != IE && std::next(x: I)->first == I->first)) {
458 Deferred.push_back(x: WeakTrackingVH(I->second));
459 }
460 }
461
462 do {
463 std::vector<WeakTrackingVH> Worklist;
464 Deferred.swap(x&: Worklist);
465
466 LLVM_DEBUG(doFunctionalCheck(Worklist));
467
468 LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
469 LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
470
471 // Insert functions and merge them.
472 for (WeakTrackingVH &I : Worklist) {
473 if (!I)
474 continue;
475 Function *F = cast<Function>(Val&: I);
476 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
477 Changed |= insert(NewFunction: F);
478 }
479 }
480 LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
481 } while (!Deferred.empty());
482
483 FnTree.clear();
484 FNodesInTree.clear();
485 GlobalNumbers.clear();
486 Used.clear();
487
488 return Changed;
489}
490
491DenseMap<Function *, Function *>
492MergeFunctions::runOnFunctions(ArrayRef<Function *> F) {
493 [[maybe_unused]] bool MergeResult = this->run(M&: F);
494 assert(MergeResult == !DelToNewMap.empty());
495 return this->DelToNewMap;
496}
497
498// Replace direct callers of Old with New.
499void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
500 for (Use &U : make_early_inc_range(Range: Old->uses())) {
501 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
502 if (CB && CB->isCallee(U: &U)) {
503 // Do not copy attributes from the called function to the call-site.
504 // Function comparison ensures that the attributes are the same up to
505 // type congruences in byval(), in which case we need to keep the byval
506 // type of the call-site, not the callee function.
507 remove(F: CB->getFunction());
508 U.set(New);
509 }
510 }
511}
512
513// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
514// parameter debug info, from the entry block.
515void MergeFunctions::eraseInstsUnrelatedToPDI(
516 std::vector<Instruction *> &PDIUnrelatedWL,
517 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
518 LLVM_DEBUG(
519 dbgs() << " Erasing instructions (in reverse order of appearance in "
520 "entry block) unrelated to parameter debug info from entry "
521 "block: {\n");
522 while (!PDIUnrelatedWL.empty()) {
523 Instruction *I = PDIUnrelatedWL.back();
524 LLVM_DEBUG(dbgs() << " Deleting Instruction: ");
525 LLVM_DEBUG(I->print(dbgs()));
526 LLVM_DEBUG(dbgs() << "\n");
527 I->eraseFromParent();
528 PDIUnrelatedWL.pop_back();
529 }
530
531 while (!PDVRUnrelatedWL.empty()) {
532 DbgVariableRecord *DVR = PDVRUnrelatedWL.back();
533 LLVM_DEBUG(dbgs() << " Deleting DbgVariableRecord ");
534 LLVM_DEBUG(DVR->print(dbgs()));
535 LLVM_DEBUG(dbgs() << "\n");
536 DVR->eraseFromParent();
537 PDVRUnrelatedWL.pop_back();
538 }
539
540 LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
541 "debug info from entry block. \n");
542}
543
544// Reduce G to its entry block.
545void MergeFunctions::eraseTail(Function *G) {
546 std::vector<BasicBlock *> WorklistBB;
547 for (BasicBlock &BB : drop_begin(RangeOrContainer&: *G)) {
548 BB.dropAllReferences();
549 WorklistBB.push_back(x: &BB);
550 }
551 while (!WorklistBB.empty()) {
552 BasicBlock *BB = WorklistBB.back();
553 BB->eraseFromParent();
554 WorklistBB.pop_back();
555 }
556}
557
558// We are interested in the following instructions from the entry block as being
559// related to parameter debug info:
560// - @llvm.dbg.declare
561// - stores from the incoming parameters to locations on the stack-frame
562// - allocas that create these locations on the stack-frame
563// - @llvm.dbg.value
564// - the entry block's terminator
565// The rest are unrelated to debug info for the parameters; fill up
566// PDIUnrelatedWL with such instructions.
567void MergeFunctions::filterInstsUnrelatedToPDI(
568 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL,
569 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
570 std::set<Instruction *> PDIRelated;
571 std::set<DbgVariableRecord *> PDVRRelated;
572
573 // Work out whether a dbg.value intrinsic or an equivalent DbgVariableRecord
574 // is a parameter to be preserved.
575 auto ExamineDbgValue = [](auto *DbgVal, auto &Container) {
576 LLVM_DEBUG(dbgs() << " Deciding: ");
577 LLVM_DEBUG(DbgVal->print(dbgs()));
578 LLVM_DEBUG(dbgs() << "\n");
579 DILocalVariable *DILocVar = DbgVal->getVariable();
580 if (DILocVar->isParameter()) {
581 LLVM_DEBUG(dbgs() << " Include (parameter): ");
582 LLVM_DEBUG(DbgVal->print(dbgs()));
583 LLVM_DEBUG(dbgs() << "\n");
584 Container.insert(DbgVal);
585 } else {
586 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
587 LLVM_DEBUG(DbgVal->print(dbgs()));
588 LLVM_DEBUG(dbgs() << "\n");
589 }
590 };
591
592 auto ExamineDbgDeclare = [&PDIRelated](auto *DbgDecl, auto &Container) {
593 LLVM_DEBUG(dbgs() << " Deciding: ");
594 LLVM_DEBUG(DbgDecl->print(dbgs()));
595 LLVM_DEBUG(dbgs() << "\n");
596 DILocalVariable *DILocVar = DbgDecl->getVariable();
597 if (DILocVar->isParameter()) {
598 LLVM_DEBUG(dbgs() << " Parameter: ");
599 LLVM_DEBUG(DILocVar->print(dbgs()));
600 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DbgDecl->getAddress());
601 if (AI) {
602 LLVM_DEBUG(dbgs() << " Processing alloca users: ");
603 LLVM_DEBUG(dbgs() << "\n");
604 for (User *U : AI->users()) {
605 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) {
606 if (Value *Arg = SI->getValueOperand()) {
607 if (isa<Argument>(Val: Arg)) {
608 LLVM_DEBUG(dbgs() << " Include: ");
609 LLVM_DEBUG(AI->print(dbgs()));
610 LLVM_DEBUG(dbgs() << "\n");
611 PDIRelated.insert(x: AI);
612 LLVM_DEBUG(dbgs() << " Include (parameter): ");
613 LLVM_DEBUG(SI->print(dbgs()));
614 LLVM_DEBUG(dbgs() << "\n");
615 PDIRelated.insert(x: SI);
616 LLVM_DEBUG(dbgs() << " Include: ");
617 LLVM_DEBUG(DbgDecl->print(dbgs()));
618 LLVM_DEBUG(dbgs() << "\n");
619 Container.insert(DbgDecl);
620 } else {
621 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
622 LLVM_DEBUG(SI->print(dbgs()));
623 LLVM_DEBUG(dbgs() << "\n");
624 }
625 }
626 } else {
627 LLVM_DEBUG(dbgs() << " Defer: ");
628 LLVM_DEBUG(U->print(dbgs()));
629 LLVM_DEBUG(dbgs() << "\n");
630 }
631 }
632 } else {
633 LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");
634 LLVM_DEBUG(DbgDecl->print(dbgs()));
635 LLVM_DEBUG(dbgs() << "\n");
636 }
637 } else {
638 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
639 LLVM_DEBUG(DbgDecl->print(dbgs()));
640 LLVM_DEBUG(dbgs() << "\n");
641 }
642 };
643
644 for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
645 BI != BIE; ++BI) {
646 // Examine DbgVariableRecords as they happen "before" the instruction. Are
647 // they connected to parameters?
648 for (DbgVariableRecord &DVR : filterDbgVars(R: BI->getDbgRecordRange())) {
649 if (DVR.isDbgValue() || DVR.isDbgAssign()) {
650 ExamineDbgValue(&DVR, PDVRRelated);
651 } else {
652 assert(DVR.isDbgDeclare());
653 ExamineDbgDeclare(&DVR, PDVRRelated);
654 }
655 }
656
657 if (auto *DVI = dyn_cast<DbgValueInst>(Val: &*BI)) {
658 ExamineDbgValue(DVI, PDIRelated);
659 } else if (auto *DDI = dyn_cast<DbgDeclareInst>(Val: &*BI)) {
660 ExamineDbgDeclare(DDI, PDIRelated);
661 } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
662 LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
663 LLVM_DEBUG(BI->print(dbgs()));
664 LLVM_DEBUG(dbgs() << "\n");
665 PDIRelated.insert(x: &*BI);
666 } else {
667 LLVM_DEBUG(dbgs() << " Defer: ");
668 LLVM_DEBUG(BI->print(dbgs()));
669 LLVM_DEBUG(dbgs() << "\n");
670 }
671 }
672 LLVM_DEBUG(
673 dbgs()
674 << " Report parameter debug info related/related instructions: {\n");
675
676 auto IsPDIRelated = [](auto *Rec, auto &Container, auto &UnrelatedCont) {
677 if (Container.find(Rec) == Container.end()) {
678 LLVM_DEBUG(dbgs() << " !PDIRelated: ");
679 LLVM_DEBUG(Rec->print(dbgs()));
680 LLVM_DEBUG(dbgs() << "\n");
681 UnrelatedCont.push_back(Rec);
682 } else {
683 LLVM_DEBUG(dbgs() << " PDIRelated: ");
684 LLVM_DEBUG(Rec->print(dbgs()));
685 LLVM_DEBUG(dbgs() << "\n");
686 }
687 };
688
689 // Collect the set of unrelated instructions and debug records.
690 for (Instruction &I : *GEntryBlock) {
691 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange()))
692 IsPDIRelated(&DVR, PDVRRelated, PDVRUnrelatedWL);
693 IsPDIRelated(&I, PDIRelated, PDIUnrelatedWL);
694 }
695 LLVM_DEBUG(dbgs() << " }\n");
696}
697
698/// Whether this function may be replaced by a forwarding thunk.
699static bool canCreateThunkFor(Function *F) {
700 if (F->isVarArg())
701 return false;
702
703 // Don't merge tiny functions using a thunk, since it can just end up
704 // making the function larger.
705 if (F->size() == 1) {
706 if (F->front().sizeWithoutDebug() < 2) {
707 LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()
708 << " is too small to bother creating a thunk for\n");
709 return false;
710 }
711 }
712 return true;
713}
714
715/// Copy all metadata of a specific kind from one function to another.
716static void copyMetadataIfPresent(Function *From, Function *To,
717 StringRef Kind) {
718 SmallVector<MDNode *, 4> MDs;
719 From->getMetadata(Kind, MDs);
720 for (MDNode *MD : MDs)
721 To->addMetadata(Kind, MD&: *MD);
722}
723
724// Replace G with a simple tail call to bitcast(F). Also (unless
725// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
726// delete G. Under MergeFunctionsPDI, we use G itself for creating
727// the thunk as we preserve the debug info (and associated instructions)
728// from G's entry block pertaining to G's incoming arguments which are
729// passed on as corresponding arguments in the call that G makes to F.
730// For better debugability, under MergeFunctionsPDI, we do not modify G's
731// call sites to point to F even when within the same translation unit.
732void MergeFunctions::writeThunk(Function *F, Function *G) {
733 BasicBlock *GEntryBlock = nullptr;
734 std::vector<Instruction *> PDIUnrelatedWL;
735 std::vector<DbgVariableRecord *> PDVRUnrelatedWL;
736 BasicBlock *BB = nullptr;
737 Function *NewG = nullptr;
738 if (MergeFunctionsPDI) {
739 LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
740 "function as thunk; retain original: "
741 << G->getName() << "()\n");
742 GEntryBlock = &G->getEntryBlock();
743 LLVM_DEBUG(
744 dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
745 "debug info for "
746 << G->getName() << "() {\n");
747 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL, PDVRUnrelatedWL);
748 GEntryBlock->getTerminator()->eraseFromParent();
749 BB = GEntryBlock;
750 } else {
751 NewG = Function::Create(Ty: G->getFunctionType(), Linkage: G->getLinkage(),
752 AddrSpace: G->getAddressSpace(), N: "", M: G->getParent());
753 NewG->setComdat(G->getComdat());
754 BB = BasicBlock::Create(Context&: F->getContext(), Name: "", Parent: NewG);
755 }
756
757 IRBuilder<> Builder(BB);
758 Function *H = MergeFunctionsPDI ? G : NewG;
759 SmallVector<Value *, 16> Args;
760 unsigned i = 0;
761 FunctionType *FFTy = F->getFunctionType();
762 for (Argument &AI : H->args()) {
763 Args.push_back(Elt: Builder.CreateAggregateCast(V: &AI, DestTy: FFTy->getParamType(i)));
764 ++i;
765 }
766
767 CallInst *CI = Builder.CreateCall(Callee: F, Args);
768 ReturnInst *RI = nullptr;
769 bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail &&
770 G->getCallingConv() == CallingConv::SwiftTail;
771 CI->setTailCallKind(isSwiftTailCall ? CallInst::TCK_MustTail
772 : CallInst::TCK_Tail);
773 CI->setCallingConv(F->getCallingConv());
774 CI->setAttributes(F->getAttributes());
775 if (H->getReturnType()->isVoidTy()) {
776 RI = Builder.CreateRetVoid();
777 } else {
778 RI = Builder.CreateRet(V: Builder.CreateAggregateCast(V: CI, DestTy: H->getReturnType()));
779 }
780
781 if (MergeFunctionsPDI) {
782 DISubprogram *DIS = G->getSubprogram();
783 if (DIS) {
784 DebugLoc CIDbgLoc =
785 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
786 DebugLoc RIDbgLoc =
787 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
788 CI->setDebugLoc(CIDbgLoc);
789 RI->setDebugLoc(RIDbgLoc);
790 } else {
791 LLVM_DEBUG(
792 dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
793 << G->getName() << "()\n");
794 }
795 eraseTail(G);
796 eraseInstsUnrelatedToPDI(PDIUnrelatedWL, PDVRUnrelatedWL);
797 LLVM_DEBUG(
798 dbgs() << "} // End of parameter related debug info filtering for: "
799 << G->getName() << "()\n");
800 } else {
801 NewG->copyAttributesFrom(Src: G);
802 NewG->takeName(V: G);
803 // Ensure CFI type metadata is propagated to the new function.
804 copyMetadataIfPresent(From: G, To: NewG, Kind: "type");
805 copyMetadataIfPresent(From: G, To: NewG, Kind: "kcfi_type");
806 removeUsers(V: G);
807 G->replaceAllUsesWith(V: NewG);
808 G->eraseFromParent();
809 }
810
811 LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
812 ++NumThunksWritten;
813}
814
815// Whether this function may be replaced by an alias
816static bool canCreateAliasFor(Function *F) {
817 if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
818 return false;
819
820 // We should only see linkages supported by aliases here
821 assert(F->hasLocalLinkage() || F->hasExternalLinkage()
822 || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
823 return true;
824}
825
826// Replace G with an alias to F (deleting function G)
827void MergeFunctions::writeAlias(Function *F, Function *G) {
828 PointerType *PtrType = G->getType();
829 auto *GA = GlobalAlias::create(Ty: G->getValueType(), AddressSpace: PtrType->getAddressSpace(),
830 Linkage: G->getLinkage(), Name: "", Aliasee: F, Parent: G->getParent());
831
832 const MaybeAlign FAlign = F->getAlign();
833 const MaybeAlign GAlign = G->getAlign();
834 if (FAlign || GAlign)
835 F->setAlignment(std::max(a: FAlign.valueOrOne(), b: GAlign.valueOrOne()));
836 else
837 F->setAlignment(std::nullopt);
838 GA->takeName(V: G);
839 GA->setVisibility(G->getVisibility());
840 GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
841
842 removeUsers(V: G);
843 G->replaceAllUsesWith(V: GA);
844 G->eraseFromParent();
845
846 LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
847 ++NumAliasesWritten;
848}
849
850// If needed, replace G with an alias to F if possible, or a thunk to F if
851// profitable. Returns false if neither is the case. If \p G is not needed (i.e.
852// it is discardable and unused), \p G is removed directly.
853bool MergeFunctions::writeThunkOrAliasIfNeeded(Function *F, Function *G) {
854 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
855 G->eraseFromParent();
856 return true;
857 }
858 if (canCreateAliasFor(F: G)) {
859 writeAlias(F, G);
860 return true;
861 }
862 if (canCreateThunkFor(F)) {
863 writeThunk(F, G);
864 return true;
865 }
866 return false;
867}
868
869/// Returns true if \p F is either weak_odr or linkonce_odr.
870static bool isODR(const Function *F) {
871 return F->hasWeakODRLinkage() || F->hasLinkOnceODRLinkage();
872}
873
874// Merge two equivalent functions. Upon completion, Function G is deleted.
875void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
876
877 // Create a new thunk that both F and G can call, if F cannot call G directly.
878 // That is the case if F is either interposable or if G is either weak_odr or
879 // linkonce_odr.
880 if (F->isInterposable() || (isODR(F) && isODR(F: G))) {
881 assert((!isODR(G) || isODR(F)) &&
882 "if G is ODR, F must also be ODR due to ordering");
883
884 // Both writeThunkOrAliasIfNeeded() calls below must succeed, either because
885 // we can create aliases for G and NewF, or because a thunk for F is
886 // profitable. F here has the same signature as NewF below, so that's what
887 // we check.
888 if (!canCreateThunkFor(F) &&
889 (!canCreateAliasFor(F) || !canCreateAliasFor(F: G)))
890 return;
891
892 // Make them both thunks to the same internal function.
893 Function *NewF = Function::Create(Ty: F->getFunctionType(), Linkage: F->getLinkage(),
894 AddrSpace: F->getAddressSpace(), N: "", M: F->getParent());
895 NewF->copyAttributesFrom(Src: F);
896 NewF->takeName(V: F);
897 NewF->setComdat(F->getComdat());
898 F->setComdat(nullptr);
899 // Ensure CFI type metadata is propagated to the new function.
900 copyMetadataIfPresent(From: F, To: NewF, Kind: "type");
901 copyMetadataIfPresent(From: F, To: NewF, Kind: "kcfi_type");
902 removeUsers(V: F);
903 F->replaceAllUsesWith(V: NewF);
904
905 // If G or NewF are (weak|linkonce)_odr, update all callers to call the
906 // thunk.
907 if (isODR(F: G))
908 replaceDirectCallers(Old: G, New: F);
909 if (isODR(F))
910 replaceDirectCallers(Old: NewF, New: F);
911
912 // We collect alignment before writeThunkOrAliasIfNeeded that overwrites
913 // NewF and G's content.
914 const MaybeAlign NewFAlign = NewF->getAlign();
915 const MaybeAlign GAlign = G->getAlign();
916
917 writeThunkOrAliasIfNeeded(F, G);
918 writeThunkOrAliasIfNeeded(F, G: NewF);
919
920 if (NewFAlign || GAlign)
921 F->setAlignment(std::max(a: NewFAlign.valueOrOne(), b: GAlign.valueOrOne()));
922 else
923 F->setAlignment(std::nullopt);
924 F->setLinkage(GlobalValue::PrivateLinkage);
925 ++NumDoubleWeak;
926 ++NumFunctionsMerged;
927 } else {
928 // For better debugability, under MergeFunctionsPDI, we do not modify G's
929 // call sites to point to F even when within the same translation unit.
930 if (!G->isInterposable() && !MergeFunctionsPDI) {
931 // Functions referred to by llvm.used/llvm.compiler.used are special:
932 // there are uses of the symbol name that are not visible to LLVM,
933 // usually from inline asm.
934 if (G->hasGlobalUnnamedAddr() && !Used.contains(Ptr: G)) {
935 // G might have been a key in our GlobalNumberState, and it's illegal
936 // to replace a key in ValueMap<GlobalValue *> with a non-global.
937 GlobalNumbers.erase(Global: G);
938 // If G's address is not significant, replace it entirely.
939 removeUsers(V: G);
940 G->replaceAllUsesWith(V: F);
941 } else {
942 // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
943 // above).
944 replaceDirectCallers(Old: G, New: F);
945 }
946 }
947
948 // If G was internal then we may have replaced all uses of G with F. If so,
949 // stop here and delete G. There's no need for a thunk. (See note on
950 // MergeFunctionsPDI above).
951 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
952 G->eraseFromParent();
953 ++NumFunctionsMerged;
954 return;
955 }
956
957 if (writeThunkOrAliasIfNeeded(F, G)) {
958 ++NumFunctionsMerged;
959 }
960 }
961}
962
963/// Replace function F by function G.
964void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
965 Function *G) {
966 Function *F = FN.getFunc();
967 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
968 "The two functions must be equal");
969
970 auto I = FNodesInTree.find(Val: F);
971 assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
972 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
973
974 FnTreeType::iterator IterToFNInFnTree = I->second;
975 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
976 // Remove F -> FN and insert G -> FN
977 FNodesInTree.erase(I);
978 FNodesInTree.insert(KV: {G, IterToFNInFnTree});
979 // Replace F with G in FN, which is stored inside the FnTree.
980 FN.replaceBy(G);
981}
982
983// Ordering for functions that are equal under FunctionComparator
984static bool isFuncOrderCorrect(const Function *F, const Function *G) {
985 if (isODR(F) != isODR(F: G)) {
986 // ODR functions before non-ODR functions. A ODR function can call a non-ODR
987 // function if it is not interposable, but not the other way around.
988 return isODR(F: G);
989 }
990
991 if (F->isInterposable() != G->isInterposable()) {
992 // Strong before weak, because the weak function may call the strong
993 // one, but not the other way around.
994 return !F->isInterposable();
995 }
996
997 if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
998 // External before local, because we definitely have to keep the external
999 // function, but may be able to drop the local one.
1000 return !F->hasLocalLinkage();
1001 }
1002
1003 // Impose a total order (by name) on the replacement of functions. This is
1004 // important when operating on more than one module independently to prevent
1005 // cycles of thunks calling each other when the modules are linked together.
1006 return F->getName() <= G->getName();
1007}
1008
1009// Insert a ComparableFunction into the FnTree, or merge it away if equal to one
1010// that was already inserted.
1011bool MergeFunctions::insert(Function *NewFunction) {
1012 std::pair<FnTreeType::iterator, bool> Result =
1013 FnTree.insert(x: FunctionNode(NewFunction));
1014
1015 if (Result.second) {
1016 assert(FNodesInTree.count(NewFunction) == 0);
1017 FNodesInTree.insert(KV: {NewFunction, Result.first});
1018 LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
1019 << '\n');
1020 return false;
1021 }
1022
1023 const FunctionNode &OldF = *Result.first;
1024
1025 if (!isFuncOrderCorrect(F: OldF.getFunc(), G: NewFunction)) {
1026 // Swap the two functions.
1027 Function *F = OldF.getFunc();
1028 replaceFunctionInTree(FN: *Result.first, G: NewFunction);
1029 NewFunction = F;
1030 assert(OldF.getFunc() != F && "Must have swapped the functions.");
1031 }
1032
1033 LLVM_DEBUG(dbgs() << " " << OldF.getFunc()->getName()
1034 << " == " << NewFunction->getName() << '\n');
1035
1036 Function *DeleteF = NewFunction;
1037 mergeTwoFunctions(F: OldF.getFunc(), G: DeleteF);
1038 this->DelToNewMap.insert(KV: {DeleteF, OldF.getFunc()});
1039 return true;
1040}
1041
1042// Remove a function from FnTree. If it was already in FnTree, add
1043// it to Deferred so that we'll look at it in the next round.
1044void MergeFunctions::remove(Function *F) {
1045 auto I = FNodesInTree.find(Val: F);
1046 if (I != FNodesInTree.end()) {
1047 LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
1048 FnTree.erase(position: I->second);
1049 // I->second has been invalidated, remove it from the FNodesInTree map to
1050 // preserve the invariant.
1051 FNodesInTree.erase(I);
1052 Deferred.emplace_back(args&: F);
1053 }
1054}
1055
1056// For each instruction used by the value, remove() the function that contains
1057// the instruction. This should happen right before a call to RAUW.
1058void MergeFunctions::removeUsers(Value *V) {
1059 for (User *U : V->users())
1060 if (auto *I = dyn_cast<Instruction>(Val: U))
1061 remove(F: I->getFunction());
1062}
1063