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 // Oracle functions of llvm.speculative.load may only be referenced by
460 // llvm.speculative.load, so they can neither become thunks nor be called.
461 return !F.isDeclaration() && !F.hasAvailableExternallyLinkage() &&
462 !F.hasFnAttribute(Kind: Attribute::NoIPA) &&
463 !F.hasFnAttribute(Kind: "oracle-function") &&
464 !hasDistinctMetadataIntrinsic(F);
465}
466
467inline Function *asPtr(Function *Fn) { return Fn; }
468inline Function *asPtr(Function &Fn) { return &Fn; }
469
470template <typename FuncContainer> bool MergeFunctions::run(FuncContainer &M) {
471 bool Changed = false;
472
473 // All functions in the module, ordered by hash. Functions with a unique
474 // hash value are easily eliminated.
475 std::vector<std::pair<stable_hash, Function *>> HashedFuncs;
476 for (auto &Func : M) {
477 Function *FuncPtr = asPtr(Func);
478 if (isEligibleForMerging(F&: *FuncPtr)) {
479 HashedFuncs.push_back(x: {StructuralHash(F: *FuncPtr), FuncPtr});
480 }
481 }
482
483 llvm::stable_sort(Range&: HashedFuncs, C: less_first());
484
485 auto S = HashedFuncs.begin();
486 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
487 // If the hash value matches the previous value or the next one, we must
488 // consider merging it. Otherwise it is dropped and never considered again.
489 if ((I != S && std::prev(x: I)->first == I->first) ||
490 (std::next(x: I) != IE && std::next(x: I)->first == I->first)) {
491 Deferred.push_back(x: WeakTrackingVH(I->second));
492 }
493 }
494
495 do {
496 std::vector<WeakTrackingVH> Worklist;
497 Deferred.swap(x&: Worklist);
498
499 LLVM_DEBUG(doFunctionalCheck(Worklist));
500
501 LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
502 LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
503
504 // Insert functions and merge them.
505 for (WeakTrackingVH &I : Worklist) {
506 if (!I)
507 continue;
508 Function *F = cast<Function>(Val&: I);
509 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
510 !F->hasFnAttribute(Kind: Attribute::NoIPA)) {
511 Changed |= insert(NewFunction: F);
512 }
513 }
514 LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
515 } while (!Deferred.empty());
516
517 FnTree.clear();
518 FNodesInTree.clear();
519 GlobalNumbers.clear();
520 Used.clear();
521
522 return Changed;
523}
524
525DenseMap<Function *, Function *>
526MergeFunctions::runOnFunctions(ArrayRef<Function *> Funcs) {
527 [[maybe_unused]] bool MergeResult = this->run(M&: Funcs);
528 assert(MergeResult == !DelToNewMap.empty());
529 return this->DelToNewMap;
530}
531
532// Direct calls to Old are about to call New. The verifier requires a location
533// on a call from a function with debug info to a function with debug info, but
534// a call to Old need not have one if Old has no debug info. Give such calls a
535// line 0 location in the caller.
536static void addMissingCallLocations(Function *Old, Function *New) {
537 if (!New->getSubprogram())
538 return;
539 for (Use &U : Old->uses()) {
540 auto *CB = dyn_cast<CallBase>(Val: U.getUser());
541 if (!CB || !CB->isCallee(U: &U) || CB->getDebugLoc())
542 continue;
543 if (DISubprogram *SP = CB->getFunction()->getSubprogram())
544 CB->setDebugLoc(DILocation::get(Context&: CB->getContext(), Line: 0, Column: 0, Scope: SP));
545 }
546}
547
548// Replace direct callers of Old with New.
549void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
550 addMissingCallLocations(Old, New);
551 for (Use &U : make_early_inc_range(Range: Old->uses())) {
552 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
553 if (CB && CB->isCallee(U: &U)) {
554 // Do not copy attributes from the called function to the call-site.
555 // Function comparison ensures that the attributes are the same up to
556 // type congruences in byval(), in which case we need to keep the byval
557 // type of the call-site, not the callee function.
558 remove(F: CB->getFunction());
559 U.set(New);
560 }
561 }
562}
563
564// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
565// parameter debug info, from the entry block.
566void MergeFunctions::eraseInstsUnrelatedToPDI(
567 std::vector<Instruction *> &PDIUnrelatedWL,
568 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
569 LLVM_DEBUG(
570 dbgs() << " Erasing instructions (in reverse order of appearance in "
571 "entry block) unrelated to parameter debug info from entry "
572 "block: {\n");
573 while (!PDIUnrelatedWL.empty()) {
574 Instruction *I = PDIUnrelatedWL.back();
575 LLVM_DEBUG(dbgs() << " Deleting Instruction: ");
576 LLVM_DEBUG(I->print(dbgs()));
577 LLVM_DEBUG(dbgs() << "\n");
578 I->eraseFromParent();
579 PDIUnrelatedWL.pop_back();
580 }
581
582 while (!PDVRUnrelatedWL.empty()) {
583 DbgVariableRecord *DVR = PDVRUnrelatedWL.back();
584 LLVM_DEBUG(dbgs() << " Deleting DbgVariableRecord ");
585 LLVM_DEBUG(DVR->print(dbgs()));
586 LLVM_DEBUG(dbgs() << "\n");
587 DVR->eraseFromParent();
588 PDVRUnrelatedWL.pop_back();
589 }
590
591 LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
592 "debug info from entry block. \n");
593}
594
595// Reduce G to its entry block.
596void MergeFunctions::eraseTail(Function *G) {
597 std::vector<BasicBlock *> WorklistBB;
598 for (BasicBlock &BB : drop_begin(RangeOrContainer&: *G)) {
599 BB.dropAllReferences();
600 WorklistBB.push_back(x: &BB);
601 }
602 while (!WorklistBB.empty()) {
603 BasicBlock *BB = WorklistBB.back();
604 BB->eraseFromParent();
605 WorklistBB.pop_back();
606 }
607}
608
609// We are interested in the following instructions from the entry block as being
610// related to parameter debug info:
611// - @llvm.dbg.declare
612// - stores from the incoming parameters to locations on the stack-frame
613// - allocas that create these locations on the stack-frame
614// - @llvm.dbg.value
615// - the entry block's terminator
616// The rest are unrelated to debug info for the parameters; fill up
617// PDIUnrelatedWL with such instructions.
618void MergeFunctions::filterInstsUnrelatedToPDI(
619 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL,
620 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {
621 std::set<Instruction *> PDIRelated;
622 std::set<DbgVariableRecord *> PDVRRelated;
623
624 // Work out whether a dbg.value intrinsic or an equivalent DbgVariableRecord
625 // is a parameter to be preserved.
626 auto ExamineDbgValue = [&PDVRRelated](DbgVariableRecord *DbgVal) {
627 LLVM_DEBUG(dbgs() << " Deciding: ");
628 LLVM_DEBUG(DbgVal->print(dbgs()));
629 LLVM_DEBUG(dbgs() << "\n");
630 DILocalVariable *DILocVar = DbgVal->getVariable();
631 if (DILocVar->isParameter()) {
632 LLVM_DEBUG(dbgs() << " Include (parameter): ");
633 LLVM_DEBUG(DbgVal->print(dbgs()));
634 LLVM_DEBUG(dbgs() << "\n");
635 PDVRRelated.insert(x: DbgVal);
636 } else {
637 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
638 LLVM_DEBUG(DbgVal->print(dbgs()));
639 LLVM_DEBUG(dbgs() << "\n");
640 }
641 };
642
643 auto ExamineDbgDeclare = [&PDIRelated,
644 &PDVRRelated](DbgVariableRecord *DbgDecl) {
645 LLVM_DEBUG(dbgs() << " Deciding: ");
646 LLVM_DEBUG(DbgDecl->print(dbgs()));
647 LLVM_DEBUG(dbgs() << "\n");
648 DILocalVariable *DILocVar = DbgDecl->getVariable();
649 if (DILocVar->isParameter()) {
650 LLVM_DEBUG(dbgs() << " Parameter: ");
651 LLVM_DEBUG(DILocVar->print(dbgs()));
652 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(Val: DbgDecl->getAddress());
653 if (AI) {
654 LLVM_DEBUG(dbgs() << " Processing alloca users: ");
655 LLVM_DEBUG(dbgs() << "\n");
656 for (User *U : AI->users()) {
657 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) {
658 if (Value *Arg = SI->getValueOperand()) {
659 if (isa<Argument>(Val: Arg)) {
660 LLVM_DEBUG(dbgs() << " Include: ");
661 LLVM_DEBUG(AI->print(dbgs()));
662 LLVM_DEBUG(dbgs() << "\n");
663 PDIRelated.insert(x: AI);
664 LLVM_DEBUG(dbgs() << " Include (parameter): ");
665 LLVM_DEBUG(SI->print(dbgs()));
666 LLVM_DEBUG(dbgs() << "\n");
667 PDIRelated.insert(x: SI);
668 LLVM_DEBUG(dbgs() << " Include: ");
669 LLVM_DEBUG(DbgDecl->print(dbgs()));
670 LLVM_DEBUG(dbgs() << "\n");
671 PDVRRelated.insert(x: DbgDecl);
672 } else {
673 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
674 LLVM_DEBUG(SI->print(dbgs()));
675 LLVM_DEBUG(dbgs() << "\n");
676 }
677 }
678 } else {
679 LLVM_DEBUG(dbgs() << " Defer: ");
680 LLVM_DEBUG(U->print(dbgs()));
681 LLVM_DEBUG(dbgs() << "\n");
682 }
683 }
684 } else {
685 LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");
686 LLVM_DEBUG(DbgDecl->print(dbgs()));
687 LLVM_DEBUG(dbgs() << "\n");
688 }
689 } else {
690 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
691 LLVM_DEBUG(DbgDecl->print(dbgs()));
692 LLVM_DEBUG(dbgs() << "\n");
693 }
694 };
695
696 for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
697 BI != BIE; ++BI) {
698 // Examine DbgVariableRecords as they happen "before" the instruction. Are
699 // they connected to parameters?
700 for (DbgVariableRecord &DVR : filterDbgVars(R: BI->getDbgRecordRange())) {
701 if (DVR.isDbgValue() || DVR.isDbgAssign()) {
702 ExamineDbgValue(&DVR);
703 } else {
704 assert(DVR.isDbgDeclare());
705 ExamineDbgDeclare(&DVR);
706 }
707 }
708
709 if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
710 LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
711 LLVM_DEBUG(BI->print(dbgs()));
712 LLVM_DEBUG(dbgs() << "\n");
713 PDIRelated.insert(x: &*BI);
714 } else {
715 LLVM_DEBUG(dbgs() << " Defer: ");
716 LLVM_DEBUG(BI->print(dbgs()));
717 LLVM_DEBUG(dbgs() << "\n");
718 }
719 }
720 LLVM_DEBUG(
721 dbgs()
722 << " Report parameter debug info related/related instructions: {\n");
723
724 auto IsPDIRelated = [](auto *Rec, auto &Container, auto &UnrelatedCont) {
725 if (Container.find(Rec) == Container.end()) {
726 LLVM_DEBUG(dbgs() << " !PDIRelated: ");
727 LLVM_DEBUG(Rec->print(dbgs()));
728 LLVM_DEBUG(dbgs() << "\n");
729 UnrelatedCont.push_back(Rec);
730 } else {
731 LLVM_DEBUG(dbgs() << " PDIRelated: ");
732 LLVM_DEBUG(Rec->print(dbgs()));
733 LLVM_DEBUG(dbgs() << "\n");
734 }
735 };
736
737 // Collect the set of unrelated instructions and debug records.
738 for (Instruction &I : *GEntryBlock) {
739 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange()))
740 IsPDIRelated(&DVR, PDVRRelated, PDVRUnrelatedWL);
741 IsPDIRelated(&I, PDIRelated, PDIUnrelatedWL);
742 }
743 LLVM_DEBUG(dbgs() << " }\n");
744}
745
746/// Whether this function may be replaced by a forwarding thunk.
747static bool canCreateThunkFor(Function *F) {
748 if (F->isVarArg())
749 return false;
750
751 if (F->hasKernelCallingConv())
752 return false;
753
754 // Don't merge tiny functions using a thunk, since it can just end up
755 // making the function larger.
756 if (F->size() == 1) {
757 if (F->front().size() < 2) {
758 LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()
759 << " is too small to bother creating a thunk for\n");
760 return false;
761 }
762 }
763 return true;
764}
765
766/// Copy all metadata of a specific kind from one function to another.
767static void copyMetadataIfPresent(Function *From, Function *To,
768 StringRef Kind) {
769 SmallVector<MDNode *, 4> MDs;
770 From->getMetadata(Kind, MDs);
771 for (MDNode *MD : MDs)
772 To->addMetadata(Kind, MD&: *MD);
773}
774
775// Replace G with a simple tail call to bitcast(F). Also (unless
776// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
777// delete G. Under MergeFunctionsPDI, we use G itself for creating
778// the thunk as we preserve the debug info (and associated instructions)
779// from G's entry block pertaining to G's incoming arguments which are
780// passed on as corresponding arguments in the call that G makes to F.
781// For better debugability, under MergeFunctionsPDI, we do not modify G's
782// call sites to point to F even when within the same translation unit.
783void MergeFunctions::writeThunk(Function *F, Function *G) {
784 std::optional<uint64_t> GEntryCount = G->getEntryCount();
785 BasicBlock *GEntryBlock = nullptr;
786 std::vector<Instruction *> PDIUnrelatedWL;
787 std::vector<DbgVariableRecord *> PDVRUnrelatedWL;
788 BasicBlock *BB = nullptr;
789 Function *NewG = nullptr;
790 if (MergeFunctionsPDI) {
791 LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
792 "function as thunk; retain original: "
793 << G->getName() << "()\n");
794 GEntryBlock = &G->getEntryBlock();
795 LLVM_DEBUG(
796 dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
797 "debug info for "
798 << G->getName() << "() {\n");
799 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL, PDVRUnrelatedWL);
800 GEntryBlock->getTerminator()->eraseFromParent();
801 BB = GEntryBlock;
802 } else {
803 NewG = Function::Create(Ty: G->getFunctionType(), Linkage: G->getLinkage(),
804 AddrSpace: G->getAddressSpace(), N: "", M: G->getParent());
805 NewG->setComdat(G->getComdat());
806 BB = BasicBlock::Create(Context&: F->getContext(), Name: "", Parent: NewG);
807 }
808
809 IRBuilder<> Builder(BB);
810 Function *H = MergeFunctionsPDI ? G : NewG;
811 SmallVector<Value *, 16> Args;
812 unsigned i = 0;
813 FunctionType *FFTy = F->getFunctionType();
814 for (Argument &AI : H->args()) {
815 Args.push_back(Elt: Builder.CreateAggregateCast(V: &AI, DestTy: FFTy->getParamType(i)));
816 ++i;
817 }
818
819 CallInst *CI = Builder.CreateCall(Callee: F, Args);
820 ReturnInst *RI = nullptr;
821 bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail &&
822 G->getCallingConv() == CallingConv::SwiftTail;
823 CI->setTailCallKind(isSwiftTailCall ? CallInst::TCK_MustTail
824 : CallInst::TCK_Tail);
825 CI->setCallingConv(F->getCallingConv());
826 CI->setAttributes(F->getAttributes());
827 if (H->getReturnType()->isVoidTy()) {
828 RI = Builder.CreateRetVoid();
829 } else {
830 RI = Builder.CreateRet(V: Builder.CreateAggregateCast(V: CI, DestTy: H->getReturnType()));
831 }
832
833 if (MergeFunctionsPDI) {
834 DISubprogram *DIS = G->getSubprogram();
835 if (DIS) {
836 DebugLoc CIDbgLoc =
837 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
838 DebugLoc RIDbgLoc =
839 DILocation::get(Context&: DIS->getContext(), Line: DIS->getScopeLine(), Column: 0, Scope: DIS);
840 CI->setDebugLoc(CIDbgLoc);
841 RI->setDebugLoc(RIDbgLoc);
842 } else {
843 LLVM_DEBUG(
844 dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
845 << G->getName() << "()\n");
846 }
847 eraseTail(G);
848 eraseInstsUnrelatedToPDI(PDIUnrelatedWL, PDVRUnrelatedWL);
849 LLVM_DEBUG(
850 dbgs() << "} // End of parameter related debug info filtering for: "
851 << G->getName() << "()\n");
852 } else {
853 NewG->copyAttributesFrom(Src: G);
854 if (GEntryCount)
855 NewG->setEntryCount(Count: *GEntryCount);
856 NewG->takeName(V: G);
857 // Ensure CFI type metadata is propagated to the new function.
858 copyMetadataIfPresent(From: G, To: NewG, Kind: "type");
859 copyMetadataIfPresent(From: G, To: NewG, Kind: "kcfi_type");
860 copyMetadataIfPresent(From: G, To: NewG, Kind: "callgraph");
861 removeUsers(V: G);
862 G->replaceAllUsesWith(V: NewG);
863 G->eraseFromParent();
864 }
865
866 LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
867 ++NumThunksWritten;
868}
869
870// Whether this function may be replaced by an alias
871static bool canCreateAliasFor(Function *F) {
872 if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
873 return false;
874
875 // We should only see linkages supported by aliases here
876 assert(F->hasLocalLinkage() || F->hasExternalLinkage()
877 || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
878 return true;
879}
880
881static bool hasNonLocalAlias(const Function *F) {
882 for (const GlobalAlias &GA : F->getParent()->aliases())
883 if (!GA.hasLocalLinkage() && GA.getAliaseeObject() == F)
884 return true;
885 return false;
886}
887
888/// A COFF weak external must name its target, and a local symbol has no name
889/// the linker can agree on across objects (LNK1227).
890static bool canBeAliasee(const Function *F) {
891 if (!F->getParent()->getTargetTriple().isOSBinFormatCOFF())
892 return true;
893 return F->hasName() && !F->hasLocalLinkage();
894}
895
896// Replace G with an alias to F (deleting function G)
897void MergeFunctions::writeAlias(Function *F, Function *G) {
898 PointerType *PtrType = G->getType();
899 auto *GA =
900 GlobalAlias::create(Ty: G->getFunctionType(), AddressSpace: PtrType->getAddressSpace(),
901 Linkage: G->getLinkage(), Name: "", Aliasee: F, Parent: G->getParent());
902
903 const MaybeAlign FAlign = F->getAlign();
904 const MaybeAlign GAlign = G->getAlign();
905 if (FAlign || GAlign)
906 F->setAlignment(std::max(a: FAlign.valueOrOne(), b: GAlign.valueOrOne()));
907 else
908 F->setAlignment(std::nullopt);
909 GA->takeName(V: G);
910 GA->setVisibility(G->getVisibility());
911 GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
912
913 removeUsers(V: G);
914 G->replaceAllUsesWith(V: GA);
915 G->eraseFromParent();
916
917 LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
918 ++NumAliasesWritten;
919}
920
921static DenseSet<GlobalValue::GUID> unionImportGUIDs(const Function &F,
922 const Function &G) {
923 DenseSet<GlobalValue::GUID> AllImports = F.getImportGUIDs();
924 DenseSet<GlobalValue::GUID> GImports = G.getImportGUIDs();
925 AllImports.insert(I: GImports.begin(), E: GImports.end());
926 return AllImports;
927}
928
929static void mergeEntryCountsAndImportsInto(Function &F, Function &G) {
930 std::optional<uint64_t> FEntryCount = F.getEntryCount();
931 std::optional<uint64_t> GEntryCount = G.getEntryCount();
932 DenseSet<GlobalValue::GUID> AllImports = unionImportGUIDs(F, G);
933 if (!FEntryCount && !GEntryCount && AllImports.empty())
934 return;
935
936 // -1 is a safe placeholder here, getEntryCount() already treats it as
937 // "unknown" (same sentinel SamplePGO uses for no-sample functions), so
938 // it won't look hot to anyone reading the count back.
939 uint64_t Sum = static_cast<uint64_t>(-1);
940 if (FEntryCount || GEntryCount)
941 Sum = SaturatingAdd(X: FEntryCount ? *FEntryCount : uint64_t{0},
942 Y: GEntryCount ? *GEntryCount : uint64_t{0});
943 F.setEntryCount(Count: Sum, Imports: AllImports.empty() ? nullptr : &AllImports);
944}
945
946bool MergeFunctions::writeThunkOrAliasIfNeeded(Function *F, Function *G) {
947 bool ShouldErase =
948 G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI;
949 bool ShouldAlias = canCreateAliasFor(F: G) && canBeAliasee(F);
950 bool ShouldThunk = canCreateThunkFor(F);
951
952 if (!ShouldErase && !ShouldAlias && !ShouldThunk)
953 return false;
954
955 if (ShouldErase) {
956 G->eraseFromParent();
957 return true;
958 }
959
960 if (ShouldAlias) {
961 writeAlias(F, G);
962 return true;
963 }
964 if (ShouldThunk) {
965 writeThunk(F, G);
966 return true;
967 }
968
969 llvm_unreachable("Erase, alias or thunk must apply");
970}
971
972/// Returns true if \p F is either weak_odr or linkonce_odr.
973static bool isODR(const Function *F) {
974 return F->hasWeakODRLinkage() || F->hasLinkOnceODRLinkage();
975}
976
977static uint64_t getBlockCountForMerging(const BlockFrequencyInfo &BFI,
978 const BasicBlock *BB) {
979 if (auto Count = BFI.getBlockProfileCount(BB))
980 return *Count;
981 return 1;
982}
983
984// The branch weights are relative within a function. Before merging we
985// normalize these to absolute counts.
986// (weight * BlockCount / TotalWeight)
987static uint64_t scaleToBlockCount(uint64_t Weight, uint64_t TotalWeight,
988 uint64_t BlockCount) {
989 if (Weight == 0 || TotalWeight == 0 || BlockCount == 0)
990 return 0;
991 APInt Num(128, BlockCount);
992 Num *= APInt(128, Weight);
993 APInt Den(128, TotalWeight);
994 Num = (Num + Den.lshr(shiftAmt: 1)).udiv(RHS: Den);
995 assert(Num.getActiveBits() <= 64 &&
996 "scaleToBlockCount: result exceeds uint64_t; Weight > TotalWeight?");
997 return Num.getLimitedValue();
998}
999
1000// Combine the scaled branch_weights of corresponding instructions of F and G.
1001static void mergeBranchWeightsOnInstructions(Instruction *DstI,
1002 const Instruction *SrcI,
1003 const BlockFrequencyInfo &DstBFI,
1004 const BlockFrequencyInfo &SrcBFI) {
1005 SmallVector<uint32_t, 8> DstWeights, SrcWeights;
1006 bool HasDst = extractBranchWeights(I: *DstI, Weights&: DstWeights);
1007 bool HasSrc = extractBranchWeights(I: *SrcI, Weights&: SrcWeights);
1008 if (!HasDst && !HasSrc)
1009 return;
1010
1011 uint64_t DstBlockCount = getBlockCountForMerging(BFI: DstBFI, BB: DstI->getParent());
1012 uint64_t SrcBlockCount = getBlockCountForMerging(BFI: SrcBFI, BB: SrcI->getParent());
1013
1014 uint64_t DstTotal = 0, SrcTotal = 0;
1015 if (HasDst)
1016 extractProfTotalWeight(I: *DstI, TotalWeights&: DstTotal);
1017 if (HasSrc)
1018 extractProfTotalWeight(I: *SrcI, TotalWeights&: SrcTotal);
1019
1020 assert((!HasDst || !HasSrc || DstWeights.size() == SrcWeights.size()) &&
1021 "equivalent branch/select instructions must have matching weight "
1022 "arity");
1023 size_t NumWeights = HasDst ? DstWeights.size() : SrcWeights.size();
1024 SmallVector<uint64_t, 8> MergedWeights;
1025 MergedWeights.reserve(N: NumWeights);
1026 for (size_t I = 0; I < NumWeights; ++I) {
1027 uint64_t DstW = HasDst ? DstWeights[I] : 0;
1028 uint64_t SrcW = HasSrc ? SrcWeights[I] : 0;
1029 uint64_t DstAbs = scaleToBlockCount(Weight: DstW, TotalWeight: DstTotal, BlockCount: DstBlockCount);
1030 uint64_t SrcAbs = scaleToBlockCount(Weight: SrcW, TotalWeight: SrcTotal, BlockCount: SrcBlockCount);
1031 MergedWeights.push_back(Elt: SaturatingAdd(X: DstAbs, Y: SrcAbs));
1032 }
1033
1034 bool IsExpected =
1035 hasBranchWeightOrigin(I: *DstI) && hasBranchWeightOrigin(I: *SrcI);
1036 setFittedBranchWeights(I&: *DstI, Weights: MergedWeights, IsExpected);
1037}
1038
1039// Accumulate value profile counts of Instruction I into Merged. Value profile
1040// counts are absolute, not relative branch-style weights.
1041static void addValueProfile(const Instruction &I, InstrProfValueKind Kind,
1042 DenseMap<uint64_t, uint64_t> &Merged) {
1043 uint64_t Total = 0;
1044 SmallVector<InstrProfValueData, 4> VDs =
1045 getValueProfDataFromInst(Inst: I, ValueKind: Kind, /*MaxNumValueData=*/UINT32_MAX, TotalC&: Total);
1046 if (VDs.empty())
1047 return;
1048 for (const InstrProfValueData &VD : VDs)
1049 Merged[VD.Value] = SaturatingAdd(X: Merged[VD.Value], Y: VD.Count);
1050}
1051
1052// Merge (union) value profiles of Dst and Src.
1053static void mergeValueProfileOnInstructions(Instruction *DstI,
1054 const Instruction *SrcI) {
1055 MDNode *DstProf = DstI->getMetadata(KindID: LLVMContext::MD_prof);
1056 MDNode *SrcProf = SrcI->getMetadata(KindID: LLVMContext::MD_prof);
1057 bool HasDst = DstProf && isValueProfileMD(ProfileData: DstProf);
1058 bool HasSrc = SrcProf && isValueProfileMD(ProfileData: SrcProf);
1059 if (!HasDst && !HasSrc)
1060 return;
1061
1062 auto *DstKind =
1063 HasDst ? mdconst::dyn_extract<ConstantInt>(MD: DstProf->getOperand(I: 1))
1064 : nullptr;
1065 auto *SrcKind =
1066 HasSrc ? mdconst::dyn_extract<ConstantInt>(MD: SrcProf->getOperand(I: 1))
1067 : nullptr;
1068 if (HasDst && HasSrc && DstKind && SrcKind &&
1069 DstKind->getZExtValue() != SrcKind->getZExtValue()) {
1070 DstI->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1071 return;
1072 }
1073
1074 const ConstantInt *KindCI = DstKind ? DstKind : SrcKind;
1075 if (!KindCI) {
1076 DstI->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1077 return;
1078 }
1079
1080 InstrProfValueKind Kind =
1081 static_cast<InstrProfValueKind>(KindCI->getZExtValue());
1082
1083 DenseMap<uint64_t, uint64_t> Merged;
1084 if (HasDst)
1085 addValueProfile(I: *DstI, Kind, Merged);
1086 if (HasSrc)
1087 addValueProfile(I: *SrcI, Kind, Merged);
1088
1089 if (Merged.empty())
1090 return;
1091
1092 SmallVector<InstrProfValueData, 8> VDs;
1093 VDs.reserve(N: Merged.size());
1094 uint64_t Sum = 0;
1095 for (auto &[Value, Count] : Merged) {
1096 VDs.push_back(Elt: {.Value: Value, .Count: Count});
1097 Sum = SaturatingAdd(X: Sum, Y: Count);
1098 }
1099 llvm::sort(C&: VDs, Comp: [](const InstrProfValueData &A, const InstrProfValueData &B) {
1100 return A.Count > B.Count;
1101 });
1102 annotateValueSite(M&: *DstI->getFunction()->getParent(), Inst&: *DstI, VDs, Sum, ValueKind: Kind,
1103 MaxMDCount: VDs.size());
1104}
1105
1106void MergeFunctions::mergeInstrAnnotations(Function *Dst, Function *Src) {
1107 const BlockFrequencyInfo &DstBFI =
1108 FAM.getResult<BlockFrequencyAnalysis>(IR&: *Dst);
1109 const BlockFrequencyInfo &SrcBFI =
1110 FAM.getResult<BlockFrequencyAnalysis>(IR&: *Src);
1111
1112 // FunctionComparator guarantees identical CFG topology and instruction
1113 // ordering. Walk the CFGs in RPO rather than function block-list order, as
1114 // equivalent functions need not store their basic blocks in the same order.
1115 ReversePostOrderTraversal<Function *> DstRPOT(Dst);
1116 ReversePostOrderTraversal<Function *> SrcRPOT(Src);
1117 for (auto [DstBB, SrcBB] : llvm::zip_equal(t&: DstRPOT, u&: SrcRPOT)) {
1118 for (auto [DstI, SrcI] : llvm::zip_equal(t&: *DstBB, u&: *SrcBB)) {
1119 // Merge poison-generating flags.
1120 DstI.andIRFlags(V: &SrcI);
1121
1122 MDNode *DstProf = DstI.getMetadata(KindID: LLVMContext::MD_prof);
1123 MDNode *SrcProf = SrcI.getMetadata(KindID: LLVMContext::MD_prof);
1124 if ((DstProf && isValueProfileMD(ProfileData: DstProf)) ||
1125 (SrcProf && isValueProfileMD(ProfileData: SrcProf)))
1126 mergeValueProfileOnInstructions(DstI: &DstI, SrcI: &SrcI);
1127
1128 // Handle branch weights on SelectInsts here. Terminators are handled
1129 // separately below, outside the instruction loop.
1130 if (isa<SelectInst>(Val: DstI))
1131 mergeBranchWeightsOnInstructions(DstI: &DstI, SrcI: &SrcI, DstBFI, SrcBFI);
1132 }
1133 Instruction *DstTerm = DstBB->getTerminator();
1134 const Instruction *SrcTerm = SrcBB->getTerminator();
1135 mergeBranchWeightsOnInstructions(DstI: DstTerm, SrcI: SrcTerm, DstBFI, SrcBFI);
1136 }
1137
1138 PreservedAnalyses PA = PreservedAnalyses::all();
1139 PA.abandon<BranchProbabilityAnalysis>();
1140 PA.abandon<BlockFrequencyAnalysis>();
1141 FAM.invalidate(IR&: *Dst, PA);
1142}
1143
1144// Merge two equivalent functions. Upon completion, Function G is deleted.
1145void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
1146
1147 std::optional<uint64_t> FEntryCount = F->getEntryCount();
1148
1149 // Create a new thunk that both F and G can call, if F cannot call G directly.
1150 // That is the case if F is either interposable or if G is either weak_odr or
1151 // linkonce_odr.
1152 if (F->isInterposable() || (isODR(F) && isODR(F: G))) {
1153 assert((!isODR(G) || isODR(F)) &&
1154 "if G is ODR, F must also be ODR due to ordering");
1155
1156 // Both writeThunkOrAliasIfNeeded() calls below must succeed, either because
1157 // we can create aliases for G and NewF, or because a thunk for F is
1158 // profitable. F here has the same signature as NewF below, so that's what
1159 // we check.
1160 if (!canCreateThunkFor(F) &&
1161 (!canCreateAliasFor(F) || !canCreateAliasFor(F: G)))
1162 return;
1163
1164 // Make them both thunks to the same internal function.
1165 Function *NewF = Function::Create(Ty: F->getFunctionType(), Linkage: F->getLinkage(),
1166 AddrSpace: F->getAddressSpace(), N: "", M: F->getParent());
1167 NewF->copyAttributesFrom(Src: F);
1168 NewF->takeName(V: F);
1169 NewF->setComdat(F->getComdat());
1170 F->setComdat(nullptr);
1171 // Ensure CFI type metadata is propagated to the new function.
1172 copyMetadataIfPresent(From: F, To: NewF, Kind: "type");
1173 copyMetadataIfPresent(From: F, To: NewF, Kind: "kcfi_type");
1174 copyMetadataIfPresent(From: F, To: NewF, Kind: "callgraph");
1175 removeUsers(V: F);
1176 F->replaceAllUsesWith(V: NewF);
1177
1178 // If G or NewF are (weak|linkonce)_odr, update all callers to call the
1179 // thunk.
1180 if (isODR(F: G))
1181 replaceDirectCallers(Old: G, New: F);
1182 if (isODR(F))
1183 replaceDirectCallers(Old: NewF, New: F);
1184
1185 // We collect alignment before writeThunkOrAliasIfNeeded that overwrites
1186 // NewF and G's content.
1187 const MaybeAlign NewFAlign = NewF->getAlign();
1188 const MaybeAlign GAlign = G->getAlign();
1189
1190 // Merge annotations, while G still has its body.
1191 mergeInstrAnnotations(Dst: F, Src: G);
1192 mergeEntryCountsAndImportsInto(F&: *F, G&: *G);
1193
1194 writeThunkOrAliasIfNeeded(F, G);
1195 if (FEntryCount)
1196 NewF->setEntryCount(Count: *FEntryCount);
1197 // NewF becomes thunk/alias to the shared body F, it has no annotations to
1198 // be merged.
1199 writeThunkOrAliasIfNeeded(F, G: NewF);
1200
1201 if (NewFAlign || GAlign)
1202 F->setAlignment(std::max(a: NewFAlign.valueOrOne(), b: GAlign.valueOrOne()));
1203 else
1204 F->setAlignment(std::nullopt);
1205 F->setLinkage(GlobalValue::PrivateLinkage);
1206 ++NumDoubleWeak;
1207 ++NumFunctionsMerged;
1208 } else {
1209 // For better debugability, under MergeFunctionsPDI, we do not modify G's
1210 // call sites to point to F even when within the same translation unit.
1211 if (!G->isInterposable() && !MergeFunctionsPDI) {
1212 // Functions referred to by llvm.used/llvm.compiler.used are special:
1213 // there are uses of the symbol name that are not visible to LLVM,
1214 // usually from inline asm.
1215 // Replacing G also retargets G's aliases at F.
1216 if (G->hasGlobalUnnamedAddr() && !Used.contains(Ptr: G) &&
1217 (!hasNonLocalAlias(F: G) || canBeAliasee(F))) {
1218 // G might have been a key in our GlobalNumberState, and it's illegal
1219 // to replace a key in ValueMap<GlobalValue *> with a non-global.
1220 GlobalNumbers.erase(Global: G);
1221 // If G's address is not significant, replace it entirely.
1222 removeUsers(V: G);
1223 addMissingCallLocations(Old: G, New: F);
1224 G->replaceAllUsesWith(V: F);
1225 } else {
1226 // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
1227 // above).
1228 replaceDirectCallers(Old: G, New: F);
1229 }
1230 }
1231
1232 mergeInstrAnnotations(Dst: F, Src: G);
1233 mergeEntryCountsAndImportsInto(F&: *F, G&: *G);
1234
1235 // If G was internal then we may have replaced all uses of G with F. If so,
1236 // stop here and delete G. There's no need for a thunk. (See note on
1237 // MergeFunctionsPDI above).
1238 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
1239 G->eraseFromParent();
1240 ++NumFunctionsMerged;
1241 return;
1242 }
1243
1244 if (writeThunkOrAliasIfNeeded(F, G))
1245 ++NumFunctionsMerged;
1246 }
1247}
1248
1249/// Replace function F by function G.
1250void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
1251 Function *G) {
1252 Function *F = FN.getFunc();
1253 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
1254 "The two functions must be equal");
1255
1256 auto I = FNodesInTree.find(Val: F);
1257 assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
1258 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
1259
1260 FnTreeType::iterator IterToFNInFnTree = I->second;
1261 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
1262 // Remove F -> FN and insert G -> FN
1263 FNodesInTree.erase(I);
1264 FNodesInTree.insert(KV: {G, IterToFNInFnTree});
1265 // Replace F with G in FN, which is stored inside the FnTree.
1266 FN.replaceBy(G);
1267}
1268
1269// Ordering for functions that are equal under FunctionComparator
1270static bool isFuncOrderCorrect(const Function *F, const Function *G) {
1271 if (isODR(F) != isODR(F: G)) {
1272 // ODR functions before non-ODR functions. A ODR function can call a non-ODR
1273 // function if it is not interposable, but not the other way around.
1274 return isODR(F: G);
1275 }
1276
1277 if (F->isInterposable() != G->isInterposable()) {
1278 // Strong before weak, because the weak function may call the strong
1279 // one, but not the other way around.
1280 return !F->isInterposable();
1281 }
1282
1283 if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
1284 // External before local, because we definitely have to keep the external
1285 // function, but may be able to drop the local one.
1286 return !F->hasLocalLinkage();
1287 }
1288
1289 // Impose a total order (by name) on the replacement of functions. This is
1290 // important when operating on more than one module independently to prevent
1291 // cycles of thunks calling each other when the modules are linked together.
1292 return F->getName() <= G->getName();
1293}
1294
1295// Insert a ComparableFunction into the FnTree, or merge it away if equal to one
1296// that was already inserted.
1297bool MergeFunctions::insert(Function *NewFunction) {
1298 std::pair<FnTreeType::iterator, bool> Result =
1299 FnTree.insert(x: FunctionNode(NewFunction));
1300
1301 if (Result.second) {
1302 assert(FNodesInTree.count(NewFunction) == 0);
1303 FNodesInTree.insert(KV: {NewFunction, Result.first});
1304 LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
1305 << '\n');
1306 return false;
1307 }
1308
1309 const FunctionNode &OldF = *Result.first;
1310
1311 if (!isFuncOrderCorrect(F: OldF.getFunc(), G: NewFunction)) {
1312 // Swap the two functions.
1313 Function *F = OldF.getFunc();
1314 replaceFunctionInTree(FN: *Result.first, G: NewFunction);
1315 NewFunction = F;
1316 assert(OldF.getFunc() != F && "Must have swapped the functions.");
1317 }
1318
1319 // Capture the Function pointer before mergeTwoFunctions, which may invalidate
1320 // OldF by erasing it from FnTree via removeUsers().
1321 Function *OldFunc = OldF.getFunc();
1322
1323 LLVM_DEBUG(dbgs() << " " << OldFunc->getName()
1324 << " == " << NewFunction->getName() << '\n');
1325
1326 Function *DeleteF = NewFunction;
1327 mergeTwoFunctions(F: OldFunc, G: DeleteF);
1328 this->DelToNewMap.insert(KV: {DeleteF, OldFunc});
1329 return true;
1330}
1331
1332// Remove a function from FnTree. If it was already in FnTree, add
1333// it to Deferred so that we'll look at it in the next round.
1334void MergeFunctions::remove(Function *F) {
1335 auto I = FNodesInTree.find(Val: F);
1336 if (I != FNodesInTree.end()) {
1337 LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
1338 FnTree.erase(position: I->second);
1339 // I->second has been invalidated, remove it from the FNodesInTree map to
1340 // preserve the invariant.
1341 FNodesInTree.erase(I);
1342 Deferred.emplace_back(args&: F);
1343 }
1344}
1345
1346// For each instruction used by the value, remove() the function that contains
1347// the instruction. This should happen right before a call to RAUW.
1348void MergeFunctions::removeUsers(Value *V) {
1349 for (User *U : V->users())
1350 if (auto *I = dyn_cast<Instruction>(Val: U))
1351 remove(F: I->getFunction());
1352}
1353