From 5a2e4d83b41d4519f33486dfaec106bf94667c73 Mon Sep 17 00:00:00 2001
From: Nick Lewycky <nicholas@mxc.ca>
Date: Tue, 31 Aug 2010 08:29:37 +0000
Subject: [PATCH] Fix an infinite loop; merging two functions will create a new
 function (if the two are weak, we make them thunks to a new strong function)
 so don't iterate through the function list as we're modifying it.

Also add back the outermost loop which got removed during the cleanups.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112595 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/IPO/MergeFunctions.cpp | 76 +++++++++++++++++++++--------------
 1 file changed, 45 insertions(+), 31 deletions(-)

diff --git a/lib/Transforms/IPO/MergeFunctions.cpp b/lib/Transforms/IPO/MergeFunctions.cpp
index cefed1a059..5d838f98aa 100644
--- a/lib/Transforms/IPO/MergeFunctions.cpp
+++ b/lib/Transforms/IPO/MergeFunctions.cpp
@@ -63,6 +63,7 @@
 #include "llvm/Support/ValueHandle.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetData.h"
+#include <vector>
 using namespace llvm;
 
 STATISTIC(NumFunctionsMerged, "Number of functions merged");
@@ -82,7 +83,8 @@ namespace {
 
   private:
     /// MergeTwoFunctions - Merge two equivalent functions. Upon completion, G
-    /// is deleted.
+    /// may be deleted, or may be converted into a thunk. In either case, it
+    /// should never be visited again.
     void MergeTwoFunctions(Function *F, Function *G) const;
 
     /// WriteThunk - Replace G with a simple tail call to bitcast(F). Also
@@ -598,41 +600,53 @@ struct MergeFunctionsEqualityInfo {
 };
 
 bool MergeFunctions::runOnModule(Module &M) {
-  bool Changed = false;
-
-  TD = getAnalysisIfAvailable<TargetData>();
-
   typedef DenseSet<ComparableFunction *, MergeFunctionsEqualityInfo> FnSetType;
-  FnSetType FnSet;
-  for (Module::iterator F = M.begin(), E = M.end(); F != E;) {
-    if (F->isDeclaration() || F->hasAvailableExternallyLinkage()) {
-      ++F;
-      continue;
-    }
-
-    ComparableFunction *NewF = new ComparableFunction(F, TD);
-    ++F;
-    std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF);
-    if (!Result.second) {
-      ComparableFunction *&OldF = *Result.first;
-      assert(OldF && "Expected a hash collision");
-
-      // NewF will be deleted in favour of OldF unless NewF is strong and OldF
-      // is weak in which case swap them to keep the strong definition.
 
-      if (OldF->Func->isWeakForLinker() && !NewF->Func->isWeakForLinker())
-        std::swap(OldF, NewF);
+  bool Changed = false;
+  TD = getAnalysisIfAvailable<TargetData>();
 
-      DEBUG(dbgs() << "  " << OldF->Func->getName() << " == "
-                   << NewF->Func->getName() << '\n');
+  std::vector<Function *> Funcs;
+  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+    if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage())
+      Funcs.push_back(F);
+  }
 
-      Changed = true;
-      Function *DeleteF = NewF->Func;
-      delete NewF;
-      MergeTwoFunctions(OldF->Func, DeleteF);
+  bool LocalChanged;
+  do {
+    LocalChanged = false;
+
+    FnSetType FnSet;
+    for (unsigned i = 0, e = Funcs.size(); i != e;) {
+      Function *F = Funcs[i];
+      ComparableFunction *NewF = new ComparableFunction(F, TD);
+      std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF);
+      if (!Result.second) {
+        ComparableFunction *&OldF = *Result.first;
+        assert(OldF && "Expected a hash collision");
+
+        // NewF will be deleted in favour of OldF unless NewF is strong and
+        // OldF is weak in which case swap them to keep the strong definition.
+
+        if (OldF->Func->isWeakForLinker() && !NewF->Func->isWeakForLinker())
+          std::swap(OldF, NewF);
+
+        DEBUG(dbgs() << "  " << OldF->Func->getName() << " == "
+                     << NewF->Func->getName() << '\n');
+
+	Funcs.erase(Funcs.begin() + i);
+	--e;
+
+        Function *DeleteF = NewF->Func;
+        delete NewF;
+        MergeTwoFunctions(OldF->Func, DeleteF);
+	LocalChanged = true;
+        Changed = true;
+      } else {
+	++i;
+      }
     }
-  }
+    DeleteContainerPointers(FnSet);
+  } while (LocalChanged);
 
-  DeleteContainerPointers(FnSet);
   return Changed;
 }
-- 
2.11.4.GIT