From 603d6b56a2b72358e7b599aab743beb44823d76c Mon Sep 17 00:00:00 2001
From: Rafael Espindola <rafael.espindola@gmail.com>
Date: Mon, 23 Jan 2012 03:41:53 +0000
Subject: [PATCH] The iteration order over a std::set<Module*> depends on the
 addresses of the modules. Avoid that to make the order the linker sees the
 modules deterministic.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148676 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Bitcode/Archive.h |  2 +-
 lib/Archive/ArchiveReader.cpp  | 28 +++++++++++++++-------------
 lib/Linker/LinkArchives.cpp    |  4 ++--
 3 files changed, 18 insertions(+), 16 deletions(-)

diff --git a/include/llvm/Bitcode/Archive.h b/include/llvm/Bitcode/Archive.h
index f89a86cb0f7..86c44c7f150 100644
--- a/include/llvm/Bitcode/Archive.h
+++ b/include/llvm/Bitcode/Archive.h
@@ -394,7 +394,7 @@ class Archive {
     /// @brief Look up multiple symbols in the archive.
     bool findModulesDefiningSymbols(
       std::set<std::string>& symbols,     ///< Symbols to be sought
-      std::set<Module*>& modules,         ///< The modules matching \p symbols
+      SmallVectorImpl<Module*>& modules,  ///< The modules matching \p symbols
       std::string* ErrMessage             ///< Error msg storage, if non-zero
     );
 
diff --git a/lib/Archive/ArchiveReader.cpp b/lib/Archive/ArchiveReader.cpp
index eef6fe0b1c1..0c89baa0d7d 100644
--- a/lib/Archive/ArchiveReader.cpp
+++ b/lib/Archive/ArchiveReader.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "ArchiveInternals.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Module.h"
@@ -504,7 +505,7 @@ Archive::findModuleDefiningSymbol(const std::string& symbol,
 // Modules that define those symbols.
 bool
 Archive::findModulesDefiningSymbols(std::set<std::string>& symbols,
-                                    std::set<Module*>& result,
+                                    SmallVectorImpl<Module*>& result,
                                     std::string* error) {
   if (!mapfile || !base) {
     if (error)
@@ -569,21 +570,22 @@ Archive::findModulesDefiningSymbols(std::set<std::string>& symbols,
   // At this point we have a valid symbol table (one way or another) so we
   // just use it to quickly find the symbols requested.
 
+  SmallPtrSet<Module*, 16> Added;
   for (std::set<std::string>::iterator I=symbols.begin(),
-       E=symbols.end(); I != E;) {
+       E=symbols.end(); I != E; ++I) {
     // See if this symbol exists
     Module* m = findModuleDefiningSymbol(*I,error);
-    if (m) {
-      // The symbol exists, insert the Module into our result, duplicates will
-      // be ignored.
-      result.insert(m);
-
-      // Remove the symbol now that its been resolved, being careful to
-      // post-increment the iterator.
-      symbols.erase(I++);
-    } else {
-      ++I;
-    }
+    if (!m)
+      continue;
+    bool NewMember = Added.insert(m);
+    if (!NewMember)
+      continue;
+
+    // The symbol exists, insert the Module into our result.
+    result.push_back(m);
+
+    // Remove the symbol now that its been resolved.
+    symbols.erase(I);
   }
   return true;
 }
diff --git a/lib/Linker/LinkArchives.cpp b/lib/Linker/LinkArchives.cpp
index 7a594246523..c16d1958cdf 100644
--- a/lib/Linker/LinkArchives.cpp
+++ b/lib/Linker/LinkArchives.cpp
@@ -140,7 +140,7 @@ Linker::LinkInArchive(const sys::Path &Filename, bool &is_native) {
     // Find the modules we need to link into the target module.  Note that arch
     // keeps ownership of these modules and may return the same Module* from a
     // subsequent call.
-    std::set<Module*> Modules;
+    SmallVector<Module*, 16> Modules;
     if (!arch->findModulesDefiningSymbols(UndefinedSymbols, Modules, &ErrMsg))
       return error("Cannot find symbols in '" + Filename.str() + 
                    "': " + ErrMsg);
@@ -157,7 +157,7 @@ Linker::LinkInArchive(const sys::Path &Filename, bool &is_native) {
         UndefinedSymbols.end());
 
     // Loop over all the Modules that we got back from the archive
-    for (std::set<Module*>::iterator I=Modules.begin(), E=Modules.end();
+    for (SmallVectorImpl<Module*>::iterator I=Modules.begin(), E=Modules.end();
          I != E; ++I) {
 
       // Get the module we must link in.
-- 
2.34.1