[Assumptions] Make collecting ephemeral values not quadratic in the number of assume intrinsics.

[chandlerc]

Summary

The classical way to have a cache-friendly vector style container when
we need queue semantics for BFS instead of stack semantics for DFS is to
use an ever-growing vector and an index. Erasing from the front requires
O(size) work, and unless we expect the worklist to grow *very* large,
its probably cheaper to just grow and race down the list.

But that makes it more bad that we're putting the assume intrinsics in
this at all. We end up looking at the (by definition empty) use list to
see if they're ephemeral (when we've already put them in that set), etc.

Instead, directly populate the worklist with the operands when we mark
the assume intrinsics as ephemeral. Also, test the visited set *before*
putting things into the worklist so we don't accumulate the same value
in the list 100s of times.

It would be nice to use a set-vector for this but I think its useful to
test the set earlier to avoid repeatedly querying whether the same
instruction is safe to speculate.

Hopefully with these changes the number of values pushed onto the
worklist is smaller, and we avoid quadratic work by letting it grow as
necessary.

[hfinkel]

lib/Analysis/CodeMetrics.cpp

54 ↗

(On Diff #67665)

Is there a reason to use the index here? Why not write this as:

for (auto I = Worklist.begin(); I != Worklist.end(); ++I) {
  const Value *V = *I;

85 ↗

(On Diff #67665)

to a -> do a

[chandlerc]

lib/Analysis/CodeMetrics.cpp

54 ↗

(On Diff #67665)

Because that isn't valid.

When you grow the worklist you invalidate all iterators (because the iterators are just pointers and its a vector that may have to re-allocate).

[dberris]

How hard would it be to amortize the removal from the queue grows to a certain size? I ask because at some point the cost of copying around chunks of memory when a vector grows might outweigh the cost of just regularly trimming the queue if there are visited/stale entries at the beginning to the "current head" iterator.

[chandlerc]

In D23396#517618, @dberris wrote:

How hard would it be to amortize the removal from the queue grows to a certain size? I ask because at some point the cost of copying around chunks of memory when a vector grows might outweigh the cost of just regularly trimming the queue if there are visited/stale entries at the beginning to the "current head" iterator.

I suspect this would hard to make worthwhile...

Because the growth is amortized already, the copies are too. So you're not going to see something *really* hot here no matter what. The real risk is that this uses gobs and gobs of memory.

But it still seems like a very low risk. This is strictly bounded on the number of instructions in a function. I think we are always going to be OK creating a vector with that many pointers in it (and even the visited set of those pointers) in terms of memory usage, so I'm not sure there is really an effective way to make this substantially cheaper.

If you have a concrete suggestion though, I'm happy to look at it. We have lots of worklists like this in LLVM.

[dberris]

If you have a concrete suggestion though, I'm happy to look at it. We have lots of worklists like this in LLVM.

Not at this moment -- but I do think it's worthwhile to have an ADT to implement worklists and algorithms around it, if only to make it easier to reason about the code utilising them (and be able to consolidate the efficiency work to a smaller set of places).

[majnemer]

lib/Analysis/CodeMetrics.cpp

32–33 ↗

(On Diff #67665)

I think you could use a SetVector here because you never pop from Worklist, right?

34 ↗

(On Diff #67665)

const auto *?

[hfinkel]

lib/Analysis/CodeMetrics.cpp

54 ↗

(On Diff #67665)

Ah, right ;) -- Why don't we use a std::deque for these things?

[chandlerc]

lib/Analysis/CodeMetrics.cpp

32–33 ↗

(On Diff #67665)

I started with that, but we add things to the visited set that we don't put on the worklist which allows us to avoid repeatedly querying isSafeToSpeculativelyExecute. While micro-optimizing the data structure seems unlikely to be worthwhile (see my comment below), avoiding repeated calls to this fairly heavy weight routine do seem worthwhile when the cost is just keeping the set separate.

54 ↗

(On Diff #67665)

Because std::deque is *amazingly* slower, especially for the common case of a small number of values. And any deque implementation will have this property really. Too much book-keeping for too little value.

As Danny pointed out, far and away the best data structure patterns we will come up with will look roughly like a double stack or a vector that auto-shrinks the front when forced to re-allocate due to growth at the back.

But I strongly, strongly suspect that *this* is not the code path so hot to motivate adding a highly tuned data structure. So I don't think we should wait for that here, I think we should go with the normal, boring solution that is used pretty much everywhere else already. And if/when we find something that is hot enough to *really* care, let's build a nicely tuned thing.

All I really want is to make this not quadratic. ;]

[hfinkel]

lib/Analysis/CodeMetrics.cpp

54 ↗

(On Diff #67665)

Because std::deque is *amazingly* slower, especially for the common case of a small number of values.
...
But I strongly, strongly suspect that *this* is not the code path so hot to motivate adding a highly tuned data structure.

So this is kind of my point ;) -- but fair enough, if this is the useful general pattern, this LGTM.

llvm/trunk/lib/Analysis/CodeMetrics.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "code-metrics"
 
 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 (!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);
   }
 }
 
 // Find all ephemeral values.
 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)
       continue;
     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,
                                     const SmallPtrSetImpl<const Value*> &EphValues) {
   ++NumBlocks;