Improved MergeFunctions to merge similar functions

[hiraditya]

Please fix clang-tidy warnings.

[vish99]

Clang-tidy warnings fix

[hiraditya]

llvm/include/llvm/Transforms/Utils/FunctionComparator.h

493

Remove underscores and add camecase name.

[vish99]

Testcase fix

[vish99]

clang-format fix

llvm/include/llvm/Transforms/IPO.h

 /// createReversePostOrderFunctionAttrsPass - This pass walks SCCs of the call
 /// graph in RPO to deduce and propagate function attributes. Currently it
 /// only handles synthesizing norecurse attributes.
 ///
 Pass *createReversePostOrderFunctionAttrsPass();
 
 //===----------------------------------------------------------------------===//
 /// createMergeFunctionsPass - This pass discovers identical functions and
-/// collapses them.
+/// collapses them or merges similar functions if partial merging is enabled.
 ///
-ModulePass *createMergeFunctionsPass();
+ModulePass *createMergeFunctionsPass(bool doPartialMerging = false);
 
 //===----------------------------------------------------------------------===//
 /// createHotColdSplittingPass - This pass outlines cold blocks into a separate
 /// function(s).
 ModulePass *createHotColdSplittingPass();
 
 //===----------------------------------------------------------------------===//
 /// createPartialInliningPass - This pass inlines parts of functions.

llvm/include/llvm/Transforms/Utils/Cloning.h

 /// non-null.
 ///
 /// VMap contains no non-identity GlobalValue mappings and debug info metadata
 /// will not be cloned.
 ///
 Function *CloneFunction(Function *F, ValueToValueMapTy &VMap,
                         ClonedCodeInfo *CodeInfo = nullptr);
 
+/// Used to control @fn CloneFunctionInto.
+enum class CloneType {
+  InvalidCloneType,
+  /// Cloning will result in module level changes.
+  ModuleLevelChanges,
+  /// !ModuleLevelChanges, When no module level changes will be made to the
+  /// cloned function.
+  NoModuleLevelChanges,
+  /// Cloning will be used for extracting functions by passes like function
+  /// merging, it does not require module level changes but debug info needs
+  /// special treatment like: DISubprogram is not cloned.
+  ExtractingFunctions,
+};
+
 /// Clone OldFunc into NewFunc, transforming the old arguments into references
 /// to VMap values.  Note that if NewFunc already has basic blocks, the ones
 /// cloned into it will be added to the end of the function.  This function
 /// fills in a list of return instructions, and can optionally remap types
 /// and/or append the specified suffix to all values cloned.
 ///
 /// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue
 /// mappings.
 ///
 void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
-                       ValueToValueMapTy &VMap, bool ModuleLevelChanges,
-                       SmallVectorImpl<ReturnInst*> &Returns,
+                       ValueToValueMapTy &VMap, CloneType CT,
+                       SmallVectorImpl<ReturnInst *> &Returns,
                        const char *NameSuffix = "",
                        ClonedCodeInfo *CodeInfo = nullptr,
                        ValueMapTypeRemapper *TypeMapper = nullptr,
                        ValueMaterializer *Materializer = nullptr);
 
 void CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
                                const Instruction *StartingInst,
                                ValueToValueMapTy &VMap, bool ModuleLevelChanges,

llvm/include/llvm/Transforms/Utils/FunctionComparator.h

-//===- FunctionComparator.h - Function Comparator ---------------*- C++ -*-===//
+//===- PreciseFunctionComparator.h - Function Comparator ---------------*- C++
+//-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This file defines the FunctionComparator and GlobalNumberState classes which
-// are used by the MergeFunctions pass for comparing functions.
+// This file defines the PreciseFunctionComparator and GlobalNumberState classes
+// which are used by the MergeFunctions pass for comparing functions.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
-#define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
+#ifndef LLVM_TRANSFORMS_UTILS_FunctionComparator_H
+#define LLVM_TRANSFORMS_UTILS_FunctionComparator_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
 #include <cstdint>
+#include <list>
 #include <tuple>
+#include <vector>
 
 namespace llvm {
 
 class APFloat;
 class APInt;
 class BasicBlock;
 class Constant;
 class Function;
void erase(GlobalValue *Global) {
     GlobalNumbers.erase(Global);
   }
 
   void clear() {
     GlobalNumbers.clear();
   }
 };
 
-/// FunctionComparator - Compares two functions to determine whether or not
-/// they will generate machine code with the same behaviour. DataLayout is
+/// PreciseFunctionComparator - Compares two functions to determine whether or
+/// not they will generate machine code with the same behaviour. DataLayout is
 /// used if available. The comparator always fails conservatively (erring on the
 /// side of claiming that two functions are different).
-class FunctionComparator {
+class PreciseFunctionComparator {
 public:
-  FunctionComparator(const Function *F1, const Function *F2,
-                     GlobalNumberState* GN)
+  PreciseFunctionComparator(const Function *F1, const Function *F2,
+                            GlobalNumberState *GN)
       : FnL(F1), FnR(F2), GlobalNumbers(GN) {}
 
   /// Test whether the two functions have equivalent behaviour.
   int compare();
 
   /// Hash a function. Equivalent functions will have the same hash, and unequal
   /// functions will have different hashes with high probability.
   using FunctionHash = uint64_t;
private:
   /// Values that were met at same place will be with same serial numbers.
   /// In this case it would be good to explain few points about values assigned
   /// to BBs and other ways of implementation (see below).
   ///
   /// 1. Safety of BB reordering.
   /// It's safe to change the order of BasicBlocks in function.
   /// Relationship with other functions and serial numbering will not be
   /// changed in this case.
-  /// As follows from FunctionComparator::compare(), we do CFG walk: we start
-  /// from the entry, and then take each terminator. So it doesn't matter how in
-  /// fact BBs are ordered in function. And since cmpValues are called during
-  /// this walk, the numbering depends only on how BBs located inside the CFG.
-  /// So the answer is - yes. We will get the same numbering.
+  /// As follows from PreciseFunctionComparator::compare(), we do CFG walk: we
+  /// start from the entry, and then take each terminator. So it doesn't matter
+  /// how in fact BBs are ordered in function. And since cmpValues are called
+  /// during this walk, the numbering depends only on how BBs located inside the
+  /// CFG. So the answer is - yes. We will get the same numbering.
   ///
   /// 2. Impossibility to use dominance properties of values.
   /// If we compare two instruction operands: first is usage of local
   /// variable AL from function FL, and second is usage of local variable AR
   /// from FR, we could compare their origins and check whether they are
   /// defined at the same place.
   /// But, we are still not able to compare operands of PHI nodes, since those
   /// could be operands from further BBs we didn't scan yet.
   /// So it's impossible to use dominance properties in general.
   mutable DenseMap<const Value*, int> sn_mapL, sn_mapR;
 
   // The global state we will use
   GlobalNumberState* GlobalNumbers;
 };
 
+/// PartialFunctionComparator - Compares two functions to determine whether or
+/// not they are exavtly identical having with minute differences.
+class PartialFunctionComparator {
+public:
+  PartialFunctionComparator(const DataLayout *DL, Function *F1, Function *F2)
+      : isDifferent(false), isNotMergeable(false), BasicBlockCount(0),
+        InstructionCount(0), DifferingInstructionsCount(0), F1(F1), F2(F2),
+        SimilarityMetric(0), DL(DL), ID(CurID++) {}
+
+  ~PartialFunctionComparator() {}
+
+  /// Test whether the two functions have equivalent behaviour. Returns true if
+  /// they are equal or can be merged, false if not.
+  bool compare();
+
+  /// Indicate whether the two functions are an exact match after comparison
+  bool isExactMatch();
+
+  /// Indicate whether the two functions candidates for merging after comparison
+  bool isMergeCandidate();
+
+  /// Get a similarity metric between the two functions. Higher means more
+  /// similar.
+  unsigned getSimilarityMetric() {
+    if (!SimilarityMetric)
+      SimilarityMetric =
+          (unsigned)(((float)InstructionCount - DifferingInstructionsCount) /
+                     InstructionCount * 10000);
+    return SimilarityMetric;
+  }
+
+  Function *getF1() { return F1; }
+  Function *getF2() { return F2; }
+  ValueToValueMapTy &getF1toF2Map() { return id_map; }
+  ValueToValueMapTy &getF2toF1Map() { return seen_values; }
+  const DataLayout *getDataLayout() { return DL; }
+
+  /// Assign or look up previously assigned numbers for the two values, and
+  /// return whether the numbers are equal. Numbers are assigned in the order
+  /// visited. If NoSelfRef is set, F1 and F2 are not assigned to each other
+  /// (treated as 'equal').
+  bool enumerate(const Value *V1, const Value *V2, bool NoSelfRef = false);
+
+  /// Compare two Types, treating all pointer types as equal.
+  bool isEquivalentType(Type *Ty1, Type *Ty2) const;
+
+  /// Instructions that differ between the two functions (F1's -> F2's inst).
+  MapVector<const Instruction *, const Instruction *> DifferingInstructions;
+
+  /// Instructions that reference F1/F2 itself (recursive calls etc.)
+  /// These may need special treatment when merging differing functions.
+  MapVector<const Instruction *, const Instruction *> SelfRefInstructions;
+
+  /// Return the unique ID for the object.
+  unsigned getID() { return ID; }
+
+  bool isDifferent;
+  bool isNotMergeable;
+
+  // Comparison statistics
+  unsigned BasicBlockCount;
+  unsigned InstructionCount;
+  unsigned DifferingInstructionsCount;
+
+private:
+  /// Test whether two basic blocks have equivalent behaviour. Returns true if
+  /// they are equal or can be merged, false if not. PHINodes are not compared
+  /// in this function, but added to the PHIsFound list for delayed processing.
+  bool
+  compare(const BasicBlock *BB1, const BasicBlock *BB2,
+          std::list<std::pair<const PHINode *, const PHINode *>> *PHIsFound);
+
+  /// Compare pairs of PHI nodes. Returns true if all pairs are equal or can
+  /// be merged, false if not.
+  bool comparePHIs(
+      const std::list<std::pair<const PHINode *, const PHINode *>> &PHIs);
+
+  /// Compare two Instructions for equivalence, similar to
+  /// Instruction::isSameOperationAs but with modifications to the type
+  /// comparison.
+  bool isEquivalentOperation(const Instruction *I1,
+                             const Instruction *I2) const;
+
+  /// Compare two GEPs for equivalent pointer arithmetic.
+  bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2);
+  bool isEquivalentGEP(const GetElementPtrInst *GEP1,
+                       const GetElementPtrInst *GEP2) {
+    return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2));
+  }
+
+  // The two functions undergoing comparison.
+  Function *F1, *F2;
+
+  unsigned SimilarityMetric;
+
+  const DataLayout *DL;
+
+  ValueToValueMapTy id_map;
+  ValueToValueMapTy seen_values;
+
+  // Maintain a unique ID for each object.
+  static unsigned CurID;
+  unsigned ID;
+};
+
 } // end namespace llvm
 
-#endif // LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
+#endif // LLVM_TRANSFORMS_UTILS_FunctionComparator_H

llvm/lib/ExecutionEngine/Orc/IndirectionUtils.cpp

void moveFunctionBody(Function &OrigF, ValueToValueMapTy &VMap,
   else
     assert(VMap[&OrigF] == NewF && "Incorrect function mapping in VMap.");
   assert(NewF && "Function mapping missing from VMap.");
   assert(NewF->getParent() != OrigF.getParent() &&
          "moveFunctionBody should only be used to move bodies between "
          "modules.");
 
   SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
-  CloneFunctionInto(NewF, &OrigF, VMap, /*ModuleLevelChanges=*/true, Returns,
+  CloneFunctionInto(NewF, &OrigF, VMap, CloneType::ModuleLevelChanges, Returns,
                     "", nullptr, nullptr, Materializer);
   OrigF.deleteBody();
 }
 
 GlobalVariable* cloneGlobalVariableDecl(Module &Dst, const GlobalVariable &GV,
                                         ValueToValueMapTy *VMap) {
   GlobalVariable *NewGV = new GlobalVariable(
       Dst, GV.getValueType(), GV.isConstant(),

llvm/lib/Target/AMDGPU/R600OpenCLImageTypeLoweringPass.cpp

for (auto &Arg: F->args()) {
       NewFArgIt->setName(ArgName);
       VMap[&Arg] = &(*NewFArgIt++);
       if (IsImageType(ArgTypeFromMD(KernelMDNode, Arg.getArgNo()))) {
         (NewFArgIt++)->setName(Twine("__size_") + ArgName);
         (NewFArgIt++)->setName(Twine("__format_") + ArgName);
       }
     }
     SmallVector<ReturnInst*, 8> Returns;
-    CloneFunctionInto(NewF, F, VMap, /*ModuleLevelChanges=*/false, Returns);
+    CloneFunctionInto(NewF, F, VMap, CloneType::NoModuleLevelChanges, Returns);
 
     // Build new MDNode.
     SmallVector<Metadata *, 6> KernelMDArgs;
     KernelMDArgs.push_back(ConstantAsMetadata::get(NewF));
     for (unsigned i = 0; i < NumKernelArgMDNodes; ++i)
       KernelMDArgs.push_back(MDNode::get(*Context, NewArgMDs.ArgVector[i]));
     MDNode *NewMDNode = MDNode::get(*Context, KernelMDArgs);
 

llvm/lib/Transforms/Coroutines/CoroSplit.cpp

void CoroCloner::create() {
   auto savedDLLStorageClass = NewF->getDLLStorageClass();
 
   // NewF's linkage (which CloneFunctionInto does *not* change) might not
   // be compatible with the visibility of OrigF (which it *does* change),
   // so protect against that.
   auto savedLinkage = NewF->getLinkage();
   NewF->setLinkage(llvm::GlobalValue::ExternalLinkage);
 
-  CloneFunctionInto(NewF, &OrigF, VMap, /*ModuleLevelChanges=*/true, Returns);
+  CloneFunctionInto(NewF, &OrigF, VMap, CloneType::ModuleLevelChanges, Returns);
 
   NewF->setLinkage(savedLinkage);
   NewF->setVisibility(savedVisibility);
   NewF->setUnnamedAddr(savedUnnamedAddr);
   NewF->setDLLStorageClass(savedDLLStorageClass);
 
   auto &Context = NewF->getContext();
 

llvm/lib/Transforms/IPO/MergeFunctions.cpp

 // Simplest cross-reference case (fA <--> fB) was implemented in previous
 // versions of MergeFunctions, though it presented only in two function pairs
 // in test-suite (that counts >50k functions)
 // Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A)
 // could cover much more cases.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Transforms/IPO/MergeFunctions.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"

 #include "llvm/IR/ValueMap.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
-#include "llvm/Transforms/IPO/MergeFunctions.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/FunctionComparator.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <set>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mergefunc"
 
 STATISTIC(NumFunctionsMerged, "Number of functions merged");
 STATISTIC(NumThunksWritten, "Number of thunks generated");
 STATISTIC(NumAliasesWritten, "Number of aliases generated");
 STATISTIC(NumDoubleWeak, "Number of new functions created");
+STATISTIC(NumMultiMerged, "Number of multi-merged functions");
+STATISTIC(NumSimilarFunctionsMerged, "Number of similar functions merged");
 
 static cl::opt<unsigned> NumFunctionsForSanityCheck(
     "mergefunc-sanity",
     cl::desc("How many functions in module could be used for "
              "MergeFunctions pass sanity check. "
              "'0' disables this check. Works only with '-debug' key."),
     cl::init(0), cl::Hidden);
 
MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,
                       cl::desc("Preserve debug info in thunk when mergefunc "
                                "transformations are made."));
 
 static cl::opt<bool>
     MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden,
                           cl::init(false),
                           cl::desc("Allow mergefunc to create aliases"));
 
+static cl::opt<unsigned> MergeDifferingMinInsts(
+    "mergesimilarfunc-diff-min-insts", cl::Hidden, cl::init(15),
+    cl::desc("Min instructions required to try merging differing functions"));
+
+static cl::opt<unsigned> MergeMaxDiffering(
+    "mergesimilarfunc-max-diff", cl::Hidden, cl::init(8),
+    cl::desc("Maximum number of differing instructions allowed"));
+
+static cl::opt<unsigned> MergeMinSimilarity(
+    "mergesimilarfunc-min-similarity", cl::Hidden, cl::init(70),
+    cl::desc("Minimum percentage of similar instructions required"));
+
+static cl::opt<bool> OptPrintMerges("mergesimilarfunc-print-merges", cl::Hidden,
+                                    cl::init(false));
+
+cl::opt<bool> UseGlobalAliases(
+    "mergesimilarfunc-global-aliases", cl::Hidden, cl::init(false),
+    cl::desc("Enable writing alias by enabling global aliases"));
+
+cl::opt<unsigned> MergeMinInsts(
+    "mergesimilarfunc-min-insts", cl::Hidden, cl::init(4),
+    cl::desc("Min instructions required to even consider single block fns"));
+
+static const char *MERGED_SUFFIX = "__merged";
+
+void PrintMerges(const char *Desc, Function *Old, Function *New) {
+  if (OptPrintMerges) {
+    dbgs() << "=== [" << Desc << "] replacing " << Old->getName() << " with "
+           << New->getName() << "\n";
+  }
+}
+
+namespace Opt {
+static cl::opt<bool> EnableSimilarFunctionMerging(
+    "mergesimilarfunc", cl::init(false),
+    cl::desc("Enable merging of functions with minute differences"));
+
+// Minimize the name pollution caused by the enum values.
+enum MergeLevelEnum { none, size, all };
+static cl::opt<enum MergeLevelEnum> MergeLevel(
+    "mergesimilarfunc-level", cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Level of function merging:"), cl::init(size),
+    cl::values(clEnumVal(none, "function merging disabled"),
+               clEnumVal(size, "only try to merge functions that are optimized "
+                               "for size"),
+               clEnumVal(all, "attempt to merge all similar functions")));
+} // namespace Opt
+
+/// Returns the type id for a type to be hashed. We turn pointer types into
+/// integers here because the actual compare logic below considers pointers and
+/// integers of the same size as equal.
+static Type::TypeID getTypeIDForHash(Type *Ty) {
+  if (Ty->isPointerTy())
+    return Type::IntegerTyID;
+  return Ty->getTypeID();
+}
+
+/// Creates a hash-code for the function which is the same for any two
+/// functions that will compare equal, without looking at the instructions
+/// inside the function.
+static unsigned profileFunction(const Function *F) {
+  FunctionType *FTy = F->getFunctionType();
+
+  FoldingSetNodeID ID;
+  ID.AddInteger(F->size());
+  ID.AddInteger(F->getCallingConv());
+  ID.AddBoolean(F->hasGC());
+  ID.AddBoolean(F->isInterposable());
+  ID.AddBoolean(FTy->isVarArg());
+  ID.AddInteger(getTypeIDForHash(FTy->getReturnType()));
+  for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
+    ID.AddInteger(getTypeIDForHash(FTy->getParamType(i)));
+  return ID.ComputeHash();
+}
+
+/// Insert function NewF into module, placing it immediately after the
+/// existing function PredF. If PredF does not exist, insert at the end.
+static void insertFunctionAfter(Function *NewF, Function *PredF) {
+  Module *M = PredF->getParent();
+  Module::FunctionListType &FList = M->getFunctionList();
+
+  for (Module::FunctionListType::iterator I = FList.begin(), E = FList.end();
+       I != E; ++I) {
+    if (PredF == &*I) {
+      FList.insertAfter(I, NewF);
+      return;
+    }
+  }
+
+  // Couldn't find PredF, insert at end
+  FList.push_back(NewF);
+}
+
+/// Create a cast instruction if needed to cast V to type DstType. We treat
+/// pointer and integer types of the same bitwidth as equivalent, so this can be
+/// used to cast them to each other where needed. The function returns the Value
+/// itself if no cast is needed, or a new CastInst instance inserted before
+/// InsertBefore. The integer type equivalent to pointers must be passed as
+/// IntPtrType (get it from DataLayout). This is guaranteed to generate no-op
+/// casts, otherwise it will assert.
+static Value *createCastIfNeeded(Value *V, Type *DstType, Value *InstrOrBB,
+                                 Type *IntPtrType) {
+  if (V->getType() == DstType)
+    return V;
+
+  BasicBlock *InsertAtEnd = dyn_cast<BasicBlock>(InstrOrBB);
+  Instruction *InsertBefore = dyn_cast<Instruction>(InstrOrBB);
+  BasicBlock *InsertBB = InsertAtEnd ? InsertAtEnd : InsertBefore->getParent();
+
+  CastInst *Result;
+  Type *OrigType = V->getType();
+
+  if (OrigType->isStructTy()) {
+    assert(DstType->isStructTy());
+    assert(OrigType->getStructNumElements() == DstType->getStructNumElements());
+
+    IRBuilder<> Builder(InsertBB);
+    if (InsertBefore)
+      Builder.SetInsertPoint(InsertBefore);
+    Value *Result = UndefValue::get(DstType);
+    for (unsigned int I = 0, E = OrigType->getStructNumElements(); I < E; ++I) {
+      Value *ExtractedValue =
+          Builder.CreateExtractValue(V, ArrayRef<unsigned int>(I));
+      Value *Element =
+          createCastIfNeeded(ExtractedValue, DstType->getStructElementType(I),
+                             InstrOrBB, IntPtrType);
+      Result =
+          Builder.CreateInsertValue(Result, Element, ArrayRef<unsigned int>(I));
+    }
+    return Result;
+  }
+  assert(!DstType->isStructTy());
+
+  if (OrigType->isPointerTy() &&
+      (DstType->isIntegerTy() || DstType->isPointerTy())) {
+    if (InsertBefore)
+      Result = CastInst::CreatePointerCast(V, DstType, "", InsertBefore);
+    else
+      Result = CastInst::CreatePointerCast(V, DstType, "", InsertAtEnd);
+  } else if (OrigType->isIntegerTy() && DstType->isPointerTy() &&
+             OrigType == IntPtrType) {
+    // Int -> Ptr
+    if (InsertBefore) {
+      Result =
+          CastInst::Create(CastInst::IntToPtr, V, DstType, "", InsertBefore);
+    } else {
+      Result =
+          CastInst::Create(CastInst::IntToPtr, V, DstType, "", InsertAtEnd);
+    }
+  } else {
+    llvm_unreachable("Can only cast int -> ptr or ptr -> (ptr or int)");
+  }
+
+  assert(cast<CastInst>(Result)->isNoopCast(IntPtrType) &&
+         "Cast is not a no-op cast. Potential loss of precision");
+
+  return Result;
+}
+
+/// Replace Inst1 by a switch statement that executes Inst1 or one of Inst2s
+/// depending on the value of SwitchVal. If a value in Inst2s is NULL, it
+/// defaults to executing Inst1. Returns set of terminator instructions of newly
+/// created switch blocks in Ret.
+///
+/// For instance, the transformation may look as follows:
+///         ...Head...
+///           Inst1           with all of Insts2s without parents
+///         ...Tail...
+///  into
+///         ...Head...
+///           Switch
+///         /     |       \                    .
+///    (default) (1)       (2)
+///      Inst1   Inst2s[0] Inst2s[1]
+///     Ret[0]   Ret[1]    Ret[2]
+///        \      |       /
+///         ...Tail...
+///
+static void SplitBlockAndInsertSwitch(Value *SwitchVal, Instruction *Inst1,
+                                      SmallVectorImpl<Instruction *> &Inst2s,
+                                      SmallVectorImpl<Instruction *> &Ret) {
+  // Split block
+  BasicBlock *Head = Inst1->getParent();
+  BasicBlock *Tail = Head->splitBasicBlock(Inst1);
+
+  // Create default block
+  LLVMContext &C = Head->getContext();
+  BasicBlock *DefaultBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
+
+  // Insert switch instruction at end of Head
+  Instruction *HeadOldTerm = Head->getTerminator();
+  SwitchInst *Switch =
+      SwitchInst::Create(SwitchVal, DefaultBlock, Inst2s.size());
+  ReplaceInstWithInst(HeadOldTerm, Switch);
+
+  // Move instructions into the blocks
+  if (Inst1->isTerminator()) {
+    Inst1->removeFromParent();
+    DefaultBlock->getInstList().push_back(Inst1);
+    Ret.push_back(cast<Instruction>(Inst1));
+  } else {
+    Instruction *DefaultTerm = BranchInst::Create(Tail, DefaultBlock);
+    Inst1->moveBefore(DefaultTerm);
+    Ret.push_back(DefaultTerm);
+  }
+
+  for (unsigned InstPos = 0, InstNum = Inst2s.size(); InstPos < InstNum;
+       ++InstPos) {
+    Instruction *Inst2 = Inst2s[InstPos];
+    if (!Inst2) {
+      Ret.push_back(NULL);
+      continue;
+    }
+
+    BasicBlock *CaseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
+
+    // Update the debug information of the merged instruction by marking it as
+    // 'inlined' at this location. If only Inst1 or Inst2 has debug
+    // information, we try to do something sensible that won't break the
+    // verifier.
+    if (Inst1->getDebugLoc()) {
+      if (Inst2->getDebugLoc()) {
+        const DebugLoc &I2Loc = Inst2->getDebugLoc();
+        Inst2->setDebugLoc(
+            DebugLoc::get(I2Loc.getLine(), I2Loc.getCol(), I2Loc.getScope(),
+                          /*InlinedAt*/ Inst1->getDebugLoc().getAsMDNode()));
+      } else {
+        Inst2->setDebugLoc(Inst1->getDebugLoc());
+      }
+    } else if (Inst2->getDebugLoc()) {
+      Inst2->setDebugLoc(DebugLoc());
+    }
+
+    if (Inst2->isTerminator()) {
+      assert(Inst1->isTerminator() &&
+             "Inst1 and Inst2 must both be terminators or non-terminators!");
+      CaseBlock->getInstList().push_back(Inst2);
+      Ret.push_back(cast<Instruction>(Inst2));
+    } else {
+      Instruction *CaseTerm = BranchInst::Create(Tail, CaseBlock);
+      Inst2->insertBefore(CaseTerm);
+      Ret.push_back(CaseTerm);
+    }
+
+    Switch->addCase(
+        ConstantInt::get(cast<IntegerType>(SwitchVal->getType()), InstPos + 1),
+        CaseBlock);
+  }
+
+  // If Inst1 (and Inst2s) are Terminator Inst's, Tail will be empty and can be
+  // deleted now. We also need to update PHI nodes to add the additional
+  // incoming blocks from the SwitchInst.
+  if (Inst1->isTerminator()) {
+    for (succ_iterator I = succ_begin(DefaultBlock), E = succ_end(DefaultBlock);
+         I != E; ++I) {
+      BasicBlock *Successor = *I;
+      PHINode *Phi;
+
+      for (BasicBlock::iterator II = Successor->begin();
+           (Phi = dyn_cast<PHINode>(II)); ++II)
+        for (unsigned ValId = 0, ValEnd = Phi->getNumIncomingValues();
+             ValId != ValEnd; ++ValId)
+          if (Phi->getIncomingBlock(ValId) == Tail) {
+            Phi->setIncomingBlock(ValId, DefaultBlock);
+            SmallVectorImpl<Instruction *>::iterator SwitchI = Ret.begin(),
+                                                     SwitchE = Ret.end();
+            for (++SwitchI; SwitchI != SwitchE; ++SwitchI) {
+              if (!*SwitchI)
+                continue;
+              Phi->addIncoming(Phi->getIncomingValue(ValId),
+                               (*SwitchI)->getParent());
+            }
+          }
+    }
+
+    Tail->eraseFromParent();
+  }
+}
+
+/// Returns true if the functions being compared can be merged as per
+/// PartialFunctionComparator else checks if the functions can be merged as per
+/// the heuristics
+bool isMergeCandidate(PartialFunctionComparator *Comp) {
+  if (Comp->isNotMergeable)
+    return false;
+
+  if (!Comp->isDifferent)
+    return true;
+
+  if (Comp->InstructionCount > MergeDifferingMinInsts &&
+      Comp->DifferingInstructionsCount <= MergeMaxDiffering &&
+      Comp->getSimilarityMetric() > MergeMinSimilarity)
+    return true;
+
+  return Comp->isMergeCandidate();
+}
+
 namespace {
 
 class FunctionNode {
   mutable AssertingVH<Function> F;
-  FunctionComparator::FunctionHash Hash;
+  PreciseFunctionComparator::FunctionHash Hash;
 
 public:
   // Note the hash is recalculated potentially multiple times, but it is cheap.
   FunctionNode(Function *F)
-    : F(F), Hash(FunctionComparator::functionHash(*F))  {}
+      : F(F), Hash(PreciseFunctionComparator::functionHash(*F)) {}
 
   Function *getFunc() const { return F; }
-  FunctionComparator::FunctionHash getHash() const { return Hash; }
+  PreciseFunctionComparator::FunctionHash getHash() const { return Hash; }
 
   /// Replace the reference to the function F by the function G, assuming their
   /// implementations are equal.
   void replaceBy(Function *G) const {
     F = G;
   }
 };
 
private:
 
   public:
     FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
 
     bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
       // Order first by hashes, then full function comparison.
       if (LHS.getHash() != RHS.getHash())
         return LHS.getHash() < RHS.getHash();
-      FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
+      PreciseFunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(),
+                                     GlobalNumbers);
       return FCmp.compare() == -1;
     }
   };
   using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
 
   GlobalNumberState GlobalNumbers;
 
   /// A work queue of functions that may have been modified and should be
