LLVM API Documentation

MergeFunctions.cpp
Go to the documentation of this file.
00001 //===- MergeFunctions.cpp - Merge identical functions ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass looks for equivalent functions that are mergable and folds them.
00011 //
00012 // Order relation is defined on set of functions. It was made through
00013 // special function comparison procedure that returns
00014 // 0 when functions are equal,
00015 // -1 when Left function is less than right function, and
00016 // 1 for opposite case. We need total-ordering, so we need to maintain
00017 // four properties on the functions set:
00018 // a <= a (reflexivity)
00019 // if a <= b and b <= a then a = b (antisymmetry)
00020 // if a <= b and b <= c then a <= c (transitivity).
00021 // for all a and b: a <= b or b <= a (totality).
00022 //
00023 // Comparison iterates through each instruction in each basic block.
00024 // Functions are kept on binary tree. For each new function F we perform
00025 // lookup in binary tree.
00026 // In practice it works the following way:
00027 // -- We define Function* container class with custom "operator<" (FunctionPtr).
00028 // -- "FunctionPtr" instances are stored in std::set collection, so every
00029 //    std::set::insert operation will give you result in log(N) time.
00030 //
00031 // When a match is found the functions are folded. If both functions are
00032 // overridable, we move the functionality into a new internal function and
00033 // leave two overridable thunks to it.
00034 //
00035 //===----------------------------------------------------------------------===//
00036 //
00037 // Future work:
00038 //
00039 // * virtual functions.
00040 //
00041 // Many functions have their address taken by the virtual function table for
00042 // the object they belong to. However, as long as it's only used for a lookup
00043 // and call, this is irrelevant, and we'd like to fold such functions.
00044 //
00045 // * be smarter about bitcasts.
00046 //
00047 // In order to fold functions, we will sometimes add either bitcast instructions
00048 // or bitcast constant expressions. Unfortunately, this can confound further
00049 // analysis since the two functions differ where one has a bitcast and the
00050 // other doesn't. We should learn to look through bitcasts.
00051 //
00052 // * Compare complex types with pointer types inside.
00053 // * Compare cross-reference cases.
00054 // * Compare complex expressions.
00055 //
00056 // All the three issues above could be described as ability to prove that
00057 // fA == fB == fC == fE == fF == fG in example below:
00058 //
00059 //  void fA() {
00060 //    fB();
00061 //  }
00062 //  void fB() {
00063 //    fA();
00064 //  }
00065 //
00066 //  void fE() {
00067 //    fF();
00068 //  }
00069 //  void fF() {
00070 //    fG();
00071 //  }
00072 //  void fG() {
00073 //    fE();
00074 //  }
00075 //
00076 // Simplest cross-reference case (fA <--> fB) was implemented in previous
00077 // versions of MergeFunctions, though it presented only in two function pairs
00078 // in test-suite (that counts >50k functions)
00079 // Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A)
00080 // could cover much more cases.
00081 //
00082 //===----------------------------------------------------------------------===//
00083 
00084 #include "llvm/Transforms/IPO.h"
00085 #include "llvm/ADT/DenseSet.h"
00086 #include "llvm/ADT/FoldingSet.h"
00087 #include "llvm/ADT/STLExtras.h"
00088 #include "llvm/ADT/SmallSet.h"
00089 #include "llvm/ADT/Statistic.h"
00090 #include "llvm/IR/CallSite.h"
00091 #include "llvm/IR/Constants.h"
00092 #include "llvm/IR/DataLayout.h"
00093 #include "llvm/IR/IRBuilder.h"
00094 #include "llvm/IR/InlineAsm.h"
00095 #include "llvm/IR/Instructions.h"
00096 #include "llvm/IR/LLVMContext.h"
00097 #include "llvm/IR/Module.h"
00098 #include "llvm/IR/Operator.h"
00099 #include "llvm/IR/ValueHandle.h"
00100 #include "llvm/Pass.h"
00101 #include "llvm/Support/CommandLine.h"
00102 #include "llvm/Support/Debug.h"
00103 #include "llvm/Support/ErrorHandling.h"
00104 #include "llvm/Support/raw_ostream.h"
00105 #include <vector>
00106 using namespace llvm;
00107 
00108 #define DEBUG_TYPE "mergefunc"
00109 
00110 STATISTIC(NumFunctionsMerged, "Number of functions merged");
00111 STATISTIC(NumThunksWritten, "Number of thunks generated");
00112 STATISTIC(NumAliasesWritten, "Number of aliases generated");
00113 STATISTIC(NumDoubleWeak, "Number of new functions created");
00114 
00115 static cl::opt<unsigned> NumFunctionsForSanityCheck(
00116     "mergefunc-sanity",
00117     cl::desc("How many functions in module could be used for "
00118              "MergeFunctions pass sanity check. "
00119              "'0' disables this check. Works only with '-debug' key."),
00120     cl::init(0), cl::Hidden);
00121 
00122 namespace {
00123 
00124 /// FunctionComparator - Compares two functions to determine whether or not
00125 /// they will generate machine code with the same behaviour. DataLayout is
00126 /// used if available. The comparator always fails conservatively (erring on the
00127 /// side of claiming that two functions are different).
00128 class FunctionComparator {
00129 public:
00130   FunctionComparator(const DataLayout *DL, const Function *F1,
00131                      const Function *F2)
00132       : FnL(F1), FnR(F2), DL(DL) {}
00133 
00134   /// Test whether the two functions have equivalent behaviour.
00135   int compare();
00136 
00137 private:
00138   /// Test whether two basic blocks have equivalent behaviour.
00139   int compare(const BasicBlock *BBL, const BasicBlock *BBR);
00140 
00141   /// Constants comparison.
00142   /// Its analog to lexicographical comparison between hypothetical numbers
00143   /// of next format:
00144   /// <bitcastability-trait><raw-bit-contents>
00145   ///
00146   /// 1. Bitcastability.
00147   /// Check whether L's type could be losslessly bitcasted to R's type.
00148   /// On this stage method, in case when lossless bitcast is not possible
00149   /// method returns -1 or 1, thus also defining which type is greater in
00150   /// context of bitcastability.
00151   /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight
00152   ///          to the contents comparison.
00153   ///          If types differ, remember types comparison result and check
00154   ///          whether we still can bitcast types.
00155   /// Stage 1: Types that satisfies isFirstClassType conditions are always
00156   ///          greater then others.
00157   /// Stage 2: Vector is greater then non-vector.
00158   ///          If both types are vectors, then vector with greater bitwidth is
00159   ///          greater.
00160   ///          If both types are vectors with the same bitwidth, then types
00161   ///          are bitcastable, and we can skip other stages, and go to contents
00162   ///          comparison.
00163   /// Stage 3: Pointer types are greater than non-pointers. If both types are
00164   ///          pointers of the same address space - go to contents comparison.
00165   ///          Different address spaces: pointer with greater address space is
00166   ///          greater.
00167   /// Stage 4: Types are neither vectors, nor pointers. And they differ.
00168   ///          We don't know how to bitcast them. So, we better don't do it,
00169   ///          and return types comparison result (so it determines the
00170   ///          relationship among constants we don't know how to bitcast).
00171   ///
00172   /// Just for clearance, let's see how the set of constants could look
00173   /// on single dimension axis:
00174   ///
00175   /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
00176   /// Where: NFCT - Not a FirstClassType
00177   ///        FCT - FirstClassTyp:
00178   ///
00179   /// 2. Compare raw contents.
00180   /// It ignores types on this stage and only compares bits from L and R.
00181   /// Returns 0, if L and R has equivalent contents.
00182   /// -1 or 1 if values are different.
00183   /// Pretty trivial:
00184   /// 2.1. If contents are numbers, compare numbers.
00185   ///    Ints with greater bitwidth are greater. Ints with same bitwidths
00186   ///    compared by their contents.
00187   /// 2.2. "And so on". Just to avoid discrepancies with comments
00188   /// perhaps it would be better to read the implementation itself.
00189   /// 3. And again about overall picture. Let's look back at how the ordered set
00190   /// of constants will look like:
00191   /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
00192   ///
00193   /// Now look, what could be inside [FCT, "others"], for example:
00194   /// [FCT, "others"] =
00195   /// [
00196   ///   [double 0.1], [double 1.23],
00197   ///   [i32 1], [i32 2],
00198   ///   { double 1.0 },       ; StructTyID, NumElements = 1
00199   ///   { i32 1 },            ; StructTyID, NumElements = 1
00200   ///   { double 1, i32 1 },  ; StructTyID, NumElements = 2
00201   ///   { i32 1, double 1 }   ; StructTyID, NumElements = 2
00202   /// ]
00203   ///
00204   /// Let's explain the order. Float numbers will be less than integers, just
00205   /// because of cmpType terms: FloatTyID < IntegerTyID.
00206   /// Floats (with same fltSemantics) are sorted according to their value.
00207   /// Then you can see integers, and they are, like a floats,
00208   /// could be easy sorted among each others.
00209   /// The structures. Structures are grouped at the tail, again because of their
00210   /// TypeID: StructTyID > IntegerTyID > FloatTyID.
00211   /// Structures with greater number of elements are greater. Structures with
00212   /// greater elements going first are greater.
00213   /// The same logic with vectors, arrays and other possible complex types.
00214   ///
00215   /// Bitcastable constants.
00216   /// Let's assume, that some constant, belongs to some group of
00217   /// "so-called-equal" values with different types, and at the same time
00218   /// belongs to another group of constants with equal types
00219   /// and "really" equal values.
00220   ///
00221   /// Now, prove that this is impossible:
00222   ///
00223   /// If constant A with type TyA is bitcastable to B with type TyB, then:
00224   /// 1. All constants with equal types to TyA, are bitcastable to B. Since
00225   ///    those should be vectors (if TyA is vector), pointers
00226   ///    (if TyA is pointer), or else (if TyA equal to TyB), those types should
00227   ///    be equal to TyB.
00228   /// 2. All constants with non-equal, but bitcastable types to TyA, are
00229   ///    bitcastable to B.
00230   ///    Once again, just because we allow it to vectors and pointers only.
00231   ///    This statement could be expanded as below:
00232   /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to
00233   ///      vector B, and thus bitcastable to B as well.
00234   /// 2.2. All pointers of the same address space, no matter what they point to,
00235   ///      bitcastable. So if C is pointer, it could be bitcasted to A and to B.
00236   /// So any constant equal or bitcastable to A is equal or bitcastable to B.
00237   /// QED.
00238   ///
00239   /// In another words, for pointers and vectors, we ignore top-level type and
00240   /// look at their particular properties (bit-width for vectors, and
00241   /// address space for pointers).
00242   /// If these properties are equal - compare their contents.
00243   int cmpConstants(const Constant *L, const Constant *R);
00244 
00245   /// Assign or look up previously assigned numbers for the two values, and
00246   /// return whether the numbers are equal. Numbers are assigned in the order
00247   /// visited.
00248   /// Comparison order:
00249   /// Stage 0: Value that is function itself is always greater then others.
00250   ///          If left and right values are references to their functions, then
00251   ///          they are equal.
00252   /// Stage 1: Constants are greater than non-constants.
00253   ///          If both left and right are constants, then the result of
00254   ///          cmpConstants is used as cmpValues result.
00255   /// Stage 2: InlineAsm instances are greater than others. If both left and
00256   ///          right are InlineAsm instances, InlineAsm* pointers casted to
00257   ///          integers and compared as numbers.
00258   /// Stage 3: For all other cases we compare order we meet these values in
00259   ///          their functions. If right value was met first during scanning,
00260   ///          then left value is greater.
00261   ///          In another words, we compare serial numbers, for more details
00262   ///          see comments for sn_mapL and sn_mapR.
00263   int cmpValues(const Value *L, const Value *R);
00264 
00265   /// Compare two Instructions for equivalence, similar to
00266   /// Instruction::isSameOperationAs but with modifications to the type
00267   /// comparison.
00268   /// Stages are listed in "most significant stage first" order:
00269   /// On each stage below, we do comparison between some left and right
00270   /// operation parts. If parts are non-equal, we assign parts comparison
00271   /// result to the operation comparison result and exit from method.
00272   /// Otherwise we proceed to the next stage.
00273   /// Stages:
00274   /// 1. Operations opcodes. Compared as numbers.
00275   /// 2. Number of operands.
00276   /// 3. Operation types. Compared with cmpType method.
00277   /// 4. Compare operation subclass optional data as stream of bytes:
00278   /// just convert it to integers and call cmpNumbers.
00279   /// 5. Compare in operation operand types with cmpType in
00280   /// most significant operand first order.
00281   /// 6. Last stage. Check operations for some specific attributes.
00282   /// For example, for Load it would be:
00283   /// 6.1.Load: volatile (as boolean flag)
00284   /// 6.2.Load: alignment (as integer numbers)
00285   /// 6.3.Load: synch-scope (as integer numbers)
00286   /// 6.4.Load: range metadata (as integer numbers)
00287   /// On this stage its better to see the code, since its not more than 10-15
00288   /// strings for particular instruction, and could change sometimes.
00289   int cmpOperations(const Instruction *L, const Instruction *R) const;
00290 
00291   /// Compare two GEPs for equivalent pointer arithmetic.
00292   /// Parts to be compared for each comparison stage,
00293   /// most significant stage first:
00294   /// 1. Address space. As numbers.
00295   /// 2. Constant offset, (if "DataLayout *DL" field is not NULL,
00296   /// using GEPOperator::accumulateConstantOffset method).
00297   /// 3. Pointer operand type (using cmpType method).
00298   /// 4. Number of operands.
00299   /// 5. Compare operands, using cmpValues method.
00300   int cmpGEPs(const GEPOperator *GEPL, const GEPOperator *GEPR);
00301   int cmpGEPs(const GetElementPtrInst *GEPL, const GetElementPtrInst *GEPR) {
00302     return cmpGEPs(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR));
00303   }
00304 
00305   /// cmpType - compares two types,
00306   /// defines total ordering among the types set.
00307   ///
00308   /// Return values:
00309   /// 0 if types are equal,
00310   /// -1 if Left is less than Right,
00311   /// +1 if Left is greater than Right.
00312   ///
00313   /// Description:
00314   /// Comparison is broken onto stages. Like in lexicographical comparison
00315   /// stage coming first has higher priority.
00316   /// On each explanation stage keep in mind total ordering properties.
00317   ///
00318   /// 0. Before comparison we coerce pointer types of 0 address space to
00319   /// integer.
00320   /// We also don't bother with same type at left and right, so
00321   /// just return 0 in this case.
00322   ///
00323   /// 1. If types are of different kind (different type IDs).
00324   ///    Return result of type IDs comparison, treating them as numbers.
00325   /// 2. If types are vectors or integers, compare Type* values as numbers.
00326   /// 3. Types has same ID, so check whether they belongs to the next group:
00327   /// * Void
00328   /// * Float
00329   /// * Double
00330   /// * X86_FP80
00331   /// * FP128
00332   /// * PPC_FP128
00333   /// * Label
00334   /// * Metadata
00335   /// If so - return 0, yes - we can treat these types as equal only because
00336   /// their IDs are same.
00337   /// 4. If Left and Right are pointers, return result of address space
00338   /// comparison (numbers comparison). We can treat pointer types of same
00339   /// address space as equal.
00340   /// 5. If types are complex.
00341   /// Then both Left and Right are to be expanded and their element types will
00342   /// be checked with the same way. If we get Res != 0 on some stage, return it.
00343   /// Otherwise return 0.
00344   /// 6. For all other cases put llvm_unreachable.
00345   int cmpTypes(Type *TyL, Type *TyR) const;
00346 
00347   int cmpNumbers(uint64_t L, uint64_t R) const;
00348 
00349   int cmpAPInts(const APInt &L, const APInt &R) const;
00350   int cmpAPFloats(const APFloat &L, const APFloat &R) const;
00351   int cmpStrings(StringRef L, StringRef R) const;
00352   int cmpAttrs(const AttributeSet L, const AttributeSet R) const;
00353 
00354   // The two functions undergoing comparison.
00355   const Function *FnL, *FnR;
00356 
00357   const DataLayout *DL;
00358 
00359   /// Assign serial numbers to values from left function, and values from
00360   /// right function.
00361   /// Explanation:
00362   /// Being comparing functions we need to compare values we meet at left and
00363   /// right sides.
00364   /// Its easy to sort things out for external values. It just should be
00365   /// the same value at left and right.
00366   /// But for local values (those were introduced inside function body)
00367   /// we have to ensure they were introduced at exactly the same place,
00368   /// and plays the same role.
00369   /// Let's assign serial number to each value when we meet it first time.
00370   /// Values that were met at same place will be with same serial numbers.
00371   /// In this case it would be good to explain few points about values assigned
00372   /// to BBs and other ways of implementation (see below).
00373   ///
00374   /// 1. Safety of BB reordering.
00375   /// It's safe to change the order of BasicBlocks in function.
00376   /// Relationship with other functions and serial numbering will not be
00377   /// changed in this case.
00378   /// As follows from FunctionComparator::compare(), we do CFG walk: we start
00379   /// from the entry, and then take each terminator. So it doesn't matter how in
00380   /// fact BBs are ordered in function. And since cmpValues are called during
00381   /// this walk, the numbering depends only on how BBs located inside the CFG.
00382   /// So the answer is - yes. We will get the same numbering.
00383   ///
00384   /// 2. Impossibility to use dominance properties of values.
00385   /// If we compare two instruction operands: first is usage of local
00386   /// variable AL from function FL, and second is usage of local variable AR
00387   /// from FR, we could compare their origins and check whether they are
00388   /// defined at the same place.
00389   /// But, we are still not able to compare operands of PHI nodes, since those
00390   /// could be operands from further BBs we didn't scan yet.
00391   /// So it's impossible to use dominance properties in general.
00392   DenseMap<const Value*, int> sn_mapL, sn_mapR;
00393 };
00394 
00395 class FunctionNode {
00396   AssertingVH<Function> F;
00397   const DataLayout *DL;
00398 
00399 public:
00400   FunctionNode(Function *F, const DataLayout *DL) : F(F), DL(DL) {}
00401   Function *getFunc() const { return F; }
00402   void release() { F = 0; }
00403   bool operator<(const FunctionNode &RHS) const {
00404     return (FunctionComparator(DL, F, RHS.getFunc()).compare()) == -1;
00405   }
00406 };
00407 }
00408 
00409 int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const {
00410   if (L < R) return -1;
00411   if (L > R) return 1;
00412   return 0;
00413 }
00414 
00415 int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const {
00416   if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth()))
00417     return Res;
00418   if (L.ugt(R)) return 1;
00419   if (R.ugt(L)) return -1;
00420   return 0;
00421 }
00422 
00423 int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const {
00424   if (int Res = cmpNumbers((uint64_t)&L.getSemantics(),
00425                            (uint64_t)&R.getSemantics()))
00426     return Res;
00427   return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt());
00428 }
00429 
00430 int FunctionComparator::cmpStrings(StringRef L, StringRef R) const {
00431   // Prevent heavy comparison, compare sizes first.
00432   if (int Res = cmpNumbers(L.size(), R.size()))
00433     return Res;
00434 
00435   // Compare strings lexicographically only when it is necessary: only when
00436   // strings are equal in size.
00437   return L.compare(R);
00438 }
00439 
00440 int FunctionComparator::cmpAttrs(const AttributeSet L,
00441                                  const AttributeSet R) const {
00442   if (int Res = cmpNumbers(L.getNumSlots(), R.getNumSlots()))
00443     return Res;
00444 
00445   for (unsigned i = 0, e = L.getNumSlots(); i != e; ++i) {
00446     AttributeSet::iterator LI = L.begin(i), LE = L.end(i), RI = R.begin(i),
00447                            RE = R.end(i);
00448     for (; LI != LE && RI != RE; ++LI, ++RI) {
00449       Attribute LA = *LI;
00450       Attribute RA = *RI;
00451       if (LA < RA)
00452         return -1;
00453       if (RA < LA)
00454         return 1;
00455     }
00456     if (LI != LE)
00457       return 1;
00458     if (RI != RE)
00459       return -1;
00460   }
00461   return 0;
00462 }
00463 
00464 /// Constants comparison:
00465 /// 1. Check whether type of L constant could be losslessly bitcasted to R
00466 /// type.
00467 /// 2. Compare constant contents.
00468 /// For more details see declaration comments.
00469 int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) {
00470 
00471   Type *TyL = L->getType();
00472   Type *TyR = R->getType();
00473 
00474   // Check whether types are bitcastable. This part is just re-factored
00475   // Type::canLosslesslyBitCastTo method, but instead of returning true/false,
00476   // we also pack into result which type is "less" for us.
00477   int TypesRes = cmpTypes(TyL, TyR);
00478   if (TypesRes != 0) {
00479     // Types are different, but check whether we can bitcast them.
00480     if (!TyL->isFirstClassType()) {
00481       if (TyR->isFirstClassType())
00482         return -1;
00483       // Neither TyL nor TyR are values of first class type. Return the result
00484       // of comparing the types
00485       return TypesRes;
00486     }
00487     if (!TyR->isFirstClassType()) {
00488       if (TyL->isFirstClassType())
00489         return 1;
00490       return TypesRes;
00491     }
00492 
00493     // Vector -> Vector conversions are always lossless if the two vector types
00494     // have the same size, otherwise not.
00495     unsigned TyLWidth = 0;
00496     unsigned TyRWidth = 0;
00497 
00498     if (const VectorType *VecTyL = dyn_cast<VectorType>(TyL))
00499       TyLWidth = VecTyL->getBitWidth();
00500     if (const VectorType *VecTyR = dyn_cast<VectorType>(TyR))
00501       TyRWidth = VecTyR->getBitWidth();
00502 
00503     if (TyLWidth != TyRWidth)
00504       return cmpNumbers(TyLWidth, TyRWidth);
00505 
00506     // Zero bit-width means neither TyL nor TyR are vectors.
00507     if (!TyLWidth) {
00508       PointerType *PTyL = dyn_cast<PointerType>(TyL);
00509       PointerType *PTyR = dyn_cast<PointerType>(TyR);
00510       if (PTyL && PTyR) {
00511         unsigned AddrSpaceL = PTyL->getAddressSpace();
00512         unsigned AddrSpaceR = PTyR->getAddressSpace();
00513         if (int Res = cmpNumbers(AddrSpaceL, AddrSpaceR))
00514           return Res;
00515       }
00516       if (PTyL)
00517         return 1;
00518       if (PTyR)
00519         return -1;
00520 
00521       // TyL and TyR aren't vectors, nor pointers. We don't know how to
00522       // bitcast them.
00523       return TypesRes;
00524     }
00525   }
00526 
00527   // OK, types are bitcastable, now check constant contents.
00528 
00529   if (L->isNullValue() && R->isNullValue())
00530     return TypesRes;
00531   if (L->isNullValue() && !R->isNullValue())
00532     return 1;
00533   if (!L->isNullValue() && R->isNullValue())
00534     return -1;
00535 
00536   if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
00537     return Res;
00538 
00539   switch (L->getValueID()) {
00540   case Value::UndefValueVal: return TypesRes;
00541   case Value::ConstantIntVal: {
00542     const APInt &LInt = cast<ConstantInt>(L)->getValue();
00543     const APInt &RInt = cast<ConstantInt>(R)->getValue();
00544     return cmpAPInts(LInt, RInt);
00545   }
00546   case Value::ConstantFPVal: {
00547     const APFloat &LAPF = cast<ConstantFP>(L)->getValueAPF();
00548     const APFloat &RAPF = cast<ConstantFP>(R)->getValueAPF();
00549     return cmpAPFloats(LAPF, RAPF);
00550   }
00551   case Value::ConstantArrayVal: {
00552     const ConstantArray *LA = cast<ConstantArray>(L);
00553     const ConstantArray *RA = cast<ConstantArray>(R);
00554     uint64_t NumElementsL = cast<ArrayType>(TyL)->getNumElements();
00555     uint64_t NumElementsR = cast<ArrayType>(TyR)->getNumElements();
00556     if (int Res = cmpNumbers(NumElementsL, NumElementsR))
00557       return Res;
00558     for (uint64_t i = 0; i < NumElementsL; ++i) {
00559       if (int Res = cmpConstants(cast<Constant>(LA->getOperand(i)),
00560                                  cast<Constant>(RA->getOperand(i))))
00561         return Res;
00562     }
00563     return 0;
00564   }
00565   case Value::ConstantStructVal: {
00566     const ConstantStruct *LS = cast<ConstantStruct>(L);
00567     const ConstantStruct *RS = cast<ConstantStruct>(R);
00568     unsigned NumElementsL = cast<StructType>(TyL)->getNumElements();
00569     unsigned NumElementsR = cast<StructType>(TyR)->getNumElements();
00570     if (int Res = cmpNumbers(NumElementsL, NumElementsR))
00571       return Res;
00572     for (unsigned i = 0; i != NumElementsL; ++i) {
00573       if (int Res = cmpConstants(cast<Constant>(LS->getOperand(i)),
00574                                  cast<Constant>(RS->getOperand(i))))
00575         return Res;
00576     }
00577     return 0;
00578   }
00579   case Value::ConstantVectorVal: {
00580     const ConstantVector *LV = cast<ConstantVector>(L);
00581     const ConstantVector *RV = cast<ConstantVector>(R);
00582     unsigned NumElementsL = cast<VectorType>(TyL)->getNumElements();
00583     unsigned NumElementsR = cast<VectorType>(TyR)->getNumElements();
00584     if (int Res = cmpNumbers(NumElementsL, NumElementsR))
00585       return Res;
00586     for (uint64_t i = 0; i < NumElementsL; ++i) {
00587       if (int Res = cmpConstants(cast<Constant>(LV->getOperand(i)),
00588                                  cast<Constant>(RV->getOperand(i))))
00589         return Res;
00590     }
00591     return 0;
00592   }
00593   case Value::ConstantExprVal: {
00594     const ConstantExpr *LE = cast<ConstantExpr>(L);
00595     const ConstantExpr *RE = cast<ConstantExpr>(R);
00596     unsigned NumOperandsL = LE->getNumOperands();
00597     unsigned NumOperandsR = RE->getNumOperands();
00598     if (int Res = cmpNumbers(NumOperandsL, NumOperandsR))
00599       return Res;
00600     for (unsigned i = 0; i < NumOperandsL; ++i) {
00601       if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)),
00602                                  cast<Constant>(RE->getOperand(i))))
00603         return Res;
00604     }
00605     return 0;
00606   }
00607   case Value::FunctionVal:
00608   case Value::GlobalVariableVal:
00609   case Value::GlobalAliasVal:
00610   default: // Unknown constant, cast L and R pointers to numbers and compare.
00611     return cmpNumbers((uint64_t)L, (uint64_t)R);
00612   }
00613 }
00614 
00615 /// cmpType - compares two types,
00616 /// defines total ordering among the types set.
00617 /// See method declaration comments for more details.
00618 int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
00619 
00620   PointerType *PTyL = dyn_cast<PointerType>(TyL);
00621   PointerType *PTyR = dyn_cast<PointerType>(TyR);
00622 
00623   if (DL) {
00624     if (PTyL && PTyL->getAddressSpace() == 0) TyL = DL->getIntPtrType(TyL);
00625     if (PTyR && PTyR->getAddressSpace() == 0) TyR = DL->getIntPtrType(TyR);
00626   }
00627 
00628   if (TyL == TyR)
00629     return 0;
00630 
00631   if (int Res = cmpNumbers(TyL->getTypeID(), TyR->getTypeID()))
00632     return Res;
00633 
00634   switch (TyL->getTypeID()) {
00635   default:
00636     llvm_unreachable("Unknown type!");
00637     // Fall through in Release mode.
00638   case Type::IntegerTyID:
00639   case Type::VectorTyID:
00640     // TyL == TyR would have returned true earlier.
00641     return cmpNumbers((uint64_t)TyL, (uint64_t)TyR);
00642 
00643   case Type::VoidTyID:
00644   case Type::FloatTyID:
00645   case Type::DoubleTyID:
00646   case Type::X86_FP80TyID:
00647   case Type::FP128TyID:
00648   case Type::PPC_FP128TyID:
00649   case Type::LabelTyID:
00650   case Type::MetadataTyID:
00651     return 0;
00652 
00653   case Type::PointerTyID: {
00654     assert(PTyL && PTyR && "Both types must be pointers here.");
00655     return cmpNumbers(PTyL->getAddressSpace(), PTyR->getAddressSpace());
00656   }
00657 
00658   case Type::StructTyID: {
00659     StructType *STyL = cast<StructType>(TyL);
00660     StructType *STyR = cast<StructType>(TyR);
00661     if (STyL->getNumElements() != STyR->getNumElements())
00662       return cmpNumbers(STyL->getNumElements(), STyR->getNumElements());
00663 
00664     if (STyL->isPacked() != STyR->isPacked())
00665       return cmpNumbers(STyL->isPacked(), STyR->isPacked());
00666 
00667     for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) {
00668       if (int Res = cmpTypes(STyL->getElementType(i), STyR->getElementType(i)))
00669         return Res;
00670     }
00671     return 0;
00672   }
00673 
00674   case Type::FunctionTyID: {
00675     FunctionType *FTyL = cast<FunctionType>(TyL);
00676     FunctionType *FTyR = cast<FunctionType>(TyR);
00677     if (FTyL->getNumParams() != FTyR->getNumParams())
00678       return cmpNumbers(FTyL->getNumParams(), FTyR->getNumParams());
00679 
00680     if (FTyL->isVarArg() != FTyR->isVarArg())
00681       return cmpNumbers(FTyL->isVarArg(), FTyR->isVarArg());
00682 
00683     if (int Res = cmpTypes(FTyL->getReturnType(), FTyR->getReturnType()))
00684       return Res;
00685 
00686     for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) {
00687       if (int Res = cmpTypes(FTyL->getParamType(i), FTyR->getParamType(i)))
00688         return Res;
00689     }
00690     return 0;
00691   }
00692 
00693   case Type::ArrayTyID: {
00694     ArrayType *ATyL = cast<ArrayType>(TyL);
00695     ArrayType *ATyR = cast<ArrayType>(TyR);
00696     if (ATyL->getNumElements() != ATyR->getNumElements())
00697       return cmpNumbers(ATyL->getNumElements(), ATyR->getNumElements());
00698     return cmpTypes(ATyL->getElementType(), ATyR->getElementType());
00699   }
00700   }
00701 }
00702 
00703 // Determine whether the two operations are the same except that pointer-to-A
00704 // and pointer-to-B are equivalent. This should be kept in sync with
00705 // Instruction::isSameOperationAs.
00706 // Read method declaration comments for more details.
00707 int FunctionComparator::cmpOperations(const Instruction *L,
00708                                       const Instruction *R) const {
00709   // Differences from Instruction::isSameOperationAs:
00710   //  * replace type comparison with calls to isEquivalentType.
00711   //  * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top
00712   //  * because of the above, we don't test for the tail bit on calls later on
00713   if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode()))
00714     return Res;
00715 
00716   if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands()))
00717     return Res;
00718 
00719   if (int Res = cmpTypes(L->getType(), R->getType()))
00720     return Res;
00721 
00722   if (int Res = cmpNumbers(L->getRawSubclassOptionalData(),
00723                            R->getRawSubclassOptionalData()))
00724     return Res;
00725 
00726   // We have two instructions of identical opcode and #operands.  Check to see
00727   // if all operands are the same type
00728   for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) {
00729     if (int Res =
00730             cmpTypes(L->getOperand(i)->getType(), R->getOperand(i)->getType()))
00731       return Res;
00732   }
00733 
00734   // Check special state that is a part of some instructions.
00735   if (const LoadInst *LI = dyn_cast<LoadInst>(L)) {
00736     if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile()))
00737       return Res;
00738     if (int Res =
00739             cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment()))
00740       return Res;
00741     if (int Res =
00742             cmpNumbers(LI->getOrdering(), cast<LoadInst>(R)->getOrdering()))
00743       return Res;
00744     if (int Res =
00745             cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope()))
00746       return Res;
00747     return cmpNumbers((uint64_t)LI->getMetadata(LLVMContext::MD_range),
00748                       (uint64_t)cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
00749   }
00750   if (const StoreInst *SI = dyn_cast<StoreInst>(L)) {
00751     if (int Res =
00752             cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile()))
00753       return Res;
00754     if (int Res =
00755             cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment()))
00756       return Res;
00757     if (int Res =
00758             cmpNumbers(SI->getOrdering(), cast<StoreInst>(R)->getOrdering()))
00759       return Res;
00760     return cmpNumbers(SI->getSynchScope(), cast<StoreInst>(R)->getSynchScope());
00761   }
00762   if (const CmpInst *CI = dyn_cast<CmpInst>(L))
00763     return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate());
00764   if (const CallInst *CI = dyn_cast<CallInst>(L)) {
00765     if (int Res = cmpNumbers(CI->getCallingConv(),
00766                              cast<CallInst>(R)->getCallingConv()))
00767       return Res;
00768     if (int Res =
00769             cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes()))
00770       return Res;
00771     return cmpNumbers(
00772         (uint64_t)CI->getMetadata(LLVMContext::MD_range),
00773         (uint64_t)cast<CallInst>(R)->getMetadata(LLVMContext::MD_range));
00774   }
00775   if (const InvokeInst *CI = dyn_cast<InvokeInst>(L)) {
00776     if (int Res = cmpNumbers(CI->getCallingConv(),
00777                              cast<InvokeInst>(R)->getCallingConv()))
00778       return Res;
00779     if (int Res =
00780             cmpAttrs(CI->getAttributes(), cast<InvokeInst>(R)->getAttributes()))
00781       return Res;
00782     return cmpNumbers(
00783         (uint64_t)CI->getMetadata(LLVMContext::MD_range),
00784         (uint64_t)cast<InvokeInst>(R)->getMetadata(LLVMContext::MD_range));
00785   }
00786   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) {
00787     ArrayRef<unsigned> LIndices = IVI->getIndices();
00788     ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices();
00789     if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
00790       return Res;
00791     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
00792       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
00793         return Res;
00794     }
00795   }
00796   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) {
00797     ArrayRef<unsigned> LIndices = EVI->getIndices();
00798     ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices();
00799     if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
00800       return Res;
00801     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
00802       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
00803         return Res;
00804     }
00805   }
00806   if (const FenceInst *FI = dyn_cast<FenceInst>(L)) {
00807     if (int Res =
00808             cmpNumbers(FI->getOrdering(), cast<FenceInst>(R)->getOrdering()))
00809       return Res;
00810     return cmpNumbers(FI->getSynchScope(), cast<FenceInst>(R)->getSynchScope());
00811   }
00812 
00813   if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(L)) {
00814     if (int Res = cmpNumbers(CXI->isVolatile(),
00815                              cast<AtomicCmpXchgInst>(R)->isVolatile()))
00816       return Res;
00817     if (int Res = cmpNumbers(CXI->isWeak(),
00818                              cast<AtomicCmpXchgInst>(R)->isWeak()))
00819       return Res;
00820     if (int Res = cmpNumbers(CXI->getSuccessOrdering(),
00821                              cast<AtomicCmpXchgInst>(R)->getSuccessOrdering()))
00822       return Res;
00823     if (int Res = cmpNumbers(CXI->getFailureOrdering(),
00824                              cast<AtomicCmpXchgInst>(R)->getFailureOrdering()))
00825       return Res;
00826     return cmpNumbers(CXI->getSynchScope(),
00827                       cast<AtomicCmpXchgInst>(R)->getSynchScope());
00828   }
00829   if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(L)) {
00830     if (int Res = cmpNumbers(RMWI->getOperation(),
00831                              cast<AtomicRMWInst>(R)->getOperation()))
00832       return Res;
00833     if (int Res = cmpNumbers(RMWI->isVolatile(),
00834                              cast<AtomicRMWInst>(R)->isVolatile()))
00835       return Res;
00836     if (int Res = cmpNumbers(RMWI->getOrdering(),
00837                              cast<AtomicRMWInst>(R)->getOrdering()))
00838       return Res;
00839     return cmpNumbers(RMWI->getSynchScope(),
00840                       cast<AtomicRMWInst>(R)->getSynchScope());
00841   }
00842   return 0;
00843 }
00844 
00845 // Determine whether two GEP operations perform the same underlying arithmetic.
00846 // Read method declaration comments for more details.
00847 int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
00848                                const GEPOperator *GEPR) {
00849 
00850   unsigned int ASL = GEPL->getPointerAddressSpace();
00851   unsigned int ASR = GEPR->getPointerAddressSpace();
00852 
00853   if (int Res = cmpNumbers(ASL, ASR))
00854     return Res;
00855 
00856   // When we have target data, we can reduce the GEP down to the value in bytes
00857   // added to the address.
00858   if (DL) {
00859     unsigned BitWidth = DL->getPointerSizeInBits(ASL);
00860     APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0);
00861     if (GEPL->accumulateConstantOffset(*DL, OffsetL) &&
00862         GEPR->accumulateConstantOffset(*DL, OffsetR))
00863       return cmpAPInts(OffsetL, OffsetR);
00864   }
00865 
00866   if (int Res = cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
00867                            (uint64_t)GEPR->getPointerOperand()->getType()))
00868     return Res;
00869 
00870   if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
00871     return Res;
00872 
00873   for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
00874     if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
00875       return Res;
00876   }
00877 
00878   return 0;
00879 }
00880 
00881 /// Compare two values used by the two functions under pair-wise comparison. If
00882 /// this is the first time the values are seen, they're added to the mapping so
00883 /// that we will detect mismatches on next use.
00884 /// See comments in declaration for more details.
00885 int FunctionComparator::cmpValues(const Value *L, const Value *R) {
00886   // Catch self-reference case.
00887   if (L == FnL) {
00888     if (R == FnR)
00889       return 0;
00890     return -1;
00891   }
00892   if (R == FnR) {
00893     if (L == FnL)
00894       return 0;
00895     return 1;
00896   }
00897 
00898   const Constant *ConstL = dyn_cast<Constant>(L);
00899   const Constant *ConstR = dyn_cast<Constant>(R);
00900   if (ConstL && ConstR) {
00901     if (L == R)
00902       return 0;
00903     return cmpConstants(ConstL, ConstR);
00904   }
00905 
00906   if (ConstL)
00907     return 1;
00908   if (ConstR)
00909     return -1;
00910 
00911   const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L);
00912   const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R);
00913 
00914   if (InlineAsmL && InlineAsmR)
00915     return cmpNumbers((uint64_t)L, (uint64_t)R);
00916   if (InlineAsmL)
00917     return 1;
00918   if (InlineAsmR)
00919     return -1;
00920 
00921   auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())),
00922        RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size()));
00923 
00924   return cmpNumbers(LeftSN.first->second, RightSN.first->second);
00925 }
00926 // Test whether two basic blocks have equivalent behaviour.
00927 int FunctionComparator::compare(const BasicBlock *BBL, const BasicBlock *BBR) {
00928   BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
00929   BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
00930 
00931   do {
00932     if (int Res = cmpValues(InstL, InstR))
00933       return Res;
00934 
00935     const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(InstL);
00936     const GetElementPtrInst *GEPR = dyn_cast<GetElementPtrInst>(InstR);
00937 
00938     if (GEPL && !GEPR)
00939       return 1;
00940     if (GEPR && !GEPL)
00941       return -1;
00942 
00943     if (GEPL && GEPR) {
00944       if (int Res =
00945               cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand()))
00946         return Res;
00947       if (int Res = cmpGEPs(GEPL, GEPR))
00948         return Res;
00949     } else {
00950       if (int Res = cmpOperations(InstL, InstR))
00951         return Res;
00952       assert(InstL->getNumOperands() == InstR->getNumOperands());
00953 
00954       for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
00955         Value *OpL = InstL->getOperand(i);
00956         Value *OpR = InstR->getOperand(i);
00957         if (int Res = cmpValues(OpL, OpR))
00958           return Res;
00959         if (int Res = cmpNumbers(OpL->getValueID(), OpR->getValueID()))
00960           return Res;
00961         // TODO: Already checked in cmpOperation
00962         if (int Res = cmpTypes(OpL->getType(), OpR->getType()))
00963           return Res;
00964       }
00965     }
00966 
00967     ++InstL, ++InstR;
00968   } while (InstL != InstLE && InstR != InstRE);
00969 
00970   if (InstL != InstLE && InstR == InstRE)
00971     return 1;
00972   if (InstL == InstLE && InstR != InstRE)
00973     return -1;
00974   return 0;
00975 }
00976 
00977 // Test whether the two functions have equivalent behaviour.
00978 int FunctionComparator::compare() {
00979 
00980   sn_mapL.clear();
00981   sn_mapR.clear();
00982 
00983   if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes()))
00984     return Res;
00985 
00986   if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC()))
00987     return Res;
00988 
00989   if (FnL->hasGC()) {
00990     if (int Res = cmpNumbers((uint64_t)FnL->getGC(), (uint64_t)FnR->getGC()))
00991       return Res;
00992   }
00993 
00994   if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection()))
00995     return Res;
00996 
00997   if (FnL->hasSection()) {
00998     if (int Res = cmpStrings(FnL->getSection(), FnR->getSection()))
00999       return Res;
01000   }
01001 
01002   if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg()))
01003     return Res;
01004 
01005   // TODO: if it's internal and only used in direct calls, we could handle this
01006   // case too.
01007   if (int Res = cmpNumbers(FnL->getCallingConv(), FnR->getCallingConv()))
01008     return Res;
01009 
01010   if (int Res = cmpTypes(FnL->getFunctionType(), FnR->getFunctionType()))
01011     return Res;
01012 
01013   assert(FnL->arg_size() == FnR->arg_size() &&
01014          "Identically typed functions have different numbers of args!");
01015 
01016   // Visit the arguments so that they get enumerated in the order they're
01017   // passed in.
01018   for (Function::const_arg_iterator ArgLI = FnL->arg_begin(),
01019                                     ArgRI = FnR->arg_begin(),
01020                                     ArgLE = FnL->arg_end();
01021        ArgLI != ArgLE; ++ArgLI, ++ArgRI) {
01022     if (cmpValues(ArgLI, ArgRI) != 0)
01023       llvm_unreachable("Arguments repeat!");
01024   }
01025 
01026   // We do a CFG-ordered walk since the actual ordering of the blocks in the
01027   // linked list is immaterial. Our walk starts at the entry block for both
01028   // functions, then takes each block from each terminator in order. As an
01029   // artifact, this also means that unreachable blocks are ignored.
01030   SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs;
01031   SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1.
01032 
01033   FnLBBs.push_back(&FnL->getEntryBlock());
01034   FnRBBs.push_back(&FnR->getEntryBlock());
01035 
01036   VisitedBBs.insert(FnLBBs[0]);
01037   while (!FnLBBs.empty()) {
01038     const BasicBlock *BBL = FnLBBs.pop_back_val();
01039     const BasicBlock *BBR = FnRBBs.pop_back_val();
01040 
01041     if (int Res = cmpValues(BBL, BBR))
01042       return Res;
01043 
01044     if (int Res = compare(BBL, BBR))
01045       return Res;
01046 
01047     const TerminatorInst *TermL = BBL->getTerminator();
01048     const TerminatorInst *TermR = BBR->getTerminator();
01049 
01050     assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
01051     for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
01052       if (!VisitedBBs.insert(TermL->getSuccessor(i)).second)
01053         continue;
01054 
01055       FnLBBs.push_back(TermL->getSuccessor(i));
01056       FnRBBs.push_back(TermR->getSuccessor(i));
01057     }
01058   }
01059   return 0;
01060 }
01061 
01062 namespace {
01063 
01064 /// MergeFunctions finds functions which will generate identical machine code,
01065 /// by considering all pointer types to be equivalent. Once identified,
01066 /// MergeFunctions will fold them by replacing a call to one to a call to a
01067 /// bitcast of the other.
01068 ///
01069 class MergeFunctions : public ModulePass {
01070 public:
01071   static char ID;
01072   MergeFunctions()
01073     : ModulePass(ID), HasGlobalAliases(false) {
01074     initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
01075   }
01076 
01077   bool runOnModule(Module &M) override;
01078 
01079 private:
01080   typedef std::set<FunctionNode> FnTreeType;
01081 
01082   /// A work queue of functions that may have been modified and should be
01083   /// analyzed again.
01084   std::vector<WeakVH> Deferred;
01085 
01086   /// Checks the rules of order relation introduced among functions set.
01087   /// Returns true, if sanity check has been passed, and false if failed.
01088   bool doSanityCheck(std::vector<WeakVH> &Worklist);
01089 
01090   /// Insert a ComparableFunction into the FnTree, or merge it away if it's
01091   /// equal to one that's already present.
01092   bool insert(Function *NewFunction);
01093 
01094   /// Remove a Function from the FnTree and queue it up for a second sweep of
01095   /// analysis.
01096   void remove(Function *F);
01097 
01098   /// Find the functions that use this Value and remove them from FnTree and
01099   /// queue the functions.
01100   void removeUsers(Value *V);
01101 
01102   /// Replace all direct calls of Old with calls of New. Will bitcast New if
01103   /// necessary to make types match.
01104   void replaceDirectCallers(Function *Old, Function *New);
01105 
01106   /// Merge two equivalent functions. Upon completion, G may be deleted, or may
01107   /// be converted into a thunk. In either case, it should never be visited
01108   /// again.
01109   void mergeTwoFunctions(Function *F, Function *G);
01110 
01111   /// Replace G with a thunk or an alias to F. Deletes G.
01112   void writeThunkOrAlias(Function *F, Function *G);
01113 
01114   /// Replace G with a simple tail call to bitcast(F). Also replace direct uses
01115   /// of G with bitcast(F). Deletes G.
01116   void writeThunk(Function *F, Function *G);
01117 
01118   /// Replace G with an alias to F. Deletes G.
01119   void writeAlias(Function *F, Function *G);
01120 
01121   /// The set of all distinct functions. Use the insert() and remove() methods
01122   /// to modify it.
01123   FnTreeType FnTree;
01124 
01125   /// DataLayout for more accurate GEP comparisons. May be NULL.
01126   const DataLayout *DL;
01127 
01128   /// Whether or not the target supports global aliases.
01129   bool HasGlobalAliases;
01130 };
01131 
01132 }  // end anonymous namespace
01133 
01134 char MergeFunctions::ID = 0;
01135 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
01136 
01137 ModulePass *llvm::createMergeFunctionsPass() {
01138   return new MergeFunctions();
01139 }
01140 
01141 bool MergeFunctions::doSanityCheck(std::vector<WeakVH> &Worklist) {
01142   if (const unsigned Max = NumFunctionsForSanityCheck) {
01143     unsigned TripleNumber = 0;
01144     bool Valid = true;
01145 
01146     dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
01147 
01148     unsigned i = 0;
01149     for (std::vector<WeakVH>::iterator I = Worklist.begin(), E = Worklist.end();
01150          I != E && i < Max; ++I, ++i) {
01151       unsigned j = i;
01152       for (std::vector<WeakVH>::iterator J = I; J != E && j < Max; ++J, ++j) {
01153         Function *F1 = cast<Function>(*I);
01154         Function *F2 = cast<Function>(*J);
01155         int Res1 = FunctionComparator(DL, F1, F2).compare();
01156         int Res2 = FunctionComparator(DL, F2, F1).compare();
01157 
01158         // If F1 <= F2, then F2 >= F1, otherwise report failure.
01159         if (Res1 != -Res2) {
01160           dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
01161                  << "\n";
01162           F1->dump();
01163           F2->dump();
01164           Valid = false;
01165         }
01166 
01167         if (Res1 == 0)
01168           continue;
01169 
01170         unsigned k = j;
01171         for (std::vector<WeakVH>::iterator K = J; K != E && k < Max;
01172              ++k, ++K, ++TripleNumber) {
01173           if (K == J)
01174             continue;
01175 
01176           Function *F3 = cast<Function>(*K);
01177           int Res3 = FunctionComparator(DL, F1, F3).compare();
01178           int Res4 = FunctionComparator(DL, F2, F3).compare();
01179 
01180           bool Transitive = true;
01181 
01182           if (Res1 != 0 && Res1 == Res4) {
01183             // F1 > F2, F2 > F3 => F1 > F3
01184             Transitive = Res3 == Res1;
01185           } else if (Res3 != 0 && Res3 == -Res4) {
01186             // F1 > F3, F3 > F2 => F1 > F2
01187             Transitive = Res3 == Res1;
01188           } else if (Res4 != 0 && -Res3 == Res4) {
01189             // F2 > F3, F3 > F1 => F2 > F1
01190             Transitive = Res4 == -Res1;
01191           }
01192 
01193           if (!Transitive) {
01194             dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
01195                    << TripleNumber << "\n";
01196             dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
01197                    << Res4 << "\n";
01198             F1->dump();
01199             F2->dump();
01200             F3->dump();
01201             Valid = false;
01202           }
01203         }
01204       }
01205     }
01206 
01207     dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
01208     return Valid;
01209   }
01210   return true;
01211 }
01212 
01213 bool MergeFunctions::runOnModule(Module &M) {
01214   bool Changed = false;
01215   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
01216   DL = DLP ? &DLP->getDataLayout() : nullptr;
01217 
01218   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
01219     if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage())
01220       Deferred.push_back(WeakVH(I));
01221   }
01222 
01223   do {
01224     std::vector<WeakVH> Worklist;
01225     Deferred.swap(Worklist);
01226 
01227     DEBUG(doSanityCheck(Worklist));
01228 
01229     DEBUG(dbgs() << "size of module: " << M.size() << '\n');
01230     DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
01231 
01232     // Insert only strong functions and merge them. Strong function merging
01233     // always deletes one of them.
01234     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
01235            E = Worklist.end(); I != E; ++I) {
01236       if (!*I) continue;
01237       Function *F = cast<Function>(*I);
01238       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
01239           !F->mayBeOverridden()) {
01240         Changed |= insert(F);
01241       }
01242     }
01243 
01244     // Insert only weak functions and merge them. By doing these second we
01245     // create thunks to the strong function when possible. When two weak
01246     // functions are identical, we create a new strong function with two weak
01247     // weak thunks to it which are identical but not mergable.
01248     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
01249            E = Worklist.end(); I != E; ++I) {
01250       if (!*I) continue;
01251       Function *F = cast<Function>(*I);
01252       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
01253           F->mayBeOverridden()) {
01254         Changed |= insert(F);
01255       }
01256     }
01257     DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
01258   } while (!Deferred.empty());
01259 
01260   FnTree.clear();
01261 
01262   return Changed;
01263 }
01264 
01265 // Replace direct callers of Old with New.
01266 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
01267   Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
01268   for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
01269     Use *U = &*UI;
01270     ++UI;
01271     CallSite CS(U->getUser());
01272     if (CS && CS.isCallee(U)) {
01273       remove(CS.getInstruction()->getParent()->getParent());
01274       U->set(BitcastNew);
01275     }
01276   }
01277 }
01278 
01279 // Replace G with an alias to F if possible, or else a thunk to F. Deletes G.
01280 void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
01281   if (HasGlobalAliases && G->hasUnnamedAddr()) {
01282     if (G->hasExternalLinkage() || G->hasLocalLinkage() ||
01283         G->hasWeakLinkage()) {
01284       writeAlias(F, G);
01285       return;
01286     }
01287   }
01288 
01289   writeThunk(F, G);
01290 }
01291 
01292 // Helper for writeThunk,
01293 // Selects proper bitcast operation,
01294 // but a bit simpler then CastInst::getCastOpcode.
01295 static Value *createCast(IRBuilder<false> &Builder, Value *V, Type *DestTy) {
01296   Type *SrcTy = V->getType();
01297   if (SrcTy->isStructTy()) {
01298     assert(DestTy->isStructTy());
01299     assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
01300     Value *Result = UndefValue::get(DestTy);
01301     for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
01302       Value *Element = createCast(
01303           Builder, Builder.CreateExtractValue(V, makeArrayRef(I)),
01304           DestTy->getStructElementType(I));
01305 
01306       Result =
01307           Builder.CreateInsertValue(Result, Element, makeArrayRef(I));
01308     }
01309     return Result;
01310   }
01311   assert(!DestTy->isStructTy());
01312   if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
01313     return Builder.CreateIntToPtr(V, DestTy);
01314   else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
01315     return Builder.CreatePtrToInt(V, DestTy);
01316   else
01317     return Builder.CreateBitCast(V, DestTy);
01318 }
01319 
01320 // Replace G with a simple tail call to bitcast(F). Also replace direct uses
01321 // of G with bitcast(F). Deletes G.
01322 void MergeFunctions::writeThunk(Function *F, Function *G) {
01323   if (!G->mayBeOverridden()) {
01324     // Redirect direct callers of G to F.
01325     replaceDirectCallers(G, F);
01326   }
01327 
01328   // If G was internal then we may have replaced all uses of G with F. If so,
01329   // stop here and delete G. There's no need for a thunk.
01330   if (G->hasLocalLinkage() && G->use_empty()) {
01331     G->eraseFromParent();
01332     return;
01333   }
01334 
01335   Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
01336                                     G->getParent());
01337   BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
01338   IRBuilder<false> Builder(BB);
01339 
01340   SmallVector<Value *, 16> Args;
01341   unsigned i = 0;
01342   FunctionType *FFTy = F->getFunctionType();
01343   for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
01344        AI != AE; ++AI) {
01345     Args.push_back(createCast(Builder, (Value*)AI, FFTy->getParamType(i)));
01346     ++i;
01347   }
01348 
01349   CallInst *CI = Builder.CreateCall(F, Args);
01350   CI->setTailCall();
01351   CI->setCallingConv(F->getCallingConv());
01352   if (NewG->getReturnType()->isVoidTy()) {
01353     Builder.CreateRetVoid();
01354   } else {
01355     Builder.CreateRet(createCast(Builder, CI, NewG->getReturnType()));
01356   }
01357 
01358   NewG->copyAttributesFrom(G);
01359   NewG->takeName(G);
01360   removeUsers(G);
01361   G->replaceAllUsesWith(NewG);
01362   G->eraseFromParent();
01363 
01364   DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n');
01365   ++NumThunksWritten;
01366 }
01367 
01368 // Replace G with an alias to F and delete G.
01369 void MergeFunctions::writeAlias(Function *F, Function *G) {
01370   PointerType *PTy = G->getType();
01371   auto *GA = GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
01372                                  G->getLinkage(), "", F);
01373   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
01374   GA->takeName(G);
01375   GA->setVisibility(G->getVisibility());
01376   removeUsers(G);
01377   G->replaceAllUsesWith(GA);
01378   G->eraseFromParent();
01379 
01380   DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
01381   ++NumAliasesWritten;
01382 }
01383 
01384 // Merge two equivalent functions. Upon completion, Function G is deleted.
01385 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
01386   if (F->mayBeOverridden()) {
01387     assert(G->mayBeOverridden());
01388 
01389     if (HasGlobalAliases) {
01390       // Make them both thunks to the same internal function.
01391       Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
01392                                      F->getParent());
01393       H->copyAttributesFrom(F);
01394       H->takeName(F);
01395       removeUsers(F);
01396       F->replaceAllUsesWith(H);
01397 
01398       unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
01399 
01400       writeAlias(F, G);
01401       writeAlias(F, H);
01402 
01403       F->setAlignment(MaxAlignment);
01404       F->setLinkage(GlobalValue::PrivateLinkage);
01405     } else {
01406       // We can't merge them. Instead, pick one and update all direct callers
01407       // to call it and hope that we improve the instruction cache hit rate.
01408       replaceDirectCallers(G, F);
01409     }
01410 
01411     ++NumDoubleWeak;
01412   } else {
01413     writeThunkOrAlias(F, G);
01414   }
01415 
01416   ++NumFunctionsMerged;
01417 }
01418 
01419 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
01420 // that was already inserted.
01421 bool MergeFunctions::insert(Function *NewFunction) {
01422   std::pair<FnTreeType::iterator, bool> Result =
01423       FnTree.insert(FunctionNode(NewFunction, DL));
01424 
01425   if (Result.second) {
01426     DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n');
01427     return false;
01428   }
01429 
01430   const FunctionNode &OldF = *Result.first;
01431 
01432   // Don't merge tiny functions, since it can just end up making the function
01433   // larger.
01434   // FIXME: Should still merge them if they are unnamed_addr and produce an
01435   // alias.
01436   if (NewFunction->size() == 1) {
01437     if (NewFunction->front().size() <= 2) {
01438       DEBUG(dbgs() << NewFunction->getName()
01439                    << " is to small to bother merging\n");
01440       return false;
01441     }
01442   }
01443 
01444   // Never thunk a strong function to a weak function.
01445   assert(!OldF.getFunc()->mayBeOverridden() || NewFunction->mayBeOverridden());
01446 
01447   DEBUG(dbgs() << "  " << OldF.getFunc()->getName()
01448                << " == " << NewFunction->getName() << '\n');
01449 
01450   Function *DeleteF = NewFunction;
01451   mergeTwoFunctions(OldF.getFunc(), DeleteF);
01452   return true;
01453 }
01454 
01455 // Remove a function from FnTree. If it was already in FnTree, add
01456 // it to Deferred so that we'll look at it in the next round.
01457 void MergeFunctions::remove(Function *F) {
01458   // We need to make sure we remove F, not a function "equal" to F per the
01459   // function equality comparator.
01460   FnTreeType::iterator found = FnTree.find(FunctionNode(F, DL));
01461   size_t Erased = 0;
01462   if (found != FnTree.end() && found->getFunc() == F) {
01463     Erased = 1;
01464     FnTree.erase(found);
01465   }
01466 
01467   if (Erased) {
01468     DEBUG(dbgs() << "Removed " << F->getName()
01469                  << " from set and deferred it.\n");
01470     Deferred.push_back(F);
01471   }
01472 }
01473 
01474 // For each instruction used by the value, remove() the function that contains
01475 // the instruction. This should happen right before a call to RAUW.
01476 void MergeFunctions::removeUsers(Value *V) {
01477   std::vector<Value *> Worklist;
01478   Worklist.push_back(V);
01479   while (!Worklist.empty()) {
01480     Value *V = Worklist.back();
01481     Worklist.pop_back();
01482 
01483     for (User *U : V->users()) {
01484       if (Instruction *I = dyn_cast<Instruction>(U)) {
01485         remove(I->getParent()->getParent());
01486       } else if (isa<GlobalValue>(U)) {
01487         // do nothing
01488       } else if (Constant *C = dyn_cast<Constant>(U)) {
01489         for (User *UU : C->users())
01490           Worklist.push_back(UU);
01491       }
01492     }
01493   }
01494 }