[GVN] Rewrite IsValueFullyAvailableInBlock()

[lebedev.ri]

Summary

While this doesn't appear to help with the perf issue being exposed by D84108,
the function as-is is very weird, convoluted, and what's worse, recursive.

There was no need for SpeculativelyAvaliableAndUsedForSpeculation,
tri-state choice is enough. We don't even ever check for that state.

The basic idea here is that we need to perform a depth-first traversal of the
predecessors of the basic block in question, either finding a preexisting
state for the block in a map, or inserting a "placeholder" SpeculativelyAvaliable,

If we encounter an Unavaliable block, then we need to give up search,
and back-propagate the Unavaliable state to the each successor of said block,
more specifically to the each SpeculativelyAvaliable we've just created.

However, if we have traversed entirety of the predecessors and have not
encountered an Unavaliable block, then it must mean the value is fully available.
We could update each inserted SpeculativelyAvaliable into a Avaliable,
but we don't need to, as assertion excersizes, because we can assume that if
we see an SpeculativelyAvaliable entry, it is actually Avaliable,
because during the time we've produced it, if we would have found that it
has an Unavaliable predecessor, we would have updated it's successors,
including this block, into Unavaliable

[xbolva00]

llvm/lib/Transforms/Scalar/GVN.cpp

683

Available

(Same typo below)

[lebedev.ri]

Fix typo Avaliable->Available everywhere in the patch.

llvm/lib/Transforms/Scalar/GVN.cpp

683

Ugh, thanks!

[nikic]

While this doesn't appear to help with the perf issue being exposed by D84108, the function as-is is very weird, convoluted, and what's worse, recursive.

Would it be possible to share the pre-GVN IR for the problematic case? (Independently of this cleanup, just curious)

But i'm not sure instructions is *really* the right metric here, Because task-clock stat really improved, by -1.5% .. -5% all across the board.

This is just (very large) noise. I've added a disclaimer to the page that the task-clock/wall-time results are best ignored.

[lebedev.ri]

In D84181#2163120, @nikic wrote:

While this doesn't appear to help with the perf issue being exposed by D84108, the function as-is is very weird, convoluted, and what's worse, recursive.

Would it be possible to share the pre-GVN IR for the problematic case? (Independently of this cleanup, just curious)

I don't have any particular problematic case in mind, but here's pre-GVN (i disabled all passes in pipeline starting with GVN)
llvm-test-suite/MultiSource/Applications/JM/lencod/context_ini.c (produced with D84108)

lencod-context_ini-pre-gvn.ll.xz55 KBDownload

But i'm not sure instructions is *really* the right metric here, Because task-clock stat really improved, by -1.5% .. -5% all across the board.

This is just (very large) noise. I've added a disclaimer to the page that the task-clock/wall-time results are best ignored.

And here's standalone results:

y$ perf stat --repeat=100 /builddirs/llvm-project/build-Clang10-Release/bin/opt-old /tmp/lencod-context_ini-pre-gvn.bc -o /dev/null -gvn ; perf stat --repeat=100 /builddirs/llvm-project/build-Clang10-Release/bin/opt /tmp/lencod-context_ini-pre-gvn.bc -o /dev/null -gvn

 Performance counter stats for '/builddirs/llvm-project/build-Clang10-Release/bin/opt-old /tmp/lencod-context_ini-pre-gvn.bc -o /dev/null -gvn' (100 runs):

            795.35 msec task-clock                #    0.999 CPUs utilized            ( +-  0.04% )
                 3      context-switches          #    0.004 K/sec                    ( +-  4.66% )
                 0      cpu-migrations            #    0.000 K/sec                  
              2723      page-faults               #    0.003 M/sec                    ( +-  0.23% )
        3186511786      cycles                    #    4.006 GHz                      ( +-  0.04% )  (83.20%)
         522856359      stalled-cycles-frontend   #   16.41% frontend cycles idle     ( +-  0.09% )  (83.36%)
         956532477      stalled-cycles-backend    #   30.02% backend cycles idle      ( +-  0.11% )  (33.44%)
        2668685815      instructions              #    0.84  insn per cycle         
                                                  #    0.36  stalled cycles per insn  ( +-  0.04% )  (50.05%)
         514286258      branches                  #  646.619 M/sec                    ( +-  0.03% )  (66.64%)
          19609714      branch-misses             #    3.81% of all branches          ( +-  0.06% )  (83.24%)

          0.795919 +- 0.000313 seconds time elapsed  ( +-  0.04% )


 Performance counter stats for '/builddirs/llvm-project/build-Clang10-Release/bin/opt /tmp/lencod-context_ini-pre-gvn.bc -o /dev/null -gvn' (100 runs):

            787.80 msec task-clock                #    0.999 CPUs utilized            ( +-  0.04% )
                 3      context-switches          #    0.003 K/sec                    ( +-  6.11% )
                 0      cpu-migrations            #    0.000 K/sec                    ( +- 70.35% )
              2703      page-faults               #    0.003 M/sec                    ( +-  0.20% )
        3156293784      cycles                    #    4.006 GHz                      ( +-  0.04% )  (83.23%)
         520963102      stalled-cycles-frontend   #   16.51% frontend cycles idle     ( +-  0.09% )  (83.24%)
         931974714      stalled-cycles-backend    #   29.53% backend cycles idle      ( +-  0.14% )  (33.52%)
        2681503031      instructions              #    0.85  insn per cycle         
                                                  #    0.35  stalled cycles per insn  ( +-  0.05% )  (50.28%)
         515472885      branches                  #  654.318 M/sec                    ( +-  0.03% )  (66.96%)
          18427045      branch-misses             #    3.57% of all branches          ( +-  0.08% )  (83.43%)

          0.788365 +- 0.000320 seconds time elapsed  ( +-  0.04% )

