MergeFunctions.cpp revision 081c34b725980f995be9080eaec24cd3dfaaf065
1//===- MergeFunctions.cpp - Merge identical functions ---------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass looks for equivalent functions that are mergable and folds them. 11// 12// A hash is computed from the function, based on its type and number of 13// basic blocks. 14// 15// Once all hashes are computed, we perform an expensive equality comparison 16// on each function pair. This takes n^2/2 comparisons per bucket, so it's 17// important that the hash function be high quality. The equality comparison 18// iterates through each instruction in each basic block. 19// 20// When a match is found the functions are folded. If both functions are 21// overridable, we move the functionality into a new internal function and 22// leave two overridable thunks to it. 23// 24//===----------------------------------------------------------------------===// 25// 26// Future work: 27// 28// * virtual functions. 29// 30// Many functions have their address taken by the virtual function table for 31// the object they belong to. However, as long as it's only used for a lookup 32// and call, this is irrelevant, and we'd like to fold such functions. 33// 34// * switch from n^2 pair-wise comparisons to an n-way comparison for each 35// bucket. 36// 37// * be smarter about bitcasts. 38// 39// In order to fold functions, we will sometimes add either bitcast instructions 40// or bitcast constant expressions. Unfortunately, this can confound further 41// analysis since the two functions differ where one has a bitcast and the 42// other doesn't. We should learn to look through bitcasts. 43// 44//===----------------------------------------------------------------------===// 45 46#define DEBUG_TYPE "mergefunc" 47#include "llvm/Transforms/IPO.h" 48#include "llvm/ADT/DenseSet.h" 49#include "llvm/ADT/FoldingSet.h" 50#include "llvm/ADT/SmallSet.h" 51#include "llvm/ADT/Statistic.h" 52#include "llvm/ADT/STLExtras.h" 53#include "llvm/Constants.h" 54#include "llvm/InlineAsm.h" 55#include "llvm/Instructions.h" 56#include "llvm/LLVMContext.h" 57#include "llvm/Module.h" 58#include "llvm/Pass.h" 59#include "llvm/Support/CallSite.h" 60#include "llvm/Support/Debug.h" 61#include "llvm/Support/ErrorHandling.h" 62#include "llvm/Support/IRBuilder.h" 63#include "llvm/Support/ValueHandle.h" 64#include "llvm/Support/raw_ostream.h" 65#include "llvm/Target/TargetData.h" 66#include <vector> 67using namespace llvm; 68 69STATISTIC(NumFunctionsMerged, "Number of functions merged"); 70STATISTIC(NumThunksWritten, "Number of thunks generated"); 71STATISTIC(NumDoubleWeak, "Number of new functions created"); 72 73/// ProfileFunction - Creates a hash-code for the function which is the same 74/// for any two functions that will compare equal, without looking at the 75/// instructions inside the function. 76static unsigned ProfileFunction(const Function *F) { 77 const FunctionType *FTy = F->getFunctionType(); 78 79 FoldingSetNodeID ID; 80 ID.AddInteger(F->size()); 81 ID.AddInteger(F->getCallingConv()); 82 ID.AddBoolean(F->hasGC()); 83 ID.AddBoolean(FTy->isVarArg()); 84 ID.AddInteger(FTy->getReturnType()->getTypeID()); 85 for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) 86 ID.AddInteger(FTy->getParamType(i)->getTypeID()); 87 return ID.ComputeHash(); 88} 89 90namespace { 91 92class ComparableFunction { 93public: 94 static const ComparableFunction EmptyKey; 95 static const ComparableFunction TombstoneKey; 96 97 ComparableFunction(Function *Func, TargetData *TD) 98 : Func(Func), Hash(ProfileFunction(Func)), TD(TD) {} 99 100 Function *getFunc() const { return Func; } 101 unsigned getHash() const { return Hash; } 102 TargetData *getTD() const { return TD; } 103 104 // Drops AssertingVH reference to the function. Outside of debug mode, this 105 // does nothing. 106 void release() { 107 assert(Func && 108 "Attempted to release function twice, or release empty/tombstone!"); 109 Func = NULL; 110 } 111 112private: 113 explicit ComparableFunction(unsigned Hash) 114 : Func(NULL), Hash(Hash), TD(NULL) {} 115 116 AssertingVH<Function> Func; 117 unsigned Hash; 118 TargetData *TD; 119}; 120 121const ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0); 122const ComparableFunction ComparableFunction::TombstoneKey = 123 ComparableFunction(1); 124 125} 126 127namespace llvm { 128 template <> 129 struct DenseMapInfo<ComparableFunction> { 130 static ComparableFunction getEmptyKey() { 131 return ComparableFunction::EmptyKey; 132 } 133 static ComparableFunction getTombstoneKey() { 134 return ComparableFunction::TombstoneKey; 135 } 136 static unsigned getHashValue(const ComparableFunction &CF) { 137 return CF.getHash(); 138 } 139 static bool isEqual(const ComparableFunction &LHS, 140 const ComparableFunction &RHS); 141 }; 142} 143 144namespace { 145 146/// MergeFunctions finds functions which will generate identical machine code, 147/// by considering all pointer types to be equivalent. Once identified, 148/// MergeFunctions will fold them by replacing a call to one to a call to a 149/// bitcast of the other. 150/// 151class MergeFunctions : public ModulePass { 152public: 153 static char ID; 154 MergeFunctions() : ModulePass(ID) { 155 initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); 156 } 157 158 bool runOnModule(Module &M); 159 160private: 161 typedef DenseSet<ComparableFunction> FnSetType; 162 163 164 /// Insert a ComparableFunction into the FnSet, or merge it away if it's 165 /// equal to one that's already present. 166 bool Insert(FnSetType &FnSet, ComparableFunction &NewF); 167 168 /// MergeTwoFunctions - Merge two equivalent functions. Upon completion, G 169 /// may be deleted, or may be converted into a thunk. In either case, it 170 /// should never be visited again. 171 void MergeTwoFunctions(Function *F, Function *G) const; 172 173 /// WriteThunk - Replace G with a simple tail call to bitcast(F). Also 174 /// replace direct uses of G with bitcast(F). Deletes G. 175 void WriteThunk(Function *F, Function *G) const; 176 177 TargetData *TD; 178}; 179 180} // end anonymous namespace 181 182char MergeFunctions::ID = 0; 183INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false) 184 185ModulePass *llvm::createMergeFunctionsPass() { 186 return new MergeFunctions(); 187} 188 189namespace { 190/// FunctionComparator - Compares two functions to determine whether or not 191/// they will generate machine code with the same behaviour. TargetData is 192/// used if available. The comparator always fails conservatively (erring on the 193/// side of claiming that two functions are different). 194class FunctionComparator { 195public: 196 FunctionComparator(const TargetData *TD, const Function *F1, 197 const Function *F2) 198 : F1(F1), F2(F2), TD(TD), IDMap1Count(0), IDMap2Count(0) {} 199 200 /// Compare - test whether the two functions have equivalent behaviour. 201 bool Compare(); 202 203private: 204 /// Compare - test whether two basic blocks have equivalent behaviour. 205 bool Compare(const BasicBlock *BB1, const BasicBlock *BB2); 206 207 /// Enumerate - Assign or look up previously assigned numbers for the two 208 /// values, and return whether the numbers are equal. Numbers are assigned in 209 /// the order visited. 210 bool Enumerate(const Value *V1, const Value *V2); 211 212 /// isEquivalentOperation - Compare two Instructions for equivalence, similar 213 /// to Instruction::isSameOperationAs but with modifications to the type 214 /// comparison. 215 bool isEquivalentOperation(const Instruction *I1, 216 const Instruction *I2) const; 217 218 /// isEquivalentGEP - Compare two GEPs for equivalent pointer arithmetic. 219 bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2); 220 bool isEquivalentGEP(const GetElementPtrInst *GEP1, 221 const GetElementPtrInst *GEP2) { 222 return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2)); 223 } 224 225 /// isEquivalentType - Compare two Types, treating all pointer types as equal. 226 bool isEquivalentType(const Type *Ty1, const Type *Ty2) const; 227 228 // The two functions undergoing comparison. 229 const Function *F1, *F2; 230 231 const TargetData *TD; 232 233 typedef DenseMap<const Value *, unsigned long> IDMap; 234 IDMap Map1, Map2; 235 unsigned long IDMap1Count, IDMap2Count; 236}; 237} 238 239/// isEquivalentType - any two pointers in the same address space are 240/// equivalent. Otherwise, standard type equivalence rules apply. 241bool FunctionComparator::isEquivalentType(const Type *Ty1, 242 const Type *Ty2) const { 243 if (Ty1 == Ty2) 244 return true; 245 if (Ty1->getTypeID() != Ty2->getTypeID()) 246 return false; 247 248 switch(Ty1->getTypeID()) { 249 default: 250 llvm_unreachable("Unknown type!"); 251 // Fall through in Release mode. 252 case Type::IntegerTyID: 253 case Type::OpaqueTyID: 254 // Ty1 == Ty2 would have returned true earlier. 255 return false; 256 257 case Type::VoidTyID: 258 case Type::FloatTyID: 259 case Type::DoubleTyID: 260 case Type::X86_FP80TyID: 261 case Type::FP128TyID: 262 case Type::PPC_FP128TyID: 263 case Type::LabelTyID: 264 case Type::MetadataTyID: 265 return true; 266 267 case Type::PointerTyID: { 268 const PointerType *PTy1 = cast<PointerType>(Ty1); 269 const PointerType *PTy2 = cast<PointerType>(Ty2); 270 return PTy1->getAddressSpace() == PTy2->getAddressSpace(); 271 } 272 273 case Type::StructTyID: { 274 const StructType *STy1 = cast<StructType>(Ty1); 275 const StructType *STy2 = cast<StructType>(Ty2); 276 if (STy1->getNumElements() != STy2->getNumElements()) 277 return false; 278 279 if (STy1->isPacked() != STy2->isPacked()) 280 return false; 281 282 for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) { 283 if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i))) 284 return false; 285 } 286 return true; 287 } 288 289 case Type::FunctionTyID: { 290 const FunctionType *FTy1 = cast<FunctionType>(Ty1); 291 const FunctionType *FTy2 = cast<FunctionType>(Ty2); 292 if (FTy1->getNumParams() != FTy2->getNumParams() || 293 FTy1->isVarArg() != FTy2->isVarArg()) 294 return false; 295 296 if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType())) 297 return false; 298 299 for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) { 300 if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i))) 301 return false; 302 } 303 return true; 304 } 305 306 case Type::ArrayTyID: { 307 const ArrayType *ATy1 = cast<ArrayType>(Ty1); 308 const ArrayType *ATy2 = cast<ArrayType>(Ty2); 309 return ATy1->getNumElements() == ATy2->getNumElements() && 310 isEquivalentType(ATy1->getElementType(), ATy2->getElementType()); 311 } 312 313 case Type::VectorTyID: { 314 const VectorType *VTy1 = cast<VectorType>(Ty1); 315 const VectorType *VTy2 = cast<VectorType>(Ty2); 316 return VTy1->getNumElements() == VTy2->getNumElements() && 317 isEquivalentType(VTy1->getElementType(), VTy2->getElementType()); 318 } 319 } 320} 321 322/// isEquivalentOperation - determine whether the two operations are the same 323/// except that pointer-to-A and pointer-to-B are equivalent. This should be 324/// kept in sync with Instruction::isSameOperationAs. 325bool FunctionComparator::isEquivalentOperation(const Instruction *I1, 326 const Instruction *I2) const { 327 if (I1->getOpcode() != I2->getOpcode() || 328 I1->getNumOperands() != I2->getNumOperands() || 329 !isEquivalentType(I1->getType(), I2->getType()) || 330 !I1->hasSameSubclassOptionalData(I2)) 331 return false; 332 333 // We have two instructions of identical opcode and #operands. Check to see 334 // if all operands are the same type 335 for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) 336 if (!isEquivalentType(I1->getOperand(i)->getType(), 337 I2->getOperand(i)->getType())) 338 return false; 339 340 // Check special state that is a part of some instructions. 341 if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) 342 return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() && 343 LI->getAlignment() == cast<LoadInst>(I2)->getAlignment(); 344 if (const StoreInst *SI = dyn_cast<StoreInst>(I1)) 345 return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() && 346 SI->getAlignment() == cast<StoreInst>(I2)->getAlignment(); 347 if (const CmpInst *CI = dyn_cast<CmpInst>(I1)) 348 return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate(); 349 if (const CallInst *CI = dyn_cast<CallInst>(I1)) 350 return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() && 351 CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() && 352 CI->getAttributes().getRawPointer() == 353 cast<CallInst>(I2)->getAttributes().getRawPointer(); 354 if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1)) 355 return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() && 356 CI->getAttributes().getRawPointer() == 357 cast<InvokeInst>(I2)->getAttributes().getRawPointer(); 358 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) { 359 if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices()) 360 return false; 361 for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) 362 if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i]) 363 return false; 364 return true; 365 } 366 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) { 367 if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices()) 368 return false; 369 for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) 370 if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i]) 371 return false; 372 return true; 373 } 374 375 return true; 376} 377 378/// isEquivalentGEP - determine whether two GEP operations perform the same 379/// underlying arithmetic. 380bool FunctionComparator::isEquivalentGEP(const GEPOperator *GEP1, 381 const GEPOperator *GEP2) { 382 // When we have target data, we can reduce the GEP down to the value in bytes 383 // added to the address. 384 if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) { 385 SmallVector<Value *, 8> Indices1(GEP1->idx_begin(), GEP1->idx_end()); 386 SmallVector<Value *, 8> Indices2(GEP2->idx_begin(), GEP2->idx_end()); 387 uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(), 388 Indices1.data(), Indices1.size()); 389 uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(), 390 Indices2.data(), Indices2.size()); 391 return Offset1 == Offset2; 392 } 393 394 if (GEP1->getPointerOperand()->getType() != 395 GEP2->getPointerOperand()->getType()) 396 return false; 397 398 if (GEP1->getNumOperands() != GEP2->getNumOperands()) 399 return false; 400 401 for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) { 402 if (!Enumerate(GEP1->getOperand(i), GEP2->getOperand(i))) 403 return false; 404 } 405 406 return true; 407} 408 409/// Enumerate - Compare two values used by the two functions under pair-wise 410/// comparison. If this is the first time the values are seen, they're added to 411/// the mapping so that we will detect mismatches on next use. 412bool FunctionComparator::Enumerate(const Value *V1, const Value *V2) { 413 // Check for function @f1 referring to itself and function @f2 referring to 414 // itself, or referring to each other, or both referring to either of them. 415 // They're all equivalent if the two functions are otherwise equivalent. 416 if (V1 == F1 && V2 == F2) 417 return true; 418 if (V1 == F2 && V2 == F1) 419 return true; 420 421 // TODO: constant expressions with GEP or references to F1 or F2. 422 if (isa<Constant>(V1)) 423 return V1 == V2; 424 425 if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) { 426 const InlineAsm *IA1 = cast<InlineAsm>(V1); 427 const InlineAsm *IA2 = cast<InlineAsm>(V2); 428 return IA1->getAsmString() == IA2->getAsmString() && 429 IA1->getConstraintString() == IA2->getConstraintString(); 430 } 431 432 unsigned long &ID1 = Map1[V1]; 433 if (!ID1) 434 ID1 = ++IDMap1Count; 435 436 unsigned long &ID2 = Map2[V2]; 437 if (!ID2) 438 ID2 = ++IDMap2Count; 439 440 return ID1 == ID2; 441} 442 443/// Compare - test whether two basic blocks have equivalent behaviour. 444bool FunctionComparator::Compare(const BasicBlock *BB1, const BasicBlock *BB2) { 445 BasicBlock::const_iterator F1I = BB1->begin(), F1E = BB1->end(); 446 BasicBlock::const_iterator F2I = BB2->begin(), F2E = BB2->end(); 447 448 do { 449 if (!Enumerate(F1I, F2I)) 450 return false; 451 452 if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(F1I)) { 453 const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(F2I); 454 if (!GEP2) 455 return false; 456 457 if (!Enumerate(GEP1->getPointerOperand(), GEP2->getPointerOperand())) 458 return false; 459 460 if (!isEquivalentGEP(GEP1, GEP2)) 461 return false; 462 } else { 463 if (!isEquivalentOperation(F1I, F2I)) 464 return false; 465 466 assert(F1I->getNumOperands() == F2I->getNumOperands()); 467 for (unsigned i = 0, e = F1I->getNumOperands(); i != e; ++i) { 468 Value *OpF1 = F1I->getOperand(i); 469 Value *OpF2 = F2I->getOperand(i); 470 471 if (!Enumerate(OpF1, OpF2)) 472 return false; 473 474 if (OpF1->getValueID() != OpF2->getValueID() || 475 !isEquivalentType(OpF1->getType(), OpF2->getType())) 476 return false; 477 } 478 } 479 480 ++F1I, ++F2I; 481 } while (F1I != F1E && F2I != F2E); 482 483 return F1I == F1E && F2I == F2E; 484} 485 486/// Compare - test whether the two functions have equivalent behaviour. 487bool FunctionComparator::Compare() { 488 // We need to recheck everything, but check the things that weren't included 489 // in the hash first. 490 491 if (F1->getAttributes() != F2->getAttributes()) 492 return false; 493 494 if (F1->hasGC() != F2->hasGC()) 495 return false; 496 497 if (F1->hasGC() && F1->getGC() != F2->getGC()) 498 return false; 499 500 if (F1->hasSection() != F2->hasSection()) 501 return false; 502 503 if (F1->hasSection() && F1->getSection() != F2->getSection()) 504 return false; 505 506 if (F1->isVarArg() != F2->isVarArg()) 507 return false; 508 509 // TODO: if it's internal and only used in direct calls, we could handle this 510 // case too. 511 if (F1->getCallingConv() != F2->getCallingConv()) 512 return false; 513 514 if (!isEquivalentType(F1->getFunctionType(), F2->getFunctionType())) 515 return false; 516 517 assert(F1->arg_size() == F2->arg_size() && 518 "Identically typed functions have different numbers of args!"); 519 520 // Visit the arguments so that they get enumerated in the order they're 521 // passed in. 522 for (Function::const_arg_iterator f1i = F1->arg_begin(), 523 f2i = F2->arg_begin(), f1e = F1->arg_end(); f1i != f1e; ++f1i, ++f2i) { 524 if (!Enumerate(f1i, f2i)) 525 llvm_unreachable("Arguments repeat!"); 526 } 527 528 // We do a CFG-ordered walk since the actual ordering of the blocks in the 529 // linked list is immaterial. Our walk starts at the entry block for both 530 // functions, then takes each block from each terminator in order. As an 531 // artifact, this also means that unreachable blocks are ignored. 532 SmallVector<const BasicBlock *, 8> F1BBs, F2BBs; 533 SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1. 534 535 F1BBs.push_back(&F1->getEntryBlock()); 536 F2BBs.push_back(&F2->getEntryBlock()); 537 538 VisitedBBs.insert(F1BBs[0]); 539 while (!F1BBs.empty()) { 540 const BasicBlock *F1BB = F1BBs.pop_back_val(); 541 const BasicBlock *F2BB = F2BBs.pop_back_val(); 542 543 if (!Enumerate(F1BB, F2BB) || !Compare(F1BB, F2BB)) 544 return false; 545 546 const TerminatorInst *F1TI = F1BB->getTerminator(); 547 const TerminatorInst *F2TI = F2BB->getTerminator(); 548 549 assert(F1TI->getNumSuccessors() == F2TI->getNumSuccessors()); 550 for (unsigned i = 0, e = F1TI->getNumSuccessors(); i != e; ++i) { 551 if (!VisitedBBs.insert(F1TI->getSuccessor(i))) 552 continue; 553 554 F1BBs.push_back(F1TI->getSuccessor(i)); 555 F2BBs.push_back(F2TI->getSuccessor(i)); 556 } 557 } 558 return true; 559} 560 561/// WriteThunk - Replace G with a simple tail call to bitcast(F). Also replace 562/// direct uses of G with bitcast(F). Deletes G. 563void MergeFunctions::WriteThunk(Function *F, Function *G) const { 564 if (!G->mayBeOverridden()) { 565 // Redirect direct callers of G to F. 566 Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 567 for (Value::use_iterator UI = G->use_begin(), UE = G->use_end(); 568 UI != UE;) { 569 Value::use_iterator TheIter = UI; 570 ++UI; 571 CallSite CS(*TheIter); 572 if (CS && CS.isCallee(TheIter)) 573 TheIter.getUse().set(BitcastF); 574 } 575 } 576 577 // If G was internal then we may have replaced all uses of G with F. If so, 578 // stop here and delete G. There's no need for a thunk. 579 if (G->hasLocalLinkage() && G->use_empty()) { 580 G->eraseFromParent(); 581 return; 582 } 583 584 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 585 G->getParent()); 586 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 587 IRBuilder<false> Builder(BB); 588 589 SmallVector<Value *, 16> Args; 590 unsigned i = 0; 591 const FunctionType *FFTy = F->getFunctionType(); 592 for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 593 AI != AE; ++AI) { 594 Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i))); 595 ++i; 596 } 597 598 CallInst *CI = Builder.CreateCall(F, Args.begin(), Args.end()); 599 CI->setTailCall(); 600 CI->setCallingConv(F->getCallingConv()); 601 if (NewG->getReturnType()->isVoidTy()) { 602 Builder.CreateRetVoid(); 603 } else { 604 Builder.CreateRet(Builder.CreateBitCast(CI, NewG->getReturnType())); 605 } 606 607 NewG->copyAttributesFrom(G); 608 NewG->takeName(G); 609 G->replaceAllUsesWith(NewG); 610 G->eraseFromParent(); 611 612 DEBUG(dbgs() << "WriteThunk: " << NewG->getName() << '\n'); 613 ++NumThunksWritten; 614} 615 616/// MergeTwoFunctions - Merge two equivalent functions. Upon completion, 617/// Function G is deleted. 618void MergeFunctions::MergeTwoFunctions(Function *F, Function *G) const { 619 if (F->mayBeOverridden()) { 620 assert(G->mayBeOverridden()); 621 622 // Make them both thunks to the same internal function. 623 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 624 F->getParent()); 625 H->copyAttributesFrom(F); 626 H->takeName(F); 627 F->replaceAllUsesWith(H); 628 629 unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); 630 631 WriteThunk(F, G); 632 WriteThunk(F, H); 633 634 F->setAlignment(MaxAlignment); 635 F->setLinkage(GlobalValue::InternalLinkage); 636 637 ++NumDoubleWeak; 638 } else { 639 WriteThunk(F, G); 640 } 641 642 ++NumFunctionsMerged; 643} 644 645// Insert - Insert a ComparableFunction into the FnSet, or merge it away if 646// equal to one that's already inserted. 647bool MergeFunctions::Insert(FnSetType &FnSet, ComparableFunction &NewF) { 648 std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF); 649 if (Result.second) 650 return false; 651 652 const ComparableFunction &OldF = *Result.first; 653 654 // Never thunk a strong function to a weak function. 655 assert(!OldF.getFunc()->mayBeOverridden() || 656 NewF.getFunc()->mayBeOverridden()); 657 658 DEBUG(dbgs() << " " << OldF.getFunc()->getName() << " == " 659 << NewF.getFunc()->getName() << '\n'); 660 661 Function *DeleteF = NewF.getFunc(); 662 NewF.release(); 663 MergeTwoFunctions(OldF.getFunc(), DeleteF); 664 return true; 665} 666 667// IsThunk - This method determines whether or not a given Function is a thunk\// like the ones emitted by this pass and therefore not subject to further 668// merging. 669static bool IsThunk(const Function *F) { 670 // The safe direction to fail is to return true. In that case, the function 671 // will be removed from merging analysis. If we failed to including functions 672 // then we may try to merge unmergable thing (ie., identical weak functions) 673 // which will push us into an infinite loop. 674 675 assert(!F->isDeclaration() && "Expected a function definition."); 676 677 const BasicBlock *BB = &F->front(); 678 // A thunk is: 679 // bitcast-inst* 680 // optional-reg tail call @thunkee(args...*) 681 // ret void|optional-reg 682 // where the args are in the same order as the arguments. 683 684 // Put this at the top since it triggers most often. 685 const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()); 686 if (!RI) return false; 687 688 // Verify that the sequence of bitcast-inst's are all casts of arguments and 689 // that there aren't any extras (ie. no repeated casts). 690 int LastArgNo = -1; 691 BasicBlock::const_iterator I = BB->begin(); 692 while (const BitCastInst *BCI = dyn_cast<BitCastInst>(I)) { 693 const Argument *A = dyn_cast<Argument>(BCI->getOperand(0)); 694 if (!A) return false; 695 if ((int)A->getArgNo() <= LastArgNo) return false; 696 LastArgNo = A->getArgNo(); 697 ++I; 698 } 699 700 // Verify that we have a direct tail call and that the calling conventions 701 // and number of arguments match. 702 const CallInst *CI = dyn_cast<CallInst>(I++); 703 if (!CI || !CI->isTailCall() || !CI->getCalledFunction() || 704 CI->getCallingConv() != CI->getCalledFunction()->getCallingConv() || 705 CI->getNumArgOperands() != F->arg_size()) 706 return false; 707 708 // Verify that the call instruction has the same arguments as this function 709 // and that they're all either the incoming argument or a cast of the right 710 // argument. 711 for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) { 712 const Value *V = CI->getArgOperand(i); 713 const Argument *A = dyn_cast<Argument>(V); 714 if (!A) { 715 const BitCastInst *BCI = dyn_cast<BitCastInst>(V); 716 if (!BCI) return false; 717 A = cast<Argument>(BCI->getOperand(0)); 718 } 719 if (A->getArgNo() != i) return false; 720 } 721 722 // Verify that the terminator is a ret void (if we're void) or a ret of the 723 // call's return, or a ret of a bitcast of the call's return. 724 const Value *RetOp = CI; 725 if (const BitCastInst *BCI = dyn_cast<BitCastInst>(I)) { 726 ++I; 727 if (BCI->getOperand(0) != CI) return false; 728 RetOp = BCI; 729 } 730 if (RI != I) return false; 731 if (RI->getNumOperands() == 0) 732 return CI->getType()->isVoidTy(); 733 return RI->getReturnValue() == CI; 734} 735 736bool MergeFunctions::runOnModule(Module &M) { 737 bool Changed = false; 738 TD = getAnalysisIfAvailable<TargetData>(); 739 740 bool LocalChanged; 741 do { 742 DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 743 LocalChanged = false; 744 FnSetType FnSet; 745 746 // Insert only strong functions and merge them. Strong function merging 747 // always deletes one of them. 748 for (Module::iterator I = M.begin(), E = M.end(); I != E;) { 749 Function *F = I++; 750 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 751 !F->mayBeOverridden() && !IsThunk(F)) { 752 ComparableFunction CF = ComparableFunction(F, TD); 753 LocalChanged |= Insert(FnSet, CF); 754 } 755 } 756 757 // Insert only weak functions and merge them. By doing these second we 758 // create thunks to the strong function when possible. When two weak 759 // functions are identical, we create a new strong function with two weak 760 // weak thunks to it which are identical but not mergable. 761 for (Module::iterator I = M.begin(), E = M.end(); I != E;) { 762 Function *F = I++; 763 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 764 F->mayBeOverridden() && !IsThunk(F)) { 765 ComparableFunction CF = ComparableFunction(F, TD); 766 LocalChanged |= Insert(FnSet, CF); 767 } 768 } 769 DEBUG(dbgs() << "size of FnSet: " << FnSet.size() << '\n'); 770 Changed |= LocalChanged; 771 } while (LocalChanged); 772 773 return Changed; 774} 775 776bool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS, 777 const ComparableFunction &RHS) { 778 if (LHS.getFunc() == RHS.getFunc() && 779 LHS.getHash() == RHS.getHash()) 780 return true; 781 if (!LHS.getFunc() || !RHS.getFunc()) 782 return false; 783 assert(LHS.getTD() == RHS.getTD() && 784 "Comparing functions for different targets"); 785 return FunctionComparator(LHS.getTD(), 786 LHS.getFunc(), RHS.getFunc()).Compare(); 787} 788