#endif
   // Map functions to the iterators of the FunctionNode which contains them
   // in the FnTree. This must be updated carefully whenever the FnTree is
   // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
   // dangling iterators into FnTree. The invariant that preserves this is that
   // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
   DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
 };
 
+/// ComparableFunction - A struct that pairs together functions with a
+/// DataLayout so that we can keep them together as elements in the DenseSet.
+class ComparableFunction {
+public:
+  ComparableFunction() : Func(0), IsNew(false) {}
+
+  ComparableFunction(const ComparableFunction &that)
+      : Func(that.Func), IsNew(that.IsNew) {}
+
+  ComparableFunction(Function *Func) : Func(Func), IsNew(true) {}
+
+  ~ComparableFunction() {}
+
+  ComparableFunction &operator=(const ComparableFunction &that) {
+    Func = that.Func;
+    IsNew = that.IsNew;
+    return *this;
+  }
+
+  Function *getFunc() const { return Func; }
+  bool isNew() const { return IsNew; }
+
+  // Drops AssertingVH reference to the function. Outside of debug mode, this
+  // does nothing.
+  void release() {
+    assert(Func &&
+           "Attempted to release function twice, or release empty/tombstone!");
+    Func = NULL;
+  }
+
+  void markCompared() { IsNew = false; }
+
+private:
+  AssertingVH<Function> Func;
+  bool IsNew;
+};
+
+struct PartialFunctionComparatorOrdering {
+  bool operator()(PartialFunctionComparator *LHS,
+                  PartialFunctionComparator *RHS) const {
+    unsigned MetricLHS = LHS->getSimilarityMetric(),
+             MetricRHS = RHS->getSimilarityMetric();
+
+    // If the metric is the same, then default to the unique ID. We need
+    // to use a unique value instead of the object address to ensure
+    // deterministic ordering.
+    if (MetricLHS == MetricRHS)
+      return LHS->getID() > RHS->getID();
+    return MetricLHS > MetricRHS;
+  }
+};
+
+class MergeRegistry {
+public:
+  typedef MapVector<unsigned, std::list<ComparableFunction>> FnCompareMap;
+  typedef std::set<PartialFunctionComparator *,
+                   PartialFunctionComparatorOrdering>
+      FnComparatorSet;
+  typedef std::map<Function *, FnComparatorSet> SimilarFnMap;
+
+  ~MergeRegistry();
+
+  void clear();
+
+  /// Defer a function for consideration in the next round.
+  void defer(Function *F);
+
+  /// Return true if we have deferred functions that can be enqueued.
+  bool haveDeferred() { return !Deferred.empty(); }
+
+  /// Move all the deferred functions into buckets to consider them for merging.
+  /// Returns number of functions that have been added.
+  unsigned enqueue();
+
+  /// Add a candidate for merging
+  void insertCandidate(PartialFunctionComparator *Comp);
+
+  /// Remove a Function from the FnSet and queue it up for a second sweep of
+  /// analysis if Reanalyze is set. If it is a candidate for merging, remove it
+  /// from consideration.
+  void remove(Function *F, bool Reanalyze = true);
+
+  /// Return the similarity metric of the most similar function to F that is
+  /// not listed in the Ignore set.
+  unsigned getMaxSimilarity(Function *F, const DenseSet<Function *> &Ignore);
+
+  /// The collection of buckets that contain functions that may be similar to
+  /// each other (same hash value).
+  FnCompareMap FunctionsToCompare;
+
+  std::list<PartialFunctionComparator *> FunctionsToMerge;
+  SimilarFnMap SimilarFunctions;
+
+private:
+  typedef std::vector<WeakVH> FnDeferredQueue;
+
+  /// A work queue of functions that may have been modified and should be
+  /// analyzed again.
+  FnDeferredQueue Deferred;
+};
+
+class MergeSimilarFunctions {
+public:
+  // static char ID;
+  MergeSimilarFunctions(const ModuleSummaryIndex *Summary = nullptr) {}
+  /*
+    : ModulePass(ID) {
+    initializeMergeSimilarFunctionsPass(*PassRegistry::getPassRegistry());
+  }
+  */
+  bool runOnModule(Module &M);
+
+private:
+  /// Find the functions that use this Value and remove them from FnSet and
+  /// queue the functions.
+  void removeUsers(Value *V);
+
+  /// Replace all direct calls of Old with calls of New. Will bitcast New if
+  /// necessary to make types match.
+  void replaceDirectCallers(Function *Old, Function *New);
+
+  /// Process functions in the specified bucket, by either doing equiv merging
+  /// marking them for diff merging. Returns false if the bucket needs to be
+  /// re-scanned after an equiv merge. Sets Changed if the module was changed by
+  /// equiv merge.
+  bool mergeBucket(std::list<ComparableFunction> &Fns, bool &Changed);
+
+  /// Exhaustively compare all functions in each bucket and do equiv merging
+  /// where possible. Functions that have already been compared will not be
+  /// compared again. Returns true if the module was modified.
+  bool doExhaustiveCompareMerge();
+
+  /// Merge all the functions marked for diff merging. Returns true if the
+  /// module was modified.
+  bool doDiffMerge();
+
+  /// Merge two equivalent functions. Upon completion, G may be deleted, or may
+  /// be converted into a thunk. In either case, it should never be visited
+  /// again.
+  void mergeTwoFunctions(Function *F, Function *G);
+
+  /// Merge a set of functions with differences.
+  void
+  outlineAndMergeFunctions(SmallVectorImpl<PartialFunctionComparator *> &Fns);
+
+  /// Replace G with a thunk or an alias to F. Deletes G.
+  void writeThunkOrAlias(Function *F, Function *G);
+
+  /// Replace G with a simple tail call to bitcast(F). Also replace direct uses
+  /// of G with bitcast(F). Deletes G.
+  void writeThunk(Function *F, Function *G);
+
+  /// Replace G with a tail call to F with an additional argument.
+  void writeThunkWithChoice(Function *NewF, Function *OldF, int Choice);
+
+  /// Replace G with an alias to F. Deletes G.
+  void writeAlias(Function *F, Function *G);
+
+  /// DataLayout for more accurate GEP comparisons. May be NULL.
+  const DataLayout *DL;
+
+  /// Merge registry. Stores all the information about functions being
+  /// considered for merging as well as current candidates for merging.
+  MergeRegistry Registry;
+};
+
 class MergeFunctionsLegacyPass : public ModulePass {
 public:
   static char ID;
+  bool doPartialMerging;
 
-  MergeFunctionsLegacyPass(): ModulePass(ID) {
+  MergeFunctionsLegacyPass(bool doPartialMerging = false)
+      : ModulePass(ID), doPartialMerging(doPartialMerging) {
     initializeMergeFunctionsLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M) override {
     if (skipModule(M))
       return false;
 
+    if (!doPartialMerging && !Opt::EnableSimilarFunctionMerging) {
       MergeFunctions MF;
       return MF.runOnModule(M);
+    } else {
+      MergeSimilarFunctions MSF;
+      return MSF.runOnModule(M);
+    }
   }
 };
 
 } // end anonymous namespace
 
 char MergeFunctionsLegacyPass::ID = 0;
 INITIALIZE_PASS(MergeFunctionsLegacyPass, "mergefunc",
                 "Merge Functions", false, false)
 
-ModulePass *llvm::createMergeFunctionsPass() {
-  return new MergeFunctionsLegacyPass();
+ModulePass *llvm::createMergeFunctionsPass(bool doPartialMerging) {
+  return new MergeFunctionsLegacyPass(doPartialMerging);
 }
 
 PreservedAnalyses MergeFunctionsPass::run(Module &M,
                                           ModuleAnalysisManager &AM) {
   MergeFunctions MF;
   if (!MF.runOnModule(M))
     return PreservedAnalyses::all();
   return PreservedAnalyses::none();
if (const unsigned Max = NumFunctionsForSanityCheck) {
     for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),
                                                E = Worklist.end();
          I != E && i < Max; ++I, ++i) {
       unsigned j = i;
       for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;
            ++J, ++j) {
         Function *F1 = cast<Function>(*I);
         Function *F2 = cast<Function>(*J);
-        int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
-        int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
+        int Res1 = PreciseFunctionComparator(F1, F2, &GlobalNumbers).compare();
+        int Res2 = PreciseFunctionComparator(F2, F1, &GlobalNumbers).compare();
 
         // If F1 <= F2, then F2 >= F1, otherwise report failure.
         if (Res1 != -Res2) {
           dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
                  << "\n";
           dbgs() << *F1 << '\n' << *F2 << '\n';
           Valid = false;
         }
 
         if (Res1 == 0)
           continue;
 
         unsigned k = j;
         for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;
              ++k, ++K, ++TripleNumber) {
           if (K == J)
             continue;
 
           Function *F3 = cast<Function>(*K);
-          int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
-          int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();
+          int Res3 =
+              PreciseFunctionComparator(F1, F3, &GlobalNumbers).compare();
+          int Res4 =
+              PreciseFunctionComparator(F2, F3, &GlobalNumbers).compare();
 
           bool Transitive = true;
 
           if (Res1 != 0 && Res1 == Res4) {
             // F1 > F2, F2 > F3 => F1 > F3
             Transitive = Res3 == Res1;
           } else if (Res3 != 0 && Res3 == -Res4) {
             // F1 > F3, F3 > F2 => F1 > F2
static bool isEligibleForMerging(Function &F) {
   return !F.isDeclaration() && !F.hasAvailableExternallyLinkage();
 }
 
 bool MergeFunctions::runOnModule(Module &M) {
   bool Changed = false;
 
   // All functions in the module, ordered by hash. Functions with a unique
   // hash value are easily eliminated.
-  std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
+  std::vector<std::pair<PreciseFunctionComparator::FunctionHash, Function *>>
       HashedFuncs;
   for (Function &Func : M) {
     if (isEligibleForMerging(Func)) {
-      HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func});
+      HashedFuncs.push_back(
+          {PreciseFunctionComparator::functionHash(Func), &Func});
     }
   }
 
   llvm::stable_sort(HashedFuncs, less_first());
 
   auto S = HashedFuncs.begin();
   for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
     // If the hash value matches the previous value or the next one, we must
if (F->isInterposable()) {
     }
   }
 }
 
 /// Replace function F by function G.
 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
                                            Function *G) {
   Function *F = FN.getFunc();
-  assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
+  assert(PreciseFunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
          "The two functions must be equal");
 
   auto I = FNodesInTree.find(F);
   assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
   assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
 
   FnTreeType::iterator IterToFNInFnTree = I->second;
   assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
   // Remove F -> FN and insert G -> FN
   FNodesInTree.erase(I);
   FNodesInTree.insert({G, IterToFNInFnTree});
   // Replace F with G in FN, which is stored inside the FnTree.
   FN.replaceBy(G);
 }
 
