1060 lines · cpp
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-exception6//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 through12// special function comparison procedure that returns13// 0 when functions are equal,14// -1 when Left function is less than right function, and15// 1 for opposite case. We need total-ordering, so we need to maintain16// 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 perform24// 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 every28// 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, and31// two functions are only compared if they have the same hash. This hash is32// cheap to compute, and has the property that if function F == G according to33// the comparison function, then hash(F) == hash(G). This consistency property34// is critical to ensuring all possible merging opportunities are exploited.35// Collisions in the hash affect the speed of the pass but not the correctness36// or determinism of the resulting transformation.37//38// When a match is found the functions are folded. If both functions are39// overridable, we move the functionality into a new internal function and40// 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 for49// the object they belong to. However, as long as it's only used for a lookup50// 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 instructions55// or bitcast constant expressions. Unfortunately, this can confound further56// analysis since the two functions differ where one has a bitcast and the57// 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 that64// 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 previous84// versions of MergeFunctions, though it presented only in two function pairs85// in test-suite (that counts >50k functions)86// Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A)87// could cover much more cases.88//89//===----------------------------------------------------------------------===//90 91#include "llvm/Transforms/IPO/MergeFunctions.h"92#include "llvm/ADT/ArrayRef.h"93#include "llvm/ADT/SmallVector.h"94#include "llvm/ADT/Statistic.h"95#include "llvm/IR/Argument.h"96#include "llvm/IR/BasicBlock.h"97#include "llvm/IR/DebugInfoMetadata.h"98#include "llvm/IR/DebugLoc.h"99#include "llvm/IR/DerivedTypes.h"100#include "llvm/IR/Function.h"101#include "llvm/IR/GlobalValue.h"102#include "llvm/IR/IRBuilder.h"103#include "llvm/IR/InstrTypes.h"104#include "llvm/IR/Instruction.h"105#include "llvm/IR/Instructions.h"106#include "llvm/IR/IntrinsicInst.h"107#include "llvm/IR/Module.h"108#include "llvm/IR/StructuralHash.h"109#include "llvm/IR/Type.h"110#include "llvm/IR/Use.h"111#include "llvm/IR/User.h"112#include "llvm/IR/Value.h"113#include "llvm/IR/ValueHandle.h"114#include "llvm/Support/Casting.h"115#include "llvm/Support/CommandLine.h"116#include "llvm/Support/Debug.h"117#include "llvm/Support/raw_ostream.h"118#include "llvm/Transforms/IPO.h"119#include "llvm/Transforms/Utils/FunctionComparator.h"120#include "llvm/Transforms/Utils/ModuleUtils.h"121#include <algorithm>122#include <cassert>123#include <iterator>124#include <set>125#include <utility>126#include <vector>127 128using namespace llvm;129 130#define DEBUG_TYPE "mergefunc"131 132STATISTIC(NumFunctionsMerged, "Number of functions merged");133STATISTIC(NumThunksWritten, "Number of thunks generated");134STATISTIC(NumAliasesWritten, "Number of aliases generated");135STATISTIC(NumDoubleWeak, "Number of new functions created");136 137static cl::opt<unsigned> NumFunctionsForVerificationCheck(138 "mergefunc-verify",139 cl::desc("How many functions in a module could be used for "140 "MergeFunctions to pass a basic correctness check. "141 "'0' disables this check. Works only with '-debug' key."),142 cl::init(0), cl::Hidden);143 144// Under option -mergefunc-preserve-debug-info we:145// - Do not create a new function for a thunk.146// - Retain the debug info for a thunk's parameters (and associated147// instructions for the debug info) from the entry block.148// Note: -debug will display the algorithm at work.149// - Create debug-info for the call (to the shared implementation) made by150// a thunk and its return value.151// - Erase the rest of the function, retaining the (minimally sized) entry152// block to create a thunk.153// - Preserve a thunk's call site to point to the thunk even when both occur154// within the same translation unit, to aid debugability. Note that this155// behaviour differs from the underlying -mergefunc implementation which156// modifies the thunk's call site to point to the shared implementation157// when both occur within the same translation unit.158static cl::opt<bool>159 MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,160 cl::init(false),161 cl::desc("Preserve debug info in thunk when mergefunc "162 "transformations are made."));163 164static cl::opt<bool>165 MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden,166 cl::init(false),167 cl::desc("Allow mergefunc to create aliases"));168 169namespace {170 171class FunctionNode {172 mutable AssertingVH<Function> F;173 stable_hash Hash;174 175public:176 // Note the hash is recalculated potentially multiple times, but it is cheap.177 FunctionNode(Function *F) : F(F), Hash(StructuralHash(*F)) {}178 179 Function *getFunc() const { return F; }180 stable_hash getHash() const { return Hash; }181 182 /// Replace the reference to the function F by the function G, assuming their183 /// implementations are equal.184 void replaceBy(Function *G) const {185 F = G;186 }187};188 189/// MergeFunctions finds functions which will generate identical machine code,190/// by considering all pointer types to be equivalent. Once identified,191/// MergeFunctions will fold them by replacing a call to one to a call to a192/// bitcast of the other.193class MergeFunctions {194public:195 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {196 }197 198 template <typename FuncContainer> bool run(FuncContainer &Functions);199 DenseMap<Function *, Function *> runOnFunctions(ArrayRef<Function *> F);200 201 SmallPtrSet<GlobalValue *, 4> &getUsed();202 203private:204 // The function comparison operator is provided here so that FunctionNodes do205 // not need to become larger with another pointer.206 class FunctionNodeCmp {207 GlobalNumberState* GlobalNumbers;208 209 public:210 FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}211 212 bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {213 // Order first by hashes, then full function comparison.214 if (LHS.getHash() != RHS.getHash())215 return LHS.getHash() < RHS.getHash();216 FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);217 return FCmp.compare() < 0;218 }219 };220 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;221 222 GlobalNumberState GlobalNumbers;223 224 /// A work queue of functions that may have been modified and should be225 /// analyzed again.226 std::vector<WeakTrackingVH> Deferred;227 228 /// Set of values marked as used in llvm.used and llvm.compiler.used.229 SmallPtrSet<GlobalValue *, 4> Used;230 231#ifndef NDEBUG232 /// Checks the rules of order relation introduced among functions set.233 /// Returns true, if check has been passed, and false if failed.234 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist);235#endif236 237 /// Insert a ComparableFunction into the FnTree, or merge it away if it's238 /// equal to one that's already present.239 bool insert(Function *NewFunction);240 241 /// Remove a Function from the FnTree and queue it up for a second sweep of242 /// analysis.243 void remove(Function *F);244 245 /// Find the functions that use this Value and remove them from FnTree and246 /// queue the functions.247 void removeUsers(Value *V);248 249 /// Replace all direct calls of Old with calls of New. Will bitcast New if250 /// necessary to make types match.251 void replaceDirectCallers(Function *Old, Function *New);252 253 /// Merge two equivalent functions. Upon completion, G may be deleted, or may254 /// be converted into a thunk. In either case, it should never be visited255 /// again.256 void mergeTwoFunctions(Function *F, Function *G);257 258 /// Fill PDIUnrelatedWL with instructions from the entry block that are259 /// unrelated to parameter related debug info.260 /// \param PDVRUnrelatedWL The equivalent non-intrinsic debug records.261 void262 filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,263 std::vector<Instruction *> &PDIUnrelatedWL,264 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL);265 266 /// Erase the rest of the CFG (i.e. barring the entry block).267 void eraseTail(Function *G);268 269 /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the270 /// parameter debug info, from the entry block.271 /// \param PDVRUnrelatedWL contains the equivalent set of non-instruction272 /// debug-info records.273 void274 eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL,275 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL);276 277 /// Replace G with a simple tail call to bitcast(F). Also (unless278 /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),279 /// delete G.280 void writeThunk(Function *F, Function *G);281 282 // Replace G with an alias to F (deleting function G)283 void writeAlias(Function *F, Function *G);284 285 // If needed, replace G with an alias to F if possible, or a thunk to F if286 // profitable. Returns false if neither is the case. If \p G is not needed287 // (i.e. it is discardable and not used), \p G is removed directly.288 bool writeThunkOrAliasIfNeeded(Function *F, Function *G);289 290 /// Replace function F with function G in the function tree.291 void replaceFunctionInTree(const FunctionNode &FN, Function *G);292 293 /// The set of all distinct functions. Use the insert() and remove() methods294 /// to modify it. The map allows efficient lookup and deferring of Functions.295 FnTreeType FnTree;296 297 // Map functions to the iterators of the FunctionNode which contains them298 // in the FnTree. This must be updated carefully whenever the FnTree is299 // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid300 // dangling iterators into FnTree. The invariant that preserves this is that301 // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.302 DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;303 304 /// Deleted-New functions mapping305 DenseMap<Function *, Function *> DelToNewMap;306};307} // end anonymous namespace308 309PreservedAnalyses MergeFunctionsPass::run(Module &M,310 ModuleAnalysisManager &AM) {311 if (!MergeFunctionsPass::runOnModule(M))312 return PreservedAnalyses::all();313 return PreservedAnalyses::none();314}315 316SmallPtrSet<GlobalValue *, 4> &MergeFunctions::getUsed() { return Used; }317 318bool MergeFunctionsPass::runOnModule(Module &M) {319 MergeFunctions MF;320 SmallVector<GlobalValue *, 4> UsedV;321 collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false);322 collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/true);323 MF.getUsed().insert_range(UsedV);324 return MF.run(M);325}326 327DenseMap<Function *, Function *>328MergeFunctionsPass::runOnFunctions(ArrayRef<Function *> F) {329 MergeFunctions MF;330 return MF.runOnFunctions(F);331}332 333#ifndef NDEBUG334bool MergeFunctions::doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist) {335 if (const unsigned Max = NumFunctionsForVerificationCheck) {336 unsigned TripleNumber = 0;337 bool Valid = true;338 339 dbgs() << "MERGEFUNC-VERIFY: Started for first " << Max << " functions.\n";340 341 unsigned i = 0;342 for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),343 E = Worklist.end();344 I != E && i < Max; ++I, ++i) {345 unsigned j = i;346 for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;347 ++J, ++j) {348 Function *F1 = cast<Function>(*I);349 Function *F2 = cast<Function>(*J);350 int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();351 int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();352 353 // If F1 <= F2, then F2 >= F1, otherwise report failure.354 if (Res1 != -Res2) {355 dbgs() << "MERGEFUNC-VERIFY: Non-symmetric; triple: " << TripleNumber356 << "\n";357 dbgs() << *F1 << '\n' << *F2 << '\n';358 Valid = false;359 }360 361 if (Res1 == 0)362 continue;363 364 unsigned k = j;365 for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;366 ++k, ++K, ++TripleNumber) {367 if (K == J)368 continue;369 370 Function *F3 = cast<Function>(*K);371 int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();372 int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();373 374 bool Transitive = true;375 376 if (Res1 != 0 && Res1 == Res4) {377 // F1 > F2, F2 > F3 => F1 > F3378 Transitive = Res3 == Res1;379 } else if (Res3 != 0 && Res3 == -Res4) {380 // F1 > F3, F3 > F2 => F1 > F2381 Transitive = Res3 == Res1;382 } else if (Res4 != 0 && -Res3 == Res4) {383 // F2 > F3, F3 > F1 => F2 > F1384 Transitive = Res4 == -Res1;385 }386 387 if (!Transitive) {388 dbgs() << "MERGEFUNC-VERIFY: Non-transitive; triple: "389 << TripleNumber << "\n";390 dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "391 << Res4 << "\n";392 dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n';393 Valid = false;394 }395 }396 }397 }398 399 dbgs() << "MERGEFUNC-VERIFY: " << (Valid ? "Passed." : "Failed.") << "\n";400 return Valid;401 }402 return true;403}404#endif405 406/// Check whether \p F has an intrinsic which references407/// distinct metadata as an operand. The most common408/// instance of this would be CFI checks for function-local types.409static bool hasDistinctMetadataIntrinsic(const Function &F) {410 for (const BasicBlock &BB : F) {411 for (const Instruction &I : BB.instructionsWithoutDebug()) {412 if (!isa<IntrinsicInst>(&I))413 continue;414 415 for (Value *Op : I.operands()) {416 auto *MDL = dyn_cast<MetadataAsValue>(Op);417 if (!MDL)418 continue;419 if (MDNode *N = dyn_cast<MDNode>(MDL->getMetadata()))420 if (N->isDistinct())421 return true;422 }423 }424 }425 return false;426}427 428/// Check whether \p F is eligible for function merging.429static bool isEligibleForMerging(Function &F) {430 return !F.isDeclaration() && !F.hasAvailableExternallyLinkage() &&431 !hasDistinctMetadataIntrinsic(F);432}433 434inline Function *asPtr(Function *Fn) { return Fn; }435inline Function *asPtr(Function &Fn) { return &Fn; }436 437template <typename FuncContainer> bool MergeFunctions::run(FuncContainer &M) {438 bool Changed = false;439 440 // All functions in the module, ordered by hash. Functions with a unique441 // hash value are easily eliminated.442 std::vector<std::pair<stable_hash, Function *>> HashedFuncs;443 for (auto &Func : M) {444 Function *FuncPtr = asPtr(Func);445 if (isEligibleForMerging(*FuncPtr)) {446 HashedFuncs.push_back({StructuralHash(*FuncPtr), FuncPtr});447 }448 }449 450 llvm::stable_sort(HashedFuncs, less_first());451 452 auto S = HashedFuncs.begin();453 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {454 // If the hash value matches the previous value or the next one, we must455 // consider merging it. Otherwise it is dropped and never considered again.456 if ((I != S && std::prev(I)->first == I->first) ||457 (std::next(I) != IE && std::next(I)->first == I->first)) {458 Deferred.push_back(WeakTrackingVH(I->second));459 }460 }461 462 do {463 std::vector<WeakTrackingVH> Worklist;464 Deferred.swap(Worklist);465 466 LLVM_DEBUG(doFunctionalCheck(Worklist));467 468 LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');469 LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');470 471 // Insert functions and merge them.472 for (WeakTrackingVH &I : Worklist) {473 if (!I)474 continue;475 Function *F = cast<Function>(I);476 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {477 Changed |= insert(F);478 }479 }480 LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');481 } while (!Deferred.empty());482 483 FnTree.clear();484 FNodesInTree.clear();485 GlobalNumbers.clear();486 Used.clear();487 488 return Changed;489}490 491DenseMap<Function *, Function *>492MergeFunctions::runOnFunctions(ArrayRef<Function *> F) {493 [[maybe_unused]] bool MergeResult = this->run(F);494 assert(MergeResult == !DelToNewMap.empty());495 return this->DelToNewMap;496}497 498// Replace direct callers of Old with New.499void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {500 for (Use &U : make_early_inc_range(Old->uses())) {501 CallBase *CB = dyn_cast<CallBase>(U.getUser());502 if (CB && CB->isCallee(&U)) {503 // Do not copy attributes from the called function to the call-site.504 // Function comparison ensures that the attributes are the same up to505 // type congruences in byval(), in which case we need to keep the byval506 // type of the call-site, not the callee function.507 remove(CB->getFunction());508 U.set(New);509 }510 }511}512 513// Erase the instructions in PDIUnrelatedWL as they are unrelated to the514// parameter debug info, from the entry block.515void MergeFunctions::eraseInstsUnrelatedToPDI(516 std::vector<Instruction *> &PDIUnrelatedWL,517 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {518 LLVM_DEBUG(519 dbgs() << " Erasing instructions (in reverse order of appearance in "520 "entry block) unrelated to parameter debug info from entry "521 "block: {\n");522 while (!PDIUnrelatedWL.empty()) {523 Instruction *I = PDIUnrelatedWL.back();524 LLVM_DEBUG(dbgs() << " Deleting Instruction: ");525 LLVM_DEBUG(I->print(dbgs()));526 LLVM_DEBUG(dbgs() << "\n");527 I->eraseFromParent();528 PDIUnrelatedWL.pop_back();529 }530 531 while (!PDVRUnrelatedWL.empty()) {532 DbgVariableRecord *DVR = PDVRUnrelatedWL.back();533 LLVM_DEBUG(dbgs() << " Deleting DbgVariableRecord ");534 LLVM_DEBUG(DVR->print(dbgs()));535 LLVM_DEBUG(dbgs() << "\n");536 DVR->eraseFromParent();537 PDVRUnrelatedWL.pop_back();538 }539 540 LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "541 "debug info from entry block. \n");542}543 544// Reduce G to its entry block.545void MergeFunctions::eraseTail(Function *G) {546 std::vector<BasicBlock *> WorklistBB;547 for (BasicBlock &BB : drop_begin(*G)) {548 BB.dropAllReferences();549 WorklistBB.push_back(&BB);550 }551 while (!WorklistBB.empty()) {552 BasicBlock *BB = WorklistBB.back();553 BB->eraseFromParent();554 WorklistBB.pop_back();555 }556}557 558// We are interested in the following instructions from the entry block as being559// related to parameter debug info:560// - @llvm.dbg.declare561// - stores from the incoming parameters to locations on the stack-frame562// - allocas that create these locations on the stack-frame563// - @llvm.dbg.value564// - the entry block's terminator565// The rest are unrelated to debug info for the parameters; fill up566// PDIUnrelatedWL with such instructions.567void MergeFunctions::filterInstsUnrelatedToPDI(568 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL,569 std::vector<DbgVariableRecord *> &PDVRUnrelatedWL) {570 std::set<Instruction *> PDIRelated;571 std::set<DbgVariableRecord *> PDVRRelated;572 573 // Work out whether a dbg.value intrinsic or an equivalent DbgVariableRecord574 // is a parameter to be preserved.575 auto ExamineDbgValue = [&PDVRRelated](DbgVariableRecord *DbgVal) {576 LLVM_DEBUG(dbgs() << " Deciding: ");577 LLVM_DEBUG(DbgVal->print(dbgs()));578 LLVM_DEBUG(dbgs() << "\n");579 DILocalVariable *DILocVar = DbgVal->getVariable();580 if (DILocVar->isParameter()) {581 LLVM_DEBUG(dbgs() << " Include (parameter): ");582 LLVM_DEBUG(DbgVal->print(dbgs()));583 LLVM_DEBUG(dbgs() << "\n");584 PDVRRelated.insert(DbgVal);585 } else {586 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");587 LLVM_DEBUG(DbgVal->print(dbgs()));588 LLVM_DEBUG(dbgs() << "\n");589 }590 };591 592 auto ExamineDbgDeclare = [&PDIRelated,593 &PDVRRelated](DbgVariableRecord *DbgDecl) {594 LLVM_DEBUG(dbgs() << " Deciding: ");595 LLVM_DEBUG(DbgDecl->print(dbgs()));596 LLVM_DEBUG(dbgs() << "\n");597 DILocalVariable *DILocVar = DbgDecl->getVariable();598 if (DILocVar->isParameter()) {599 LLVM_DEBUG(dbgs() << " Parameter: ");600 LLVM_DEBUG(DILocVar->print(dbgs()));601 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DbgDecl->getAddress());602 if (AI) {603 LLVM_DEBUG(dbgs() << " Processing alloca users: ");604 LLVM_DEBUG(dbgs() << "\n");605 for (User *U : AI->users()) {606 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {607 if (Value *Arg = SI->getValueOperand()) {608 if (isa<Argument>(Arg)) {609 LLVM_DEBUG(dbgs() << " Include: ");610 LLVM_DEBUG(AI->print(dbgs()));611 LLVM_DEBUG(dbgs() << "\n");612 PDIRelated.insert(AI);613 LLVM_DEBUG(dbgs() << " Include (parameter): ");614 LLVM_DEBUG(SI->print(dbgs()));615 LLVM_DEBUG(dbgs() << "\n");616 PDIRelated.insert(SI);617 LLVM_DEBUG(dbgs() << " Include: ");618 LLVM_DEBUG(DbgDecl->print(dbgs()));619 LLVM_DEBUG(dbgs() << "\n");620 PDVRRelated.insert(DbgDecl);621 } else {622 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");623 LLVM_DEBUG(SI->print(dbgs()));624 LLVM_DEBUG(dbgs() << "\n");625 }626 }627 } else {628 LLVM_DEBUG(dbgs() << " Defer: ");629 LLVM_DEBUG(U->print(dbgs()));630 LLVM_DEBUG(dbgs() << "\n");631 }632 }633 } else {634 LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");635 LLVM_DEBUG(DbgDecl->print(dbgs()));636 LLVM_DEBUG(dbgs() << "\n");637 }638 } else {639 LLVM_DEBUG(dbgs() << " Delete (!parameter): ");640 LLVM_DEBUG(DbgDecl->print(dbgs()));641 LLVM_DEBUG(dbgs() << "\n");642 }643 };644 645 for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();646 BI != BIE; ++BI) {647 // Examine DbgVariableRecords as they happen "before" the instruction. Are648 // they connected to parameters?649 for (DbgVariableRecord &DVR : filterDbgVars(BI->getDbgRecordRange())) {650 if (DVR.isDbgValue() || DVR.isDbgAssign()) {651 ExamineDbgValue(&DVR);652 } else {653 assert(DVR.isDbgDeclare());654 ExamineDbgDeclare(&DVR);655 }656 }657 658 if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {659 LLVM_DEBUG(dbgs() << " Will Include Terminator: ");660 LLVM_DEBUG(BI->print(dbgs()));661 LLVM_DEBUG(dbgs() << "\n");662 PDIRelated.insert(&*BI);663 } else {664 LLVM_DEBUG(dbgs() << " Defer: ");665 LLVM_DEBUG(BI->print(dbgs()));666 LLVM_DEBUG(dbgs() << "\n");667 }668 }669 LLVM_DEBUG(670 dbgs()671 << " Report parameter debug info related/related instructions: {\n");672 673 auto IsPDIRelated = [](auto *Rec, auto &Container, auto &UnrelatedCont) {674 if (Container.find(Rec) == Container.end()) {675 LLVM_DEBUG(dbgs() << " !PDIRelated: ");676 LLVM_DEBUG(Rec->print(dbgs()));677 LLVM_DEBUG(dbgs() << "\n");678 UnrelatedCont.push_back(Rec);679 } else {680 LLVM_DEBUG(dbgs() << " PDIRelated: ");681 LLVM_DEBUG(Rec->print(dbgs()));682 LLVM_DEBUG(dbgs() << "\n");683 }684 };685 686 // Collect the set of unrelated instructions and debug records.687 for (Instruction &I : *GEntryBlock) {688 for (DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange()))689 IsPDIRelated(&DVR, PDVRRelated, PDVRUnrelatedWL);690 IsPDIRelated(&I, PDIRelated, PDIUnrelatedWL);691 }692 LLVM_DEBUG(dbgs() << " }\n");693}694 695/// Whether this function may be replaced by a forwarding thunk.696static bool canCreateThunkFor(Function *F) {697 if (F->isVarArg())698 return false;699 700 // Don't merge tiny functions using a thunk, since it can just end up701 // making the function larger.702 if (F->size() == 1) {703 if (F->front().sizeWithoutDebug() < 2) {704 LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()705 << " is too small to bother creating a thunk for\n");706 return false;707 }708 }709 return true;710}711 712/// Copy all metadata of a specific kind from one function to another.713static void copyMetadataIfPresent(Function *From, Function *To,714 StringRef Kind) {715 SmallVector<MDNode *, 4> MDs;716 From->getMetadata(Kind, MDs);717 for (MDNode *MD : MDs)718 To->addMetadata(Kind, *MD);719}720 721// Replace G with a simple tail call to bitcast(F). Also (unless722// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),723// delete G. Under MergeFunctionsPDI, we use G itself for creating724// the thunk as we preserve the debug info (and associated instructions)725// from G's entry block pertaining to G's incoming arguments which are726// passed on as corresponding arguments in the call that G makes to F.727// For better debugability, under MergeFunctionsPDI, we do not modify G's728// call sites to point to F even when within the same translation unit.729void MergeFunctions::writeThunk(Function *F, Function *G) {730 BasicBlock *GEntryBlock = nullptr;731 std::vector<Instruction *> PDIUnrelatedWL;732 std::vector<DbgVariableRecord *> PDVRUnrelatedWL;733 BasicBlock *BB = nullptr;734 Function *NewG = nullptr;735 if (MergeFunctionsPDI) {736 LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "737 "function as thunk; retain original: "738 << G->getName() << "()\n");739 GEntryBlock = &G->getEntryBlock();740 LLVM_DEBUG(741 dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "742 "debug info for "743 << G->getName() << "() {\n");744 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL, PDVRUnrelatedWL);745 GEntryBlock->getTerminator()->eraseFromParent();746 BB = GEntryBlock;747 } else {748 NewG = Function::Create(G->getFunctionType(), G->getLinkage(),749 G->getAddressSpace(), "", G->getParent());750 NewG->setComdat(G->getComdat());751 BB = BasicBlock::Create(F->getContext(), "", NewG);752 }753 754 IRBuilder<> Builder(BB);755 Function *H = MergeFunctionsPDI ? G : NewG;756 SmallVector<Value *, 16> Args;757 unsigned i = 0;758 FunctionType *FFTy = F->getFunctionType();759 for (Argument &AI : H->args()) {760 Args.push_back(Builder.CreateAggregateCast(&AI, FFTy->getParamType(i)));761 ++i;762 }763 764 CallInst *CI = Builder.CreateCall(F, Args);765 ReturnInst *RI = nullptr;766 bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail &&767 G->getCallingConv() == CallingConv::SwiftTail;768 CI->setTailCallKind(isSwiftTailCall ? CallInst::TCK_MustTail769 : CallInst::TCK_Tail);770 CI->setCallingConv(F->getCallingConv());771 CI->setAttributes(F->getAttributes());772 if (H->getReturnType()->isVoidTy()) {773 RI = Builder.CreateRetVoid();774 } else {775 RI = Builder.CreateRet(Builder.CreateAggregateCast(CI, H->getReturnType()));776 }777 778 if (MergeFunctionsPDI) {779 DISubprogram *DIS = G->getSubprogram();780 if (DIS) {781 DebugLoc CIDbgLoc =782 DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS);783 DebugLoc RIDbgLoc =784 DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS);785 CI->setDebugLoc(CIDbgLoc);786 RI->setDebugLoc(RIDbgLoc);787 } else {788 LLVM_DEBUG(789 dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "790 << G->getName() << "()\n");791 }792 eraseTail(G);793 eraseInstsUnrelatedToPDI(PDIUnrelatedWL, PDVRUnrelatedWL);794 LLVM_DEBUG(795 dbgs() << "} // End of parameter related debug info filtering for: "796 << G->getName() << "()\n");797 } else {798 NewG->copyAttributesFrom(G);799 NewG->takeName(G);800 // Ensure CFI type metadata is propagated to the new function.801 copyMetadataIfPresent(G, NewG, "type");802 copyMetadataIfPresent(G, NewG, "kcfi_type");803 removeUsers(G);804 G->replaceAllUsesWith(NewG);805 G->eraseFromParent();806 }807 808 LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');809 ++NumThunksWritten;810}811 812// Whether this function may be replaced by an alias813static bool canCreateAliasFor(Function *F) {814 if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())815 return false;816 817 // We should only see linkages supported by aliases here818 assert(F->hasLocalLinkage() || F->hasExternalLinkage()819 || F->hasWeakLinkage() || F->hasLinkOnceLinkage());820 return true;821}822 823// Replace G with an alias to F (deleting function G)824void MergeFunctions::writeAlias(Function *F, Function *G) {825 PointerType *PtrType = G->getType();826 auto *GA = GlobalAlias::create(G->getValueType(), PtrType->getAddressSpace(),827 G->getLinkage(), "", F, G->getParent());828 829 const MaybeAlign FAlign = F->getAlign();830 const MaybeAlign GAlign = G->getAlign();831 if (FAlign || GAlign)832 F->setAlignment(std::max(FAlign.valueOrOne(), GAlign.valueOrOne()));833 else834 F->setAlignment(std::nullopt);835 GA->takeName(G);836 GA->setVisibility(G->getVisibility());837 GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);838 839 removeUsers(G);840 G->replaceAllUsesWith(GA);841 G->eraseFromParent();842 843 LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');844 ++NumAliasesWritten;845}846 847// If needed, replace G with an alias to F if possible, or a thunk to F if848// profitable. Returns false if neither is the case. If \p G is not needed (i.e.849// it is discardable and unused), \p G is removed directly.850bool MergeFunctions::writeThunkOrAliasIfNeeded(Function *F, Function *G) {851 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {852 G->eraseFromParent();853 return true;854 }855 if (canCreateAliasFor(G)) {856 writeAlias(F, G);857 return true;858 }859 if (canCreateThunkFor(F)) {860 writeThunk(F, G);861 return true;862 }863 return false;864}865 866/// Returns true if \p F is either weak_odr or linkonce_odr.867static bool isODR(const Function *F) {868 return F->hasWeakODRLinkage() || F->hasLinkOnceODRLinkage();869}870 871// Merge two equivalent functions. Upon completion, Function G is deleted.872void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {873 874 // Create a new thunk that both F and G can call, if F cannot call G directly.875 // That is the case if F is either interposable or if G is either weak_odr or876 // linkonce_odr.877 if (F->isInterposable() || (isODR(F) && isODR(G))) {878 assert((!isODR(G) || isODR(F)) &&879 "if G is ODR, F must also be ODR due to ordering");880 881 // Both writeThunkOrAliasIfNeeded() calls below must succeed, either because882 // we can create aliases for G and NewF, or because a thunk for F is883 // profitable. F here has the same signature as NewF below, so that's what884 // we check.885 if (!canCreateThunkFor(F) &&886 (!canCreateAliasFor(F) || !canCreateAliasFor(G)))887 return;888 889 // Make them both thunks to the same internal function.890 Function *NewF = Function::Create(F->getFunctionType(), F->getLinkage(),891 F->getAddressSpace(), "", F->getParent());892 NewF->copyAttributesFrom(F);893 NewF->takeName(F);894 NewF->setComdat(F->getComdat());895 F->setComdat(nullptr);896 // Ensure CFI type metadata is propagated to the new function.897 copyMetadataIfPresent(F, NewF, "type");898 copyMetadataIfPresent(F, NewF, "kcfi_type");899 removeUsers(F);900 F->replaceAllUsesWith(NewF);901 902 // If G or NewF are (weak|linkonce)_odr, update all callers to call the903 // thunk.904 if (isODR(G))905 replaceDirectCallers(G, F);906 if (isODR(F))907 replaceDirectCallers(NewF, F);908 909 // We collect alignment before writeThunkOrAliasIfNeeded that overwrites910 // NewF and G's content.911 const MaybeAlign NewFAlign = NewF->getAlign();912 const MaybeAlign GAlign = G->getAlign();913 914 writeThunkOrAliasIfNeeded(F, G);915 writeThunkOrAliasIfNeeded(F, NewF);916 917 if (NewFAlign || GAlign)918 F->setAlignment(std::max(NewFAlign.valueOrOne(), GAlign.valueOrOne()));919 else920 F->setAlignment(std::nullopt);921 F->setLinkage(GlobalValue::PrivateLinkage);922 ++NumDoubleWeak;923 ++NumFunctionsMerged;924 } else {925 // For better debugability, under MergeFunctionsPDI, we do not modify G's926 // call sites to point to F even when within the same translation unit.927 if (!G->isInterposable() && !MergeFunctionsPDI) {928 // Functions referred to by llvm.used/llvm.compiler.used are special:929 // there are uses of the symbol name that are not visible to LLVM,930 // usually from inline asm.931 if (G->hasGlobalUnnamedAddr() && !Used.contains(G)) {932 // G might have been a key in our GlobalNumberState, and it's illegal933 // to replace a key in ValueMap<GlobalValue *> with a non-global.934 GlobalNumbers.erase(G);935 // If G's address is not significant, replace it entirely.936 removeUsers(G);937 G->replaceAllUsesWith(F);938 } else {939 // Redirect direct callers of G to F. (See note on MergeFunctionsPDI940 // above).941 replaceDirectCallers(G, F);942 }943 }944 945 // If G was internal then we may have replaced all uses of G with F. If so,946 // stop here and delete G. There's no need for a thunk. (See note on947 // MergeFunctionsPDI above).948 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {949 G->eraseFromParent();950 ++NumFunctionsMerged;951 return;952 }953 954 if (writeThunkOrAliasIfNeeded(F, G)) {955 ++NumFunctionsMerged;956 }957 }958}959 960/// Replace function F by function G.961void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,962 Function *G) {963 Function *F = FN.getFunc();964 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&965 "The two functions must be equal");966 967 auto I = FNodesInTree.find(F);968 assert(I != FNodesInTree.end() && "F should be in FNodesInTree");969 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");970 971 FnTreeType::iterator IterToFNInFnTree = I->second;972 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");973 // Remove F -> FN and insert G -> FN974 FNodesInTree.erase(I);975 FNodesInTree.insert({G, IterToFNInFnTree});976 // Replace F with G in FN, which is stored inside the FnTree.977 FN.replaceBy(G);978}979 980// Ordering for functions that are equal under FunctionComparator981static bool isFuncOrderCorrect(const Function *F, const Function *G) {982 if (isODR(F) != isODR(G)) {983 // ODR functions before non-ODR functions. A ODR function can call a non-ODR984 // function if it is not interposable, but not the other way around.985 return isODR(G);986 }987 988 if (F->isInterposable() != G->isInterposable()) {989 // Strong before weak, because the weak function may call the strong990 // one, but not the other way around.991 return !F->isInterposable();992 }993 994 if (F->hasLocalLinkage() != G->hasLocalLinkage()) {995 // External before local, because we definitely have to keep the external996 // function, but may be able to drop the local one.997 return !F->hasLocalLinkage();998 }999 1000 // Impose a total order (by name) on the replacement of functions. This is1001 // important when operating on more than one module independently to prevent1002 // cycles of thunks calling each other when the modules are linked together.1003 return F->getName() <= G->getName();1004}1005 1006// Insert a ComparableFunction into the FnTree, or merge it away if equal to one1007// that was already inserted.1008bool MergeFunctions::insert(Function *NewFunction) {1009 std::pair<FnTreeType::iterator, bool> Result =1010 FnTree.insert(FunctionNode(NewFunction));1011 1012 if (Result.second) {1013 assert(FNodesInTree.count(NewFunction) == 0);1014 FNodesInTree.insert({NewFunction, Result.first});1015 LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()1016 << '\n');1017 return false;1018 }1019 1020 const FunctionNode &OldF = *Result.first;1021 1022 if (!isFuncOrderCorrect(OldF.getFunc(), NewFunction)) {1023 // Swap the two functions.1024 Function *F = OldF.getFunc();1025 replaceFunctionInTree(*Result.first, NewFunction);1026 NewFunction = F;1027 assert(OldF.getFunc() != F && "Must have swapped the functions.");1028 }1029 1030 LLVM_DEBUG(dbgs() << " " << OldF.getFunc()->getName()1031 << " == " << NewFunction->getName() << '\n');1032 1033 Function *DeleteF = NewFunction;1034 mergeTwoFunctions(OldF.getFunc(), DeleteF);1035 this->DelToNewMap.insert({DeleteF, OldF.getFunc()});1036 return true;1037}1038 1039// Remove a function from FnTree. If it was already in FnTree, add1040// it to Deferred so that we'll look at it in the next round.1041void MergeFunctions::remove(Function *F) {1042 auto I = FNodesInTree.find(F);1043 if (I != FNodesInTree.end()) {1044 LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");1045 FnTree.erase(I->second);1046 // I->second has been invalidated, remove it from the FNodesInTree map to1047 // preserve the invariant.1048 FNodesInTree.erase(I);1049 Deferred.emplace_back(F);1050 }1051}1052 1053// For each instruction used by the value, remove() the function that contains1054// the instruction. This should happen right before a call to RAUW.1055void MergeFunctions::removeUsers(Value *V) {1056 for (User *U : V->users())1057 if (auto *I = dyn_cast<Instruction>(U))1058 remove(I->getFunction());1059}1060