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