Improve the determinism of MergeFunctions

[• jrkoenig]

Summary

Merge functions previously relied on unsigned comparisons of pointer values to
order functions. This caused observable non-determinism in the compiler for
large bitcode programs. Basically, opt -mergefuncs program.bc | md5sum produces
different hashes when run repeatedly on the same machine. Differing output was
observed on three large bitcodes, but it was less frequent on the smallest file.
It is possible that this only manifests on the large inputs, hence remaining
undetected until now.

This patch fixes this by removing (almost, see below) all places where
comparisons between pointers are used to order functions. Most of these changes
are local, but the comparison of global values requires assigning an identifier
to each local in the order it is visited. This is very similar to the way the
comparison function identifies Value*'s defined within a function. Because the
order of visiting the functions and their subparts is deterministic, the
identifiers assigned to the globals will be as well, and the order of functions
will be deterministic.

With these changes, there is no more observed non-determinism. There is also
only minor slowdowns (negligible to 4%) compared to the baseline, which is
likely a result of the fact that global comparisons involve hash lookups and not
just pointer comparisons.

The one caveat so far is that programs containing BlockAddress constants can
still be non-deterministic. It is not clear what the right solution is here. In
particular, even if the global numbers are used to order by function, we still
need a way to order the BasicBlock*'s. Unfortunately, we cannot just bail out
and fail to order the functions or consider them equal, because we require a
total order over functions. Note that programs with BlockAddress constants are
relatively rare, so the impact of leaving this in is minor as long as this pass
is opt-in.

[jfb]

lib/Transforms/IPO/MergeFunctions.cpp

159 ↗

(On Diff #32622)

Use std::tie here, it'll make the code easier to read since you can name first and second: I had to look up insert's API to figure this out :-)

460 ↗

