MergeFunctions.cpp revision f5db8d3671fd4faf65f6a63ed1910cf801fa10f9
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 const ArrayType *ATy1 = cast<ArrayType>(Ty1); 221 const ArrayType *ATy2 = cast<ArrayType>(Ty2); 222 return ATy1->getNumElements() == ATy2->getNumElements() && 223 isEquivalentType(ATy1->getElementType(), ATy2->getElementType()); 224 } 225 case Type::VectorTyID: { 226 const VectorType *VTy1 = cast<VectorType>(Ty1); 227 const VectorType *VTy2 = cast<VectorType>(Ty2); 228 return VTy1->getNumElements() == VTy2->getNumElements() && 229 isEquivalentType(VTy1->getElementType(), VTy2->getElementType()); 230 } 231 } 232} 233 234/// isEquivalentOperation - determine whether the two operations are the same 235/// except that pointer-to-A and pointer-to-B are equivalent. This should be 236/// kept in sync with Instruction::isSameOperationAs. 237static bool 238isEquivalentOperation(const Instruction *I1, const Instruction *I2) { 239 if (I1->getOpcode() != I2->getOpcode() || 240 I1->getNumOperands() != I2->getNumOperands() || 241 !isEquivalentType(I1->getType(), I2->getType()) || 242 !I1->hasSameSubclassOptionalData(I2)) 243 return false; 244 245 // We have two instructions of identical opcode and #operands. Check to see 246 // if all operands are the same type 247 for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) 248 if (!isEquivalentType(I1->getOperand(i)->getType(), 249 I2->getOperand(i)->getType())) 250 return false; 251 252 // Check special state that is a part of some instructions. 253 if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) 254 return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() && 255 LI->getAlignment() == cast<LoadInst>(I2)->getAlignment(); 256 if (const StoreInst *SI = dyn_cast<StoreInst>(I1)) 257 return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() && 258 SI->getAlignment() == cast<StoreInst>(I2)->getAlignment(); 259 if (const CmpInst *CI = dyn_cast<CmpInst>(I1)) 260 return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate(); 261 if (const CallInst *CI = dyn_cast<CallInst>(I1)) 262 return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() && 263 CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() && 264 CI->getAttributes().getRawPointer() == 265 cast<CallInst>(I2)->getAttributes().getRawPointer(); 266 if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1)) 267 return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() && 268 CI->getAttributes().getRawPointer() == 269 cast<InvokeInst>(I2)->getAttributes().getRawPointer(); 270 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) { 271 if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices()) 272 return false; 273 for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) 274 if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i]) 275 return false; 276 return true; 277 } 278 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) { 279 if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices()) 280 return false; 281 for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) 282 if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i]) 283 return false; 284 return true; 285 } 286 287 return true; 288} 289 290bool MergeFunctions::isEquivalentGEP(const GetElementPtrInst *GEP1, 291 const GetElementPtrInst *GEP2) { 292 if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) { 293 SmallVector<Value *, 8> Indices1, Indices2; 294 for (GetElementPtrInst::const_op_iterator I = GEP1->idx_begin(), 295 E = GEP1->idx_end(); I != E; ++I) { 296 Indices1.push_back(*I); 297 } 298 for (GetElementPtrInst::const_op_iterator I = GEP2->idx_begin(), 299 E = GEP2->idx_end(); I != E; ++I) { 300 Indices2.push_back(*I); 301 } 302 uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(), 303 Indices1.data(), Indices1.size()); 304 uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(), 305 Indices2.data(), Indices2.size()); 306 return Offset1 == Offset2; 307 } 308 309 // Equivalent types aren't enough. 310 if (GEP1->getPointerOperand()->getType() != 311 GEP2->getPointerOperand()->getType()) 312 return false; 313 314 if (GEP1->getNumOperands() != GEP2->getNumOperands()) 315 return false; 316 317 for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) { 318 if (!compare(GEP1->getOperand(i), GEP2->getOperand(i))) 319 return false; 320 } 321 322 return true; 323} 324 325bool MergeFunctions::compare(const Value *V1, const Value *V2) { 326 if (V1 == LHS || V1 == RHS) 327 if (V2 == LHS || V2 == RHS) 328 return true; 329 330 // TODO: constant expressions in terms of LHS and RHS 331 if (isa<Constant>(V1)) 332 return V1 == V2; 333 334 if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) { 335 const InlineAsm *IA1 = cast<InlineAsm>(V1); 336 const InlineAsm *IA2 = cast<InlineAsm>(V2); 337 return IA1->getAsmString() == IA2->getAsmString() && 338 IA1->getConstraintString() == IA2->getConstraintString(); 339 } 340 341 // We enumerate constants globally and arguments, basic blocks or 342 // instructions within the function they belong to. 343 const Function *Domain1 = NULL; 344 if (const Argument *A = dyn_cast<Argument>(V1)) { 345 Domain1 = A->getParent(); 346 } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V1)) { 347 Domain1 = BB->getParent(); 348 } else if (const Instruction *I = dyn_cast<Instruction>(V1)) { 349 Domain1 = I->getParent()->getParent(); 350 } 351 352 const Function *Domain2 = NULL; 353 if (const Argument *A = dyn_cast<Argument>(V2)) { 354 Domain2 = A->getParent(); 355 } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V2)) { 356 Domain2 = BB->getParent(); 357 } else if (const Instruction *I = dyn_cast<Instruction>(V2)) { 358 Domain2 = I->getParent()->getParent(); 359 } 360 361 if (Domain1 != Domain2) 362 if (Domain1 != LHS && Domain1 != RHS) 363 if (Domain2 != LHS && Domain2 != RHS) 364 return false; 365 366 IDMap &Map1 = Domains[Domain1]; 367 unsigned long &ID1 = Map1[V1]; 368 if (!ID1) 369 ID1 = ++DomainCount[Domain1]; 370 371 IDMap &Map2 = Domains[Domain2]; 372 unsigned long &ID2 = Map2[V2]; 373 if (!ID2) 374 ID2 = ++DomainCount[Domain2]; 375 376 return ID1 == ID2; 377} 378 379bool MergeFunctions::equals(const BasicBlock *BB1, const BasicBlock *BB2) { 380 BasicBlock::const_iterator FI = BB1->begin(), FE = BB1->end(); 381 BasicBlock::const_iterator GI = BB2->begin(), GE = BB2->end(); 382 383 do { 384 if (!compare(FI, GI)) 385 return false; 386 387 if (isa<GetElementPtrInst>(FI) && isa<GetElementPtrInst>(GI)) { 388 const GetElementPtrInst *GEP1 = cast<GetElementPtrInst>(FI); 389 const GetElementPtrInst *GEP2 = cast<GetElementPtrInst>(GI); 390 391 if (!compare(GEP1->getPointerOperand(), GEP2->getPointerOperand())) 392 return false; 393 394 if (!isEquivalentGEP(GEP1, GEP2)) 395 return false; 396 } else { 397 if (!isEquivalentOperation(FI, GI)) 398 return false; 399 400 for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) { 401 Value *OpF = FI->getOperand(i); 402 Value *OpG = GI->getOperand(i); 403 404 if (!compare(OpF, OpG)) 405 return false; 406 407 if (OpF->getValueID() != OpG->getValueID() || 408 !isEquivalentType(OpF->getType(), OpG->getType())) 409 return false; 410 } 411 } 412 413 ++FI, ++GI; 414 } while (FI != FE && GI != GE); 415 416 return FI == FE && GI == GE; 417} 418 419bool MergeFunctions::equals(const Function *F, const Function *G) { 420 // We need to recheck everything, but check the things that weren't included 421 // in the hash first. 422 423 if (F->getAttributes() != G->getAttributes()) 424 return false; 425 426 if (F->hasGC() != G->hasGC()) 427 return false; 428 429 if (F->hasGC() && F->getGC() != G->getGC()) 430 return false; 431 432 if (F->hasSection() != G->hasSection()) 433 return false; 434 435 if (F->hasSection() && F->getSection() != G->getSection()) 436 return false; 437 438 if (F->isVarArg() != G->isVarArg()) 439 return false; 440 441 // TODO: if it's internal and only used in direct calls, we could handle this 442 // case too. 443 if (F->getCallingConv() != G->getCallingConv()) 444 return false; 445 446 if (!isEquivalentType(F->getFunctionType(), G->getFunctionType())) 447 return false; 448 449 assert(F->arg_size() == G->arg_size() && 450 "Identical functions have a different number of args."); 451 452 LHS = F; 453 RHS = G; 454 455 // Visit the arguments so that they get enumerated in the order they're 456 // passed in. 457 for (Function::const_arg_iterator fi = F->arg_begin(), gi = G->arg_begin(), 458 fe = F->arg_end(); fi != fe; ++fi, ++gi) { 459 if (!compare(fi, gi)) 460 llvm_unreachable("Arguments repeat"); 461 } 462 463 SmallVector<const BasicBlock *, 8> FBBs, GBBs; 464 SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F. 465 FBBs.push_back(&F->getEntryBlock()); 466 GBBs.push_back(&G->getEntryBlock()); 467 VisitedBBs.insert(FBBs[0]); 468 while (!FBBs.empty()) { 469 const BasicBlock *FBB = FBBs.pop_back_val(); 470 const BasicBlock *GBB = GBBs.pop_back_val(); 471 if (!compare(FBB, GBB) || !equals(FBB, GBB)) { 472 Domains.clear(); 473 DomainCount.clear(); 474 return false; 475 } 476 const TerminatorInst *FTI = FBB->getTerminator(); 477 const TerminatorInst *GTI = GBB->getTerminator(); 478 assert(FTI->getNumSuccessors() == GTI->getNumSuccessors()); 479 for (unsigned i = 0, e = FTI->getNumSuccessors(); i != e; ++i) { 480 if (!VisitedBBs.insert(FTI->getSuccessor(i))) 481 continue; 482 FBBs.push_back(FTI->getSuccessor(i)); 483 GBBs.push_back(GTI->getSuccessor(i)); 484 } 485 } 486 487 Domains.clear(); 488 DomainCount.clear(); 489 return true; 490} 491 492// ===----------------------------------------------------------------------=== 493// Folding of functions 494// ===----------------------------------------------------------------------=== 495 496// Cases: 497// * F is external strong, G is external strong: 498// turn G into a thunk to F (1) 499// * F is external strong, G is external weak: 500// turn G into a thunk to F (1) 501// * F is external weak, G is external weak: 502// unfoldable 503// * F is external strong, G is internal: 504// address of G taken: 505// turn G into a thunk to F (1) 506// address of G not taken: 507// make G an alias to F (2) 508// * F is internal, G is external weak 509// address of F is taken: 510// turn G into a thunk to F (1) 511// address of F is not taken: 512// make G an alias of F (2) 513// * F is internal, G is internal: 514// address of F and G are taken: 515// turn G into a thunk to F (1) 516// address of G is not taken: 517// make G an alias to F (2) 518// 519// alias requires linkage == (external,local,weak) fallback to creating a thunk 520// external means 'externally visible' linkage != (internal,private) 521// internal means linkage == (internal,private) 522// weak means linkage mayBeOverridable 523// being external implies that the address is taken 524// 525// 1. turn G into a thunk to F 526// 2. make G an alias to F 527 528enum LinkageCategory { 529 ExternalStrong, 530 ExternalWeak, 531 Internal 532}; 533 534static LinkageCategory categorize(const Function *F) { 535 switch (F->getLinkage()) { 536 case GlobalValue::InternalLinkage: 537 case GlobalValue::PrivateLinkage: 538 case GlobalValue::LinkerPrivateLinkage: 539 return Internal; 540 541 case GlobalValue::WeakAnyLinkage: 542 case GlobalValue::WeakODRLinkage: 543 case GlobalValue::ExternalWeakLinkage: 544 case GlobalValue::LinkerPrivateWeakLinkage: 545 return ExternalWeak; 546 547 case GlobalValue::ExternalLinkage: 548 case GlobalValue::AvailableExternallyLinkage: 549 case GlobalValue::LinkOnceAnyLinkage: 550 case GlobalValue::LinkOnceODRLinkage: 551 case GlobalValue::AppendingLinkage: 552 case GlobalValue::DLLImportLinkage: 553 case GlobalValue::DLLExportLinkage: 554 case GlobalValue::CommonLinkage: 555 return ExternalStrong; 556 } 557 558 llvm_unreachable("Unknown LinkageType."); 559 return ExternalWeak; 560} 561 562static void ThunkGToF(Function *F, Function *G) { 563 if (!G->mayBeOverridden()) { 564 // Redirect direct callers of G to F. 565 Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 566 for (Value::use_iterator UI = G->use_begin(), UE = G->use_end(); 567 UI != UE;) { 568 Value::use_iterator TheIter = UI; 569 ++UI; 570 CallSite CS(*TheIter); 571 if (CS && CS.isCallee(TheIter)) 572 TheIter.getUse().set(BitcastF); 573 } 574 } 575 576 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 577 G->getParent()); 578 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 579 580 SmallVector<Value *, 16> Args; 581 unsigned i = 0; 582 const FunctionType *FFTy = F->getFunctionType(); 583 for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 584 AI != AE; ++AI) { 585 if (FFTy->getParamType(i) == AI->getType()) { 586 Args.push_back(AI); 587 } else { 588 Args.push_back(new BitCastInst(AI, FFTy->getParamType(i), "", BB)); 589 } 590 ++i; 591 } 592 593 CallInst *CI = CallInst::Create(F, Args.begin(), Args.end(), "", BB); 594 CI->setTailCall(); 595 CI->setCallingConv(F->getCallingConv()); 596 if (NewG->getReturnType()->isVoidTy()) { 597 ReturnInst::Create(F->getContext(), BB); 598 } else if (CI->getType() != NewG->getReturnType()) { 599 Value *BCI = new BitCastInst(CI, NewG->getReturnType(), "", BB); 600 ReturnInst::Create(F->getContext(), BCI, BB); 601 } else { 602 ReturnInst::Create(F->getContext(), CI, BB); 603 } 604 605 NewG->copyAttributesFrom(G); 606 NewG->takeName(G); 607 G->replaceAllUsesWith(NewG); 608 G->eraseFromParent(); 609} 610 611static void AliasGToF(Function *F, Function *G) { 612 // Darwin will trigger llvm_unreachable if asked to codegen an alias. 613 return ThunkGToF(F, G); 614 615#if 0 616 if (!G->hasExternalLinkage() && !G->hasLocalLinkage() && !G->hasWeakLinkage()) 617 return ThunkGToF(F, G); 618 619 GlobalAlias *GA = new GlobalAlias( 620 G->getType(), G->getLinkage(), "", 621 ConstantExpr::getBitCast(F, G->getType()), G->getParent()); 622 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 623 GA->takeName(G); 624 GA->setVisibility(G->getVisibility()); 625 G->replaceAllUsesWith(GA); 626 G->eraseFromParent(); 627#endif 628} 629 630static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) { 631 Function *F = FnVec[i]; 632 Function *G = FnVec[j]; 633 634 LinkageCategory catF = categorize(F); 635 LinkageCategory catG = categorize(G); 636 637 if (catF == ExternalWeak || (catF == Internal && catG == ExternalStrong)) { 638 std::swap(FnVec[i], FnVec[j]); 639 std::swap(F, G); 640 std::swap(catF, catG); 641 } 642 643 switch (catF) { 644 case ExternalStrong: 645 switch (catG) { 646 case ExternalStrong: 647 case ExternalWeak: 648 ThunkGToF(F, G); 649 break; 650 case Internal: 651 if (G->hasAddressTaken()) 652 ThunkGToF(F, G); 653 else 654 AliasGToF(F, G); 655 break; 656 } 657 break; 658 659 case ExternalWeak: { 660 assert(catG == ExternalWeak); 661 662 // Make them both thunks to the same internal function. 663 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 664 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 665 F->getParent()); 666 H->copyAttributesFrom(F); 667 H->takeName(F); 668 F->replaceAllUsesWith(H); 669 670 ThunkGToF(F, G); 671 ThunkGToF(F, H); 672 673 F->setLinkage(GlobalValue::InternalLinkage); 674 } break; 675 676 case Internal: 677 switch (catG) { 678 case ExternalStrong: 679 llvm_unreachable(0); 680 // fall-through 681 case ExternalWeak: 682 if (F->hasAddressTaken()) 683 ThunkGToF(F, G); 684 else 685 AliasGToF(F, G); 686 break; 687 case Internal: { 688 bool addrTakenF = F->hasAddressTaken(); 689 bool addrTakenG = G->hasAddressTaken(); 690 if (!addrTakenF && addrTakenG) { 691 std::swap(FnVec[i], FnVec[j]); 692 std::swap(F, G); 693 std::swap(addrTakenF, addrTakenG); 694 } 695 696 if (addrTakenF && addrTakenG) { 697 ThunkGToF(F, G); 698 } else { 699 assert(!addrTakenG); 700 AliasGToF(F, G); 701 } 702 } break; 703 } break; 704 } 705 706 ++NumFunctionsMerged; 707 return true; 708} 709 710// ===----------------------------------------------------------------------=== 711// Pass definition 712// ===----------------------------------------------------------------------=== 713 714bool MergeFunctions::runOnModule(Module &M) { 715 bool Changed = false; 716 717 std::map<unsigned long, std::vector<Function *> > FnMap; 718 719 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 720 if (F->isDeclaration()) 721 continue; 722 723 FnMap[hash(F)].push_back(F); 724 } 725 726 TD = getAnalysisIfAvailable<TargetData>(); 727 728 bool LocalChanged; 729 do { 730 LocalChanged = false; 731 DEBUG(dbgs() << "size: " << FnMap.size() << "\n"); 732 for (std::map<unsigned long, std::vector<Function *> >::iterator 733 I = FnMap.begin(), E = FnMap.end(); I != E; ++I) { 734 std::vector<Function *> &FnVec = I->second; 735 DEBUG(dbgs() << "hash (" << I->first << "): " << FnVec.size() << "\n"); 736 737 for (int i = 0, e = FnVec.size(); i != e; ++i) { 738 for (int j = i + 1; j != e; ++j) { 739 bool isEqual = equals(FnVec[i], FnVec[j]); 740 741 DEBUG(dbgs() << " " << FnVec[i]->getName() 742 << (isEqual ? " == " : " != ") 743 << FnVec[j]->getName() << "\n"); 744 745 if (isEqual) { 746 if (fold(FnVec, i, j)) { 747 LocalChanged = true; 748 FnVec.erase(FnVec.begin() + j); 749 --j, --e; 750 } 751 } 752 } 753 } 754 755 } 756 Changed |= LocalChanged; 757 } while (LocalChanged); 758 759 return Changed; 760} 761