-// Ordering for functions that are equal under FunctionComparator
+// Ordering for functions that are equal under PreciseFunctionComparator
 static bool isFuncOrderCorrect(const Function *F, const Function *G) {
   if (F->isInterposable() != G->isInterposable()) {
     // Strong before weak, because the weak function may call the strong
     // one, but not the other way around.
     return !F->isInterposable();
   }
   if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
     // External before local, because we definitely have to keep the external

 
 // For each instruction used by the value, remove() the function that contains
 // the instruction. This should happen right before a call to RAUW.
 void MergeFunctions::removeUsers(Value *V) {
   for (User *U : V->users())
     if (auto *I = dyn_cast<Instruction>(U))
       remove(I->getFunction());
 }
+
+MergeRegistry::~MergeRegistry() { this->clear(); }
+
+void MergeRegistry::clear() {
+  Deferred.clear();
+  SimilarFunctions.clear();
+  for (std::list<PartialFunctionComparator *>::iterator
+           I = FunctionsToMerge.begin(),
+           E = FunctionsToMerge.end();
+       I != E; ++I) {
+    PartialFunctionComparator *FC = *I;
+    delete FC;
+  }
+  FunctionsToMerge.clear();
+  FunctionsToCompare.clear();
+}
+
+static bool isAliasCapable(Function *G) {
+  return UseGlobalAliases && G->hasGlobalUnnamedAddr() &&
+         (G->hasExternalLinkage() || G->hasLocalLinkage() ||
+          G->hasWeakLinkage());
+}
+
+static bool isComparisonCandidate(Function *F) {
+  if (Opt::MergeLevel == Opt::size) {
+    // Only consider functions that are to be optimized for size.
+    // By default, that is all functions at -Os/-Oz and nothing at -O2.
+    bool Os = F->getAttributes().hasAttribute(AttributeList::FunctionIndex,
+                                              Attribute::OptimizeForSize);
+    bool Oz = F->getAttributes().hasAttribute(AttributeList::FunctionIndex,
+                                              Attribute::MinSize);
+    if (!Os && !Oz)
+      return false;
+  }
+
+  // Ignore declarations and tiny functions - no point in merging those
+  if (F->isDeclaration())
+    return false;
+  if (F->getName().endswith(MERGED_SUFFIX))
+    return false;
+  if (F->hasAvailableExternallyLinkage())
+    return false;
+  if (F->hasFnAttribute(Attribute::AlwaysInline))
+    return false;
+  if (F->size() == 1 && F->begin()->size() < MergeMinInsts)
+    return isAliasCapable(F);
+
+  return true;
+}
+
+void MergeRegistry::defer(Function *F) {
+  if (isComparisonCandidate(F))
+    Deferred.push_back(F);
+}
+
+// Move functions from Deferred into buckets. remove() may have been called
+// multiple times for the same function, so eliminate duplicates using the
+// set. We reverse them because MergeSimilarFunctions::insert inserts at the
+// front of each bucket.
+unsigned MergeRegistry::enqueue() {
+  DenseSet<Function *> InsertedFuncs;
+
+  for (std::vector<WeakVH>::reverse_iterator DefI = Deferred.rbegin(),
+                                             DefE = Deferred.rend();
+       DefI != DefE; ++DefI) {
+    Value *V = *DefI;
+    Function *F = dyn_cast_or_null<Function>(V);
+    if (!F)
+      continue;
+    if (InsertedFuncs.find(F) != InsertedFuncs.end())
+      continue;
+    if (!isComparisonCandidate(F))
+      continue;
+
+    unsigned Hash = profileFunction(F);
+    FunctionsToCompare[Hash].push_front(F);
+
+    InsertedFuncs.insert(F);
+  }
+
+  Deferred.clear();
+
+  return InsertedFuncs.size();
+}
+
+void MergeRegistry::insertCandidate(PartialFunctionComparator *Comp) {
+  FunctionsToMerge.push_back(Comp);
+  SimilarFunctions[Comp->getF1()].insert(Comp);
+}
+
+static void removeFromBucket(Function *F,
+                             std::list<ComparableFunction> &Bucket) {
+  for (std::list<ComparableFunction>::iterator I = Bucket.begin(),
+                                               E = Bucket.end();
+       I != E; ++I) {
+    if (I->getFunc() == F) {
+      Bucket.erase(I);
+      return;
+    }
+  }
+}
+
+void MergeRegistry::remove(Function *F, bool Reanalyze /*=true*/) {
+  // There is no need to remove a function that is not already
+  // in a bucket.
+  if (!isComparisonCandidate(F))
+    return;
+
+  unsigned Hash = profileFunction(F);
+  std::list<ComparableFunction> &Bucket = FunctionsToCompare[Hash];
+
+  removeFromBucket(F, Bucket);
+
+  if (Reanalyze)
+    Deferred.push_back(F);
+
+  // Check whether we have any existing PartialFunctionComparator objects for
+  // this fn. If yes, discard them because F has changed. Retry merging for
+  // those functions by adding them to Deferred.
+  std::list<PartialFunctionComparator *>::iterator I = FunctionsToMerge.begin();
+  while (I != FunctionsToMerge.end()) {
+    PartialFunctionComparator *Comp = *I;
+    if (Comp->getF1() == F) {
+      Function *OtherF = Comp->getF2();
+      Deferred.push_back(OtherF);
+      removeFromBucket(OtherF, Bucket);
+      if (!SimilarFunctions[F].erase(Comp))
+        llvm_unreachable("Inconsistent SimilarFunctions set");
+      I = FunctionsToMerge.erase(I);
+      delete Comp;
+    } else if (Comp->getF2() == F) {
+      Function *OtherF = Comp->getF1();
+      Deferred.push_back(OtherF);
+      removeFromBucket(OtherF, Bucket);
+      if (!SimilarFunctions[OtherF].erase(Comp))
+        llvm_unreachable("Inconsistent SimilarFunctions set");
+      I = FunctionsToMerge.erase(I);
+      delete Comp;
+    } else {
+      ++I;
+    }
+  }
+}
+
+unsigned MergeRegistry::getMaxSimilarity(Function *F,
+                                         const DenseSet<Function *> &Ignore) {
+  FnComparatorSet &Similar = SimilarFunctions[F];
+
+  for (FnComparatorSet::iterator I = Similar.begin(), E = Similar.end(); I != E;
+       ++I) {
+    PartialFunctionComparator *Comp = *I;
+    if (Ignore.count(Comp->getF2()))
+      continue;
+
+    return Comp->getSimilarityMetric();
+  }
+
+  return 0;
+}
+
+bool MergeSimilarFunctions::runOnModule(Module &M) {
+  if (Opt::MergeLevel == Opt::none)
+    return false;
+
+  bool Changed = false;
+
+  DL = &M.getDataLayout();
+
+  for (auto &I : M)
+    Registry.defer(&I);
+
+  do {
+    unsigned InsertCount = Registry.enqueue();
+
+    LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
+    LLVM_DEBUG(dbgs() << "size of worklist: " << InsertCount << '\n');
+    (void)InsertCount;
+
+    Changed |= doExhaustiveCompareMerge();
+  } while (Registry.haveDeferred());
+
+  Changed |= doDiffMerge();
+
+  Registry.clear();
+  return Changed;
+}
+
+// Replace direct callers of Old with New.
+void MergeSimilarFunctions::replaceDirectCallers(Function *Old, Function *New) {
+  Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
+  for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
+    Use *U = &*UI;
+    ++UI;
+    CallBase *CB = dyn_cast<CallBase>(U->getUser());
+    if (CB && CB->isCallee(U)) {
+      // Do not copy attributes from the called function to the call-site.
+      // Function comparison ensures that the attributes are the same up to
+      // type congruences in byval(), in which case we need to keep the byval
+      // type of the call-site, not the callee function.
+      Registry.remove(CB->getFunction());
+      U->set(BitcastNew);
+    }
+  }
+}
+
+// Replace G with an alias to F if possible, or else a thunk to F. Deletes G.
+void MergeSimilarFunctions::writeThunkOrAlias(Function *F, Function *G) {
+  if (isAliasCapable(G)) {
+    writeAlias(F, G);
+    return;
+  }
+
+  writeThunk(F, G);
+}
+
+static void writeThunkBody(Function *Thunk, Function *F, ConstantInt *Choice,
+                           const DataLayout *DL) {
+  BasicBlock *BB = &Thunk->getEntryBlock();
+  IRBuilder<> Builder(BB);
+
+  SmallVector<Value *, 16> Args;
+  unsigned i = 0;
+  FunctionType *FFTy = F->getFunctionType();
+  Type *IntPtrTy = DL->getIntPtrType(FFTy->getContext());
+  for (auto &AI : Thunk->args()) {
+    Value *Cast = createCastIfNeeded(&AI, FFTy->getParamType(i), BB, IntPtrTy);
+    Args.push_back(Cast);
+    ++i;
+  }
+  if (Choice)
+    Args.push_back(Choice);
+
+  CallInst *CI = Builder.CreateCall(F, Args);
+  CI->setTailCall();
+  CI->setCallingConv(F->getCallingConv());
+  CI->setAttributes(F->getAttributes());
+  CI->setIsNoInline();
+  if (Thunk->getReturnType()->isVoidTy()) {
+    Builder.CreateRetVoid();
+  } else {
+    Type *RetTy = Thunk->getReturnType();
+    if (CI->getType()->isIntegerTy() && RetTy->isPointerTy())
+      Builder.CreateRet(Builder.CreateIntToPtr(CI, RetTy));
+    else if (CI->getType()->isPointerTy() && RetTy->isIntegerTy())
+      Builder.CreateRet(Builder.CreatePtrToInt(CI, RetTy));
+    else {
+      Value *Cast = createCastIfNeeded(CI, RetTy, BB, IntPtrTy);
+      Builder.CreateRet(Cast);
+    }
+  }
+}
+
+// Replace G with a simple tail call to bitcast(F). Also replace direct uses
+// of G with bitcast(F). Deletes G.
+void MergeSimilarFunctions::writeThunk(Function *F, Function *G) {
+  if (!G->isInterposable()) {
+    // Redirect direct callers of G to F.
+    replaceDirectCallers(G, F);
+  }
+
+  // If G was internal then we may have replaced all uses of G with F. If so,
+  // stop here and delete G. There's no need for a thunk.
+  if (G->hasLocalLinkage() && G->use_empty()) {
+    LLVM_DEBUG(dbgs() << "All uses of " << G->getName() << " replaced by "
+                      << F->getName() << ". Removing it.\n");
+    G->eraseFromParent();
+    return;
+  }
+
+  Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
+                                    G->getParent());
+  BasicBlock::Create(F->getContext(), "", NewG);
+
+  writeThunkBody(NewG, F, nullptr, DL);
+
+  NewG->copyAttributesFrom(G);
+  NewG->takeName(G);
+  removeUsers(G);
+  G->replaceAllUsesWith(NewG);
+  G->eraseFromParent();
+
+  LLVM_DEBUG(dbgs() << "writeThunk: " << NewG->getName() << " calling "
+                    << F->getName() << '\n');
+  ++NumThunksWritten;
+}
+
+void MergeSimilarFunctions::writeThunkWithChoice(Function *NewF, Function *OldF,
+                                                 int Choice) {
+  // Deleting the body of a function sets its linkage to External. Save the old
+  // one here and restore it at the end.
+  GlobalValue::LinkageTypes OldFLinkage = OldF->getLinkage();
+
+  // Delete OldF's body
+  OldF->deleteBody();
+  BasicBlock::Create(OldF->getContext(), "", OldF);
+
+  // Insert single BB with tail call
+  IntegerType *Int32Ty = Type::getInt32Ty(OldF->getContext());
+  ConstantInt *ChoiceConst = ConstantInt::get(Int32Ty, Choice);
+  writeThunkBody(OldF, NewF, ChoiceConst, DL);
+  OldF->setLinkage(OldFLinkage);
+}
+
+// Replace G with an alias to F and delete G.
+void MergeSimilarFunctions::writeAlias(Function *F, Function *G) {
+
+  // Replace all current uses of G in constants with F. This handles virtual
+  // table and other references. Do this first so that we don't modify thge
+  // global alias we're about to create.
+  SmallVector<Use *, 8> Uses;
+  for (auto I = G->use_begin(), E = G->use_end(); I != E; ++I) {
+    Use *U = I.operator->();
+    Constant *CV = dyn_cast<Constant>(U->getUser());
+    if (!CV)
+      continue;
+    Uses.push_back(U);
+  }
+  for (auto I = Uses.begin(), E = Uses.end(); I != E; ++I) {
+    Use *U = *I;
+    U->set(F);
+  }
+
+  PointerType *PTy = G->getType();
+  auto *GA = GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
+                                 G->getLinkage(), "", F);
+  F->setAlignment(MaybeAlign(std::max(F->getAlignment(), G->getAlignment())));
+  GA->takeName(G);
+  GA->setVisibility(G->getVisibility());
+  removeUsers(G);
+  G->replaceAllUsesWith(GA);
+  G->eraseFromParent();
+
+  LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
+  ++NumAliasesWritten;
+}
+
+// Merge two equivalent functions. Upon completion, Function G is deleted.
+void MergeSimilarFunctions::mergeTwoFunctions(Function *F, Function *G) {
+  if (F->isInterposable()) {
+    assert(G->isInterposable());
+
+    if (UseGlobalAliases) {
+      // Make them both thunks to the same internal function.
+      Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
+                                     F->getParent());
+      H->copyAttributesFrom(F);
+      H->takeName(F);
+      removeUsers(F);
+      F->replaceAllUsesWith(H);
+
+      unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
+
+      writeAlias(F, G);
+      writeAlias(F, H);
+
+      F->setAlignment(MaybeAlign(MaxAlignment));
+      F->setLinkage(GlobalValue::PrivateLinkage);
+    } else {
+      // We can't merge them. Instead, pick one and update all direct callers
+      // to call it and hope that we improve the instruction cache hit rate.
+      replaceDirectCallers(G, F);
+    }
+
+    ++NumDoubleWeak;
+  } else {
+    writeThunkOrAlias(F, G);
+  }
+
+  ++NumFunctionsMerged;
+}
+
+static Value *getLastArg(Function *F) {
+  auto it = F->arg_begin();
+  std::advance(it, F->arg_size() - 1);
+  return it;
+}
+
+static void insertCondAndRemapInstructions(
+    Instruction *F1InstInNewF, const std::vector<const Instruction *> &F2Insts,
+    Function *NewF, ValueToValueMapTy &F1toNewF,
+    const SmallVectorImpl<PartialFunctionComparator *> &Comps, Type *IntPtrTy) {
+  assert(F2Insts.size() == Comps.size() &&
+         "Mis-match between F2Insts & Comps!");
+
+  SmallVector<Instruction *, 8> F2InstsInNewF;
+  for (unsigned FnI = 0, FnE = F2Insts.size(); FnI != FnE; ++FnI) {
+    const Instruction *F2Inst = F2Insts[FnI];
+    if (!F2Inst) {
+      F2InstsInNewF.push_back(NULL);
+      continue;
+    }
+
+    Instruction *F2InstInNewF = F2Inst->clone();
+
+    // Remap F2Inst: F2 values -> F1 values
+    RemapInstruction(F2InstInNewF, Comps[FnI]->getF2toF1Map(),
+                     RF_NoModuleLevelChanges);
+    // Remap F2Inst: F1 values -> NewF values
+    RemapInstruction(F2InstInNewF, F1toNewF, RF_NoModuleLevelChanges);
+
+    F2InstsInNewF.push_back(F2InstInNewF);
+  }
+
+  SmallVector<Instruction *, 8> Terminators;
+  SplitBlockAndInsertSwitch(getLastArg(NewF), F1InstInNewF, F2InstsInNewF,
+                            Terminators);
+
+  assert(Terminators.size() == F2InstsInNewF.size() + 1 &&
+         "Not enough terminators returned");
+
+  // F2InstsInNewF are now hooked up to the correct values in NewF. However,
+  // some of their operands may be pointers/integers so they could potentially
+  // have the wrong type in NewF (since we treat all pointers and integers of
+  // same size as equal). Insert casts if needed.
+  for (unsigned FnI = 0, FnE = F2InstsInNewF.size(); FnI != FnE; ++FnI) {
+    Instruction *F2InstInNewF = F2InstsInNewF[FnI];
+    if (!F2InstInNewF)
+      continue;
+    const Instruction *F2Inst = F2Insts[FnI];
+
+    for (unsigned OpId = 0; OpId < F2InstInNewF->getNumOperands(); ++OpId) {
+      Value *F2NewFOperand = F2InstInNewF->getOperand(OpId);
+      Value *F2OrigOperand = F2Inst->getOperand(OpId);
+
+      if (F2NewFOperand->getType() != F2OrigOperand->getType()) {
+        Value *Cast = createCastIfNeeded(
+            F2NewFOperand, F2OrigOperand->getType(), F2InstInNewF, IntPtrTy);
+        F2InstInNewF->setOperand(OpId, Cast);
+      }
+    }
+  }
+
+  if (ReturnInst *F1Ret = dyn_cast<ReturnInst>(F1InstInNewF)) {
+    // If we're handling differing return instructions, we need to ensure that
+    // they all return the same type. Since we treat pointer types as equal, we
+    // may need to insert a bitcast.
+    for (Instruction *F2Inst : F2InstsInNewF) {
+      if (!F2Inst)
+        continue;
+
+      // F2Inst must also be a return instruction due to control flow
+      // isomorphism.
+      ReturnInst *F2Ret = cast<ReturnInst>(F2Inst);
+
+      if (F2Ret->getReturnValue()->getType() !=
+          F1Ret->getReturnValue()->getType())
+        F2Ret->setOperand(0,
+                          createCastIfNeeded(F2Ret->getReturnValue(),
+                                             F1Ret->getReturnValue()->getType(),
+                                             F2Ret, IntPtrTy));
+    }
+  } else if (!F1InstInNewF->use_empty()) {
+    // If the instructions have uses, we need to insert a PHI node.
+    //
+    // We treat all pointer types as equal, so we may need to insert
+    // a bitcast to ensure that all incoming values of the PHI node have the
+    // same type
+    Type *F1IType = F1InstInNewF->getType();
+    BasicBlock *TailBB = Terminators[0]->getSuccessor(0);
+    PHINode *Phi =
+        PHINode::Create(F1IType, F2InstsInNewF.size(), "", &TailBB->front());
+    F1InstInNewF->replaceAllUsesWith(Phi);
+
+    Phi->addIncoming(F1InstInNewF, F1InstInNewF->getParent());
+    for (unsigned FnI = 0, FnE = F2InstsInNewF.size(); FnI != FnE; ++FnI) {
+      Instruction *F2InstInNewF = F2InstsInNewF[FnI];
+      if (!F2InstInNewF)
+        continue;
+
+      if (F2InstInNewF->getType() != F1IType) {
+        assert(!F2InstInNewF->isTerminator() &&
+               "Cannot cast result of terminator instruction");
+
+        F2InstInNewF = cast<Instruction>(createCastIfNeeded(
+            F2InstInNewF, F1IType, Terminators[FnI + 1], IntPtrTy));
+      }
+
+      Phi->addIncoming(F2InstInNewF, F2InstInNewF->getParent());
+    }
+  }
+}
+
+static void
+mergePHINode(const SmallVectorImpl<PartialFunctionComparator *> &Fns,
+             Function *NewF, ValueToValueMapTy &VMap, /* F1->FNew */
+             const PHINode *F1PhiInst,
+             std::vector<const Instruction *> F2PhiInsts) {
+  PHINode *F1PhiInNewF = dyn_cast<PHINode>(VMap[F1PhiInst]);
+  assert(F1PhiInNewF && "Cannot find F1Inst in NewF!");
+
+  // The incoming blocks in any of the F2PhiInsts may be in a different order.
+  // If this is the case, we have to reorder them. F2PhiInsts is intentionally a
+  // copy, so we can modify it
+  SmallVector<PHINode *, 4> GCInsts; // so we can delete them later.
+  for (unsigned FnI = 0, FnE = F2PhiInsts.size(); FnI != FnE; ++FnI) {
+    const PHINode *F2PhiInst = dyn_cast_or_null<const PHINode>(F2PhiInsts[FnI]);
+    if (!F2PhiInst)
+      continue;
+
+    for (unsigned I = 0, E = F1PhiInNewF->getNumIncomingValues(); I < E; ++I) {
+      if (!Fns[FnI]->enumerate(F1PhiInst->getIncomingBlock(I),
+                               F2PhiInst->getIncomingBlock(I))) {
+        // Non-equivalent blocks in the same position - need to reorder PhiInst
+        PHINode *ReorderedF2PhiInst = PHINode::Create(F2PhiInst->getType(), E);
+
+        for (unsigned II = 0; II < E; ++II) {
+          Value *BBVal =
+              Fns[FnI]->getF1toF2Map()[F1PhiInst->getIncomingBlock(II)];
+          BasicBlock *BB = cast<BasicBlock>(BBVal);
+          Value *Val = F2PhiInst->getIncomingValueForBlock(BB);
+          ReorderedF2PhiInst->addIncoming(Val, BB);
+        }
+
+        F2PhiInsts[FnI] = ReorderedF2PhiInst;
+        GCInsts.push_back(ReorderedF2PhiInst);
+        break;
+      }
+    }
+  }
+
+  // Now merge the PHI nodes.
+  for (unsigned i = 0; i < F1PhiInNewF->getNumIncomingValues(); ++i) {
+    Value *F1InValNewF = F1PhiInNewF->getIncomingValue(i),
+          *F1InVal = F1PhiInst->getIncomingValue(i);
+    BasicBlock *F1NewFInBlock = F1PhiInNewF->getIncomingBlock(i);
+    // If this is a repeat occurrence of the same incoming BasicBlock, we
+    // will have already dealt with it in a previous iteration.
+    if (F1PhiInNewF->getBasicBlockIndex(F1PhiInNewF->getIncomingBlock(i)) !=
+        (int)i)
+      continue;
+
+    Value *NewIncoming = F1InValNewF;
+
+    Instruction *InsertPt = F1NewFInBlock->getTerminator();
+
+    // Build up a chain of cmps and selects that pick the correct incoming
+    // value.
+    for (unsigned FnI = 0, FnE = F2PhiInsts.size(); FnI != FnE; ++FnI) {
+      if (!F2PhiInsts[FnI])
+        continue;
+      const PHINode *F2PhiInst = cast<const PHINode>(F2PhiInsts[FnI]);
+      Value *F2InVal = F2PhiInst->getIncomingValue(i);
+
+      // If we know these are equivalent, there's no further work to do
+      if (Fns[FnI]->enumerate(F1InVal, F2InVal, /*NoSelfRef=*/true) &&
+          Fns[FnI]->enumerate(F1PhiInst->getIncomingBlock(i),
+                              F2PhiInst->getIncomingBlock(i)))
+        continue;
+
+      assert(Fns[FnI]->enumerate(F1PhiInst->getIncomingBlock(i),
+                                 F2PhiInst->getIncomingBlock(i)) &&
+             "Non-equivalent incoming BBs in PHI.");
+
+      // We have different incoming values from the same block
+      // Translate F2's incoming value to NewF if needed
+      Value *F2InValNewF = F2InVal;
+      if (!isa<Constant>(F2InVal)) {
+        Value *V = Fns[FnI]->getF2toF1Map()[F2InVal]; // F2->F1
+        F2InValNewF = VMap[V];                        // F1->NewF
+        assert(V && F2InValNewF && "Cannot map F2InVal to NewF");
+      }
+
+      // Cast F2InValNewF to the correct type if needed
+      LLVMContext &Ctx = F1InValNewF->getType()->getContext();
+      const DataLayout *FTD = Fns[FnI]->getDataLayout();
+      Type *IntPtrTy = FTD ? FTD->getIntPtrType(Ctx) : NULL;
+      F2InValNewF = createCastIfNeeded(F2InValNewF, F1InValNewF->getType(),
+                                       InsertPt, IntPtrTy);
+
+      // Create compare & select
+      Value *ChoiceArg = getLastArg(NewF);
+      Value *SelectBit =
+          new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, getLastArg(NewF),
+                       ConstantInt::get(ChoiceArg->getType(), FnI + 1));
+
+      // SelectBit true -> F2InValNewF, SelectBit false -> existing NewIncoming.
+      NewIncoming =
+          SelectInst::Create(SelectBit, F2InValNewF, NewIncoming, "", InsertPt);
+    }
+
+    if (NewIncoming == F1InValNewF)
+      continue; // no change for this incoming value
+
+    // Replace all occurrences of this incoming value/block by the new
+    // ones (phi nodes can have repeated arguments)
+    for (unsigned j = i; j < F1PhiInNewF->getNumIncomingValues(); ++j) {
+      if (F1PhiInNewF->getIncomingBlock(j) == F1NewFInBlock) {
+        F1PhiInNewF->setIncomingValue(j, NewIncoming);
+      }
+    }
+  }
+
+  // Garbage-collect the reordered PHI nodes we temporarily created.
+  for (SmallVectorImpl<PHINode *>::iterator I = GCInsts.begin(),
+                                            E = GCInsts.end();
+       I != E; ++I)
+    delete *I;
+}
+
+static bool rewriteRecursiveCall(const CallInst *F1I, const CallInst *F2I,
+                                 CallInst *NewFI, const Function *F1,
+                                 const Function *F2, Function *NewF) {
+  if (!(F1I->getCalledFunction() == F1 && F2I->getCalledFunction() == F2) &&
+      !(F1I->getCalledFunction() == F2 && F2I->getCalledFunction() == F1))
+    return false; // not a recursive/mutually recursive call
+
+  // Replace NewFI by recursive call to NewF with additional choice argument
+  SmallVector<Value *, 16> Args;
+  for (unsigned AI = 0, End = NewFI->getNumArgOperands(); AI < End; ++AI) {
+    Value *Arg = NewFI->getArgOperand(AI);
+
+    // Check if F1 or F2 is one of the arguments (veeery unusual case, don't
+    // handle it for now).
+    if (Arg == F1 || Arg == F2)
+      return false;
+
+    Args.push_back(Arg);
+  }
+
+  if (F1I->getCalledFunction() == F1 && F2I->getCalledFunction() == F2) {
+    Args.push_back(getLastArg(NewF));
+  } else {
+    // Need to invert the choice argument
+    Value *ChoiceArg = getLastArg(NewF);
+    Constant *One = ConstantInt::get(ChoiceArg->getType(), 1);
+    Args.push_back(
+        BinaryOperator::Create(Instruction::Xor, ChoiceArg, One, "", NewFI));
+  }
+
+  CallInst *CI = CallInst::Create(NewF, Args);
+  CI->setCallingConv(NewF->getCallingConv());
+
+  ReplaceInstWithInst(NewFI, CI);
+
+  return true;
+}
+
+/// Clone F1 into a new function with F1's name + MERGE_SUFFIX. Adds an
+/// additional i32 argument to the function.
+static Function *cloneAndAddArgument(Function *F1, ValueToValueMapTy &VMap) {
+  LLVMContext &Context = F1->getContext();
+
+  std::vector<Type *> ArgTypes;
+  for (const auto &Arg : F1->args())
+    ArgTypes.push_back(Arg.getType());
+  ArgTypes.push_back(Type::getInt32Ty(Context));
+
+  FunctionType *FTy =
+      FunctionType::get(F1->getFunctionType()->getReturnType(), ArgTypes,
+                        F1->getFunctionType()->isVarArg());
+  Function *NewF =
+      Function::Create(FTy, F1->getLinkage(), F1->getName() + MERGED_SUFFIX);
+
+  insertFunctionAfter(NewF, F1);
+
+  if (F1->hasSection())
+    NewF->setSection(F1->getSection());
+
+  if (F1->getFunctionType()->isVarArg())
+    NewF->setCallingConv(CallingConv::C);
+  else
+    NewF->setCallingConv(CallingConv::Fast);
+
+  Function::arg_iterator DestI = NewF->arg_begin();
+  for (auto &Arg : F1->args()) {
+    Argument *DestIn = &*DestI;
+    DestIn->setName(Arg.getName()); // Copy the name over...
+    VMap[&Arg] = DestIn;            // Add mapping to VMap
+    ++DestI;
+  }
+
+  // Name the selector argument
+  (*DestI).setName("__merge_arg");
+
+  SmallVector<ReturnInst *, 8> Returns;
+  CloneFunctionInto(NewF, F1, VMap, CloneType::ExtractingFunctions, Returns);
+  // Set linkage to set visibility to default.
+  NewF->setLinkage(GlobalValue::InternalLinkage);
+
+  return NewF;
+}
+
+typedef MapVector<const Instruction *, std::vector<const Instruction *>>
+    CombinedDiffMap;
+
+void MergeSimilarFunctions::outlineAndMergeFunctions(
+    SmallVectorImpl<PartialFunctionComparator *> &Fns) {
+  assert(!Fns.empty() && "Cannot merge empty set of functions");
+
+  // All comparator instances in Fns share the same F1
+  Function *F1 = Fns.front()->getF1();
+
+  // Clone F1 into new function with an additional i32 argument
+  ValueToValueMapTy VMap; // maps F1 values -> NewF values
+  Function *NewF = cloneAndAddArgument(F1, VMap);
+
+  // Combine all the DifferingInstructions maps in Fns into one single map of
+  // lists to aid the merging process.
+  //
+  // Map F1 instruction -> list of F2 instructions indexed by position in Fns.
+  CombinedDiffMap AllDifferingInstructions;
+  for (unsigned I = 0, E = Fns.size(); I != E; ++I) {
+    PartialFunctionComparator *Comp = Fns[I];
+    for (MapVector<const Instruction *, const Instruction *>::iterator
+             DiffI = Comp->DifferingInstructions.begin(),
+             DiffE = Comp->DifferingInstructions.end();
+         DiffI != DiffE; ++DiffI) {
+      AllDifferingInstructions[DiffI->first].resize(Fns.size());
+      AllDifferingInstructions[DiffI->first][I] = DiffI->second;
+    }
+  }
+
+  // Merge differing PHI nodes. We need to handle these first because they could
+  // be affected later on when we split basic blocks, thus making them
+  // impossible to merge.
+  for (CombinedDiffMap::const_iterator I = AllDifferingInstructions.begin(),
+                                       E = AllDifferingInstructions.end();
+       I != E; ++I) {
+    const PHINode *F1PhiInst = dyn_cast<PHINode>(I->first);
+    if (!F1PhiInst)
+      continue;
+
+    const std::vector<const Instruction *> &F2PhiInsts = I->second;
+
+    mergePHINode(Fns, NewF, VMap, F1PhiInst, F2PhiInsts);
+  }
+
+  // Merge recursive calls
+  //
+  // TODO: We currently only support this optimization for pairs of functions.
+  // If more than two functions are merged, we mark the recursive calls as
+  // DifferingInstructions which causes switch statements to be inserted and
+  // recursive calls going through thunks. It wouldn't be too hard to implement
+  // self-recursive calls for multi-merges. *Mutually* recursive calls with
+  // multi-merges are a little trickier - that's why we leave it for now.
+  if (Fns.size() == 1) {
+    PartialFunctionComparator *Comp = Fns.front();
+    for (MapVector<const Instruction *, const Instruction *>::const_iterator
+             I = Comp->SelfRefInstructions.begin(),
+             E = Comp->SelfRefInstructions.end();
+         I != E; ++I) {
+      const Instruction *F1I = I->first;
+      if (Comp->DifferingInstructions.count(F1I))
+        continue; // Differing in other ways too, so deal with it later.
+
+      // Attempt recursive call rewriting
+      if (isa<CallInst>(F1I)) {
+        const CallInst *F1Call = cast<const CallInst>(F1I);
+        const CallInst *F2Call = dyn_cast<const CallInst>(I->second);
+        CallInst *NewFCall = dyn_cast<CallInst>(VMap[F1I]);
+
+        if (F1Call && F2Call && NewFCall &&
+            rewriteRecursiveCall(F1Call, F2Call, NewFCall, Comp->getF1(),
+                                 Comp->getF2(), NewF))
+          continue;
+      }
+
+      // Can't rewrite it. Mark as differing and insert conditional later
+      Comp->DifferingInstructions[F1I] = I->second;
+    }
+  } else {
+    for (unsigned I = 0, E = Fns.size(); I != E; ++I) {
+      PartialFunctionComparator *Comp = Fns[I];
+      for (MapVector<const Instruction *, const Instruction *>::const_iterator
+               II = Comp->SelfRefInstructions.begin(),
+               EE = Comp->SelfRefInstructions.end();
+           II != EE; ++II) {
+        const Instruction *F1I = II->first;
+        if (Comp->DifferingInstructions.count(F1I))
+          continue; // Differing in other ways too, so deal with it later.
+
+        AllDifferingInstructions[F1I].resize(Fns.size());
+        AllDifferingInstructions[F1I][I] = II->second;
+      }
+    }
+  }
+
+  // For each differing instruction, splice basic block, and insert conditional
+  LLVMContext &Context = NewF->getContext();
+  Type *IntPtrType = DL->getIntPtrType(Context);
+  for (CombinedDiffMap::const_iterator I = AllDifferingInstructions.begin(),
+                                       E = AllDifferingInstructions.end();
+       I != E; ++I) {
+    const Instruction *F1Inst = I->first;
+    const std::vector<const Instruction *> &F2Insts = I->second;
+
+    assert(VMap.find(F1Inst) != VMap.end() && "Cannot find differing inst!");
+    Instruction *F1InstInNewF = cast<Instruction>(VMap[F1Inst]);
+
+    if (isa<PHINode>(F1InstInNewF))
+      continue; // we already handled these above
+
+    insertCondAndRemapInstructions(F1InstInNewF, F2Insts, NewF, VMap, Fns,
+                                   IntPtrType);
+  }
+
+  // Replace functions with thunks
+  PrintMerges("FNSM", F1, NewF);
+  writeThunkWithChoice(NewF, F1, 0);
+  for (unsigned FnI = 0, FnE = Fns.size(); FnI != FnE; ++FnI) {
+    Function *F2 = Fns[FnI]->getF2();
+    PrintMerges("FNSM", F2, NewF);
+    writeThunkWithChoice(NewF, F2, FnI + 1);
+  }
+  NumSimilarFunctionsMerged += Fns.size() + 1;
+}
+
+// For each instruction used by the value, remove() the function that contains
+// the instruction. This should happen right before a call to RAUW.
+void MergeSimilarFunctions::removeUsers(Value *V) {
+  std::vector<Value *> Worklist;
+  Worklist.push_back(V);
+  while (!Worklist.empty()) {
+    Value *V = Worklist.back();
+    Worklist.pop_back();
+
+    for (User *U : V->users()) {
+      if (Instruction *I = dyn_cast<Instruction>(U)) {
+        Registry.remove(I->getParent()->getParent());
+      } else if (isa<GlobalValue>(U)) {
+        // do nothing
+      } else if (Constant *C = dyn_cast<Constant>(U)) {
+        for (User *UU : C->users())
+          Worklist.push_back(UU);
+      }
+    }
+  }
+}
+
+bool MergeSimilarFunctions::mergeBucket(std::list<ComparableFunction> &Fns,
+                                        bool &Changed) {
+  for (std::list<ComparableFunction>::iterator FnI = Fns.begin(),
+                                               FnE = Fns.end();
+       FnI != FnE; ++FnI) {
+    if (!FnI->isNew())
+      continue;
+
+    if (!FnI->getFunc())
+      continue;
+
+    SmallVector<PartialFunctionComparator *, 8> DiffMergeCandidates;
+
+    std::list<ComparableFunction>::iterator Fn2I = FnI;
+    for (++Fn2I; Fn2I != FnE; ++Fn2I) {
+      if (!Fn2I->getFunc())
+        continue;
+
+      assert(FnI->getFunc() != Fn2I->getFunc() &&
+             "Duplicate function in list!");
+
+      PartialFunctionComparator *Comp =
+          new PartialFunctionComparator(DL, FnI->getFunc(), Fn2I->getFunc());
+
+      if (!Comp->compare() || !isMergeCandidate(Comp)) {
+        delete Comp;
+        continue;
+      }
+
+      // Never thunk a strong function to a weak function.
+      assert(!FnI->getFunc()->isInterposable() ||
+             Fn2I->getFunc()->isInterposable());
+
+      if (Comp->isExactMatch()) {
+        // Equiv merge the two functions. Throw away any diff merge
+        // candidate we might have found so far.
+        delete Comp;
+
+        LLVM_DEBUG(dbgs() << "- Equiv merge " << FnI->getFunc()->getName()
+                          << " == " << Fn2I->getFunc()->getName() << '\n');
+
+        PrintMerges("FNEQ", FnI->getFunc(), Fn2I->getFunc());
+
+        Function *DeleteF = Fn2I->getFunc();
+        Registry.remove(DeleteF, /*reanalyze=*/false);
+
+        mergeTwoFunctions(FnI->getFunc(), DeleteF);
+
+        Changed = true;
+
+        // mergeTwoFunctions may have removed functions from this bucket and
+        // invalidated the iterators. Rescan the whole bucket, continuing
+        // from the current function (previous ones will have been
+        // markCompared())
+        for (SmallVector<PartialFunctionComparator *, 8>::iterator
+                 I = DiffMergeCandidates.begin(),
+                 E = DiffMergeCandidates.end();
+             I != E; ++I)
+          delete *I;
+
+        return false;
+      } else {
+        DiffMergeCandidates.push_back(Comp);
+      }
+    }
+
+    if (!DiffMergeCandidates.empty()) {
+      // Add to our list of candidates for diff merging
+      for (SmallVector<PartialFunctionComparator *, 8>::iterator
+               I = DiffMergeCandidates.begin(),
+               E = DiffMergeCandidates.end();
+           I != E; ++I) {
+        Registry.insertCandidate(*I);
+      }
+    }
+
+    FnI->markCompared();
+  }
+
+  return true;
+}
+
+bool MergeSimilarFunctions::doExhaustiveCompareMerge() {
+  bool Changed = false;
+
+  // Process buckets with strong functions first.
+  for (MergeRegistry::FnCompareMap::iterator
+           BucketsI = Registry.FunctionsToCompare.begin(),
+           BucketsE = Registry.FunctionsToCompare.end();
+       BucketsI != BucketsE; ++BucketsI) {
+    std::list<ComparableFunction> &Fns = BucketsI->second;
+    if (Fns.size() < 2 || Fns.front().getFunc()->isInterposable())
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Processing strong bucket " << BucketsI->first
+                      << " with " << Fns.size() << " functions\n");
+    // Repeatedly scan this bucket, until we find no more functions to equiv
+    // merge.
+    while (!mergeBucket(Fns, Changed) && Fns.size() > 1) {
+      LLVM_DEBUG(dbgs() << "Rescanning bucket.\n");
+    }
+  }
+
+  // Process buckets with weak functions.
+  for (MergeRegistry::FnCompareMap::iterator
+           BucketsI = Registry.FunctionsToCompare.begin(),
+           BucketsE = Registry.FunctionsToCompare.end();
+       BucketsI != BucketsE; ++BucketsI) {
+    std::list<ComparableFunction> &Fns = BucketsI->second;
+    if (Fns.size() < 2 || !Fns.front().getFunc()->isInterposable())
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Processing weak bucket " << BucketsI->first
+                      << " with " << Fns.size() << " functions\n");
+    // Repeatedly scan this bucket, until we find no more functions to equiv
+    // merge.
+    while (!mergeBucket(Fns, Changed) && Fns.size() > 1) {
+      LLVM_DEBUG(dbgs() << "Rescanning bucket.\n");
+    }
+  }
+
+  return Changed;
+}
+
+static bool orderComparatorsByMetric(PartialFunctionComparator *Cmp1,
+                                     PartialFunctionComparator *Cmp2) {
+  return (Cmp1->getSimilarityMetric() > Cmp2->getSimilarityMetric());
+}
+
+bool MergeSimilarFunctions::doDiffMerge() {
+  if (Registry.FunctionsToMerge.empty())
+    return false;
+
+  bool Changed = false;
+  DenseSet<Function *> MergedFns; // Functions that have already been merged
+  Registry.FunctionsToMerge.sort(orderComparatorsByMetric);
+
+  for (std::list<PartialFunctionComparator *>::iterator
+           I = Registry.FunctionsToMerge.begin(),
+           E = Registry.FunctionsToMerge.end();
+       I != E; ++I) {
+    PartialFunctionComparator *Comp = *I;
+    Function *F1 = Comp->getF1();
+    // Ignore it if we've already merged this fn
+    if (MergedFns.count(F1) || MergedFns.count(Comp->getF2()))
+      continue;
+
+    assert(Registry.SimilarFunctions.count(F1) &&
+           "Comparator doesn't exist in SimilarFunctions map");
+
+    // Look at all functions F that F1 could be merged with. Merge with each F,
+    // unless there is another function F' that is more similar to F than F1.
+    MergeRegistry::FnComparatorSet &SimilarFns = Registry.SimilarFunctions[F1];
+    SmallVector<PartialFunctionComparator *, 4> CurrentMerge;
+
+    for (MergeRegistry::FnComparatorSet::iterator
+             CandidateI = SimilarFns.begin(),
+             CandidateE = SimilarFns.end();
+         CandidateI != CandidateE; ++CandidateI) {
+      PartialFunctionComparator *Comp2 = *CandidateI;
+      assert(Comp2->getF1() == F1 && "Inconsistency in SimilarFunctions");
+      Function *F2 = Comp2->getF2();
+
+      // Ignore it if we've already merged this fn
+      if (MergedFns.count(F2))
+        continue;
+
+      // Check whether there is a better merge candidate for F2
+      if (Registry.getMaxSimilarity(F2, MergedFns) >
+          Comp2->getSimilarityMetric())
+        continue;
+
+      // Ok, we actually want to merge with F2
+      CurrentMerge.push_back(Comp2);
+      MergedFns.insert(F2);
+    }
+
+    if (CurrentMerge.empty())
+      continue;
+
+    MergedFns.insert(F1);
+
+    NumMultiMerged += CurrentMerge.size();
+
+    LLVM_DEBUG(dbgs() << "- Multi merge of " << F1->getName() << " with "
+                      << CurrentMerge.size() << " functions.\n");
+
+    Changed = true;
+    outlineAndMergeFunctions(CurrentMerge);
+  }
+
+  return Changed;
+}
 No newline at end of file

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