So there it's an improvement of -0.949% +- 0.04%

[mkazantsev]

Though I don't see obvious problems in the new algorithm, I cannot wrap my mind around the old one and can't say if they are doing the same thing. I'd suggest the following reliable way to make sure it is NFC:

• Instead of changing logic of IsValueFullyAvailableInBlock, introduce a new version of it and use it.
• In debug mode, also call the old one and assert that the results are the same.
• Then, after it has been in for a long enough while and we are certain those algorithms do the same thing, remove the old one.

WDYT?

llvm/lib/Transforms/Scalar/GVN.cpp

701–703

This name only makes sense because it is used as DFS traversal root. In function signature, BB is more clear.

[lebedev.ri]

In D84181#2168668, @mkazantsev wrote:

Though I don't see obvious problems in the new algorithm, I cannot wrap my mind around the old one

Yeah, i had that feeling myself :/ That's why i've put @lattner as reviewer,
since it was him who seems to have wrote/modified it in rL60408/rL60588 ~12 years ago.

and can't say if they are doing the same thing.

Any particular part that is causing trouble?
The code essentially consists of two separate parts, "maze solving" and backpropagation.

I think, backpropagation is obviously identical at least?
We start at the first block we've found to be an unavailable.
We need to mark each successor block, that isn't known to be available, as unavailable.
Also, to not pay for what we don't use, we should only mark the blocks that we care about,
i.e. those that are already present in the FullyAvailableBlocks map.
So we put said block into worklist, and do pretty typical worklist dance,
take block from worklist, and query (with insert!) it's availability status in a map.
WARNING that in the old version, if the block wasn't in a map already, this adds it as unavailable!
Then, if we have found out that it was unavailable, we just go to the next entry in worklist.
If it wasn't unavailable, we mark it as such
(WARNING: in old version, it would also mark available blocks as unavailable, which is obviously bogus,
while we should only do that for speculatively available blocks),
and proceed to further backpropagate that information to it's successors (by putting them into worklist).

The "maze solving" seems pretty intuitive in hindsight, too:
We start at some block, we want to know if some value is available in that block.
So we see if the map already contains an entry for the block, then we know our answer,
it is either explicitly marked as unavailable, or it's available/speculatively available.
Otherwise, as a perf optimization, we think it will be available, so that added an entry to the map,
marking the block as speculatively available.
Now, we need to check if the value can live-in from each(!) predecessor.
The value can't live-in if there are no predecessors and the block is unavailable.
If there are predecessors, we need to visit each one and do the all over again.

As soon as we find out that the block is unavailable, we have a problem,
we may have marked blocks as speculatively available along the way to the unavailable block.
It is important to notice that we don't deviate from our exploration path,
so all the blocks we have just marked as speculatively available are successors of this block.

Otherwise, if we never encounter an unavailable block, then we're all good.
Since we would have retrospectively fixed all the blocks we have set as speculatively available
as unavailable, from now on, all these speculatively available blocks are available.

All this logic is verified with asserts in the end.

I'd suggest the following reliable way to make sure it is NFC:

