[orc] Avoid pathological propogation order (#107488)

In certain pathological object files we were getting extremely slow
linking because we were repeatedly propogating dependencies to the same
blocks instead of accumulating as many changes as possible. Change the
order of iteration so that we go through every node in the worklist
before returning to any previous node, reducing the number of expensive
dependency iterations.

In practice, this took one case from 60 seconds to 2 seconds. Note: the
performance is still non-deterministic, because the block order itself
is non-deterministic.

rdar://133734391

1 files changed, 4 insertions, 3 deletions

diff --git a/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp b/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp
index a66c40d..073c25e 100644
--- a/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp
+++ b/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp
@@ -605,7 +605,7 @@ private:
       bool DependenciesChanged = true;
     };
     DenseMap<Block *, BlockInfo> BlockInfos;
-    SmallVector<Block *> WorkList;
+    std::deque<Block *> WorkList;
 
     // Pre-allocate map entries. This prevents any iterator/reference
     // invalidation in the next loop.
@@ -637,7 +637,8 @@ private:
 
     // Propagate block-level dependencies through the block-dependence graph.
     while (!WorkList.empty()) {
-      auto *B = WorkList.pop_back_val();
+      auto *B = WorkList.back();
+      WorkList.pop_back();
 
       auto &BI = BlockInfos[B];
       assert(BI.DependenciesChanged &&
@@ -650,7 +651,7 @@ private:
               DependantBI.Dependencies.insert(Dependency).second)
             if (!DependantBI.DependenciesChanged) {
               DependantBI.DependenciesChanged = true;
-              WorkList.push_back(Dependant);
+              WorkList.push_front(Dependant);
             }
         }
       }