cl::opt<bool> FlattenedProfileUsed(
     "flattened-profile-used", cl::init(false), cl::Hidden,
     cl::desc("Indicate the sample profile being used is flattened, i.e., "
              "no inline hierachy exists in the profile. "));
 
 cl::opt<bool> EnableOrderFileInstrumentation(
     "enable-order-file-instrumentation", cl::init(false), cl::Hidden,
     cl::desc("Enable order file instrumentation (default = off)"));
 
+static cl::opt<bool> EnableMergeSimilarFunctions(
+    "enable-merge-sim-functions", cl::init(false), cl::Hidden,
+    cl::desc("Enable the Function merging pass (default = on)"));
+
 static cl::opt<bool>
     EnableMatrix("enable-matrix", cl::init(false), cl::Hidden,
                  cl::desc("Enable lowering of the matrix intrinsics"));
 
 cl::opt<AttributorRunOption> AttributorRun(
     "attributor-enable", cl::Hidden, cl::init(AttributorRunOption::NONE),
     cl::desc("Enable the attributor inter-procedural deduction pass."),
     cl::values(clEnumValN(AttributorRunOption::ALL, "all",
if (AttributorRun & AttributorRunOption::CGSCC)
     MPM.add(createAttributorCGSCCLegacyPass());
 
   // Try to perform OpenMP specific optimizations. This is a (quick!) no-op if
   // there are no OpenMP runtime calls present in the module.
   if (OptLevel > 1)
     MPM.add(createOpenMPOptLegacyPass());
 
   MPM.add(createPostOrderFunctionAttrsLegacyPass());
+
+  if (EnableMergeSimilarFunctions) {
+    MPM.add(createMergeFunctionsPass(true));
+  }
+
   if (OptLevel > 2)
     MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args
 
   addExtensionsToPM(EP_CGSCCOptimizerLate, MPM);
   addFunctionSimplificationPasses(MPM);
 
   // FIXME: This is a HACK! The inliner pass above implicitly creates a CGSCC
   // pass manager that we are specifically trying to avoid. To prevent this
void PassManagerBuilder::populateModulePassManager(
   // See comment in the new PM for justification of scheduling splitting at
   // this stage (\ref buildModuleSimplificationPipeline).
   if (EnableHotColdSplit && !(PrepareForLTO || PrepareForThinLTO))
     MPM.add(createHotColdSplittingPass());
 
   if (MergeFunctions)
     MPM.add(createMergeFunctionsPass());
 
+  if (EnableMergeSimilarFunctions)
+    MPM.add(createMergeFunctionsPass(true));
+
   // LoopSink pass sinks instructions hoisted by LICM, which serves as a
   // canonicalization pass that enables other optimizations. As a result,
   // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
   // result too early.
   MPM.add(createLoopSinkPass());
   // Get rid of LCSSA nodes.
   MPM.add(createInstSimplifyLegacyPass());
 
void PassManagerBuilder::addLateLTOOptimizationPasses(
 
   // Now that we have optimized the program, discard unreachable functions.
   PM.add(createGlobalDCEPass());
 
   // FIXME: this is profitable (for compiler time) to do at -O0 too, but
   // currently it damages debug info.
   if (MergeFunctions)
     PM.add(createMergeFunctionsPass());
+
+  if (EnableMergeSimilarFunctions)
+    PM.add(createMergeFunctionsPass(true));
 }
 
 void PassManagerBuilder::populateThinLTOPassManager(
     legacy::PassManagerBase &PM) {
   PerformThinLTO = true;
   if (LibraryInfo)
     PM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 

llvm/lib/Transforms/Utils/CloneFunction.cpp

BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap,
   }
   return NewBB;
 }
 
 // Clone OldFunc into NewFunc, transforming the old arguments into references to
 // VMap values.
 //
 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
-                             ValueToValueMapTy &VMap,
-                             bool ModuleLevelChanges,
-                             SmallVectorImpl<ReturnInst*> &Returns,
+                             ValueToValueMapTy &VMap, CloneType CT,
+                             SmallVectorImpl<ReturnInst *> &Returns,
                              const char *NameSuffix, ClonedCodeInfo *CodeInfo,
                              ValueMapTypeRemapper *TypeMapper,
                              ValueMaterializer *Materializer) {
   assert(NameSuffix && "NameSuffix cannot be null!");
 
 #ifndef NDEBUG
   for (const Argument &I : OldFunc->args())
     assert(VMap.count(&I) && "No mapping from source argument specified!");
 #endif
 
   // Copy all attributes other than those stored in the AttributeList.  We need
   // to remap the parameter indices of the AttributeList.
   AttributeList NewAttrs = NewFunc->getAttributes();
   NewFunc->copyAttributesFrom(OldFunc);
   NewFunc->setAttributes(NewAttrs);
 
+  RemapFlags RF =
+      (CT == CloneType::ModuleLevelChanges) ? RF_None : RF_NoModuleLevelChanges;
   // Fix up the personality function that got copied over.
   if (OldFunc->hasPersonalityFn())
-    NewFunc->setPersonalityFn(
-        MapValue(OldFunc->getPersonalityFn(), VMap,
-                 ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
+    NewFunc->setPersonalityFn(MapValue(OldFunc->getPersonalityFn(), VMap, RF,
                                        TypeMapper, Materializer));
 
   SmallVector<AttributeSet, 4> NewArgAttrs(NewFunc->arg_size());
   AttributeList OldAttrs = OldFunc->getAttributes();
 
   // Clone any argument attributes that are present in the VMap.
   for (const Argument &OldArg : OldFunc->args()) {
     if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
       NewArgAttrs[NewArg->getArgNo()] =
           OldAttrs.getParamAttributes(OldArg.getArgNo());
     }
   }
 
   NewFunc->setAttributes(
       AttributeList::get(NewFunc->getContext(), OldAttrs.getFnAttributes(),
                          OldAttrs.getRetAttributes(), NewArgAttrs));
 
-  bool MustCloneSP =
-      OldFunc->getParent() && OldFunc->getParent() == NewFunc->getParent();
+  bool MustCloneSP = CT != CloneType::ExtractingFunctions &&
+                     OldFunc->getParent() &&
+                     OldFunc->getParent() == NewFunc->getParent();
   DISubprogram *SP = OldFunc->getSubprogram();
   if (SP) {
-    assert(!MustCloneSP || ModuleLevelChanges);
+    assert(!MustCloneSP || CT == CloneType::ModuleLevelChanges);
     // Add mappings for some DebugInfo nodes that we don't want duplicated
     // even if they're distinct.
     auto &MD = VMap.MD();
     MD[SP->getUnit()].reset(SP->getUnit());
     MD[SP->getType()].reset(SP->getType());
     MD[SP->getFile()].reset(SP->getFile());
     // If we're not cloning into the same module, no need to clone the
     // subprogram
     if (!MustCloneSP)
       MD[SP].reset(SP);
   }
 
   SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
   OldFunc->getAllMetadata(MDs);
   for (auto MD : MDs) {
     NewFunc->addMetadata(
-        MD.first,
-        *MapMetadata(MD.second, VMap,
-                     ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
-                     TypeMapper, Materializer));
+        MD.first, *MapMetadata(MD.second, VMap, RF, TypeMapper, Materializer));
   }
 
   // When we remap instructions, we want to avoid duplicating inlined
   // DISubprograms, so record all subprograms we find as we duplicate
   // instructions and then freeze them in the MD map.
   // We also record information about dbg.value and dbg.declare to avoid
   // duplicating the types.
   DebugInfoFinder DIFinder;
 
   // Loop over all of the basic blocks in the function, cloning them as
   // appropriate.  Note that we save BE this way in order to handle cloning of
   // recursive functions into themselves.
   //
   for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
        BI != BE; ++BI) {
     const BasicBlock &BB = *BI;
 
     // Create a new basic block and copy instructions into it!
-    BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo,
-                                      ModuleLevelChanges ? &DIFinder : nullptr);
+    BasicBlock *CBB = CloneBasicBlock(
+        &BB, VMap, NameSuffix, NewFunc, CodeInfo,
+        (CT == CloneType::ModuleLevelChanges) ? &DIFinder : nullptr);
 
     // Add basic block mapping.
     VMap[&BB] = CBB;
 
     // It is only legal to clone a function if a block address within that
     // function is never referenced outside of the function.  Given that, we
     // want to map block addresses from the old function to block addresses in
     // the clone. (This is different from the generic ValueMapper
#endif
   // Loop over all of the instructions in the function, fixing up operand
   // references as we go.  This uses VMap to do all the hard work.
   for (Function::iterator BB =
            cast<BasicBlock>(VMap[&OldFunc->front()])->getIterator(),
                           BE = NewFunc->end();
        BB != BE; ++BB)
     // Loop over all instructions, fixing each one as we find it...
     for (Instruction &II : *BB)
-      RemapInstruction(&II, VMap,
-                       ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
-                       TypeMapper, Materializer);
+      RemapInstruction(&II, VMap, RF, TypeMapper, Materializer);
 
   // Register all DICompileUnits of the old parent module in the new parent module
   auto* OldModule = OldFunc->getParent();
   auto* NewModule = NewFunc->getParent();
   if (OldModule && NewModule && OldModule != NewModule && DIFinder.compile_unit_count()) {
     auto* NMD = NewModule->getOrInsertNamedMetadata("llvm.dbg.cu");
     // Avoid multiple insertions of the same DICompileUnit to NMD.
     SmallPtrSet<const void*, 8> Visited;
Function *llvm::CloneFunction(Function *F, ValueToValueMapTy &VMap,
   // Loop over the arguments, copying the names of the mapped arguments over...
   Function::arg_iterator DestI = NewF->arg_begin();
   for (const Argument & I : F->args())
     if (VMap.count(&I) == 0) {     // Is this argument preserved?
       DestI->setName(I.getName()); // Copy the name over...
       VMap[&I] = &*DestI++;        // Add mapping to VMap
     }
 
-  SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
-  CloneFunctionInto(NewF, F, VMap, F->getSubprogram() != nullptr, Returns, "",
-                    CodeInfo);
+  SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
+  CloneType CT = F->getSubprogram() != nullptr ? CloneType::ModuleLevelChanges
+                                               : CloneType::InvalidCloneType;
+  CloneFunctionInto(NewF, F, VMap, CT, Returns, "", CodeInfo);
 
   return NewF;
 }
 
 
 
 namespace {
   /// This is a private class used to implement CloneAndPruneFunctionInto.

llvm/lib/Transforms/Utils/CloneModule.cpp

for (const Function &I : M) {
     Function::arg_iterator DestI = F->arg_begin();
     for (Function::const_arg_iterator J = I.arg_begin(); J != I.arg_end();
          ++J) {
       DestI->setName(J->getName());
       VMap[&*J] = &*DestI++;
     }
 
     SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
-    CloneFunctionInto(F, &I, VMap, /*ModuleLevelChanges=*/true, Returns);
+    CloneFunctionInto(F, &I, VMap, CloneType::ModuleLevelChanges, Returns);
 
     if (I.hasPersonalityFn())
       F->setPersonalityFn(MapValue(I.getPersonalityFn(), VMap));
 
     copyComdat(F, &I);
   }
 
   // And aliases

llvm/lib/Transforms/Utils/FunctionComparator.cpp

-//===- FunctionComparator.h - Function Comparator -------------------------===//
+//===- PreciseFunctionComparator.h - Function Comparator
+//-------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements the FunctionComparator and GlobalNumberState classes
-// which are used by the MergeFunctions pass for comparing functions.
-//
+// This file implements the PreciseFunctionComparator, PartialFunctionComparator
+// and GlobalNumberState classes which are used by the MergeFunctions pass for
+// comparing functions.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/FunctionComparator.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallPtrSet.h"

 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
 using namespace llvm;
 
-#define DEBUG_TYPE "functioncomparator"
+#define DEBUG_TYPE "FunctionComparator"
 
-int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const {
+int PreciseFunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const {
   if (L < R)
     return -1;
   if (L > R)
     return 1;
   return 0;
 }
 
-int FunctionComparator::cmpOrderings(AtomicOrdering L, AtomicOrdering R) const {
+int PreciseFunctionComparator::cmpOrderings(AtomicOrdering L,
+                                            AtomicOrdering R) const {
   if ((int)L < (int)R)
     return -1;
   if ((int)L > (int)R)
     return 1;
   return 0;
 }
 
-int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const {
+int PreciseFunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const {
   if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth()))
     return Res;
   if (L.ugt(R))
     return 1;
   if (R.ugt(L))
     return -1;
   return 0;
 }
 
-int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const {
+int PreciseFunctionComparator::cmpAPFloats(const APFloat &L,
+                                           const APFloat &R) const {
   // Floats are ordered first by semantics (i.e. float, double, half, etc.),
   // then by value interpreted as a bitstring (aka APInt).
   const fltSemantics &SL = L.getSemantics(), &SR = R.getSemantics();
   if (int Res = cmpNumbers(APFloat::semanticsPrecision(SL),
                            APFloat::semanticsPrecision(SR)))
     return Res;
   if (int Res = cmpNumbers(APFloat::semanticsMaxExponent(SL),
                            APFloat::semanticsMaxExponent(SR)))
     return Res;
   if (int Res = cmpNumbers(APFloat::semanticsMinExponent(SL),
                            APFloat::semanticsMinExponent(SR)))
     return Res;
   if (int Res = cmpNumbers(APFloat::semanticsSizeInBits(SL),
                            APFloat::semanticsSizeInBits(SR)))
     return Res;
   return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt());
 }
 
-int FunctionComparator::cmpMem(StringRef L, StringRef R) const {
+int PreciseFunctionComparator::cmpMem(StringRef L, StringRef R) const {
   // Prevent heavy comparison, compare sizes first.
   if (int Res = cmpNumbers(L.size(), R.size()))
     return Res;
 
   // Compare strings lexicographically only when it is necessary: only when
   // strings are equal in size.
   return L.compare(R);
 }
 
-int FunctionComparator::cmpAttrs(const AttributeList L,
+int PreciseFunctionComparator::cmpAttrs(const AttributeList L,
                                         const AttributeList R) const {
   if (int Res = cmpNumbers(L.getNumAttrSets(), R.getNumAttrSets()))
     return Res;
 
   for (unsigned i = L.index_begin(), e = L.index_end(); i != e; ++i) {
     AttributeSet LAS = L.getAttributes(i);
     AttributeSet RAS = R.getAttributes(i);
     AttributeSet::iterator LI = LAS.begin(), LE = LAS.end();
     AttributeSet::iterator RI = RAS.begin(), RE = RAS.end();
for (unsigned i = L.index_begin(), e = L.index_end(); i != e; ++i) {
     if (LI != LE)
       return 1;
     if (RI != RE)
       return -1;
   }
   return 0;
 }
 
-int FunctionComparator::cmpRangeMetadata(const MDNode *L,
+int PreciseFunctionComparator::cmpRangeMetadata(const MDNode *L,
                                                 const MDNode *R) const {
   if (L == R)
     return 0;
   if (!L)
     return -1;
   if (!R)
     return 1;
   // Range metadata is a sequence of numbers. Make sure they are the same
   // sequence.
for (size_t I = 0; I < L->getNumOperands(); ++I) {
     ConstantInt *LLow = mdconst::extract<ConstantInt>(L->getOperand(I));
     ConstantInt *RLow = mdconst::extract<ConstantInt>(R->getOperand(I));
     if (int Res = cmpAPInts(LLow->getValue(), RLow->getValue()))
       return Res;
   }
   return 0;
 }
 
-int FunctionComparator::cmpOperandBundlesSchema(const CallBase &LCS,
-                                                const CallBase &RCS) const {
+int PreciseFunctionComparator::cmpOperandBundlesSchema(
+    const CallBase &LCS, const CallBase &RCS) const {
   assert(LCS.getOpcode() == RCS.getOpcode() && "Can't compare otherwise!");
 
   if (int Res =
           cmpNumbers(LCS.getNumOperandBundles(), RCS.getNumOperandBundles()))
     return Res;
 
   for (unsigned I = 0, E = LCS.getNumOperandBundles(); I != E; ++I) {
     auto OBL = LCS.getOperandBundleAt(I);
int PreciseFunctionComparator::cmpOperandBundlesSchema(
   return 0;
 }
 
 /// Constants comparison:
 /// 1. Check whether type of L constant could be losslessly bitcasted to R
 /// type.
 /// 2. Compare constant contents.
 /// For more details see declaration comments.
-int FunctionComparator::cmpConstants(const Constant *L,
+int PreciseFunctionComparator::cmpConstants(const Constant *L,
                                             const Constant *R) const {
   Type *TyL = L->getType();
   Type *TyR = R->getType();
 
   // Check whether types are bitcastable. This part is just re-factored
   // Type::canLosslesslyBitCastTo method, but instead of returning true/false,
   // we also pack into result which type is "less" for us.
   int TypesRes = cmpTypes(TyL, TyR);
   if (TypesRes != 0) {
int PreciseFunctionComparator::cmpConstants(const Constant *L,
   }
   default: // Unknown constant, abort.
     LLVM_DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n");
     llvm_unreachable("Constant ValueID not recognized.");
     return -1;
   }
 }
 
-int FunctionComparator::cmpGlobalValues(GlobalValue *L, GlobalValue *R) const {
+int PreciseFunctionComparator::cmpGlobalValues(GlobalValue *L,
+                                               GlobalValue *R) const {
   uint64_t LNumber = GlobalNumbers->getNumber(L);
   uint64_t RNumber = GlobalNumbers->getNumber(R);
   return cmpNumbers(LNumber, RNumber);
 }
 
 /// cmpType - compares two types,
 /// defines total ordering among the types set.
 /// See method declaration comments for more details.
-int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
+int PreciseFunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
   PointerType *PTyL = dyn_cast<PointerType>(TyL);
   PointerType *PTyR = dyn_cast<PointerType>(TyR);
 
   const DataLayout &DL = FnL->getParent()->getDataLayout();
   if (PTyL && PTyL->getAddressSpace() == 0)
     TyL = DL.getIntPtrType(TyL);
   if (PTyR && PTyR->getAddressSpace() == 0)
     TyR = DL.getIntPtrType(TyR);
int PreciseFunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
   }
   }
 }
 
 // Determine whether the two operations are the same except that pointer-to-A
 // and pointer-to-B are equivalent. This should be kept in sync with
 // Instruction::isSameOperationAs.
 // Read method declaration comments for more details.
-int FunctionComparator::cmpOperations(const Instruction *L,
+int PreciseFunctionComparator::cmpOperations(const Instruction *L,
                                              const Instruction *R,
                                              bool &needToCmpOperands) const {
   needToCmpOperands = true;
   if (int Res = cmpValues(L, R))
     return Res;
 
   // Differences from Instruction::isSameOperationAs:
   //  * replace type comparison with calls to cmpTypes.
   //  * we test for I->getRawSubclassOptionalData (nuw/nsw/tail) at the top.
   //  * because of the above, we don't test for the tail bit on calls later on.
for (unsigned i = 0, e = PNL->getNumIncomingValues(); i != e; ++i) {
         return Res;
     }
   }
   return 0;
 }
 
 // Determine whether two GEP operations perform the same underlying arithmetic.
 // Read method declaration comments for more details.
-int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
+int PreciseFunctionComparator::cmpGEPs(const GEPOperator *GEPL,
                                        const GEPOperator *GEPR) const {
   unsigned int ASL = GEPL->getPointerAddressSpace();
   unsigned int ASR = GEPR->getPointerAddressSpace();
 
   if (int Res = cmpNumbers(ASL, ASR))
     return Res;
 
   // When we have target data, we can reduce the GEP down to the value in bytes
   // added to the address.
int PreciseFunctionComparator::cmpGEPs(const GEPOperator *GEPL,
   for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
     if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
       return Res;
   }
 
   return 0;
 }
 
-int FunctionComparator::cmpInlineAsm(const InlineAsm *L,
+int PreciseFunctionComparator::cmpInlineAsm(const InlineAsm *L,
                                             const InlineAsm *R) const {
   // InlineAsm's are uniqued. If they are the same pointer, obviously they are
   // the same, otherwise compare the fields.
   if (L == R)
     return 0;
   if (int Res = cmpTypes(L->getFunctionType(), R->getFunctionType()))
     return Res;
   if (int Res = cmpMem(L->getAsmString(), R->getAsmString()))
     return Res;
   if (int Res = cmpMem(L->getConstraintString(), R->getConstraintString()))
     return Res;
   if (int Res = cmpNumbers(L->hasSideEffects(), R->hasSideEffects()))
     return Res;
   if (int Res = cmpNumbers(L->isAlignStack(), R->isAlignStack()))
     return Res;
   if (int Res = cmpNumbers(L->getDialect(), R->getDialect()))
     return Res;
   assert(L->getFunctionType() != R->getFunctionType());
   return 0;
 }
 
 /// Compare two values used by the two functions under pair-wise comparison. If
 /// this is the first time the values are seen, they're added to the mapping so
 /// that we will detect mismatches on next use.
 /// See comments in declaration for more details.
-int FunctionComparator::cmpValues(const Value *L, const Value *R) const {
+int PreciseFunctionComparator::cmpValues(const Value *L, const Value *R) const {
   // Catch self-reference case.
   if (L == FnL) {
     if (R == FnR)
       return 0;
     return -1;
   }
   if (R == FnR) {
     if (L == FnL)
int PreciseFunctionComparator::cmpValues(const Value *L, const Value *R) const {
 
   auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())),
        RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size()));
 
   return cmpNumbers(LeftSN.first->second, RightSN.first->second);
 }
 
 // Test whether two basic blocks have equivalent behaviour.
-int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
+int PreciseFunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
                                               const BasicBlock *BBR) const {
   BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
   BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
 
   do {
     bool needToCmpOperands = true;
     if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands))
       return Res;
     if (needToCmpOperands) {
int PreciseFunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
 
   if (InstL != InstLE && InstR == InstRE)
     return 1;
   if (InstL == InstLE && InstR != InstRE)
     return -1;
   return 0;
 }
 
-int FunctionComparator::compareSignature() const {
+int PreciseFunctionComparator::compareSignature() const {
   if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes()))
     return Res;
 
   if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC()))
     return Res;
 
   if (FnL->hasGC()) {
     if (int Res = cmpMem(FnL->getGC(), FnR->getGC()))
for (Function::const_arg_iterator ArgLI = FnL->arg_begin(),
        ArgLI != ArgLE; ++ArgLI, ++ArgRI) {
     if (cmpValues(&*ArgLI, &*ArgRI) != 0)
       llvm_unreachable("Arguments repeat!");
   }
   return 0;
 }
 
 // Test whether the two functions have equivalent behaviour.
-int FunctionComparator::compare() {
+int PreciseFunctionComparator::compare() {
   beginCompare();
 
   if (int Res = compareSignature())
     return Res;
 
   // We do a CFG-ordered walk since the actual ordering of the blocks in the
   // linked list is immaterial. Our walk starts at the entry block for both
   // functions, then takes each block from each terminator in order. As an

 // successors of each basic block in depth first order), and the order of
 // opcodes of each instruction within each of these basic blocks. This mirrors
 // the strategy compare() uses to compare functions by walking the BBs in depth
 // first order and comparing each instruction in sequence. Because this hash
 // does not look at the operands, it is insensitive to things such as the
 // target of calls and the constants used in the function, which makes it useful
 // when possibly merging functions which are the same modulo constants and call
 // targets.
-FunctionComparator::FunctionHash FunctionComparator::functionHash(Function &F) {
+PreciseFunctionComparator::FunctionHash
+PreciseFunctionComparator::functionHash(Function &F) {
   HashAccumulator64 H;
   H.add(F.isVarArg());
   H.add(F.arg_size());
 
   SmallVector<const BasicBlock *, 8> BBs;
   SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
 
-  // Walk the blocks in the same order as FunctionComparator::cmpBasicBlocks(),
-  // accumulating the hash of the function "structure." (BB and opcode sequence)
+  // Walk the blocks in the same order as
+  // PreciseFunctionComparator::cmpBasicBlocks(), accumulating the hash of the
+  // function "structure." (BB and opcode sequence)
   BBs.push_back(&F.getEntryBlock());
   VisitedBBs.insert(BBs[0]);
   while (!BBs.empty()) {
     const BasicBlock *BB = BBs.pop_back_val();
     // This random value acts as a block header, as otherwise the partition of
     // opcodes into BBs wouldn't affect the hash, only the order of the opcodes
     H.add(45798);
     for (auto &Inst : *BB) {
       H.add(Inst.getOpcode());
     }
     const Instruction *Term = BB->getTerminator();
     for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
       if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
         continue;
       BBs.push_back(Term->getSuccessor(i));
     }
   }
   return H.getHash();
 }
+
+unsigned PartialFunctionComparator::CurID = 0;
+
+// Any two pointers in the same address space are equivalent, intptr_t and
+// pointers are equivalent. Otherwise, standard type equivalence rules apply.
+bool PartialFunctionComparator::isEquivalentType(Type *Ty1, Type *Ty2) const {
+  if (Ty1 == Ty2)
+    return true;
+  if (Ty1->getTypeID() != Ty2->getTypeID()) {
+    LLVMContext &Ctx = Ty1->getContext();
+    if (isa<PointerType>(Ty1) && Ty2 == DL->getIntPtrType(Ctx))
+      return true;
+    if (isa<PointerType>(Ty2) && Ty1 == DL->getIntPtrType(Ctx))
+      return true;
+    return false;
+  }
+
+  switch (Ty1->getTypeID()) {
+  default:
+    llvm_unreachable("Unknown type!");
+    // Fall through in Release mode.
+  case Type::IntegerTyID:
+  case Type::FixedVectorTyID:
+  case Type::ScalableVectorTyID:
+    // Ty1 == Ty2 would have returned true earlier.
+    return false;
+
+  case Type::VoidTyID:
+  case Type::FloatTyID:
+  case Type::DoubleTyID:
+  case Type::X86_FP80TyID:
+  case Type::FP128TyID:
+  case Type::PPC_FP128TyID:
+  case Type::LabelTyID:
+  case Type::MetadataTyID:
+    return true;
+
+  case Type::PointerTyID: {
+    PointerType *PTy1 = cast<PointerType>(Ty1);
+    PointerType *PTy2 = cast<PointerType>(Ty2);
+    return PTy1->getAddressSpace() == PTy2->getAddressSpace();
+  }
+
+  case Type::StructTyID: {
+    StructType *STy1 = cast<StructType>(Ty1);
+    StructType *STy2 = cast<StructType>(Ty2);
+    if (STy1->getNumElements() != STy2->getNumElements())
+      return false;
+
+    if (STy1->isPacked() != STy2->isPacked())
+      return false;
+
+    for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) {
+      if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i)))
+        return false;
+    }
+    return true;
+  }
+
+  case Type::FunctionTyID: {
+    FunctionType *FTy1 = cast<FunctionType>(Ty1);
+    FunctionType *FTy2 = cast<FunctionType>(Ty2);
+    if (FTy1->getNumParams() != FTy2->getNumParams() ||
+        FTy1->isVarArg() != FTy2->isVarArg())
+      return false;
+
+    if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType()))
+      return false;
+
+    for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) {
+      if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i)))
+        return false;
+    }
+    return true;
+  }
+
+  case Type::ArrayTyID: {
+    ArrayType *ATy1 = cast<ArrayType>(Ty1);
+    ArrayType *ATy2 = cast<ArrayType>(Ty2);
+    return ATy1->getNumElements() == ATy2->getNumElements() &&
+           isEquivalentType(ATy1->getElementType(), ATy2->getElementType());
+  }
+  }
+}
+
+// Determine whether the two operations are the same except that pointer-to-A
+// and pointer-to-B are equivalent. This should be kept in sync with
+// Instruction::isSameOperationAs.
+bool PartialFunctionComparator::isEquivalentOperation(
+    const Instruction *I1, const Instruction *I2) const {
+  // Differences from Instruction::isSameOperationAs:
+  //  * replace type comparison with calls to isEquivalentType.
+  //  * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top
+  //  * because of the above, we don't test for the tail bit on calls later on
+  if (I1->getOpcode() != I2->getOpcode() ||
+      I1->getNumOperands() != I2->getNumOperands() ||
+      !isEquivalentType(I1->getType(), I2->getType()) ||
+      !I1->hasSameSubclassOptionalData(I2))
+    return false;
+
+  // We have two instructions of identical opcode and #operands.  Check to see
+  // if all operands are the same type
+  for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i)
+    if (!isEquivalentType(I1->getOperand(i)->getType(),
+                          I2->getOperand(i)->getType()))
+      return false;
+
+  // Check special state that is a part of some instructions.
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) {
+    const LoadInst *LI2 = cast<LoadInst>(I2);
+    return LI->isVolatile() == LI2->isVolatile() &&
+           LI->getAlignment() == LI2->getAlignment() &&
+           LI->getOrdering() == LI2->getOrdering() &&
+           LI->getSyncScopeID() == LI2->getSyncScopeID() &&
+           LI->getMetadata(LLVMContext::MD_range) ==
+               LI2->getMetadata(LLVMContext::MD_range);
+  }
+  if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
+    return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
+           SI->getAlignment() == cast<StoreInst>(I2)->getAlignment() &&
+           SI->getOrdering() == cast<StoreInst>(I2)->getOrdering() &&
+           SI->getSyncScopeID() == cast<StoreInst>(I2)->getSyncScopeID();
+  if (const AllocaInst *AI = dyn_cast<AllocaInst>(I1)) {
+    if (AI->getArraySize() != cast<AllocaInst>(I2)->getArraySize() ||
+        AI->getAlignment() != cast<AllocaInst>(I2)->getAlignment())
+      return false;
+
+    // If size is known, I2 can be seen as equivalent to I1 if it allocates
+    // the same or less memory.
+    if (DL->getTypeAllocSize(AI->getAllocatedType()) <
+        DL->getTypeAllocSize(cast<AllocaInst>(I2)->getAllocatedType()))
+      return false;
+
+    return true;
+  }
+  if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
+    return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
+  if (const CallInst *CI = dyn_cast<CallInst>(I1))
+    return CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
+           CI->getAttributes() == cast<CallInst>(I2)->getAttributes();
+  if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
+    return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
+           CI->getAttributes() == cast<InvokeInst>(I2)->getAttributes();
+  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1))
+    return IVI->getIndices() == cast<InsertValueInst>(I2)->getIndices();
+  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1))
+    return EVI->getIndices() == cast<ExtractValueInst>(I2)->getIndices();
+  if (const FenceInst *FI = dyn_cast<FenceInst>(I1))
+    return FI->getOrdering() == cast<FenceInst>(I2)->getOrdering() &&
+           FI->getSyncScopeID() == cast<FenceInst>(I2)->getSyncScopeID();
+  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I1)) {
+    const AtomicCmpXchgInst *CXI2 = cast<AtomicCmpXchgInst>(I2);
+    return CXI->isVolatile() == CXI2->isVolatile() &&
+           CXI->isWeak() == CXI2->isWeak() &&
+           CXI->getSuccessOrdering() == CXI2->getSuccessOrdering() &&
+           CXI->getFailureOrdering() == CXI2->getFailureOrdering() &&
+           CXI->getSyncScopeID() == CXI2->getSyncScopeID();
+  }
+  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I1))
+    return RMWI->getOperation() == cast<AtomicRMWInst>(I2)->getOperation() &&
+           RMWI->isVolatile() == cast<AtomicRMWInst>(I2)->isVolatile() &&
+           RMWI->getOrdering() == cast<AtomicRMWInst>(I2)->getOrdering() &&
+           RMWI->getSyncScopeID() == cast<AtomicRMWInst>(I2)->getSyncScopeID();
+
+  return true;
+}
+
+// Determine whether two GEP operations perform the same underlying arithmetic.
+bool PartialFunctionComparator::isEquivalentGEP(const GEPOperator *GEP1,
+                                                const GEPOperator *GEP2) {
+  // When we have target data, we can reduce the GEP down to the value in bytes
+  // added to the address.
+  if (GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) {
+    SmallVector<Value *, 8> Indices1(GEP1->idx_begin(), GEP1->idx_end());
+    SmallVector<Value *, 8> Indices2(GEP2->idx_begin(), GEP2->idx_end());
+    uint64_t Offset1 =
+        DL->getIndexedOffsetInType(GEP1->getSourceElementType(), Indices1);
+    uint64_t Offset2 =
+        DL->getIndexedOffsetInType(GEP2->getSourceElementType(), Indices2);
+    return Offset1 == Offset2;
+  }
+
+  if (GEP1->getPointerOperand()->getType() !=
+      GEP2->getPointerOperand()->getType())
+    return false;
+
+  if (GEP1->getNumOperands() != GEP2->getNumOperands())
+    return false;
+
+  for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) {
+    if (!enumerate(GEP1->getOperand(i), GEP2->getOperand(i)))
+      return false;
+  }
+
+  return true;
+}
+
+// Compare two values used by the two functions under pair-wise comparison. If
+// this is the first time the values are seen, they're added to the mapping so
+// that we will detect mismatches on next use.
+bool PartialFunctionComparator::enumerate(const Value *V1, const Value *V2,
+                                          bool NoSelfRef /*=false*/) {
+  // Check for function @f1 referring to itself and function @f2 referring to
+  // itself. For compatibility with llvm's MergeFunctions, disallow referring to
+  // each other, or both referring to either of them.
+  if (!NoSelfRef && V1 == F1 && V2 == F2)
+    return true;
+
+  // FIXME: This is very conservative for now, but keeping this for thinlto.
+  if (isa<GlobalVariable>(V1) || isa<GlobalVariable>(V2))
+    return false;
+  if (const Constant *C1 = dyn_cast<Constant>(V1)) {
+    if (V1 == V2)
+      return true;
+    const Constant *C2 = dyn_cast<Constant>(V2);
+    if (!C2)
+      return false;
+    // TODO: constant expressions with GEP or references to F1 or F2.
+    if (C1->isNullValue() && C2->isNullValue() &&
+        isEquivalentType(C1->getType(), C2->getType()))
+      return true;
+    // Try bitcasting C2 to C1's type. If the bitcast is legal and returns C1
+    // then they must have equal bit patterns. Aggregate types cannot be
+    // bitcast.
+    if (C1->getType()->isAggregateType() || C2->getType()->isAggregateType())
+      return false;
+    return C1->getType()->canLosslesslyBitCastTo(C2->getType()) &&
+           C1 == ConstantExpr::getBitCast(const_cast<Constant *>(C2),
+                                          C1->getType());
+  }
+
+  if (isa<InlineAsm>(V1) || isa<InlineAsm>(V2))
+    return V1 == V2;
+
+  // Check that V1 maps to V2. If we find a value that V1 maps to then we simply
+  // check whether it's equal to V2. When there is no mapping then we need to
+  // ensure that V2 isn't already equivalent to something else. For this
+  // purpose, we track the V2 values in a set.
+
+  ValueToValueMapTy::iterator I = id_map.find(V1);
+  if (I != id_map.end())
+    return V2 == I->second;
+  // FIXME: Const casts!!!
+  if (!seen_values.insert(std::make_pair(V2, const_cast<Value *>(V1))).second)
+    return false;
+  id_map[V1] = const_cast<Value *>(V2);
+  return true;
+}
+
+/// Test whether two basic blocks have equivalent behaviour. Returns true if the
+/// blocks can be merged, false if they cannot. Differing instructions are
+/// recorded in DifferingInstructions.
+bool PartialFunctionComparator::compare(
+    const BasicBlock *BB1, const BasicBlock *BB2,
+    std::list<std::pair<const PHINode *, const PHINode *>> *PHIsFound) {
+  BasicBlock::const_iterator F1I, F1E, F2I, F2E;
+
+  for (F1I = BB1->begin(), F1E = BB1->end(), F2I = BB2->begin(),
+      F2E = BB2->end();
+       F1I != F1E && F2I != F2E; ++F1I, ++F2I) {
+    // Skip debug information
+    const CallInst *DbgCall;
+    while (F1I != F1E && (DbgCall = dyn_cast<CallInst>(F1I)) &&
+           DbgCall->getCalledFunction() &&
+           DbgCall->getCalledFunction()->hasName() &&
+           DbgCall->getCalledFunction()->getName().startswith("llvm.dbg."))
+      ++F1I;
+
+    while (F2I != F2E && (DbgCall = dyn_cast<CallInst>(F2I)) &&
+           DbgCall->getCalledFunction() &&
+           DbgCall->getCalledFunction()->hasName() &&
+           DbgCall->getCalledFunction()->getName().startswith("llvm.dbg."))
+      ++F2I;
+
+    if (F1I == F1E || F2I == F2E)
+      break;
+
+    // Ok, we're dealing with real instructions. Check a few cases that will
+    // prevent merging first.
+    const Instruction *F1In = &*F1I;
+    const Instruction *F2In = &*F2I;
+
+    // Cannot merge insts that differ in whether they have uses
+    if (F1In->use_empty() != F2In->use_empty()) {
+      // TODO: Could implement merging for this case (would need to introduce a
+      // dummy value in the PHI node etc.)
+      return false;
+    }
+
+    // Cannot merge insts whose types are non-equivalent
+    if (!isEquivalentType(F1In->getType(), F2In->getType())) {
+      return false;
+    }
+
+    // TODO:  Currently cannot merge InvokeInsts with differing result types
+    //        that have uses. We cannot push up a bitcast into their block after
+    //        them because they are terminators. Would need to insert an
+    //        additional BB.
+    if (isa<InvokeInst>(F1In) && !F1In->use_empty() &&
+        F1In->getType() != F2In->getType())
+      return false;
+
+    if (!enumerate(F1In, F2In))
+      goto differing_instructions;
+
+    if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(F1In)) {
+      const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(F2In);
+      if (!GEP2)
+        goto differing_instructions;
+
+      if (!enumerate(GEP1->getPointerOperand(), GEP2->getPointerOperand()))
+        goto differing_instructions;
+
+      if (!isEquivalentGEP(GEP1, GEP2))
+        goto differing_instructions;
+    } else if (const PHINode *Phi1 = dyn_cast<PHINode>(F1In)) {
+      const PHINode *Phi2 = dyn_cast<PHINode>(F2In);
+      // We can't currently merge a PHI and non-PHI instruction
+      if (!Phi2)
+        return false;
+
+      // We can't currently merge PHI nodes with different numbers of incoming
+      // values
+      if (F1In->getNumOperands() != F2In->getNumOperands())
+        return false;
+
+      // We need to treat PHI nodes specially. Their incoming values may be in a
+      // different order even if they are equivalent. We can't compare them
+      // until we've seen the incoming blocks and know which values are
+      // equivalent. Therefore postpone PHINode comparison until the end.
+      PHIsFound->push_back(std::make_pair(Phi1, Phi2));
+    } else {
+      if (!isEquivalentOperation(F1In, F2In))
+        goto differing_instructions;
+
+      bool IsCall = isa<CallInst>(F1In);
+      assert(F1In->getNumOperands() == F2In->getNumOperands());
+      for (unsigned i = 0, e = F1In->getNumOperands(); i != e; ++i) {
+        Value *OpF1 = F1In->getOperand(i);
+        Value *OpF2 = F2In->getOperand(i);
+
+        // Allow self-reference if this is a call instruction and the last
+        // operand which is the called function
+        bool AllowSelfRef = IsCall && (i + 1) == e;
+
+        if (!enumerate(OpF1, OpF2, !AllowSelfRef))
+          goto differing_instructions;
+
+        if (!isEquivalentType(OpF1->getType(), OpF2->getType()))
+          goto differing_instructions;
+
+        if ((OpF1 == F1 && OpF2 == F2) || (OpF1 == F2 && OpF2 == F1))
+          SelfRefInstructions[F1In] = F2In;
+      }
+    }
+
+    continue;
+
+  differing_instructions:
+    // Cannot merge functions with differing landing pad instructions yet. They
+    // would need special treatment which involves updating the corresponding
+    // invoke instructions.
+    if (isa<LandingPadInst>(F1In))
+      return false;
+    if (isa<InvokeInst>(F1In))
+      return false;
+
+    DifferingInstructions[F1In] = F2In;
+  }
+
+  // We cannot currently merge basic blocks with different instruction counts
+  return F1I == F1E && F2I == F2E;
+}
+
+bool PartialFunctionComparator::comparePHIs(
+    const std::list<std::pair<const PHINode *, const PHINode *>> &PHIs) {
+  if (PHIs.empty())
+    return true;
+
+  for (std::list<std::pair<const PHINode *, const PHINode *>>::const_iterator
+           I = PHIs.begin(),
+           E = PHIs.end();
+       I != E; ++I) {
+    const PHINode *Phi1 = I->first, *Phi2 = I->second;
+
+    for (unsigned ValId = 0, ValNum = Phi1->getNumIncomingValues();
+         ValId < ValNum; ++ValId) {
+      Value *Phi1Val = Phi1->getIncomingValue(ValId);
+
+      // Get corresponding Phi2Val
+      Value *BBinPhi2Val = getF1toF2Map()[Phi1->getIncomingBlock(ValId)];
+
+      if (!BBinPhi2Val)
+        return false; // Currently can't handle differing predecessor blocks
+
+      BasicBlock *BBinPhi2 = cast<BasicBlock>(BBinPhi2Val);
+      Value *Phi2Val = Phi2->getIncomingValueForBlock(BBinPhi2);
+
+      // Enumerate the values. If the PHI node references the function itself (a
+      // very rare case), we mark it as different (NoSelfRef). This is only
+      // necessary for outline merging, not equiv merging. TODO: Make equal
+      // merging possible with such PHI nodes.
+      if (!enumerate(Phi1Val, Phi2Val, /*NoSelfRef=*/true)) {
+        DifferingInstructions[Phi1] = Phi2;
+        break;
+      }
+    }
+  }
+
+  return true;
+}
+
+// Test whether the two functions have equivalent behaviour.
+bool PartialFunctionComparator::compare() {
+  // We need to recheck everything, but check the things that weren't included
+  // in the hash first.
+  if (F1->getAttributes() != F2->getAttributes())
+    goto not_mergeable;
+
+  if (F1->hasGC() != F2->hasGC())
+    goto not_mergeable;
+
+  if (F1->hasGC() && F1->getGC() != F2->getGC())
+    goto not_mergeable;
+
+  if (!F1->getSection().equals(F2->getSection()))
+    goto not_mergeable;
+
+  if (F1->isVarArg() != F2->isVarArg())
+    goto not_mergeable;
+
+  if (F1->isInterposable() != F2->isInterposable())
+    goto not_mergeable;
+
+  if (F1->size() != F2->size())
+    goto not_mergeable;
+
+  // TODO: if it's internal and only used in direct calls, we could handle
+  // this case too.
+  if (F1->getCallingConv() != F2->getCallingConv())
+    goto not_mergeable;
+
+  if (!isEquivalentType(F1->getFunctionType(), F2->getFunctionType()))
+    goto not_mergeable;
+
+  assert(F1->arg_size() == F2->arg_size() &&
+         "Identically typed functions have different numbers of args!");
+
+  // Visit the arguments so that they get enumerated in the order they're
+  // passed in.
+  for (Function::const_arg_iterator f1i = F1->arg_begin(),
+                                    f2i = F2->arg_begin(), f1e = F1->arg_end();
+       f1i != f1e; ++f1i, ++f2i) {
+    if (!enumerate(&*f1i, &*f2i))
+      llvm_unreachable("Arguments repeat!");
+  }
+
+  // We do a CFG-ordered walk since the actual ordering of the blocks in the
+  // linked list is immaterial. Our walk starts at the entry block for both
+  // functions, then takes each block from each terminator in order. As an
+  // artifact, this also means that unreachable blocks are ignored.
+  {
+    SmallVector<const BasicBlock *, 8> F1BBs, F2BBs;
+    SmallSet<const BasicBlock *, 32> VisitedBBs; // in terms of F1.
+    std::list<std::pair<const PHINode *, const PHINode *>> PHIsFound;
+
+    F1BBs.push_back(&F1->getEntryBlock());
+    F2BBs.push_back(&F2->getEntryBlock());
+
+    VisitedBBs.insert(F1BBs[0]);
+    while (!F1BBs.empty()) {
+      const BasicBlock *F1BB = F1BBs.pop_back_val();
+      const BasicBlock *F2BB = F2BBs.pop_back_val();
+
+      // Check for control flow divergence
+      if (!enumerate(F1BB, F2BB))
+        goto not_mergeable;
+
+      const Instruction *F1TI = F1BB->getTerminator();
+      const Instruction *F2TI = F2BB->getTerminator();
+
+      // TODO: Implement merging of blocks with different numbers of
+      // instructions.
+      if (F1TI->getNumSuccessors() != F2TI->getNumSuccessors() ||
+          F1BB->size() != F2BB->size())
+        goto not_mergeable;
+
+      // The actual instruction-by-instruction comparison
+      if (!compare(F1BB, F2BB, &PHIsFound))
+        goto not_mergeable;
+
+      // FIXME: Count this in compare(F1BB,F2BB) so it doesn't include debug
+      // instructions.
+      InstructionCount += std::max(F1BB->size(), F2BB->size());
+
+      assert(F1TI->getNumSuccessors() == F2TI->getNumSuccessors());
+      for (unsigned i = 0, e = F1TI->getNumSuccessors(); i != e; ++i) {
+        if (!VisitedBBs.insert(F1TI->getSuccessor(i)).second)
+          continue;
+
+        F1BBs.push_back(F1TI->getSuccessor(i));
+        F2BBs.push_back(F2TI->getSuccessor(i));
+      }
+    }
+
+    BasicBlockCount = VisitedBBs.size();
+
+    // After we've seen all values and BBs, compare the PHI nodes
+    if (!comparePHIs(PHIsFound))
+      goto not_mergeable;
+  }
+
+  if (DifferingInstructions.size()) {
+    // Currently we can't merge vararg functions with differing instructions.
+    // TODO: Explore whether this is feasible; the difficult bit is the
+    // additional argument we need to add.
+    if (F1->isVarArg())
+      goto not_mergeable;
+
+    isDifferent = true;
+    DifferingInstructionsCount += DifferingInstructions.size();
+
+    LLVM_DEBUG(
+        float Metric = ((float)InstructionCount - DifferingInstructionsCount) /
+                       InstructionCount * 100;
+        dbgs() << "Similar fns: " << F1->getName() << " and " << F2->getName()
+               << " bbs=" << BasicBlockCount << " insts=" << InstructionCount
+               << " failed=" << DifferingInstructionsCount
+               << " metric=" << format("%0.2f", Metric) << '\n');
+  }
+
+  return true;
+
+not_mergeable:
+  // Fail: cannot merge the two functions
+  isNotMergeable = true;
+  return false;
+}
+
+bool PartialFunctionComparator::isExactMatch() {
+  return (!isNotMergeable && !isDifferent);
+}
+
+bool PartialFunctionComparator::isMergeCandidate() {
+  if (isNotMergeable)
+    return false;
+
+  if (!isDifferent)
+    return true;
+
+  // Tolerate higher difference with higher similarity.
+  if (InstructionCount > 100 && DifferingInstructionsCount <= 60 &&
+      getSimilarityMetric() > 90)
+    return true;
+
+  return false;
+}