• Instead of changing logic of IsValueFullyAvailableInBlock, introduce a new version of it and use it.
• In debug mode, also call the old one and assert that the results are the same.
• Then, after it has been in for a long enough while and we are certain those algorithms do the same thing, remove the old one.

WDYT?

I'm afraid it's not that easy to do.

1. We'd need to workaround the situation where the old code gave up due to the gvn-max-recurse-depth recursion limit
2. We'll need to duplicate FullyAvailableBlocks so we pass the identical one into both the old version and the new one. Note that we can't equality-compare them afterwards, because the new code, unlike the old one, in backpropagation, doesn't insert new nodes
3. The new code doesn't (erroneously) mark previously available successor nodes of an unavailable node unavailable. This technically i guess makes it a non-NFC patch,

[fhahn]

This overall makes sense I think.

In D84181#2168702, @lebedev.ri wrote:

In D84181#2168668, @mkazantsev wrote:>

I'd suggest the following reliable way to make sure it is NFC:

• Instead of changing logic of IsValueFullyAvailableInBlock, introduce a new version of it and use it.
• In debug mode, also call the old one and assert that the results are the same.
• Then, after it has been in for a long enough while and we are certain those algorithms do the same thing, remove the old one.

WDYT?

I'm afraid it's not that easy to do.

1. We'd need to workaround the situation where the old code gave up due to the gvn-max-recurse-depth recursion limit

I think we also need some kind of limit on the worklist size for the iterative algorithm. Without it we might traverse the whole function in some cases, which could lead to huge compile-times in some degenerate cases I think.

2. We'll need to duplicate FullyAvailableBlocks so we pass the identical one into both the old version and the new one. Note that we can't equality-compare them afterwards, because the new code, unlike the old one, in backpropagation, doesn't insert new nodes
3. The new code doesn't (erroneously) mark previously available successor nodes of an unavailable node unavailable. This technically i guess makes it a non-NFC patch,

Yes I think this shouldn't be marked as NFC.

It would be interesting however, how often the answers diverge (with respect the how the result is used in GVN). For example, it would be interesting to know how often PRE triggers in GVN on some large programs (e.g. MultiSource/SPEC/LLVM bootstrap) and how many differences codegen differences there are between the old and new implementation. Hopefully that would be a very small number, which might lead to a test case for the new behavior.

llvm/lib/Transforms/Scalar/GVN.cpp

702

Not sure about the name change. It's not clear to me what fixpoint means here. More accurately, its the map of blocks with known states, right? Whatever name is chosen, the comment above needs updating and we should keep the name consistent at the call sites.

775

The place of the comment next to the return seems a bit strange to me. IMO it would make more sense to have a comment above Worklist.append, stating we queue the successors to continue back-propagating.

787

Again, it is not entirely clear what "non-fixpoint" refers to here. It only means blocks marked as SpeculativelyAvailable, right? Also, back-propagating seems a bit counter-intuitive here at a first glance, if you think of the CFG as a directed graph (edges directed from BB to its successors).

Saying something like

// Okay, we have encountered an "unavailable" block.
// Mark SpeculativelAvailable blocks reachable from UnavailableBB as unavailable as well. Paths are terminated when they reach blocks no in Fixpoints or they are not marked as SpeculativelAvailable.

809

nit: could this just return !UnabilableBB?

[lebedev.ri]

In D84181#2168819, @fhahn wrote:

This overall makes sense I think.

In D84181#2168702, @lebedev.ri wrote:

In D84181#2168668, @mkazantsev wrote:>

I'd suggest the following reliable way to make sure it is NFC:

• Instead of changing logic of IsValueFullyAvailableInBlock, introduce a new version of it and use it.
• In debug mode, also call the old one and assert that the results are the same.
• Then, after it has been in for a long enough while and we are certain those algorithms do the same thing, remove the old one.

WDYT?

I'm afraid it's not that easy to do.

1. We'd need to workaround the situation where the old code gave up due to the gvn-max-recurse-depth recursion limit

I think we also need some kind of limit on the worklist size for the iterative algorithm. Without it we might traverse the whole function in some cases, which could lead to huge compile-times in some degenerate cases I think.

Okay, added one. Right now it's based on the number of times we find a previously unknown block,
mark it as speculatively available, and recurse into it. I think this is the correct way,
i wouldn't think we should just count every block queried, even if we'd found an entry in map?

I don't have SPEC, and didn't try it on whole LLVM, but on vanilla test-suite + RawSpeed + darktable,
said IsValueFullyAvailableInBlockNumSpeculationsMax stat is at max 300, so i've picked a limit of 600.

