[modules] Change module manager visitation order to be a bit more stable when

more modules are added: visit modules depth-first rather than breadth-first.
The visitation is still (approximately) oldest-to-newest, and still guarantees
that a module is visited before anything it imports, so modules that are
imported by others sometimes need to jump to a later position in the visitation
order when more modules are loaded, but independent module trees don't
interfere with each other any more.

llvm-svn: 242863

1 files changed, 9 insertions, 13 deletions

diff --git a/clang/lib/Serialization/ModuleManager.cpp b/clang/lib/Serialization/ModuleManager.cpp
index 2716194..a52abe6 100644
--- a/clang/lib/Serialization/ModuleManager.cpp
+++ b/clang/lib/Serialization/ModuleManager.cpp
@@ -316,28 +316,24 @@ ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
     SmallVector<ModuleFile *, 4> Queue;
     Queue.reserve(N);
     llvm::SmallVector<unsigned, 4> UnusedIncomingEdges;
-    UnusedIncomingEdges.reserve(size());
-    for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) {
-      if (unsigned Size = (*M)->ImportedBy.size())
-        UnusedIncomingEdges.push_back(Size);
-      else {
-        UnusedIncomingEdges.push_back(0);
+    UnusedIncomingEdges.resize(size());
+    for (auto M = rbegin(), MEnd = rend(); M != MEnd; ++M) {
+      unsigned Size = (*M)->ImportedBy.size();
+      UnusedIncomingEdges[(*M)->Index] = Size;
+      if (!Size)
         Queue.push_back(*M);
-      }
     }
 
     // Traverse the graph, making sure to visit a module before visiting any
     // of its dependencies.
-    unsigned QueueStart = 0;
-    while (QueueStart < Queue.size()) {
-      ModuleFile *CurrentModule = Queue[QueueStart++];
+    while (!Queue.empty()) {
+      ModuleFile *CurrentModule = Queue.pop_back_val();
       VisitOrder.push_back(CurrentModule);
 
       // For any module that this module depends on, push it on the
       // stack (if it hasn't already been marked as visited).
-      for (llvm::SetVector<ModuleFile *>::iterator
-             M = CurrentModule->Imports.begin(),
-             MEnd = CurrentModule->Imports.end();
+      for (auto M = CurrentModule->Imports.rbegin(),
+                MEnd = CurrentModule->Imports.rend();
            M != MEnd; ++M) {
         // Remove our current module as an impediment to visiting the
         // module we depend on. If we were the last unvisited module