MergeFunctions.cpp revision 218893
1193326Sed//===- MergeFunctions.cpp - Merge identical functions ---------------------===// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10198092Srdivacky// This pass looks for equivalent functions that are mergable and folds them. 11193326Sed// 12193326Sed// A hash is computed from the function, based on its type and number of 13193326Sed// basic blocks. 14193326Sed// 15280031Sdim// Once all hashes are computed, we perform an expensive equality comparison 16280031Sdim// on each function pair. This takes n^2/2 comparisons per bucket, so it's 17193326Sed// important that the hash function be high quality. The equality comparison 18193326Sed// iterates through each instruction in each basic block. 19249423Sdim// 20193326Sed// When a match is found the functions are folded. If both functions are 21193326Sed// overridable, we move the functionality into a new internal function and 22193326Sed// leave two overridable thunks to it. 23198092Srdivacky// 24193326Sed//===----------------------------------------------------------------------===// 25193326Sed// 26193326Sed// Future work: 27193326Sed// 28193326Sed// * virtual functions. 29193326Sed// 30193326Sed// Many functions have their address taken by the virtual function table for 31198092Srdivacky// the object they belong to. However, as long as it's only used for a lookup 32193326Sed// and call, this is irrelevant, and we'd like to fold such functions. 33198092Srdivacky// 34193326Sed// * switch from n^2 pair-wise comparisons to an n-way comparison for each 35193326Sed// bucket. 36193326Sed// 37193326Sed// * be smarter about bitcasts. 38198092Srdivacky// 39193326Sed// In order to fold functions, we will sometimes add either bitcast instructions 40193326Sed// or bitcast constant expressions. Unfortunately, this can confound further 41193326Sed// analysis since the two functions differ where one has a bitcast and the 42193326Sed// other doesn't. We should learn to look through bitcasts. 43198092Srdivacky// 44193326Sed//===----------------------------------------------------------------------===// 45193326Sed 46193326Sed#define DEBUG_TYPE "mergefunc" 47198092Srdivacky#include "llvm/Transforms/IPO.h" 48193326Sed#include "llvm/ADT/DenseSet.h" 49193326Sed#include "llvm/ADT/FoldingSet.h" 50193326Sed#include "llvm/ADT/SmallSet.h" 51193326Sed#include "llvm/ADT/Statistic.h" 52193326Sed#include "llvm/ADT/STLExtras.h" 53193326Sed#include "llvm/Constants.h" 54193326Sed#include "llvm/InlineAsm.h" 55193326Sed#include "llvm/Instructions.h" 56193326Sed#include "llvm/LLVMContext.h" 57193326Sed#include "llvm/Module.h" 58198092Srdivacky#include "llvm/Pass.h" 59193326Sed#include "llvm/Support/CallSite.h" 60198092Srdivacky#include "llvm/Support/Debug.h" 61193326Sed#include "llvm/Support/ErrorHandling.h" 62193326Sed#include "llvm/Support/IRBuilder.h" 63198092Srdivacky#include "llvm/Support/ValueHandle.h" 64193326Sed#include "llvm/Support/raw_ostream.h" 65198092Srdivacky#include "llvm/Target/TargetData.h" 66193326Sed#include <vector> 67193326Sedusing namespace llvm; 68193326Sed 69193326SedSTATISTIC(NumFunctionsMerged, "Number of functions merged"); 70198092SrdivackySTATISTIC(NumThunksWritten, "Number of thunks generated"); 71193326SedSTATISTIC(NumAliasesWritten, "Number of aliases generated"); 72193326SedSTATISTIC(NumDoubleWeak, "Number of new functions created"); 73193326Sed 74198092Srdivacky/// Creates a hash-code for the function which is the same for any two 75193326Sed/// functions that will compare equal, without looking at the instructions 76193326Sed/// inside the function. 77193326Sedstatic unsigned profileFunction(const Function *F) { 78193326Sed const FunctionType *FTy = F->getFunctionType(); 79193326Sed 80198092Srdivacky FoldingSetNodeID ID; 81193326Sed ID.AddInteger(F->size()); 82193326Sed ID.AddInteger(F->getCallingConv()); 83193326Sed ID.AddBoolean(F->hasGC()); 84 ID.AddBoolean(FTy->isVarArg()); 85 ID.AddInteger(FTy->getReturnType()->getTypeID()); 86 for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) 87 ID.AddInteger(FTy->getParamType(i)->getTypeID()); 88 return ID.ComputeHash(); 89} 90 91namespace { 92 93/// ComparableFunction - A struct that pairs together functions with a 94/// TargetData so that we can keep them together as elements in the DenseSet. 95class ComparableFunction { 96public: 97 static const ComparableFunction EmptyKey; 98 static const ComparableFunction TombstoneKey; 99 static TargetData * const LookupOnly; 100 101 ComparableFunction(Function *Func, TargetData *TD) 102 : Func(Func), Hash(profileFunction(Func)), TD(TD) {} 103 104 Function *getFunc() const { return Func; } 105 unsigned getHash() const { return Hash; } 106 TargetData *getTD() const { return TD; } 107 108 // Drops AssertingVH reference to the function. Outside of debug mode, this 109 // does nothing. 110 void release() { 111 assert(Func && 112 "Attempted to release function twice, or release empty/tombstone!"); 113 Func = NULL; 114 } 115 116private: 117 explicit ComparableFunction(unsigned Hash) 118 : Func(NULL), Hash(Hash), TD(NULL) {} 119 120 AssertingVH<Function> Func; 121 unsigned Hash; 122 TargetData *TD; 123}; 124 125const ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0); 126const ComparableFunction ComparableFunction::TombstoneKey = 127 ComparableFunction(1); 128TargetData * const ComparableFunction::LookupOnly = (TargetData*)(-1); 129 130} 131 132namespace llvm { 133 template <> 134 struct DenseMapInfo<ComparableFunction> { 135 static ComparableFunction getEmptyKey() { 136 return ComparableFunction::EmptyKey; 137 } 138 static ComparableFunction getTombstoneKey() { 139 return ComparableFunction::TombstoneKey; 140 } 141 static unsigned getHashValue(const ComparableFunction &CF) { 142 return CF.getHash(); 143 } 144 static bool isEqual(const ComparableFunction &LHS, 145 const ComparableFunction &RHS); 146 }; 147} 148 149namespace { 150 151/// FunctionComparator - Compares two functions to determine whether or not 152/// they will generate machine code with the same behaviour. TargetData is 153/// used if available. The comparator always fails conservatively (erring on the 154/// side of claiming that two functions are different). 155class FunctionComparator { 156public: 157 FunctionComparator(const TargetData *TD, const Function *F1, 158 const Function *F2) 159 : F1(F1), F2(F2), TD(TD) {} 160 161 /// Test whether the two functions have equivalent behaviour. 162 bool compare(); 163 164private: 165 /// Test whether two basic blocks have equivalent behaviour. 166 bool compare(const BasicBlock *BB1, const BasicBlock *BB2); 167 168 /// Assign or look up previously assigned numbers for the two values, and 169 /// return whether the numbers are equal. Numbers are assigned in the order 170 /// visited. 171 bool enumerate(const Value *V1, const Value *V2); 172 173 /// Compare two Instructions for equivalence, similar to 174 /// Instruction::isSameOperationAs but with modifications to the type 175 /// comparison. 176 bool isEquivalentOperation(const Instruction *I1, 177 const Instruction *I2) const; 178 179 /// Compare two GEPs for equivalent pointer arithmetic. 180 bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2); 181 bool isEquivalentGEP(const GetElementPtrInst *GEP1, 182 const GetElementPtrInst *GEP2) { 183 return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2)); 184 } 185 186 /// Compare two Types, treating all pointer types as equal. 187 bool isEquivalentType(const Type *Ty1, const Type *Ty2) const; 188 189 // The two functions undergoing comparison. 190 const Function *F1, *F2; 191 192 const TargetData *TD; 193 194 DenseMap<const Value *, const Value *> id_map; 195 DenseSet<const Value *> seen_values; 196}; 197 198} 199 200// Any two pointers in the same address space are equivalent, intptr_t and 201// pointers are equivalent. Otherwise, standard type equivalence rules apply. 202bool FunctionComparator::isEquivalentType(const Type *Ty1, 203 const Type *Ty2) const { 204 if (Ty1 == Ty2) 205 return true; 206 if (Ty1->getTypeID() != Ty2->getTypeID()) { 207 if (TD) { 208 LLVMContext &Ctx = Ty1->getContext(); 209 if (isa<PointerType>(Ty1) && Ty2 == TD->getIntPtrType(Ctx)) return true; 210 if (isa<PointerType>(Ty2) && Ty1 == TD->getIntPtrType(Ctx)) return true; 211 } 212 return false; 213 } 214 215 switch(Ty1->getTypeID()) { 216 default: 217 llvm_unreachable("Unknown type!"); 218 // Fall through in Release mode. 219 case Type::IntegerTyID: 220 case Type::OpaqueTyID: 221 case Type::VectorTyID: 222 // Ty1 == Ty2 would have returned true earlier. 223 return false; 224 225 case Type::VoidTyID: 226 case Type::FloatTyID: 227 case Type::DoubleTyID: 228 case Type::X86_FP80TyID: 229 case Type::FP128TyID: 230 case Type::PPC_FP128TyID: 231 case Type::LabelTyID: 232 case Type::MetadataTyID: 233 return true; 234 235 case Type::PointerTyID: { 236 const PointerType *PTy1 = cast<PointerType>(Ty1); 237 const PointerType *PTy2 = cast<PointerType>(Ty2); 238 return PTy1->getAddressSpace() == PTy2->getAddressSpace(); 239 } 240 241 case Type::StructTyID: { 242 const StructType *STy1 = cast<StructType>(Ty1); 243 const StructType *STy2 = cast<StructType>(Ty2); 244 if (STy1->getNumElements() != STy2->getNumElements()) 245 return false; 246 247 if (STy1->isPacked() != STy2->isPacked()) 248 return false; 249 250 for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) { 251 if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i))) 252 return false; 253 } 254 return true; 255 } 256 257 case Type::FunctionTyID: { 258 const FunctionType *FTy1 = cast<FunctionType>(Ty1); 259 const FunctionType *FTy2 = cast<FunctionType>(Ty2); 260 if (FTy1->getNumParams() != FTy2->getNumParams() || 261 FTy1->isVarArg() != FTy2->isVarArg()) 262 return false; 263 264 if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType())) 265 return false; 266 267 for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) { 268 if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i))) 269 return false; 270 } 271 return true; 272 } 273 274 case Type::ArrayTyID: { 275 const ArrayType *ATy1 = cast<ArrayType>(Ty1); 276 const ArrayType *ATy2 = cast<ArrayType>(Ty2); 277 return ATy1->getNumElements() == ATy2->getNumElements() && 278 isEquivalentType(ATy1->getElementType(), ATy2->getElementType()); 279 } 280 } 281} 282 283// Determine whether the two operations are the same except that pointer-to-A 284// and pointer-to-B are equivalent. This should be kept in sync with 285// Instruction::isSameOperationAs. 286bool FunctionComparator::isEquivalentOperation(const Instruction *I1, 287 const Instruction *I2) const { 288 // Differences from Instruction::isSameOperationAs: 289 // * replace type comparison with calls to isEquivalentType. 290 // * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top 291 // * because of the above, we don't test for the tail bit on calls later on 292 if (I1->getOpcode() != I2->getOpcode() || 293 I1->getNumOperands() != I2->getNumOperands() || 294 !isEquivalentType(I1->getType(), I2->getType()) || 295 !I1->hasSameSubclassOptionalData(I2)) 296 return false; 297 298 // We have two instructions of identical opcode and #operands. Check to see 299 // if all operands are the same type 300 for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) 301 if (!isEquivalentType(I1->getOperand(i)->getType(), 302 I2->getOperand(i)->getType())) 303 return false; 304 305 // Check special state that is a part of some instructions. 306 if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) 307 return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() && 308 LI->getAlignment() == cast<LoadInst>(I2)->getAlignment(); 309 if (const StoreInst *SI = dyn_cast<StoreInst>(I1)) 310 return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() && 311 SI->getAlignment() == cast<StoreInst>(I2)->getAlignment(); 312 if (const CmpInst *CI = dyn_cast<CmpInst>(I1)) 313 return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate(); 314 if (const CallInst *CI = dyn_cast<CallInst>(I1)) 315 return CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() && 316 CI->getAttributes() == cast<CallInst>(I2)->getAttributes(); 317 if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1)) 318 return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() && 319 CI->getAttributes() == cast<InvokeInst>(I2)->getAttributes(); 320 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) { 321 if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices()) 322 return false; 323 for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) 324 if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i]) 325 return false; 326 return true; 327 } 328 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) { 329 if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices()) 330 return false; 331 for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) 332 if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i]) 333 return false; 334 return true; 335 } 336 337 return true; 338} 339 340// Determine whether two GEP operations perform the same underlying arithmetic. 341bool FunctionComparator::isEquivalentGEP(const GEPOperator *GEP1, 342 const GEPOperator *GEP2) { 343 // When we have target data, we can reduce the GEP down to the value in bytes 344 // added to the address. 345 if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) { 346 SmallVector<Value *, 8> Indices1(GEP1->idx_begin(), GEP1->idx_end()); 347 SmallVector<Value *, 8> Indices2(GEP2->idx_begin(), GEP2->idx_end()); 348 uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(), 349 Indices1.data(), Indices1.size()); 350 uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(), 351 Indices2.data(), Indices2.size()); 352 return Offset1 == Offset2; 353 } 354 355 if (GEP1->getPointerOperand()->getType() != 356 GEP2->getPointerOperand()->getType()) 357 return false; 358 359 if (GEP1->getNumOperands() != GEP2->getNumOperands()) 360 return false; 361 362 for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) { 363 if (!enumerate(GEP1->getOperand(i), GEP2->getOperand(i))) 364 return false; 365 } 366 367 return true; 368} 369 370// Compare two values used by the two functions under pair-wise comparison. If 371// this is the first time the values are seen, they're added to the mapping so 372// that we will detect mismatches on next use. 373bool FunctionComparator::enumerate(const Value *V1, const Value *V2) { 374 // Check for function @f1 referring to itself and function @f2 referring to 375 // itself, or referring to each other, or both referring to either of them. 376 // They're all equivalent if the two functions are otherwise equivalent. 377 if (V1 == F1 && V2 == F2) 378 return true; 379 if (V1 == F2 && V2 == F1) 380 return true; 381 382 if (const Constant *C1 = dyn_cast<Constant>(V1)) { 383 if (V1 == V2) return true; 384 const Constant *C2 = dyn_cast<Constant>(V2); 385 if (!C2) return false; 386 // TODO: constant expressions with GEP or references to F1 or F2. 387 if (C1->isNullValue() && C2->isNullValue() && 388 isEquivalentType(C1->getType(), C2->getType())) 389 return true; 390 // Try bitcasting C2 to C1's type. If the bitcast is legal and returns C1 391 // then they must have equal bit patterns. 392 return C1->getType()->canLosslesslyBitCastTo(C2->getType()) && 393 C1 == ConstantExpr::getBitCast(const_cast<Constant*>(C2), C1->getType()); 394 } 395 396 if (isa<InlineAsm>(V1) || isa<InlineAsm>(V2)) 397 return V1 == V2; 398 399 // Check that V1 maps to V2. If we find a value that V1 maps to then we simply 400 // check whether it's equal to V2. When there is no mapping then we need to 401 // ensure that V2 isn't already equivalent to something else. For this 402 // purpose, we track the V2 values in a set. 403 404 const Value *&map_elem = id_map[V1]; 405 if (map_elem) 406 return map_elem == V2; 407 if (!seen_values.insert(V2).second) 408 return false; 409 map_elem = V2; 410 return true; 411} 412 413// Test whether two basic blocks have equivalent behaviour. 414bool FunctionComparator::compare(const BasicBlock *BB1, const BasicBlock *BB2) { 415 BasicBlock::const_iterator F1I = BB1->begin(), F1E = BB1->end(); 416 BasicBlock::const_iterator F2I = BB2->begin(), F2E = BB2->end(); 417 418 do { 419 if (!enumerate(F1I, F2I)) 420 return false; 421 422 if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(F1I)) { 423 const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(F2I); 424 if (!GEP2) 425 return false; 426 427 if (!enumerate(GEP1->getPointerOperand(), GEP2->getPointerOperand())) 428 return false; 429 430 if (!isEquivalentGEP(GEP1, GEP2)) 431 return false; 432 } else { 433 if (!isEquivalentOperation(F1I, F2I)) 434 return false; 435 436 assert(F1I->getNumOperands() == F2I->getNumOperands()); 437 for (unsigned i = 0, e = F1I->getNumOperands(); i != e; ++i) { 438 Value *OpF1 = F1I->getOperand(i); 439 Value *OpF2 = F2I->getOperand(i); 440 441 if (!enumerate(OpF1, OpF2)) 442 return false; 443 444 if (OpF1->getValueID() != OpF2->getValueID() || 445 !isEquivalentType(OpF1->getType(), OpF2->getType())) 446 return false; 447 } 448 } 449 450 ++F1I, ++F2I; 451 } while (F1I != F1E && F2I != F2E); 452 453 return F1I == F1E && F2I == F2E; 454} 455 456// Test whether the two functions have equivalent behaviour. 457bool FunctionComparator::compare() { 458 // We need to recheck everything, but check the things that weren't included 459 // in the hash first. 460 461 if (F1->getAttributes() != F2->getAttributes()) 462 return false; 463 464 if (F1->hasGC() != F2->hasGC()) 465 return false; 466 467 if (F1->hasGC() && F1->getGC() != F2->getGC()) 468 return false; 469 470 if (F1->hasSection() != F2->hasSection()) 471 return false; 472 473 if (F1->hasSection() && F1->getSection() != F2->getSection()) 474 return false; 475 476 if (F1->isVarArg() != F2->isVarArg()) 477 return false; 478 479 // TODO: if it's internal and only used in direct calls, we could handle this 480 // case too. 481 if (F1->getCallingConv() != F2->getCallingConv()) 482 return false; 483 484 if (!isEquivalentType(F1->getFunctionType(), F2->getFunctionType())) 485 return false; 486 487 assert(F1->arg_size() == F2->arg_size() && 488 "Identically typed functions have different numbers of args!"); 489 490 // Visit the arguments so that they get enumerated in the order they're 491 // passed in. 492 for (Function::const_arg_iterator f1i = F1->arg_begin(), 493 f2i = F2->arg_begin(), f1e = F1->arg_end(); f1i != f1e; ++f1i, ++f2i) { 494 if (!enumerate(f1i, f2i)) 495 llvm_unreachable("Arguments repeat!"); 496 } 497 498 // We do a CFG-ordered walk since the actual ordering of the blocks in the 499 // linked list is immaterial. Our walk starts at the entry block for both 500 // functions, then takes each block from each terminator in order. As an 501 // artifact, this also means that unreachable blocks are ignored. 502 SmallVector<const BasicBlock *, 8> F1BBs, F2BBs; 503 SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1. 504 505 F1BBs.push_back(&F1->getEntryBlock()); 506 F2BBs.push_back(&F2->getEntryBlock()); 507 508 VisitedBBs.insert(F1BBs[0]); 509 while (!F1BBs.empty()) { 510 const BasicBlock *F1BB = F1BBs.pop_back_val(); 511 const BasicBlock *F2BB = F2BBs.pop_back_val(); 512 513 if (!enumerate(F1BB, F2BB) || !compare(F1BB, F2BB)) 514 return false; 515 516 const TerminatorInst *F1TI = F1BB->getTerminator(); 517 const TerminatorInst *F2TI = F2BB->getTerminator(); 518 519 assert(F1TI->getNumSuccessors() == F2TI->getNumSuccessors()); 520 for (unsigned i = 0, e = F1TI->getNumSuccessors(); i != e; ++i) { 521 if (!VisitedBBs.insert(F1TI->getSuccessor(i))) 522 continue; 523 524 F1BBs.push_back(F1TI->getSuccessor(i)); 525 F2BBs.push_back(F2TI->getSuccessor(i)); 526 } 527 } 528 return true; 529} 530 531namespace { 532 533/// MergeFunctions finds functions which will generate identical machine code, 534/// by considering all pointer types to be equivalent. Once identified, 535/// MergeFunctions will fold them by replacing a call to one to a call to a 536/// bitcast of the other. 537/// 538class MergeFunctions : public ModulePass { 539public: 540 static char ID; 541 MergeFunctions() 542 : ModulePass(ID), HasGlobalAliases(false) { 543 initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); 544 } 545 546 bool runOnModule(Module &M); 547 548private: 549 typedef DenseSet<ComparableFunction> FnSetType; 550 551 /// A work queue of functions that may have been modified and should be 552 /// analyzed again. 553 std::vector<WeakVH> Deferred; 554 555 /// Insert a ComparableFunction into the FnSet, or merge it away if it's 556 /// equal to one that's already present. 557 bool insert(ComparableFunction &NewF); 558 559 /// Remove a Function from the FnSet and queue it up for a second sweep of 560 /// analysis. 561 void remove(Function *F); 562 563 /// Find the functions that use this Value and remove them from FnSet and 564 /// queue the functions. 565 void removeUsers(Value *V); 566 567 /// Replace all direct calls of Old with calls of New. Will bitcast New if 568 /// necessary to make types match. 569 void replaceDirectCallers(Function *Old, Function *New); 570 571 /// Merge two equivalent functions. Upon completion, G may be deleted, or may 572 /// be converted into a thunk. In either case, it should never be visited 573 /// again. 574 void mergeTwoFunctions(Function *F, Function *G); 575 576 /// Replace G with a thunk or an alias to F. Deletes G. 577 void writeThunkOrAlias(Function *F, Function *G); 578 579 /// Replace G with a simple tail call to bitcast(F). Also replace direct uses 580 /// of G with bitcast(F). Deletes G. 581 void writeThunk(Function *F, Function *G); 582 583 /// Replace G with an alias to F. Deletes G. 584 void writeAlias(Function *F, Function *G); 585 586 /// The set of all distinct functions. Use the insert() and remove() methods 587 /// to modify it. 588 FnSetType FnSet; 589 590 /// TargetData for more accurate GEP comparisons. May be NULL. 591 TargetData *TD; 592 593 /// Whether or not the target supports global aliases. 594 bool HasGlobalAliases; 595}; 596 597} // end anonymous namespace 598 599char MergeFunctions::ID = 0; 600INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false) 601 602ModulePass *llvm::createMergeFunctionsPass() { 603 return new MergeFunctions(); 604} 605 606bool MergeFunctions::runOnModule(Module &M) { 607 bool Changed = false; 608 TD = getAnalysisIfAvailable<TargetData>(); 609 610 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 611 if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) 612 Deferred.push_back(WeakVH(I)); 613 } 614 FnSet.resize(Deferred.size()); 615 616 do { 617 std::vector<WeakVH> Worklist; 618 Deferred.swap(Worklist); 619 620 DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 621 DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); 622 623 // Insert only strong functions and merge them. Strong function merging 624 // always deletes one of them. 625 for (std::vector<WeakVH>::iterator I = Worklist.begin(), 626 E = Worklist.end(); I != E; ++I) { 627 if (!*I) continue; 628 Function *F = cast<Function>(*I); 629 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 630 !F->mayBeOverridden()) { 631 ComparableFunction CF = ComparableFunction(F, TD); 632 Changed |= insert(CF); 633 } 634 } 635 636 // Insert only weak functions and merge them. By doing these second we 637 // create thunks to the strong function when possible. When two weak 638 // functions are identical, we create a new strong function with two weak 639 // weak thunks to it which are identical but not mergable. 640 for (std::vector<WeakVH>::iterator I = Worklist.begin(), 641 E = Worklist.end(); I != E; ++I) { 642 if (!*I) continue; 643 Function *F = cast<Function>(*I); 644 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 645 F->mayBeOverridden()) { 646 ComparableFunction CF = ComparableFunction(F, TD); 647 Changed |= insert(CF); 648 } 649 } 650 DEBUG(dbgs() << "size of FnSet: " << FnSet.size() << '\n'); 651 } while (!Deferred.empty()); 652 653 FnSet.clear(); 654 655 return Changed; 656} 657 658bool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS, 659 const ComparableFunction &RHS) { 660 if (LHS.getFunc() == RHS.getFunc() && 661 LHS.getHash() == RHS.getHash()) 662 return true; 663 if (!LHS.getFunc() || !RHS.getFunc()) 664 return false; 665 666 // One of these is a special "underlying pointer comparison only" object. 667 if (LHS.getTD() == ComparableFunction::LookupOnly || 668 RHS.getTD() == ComparableFunction::LookupOnly) 669 return false; 670 671 assert(LHS.getTD() == RHS.getTD() && 672 "Comparing functions for different targets"); 673 674 return FunctionComparator(LHS.getTD(), LHS.getFunc(), 675 RHS.getFunc()).compare(); 676} 677 678// Replace direct callers of Old with New. 679void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { 680 Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); 681 for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end(); 682 UI != UE;) { 683 Value::use_iterator TheIter = UI; 684 ++UI; 685 CallSite CS(*TheIter); 686 if (CS && CS.isCallee(TheIter)) { 687 remove(CS.getInstruction()->getParent()->getParent()); 688 TheIter.getUse().set(BitcastNew); 689 } 690 } 691} 692 693// Replace G with an alias to F if possible, or else a thunk to F. Deletes G. 694void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { 695 if (HasGlobalAliases && G->hasUnnamedAddr()) { 696 if (G->hasExternalLinkage() || G->hasLocalLinkage() || 697 G->hasWeakLinkage()) { 698 writeAlias(F, G); 699 return; 700 } 701 } 702 703 writeThunk(F, G); 704} 705 706// Replace G with a simple tail call to bitcast(F). Also replace direct uses 707// of G with bitcast(F). Deletes G. 708void MergeFunctions::writeThunk(Function *F, Function *G) { 709 if (!G->mayBeOverridden()) { 710 // Redirect direct callers of G to F. 711 replaceDirectCallers(G, F); 712 } 713 714 // If G was internal then we may have replaced all uses of G with F. If so, 715 // stop here and delete G. There's no need for a thunk. 716 if (G->hasLocalLinkage() && G->use_empty()) { 717 G->eraseFromParent(); 718 return; 719 } 720 721 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 722 G->getParent()); 723 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 724 IRBuilder<false> Builder(BB); 725 726 SmallVector<Value *, 16> Args; 727 unsigned i = 0; 728 const FunctionType *FFTy = F->getFunctionType(); 729 for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 730 AI != AE; ++AI) { 731 Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i))); 732 ++i; 733 } 734 735 CallInst *CI = Builder.CreateCall(F, Args.begin(), Args.end()); 736 CI->setTailCall(); 737 CI->setCallingConv(F->getCallingConv()); 738 if (NewG->getReturnType()->isVoidTy()) { 739 Builder.CreateRetVoid(); 740 } else { 741 Builder.CreateRet(Builder.CreateBitCast(CI, NewG->getReturnType())); 742 } 743 744 NewG->copyAttributesFrom(G); 745 NewG->takeName(G); 746 removeUsers(G); 747 G->replaceAllUsesWith(NewG); 748 G->eraseFromParent(); 749 750 DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n'); 751 ++NumThunksWritten; 752} 753 754// Replace G with an alias to F and delete G. 755void MergeFunctions::writeAlias(Function *F, Function *G) { 756 Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 757 GlobalAlias *GA = new GlobalAlias(G->getType(), G->getLinkage(), "", 758 BitcastF, G->getParent()); 759 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 760 GA->takeName(G); 761 GA->setVisibility(G->getVisibility()); 762 removeUsers(G); 763 G->replaceAllUsesWith(GA); 764 G->eraseFromParent(); 765 766 DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); 767 ++NumAliasesWritten; 768} 769 770// Merge two equivalent functions. Upon completion, Function G is deleted. 771void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { 772 if (F->mayBeOverridden()) { 773 assert(G->mayBeOverridden()); 774 775 if (HasGlobalAliases) { 776 // Make them both thunks to the same internal function. 777 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 778 F->getParent()); 779 H->copyAttributesFrom(F); 780 H->takeName(F); 781 removeUsers(F); 782 F->replaceAllUsesWith(H); 783 784 unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); 785 786 writeAlias(F, G); 787 writeAlias(F, H); 788 789 F->setAlignment(MaxAlignment); 790 F->setLinkage(GlobalValue::PrivateLinkage); 791 } else { 792 // We can't merge them. Instead, pick one and update all direct callers 793 // to call it and hope that we improve the instruction cache hit rate. 794 replaceDirectCallers(G, F); 795 } 796 797 ++NumDoubleWeak; 798 } else { 799 writeThunkOrAlias(F, G); 800 } 801 802 ++NumFunctionsMerged; 803} 804 805// Insert a ComparableFunction into the FnSet, or merge it away if equal to one 806// that was already inserted. 807bool MergeFunctions::insert(ComparableFunction &NewF) { 808 std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF); 809 if (Result.second) { 810 DEBUG(dbgs() << "Inserting as unique: " << NewF.getFunc()->getName() << '\n'); 811 return false; 812 } 813 814 const ComparableFunction &OldF = *Result.first; 815 816 // Never thunk a strong function to a weak function. 817 assert(!OldF.getFunc()->mayBeOverridden() || 818 NewF.getFunc()->mayBeOverridden()); 819 820 DEBUG(dbgs() << " " << OldF.getFunc()->getName() << " == " 821 << NewF.getFunc()->getName() << '\n'); 822 823 Function *DeleteF = NewF.getFunc(); 824 NewF.release(); 825 mergeTwoFunctions(OldF.getFunc(), DeleteF); 826 return true; 827} 828 829// Remove a function from FnSet. If it was already in FnSet, add it to Deferred 830// so that we'll look at it in the next round. 831void MergeFunctions::remove(Function *F) { 832 // We need to make sure we remove F, not a function "equal" to F per the 833 // function equality comparator. 834 // 835 // The special "lookup only" ComparableFunction bypasses the expensive 836 // function comparison in favour of a pointer comparison on the underlying 837 // Function*'s. 838 ComparableFunction CF = ComparableFunction(F, ComparableFunction::LookupOnly); 839 if (FnSet.erase(CF)) { 840 DEBUG(dbgs() << "Removed " << F->getName() << " from set and deferred it.\n"); 841 Deferred.push_back(F); 842 } 843} 844 845// For each instruction used by the value, remove() the function that contains 846// the instruction. This should happen right before a call to RAUW. 847void MergeFunctions::removeUsers(Value *V) { 848 std::vector<Value *> Worklist; 849 Worklist.push_back(V); 850 while (!Worklist.empty()) { 851 Value *V = Worklist.back(); 852 Worklist.pop_back(); 853 854 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); 855 UI != UE; ++UI) { 856 Use &U = UI.getUse(); 857 if (Instruction *I = dyn_cast<Instruction>(U.getUser())) { 858 remove(I->getParent()->getParent()); 859 } else if (isa<GlobalValue>(U.getUser())) { 860 // do nothing 861 } else if (Constant *C = dyn_cast<Constant>(U.getUser())) { 862 for (Value::use_iterator CUI = C->use_begin(), CUE = C->use_end(); 863 CUI != CUE; ++CUI) 864 Worklist.push_back(*CUI); 865 } 866 } 867 } 868} 869