2. We'll need to duplicate FullyAvailableBlocks so we pass the identical one into both the old version and the new one. Note that we can't equality-compare them afterwards, because the new code, unlike the old one, in backpropagation, doesn't insert new nodes
3. The new code doesn't (erroneously) mark previously available successor nodes of an unavailable node unavailable. This technically i guess makes it a non-NFC patch,

Yes I think this shouldn't be marked as NFC.

It would be interesting however, how often the answers diverge (with respect the how the result is used in GVN). For example, it would be interesting to know how often PRE triggers in GVN on some large programs (e.g. MultiSource/SPEC/LLVM bootstrap) and how many differences codegen differences there are between the old and new implementation. Hopefully that would be a very small number, which might lead to a test case for the new behavior.

Let's see if i can catch such a case..

[lebedev.ri]

In D84181#2168983, @lebedev.ri wrote:

In D84181#2168819, @fhahn wrote:

This overall makes sense I think.

In D84181#2168702, @lebedev.ri wrote:

In D84181#2168668, @mkazantsev wrote:>

I'd suggest the following reliable way to make sure it is NFC:

• Instead of changing logic of IsValueFullyAvailableInBlock, introduce a new version of it and use it.
• In debug mode, also call the old one and assert that the results are the same.
• Then, after it has been in for a long enough while and we are certain those algorithms do the same thing, remove the old one.

WDYT?

I'm afraid it's not that easy to do.

1. We'd need to workaround the situation where the old code gave up due to the gvn-max-recurse-depth recursion limit

I think we also need some kind of limit on the worklist size for the iterative algorithm. Without it we might traverse the whole function in some cases, which could lead to huge compile-times in some degenerate cases I think.

Okay, added one. Right now it's based on the number of times we find a previously unknown block,
mark it as speculatively available, and recurse into it. I think this is the correct way,
i wouldn't think we should just count every block queried, even if we'd found an entry in map?

I don't have SPEC, and didn't try it on whole LLVM, but on vanilla test-suite + RawSpeed + darktable,
said IsValueFullyAvailableInBlockNumSpeculationsMax stat is at max 300, so i've picked a limit of 600.

2. We'll need to duplicate FullyAvailableBlocks so we pass the identical one into both the old version and the new one. Note that we can't equality-compare them afterwards, because the new code, unlike the old one, in backpropagation, doesn't insert new nodes
3. The new code doesn't (erroneously) mark previously available successor nodes of an unavailable node unavailable. This technically i guess makes it a non-NFC patch,

Yes I think this shouldn't be marked as NFC.

It would be interesting however, how often the answers diverge (with respect the how the result is used in GVN). For example, it would be interesting to know how often PRE triggers in GVN on some large programs (e.g. MultiSource/SPEC/LLVM bootstrap) and how many differences codegen differences there are between the old and new implementation. Hopefully that would be a very small number, which might lead to a test case for the new behavior.

Let's see if i can catch such a case..

Done. It's rather horrible, but better than nothing i guess.

[fhahn]

llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll

3–4

those should not be needed.

3–4

Not used currently? I think the test below would benefit from having some actual users of %i & i7 that cannot be folded away.

76–78

nit: unnecessary attribute/dso_local. Same for _Z2axv

[lebedev.ri]

@fhahn thanks for taking a look!
Indeed, the test is bad.

llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll

3–4

It would benefit indeed, but that breaks the test :/
It's overreduced, but i'm not sure what extra interestingness tests i should have used.

[fhahn]

In D84181#2171662, @lebedev.ri wrote:

@fhahn thanks for taking a look!
Indeed, the test is bad.

Perhaps the problem was a missing read none on the use calls?

E.g. something like the following seems to work as expected. Might still be possible to remove some parts of the cfg.

define i32 @loadpre_opportunity(i32** %arg, i1 %arg1, i1 %arg2, i1 %arg3) {
bb:
  %i = load i32*, i32** %arg, align 8
  %i4 = getelementptr inbounds i32, i32* %i, i64 0
  br label %bb5

bb5:
  %v.1 = call i32 @use(i32* %i4)
  br label %bb9

bb6:
  %i7 = load i32*, i32** %arg, align 8
  %i8 = getelementptr inbounds i32, i32* %i7, i64 0
  %v.2 = call i32 @use(i32* %i8)
  br label %bb9

bb9:
  %p = phi i32 [ %v.1, %bb5 ], [ %v.2, %bb6]
  br i1 %arg1, label %bb6, label %bb10

bb10:
  call void @somecall()
  br i1 %arg2, label %bb12, label %bb15

bb12:
  br label %bb13

bb13:
  br i1 %arg3, label %bb14, label %bb13

bb14:
  br label %bb15

bb15:
  %c = call i1 @cond()
  br i1 %c, label %bb6, label %exit

exit:
  ret i32 %p
}

