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 // As an optimization, a hash of the function structure is calculated first, and 32 // two functions are only compared if they have the same hash. This hash is 33 // cheap to compute, and has the property that if function F == G according to 34 // the comparison function, then hash(F) == hash(G). This consistency property 35 // is critical to ensuring all possible merging opportunities are exploited. 36 // Collisions in the hash affect the speed of the pass but not the correctness 37 // or determinism of the resulting transformation. 38 // 39 // When a match is found the functions are folded. If both functions are 40 // overridable, we move the functionality into a new internal function and 41 // leave two overridable thunks to it. 42 // 43 //===----------------------------------------------------------------------===// 44 // 45 // Future work: 46 // 47 // * virtual functions. 48 // 49 // Many functions have their address taken by the virtual function table for 50 // the object they belong to. However, as long as it's only used for a lookup 51 // and call, this is irrelevant, and we'd like to fold such functions. 52 // 53 // * be smarter about bitcasts. 54 // 55 // In order to fold functions, we will sometimes add either bitcast instructions 56 // or bitcast constant expressions. Unfortunately, this can confound further 57 // analysis since the two functions differ where one has a bitcast and the 58 // other doesn't. We should learn to look through bitcasts. 59 // 60 // * Compare complex types with pointer types inside. 61 // * Compare cross-reference cases. 62 // * Compare complex expressions. 63 // 64 // All the three issues above could be described as ability to prove that 65 // fA == fB == fC == fE == fF == fG in example below: 66 // 67 // void fA() { 68 // fB(); 69 // } 70 // void fB() { 71 // fA(); 72 // } 73 // 74 // void fE() { 75 // fF(); 76 // } 77 // void fF() { 78 // fG(); 79 // } 80 // void fG() { 81 // fE(); 82 // } 83 // 84 // Simplest cross-reference case (fA <--> fB) was implemented in previous 85 // versions of MergeFunctions, though it presented only in two function pairs 86 // in test-suite (that counts >50k functions) 87 // Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A) 88 // could cover much more cases. 89 // 90 //===----------------------------------------------------------------------===// 91 92 #include "llvm/ADT/Hashing.h" 93 #include "llvm/ADT/STLExtras.h" 94 #include "llvm/ADT/SmallSet.h" 95 #include "llvm/ADT/Statistic.h" 96 #include "llvm/IR/CallSite.h" 97 #include "llvm/IR/Constants.h" 98 #include "llvm/IR/DataLayout.h" 99 #include "llvm/IR/IRBuilder.h" 100 #include "llvm/IR/InlineAsm.h" 101 #include "llvm/IR/Instructions.h" 102 #include "llvm/IR/LLVMContext.h" 103 #include "llvm/IR/Module.h" 104 #include "llvm/IR/Operator.h" 105 #include "llvm/IR/ValueHandle.h" 106 #include "llvm/IR/ValueMap.h" 107 #include "llvm/Pass.h" 108 #include "llvm/Support/CommandLine.h" 109 #include "llvm/Support/Debug.h" 110 #include "llvm/Support/ErrorHandling.h" 111 #include "llvm/Support/raw_ostream.h" 112 #include "llvm/Transforms/IPO.h" 113 #include <vector> 114 115 using namespace llvm; 116 117 #define DEBUG_TYPE "mergefunc" 118 119 STATISTIC(NumFunctionsMerged, "Number of functions merged"); 120 STATISTIC(NumThunksWritten, "Number of thunks generated"); 121 STATISTIC(NumAliasesWritten, "Number of aliases generated"); 122 STATISTIC(NumDoubleWeak, "Number of new functions created"); 123 124 static cl::opt<unsigned> NumFunctionsForSanityCheck( 125 "mergefunc-sanity", 126 cl::desc("How many functions in module could be used for " 127 "MergeFunctions pass sanity check. " 128 "'0' disables this check. Works only with '-debug' key."), 129 cl::init(0), cl::Hidden); 130 131 namespace { 132 133 /// GlobalNumberState assigns an integer to each global value in the program, 134 /// which is used by the comparison routine to order references to globals. This 135 /// state must be preserved throughout the pass, because Functions and other 136 /// globals need to maintain their relative order. Globals are assigned a number 137 /// when they are first visited. This order is deterministic, and so the 138 /// assigned numbers are as well. When two functions are merged, neither number 139 /// is updated. If the symbols are weak, this would be incorrect. If they are 140 /// strong, then one will be replaced at all references to the other, and so 141 /// direct callsites will now see one or the other symbol, and no update is 142 /// necessary. Note that if we were guaranteed unique names, we could just 143 /// compare those, but this would not work for stripped bitcodes or for those 144 /// few symbols without a name. 145 class GlobalNumberState { 146 struct Config : ValueMapConfig<GlobalValue*> { 147 enum { FollowRAUW = false }; 148 }; 149 // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW 150 // occurs, the mapping does not change. Tracking changes is unnecessary, and 151 // also problematic for weak symbols (which may be overwritten). 152 typedef ValueMap<GlobalValue *, uint64_t, Config> ValueNumberMap; 153 ValueNumberMap GlobalNumbers; 154 // The next unused serial number to assign to a global. 155 uint64_t NextNumber; 156 public: 157 GlobalNumberState() : GlobalNumbers(), NextNumber(0) {} 158 uint64_t getNumber(GlobalValue* Global) { 159 ValueNumberMap::iterator MapIter; 160 bool Inserted; 161 std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber}); 162 if (Inserted) 163 NextNumber++; 164 return MapIter->second; 165 } 166 void clear() { 167 GlobalNumbers.clear(); 168 } 169 }; 170 171 /// FunctionComparator - Compares two functions to determine whether or not 172 /// they will generate machine code with the same behaviour. DataLayout is 173 /// used if available. The comparator always fails conservatively (erring on the 174 /// side of claiming that two functions are different). 175 class FunctionComparator { 176 public: 177 FunctionComparator(const Function *F1, const Function *F2, 178 GlobalNumberState* GN) 179 : FnL(F1), FnR(F2), GlobalNumbers(GN) {} 180 181 /// Test whether the two functions have equivalent behaviour. 182 int compare(); 183 /// Hash a function. Equivalent functions will have the same hash, and unequal 184 /// functions will have different hashes with high probability. 185 typedef uint64_t FunctionHash; 186 static FunctionHash functionHash(Function &); 187 188 private: 189 /// Test whether two basic blocks have equivalent behaviour. 190 int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR) const; 191 192 /// Constants comparison. 193 /// Its analog to lexicographical comparison between hypothetical numbers 194 /// of next format: 195 /// <bitcastability-trait><raw-bit-contents> 196 /// 197 /// 1. Bitcastability. 198 /// Check whether L's type could be losslessly bitcasted to R's type. 199 /// On this stage method, in case when lossless bitcast is not possible 200 /// method returns -1 or 1, thus also defining which type is greater in 201 /// context of bitcastability. 202 /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight 203 /// to the contents comparison. 204 /// If types differ, remember types comparison result and check 205 /// whether we still can bitcast types. 206 /// Stage 1: Types that satisfies isFirstClassType conditions are always 207 /// greater then others. 208 /// Stage 2: Vector is greater then non-vector. 209 /// If both types are vectors, then vector with greater bitwidth is 210 /// greater. 211 /// If both types are vectors with the same bitwidth, then types 212 /// are bitcastable, and we can skip other stages, and go to contents 213 /// comparison. 214 /// Stage 3: Pointer types are greater than non-pointers. If both types are 215 /// pointers of the same address space - go to contents comparison. 216 /// Different address spaces: pointer with greater address space is 217 /// greater. 218 /// Stage 4: Types are neither vectors, nor pointers. And they differ. 219 /// We don't know how to bitcast them. So, we better don't do it, 220 /// and return types comparison result (so it determines the 221 /// relationship among constants we don't know how to bitcast). 222 /// 223 /// Just for clearance, let's see how the set of constants could look 224 /// on single dimension axis: 225 /// 226 /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors] 227 /// Where: NFCT - Not a FirstClassType 228 /// FCT - FirstClassTyp: 229 /// 230 /// 2. Compare raw contents. 231 /// It ignores types on this stage and only compares bits from L and R. 232 /// Returns 0, if L and R has equivalent contents. 233 /// -1 or 1 if values are different. 234 /// Pretty trivial: 235 /// 2.1. If contents are numbers, compare numbers. 236 /// Ints with greater bitwidth are greater. Ints with same bitwidths 237 /// compared by their contents. 238 /// 2.2. "And so on". Just to avoid discrepancies with comments 239 /// perhaps it would be better to read the implementation itself. 240 /// 3. And again about overall picture. Let's look back at how the ordered set 241 /// of constants will look like: 242 /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors] 243 /// 244 /// Now look, what could be inside [FCT, "others"], for example: 245 /// [FCT, "others"] = 246 /// [ 247 /// [double 0.1], [double 1.23], 248 /// [i32 1], [i32 2], 249 /// { double 1.0 }, ; StructTyID, NumElements = 1 250 /// { i32 1 }, ; StructTyID, NumElements = 1 251 /// { double 1, i32 1 }, ; StructTyID, NumElements = 2 252 /// { i32 1, double 1 } ; StructTyID, NumElements = 2 253 /// ] 254 /// 255 /// Let's explain the order. Float numbers will be less than integers, just 256 /// because of cmpType terms: FloatTyID < IntegerTyID. 257 /// Floats (with same fltSemantics) are sorted according to their value. 258 /// Then you can see integers, and they are, like a floats, 259 /// could be easy sorted among each others. 260 /// The structures. Structures are grouped at the tail, again because of their 261 /// TypeID: StructTyID > IntegerTyID > FloatTyID. 262 /// Structures with greater number of elements are greater. Structures with 263 /// greater elements going first are greater. 264 /// The same logic with vectors, arrays and other possible complex types. 265 /// 266 /// Bitcastable constants. 267 /// Let's assume, that some constant, belongs to some group of 268 /// "so-called-equal" values with different types, and at the same time 269 /// belongs to another group of constants with equal types 270 /// and "really" equal values. 271 /// 272 /// Now, prove that this is impossible: 273 /// 274 /// If constant A with type TyA is bitcastable to B with type TyB, then: 275 /// 1. All constants with equal types to TyA, are bitcastable to B. Since 276 /// those should be vectors (if TyA is vector), pointers 277 /// (if TyA is pointer), or else (if TyA equal to TyB), those types should 278 /// be equal to TyB. 279 /// 2. All constants with non-equal, but bitcastable types to TyA, are 280 /// bitcastable to B. 281 /// Once again, just because we allow it to vectors and pointers only. 282 /// This statement could be expanded as below: 283 /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to 284 /// vector B, and thus bitcastable to B as well. 285 /// 2.2. All pointers of the same address space, no matter what they point to, 286 /// bitcastable. So if C is pointer, it could be bitcasted to A and to B. 287 /// So any constant equal or bitcastable to A is equal or bitcastable to B. 288 /// QED. 289 /// 290 /// In another words, for pointers and vectors, we ignore top-level type and 291 /// look at their particular properties (bit-width for vectors, and 292 /// address space for pointers). 293 /// If these properties are equal - compare their contents. 294 int cmpConstants(const Constant *L, const Constant *R) const; 295 296 /// Compares two global values by number. Uses the GlobalNumbersState to 297 /// identify the same gobals across function calls. 298 int cmpGlobalValues(GlobalValue *L, GlobalValue *R) const; 299 300 /// Assign or look up previously assigned numbers for the two values, and 301 /// return whether the numbers are equal. Numbers are assigned in the order 302 /// visited. 303 /// Comparison order: 304 /// Stage 0: Value that is function itself is always greater then others. 305 /// If left and right values are references to their functions, then 306 /// they are equal. 307 /// Stage 1: Constants are greater than non-constants. 308 /// If both left and right are constants, then the result of 309 /// cmpConstants is used as cmpValues result. 310 /// Stage 2: InlineAsm instances are greater than others. If both left and 311 /// right are InlineAsm instances, InlineAsm* pointers casted to 312 /// integers and compared as numbers. 313 /// Stage 3: For all other cases we compare order we meet these values in 314 /// their functions. If right value was met first during scanning, 315 /// then left value is greater. 316 /// In another words, we compare serial numbers, for more details 317 /// see comments for sn_mapL and sn_mapR. 318 int cmpValues(const Value *L, const Value *R) const; 319 320 /// Compare two Instructions for equivalence, similar to 321 /// Instruction::isSameOperationAs. 322 /// 323 /// Stages are listed in "most significant stage first" order: 324 /// On each stage below, we do comparison between some left and right 325 /// operation parts. If parts are non-equal, we assign parts comparison 326 /// result to the operation comparison result and exit from method. 327 /// Otherwise we proceed to the next stage. 328 /// Stages: 329 /// 1. Operations opcodes. Compared as numbers. 330 /// 2. Number of operands. 331 /// 3. Operation types. Compared with cmpType method. 332 /// 4. Compare operation subclass optional data as stream of bytes: 333 /// just convert it to integers and call cmpNumbers. 334 /// 5. Compare in operation operand types with cmpType in 335 /// most significant operand first order. 336 /// 6. Last stage. Check operations for some specific attributes. 337 /// For example, for Load it would be: 338 /// 6.1.Load: volatile (as boolean flag) 339 /// 6.2.Load: alignment (as integer numbers) 340 /// 6.3.Load: ordering (as underlying enum class value) 341 /// 6.4.Load: synch-scope (as integer numbers) 342 /// 6.5.Load: range metadata (as integer ranges) 343 /// On this stage its better to see the code, since its not more than 10-15 344 /// strings for particular instruction, and could change sometimes. 345 int cmpOperations(const Instruction *L, const Instruction *R) const; 346 347 /// Compare two GEPs for equivalent pointer arithmetic. 348 /// Parts to be compared for each comparison stage, 349 /// most significant stage first: 350 /// 1. Address space. As numbers. 351 /// 2. Constant offset, (using GEPOperator::accumulateConstantOffset method). 352 /// 3. Pointer operand type (using cmpType method). 353 /// 4. Number of operands. 354 /// 5. Compare operands, using cmpValues method. 355 int cmpGEPs(const GEPOperator *GEPL, const GEPOperator *GEPR) const; 356 int cmpGEPs(const GetElementPtrInst *GEPL, 357 const GetElementPtrInst *GEPR) const { 358 return cmpGEPs(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR)); 359 } 360 361 /// cmpType - compares two types, 362 /// defines total ordering among the types set. 363 /// 364 /// Return values: 365 /// 0 if types are equal, 366 /// -1 if Left is less than Right, 367 /// +1 if Left is greater than Right. 368 /// 369 /// Description: 370 /// Comparison is broken onto stages. Like in lexicographical comparison 371 /// stage coming first has higher priority. 372 /// On each explanation stage keep in mind total ordering properties. 373 /// 374 /// 0. Before comparison we coerce pointer types of 0 address space to 375 /// integer. 376 /// We also don't bother with same type at left and right, so 377 /// just return 0 in this case. 378 /// 379 /// 1. If types are of different kind (different type IDs). 380 /// Return result of type IDs comparison, treating them as numbers. 381 /// 2. If types are integers, check that they have the same width. If they 382 /// are vectors, check that they have the same count and subtype. 383 /// 3. Types have the same ID, so check whether they are one of: 384 /// * Void 385 /// * Float 386 /// * Double 387 /// * X86_FP80 388 /// * FP128 389 /// * PPC_FP128 390 /// * Label 391 /// * Metadata 392 /// We can treat these types as equal whenever their IDs are same. 393 /// 4. If Left and Right are pointers, return result of address space 394 /// comparison (numbers comparison). We can treat pointer types of same 395 /// address space as equal. 396 /// 5. If types are complex. 397 /// Then both Left and Right are to be expanded and their element types will 398 /// be checked with the same way. If we get Res != 0 on some stage, return it. 399 /// Otherwise return 0. 400 /// 6. For all other cases put llvm_unreachable. 401 int cmpTypes(Type *TyL, Type *TyR) const; 402 403 int cmpNumbers(uint64_t L, uint64_t R) const; 404 int cmpOrderings(AtomicOrdering L, AtomicOrdering R) const; 405 int cmpAPInts(const APInt &L, const APInt &R) const; 406 int cmpAPFloats(const APFloat &L, const APFloat &R) const; 407 int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const; 408 int cmpMem(StringRef L, StringRef R) const; 409 int cmpAttrs(const AttributeSet L, const AttributeSet R) const; 410 int cmpRangeMetadata(const MDNode *L, const MDNode *R) const; 411 int cmpOperandBundlesSchema(const Instruction *L, const Instruction *R) const; 412 413 // The two functions undergoing comparison. 414 const Function *FnL, *FnR; 415 416 /// Assign serial numbers to values from left function, and values from 417 /// right function. 418 /// Explanation: 419 /// Being comparing functions we need to compare values we meet at left and 420 /// right sides. 421 /// Its easy to sort things out for external values. It just should be 422 /// the same value at left and right. 423 /// But for local values (those were introduced inside function body) 424 /// we have to ensure they were introduced at exactly the same place, 425 /// and plays the same role. 426 /// Let's assign serial number to each value when we meet it first time. 427 /// Values that were met at same place will be with same serial numbers. 428 /// In this case it would be good to explain few points about values assigned 429 /// to BBs and other ways of implementation (see below). 430 /// 431 /// 1. Safety of BB reordering. 432 /// It's safe to change the order of BasicBlocks in function. 433 /// Relationship with other functions and serial numbering will not be 434 /// changed in this case. 435 /// As follows from FunctionComparator::compare(), we do CFG walk: we start 436 /// from the entry, and then take each terminator. So it doesn't matter how in 437 /// fact BBs are ordered in function. And since cmpValues are called during 438 /// this walk, the numbering depends only on how BBs located inside the CFG. 439 /// So the answer is - yes. We will get the same numbering. 440 /// 441 /// 2. Impossibility to use dominance properties of values. 442 /// If we compare two instruction operands: first is usage of local 443 /// variable AL from function FL, and second is usage of local variable AR 444 /// from FR, we could compare their origins and check whether they are 445 /// defined at the same place. 446 /// But, we are still not able to compare operands of PHI nodes, since those 447 /// could be operands from further BBs we didn't scan yet. 448 /// So it's impossible to use dominance properties in general. 449 mutable DenseMap<const Value*, int> sn_mapL, sn_mapR; 450 451 // The global state we will use 452 GlobalNumberState* GlobalNumbers; 453 }; 454 455 class FunctionNode { 456 mutable AssertingVH<Function> F; 457 FunctionComparator::FunctionHash Hash; 458 public: 459 // Note the hash is recalculated potentially multiple times, but it is cheap. 460 FunctionNode(Function *F) 461 : F(F), Hash(FunctionComparator::functionHash(*F)) {} 462 Function *getFunc() const { return F; } 463 FunctionComparator::FunctionHash getHash() const { return Hash; } 464 465 /// Replace the reference to the function F by the function G, assuming their 466 /// implementations are equal. 467 void replaceBy(Function *G) const { 468 F = G; 469 } 470 471 void release() { F = nullptr; } 472 }; 473 } // end anonymous namespace 474 475 int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const { 476 if (L < R) return -1; 477 if (L > R) return 1; 478 return 0; 479 } 480 481 int FunctionComparator::cmpOrderings(AtomicOrdering L, AtomicOrdering R) const { 482 if ((int)L < (int)R) return -1; 483 if ((int)L > (int)R) return 1; 484 return 0; 485 } 486 487 int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const { 488 if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth())) 489 return Res; 490 if (L.ugt(R)) return 1; 491 if (R.ugt(L)) return -1; 492 return 0; 493 } 494 495 int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const { 496 // Floats are ordered first by semantics (i.e. float, double, half, etc.), 497 // then by value interpreted as a bitstring (aka APInt). 498 const fltSemantics &SL = L.getSemantics(), &SR = R.getSemantics(); 499 if (int Res = cmpNumbers(APFloat::semanticsPrecision(SL), 500 APFloat::semanticsPrecision(SR))) 501 return Res; 502 if (int Res = cmpNumbers(APFloat::semanticsMaxExponent(SL), 503 APFloat::semanticsMaxExponent(SR))) 504 return Res; 505 if (int Res = cmpNumbers(APFloat::semanticsMinExponent(SL), 506 APFloat::semanticsMinExponent(SR))) 507 return Res; 508 if (int Res = cmpNumbers(APFloat::semanticsSizeInBits(SL), 509 APFloat::semanticsSizeInBits(SR))) 510 return Res; 511 return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt()); 512 } 513 514 int FunctionComparator::cmpMem(StringRef L, StringRef R) const { 515 // Prevent heavy comparison, compare sizes first. 516 if (int Res = cmpNumbers(L.size(), R.size())) 517 return Res; 518 519 // Compare strings lexicographically only when it is necessary: only when 520 // strings are equal in size. 521 return L.compare(R); 522 } 523 524 int FunctionComparator::cmpAttrs(const AttributeSet L, 525 const AttributeSet R) const { 526 if (int Res = cmpNumbers(L.getNumSlots(), R.getNumSlots())) 527 return Res; 528 529 for (unsigned i = 0, e = L.getNumSlots(); i != e; ++i) { 530 AttributeSet::iterator LI = L.begin(i), LE = L.end(i), RI = R.begin(i), 531 RE = R.end(i); 532 for (; LI != LE && RI != RE; ++LI, ++RI) { 533 Attribute LA = *LI; 534 Attribute RA = *RI; 535 if (LA < RA) 536 return -1; 537 if (RA < LA) 538 return 1; 539 } 540 if (LI != LE) 541 return 1; 542 if (RI != RE) 543 return -1; 544 } 545 return 0; 546 } 547 548 int FunctionComparator::cmpRangeMetadata(const MDNode *L, 549 const MDNode *R) const { 550 if (L == R) 551 return 0; 552 if (!L) 553 return -1; 554 if (!R) 555 return 1; 556 // Range metadata is a sequence of numbers. Make sure they are the same 557 // sequence. 558 // TODO: Note that as this is metadata, it is possible to drop and/or merge 559 // this data when considering functions to merge. Thus this comparison would 560 // return 0 (i.e. equivalent), but merging would become more complicated 561 // because the ranges would need to be unioned. It is not likely that 562 // functions differ ONLY in this metadata if they are actually the same 563 // function semantically. 564 if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands())) 565 return Res; 566 for (size_t I = 0; I < L->getNumOperands(); ++I) { 567 ConstantInt *LLow = mdconst::extract<ConstantInt>(L->getOperand(I)); 568 ConstantInt *RLow = mdconst::extract<ConstantInt>(R->getOperand(I)); 569 if (int Res = cmpAPInts(LLow->getValue(), RLow->getValue())) 570 return Res; 571 } 572 return 0; 573 } 574 575 int FunctionComparator::cmpOperandBundlesSchema(const Instruction *L, 576 const Instruction *R) const { 577 ImmutableCallSite LCS(L); 578 ImmutableCallSite RCS(R); 579 580 assert(LCS && RCS && "Must be calls or invokes!"); 581 assert(LCS.isCall() == RCS.isCall() && "Can't compare otherwise!"); 582 583 if (int Res = 584 cmpNumbers(LCS.getNumOperandBundles(), RCS.getNumOperandBundles())) 585 return Res; 586 587 for (unsigned i = 0, e = LCS.getNumOperandBundles(); i != e; ++i) { 588 auto OBL = LCS.getOperandBundleAt(i); 589 auto OBR = RCS.getOperandBundleAt(i); 590 591 if (int Res = OBL.getTagName().compare(OBR.getTagName())) 592 return Res; 593 594 if (int Res = cmpNumbers(OBL.Inputs.size(), OBR.Inputs.size())) 595 return Res; 596 } 597 598 return 0; 599 } 600 601 /// Constants comparison: 602 /// 1. Check whether type of L constant could be losslessly bitcasted to R 603 /// type. 604 /// 2. Compare constant contents. 605 /// For more details see declaration comments. 606 int FunctionComparator::cmpConstants(const Constant *L, 607 const Constant *R) const { 608 609 Type *TyL = L->getType(); 610 Type *TyR = R->getType(); 611 612 // Check whether types are bitcastable. This part is just re-factored 613 // Type::canLosslesslyBitCastTo method, but instead of returning true/false, 614 // we also pack into result which type is "less" for us. 615 int TypesRes = cmpTypes(TyL, TyR); 616 if (TypesRes != 0) { 617 // Types are different, but check whether we can bitcast them. 618 if (!TyL->isFirstClassType()) { 619 if (TyR->isFirstClassType()) 620 return -1; 621 // Neither TyL nor TyR are values of first class type. Return the result 622 // of comparing the types 623 return TypesRes; 624 } 625 if (!TyR->isFirstClassType()) { 626 if (TyL->isFirstClassType()) 627 return 1; 628 return TypesRes; 629 } 630 631 // Vector -> Vector conversions are always lossless if the two vector types 632 // have the same size, otherwise not. 633 unsigned TyLWidth = 0; 634 unsigned TyRWidth = 0; 635 636 if (auto *VecTyL = dyn_cast<VectorType>(TyL)) 637 TyLWidth = VecTyL->getBitWidth(); 638 if (auto *VecTyR = dyn_cast<VectorType>(TyR)) 639 TyRWidth = VecTyR->getBitWidth(); 640 641 if (TyLWidth != TyRWidth) 642 return cmpNumbers(TyLWidth, TyRWidth); 643 644 // Zero bit-width means neither TyL nor TyR are vectors. 645 if (!TyLWidth) { 646 PointerType *PTyL = dyn_cast<PointerType>(TyL); 647 PointerType *PTyR = dyn_cast<PointerType>(TyR); 648 if (PTyL && PTyR) { 649 unsigned AddrSpaceL = PTyL->getAddressSpace(); 650 unsigned AddrSpaceR = PTyR->getAddressSpace(); 651 if (int Res = cmpNumbers(AddrSpaceL, AddrSpaceR)) 652 return Res; 653 } 654 if (PTyL) 655 return 1; 656 if (PTyR) 657 return -1; 658 659 // TyL and TyR aren't vectors, nor pointers. We don't know how to 660 // bitcast them. 661 return TypesRes; 662 } 663 } 664 665 // OK, types are bitcastable, now check constant contents. 666 667 if (L->isNullValue() && R->isNullValue()) 668 return TypesRes; 669 if (L->isNullValue() && !R->isNullValue()) 670 return 1; 671 if (!L->isNullValue() && R->isNullValue()) 672 return -1; 673 674 auto GlobalValueL = const_cast<GlobalValue*>(dyn_cast<GlobalValue>(L)); 675 auto GlobalValueR = const_cast<GlobalValue*>(dyn_cast<GlobalValue>(R)); 676 if (GlobalValueL && GlobalValueR) { 677 return cmpGlobalValues(GlobalValueL, GlobalValueR); 678 } 679 680 if (int Res = cmpNumbers(L->getValueID(), R->getValueID())) 681 return Res; 682 683 if (const auto *SeqL = dyn_cast<ConstantDataSequential>(L)) { 684 const auto *SeqR = cast<ConstantDataSequential>(R); 685 // This handles ConstantDataArray and ConstantDataVector. Note that we 686 // compare the two raw data arrays, which might differ depending on the host 687 // endianness. This isn't a problem though, because the endiness of a module 688 // will affect the order of the constants, but this order is the same 689 // for a given input module and host platform. 690 return cmpMem(SeqL->getRawDataValues(), SeqR->getRawDataValues()); 691 } 692 693 switch (L->getValueID()) { 694 case Value::UndefValueVal: 695 case Value::ConstantTokenNoneVal: 696 return TypesRes; 697 case Value::ConstantIntVal: { 698 const APInt &LInt = cast<ConstantInt>(L)->getValue(); 699 const APInt &RInt = cast<ConstantInt>(R)->getValue(); 700 return cmpAPInts(LInt, RInt); 701 } 702 case Value::ConstantFPVal: { 703 const APFloat &LAPF = cast<ConstantFP>(L)->getValueAPF(); 704 const APFloat &RAPF = cast<ConstantFP>(R)->getValueAPF(); 705 return cmpAPFloats(LAPF, RAPF); 706 } 707 case Value::ConstantArrayVal: { 708 const ConstantArray *LA = cast<ConstantArray>(L); 709 const ConstantArray *RA = cast<ConstantArray>(R); 710 uint64_t NumElementsL = cast<ArrayType>(TyL)->getNumElements(); 711 uint64_t NumElementsR = cast<ArrayType>(TyR)->getNumElements(); 712 if (int Res = cmpNumbers(NumElementsL, NumElementsR)) 713 return Res; 714 for (uint64_t i = 0; i < NumElementsL; ++i) { 715 if (int Res = cmpConstants(cast<Constant>(LA->getOperand(i)), 716 cast<Constant>(RA->getOperand(i)))) 717 return Res; 718 } 719 return 0; 720 } 721 case Value::ConstantStructVal: { 722 const ConstantStruct *LS = cast<ConstantStruct>(L); 723 const ConstantStruct *RS = cast<ConstantStruct>(R); 724 unsigned NumElementsL = cast<StructType>(TyL)->getNumElements(); 725 unsigned NumElementsR = cast<StructType>(TyR)->getNumElements(); 726 if (int Res = cmpNumbers(NumElementsL, NumElementsR)) 727 return Res; 728 for (unsigned i = 0; i != NumElementsL; ++i) { 729 if (int Res = cmpConstants(cast<Constant>(LS->getOperand(i)), 730 cast<Constant>(RS->getOperand(i)))) 731 return Res; 732 } 733 return 0; 734 } 735 case Value::ConstantVectorVal: { 736 const ConstantVector *LV = cast<ConstantVector>(L); 737 const ConstantVector *RV = cast<ConstantVector>(R); 738 unsigned NumElementsL = cast<VectorType>(TyL)->getNumElements(); 739 unsigned NumElementsR = cast<VectorType>(TyR)->getNumElements(); 740 if (int Res = cmpNumbers(NumElementsL, NumElementsR)) 741 return Res; 742 for (uint64_t i = 0; i < NumElementsL; ++i) { 743 if (int Res = cmpConstants(cast<Constant>(LV->getOperand(i)), 744 cast<Constant>(RV->getOperand(i)))) 745 return Res; 746 } 747 return 0; 748 } 749 case Value::ConstantExprVal: { 750 const ConstantExpr *LE = cast<ConstantExpr>(L); 751 const ConstantExpr *RE = cast<ConstantExpr>(R); 752 unsigned NumOperandsL = LE->getNumOperands(); 753 unsigned NumOperandsR = RE->getNumOperands(); 754 if (int Res = cmpNumbers(NumOperandsL, NumOperandsR)) 755 return Res; 756 for (unsigned i = 0; i < NumOperandsL; ++i) { 757 if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)), 758 cast<Constant>(RE->getOperand(i)))) 759 return Res; 760 } 761 return 0; 762 } 763 case Value::BlockAddressVal: { 764 const BlockAddress *LBA = cast<BlockAddress>(L); 765 const BlockAddress *RBA = cast<BlockAddress>(R); 766 if (int Res = cmpValues(LBA->getFunction(), RBA->getFunction())) 767 return Res; 768 if (LBA->getFunction() == RBA->getFunction()) { 769 // They are BBs in the same function. Order by which comes first in the 770 // BB order of the function. This order is deterministic. 771 Function* F = LBA->getFunction(); 772 BasicBlock *LBB = LBA->getBasicBlock(); 773 BasicBlock *RBB = RBA->getBasicBlock(); 774 if (LBB == RBB) 775 return 0; 776 for(BasicBlock &BB : F->getBasicBlockList()) { 777 if (&BB == LBB) { 778 assert(&BB != RBB); 779 return -1; 780 } 781 if (&BB == RBB) 782 return 1; 783 } 784 llvm_unreachable("Basic Block Address does not point to a basic block in " 785 "its function."); 786 return -1; 787 } else { 788 // cmpValues said the functions are the same. So because they aren't 789 // literally the same pointer, they must respectively be the left and 790 // right functions. 791 assert(LBA->getFunction() == FnL && RBA->getFunction() == FnR); 792 // cmpValues will tell us if these are equivalent BasicBlocks, in the 793 // context of their respective functions. 794 return cmpValues(LBA->getBasicBlock(), RBA->getBasicBlock()); 795 } 796 } 797 default: // Unknown constant, abort. 798 DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n"); 799 llvm_unreachable("Constant ValueID not recognized."); 800 return -1; 801 } 802 } 803 804 int FunctionComparator::cmpGlobalValues(GlobalValue *L, GlobalValue *R) const { 805 return cmpNumbers(GlobalNumbers->getNumber(L), GlobalNumbers->getNumber(R)); 806 } 807 808 /// cmpType - compares two types, 809 /// defines total ordering among the types set. 810 /// See method declaration comments for more details. 811 int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const { 812 PointerType *PTyL = dyn_cast<PointerType>(TyL); 813 PointerType *PTyR = dyn_cast<PointerType>(TyR); 814 815 const DataLayout &DL = FnL->getParent()->getDataLayout(); 816 if (PTyL && PTyL->getAddressSpace() == 0) 817 TyL = DL.getIntPtrType(TyL); 818 if (PTyR && PTyR->getAddressSpace() == 0) 819 TyR = DL.getIntPtrType(TyR); 820 821 if (TyL == TyR) 822 return 0; 823 824 if (int Res = cmpNumbers(TyL->getTypeID(), TyR->getTypeID())) 825 return Res; 826 827 switch (TyL->getTypeID()) { 828 default: 829 llvm_unreachable("Unknown type!"); 830 // Fall through in Release mode. 831 case Type::IntegerTyID: 832 return cmpNumbers(cast<IntegerType>(TyL)->getBitWidth(), 833 cast<IntegerType>(TyR)->getBitWidth()); 834 case Type::VectorTyID: { 835 VectorType *VTyL = cast<VectorType>(TyL), *VTyR = cast<VectorType>(TyR); 836 if (int Res = cmpNumbers(VTyL->getNumElements(), VTyR->getNumElements())) 837 return Res; 838 return cmpTypes(VTyL->getElementType(), VTyR->getElementType()); 839 } 840 // TyL == TyR would have returned true earlier, because types are uniqued. 841 case Type::VoidTyID: 842 case Type::FloatTyID: 843 case Type::DoubleTyID: 844 case Type::X86_FP80TyID: 845 case Type::FP128TyID: 846 case Type::PPC_FP128TyID: 847 case Type::LabelTyID: 848 case Type::MetadataTyID: 849 case Type::TokenTyID: 850 return 0; 851 852 case Type::PointerTyID: { 853 assert(PTyL && PTyR && "Both types must be pointers here."); 854 return cmpNumbers(PTyL->getAddressSpace(), PTyR->getAddressSpace()); 855 } 856 857 case Type::StructTyID: { 858 StructType *STyL = cast<StructType>(TyL); 859 StructType *STyR = cast<StructType>(TyR); 860 if (STyL->getNumElements() != STyR->getNumElements()) 861 return cmpNumbers(STyL->getNumElements(), STyR->getNumElements()); 862 863 if (STyL->isPacked() != STyR->isPacked()) 864 return cmpNumbers(STyL->isPacked(), STyR->isPacked()); 865 866 for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) { 867 if (int Res = cmpTypes(STyL->getElementType(i), STyR->getElementType(i))) 868 return Res; 869 } 870 return 0; 871 } 872 873 case Type::FunctionTyID: { 874 FunctionType *FTyL = cast<FunctionType>(TyL); 875 FunctionType *FTyR = cast<FunctionType>(TyR); 876 if (FTyL->getNumParams() != FTyR->getNumParams()) 877 return cmpNumbers(FTyL->getNumParams(), FTyR->getNumParams()); 878 879 if (FTyL->isVarArg() != FTyR->isVarArg()) 880 return cmpNumbers(FTyL->isVarArg(), FTyR->isVarArg()); 881 882 if (int Res = cmpTypes(FTyL->getReturnType(), FTyR->getReturnType())) 883 return Res; 884 885 for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) { 886 if (int Res = cmpTypes(FTyL->getParamType(i), FTyR->getParamType(i))) 887 return Res; 888 } 889 return 0; 890 } 891 892 case Type::ArrayTyID: { 893 ArrayType *ATyL = cast<ArrayType>(TyL); 894 ArrayType *ATyR = cast<ArrayType>(TyR); 895 if (ATyL->getNumElements() != ATyR->getNumElements()) 896 return cmpNumbers(ATyL->getNumElements(), ATyR->getNumElements()); 897 return cmpTypes(ATyL->getElementType(), ATyR->getElementType()); 898 } 899 } 900 } 901 902 // Determine whether the two operations are the same except that pointer-to-A 903 // and pointer-to-B are equivalent. This should be kept in sync with 904 // Instruction::isSameOperationAs. 905 // Read method declaration comments for more details. 906 int FunctionComparator::cmpOperations(const Instruction *L, 907 const Instruction *R) const { 908 // Differences from Instruction::isSameOperationAs: 909 // * replace type comparison with calls to cmpTypes. 910 // * we test for I->getRawSubclassOptionalData (nuw/nsw/tail) at the top. 911 // * because of the above, we don't test for the tail bit on calls later on. 912 if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode())) 913 return Res; 914 915 if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands())) 916 return Res; 917 918 if (int Res = cmpTypes(L->getType(), R->getType())) 919 return Res; 920 921 if (int Res = cmpNumbers(L->getRawSubclassOptionalData(), 922 R->getRawSubclassOptionalData())) 923 return Res; 924 925 // We have two instructions of identical opcode and #operands. Check to see 926 // if all operands are the same type 927 for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) { 928 if (int Res = 929 cmpTypes(L->getOperand(i)->getType(), R->getOperand(i)->getType())) 930 return Res; 931 } 932 933 // Check special state that is a part of some instructions. 934 if (const AllocaInst *AI = dyn_cast<AllocaInst>(L)) { 935 if (int Res = cmpTypes(AI->getAllocatedType(), 936 cast<AllocaInst>(R)->getAllocatedType())) 937 return Res; 938 return cmpNumbers(AI->getAlignment(), cast<AllocaInst>(R)->getAlignment()); 939 } 940 if (const LoadInst *LI = dyn_cast<LoadInst>(L)) { 941 if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile())) 942 return Res; 943 if (int Res = 944 cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment())) 945 return Res; 946 if (int Res = 947 cmpOrderings(LI->getOrdering(), cast<LoadInst>(R)->getOrdering())) 948 return Res; 949 if (int Res = 950 cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope())) 951 return Res; 952 return cmpRangeMetadata(LI->getMetadata(LLVMContext::MD_range), 953 cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range)); 954 } 955 if (const StoreInst *SI = dyn_cast<StoreInst>(L)) { 956 if (int Res = 957 cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile())) 958 return Res; 959 if (int Res = 960 cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment())) 961 return Res; 962 if (int Res = 963 cmpOrderings(SI->getOrdering(), cast<StoreInst>(R)->getOrdering())) 964 return Res; 965 return cmpNumbers(SI->getSynchScope(), cast<StoreInst>(R)->getSynchScope()); 966 } 967 if (const CmpInst *CI = dyn_cast<CmpInst>(L)) 968 return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate()); 969 if (const CallInst *CI = dyn_cast<CallInst>(L)) { 970 if (int Res = cmpNumbers(CI->getCallingConv(), 971 cast<CallInst>(R)->getCallingConv())) 972 return Res; 973 if (int Res = 974 cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes())) 975 return Res; 976 if (int Res = cmpOperandBundlesSchema(CI, R)) 977 return Res; 978 return cmpRangeMetadata( 979 CI->getMetadata(LLVMContext::MD_range), 980 cast<CallInst>(R)->getMetadata(LLVMContext::MD_range)); 981 } 982 if (const InvokeInst *II = dyn_cast<InvokeInst>(L)) { 983 if (int Res = cmpNumbers(II->getCallingConv(), 984 cast<InvokeInst>(R)->getCallingConv())) 985 return Res; 986 if (int Res = 987 cmpAttrs(II->getAttributes(), cast<InvokeInst>(R)->getAttributes())) 988 return Res; 989 if (int Res = cmpOperandBundlesSchema(II, R)) 990 return Res; 991 return cmpRangeMetadata( 992 II->getMetadata(LLVMContext::MD_range), 993 cast<InvokeInst>(R)->getMetadata(LLVMContext::MD_range)); 994 } 995 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) { 996 ArrayRef<unsigned> LIndices = IVI->getIndices(); 997 ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices(); 998 if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) 999 return Res; 1000 for (size_t i = 0, e = LIndices.size(); i != e; ++i) { 1001 if (int Res = cmpNumbers(LIndices[i], RIndices[i])) 1002 return Res; 1003 } 1004 return 0; 1005 } 1006 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) { 1007 ArrayRef<unsigned> LIndices = EVI->getIndices(); 1008 ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices(); 1009 if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) 1010 return Res; 1011 for (size_t i = 0, e = LIndices.size(); i != e; ++i) { 1012 if (int Res = cmpNumbers(LIndices[i], RIndices[i])) 1013 return Res; 1014 } 1015 } 1016 if (const FenceInst *FI = dyn_cast<FenceInst>(L)) { 1017 if (int Res = 1018 cmpOrderings(FI->getOrdering(), cast<FenceInst>(R)->getOrdering())) 1019 return Res; 1020 return cmpNumbers(FI->getSynchScope(), cast<FenceInst>(R)->getSynchScope()); 1021 } 1022 if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(L)) { 1023 if (int Res = cmpNumbers(CXI->isVolatile(), 1024 cast<AtomicCmpXchgInst>(R)->isVolatile())) 1025 return Res; 1026 if (int Res = cmpNumbers(CXI->isWeak(), 1027 cast<AtomicCmpXchgInst>(R)->isWeak())) 1028 return Res; 1029 if (int Res = 1030 cmpOrderings(CXI->getSuccessOrdering(), 1031 cast<AtomicCmpXchgInst>(R)->getSuccessOrdering())) 1032 return Res; 1033 if (int Res = 1034 cmpOrderings(CXI->getFailureOrdering(), 1035 cast<AtomicCmpXchgInst>(R)->getFailureOrdering())) 1036 return Res; 1037 return cmpNumbers(CXI->getSynchScope(), 1038 cast<AtomicCmpXchgInst>(R)->getSynchScope()); 1039 } 1040 if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(L)) { 1041 if (int Res = cmpNumbers(RMWI->getOperation(), 1042 cast<AtomicRMWInst>(R)->getOperation())) 1043 return Res; 1044 if (int Res = cmpNumbers(RMWI->isVolatile(), 1045 cast<AtomicRMWInst>(R)->isVolatile())) 1046 return Res; 1047 if (int Res = cmpOrderings(RMWI->getOrdering(), 1048 cast<AtomicRMWInst>(R)->getOrdering())) 1049 return Res; 1050 return cmpNumbers(RMWI->getSynchScope(), 1051 cast<AtomicRMWInst>(R)->getSynchScope()); 1052 } 1053 if (const PHINode *PNL = dyn_cast<PHINode>(L)) { 1054 const PHINode *PNR = cast<PHINode>(R); 1055 // Ensure that in addition to the incoming values being identical 1056 // (checked by the caller of this function), the incoming blocks 1057 // are also identical. 1058 for (unsigned i = 0, e = PNL->getNumIncomingValues(); i != e; ++i) { 1059 if (int Res = 1060 cmpValues(PNL->getIncomingBlock(i), PNR->getIncomingBlock(i))) 1061 return Res; 1062 } 1063 } 1064 return 0; 1065 } 1066 1067 // Determine whether two GEP operations perform the same underlying arithmetic. 1068 // Read method declaration comments for more details. 1069 int FunctionComparator::cmpGEPs(const GEPOperator *GEPL, 1070 const GEPOperator *GEPR) const { 1071 1072 unsigned int ASL = GEPL->getPointerAddressSpace(); 1073 unsigned int ASR = GEPR->getPointerAddressSpace(); 1074 1075 if (int Res = cmpNumbers(ASL, ASR)) 1076 return Res; 1077 1078 // When we have target data, we can reduce the GEP down to the value in bytes 1079 // added to the address. 1080 const DataLayout &DL = FnL->getParent()->getDataLayout(); 1081 unsigned BitWidth = DL.getPointerSizeInBits(ASL); 1082 APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0); 1083 if (GEPL->accumulateConstantOffset(DL, OffsetL) && 1084 GEPR->accumulateConstantOffset(DL, OffsetR)) 1085 return cmpAPInts(OffsetL, OffsetR); 1086 if (int Res = cmpTypes(GEPL->getSourceElementType(), 1087 GEPR->getSourceElementType())) 1088 return Res; 1089 1090 if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands())) 1091 return Res; 1092 1093 for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) { 1094 if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i))) 1095 return Res; 1096 } 1097 1098 return 0; 1099 } 1100 1101 int FunctionComparator::cmpInlineAsm(const InlineAsm *L, 1102 const InlineAsm *R) const { 1103 // InlineAsm's are uniqued. If they are the same pointer, obviously they are 1104 // the same, otherwise compare the fields. 1105 if (L == R) 1106 return 0; 1107 if (int Res = cmpTypes(L->getFunctionType(), R->getFunctionType())) 1108 return Res; 1109 if (int Res = cmpMem(L->getAsmString(), R->getAsmString())) 1110 return Res; 1111 if (int Res = cmpMem(L->getConstraintString(), R->getConstraintString())) 1112 return Res; 1113 if (int Res = cmpNumbers(L->hasSideEffects(), R->hasSideEffects())) 1114 return Res; 1115 if (int Res = cmpNumbers(L->isAlignStack(), R->isAlignStack())) 1116 return Res; 1117 if (int Res = cmpNumbers(L->getDialect(), R->getDialect())) 1118 return Res; 1119 llvm_unreachable("InlineAsm blocks were not uniqued."); 1120 return 0; 1121 } 1122 1123 /// Compare two values used by the two functions under pair-wise comparison. If 1124 /// this is the first time the values are seen, they're added to the mapping so 1125 /// that we will detect mismatches on next use. 1126 /// See comments in declaration for more details. 1127 int FunctionComparator::cmpValues(const Value *L, const Value *R) const { 1128 // Catch self-reference case. 1129 if (L == FnL) { 1130 if (R == FnR) 1131 return 0; 1132 return -1; 1133 } 1134 if (R == FnR) { 1135 if (L == FnL) 1136 return 0; 1137 return 1; 1138 } 1139 1140 const Constant *ConstL = dyn_cast<Constant>(L); 1141 const Constant *ConstR = dyn_cast<Constant>(R); 1142 if (ConstL && ConstR) { 1143 if (L == R) 1144 return 0; 1145 return cmpConstants(ConstL, ConstR); 1146 } 1147 1148 if (ConstL) 1149 return 1; 1150 if (ConstR) 1151 return -1; 1152 1153 const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L); 1154 const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R); 1155 1156 if (InlineAsmL && InlineAsmR) 1157 return cmpInlineAsm(InlineAsmL, InlineAsmR); 1158 if (InlineAsmL) 1159 return 1; 1160 if (InlineAsmR) 1161 return -1; 1162 1163 auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())), 1164 RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size())); 1165 1166 return cmpNumbers(LeftSN.first->second, RightSN.first->second); 1167 } 1168 // Test whether two basic blocks have equivalent behaviour. 1169 int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL, 1170 const BasicBlock *BBR) const { 1171 BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end(); 1172 BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end(); 1173 1174 do { 1175 if (int Res = cmpValues(&*InstL, &*InstR)) 1176 return Res; 1177 1178 const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(InstL); 1179 const GetElementPtrInst *GEPR = dyn_cast<GetElementPtrInst>(InstR); 1180 1181 if (GEPL && !GEPR) 1182 return 1; 1183 if (GEPR && !GEPL) 1184 return -1; 1185 1186 if (GEPL && GEPR) { 1187 if (int Res = 1188 cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand())) 1189 return Res; 1190 if (int Res = cmpGEPs(GEPL, GEPR)) 1191 return Res; 1192 } else { 1193 if (int Res = cmpOperations(&*InstL, &*InstR)) 1194 return Res; 1195 assert(InstL->getNumOperands() == InstR->getNumOperands()); 1196 1197 for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) { 1198 Value *OpL = InstL->getOperand(i); 1199 Value *OpR = InstR->getOperand(i); 1200 if (int Res = cmpValues(OpL, OpR)) 1201 return Res; 1202 // cmpValues should ensure this is true. 1203 assert(cmpTypes(OpL->getType(), OpR->getType()) == 0); 1204 } 1205 } 1206 1207 ++InstL; 1208 ++InstR; 1209 } while (InstL != InstLE && InstR != InstRE); 1210 1211 if (InstL != InstLE && InstR == InstRE) 1212 return 1; 1213 if (InstL == InstLE && InstR != InstRE) 1214 return -1; 1215 return 0; 1216 } 1217 1218 // Test whether the two functions have equivalent behaviour. 1219 int FunctionComparator::compare() { 1220 sn_mapL.clear(); 1221 sn_mapR.clear(); 1222 1223 if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes())) 1224 return Res; 1225 1226 if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC())) 1227 return Res; 1228 1229 if (FnL->hasGC()) { 1230 if (int Res = cmpMem(FnL->getGC(), FnR->getGC())) 1231 return Res; 1232 } 1233 1234 if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection())) 1235 return Res; 1236 1237 if (FnL->hasSection()) { 1238 if (int Res = cmpMem(FnL->getSection(), FnR->getSection())) 1239 return Res; 1240 } 1241 1242 if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg())) 1243 return Res; 1244 1245 // TODO: if it's internal and only used in direct calls, we could handle this 1246 // case too. 1247 if (int Res = cmpNumbers(FnL->getCallingConv(), FnR->getCallingConv())) 1248 return Res; 1249 1250 if (int Res = cmpTypes(FnL->getFunctionType(), FnR->getFunctionType())) 1251 return Res; 1252 1253 assert(FnL->arg_size() == FnR->arg_size() && 1254 "Identically typed functions have different numbers of args!"); 1255 1256 // Visit the arguments so that they get enumerated in the order they're 1257 // passed in. 1258 for (Function::const_arg_iterator ArgLI = FnL->arg_begin(), 1259 ArgRI = FnR->arg_begin(), 1260 ArgLE = FnL->arg_end(); 1261 ArgLI != ArgLE; ++ArgLI, ++ArgRI) { 1262 if (cmpValues(&*ArgLI, &*ArgRI) != 0) 1263 llvm_unreachable("Arguments repeat!"); 1264 } 1265 1266 // We do a CFG-ordered walk since the actual ordering of the blocks in the 1267 // linked list is immaterial. Our walk starts at the entry block for both 1268 // functions, then takes each block from each terminator in order. As an 1269 // artifact, this also means that unreachable blocks are ignored. 1270 SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs; 1271 SmallPtrSet<const BasicBlock *, 32> VisitedBBs; // in terms of F1. 1272 1273 FnLBBs.push_back(&FnL->getEntryBlock()); 1274 FnRBBs.push_back(&FnR->getEntryBlock()); 1275 1276 VisitedBBs.insert(FnLBBs[0]); 1277 while (!FnLBBs.empty()) { 1278 const BasicBlock *BBL = FnLBBs.pop_back_val(); 1279 const BasicBlock *BBR = FnRBBs.pop_back_val(); 1280 1281 if (int Res = cmpValues(BBL, BBR)) 1282 return Res; 1283 1284 if (int Res = cmpBasicBlocks(BBL, BBR)) 1285 return Res; 1286 1287 const TerminatorInst *TermL = BBL->getTerminator(); 1288 const TerminatorInst *TermR = BBR->getTerminator(); 1289 1290 assert(TermL->getNumSuccessors() == TermR->getNumSuccessors()); 1291 for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) { 1292 if (!VisitedBBs.insert(TermL->getSuccessor(i)).second) 1293 continue; 1294 1295 FnLBBs.push_back(TermL->getSuccessor(i)); 1296 FnRBBs.push_back(TermR->getSuccessor(i)); 1297 } 1298 } 1299 return 0; 1300 } 1301 1302 namespace { 1303 // Accumulate the hash of a sequence of 64-bit integers. This is similar to a 1304 // hash of a sequence of 64bit ints, but the entire input does not need to be 1305 // available at once. This interface is necessary for functionHash because it 1306 // needs to accumulate the hash as the structure of the function is traversed 1307 // without saving these values to an intermediate buffer. This form of hashing 1308 // is not often needed, as usually the object to hash is just read from a 1309 // buffer. 1310 class HashAccumulator64 { 1311 uint64_t Hash; 1312 public: 1313 // Initialize to random constant, so the state isn't zero. 1314 HashAccumulator64() { Hash = 0x6acaa36bef8325c5ULL; } 1315 void add(uint64_t V) { 1316 Hash = llvm::hashing::detail::hash_16_bytes(Hash, V); 1317 } 1318 // No finishing is required, because the entire hash value is used. 1319 uint64_t getHash() { return Hash; } 1320 }; 1321 } // end anonymous namespace 1322 1323 // A function hash is calculated by considering only the number of arguments and 1324 // whether a function is varargs, the order of basic blocks (given by the 1325 // successors of each basic block in depth first order), and the order of 1326 // opcodes of each instruction within each of these basic blocks. This mirrors 1327 // the strategy compare() uses to compare functions by walking the BBs in depth 1328 // first order and comparing each instruction in sequence. Because this hash 1329 // does not look at the operands, it is insensitive to things such as the 1330 // target of calls and the constants used in the function, which makes it useful 1331 // when possibly merging functions which are the same modulo constants and call 1332 // targets. 1333 FunctionComparator::FunctionHash FunctionComparator::functionHash(Function &F) { 1334 HashAccumulator64 H; 1335 H.add(F.isVarArg()); 1336 H.add(F.arg_size()); 1337 1338 SmallVector<const BasicBlock *, 8> BBs; 1339 SmallSet<const BasicBlock *, 16> VisitedBBs; 1340 1341 // Walk the blocks in the same order as FunctionComparator::cmpBasicBlocks(), 1342 // accumulating the hash of the function "structure." (BB and opcode sequence) 1343 BBs.push_back(&F.getEntryBlock()); 1344 VisitedBBs.insert(BBs[0]); 1345 while (!BBs.empty()) { 1346 const BasicBlock *BB = BBs.pop_back_val(); 1347 // This random value acts as a block header, as otherwise the partition of 1348 // opcodes into BBs wouldn't affect the hash, only the order of the opcodes 1349 H.add(45798); 1350 for (auto &Inst : *BB) { 1351 H.add(Inst.getOpcode()); 1352 } 1353 const TerminatorInst *Term = BB->getTerminator(); 1354 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 1355 if (!VisitedBBs.insert(Term->getSuccessor(i)).second) 1356 continue; 1357 BBs.push_back(Term->getSuccessor(i)); 1358 } 1359 } 1360 return H.getHash(); 1361 } 1362 1363 1364 namespace { 1365 1366 /// MergeFunctions finds functions which will generate identical machine code, 1367 /// by considering all pointer types to be equivalent. Once identified, 1368 /// MergeFunctions will fold them by replacing a call to one to a call to a 1369 /// bitcast of the other. 1370 /// 1371 class MergeFunctions : public ModulePass { 1372 public: 1373 static char ID; 1374 MergeFunctions() 1375 : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)), FNodesInTree(), 1376 HasGlobalAliases(false) { 1377 initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); 1378 } 1379 1380 bool runOnModule(Module &M) override; 1381 1382 private: 1383 // The function comparison operator is provided here so that FunctionNodes do 1384 // not need to become larger with another pointer. 1385 class FunctionNodeCmp { 1386 GlobalNumberState* GlobalNumbers; 1387 public: 1388 FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {} 1389 bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const { 1390 // Order first by hashes, then full function comparison. 1391 if (LHS.getHash() != RHS.getHash()) 1392 return LHS.getHash() < RHS.getHash(); 1393 FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers); 1394 return FCmp.compare() == -1; 1395 } 1396 }; 1397 typedef std::set<FunctionNode, FunctionNodeCmp> FnTreeType; 1398 1399 GlobalNumberState GlobalNumbers; 1400 1401 /// A work queue of functions that may have been modified and should be 1402 /// analyzed again. 1403 std::vector<WeakVH> Deferred; 1404 1405 /// Checks the rules of order relation introduced among functions set. 1406 /// Returns true, if sanity check has been passed, and false if failed. 1407 bool doSanityCheck(std::vector<WeakVH> &Worklist); 1408 1409 /// Insert a ComparableFunction into the FnTree, or merge it away if it's 1410 /// equal to one that's already present. 1411 bool insert(Function *NewFunction); 1412 1413 /// Remove a Function from the FnTree and queue it up for a second sweep of 1414 /// analysis. 1415 void remove(Function *F); 1416 1417 /// Find the functions that use this Value and remove them from FnTree and 1418 /// queue the functions. 1419 void removeUsers(Value *V); 1420 1421 /// Replace all direct calls of Old with calls of New. Will bitcast New if 1422 /// necessary to make types match. 1423 void replaceDirectCallers(Function *Old, Function *New); 1424 1425 /// Merge two equivalent functions. Upon completion, G may be deleted, or may 1426 /// be converted into a thunk. In either case, it should never be visited 1427 /// again. 1428 void mergeTwoFunctions(Function *F, Function *G); 1429 1430 /// Replace G with a thunk or an alias to F. Deletes G. 1431 void writeThunkOrAlias(Function *F, Function *G); 1432 1433 /// Replace G with a simple tail call to bitcast(F). Also replace direct uses 1434 /// of G with bitcast(F). Deletes G. 1435 void writeThunk(Function *F, Function *G); 1436 1437 /// Replace G with an alias to F. Deletes G. 1438 void writeAlias(Function *F, Function *G); 1439 1440 /// Replace function F with function G in the function tree. 1441 void replaceFunctionInTree(const FunctionNode &FN, Function *G); 1442 1443 /// The set of all distinct functions. Use the insert() and remove() methods 1444 /// to modify it. The map allows efficient lookup and deferring of Functions. 1445 FnTreeType FnTree; 1446 // Map functions to the iterators of the FunctionNode which contains them 1447 // in the FnTree. This must be updated carefully whenever the FnTree is 1448 // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid 1449 // dangling iterators into FnTree. The invariant that preserves this is that 1450 // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree. 1451 ValueMap<Function*, FnTreeType::iterator> FNodesInTree; 1452 1453 /// Whether or not the target supports global aliases. 1454 bool HasGlobalAliases; 1455 }; 1456 1457 } // end anonymous namespace 1458 1459 char MergeFunctions::ID = 0; 1460 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false) 1461 1462 ModulePass *llvm::createMergeFunctionsPass() { 1463 return new MergeFunctions(); 1464 } 1465 1466 bool MergeFunctions::doSanityCheck(std::vector<WeakVH> &Worklist) { 1467 if (const unsigned Max = NumFunctionsForSanityCheck) { 1468 unsigned TripleNumber = 0; 1469 bool Valid = true; 1470 1471 dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n"; 1472 1473 unsigned i = 0; 1474 for (std::vector<WeakVH>::iterator I = Worklist.begin(), E = Worklist.end(); 1475 I != E && i < Max; ++I, ++i) { 1476 unsigned j = i; 1477 for (std::vector<WeakVH>::iterator J = I; J != E && j < Max; ++J, ++j) { 1478 Function *F1 = cast<Function>(*I); 1479 Function *F2 = cast<Function>(*J); 1480 int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare(); 1481 int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare(); 1482 1483 // If F1 <= F2, then F2 >= F1, otherwise report failure. 1484 if (Res1 != -Res2) { 1485 dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber 1486 << "\n"; 1487 F1->dump(); 1488 F2->dump(); 1489 Valid = false; 1490 } 1491 1492 if (Res1 == 0) 1493 continue; 1494 1495 unsigned k = j; 1496 for (std::vector<WeakVH>::iterator K = J; K != E && k < Max; 1497 ++k, ++K, ++TripleNumber) { 1498 if (K == J) 1499 continue; 1500 1501 Function *F3 = cast<Function>(*K); 1502 int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare(); 1503 int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare(); 1504 1505 bool Transitive = true; 1506 1507 if (Res1 != 0 && Res1 == Res4) { 1508 // F1 > F2, F2 > F3 => F1 > F3 1509 Transitive = Res3 == Res1; 1510 } else if (Res3 != 0 && Res3 == -Res4) { 1511 // F1 > F3, F3 > F2 => F1 > F2 1512 Transitive = Res3 == Res1; 1513 } else if (Res4 != 0 && -Res3 == Res4) { 1514 // F2 > F3, F3 > F1 => F2 > F1 1515 Transitive = Res4 == -Res1; 1516 } 1517 1518 if (!Transitive) { 1519 dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: " 1520 << TripleNumber << "\n"; 1521 dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", " 1522 << Res4 << "\n"; 1523 F1->dump(); 1524 F2->dump(); 1525 F3->dump(); 1526 Valid = false; 1527 } 1528 } 1529 } 1530 } 1531 1532 dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n"; 1533 return Valid; 1534 } 1535 return true; 1536 } 1537 1538 bool MergeFunctions::runOnModule(Module &M) { 1539 if (skipModule(M)) 1540 return false; 1541 1542 bool Changed = false; 1543 1544 // All functions in the module, ordered by hash. Functions with a unique 1545 // hash value are easily eliminated. 1546 std::vector<std::pair<FunctionComparator::FunctionHash, Function *>> 1547 HashedFuncs; 1548 for (Function &Func : M) { 1549 if (!Func.isDeclaration() && !Func.hasAvailableExternallyLinkage()) { 1550 HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func}); 1551 } 1552 } 1553 1554 std::stable_sort( 1555 HashedFuncs.begin(), HashedFuncs.end(), 1556 [](const std::pair<FunctionComparator::FunctionHash, Function *> &a, 1557 const std::pair<FunctionComparator::FunctionHash, Function *> &b) { 1558 return a.first < b.first; 1559 }); 1560 1561 auto S = HashedFuncs.begin(); 1562 for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) { 1563 // If the hash value matches the previous value or the next one, we must 1564 // consider merging it. Otherwise it is dropped and never considered again. 1565 if ((I != S && std::prev(I)->first == I->first) || 1566 (std::next(I) != IE && std::next(I)->first == I->first) ) { 1567 Deferred.push_back(WeakVH(I->second)); 1568 } 1569 } 1570 1571 do { 1572 std::vector<WeakVH> Worklist; 1573 Deferred.swap(Worklist); 1574 1575 DEBUG(doSanityCheck(Worklist)); 1576 1577 DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 1578 DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); 1579 1580 // Insert functions and merge them. 1581 for (WeakVH &I : Worklist) { 1582 if (!I) 1583 continue; 1584 Function *F = cast<Function>(I); 1585 if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) { 1586 Changed |= insert(F); 1587 } 1588 } 1589 DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n'); 1590 } while (!Deferred.empty()); 1591 1592 FnTree.clear(); 1593 GlobalNumbers.clear(); 1594 1595 return Changed; 1596 } 1597 1598 // Replace direct callers of Old with New. 1599 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { 1600 Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); 1601 for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) { 1602 Use *U = &*UI; 1603 ++UI; 1604 CallSite CS(U->getUser()); 1605 if (CS && CS.isCallee(U)) { 1606 // Transfer the called function's attributes to the call site. Due to the 1607 // bitcast we will 'lose' ABI changing attributes because the 'called 1608 // function' is no longer a Function* but the bitcast. Code that looks up 1609 // the attributes from the called function will fail. 1610 1611 // FIXME: This is not actually true, at least not anymore. The callsite 1612 // will always have the same ABI affecting attributes as the callee, 1613 // because otherwise the original input has UB. Note that Old and New 1614 // always have matching ABI, so no attributes need to be changed. 1615 // Transferring other attributes may help other optimizations, but that 1616 // should be done uniformly and not in this ad-hoc way. 1617 auto &Context = New->getContext(); 1618 auto NewFuncAttrs = New->getAttributes(); 1619 auto CallSiteAttrs = CS.getAttributes(); 1620 1621 CallSiteAttrs = CallSiteAttrs.addAttributes( 1622 Context, AttributeSet::ReturnIndex, NewFuncAttrs.getRetAttributes()); 1623 1624 for (unsigned argIdx = 0; argIdx < CS.arg_size(); argIdx++) { 1625 AttributeSet Attrs = NewFuncAttrs.getParamAttributes(argIdx); 1626 if (Attrs.getNumSlots()) 1627 CallSiteAttrs = CallSiteAttrs.addAttributes(Context, argIdx, Attrs); 1628 } 1629 1630 CS.setAttributes(CallSiteAttrs); 1631 1632 remove(CS.getInstruction()->getParent()->getParent()); 1633 U->set(BitcastNew); 1634 } 1635 } 1636 } 1637 1638 // Replace G with an alias to F if possible, or else a thunk to F. Deletes G. 1639 void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { 1640 if (HasGlobalAliases && G->hasGlobalUnnamedAddr()) { 1641 if (G->hasExternalLinkage() || G->hasLocalLinkage() || 1642 G->hasWeakLinkage()) { 1643 writeAlias(F, G); 1644 return; 1645 } 1646 } 1647 1648 writeThunk(F, G); 1649 } 1650 1651 // Helper for writeThunk, 1652 // Selects proper bitcast operation, 1653 // but a bit simpler then CastInst::getCastOpcode. 1654 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) { 1655 Type *SrcTy = V->getType(); 1656 if (SrcTy->isStructTy()) { 1657 assert(DestTy->isStructTy()); 1658 assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements()); 1659 Value *Result = UndefValue::get(DestTy); 1660 for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) { 1661 Value *Element = createCast( 1662 Builder, Builder.CreateExtractValue(V, makeArrayRef(I)), 1663 DestTy->getStructElementType(I)); 1664 1665 Result = 1666 Builder.CreateInsertValue(Result, Element, makeArrayRef(I)); 1667 } 1668 return Result; 1669 } 1670 assert(!DestTy->isStructTy()); 1671 if (SrcTy->isIntegerTy() && DestTy->isPointerTy()) 1672 return Builder.CreateIntToPtr(V, DestTy); 1673 else if (SrcTy->isPointerTy() && DestTy->isIntegerTy()) 1674 return Builder.CreatePtrToInt(V, DestTy); 1675 else 1676 return Builder.CreateBitCast(V, DestTy); 1677 } 1678 1679 // Replace G with a simple tail call to bitcast(F). Also replace direct uses 1680 // of G with bitcast(F). Deletes G. 1681 void MergeFunctions::writeThunk(Function *F, Function *G) { 1682 if (!G->isInterposable()) { 1683 // Redirect direct callers of G to F. 1684 replaceDirectCallers(G, F); 1685 } 1686 1687 // If G was internal then we may have replaced all uses of G with F. If so, 1688 // stop here and delete G. There's no need for a thunk. 1689 if (G->hasLocalLinkage() && G->use_empty()) { 1690 G->eraseFromParent(); 1691 return; 1692 } 1693 1694 Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 1695 G->getParent()); 1696 BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 1697 IRBuilder<> Builder(BB); 1698 1699 SmallVector<Value *, 16> Args; 1700 unsigned i = 0; 1701 FunctionType *FFTy = F->getFunctionType(); 1702 for (Argument & AI : NewG->args()) { 1703 Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i))); 1704 ++i; 1705 } 1706 1707 CallInst *CI = Builder.CreateCall(F, Args); 1708 CI->setTailCall(); 1709 CI->setCallingConv(F->getCallingConv()); 1710 CI->setAttributes(F->getAttributes()); 1711 if (NewG->getReturnType()->isVoidTy()) { 1712 Builder.CreateRetVoid(); 1713 } else { 1714 Builder.CreateRet(createCast(Builder, CI, NewG->getReturnType())); 1715 } 1716 1717 NewG->copyAttributesFrom(G); 1718 NewG->takeName(G); 1719 removeUsers(G); 1720 G->replaceAllUsesWith(NewG); 1721 G->eraseFromParent(); 1722 1723 DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n'); 1724 ++NumThunksWritten; 1725 } 1726 1727 // Replace G with an alias to F and delete G. 1728 void MergeFunctions::writeAlias(Function *F, Function *G) { 1729 auto *GA = GlobalAlias::create(G->getLinkage(), "", F); 1730 F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 1731 GA->takeName(G); 1732 GA->setVisibility(G->getVisibility()); 1733 removeUsers(G); 1734 G->replaceAllUsesWith(GA); 1735 G->eraseFromParent(); 1736 1737 DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); 1738 ++NumAliasesWritten; 1739 } 1740 1741 // Merge two equivalent functions. Upon completion, Function G is deleted. 1742 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { 1743 if (F->isInterposable()) { 1744 assert(G->isInterposable()); 1745 1746 // Make them both thunks to the same internal function. 1747 Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 1748 F->getParent()); 1749 H->copyAttributesFrom(F); 1750 H->takeName(F); 1751 removeUsers(F); 1752 F->replaceAllUsesWith(H); 1753 1754 unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); 1755 1756 if (HasGlobalAliases) { 1757 writeAlias(F, G); 1758 writeAlias(F, H); 1759 } else { 1760 writeThunk(F, G); 1761 writeThunk(F, H); 1762 } 1763 1764 F->setAlignment(MaxAlignment); 1765 F->setLinkage(GlobalValue::PrivateLinkage); 1766 ++NumDoubleWeak; 1767 } else { 1768 writeThunkOrAlias(F, G); 1769 } 1770 1771 ++NumFunctionsMerged; 1772 } 1773 1774 /// Replace function F by function G. 1775 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN, 1776 Function *G) { 1777 Function *F = FN.getFunc(); 1778 assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 && 1779 "The two functions must be equal"); 1780 1781 auto I = FNodesInTree.find(F); 1782 assert(I != FNodesInTree.end() && "F should be in FNodesInTree"); 1783 assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G"); 1784 1785 FnTreeType::iterator IterToFNInFnTree = I->second; 1786 assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree."); 1787 // Remove F -> FN and insert G -> FN 1788 FNodesInTree.erase(I); 1789 FNodesInTree.insert({G, IterToFNInFnTree}); 1790 // Replace F with G in FN, which is stored inside the FnTree. 1791 FN.replaceBy(G); 1792 } 1793 1794 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one 1795 // that was already inserted. 1796 bool MergeFunctions::insert(Function *NewFunction) { 1797 std::pair<FnTreeType::iterator, bool> Result = 1798 FnTree.insert(FunctionNode(NewFunction)); 1799 1800 if (Result.second) { 1801 assert(FNodesInTree.count(NewFunction) == 0); 1802 FNodesInTree.insert({NewFunction, Result.first}); 1803 DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n'); 1804 return false; 1805 } 1806 1807 const FunctionNode &OldF = *Result.first; 1808 1809 // Don't merge tiny functions, since it can just end up making the function 1810 // larger. 1811 // FIXME: Should still merge them if they are unnamed_addr and produce an 1812 // alias. 1813 if (NewFunction->size() == 1) { 1814 if (NewFunction->front().size() <= 2) { 1815 DEBUG(dbgs() << NewFunction->getName() 1816 << " is to small to bother merging\n"); 1817 return false; 1818 } 1819 } 1820 1821 // Impose a total order (by name) on the replacement of functions. This is 1822 // important when operating on more than one module independently to prevent 1823 // cycles of thunks calling each other when the modules are linked together. 1824 // 1825 // First of all, we process strong functions before weak functions. 1826 if ((OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()) || 1827 (OldF.getFunc()->isInterposable() == NewFunction->isInterposable() && 1828 OldF.getFunc()->getName() > NewFunction->getName())) { 1829 // Swap the two functions. 1830 Function *F = OldF.getFunc(); 1831 replaceFunctionInTree(*Result.first, NewFunction); 1832 NewFunction = F; 1833 assert(OldF.getFunc() != F && "Must have swapped the functions."); 1834 } 1835 1836 DEBUG(dbgs() << " " << OldF.getFunc()->getName() 1837 << " == " << NewFunction->getName() << '\n'); 1838 1839 Function *DeleteF = NewFunction; 1840 mergeTwoFunctions(OldF.getFunc(), DeleteF); 1841 return true; 1842 } 1843 1844 // Remove a function from FnTree. If it was already in FnTree, add 1845 // it to Deferred so that we'll look at it in the next round. 1846 void MergeFunctions::remove(Function *F) { 1847 auto I = FNodesInTree.find(F); 1848 if (I != FNodesInTree.end()) { 1849 DEBUG(dbgs() << "Deferred " << F->getName()<< ".\n"); 1850 FnTree.erase(I->second); 1851 // I->second has been invalidated, remove it from the FNodesInTree map to 1852 // preserve the invariant. 1853 FNodesInTree.erase(I); 1854 Deferred.emplace_back(F); 1855 } 1856 } 1857 1858 // For each instruction used by the value, remove() the function that contains 1859 // the instruction. This should happen right before a call to RAUW. 1860 void MergeFunctions::removeUsers(Value *V) { 1861 std::vector<Value *> Worklist; 1862 Worklist.push_back(V); 1863 SmallSet<Value*, 8> Visited; 1864 Visited.insert(V); 1865 while (!Worklist.empty()) { 1866 Value *V = Worklist.back(); 1867 Worklist.pop_back(); 1868 1869 for (User *U : V->users()) { 1870 if (Instruction *I = dyn_cast<Instruction>(U)) { 1871 remove(I->getParent()->getParent()); 1872 } else if (isa<GlobalValue>(U)) { 1873 // do nothing 1874 } else if (Constant *C = dyn_cast<Constant>(U)) { 1875 for (User *UU : C->users()) { 1876 if (!Visited.insert(UU).second) 1877 Worklist.push_back(UU); 1878 } 1879 } 1880 } 1881 } 1882 } 1883