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