declare void @somecall()
declare i32 @use(i32*) readnone
declare i1 @cond() readnone

[lebedev.ri]

@fhahn thanks! that is indeed better.

[fhahn]

Thanks for the test case! I think this makes sense and is in the spirit of the original implementation, with some improvements. Some more comments, mostly related to wording inline.

llvm/lib/Transforms/Scalar/GVN.cpp

102

For consistency, I would suggest updating the wording to use a similar style to above, e.g. Number of blocks speculated as available in IsVal... Same for the second stat.

123

Is the default not 600?

720

nit: use try_emplace to skip std::make_pair? (if that compiles)

762

nit: maybe adjust with something like as fixpoint yet (the Unavailable and Available states are fixpoints) to make clear what we mean with fixpoints.

779

As mentioned earlier, it seems odd to me to call propagating to successors as 'back-propagating'. I guess it makes sense if you think about it as back-propagating to the starting node. Might be good to clarify the comment. Might just say Queue successors for further processing.

llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll

2

also add a line with the limit set so we don't perform the optimization, to check that the limit works?

[lebedev.ri]

Thank you for taking a look!

In D84181#2175234, @fhahn wrote:

Thanks for the test case! I think this makes sense and is in the spirit of the original implementation, with some improvements. Some more comments, mostly related to wording inline.

Nits addressed.

[fhahn]

LGTM, thanks. Might be good to wait a day with committing, in case there are any additional concerns.

llvm/lib/Transforms/Scalar/GVN.cpp

764

nit: add period at end of sentence

[lebedev.ri]

In D84181#2175360, @fhahn wrote:

LGTM, thanks. Might be good to wait a day with committing, in case there are any additional concerns.

Thank you for the review!
I'll wait a bit.

llvm/lib/Transforms/Scalar/GVN.cpp

 STATISTIC(NumGVNInstr,  "Number of instructions deleted");
 STATISTIC(NumGVNLoad,   "Number of loads deleted");
 STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
 STATISTIC(NumGVNBlocks, "Number of blocks merged");
 STATISTIC(NumGVNSimpl,  "Number of instructions simplified");
 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
 STATISTIC(NumPRELoad,   "Number of loads PRE'd");
 
+STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
+          "How many blocks have we speculated as avaliable in "
+          "IsValueFullyAvailableInBlock(), max?");
+STATISTIC(MaxBBSpeculationCutoffReachedTimes,
+          "How many did we reach a gvn-max-block-speculations cut-off "
+          "preventing further exploration?");
+
 static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);
 static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true));
 static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",
                                             cl::init(true));
 static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));
 
-// Maximum allowed recursion depth.
-static cl::opt<uint32_t>
-MaxRecurseDepth("gvn-max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore,
-                cl::desc("Max recurse depth in GVN (default = 1000)"));
-
 static cl::opt<uint32_t> MaxNumDeps(
     "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore,
     cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));
 
+// This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
+static cl::opt<uint32_t> MaxBBSpeculations(
+    "gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore,
+    cl::desc("Max number of blocks we're willing to speculate on (and recurse "
+             "into) when deducing if a value is fully avaliable or not in GVN "
+             "(default = unlimited)"));
+
 struct llvm::GVN::Expression {
   uint32_t opcode;
   bool commutative = false;
   Type *type = nullptr;
   SmallVector<uint32_t, 4> varargs;
 
   Expression(uint32_t o = ~2U) : opcode(o) {}
 
for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
       I->second->dump();
   }
   errs() << "}\n";
 }
 #endif
 
 enum class AvaliabilityState : char {
   /// We know the block *is not* fully available. This is a fixpoint.
-  Unavaliable = 0,
+  Unavailable = 0,
   /// We know the block *is* fully available. This is a fixpoint.
-  Avaliable = 1,
+  Available = 1,
   /// We do not know whether the block is fully available or not,
   /// but we are currently speculating that it will be.
-  SpeculativelyAvaliable = 2,
-  /// We are speculating for this block and have used that
-  /// to speculate for other blocks.
-  SpeculativelyAvaliableAndUsedForSpeculation = 3,
+  /// If it would have turned out that the block was, in fact, not fully
+  /// available, this would have been cleaned up into an Unavailable.
+  SpeculativelyAvailable = 2,
 };
 
 /// Return true if we can prove that the value
 /// we're analyzing is fully available in the specified block.  As we go, keep
 /// track of which blocks we know are fully alive in FullyAvailableBlocks.  This
 /// map is actually a tri-state map with the following values:
 ///   0) we know the block *is not* fully available.
 ///   1) we know the block *is* fully available.
 ///   2) we do not know whether the block is fully available or not, but we are
 ///      currently speculating that it will be.
