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