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// Order relation is defined on set of functions. It was made through 13// special function comparison procedure that returns 14// 0 when functions are equal, 15// -1 when Left function is less than right function, and 16// 1 for opposite case. We need total-ordering, so we need to maintain 17// four properties on the functions set: 18// a <= a (reflexivity) 19// if a <= b and b <= a then a = b (antisymmetry) 20// if a <= b and b <= c then a <= c (transitivity). 21// for all a and b: a <= b or b <= a (totality). 22// 23// Comparison iterates through each instruction in each basic block. 24// Functions are kept on binary tree. For each new function F we perform 25// lookup in binary tree. 26// In practice it works the following way: 27// -- We define Function* container class with custom "operator<" (FunctionPtr). 28// -- "FunctionPtr" instances are stored in std::set collection, so every 29// std::set::insert operation will give you result in log(N) time. 30// 31// When a match is found the functions are folded. If both functions are 32// overridable, we move the functionality into a new internal function and 33// leave two overridable thunks to it. 34// 35//===----------------------------------------------------------------------===// 36// 37// Future work: 38// 39// * virtual functions. 40// 41// Many functions have their address taken by the virtual function table for 42// the object they belong to. However, as long as it's only used for a lookup 43// and call, this is irrelevant, and we'd like to fold such functions. 44// 45// * be smarter about bitcasts. 46// 47// In order to fold functions, we will sometimes add either bitcast instructions 48// or bitcast constant expressions. Unfortunately, this can confound further 49// analysis since the two functions differ where one has a bitcast and the 50// other doesn't. We should learn to look through bitcasts. 51// 52// * Compare complex types with pointer types inside. 53// * Compare cross-reference cases. 54// * Compare complex expressions. 55// 56// All the three issues above could be described as ability to prove that 57// fA == fB == fC == fE == fF == fG in example below: 58// 59// void fA() { 60// fB(); 61// } 62// void fB() { 63// fA(); 64// } 65// 66// void fE() { 67// fF(); 68// } 69// void fF() { 70// fG(); 71// } 72// void fG() { 73// fE(); 74// } 75// 76// Simplest cross-reference case (fA <--> fB) was implemented in previous 77// versions of MergeFunctions, though it presented only in two function pairs 78// in test-suite (that counts >50k functions) 79// Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A) 80// could cover much more cases. 81// 82//===----------------------------------------------------------------------===// 83 84#include "llvm/Transforms/IPO.h" 85#include "llvm/ADT/DenseSet.h" 86#include "llvm/ADT/FoldingSet.h" 87#include "llvm/ADT/STLExtras.h" 88#include "llvm/ADT/SmallSet.h" 89#include "llvm/ADT/Statistic.h" 90#include "llvm/IR/CallSite.h" 91#include "llvm/IR/Constants.h" 92#include "llvm/IR/DataLayout.h" 93#include "llvm/IR/IRBuilder.h" 94#include "llvm/IR/InlineAsm.h" 95#include "llvm/IR/Instructions.h" 96#include "llvm/IR/LLVMContext.h" 97#include "llvm/IR/Module.h" 98#include "llvm/IR/Operator.h" 99#include "llvm/IR/ValueHandle.h" 100#include "llvm/Pass.h" 101#include "llvm/Support/CommandLine.h" 102#include "llvm/Support/Debug.h" 103#include "llvm/Support/ErrorHandling.h" 104#include "llvm/Support/raw_ostream.h" 105#include <vector> 106using namespace llvm; 107 108#define DEBUG_TYPE "mergefunc" 109 110STATISTIC(NumFunctionsMerged, "Number of functions merged"); 111STATISTIC(NumThunksWritten, "Number of thunks generated"); 112STATISTIC(NumAliasesWritten, "Number of aliases generated"); 113STATISTIC(NumDoubleWeak, "Number of new functions created"); 114 115static cl::opt<unsigned> NumFunctionsForSanityCheck( 116 "mergefunc-sanity", 117 cl::desc("How many functions in module could be used for " 118 "MergeFunctions pass sanity check. " 119 "'0' disables this check. Works only with '-debug' key."), 120 cl::init(0), cl::Hidden); 121 122namespace { 123 124/// FunctionComparator - Compares two functions to determine whether or not 125/// they will generate machine code with the same behaviour. DataLayout is 126/// used if available. The comparator always fails conservatively (erring on the 127/// side of claiming that two functions are different). 128class FunctionComparator { 129public: 130 FunctionComparator(const Function *F1, const Function *F2) 131 : FnL(F1), FnR(F2) {} 132 133 /// Test whether the two functions have equivalent behaviour. 134 int compare(); 135 136private: 137 /// Test whether two basic blocks have equivalent behaviour. 138 int compare(const BasicBlock *BBL, const BasicBlock *BBR); 139 140 /// Constants comparison. 141 /// Its analog to lexicographical comparison between hypothetical numbers 142 /// of next format: 143 /// <bitcastability-trait><raw-bit-contents> 144 /// 145 /// 1. Bitcastability. 146 /// Check whether L's type could be losslessly bitcasted to R's type. 147 /// On this stage method, in case when lossless bitcast is not possible 148 /// method returns -1 or 1, thus also defining which type is greater in 149 /// context of bitcastability. 150 /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight 151 /// to the contents comparison. 152 /// If types differ, remember types comparison result and check 153 /// whether we still can bitcast types. 154 /// Stage 1: Types that satisfies isFirstClassType conditions are always 155 /// greater then others. 156 /// Stage 2: Vector is greater then non-vector. 157 /// If both types are vectors, then vector with greater bitwidth is 158 /// greater. 159 /// If both types are vectors with the same bitwidth, then types 160 /// are bitcastable, and we can skip other stages, and go to contents 161 /// comparison. 162 /// Stage 3: Pointer types are greater than non-pointers. If both types are 163 /// pointers of the same address space - go to contents comparison. 164 /// Different address spaces: pointer with greater address space is 165 /// greater. 166 /// Stage 4: Types are neither vectors, nor pointers. And they differ. 167 /// We don't know how to bitcast them. So, we better don't do it, 168 /// and return types comparison result (so it determines the 169 /// relationship among constants we don't know how to bitcast). 170 /// 171 /// Just for clearance, let's see how the set of constants could look 172 /// on single dimension axis: 173 /// 174 /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors] 175 /// Where: NFCT - Not a FirstClassType 176 /// FCT - FirstClassTyp: 177 /// 178 /// 2. Compare raw contents. 179 /// It ignores types on this stage and only compares bits from L and R. 180 /// Returns 0, if L and R has equivalent contents. 181 /// -1 or 1 if values are different. 182 /// Pretty trivial: 183 /// 2.1. If contents are numbers, compare numbers. 184 /// Ints with greater bitwidth are greater. Ints with same bitwidths 185 /// compared by their contents. 186 /// 2.2. "And so on". Just to avoid discrepancies with comments 187 /// perhaps it would be better to read the implementation itself. 188 /// 3. And again about overall picture. Let's look back at how the ordered set 189 /// of constants will look like: 190 /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors] 191 /// 192 /// Now look, what could be inside [FCT, "others"], for example: 193 /// [FCT, "others"] = 194 /// [ 195 /// [double 0.1], [double 1.23], 196 /// [i32 1], [i32 2], 197 /// { double 1.0 }, ; StructTyID, NumElements = 1 198 /// { i32 1 }, ; StructTyID, NumElements = 1 199 /// { double 1, i32 1 }, ; StructTyID, NumElements = 2 200 /// { i32 1, double 1 } ; StructTyID, NumElements = 2 201 /// ] 202 /// 203 /// Let's explain the order. Float numbers will be less than integers, just 204 /// because of cmpType terms: FloatTyID < IntegerTyID. 205 /// Floats (with same fltSemantics) are sorted according to their value. 206 /// Then you can see integers, and they are, like a floats, 207 /// could be easy sorted among each others. 208 /// The structures. Structures are grouped at the tail, again because of their 209 /// TypeID: StructTyID > IntegerTyID > FloatTyID. 210 /// Structures with greater number of elements are greater. Structures with 211 /// greater elements going first are greater. 212 /// The same logic with vectors, arrays and other possible complex types. 213 /// 214 /// Bitcastable constants. 215 /// Let's assume, that some constant, belongs to some group of 216 /// "so-called-equal" values with different types, and at the same time 217 /// belongs to another group of constants with equal types 218 /// and "really" equal values. 219 /// 220 /// Now, prove that this is impossible: 221 /// 222 /// If constant A with type TyA is bitcastable to B with type TyB, then: 223 /// 1. All constants with equal types to TyA, are bitcastable to B. Since 224 /// those should be vectors (if TyA is vector), pointers 225 /// (if TyA is pointer), or else (if TyA equal to TyB), those types should 226 /// be equal to TyB. 227 /// 2. All constants with non-equal, but bitcastable types to TyA, are 228 /// bitcastable to B. 229 /// Once again, just because we allow it to vectors and pointers only. 230 /// This statement could be expanded as below: 231 /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to 232 /// vector B, and thus bitcastable to B as well. 233 /// 2.2. All pointers of the same address space, no matter what they point to, 234 /// bitcastable. So if C is pointer, it could be bitcasted to A and to B. 235 /// So any constant equal or bitcastable to A is equal or bitcastable to B. 236 /// QED. 237 /// 238 /// In another words, for pointers and vectors, we ignore top-level type and 239 /// look at their particular properties (bit-width for vectors, and 240 /// address space for pointers). 241 /// If these properties are equal - compare their contents. 242 int cmpConstants(const Constant *L, const Constant *R); 243 244 /// Assign or look up previously assigned numbers for the two values, and 245 /// return whether the numbers are equal. Numbers are assigned in the order 246 /// visited. 247 /// Comparison order: 248 /// Stage 0: Value that is function itself is always greater then others. 249 /// If left and right values are references to their functions, then 250 /// they are equal. 251 /// Stage 1: Constants are greater than non-constants. 252 /// If both left and right are constants, then the result of 253 /// cmpConstants is used as cmpValues result. 254 /// Stage 2: InlineAsm instances are greater than others. If both left and 255 /// right are InlineAsm instances, InlineAsm* pointers casted to 256 /// integers and compared as numbers. 257 /// Stage 3: For all other cases we compare order we meet these values in 258 /// their functions. If right value was met first during scanning, 259 /// then left value is greater. 260 /// In another words, we compare serial numbers, for more details 261 /// see comments for sn_mapL and sn_mapR. 262 int cmpValues(const Value *L, const Value *R); 263 264 /// Compare two Instructions for equivalence, similar to 265 /// Instruction::isSameOperationAs but with modifications to the type 266 /// comparison. 267 /// Stages are listed in "most significant stage first" order: 268 /// On each stage below, we do comparison between some left and right 269 /// operation parts. If parts are non-equal, we assign parts comparison 270 /// result to the operation comparison result and exit from method. 271 /// Otherwise we proceed to the next stage. 272 /// Stages: 273 /// 1. Operations opcodes. Compared as numbers. 274 /// 2. Number of operands. 275 /// 3. Operation types. Compared with cmpType method. 276 /// 4. Compare operation subclass optional data as stream of bytes: 277 /// just convert it to integers and call cmpNumbers. 278 /// 5. Compare in operation operand types with cmpType in 279 /// most significant operand first order. 280 /// 6. Last stage. Check operations for some specific attributes. 281 /// For example, for Load it would be: 282 /// 6.1.Load: volatile (as boolean flag) 283 /// 6.2.Load: alignment (as integer numbers) 284 /// 6.3.Load: synch-scope (as integer numbers) 285 /// 6.4.Load: range metadata (as integer numbers) 286 /// On this stage its better to see the code, since its not more than 10-15 287 /// strings for particular instruction, and could change sometimes. 288 int cmpOperations(const Instruction *L, const Instruction *R) const; 289 290 /// Compare two GEPs for equivalent pointer arithmetic. 291 /// Parts to be compared for each comparison stage, 292 /// most significant stage first: 293 /// 1. Address space. As numbers. 294 /// 2. Constant offset, (using GEPOperator::accumulateConstantOffset method). 295 /// 3. Pointer operand type (using cmpType method). 296 /// 4. Number of operands. 297 /// 5. Compare operands, using cmpValues method. 298 int cmpGEPs(const GEPOperator *GEPL, const GEPOperator *GEPR); 299 int cmpGEPs(const GetElementPtrInst *GEPL, const GetElementPtrInst *GEPR) { 300 return cmpGEPs(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR)); 301 } 302 303 /// cmpType - compares two types, 304 /// defines total ordering among the types set. 305 /// 306 /// Return values: 307 /// 0 if types are equal, 308 /// -1 if Left is less than Right, 309 /// +1 if Left is greater than Right. 310 /// 311 /// Description: 312 /// Comparison is broken onto stages. Like in lexicographical comparison 313 /// stage coming first has higher priority. 314 /// On each explanation stage keep in mind total ordering properties. 315 /// 316 /// 0. Before comparison we coerce pointer types of 0 address space to 317 /// integer. 318 /// We also don't bother with same type at left and right, so 319 /// just return 0 in this case. 320 /// 321 /// 1. If types are of different kind (different type IDs). 322 /// Return result of type IDs comparison, treating them as numbers. 323 /// 2. If types are vectors or integers, compare Type* values as numbers. 324 /// 3. Types has same ID, so check whether they belongs to the next group: 325 /// * Void 326 /// * Float 327 /// * Double 328 /// * X86_FP80 329 /// * FP128 330 /// * PPC_FP128 331 /// * Label 332 /// * Metadata 333 /// If so - return 0, yes - we can treat these types as equal only because 334 /// their IDs are same. 335 /// 4. If Left and Right are pointers, return result of address space 336 /// comparison (numbers comparison). We can treat pointer types of same 337 /// address space as equal. 338 /// 5. If types are complex. 339 /// Then both Left and Right are to be expanded and their element types will 340 /// be checked with the same way. If we get Res != 0 on some stage, return it. 341 /// Otherwise return 0. 342 /// 6. For all other cases put llvm_unreachable. 343 int cmpTypes(Type *TyL, Type *TyR) const; 344 345 int cmpNumbers(uint64_t L, uint64_t R) const; 346 347 int cmpAPInts(const APInt &L, const APInt &R) const; 348 int cmpAPFloats(const APFloat &L, const APFloat &R) const; 349 int cmpStrings(StringRef L, StringRef R) const; 350 int cmpAttrs(const AttributeSet L, const AttributeSet R) const; 351 352 // The two functions undergoing comparison. 353 const Function *FnL, *FnR; 354 355 /// Assign serial numbers to values from left function, and values from 356 /// right function. 357 /// Explanation: 358 /// Being comparing functions we need to compare values we meet at left and 359 /// right sides. 360 /// Its easy to sort things out for external values. It just should be 361 /// the same value at left and right. 362 /// But for local values (those were introduced inside function body) 363 /// we have to ensure they were introduced at exactly the same place, 364 /// and plays the same role. 365 /// Let's assign serial number to each value when we meet it first time. 366 /// Values that were met at same place will be with same serial numbers. 367 /// In this case it would be good to explain few points about values assigned 368 /// to BBs and other ways of implementation (see below). 369 /// 370 /// 1. Safety of BB reordering. 371 /// It's safe to change the order of BasicBlocks in function. 372 /// Relationship with other functions and serial numbering will not be 373 /// changed in this case. 374 /// As follows from FunctionComparator::compare(), we do CFG walk: we start 375 /// from the entry, and then take each terminator. So it doesn't matter how in 376 /// fact BBs are ordered in function. And since cmpValues are called during 377 /// this walk, the numbering depends only on how BBs located inside the CFG. 378 /// So the answer is - yes. We will get the same numbering. 379 /// 380 /// 2. Impossibility to use dominance properties of values. 381 /// If we compare two instruction operands: first is usage of local 382 /// variable AL from function FL, and second is usage of local variable AR 383 /// from FR, we could compare their origins and check whether they are 384 /// defined at the same place. 385 /// But, we are still not able to compare operands of PHI nodes, since those 386 /// could be operands from further BBs we didn't scan yet. 387 /// So it's impossible to use dominance properties in general. 388 DenseMap<const Value*, int> sn_mapL, sn_mapR; 389}; 390 391class FunctionNode { 392 AssertingVH<Function> F; 393 394public: 395 FunctionNode(Function *F) : F(F) {} 396 Function *getFunc() const { return F; } 397 void release() { F = 0; } 398 bool operator<(const FunctionNode &RHS) const { 399 return (FunctionComparator(F, RHS.getFunc()).compare()) == -1; 400 } 401}; 402} 403 404int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const { 405 if (L < R) return -1; 406 if (L > R) return 1; 407 return 0; 408} 409 410int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const { 411 if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth())) 412 return Res; 413 if (L.ugt(R)) return 1; 414 if (R.ugt(L)) return -1; 415 return 0; 416} 417 418int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const { 419 if (int Res = cmpNumbers((uint64_t)&L.getSemantics(), 420 (uint64_t)&R.getSemantics())) 421 return Res; 422 return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt()); 423} 424 425int FunctionComparator::cmpStrings(StringRef L, StringRef R) const { 426 // Prevent heavy comparison, compare sizes first. 427 if (int Res = cmpNumbers(L.size(), R.size())) 428 return Res; 429 430 // Compare strings lexicographically only when it is necessary: only when 431 // strings are equal in size. 432 return L.compare(R); 433} 434 435int FunctionComparator::cmpAttrs(const AttributeSet L, 436 const AttributeSet R) const { 437 if (int Res = cmpNumbers(L.getNumSlots(), R.getNumSlots())) 438 return Res; 439 440 for (unsigned i = 0, e = L.getNumSlots(); i != e; ++i) { 441 AttributeSet::iterator LI = L.begin(i), LE = L.end(i), RI = R.begin(i), 442 RE = R.end(i); 443 for (; LI != LE && RI != RE; ++LI, ++RI) { 444 Attribute LA = *LI; 445 Attribute RA = *RI; 446 if (LA < RA) 447 return -1; 448 if (RA < LA) 449 return 1; 450 } 451 if (LI != LE) 452 return 1; 453 if (RI != RE) 454 return -1; 455 } 456 return 0; 457} 458 459/// Constants comparison: 460/// 1. Check whether type of L constant could be losslessly bitcasted to R 461/// type. 462/// 2. Compare constant contents. 463/// For more details see declaration comments. 464int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) { 465 466 Type *TyL = L->getType(); 467 Type *TyR = R->getType(); 468 469 // Check whether types are bitcastable. This part is just re-factored 470 // Type::canLosslesslyBitCastTo method, but instead of returning true/false, 471 // we also pack into result which type is "less" for us. 472 int TypesRes = cmpTypes(TyL, TyR); 473 if (TypesRes != 0) { 474 // Types are different, but check whether we can bitcast them. 475 if (!TyL->isFirstClassType()) { 476 if (TyR->isFirstClassType()) 477 return -1; 478 // Neither TyL nor TyR are values of first class type. Return the result 479 // of comparing the types 480 return TypesRes; 481 } 482 if (!TyR->isFirstClassType()) { 483 if (TyL->isFirstClassType()) 484 return 1; 485 return TypesRes; 486 } 487 488 // Vector -> Vector conversions are always lossless if the two vector types 489 // have the same size, otherwise not. 490 unsigned TyLWidth = 0; 491 unsigned TyRWidth = 0; 492 493 if (const VectorType *VecTyL = dyn_cast<VectorType>(TyL)) 494 TyLWidth = VecTyL->getBitWidth(); 495 if (const VectorType *VecTyR = dyn_cast<VectorType>(TyR)) 496 TyRWidth = VecTyR->getBitWidth(); 497 498 if (TyLWidth != TyRWidth) 499 return cmpNumbers(TyLWidth, TyRWidth); 500 501 // Zero bit-width means neither TyL nor TyR are vectors. 502 if (!TyLWidth) { 503 PointerType *PTyL = dyn_cast<PointerType>(TyL); 504 PointerType *PTyR = dyn_cast<PointerType>(TyR); 505 if (PTyL && PTyR) { 506 unsigned AddrSpaceL = PTyL->getAddressSpace(); 507 unsigned AddrSpaceR = PTyR->getAddressSpace(); 508 if (int Res = cmpNumbers(AddrSpaceL, AddrSpaceR)) 509 return Res; 510 } 511 if (PTyL) 512 return 1; 513 if (PTyR) 514 return -1; 515 516 // TyL and TyR aren't vectors, nor pointers. We don't know how to 517 // bitcast them. 518 return TypesRes; 519 } 520 } 521 522 // OK, types are bitcastable, now check constant contents. 523 524 if (L->isNullValue() && R->isNullValue()) 525 return TypesRes; 526 if (L->isNullValue() && !R->isNullValue()) 527 return 1; 528 if (!L->isNullValue() && R->isNullValue()) 529 return -1; 530 531 if (int Res = cmpNumbers(L->getValueID(), R->getValueID())) 532 return Res; 533 534 switch (L->getValueID()) { 535 case Value::UndefValueVal: return TypesRes; 536 case Value::ConstantIntVal: { 537 const APInt &LInt = cast<ConstantInt>(L)->getValue(); 538 const APInt &RInt = cast<ConstantInt>(R)->getValue(); 539 return cmpAPInts(LInt, RInt); 540 } 541 case Value::ConstantFPVal: { 542 const APFloat &LAPF = cast<ConstantFP>(L)->getValueAPF(); 543 const APFloat &RAPF = cast<ConstantFP>(R)->getValueAPF(); 544 return cmpAPFloats(LAPF, RAPF); 545 } 546 case Value::ConstantArrayVal: { 547 const ConstantArray *LA = cast<ConstantArray>(L); 548 const ConstantArray *RA = cast<ConstantArray>(R); 549 uint64_t NumElementsL = cast<ArrayType>(TyL)->getNumElements(); 550 uint64_t NumElementsR = cast<ArrayType>(TyR)->getNumElements(); 551 if (int Res = cmpNumbers(NumElementsL, NumElementsR)) 552 return Res; 553 for (uint64_t i = 0; i < NumElementsL; ++i) { 554 if (int Res = cmpConstants(cast<Constant>(LA->getOperand(i)), 555 cast<Constant>(RA->getOperand(i)))) 556 return Res; 557 } 558 return 0; 559 } 560 case Value::ConstantStructVal: { 561 const ConstantStruct *LS = cast<ConstantStruct>(L); 562 const ConstantStruct *RS = cast<ConstantStruct>(R); 563 unsigned NumElementsL = cast<StructType>(TyL)->getNumElements(); 564 unsigned NumElementsR = cast<StructType>(TyR)->getNumElements(); 565 if (int Res = cmpNumbers(NumElementsL, NumElementsR)) 566 return Res; 567 for (unsigned i = 0; i != NumElementsL; ++i) { 568 if (int Res = cmpConstants(cast<Constant>(LS->getOperand(i)), 569 cast<Constant>(RS->getOperand(i)))) 570 return Res; 571 } 572 return 0; 573 } 574 case Value::ConstantVectorVal: { 575 const ConstantVector *LV = cast<ConstantVector>(L); 576 const ConstantVector *RV = cast<ConstantVector>(R); 577 unsigned NumElementsL = cast<VectorType>(TyL)->getNumElements(); 578 unsigned NumElementsR = cast<VectorType>(TyR)->getNumElements(); 579 if (int Res = cmpNumbers(NumElementsL, NumElementsR)) 580 return Res; 581 for (uint64_t i = 0; i < NumElementsL; ++i) { 582 if (int Res = cmpConstants(cast<Constant>(LV->getOperand(i)), 583 cast<Constant>(RV->getOperand(i)))) 584 return Res; 585 } 586 return 0; 587 } 588 case Value::ConstantExprVal: { 589 const ConstantExpr *LE = cast<ConstantExpr>(L); 590 const ConstantExpr *RE = cast<ConstantExpr>(R); 591 unsigned NumOperandsL = LE->getNumOperands(); 592 unsigned NumOperandsR = RE->getNumOperands(); 593 if (int Res = cmpNumbers(NumOperandsL, NumOperandsR)) 594 return Res; 595 for (unsigned i = 0; i < NumOperandsL; ++i) { 596 if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)), 597 cast<Constant>(RE->getOperand(i)))) 598 return Res; 599 } 600 return 0; 601 } 602 case Value::FunctionVal: 603 case Value::GlobalVariableVal: 604 case Value::GlobalAliasVal: 605 default: // Unknown constant, cast L and R pointers to numbers and compare. 606 return cmpNumbers((uint64_t)L, (uint64_t)R); 607 } 608} 609 610/// cmpType - compares two types, 611/// defines total ordering among the types set. 612/// See method declaration comments for more details. 613int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const { 614 615 PointerType *PTyL = dyn_cast<PointerType>(TyL); 616 PointerType *PTyR = dyn_cast<PointerType>(TyR); 617 618 const DataLayout &DL = FnL->getParent()->getDataLayout(); 619 if (PTyL && PTyL->getAddressSpace() == 0) 620 TyL = DL.getIntPtrType(TyL); 621 if (PTyR && PTyR->getAddressSpace() == 0) 622 TyR = DL.getIntPtrType(TyR); 623 624 if (TyL == TyR) 625 return 0; 626 627 if (int Res = cmpNumbers(TyL->getTypeID(), TyR->getTypeID())) 628 return Res; 629 630 switch (TyL->getTypeID()) { 631 default: 632 llvm_unreachable("Unknown type!"); 633 // Fall through in Release mode. 634 case Type::IntegerTyID: 635 case Type::VectorTyID: 636 // TyL == TyR would have returned true earlier. 637 return cmpNumbers((uint64_t)TyL, (uint64_t)TyR); 638 639 case Type::VoidTyID: 640 case Type::FloatTyID: 641 case Type::DoubleTyID: 642 case Type::X86_FP80TyID: 643 case Type::FP128TyID: 644 case Type::PPC_FP128TyID: 645 case Type::LabelTyID: 646 case Type::MetadataTyID: 647 return 0; 648 649 case Type::PointerTyID: { 650 assert(PTyL && PTyR && "Both types must be pointers here."); 651 return cmpNumbers(PTyL->getAddressSpace(), PTyR->getAddressSpace()); 652 } 653 654 case Type::StructTyID: { 655 StructType *STyL = cast<StructType>(TyL); 656 StructType *STyR = cast<StructType>(TyR); 657 if (STyL->getNumElements() != STyR->getNumElements()) 658 return cmpNumbers(STyL->getNumElements(), STyR->getNumElements()); 659 660 if (STyL->isPacked() != STyR->isPacked()) 661 return cmpNumbers(STyL->isPacked(), STyR->isPacked()); 662 663 for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) { 664 if (int Res = cmpTypes(STyL->getElementType(i), STyR->getElementType(i))) 665 return Res; 666 } 667 return 0; 668 } 669 670 case Type::FunctionTyID: { 671 FunctionType *FTyL = cast<FunctionType>(TyL); 672 FunctionType *FTyR = cast<FunctionType>(TyR); 673 if (FTyL->getNumParams() != FTyR->getNumParams()) 674 return cmpNumbers(FTyL->getNumParams(), FTyR->getNumParams()); 675 676 if (FTyL->isVarArg() != FTyR->isVarArg()) 677 return cmpNumbers(FTyL->isVarArg(), FTyR->isVarArg()); 678 679 if (int Res = cmpTypes(FTyL->getReturnType(), FTyR->getReturnType())) 680 return Res; 681 682 for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) { 683 if (int Res = cmpTypes(FTyL->getParamType(i), FTyR->getParamType(i))) 684 return Res; 685 } 686 return 0; 687 } 688 689 case Type::ArrayTyID: { 690 ArrayType *ATyL = cast<ArrayType>(TyL); 691 ArrayType *ATyR = cast<ArrayType>(TyR); 692 if (ATyL->getNumElements() != ATyR->getNumElements()) 693 return cmpNumbers(ATyL->getNumElements(), ATyR->getNumElements()); 694 return cmpTypes(ATyL->getElementType(), ATyR->getElementType()); 695 } 696 } 697} 698 699// Determine whether the two operations are the same except that pointer-to-A 700// and pointer-to-B are equivalent. This should be kept in sync with 701// Instruction::isSameOperationAs. 702// Read method declaration comments for more details. 703int FunctionComparator::cmpOperations(const Instruction *L, 704 const Instruction *R) const { 705 // Differences from Instruction::isSameOperationAs: 706 // * replace type comparison with calls to isEquivalentType. 707 // * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top 708 // * because of the above, we don't test for the tail bit on calls later on 709 if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode())) 710 return Res; 711 712 if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands())) 713 return Res; 714 715 if (int Res = cmpTypes(L->getType(), R->getType())) 716 return Res; 717 718 if (int Res = cmpNumbers(L->getRawSubclassOptionalData(), 719 R->getRawSubclassOptionalData())) 720 return Res; 721 722 // We have two instructions of identical opcode and #operands. Check to see 723 // if all operands are the same type 724 for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) { 725 if (int Res = 726 cmpTypes(L->getOperand(i)->getType(), R->getOperand(i)->getType())) 727 return Res; 728 } 729 730 // Check special state that is a part of some instructions. 731 if (const LoadInst *LI = dyn_cast<LoadInst>(L)) { 732 if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile())) 733 return Res; 734 if (int Res = 735 cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment())) 736 return Res; 737 if (int Res = 738 cmpNumbers(LI->getOrdering(), cast<LoadInst>(R)->getOrdering())) 739 return Res; 740 if (int Res = 741 cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope())) 742 return Res; 743 return cmpNumbers((uint64_t)LI->getMetadata(LLVMContext::MD_range), 744 (uint64_t)cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range)); 745 } 746 if (const StoreInst *SI = dyn_cast<StoreInst>(L)) { 747 if (int Res = 748 cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile())) 749 return Res; 750 if (int Res = 751 cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment())) 752 return Res; 753 if (int Res = 754 cmpNumbers(SI->getOrdering(), cast<StoreInst>(R)->getOrdering())) 755 return Res; 756 return cmpNumbers(SI->getSynchScope(), cast<StoreInst>(R)->getSynchScope()); 757 } 758 if (const CmpInst *CI = dyn_cast<CmpInst>(L)) 759 return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate()); 760 if (const CallInst *CI = dyn_cast<CallInst>(L)) { 761 if (int Res = cmpNumbers(CI->getCallingConv(), 762 cast<CallInst>(R)->getCallingConv())) 763 return Res; 764 if (int Res = 765 cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes())) 766 return Res; 767 return cmpNumbers( 768 (uint64_t)CI->getMetadata(LLVMContext::MD_range), 769 (uint64_t)cast<CallInst>(R)->getMetadata(LLVMContext::MD_range)); 770 } 771 if (const InvokeInst *CI = dyn_cast<InvokeInst>(L)) { 772 if (int Res = cmpNumbers(CI->getCallingConv(), 773 cast<InvokeInst>(R)->getCallingConv())) 774 return Res; 775 if (int Res = 776 cmpAttrs(CI->getAttributes(), cast<InvokeInst>(R)->getAttributes())) 777 return Res; 778 return cmpNumbers( 779 (uint64_t)CI->getMetadata(LLVMContext::MD_range), 780 (uint64_t)cast<InvokeInst>(R)->getMetadata(LLVMContext::MD_range)); 781 } 782 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) { 783 ArrayRef<unsigned> LIndices = IVI->getIndices(); 784 ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices(); 785 if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) 786 return Res; 787 for (size_t i = 0, e = LIndices.size(); i != e; ++i) { 788 if (int Res = cmpNumbers(LIndices[i], RIndices[i])) 789 return Res; 790 } 791 } 792 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) { 793 ArrayRef<unsigned> LIndices = EVI->getIndices(); 794 ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices(); 795 if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) 796 return Res; 797 for (size_t i = 0, e = LIndices.size(); i != e; ++i) { 798 if (int Res = cmpNumbers(LIndices[i], RIndices[i])) 799 return Res; 800 } 801 } 802 if (const FenceInst *FI = dyn_cast<FenceInst>(L)) { 803 if (int Res = 804 cmpNumbers(FI->getOrdering(), cast<FenceInst>(R)->getOrdering())) 805 return Res; 806 return cmpNumbers(FI->getSynchScope(), cast<FenceInst>(R)->getSynchScope()); 807 } 808 809 if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(L)) { 810 if (int Res = cmpNumbers(CXI->isVolatile(), 811 cast<AtomicCmpXchgInst>(R)->isVolatile())) 812 return Res; 813 if (int Res = cmpNumbers(CXI->isWeak(), 814 cast<AtomicCmpXchgInst>(R)->isWeak())) 815 return Res; 816 if (int Res = cmpNumbers(CXI->getSuccessOrdering(), 817 cast<AtomicCmpXchgInst>(R)->getSuccessOrdering())) 818 return Res; 819 if (int Res = cmpNumbers(CXI->getFailureOrdering(), 820 cast<AtomicCmpXchgInst>(R)->getFailureOrdering())) 821 return Res; 822 return cmpNumbers(CXI->getSynchScope(), 823 cast<AtomicCmpXchgInst>(R)->getSynchScope()); 824 } 825 if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(L)) { 826 if (int Res = cmpNumbers(RMWI->getOperation(), 827 cast<AtomicRMWInst>(R)->getOperation())) 828 return Res; 829 if (int Res = cmpNumbers(RMWI->isVolatile(), 830 cast<AtomicRMWInst>(R)->isVolatile())) 831 return Res; 832 if (int Res = cmpNumbers(RMWI->getOrdering(), 833 cast<AtomicRMWInst>(R)->getOrdering())) 834 return Res; 835 return cmpNumbers(RMWI->getSynchScope(), 836 cast<AtomicRMWInst>(R)->getSynchScope()); 837 } 838 return 0; 839} 840 841// Determine whether two GEP operations perform the same underlying arithmetic. 842// Read method declaration comments for more details. 843int FunctionComparator::cmpGEPs(const GEPOperator *GEPL, 844 const GEPOperator *GEPR) { 845 846 unsigned int ASL = GEPL->getPointerAddressSpace(); 847 unsigned int ASR = GEPR->getPointerAddressSpace(); 848 849 if (int Res = cmpNumbers(ASL, ASR)) 850 return Res; 851 852 // When we have target data, we can reduce the GEP down to the value in bytes 853 // added to the address. 854 const DataLayout &DL = FnL->getParent()->getDataLayout(); 855 unsigned BitWidth = DL.getPointerSizeInBits(ASL); 856 APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0); 857 if (GEPL->accumulateConstantOffset(DL, OffsetL) && 858 GEPR->accumulateConstantOffset(DL, OffsetR)) 859 return cmpAPInts(OffsetL, OffsetR); 860 861 if (int Res = cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(), 862 (uint64_t)GEPR->getPointerOperand()->getType())) 863 return Res; 864 865 if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands())) 866 return Res; 867 868 for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) { 869 if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i))) 870 return Res; 871 } 872 873 return 0; 874} 875 876/// Compare two values used by the two functions under pair-wise comparison. If 877/// this is the first time the values are seen, they're added to the mapping so 878/// that we will detect mismatches on next use. 879/// See comments in declaration for more details. 880int FunctionComparator::cmpValues(const Value *L, const Value *R) { 881 // Catch self-reference case. 882 if (L == FnL) { 883 if (R == FnR) 884 return 0; 885 return -1; 886 } 887 if (R == FnR) { 888 if (L == FnL) 889 return 0; 890 return 1; 891 } 892 893 const Constant *ConstL = dyn_cast<Constant>(L); 894 const Constant *ConstR = dyn_cast<Constant>(R); 895 if (ConstL && ConstR) { 896 if (L == R) 897 return 0; 898 return cmpConstants(ConstL, ConstR); 899 } 900 901 if (ConstL) 902 return 1; 903 if (ConstR) 904 return -1; 905 906 const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L); 907 const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R); 908 909 if (InlineAsmL && InlineAsmR) 910 return cmpNumbers((uint64_t)L, (uint64_t)R); 911 if (InlineAsmL) 912 return 1; 913 if (InlineAsmR) 914 return -1; 915 916 auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())), 917 RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size())); 918 919 return cmpNumbers(LeftSN.first->second, RightSN.first->second); 920} 921// Test whether two basic blocks have equivalent behaviour. 922int FunctionComparator::compare(const BasicBlock *BBL, const BasicBlock *BBR) { 923 BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end(); 924 BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end(); 925 926 do { 927 if (int Res = cmpValues(InstL, InstR)) 928 return Res; 929 930 const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(InstL); 931 const GetElementPtrInst *GEPR = dyn_cast<GetElementPtrInst>(InstR); 932 933 if (GEPL && !GEPR) 934 return 1; 935 if (GEPR && !GEPL) 936 return -1; 937 938 if (GEPL && GEPR) { 939 if (int Res = 940 cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand())) 941 return Res; 942 if (int Res = cmpGEPs(GEPL, GEPR)) 943 return Res; 944 } else { 945 if (int Res = cmpOperations(InstL, InstR)) 946 return Res; 947 assert(InstL->getNumOperands() == InstR->getNumOperands()); 948 949 for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) { 950 Value *OpL = InstL->getOperand(i); 951 Value *OpR = InstR->getOperand(i); 952 if (int Res = cmpValues(OpL, OpR)) 953 return Res; 954 if (int Res = cmpNumbers(OpL->getValueID(), OpR->getValueID())) 955 return Res; 956 // TODO: Already checked in cmpOperation 957 if (int Res = cmpTypes(OpL->getType(), OpR->getType())) 958 return Res; 959 } 960 } 961 962 ++InstL, ++InstR; 963 } while (InstL != InstLE && InstR != InstRE); 964 965 if (InstL != InstLE && InstR == InstRE) 966 return 1; 967 if (InstL == InstLE && InstR != InstRE) 968 return -1; 969 return 0; 970} 971 972// Test whether the two functions have equivalent behaviour. 973int FunctionComparator::compare() { 974 975 sn_mapL.clear(); 976 sn_mapR.clear(); 977 978 if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes())) 979 return Res; 980 981 if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC())) 982 return Res; 983 984 if (FnL->hasGC()) { 985 if (int Res = cmpNumbers((uint64_t)FnL->getGC(), (uint64_t)FnR->getGC())) 986 return Res; 987 } 988 989 if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection())) 990 return Res; 991 992 if (FnL->hasSection()) { 993 if (int Res = cmpStrings(FnL->getSection(), FnR->getSection())) 994 return Res; 995 } 996 997 if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg())) 998 return Res; 999 1000 // TODO: if it's internal and only used in direct calls, we could handle this 1001 // case too. 1002 if (int Res = cmpNumbers(FnL->getCallingConv(), FnR->getCallingConv())) 1003 return Res; 1004 1005 if (int Res = cmpTypes(FnL->getFunctionType(), FnR->getFunctionType())) 1006 return Res; 1007 1008 assert(FnL->arg_size() == FnR->arg_size() && 1009 "Identically typed functions have different numbers of args!"); 1010 1011 // Visit the arguments so that they get enumerated in the order they're 1012 // passed in. 1013 for (Function::const_arg_iterator ArgLI = FnL->arg_begin(), 1014 ArgRI = FnR->arg_begin(), 1015 ArgLE = FnL->arg_end(); 1016 ArgLI != ArgLE; ++ArgLI, ++ArgRI) { 1017 if (cmpValues(ArgLI, ArgRI) != 0) 1018 llvm_unreachable("Arguments repeat!"); 1019 } 1020 1021 // We do a CFG-ordered walk since the actual ordering of the blocks in the 1022 // linked list is immaterial. Our walk starts at the entry block for both 1023 // functions, then takes each block from each terminator in order. As an 1024 // artifact, this also means that unreachable blocks are ignored. 1025 SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs; 1026 SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1. 1027 1028 FnLBBs.push_back(&FnL->getEntryBlock()); 1029 FnRBBs.push_back(&FnR->getEntryBlock()); 1030 1031 VisitedBBs.insert(FnLBBs[0]); 1032 while (!FnLBBs.empty()) { 1033 const BasicBlock *BBL = FnLBBs.pop_back_val(); 1034 const BasicBlock *BBR = FnRBBs.pop_back_val(); 1035 1036 if (int Res = cmpValues(BBL, BBR)) 1037 return Res; 1038 1039 if (int Res = compare(BBL, BBR)) 1040 return Res; 1041 1042 const TerminatorInst *TermL = BBL->getTerminator(); 1043 const TerminatorInst *TermR = BBR->getTerminator(); 1044 1045 assert(TermL->getNumSuccessors() == TermR->getNumSuccessors()); 1046 for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) { 1047 if (!VisitedBBs.insert(TermL->getSuccessor(i)).second) 1048 continue; 1049 1050 FnLBBs.push_back(TermL->getSuccessor(i)); 1051 FnRBBs.push_back(TermR->getSuccessor(i)); 1052 } 1053 } 1054 return 0; 1055} 1056 1057namespace { 1058 1059/// MergeFunctions finds functions which will generate identical machine code, 1060/// by considering all pointer types to be equivalent. Once identified, 1061/// MergeFunctions will fold them by replacing a call to one to a call to a 1062/// bitcast of the other. 1063/// 1064class MergeFunctions : public ModulePass { 1065public: 1066 static char ID; 1067 MergeFunctions() 1068 : ModulePass(ID), HasGlobalAliases(false) { 1069 initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); 1070 } 1071 1072 bool runOnModule(Module &M) override; 1073 1074private: 1075 typedef std::set<FunctionNode> FnTreeType; 1076 1077 /// A work queue of functions that may have been modified and should be 1078 /// analyzed again. 1079 std::vector<WeakVH> Deferred; 1080 1081 /// Checks the rules of order relation introduced among functions set. 1082 /// Returns true, if sanity check has been passed, and false if failed. 1083 bool doSanityCheck(std::vector<WeakVH> &Worklist); 1084 1085 /// Insert a ComparableFunction into the FnTree, or merge it away if it's 1086 /// equal to one that's already present. 1087 bool insert(Function *NewFunction); 1088 1089 /// Remove a Function from the FnTree and queue it up for a second sweep of 1090 /// analysis. 1091 void remove(Function *F); 1092 1093 /// Find the functions that use this Value and remove them from FnTree and 1094 /// queue the functions. 1095 void removeUsers(Value *V); 1096 1097 /// Replace all direct calls of Old with calls of New. Will bitcast New if 1098 /// necessary to make types match. 1099 void replaceDirectCallers(Function *Old, Function *New); 1100 1101 /// Merge two equivalent functions. Upon completion, G may be deleted, or may 1102 /// be converted into a thunk. In either case, it should never be visited 1103 /// again. 1104 void mergeTwoFunctions(Function *F, Function *G); 1105 1106 /// Replace G with a thunk or an alias to F. Deletes G. 1107 void writeThunkOrAlias(Function *F, Function *G); 1108 1109 /// Replace G with a simple tail call to bitcast(F). Also replace direct uses 1110 /// of G with bitcast(F). Deletes G. 1111 void writeThunk(Function *F, Function *G); 1112 1113 /// Replace G with an alias to F. Deletes G. 1114 void writeAlias(Function *F, Function *G); 1115 1116 /// The set of all distinct functions. Use the insert() and remove() methods 1117 /// to modify it. 1118 FnTreeType FnTree; 1119 1120 /// Whether or not the target supports global aliases. 1121 bool HasGlobalAliases; 1122}; 1123 1124} // end anonymous namespace 1125 1126char MergeFunctions::ID = 0; 1127INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false) 1128 1129ModulePass *llvm::createMergeFunctionsPass() { 1130 return new MergeFunctions(); 1131} 1132 1133bool MergeFunctions::doSanityCheck(std::vector<WeakVH> &Worklist) { 1134 if (const unsigned Max = NumFunctionsForSanityCheck) { 1135 unsigned TripleNumber = 0; 1136 bool Valid = true; 1137 1138 dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n"; 1139 1140 unsigned i = 0; 1141 for (std::vector<WeakVH>::iterator I = Worklist.begin(), E = Worklist.end(); 1142 I != E && i < Max; ++I, ++i) { 1143 unsigned j = i; 1144 for (std::vector<WeakVH>::iterator J = I; J != E && j < Max; ++J, ++j) { 1145 Function *F1 = cast<Function>(*I); 1146 Function *F2 = cast<Function>(*J); 1147 int Res1 = FunctionComparator(F1, F2).compare(); 1148 int Res2 = FunctionComparator(F2, F1).compare(); 1149 1150 // If F1 <= F2, then F2 >= F1, otherwise report failure. 1151 if (Res1 != -Res2) { 1152 dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber 1153 << "\n"; 1154 F1->dump(); 1155 F2->dump(); 1156 Valid = false; 1157 } 1158 1159 if (Res1 == 0) 1160 continue; 1161 1162 unsigned k = j; 1163 for (std::vector<WeakVH>::iterator K = J; K != E && k < Max; 1164 ++k, ++K, ++TripleNumber) { 1165 if (K == J) 1166 continue; 1167 1168 Function *F3 = cast<Function>(*K); 1169 int Res3 = FunctionComparator(F1, F3).compare(); 1170 int Res4 = FunctionComparator(F2, F3).compare(); 1171 1172 bool Transitive = true; 1173 1174 if (Res1 != 0 && Res1 == Res4) { 1175 // F1 > F2, F2 > F3 => F1 > F3 1176 Transitive = Res3 == Res1; 1177 } else if (Res3 != 0 && Res3 == -Res4) { 1178 // F1 > F3, F3 > F2 => F1 > F2 1179 Transitive = Res3 == Res1; 1180 } else if (Res4 != 0 && -Res3 == Res4) { 1181 // F2 > F3, F3 > F1 => F2 > F1 1182 Transitive = Res4 == -Res1; 1183 } 1184 1185 if (!Transitive) { 1186 dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: " 1187 << TripleNumber << "\n"; 1188 dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", " 1189 << Res4 << "\n"; 1190 F1->dump(); 1191 F2->dump(); 1192 F3->dump(); 1193 Valid = false; 1194 } 1195 } 1196 } 1197 } 1198 1199 dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n"; 1200 return Valid; 1201 } 1202 return true; 1203} 1204 1205bool MergeFunctions::runOnModule(Module &M) { 1206 bool Changed = false; 1207 1208 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1209 if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) 1210 Deferred.push_back(WeakVH(I)); 1211 } 1212 1213 do { 1214 std::vector<WeakVH> Worklist; 1215 Deferred.swap(Worklist); 1216 1217 DEBUG(doSanityCheck(Worklist)); 1218 1219 DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 1220 DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); 1221 1222 // Insert only strong functions and merge them. Strong function merging 1223 // always deletes one of them. 1224 for (std::vector<WeakVH>::iterator I = Worklist.begin(), 1225 E = Worklist.end(); I != E; ++I) { 1226 if (!*I) continue; 1227 Function *F = cast<Function>(*I); 1228 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 1229 !F->mayBeOverridden()) { 1230 Changed |= insert(F); 1231 } 1232 } 1233 1234 // Insert only weak functions and merge them. By doing these second we 1235 // create thunks to the strong function when possible. When two weak 1236 // functions are identical, we create a new strong function with two weak 1237 // weak thunks to it which are identical but not mergable. 1238 for (std::vector<WeakVH>::iterator I = Worklist.begin(), 1239 E = Worklist.end(); I != E; ++I) { 1240 if (!*I) continue; 1241 Function *F = cast<Function>(*I); 1242 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 1243 F->mayBeOverridden()) { 1244 Changed |= insert(F); 1245 } 1246 } 1247 DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n'); 1248 } while (!Deferred.empty()); 1249 1250 FnTree.clear(); 1251 1252 return Changed; 1253} 1254 1255// Replace direct callers of Old with New. 1256void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { 1257 Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); 1258 for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) { 1259 Use *U = &*UI; 1260 ++UI; 1261 CallSite CS(U->getUser()); 1262 if (CS && CS.isCallee(U)) { 1263 remove(CS.getInstruction()->getParent()->getParent()); 1264 U->set(BitcastNew); 1265 } 1266 } 1267} 1268 1269// Replace G with an alias to F if possible, or else a thunk to F. Deletes G. 1270void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { 1271 if (HasGlobalAliases && G->hasUnnamedAddr()) { 1272 if (G->hasExternalLinkage() || G->hasLocalLinkage() || 1273 G->hasWeakLinkage()) { 1274 writeAlias(F, G); 1275 return; 1276 } 1277 } 1278 1279 writeThunk(F, G); 1280} 1281 1282// Helper for writeThunk, 1283// Selects proper bitcast operation, 1284// but a bit simpler then CastInst::getCastOpcode. 1285static Value *createCast(IRBuilder<false> &Builder, Value *V, Type *DestTy) { 1286 Type *SrcTy = V->getType(); 1287 if (SrcTy->isStructTy()) { 1288 assert(DestTy->isStructTy()); 1289 assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements()); 1290 Value *Result = UndefValue::get(DestTy); 1291 for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) { 1292 Value *Element = createCast( 1293 Builder, Builder.CreateExtractValue(V, makeArrayRef(I)), 1294 DestTy->getStructElementType(I)); 1295 1296 Result = 1297 Builder.CreateInsertValue(Result, Element, makeArrayRef(I)); 1298 } 1299 return Result; 1300 } 1301 assert(!DestTy->isStructTy()); 1302 if (SrcTy->isIntegerTy() && DestTy->isPointerTy()) 1303 return Builder.CreateIntToPtr(V, DestTy); 1304 else if (SrcTy->isPointerTy() && DestTy->isIntegerTy()) 1305 return Builder.CreatePtrToInt(V, DestTy); 1306 else 1307 return Builder.CreateBitCast(V, DestTy); 1308} 1309 1310// Replace G with a simple tail call to bitcast(F). Also replace direct uses 1311// of G with bitcast(F). Deletes G. 1312void MergeFunctions::writeThunk(Function *F, Function *G) { 1313 if (!G->mayBeOverridden()) { 1314 // Redirect direct callers of G to F. 1315 replaceDirectCallers(G, F); 1316 } 1317 1318 // If G was internal then we may have replaced all uses of G with F. If so, 1319 // stop here and delete G. There's no need for a thunk. 1320 if (G->hasLocalLinkage() && G->use_empty()) { 1321 G->eraseFromParent(); 1322 return; 1323 } 1324 1325 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 1326 G->getParent()); 1327 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 1328 IRBuilder<false> Builder(BB); 1329 1330 SmallVector<Value *, 16> Args; 1331 unsigned i = 0; 1332 FunctionType *FFTy = F->getFunctionType(); 1333 for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 1334 AI != AE; ++AI) { 1335 Args.push_back(createCast(Builder, (Value*)AI, FFTy->getParamType(i))); 1336 ++i; 1337 } 1338 1339 CallInst *CI = Builder.CreateCall(F, Args); 1340 CI->setTailCall(); 1341 CI->setCallingConv(F->getCallingConv()); 1342 if (NewG->getReturnType()->isVoidTy()) { 1343 Builder.CreateRetVoid(); 1344 } else { 1345 Builder.CreateRet(createCast(Builder, CI, NewG->getReturnType())); 1346 } 1347 1348 NewG->copyAttributesFrom(G); 1349 NewG->takeName(G); 1350 removeUsers(G); 1351 G->replaceAllUsesWith(NewG); 1352 G->eraseFromParent(); 1353 1354 DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n'); 1355 ++NumThunksWritten; 1356} 1357 1358// Replace G with an alias to F and delete G. 1359void MergeFunctions::writeAlias(Function *F, Function *G) { 1360 PointerType *PTy = G->getType(); 1361 auto *GA = GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(), 1362 G->getLinkage(), "", F); 1363 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 1364 GA->takeName(G); 1365 GA->setVisibility(G->getVisibility()); 1366 removeUsers(G); 1367 G->replaceAllUsesWith(GA); 1368 G->eraseFromParent(); 1369 1370 DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); 1371 ++NumAliasesWritten; 1372} 1373 1374// Merge two equivalent functions. Upon completion, Function G is deleted. 1375void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { 1376 if (F->mayBeOverridden()) { 1377 assert(G->mayBeOverridden()); 1378 1379 if (HasGlobalAliases) { 1380 // Make them both thunks to the same internal function. 1381 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 1382 F->getParent()); 1383 H->copyAttributesFrom(F); 1384 H->takeName(F); 1385 removeUsers(F); 1386 F->replaceAllUsesWith(H); 1387 1388 unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); 1389 1390 writeAlias(F, G); 1391 writeAlias(F, H); 1392 1393 F->setAlignment(MaxAlignment); 1394 F->setLinkage(GlobalValue::PrivateLinkage); 1395 } else { 1396 // We can't merge them. Instead, pick one and update all direct callers 1397 // to call it and hope that we improve the instruction cache hit rate. 1398 replaceDirectCallers(G, F); 1399 } 1400 1401 ++NumDoubleWeak; 1402 } else { 1403 writeThunkOrAlias(F, G); 1404 } 1405 1406 ++NumFunctionsMerged; 1407} 1408 1409// Insert a ComparableFunction into the FnTree, or merge it away if equal to one 1410// that was already inserted. 1411bool MergeFunctions::insert(Function *NewFunction) { 1412 std::pair<FnTreeType::iterator, bool> Result = 1413 FnTree.insert(FunctionNode(NewFunction)); 1414 1415 if (Result.second) { 1416 DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n'); 1417 return false; 1418 } 1419 1420 const FunctionNode &OldF = *Result.first; 1421 1422 // Don't merge tiny functions, since it can just end up making the function 1423 // larger. 1424 // FIXME: Should still merge them if they are unnamed_addr and produce an 1425 // alias. 1426 if (NewFunction->size() == 1) { 1427 if (NewFunction->front().size() <= 2) { 1428 DEBUG(dbgs() << NewFunction->getName() 1429 << " is to small to bother merging\n"); 1430 return false; 1431 } 1432 } 1433 1434 // Never thunk a strong function to a weak function. 1435 assert(!OldF.getFunc()->mayBeOverridden() || NewFunction->mayBeOverridden()); 1436 1437 DEBUG(dbgs() << " " << OldF.getFunc()->getName() 1438 << " == " << NewFunction->getName() << '\n'); 1439 1440 Function *DeleteF = NewFunction; 1441 mergeTwoFunctions(OldF.getFunc(), DeleteF); 1442 return true; 1443} 1444 1445// Remove a function from FnTree. If it was already in FnTree, add 1446// it to Deferred so that we'll look at it in the next round. 1447void MergeFunctions::remove(Function *F) { 1448 // We need to make sure we remove F, not a function "equal" to F per the 1449 // function equality comparator. 1450 FnTreeType::iterator found = FnTree.find(FunctionNode(F)); 1451 size_t Erased = 0; 1452 if (found != FnTree.end() && found->getFunc() == F) { 1453 Erased = 1; 1454 FnTree.erase(found); 1455 } 1456 1457 if (Erased) { 1458 DEBUG(dbgs() << "Removed " << F->getName() 1459 << " from set and deferred it.\n"); 1460 Deferred.push_back(F); 1461 } 1462} 1463 1464// For each instruction used by the value, remove() the function that contains 1465// the instruction. This should happen right before a call to RAUW. 1466void MergeFunctions::removeUsers(Value *V) { 1467 std::vector<Value *> Worklist; 1468 Worklist.push_back(V); 1469 while (!Worklist.empty()) { 1470 Value *V = Worklist.back(); 1471 Worklist.pop_back(); 1472 1473 for (User *U : V->users()) { 1474 if (Instruction *I = dyn_cast<Instruction>(U)) { 1475 remove(I->getParent()->getParent()); 1476 } else if (isa<GlobalValue>(U)) { 1477 // do nothing 1478 } else if (Constant *C = dyn_cast<Constant>(U)) { 1479 for (User *UU : C->users()) 1480 Worklist.push_back(UU); 1481 } 1482 } 1483 } 1484} 1485