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