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 cmpOperation(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 cmpGEP(const GEPOperator *GEPL, const GEPOperator *GEPR);
00301   int cmpGEP(const GetElementPtrInst *GEPL, const GetElementPtrInst *GEPR) {
00302     return cmpGEP(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 cmpType(Type *TyL, Type *TyR) const;
00346 
00347   int cmpNumbers(uint64_t L, uint64_t R) const;
00348 
00349   int cmpAPInt(const APInt &L, const APInt &R) const;
00350   int cmpAPFloat(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 FunctionPtr {
00396   AssertingVH<Function> F;
00397   const DataLayout *DL;
00398 
00399 public:
00400   FunctionPtr(Function *F, const DataLayout *DL) : F(F), DL(DL) {}
00401   Function *getFunc() const { return F; }
00402   void release() { F = 0; }
00403   bool operator<(const FunctionPtr &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::cmpAPInt(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::cmpAPFloat(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 cmpAPInt(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 = cmpType(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 cmpAPInt(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 cmpAPFloat(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::cmpType(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 = cmpType(STyL->getElementType(i),
00669                             STyR->getElementType(i)))
00670         return Res;
00671     }
00672     return 0;
00673   }
00674 
00675   case Type::FunctionTyID: {
00676     FunctionType *FTyL = cast<FunctionType>(TyL);
00677     FunctionType *FTyR = cast<FunctionType>(TyR);
00678     if (FTyL->getNumParams() != FTyR->getNumParams())
00679       return cmpNumbers(FTyL->getNumParams(), FTyR->getNumParams());
00680 
00681     if (FTyL->isVarArg() != FTyR->isVarArg())
00682       return cmpNumbers(FTyL->isVarArg(), FTyR->isVarArg());
00683 
00684     if (int Res = cmpType(FTyL->getReturnType(), FTyR->getReturnType()))
00685       return Res;
00686 
00687     for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) {
00688       if (int Res = cmpType(FTyL->getParamType(i), FTyR->getParamType(i)))
00689         return Res;
00690     }
00691     return 0;
00692   }
00693 
00694   case Type::ArrayTyID: {
00695     ArrayType *ATyL = cast<ArrayType>(TyL);
00696     ArrayType *ATyR = cast<ArrayType>(TyR);
00697     if (ATyL->getNumElements() != ATyR->getNumElements())
00698       return cmpNumbers(ATyL->getNumElements(), ATyR->getNumElements());
00699     return cmpType(ATyL->getElementType(), ATyR->getElementType());
00700   }
00701   }
00702 }
00703 
00704 // Determine whether the two operations are the same except that pointer-to-A
00705 // and pointer-to-B are equivalent. This should be kept in sync with
00706 // Instruction::isSameOperationAs.
00707 // Read method declaration comments for more details.
00708 int FunctionComparator::cmpOperation(const Instruction *L,
00709                                      const Instruction *R) const {
00710   // Differences from Instruction::isSameOperationAs:
00711   //  * replace type comparison with calls to isEquivalentType.
00712   //  * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top
00713   //  * because of the above, we don't test for the tail bit on calls later on
00714   if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode()))
00715     return Res;
00716 
00717   if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands()))
00718     return Res;
00719 
00720   if (int Res = cmpType(L->getType(), R->getType()))
00721     return Res;
00722 
00723   if (int Res = cmpNumbers(L->getRawSubclassOptionalData(),
00724                            R->getRawSubclassOptionalData()))
00725     return Res;
00726 
00727   // We have two instructions of identical opcode and #operands.  Check to see
00728   // if all operands are the same type
00729   for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) {
00730     if (int Res =
00731             cmpType(L->getOperand(i)->getType(), R->getOperand(i)->getType()))
00732       return Res;
00733   }
00734 
00735   // Check special state that is a part of some instructions.
00736   if (const LoadInst *LI = dyn_cast<LoadInst>(L)) {
00737     if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile()))
00738       return Res;
00739     if (int Res =
00740             cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment()))
00741       return Res;
00742     if (int Res =
00743             cmpNumbers(LI->getOrdering(), cast<LoadInst>(R)->getOrdering()))
00744       return Res;
00745     if (int Res =
00746             cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope()))
00747       return Res;
00748     return cmpNumbers((uint64_t)LI->getMetadata(LLVMContext::MD_range),
00749                       (uint64_t)cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
00750   }
00751   if (const StoreInst *SI = dyn_cast<StoreInst>(L)) {
00752     if (int Res =
00753             cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile()))
00754       return Res;
00755     if (int Res =
00756             cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment()))
00757       return Res;
00758     if (int Res =
00759             cmpNumbers(SI->getOrdering(), cast<StoreInst>(R)->getOrdering()))
00760       return Res;
00761     return cmpNumbers(SI->getSynchScope(), cast<StoreInst>(R)->getSynchScope());
00762   }
00763   if (const CmpInst *CI = dyn_cast<CmpInst>(L))
00764     return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate());
00765   if (const CallInst *CI = dyn_cast<CallInst>(L)) {
00766     if (int Res = cmpNumbers(CI->getCallingConv(),
00767                              cast<CallInst>(R)->getCallingConv()))
00768       return Res;
00769     if (int Res =
00770             cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes()))
00771       return Res;
00772     return cmpNumbers(
00773         (uint64_t)CI->getMetadata(LLVMContext::MD_range),
00774         (uint64_t)cast<CallInst>(R)->getMetadata(LLVMContext::MD_range));
00775   }
00776   if (const InvokeInst *CI = dyn_cast<InvokeInst>(L)) {
00777     if (int Res = cmpNumbers(CI->getCallingConv(),
00778                              cast<InvokeInst>(R)->getCallingConv()))
00779       return Res;
00780     if (int Res =
00781             cmpAttrs(CI->getAttributes(), cast<InvokeInst>(R)->getAttributes()))
00782       return Res;
00783     return cmpNumbers(
00784         (uint64_t)CI->getMetadata(LLVMContext::MD_range),
00785         (uint64_t)cast<InvokeInst>(R)->getMetadata(LLVMContext::MD_range));
00786   }
00787   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) {
00788     ArrayRef<unsigned> LIndices = IVI->getIndices();
00789     ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices();
00790     if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
00791       return Res;
00792     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
00793       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
00794         return Res;
00795     }
00796   }
00797   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) {
00798     ArrayRef<unsigned> LIndices = EVI->getIndices();
00799     ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices();
00800     if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
00801       return Res;
00802     for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
00803       if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
00804         return Res;
00805     }
00806   }
00807   if (const FenceInst *FI = dyn_cast<FenceInst>(L)) {
00808     if (int Res =
00809             cmpNumbers(FI->getOrdering(), cast<FenceInst>(R)->getOrdering()))
00810       return Res;
00811     return cmpNumbers(FI->getSynchScope(), cast<FenceInst>(R)->getSynchScope());
00812   }
00813 
00814   if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(L)) {
00815     if (int Res = cmpNumbers(CXI->isVolatile(),
00816                              cast<AtomicCmpXchgInst>(R)->isVolatile()))
00817       return Res;
00818     if (int Res = cmpNumbers(CXI->isWeak(),
00819                              cast<AtomicCmpXchgInst>(R)->isWeak()))
00820       return Res;
00821     if (int Res = cmpNumbers(CXI->getSuccessOrdering(),
00822                              cast<AtomicCmpXchgInst>(R)->getSuccessOrdering()))
00823       return Res;
00824     if (int Res = cmpNumbers(CXI->getFailureOrdering(),
00825                              cast<AtomicCmpXchgInst>(R)->getFailureOrdering()))
00826       return Res;
00827     return cmpNumbers(CXI->getSynchScope(),
00828                       cast<AtomicCmpXchgInst>(R)->getSynchScope());
00829   }
00830   if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(L)) {
00831     if (int Res = cmpNumbers(RMWI->getOperation(),
00832                              cast<AtomicRMWInst>(R)->getOperation()))
00833       return Res;
00834     if (int Res = cmpNumbers(RMWI->isVolatile(),
00835                              cast<AtomicRMWInst>(R)->isVolatile()))
00836       return Res;
00837     if (int Res = cmpNumbers(RMWI->getOrdering(),
00838                              cast<AtomicRMWInst>(R)->getOrdering()))
00839       return Res;
00840     return cmpNumbers(RMWI->getSynchScope(),
00841                       cast<AtomicRMWInst>(R)->getSynchScope());
00842   }
00843   return 0;
00844 }
00845 
00846 // Determine whether two GEP operations perform the same underlying arithmetic.
00847 // Read method declaration comments for more details.
00848 int FunctionComparator::cmpGEP(const GEPOperator *GEPL,
00849                                const GEPOperator *GEPR) {
00850 
00851   unsigned int ASL = GEPL->getPointerAddressSpace();
00852   unsigned int ASR = GEPR->getPointerAddressSpace();
00853 
00854   if (int Res = cmpNumbers(ASL, ASR))
00855     return Res;
00856 
00857   // When we have target data, we can reduce the GEP down to the value in bytes
00858   // added to the address.
00859   if (DL) {
00860     unsigned BitWidth = DL->getPointerSizeInBits(ASL);
00861     APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0);
00862     if (GEPL->accumulateConstantOffset(*DL, OffsetL) &&
00863         GEPR->accumulateConstantOffset(*DL, OffsetR))
00864       return cmpAPInt(OffsetL, OffsetR);
00865   }
00866 
00867   if (int Res = cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
00868                            (uint64_t)GEPR->getPointerOperand()->getType()))
00869     return Res;
00870 
00871   if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
00872     return Res;
00873 
00874   for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
00875     if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
00876       return Res;
00877   }
00878 
00879   return 0;
00880 }
00881 
00882 /// Compare two values used by the two functions under pair-wise comparison. If
00883 /// this is the first time the values are seen, they're added to the mapping so
00884 /// that we will detect mismatches on next use.
00885 /// See comments in declaration for more details.
00886 int FunctionComparator::cmpValues(const Value *L, const Value *R) {
00887   // Catch self-reference case.
00888   if (L == FnL) {
00889     if (R == FnR)
00890       return 0;
00891     return -1;
00892   }
00893   if (R == FnR) {
00894     if (L == FnL)
00895       return 0;
00896     return 1;
00897   }
00898 
00899   const Constant *ConstL = dyn_cast<Constant>(L);
00900   const Constant *ConstR = dyn_cast<Constant>(R);
00901   if (ConstL && ConstR) {
00902     if (L == R)
00903       return 0;
00904     return cmpConstants(ConstL, ConstR);
00905   }
00906 
00907   if (ConstL)
00908     return 1;
00909   if (ConstR)
00910     return -1;
00911 
00912   const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L);
00913   const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R);
00914 
00915   if (InlineAsmL && InlineAsmR)
00916     return cmpNumbers((uint64_t)L, (uint64_t)R);
00917   if (InlineAsmL)
00918     return 1;
00919   if (InlineAsmR)
00920     return -1;
00921 
00922   auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())),
00923        RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size()));
00924 
00925   return cmpNumbers(LeftSN.first->second, RightSN.first->second);
00926 }
00927 // Test whether two basic blocks have equivalent behaviour.
00928 int FunctionComparator::compare(const BasicBlock *BBL, const BasicBlock *BBR) {
00929   BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
00930   BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
00931 
00932   do {
00933     if (int Res = cmpValues(InstL, InstR))
00934       return Res;
00935 
00936     const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(InstL);
00937     const GetElementPtrInst *GEPR = dyn_cast<GetElementPtrInst>(InstR);
00938 
00939     if (GEPL && !GEPR)
00940       return 1;
00941     if (GEPR && !GEPL)
00942       return -1;
00943 
00944     if (GEPL && GEPR) {
00945       if (int Res =
00946               cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand()))
00947         return Res;
00948       if (int Res = cmpGEP(GEPL, GEPR))
00949         return Res;
00950     } else {
00951       if (int Res = cmpOperation(InstL, InstR))
00952         return Res;
00953       assert(InstL->getNumOperands() == InstR->getNumOperands());
00954 
00955       for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
00956         Value *OpL = InstL->getOperand(i);
00957         Value *OpR = InstR->getOperand(i);
00958         if (int Res = cmpValues(OpL, OpR))
00959           return Res;
00960         if (int Res = cmpNumbers(OpL->getValueID(), OpR->getValueID()))
00961           return Res;
00962         // TODO: Already checked in cmpOperation
00963         if (int Res = cmpType(OpL->getType(), OpR->getType()))
00964           return Res;
00965       }
00966     }
00967 
00968     ++InstL, ++InstR;
00969   } while (InstL != InstLE && InstR != InstRE);
00970 
00971   if (InstL != InstLE && InstR == InstRE)
00972     return 1;
00973   if (InstL == InstLE && InstR != InstRE)
00974     return -1;
00975   return 0;
00976 }
00977 
00978 // Test whether the two functions have equivalent behaviour.
00979 int FunctionComparator::compare() {
00980 
00981   sn_mapL.clear();
00982   sn_mapR.clear();
00983 
00984   if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes()))
00985     return Res;
00986 
00987   if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC()))
00988     return Res;
00989 
00990   if (FnL->hasGC()) {
00991     if (int Res = cmpNumbers((uint64_t)FnL->getGC(), (uint64_t)FnR->getGC()))
00992       return Res;
00993   }
00994 
00995   if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection()))
00996     return Res;
00997 
00998   if (FnL->hasSection()) {
00999     if (int Res = cmpStrings(FnL->getSection(), FnR->getSection()))
01000       return Res;
01001   }
01002 
01003   if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg()))
01004     return Res;
01005 
01006   // TODO: if it's internal and only used in direct calls, we could handle this
01007   // case too.
01008   if (int Res = cmpNumbers(FnL->getCallingConv(), FnR->getCallingConv()))
01009     return Res;
01010 
01011   if (int Res = cmpType(FnL->getFunctionType(), FnR->getFunctionType()))
01012     return Res;
01013 
01014   assert(FnL->arg_size() == FnR->arg_size() &&
01015          "Identically typed functions have different numbers of args!");
01016 
01017   // Visit the arguments so that they get enumerated in the order they're
01018   // passed in.
01019   for (Function::const_arg_iterator ArgLI = FnL->arg_begin(),
01020                                     ArgRI = FnR->arg_begin(),
01021                                     ArgLE = FnL->arg_end();
01022        ArgLI != ArgLE; ++ArgLI, ++ArgRI) {
01023     if (cmpValues(ArgLI, ArgRI) != 0)
01024       llvm_unreachable("Arguments repeat!");
01025   }
01026 
01027   // We do a CFG-ordered walk since the actual ordering of the blocks in the
01028   // linked list is immaterial. Our walk starts at the entry block for both
01029   // functions, then takes each block from each terminator in order. As an
01030   // artifact, this also means that unreachable blocks are ignored.
01031   SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs;
01032   SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1.
01033 
01034   FnLBBs.push_back(&FnL->getEntryBlock());
01035   FnRBBs.push_back(&FnR->getEntryBlock());
01036 
01037   VisitedBBs.insert(FnLBBs[0]);
01038   while (!FnLBBs.empty()) {
01039     const BasicBlock *BBL = FnLBBs.pop_back_val();
01040     const BasicBlock *BBR = FnRBBs.pop_back_val();
01041 
01042     if (int Res = cmpValues(BBL, BBR))
01043       return Res;
01044 
01045     if (int Res = compare(BBL, BBR))
01046       return Res;
01047 
01048     const TerminatorInst *TermL = BBL->getTerminator();
01049     const TerminatorInst *TermR = BBR->getTerminator();
01050 
01051     assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
01052     for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
01053       if (!VisitedBBs.insert(TermL->getSuccessor(i)))
01054         continue;
01055 
01056       FnLBBs.push_back(TermL->getSuccessor(i));
01057       FnRBBs.push_back(TermR->getSuccessor(i));
01058     }
01059   }
01060   return 0;
01061 }
01062 
01063 namespace {
01064 
01065 /// MergeFunctions finds functions which will generate identical machine code,
01066 /// by considering all pointer types to be equivalent. Once identified,
01067 /// MergeFunctions will fold them by replacing a call to one to a call to a
01068 /// bitcast of the other.
01069 ///
01070 class MergeFunctions : public ModulePass {
01071 public:
01072   static char ID;
01073   MergeFunctions()
01074     : ModulePass(ID), HasGlobalAliases(false) {
01075     initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
01076   }
01077 
01078   bool runOnModule(Module &M) override;
01079 
01080 private:
01081   typedef std::set<FunctionPtr> FnTreeType;
01082 
01083   /// A work queue of functions that may have been modified and should be
01084   /// analyzed again.
01085   std::vector<WeakVH> Deferred;
01086 
01087   /// Checks the rules of order relation introduced among functions set.
01088   /// Returns true, if sanity check has been passed, and false if failed.
01089   bool doSanityCheck(std::vector<WeakVH> &Worklist);
01090 
01091   /// Insert a ComparableFunction into the FnTree, or merge it away if it's
01092   /// equal to one that's already present.
01093   bool insert(Function *NewFunction);
01094 
01095   /// Remove a Function from the FnTree and queue it up for a second sweep of
01096   /// analysis.
01097   void remove(Function *F);
01098 
01099   /// Find the functions that use this Value and remove them from FnTree and
01100   /// queue the functions.
01101   void removeUsers(Value *V);
01102 
01103   /// Replace all direct calls of Old with calls of New. Will bitcast New if
01104   /// necessary to make types match.
01105   void replaceDirectCallers(Function *Old, Function *New);
01106 
01107   /// Merge two equivalent functions. Upon completion, G may be deleted, or may
01108   /// be converted into a thunk. In either case, it should never be visited
01109   /// again.
01110   void mergeTwoFunctions(Function *F, Function *G);
01111 
01112   /// Replace G with a thunk or an alias to F. Deletes G.
01113   void writeThunkOrAlias(Function *F, Function *G);
01114 
01115   /// Replace G with a simple tail call to bitcast(F). Also replace direct uses
01116   /// of G with bitcast(F). Deletes G.
01117   void writeThunk(Function *F, Function *G);
01118 
01119   /// Replace G with an alias to F. Deletes G.
01120   void writeAlias(Function *F, Function *G);
01121 
01122   /// The set of all distinct functions. Use the insert() and remove() methods
01123   /// to modify it.
01124   FnTreeType FnTree;
01125 
01126   /// DataLayout for more accurate GEP comparisons. May be NULL.
01127   const DataLayout *DL;
01128 
01129   /// Whether or not the target supports global aliases.
01130   bool HasGlobalAliases;
01131 };
01132 
01133 }  // end anonymous namespace
01134 
01135 char MergeFunctions::ID = 0;
01136 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
01137 
01138 ModulePass *llvm::createMergeFunctionsPass() {
01139   return new MergeFunctions();
01140 }
01141 
01142 bool MergeFunctions::doSanityCheck(std::vector<WeakVH> &Worklist) {
01143   if (const unsigned Max = NumFunctionsForSanityCheck) {
01144     unsigned TripleNumber = 0;
01145     bool Valid = true;
01146 
01147     dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
01148 
01149     unsigned i = 0;
01150     for (std::vector<WeakVH>::iterator I = Worklist.begin(), E = Worklist.end();
01151          I != E && i < Max; ++I, ++i) {
01152       unsigned j = i;
01153       for (std::vector<WeakVH>::iterator J = I; J != E && j < Max; ++J, ++j) {
01154         Function *F1 = cast<Function>(*I);
01155         Function *F2 = cast<Function>(*J);
01156         int Res1 = FunctionComparator(DL, F1, F2).compare();
01157         int Res2 = FunctionComparator(DL, F2, F1).compare();
01158 
01159         // If F1 <= F2, then F2 >= F1, otherwise report failure.
01160         if (Res1 != -Res2) {
01161           dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
01162                  << "\n";
01163           F1->dump();
01164           F2->dump();
01165           Valid = false;
01166         }
01167 
01168         if (Res1 == 0)
01169           continue;
01170 
01171         unsigned k = j;
01172         for (std::vector<WeakVH>::iterator K = J; K != E && k < Max;
01173              ++k, ++K, ++TripleNumber) {
01174           if (K == J)
01175             continue;
01176 
01177           Function *F3 = cast<Function>(*K);
01178           int Res3 = FunctionComparator(DL, F1, F3).compare();
01179           int Res4 = FunctionComparator(DL, F2, F3).compare();
01180 
01181           bool Transitive = true;
01182 
01183           if (Res1 != 0 && Res1 == Res4) {
01184             // F1 > F2, F2 > F3 => F1 > F3
01185             Transitive = Res3 == Res1;
01186           } else if (Res3 != 0 && Res3 == -Res4) {
01187             // F1 > F3, F3 > F2 => F1 > F2
01188             Transitive = Res3 == Res1;
01189           } else if (Res4 != 0 && -Res3 == Res4) {
01190             // F2 > F3, F3 > F1 => F2 > F1
01191             Transitive = Res4 == -Res1;
01192           }
01193 
01194           if (!Transitive) {
01195             dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
01196                    << TripleNumber << "\n";
01197             dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
01198                    << Res4 << "\n";
01199             F1->dump();
01200             F2->dump();
01201             F3->dump();
01202             Valid = false;
01203           }
01204         }
01205       }
01206     }
01207 
01208     dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
01209     return Valid;
01210   }
01211   return true;
01212 }
01213 
01214 bool MergeFunctions::runOnModule(Module &M) {
01215   bool Changed = false;
01216   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
01217   DL = DLP ? &DLP->getDataLayout() : nullptr;
01218 
01219   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
01220     if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage())
01221       Deferred.push_back(WeakVH(I));
01222   }
01223 
01224   do {
01225     std::vector<WeakVH> Worklist;
01226     Deferred.swap(Worklist);
01227 
01228     DEBUG(doSanityCheck(Worklist));
01229 
01230     DEBUG(dbgs() << "size of module: " << M.size() << '\n');
01231     DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
01232 
01233     // Insert only strong functions and merge them. Strong function merging
01234     // always deletes one of them.
01235     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
01236            E = Worklist.end(); I != E; ++I) {
01237       if (!*I) continue;
01238       Function *F = cast<Function>(*I);
01239       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
01240           !F->mayBeOverridden()) {
01241         Changed |= insert(F);
01242       }
01243     }
01244 
01245     // Insert only weak functions and merge them. By doing these second we
01246     // create thunks to the strong function when possible. When two weak
01247     // functions are identical, we create a new strong function with two weak
01248     // weak thunks to it which are identical but not mergable.
01249     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
01250            E = Worklist.end(); I != E; ++I) {
01251       if (!*I) continue;
01252       Function *F = cast<Function>(*I);
01253       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
01254           F->mayBeOverridden()) {
01255         Changed |= insert(F);
01256       }
01257     }
01258     DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
01259   } while (!Deferred.empty());
01260 
01261   FnTree.clear();
01262 
01263   return Changed;
01264 }
01265 
01266 // Replace direct callers of Old with New.
01267 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
01268   Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
01269   for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
01270     Use *U = &*UI;
01271     ++UI;
01272     CallSite CS(U->getUser());
01273     if (CS && CS.isCallee(U)) {
01274       remove(CS.getInstruction()->getParent()->getParent());
01275       U->set(BitcastNew);
01276     }
01277   }
01278 }
01279 
01280 // Replace G with an alias to F if possible, or else a thunk to F. Deletes G.
01281 void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
01282   if (HasGlobalAliases && G->hasUnnamedAddr()) {
01283     if (G->hasExternalLinkage() || G->hasLocalLinkage() ||
01284         G->hasWeakLinkage()) {
01285       writeAlias(F, G);
01286       return;
01287     }
01288   }
01289 
01290   writeThunk(F, G);
01291 }
01292 
01293 // Helper for writeThunk,
01294 // Selects proper bitcast operation,
01295 // but a bit simpler then CastInst::getCastOpcode.
01296 static Value *createCast(IRBuilder<false> &Builder, Value *V, Type *DestTy) {
01297   Type *SrcTy = V->getType();
01298   if (SrcTy->isStructTy()) {
01299     assert(DestTy->isStructTy());
01300     assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
01301     Value *Result = UndefValue::get(DestTy);
01302     for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
01303       Value *Element = createCast(
01304           Builder, Builder.CreateExtractValue(V, ArrayRef<unsigned int>(I)),
01305           DestTy->getStructElementType(I));
01306 
01307       Result =
01308           Builder.CreateInsertValue(Result, Element, ArrayRef<unsigned int>(I));
01309     }
01310     return Result;
01311   }
01312   assert(!DestTy->isStructTy());
01313   if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
01314     return Builder.CreateIntToPtr(V, DestTy);
01315   else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
01316     return Builder.CreatePtrToInt(V, DestTy);
01317   else
01318     return Builder.CreateBitCast(V, DestTy);
01319 }
01320 
01321 // Replace G with a simple tail call to bitcast(F). Also replace direct uses
01322 // of G with bitcast(F). Deletes G.
01323 void MergeFunctions::writeThunk(Function *F, Function *G) {
01324   if (!G->mayBeOverridden()) {
01325     // Redirect direct callers of G to F.
01326     replaceDirectCallers(G, F);
01327   }
01328 
01329   // If G was internal then we may have replaced all uses of G with F. If so,
01330   // stop here and delete G. There's no need for a thunk.
01331   if (G->hasLocalLinkage() && G->use_empty()) {
01332     G->eraseFromParent();
01333     return;
01334   }
01335 
01336   Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
01337                                     G->getParent());
01338   BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
01339   IRBuilder<false> Builder(BB);
01340 
01341   SmallVector<Value *, 16> Args;
01342   unsigned i = 0;
01343   FunctionType *FFTy = F->getFunctionType();
01344   for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
01345        AI != AE; ++AI) {
01346     Args.push_back(createCast(Builder, (Value*)AI, FFTy->getParamType(i)));
01347     ++i;
01348   }
01349 
01350   CallInst *CI = Builder.CreateCall(F, Args);
01351   CI->setTailCall();
01352   CI->setCallingConv(F->getCallingConv());
01353   if (NewG->getReturnType()->isVoidTy()) {
01354     Builder.CreateRetVoid();
01355   } else {
01356     Builder.CreateRet(createCast(Builder, CI, NewG->getReturnType()));
01357   }
01358 
01359   NewG->copyAttributesFrom(G);
01360   NewG->takeName(G);
01361   removeUsers(G);
01362   G->replaceAllUsesWith(NewG);
01363   G->eraseFromParent();
01364 
01365   DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n');
01366   ++NumThunksWritten;
01367 }
01368 
01369 // Replace G with an alias to F and delete G.
01370 void MergeFunctions::writeAlias(Function *F, Function *G) {
01371   PointerType *PTy = G->getType();
01372   auto *GA = GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
01373                                  G->getLinkage(), "", F);
01374   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
01375   GA->takeName(G);
01376   GA->setVisibility(G->getVisibility());
01377   removeUsers(G);
01378   G->replaceAllUsesWith(GA);
01379   G->eraseFromParent();
01380 
01381   DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
01382   ++NumAliasesWritten;
01383 }
01384 
01385 // Merge two equivalent functions. Upon completion, Function G is deleted.
01386 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
01387   if (F->mayBeOverridden()) {
01388     assert(G->mayBeOverridden());
01389 
01390     if (HasGlobalAliases) {
01391       // Make them both thunks to the same internal function.
01392       Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
01393                                      F->getParent());
01394       H->copyAttributesFrom(F);
01395       H->takeName(F);
01396       removeUsers(F);
01397       F->replaceAllUsesWith(H);
01398 
01399       unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
01400 
01401       writeAlias(F, G);
01402       writeAlias(F, H);
01403 
01404       F->setAlignment(MaxAlignment);
01405       F->setLinkage(GlobalValue::PrivateLinkage);
01406     } else {
01407       // We can't merge them. Instead, pick one and update all direct callers
01408       // to call it and hope that we improve the instruction cache hit rate.
01409       replaceDirectCallers(G, F);
01410     }
01411 
01412     ++NumDoubleWeak;
01413   } else {
01414     writeThunkOrAlias(F, G);
01415   }
01416 
01417   ++NumFunctionsMerged;
01418 }
01419 
01420 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
01421 // that was already inserted.
01422 bool MergeFunctions::insert(Function *NewFunction) {
01423   std::pair<FnTreeType::iterator, bool> Result =
01424       FnTree.insert(FunctionPtr(NewFunction, DL));
01425 
01426   if (Result.second) {
01427     DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n');
01428     return false;
01429   }
01430 
01431   const FunctionPtr &OldF = *Result.first;
01432 
01433   // Don't merge tiny functions, since it can just end up making the function
01434   // larger.
01435   // FIXME: Should still merge them if they are unnamed_addr and produce an
01436   // alias.
01437   if (NewFunction->size() == 1) {
01438     if (NewFunction->front().size() <= 2) {
01439       DEBUG(dbgs() << NewFunction->getName()
01440                    << " is to small to bother merging\n");
01441       return false;
01442     }
01443   }
01444 
01445   // Never thunk a strong function to a weak function.
01446   assert(!OldF.getFunc()->mayBeOverridden() || NewFunction->mayBeOverridden());
01447 
01448   DEBUG(dbgs() << "  " << OldF.getFunc()->getName()
01449                << " == " << NewFunction->getName() << '\n');
01450 
01451   Function *DeleteF = NewFunction;
01452   mergeTwoFunctions(OldF.getFunc(), DeleteF);
01453   return true;
01454 }
01455 
01456 // Remove a function from FnTree. If it was already in FnTree, add
01457 // it to Deferred so that we'll look at it in the next round.
01458 void MergeFunctions::remove(Function *F) {
01459   // We need to make sure we remove F, not a function "equal" to F per the
01460   // function equality comparator.
01461   FnTreeType::iterator found = FnTree.find(FunctionPtr(F, DL));
01462   size_t Erased = 0;
01463   if (found != FnTree.end() && found->getFunc() == F) {
01464     Erased = 1;
01465     FnTree.erase(found);
01466   }
01467 
01468   if (Erased) {
01469     DEBUG(dbgs() << "Removed " << F->getName()
01470                  << " from set and deferred it.\n");
01471     Deferred.push_back(F);
01472   }
01473 }
01474 
01475 // For each instruction used by the value, remove() the function that contains
01476 // the instruction. This should happen right before a call to RAUW.
01477 void MergeFunctions::removeUsers(Value *V) {
01478   std::vector<Value *> Worklist;
01479   Worklist.push_back(V);
01480   while (!Worklist.empty()) {
01481     Value *V = Worklist.back();
01482     Worklist.pop_back();
01483 
01484     for (User *U : V->users()) {
01485       if (Instruction *I = dyn_cast<Instruction>(U)) {
01486         remove(I->getParent()->getParent());
01487       } else if (isa<GlobalValue>(U)) {
01488         // do nothing
01489       } else if (Constant *C = dyn_cast<Constant>(U)) {
01490         for (User *UU : C->users())
01491           Worklist.push_back(UU);
01492       }
01493     }
01494   }
01495 }