-///   3) we are speculating for this block and have used that to speculate for
-///      other blocks.
 static bool IsValueFullyAvailableInBlock(
     BasicBlock *BB,
-    DenseMap<BasicBlock *, AvaliabilityState> &FullyAvailableBlocks,
-    uint32_t RecurseDepth) {
-  if (RecurseDepth > MaxRecurseDepth)
-    return false;
+    DenseMap<BasicBlock *, AvaliabilityState> &FullyAvailableBlocks) {
+  SmallVector<BasicBlock *, 32> Worklist;
+  Optional<BasicBlock *> UnavailableBB;
+
+  // The number of times we didn't find an entry for a block in a map and
+  // optimistically inserted an entry marking block as speculatively avaliable.
+  unsigned NumNewNewSpeculativelyAvailableBBs = 0;
+
+#ifndef NDEBUG
+  SmallSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;
+  SmallVector<BasicBlock *, 32> AvailableBBs;
+#endif
 
-  // Optimistically assume that the block is speculatively available and check
+  Worklist.emplace_back(BB);
+  while (!Worklist.empty()) {
+    BasicBlock *CurrBB = Worklist.pop_back_val(); // LIFO - depth-first!
+    // Optimistically assume that the block is Speculatively Available and check
     // to see if we already know about this block in one lookup.
     std::pair<DenseMap<BasicBlock *, AvaliabilityState>::iterator, bool> IV =
         FullyAvailableBlocks.insert(
-          std::make_pair(BB, AvaliabilityState::SpeculativelyAvaliable));
+            std::make_pair(CurrBB, AvaliabilityState::SpeculativelyAvailable));
+    AvaliabilityState &State = IV.first->second;
 
-  // If the entry already existed for this block, return the precomputed value.
+    // Did the entry already exist for this block?
     if (!IV.second) {
-    // If this is a speculative "available" value, mark it as being used for
-    // speculation of other blocks.
-    if (IV.first->second == AvaliabilityState::SpeculativelyAvaliable)
-      IV.first->second =
-          AvaliabilityState::SpeculativelyAvaliableAndUsedForSpeculation;
-    return IV.first->second != AvaliabilityState::Unavaliable;
+      if (State == AvaliabilityState::Unavailable) {
+        UnavailableBB = CurrBB;
+        break; // Backpropagate unavaliability info.
       }
 
-  // Otherwise, see if it is fully available in all predecessors.
-  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
-
-  // If this block has no predecessors, it isn't live-in here.
-  if (PI == PE)
-    goto SpeculationFailure;
-
-  for (; PI != PE; ++PI)
-    // If the value isn't fully available in one of our predecessors, then it
-    // isn't fully available in this block either.  Undo our previous
-    // optimistic assumption and bail out.
-    if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks,RecurseDepth+1))
-      goto SpeculationFailure;
+#ifndef NDEBUG
+      AvailableBBs.emplace_back(CurrBB);
+#endif
+      continue; // Don't recurse further, but continue processing worklist.
+    }
 
-  return true;
+    // No entry found for block.
+    ++NumNewNewSpeculativelyAvailableBBs;
+    bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;
 
-// If we get here, we found out that this is not, after
-// all, a fully-available block.  We have a problem if we speculated on this and
-// used the speculation to mark other blocks as available.
-SpeculationFailure:
-  AvaliabilityState &BBVal = FullyAvailableBlocks[BB];
+    // If we have exhausted our budget, mark this block as unavailable.
+    // Also, if this block has no predecessors, the value isn't live-in here.
+    if (OutOfBudget || pred_empty(CurrBB)) {
+      MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
+      State = AvaliabilityState::Unavailable;
+      UnavailableBB = CurrBB;
+      break; // Backpropagate unavaliability info.
+    }
 
