fix a crash in MergeFunctions related to ordering of weak/strong functions

[eeckstein]

Summary

The assumption, made in insert() that weak functions are always inserted after strong functions, is only true in the first round of adding functions. In subsequent rounds this is no longer guaranteed , because we might remove a strong function from the tree (because it's modifier) and add it later, where a equivalent weak function already exists in the tree.
This change removes the assert in insert() and explicitly enforces a weak->strong order.
This also removes the need of two separate loops in runOnModule().

[eeckstein]

forgot to add the test file

[eeckstein]

ping?

[eeckstein]

ping (2)

[eeckstein]

Thanks for reviewing!
Committed in r271299

lib/Transforms/IPO/MergeFunctions.cpp

do {
     std::vector<WeakVH> Worklist;
     Deferred.swap(Worklist);
 
     DEBUG(doSanityCheck(Worklist));
 
     DEBUG(dbgs() << "size of module: " << M.size() << '\n');
     DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
 
-    // Insert only strong functions and merge them. Strong function merging
-    // always deletes one of them.
+    // Insert functions and merge them.
     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
            E = Worklist.end(); I != E; ++I) {
       if (!*I) continue;
       Function *F = cast<Function>(*I);
-      if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
-          !F->isInterposable()) {
-        Changed |= insert(F);
-      }
-    }
-
-    // Insert only weak functions and merge them. By doing these second we
-    // create thunks to the strong function when possible. When two weak
-    // functions are identical, we create a new strong function with two weak
-    // weak thunks to it which are identical but not mergable.
-    for (std::vector<WeakVH>::iterator I = Worklist.begin(),
-           E = Worklist.end(); I != E; ++I) {
-      if (!*I) continue;
-      Function *F = cast<Function>(*I);
-      if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
-          F->isInterposable()) {
+      if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
         Changed |= insert(F);
       }
     }
     DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
   } while (!Deferred.empty());
 
   FnTree.clear();
   GlobalNumbers.clear();
if (NewFunction->front().size() <= 2) {
       return false;
     }
   }
 
   // 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.
   //
-  // When one function is weak and the other is strong there is an order imposed
-  // already. We process strong functions before weak functions.
-  if ((OldF.getFunc()->isInterposable() && NewFunction->isInterposable()) ||
-      (!OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()))
-    if (OldF.getFunc()->getName() > NewFunction->getName()) {
-      // Swap the two functions.
-      Function *F = OldF.getFunc();
-      replaceFunctionInTree(*Result.first, NewFunction);
-      NewFunction = F;
-      assert(OldF.getFunc() != F && "Must have swapped the functions.");
-    }
+  // 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())) {
 
-  // Never thunk a strong function to a weak function.
-  assert(!OldF.getFunc()->isInterposable() || NewFunction->isInterposable());
-
   DEBUG(dbgs() << "  " << OldF.getFunc()->getName()
                << " == " << NewFunction->getName() << '\n');
 
   Function *DeleteF = NewFunction;
   mergeTwoFunctions(OldF.getFunc(), DeleteF);
   return true;
 }
 

test/Transforms/MergeFunc/merge-weak-crash.ll

+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; CHECK-LABEL: define i32 @func1
+; CHECK: call i32 @func2
+; CHECK: ret
+
+; CHECK-LABEL: define i32 @func2
+; CHECK: call i32 @unknown
+; CHECK: ret
+
+; CHECK-LABEL: define i32 @func4
+; CHECK: call i32 @func2
+; CHECK: ret
+
+; CHECK-LABEL: define weak i32 @func3_weak
+; CHECK: call i32 @func1
+; CHECK: ret
+
+define i32 @func1(i32 %x, i32 %y) {
+  %sum = add i32 %x, %y
+  %sum2 = add i32 %sum, %y
+  %sum3 = call i32 @func4(i32 %sum, i32 %sum2)
+  ret i32 %sum3
+}
+
+define i32 @func4(i32 %x, i32 %y) {
+  %sum = add i32 %x, %y
+  %sum2 = add i32 %sum, %y
+  %sum3 = call i32 @unknown(i32 %sum, i32 %sum2)
+  ret i32 %sum3
+}
+
+define weak i32 @func3_weak(i32 %x, i32 %y) {
+  %sum = add i32 %x, %y
+  %sum2 = add i32 %sum, %y
+  %sum3 = call i32 @func2(i32 %sum, i32 %sum2)
+  ret i32 %sum3
+}
+
+define i32 @func2(i32 %x, i32 %y) {
+  %sum = add i32 %x, %y
+  %sum2 = add i32 %sum, %y
+  %sum3 = call i32 @unknown(i32 %sum, i32 %sum2)
+  ret i32 %sum3
+}
+
+declare i32 @unknown(i32 %x, i32 %y)