1 files changed, 40 insertions, 26 deletions

diff --git a/lib/Analysis/CodeMetrics.cpp b/lib/Analysis/CodeMetrics.cpp
index ed8370498dd0..bdffdd8eb270 100644
--- a/lib/Analysis/CodeMetrics.cpp
+++ b/lib/Analysis/CodeMetrics.cpp
@@ -27,36 +27,45 @@
 
 using namespace llvm;
 
-static void completeEphemeralValues(SmallVector<const Value *, 16> &WorkSet,
-                                    SmallPtrSetImpl<const Value*> &EphValues) {
-  SmallPtrSet<const Value *, 32> Visited;
-
-  // Make sure that all of the items in WorkSet are in our EphValues set.
-  EphValues.insert(WorkSet.begin(), WorkSet.end());
+static void
+appendSpeculatableOperands(const Value *V,
+                           SmallPtrSetImpl<const Value *> &Visited,
+                           SmallVectorImpl<const Value *> &Worklist) {
+  const User *U = dyn_cast<User>(V);
+  if (!U)
+    return;
+
+  for (const Value *Operand : U->operands())
+    if (Visited.insert(Operand).second)
+      if (isSafeToSpeculativelyExecute(Operand))
+        Worklist.push_back(Operand);
+}
 
+static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited,
+                                    SmallVectorImpl<const Value *> &Worklist,
+                                    SmallPtrSetImpl<const Value *> &EphValues) {
   // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
   // alive only by ephemeral values.
 
-  while (!WorkSet.empty()) {
-    const Value *V = WorkSet.front();
-    WorkSet.erase(WorkSet.begin());
+  // Walk the worklist using an index but without caching the size so we can
+  // append more entries as we process the worklist. This forms a queue without
+  // quadratic behavior by just leaving processed nodes at the head of the
+  // worklist forever.
+  for (int i = 0; i < (int)Worklist.size(); ++i) {
+    const Value *V = Worklist[i];
 
-    if (!Visited.insert(V).second)
-      continue;
+    assert(Visited.count(V) &&
+           "Failed to add a worklist entry to our visited set!");
 
     // If all uses of this value are ephemeral, then so is this value.
-    if (!std::all_of(V->user_begin(), V->user_end(),
-                     [&](const User *U) { return EphValues.count(U); }))
+    if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
       continue;
 
     EphValues.insert(V);
     DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
 
-    if (const User *U = dyn_cast<User>(V))
-      for (const Value *J : U->operands()) {
-        if (isSafeToSpeculativelyExecute(J))
-          WorkSet.push_back(J);
-      }
+    // Append any more operands to consider.
+    appendSpeculatableOperands(V, Visited, Worklist);
   }
 }
 
@@ -64,29 +73,32 @@ static void completeEphemeralValues(SmallVector<const Value *, 16> &WorkSet,
 void CodeMetrics::collectEphemeralValues(
     const Loop *L, AssumptionCache *AC,
     SmallPtrSetImpl<const Value *> &EphValues) {
-  SmallVector<const Value *, 16> WorkSet;
+  SmallPtrSet<const Value *, 32> Visited;
+  SmallVector<const Value *, 16> Worklist;
 
   for (auto &AssumeVH : AC->assumptions()) {
     if (!AssumeVH)
       continue;
     Instruction *I = cast<Instruction>(AssumeVH);
 
-    // Filter out call sites outside of the loop so we don't to a function's
+    // Filter out call sites outside of the loop so we don't do a function's
     // worth of work for each of its loops (and, in the common case, ephemeral
     // values in the loop are likely due to @llvm.assume calls in the loop).
     if (!L->contains(I->getParent()))
       continue;
 
-    WorkSet.push_back(I);
+    if (EphValues.insert(I).second)
+      appendSpeculatableOperands(I, Visited, Worklist);
   }
 
-  completeEphemeralValues(WorkSet, EphValues);
+  completeEphemeralValues(Visited, Worklist, EphValues);
 }
 
 void CodeMetrics::collectEphemeralValues(
     const Function *F, AssumptionCache *AC,
     SmallPtrSetImpl<const Value *> &EphValues) {
-  SmallVector<const Value *, 16> WorkSet;
+  SmallPtrSet<const Value *, 32> Visited;
+  SmallVector<const Value *, 16> Worklist;
 
   for (auto &AssumeVH : AC->assumptions()) {
     if (!AssumeVH)
@@ -94,17 +106,19 @@ void CodeMetrics::collectEphemeralValues(
     Instruction *I = cast<Instruction>(AssumeVH);
     assert(I->getParent()->getParent() == F &&
            "Found assumption for the wrong function!");
-    WorkSet.push_back(I);
+
+    if (EphValues.insert(I).second)
+      appendSpeculatableOperands(I, Visited, Worklist);
   }
 
-  completeEphemeralValues(WorkSet, EphValues);
+  completeEphemeralValues(Visited, Worklist, EphValues);
 }
 
 /// Fill in the current structure with information gleaned from the specified
 /// block.
 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
                                     const TargetTransformInfo &TTI,
-                                    SmallPtrSetImpl<const Value*> &EphValues) {
+                                    const SmallPtrSetImpl<const Value*> &EphValues) {
   ++NumBlocks;
   unsigned NumInstsBeforeThisBB = NumInsts;
   for (const Instruction &I : *BB) {