llvm/test/Transforms/MergeSimilarFunc/merge-alloca.ll

+;RUN: opt -mergefunc -mergesimilarfunc -mergesimilarfunc-level=all -S < %s | FileCheck %s
+;
+; Test whether mergefunc merges allocas of different sizes correctly
+;
+
+target datalayout = "e-m:e-p:32:32-i1:32-i64:64-a:0-v32:32-n16:32"
+
+%struct.A = type { i32, i32 }
+%struct.B = type { i32, i32, i32 }
+
+; Function Attrs: nounwind optsize
+define void @f1() #0 {
+; CHECK-LABEL: @f1__merged(
+; CHECK: alloca %struct.A
+; CHECK: alloca %struct.B
+entry:
+  %a = alloca %struct.A, align 4
+  %0 = bitcast %struct.A* %a to i8*
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  ret void
+}
+
+; Function Attrs: optsize
+declare void @externalFun(i8*) #1
+
+; Function Attrs: nounwind optsize
+define void @f2() #0 {
+entry:
+  %a = alloca %struct.B, align 4
+  %0 = bitcast %struct.B* %a to i8*
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  call void @externalFun(i8* %0) #2
+  ret void
+}
+
+; Function Attrs: nounwind optsize
+define void @f3() #0 {
+entry:
+  %a = alloca i8, align 1
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  call void @externalFun(i8* %a) #2
+  ret void
+}
+
+attributes #0 = { nounwind optsize "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { optsize "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind optsize }