-  // If we didn't speculate on this, just return with it set to unavaliable.
-  if (BBVal == AvaliabilityState::SpeculativelyAvaliable) {
-    BBVal = AvaliabilityState::Unavaliable;
-    return false;
+    // Tentatively consider this block as speculatively available.
+#ifndef NDEBUG
+    NewSpeculativelyAvailableBBs.insert(CurrBB);
+#endif
+    // And further recurse into block's predecessors, in depth-first order!
+    Worklist.append(pred_begin(CurrBB), pred_end(CurrBB));
   }
 
-  // If we did speculate on this value, we could have blocks set to
-  // speculatively avaliable that are incorrect. Walk the (transitive)
-  // successors of this block and mark them as unavaliable instead.
-  SmallVector<BasicBlock*, 32> BBWorklist;
-  BBWorklist.push_back(BB);
+#if LLVM_ENABLE_STATS
+  IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
+      NumNewNewSpeculativelyAvailableBBs);
+#endif
 
-  do {
-    BasicBlock *Entry = BBWorklist.pop_back_val();
-    // Note that this sets blocks to unavailable if they happen to not
-    // already be in FullyAvailableBlocks.  This is safe.
-    AvaliabilityState &EntryVal = FullyAvailableBlocks[Entry];
-    if (EntryVal == AvaliabilityState::Unavaliable)
-      continue; // Already unavailable.
+  // If the block isn't marked as fixpoint yet, do so and enqueue successors
+  auto MarkAsFixpointAndEnqueueSuccessors =
+      [&](BasicBlock *BB, AvaliabilityState FixpointState) {
+        auto It = FullyAvailableBlocks.find(BB);
+        if (It == FullyAvailableBlocks.end())
+          return; // Never queried this block, leave as-is.
+        switch (AvaliabilityState &State = It->second) {
+        case AvaliabilityState::Unavailable:
+        case AvaliabilityState::Available:
+          return; // Don't backpropagate further, continue processing worklist.
+        case AvaliabilityState::SpeculativelyAvailable: // Fix it!
+          State = FixpointState;
+#ifndef NDEBUG
+          assert(NewSpeculativelyAvailableBBs.erase(BB) &&
+                 "Found a speculatively available successor leftover?");
+#endif
+          // *DO* backpropagate further, continue processing worklist.
+          Worklist.append(succ_begin(BB), succ_end(BB));
+          return;
+        }
+      };
 
-    // Mark as unavailable.
-    EntryVal = AvaliabilityState::Unavaliable;
+  if (UnavailableBB) {
+    // Okay, we have encountered an unavailable block.
+    // Mark speculatively available blocks reachable from UnavailableBB as
+    // unavailable as well. Paths are terminated when they reach blocks not in
+    // FullyAvailableBlocks or they are not marked as speculatively available.
+    Worklist.clear();
+    Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));
+    while (!Worklist.empty())
+      MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
+                                         AvaliabilityState::Unavailable);
+  }
+
+#ifndef NDEBUG
+  Worklist.clear();
+  for (BasicBlock *AvailableBB : AvailableBBs)
+    Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));
+  while (!Worklist.empty())
+    MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
+                                       AvaliabilityState::Available);
 
-    BBWorklist.append(succ_begin(Entry), succ_end(Entry));
-  } while (!BBWorklist.empty());
+  assert(NewSpeculativelyAvailableBBs.empty() &&
+         "Must have fixed all the new speculatively available blocks.");
+#endif
 