(On Diff #32622)

?

484 ↗

(On Diff #32622)

existant?

489 ↗

(On Diff #32622)

Why not also compare min/max exponent here? It seems like you could add bool operator==(const fltSemantics&, const fltSemantics&) and use that?

616 ↗

(On Diff #32622)

I think it would be worth renaming cmpStrings to cmpMem because that's what StringRef does: it ignores null-termination and does memcmp based on the declared size.

Could you also add a mergefuncs test that makes sure this is the case: two functions with ConstantDataArray (or vector) which have the same length, same prefix, a null byte, and then different tail. They shouldn't get merged with the current implementation.

690 ↗

(On Diff #32622)

Can you cmpBasicBlocks?

695 ↗

(On Diff #32622)

I think some MSVC versions are sad if you don't have a return here. It should be conservative, so not 0.

729 ↗

(On Diff #32622)

Is TyR also known to be IntegerType here? I don't think it is.

731 ↗

(On Diff #32622)

Same here.

998 ↗

(On Diff #32622)

No comparison of getType and getFunctionType?

999 ↗

(On Diff #32622)

Same on final return for MSVC.

[• jrkoenig]

Addressed @jfb's comments.

lib/Transforms/IPO/MergeFunctions.cpp

460 ↗

(On Diff #32622)

GlobalNumbers is not in scope. Moved this assertion to MergeFunctions, where it is in scope

484 ↗

(On Diff #32622)

Extant is technically correct, but I changed it to existing :)

489 ↗

(On Diff #32622)

I'll add APFloat::semanticsMaxExponent/MinExponent and use them here in another patch, as that will touch another file.

690 ↗

(On Diff #32622)

No, cmpBasicBlocks will only verify that the instructions are the same, not that the two Block Addresses point to semantically identical code (because we also need to account for successor blocks). A full solution would do something like compare the functions, and if they are the same, compare the index of each basic block within the function in depth first proposal order.

729 ↗

(On Diff #32622)

From right above the switch, TyL->getTypeID() == TyR->getTypeID(), otherwise the comparison would have have returned.

998 ↗

(On Diff #32622)

Oh, I pulled in all the fields from llvm::InlineAsmKeyType, but the type is also used in the uniquing. Fixed.

[• jrkoenig]

Forgot a &

[jfb]

lgtm besides two nits.

test/Transforms/MergeFunc/constant-entire-value.ll

2 ↗

(On Diff #32862)

Add a description of what this is doing (the 0 check isn't obvious).

22 ↗

(On Diff #32862)

CHECK-NOT like this is usually done with a different RUN: opt ... line, which checks the entire file.

[• jrkoenig]

Made test more robust; added comment

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueHandle.h"
+#include "llvm/IR/ValueMap.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #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");
 
 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);
 
 namespace {
 
+/// GlobalNumberState assigns an integer to each global value in the program,
+/// which is used by the comparison routine to order references to globals. This
+/// state must be preserved throughout the pass, because Functions and other
+/// globals need to maintain their relative order. Globals are assigned a number
+/// when they are first visited. This order is deterministic, and so the
+/// assigned numbers are as well. When two functions are merged, neither number
+/// is updated. If the symbols are weak, this would be incorrect. If they are
+/// strong, then one will be replaced at all references to the other, and so
+/// direct callsites will now see one or the other symbol, and no update is
+/// necessary. Note that if we were guaranteed unique names, we could just
+/// compare those, but this would not work for stripped bitcodes or for those
+/// few symbols without a name.
+class GlobalNumberState {
+  struct Config : ValueMapConfig<GlobalValue*> {
+    enum { FollowRAUW = false };
+  };
+  // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW
+  // occurs, the mapping does not change. Tracking changes is unnecessary, and
+  // also problematic for weak symbols (which may be overwritten).
+  typedef ValueMap<GlobalValue *, uint64_t, Config> ValueNumberMap;
+  ValueNumberMap GlobalNumbers;
+  // The next unused serial number to assign to a global.
+  uint64_t NextNumber;
+  public:
+    GlobalNumberState() : GlobalNumbers(), NextNumber(0) {}
+    uint64_t getNumber(GlobalValue* Global) {
+      ValueNumberMap::iterator MapIter;
+      bool Inserted;
+      std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber});
+      if (Inserted)
+        NextNumber++;
+      return MapIter->second;
+    }
+};
+
 /// FunctionComparator - 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 {
 public:
-  FunctionComparator(const Function *F1, const Function *F2)
-      : FnL(F1), FnR(F2) {}
+  FunctionComparator(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.
   typedef uint64_t FunctionHash;
   static FunctionHash functionHash(Function &);
 
 private:
   /// Test whether two basic blocks have equivalent behaviour.
-  int compare(const BasicBlock *BBL, const BasicBlock *BBR);
+  int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR);
 
   /// Constants comparison.
   /// Its analog to lexicographical comparison between hypothetical numbers
   /// of next format:
   /// <bitcastability-trait><raw-bit-contents>
   ///
   /// 1. Bitcastability.
   /// Check whether L's type could be losslessly bitcasted to R's type.
private:
   /// QED.
   ///
   /// In another words, for pointers and vectors, we ignore top-level type and
   /// look at their particular properties (bit-width for vectors, and
   /// address space for pointers).
   /// If these properties are equal - compare their contents.
   int cmpConstants(const Constant *L, const Constant *R);
 
+  /// Compares two global values by number. Uses the GlobalNumbersState to
+  /// identify the same gobals across function calls.
+  int cmpGlobalValues(GlobalValue *L, GlobalValue *R);
+
   /// 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.
   /// Comparison order:
   /// Stage 0: Value that is function itself is always greater then others.
   ///          If left and right values are references to their functions, then
   ///          they are equal.
   /// Stage 1: Constants are greater than non-constants.
private:
   ///
   /// 0. Before comparison we coerce pointer types of 0 address space to
   /// integer.
   /// We also don't bother with same type at left and right, so
   /// just return 0 in this case.
   ///
   /// 1. If types are of different kind (different type IDs).
   ///    Return result of type IDs comparison, treating them as numbers.
-  /// 2. If types are vectors or integers, compare Type* values as numbers.
-  /// 3. Types has same ID, so check whether they belongs to the next group:
+  /// 2. If types are integers, check that they have the same width. If they
+  /// are vectors, check that they have the same count and subtype.
+  /// 3. Types have the same ID, so check whether they are one of:
   /// * Void
   /// * Float
   /// * Double
   /// * X86_FP80
   /// * FP128
   /// * PPC_FP128
   /// * Label
   /// * Metadata
-  /// If so - return 0, yes - we can treat these types as equal only because
-  /// their IDs are same.
+  /// We can treat these types as equal whenever their IDs are same.
   /// 4. If Left and Right are pointers, return result of address space
   /// comparison (numbers comparison). We can treat pointer types of same
   /// address space as equal.
   /// 5. If types are complex.
   /// Then both Left and Right are to be expanded and their element types will
   /// be checked with the same way. If we get Res != 0 on some stage, return it.
   /// Otherwise return 0.
   /// 6. For all other cases put llvm_unreachable.
   int cmpTypes(Type *TyL, Type *TyR) const;
 
   int cmpNumbers(uint64_t L, uint64_t R) const;
 
   int cmpAPInts(const APInt &L, const APInt &R) const;
   int cmpAPFloats(const APFloat &L, const APFloat &R) const;
-  int cmpStrings(StringRef L, StringRef R) const;
+  int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const;
+  int cmpMem(StringRef L, StringRef R) const;
   int cmpAttrs(const AttributeSet L, const AttributeSet R) const;
 
   // The two functions undergoing comparison.
   const Function *FnL, *FnR;
 
   /// Assign serial numbers to values from left function, and values from
   /// right function.
   /// Explanation:
private:
   /// 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.
   DenseMap<const Value*, int> sn_mapL, sn_mapR;
+
+  // The global state we will use
+  GlobalNumberState* GlobalNumbers;
 };
 
 class FunctionNode {
   mutable AssertingVH<Function> F;
   FunctionComparator::FunctionHash Hash;
-
 public:
   // Note the hash is recalculated potentially multiple times, but it is cheap.
-  FunctionNode(Function *F) : F(F), Hash(FunctionComparator::functionHash(*F)){}
+  FunctionNode(Function *F)
+    : F(F), Hash(FunctionComparator::functionHash(*F))  {}
   Function *getFunc() const { return F; }
+  FunctionComparator::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 {
-    assert(!(*this < FunctionNode(G)) && !(FunctionNode(G) < *this) &&
-           "The two functions must be equal");
-
     F = G;
   }
 
   void release() { F = 0; }
-  bool operator<(const FunctionNode &RHS) const {
-    // Order first by hashes, then full function comparison.
-    if (Hash != RHS.Hash)
-      return Hash < RHS.Hash;
-    return (FunctionComparator(F, RHS.getFunc()).compare()) == -1;
-  }
 };
 }
 
 int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const {
   if (L < R) return -1;
   if (L > R) return 1;
   return 0;
 }
 
 int FunctionComparator::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 {
-  if (int Res = cmpNumbers((uint64_t)&L.getSemantics(),
-                           (uint64_t)&R.getSemantics()))
+  // TODO: This correctly handles all existing fltSemantics, because they all
+  // have different precisions. This isn't very robust, however, if new types
+  // with different exponent ranges are introduced.
+  const fltSemantics &SL = L.getSemantics(), &SR = R.getSemantics();
+  if (int Res = cmpNumbers(APFloat::semanticsPrecision(SL),
+                           APFloat::semanticsPrecision(SR)))
     return Res;
   return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt());
 }
 
-int FunctionComparator::cmpStrings(StringRef L, StringRef R) const {
+int FunctionComparator::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::cmpConstants(const Constant *L, const Constant *R) {
 
   if (L->isNullValue() && R->isNullValue())
     return TypesRes;
   if (L->isNullValue() && !R->isNullValue())
     return 1;
   if (!L->isNullValue() && R->isNullValue())
     return -1;
 
+  auto GlobalValueL = const_cast<GlobalValue*>(dyn_cast<GlobalValue>(L));
+  auto GlobalValueR = const_cast<GlobalValue*>(dyn_cast<GlobalValue>(R));
+  if (GlobalValueL && GlobalValueR) {
+    return cmpGlobalValues(GlobalValueL, GlobalValueR);
+  }
+
   if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
     return Res;
 
+  if (const auto *SeqL = dyn_cast<ConstantDataSequential>(L)) {
+    const auto *SeqR = dyn_cast<ConstantDataSequential>(R);
+    // This handles ConstantDataArray and ConstantDataVector. Note that we
+    // compare the two raw data arrays, which might differ depending on the host
+    // endianness. This isn't a problem though, because the endiness of a module
+    // will affect the order of the constants, but this order is the same
+    // for a given input module and host platform.
+    return cmpMem(SeqL->getRawDataValues(), SeqR->getRawDataValues());
+  }
+
   switch (L->getValueID()) {
   case Value::UndefValueVal: return TypesRes;
   case Value::ConstantIntVal: {
     const APInt &LInt = cast<ConstantInt>(L)->getValue();
     const APInt &RInt = cast<ConstantInt>(R)->getValue();
     return cmpAPInts(LInt, RInt);
   }
   case Value::ConstantFPVal: {
if (int Res = cmpNumbers(NumOperandsL, NumOperandsR))
       return Res;
     for (unsigned i = 0; i < NumOperandsL; ++i) {
       if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)),
                                  cast<Constant>(RE->getOperand(i))))
         return Res;
     }
     return 0;
   }
-  case Value::FunctionVal:
-  case Value::GlobalVariableVal:
-  case Value::GlobalAliasVal:
-  default: // Unknown constant, cast L and R pointers to numbers and compare.
+  case Value::BlockAddressVal: {
+    // FIXME: This still uses a pointer comparison. It isn't clear how to remove
+    // this. This only affects programs which take BlockAddresses and store them
+    // as constants, which is limited to interepreters, etc.
     return cmpNumbers((uint64_t)L, (uint64_t)R);
   }
+  default: // Unknown constant, abort.
+    DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n");
+    llvm_unreachable("Constant ValueID not recognized.");
+    return -1;
+  }
+}
+
+int FunctionComparator::cmpGlobalValues(GlobalValue *L, GlobalValue* R) {
+  return cmpNumbers(GlobalNumbers->getNumber(L), GlobalNumbers->getNumber(R));
 }
 
 /// 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 {
 
   PointerType *PTyL = dyn_cast<PointerType>(TyL);
int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
   if (int Res = cmpNumbers(TyL->getTypeID(), TyR->getTypeID()))
     return Res;
 
   switch (TyL->getTypeID()) {
   default:
     llvm_unreachable("Unknown type!");
     // Fall through in Release mode.
   case Type::IntegerTyID:
-  case Type::VectorTyID:
-    // TyL == TyR would have returned true earlier.
-    return cmpNumbers((uint64_t)TyL, (uint64_t)TyR);
-
+    return cmpNumbers(cast<IntegerType>(TyL)->getBitWidth(),
+                      cast<IntegerType>(TyR)->getBitWidth());
+  case Type::VectorTyID: {
+    VectorType *VTyL = cast<VectorType>(TyL), *VTyR = cast<VectorType>(TyR);
+    if (int Res = cmpNumbers(VTyL->getNumElements(), VTyR->getNumElements()))
+      return Res;
+    return cmpTypes(VTyL->getElementType(), VTyR->getElementType());
+  }
+  // TyL == TyR would have returned true earlier, because types are uniqued.
   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:
int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
   // When we have target data, we can reduce the GEP down to the value in bytes
   // added to the address.
   const DataLayout &DL = FnL->getParent()->getDataLayout();
   unsigned BitWidth = DL.getPointerSizeInBits(ASL);
   APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0);
   if (GEPL->accumulateConstantOffset(DL, OffsetL) &&
       GEPR->accumulateConstantOffset(DL, OffsetR))
     return cmpAPInts(OffsetL, OffsetR);
-
-  if (int Res = cmpNumbers((uint64_t)GEPL->getPointerOperand()->getType(),
-                           (uint64_t)GEPR->getPointerOperand()->getType()))
+  if (int Res = cmpTypes(GEPL->getPointerOperand()->getType(),
+                         GEPR->getPointerOperand()->getType()))
     return Res;
 
   if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
     return Res;
 
   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,
+                                     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;
+  llvm_unreachable("InlineAsm blocks were not uniqued.");
+  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) {
   // Catch self-reference case.
   if (L == FnL) {
     if (R == FnR)
if (ConstL)
     return 1;
   if (ConstR)
     return -1;
 
   const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L);
   const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R);
 
   if (InlineAsmL && InlineAsmR)
-    return cmpNumbers((uint64_t)L, (uint64_t)R);
+    return cmpInlineAsm(InlineAsmL, InlineAsmR);
   if (InlineAsmL)
     return 1;
   if (InlineAsmR)
     return -1;
 
   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::compare(const BasicBlock *BBL, const BasicBlock *BBR) {
+int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
+                                       const BasicBlock *BBR) {
   BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
   BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
 
   do {
     if (int Res = cmpValues(InstL, InstR))
       return Res;
 
     const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(InstL);
int FunctionComparator::compare() {
 
   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 = cmpNumbers((uint64_t)FnL->getGC(), (uint64_t)FnR->getGC()))
+    if (int Res = cmpMem(FnL->getGC(), FnR->getGC()))
       return Res;
   }
 
   if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection()))
     return Res;
 
   if (FnL->hasSection()) {
-    if (int Res = cmpStrings(FnL->getSection(), FnR->getSection()))
+    if (int Res = cmpMem(FnL->getSection(), FnR->getSection()))
       return Res;
   }
 
   if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg()))
     return Res;
 
   // TODO: if it's internal and only used in direct calls, we could handle this
   // case too.
int FunctionComparator::compare() {
   VisitedBBs.insert(FnLBBs[0]);
   while (!FnLBBs.empty()) {
     const BasicBlock *BBL = FnLBBs.pop_back_val();
     const BasicBlock *BBR = FnRBBs.pop_back_val();
 
     if (int Res = cmpValues(BBL, BBR))
       return Res;
 
-    if (int Res = compare(BBL, BBR))
+    if (int Res = cmpBasicBlocks(BBL, BBR))
       return Res;
 
     const TerminatorInst *TermL = BBL->getTerminator();
     const TerminatorInst *TermR = BBR->getTerminator();
 
     assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
     for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
       if (!VisitedBBs.insert(TermL->getSuccessor(i)).second)

 FunctionComparator::FunctionHash FunctionComparator::functionHash(Function &F) {
   HashAccumulator64 H;
   H.add(F.isVarArg());
   H.add(F.arg_size());
   
   SmallVector<const BasicBlock *, 8> BBs;
   SmallSet<const BasicBlock *, 16> VisitedBBs;
 
-  // Walk the blocks in the same order as FunctionComparator::compare(),
+  // Walk the blocks in the same order as FunctionComparator::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); 

 /// by considering all pointer types to be equivalent. Once identified,
 /// MergeFunctions will fold them by replacing a call to one to a call to a
 /// bitcast of the other.
 ///
 class MergeFunctions : public ModulePass {
 public:
   static char ID;
   MergeFunctions()
-    : ModulePass(ID), HasGlobalAliases(false) {
+    : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)),
+      HasGlobalAliases(false) {
     initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M) override;
 
 private:
-  typedef std::set<FunctionNode> FnTreeType;
+  // The function comparison operator is provided here so that FunctionNodes do
+  // not need to become larger with another pointer.
+  class FunctionNodeCmp {
+    GlobalNumberState* GlobalNumbers;
+  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);
+      return FCmp.compare() == -1;
+    }
+  };
+  typedef std::set<FunctionNode, FunctionNodeCmp> FnTreeType;
+
+  GlobalNumberState GlobalNumbers;
 
   /// A work queue of functions that may have been modified and should be
   /// analyzed again.
   std::vector<WeakVH> Deferred;
 
   /// Checks the rules of order relation introduced among functions set.
   /// Returns true, if sanity check has been passed, and false if failed.
   bool doSanityCheck(std::vector<WeakVH> &Worklist);
if (const unsigned Max = NumFunctionsForSanityCheck) {
 
     unsigned i = 0;
     for (std::vector<WeakVH>::iterator I = Worklist.begin(), E = Worklist.end();
          I != E && i < Max; ++I, ++i) {
       unsigned j = i;
       for (std::vector<WeakVH>::iterator J = I; J != E && j < Max; ++J, ++j) {
         Function *F1 = cast<Function>(*I);
         Function *F2 = cast<Function>(*J);
-        int Res1 = FunctionComparator(F1, F2).compare();
-        int Res2 = FunctionComparator(F2, F1).compare();
+        int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
+        int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
 
         // If F1 <= F2, then F2 >= F1, otherwise report failure.
         if (Res1 != -Res2) {
           dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
                  << "\n";
           F1->dump();
           F2->dump();
           Valid = false;
         }
 
         if (Res1 == 0)
           continue;
 
         unsigned k = j;
         for (std::vector<WeakVH>::iterator K = J; K != E && k < Max;
              ++k, ++K, ++TripleNumber) {
           if (K == J)
             continue;
 
           Function *F3 = cast<Function>(*K);
-          int Res3 = FunctionComparator(F1, F3).compare();
-          int Res4 = FunctionComparator(F2, F3).compare();
+          int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
+          int Res4 = FunctionComparator(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
void MergeFunctions::replaceFunctionInTree(FnTreeType::iterator &IterToF,
   Function *F = IterToF->getFunc();
 
   // A total order is already guaranteed otherwise because we process strong
   // functions before weak functions.
   assert(((F->mayBeOverridden() && G->mayBeOverridden()) ||
           (!F->mayBeOverridden() && !G->mayBeOverridden())) &&
          "Only change functions if both are strong or both are weak");
   (void)F;
+  assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
+         "The two functions must be equal");
 
   IterToF->replaceBy(G);
 }
 
 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
 // that was already inserted.
 bool MergeFunctions::insert(Function *NewFunction) {
   std::pair<FnTreeType::iterator, bool> Result =

llvm/trunk/test/Transforms/MergeFunc/constant-entire-value.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; RUN: opt -S -mergefunc < %s | FileCheck -check-prefix=NOPLUS %s
+
+; This makes sure that zeros in constants don't cause problems with string based
+; memory comparisons
+define internal i32 @sum(i32 %x, i32 %y) {
+; CHECK-LABEL: @sum
+  %sum = add i32 %x, %y
+  %1 = extractvalue [3 x i32] [ i32 3, i32 0, i32 2 ], 2
+  %sum2 = add i32 %sum, %1
+  %sum3 = add i32 %sum2, %y
+  ret i32 %sum3
+}
+
+define internal i32 @add(i32 %x, i32 %y) {
+; CHECK-LABEL: @add
+  %sum = add i32 %x, %y
+  %1 = extractvalue [3 x i32] [ i32 3, i32 0, i32 1 ], 2
+  %sum2 = add i32 %sum, %1
+  %sum3 = add i32 %sum2, %y
+  ret i32 %sum3
+}
+
+define internal i32 @plus(i32 %x, i32 %y) {
+; NOPLUS-NOT: @plus
+  %sum = add i32 %x, %y
+  %1 = extractvalue [3 x i32] [ i32 3, i32 0, i32 5 ], 2
+  %sum2 = add i32 %sum, %1
+  %sum3 = add i32 %sum2, %y
+  ret i32 %sum3
+}
+
+define internal i32 @next(i32 %x, i32 %y) {
+; CHECK-LABEL: @next
+  %sum = add i32 %x, %y
+  %1 = extractvalue [3 x i32] [ i32 3, i32 0, i32 5 ], 2
+  %sum2 = add i32 %sum, %1
+  %sum3 = add i32 %sum2, %y
+  ret i32 %sum3
+}
+