llvm/test/Transforms/MergeSimilarFunc/merge-debug-info-2.ll

+; RUN: opt -S -mergefunc -mergesimilarfunc -mergesimilarfunc-diff-min-insts=5 < %s | FileCheck %s
+; This used to fail with assertion in CloneFunction
+; REQUIRES: asserts
+; CHECK-LABEL: @foo__merged(
+
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+target triple = "arm64-apple-ios8.0.0"
+
+%struct.wibble = type { %struct.wibble.0*, %struct.wibble* }
+%struct.wibble.0 = type { i64*, i8*, i64*, i64*, %struct.eggs*, %struct.wibble* }
+%struct.eggs = type { %struct.wombat*, %struct.eggs* }
+%struct.wombat = type { i8*, %struct.blam*, %struct.blam* }
+%struct.blam = type { i8*, %struct.blam* }
+%struct.snork = type { %struct.bar*, %struct.snork* }
+%struct.bar = type { i64*, i8* }
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #0
+
+; Function Attrs: minsize nounwind optsize ssp uwtable
+define hidden void @foo(%struct.wibble* %arg) #1 align 2 !dbg !4 {
+bb:
+  %tmp = alloca %struct.wibble*, align 8
+  %tmp2 = load %struct.wibble*, %struct.wibble** %tmp, align 8, !dbg !12
+  %tmp3 = icmp ne %struct.wibble* %tmp2, null, !dbg !13
+  br i1 %tmp3, label %bb4, label %bb13, !dbg !14
+
+bb4:                                              ; preds = %bb
+  call void @foo.1() #3, !dbg !26
+  unreachable
+
+bb13:                                             ; preds = %bb
+  ret void, !dbg !27
+}
+
+; Function Attrs: minsize nounwind optsize ssp uwtable
+declare hidden void @foo.1() #1 align 2
+
+; Function Attrs: minsize nounwind optsize ssp uwtable
+define void @quux() unnamed_addr #1 align 2 !dbg !28 {
+bb:
+  ret void
+}
+
+; Function Attrs: minsize nounwind optsize ssp uwtable
+define hidden void @baz(%struct.snork* %arg) #1 align 2 !dbg !30 {
+bb:
+  %tmp = alloca %struct.snork*, align 8
+  %tmp2 = load %struct.snork*, %struct.snork** %tmp, align 8, !dbg !31
+  %tmp3 = icmp ne %struct.snork* %tmp2, null, !dbg !32
+  br i1 %tmp3, label %bb4, label %bb13, !dbg !33
+
+bb4:                                              ; preds = %bb
+  call void @blam() #3, !dbg !42
+  unreachable
+
+bb13:                                             ; preds = %bb
+  ret void, !dbg !43
+}
+
+; Function Attrs: minsize nounwind optsize ssp uwtable
+declare hidden void @blam() #1 align 2
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { minsize nounwind optsize ssp uwtable }
+attributes #2 = { nounwind }
+attributes #3 = { minsize optsize }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "(based on LLVM 5.0.0)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly)
+!1 = !DIFile(filename: "foo.cpp", directory: "/")
+!2 = !{i32 2, !"Debug Info Version", i32 3}
+!3 = !{i32 7, !"PIC Level", i32 2}
+!4 = distinct !DISubprogram(name: "delete", scope: !5, file: !5, line: 31, type: !6, isLocal: false, isDefinition: true, scopeLine: 32, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
+!5 = !DIFile(filename: "foo.h", directory: "/")
+!6 = !DISubroutineType(types: !7)
+!7 = !{}
+!9 = !{!"any pointer", !10, i64 0}
+!10 = !{!"omnipotent char", !11, i64 0}
+!11 = !{!"Simple C++ TBAA"}
+!12 = !DILocation(line: 33, column: 11, scope: !4)
+!13 = !DILocation(line: 33, column: 16, scope: !4)
+!14 = !DILocation(line: 33, column: 5, scope: !4)
+!21 = !{!"_ZTSN", !9, i64 0, !9, i64 8}
+!23 = !DILocation(line: 37, column: 25, scope: !4)
+!24 = !DILocation(line: 37, column: 31, scope: !4)
+!25 = !{!21, !9, i64 0}
+!26 = !DILocation(line: 37, column: 7, scope: !4)
+!27 = !DILocation(line: 41, column: 3, scope: !4)
+!28 = distinct !DISubprogram(name: "~destruct", scope: !29, file: !29, line: 31, type: !6, isLocal: false, isDefinition: true, scopeLine: 32, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
+!29 = !DIFile(filename: "bar.h", directory: "/")
+!30 = distinct !DISubprogram(name: "delete", scope: !5, file: !5, line: 31, type: !6, isLocal: false, isDefinition: true, scopeLine: 32, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
+!31 = !DILocation(line: 33, column: 11, scope: !30)
+!32 = !DILocation(line: 33, column: 16, scope: !30)
+!33 = !DILocation(line: 33, column: 5, scope: !30)
+!40 = !DILocation(line: 37, column: 25, scope: !30)
+!41 = !DILocation(line: 37, column: 31, scope: !30)
+!42 = !DILocation(line: 37, column: 7, scope: !30)
+!43 = !DILocation(line: 41, column: 3, scope: !30)

llvm/test/Transforms/MergeSimilarFunc/merge-debug-info.ll

+; This used to fail the verifier with the following error:
+; "dbg attachment points at wrong subprogram for function"
+; RUN: opt -S -mergefunc -mergesimilarfunc < %s | FileCheck %s
+; REQUIRES: asserts
+; CHECK-LABEL: @bar__merged(
+target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
+
+%struct.str_type = type { i8*, i32, i32 }
+
+; Function Attrs: nounwind optsize
+define i32 @bar(i8* %b) #0 !dbg !14 {
+entry:
+  %retval = alloca i32, align 4
+  %b.addr = alloca i8*, align 4
+  %res = alloca i32, align 4
+  %ee = alloca %struct.str_type*, align 4
+  %cleanup.dest.slot = alloca i32
+  store i8* %b, i8** %b.addr, align 4, !tbaa !31
+  call void @llvm.dbg.declare(metadata i8** %b.addr, metadata !18, metadata !35), !dbg !36
+  %0 = bitcast i32* %res to i8*, !dbg !37
+  call void @llvm.lifetime.start(i64 4, i8* %0) #4, !dbg !37
+  call void @llvm.dbg.declare(metadata i32* %res, metadata !19, metadata !35), !dbg !38
+  %1 = bitcast %struct.str_type** %ee to i8*, !dbg !39
+  call void @llvm.lifetime.start(i64 4, i8* %1) #4, !dbg !39
+  call void @llvm.dbg.declare(metadata %struct.str_type** %ee, metadata !20, metadata !35), !dbg !40
+  %2 = load i8*, i8** %b.addr, align 4, !dbg !41, !tbaa !31
+  %3 = bitcast i8* %2 to %struct.str_type*, !dbg !42
+  store %struct.str_type* %3, %struct.str_type** %ee, align 4, !dbg !40, !tbaa !31
+  %4 = load %struct.str_type*, %struct.str_type** %ee, align 4, !dbg !43, !tbaa !31
+  %set = getelementptr inbounds %struct.str_type, %struct.str_type* %4, i32 0, i32 1, !dbg !45
+  %5 = load i32, i32* %set, align 4, !dbg !45, !tbaa !46
+  %tobool = icmp ne i32 %5, 0, !dbg !43
+  br i1 %tobool, label %if.end4, label %if.then, !dbg !49
+
+if.then:                                          ; preds = %entry
+  %6 = load %struct.str_type*, %struct.str_type** %ee, align 4, !dbg !50, !tbaa !31
+  %set1 = getelementptr inbounds %struct.str_type, %struct.str_type* %6, i32 0, i32 1, !dbg !52
+  store i32 1, i32* %set1, align 4, !dbg !53, !tbaa !46
+  %7 = load %struct.str_type*, %struct.str_type** %ee, align 4, !dbg !54, !tbaa !31
+  %x = getelementptr inbounds %struct.str_type, %struct.str_type* %7, i32 0, i32 0, !dbg !55
+  %8 = load i8*, i8** %x, align 4, !dbg !55, !tbaa !56
+  %call = call i32 @foo(i8* %8) #5, !dbg !57
+  store i32 %call, i32* %res, align 4, !dbg !58, !tbaa !59
+  %9 = load i32, i32* %res, align 4, !dbg !60, !tbaa !59
+  %tobool2 = icmp ne i32 %9, 0, !dbg !60
+  br i1 %tobool2, label %if.then3, label %if.end, !dbg !62
+
+if.then3:                                         ; preds = %if.then
+  store i32 1, i32* %retval, align 4, !dbg !63
+  store i32 1, i32* %cleanup.dest.slot, align 4
+  br label %cleanup, !dbg !63
+
+if.end:                                           ; preds = %if.then
+  br label %if.end4, !dbg !64
+
+if.end4:                                          ; preds = %if.end, %entry
+  store i32 0, i32* %retval, align 4, !dbg !65
+  store i32 1, i32* %cleanup.dest.slot, align 4
+  br label %cleanup, !dbg !65
+
+cleanup:                                          ; preds = %if.end4, %if.then3
+  %10 = bitcast %struct.str_type** %ee to i8*, !dbg !66
+  call void @llvm.lifetime.end(i64 4, i8* %10) #4, !dbg !66
+  %11 = bitcast i32* %res to i8*, !dbg !66
+  call void @llvm.lifetime.end(i64 4, i8* %11) #4, !dbg !66
+  %12 = load i32, i32* %retval, align 4, !dbg !66
+  ret i32 %12, !dbg !66
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture) #2
+
+; Function Attrs: optsize
+declare i32 @foo(i8*) #3
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture) #2
+
+; Function Attrs: nounwind optsize
+define i32 @bar1(i8* %b) #0 !dbg !21 {
+entry:
+  %retval = alloca i32, align 4
+  %b.addr = alloca i8*, align 4
+  %res = alloca i32, align 4
+  %ee = alloca %struct.str_type*, align 4
+  %cleanup.dest.slot = alloca i32
+  store i8* %b, i8** %b.addr, align 4, !tbaa !31
+  call void @llvm.dbg.declare(metadata i8** %b.addr, metadata !23, metadata !35), !dbg !67
+  %0 = bitcast i32* %res to i8*, !dbg !68
+  call void @llvm.lifetime.start(i64 4, i8* %0) #4, !dbg !68
+  call void @llvm.dbg.declare(metadata i32* %res, metadata !24, metadata !35), !dbg !69
+  %1 = bitcast %struct.str_type** %ee to i8*, !dbg !70
+  call void @llvm.lifetime.start(i64 4, i8* %1) #4, !dbg !70
+  call void @llvm.dbg.declare(metadata %struct.str_type** %ee, metadata !25, metadata !35), !dbg !71
+  %2 = load i8*, i8** %b.addr, align 4, !dbg !72, !tbaa !31
+  %3 = bitcast i8* %2 to %struct.str_type*, !dbg !73
+  store %struct.str_type* %3, %struct.str_type** %ee, align 4, !dbg !71, !tbaa !31
+  %4 = load %struct.str_type*, %struct.str_type** %ee, align 4, !dbg !74, !tbaa !31
+  %get = getelementptr inbounds %struct.str_type, %struct.str_type* %4, i32 0, i32 2, !dbg !76
+  %5 = load i32, i32* %get, align 4, !dbg !76, !tbaa !77
+  %tobool = icmp ne i32 %5, 0, !dbg !74
+  br i1 %tobool, label %if.end4, label %if.then, !dbg !78
+
+if.then:                                          ; preds = %entry
+  %6 = load %struct.str_type*, %struct.str_type** %ee, align 4, !dbg !79, !tbaa !31
+  %get1 = getelementptr inbounds %struct.str_type, %struct.str_type* %6, i32 0, i32 2, !dbg !81
+  store i32 1, i32* %get1, align 4, !dbg !82, !tbaa !77
+  %7 = load %struct.str_type*, %struct.str_type** %ee, align 4, !dbg !83, !tbaa !31
+  %x = getelementptr inbounds %struct.str_type, %struct.str_type* %7, i32 0, i32 0, !dbg !84
+  %8 = load i8*, i8** %x, align 4, !dbg !84, !tbaa !56
+  %call = call i32 @foo(i8* %8) #5, !dbg !85
+  store i32 %call, i32* %res, align 4, !dbg !86, !tbaa !59
+  %9 = load i32, i32* %res, align 4, !dbg !87, !tbaa !59
+  %tobool2 = icmp ne i32 %9, 0, !dbg !87
+  br i1 %tobool2, label %if.then3, label %if.end, !dbg !89
+
+if.then3:                                         ; preds = %if.then
+  store i32 1, i32* %retval, align 4, !dbg !90
+  store i32 1, i32* %cleanup.dest.slot, align 4
+  br label %cleanup, !dbg !90
+
+if.end:                                           ; preds = %if.then
+  br label %if.end4, !dbg !91
+
+if.end4:                                          ; preds = %if.end, %entry
+  store i32 0, i32* %retval, align 4, !dbg !92
+  store i32 1, i32* %cleanup.dest.slot, align 4
+  br label %cleanup, !dbg !92
+
+cleanup:                                          ; preds = %if.end4, %if.then3
+  %10 = bitcast %struct.str_type** %ee to i8*, !dbg !93
+  call void @llvm.lifetime.end(i64 4, i8* %10) #4, !dbg !93
+  %11 = bitcast i32* %res to i8*, !dbg !93
+  call void @llvm.lifetime.end(i64 4, i8* %11) #4, !dbg !93
+  %12 = load i32, i32* %retval, align 4, !dbg !93
+  ret i32 %12, !dbg !93
+}
+
+attributes #0 = { nounwind optsize }
+attributes #1 = { nounwind readnone }
+attributes #2 = { argmemonly nounwind }
+attributes #3 = { optsize }
+attributes #4 = { nounwind }
+attributes #5 = { optsize }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!26, !27}
+!llvm.ident = !{!28}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "Clang $LLVM_VERSION_MAJOR.$LLVM_VERSION_MINOR (based on LLVM 3.9.0)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, retainedTypes: !3)
+!1 = !DIFile(filename: "test.i", directory: "/local/mnt/")
+!2 = !{}
+!3 = !{!4}
+!4 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !5, size: 32, align: 32)
+!5 = !DIDerivedType(tag: DW_TAG_typedef, name: "str_type", file: !1, line: 8, baseType: !6)
+!6 = !DICompositeType(tag: DW_TAG_structure_type, name: "str_type", file: !1, line: 3, size: 96, align: 32, elements: !7)
+!7 = !{!8, !10, !12}
+!8 = !DIDerivedType(tag: DW_TAG_member, name: "x", scope: !6, file: !1, line: 5, baseType: !9, size: 32, align: 32)
+!9 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: null, size: 32, align: 32)
+!10 = !DIDerivedType(tag: DW_TAG_member, name: "set", scope: !6, file: !1, line: 6, baseType: !11, size: 32, align: 32, offset: 32)
+!11 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!12 = !DIDerivedType(tag: DW_TAG_member, name: "get", scope: !6, file: !1, line: 7, baseType: !11, size: 32, align: 32, offset: 64)
+!14 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 10, type: !15, isLocal: false, isDefinition: true, scopeLine: 10, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !17)
+!15 = !DISubroutineType(types: !16)
+!16 = !{!11, !9}
+!17 = !{!18, !19, !20}
+!18 = !DILocalVariable(name: "b", arg: 1, scope: !14, file: !1, line: 10, type: !9)
+!19 = !DILocalVariable(name: "res", scope: !14, file: !1, line: 11, type: !11)
+!20 = !DILocalVariable(name: "ee", scope: !14, file: !1, line: 12, type: !4)
+!21 = distinct !DISubprogram(name: "bar1", scope: !1, file: !1, line: 24, type: !15, isLocal: false, isDefinition: true, scopeLine: 24, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !22)
+!22 = !{!23, !24, !25}
+!23 = !DILocalVariable(name: "b", arg: 1, scope: !21, file: !1, line: 24, type: !9)
+!24 = !DILocalVariable(name: "res", scope: !21, file: !1, line: 25, type: !11)
+!25 = !DILocalVariable(name: "ee", scope: !21, file: !1, line: 26, type: !4)
+!26 = !{i32 2, !"Dwarf Version", i32 4}
+!27 = !{i32 2, !"Debug Info Version", i32 3}
+!28 = !{!"Clang $LLVM_VERSION_MAJOR.$LLVM_VERSION_MINOR (based on LLVM 3.9.0)"}
+!31 = !{!32, !32, i64 0}
+!32 = !{!"any pointer", !33, i64 0}
+!33 = !{!"omnipotent char", !34, i64 0}
+!34 = !{!"Simple C/C++ TBAA"}
+!35 = !DIExpression()
+!36 = !DILocation(line: 10, column: 23, scope: !14)
+!37 = !DILocation(line: 11, column: 3, scope: !14)
+!38 = !DILocation(line: 11, column: 7, scope: !14)
+!39 = !DILocation(line: 12, column: 3, scope: !14)
+!40 = !DILocation(line: 12, column: 13, scope: !14)
+!41 = !DILocation(line: 12, column: 31, scope: !14)
+!42 = !DILocation(line: 12, column: 19, scope: !14)
+!43 = !DILocation(line: 14, column: 8, scope: !44)
+!44 = distinct !DILexicalBlock(scope: !14, file: !1, line: 14, column: 7)
+!45 = !DILocation(line: 14, column: 12, scope: !44)
+!46 = !{!47, !48, i64 4}
+!47 = !{!"str_type", !32, i64 0, !48, i64 4, !48, i64 8}
+!48 = !{!"int", !33, i64 0}
+!49 = !DILocation(line: 14, column: 7, scope: !14)
+!50 = !DILocation(line: 15, column: 5, scope: !51)
+!51 = distinct !DILexicalBlock(scope: !44, file: !1, line: 14, column: 18)
+!52 = !DILocation(line: 15, column: 9, scope: !51)
+!53 = !DILocation(line: 15, column: 13, scope: !51)
+!54 = !DILocation(line: 17, column: 16, scope: !51)
+!55 = !DILocation(line: 17, column: 20, scope: !51)
+!56 = !{!47, !32, i64 0}
+!57 = !DILocation(line: 17, column: 11, scope: !51)
+!58 = !DILocation(line: 17, column: 9, scope: !51)
+!59 = !{!48, !48, i64 0}
+!60 = !DILocation(line: 18, column: 9, scope: !61)
+!61 = distinct !DILexicalBlock(scope: !51, file: !1, line: 18, column: 9)
+!62 = !DILocation(line: 18, column: 9, scope: !51)
+!63 = !DILocation(line: 19, column: 7, scope: !61)
+!64 = !DILocation(line: 20, column: 3, scope: !51)
+!65 = !DILocation(line: 21, column: 3, scope: !14)
+!66 = !DILocation(line: 22, column: 1, scope: !14)
+!67 = !DILocation(line: 24, column: 24, scope: !21)
+!68 = !DILocation(line: 25, column: 3, scope: !21)
+!69 = !DILocation(line: 25, column: 7, scope: !21)
+!70 = !DILocation(line: 26, column: 3, scope: !21)
+!71 = !DILocation(line: 26, column: 13, scope: !21)
+!72 = !DILocation(line: 26, column: 31, scope: !21)
+!73 = !DILocation(line: 26, column: 19, scope: !21)
+!74 = !DILocation(line: 28, column: 8, scope: !75)
+!75 = distinct !DILexicalBlock(scope: !21, file: !1, line: 28, column: 7)
+!76 = !DILocation(line: 28, column: 12, scope: !75)
+!77 = !{!47, !48, i64 8}
+!78 = !DILocation(line: 28, column: 7, scope: !21)
+!79 = !DILocation(line: 29, column: 5, scope: !80)
+!80 = distinct !DILexicalBlock(scope: !75, file: !1, line: 28, column: 17)
+!81 = !DILocation(line: 29, column: 9, scope: !80)
+!82 = !DILocation(line: 29, column: 13, scope: !80)
+!83 = !DILocation(line: 31, column: 16, scope: !80)
+!84 = !DILocation(line: 31, column: 20, scope: !80)
+!85 = !DILocation(line: 31, column: 11, scope: !80)
+!86 = !DILocation(line: 31, column: 9, scope: !80)
+!87 = !DILocation(line: 32, column: 9, scope: !88)
+!88 = distinct !DILexicalBlock(scope: !80, file: !1, line: 32, column: 9)
+!89 = !DILocation(line: 32, column: 9, scope: !80)
+!90 = !DILocation(line: 33, column: 7, scope: !88)
+!91 = !DILocation(line: 34, column: 3, scope: !80)
+!92 = !DILocation(line: 35, column: 3, scope: !21)
+!93 = !DILocation(line: 36, column: 1, scope: !21)

llvm/test/Transforms/MergeSimilarFunc/merge-equivalent-template.ll

