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/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/Constant.h" 98 #include "llvm/IR/Constants.h" 99 #include "llvm/IR/DebugInfoMetadata.h" 100 #include "llvm/IR/DebugLoc.h" 101 #include "llvm/IR/DerivedTypes.h" 102 #include "llvm/IR/Function.h" 103 #include "llvm/IR/GlobalValue.h" 104 #include "llvm/IR/IRBuilder.h" 105 #include "llvm/IR/InstrTypes.h" 106 #include "llvm/IR/Instruction.h" 107 #include "llvm/IR/Instructions.h" 108 #include "llvm/IR/IntrinsicInst.h" 109 #include "llvm/IR/Module.h" 110 #include "llvm/IR/Type.h" 111 #include "llvm/IR/Use.h" 112 #include "llvm/IR/User.h" 113 #include "llvm/IR/Value.h" 114 #include "llvm/IR/ValueHandle.h" 115 #include "llvm/InitializePasses.h" 116 #include "llvm/Pass.h" 117 #include "llvm/Support/Casting.h" 118 #include "llvm/Support/CommandLine.h" 119 #include "llvm/Support/Debug.h" 120 #include "llvm/Support/raw_ostream.h" 121 #include "llvm/Transforms/IPO.h" 122 #include "llvm/Transforms/Utils/FunctionComparator.h" 123 #include "llvm/Transforms/Utils/ModuleUtils.h" 124 #include <algorithm> 125 #include <cassert> 126 #include <iterator> 127 #include <set> 128 #include <utility> 129 #include <vector> 130 131 using namespace llvm; 132 133 #define DEBUG_TYPE "mergefunc" 134 135 STATISTIC(NumFunctionsMerged, "Number of functions merged"); 136 STATISTIC(NumThunksWritten, "Number of thunks generated"); 137 STATISTIC(NumAliasesWritten, "Number of aliases generated"); 138 STATISTIC(NumDoubleWeak, "Number of new functions created"); 139 140 static cl::opt<unsigned> NumFunctionsForVerificationCheck( 141 "mergefunc-verify", 142 cl::desc("How many functions in a module could be used for " 143 "MergeFunctions to pass a basic correctness check. " 144 "'0' disables this check. Works only with '-debug' key."), 145 cl::init(0), cl::Hidden); 146 147 // Under option -mergefunc-preserve-debug-info we: 148 // - Do not create a new function for a thunk. 149 // - Retain the debug info for a thunk's parameters (and associated 150 // instructions for the debug info) from the entry block. 151 // Note: -debug will display the algorithm at work. 152 // - Create debug-info for the call (to the shared implementation) made by 153 // a thunk and its return value. 154 // - Erase the rest of the function, retaining the (minimally sized) entry 155 // block to create a thunk. 156 // - Preserve a thunk's call site to point to the thunk even when both occur 157 // within the same translation unit, to aid debugability. Note that this 158 // behaviour differs from the underlying -mergefunc implementation which 159 // modifies the thunk's call site to point to the shared implementation 160 // when both occur within the same translation unit. 161 static cl::opt<bool> 162 MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden, 163 cl::init(false), 164 cl::desc("Preserve debug info in thunk when mergefunc " 165 "transformations are made.")); 166 167 static cl::opt<bool> 168 MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden, 169 cl::init(false), 170 cl::desc("Allow mergefunc to create aliases")); 171 172 namespace { 173 174 class FunctionNode { 175 mutable AssertingVH<Function> F; 176 FunctionComparator::FunctionHash Hash; 177 178 public: 179 // Note the hash is recalculated potentially multiple times, but it is cheap. 180 FunctionNode(Function *F) 181 : F(F), Hash(FunctionComparator::functionHash(*F)) {} 182 183 Function *getFunc() const { return F; } 184 FunctionComparator::FunctionHash getHash() const { return Hash; } 185 186 /// Replace the reference to the function F by the function G, assuming their 187 /// implementations are equal. 188 void replaceBy(Function *G) const { 189 F = G; 190 } 191 }; 192 193 /// MergeFunctions finds functions which will generate identical machine code, 194 /// by considering all pointer types to be equivalent. Once identified, 195 /// MergeFunctions will fold them by replacing a call to one to a call to a 196 /// bitcast of the other. 197 class MergeFunctions { 198 public: 199 MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) { 200 } 201 202 bool runOnModule(Module &M); 203 204 private: 205 // The function comparison operator is provided here so that FunctionNodes do 206 // not need to become larger with another pointer. 207 class FunctionNodeCmp { 208 GlobalNumberState* GlobalNumbers; 209 210 public: 211 FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {} 212 213 bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const { 214 // Order first by hashes, then full function comparison. 215 if (LHS.getHash() != RHS.getHash()) 216 return LHS.getHash() < RHS.getHash(); 217 FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers); 218 return FCmp.compare() == -1; 219 } 220 }; 221 using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>; 222 223 GlobalNumberState GlobalNumbers; 224 225 /// A work queue of functions that may have been modified and should be 226 /// analyzed again. 227 std::vector<WeakTrackingVH> Deferred; 228 229 /// Set of values marked as used in llvm.used and llvm.compiler.used. 230 SmallPtrSet<GlobalValue *, 4> Used; 231 232 #ifndef NDEBUG 233 /// Checks the rules of order relation introduced among functions set. 234 /// Returns true, if check has been passed, and false if failed. 235 bool doFunctionalCheck(std::vector<WeakTrackingVH> &Worklist); 236 #endif 237 238 /// Insert a ComparableFunction into the FnTree, or merge it away if it's 239 /// equal to one that's already present. 240 bool insert(Function *NewFunction); 241 242 /// Remove a Function from the FnTree and queue it up for a second sweep of 243 /// analysis. 244 void remove(Function *F); 245 246 /// Find the functions that use this Value and remove them from FnTree and 247 /// queue the functions. 248 void removeUsers(Value *V); 249 250 /// Replace all direct calls of Old with calls of New. Will bitcast New if 251 /// necessary to make types match. 252 void replaceDirectCallers(Function *Old, Function *New); 253 254 /// Merge two equivalent functions. Upon completion, G may be deleted, or may 255 /// be converted into a thunk. In either case, it should never be visited 256 /// again. 257 void mergeTwoFunctions(Function *F, Function *G); 258 259 /// Fill PDIUnrelatedWL with instructions from the entry block that are 260 /// unrelated to parameter related debug info. 261 void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock, 262 std::vector<Instruction *> &PDIUnrelatedWL); 263 264 /// Erase the rest of the CFG (i.e. barring the entry block). 265 void eraseTail(Function *G); 266 267 /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the 268 /// parameter debug info, from the entry block. 269 void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL); 270 271 /// Replace G with a simple tail call to bitcast(F). Also (unless 272 /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F), 273 /// delete G. 274 void writeThunk(Function *F, Function *G); 275 276 // Replace G with an alias to F (deleting function G) 277 void writeAlias(Function *F, Function *G); 278 279 // Replace G with an alias to F if possible, or a thunk to F if possible. 280 // Returns false if neither is the case. 281 bool writeThunkOrAlias(Function *F, Function *G); 282 283 /// Replace function F with function G in the function tree. 284 void replaceFunctionInTree(const FunctionNode &FN, Function *G); 285 286 /// The set of all distinct functions. Use the insert() and remove() methods 287 /// to modify it. The map allows efficient lookup and deferring of Functions. 288 FnTreeType FnTree; 289 290 // Map functions to the iterators of the FunctionNode which contains them 291 // in the FnTree. This must be updated carefully whenever the FnTree is 292 // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid 293 // dangling iterators into FnTree. The invariant that preserves this is that 294 // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree. 295 DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree; 296 }; 297 298 class MergeFunctionsLegacyPass : public ModulePass { 299 public: 300 static char ID; 301 302 MergeFunctionsLegacyPass(): ModulePass(ID) { 303 initializeMergeFunctionsLegacyPassPass(*PassRegistry::getPassRegistry()); 304 } 305 306 bool runOnModule(Module &M) override { 307 if (skipModule(M)) 308 return false; 309 310 MergeFunctions MF; 311 return MF.runOnModule(M); 312 } 313 }; 314 315 } // end anonymous namespace 316 317 char MergeFunctionsLegacyPass::ID = 0; 318 INITIALIZE_PASS(MergeFunctionsLegacyPass, "mergefunc", 319 "Merge Functions", false, false) 320 321 ModulePass *llvm::createMergeFunctionsPass() { 322 return new MergeFunctionsLegacyPass(); 323 } 324 325 PreservedAnalyses MergeFunctionsPass::run(Module &M, 326 ModuleAnalysisManager &AM) { 327 MergeFunctions MF; 328 if (!MF.runOnModule(M)) 329 return PreservedAnalyses::all(); 330 return PreservedAnalyses::none(); 331 } 332 333 #ifndef NDEBUG 334 bool 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: " << TripleNumber 356 << "\n"; 357 dbgs() << *F1 << '\n' << *F2 << '\n'; 358 Valid = false; 359 } 360 361 if (Res1 == 0) 362 continue; 363 364 unsigned k = j; 365 for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max; 366 ++k, ++K, ++TripleNumber) { 367 if (K == J) 368 continue; 369 370 Function *F3 = cast<Function>(*K); 371 int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare(); 372 int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare(); 373 374 bool Transitive = true; 375 376 if (Res1 != 0 && Res1 == Res4) { 377 // F1 > F2, F2 > F3 => F1 > F3 378 Transitive = Res3 == Res1; 379 } else if (Res3 != 0 && Res3 == -Res4) { 380 // F1 > F3, F3 > F2 => F1 > F2 381 Transitive = Res3 == Res1; 382 } else if (Res4 != 0 && -Res3 == Res4) { 383 // F2 > F3, F3 > F1 => F2 > F1 384 Transitive = Res4 == -Res1; 385 } 386 387 if (!Transitive) { 388 dbgs() << "MERGEFUNC-VERIFY: Non-transitive; triple: " 389 << TripleNumber << "\n"; 390 dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", " 391 << Res4 << "\n"; 392 dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n'; 393 Valid = false; 394 } 395 } 396 } 397 } 398 399 dbgs() << "MERGEFUNC-VERIFY: " << (Valid ? "Passed." : "Failed.") << "\n"; 400 return Valid; 401 } 402 return true; 403 } 404 #endif 405 406 /// Check whether \p F is eligible for function merging. 407 static bool isEligibleForMerging(Function &F) { 408 return !F.isDeclaration() && !F.hasAvailableExternallyLinkage(); 409 } 410 411 bool MergeFunctions::runOnModule(Module &M) { 412 bool Changed = false; 413 414 SmallVector<GlobalValue *, 4> UsedV; 415 collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false); 416 collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/true); 417 Used.insert(UsedV.begin(), UsedV.end()); 418 419 // All functions in the module, ordered by hash. Functions with a unique 420 // hash value are easily eliminated. 421 std::vector<std::pair<FunctionComparator::FunctionHash, Function *>> 422 HashedFuncs; 423 for (Function &Func : M) { 424 if (isEligibleForMerging(Func)) { 425 HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func}); 426 } 427 } 428 429 llvm::stable_sort(HashedFuncs, less_first()); 430 431 auto S = HashedFuncs.begin(); 432 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) { 433 // If the hash value matches the previous value or the next one, we must 434 // consider merging it. Otherwise it is dropped and never considered again. 435 if ((I != S && std::prev(I)->first == I->first) || 436 (std::next(I) != IE && std::next(I)->first == I->first) ) { 437 Deferred.push_back(WeakTrackingVH(I->second)); 438 } 439 } 440 441 do { 442 std::vector<WeakTrackingVH> Worklist; 443 Deferred.swap(Worklist); 444 445 LLVM_DEBUG(doFunctionalCheck(Worklist)); 446 447 LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 448 LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); 449 450 // Insert functions and merge them. 451 for (WeakTrackingVH &I : Worklist) { 452 if (!I) 453 continue; 454 Function *F = cast<Function>(I); 455 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) { 456 Changed |= insert(F); 457 } 458 } 459 LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n'); 460 } while (!Deferred.empty()); 461 462 FnTree.clear(); 463 FNodesInTree.clear(); 464 GlobalNumbers.clear(); 465 Used.clear(); 466 467 return Changed; 468 } 469 470 // Replace direct callers of Old with New. 471 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { 472 Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); 473 for (Use &U : llvm::make_early_inc_range(Old->uses())) { 474 CallBase *CB = dyn_cast<CallBase>(U.getUser()); 475 if (CB && CB->isCallee(&U)) { 476 // Do not copy attributes from the called function to the call-site. 477 // Function comparison ensures that the attributes are the same up to 478 // type congruences in byval(), in which case we need to keep the byval 479 // type of the call-site, not the callee function. 480 remove(CB->getFunction()); 481 U.set(BitcastNew); 482 } 483 } 484 } 485 486 // Helper for writeThunk, 487 // Selects proper bitcast operation, 488 // but a bit simpler then CastInst::getCastOpcode. 489 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) { 490 Type *SrcTy = V->getType(); 491 if (SrcTy->isStructTy()) { 492 assert(DestTy->isStructTy()); 493 assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements()); 494 Value *Result = PoisonValue::get(DestTy); 495 for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) { 496 Value *Element = createCast( 497 Builder, Builder.CreateExtractValue(V, makeArrayRef(I)), 498 DestTy->getStructElementType(I)); 499 500 Result = 501 Builder.CreateInsertValue(Result, Element, makeArrayRef(I)); 502 } 503 return Result; 504 } 505 assert(!DestTy->isStructTy()); 506 if (SrcTy->isIntegerTy() && DestTy->isPointerTy()) 507 return Builder.CreateIntToPtr(V, DestTy); 508 else if (SrcTy->isPointerTy() && DestTy->isIntegerTy()) 509 return Builder.CreatePtrToInt(V, DestTy); 510 else 511 return Builder.CreateBitCast(V, DestTy); 512 } 513 514 // Erase the instructions in PDIUnrelatedWL as they are unrelated to the 515 // parameter debug info, from the entry block. 516 void MergeFunctions::eraseInstsUnrelatedToPDI( 517 std::vector<Instruction *> &PDIUnrelatedWL) { 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 LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter " 531 "debug info from entry block. \n"); 532 } 533 534 // Reduce G to its entry block. 535 void MergeFunctions::eraseTail(Function *G) { 536 std::vector<BasicBlock *> WorklistBB; 537 for (BasicBlock &BB : drop_begin(*G)) { 538 BB.dropAllReferences(); 539 WorklistBB.push_back(&BB); 540 } 541 while (!WorklistBB.empty()) { 542 BasicBlock *BB = WorklistBB.back(); 543 BB->eraseFromParent(); 544 WorklistBB.pop_back(); 545 } 546 } 547 548 // We are interested in the following instructions from the entry block as being 549 // related to parameter debug info: 550 // - @llvm.dbg.declare 551 // - stores from the incoming parameters to locations on the stack-frame 552 // - allocas that create these locations on the stack-frame 553 // - @llvm.dbg.value 554 // - the entry block's terminator 555 // The rest are unrelated to debug info for the parameters; fill up 556 // PDIUnrelatedWL with such instructions. 557 void MergeFunctions::filterInstsUnrelatedToPDI( 558 BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) { 559 std::set<Instruction *> PDIRelated; 560 for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end(); 561 BI != BIE; ++BI) { 562 if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) { 563 LLVM_DEBUG(dbgs() << " Deciding: "); 564 LLVM_DEBUG(BI->print(dbgs())); 565 LLVM_DEBUG(dbgs() << "\n"); 566 DILocalVariable *DILocVar = DVI->getVariable(); 567 if (DILocVar->isParameter()) { 568 LLVM_DEBUG(dbgs() << " Include (parameter): "); 569 LLVM_DEBUG(BI->print(dbgs())); 570 LLVM_DEBUG(dbgs() << "\n"); 571 PDIRelated.insert(&*BI); 572 } else { 573 LLVM_DEBUG(dbgs() << " Delete (!parameter): "); 574 LLVM_DEBUG(BI->print(dbgs())); 575 LLVM_DEBUG(dbgs() << "\n"); 576 } 577 } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) { 578 LLVM_DEBUG(dbgs() << " Deciding: "); 579 LLVM_DEBUG(BI->print(dbgs())); 580 LLVM_DEBUG(dbgs() << "\n"); 581 DILocalVariable *DILocVar = DDI->getVariable(); 582 if (DILocVar->isParameter()) { 583 LLVM_DEBUG(dbgs() << " Parameter: "); 584 LLVM_DEBUG(DILocVar->print(dbgs())); 585 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); 586 if (AI) { 587 LLVM_DEBUG(dbgs() << " Processing alloca users: "); 588 LLVM_DEBUG(dbgs() << "\n"); 589 for (User *U : AI->users()) { 590 if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 591 if (Value *Arg = SI->getValueOperand()) { 592 if (isa<Argument>(Arg)) { 593 LLVM_DEBUG(dbgs() << " Include: "); 594 LLVM_DEBUG(AI->print(dbgs())); 595 LLVM_DEBUG(dbgs() << "\n"); 596 PDIRelated.insert(AI); 597 LLVM_DEBUG(dbgs() << " Include (parameter): "); 598 LLVM_DEBUG(SI->print(dbgs())); 599 LLVM_DEBUG(dbgs() << "\n"); 600 PDIRelated.insert(SI); 601 LLVM_DEBUG(dbgs() << " Include: "); 602 LLVM_DEBUG(BI->print(dbgs())); 603 LLVM_DEBUG(dbgs() << "\n"); 604 PDIRelated.insert(&*BI); 605 } else { 606 LLVM_DEBUG(dbgs() << " Delete (!parameter): "); 607 LLVM_DEBUG(SI->print(dbgs())); 608 LLVM_DEBUG(dbgs() << "\n"); 609 } 610 } 611 } else { 612 LLVM_DEBUG(dbgs() << " Defer: "); 613 LLVM_DEBUG(U->print(dbgs())); 614 LLVM_DEBUG(dbgs() << "\n"); 615 } 616 } 617 } else { 618 LLVM_DEBUG(dbgs() << " Delete (alloca NULL): "); 619 LLVM_DEBUG(BI->print(dbgs())); 620 LLVM_DEBUG(dbgs() << "\n"); 621 } 622 } else { 623 LLVM_DEBUG(dbgs() << " Delete (!parameter): "); 624 LLVM_DEBUG(BI->print(dbgs())); 625 LLVM_DEBUG(dbgs() << "\n"); 626 } 627 } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) { 628 LLVM_DEBUG(dbgs() << " Will Include Terminator: "); 629 LLVM_DEBUG(BI->print(dbgs())); 630 LLVM_DEBUG(dbgs() << "\n"); 631 PDIRelated.insert(&*BI); 632 } else { 633 LLVM_DEBUG(dbgs() << " Defer: "); 634 LLVM_DEBUG(BI->print(dbgs())); 635 LLVM_DEBUG(dbgs() << "\n"); 636 } 637 } 638 LLVM_DEBUG( 639 dbgs() 640 << " Report parameter debug info related/related instructions: {\n"); 641 for (Instruction &I : *GEntryBlock) { 642 if (PDIRelated.find(&I) == PDIRelated.end()) { 643 LLVM_DEBUG(dbgs() << " !PDIRelated: "); 644 LLVM_DEBUG(I.print(dbgs())); 645 LLVM_DEBUG(dbgs() << "\n"); 646 PDIUnrelatedWL.push_back(&I); 647 } else { 648 LLVM_DEBUG(dbgs() << " PDIRelated: "); 649 LLVM_DEBUG(I.print(dbgs())); 650 LLVM_DEBUG(dbgs() << "\n"); 651 } 652 } 653 LLVM_DEBUG(dbgs() << " }\n"); 654 } 655 656 /// Whether this function may be replaced by a forwarding thunk. 657 static bool canCreateThunkFor(Function *F) { 658 if (F->isVarArg()) 659 return false; 660 661 // Don't merge tiny functions using a thunk, since it can just end up 662 // making the function larger. 663 if (F->size() == 1) { 664 if (F->front().size() <= 2) { 665 LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName() 666 << " is too small to bother creating a thunk for\n"); 667 return false; 668 } 669 } 670 return true; 671 } 672 673 // Replace G with a simple tail call to bitcast(F). Also (unless 674 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F), 675 // delete G. Under MergeFunctionsPDI, we use G itself for creating 676 // the thunk as we preserve the debug info (and associated instructions) 677 // from G's entry block pertaining to G's incoming arguments which are 678 // passed on as corresponding arguments in the call that G makes to F. 679 // For better debugability, under MergeFunctionsPDI, we do not modify G's 680 // call sites to point to F even when within the same translation unit. 681 void MergeFunctions::writeThunk(Function *F, Function *G) { 682 BasicBlock *GEntryBlock = nullptr; 683 std::vector<Instruction *> PDIUnrelatedWL; 684 BasicBlock *BB = nullptr; 685 Function *NewG = nullptr; 686 if (MergeFunctionsPDI) { 687 LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new " 688 "function as thunk; retain original: " 689 << G->getName() << "()\n"); 690 GEntryBlock = &G->getEntryBlock(); 691 LLVM_DEBUG( 692 dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related " 693 "debug info for " 694 << G->getName() << "() {\n"); 695 filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL); 696 GEntryBlock->getTerminator()->eraseFromParent(); 697 BB = GEntryBlock; 698 } else { 699 NewG = Function::Create(G->getFunctionType(), G->getLinkage(), 700 G->getAddressSpace(), "", G->getParent()); 701 NewG->setComdat(G->getComdat()); 702 BB = BasicBlock::Create(F->getContext(), "", NewG); 703 } 704 705 IRBuilder<> Builder(BB); 706 Function *H = MergeFunctionsPDI ? G : NewG; 707 SmallVector<Value *, 16> Args; 708 unsigned i = 0; 709 FunctionType *FFTy = F->getFunctionType(); 710 for (Argument &AI : H->args()) { 711 Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i))); 712 ++i; 713 } 714 715 CallInst *CI = Builder.CreateCall(F, Args); 716 ReturnInst *RI = nullptr; 717 bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail && 718 G->getCallingConv() == CallingConv::SwiftTail; 719 CI->setTailCallKind(isSwiftTailCall ? llvm::CallInst::TCK_MustTail 720 : llvm::CallInst::TCK_Tail); 721 CI->setCallingConv(F->getCallingConv()); 722 CI->setAttributes(F->getAttributes()); 723 if (H->getReturnType()->isVoidTy()) { 724 RI = Builder.CreateRetVoid(); 725 } else { 726 RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType())); 727 } 728 729 if (MergeFunctionsPDI) { 730 DISubprogram *DIS = G->getSubprogram(); 731 if (DIS) { 732 DebugLoc CIDbgLoc = 733 DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS); 734 DebugLoc RIDbgLoc = 735 DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS); 736 CI->setDebugLoc(CIDbgLoc); 737 RI->setDebugLoc(RIDbgLoc); 738 } else { 739 LLVM_DEBUG( 740 dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for " 741 << G->getName() << "()\n"); 742 } 743 eraseTail(G); 744 eraseInstsUnrelatedToPDI(PDIUnrelatedWL); 745 LLVM_DEBUG( 746 dbgs() << "} // End of parameter related debug info filtering for: " 747 << G->getName() << "()\n"); 748 } else { 749 NewG->copyAttributesFrom(G); 750 NewG->takeName(G); 751 removeUsers(G); 752 G->replaceAllUsesWith(NewG); 753 G->eraseFromParent(); 754 } 755 756 LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n'); 757 ++NumThunksWritten; 758 } 759 760 // Whether this function may be replaced by an alias 761 static bool canCreateAliasFor(Function *F) { 762 if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr()) 763 return false; 764 765 // We should only see linkages supported by aliases here 766 assert(F->hasLocalLinkage() || F->hasExternalLinkage() 767 || F->hasWeakLinkage() || F->hasLinkOnceLinkage()); 768 return true; 769 } 770 771 // Replace G with an alias to F (deleting function G) 772 void MergeFunctions::writeAlias(Function *F, Function *G) { 773 Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 774 PointerType *PtrType = G->getType(); 775 auto *GA = GlobalAlias::create(G->getValueType(), PtrType->getAddressSpace(), 776 G->getLinkage(), "", BitcastF, G->getParent()); 777 778 F->setAlignment(MaybeAlign(std::max(F->getAlignment(), G->getAlignment()))); 779 GA->takeName(G); 780 GA->setVisibility(G->getVisibility()); 781 GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); 782 783 removeUsers(G); 784 G->replaceAllUsesWith(GA); 785 G->eraseFromParent(); 786 787 LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); 788 ++NumAliasesWritten; 789 } 790 791 // Replace G with an alias to F if possible, or a thunk to F if 792 // profitable. Returns false if neither is the case. 793 bool MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { 794 if (canCreateAliasFor(G)) { 795 writeAlias(F, G); 796 return true; 797 } 798 if (canCreateThunkFor(F)) { 799 writeThunk(F, G); 800 return true; 801 } 802 return false; 803 } 804 805 // Merge two equivalent functions. Upon completion, Function G is deleted. 806 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { 807 if (F->isInterposable()) { 808 assert(G->isInterposable()); 809 810 // Both writeThunkOrAlias() calls below must succeed, either because we can 811 // create aliases for G and NewF, or because a thunk for F is profitable. 812 // F here has the same signature as NewF below, so that's what we check. 813 if (!canCreateThunkFor(F) && 814 (!canCreateAliasFor(F) || !canCreateAliasFor(G))) 815 return; 816 817 // Make them both thunks to the same internal function. 818 Function *NewF = Function::Create(F->getFunctionType(), F->getLinkage(), 819 F->getAddressSpace(), "", F->getParent()); 820 NewF->copyAttributesFrom(F); 821 NewF->takeName(F); 822 removeUsers(F); 823 F->replaceAllUsesWith(NewF); 824 825 MaybeAlign MaxAlignment(std::max(G->getAlignment(), NewF->getAlignment())); 826 827 writeThunkOrAlias(F, G); 828 writeThunkOrAlias(F, NewF); 829 830 F->setAlignment(MaxAlignment); 831 F->setLinkage(GlobalValue::PrivateLinkage); 832 ++NumDoubleWeak; 833 ++NumFunctionsMerged; 834 } else { 835 // For better debugability, under MergeFunctionsPDI, we do not modify G's 836 // call sites to point to F even when within the same translation unit. 837 if (!G->isInterposable() && !MergeFunctionsPDI) { 838 // Functions referred to by llvm.used/llvm.compiler.used are special: 839 // there are uses of the symbol name that are not visible to LLVM, 840 // usually from inline asm. 841 if (G->hasGlobalUnnamedAddr() && !Used.contains(G)) { 842 // G might have been a key in our GlobalNumberState, and it's illegal 843 // to replace a key in ValueMap<GlobalValue *> with a non-global. 844 GlobalNumbers.erase(G); 845 // If G's address is not significant, replace it entirely. 846 Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 847 removeUsers(G); 848 G->replaceAllUsesWith(BitcastF); 849 } else { 850 // Redirect direct callers of G to F. (See note on MergeFunctionsPDI 851 // above). 852 replaceDirectCallers(G, F); 853 } 854 } 855 856 // If G was internal then we may have replaced all uses of G with F. If so, 857 // stop here and delete G. There's no need for a thunk. (See note on 858 // MergeFunctionsPDI above). 859 if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) { 860 G->eraseFromParent(); 861 ++NumFunctionsMerged; 862 return; 863 } 864 865 if (writeThunkOrAlias(F, G)) { 866 ++NumFunctionsMerged; 867 } 868 } 869 } 870 871 /// Replace function F by function G. 872 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN, 873 Function *G) { 874 Function *F = FN.getFunc(); 875 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 && 876 "The two functions must be equal"); 877 878 auto I = FNodesInTree.find(F); 879 assert(I != FNodesInTree.end() && "F should be in FNodesInTree"); 880 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G"); 881 882 FnTreeType::iterator IterToFNInFnTree = I->second; 883 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree."); 884 // Remove F -> FN and insert G -> FN 885 FNodesInTree.erase(I); 886 FNodesInTree.insert({G, IterToFNInFnTree}); 887 // Replace F with G in FN, which is stored inside the FnTree. 888 FN.replaceBy(G); 889 } 890 891 // Ordering for functions that are equal under FunctionComparator 892 static bool isFuncOrderCorrect(const Function *F, const Function *G) { 893 if (F->isInterposable() != G->isInterposable()) { 894 // Strong before weak, because the weak function may call the strong 895 // one, but not the other way around. 896 return !F->isInterposable(); 897 } 898 if (F->hasLocalLinkage() != G->hasLocalLinkage()) { 899 // External before local, because we definitely have to keep the external 900 // function, but may be able to drop the local one. 901 return !F->hasLocalLinkage(); 902 } 903 // Impose a total order (by name) on the replacement of functions. This is 904 // important when operating on more than one module independently to prevent 905 // cycles of thunks calling each other when the modules are linked together. 906 return F->getName() <= G->getName(); 907 } 908 909 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one 910 // that was already inserted. 911 bool MergeFunctions::insert(Function *NewFunction) { 912 std::pair<FnTreeType::iterator, bool> Result = 913 FnTree.insert(FunctionNode(NewFunction)); 914 915 if (Result.second) { 916 assert(FNodesInTree.count(NewFunction) == 0); 917 FNodesInTree.insert({NewFunction, Result.first}); 918 LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() 919 << '\n'); 920 return false; 921 } 922 923 const FunctionNode &OldF = *Result.first; 924 925 if (!isFuncOrderCorrect(OldF.getFunc(), NewFunction)) { 926 // Swap the two functions. 927 Function *F = OldF.getFunc(); 928 replaceFunctionInTree(*Result.first, NewFunction); 929 NewFunction = F; 930 assert(OldF.getFunc() != F && "Must have swapped the functions."); 931 } 932 933 LLVM_DEBUG(dbgs() << " " << OldF.getFunc()->getName() 934 << " == " << NewFunction->getName() << '\n'); 935 936 Function *DeleteF = NewFunction; 937 mergeTwoFunctions(OldF.getFunc(), DeleteF); 938 return true; 939 } 940 941 // Remove a function from FnTree. If it was already in FnTree, add 942 // it to Deferred so that we'll look at it in the next round. 943 void MergeFunctions::remove(Function *F) { 944 auto I = FNodesInTree.find(F); 945 if (I != FNodesInTree.end()) { 946 LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n"); 947 FnTree.erase(I->second); 948 // I->second has been invalidated, remove it from the FNodesInTree map to 949 // preserve the invariant. 950 FNodesInTree.erase(I); 951 Deferred.emplace_back(F); 952 } 953 } 954 955 // For each instruction used by the value, remove() the function that contains 956 // the instruction. This should happen right before a call to RAUW. 957 void MergeFunctions::removeUsers(Value *V) { 958 for (User *U : V->users()) 959 if (auto *I = dyn_cast<Instruction>(U)) 960 remove(I->getFunction()); 961 } 962