MergeFunctions.cpp revision 664040a03c17f432a127a35013eeb6b6a26e41fb
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 implementations. 33// 34// * use SCC to cut down on pair-wise comparisons and solve larger cycles. 35// 36// The current implementation loops over a pair-wise comparison of all 37// functions in the program where the two functions in the pair are treated as 38// assumed to be equal until proven otherwise. We could both use fewer 39// comparisons and optimize more complex cases if we used strongly connected 40// components of the call graph. 41// 42// * be smarter about bitcast. 43// 44// In order to fold functions, we will sometimes add either bitcast instructions 45// or bitcast constant expressions. Unfortunately, this can confound further 46// analysis since the two functions differ where one has a bitcast and the 47// other doesn't. We should learn to peer through bitcasts without imposing bad 48// performance properties. 49// 50// * don't emit aliases for Mach-O. 51// 52// Mach-O doesn't support aliases which means that we must avoid introducing 53// them in the bitcode on architectures which don't support them, such as 54// Mac OSX. There's a few approaches to this problem; 55// a) teach codegen to lower global aliases to thunks on platforms which don't 56// support them. 57// b) always emit thunks, and create a separate thunk-to-alias pass which 58// runs on ELF systems. This has the added benefit of transforming other 59// thunks such as those produced by a C++ frontend into aliases when legal 60// to do so. 61// 62//===----------------------------------------------------------------------===// 63 64#define DEBUG_TYPE "mergefunc" 65#include "llvm/Transforms/IPO.h" 66#include "llvm/ADT/DenseMap.h" 67#include "llvm/ADT/FoldingSet.h" 68#include "llvm/ADT/SmallSet.h" 69#include "llvm/ADT/Statistic.h" 70#include "llvm/Constants.h" 71#include "llvm/InlineAsm.h" 72#include "llvm/Instructions.h" 73#include "llvm/LLVMContext.h" 74#include "llvm/Module.h" 75#include "llvm/Pass.h" 76#include "llvm/Support/CallSite.h" 77#include "llvm/Support/Debug.h" 78#include "llvm/Support/ErrorHandling.h" 79#include "llvm/Support/raw_ostream.h" 80#include "llvm/Target/TargetData.h" 81#include <map> 82#include <vector> 83using namespace llvm; 84 85STATISTIC(NumFunctionsMerged, "Number of functions merged"); 86 87namespace { 88 class MergeFunctions : public ModulePass { 89 public: 90 static char ID; // Pass identification, replacement for typeid 91 MergeFunctions() : ModulePass(&ID) {} 92 93 bool runOnModule(Module &M); 94 95 private: 96 bool isEquivalentGEP(const GetElementPtrInst *GEP1, 97 const GetElementPtrInst *GEP2); 98 99 bool equals(const BasicBlock *BB1, const BasicBlock *BB2); 100 bool equals(const Function *F, const Function *G); 101 102 bool compare(const Value *V1, const Value *V2); 103 104 const Function *LHS, *RHS; 105 typedef DenseMap<const Value *, unsigned long> IDMap; 106 IDMap Map; 107 DenseMap<const Function *, IDMap> Domains; 108 DenseMap<const Function *, unsigned long> DomainCount; 109 TargetData *TD; 110 }; 111} 112 113char MergeFunctions::ID = 0; 114static RegisterPass<MergeFunctions> X("mergefunc", "Merge Functions"); 115 116ModulePass *llvm::createMergeFunctionsPass() { 117 return new MergeFunctions(); 118} 119 120// ===----------------------------------------------------------------------=== 121// Comparison of functions 122// ===----------------------------------------------------------------------=== 123 124static unsigned long hash(const Function *F) { 125 const FunctionType *FTy = F->getFunctionType(); 126 127 FoldingSetNodeID ID; 128 ID.AddInteger(F->size()); 129 ID.AddInteger(F->getCallingConv()); 130 ID.AddBoolean(F->hasGC()); 131 ID.AddBoolean(FTy->isVarArg()); 132 ID.AddInteger(FTy->getReturnType()->getTypeID()); 133 for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) 134 ID.AddInteger(FTy->getParamType(i)->getTypeID()); 135 return ID.ComputeHash(); 136} 137 138/// isEquivalentType - any two pointers are equivalent. Otherwise, standard 139/// type equivalence rules apply. 140static bool isEquivalentType(const Type *Ty1, const Type *Ty2) { 141 if (Ty1 == Ty2) 142 return true; 143 if (Ty1->getTypeID() != Ty2->getTypeID()) 144 return false; 145 146 switch(Ty1->getTypeID()) { 147 default: 148 llvm_unreachable("Unknown type!"); 149 // Fall through in Release mode. 150 case Type::IntegerTyID: 151 case Type::OpaqueTyID: 152 // Ty1 == Ty2 would have returned true earlier. 153 return false; 154 155 case Type::VoidTyID: 156 case Type::FloatTyID: 157 case Type::DoubleTyID: 158 case Type::X86_FP80TyID: 159 case Type::FP128TyID: 160 case Type::PPC_FP128TyID: 161 case Type::LabelTyID: 162 case Type::MetadataTyID: 163 return true; 164 165 case Type::PointerTyID: { 166 const PointerType *PTy1 = cast<PointerType>(Ty1); 167 const PointerType *PTy2 = cast<PointerType>(Ty2); 168 return PTy1->getAddressSpace() == PTy2->getAddressSpace(); 169 } 170 171 case Type::StructTyID: { 172 const StructType *STy1 = cast<StructType>(Ty1); 173 const StructType *STy2 = cast<StructType>(Ty2); 174 if (STy1->getNumElements() != STy2->getNumElements()) 175 return false; 176 177 if (STy1->isPacked() != STy2->isPacked()) 178 return false; 179 180 for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) { 181 if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i))) 182 return false; 183 } 184 return true; 185 } 186 187 case Type::UnionTyID: { 188 const UnionType *UTy1 = cast<UnionType>(Ty1); 189 const UnionType *UTy2 = cast<UnionType>(Ty2); 190 191 // TODO: we could be fancy with union(A, union(A, B)) === union(A, B), etc. 192 if (UTy1->getNumElements() != UTy2->getNumElements()) 193 return false; 194 195 for (unsigned i = 0, e = UTy1->getNumElements(); i != e; ++i) { 196 if (!isEquivalentType(UTy1->getElementType(i), UTy2->getElementType(i))) 197 return false; 198 } 199 return true; 200 } 201 202 case Type::FunctionTyID: { 203 const FunctionType *FTy1 = cast<FunctionType>(Ty1); 204 const FunctionType *FTy2 = cast<FunctionType>(Ty2); 205 if (FTy1->getNumParams() != FTy2->getNumParams() || 206 FTy1->isVarArg() != FTy2->isVarArg()) 207 return false; 208 209 if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType())) 210 return false; 211 212 for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) { 213 if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i))) 214 return false; 215 } 216 return true; 217 } 218 219 case Type::ArrayTyID: 220 case Type::VectorTyID: { 221 const SequentialType *STy1 = cast<SequentialType>(Ty1); 222 const SequentialType *STy2 = cast<SequentialType>(Ty2); 223 return isEquivalentType(STy1->getElementType(), STy2->getElementType()); 224 } 225 } 226} 227 228/// isEquivalentOperation - determine whether the two operations are the same 229/// except that pointer-to-A and pointer-to-B are equivalent. This should be 230/// kept in sync with Instruction::isSameOperationAs. 231static bool 232isEquivalentOperation(const Instruction *I1, const Instruction *I2) { 233 if (I1->getOpcode() != I2->getOpcode() || 234 I1->getNumOperands() != I2->getNumOperands() || 235 !isEquivalentType(I1->getType(), I2->getType()) || 236 !I1->hasSameSubclassOptionalData(I2)) 237 return false; 238 239 // We have two instructions of identical opcode and #operands. Check to see 240 // if all operands are the same type 241 for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) 242 if (!isEquivalentType(I1->getOperand(i)->getType(), 243 I2->getOperand(i)->getType())) 244 return false; 245 246 // Check special state that is a part of some instructions. 247 if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) 248 return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() && 249 LI->getAlignment() == cast<LoadInst>(I2)->getAlignment(); 250 if (const StoreInst *SI = dyn_cast<StoreInst>(I1)) 251 return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() && 252 SI->getAlignment() == cast<StoreInst>(I2)->getAlignment(); 253 if (const CmpInst *CI = dyn_cast<CmpInst>(I1)) 254 return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate(); 255 if (const CallInst *CI = dyn_cast<CallInst>(I1)) 256 return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() && 257 CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() && 258 CI->getAttributes().getRawPointer() == 259 cast<CallInst>(I2)->getAttributes().getRawPointer(); 260 if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1)) 261 return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() && 262 CI->getAttributes().getRawPointer() == 263 cast<InvokeInst>(I2)->getAttributes().getRawPointer(); 264 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) { 265 if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices()) 266 return false; 267 for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) 268 if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i]) 269 return false; 270 return true; 271 } 272 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) { 273 if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices()) 274 return false; 275 for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) 276 if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i]) 277 return false; 278 return true; 279 } 280 281 return true; 282} 283 284bool MergeFunctions::isEquivalentGEP(const GetElementPtrInst *GEP1, 285 const GetElementPtrInst *GEP2) { 286 if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) { 287 SmallVector<Value *, 8> Indices1, Indices2; 288 for (GetElementPtrInst::const_op_iterator I = GEP1->idx_begin(), 289 E = GEP1->idx_end(); I != E; ++I) { 290 Indices1.push_back(*I); 291 } 292 for (GetElementPtrInst::const_op_iterator I = GEP2->idx_begin(), 293 E = GEP2->idx_end(); I != E; ++I) { 294 Indices2.push_back(*I); 295 } 296 uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(), 297 Indices1.data(), Indices1.size()); 298 uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(), 299 Indices2.data(), Indices2.size()); 300 return Offset1 == Offset2; 301 } 302 303 // Equivalent types aren't enough. 304 if (GEP1->getPointerOperand()->getType() != 305 GEP2->getPointerOperand()->getType()) 306 return false; 307 308 if (GEP1->getNumOperands() != GEP2->getNumOperands()) 309 return false; 310 311 for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) { 312 if (!compare(GEP1->getOperand(i), GEP2->getOperand(i))) 313 return false; 314 } 315 316 return true; 317} 318 319bool MergeFunctions::compare(const Value *V1, const Value *V2) { 320 if (V1 == LHS || V1 == RHS) 321 if (V2 == LHS || V2 == RHS) 322 return true; 323 324 // TODO: constant expressions in terms of LHS and RHS 325 if (isa<Constant>(V1)) 326 return V1 == V2; 327 328 if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) { 329 const InlineAsm *IA1 = cast<InlineAsm>(V1); 330 const InlineAsm *IA2 = cast<InlineAsm>(V2); 331 return IA1->getAsmString() == IA2->getAsmString() && 332 IA1->getConstraintString() == IA2->getConstraintString(); 333 } 334 335 // We enumerate constants globally and arguments, basic blocks or 336 // instructions within the function they belong to. 337 const Function *Domain1 = NULL; 338 if (const Argument *A = dyn_cast<Argument>(V1)) { 339 Domain1 = A->getParent(); 340 } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V1)) { 341 Domain1 = BB->getParent(); 342 } else if (const Instruction *I = dyn_cast<Instruction>(V1)) { 343 Domain1 = I->getParent()->getParent(); 344 } 345 346 const Function *Domain2 = NULL; 347 if (const Argument *A = dyn_cast<Argument>(V2)) { 348 Domain2 = A->getParent(); 349 } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V2)) { 350 Domain2 = BB->getParent(); 351 } else if (const Instruction *I = dyn_cast<Instruction>(V2)) { 352 Domain2 = I->getParent()->getParent(); 353 } 354 355 if (Domain1 != Domain2) 356 if (Domain1 != LHS && Domain1 != RHS) 357 if (Domain2 != LHS && Domain2 != RHS) 358 return false; 359 360 IDMap &Map1 = Domains[Domain1]; 361 unsigned long &ID1 = Map1[V1]; 362 if (!ID1) 363 ID1 = ++DomainCount[Domain1]; 364 365 IDMap &Map2 = Domains[Domain2]; 366 unsigned long &ID2 = Map2[V2]; 367 if (!ID2) 368 ID2 = ++DomainCount[Domain2]; 369 370 return ID1 == ID2; 371} 372 373bool MergeFunctions::equals(const BasicBlock *BB1, const BasicBlock *BB2) { 374 BasicBlock::const_iterator FI = BB1->begin(), FE = BB1->end(); 375 BasicBlock::const_iterator GI = BB2->begin(), GE = BB2->end(); 376 377 do { 378 if (!compare(FI, GI)) 379 return false; 380 381 if (isa<GetElementPtrInst>(FI) && isa<GetElementPtrInst>(GI)) { 382 const GetElementPtrInst *GEP1 = cast<GetElementPtrInst>(FI); 383 const GetElementPtrInst *GEP2 = cast<GetElementPtrInst>(GI); 384 385 if (!compare(GEP1->getPointerOperand(), GEP2->getPointerOperand())) 386 return false; 387 388 if (!isEquivalentGEP(GEP1, GEP2)) 389 return false; 390 } else { 391 if (!isEquivalentOperation(FI, GI)) 392 return false; 393 394 for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) { 395 Value *OpF = FI->getOperand(i); 396 Value *OpG = GI->getOperand(i); 397 398 if (!compare(OpF, OpG)) 399 return false; 400 401 if (OpF->getValueID() != OpG->getValueID() || 402 !isEquivalentType(OpF->getType(), OpG->getType())) 403 return false; 404 } 405 } 406 407 ++FI, ++GI; 408 } while (FI != FE && GI != GE); 409 410 return FI == FE && GI == GE; 411} 412 413bool MergeFunctions::equals(const Function *F, const Function *G) { 414 // We need to recheck everything, but check the things that weren't included 415 // in the hash first. 416 417 if (F->getAttributes() != G->getAttributes()) 418 return false; 419 420 if (F->hasGC() != G->hasGC()) 421 return false; 422 423 if (F->hasGC() && F->getGC() != G->getGC()) 424 return false; 425 426 if (F->hasSection() != G->hasSection()) 427 return false; 428 429 if (F->hasSection() && F->getSection() != G->getSection()) 430 return false; 431 432 if (F->isVarArg() != G->isVarArg()) 433 return false; 434 435 // TODO: if it's internal and only used in direct calls, we could handle this 436 // case too. 437 if (F->getCallingConv() != G->getCallingConv()) 438 return false; 439 440 if (!isEquivalentType(F->getFunctionType(), G->getFunctionType())) 441 return false; 442 443 assert(F->arg_size() == G->arg_size() && 444 "Identical functions have a different number of args."); 445 446 LHS = F; 447 RHS = G; 448 449 // Visit the arguments so that they get enumerated in the order they're 450 // passed in. 451 for (Function::const_arg_iterator fi = F->arg_begin(), gi = G->arg_begin(), 452 fe = F->arg_end(); fi != fe; ++fi, ++gi) { 453 if (!compare(fi, gi)) 454 llvm_unreachable("Arguments repeat"); 455 } 456 457 SmallVector<const BasicBlock *, 8> FBBs, GBBs; 458 SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F. 459 FBBs.push_back(&F->getEntryBlock()); 460 GBBs.push_back(&G->getEntryBlock()); 461 VisitedBBs.insert(FBBs[0]); 462 while (!FBBs.empty()) { 463 const BasicBlock *FBB = FBBs.pop_back_val(); 464 const BasicBlock *GBB = GBBs.pop_back_val(); 465 if (!compare(FBB, GBB) || !equals(FBB, GBB)) { 466 Domains.clear(); 467 DomainCount.clear(); 468 return false; 469 } 470 const TerminatorInst *FTI = FBB->getTerminator(); 471 const TerminatorInst *GTI = GBB->getTerminator(); 472 assert(FTI->getNumSuccessors() == GTI->getNumSuccessors()); 473 for (unsigned i = 0, e = FTI->getNumSuccessors(); i != e; ++i) { 474 if (!VisitedBBs.insert(FTI->getSuccessor(i))) 475 continue; 476 FBBs.push_back(FTI->getSuccessor(i)); 477 GBBs.push_back(GTI->getSuccessor(i)); 478 } 479 } 480 481 Domains.clear(); 482 DomainCount.clear(); 483 return true; 484} 485 486// ===----------------------------------------------------------------------=== 487// Folding of functions 488// ===----------------------------------------------------------------------=== 489 490// Cases: 491// * F is external strong, G is external strong: 492// turn G into a thunk to F (1) 493// * F is external strong, G is external weak: 494// turn G into a thunk to F (1) 495// * F is external weak, G is external weak: 496// unfoldable 497// * F is external strong, G is internal: 498// address of G taken: 499// turn G into a thunk to F (1) 500// address of G not taken: 501// make G an alias to F (2) 502// * F is internal, G is external weak 503// address of F is taken: 504// turn G into a thunk to F (1) 505// address of F is not taken: 506// make G an alias of F (2) 507// * F is internal, G is internal: 508// address of F and G are taken: 509// turn G into a thunk to F (1) 510// address of G is not taken: 511// make G an alias to F (2) 512// 513// alias requires linkage == (external,local,weak) fallback to creating a thunk 514// external means 'externally visible' linkage != (internal,private) 515// internal means linkage == (internal,private) 516// weak means linkage mayBeOverridable 517// being external implies that the address is taken 518// 519// 1. turn G into a thunk to F 520// 2. make G an alias to F 521 522enum LinkageCategory { 523 ExternalStrong, 524 ExternalWeak, 525 Internal 526}; 527 528static LinkageCategory categorize(const Function *F) { 529 switch (F->getLinkage()) { 530 case GlobalValue::InternalLinkage: 531 case GlobalValue::PrivateLinkage: 532 case GlobalValue::LinkerPrivateLinkage: 533 return Internal; 534 535 case GlobalValue::WeakAnyLinkage: 536 case GlobalValue::WeakODRLinkage: 537 case GlobalValue::ExternalWeakLinkage: 538 case GlobalValue::LinkerPrivateWeakLinkage: 539 return ExternalWeak; 540 541 case GlobalValue::ExternalLinkage: 542 case GlobalValue::AvailableExternallyLinkage: 543 case GlobalValue::LinkOnceAnyLinkage: 544 case GlobalValue::LinkOnceODRLinkage: 545 case GlobalValue::AppendingLinkage: 546 case GlobalValue::DLLImportLinkage: 547 case GlobalValue::DLLExportLinkage: 548 case GlobalValue::CommonLinkage: 549 return ExternalStrong; 550 } 551 552 llvm_unreachable("Unknown LinkageType."); 553 return ExternalWeak; 554} 555 556static void ThunkGToF(Function *F, Function *G) { 557 if (!G->mayBeOverridden()) { 558 // Redirect direct callers of G to F. 559 Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 560 for (Value::use_iterator UI = G->use_begin(), UE = G->use_end(); 561 UI != UE;) { 562 Value::use_iterator TheIter = UI; 563 ++UI; 564 CallSite CS(*TheIter); 565 if (CS && CS.isCallee(TheIter)) 566 TheIter.getUse().set(BitcastF); 567 } 568 } 569 570 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 571 G->getParent()); 572 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 573 574 SmallVector<Value *, 16> Args; 575 unsigned i = 0; 576 const FunctionType *FFTy = F->getFunctionType(); 577 for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 578 AI != AE; ++AI) { 579 if (FFTy->getParamType(i) == AI->getType()) { 580 Args.push_back(AI); 581 } else { 582 Args.push_back(new BitCastInst(AI, FFTy->getParamType(i), "", BB)); 583 } 584 ++i; 585 } 586 587 CallInst *CI = CallInst::Create(F, Args.begin(), Args.end(), "", BB); 588 CI->setTailCall(); 589 CI->setCallingConv(F->getCallingConv()); 590 if (NewG->getReturnType()->isVoidTy()) { 591 ReturnInst::Create(F->getContext(), BB); 592 } else if (CI->getType() != NewG->getReturnType()) { 593 Value *BCI = new BitCastInst(CI, NewG->getReturnType(), "", BB); 594 ReturnInst::Create(F->getContext(), BCI, BB); 595 } else { 596 ReturnInst::Create(F->getContext(), CI, BB); 597 } 598 599 NewG->copyAttributesFrom(G); 600 NewG->takeName(G); 601 G->replaceAllUsesWith(NewG); 602 G->eraseFromParent(); 603} 604 605static void AliasGToF(Function *F, Function *G) { 606 // Darwin will trigger llvm_unreachable if asked to codegen an alias 607 return ThunkGToF(F, G); 608 609#if 0 610 if (!G->hasExternalLinkage() && !G->hasLocalLinkage() && !G->hasWeakLinkage()) 611 return ThunkGToF(F, G); 612 613 GlobalAlias *GA = new GlobalAlias( 614 G->getType(), G->getLinkage(), "", 615 ConstantExpr::getBitCast(F, G->getType()), G->getParent()); 616 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 617 GA->takeName(G); 618 GA->setVisibility(G->getVisibility()); 619 G->replaceAllUsesWith(GA); 620 G->eraseFromParent(); 621#endif 622} 623 624static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) { 625 Function *F = FnVec[i]; 626 Function *G = FnVec[j]; 627 628 LinkageCategory catF = categorize(F); 629 LinkageCategory catG = categorize(G); 630 631 if (catF == ExternalWeak || (catF == Internal && catG == ExternalStrong)) { 632 std::swap(FnVec[i], FnVec[j]); 633 std::swap(F, G); 634 std::swap(catF, catG); 635 } 636 637 switch (catF) { 638 case ExternalStrong: 639 switch (catG) { 640 case ExternalStrong: 641 case ExternalWeak: 642 ThunkGToF(F, G); 643 break; 644 case Internal: 645 if (G->hasAddressTaken()) 646 ThunkGToF(F, G); 647 else 648 AliasGToF(F, G); 649 break; 650 } 651 break; 652 653 case ExternalWeak: { 654 assert(catG == ExternalWeak); 655 656 // Make them both thunks to the same internal function. 657 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 658 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 659 F->getParent()); 660 H->copyAttributesFrom(F); 661 H->takeName(F); 662 F->replaceAllUsesWith(H); 663 664 ThunkGToF(F, G); 665 ThunkGToF(F, H); 666 667 F->setLinkage(GlobalValue::InternalLinkage); 668 } break; 669 670 case Internal: 671 switch (catG) { 672 case ExternalStrong: 673 llvm_unreachable(0); 674 // fall-through 675 case ExternalWeak: 676 if (F->hasAddressTaken()) 677 ThunkGToF(F, G); 678 else 679 AliasGToF(F, G); 680 break; 681 case Internal: { 682 bool addrTakenF = F->hasAddressTaken(); 683 bool addrTakenG = G->hasAddressTaken(); 684 if (!addrTakenF && addrTakenG) { 685 std::swap(FnVec[i], FnVec[j]); 686 std::swap(F, G); 687 std::swap(addrTakenF, addrTakenG); 688 } 689 690 if (addrTakenF && addrTakenG) { 691 ThunkGToF(F, G); 692 } else { 693 assert(!addrTakenG); 694 AliasGToF(F, G); 695 } 696 } break; 697 } break; 698 } 699 700 ++NumFunctionsMerged; 701 return true; 702} 703 704// ===----------------------------------------------------------------------=== 705// Pass definition 706// ===----------------------------------------------------------------------=== 707 708bool MergeFunctions::runOnModule(Module &M) { 709 bool Changed = false; 710 711 std::map<unsigned long, std::vector<Function *> > FnMap; 712 713 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 714 if (F->isDeclaration()) 715 continue; 716 717 FnMap[hash(F)].push_back(F); 718 } 719 720 TD = getAnalysisIfAvailable<TargetData>(); 721 722 bool LocalChanged; 723 do { 724 LocalChanged = false; 725 DEBUG(dbgs() << "size: " << FnMap.size() << "\n"); 726 for (std::map<unsigned long, std::vector<Function *> >::iterator 727 I = FnMap.begin(), E = FnMap.end(); I != E; ++I) { 728 std::vector<Function *> &FnVec = I->second; 729 DEBUG(dbgs() << "hash (" << I->first << "): " << FnVec.size() << "\n"); 730 731 for (int i = 0, e = FnVec.size(); i != e; ++i) { 732 for (int j = i + 1; j != e; ++j) { 733 bool isEqual = equals(FnVec[i], FnVec[j]); 734 735 DEBUG(dbgs() << " " << FnVec[i]->getName() 736 << (isEqual ? " == " : " != ") 737 << FnVec[j]->getName() << "\n"); 738 739 if (isEqual) { 740 if (fold(FnVec, i, j)) { 741 LocalChanged = true; 742 FnVec.erase(FnVec.begin() + j); 743 --j, --e; 744 } 745 } 746 } 747 } 748 749 } 750 Changed |= LocalChanged; 751 } while (LocalChanged); 752 753 return Changed; 754} 755