+; RUN: opt -S -mergefunc -mergesimilarfunc %s -o - | FileCheck %s
+
+; CHECK:      define linkonce_odr void @_ZN11FooTemplateIPvE7method1EP9FooStruct(%class.FooTemplate.0* nocapture readnone %this, %struct.FooStruct* %arg0) #1 align 2 {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %field27 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0, i32 0, i32 2
+; CHECK-NEXT:   %0 = load i8, i8* %field27, align 1
+; CHECK-NEXT:   %lnot8 = icmp eq i8 %0, 0
+; CHECK-NEXT:   br i1 %lnot8, label %for.body, label %for.end
+
+; CHECK:      for.body:                                         ; preds = %for.body, %entry
+; CHECK-NEXT:   %arg0.addr.09 = phi %struct.FooStruct* [ %2, %for.body ], [ %arg0, %entry ]
+; CHECK-NEXT:   %field1 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0.addr.09, i32 0, i32 1
+; CHECK-NEXT:   %1 = load %struct.FooStruct*, %struct.FooStruct** %field1, align 4
+; CHECK-NEXT:   tail call void @_ZN11FooTemplateIPvE7method1EP9FooStruct(%class.FooTemplate.0* %this, %struct.FooStruct* %1) #2
+; CHECK-NEXT:   %field0 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0.addr.09, i32 0, i32 0
+; CHECK-NEXT:   %2 = load %struct.FooStruct*, %struct.FooStruct** %field0, align 4
+; CHECK-NEXT:   %3 = bitcast %struct.FooStruct* %arg0.addr.09 to i8*
+; CHECK-NEXT:   tail call void @_Z4bar0Pv(i8* %3) #3
+; CHECK-NEXT:   tail call void @_Z4bar1Pv(i8* %3) #3
+; CHECK-NEXT:   %field2 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %2, i32 0, i32 2
+; CHECK-NEXT:   %4 = load i8, i8* %field2, align 1
+; CHECK-NEXT:   %lnot = icmp eq i8 %4, 0
+; CHECK-NEXT:   br i1 %lnot, label %for.body, label %for.end
+
+; CHECK:      for.end:                                          ; preds = %for.body, %entry
+; CHECK-NEXT:   ret void
+; CHECK-NEXT: }
+
+; CHECK:      define linkonce_odr void @_ZN11FooTemplateIiE7method1EP9FooStruct(%class.FooTemplate* nocapture readnone %0, %struct.FooStruct* %1) #1 align 2 {
+; CHECK-NEXT:   %3 = bitcast %class.FooTemplate* %0 to %class.FooTemplate.0*
+; CHECK-NEXT:   tail call void @_ZN11FooTemplateIPvE7method1EP9FooStruct(%class.FooTemplate.0* nocapture readnone %3, %struct.FooStruct* %1)
+; CHECK-NEXT:   ret void
+; CHECK-NEXT: }
+
+; CHECK:      attributes #0 = { optsize "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+; CHECK-NEXT: attributes #1 = { nounwind optsize ssp "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+; CHECK-NEXT: attributes #2 = { optsize }
+; CHECK-NEXT: attributes #3 = { nounwind optsize }
+
+target datalayout = "e-m:e-p:32:32-i1:32-i64:64-a:0-v32:32-n16:32"
+
+%class.Foo = type { %class.FooTemplate, %class.FooTemplate.0 }
+%class.FooTemplate = type { i8 }
+%class.FooTemplate.0 = type { i8 }
+%struct.FooStruct = type { %struct.FooStruct*, %struct.FooStruct*, i8 }
+
+@_ZN3FooD1Ev = alias void(%class.Foo*), void (%class.Foo*)* @_ZN3FooD2Ev
+
+declare %struct.FooStruct* @_ZNK11FooTemplateIPvE7method2Ev(%class.FooTemplate.0*) #1
+declare void @_Z4bar0Pv(i8*) #1
+declare void @_Z4bar1Pv(i8*) #1
+declare %struct.FooStruct* @_ZNK11FooTemplateIiE7method2Ev(%class.FooTemplate*) #1
+
+; Function Attrs: nounwind optsize ssp
+define void @_ZN3FooD2Ev(%class.Foo* %this) unnamed_addr #0 align 2 {
+entry:
+  %bar_things = getelementptr inbounds %class.Foo, %class.Foo* %this, i32 0, i32 0
+  tail call void @_ZN11FooTemplateIiE7method0Ev(%class.FooTemplate* %bar_things) #2
+  %baz_things = getelementptr inbounds %class.Foo, %class.Foo* %this, i32 0, i32 1
+  tail call void @_ZN11FooTemplateIPvE7method0Ev(%class.FooTemplate.0* %baz_things) #2
+  ret void
+}
+
+; Function Attrs: nounwind optsize ssp
+define linkonce_odr void @_ZN11FooTemplateIiE7method0Ev(%class.FooTemplate* %this) #0 align 2 {
+entry:
+  %call = tail call %struct.FooStruct* @_ZNK11FooTemplateIiE7method2Ev(%class.FooTemplate* %this) #3
+  tail call void @_ZN11FooTemplateIiE7method1EP9FooStruct(%class.FooTemplate* %this, %struct.FooStruct* %call) #2
+  ret void
+}
+
+; Function Attrs: nounwind optsize ssp
+define linkonce_odr void @_ZN11FooTemplateIPvE7method0Ev(%class.FooTemplate.0* %this) #0 align 2 {
+entry:
+  %call = tail call %struct.FooStruct* @_ZNK11FooTemplateIPvE7method2Ev(%class.FooTemplate.0* %this) #3
+  tail call void @_ZN11FooTemplateIPvE7method1EP9FooStruct(%class.FooTemplate.0* %this, %struct.FooStruct* %call) #2
+  ret void
+}
+
+; Function Attrs: nounwind optsize ssp
+define linkonce_odr void @_ZN11FooTemplateIPvE7method1EP9FooStruct(%class.FooTemplate.0* nocapture readnone %this, %struct.FooStruct* %arg0) #0 align 2 {
+entry:
+  %field27 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0, i32 0, i32 2
+  %0 = load i8, i8* %field27, align 1
+  %lnot8 = icmp eq i8 %0, 0
+  br i1 %lnot8, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.body
+  %arg0.addr.09 = phi %struct.FooStruct* [ %2, %for.body ], [ %arg0, %entry ]
+  %field1 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0.addr.09, i32 0, i32 1
+  %1 = load %struct.FooStruct*, %struct.FooStruct** %field1, align 4
+  tail call void @_ZN11FooTemplateIPvE7method1EP9FooStruct(%class.FooTemplate.0* %this, %struct.FooStruct* %1) #2
+  %field0 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0.addr.09, i32 0, i32 0
+  %2 = load %struct.FooStruct*, %struct.FooStruct** %field0, align 4
+  %3 = bitcast %struct.FooStruct* %arg0.addr.09 to i8*
+  tail call void @_Z4bar0Pv(i8* %3) #3
+  tail call void @_Z4bar1Pv(i8* %3) #3
+  %field2 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %2, i32 0, i32 2
+  %4 = load i8, i8* %field2, align 1
+  %lnot = icmp eq i8 %4, 0
+  br i1 %lnot, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+; Function Attrs: nounwind optsize ssp
+define linkonce_odr void @_ZN11FooTemplateIiE7method1EP9FooStruct(%class.FooTemplate* nocapture readnone %this, %struct.FooStruct* %arg0) #0 align 2 {
+entry:
+  %field27 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0, i32 0, i32 2
+  %0 = load i8, i8* %field27, align 1
+  %lnot8 = icmp eq i8 %0, 0
+  br i1 %lnot8, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.body
+  %arg0.addr.09 = phi %struct.FooStruct* [ %2, %for.body ], [ %arg0, %entry ]
+  %field1 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0.addr.09, i32 0, i32 1
+  %1 = load %struct.FooStruct*, %struct.FooStruct** %field1, align 4
+  tail call void @_ZN11FooTemplateIiE7method1EP9FooStruct(%class.FooTemplate* %this, %struct.FooStruct* %1) #2
+  %field0 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %arg0.addr.09, i32 0, i32 0
+  %2 = load %struct.FooStruct*, %struct.FooStruct** %field0, align 4
+  %3 = bitcast %struct.FooStruct* %arg0.addr.09 to i8*
+  tail call void @_Z4bar0Pv(i8* %3) #3
+  tail call void @_Z4bar1Pv(i8* %3) #3
+  %field2 = getelementptr inbounds %struct.FooStruct, %struct.FooStruct* %2, i32 0, i32 2
+  %4 = load i8, i8* %field2, align 1
+  %lnot = icmp eq i8 %4, 0
+  br i1 %lnot, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}
+
+attributes #0 = { nounwind optsize ssp "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { optsize "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { optsize }
+attributes #3 = { nounwind optsize }

llvm/test/Transforms/MergeSimilarFunc/merge-equivalent.ll

+; RUN: opt -mergefunc -mergesimilarfunc -S %s -o - | FileCheck %s
+;
+; CHECK:      define i8* @foo_a(%struct.a_type* %arg0) #1 {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   br label %for.cond
+
+; CHECK:      for.cond:                                         ; preds = %for.inc24, %entry
+; CHECK-NEXT:   %i.0 = phi i8 [ 0, %entry ], [ %inc25, %for.inc24 ]
+; CHECK-NEXT:   %ptr0.0 = phi i8* [ null, %entry ], [ %ptr0.3, %for.inc24 ]
+; CHECK-NEXT:   %conv = zext i8 %i.0 to i32
+; CHECK-NEXT:   %cmp = icmp slt i32 %conv, 16
+; CHECK-NEXT:   br i1 %cmp, label %for.body, label %for.end26
+
+; CHECK:      for.body:                                         ; preds = %for.cond
+; CHECK-NEXT:   %call = call i8* @bar4(i32 %conv) #2
+; CHECK-NEXT:   %call4 = call i8* @bar0(i32 %conv) #2
+; CHECK-NEXT:   %0 = bitcast i8* %call4 to %struct.a_type*
+; CHECK-NEXT:   %call5 = call i32 @bar1(i8* %call) #2
+; CHECK-NEXT:   %tobool = icmp ne i32 %call5, 0
+; CHECK-NEXT:   br i1 %tobool, label %for.cond6, label %for.inc24
+
+; CHECK:      for.cond6:                                        ; preds = %for.inc, %for.body
+; CHECK-NEXT:   %k.0 = phi i8 [ %inc, %for.inc ], [ 0, %for.body ]
+; CHECK-NEXT:   %ptr0.1 = phi i8* [ %ptr0.2, %for.inc ], [ %call, %for.body ]
+; CHECK-NEXT:   %idxprom = zext i8 %k.0 to i32
+; CHECK-NEXT:   %field4 = getelementptr inbounds %struct.a_type, %struct.a_type* %arg0, i32 0, i32 4
+; CHECK-NEXT:   %arrayidx = getelementptr inbounds [2 x i8*], [2 x i8*]* %field4, i32 0, i32 %idxprom
+; CHECK-NEXT:   %1 = load i8*, i8** %arrayidx, align 4
+; CHECK-NEXT:   %cmp7 = icmp ne i8* %1, null
+; CHECK-NEXT:   br i1 %cmp7, label %land.rhs, label %for.inc24
+
+; CHECK:      land.rhs:                                         ; preds = %for.cond6
+; CHECK-NEXT:   %field410 = getelementptr inbounds %struct.a_type, %struct.a_type* %0, i32 0, i32 4
+; CHECK-NEXT:   %arrayidx11 = getelementptr inbounds [2 x i8*], [2 x i8*]* %field410, i32 0, i32 %idxprom
+; CHECK-NEXT:   %2 = load i8*, i8** %arrayidx11, align 4
+; CHECK-NEXT:   %cmp12 = icmp ne i8* %2, null
+; CHECK-NEXT:   br i1 %cmp12, label %for.body14, label %for.inc24
+
+; CHECK:      for.body14:                                       ; preds = %land.rhs
+; CHECK-NEXT:   %3 = bitcast %struct.a_type* %0 to i8*
+; CHECK-NEXT:   %4 = bitcast %struct.a_type* %arg0 to i8*
+; CHECK-NEXT:   %call15 = call i32 @bar2(i8* %3, i8* %4) #2
+; CHECK-NEXT:   %tobool16 = icmp ne i32 %call15, 0
+; CHECK-NEXT:   br i1 %tobool16, label %if.then17, label %for.inc
+
+; CHECK:      if.then17:                                        ; preds = %for.body14
+; CHECK-NEXT:   %call18 = call i32 @bar3(i8* %3, i8* %4) #2
+; CHECK-NEXT:   %tobool19 = icmp ne i32 %call18, 0
+; CHECK-NEXT:   br i1 %tobool19, label %if.then20, label %for.inc
+
+; CHECK:      if.then20:                                        ; preds = %if.then17
+; CHECK-NEXT:   br label %for.inc
+
+; CHECK:      for.inc:                                          ; preds = %if.then20, %if.then17, %for.body14
+; CHECK-NEXT:   %ptr0.2 = phi i8* [ null, %if.then20 ], [ %ptr0.1, %if.then17 ], [ null, %for.body14 ]
+; CHECK-NEXT:   %inc = add i8 %k.0, 1
+; CHECK-NEXT:   br label %for.cond6
+
+; CHECK:      for.inc24:                                        ; preds = %land.rhs, %for.cond6, %for.body
+; CHECK-NEXT:   %ptr0.3 = phi i8* [ %ptr0.1, %land.rhs ], [ %ptr0.1, %for.cond6 ], [ null, %for.body ]
+; CHECK-NEXT:   %inc25 = add i8 %i.0, 1
+; CHECK-NEXT:   br label %for.cond
+
+; CHECK:      for.end26:                                        ; preds = %for.cond
+; CHECK-NEXT:   ret i8* %ptr0.0
+; CHECK-NEXT: }
+
+; CHECK:      ; Function Attrs: nounwind optsize ssp
+; CHECK-NEXT: define i8* @foo_b(%struct.b_type* %0) #1 {
+; CHECK-NEXT:   %2 = bitcast %struct.b_type* %0 to %struct.a_type*
+; CHECK-NEXT:   %3 = tail call i8* @foo_a(%struct.a_type* %2)
+; CHECK-NEXT:   ret i8* %3
+; CHECK-NEXT: }
+
+; CHECK:      attributes #0 = { optsize "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+; CHECK-NEXT: attributes #1 = { nounwind optsize ssp "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+; CHECK-NEXT: attributes #2 = { optsize }
+
+target datalayout = "e-m:e-p:32:32-i1:32-i64:64-a:0-v32:32-n16:32"
+
+%struct.a_type = type { i32, i32, i32, i8*, [2 x i8*] }
+%struct.b_type = type { i32, i32, i32, i8*, [2 x i8*], i32 }
+
+; Function Attrs: optsize
+declare i8* @bar4(i32) #1
+declare i8* @bar0(i32) #1
+declare i32 @bar1(i8*) #1
+declare i32 @bar2(i8*, i8*) #1
+declare i32 @bar3(i8*, i8*) #1
+
+; Function Attrs: nounwind optsize ssp
+define i8* @foo_a(%struct.a_type* %arg0) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc24, %entry
+  %i.0 = phi i8 [ 0, %entry ], [ %inc25, %for.inc24 ]
+  %ptr0.0 = phi i8* [ null, %entry ], [ %ptr0.3, %for.inc24 ]
+  %conv = zext i8 %i.0 to i32
+  %cmp = icmp slt i32 %conv, 16
+  br i1 %cmp, label %for.body, label %for.end26
+
+for.body:                                         ; preds = %for.cond
+  %call = call i8* @bar4(i32 %conv) #2
+  %call4 = call i8* @bar0(i32 %conv) #2
+  %0 = bitcast i8* %call4 to %struct.a_type*
+  %call5 = call i32 @bar1(i8* %call) #2
+  %tobool = icmp ne i32 %call5, 0
+  br i1 %tobool, label %for.cond6, label %for.inc24
+
+for.cond6:                                        ; preds = %for.body, %for.inc
+  %k.0 = phi i8 [ %inc, %for.inc ], [ 0, %for.body ]
+  %ptr0.1 = phi i8* [ %ptr0.2, %for.inc ], [ %call, %for.body ]
+  %idxprom = zext i8 %k.0 to i32
+  %field4 = getelementptr inbounds %struct.a_type, %struct.a_type* %arg0, i32 0, i32 4
+  %arrayidx = getelementptr inbounds [2 x i8*], [2 x i8*]* %field4, i32 0, i32 %idxprom
+  %1 = load i8*, i8** %arrayidx, align 4
+  %cmp7 = icmp ne i8* %1, null
+  br i1 %cmp7, label %land.rhs, label %for.inc24
+
+land.rhs:                                         ; preds = %for.cond6
+  %field410 = getelementptr inbounds %struct.a_type, %struct.a_type* %0, i32 0, i32 4
+  %arrayidx11 = getelementptr inbounds [2 x i8*], [2 x i8*]* %field410, i32 0, i32 %idxprom
+  %2 = load i8*, i8** %arrayidx11, align 4
+  %cmp12 = icmp ne i8* %2, null
+  br i1 %cmp12, label %for.body14, label %for.inc24
+
+for.body14:                                       ; preds = %land.rhs
+  %3 = bitcast %struct.a_type* %0 to i8*
+  %4 = bitcast %struct.a_type* %arg0 to i8*
+  %call15 = call i32 @bar2(i8* %3, i8* %4) #2
+  %tobool16 = icmp ne i32 %call15, 0
+  br i1 %tobool16, label %if.then17, label %for.inc
+
+if.then17:                                        ; preds = %for.body14
+  %call18 = call i32 @bar3(i8* %3, i8* %4) #2
+  %tobool19 = icmp ne i32 %call18, 0
+  br i1 %tobool19, label %if.then20, label %for.inc
+
+if.then20:                                        ; preds = %if.then17
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body14, %if.then17, %if.then20
+  %ptr0.2 = phi i8* [ null, %if.then20 ], [ %ptr0.1, %if.then17 ], [ null, %for.body14 ]
+  %inc = add i8 %k.0, 1
+  br label %for.cond6
+
+for.inc24:                                        ; preds = %for.body, %for.cond6, %land.rhs
+  %ptr0.3 = phi i8* [ %ptr0.1, %land.rhs ], [ %ptr0.1, %for.cond6 ], [ null, %for.body ]
+  %inc25 = add i8 %i.0, 1
+  br label %for.cond
+
+for.end26:                                        ; preds = %for.cond
+  ret i8* %ptr0.0
+}
+
+; Function Attrs: nounwind optsize ssp
+define i8* @foo_b(%struct.b_type* %arg0) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc24, %entry
+  %i.0 = phi i8 [ 0, %entry ], [ %inc25, %for.inc24 ]
+  %ptr0.0 = phi i8* [ null, %entry ], [ %ptr0.3, %for.inc24 ]
+  %conv = zext i8 %i.0 to i32
+  %cmp = icmp slt i32 %conv, 16
+  br i1 %cmp, label %for.body, label %for.end26
+
+for.body:                                         ; preds = %for.cond
+  %call = call i8* @bar4(i32 %conv) #2
+  %call4 = call i8* @bar0(i32 %conv) #2
+  %0 = bitcast i8* %call4 to %struct.b_type*
+  %call5 = call i32 @bar1(i8* %call) #2
+  %tobool = icmp ne i32 %call5, 0
+  br i1 %tobool, label %for.cond6, label %for.inc24
+
+for.cond6:                                        ; preds = %for.body, %for.inc
+  %k.0 = phi i8 [ %inc, %for.inc ], [ 0, %for.body ]
+  %ptr0.1 = phi i8* [ %ptr0.2, %for.inc ], [ %call, %for.body ]
+  %idxprom = zext i8 %k.0 to i32
+  %field4 = getelementptr inbounds %struct.b_type, %struct.b_type* %arg0, i32 0, i32 4
+  %arrayidx = getelementptr inbounds [2 x i8*], [2 x i8*]* %field4, i32 0, i32 %idxprom
+  %1 = load i8*, i8** %arrayidx, align 4
+  %cmp7 = icmp ne i8* %1, null
+  br i1 %cmp7, label %land.rhs, label %for.inc24
+
+land.rhs:                                         ; preds = %for.cond6
+  %field410 = getelementptr inbounds %struct.b_type, %struct.b_type* %0, i32 0, i32 4
+  %arrayidx11 = getelementptr inbounds [2 x i8*], [2 x i8*]* %field410, i32 0, i32 %idxprom
+  %2 = load i8*, i8** %arrayidx11, align 4
+  %cmp12 = icmp ne i8* %2, null
+  br i1 %cmp12, label %for.body14, label %for.inc24
+
+for.body14:                                       ; preds = %land.rhs
+  %3 = bitcast %struct.b_type* %0 to i8*
+  %4 = bitcast %struct.b_type* %arg0 to i8*
+  %call15 = call i32 @bar2(i8* %3, i8* %4) #2
+  %tobool16 = icmp ne i32 %call15, 0
+  br i1 %tobool16, label %if.then17, label %for.inc
+
+if.then17:                                        ; preds = %for.body14
+  %call18 = call i32 @bar3(i8* %3, i8* %4) #2
+  %tobool19 = icmp ne i32 %call18, 0
+  br i1 %tobool19, label %if.then20, label %for.inc
+
+if.then20:                                        ; preds = %if.then17
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body14, %if.then17, %if.then20
+  %ptr0.2 = phi i8* [ null, %if.then20 ], [ %ptr0.1, %if.then17 ], [ null, %for.body14 ]
+  %inc = add i8 %k.0, 1
+  br label %for.cond6
+
+for.inc24:                                        ; preds = %for.body, %for.cond6, %land.rhs
+  %ptr0.3 = phi i8* [ %ptr0.1, %land.rhs ], [ %ptr0.1, %for.cond6 ], [ null, %for.body ]
+  %inc25 = add i8 %i.0, 1
+  br label %for.cond
+
+for.end26:                                        ; preds = %for.cond
+  ret i8* %ptr0.0
+}
+
+attributes #0 = { nounwind optsize ssp "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { optsize "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { optsize }

llvm/test/Transforms/MergeSimilarFunc/merge-noinline.ll

+; RUN: opt -S -mergefunc -mergesimilarfunc -mergesimilarfunc-level=all < %s | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+declare void @stuff()
+
+; CHECK-LABEL: @f0(
+define void @f0(i64 %p0) {
+entry:
+  call void @stuff()
+  call void @stuff()
+  call void @stuff()
+  ret void
+}
+
+; CHECK-LABEL: @f1(
+; CHECK: call void @f0{{.*}} #[[ATTR:[0-9]+]]
+; CHECK: attributes #[[ATTR]] = { {{.*}}noinline
+define void @f1(i64 %p0) {
+entry:
+  call void @stuff()
+  call void @stuff()
+  call void @stuff()
+  ret void
+}

llvm/test/Transforms/MergeSimilarFunc/merge-ret.ll

+; Check that the ret instructions are merged correctly. A bug caused
+; an incorrect merge and a verifier failure for this input.
+;
+; RUN: opt -S -mergefunc -mergesimilarfunc < %s | FileCheck %s
+;
+; CHECK-LABEL: define internal %0* @LLVMGetReturnType__merged
+; CHECK: phi %0* [
+; CHECK-NEXT: ret %0*
+; CHECK-NEXT: }
+;
+
+target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
+
+%0 = type opaque
+%1 = type { %2*, i32, i32, %1** }
+%2 = type { %3* }
+%3 = type opaque
+%4 = type { %1 }
+%5 = type opaque
+%6 = type { i32 (...)**, %1*, %7*, i8, i8, i16, i32 }
+%7 = type { %6*, %7*, %8 }
+%8 = type { i32 }
+%9 = type { %10, %1*, i32, %12, i32, i8, %18* }
+%10 = type { %11 }
+%11 = type { %6 }
+%12 = type { %13 }
+%13 = type { %14 }
+%14 = type { %15 }
+%15 = type { %16 }
+%16 = type { %17 }
+%17 = type { i32, i32, i8* }
+%18 = type <{ %2*, %19, %30, %70, %79, %87, %12, %93*, %94, %98, %12, %12, %12, i8*, %102, i8, [3 x i8] }>
+%19 = type { %20 }
+%20 = type { %21, %26* }
+%21 = type { %22 }
+%22 = type { %23 }
+%23 = type { %24 }
+%24 = type { %25, %26* }
+%25 = type { %26* }
+%26 = type <{ %27, [3 x i8], %24, i8, [3 x i8] }>
+%27 = type <{ %9, %12, %28*, %12, %12, i8 }>
+%28 = type <{ %29*, i8, [3 x i8] }>
+%29 = type opaque
+%30 = type { %31 }
+%31 = type { %32, %37* }
+%32 = type { %33 }
+%33 = type { %34 }
+%34 = type { %35 }
+%35 = type { %36, %37* }
+%36 = type { %37* }
+%37 = type { %27, %35, %38, %60, %93*, %68, %4* }
+%38 = type { %39 }
+%39 = type { %40, %44* }
+%40 = type { %41 }
+%41 = type { %42 }
+%42 = type { %43 }
+%43 = type { %44* }
+%44 = type { %6, %45, i32, %47, %37* }
+%45 = type { %46 }
+%46 = type { %43, %44* }
+%47 = type { %48 }
+%48 = type { %49, %53* }
+%49 = type { %50 }
+%50 = type { %51 }
+%51 = type { %52 }
+%52 = type { %53* }
+%53 = type { %11, %54, %44*, %56 }
+%54 = type { %55 }
+%55 = type { %52, %53* }
+%56 = type { %57 }
+%57 = type { %58 }
+%58 = type { %59* }
+%59 = type { i8, i8, i16, i32 }
+%60 = type { %61 }
+%61 = type { %62, %66* }
+%62 = type { %63 }
+%63 = type { %64 }
+%64 = type { %65 }
+%65 = type { %66* }
+%66 = type { %6, %67, %37* }
+%67 = type { %65, %66* }
+%68 = type { %69* }
+%69 = type opaque
+%70 = type { %71 }
+%71 = type { %72, %77* }
+%72 = type { %73 }
+%73 = type { %74 }
+%74 = type { %75 }
+%75 = type { %76, %77* }
+%76 = type { %77* }
+%77 = type { %78, %75 }
+%78 = type { %9 }
+%79 = type { %80 }
+%80 = type { %81, %86* }
+%81 = type { %82 }
+%82 = type { %83 }
+%83 = type { %84 }
+%84 = type { %85, %86* }
+%85 = type { %86* }
+%86 = type { %78, %84 }
+%87 = type { %88 }
+%88 = type { %89, %92* }
+%89 = type { %90 }
+%90 = type { %91, %92* }
+%91 = type { %92* }
+%92 = type { %90, %12, %18*, i8* }
+%93 = type opaque
+%94 = type <{ %95, %97, [3 x i8] }>
+%95 = type { %96**, i32, i32, i32, i32 }
+%96 = type { i32 }
+%97 = type { i8 }
+%98 = type { %99 }
+%99 = type { %100 }
+%100 = type { %101* }
+%101 = type opaque
+%102 = type { i8, i32, i8, [3 x i8], %103, %111, %12, %118, i8* }
+%103 = type { %104, %110 }
+%104 = type { %105 }
+%105 = type { %106 }
+%106 = type <{ %107, %108 }>
+%107 = type { i8*, i8*, i8* }
+%108 = type { %109 }
+%109 = type { [1 x i8] }
+%110 = type { [7 x %108] }
+%111 = type { %112, %117 }
+%112 = type { %113 }
+%113 = type { %114 }
+%114 = type { %107, %115 }
+%115 = type { %116 }
+%116 = type { [8 x i8] }
+%117 = type { [15 x %115] }
+%118 = type { %119, %124 }
+%119 = type { %120 }
+%120 = type { %121 }
+%121 = type { %107, %122 }
+%122 = type { %123 }
+%123 = type { [16 x i8] }
+%124 = type { [7 x %122] }
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture) #0
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture) #0
+
+; Function Attrs: optsize
+define %0* @LLVMGetReturnType(%0*) #1 {
+  %2 = alloca %1*, align 4
+  %3 = bitcast %1** %2 to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3)
+  %4 = bitcast %1** %2 to %0**
+  store %0* %0, %0** %4, align 4
+  %5 = call zeroext i1 @_ZN4llvm13isa_impl_wrapINS_12FunctionTypeEKPNS_4TypeEPKS2_E4doitERS4_(%1** nonnull dereferenceable(4) %2) #3
+  %6 = bitcast %0* %0 to %4*
+  br i1 %5, label %8, label %7
+
+; <label>:7:                                      ; preds = %1
+  tail call void @__assert_fail.5.0.1.2_i32_237.3() #4
+  br label %8
+
+; <label>:8:                                      ; preds = %7, %1
+  call void @llvm.lifetime.end(i64 4, i8* %3)
+  %9 = getelementptr inbounds %4, %4* %6, i32 0, i32 0, i32 3
+  %10 = bitcast %1*** %9 to %0***
+  %11 = load %0**, %0*** %10, align 4
+  %12 = load %0*, %0** %11, align 4
+  ret %0* %12
+}
+
+; Function Attrs: optsize
+declare void @__assert_fail.5.0.1.2_i32_237.3() #2
+
+; Function Attrs: optsize
+define i32 @LLVMHasUnnamedAddr(%5*) #1 {
+  %2 = alloca %6*, align 4
+  %3 = bitcast %6** %2 to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3)
+  %4 = bitcast %6** %2 to %5**
+  store %5* %0, %5** %4, align 4
+  %5 = call zeroext i1 @_ZN4llvm13isa_impl_wrapINS_11GlobalValueEKPNS_5ValueEPKS2_E4doitERS4_(%6** nonnull dereferenceable(4) %2) #3
+  %6 = bitcast %5* %0 to %9*
+  br i1 %5, label %8, label %7
+
+; <label>:7:                                      ; preds = %1
+  tail call void @__assert_fail.5.0.1.2_i32_237.3() #4
+  br label %8
+
+; <label>:8:                                      ; preds = %7, %1
+  call void @llvm.lifetime.end(i64 4, i8* %3)
+  %9 = getelementptr inbounds %9, %9* %6, i32 0, i32 2
+  %10 = load i32, i32* %9, align 4
+  %11 = lshr i32 %10, 6
+  %12 = and i32 %11, 1
+  ret i32 %12
+}
+
+; Function Attrs: optsize
+declare zeroext i1 @_ZN4llvm13isa_impl_wrapINS_12FunctionTypeEKPNS_4TypeEPKS2_E4doitERS4_(%1** nocapture readonly dereferenceable(4)) #1 align 2
+
+; Function Attrs: optsize
+declare zeroext i1 @_ZN4llvm13isa_impl_wrapINS_11GlobalValueEKPNS_5ValueEPKS2_E4doitERS4_(%6** nocapture readonly dereferenceable(4)) #1 align 2
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { optsize }
+attributes #2 = { optsize }
+attributes #3 = { optsize }
+attributes #4 = { noinline optsize }

