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