[MergeFuncs] Improve ordering of equal functions

[nikic]

Summary

MergeFunctions currently tries to process strong functions before
weak functions, because weak functions can simply call strong
functions, while a strong/weak function cannot call a weak function
(a backing strong function is needed).

This patch additionally tries to process external functions before
local functions, because we definitely have to keep the external
function, but may be able to drop the local one (and definitely
can if it is also unnamed_addr).

Unfortunately, this exposes an existing bug in the implementation:
The FnTree and FNodesInTree structures can currently go out of
sync in the case where two weak functions are merged, because the
function in FnTree/FNodesInTree is RAUWed. This leaves it behind in
FnTree (this is intended, as it is the strong backing function which
should be used for further merges), while it is replaced in
FNodesInTree (this is not intended).

This is fixed by switching FNodesInTree from using a ValueMap to
using a DenseMap of AssertingVH.

This exposes another minor issue: Currently FNodesInTree is not
cleared after MergeFunctions finishes running. Currently, this is
potentially dangerous (e.g. if something else wants to RAUW a function
with a non-function), but at the very least it is unnecessary/inefficient.
After the change to use AssertingVH it becomes more problematic,
because there are certainly passes that remove functions.

This issue is fixed by clearing FNodesInTree at the end of the pass.

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

#endif
   /// to modify it. The map allows efficient lookup and deferring of Functions.
   FnTreeType FnTree;
 
   // 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.
-  ValueMap<Function*, FnTreeType::iterator> FNodesInTree;
+  DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
 };
 
 } // end anonymous namespace
 
 char MergeFunctions::ID = 0;
 
 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
 
for (WeakTrackingVH &I : Worklist) {
       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
         Changed |= insert(F);
       }
     }
     LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
   } while (!Deferred.empty());
 
   FnTree.clear();
+  FNodesInTree.clear();
   GlobalNumbers.clear();
 
   return Changed;
 }
 
 // Replace direct callers of Old with New.
 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
   Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
   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
+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) {
   std::pair<FnTreeType::iterator, bool> Result =
       FnTree.insert(FunctionNode(NewFunction));
 
   if (Result.second) {
     assert(FNodesInTree.count(NewFunction) == 0);
     FNodesInTree.insert({NewFunction, Result.first});
     LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
                       << '\n');
     return false;
   }
 
   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);
     NewFunction = F;
     assert(OldF.getFunc() != F && "Must have swapped the functions.");
   }
 
   LLVM_DEBUG(dbgs() << "  " << OldF.getFunc()->getName()

llvm/trunk/test/Transforms/MergeFunc/external-before-local.ll

+; 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
+}