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 "IPOOptions.h"
93#include "llvm/ADT/ArrayRef.h"
94#include "llvm/ADT/DenseMap.h"
95#include "llvm/ADT/DenseSet.h"
96#include "llvm/ADT/PostOrderIterator.h"
97#include "llvm/ADT/STLExtras.h"
98#include "llvm/ADT/SmallVector.h"
99#include "llvm/ADT/Statistic.h"
100#include "llvm/Analysis/BlockFrequencyInfo.h"
101#include "llvm/Analysis/BranchProbabilityInfo.h"
102#include "llvm/IR/Argument.h"
103#include "llvm/IR/BasicBlock.h"
104#include "llvm/IR/DebugInfoMetadata.h"
105#include "llvm/IR/DebugLoc.h"
106#include "llvm/IR/DerivedTypes.h"
107#include "llvm/IR/Function.h"
108#include "llvm/IR/GlobalValue.h"
109#include "llvm/IR/IRBuilder.h"
110#include "llvm/IR/InstrTypes.h"
111#include "llvm/IR/Instruction.h"
112#include "llvm/IR/Instructions.h"
113#include "llvm/IR/IntrinsicInst.h"
114#include "llvm/IR/Metadata.h"
115#include "llvm/IR/Module.h"
116#include "llvm/IR/PassManager.h"
117#include "llvm/IR/ProfDataUtils.h"
118#include "llvm/IR/StructuralHash.h"
119#include "llvm/IR/Type.h"
120#include "llvm/IR/Use.h"
121#include "llvm/IR/User.h"
122#include "llvm/IR/Value.h"
123#include "llvm/IR/ValueHandle.h"
124#include "llvm/ProfileData/InstrProf.h"
125#include "llvm/Support/Casting.h"
126#include "llvm/Support/Debug.h"
127#include "llvm/Support/ErrorHandling.h"
128#include "llvm/Support/MathExtras.h"
129#include "llvm/Support/raw_ostream.h"
130#include "llvm/Transforms/IPO.h"
131#include "llvm/Transforms/Utils/FunctionComparator.h"
132#include "llvm/Transforms/Utils/ModuleUtils.h"
133#include <algorithm>
134#include <cassert>
135#include <cstddef>
136#include <cstdint>
137#include <iterator>
138#include <optional>
139#include <set>
140#include <utility>
141#include <vector>
142
143using namespace llvm;
144
145#define DEBUG_TYPE "mergefunc"
146
147STATISTIC(NumFunctionsMerged, "Number of functions merged");
148STATISTIC(NumThunksWritten, "Number of thunks generated");
149STATISTIC(NumAliasesWritten, "Number of aliases generated");
150STATISTIC(NumDoubleWeak, "Number of new functions created");
151
152namespace {
153
154class FunctionNode {
155 mutable AssertingVH<Function> F;
156 stable_hash Hash;
157
158public:
159 // Note the hash is recalculated potentially multiple times, but it is cheap.
160 FunctionNode(Function *F) : F(F), Hash(StructuralHash(F: *F)) {}
161
162 Function *getFunc() const { return F; }
163 stable_hash getHash() const { return Hash; }
164
165 /// Replace the reference to the function F by the function G, assuming their
166 /// implementations are equal.
167 void replaceBy(Function *G) const {
168 F = G;
169 }
170};
171
172/// MergeFunctions finds functions which will generate identical machine code,
173/// by considering all pointer types to be equivalent. Once identified,
174/// MergeFunctions will fold them by replacing a call to one to a call to a
175/// bitcast of the other.
176class MergeFunctions {
177public:
178 MergeFunctions(const IPOOptions &Opts, FunctionAnalysisManager &FAM)
179 : Opts(Opts), FnTree(FunctionNodeCmp(&GlobalNumbers)), FAM(FAM) {}
180
181 template <typename FuncContainer> bool run(FuncContainer &Functions);
182 DenseMap<Function *, Function *> runOnFunctions(ArrayRef<Function *> Funcs);
183
184 SmallPtrSet<GlobalValue *, 4> &getUsed();
185
186private:
187 const IPOOptions &Opts;
188
189 // The function comparison operator is provided here so that FunctionNodes do
190 // not need to become larger with another pointer.
191 class FunctionNodeCmp {
192 GlobalNumberState* GlobalNumbers;
193
194 public:
195 FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
196
197 bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
198 // Order first by hashes, then full function comparison.
199 if (LHS.getHash() != RHS.getHash())
200 return LHS.getHash() < RHS.getHash();
201 FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
202 return FCmp.compare() < 0;
203 }
204 };
205 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
206
207 GlobalNumberState GlobalNumbers;
208
209 /// A work queue of functions that may have been modified and should be
210 /// analyzed again.
211 std::vector<WeakTrackingVH> Deferred;
212
213 /// Set of values marked as used in llvm.used and llvm.compiler.used.
214 SmallPtrSet<GlobalValue *, 4> Used;
215
216#ifndef NDEBUG
217 /// Checks the rules of order relation introduced among functions set.
218 /// Returns true, if check has been passed, and false if failed.
219 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist);
220#endif
221
222 /// Insert a ComparableFunction into the FnTree, or merge it away if it's
223 /// equal to one that's already present.
224 bool insert(Function *NewFunction);
225
226 /// Remove a Function from the FnTree and queue it up for a second sweep of
227 /// analysis.
228 void remove(Function *F);
229
230 /// Find the functions that use this Value and remove them from FnTree and
231 /// queue the functions.
232 void removeUsers(Value *V);
233
234 /// Replace all direct calls of Old with calls of New. Will bitcast New if
235 /// necessary to make types match.
236 void replaceDirectCallers(Function *Old, Function *New);
237
238 /// Merge two equivalent functions. Upon completion, G may be deleted, or may
239 /// be converted into a thunk. In either case, it should never be visited
240 /// again.
241 void mergeTwoFunctions(Function *F, Function *G);
242
243 /// Merge \p Src's instruction-level annotations into the corresponding
244 /// instructions of \p Dst. \p Dst is the surviving function; \p Src will be
245 /// erased or rewritten after this call.
246 /// Both functions must be structurally identical.
247 void mergeInstrAnnotations(Function *Dst, Function *Src);
248
249 /// Fill PDIUnrelatedWL with instructions from the entry block that are
250 /// unrelated to parameter related debug info.
251 /// \param PDVRUnrelatedWL The equivalent non-intrinsic debug records.
252 void
253 filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,
254 std::vector<Instruction *> &PDIUnrelatedWL,
255 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL);
256
257 /// Erase the rest of the CFG (i.e. barring the entry block).
258 void eraseTail(Function *G);
259
260 /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
261 /// parameter debug info, from the entry block.
262 /// \param PDVRUnrelatedWL contains the equivalent set of non-instruction
263 /// debug-info records.
264 void
265 eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL,
266 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL);
267
268 /// Replace G with a simple tail call to bitcast(F). Also (unless
269 /// -mergefunc-preserve-debug-info is set) replace direct uses of G with
270 /// bitcast(F), delete G.
271 void writeThunk(Function *F, Function *G);
272
273 // Replace G with an alias to F (deleting function G)
274 void writeAlias(Function *F, Function *G);
275
276 // If needed, replace G with an alias to F if possible, or a thunk to F if
277 // profitable. Returns false if neither is the case. If \p G is not needed
278 // (i.e. it is discardable and not used), \p G is removed directly.
279 bool writeThunkOrAliasIfNeeded(Function *F, Function *G);
280
281 /// Replace function F with function G in the function tree.
282 void replaceFunctionInTree(const FunctionNode &FN, Function *G);
283
284 /// The set of all distinct functions. Use the insert() and remove() methods
285 /// to modify it. The map allows efficient lookup and deferring of Functions.
286 FnTreeType FnTree;
287
288 // Map functions to the iterators of the FunctionNode which contains them
289 // in the FnTree. This must be updated carefully whenever the FnTree is
290 // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
291 // dangling iterators into FnTree. The invariant that preserves this is that
292 // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
293 DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
294
295 /// Deleted-New functions mapping
296 DenseMap<Function *, Function *> DelToNewMap;
297
298 FunctionAnalysisManager &FAM;
299};
300} // end anonymous namespace
301
302PreservedAnalyses MergeFunctionsPass::run(Module &M,
303 ModuleAnalysisManager &AM) {
304 if (!MergeFunctionsPass::runOnModule(M, AM))
305 return PreservedAnalyses::all();
306 return PreservedAnalyses::none();
307}
308
309SmallPtrSet<GlobalValue *, 4> &MergeFunctions::getUsed() { return Used; }
310
311bool MergeFunctionsPass::runOnModule(Module &M, ModuleAnalysisManager &AM) {
312 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
313 MergeFunctions MF(getIPOOptions(M), FAM);
314 SmallVector<GlobalValue *, 4> UsedV;
315 collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/false);
316 collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/true);
317 MF.getUsed().insert_range(R&: UsedV);
318 return MF.run(M);
319}
320
321DenseMap<Function *, Function *>
322MergeFunctionsPass::runOnFunctions(ArrayRef<Function *> Funcs,
323 ModuleAnalysisManager &AM) {
324 if (Funcs.empty())
325 return DenseMap<Function *, Function *>();
326
327 Module &M = *Funcs.front()->getParent();
328 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
329 MergeFunctions MF(getIPOOptions(M), FAM);
330 return MF.runOnFunctions(Funcs);
331}
332
333#ifndef NDEBUG
334bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) {
335 if (const unsigned Max = Opts.mergefunc_verify) {
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 (MetadataAsValue *MDL :
416 make_isa_range<MetadataAsValue>(Range: I.operands())) {
417 if (MDNode *N = dyn_cast<MDNode>(Val: MDL->getMetadata()))
418 if (N->isDistinct())
419 return true;
420 }
421 }
422 }
423 return false;
424}
425
426/// Check whether \p F is eligible for function merging.
427static bool isEligibleForMerging(Function &F) {
428 // Oracle functions of llvm.speculative.load may only be referenced by
429 // llvm.speculative.load, so they can neither become thunks nor be called.
430 return !F.isDeclaration() && !F.hasAvailableExternallyLinkage() &&
431 !F.hasFnAttribute(Kind: Attribute::NoIPA) &&
432 !F.hasFnAttribute(Kind: "oracle-function") &&
433 !hasDistinctMetadataIntrinsic(F);
434}
435
436inline Function *asPtr(Function *Fn) { return Fn; }
437inline Function *asPtr(Function &Fn) { return &Fn; }
438
439template <typename FuncContainer> bool MergeFunctions::run(FuncContainer &M) {
440 bool Changed = false;
441
442 // All functions in the module, ordered by hash. Functions with a unique
443 // hash value are easily eliminated.
444 std::vector<std::pair<stable_hash, Function *>> HashedFuncs;
445 for (auto &Func : M) {
446 Function *FuncPtr = asPtr(Func);
447 if (isEligibleForMerging(F&: *FuncPtr)) {
448 HashedFuncs.push_back(x: {StructuralHash(F: *FuncPtr), FuncPtr});
449 }
450 }
451
452 llvm::stable_sort(Range&: HashedFuncs, C: less_first());
453
454 auto S = HashedFuncs.begin();
455 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
456 // If the hash value matches the previous value or the next one, we must
457 // consider merging it. Otherwise it is dropped and never considered again.
458 if ((I != S && std::prev(x: I)->first == I->first) ||
459 (std::next(x: I) != IE && std::next(x: I)->first == I->first)) {
460 Deferred.push_back(x: WeakTrackingVH(I->second));
461 }
462 }
463
464 do {
465 std::vector<WeakTrackingVH> Worklist;
466 Deferred.swap(x&: Worklist);
467
468 LLVM_DEBUG(doFunctionalCheck(Worklist));
469
470 LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
471 LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
472
473 // Insert functions and merge them.
474 for (WeakTrackingVH &I : Worklist) {
475 if (!I)
476 continue;
477 Function *F = cast<Function>(Val&: I);
478 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
479 !F->hasFnAttribute(Kind: Attribute::NoIPA)) {
480 Changed |= insert(NewFunction: F);
481 }
482 }
483 LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
484 } while (!Deferred.empty());
485
486 FnTree.clear();
487 FNodesInTree.clear();
488 GlobalNumbers.clear();
489 Used.clear();
490
491 return Changed;
492}
493
494DenseMap<Function *, Function *>
495MergeFunctions::runOnFunctions(ArrayRef<Function *> Funcs) {
496 [[maybe_unused]] bool MergeResult = this->run(M&: Funcs);
497 assert(MergeResult == !DelToNewMap.empty());
498 return this->DelToNewMap;
499}
500
501// Direct calls to Old are about to call New. The verifier requires a location
502// on a call from a function with debug info to a function with debug info, but
503// a call to Old need not have one if Old has no debug info. Give such calls a
504// line 0 location in the caller.
505static void addMissingCallLocations(Function *Old, Function *New) {
506 if (!New->getSubprogram())
507 return;
508 for (Use &U : Old->uses()) {
509 auto *CB = dyn_cast<CallBase>(Val: U.getUser());
510 if (!CB || !CB->isCallee(U: &U) || CB->getDebugLoc())
511 continue;
512 if (DISubprogram *SP = CB->getFunction()->getSubprogram())
513 CB->setDebugLoc(DILocation::get(Context&: CB->getContext(), Line: 0, Column: 0, Scope: SP));
514 }
515}
516
517// Replace direct callers of Old with New.
518void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
519 addMissingCallLocations(Old, New);
520 for (Use &U : make_early_inc_range(Range: Old->uses())) {
521 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
522 if (CB && CB->isCallee(U: &U)) {
523 // Do not copy attributes from the called function to the call-site.
524 // Function comparison ensures that the attributes are the same up to
525 // type congruences in byval(), in which case we need to keep the byval
526 // type of the call-site, not the callee function.
527 remove(F: CB->getFunction());
528 U.set(New);
529 }
530 }
531}
532
533// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
534// parameter debug info, from the entry block.
535void MergeFunctions::eraseInstsUnrelatedToPDI(
536 std::vector<Instruction *> &PDIUnrelatedWL,
537 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
538 LLVM_DEBUG(
539 dbgs() << " Erasing instructions (in reverse order of appearance in "
540 "entry block) unrelated to parameter debug info from entry "
541 "block: {\n");
542 while (!PDIUnrelatedWL.empty()) {
543 Instruction *I = PDIUnrelatedWL.back();
544 LLVM_DEBUG(dbgs() << " Deleting Instruction: ");
545 LLVM_DEBUG(I->print(dbgs()));
546 LLVM_DEBUG(dbgs() << "\n");
547 I->eraseFromParent();
548 PDIUnrelatedWL.pop_back();
549 }
550
551 while (!PDVRUnrelatedWL.empty()) {
552 DbgVariableRecord *DVR = PDVRUnrelatedWL.back();
553 LLVM_DEBUG(dbgs() << " Deleting DbgVariableRecord ");
554 LLVM_DEBUG(DVR->print(dbgs()));
555 LLVM_DEBUG(dbgs() << "\n");
556 DVR->eraseFromParent();
557 PDVRUnrelatedWL.pop_back();
558 }
559
560 LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
561 "debug info from entry block. \n");
562}
563
564// Reduce G to its entry block.
565void MergeFunctions::eraseTail(Function *G) {
566 std::vector<BasicBlock *> WorklistBB;
567 for (BasicBlock &BB : drop_begin(RangeOrContainer&: *G)) {
568 BB.dropAllReferences();
569 WorklistBB.push_back(x: &BB);
570 }
571 while (!WorklistBB.empty()) {
572 BasicBlock *BB = WorklistBB.back();
573 BB->eraseFromParent();
574 WorklistBB.pop_back();
575 }
576}
577
578// We are interested in the following instructions from the entry block as being
579// related to parameter debug info:
580// - @llvm.dbg.declare
581// - stores from the incoming parameters to locations on the stack-frame
582// - allocas that create these locations on the stack-frame
583// - @llvm.dbg.value
584// - the entry block's terminator
585// The rest are unrelated to debug info for the parameters; fill up
586// PDIUnrelatedWL with such instructions.
587void MergeFunctions::filterInstsUnrelatedToPDI(
588 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL,
589 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
590 std::set<Instruction *> PDIRelated;
591 std::set<DbgVariableRecord *> PDVRRelated;
592
593 // Work out whether a dbg.value intrinsic or an equivalent DbgVariableRecord
594 // is a parameter to be preserved.
595 auto ExamineDbgValue = [&PDVRRelated](DbgVariableRecord *DbgVal) {
596 LLVM_DEBUG(dbgs() << " Deciding: ");
597 LLVM_DEBUG(DbgVal->print(dbgs()));
598 LLVM_DEBUG(dbgs() << "\n");
599 DILocalVariable *DILocVar = DbgVal->getVariable();
600 if (DILocVar->isParameter()) {
601 LLVM_DEBUG(dbgs() << " Include (parameter): ");
602 LLVM_DEBUG(DbgVal->print(dbgs()));
603 LLVM_DEBUG(dbgs() << "\n");
604 PDVRRelated.insert(x: DbgVal);
605 } else {
606 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
607 LLVM_DEBUG(DbgVal->print(dbgs()));
608 LLVM_DEBUG(dbgs() << "\n");
609 }
610 };
611
612 auto ExamineDbgDeclare = [&PDIRelated,
613 &PDVRRelated](DbgVariableRecord *DbgDecl) {
614 LLVM_DEBUG(dbgs() << " Deciding: ");
615 LLVM_DEBUG(DbgDecl->print(dbgs()));
616 LLVM_DEBUG(dbgs() << "\n");
617 DILocalVariable *DILocVar = DbgDecl->getVariable();
618 if (DILocVar->isParameter()) {
619 LLVM_DEBUG(dbgs() << " Parameter: ");
620 LLVM_DEBUG(DILocVar->print(dbgs()));
621 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(Val: DbgDecl->getAddress());
622 if (AI) {
623 LLVM_DEBUG(dbgs() << " Processing alloca users: ");
624 LLVM_DEBUG(dbgs() << "\n");
625 for (User *U : AI->users()) {
626 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) {
627 if (Value *Arg = SI->getValueOperand()) {
628 if (isa<Argument>(Val: Arg)) {
629 LLVM_DEBUG(dbgs() << " Include: ");
630 LLVM_DEBUG(AI->print(dbgs()));
631 LLVM_DEBUG(dbgs() << "\n");
632 PDIRelated.insert(x: AI);
633 LLVM_DEBUG(dbgs() << " Include (parameter): ");
634 LLVM_DEBUG(SI->print(dbgs()));
635 LLVM_DEBUG(dbgs() << "\n");
636 PDIRelated.insert(x: SI);
637 LLVM_DEBUG(dbgs() << " Include: ");
638 LLVM_DEBUG(DbgDecl->print(dbgs()));
639 LLVM_DEBUG(dbgs() << "\n");
640 PDVRRelated.insert(x: DbgDecl);
641 } else {
642 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
643 LLVM_DEBUG(SI->print(dbgs()));
644 LLVM_DEBUG(dbgs() << "\n");
645 }
646 }
647 } else {
648 LLVM_DEBUG(dbgs() << " Defer: ");
649 LLVM_DEBUG(U->print(dbgs()));
650 LLVM_DEBUG(dbgs() << "\n");
651 }
652 }
653 } else {
654 LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");
655 LLVM_DEBUG(DbgDecl->print(dbgs()));
656 LLVM_DEBUG(dbgs() << "\n");
657 }
658 } else {
659 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
660 LLVM_DEBUG(DbgDecl->print(dbgs()));
661 LLVM_DEBUG(dbgs() << "\n");
662 }
663 };
664
665 for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
666 BI != BIE; ++BI) {
667 // Examine DbgVariableRecords as they happen "before" the instruction. Are
668 // they connected to parameters?
669 for (DbgVariableRecord &DVR : filterDbgVars(R: BI->getDbgRecordRange())) {
670 if (DVR.isDbgValue() || DVR.isDbgAssign()) {
671 ExamineDbgValue(&DVR);
672 } else {
673 assert(DVR.isDbgDeclare());
674 ExamineDbgDeclare(&DVR);
675 }
676 }
677
678 if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
679 LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
680 LLVM_DEBUG(BI->print(dbgs()));
681 LLVM_DEBUG(dbgs() << "\n");
682 PDIRelated.insert(x: &*BI);
683 } else {
684 LLVM_DEBUG(dbgs() << " Defer: ");
685 LLVM_DEBUG(BI->print(dbgs()));
686 LLVM_DEBUG(dbgs() << "\n");
687 }
688 }
689 LLVM_DEBUG(
690 dbgs()
691 << " Report parameter debug info related/related instructions: {\n");
692
693 auto IsPDIRelated = [](auto *Rec, auto &Container, auto &UnrelatedCont) {
694 if (Container.find(Rec) == Container.end()) {
695 LLVM_DEBUG(dbgs() << " !PDIRelated: ");
696 LLVM_DEBUG(Rec->print(dbgs()));
697 LLVM_DEBUG(dbgs() << "\n");
698 UnrelatedCont.push_back(Rec);
699 } else {
700 LLVM_DEBUG(dbgs() << " PDIRelated: ");
701 LLVM_DEBUG(Rec->print(dbgs()));
702 LLVM_DEBUG(dbgs() << "\n");
703 }
704 };
705
706 // Collect the set of unrelated instructions and debug records.
707 for (Instruction &I : *GEntryBlock) {
708 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange()))
709 IsPDIRelated(&DVR, PDVRRelated, PDVRUnrelatedWL);
710 IsPDIRelated(&I, PDIRelated, PDIUnrelatedWL);
711 }
712 LLVM_DEBUG(dbgs() << " }\n");
713}
714
715/// Whether this function may be replaced by a forwarding thunk.
716static bool canCreateThunkFor(Function *F) {
717 if (F->isVarArg())
718 return false;
719
720 if (F->hasKernelCallingConv())
721 return false;
722
723 // Don't merge tiny functions using a thunk, since it can just end up
724 // making the function larger.
725 if (F->size() == 1) {
726 if (F->front().size() < 2) {
727 LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()
728 << " is too small to bother creating a thunk for\n");
729 return false;
730 }
731 }
732 return true;
733}
734
735/// Copy all metadata of a specific kind from one function to another.
736static void copyMetadataIfPresent(Function *From, Function *To,
737 StringRef Kind) {
738 SmallVector<MDNode *, 4> MDs;
739 From->getMetadata(Kind, MDs);
740 for (MDNode *MD : MDs)
741 To->addMetadata(Kind, MD&: *MD);
742}
743
744// Replace G with a simple tail call to bitcast(F). Also (unless
745// -mergefunc-preserve-debug-info is set) replace direct uses of G with
746// bitcast(F), delete G. Under -mergefunc-preserve-debug-info, we use G itself
747// for creating the thunk as we preserve the debug info (and associated
748// instructions) from G's entry block pertaining to G's incoming arguments
749// which are passed on as corresponding arguments in the call that G makes to F.
750// For better debugability, under -mergefunc-preserve-debug-info, we do not
751// modify G's call sites to point to F even when within the same translation
752// unit.
753void MergeFunctions::writeThunk(Function *F, Function *G) {
754 std::optional<uint64_t> GEntryCount = G->getEntryCount();
755 BasicBlock *GEntryBlock = nullptr;
756 std::vector<Instruction *> PDIUnrelatedWL;
757 std::vector<DbgVariableRecord *> PDVRUnrelatedWL;
758 BasicBlock *BB = nullptr;
759 Function *NewG = nullptr;
760 if (Opts.mergefunc_preserve_debug_info) {
761 LLVM_DEBUG(dbgs() << "writeThunk: (PDI) Do not create a new "
762 "function as thunk; retain original: "
763 << G->getName() << "()\n");
764 GEntryBlock = &G->getEntryBlock();
765 LLVM_DEBUG(dbgs() << "writeThunk: (PDI) filter parameter related "
766 "debug info for "
767 << G->getName() << "() {\n");
768 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL, PDVRUnrelatedWL);
769 GEntryBlock->getTerminator()->eraseFromParent();
770 BB = GEntryBlock;
771 } else {
772 NewG = Function::Create(Ty: G->getFunctionType(), Linkage: G->getLinkage(),
773 AddrSpace: G->getAddressSpace(), N: "", M: G->getParent());
774 NewG->setComdat(G->getComdat());
775 BB = BasicBlock::Create(Context&: F->getContext(), Name: "", Parent: NewG);
776 }
777
778 IRBuilder<> Builder(BB);
779 Function *H = Opts.mergefunc_preserve_debug_info ? G : NewG;
780 SmallVector<Value *, 16> Args;
781 unsigned i = 0;
782 FunctionType *FFTy = F->getFunctionType();
783 for (Argument &AI : H->args()) {
784 Args.push_back(Elt: Builder.CreateAggregateCast(V: &AI, DestTy: FFTy->getParamType(i)));
785 ++i;
786 }
787
788 CallInst *CI = Builder.CreateCall(Callee: F, Args);
789 ReturnInst *RI = nullptr;
790 bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail &&
791 G->getCallingConv() == CallingConv::SwiftTail;
792 CI->setTailCallKind(isSwiftTailCall ? CallInst::TCK_MustTail
793 : CallInst::TCK_Tail);
794 CI->setCallingConv(F->getCallingConv());
795 CI->setAttributes(F->getAttributes());
796 if (H->getReturnType()->isVoidTy()) {
797 RI = Builder.CreateRetVoid();
798 } else {
799 RI = Builder.CreateRet(V: Builder.CreateAggregateCast(V: CI, DestTy: H->getReturnType()));
800 }
801
802 if (Opts.mergefunc_preserve_debug_info) {
803 DISubprogram *DIS = G->getSubprogram();
804 if (DIS) {
805 DebugLoc CIDbgLoc =
806 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
807 DebugLoc RIDbgLoc =
808 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
809 CI->setDebugLoc(CIDbgLoc);
810 RI->setDebugLoc(RIDbgLoc);
811 } else {
812 LLVM_DEBUG(dbgs() << "writeThunk: (PDI) No DISubprogram for "
813 << G->getName() << "()\n");
814 }
815 eraseTail(G);
816 eraseInstsUnrelatedToPDI(PDIUnrelatedWL, PDVRUnrelatedWL);
817 LLVM_DEBUG(
818 dbgs() << "} // End of parameter related debug info filtering for: "
819 << G->getName() << "()\n");
820 } else {
821 NewG->copyAttributesFrom(Src: G);
822 if (GEntryCount)
823 NewG->setEntryCount(Count: *GEntryCount);
824 NewG->takeName(V: G);
825 // Ensure CFI type metadata is propagated to the new function.
826 copyMetadataIfPresent(From: G, To: NewG, Kind: "type");
827 copyMetadataIfPresent(From: G, To: NewG, Kind: "kcfi_type");
828 copyMetadataIfPresent(From: G, To: NewG, Kind: "callgraph");
829 removeUsers(V: G);
830 G->replaceAllUsesWith(V: NewG);
831 G->eraseFromParent();
832 }
833
834 LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
835 ++NumThunksWritten;
836}
837
838// Whether this function may be replaced by an alias
839static bool canCreateAliasFor(const IPOOptions &Opts, Function *F) {
840 if (!Opts.mergefunc_use_aliases || !F->hasGlobalUnnamedAddr())
841 return false;
842
843 // We should only see linkages supported by aliases here
844 assert(F->hasLocalLinkage() || F->hasExternalLinkage()
845 || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
846 return true;
847}
848
849static bool hasNonLocalAlias(const Function *F) {
850 for (const GlobalAlias &GA : F->getParent()->aliases())
851 if (!GA.hasLocalLinkage() && GA.getAliaseeObject() == F)
852 return true;
853 return false;
854}
855
856/// A COFF weak external must name its target, and a local symbol has no name
857/// the linker can agree on across objects (LNK1227).
858static bool canBeAliasee(const Function *F) {
859 if (!F->getParent()->getTargetTriple().isOSBinFormatCOFF())
860 return true;
861 return F->hasName() && !F->hasLocalLinkage();
862}
863
864// Replace G with an alias to F (deleting function G)
865void MergeFunctions::writeAlias(Function *F, Function *G) {
866 PointerType *PtrType = G->getType();
867 auto *GA =
868 GlobalAlias::create(Ty: G->getFunctionType(), AddressSpace: PtrType->getAddressSpace(),
869 Linkage: G->getLinkage(), Name: "", Aliasee: F, Parent: G->getParent());
870
871 const MaybeAlign FAlign = F->getAlign();
872 const MaybeAlign GAlign = G->getAlign();
873 if (FAlign || GAlign)
874 F->setAlignment(std::max(a: FAlign.valueOrOne(), b: GAlign.valueOrOne()));
875 else
876 F->setAlignment(std::nullopt);
877 GA->takeName(V: G);
878 GA->setVisibility(G->getVisibility());
879 GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
880
881 removeUsers(V: G);
882 G->replaceAllUsesWith(V: GA);
883 G->eraseFromParent();
884
885 LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
886 ++NumAliasesWritten;
887}
888
889static DenseSet<GlobalValue::GUID> unionImportGUIDs(const Function &F,
890 const Function &G) {
891 DenseSet<GlobalValue::GUID> AllImports = F.getImportGUIDs();
892 DenseSet<GlobalValue::GUID> GImports = G.getImportGUIDs();
893 AllImports.insert(I: GImports.begin(), E: GImports.end());
894 return AllImports;
895}
896
897static void mergeEntryCountsAndImportsInto(Function &F, Function &G) {
898 std::optional<uint64_t> FEntryCount = F.getEntryCount();
899 std::optional<uint64_t> GEntryCount = G.getEntryCount();
900 DenseSet<GlobalValue::GUID> AllImports = unionImportGUIDs(F, G);
901 if (!FEntryCount && !GEntryCount && AllImports.empty())
902 return;
903
904 // -1 is a safe placeholder here, getEntryCount() already treats it as
905 // "unknown" (same sentinel SamplePGO uses for no-sample functions), so
906 // it won't look hot to anyone reading the count back.
907 uint64_t Sum = static_cast<uint64_t>(-1);
908 if (FEntryCount || GEntryCount)
909 Sum = SaturatingAdd(X: FEntryCount ? *FEntryCount : uint64_t{0},
910 Y: GEntryCount ? *GEntryCount : uint64_t{0});
911 F.setEntryCount(Count: Sum, Imports: AllImports.empty() ? nullptr : &AllImports);
912}
913
914bool MergeFunctions::writeThunkOrAliasIfNeeded(Function *F, Function *G) {
915 bool ShouldErase = G->isDiscardableIfUnused() && G->use_empty() &&
916 !Opts.mergefunc_preserve_debug_info;
917 bool ShouldAlias = canCreateAliasFor(Opts, F: G) && canBeAliasee(F);
918 bool ShouldThunk = canCreateThunkFor(F);
919
920 if (!ShouldErase && !ShouldAlias && !ShouldThunk)
921 return false;
922
923 if (ShouldErase) {
924 G->eraseFromParent();
925 return true;
926 }
927
928 if (ShouldAlias) {
929 writeAlias(F, G);
930 return true;
931 }
932 if (ShouldThunk) {
933 writeThunk(F, G);
934 return true;
935 }
936
937 llvm_unreachable("Erase, alias or thunk must apply");
938}
939
940/// Returns true if \p F is either weak_odr or linkonce_odr.
941static bool isODR(const Function *F) {
942 return F->hasWeakODRLinkage() || F->hasLinkOnceODRLinkage();
943}
944
945static uint64_t getBlockCountForMerging(const BlockFrequencyInfo &BFI,
946 const BasicBlock *BB) {
947 if (auto Count = BFI.getBlockProfileCount(BB))
948 return *Count;
949 return 1;
950}
951
952// Combine the scaled branch_weights of corresponding instructions of F and G.
953static void mergeBranchWeightsOnInstructions(Instruction *DstI,
954 const Instruction *SrcI,
955 const BlockFrequencyInfo &DstBFI,
956 const BlockFrequencyInfo &SrcBFI) {
957 SmallVector<uint32_t, 8> DstWeights, SrcWeights;
958 bool HasDst = extractBranchWeights(I: *DstI, Weights&: DstWeights);
959 bool HasSrc = extractBranchWeights(I: *SrcI, Weights&: SrcWeights);
960 if (!HasDst && !HasSrc)
961 return;
962
963 uint64_t DstBlockCount = getBlockCountForMerging(BFI: DstBFI, BB: DstI->getParent());
964 uint64_t SrcBlockCount = getBlockCountForMerging(BFI: SrcBFI, BB: SrcI->getParent());
965
966 uint64_t DstTotal = 0, SrcTotal = 0;
967 if (HasDst)
968 extractProfTotalWeight(I: *DstI, TotalWeights&: DstTotal);
969 if (HasSrc)
970 extractProfTotalWeight(I: *SrcI, TotalWeights&: SrcTotal);
971
972 assert((!HasDst || !HasSrc || DstWeights.size() == SrcWeights.size()) &&
973 "equivalent branch/select instructions must have matching weight "
974 "arity");
975 size_t NumWeights = HasDst ? DstWeights.size() : SrcWeights.size();
976 SmallVector<uint64_t, 8> MergedWeights;
977 MergedWeights.reserve(N: NumWeights);
978 for (size_t I = 0; I < NumWeights; ++I) {
979 uint64_t DstW = HasDst ? DstWeights[I] : 0;
980 uint64_t SrcW = HasSrc ? SrcWeights[I] : 0;
981 // The branch weights are relative within a function. Before merging we
982 // normalize these to absolute counts.
983 // (weight * BlockCount / TotalWeight)
984 uint64_t DstAbs =
985 DstTotal == 0 ? 0 : mulDivNearest(X: DstBlockCount, Y: DstW, Z: DstTotal);
986 uint64_t SrcAbs =
987 SrcTotal == 0 ? 0 : mulDivNearest(X: SrcBlockCount, Y: SrcW, Z: SrcTotal);
988 MergedWeights.push_back(Elt: SaturatingAdd(X: DstAbs, Y: SrcAbs));
989 }
990
991 bool IsExpected =
992 hasBranchWeightOrigin(I: *DstI) && hasBranchWeightOrigin(I: *SrcI);
993 setFittedBranchWeights(I&: *DstI, Weights: MergedWeights, IsExpected);
994}
995
996// Accumulate value profile counts of Instruction I into Merged. Value profile
997// counts are absolute, not relative branch-style weights.
998static void addValueProfile(const Instruction &I, InstrProfValueKind Kind,
999 DenseMap<uint64_t, uint64_t> &Merged) {
1000 uint64_t Total = 0;
1001 SmallVector<InstrProfValueData, 4> VDs =
1002 getValueProfDataFromInst(Inst: I, ValueKind: Kind, /*MaxNumValueData=*/UINT32_MAX, TotalC&: Total);
1003 if (VDs.empty())
1004 return;
1005 for (const InstrProfValueData &VD : VDs)
1006 Merged[VD.Value] = SaturatingAdd(X: Merged[VD.Value], Y: VD.Count);
1007}
1008
1009// Merge (union) value profiles of Dst and Src.
1010static void mergeValueProfileOnInstructions(Instruction *DstI,
1011 const Instruction *SrcI) {
1012 MDNode *DstProf = DstI->getMetadata(KindID: LLVMContext::MD_prof);
1013 MDNode *SrcProf = SrcI->getMetadata(KindID: LLVMContext::MD_prof);
1014 bool HasDst = DstProf && isValueProfileMD(ProfileData: DstProf);
1015 bool HasSrc = SrcProf && isValueProfileMD(ProfileData: SrcProf);
1016 if (!HasDst && !HasSrc)
1017 return;
1018
1019 auto *DstKind =
1020 HasDst ? mdconst::dyn_extract<ConstantInt>(MD: DstProf->getOperand(I: 1))
1021 : nullptr;
1022 auto *SrcKind =
1023 HasSrc ? mdconst::dyn_extract<ConstantInt>(MD: SrcProf->getOperand(I: 1))
1024 : nullptr;
1025 if (HasDst && HasSrc && DstKind && SrcKind &&
1026 DstKind->getZExtValue() != SrcKind->getZExtValue()) {
1027 DstI->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1028 return;
1029 }
1030
1031 const ConstantInt *KindCI = DstKind ? DstKind : SrcKind;
1032 if (!KindCI) {
1033 DstI->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1034 return;
1035 }
1036
1037 InstrProfValueKind Kind =
1038 static_cast<InstrProfValueKind>(KindCI->getZExtValue());
1039
1040 DenseMap<uint64_t, uint64_t> Merged;
1041 if (HasDst)
1042 addValueProfile(I: *DstI, Kind, Merged);
1043 if (HasSrc)
1044 addValueProfile(I: *SrcI, Kind, Merged);
1045
1046 if (Merged.empty())
1047 return;
1048
1049 SmallVector<InstrProfValueData, 8> VDs;
1050 VDs.reserve(N: Merged.size());
1051 uint64_t Sum = 0;
1052 for (auto &[Value, Count] : Merged) {
1053 VDs.push_back(Elt: {.Value: Value, .Count: Count});
1054 Sum = SaturatingAdd(X: Sum, Y: Count);
1055 }
1056 llvm::sort(C&: VDs, Comp: [](const InstrProfValueData &A, const InstrProfValueData &B) {
1057 return A.Count > B.Count;
1058 });
1059 annotateValueSite(M&: *DstI->getFunction()->getParent(), Inst&: *DstI, VDs, Sum, ValueKind: Kind,
1060 MaxMDCount: VDs.size());
1061}
1062
1063void MergeFunctions::mergeInstrAnnotations(Function *Dst, Function *Src) {
1064 const BlockFrequencyInfo &DstBFI =
1065 FAM.getResult<BlockFrequencyAnalysis>(IR&: *Dst);
1066 const BlockFrequencyInfo &SrcBFI =
1067 FAM.getResult<BlockFrequencyAnalysis>(IR&: *Src);
1068
1069 // FunctionComparator guarantees identical CFG topology and instruction
1070 // ordering. Walk the CFGs in RPO rather than function block-list order, as
1071 // equivalent functions need not store their basic blocks in the same order.
1072 ReversePostOrderTraversal<Function *> DstRPOT(Dst);
1073 ReversePostOrderTraversal<Function *> SrcRPOT(Src);
1074 for (auto [DstBB, SrcBB] : llvm::zip_equal(t&: DstRPOT, u&: SrcRPOT)) {
1075 for (auto [DstI, SrcI] : llvm::zip_equal(t&: *DstBB, u&: *SrcBB)) {
1076 // Merge poison-generating flags.
1077 DstI.andIRFlags(V: &SrcI);
1078
1079 MDNode *DstProf = DstI.getMetadata(KindID: LLVMContext::MD_prof);
1080 MDNode *SrcProf = SrcI.getMetadata(KindID: LLVMContext::MD_prof);
1081 if ((DstProf && isValueProfileMD(ProfileData: DstProf)) ||
1082 (SrcProf && isValueProfileMD(ProfileData: SrcProf)))
1083 mergeValueProfileOnInstructions(DstI: &DstI, SrcI: &SrcI);
1084
1085 // Handle branch weights on SelectInsts here. Terminators are handled
1086 // separately below, outside the instruction loop.
1087 if (isa<SelectInst>(Val: DstI))
1088 mergeBranchWeightsOnInstructions(DstI: &DstI, SrcI: &SrcI, DstBFI, SrcBFI);
1089 }
1090 Instruction *DstTerm = DstBB->getTerminator();
1091 const Instruction *SrcTerm = SrcBB->getTerminator();
1092 mergeBranchWeightsOnInstructions(DstI: DstTerm, SrcI: SrcTerm, DstBFI, SrcBFI);
1093 }
1094
1095 PreservedAnalyses PA = PreservedAnalyses::all();
1096 PA.abandon<BranchProbabilityAnalysis>();
1097 PA.abandon<BlockFrequencyAnalysis>();
1098 FAM.invalidate(IR&: *Dst, PA);
1099}
1100
1101// Merge two equivalent functions. Upon completion, Function G is deleted.
1102void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
1103
1104 std::optional<uint64_t> FEntryCount = F->getEntryCount();
1105
1106 // Create a new thunk that both F and G can call, if F cannot call G directly.
1107 // That is the case if F is either interposable or if G is either weak_odr or
1108 // linkonce_odr.
1109 if (F->isInterposable() || (isODR(F) && isODR(F: G))) {
1110 assert((!isODR(G) || isODR(F)) &&
1111 "if G is ODR, F must also be ODR due to ordering");
1112
1113 // Both writeThunkOrAliasIfNeeded() calls below must succeed, either because
1114 // we can create aliases for G and NewF, or because a thunk for F is
1115 // profitable. F here has the same signature as NewF below, so that's what
1116 // we check.
1117 if (!canCreateThunkFor(F) &&
1118 (!canCreateAliasFor(Opts, F) || !canCreateAliasFor(Opts, F: G)))
1119 return;
1120
1121 // Make them both thunks to the same internal function.
1122 Function *NewF = Function::Create(Ty: F->getFunctionType(), Linkage: F->getLinkage(),
1123 AddrSpace: F->getAddressSpace(), N: "", M: F->getParent());
1124 NewF->copyAttributesFrom(Src: F);
1125 NewF->takeName(V: F);
1126 NewF->setComdat(F->getComdat());
1127 F->setComdat(nullptr);
1128 // Ensure CFI type metadata is propagated to the new function.
1129 copyMetadataIfPresent(From: F, To: NewF, Kind: "type");
1130 copyMetadataIfPresent(From: F, To: NewF, Kind: "kcfi_type");
1131 copyMetadataIfPresent(From: F, To: NewF, Kind: "callgraph");
1132 removeUsers(V: F);
1133 F->replaceAllUsesWith(V: NewF);
1134
1135 // If G or NewF are (weak|linkonce)_odr, update all callers to call the
1136 // thunk.
1137 if (isODR(F: G))
1138 replaceDirectCallers(Old: G, New: F);
1139 if (isODR(F))
1140 replaceDirectCallers(Old: NewF, New: F);
1141
1142 // We collect alignment before writeThunkOrAliasIfNeeded that overwrites
1143 // NewF and G's content.
1144 const MaybeAlign NewFAlign = NewF->getAlign();
1145 const MaybeAlign GAlign = G->getAlign();
1146
1147 // Merge annotations, while G still has its body.
1148 mergeInstrAnnotations(Dst: F, Src: G);
1149 mergeEntryCountsAndImportsInto(F&: *F, G&: *G);
1150
1151 writeThunkOrAliasIfNeeded(F, G);
1152 if (FEntryCount)
1153 NewF->setEntryCount(Count: *FEntryCount);
1154 // NewF becomes thunk/alias to the shared body F, it has no annotations to
1155 // be merged.
1156 writeThunkOrAliasIfNeeded(F, G: NewF);
1157
1158 if (NewFAlign || GAlign)
1159 F->setAlignment(std::max(a: NewFAlign.valueOrOne(), b: GAlign.valueOrOne()));
1160 else
1161 F->setAlignment(std::nullopt);
1162 F->setLinkage(GlobalValue::PrivateLinkage);
1163 ++NumDoubleWeak;
1164 ++NumFunctionsMerged;
1165 } else {
1166 // For better debugability, under -mergefunc-preserve-debug-info, we do not
1167 // modify G's call sites to point to F even when within the same translation
1168 // unit.
1169 if (!G->isInterposable() && !Opts.mergefunc_preserve_debug_info) {
1170 // Functions referred to by llvm.used/llvm.compiler.used are special:
1171 // there are uses of the symbol name that are not visible to LLVM,
1172 // usually from inline asm.
1173 // Replacing G also retargets G's aliases at F.
1174 if (G->hasGlobalUnnamedAddr() && !Used.contains(Ptr: G) &&
1175 (!hasNonLocalAlias(F: G) || canBeAliasee(F))) {
1176 // G might have been a key in our GlobalNumberState, and it's illegal
1177 // to replace a key in ValueMap<GlobalValue *> with a non-global.
1178 GlobalNumbers.erase(Global: G);
1179 // If G's address is not significant, replace it entirely.
1180 removeUsers(V: G);
1181 addMissingCallLocations(Old: G, New: F);
1182 G->replaceAllUsesWith(V: F);
1183 } else {
1184 // Redirect direct callers of G to F. (See note on
1185 // -mergefunc-preserve-debug-info above).
1186 replaceDirectCallers(Old: G, New: F);
1187 }
1188 }
1189
1190 mergeInstrAnnotations(Dst: F, Src: G);
1191 mergeEntryCountsAndImportsInto(F&: *F, G&: *G);
1192
1193 // If G was internal then we may have replaced all uses of G with F. If so,
1194 // stop here and delete G. There's no need for a thunk. (See note on
1195 // -mergefunc-preserve-debug-info above).
1196 if (G->isDiscardableIfUnused() && G->use_empty() &&
1197 !Opts.mergefunc_preserve_debug_info) {
1198 G->eraseFromParent();
1199 ++NumFunctionsMerged;
1200 return;
1201 }
1202
1203 if (writeThunkOrAliasIfNeeded(F, G))
1204 ++NumFunctionsMerged;
1205 }
1206}
1207
1208/// Replace function F by function G.
1209void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
1210 Function *G) {
1211 Function *F = FN.getFunc();
1212 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
1213 "The two functions must be equal");
1214
1215 auto I = FNodesInTree.find(Val: F);
1216 assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
1217 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
1218
1219 FnTreeType::iterator IterToFNInFnTree = I->second;
1220 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
1221 // Remove F -> FN and insert G -> FN
1222 FNodesInTree.erase(I);
1223 FNodesInTree.insert(KV: {G, IterToFNInFnTree});
1224 // Replace F with G in FN, which is stored inside the FnTree.
1225 FN.replaceBy(G);
1226}
1227
1228// Ordering for functions that are equal under FunctionComparator
1229static bool isFuncOrderCorrect(const Function *F, const Function *G) {
1230 if (isODR(F) != isODR(F: G)) {
1231 // ODR functions before non-ODR functions. A ODR function can call a non-ODR
1232 // function if it is not interposable, but not the other way around.
1233 return isODR(F: G);
1234 }
1235
1236 if (F->isInterposable() != G->isInterposable()) {
1237 // Strong before weak, because the weak function may call the strong
1238 // one, but not the other way around.
1239 return !F->isInterposable();
1240 }
1241
1242 if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
1243 // External before local, because we definitely have to keep the external
1244 // function, but may be able to drop the local one.
1245 return !F->hasLocalLinkage();
1246 }
1247
1248 // Impose a total order (by name) on the replacement of functions. This is
1249 // important when operating on more than one module independently to prevent
1250 // cycles of thunks calling each other when the modules are linked together.
1251 return F->getName() <= G->getName();
1252}
1253
1254// Insert a ComparableFunction into the FnTree, or merge it away if equal to one
1255// that was already inserted.
1256bool MergeFunctions::insert(Function *NewFunction) {
1257 std::pair<FnTreeType::iterator, bool> Result =
1258 FnTree.insert(x: FunctionNode(NewFunction));
1259
1260 if (Result.second) {
1261 assert(FNodesInTree.count(NewFunction) == 0);
1262 FNodesInTree.insert(KV: {NewFunction, Result.first});
1263 LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
1264 << '\n');
1265 return false;
1266 }
1267
1268 const FunctionNode &OldF = *Result.first;
1269
1270 if (!isFuncOrderCorrect(F: OldF.getFunc(), G: NewFunction)) {
1271 // Swap the two functions.
1272 Function *F = OldF.getFunc();
1273 replaceFunctionInTree(FN: *Result.first, G: NewFunction);
1274 NewFunction = F;
1275 assert(OldF.getFunc() != F && "Must have swapped the functions.");
1276 }
1277
1278 // Capture the Function pointer before mergeTwoFunctions, which may invalidate
1279 // OldF by erasing it from FnTree via removeUsers().
1280 Function *OldFunc = OldF.getFunc();
1281
1282 LLVM_DEBUG(dbgs() << " " << OldFunc->getName()
1283 << " == " << NewFunction->getName() << '\n');
1284
1285 Function *DeleteF = NewFunction;
1286 mergeTwoFunctions(F: OldFunc, G: DeleteF);
1287 this->DelToNewMap.insert(KV: {DeleteF, OldFunc});
1288 return true;
1289}
1290
1291// Remove a function from FnTree. If it was already in FnTree, add
1292// it to Deferred so that we'll look at it in the next round.
1293void MergeFunctions::remove(Function *F) {
1294 auto I = FNodesInTree.find(Val: F);
1295 if (I != FNodesInTree.end()) {
1296 LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
1297 FnTree.erase(position: I->second);
1298 // I->second has been invalidated, remove it from the FNodesInTree map to
1299 // preserve the invariant.
1300 FNodesInTree.erase(I);
1301 Deferred.emplace_back(args&: F);
1302 }
1303}
1304
1305// For each instruction used by the value, remove() the function that contains
1306// the instruction. This should happen right before a call to RAUW.
1307void MergeFunctions::removeUsers(Value *V) {
1308 for (User *U : V->users())
1309 if (auto *I = dyn_cast<Instruction>(Val: U))
1310 remove(F: I->getFunction());
1311}
1312