Index: llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp
===================================================================
--- llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp
+++ llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp
@@ -284,7 +284,7 @@
   // 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.
-  ValueMap<Function*, FnTreeType::iterator> FNodesInTree;
+  DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
 };
 
 } // end anonymous namespace
@@ -425,6 +425,7 @@
   } while (!Deferred.empty());
 
   FnTree.clear();
+  FNodesInTree.clear();
   GlobalNumbers.clear();
 
   return Changed;
@@ -817,6 +818,24 @@
   FN.replaceBy(G);
 }
 
+// Ordering for functions that are equal under FunctionComparator
+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
+    // function, but may be able to drop the local one.
+    return !F->hasLocalLinkage();
+  }
+  // Impose a total order (by name) on the replacement of functions. This is
+  // important when operating on more than one module independently to prevent
+  // cycles of thunks calling each other when the modules are linked together.
+  return F->getName() <= G->getName();
+}
+
 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
 // that was already inserted.
 bool MergeFunctions::insert(Function *NewFunction) {
@@ -833,14 +852,7 @@
 
   const FunctionNode &OldF = *Result.first;
 
-  // Impose a total order (by name) on the replacement of functions. This is
-  // important when operating on more than one module independently to prevent
-  // cycles of thunks calling each other when the modules are linked together.
-  //
-  // First of all, we process strong functions before weak functions.
-  if ((OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()) ||
-     (OldF.getFunc()->isInterposable() == NewFunction->isInterposable() &&
-       OldF.getFunc()->getName() > NewFunction->getName())) {
+  if (!isFuncOrderCorrect(OldF.getFunc(), NewFunction)) {
     // Swap the two functions.
     Function *F = OldF.getFunc();
     replaceFunctionInTree(*Result.first, NewFunction);
Index: llvm/trunk/test/Transforms/MergeFunc/external-before-local.ll
===================================================================
--- llvm/trunk/test/Transforms/MergeFunc/external-before-local.ll
+++ llvm/trunk/test/Transforms/MergeFunc/external-before-local.ll
@@ -0,0 +1,55 @@
+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; We should normalize to test2 rather than test1,
+; because it allows us to drop test1 entirely
+
+; CHECK-NOT: define internal void @test1() unnamed_addr
+; CHECK: define void @test3() unnamed_addr
+; CHECK-NEXT: call void @test2()
+; CHECK-NEXT: call void @test2()
+  
+declare void @dummy()
+
+define internal void @test1() unnamed_addr {
+    call void @dummy()
+    call void @dummy()
+    ret void
+}
+
+define void @test2() unnamed_addr {
+    call void @dummy()
+    call void @dummy()
+    ret void
+}
+
+define void @test3() unnamed_addr {
+    call void @test1()
+    call void @test2()
+    ret void
+}
+
+; We should normalize to the existing test6 rather than
+; to a new anonymous strong backing function
+
+; CHECK: define weak void @test5()
+; CHECK-NEXT: tail call void @test6()
+; CHECK: define weak void @test4()
+; CHECK-NEXT: tail call void @test6()
+
+declare void @dummy2()
+  
+define weak void @test4() {
+    call void @dummy2()
+    call void @dummy2()
+    ret void
+}
+define weak void @test5() {
+    call void @dummy2()
+    call void @dummy2()
+    ret void
+}
+define void @test6() {
+    call void @dummy2()
+    call void @dummy2()
+    ret void
+}