-  return false;
+  return !UnavailableBB;
 }
 
 /// Given a set of loads specified by ValuesPerBlock,
 /// construct SSA form, allowing us to eliminate LI.  This returns the value
 /// that should be used at LI's definition site.
 static Value *ConstructSSAForLoadSet(LoadInst *LI,
                          SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
                                      GVN &gvn) {
bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   assert(TmpBB);
   LoadBB = TmpBB;
 
   // Check to see how many predecessors have the loaded value fully
   // available.
   MapVector<BasicBlock *, Value *> PredLoads;
   DenseMap<BasicBlock *, AvaliabilityState> FullyAvailableBlocks;
   for (const AvailableValueInBlock &AV : ValuesPerBlock)
-    FullyAvailableBlocks[AV.BB] = AvaliabilityState::Avaliable;
+    FullyAvailableBlocks[AV.BB] = AvaliabilityState::Available;
   for (BasicBlock *UnavailableBB : UnavailableBlocks)
-    FullyAvailableBlocks[UnavailableBB] = AvaliabilityState::Unavaliable;
+    FullyAvailableBlocks[UnavailableBB] = AvaliabilityState::Unavailable;
 
   SmallVector<BasicBlock *, 4> CriticalEdgePred;
   for (BasicBlock *Pred : predecessors(LoadBB)) {
     // If any predecessor block is an EH pad that does not allow non-PHI
     // instructions before the terminator, we can't PRE the load.
     if (Pred->getTerminator()->isEHPad()) {
       LLVM_DEBUG(
           dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
                  << Pred->getName() << "': " << *LI << '\n');
       return false;
     }
 
-    if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks, 0)) {
+    if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) {
       continue;
     }
 
     if (Pred->getTerminator()->getNumSuccessors() != 1) {
       if (isa<IndirectBrInst>(Pred->getTerminator())) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
                    << Pred->getName() << "': " << *LI << '\n');

llvm/test/Transforms/GVN/loadpre-missed-opportunity.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -gvn -S | FileCheck %s
 
 define i32 @loadpre_opportunity(i32** %arg, i1 %arg1, i1 %arg2, i1 %arg3) {
 ; CHECK-LABEL: @loadpre_opportunity(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I:%.*]] = load i32*, i32** [[ARG:%.*]], align 8
 ; CHECK-NEXT:    [[I6:%.*]] = call i32 @use(i32* [[I]])
 ; CHECK-NEXT:    br label [[BB11:%.*]]
 ; CHECK:       bb7:
-; CHECK-NEXT:    [[I8:%.*]] = load i32*, i32** [[ARG]], align 8
+; CHECK-NEXT:    [[I8:%.*]] = phi i32* [ [[I8_PRE:%.*]], [[BB17_BB7_CRIT_EDGE:%.*]] ], [ [[I81:%.*]], [[BB11]] ]
 ; CHECK-NEXT:    [[I10:%.*]] = call i32 @use(i32* [[I8]])
 ; CHECK-NEXT:    br label [[BB11]]
 ; CHECK:       bb11:
-; CHECK-NEXT:    [[I12:%.*]] = phi i32 [ [[I6]], [[BB:%.*]] ], [ [[I10]], [[BB7:%.*]] ]
+; CHECK-NEXT:    [[I81]] = phi i32* [ [[I]], [[BB:%.*]] ], [ [[I8]], [[BB7:%.*]] ]
+; CHECK-NEXT:    [[I12:%.*]] = phi i32 [ [[I6]], [[BB]] ], [ [[I10]], [[BB7]] ]
 ; CHECK-NEXT:    br i1 [[ARG1:%.*]], label [[BB7]], label [[BB13:%.*]]
 ; CHECK:       bb13:
 ; CHECK-NEXT:    call void @somecall()
 ; CHECK-NEXT:    br i1 [[ARG2:%.*]], label [[BB14:%.*]], label [[BB17:%.*]]
 ; CHECK:       bb14:
 ; CHECK-NEXT:    br label [[BB15:%.*]]
 ; CHECK:       bb15:
 ; CHECK-NEXT:    br i1 [[ARG3:%.*]], label [[BB16:%.*]], label [[BB15]]
 ; CHECK:       bb16:
 ; CHECK-NEXT:    br label [[BB17]]
 ; CHECK:       bb17:
 ; CHECK-NEXT:    [[I18:%.*]] = call i1 @cond()
-; CHECK-NEXT:    br i1 [[I18]], label [[BB7]], label [[BB19:%.*]]
+; CHECK-NEXT:    br i1 [[I18]], label [[BB17_BB7_CRIT_EDGE]], label [[BB19:%.*]]
+; CHECK:       bb17.bb7_crit_edge:
+; CHECK-NEXT:    [[I8_PRE]] = load i32*, i32** [[ARG]], align 8
+; CHECK-NEXT:    br label [[BB7]]
 ; CHECK:       bb19:
 ; CHECK-NEXT:    ret i32 [[I12]]
 ;
 bb:
   %i = load i32*, i32** %arg, align 8
   %i4 = getelementptr inbounds i32, i32* %i, i64 0
   br label %bb5
 

 bb17:
   %i18 = call i1 @cond()
   br i1 %i18, label %bb7, label %bb19
 
 bb19:
   ret i32 %i12
 }
 
 declare void @somecall()
 declare i32 @use(i32*) readnone
 declare i1 @cond() readnone