Index: lib/Transforms/IPO/MergeFunctions.cpp
===================================================================
--- lib/Transforms/IPO/MergeFunctions.cpp
+++ lib/Transforms/IPO/MergeFunctions.cpp
@@ -27,6 +27,14 @@
 // -- We define Function* container class with custom "operator<" (FunctionPtr).
 // -- "FunctionPtr" instances are stored in std::set collection, so every
 //    std::set::insert operation will give you result in log(N) time.
+// 
+// As an optimization, a hash of the function structure is calculated first, and
+// two functions are only compared if they have the same hash. This hash is
+// cheap to compute, and has the property that if function F == G according to
+// the comparision function, then hash(F) == hash(G). This consistency property
+// is critical to ensuring all possible merging opportunities are exploited.
+// Collisions in the hash affect the speed of the pass but not the correctness
+// or determinism of the resulting transformation.
 //
 // When a match is found the functions are folded. If both functions are
 // overridable, we move the functionality into a new internal function and
@@ -121,6 +129,27 @@
 
 namespace {
 
+// Accumulate the hash of a sequence of 64-bit integers. This is similar to a
+// hash function but the entire input does not need to be available at once.
+class HashAccumulator {
+    uint64_t Hash;
+  public:
+    // Initialize to random constant, so the state isn't zero.
+    HashAccumulator() { Hash = 0x6acaa36bef8325c5; }
+    void add(uint64_t v) {
+       // MurmurHash like hashing function, with two rounds of mixing
+       // One round is insufficient to avoid collisions
+       const uint64_t Mul = 0x9ddfea08eb382d69ULL;
+       Hash ^= v;
+       Hash *= Mul;
+       Hash ^= (Hash >> 47);
+       Hash *= Mul;
+       Hash ^= (Hash >> 44);
+    }
+    // No finishing is required, because the entire hash value is used
+    uint64_t getHash() { return Hash; }
+};
+
 /// 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
@@ -132,6 +161,9 @@
 
   /// 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.
+  static uint64_t functionHash(Function&);
 
 private:
   /// Test whether two basic blocks have equivalent behaviour.
@@ -390,9 +422,11 @@
 
 class FunctionNode {
   mutable AssertingVH<Function> F;
+  uint64_t Hash;
 
 public:
-  FunctionNode(Function *F) : F(F) {}
+  // Note the hash is recalculated potentially multiple times, but it is cheap.
+  FunctionNode(Function *F) : F(F), Hash(FunctionComparator::functionHash(*F)){}
   Function *getFunc() const { return F; }
 
   /// Replace the reference to the function F by the function G, assuming their
@@ -406,6 +440,9 @@
 
   void release() { F = 0; }
   bool operator<(const FunctionNode &RHS) const {
+    // Order first by hashes, then full function comparision
+    if (Hash != RHS.Hash)
+      return Hash < RHS.Hash;
     return (FunctionComparator(F, RHS.getFunc()).compare()) == -1;
   }
 };
@@ -1073,6 +1110,39 @@
   return 0;
 }
 
+uint64_t FunctionComparator::functionHash(Function& F) {
+  HashAccumulator H;
+  H.add(F.isVarArg() ? 5433 : 82654);
+  for(auto I = F.arg_begin(), IE = F.arg_end(); I != IE; ++I) {
+    H.add(I->getType()->getTypeID());
+  }
+  
+  SmallVector<const BasicBlock *, 8> BBs;
+  SmallSet<const BasicBlock *, 16> VisitedBBs;
+
+  // Walk the blocks in the same order as FunctionComparator::compare(),
+  // 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 TerminatorInst *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();
+}
+
+
 namespace {
 
 /// MergeFunctions finds functions which will generate identical machine code,
@@ -1227,11 +1297,29 @@
 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<uint64_t, Function*>> HashedFuncs;
+  
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
-    if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage())
-      Deferred.push_back(WeakVH(I));
+    if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) {
+      Function* F = cast<Function>(I);
+      HashedFuncs.push_back({FunctionComparator::functionHash(*F), F});
+    }
   }
 
+  std::sort(HashedFuncs.begin(), HashedFuncs.end());
+  
+  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
+    // consider merging it. Otherwise it is dropped and never considered again.
+    if((I != S && std::prev(I)->first == I->first) ||
+       (std::next(I) != IE && std::next(I)->first == I->first)) {
+      Deferred.push_back(WeakVH(I->second));
+    }
+  }
+  
   do {
     std::vector<WeakVH> Worklist;
     Deferred.swap(Worklist);