llvm/test/Transforms/MergeSimilarFunc/merge-ret2.ll

+; Check that two ret instructions with the same return type
+; are generated in the merged function. A bug caused a mismatch
+; in return types here and a verifier failure.
+;
+; RUN: opt -S -mergefunc -mergesimilarfunc < %s | FileCheck %s
+;
+; CHECK: @mrg1__merged
+; CHECK: switch i32 %__merge_arg
+; CHECK: ret %0*
+; CHECK: ret %0*
+
+target datalayout = "e-m:e-p:32:32:32-a:0-n16:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f32:32:32-f64:64:64-v32:32:32-v64:64:64-v512:512:512-v1024:1024:1024-v2048:2048:2048"
+
+%0 = type { {}*, %0* (%8*)*, %0* (%13*)*, %0* (%39*)*, %0* (%14*)*, %0* (%14*)*, %0* (%15*)*, %0* (%16*)*, %0* ()*, %0* (%17*)*, %0* (%22*)*, %0* (%28*)*, %0* (%32*)*, %0* (%37*)*, %0* (%37*)*, %0* (%37*)*, %0* ()*, %0* (%33*)*, %0* (%36*)*, %0* (%37*)*, %0* (%38*)*, %0* ()*, %0* (%39*)*, %0* ()*, %0* ()*, %0* (%40*)*, %0* ()*, %0* ()*, %0* ()*, %0* ()*, i8 ()*, void ()* }
+%1 = type { %2, i32, i8, i8, i64, i8, i8, i8, %3, %3, i8, i8 }
+%2 = type { i8, i8, i8, i8 }
+%3 = type { i32, i32, [10 x %4], %7 }
+%4 = type { %5, i8, i32, i8, %5 }
+%5 = type { %6 }
+%6 = type { i64, i64, i64, i64 }
+%7 = type { i8, i8 }
+%8 = type { %2, i32, i8, i8, i8, i8, i8, i64, %9, %3, i8, i8, i8, %12, i32, i8 }
+%9 = type { %10 }
+%10 = type { i8, i8, %11, i32, i8 }
+%11 = type { [3 x i8] }
+%12 = type { i8, i8, i8 }
+%13 = type { %2, i32, i8, i32, i8, i8, i8 }
+%14 = type { %2, i32, i8, i8, i8 }
+%15 = type { %2, i8, i8, i8 }
+%16 = type { %2, i8, %5, i8, %11, i16, i8 }
+%17 = type { %2, %18, i8 }
+%18 = type { i8, i8, i8, i8, i8, i8, i8, i8, %11, %19, %19, %20, i32, %21, i8, i16, i8 }
+%19 = type { i8, i8, i8, [255 x i8], i8 }
+%20 = type { i8, i8, i8, i8, i8, i8, i32 }
+%21 = type { i8, [3 x i8] }
+%22 = type { %2, i8, i8, %23, i8, i8, i8 }
+%23 = type { %24 }
+%24 = type { i32, [40 x %25] }
+%25 = type { %11, i8, i8, i8, i8, i8, i32, %26, i32 }
+%26 = type { i32, %27, i8 }
+%27 = type { i8, [48 x i8] }
+%28 = type { %2, i8, %29, i8, %24, i8, %31, i8, i8, i8, i8, i16, i8 }
+%29 = type { i8, %11, i8, i8, i16, i8, i8, i8, %5, i16, i16, i8, %26, i8, i8, i8, i32, i8, i8, i8, i8, %30, i8, i8, %11, i8 }
+%30 = type { i8, i8, i8, i8, i8 }
+%31 = type { i32, [40 x %11] }
+%32 = type { %2, i8, %29, i8, i8, %31, i8, i16, i8 }
+%33 = type { %2, %34, i8 }
+%34 = type { i8, [16 x %35] }
+%35 = type { i8, i8, [41 x i8] }
+%36 = type { %2, i32, i8 }
+%37 = type { %2, i8 }
+%38 = type { %2, i8, i8, %11, i16, i8, i32, i8 }
+%39 = type { %2, i32, i8, i8 }
+%40 = type { %2, i8, %11, i32, i8, i8, i8 }
+%41 = type { {}*, %41* (%8*)*, %41* (%13*)*, %41* (%39*)*, %41* (%14*)*, %41* (%14*)*, %41* (%15*)*, %41* (%16*)*, %41* ()*, %41* (%17*)*, %41* (%22*)*, %41* (%28*)*, %41* (%32*)*, %41* (%37*)*, %41* (%37*)*, %41* (%37*)*, %41* ()*, %41* (%33*)*, %41* (%36*)*, %41* (%37*)*, %41* (%38*)*, %41* ()*, %41* (%39*)*, %41* ()*, %41* ()*, %41* (%40*)*, %41* ()*, %41* ()*, %41* ()*, %41* ()*, i8 ()*, void ()* }
+
+@xx = external global i8, align 1
+@yy = external global { %0* (%1*)*, %0* (%8*)*, %0* (%13*)*, %0* (%39*)*, %0* (%14*)*, %0* (%14*)*, %0* (%15*)*, %0* (%16*)*, %0* ()*, %0* (%17*)*, %0* (%22*)*, %0* (%28*)*, %0* (%32*)*, %0* (%37*)*, %0* (%37*)*, %0* (%37*)*, %0* ()*, %0* (%33*)*, %0* (%36*)*, %0* (%37*)*, %0* (%38*)*, %0* ()*, %0* (%39*)*, %0* ()*, %0* ()*, %0* (%40*)*, %0* ()*, %0* ()*, %0* ()*, %0* ()*, i8 ()*, void ()* }, align 4
+@zz = external global { %41* (%1*)*, %41* (%8*)*, %41* (%13*)*, %41* (%39*)*, %41* (%14*)*, %41* (%14*)*, %41* (%15*)*, %41* (%16*)*, %41* ()*, %41* (%17*)*, %41* (%22*)*, %41* (%28*)*, %41* (%32*)*, %41* (%37*)*, %41* (%37*)*, %41* (%37*)*, %41* ()*, %41* (%33*)*, %41* (%36*)*, %41* (%37*)*, %41* (%38*)*, %41* ()*, %41* (%39*)*, %41* ()*, %41* ()*, %41* (%40*)*, %41* ()*, %41* ()*, %41* ()*, %41* ()*, i8 ()*, void ()* }, align 4
+
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+declare void @f1()
+declare void @f1a(i8 zeroext)
+declare signext i8 @f2()
+declare void @f3(%26* noalias nocapture sret)
+
+define internal %0* @mrg1() optsize {
+  %1 = alloca %26, align 4
+  %2 = bitcast %26* %1 to i8*
+  call void @llvm.lifetime.start(i64 56, i8* %2)
+  call void @f3(%26* nonnull sret %1)
+  call void @f1a(i8 zeroext 1)
+  %3 = load i8, i8* @xx, align 1
+  %4 = icmp eq i8 %3, 1
+  br i1 %4, label %5, label %18
+
+; <label>:5:                                      ; preds = %0
+  %6 = call signext i8 @f2()
+  %7 = icmp eq i8 %6, 2
+  br i1 %7, label %8, label %18
+
+; <label>:8:                                      ; preds = %5
+  %9 = getelementptr inbounds %26, %26* %1, i32 0, i32 0
+  %10 = load i32, i32* %9, align 4
+  %11 = icmp eq i32 %10, -1
+  br i1 %11, label %16, label %12
+
+; <label>:12:                                     ; preds = %8
+  %13 = getelementptr inbounds %26, %26* %1, i32 0, i32 2
+  %14 = load i8, i8* %13, align 1
+  %15 = icmp eq i8 %14, 1
+  br i1 %15, label %16, label %17
+
+; <label>:16:                                     ; preds = %12, %8
+  call void @f1()
+  br label %17
+
+; <label>:17:                                     ; preds = %16, %12
+  store i8 0, i8* @xx, align 1
+  br label %18
+
+; <label>:18:                                     ; preds = %17, %5, %0
+  call void @llvm.lifetime.end(i64 56, i8* %2)
+  ret %0* bitcast ({ %0* (%1*)*, %0* (%8*)*, %0* (%13*)*, %0* (%39*)*, %0* (%14*)*, %0* (%14*)*, %0* (%15*)*, %0* (%16*)*, %0* ()*, %0* (%17*)*, %0* (%22*)*, %0* (%28*)*, %0* (%32*)*, %0* (%37*)*, %0* (%37*)*, %0* (%37*)*, %0* ()*, %0* (%33*)*, %0* (%36*)*, %0* (%37*)*, %0* (%38*)*, %0* ()*, %0* (%39*)*, %0* ()*, %0* ()*, %0* (%40*)*, %0* ()*, %0* ()*, %0* ()*, %0* ()*, i8 ()*, void ()* }* @yy to %0*)
+}
+
+define internal %41* @mrg2() optsize {
+  %1 = alloca %26, align 4
+  %2 = bitcast %26* %1 to i8*
+  call void @llvm.lifetime.start(i64 56, i8* %2)
+  call void @f3(%26* nonnull sret %1)
+  call void @f1a(i8 zeroext 1)
+  %3 = load i8, i8* @xx, align 1
+  %4 = icmp eq i8 %3, 1
+  br i1 %4, label %5, label %18
+
+; <label>:5:                                      ; preds = %0
+  %6 = call signext i8 @f2()
+  %7 = icmp eq i8 %6, 2
+  br i1 %7, label %8, label %18
+
+; <label>:8:                                      ; preds = %5
+  %9 = getelementptr inbounds %26, %26* %1, i32 0, i32 0
+  %10 = load i32, i32* %9, align 4
+  %11 = icmp eq i32 %10, -1
+  br i1 %11, label %16, label %12
+
+; <label>:12:                                     ; preds = %8
+  %13 = getelementptr inbounds %26, %26* %1, i32 0, i32 2
+  %14 = load i8, i8* %13, align 1
+  %15 = icmp eq i8 %14, 1
+  br i1 %15, label %16, label %17
+
+; <label>:16:                                     ; preds = %12, %8
+  call void @f1()
+  br label %17
+
+; <label>:17:                                     ; preds = %16, %12
+  store i8 0, i8* @xx, align 1
+  br label %18
+
+; <label>:18:                                     ; preds = %17, %5, %0
+  call void @llvm.lifetime.end(i64 56, i8* %2)
+  ret %41* bitcast ({ %41* (%1*)*, %41* (%8*)*, %41* (%13*)*, %41* (%39*)*, %41* (%14*)*, %41* (%14*)*, %41* (%15*)*, %41* (%16*)*, %41* ()*, %41* (%17*)*, %41* (%22*)*, %41* (%28*)*, %41* (%32*)*, %41* (%37*)*, %41* (%37*)*, %41* (%37*)*, %41* ()*, %41* (%33*)*, %41* (%36*)*, %41* (%37*)*, %41* (%38*)*, %41* ()*, %41* (%39*)*, %41* ()*, %41* ()*, %41* (%40*)*, %41* ()*, %41* ()*, %41* ()*, %41* ()*, i8 ()*, void ()* }* @zz to %41*)
+}

llvm/test/Transforms/MergeSimilarFunc/multi-merge.ll

+; RUN: opt -mergefunc -mergesimilarfunc -mergesimilarfunc-level=all < %s -S | FileCheck %s
+
+; CHECK: define i32 @A
+; CHECK: define internal i32 @A__merged
+; CHECK: define i32 @B
+; CHECK: call i32 @A__merged
+; CHECK: define i32 @C
+; CHECK: call i32 @A__merged
+; CHECK: define i32 @D
+; CHECK: call i32 @A__merged
+
+define i32 @A(i32* %a, i32 %n, i32 %c) nounwind {
+entry:
+  %0 = bitcast i32* %a to i8*
+  %mul = mul i32 %n, 4
+  %call = tail call i8* @memset1(i8* %0, i32 %c, i32 %mul) nounwind
+  %cmp7 = icmp sgt i32 %n, 0
+  br i1 %cmp7, label %for.body, label %for.end
+
+for.body:
+  %arrayidx.phi = phi i32* [ %arrayidx.inc, %for.body ], [ %a, %entry ]
+  %i.09 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %sum.08 = phi i32 [ %add, %for.body ], [ 0, %entry ]
+  %1 = load i32, i32* %arrayidx.phi, align 4
+  %add = add nsw i32 %1, %sum.08
+  %inc = add nsw i32 %i.09, 1
+  %exitcond = icmp eq i32 %inc, %n
+  %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1
+  br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body
+
+for.cond.for.end_crit_edge:
+  %phitmp = add i32 %add, 1
+  br label %for.end
+
+for.end:
+  %sum.0.lcssa = phi i32 [ %phitmp, %for.cond.for.end_crit_edge ], [ 1, %entry ]
+  ret i32 %sum.0.lcssa
+}
+
+declare i8* @memset1(i8*, i32, i32)
+
+define i32 @B(i32* %a, i32 %n, i32 %c) nounwind {
+entry:
+  %0 = bitcast i32* %a to i8*
+  %mul = mul i32 %n, 4
+  %call = tail call i8* @memset1(i8* %0, i32 %c, i32 %mul) nounwind
+  %cmp7 = icmp sgt i32 %n, 0
+  br i1 %cmp7, label %for.body, label %for.end
+
+for.body:
+  %arrayidx.phi = phi i32* [ %arrayidx.inc, %for.body ], [ %a, %entry ]
+  %i.09 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %sum.08 = phi i32 [ %add, %for.body ], [ 0, %entry ]
+  %1 = load i32, i32* %arrayidx.phi, align 4
+  %add = add nsw i32 %1, %sum.08
+  %inc = add nsw i32 %i.09, 1
+  %exitcond = icmp eq i32 %inc, %n
+  %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1
+  br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body
+
+for.cond.for.end_crit_edge:
+  %phitmp = add i32 %add, 2
+  br label %for.end
+
+for.end:
+  %sum.0.lcssa = phi i32 [ %phitmp, %for.cond.for.end_crit_edge ], [ 2, %entry ]
+  ret i32 %sum.0.lcssa
+}
+
+define i32 @C(i32* %a, i32 %n, i32 %c) nounwind {
+entry:
+  %0 = bitcast i32* %a to i8*
+  %mul = mul i32 %n, 4
+  %call = tail call i8* @memset1(i8* %0, i32 %c, i32 %mul) nounwind
+  %cmp7 = icmp sgt i32 %n, 0
+  br i1 %cmp7, label %for.body, label %for.end
+
+for.body:
+  %arrayidx.phi = phi i32* [ %arrayidx.inc, %for.body ], [ %a, %entry ]
+  %i.09 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %sum.08 = phi i32 [ %add, %for.body ], [ 1, %entry ]
+  %1 = load i32, i32* %arrayidx.phi, align 4
+  %add = add nsw i32 %1, %sum.08
+  %inc = add nsw i32 %i.09, 1
+  %exitcond = icmp eq i32 %inc, %n
+  %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1
+  br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body
+
+for.cond.for.end_crit_edge:
+  %phitmp = add i32 %add, 3
+  br label %for.end
+
+for.end:
+  %sum.0.lcssa = phi i32 [ %phitmp, %for.cond.for.end_crit_edge ], [ 4, %entry ]
+  ret i32 %sum.0.lcssa
+}
+
+define i32 @D(i32* %a, i32 %n, i32 %c) nounwind {
+entry:
+  %0 = bitcast i32* %a to i8*
+  %mul = mul i32 %n, 4
+  %call = tail call i8* @memset1(i8* %0, i32 %c, i32 %mul) nounwind
+  %cmp7 = icmp sgt i32 %n, 0
+  br i1 %cmp7, label %for.body, label %for.end
+
+for.body:
+  %arrayidx.phi = phi i32* [ %arrayidx.inc, %for.body ], [ %a, %entry ]
+  %i.09 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %sum.08 = phi i32 [ %add, %for.body ], [ 1, %entry ]
+  %1 = load i32, i32* %arrayidx.phi, align 4
+  %add = add nsw i32 %1, %sum.08
+  %inc = add nsw i32 %i.09, 1
+  %exitcond = icmp eq i32 %inc, %n
+  %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1
+  br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body
+
+for.cond.for.end_crit_edge:
+  %phitmp = add i32 %add, 4
+  br label %for.end
+
+for.end:
+  %sum.0.lcssa = phi i32 [ %phitmp, %for.cond.for.end_crit_edge ], [ 5, %entry ]
+  ret i32 %sum.0.lcssa
+}

llvm/test/Transforms/MergeSimilarFunc/self-ref.ll

+; RUN: opt -mergefunc -mergesimilarfunc -mergesimilarfunc-level=all -mergesimilarfunc-min-insts=0 -mergesimilarfunc-diff-min-insts=0 < %s -S | FileCheck %s
+
+; This test checks if we can tell the difference between the two corresponding
+; calls to foobar.  Each call has a  reference to the containing function as the
+; only argument to foobar.
+; If we cannot tell the difference between these two calls, then the functions
+; foo and bar below will be considered identical and bar will simply be patched
+; up to call foo. However, these functions are not identical as the calls to foobar
+; are themselves different. So, these functions are similar, but not identical.
+; bar should be patched up to call foo__merged which has code to deal with the
+; two different calls to foobar.
+
+; CHECK: define i32 @bar(i32 %a) #0 {
+; CHECK: %1 = tail call i32 @foo__merged(i32 %a, i32 1)
+define i32 @foo(i32 %a) nounwind {
+entry:
+  %a.addr = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  %call = call i32 @foobar(i32 (i32)* @foo)
+  store i32 %call, i32* %b, align 4
+  %0 = load i32, i32* %a.addr, align 4
+  %1 = load i32, i32* %b, align 4
+  %add = add nsw i32 %0, %1
+  ret i32 %add
+}
+
+declare i32 @foobar(i32 (i32)*)
+
+define i32 @bar(i32 %a) nounwind {
+entry:
+  %a.addr = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  %call = call i32 @foobar(i32 (i32)* @bar)
+  store i32 %call, i32* %b, align 4
+  %0 = load i32, i32* %a.addr, align 4
+  %1 = load i32, i32* %b, align 4
+  %add = add nsw i32 %0, %1
+  ret i32 %add
+}

llvm/test/Transforms/MergeSimilarFunc/strong-weak.ll

+; RUN: opt -mergefunc -mergesimilarfunc -mergesimilarfunc-level=all -mergesimilarfunc-min-insts=0 -mergesimilarfunc-diff-min-insts=1 < %s -S
+; REQUIRES: asserts
+; CHECK-NOT: __merged
+define weak i32 @bar(i32 %a) nounwind {
+entry:
+  %a.addr = alloca i32, align 4
+  %b = alloca i32, align 4
+  %d = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  %0 = load i32, i32* %a.addr, align 4
+  %1 = load i32, i32* %d, align 4
+  %add = add nsw i32 %0, %1
+  %call = call i32 bitcast (i32 (...)* @foo to i32 ()*)()
+  %add1 = add nsw i32 %add, %call
+  store i32 %add1, i32* %b, align 4
+  %2 = load i32, i32* %b, align 4
+  ret i32 %2
+}
+
+declare i32 @foo(...)
+
+define i32 @barred(i32 %a) nounwind {
+entry:
+  %a.addr = alloca i32, align 4
+  %b = alloca i32, align 4
+  %d = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  %0 = load i32, i32* %a.addr, align 4
+  %1 = load i32, i32* %d, align 4
+  %add = add nsw i32 %0, %1
+  %call = call i32 bitcast (i32 (...)* @boohoo to i32 ()*)()
+  %add1 = add nsw i32 %add, %call
+  store i32 %add1, i32* %b, align 4
+  %2 = load i32, i32* %b, align 4
+  ret i32 %2
+}
+
+declare i32 @boohoo(...)

llvm/unittests/Transforms/Utils/CloningTest.cpp

TEST_F(CloneInstruction, Attributes) {
 
   Argument *A = &*F1->arg_begin();
   A->addAttr(Attribute::NoCapture);
 
   SmallVector<ReturnInst*, 4> Returns;
   ValueToValueMapTy VMap;
   VMap[A] = UndefValue::get(A->getType());
 
-  CloneFunctionInto(F2, F1, VMap, false, Returns);
+  CloneFunctionInto(F2, F1, VMap, CloneType::NoModuleLevelChanges, Returns);
   EXPECT_FALSE(F2->arg_begin()->hasNoCaptureAttr());
 
   delete F1;
   delete F2;
 }
 
 TEST_F(CloneInstruction, CallingConvention) {
   Type *ArgTy1[] = { Type::getInt32PtrTy(context) };
   FunctionType *FT1 =  FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
 
   Function *F1 = Function::Create(FT1, Function::ExternalLinkage);
   F1->setCallingConv(CallingConv::Cold);
   BasicBlock *BB = BasicBlock::Create(context, "", F1);
   IRBuilder<> Builder(BB);
   Builder.CreateRetVoid();
 
   Function *F2 = Function::Create(FT1, Function::ExternalLinkage);
 
   SmallVector<ReturnInst*, 4> Returns;
   ValueToValueMapTy VMap;
   VMap[&*F1->arg_begin()] = &*F2->arg_begin();
 
-  CloneFunctionInto(F2, F1, VMap, false, Returns);
+  CloneFunctionInto(F2, F1, VMap, CloneType::NoModuleLevelChanges, Returns);
   EXPECT_EQ(CallingConv::Cold, F2->getCallingConv());
 
   delete F1;
   delete F2;
 }
 
 TEST_F(CloneInstruction, DuplicateInstructionsToSplit) {
   Type *ArgTy1[] = {Type::getInt32PtrTy(context)};
TEST(CloneFunction, CloneFunctionToDifferentModule) {
   EXPECT_TRUE(GetDICompileUnitCount(*DeclModule) == 0);
   auto* DeclFunction = DeclModule->getFunction("foo");
   EXPECT_TRUE(DeclFunction != nullptr);
 
   ValueToValueMapTy VMap;
   VMap[ImplFunction] = DeclFunction;
   // No args to map
   SmallVector<ReturnInst*, 8> Returns;
-  CloneFunctionInto(DeclFunction, ImplFunction, VMap, true, Returns);
+  CloneFunctionInto(DeclFunction, ImplFunction, VMap,
+                    CloneType::ModuleLevelChanges, Returns);
 
   EXPECT_FALSE(verifyModule(*ImplModule, &errs()));
   EXPECT_FALSE(verifyModule(*DeclModule, &errs()));
   // DICompileUnit !2 shall be inserted into DeclModule.
   EXPECT_TRUE(GetDICompileUnitCount(*DeclModule) == 1);
 }
 
 class CloneModule : public ::testing::Test {

llvm/unittests/Transforms/Utils/FunctionComparatorTest.cpp

TestFunction(LLVMContext &Ctx, Module &M, int addVal) {
     B.CreateRet(I);
   }
 };
 
 /// A class for testing the FunctionComparator API.
 ///
 /// The main purpose is to test if the required protected functions are
 /// accessible from a derived class of FunctionComparator.
-class TestComparator : public FunctionComparator {
+class TestComparator : public PreciseFunctionComparator {
 public:
-  TestComparator(const Function *F1, const Function *F2,
-                 GlobalNumberState *GN)
-        : FunctionComparator(F1, F2, GN) {
-  }
+  TestComparator(const Function *F1, const Function *F2, GlobalNumberState *GN)
+      : PreciseFunctionComparator(F1, F2, GN) {}
 
   bool testFunctionAccess(const Function *F1, const Function *F2) {
     // Test if FnL and FnR are accessible.
     return F1 == FnL && F2 == FnR;
   }
 
   int testCompare() {
     return compare();