[Dominators] Add the DomTreeUpdater class

[NutshellySima]

Summary

This patch is the first in a series of patches related to the RFC - A new dominator tree updater for LLVM.

This patch introduces the DomTreeUpdater class, which provides a cleaner API to perform updates on available dominator trees (none, only DomTree, only PostDomTree, both) using different update strategies (eagerly or lazily) to simplify the updating process.

—Prior to the patch—

1. The current API is quite fragmented and different functions using these APIs need to write redundant code to manually deal with various kinds of update strategies which makes code hard to maintain.
   • Directly calling update functions of DominatorTree updates the data structure eagerly while DeferredDominance does updates lazily.
   • DeferredDominance class cannot be used when a PostDominatorTree also needs to be updated.
   • Functions receiving DT/DDT need to branch a lot which is currently necessary.
   • Functions using both DomTree and PostDomTree need to call the update function separately on both trees.
   • People need to construct an additional DeferredDominance class to use functions only receiving DDT.
2. We need to manually decide whether to erase a BasicBlock from the dominator tree when one is removed from the CFG.
3. When using lazy updating methods, the BasicBlock waiting to delete will be deleted in an unforeseeable time after being removed from the Function so the user cannot do further actions on it.
4. When we have both trees (DomTree and PostDomTree), we can try using the update information of one of them to prune updates of another to accelerate the updating process.

—After the patch—

1. The abilities of the DeferredDominance are subsumed by the new updater class. And the API user can use an enum to specify which update strategy to use.
2. The new updater class can update all the data structures it holds when the user calls the update function.
3. The new updater class will first check whether these BasicBlocks still act as a node in the holding trees then call delete to prevent further manual checks.
4. The updater class has a callbackDeleteBB function which accepts a callable to let users do additional operations on the BasicBlock before deletion.

[vsk]

unittests/IR/DomTreeUpdaterTest.cpp

608 ↗

(On Diff #152110)

Just a minor stylistic point, but it can be neater to use the extended literal syntax for IR snippets, like this:

foo = R"(
define i32 @f(i32 %i, i32 *%p) {
bb0:
    store i32 %i, i32 *%p
...
)";

[kuhar]

Thanks for the hard work!

I left you mostly stylistic comments. Please take a look at other files in this directory and the surrounding ones and see how people write comments and lay out code. This can vary a lot from a file to file, but it seems to me that the style of this patch is somewhat different to existing ones in Analysis and Transforms.
Please let me know if I'm missing some newest coding style and documentation recommendations, I might be not entirely up-to-date with it.

This patch is pretty big and it will probably take a couple of iterations before we can get it landed.

include/llvm/IR/DomTreeUpdater.h

28 ↗

(On Diff #152110)

If you want to visually split the class into a few fragments, maybe it would be better to use some character (like ===== or -----) to make it more apparent? You should be able to grep for it to see what other people use.

30 ↗

(On Diff #152110)

What sort of code patterns are you trying to prevent here? I thought it only makes sense to use explicit with constructors taking 1 argument.

37 ↗

(On Diff #152110)

I think it would be more readable if there was one empty line after a member declaration and a comment below.
(This applies to the rest of the class as well.)

38 ↗

(On Diff #152110)

This seems to imply that calling this function makes your code run faster :P.
It think it would be enough to explain that you can have eager and lazy updates and what each implies and when to use it.

42 ↗

(On Diff #152110)

This function is trivially self-explanatory, I'm not sure if we want to have a full documentation, including returned values and arguments, for simple getters like this

46 ↗

(On Diff #152110)

Same as above. It think it would be more valuable to explain thinks you cannot guess just by eyeballing function signatures.

50 ↗

(On Diff #152110)

I think it would be better to stick to the same naming scheme across the file:
here it's "Pend", below is "Pending".

57 ↗

(On Diff #152110)

Maybe: isBBPendingDeletion or merge it with the one above?
Not sure about this one, but it's weird to have 2 functions with almost exactly the same name.

60 ↗

(On Diff #152110)

Can you clarify what happens in eager vs. lazy scenario?

100 ↗

(On Diff #152110)

nit: dangling ,

108 ↗

(On Diff #152110)

What scenario?

110 ↗

(On Diff #152110)

Should or must?

110 ↗

(On Diff #152110)

How about something like this: // Recalculates held DomTree. Caller must ensure there is a DomTree to update.

116 ↗

(On Diff #152110)

Similar to above.
One more thing: why do we expose these function? Is it possible that someone wants to recalculate just one tree and leave the other one intact? If this is the case, can you explain when it would make sense?

119 ↗

(On Diff #152110)

Why doesn't it recalculate whatever trees you have?

158 ↗

(On Diff #152110)

I think S should be capitalized. Or maybe you could call it Strategy? Not sure here.

170 ↗

(On Diff #152110)

maybe: \returns true is at least one BB was deleted?

179 ↗

(On Diff #152110)

I don't think this comments gives any extra information on top of the function signature. Same for the two functions below.

183 ↗

(On Diff #152110)

Can you explain what you mean by unnecessary?

190 ↗

(On Diff #152110)

I like this comment! It's fairly brief yet explain what you consider to be valid and why you need this function.

lib/IR/DomTreeUpdater.cpp

25 ↗

(On Diff #152110)

When you are using auto with pointers, auto* is preferred.

29 ↗

(On Diff #152110)

This looks a bit weird with the comment below with no empty space. I would move it above the if.

38 ↗

(On Diff #152110)

Invalid sounds like this is some error, do you mean that the updates is a NOP?

76 ↗

(On Diff #152110)

I would put an extra line above.

92 ↗

(On Diff #152110)

Same as above.

120 ↗

(On Diff #152110)

assert(DT && PDT)

127 ↗

(On Diff #152110)

I'd put an empty line here

136 ↗

(On Diff #152110)

Also here

142 ↗

(On Diff #152110)

Empty line as well

142 ↗

(On Diff #152110)

You don't need to repeat the comments, this belongs to the declaration in the header.

145 ↗

(On Diff #152110)

assert(DT && ...)

166 ↗

(On Diff #152110)

Empty line please

168 ↗

(On Diff #152110)

This should be in the header.

176 ↗

(On Diff #152110)

Empty line please

199 ↗

(On Diff #152110)

if (!DT)

205 ↗

(On Diff #152110)

if (!PDT)

247 ↗

(On Diff #152110)

if (DT->getNode(DelBB))

250 ↗

(On Diff #152110)

Same as above

319 ↗

(On Diff #152110)

I'd put an empty line here too

334 ↗

(On Diff #152110)

Same

373 ↗

(On Diff #152110)

Empty line above please

379 ↗

(On Diff #152110)

empty line here

412 ↗

(On Diff #152110)

Extra line please

unittests/IR/DomTreeUpdaterTest.cpp

34 ↗

(On Diff #152110)

Consider using c++11 raw string literals here

54 ↗

(On Diff #152110)

Can it to ever fail here?

101 ↗

(On Diff #152110)

Is it used anywhere?

[NutshellySima]

1. Address comments.
2. Amend docs and comments in code.

[NutshellySima]

include/llvm/IR/DomTreeUpdater.h

116 ↗

(On Diff #152110)

As mentioned in the DeferredDomiance document, the DT traversal algorithm needs all BasicBlocks awaiting deletion be deleted before it determines the actual DT. So there should be such recalculate* functions to determine whether to leave the other tree intact (check whether there are BasicBlocks awaiting deletion).

[NutshellySima]

Further address comments and fix some nits.

[brzycki]

Thank you for working on this @NutshellySima , a unified dominator interface will be most welcome in LLVM. Please see my inline comments.

include/llvm/IR/DomTreeUpdater.h

70 ↗

(On Diff #152324)

The comment here doesn't make grammatical sense. Did you mean "It is required for the state of the LLVM IR to be updated *before* applying updates to the DominatorTree. This routine inspects the current IR edge relationships to determine if an update needs to be queued."

82 ↗

(On Diff #152324)

I find the wording of this comment to be a bit confusing. I understand it's difficult to describe all the state you're trying to convey but maybe it's better to rewrite a bit. Here's more along the lines of what I was thinking:

/// Notify all holding trees on an edge insertion.
/// The internal Strategy of the DTU instance alters how the insertion even is handled.
///The Eager Strategy applies the update immediately while the Lazy Strategy will
/// queue them until a flush() event. If the current IR does not contain the edge
/// inserted the update will be silently discarded unless the user sets
/// ForceRemoveInvalidUpdate to true. It is recommended to only use this method
/// when you have exactly one insertion (and no deleteions) needed to the DTU.
/// It is recommended to use applyUpdates() in all other cases.

87 ↗

(On Diff #152324)

Comments similar to insertEdge()...

142 ↗

(On Diff #152324)

I'd actually prefer if flushDomTree() and flushPostDomTree(), and flushAll() were private members. Users shouldn't have to think about flushing state. Instead, have all delections and flushes happen when they request access to a DT or PDT reference such as:

auto DTU = DomTreeUpdater(DT, PDT, Lazy);
...
DTU->applyUpdates({Foo, Bar, Insert});
DTU->applyUpdates({Bar, Baz, Delete});
...
auto DT = DTU->getDT(); // flush() and delete BBs happen here automatically.

182 ↗

(On Diff #152324)

It'd be good to mention why this is necessary in the comment. When immediately deleting a BB, the call removeFromParent() removes all its instructions as well. However, in the deferred case the block isn't really deleted and is still a child of F. This causes problems for algorithms that do for (auto BB: F) and expect terminator instructions, instruction Uses, and REPL to all be consistent for every block inside a function. Without these fixups all sorts of routines will start asserting() complaining that the state of the IR is inconsistent.

116 ↗

(On Diff #152110)

You might want to add a comment explaining why deleted BBs need to be processed first:

/// If there are BasicBlocks pending deletion they must be removed first.
/// This is necessary because the pending BBs still have their Parent set to F
/// which is traversed by the tree's recalculate() algorithm and will assert()
/// if it detects a block in F that is not dominated by entry.

119 ↗

(On Diff #152110)

I strongly dislike the idea of recalculation of DT or PDT by the caller. If the user has instantiated a DTU with DT and PDT I'd expect the class to quietly operate (and update) both. I cannot think of a situation where the caller would want DT updated but PDT not updated.

170 ↗

(On Diff #152110)

+1

[kuhar]

include/llvm/IR/DomTreeUpdater.h

164 ↗

(On Diff #152324)

Extra line, please

170 ↗

(On Diff #152324)

Extra line, please

177 ↗

(On Diff #152324)

Do you expect to have 8 callbacks here in average cases? Once you switch all users of DDT, how many callbacks registered will there be?

205 ↗

(On Diff #152324)

nit: s/Tree/Trees

lib/IR/DomTreeUpdater.cpp

28 ↗

(On Diff #152324)

Extra line, please

31 ↗

(On Diff #152324)

Extra line, please

36 ↗

(On Diff #152324)

Why not llvm::find?

44 ↗

(On Diff #152324)

Extra line, please

47 ↗

(On Diff #152324)

Extra line, please

63 ↗

(On Diff #152324)

E should be const

65 ↗

(On Diff #152324)

Extra line, please

68 ↗

(On Diff #152324)

Extra line, please

74 ↗

(On Diff #152324)

Extra line, please

106 ↗

(On Diff #152324)

An assert for begin + index < end would be welcome

116 ↗

(On Diff #152324)

I'd move such one-liners to the header

120 ↗

(On Diff #152324)

Extra line, please

175 ↗

(On Diff #152324)

Extra line, please

202 ↗

(On Diff #152324)

Extra line, please

272 ↗

(On Diff #152324)

Extra line, please

282 ↗

(On Diff #152324)

Extra line, please

310 ↗

(On Diff #152324)

Consider using llvm::find

388 ↗

(On Diff #152324)

Extra line, please

456 ↗

(On Diff #152324)

Extra line, please

319 ↗

(On Diff #152110)

I think you missed this.
Same applies to the ifs below

334 ↗

(On Diff #152110)

Missed?

[dmgreen]

Hello. Glad to see this is moving forward! This looks like it's going to be very useful.

Couple of quick, high level questions, in terms of how we expect the interface to be used. If there is a function that currently looks like this:

bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
                               LoopInfo *LI = nullptr,
                               MemoryDependenceResults *MemDep = nullptr,
                               DeferredDominance *DDT = nullptr);

.. and we'd like to make it optionally preserve PDT's, do you think it's best to have both an (optional) DT and a DTU? Just the DTU and get DT through it? Would the DTU remain optional or become required? (though possibly empty)

What about something like

BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                                   const char *Suffix,
                                   DominatorTree *DT = nullptr,
                                   LoopInfo *LI = nullptr,
                                   bool PreserveLCSSA = false);

Which I think calls DT->splitBlock() internally. Do you think updating this just to take a DTU instead of a DT, and updating all the call sites is the best way to go?

include/llvm/IR/DomTreeUpdater.h

138 ↗

(On Diff #152324)

Nit: Flush

142 ↗

(On Diff #152324)

What do you think of having DTU automatically flush remaining updates in it's deconstructor. So that things like these (to steal your examples) work:

void F(..)
{
  auto DTU = DomTreeUpdater(DT, PDT, Lazy);
  ...
  DTU->applyUpdates({Foo, Bar, Insert});
  DTU->applyUpdates({Bar, Baz, Delete});
}

or

{
  auto DTU = DomTreeUpdater(DT, PDT, Lazy);
  SomeFunctionThatUpdatesTrees(..., DTU, ...);
}

201 ↗

(On Diff #152324)

Nit: Flush

lib/IR/DomTreeUpdater.cpp

64 ↗

(On Diff #152324)

asserts tend to give a filename and linenumber by default, so maybe change this to something describing the error.

[kuhar]

In D48383#1140675, @dmgreen wrote:

Couple of quick, high level questions, in terms of how we expect the interface to be used. If there is a function that currently looks like this:

bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
                               LoopInfo *LI = nullptr,
                               MemoryDependenceResults *MemDep = nullptr,
                               DeferredDominance *DDT = nullptr);

.. and we'd like to make it optionally preserve PDT's, do you think it's best to have both an (optional) DT and a DTU? Just the DTU and get DT through it? Would the DTU remain optional or become required? (though possibly empty)

The idea is to have it only take DTU (by reference (non-optional)), such that MergeBlockIntoPredecessor preserves whatever you pass it (possibly no tree).

What about something like

BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                                   const char *Suffix,
                                   DominatorTree *DT = nullptr,
                                   LoopInfo *LI = nullptr,
                                   bool PreserveLCSSA = false);

Which I think calls DT->splitBlock() internally. Do you think updating this just to take a DTU instead of a DT, and updating all the call sites is the best way to go?

In general. the preferred way would be take DTU as an argument and try to use the incremental api.
There are some cases where it seems like you can do some smarter things with more low-level operations, e.g. changing the function entry block, splitting predecessor, but from what I know there are only a couple of them. In such cases we can expose them as dedicated functions in DTU.

[NutshellySima]

lib/IR/DomTreeUpdater.cpp

319 ↗

(On Diff #152110)

No. Phabricator does not track the correct line between current and the last patch.

[NutshellySima]

1. Address comments.
2. Remove recalculateDomTree() and recalculatePostDomTree().
3. Remove the "removeInvalidUpdate" parameter of insertEdge() and deleteEdge() and update docs to reflect this change.
4. Rename recalculateAll() to recalculate() (It can recalculate all holding trees).
5. Rename flushDomTree()/flushPostDomTree() to getDomTree()/getPostDomTree() because the functions indeed return the updated trees.

[NutshellySima]

include/llvm/IR/DomTreeUpdater.h

142 ↗

(On Diff #152324)

I think flushAll() can't be private members:

auto DTU = DomTreeUpdater(DT, Lazy);
... // Make BB0 forward/backward-unreachable.
DTU->applyUpdates(SomeUpdates);
auto DT = DTU->getDT();
...
// Now delete BB0
DTU->deleteBB(BB0);
// Now there is no pendingDTUpdates and can only use flushAll() to get BB0 removed from its parent and deleted.

[NutshellySima]

include/llvm/IR/DomTreeUpdater.h

142 ↗

(On Diff #152324)

More information on the above comments:
I remember some code will break if the internal logic of deleteBB calls removeFromParent() and deletes BB immediately when there isn't any pending DT/PDT updates.
So, I think it is needed to leave a flushAll() function to help user flush BB awaiting deletion.

[brzycki]

In D48383#1140730, @kuhar wrote:

In D48383#1140675, @dmgreen wrote:

Couple of quick, high level questions, in terms of how we expect the interface to be used. If there is a function that currently looks like this:

bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
                               LoopInfo *LI = nullptr,
                               MemoryDependenceResults *MemDep = nullptr,
                               DeferredDominance *DDT = nullptr);

.. and we'd like to make it optionally preserve PDT's, do you think it's best to have both an (optional) DT and a DTU? Just the DTU and get DT through it? Would the DTU remain optional or become required? (though possibly empty)

The idea is to have it only take DTU (by reference (non-optional)), such that MergeBlockIntoPredecessor preserves whatever you pass it (possibly no tree).

+1. I'd like to see most, if not all, of the updates to PDT/DT to be done through the DTU interface applyUpdate() call. It simplifies method signatures and provides a consistent interface to analysis and updates.

What about something like

BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                                   const char *Suffix,
                                   DominatorTree *DT = nullptr,
                                   LoopInfo *LI = nullptr,
                                   bool PreserveLCSSA = false);

Which I think calls DT->splitBlock() internally. Do you think updating this just to take a DTU instead of a DT, and updating all the call sites is the best way to go?

In general. the preferred way would be take DTU as an argument and try to use the incremental api.
There are some cases where it seems like you can do some smarter things with more low-level operations, e.g. changing the function entry block, splitting predecessor, but from what I know there are only a couple of them. In such cases we can expose them as dedicated functions in DTU.

In this case someone will have to do the flush() call during the Lazy Strategy. Either the call of SplitBlockPredecessors() will have to do:

auto DT = DTU->getDT(); // flush, deleteBBs called
auto NewBB = SplitBlockPredecessors(BB, Preds, Suffix, DT);

or

auto NewBB = SplitBlockPredecessors(BB, Preds, Suffix, DTU);
...
// Inside SplitBlockPredecessors()
auto DT = DTU->getDT();
DT->splitblock();
...

The latter example has three benefits in my opinion:

1. the details of DT/DTU are hidden from the caller
2. SplitBlockPredecessors now preserves (and u[dates) PDT for free
3. There might also be a way to update the DT/PDT without the flush() call which can be investigated without altering all the callers of SplitBlockPredecessors()

include/llvm/IR/DomTreeUpdater.h

142 ↗

(On Diff #152324)

That would be a good idea to force flushes (and deleteBB) on deconstruction iff any are pending.

142 ↗

(On Diff #152324)

You make a good point here, I think the big flush needs to be public. Can't it just be called flush() or sync() instead of flushAll()? I'm still hopeful the need for this call can be minimized by the DT/PDT getter method implicitly flushing and more call-sites only use DTU.

[NutshellySima]

include/llvm/IR/DomTreeUpdater.h

182 ↗

(On Diff #152324)

It seems that calling removeFromParent() does not remove all its instructions.

116 ↗

(On Diff #152110)

It seems that DT.recalculate() won't assert on this case.

[NutshellySima]

1. Make DomTreeUpdater flush() on deconstruction.
2. Add insertEdgeRelaxed() and deleteEdgeRelaxed() to cover the behavior of the original DeferredDominance's insertEdge()/deleteEdge().
3. Modify unittests to test the 2 new functions.

[brzycki]

Thank you for continuing this work @NutshellySima .

1. Make DomTreeUpdater flush() on deconstruction.

Excellent, this is a nice convenience.

2. Add insertEdgeRelaxed() and deleteEdgeRelaxed() to cover the behavior of the original DeferredDominance's insertEdge()/deleteEdge().

Maybe it'd be better to have a default boolean third variable?
deleteEdge(BasicBlock *From, BasicBlock *To, bool Relaxed = false) { ...

include/llvm/IR/DomTreeUpdater.h

182 ↗

(On Diff #152324)

Correction, I meant llvm::DeleteDeadBlock(). You'll see a similar loop to DDT->deleteBB() which does a RAUW to undef for all instructions and then calls removeFromParent(). The biggest change that deleteBB() does is adds a valid TI: necessary for llvm to keep the block as a child of F().

[kuhar]

In D48383#1145727, @brzycki wrote:

2. Add insertEdgeRelaxed() and deleteEdgeRelaxed() to cover the behavior of the original DeferredDominance's insertEdge()/deleteEdge().

Maybe it'd be better to have a default boolean third variable?
deleteEdge(BasicBlock *From, BasicBlock *To, bool Relaxed = false) { ...

If we agree that it would be better to have well-behaved updates in most of the places in the future, then having distinct names for these two should make it much easier to grep for. Additionally, it seems like it's not always possible to perform them with the eager strategy, is it?

[brzycki]

If we agree that it would be better to have well-behaved updates in most of the places in the future, then having distinct names for these two should make it much easier to grep for. Additionally, it seems like it's not always possible to perform them with the eager strategy, is it?

Good point, I didn't think of the calls being easier to grep. Sounds good to me. And yes, I would prefer all updates to be strict and done after CFG updates, but reality isn't always so forgiving. Having explicit *Relaxed() calls can make them easier to identify and potentially fix as we go.

[NutshellySima]

1. Address comments - Modify document of validateDeleteBB(BasicBlock *DelBB).
2. Fix some typos.
3. Remove an unimplemented function.

[kuhar]

Looks almost ready to me. Found just a couple of nits.

include/llvm/IR/DomTreeUpdater.h

58 ↗

(On Diff #153326)

I'm not sure that holding trees is grammatically correct in this place and all the other ones.
Maybe held trees or just available trees.
Perhaps @brzycki could help here.

130 ↗

(On Diff #153326)

please remove be

157 ↗

(On Diff #153326)

Can you add one extra sentence saying what it actually means to flush?

lib/IR/DomTreeUpdater.cpp

248 ↗

(On Diff #153326)

Can a BB have 0 instructions?

36 ↗

(On Diff #152324)

Missed comment?

[brzycki]

@kuhar and @NutshellySima here are a few more small comments.

include/llvm/IR/DomTreeUpdater.h

58 ↗

(On Diff #153326)

The phrase holding trees doesn't make sense in this context. I didn't mention it before because I'm not an expert on Dominators and wasn't sure if this was a technical phrase. :)

If you need to keep the phrase I'd recommend held trees but even that sounds a bit odd. Something along the lines of valid tree instances or trees contained inside. I tend to think of the DTU object instantiated with one or two tree objects.

In this particular case the english is odd when describing the false case. I'd prefer if the comment said:

/// Returns true if either of DT or PDT is valid and the tree has at
/// least one update pending. If DT or PDT is nullptr it is treated
/// as having no pending updates.

Something like that I think is a bit easier to understand.

60 ↗

(On Diff #152110)

+1. I'd assume for Eager the routine always returns false since queuing isn't allowed. It'd be good to state that explicitly.

lib/IR/DomTreeUpdater.cpp

248 ↗

(On Diff #153326)

Not for long. The only place I've seen BBs with 0 instructions is just before actual deletion. Too many routines expect, at the very least, a valid TI and will cause assert() casting nullptr to I or dereferencing a nullptr instruction instance. As much as anything's a rule in the middle end, I've found that to be pretty consistent.

[NutshellySima]

1. Address comments.
2. Fix build with C++ module.

[kuhar]

lib/IR/DomTreeUpdater.cpp

34 ↗

(On Diff #153521)

Still missed? Can we use llvm::find here?

[NutshellySima]

lib/IR/DomTreeUpdater.cpp

34 ↗

(On Diff #153521)

It was commented when I used std::any_of last time. I then switched to llvm::any_of. I believe llvm::any_of is clearer than llvm::find because after llvm::find returns an iterator, and I need to have it compared with the succ_end to find out the value of this boolean.

[kuhar]

lib/IR/DomTreeUpdater.cpp

34 ↗

(On Diff #153521)

OK

[NutshellySima]

Fix issues when building LLVM with C++ modules (Thanks Richard Smith for the advice).

[kuhar]

Looks good to me now. Thanks for making all the fixes!

[dmgreen]

+1. Nice work guys.

[brzycki]

+1 LGTM. Thank you @NutshellySima for your dedication to getting this patch ready for adoption!

[NutshellySima]

Reopen for a stack-use-after-scope bug in DomTreeUpdater_LazyUpdateBasicOperations_Test.

[NutshellySima]

Use std::function instead of function_ref in callback utils.

llvm/trunk/include/llvm/IR/DomTreeUpdater.h

+//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the DomTreeUpdater class, which provides a uniform way to
+// update dominator tree related data structures.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DOMTREEUPDATER_H
+#define LLVM_DOMTREEUPDATER_H
+
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/GenericDomTree.h"
+#include <functional>
+#include <vector>
+
+namespace llvm {
+class DomTreeUpdater {
+public:
+  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
+
+  explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
+  DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
+      : DT(&DT_), Strategy(Strategy_) {}
+  DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
+      : PDT(&PDT_), Strategy(Strategy_) {}
+  DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
+                 UpdateStrategy Strategy_)
+      : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
+
+  ~DomTreeUpdater() { flush(); }
+
+  /// Returns the UpdateStrategy of the class instance.
+  UpdateStrategy getUpdateStrategy() const { return Strategy; };
+
+  /// Returns true if it holds a DominatorTree.
+  bool hasDomTree() const { return DT != nullptr; }
+
+  /// Returns true if it holds a PostDominatorTree.
+  bool hasPostDomTree() const { return PDT != nullptr; }
+
+  /// Returns true if there is BasicBlock awaiting deletion.
+  /// The deletion will only happen until a flush event and
+  /// all available trees are up-to-date.
+  /// Returns false under Eager UpdateStrategy.
+  bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }
+
+  /// Returns true if DelBB is awaiting deletion.
+  /// Returns false under Eager UpdateStrategy.
+  bool isBBPendingDeletion(BasicBlock *DelBB) const;
+
+  /// Returns true if either of DT or PDT is valid and the tree has at
+  /// least one update pending. If DT or PDT is nullptr it is treated
+  /// as having no pending updates. This function does not check
+  /// whether there is BasicBlock awaiting deletion.
+  /// Returns false under Eager UpdateStrategy.
+  bool hasPendingUpdates() const;
+
+  /// Returns true if there are DominatorTree updates queued.
+  /// Returns false under Eager UpdateStrategy.
+  bool hasPendingDomTreeUpdates() const;
+
+  /// Returns true if there are PostDominatorTree updates queued.
+  /// Returns false under Eager UpdateStrategy.
+  bool hasPendingPostDomTreeUpdates() const;
+
+  /// Apply updates on all available trees. Under Eager UpdateStrategy with
+  /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
+  /// discard duplicated updates and self-dominance updates. The Eager
+  /// Strategy applies the updates immediately while the Lazy Strategy
+  /// queues the updates. It is required for the state of
+  /// the LLVM IR to be updated *before* applying the Updates because the
+  /// internal update routine will analyze the current state of the relationship
+  /// between a pair of (From, To) BasicBlocks to determine whether a single
+  /// update needs to be discarded.
+  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
+                    bool ForceRemoveDuplicates = false);
+
+  /// Notify all available trees on an edge insertion. Under either Strategy,
+  /// self-dominance update will be removed. The Eager Strategy applies
+  /// the update immediately while the Lazy Strategy queues the update.
+  /// It is recommended to only use this method when you have exactly one
+  /// insertion (and no deletions). It is recommended to use applyUpdates() in
+  /// all other cases. This function has to be called *after* making the update
+  /// on the actual CFG. An internal functions checks if the edge exists in the
+  /// CFG in DEBUG mode.
+  void insertEdge(BasicBlock *From, BasicBlock *To);
+
+  /// Notify all available trees on an edge insertion.
+  /// Under either Strategy, these updates will be discard silently in the
+  /// following sequence
+  /// 1. Invalid - Inserting an edge that does not exist in the CFG.
+  /// 2. Self-dominance update.
+  /// The Eager Strategy applies the update immediately while the Lazy Strategy
+  /// queues the update. It is recommended to only use this method when you have
+  /// exactly one insertion (and no deletions) and want to discard an invalid
+  /// update. Returns true if the update is valid.
+  bool insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+
+  /// Notify all available trees on an edge deletion. Under either Strategy,
+  /// self-dominance update will be removed. The Eager Strategy applies
+  /// the update immediately while the Lazy Strategy queues the update.
+  /// It is recommended to only use this method when you have exactly one
+  /// deletion (and no insertions). It is recommended to use applyUpdates() in
+  /// all other cases. This function has to be called *after* making the update
+  /// on the actual CFG. An internal functions checks if the edge doesn't exist
+  /// in the CFG in DEBUG mode.
+  void deleteEdge(BasicBlock *From, BasicBlock *To);
+
+  /// Notify all available trees on an edge deletion.
+  /// Under either Strategy, these updates will be discard silently in the
+  /// following sequence:
+  /// 1. Invalid - Deleting an edge that still exists in the CFG.
+  /// 2. Self-dominance update.
+  /// The Eager Strategy applies the update immediately while the Lazy Strategy
+  /// queues the update. It is recommended to only use this method when you have
+  /// exactly one deletion (and no insertions) and want to discard an invalid
+  /// update. Returns true if the update is valid.
+  bool deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
+
+  /// Delete DelBB. DelBB will be removed from its Parent and
+  /// erased from available trees if it exists and finally get deleted.
+  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
+  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
+  /// all available trees are up-to-date.
+  void deleteBB(BasicBlock *DelBB);
+
+  /// Delete DelBB. DelBB will be removed from its Parent and
+  /// erased from available trees if it exists. Then the callback will
+  /// be called. Finally, DelBB will be deleted.
+  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
+  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
+  /// all available trees are up-to-date.
+  /// Multiple callbacks can be queued for one DelBB under Lazy UpdateStrategy.
+  void callbackDeleteBB(BasicBlock *DelBB,
+                        std::function<void(BasicBlock *)> Callback);
+
+  /// Recalculate all available trees.
+  /// Under Lazy Strategy, available trees will only be recalculated if there
+  /// are pending updates or there is BasicBlock awaiting deletion. Returns true
+  /// if at least one tree is recalculated.
+  bool recalculate(Function &F);
+
+  /// Flush DomTree updates and return DomTree.
+  /// It also flush out of date updates applied by all available trees
+  /// and flush Deleted BBs if both trees are up-to-date.
+  /// It must only be called when it has a DomTree.
+  DominatorTree &getDomTree();
+
+  /// Flush PostDomTree updates and return PostDomTree.
+  /// It also flush out of date updates applied by all available trees
+  /// and flush Deleted BBs if both trees are up-to-date.
+  /// It must only be called when it has a PostDomTree.
+  PostDominatorTree &getPostDomTree();
+
+  /// Apply all pending updates to available trees and flush all BasicBlocks
+  /// awaiting deletion.
+  /// Does nothing under Eager UpdateStrategy.
+  void flush();
+
+  /// Debug method to help view the internal state of this class.
+  LLVM_DUMP_METHOD void dump() const;
+
+private:
+  class CallBackOnDeletion final : public CallbackVH {
+  public:
+    CallBackOnDeletion(BasicBlock *V,
+                       std::function<void(BasicBlock *)> Callback)
+        : CallbackVH(V), DelBB(V), Callback_(Callback) {}
+
+  private:
+    BasicBlock *DelBB = nullptr;
+    std::function<void(BasicBlock *)> Callback_;
+
+    void deleted() override {
+      Callback_(DelBB);
+      CallbackVH::deleted();
+    }
+  };
+
+  SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
+  size_t PendDTUpdateIndex = 0;
+  size_t PendPDTUpdateIndex = 0;
+  DominatorTree *DT = nullptr;
+  PostDominatorTree *PDT = nullptr;
+  const UpdateStrategy Strategy;
+  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
+  std::vector<CallBackOnDeletion> Callbacks;
+  bool IsRecalculatingDomTree = false;
+  bool IsRecalculatingPostDomTree = false;
+
+  /// First remove all the instructions of DelBB and then make sure DelBB has a
+  /// valid terminator instruction which is necessary to have when DelBB still
+  /// has to be inside of its parent Function while awaiting deletion under Lazy
+  /// UpdateStrategy to prevent other routines from asserting the state of the
+  /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
+  void validateDeleteBB(BasicBlock *DelBB);
+
+  /// Returns true if at least one BasicBlock is deleted.
+  bool forceFlushDeletedBB();
+
+  /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
+  /// UpdateStrategy. Returns true if the update is queued for update.
+  bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
+                       BasicBlock *To);
+
+  /// Helper function to apply all pending DomTree updates.
+  void applyDomTreeUpdates();
+
+  /// Helper function to apply all pending PostDomTree updates.
+  void applyPostDomTreeUpdates();
+
+  /// Helper function to flush deleted BasicBlocks if all available
+  /// trees are up-to-date.
+  void tryFlushDeletedBB();
+
+  /// Drop all updates applied by all available trees and delete BasicBlocks if
+  /// all available trees are up-to-date.
+  void dropOutOfDateUpdates();
+
+  /// Erase Basic Block node that has been unlinked from Function
+  /// in the DomTree and PostDomTree.
+  void eraseDelBBNode(BasicBlock *DelBB);
+
+  /// Returns true if the update appears in the LLVM IR.
+  /// It is used to check whether an update is valid in
+  /// insertEdge/deleteEdge or is unnecessary in the batch update.
+  bool isUpdateValid(DominatorTree::UpdateType Update) const;
+
+  /// Returns true if the update is self dominance.
+  bool isSelfDominance(DominatorTree::UpdateType Update) const;
+};
+} // namespace llvm
+
+#endif // LLVM_DOMTREEUPDATER_H

llvm/trunk/include/llvm/module.modulemap

module LLVM_intrinsic_gen {
   module IR_InstrTypes { header "IR/InstrTypes.h" export * }
   module IR_Instructions { header "IR/Instructions.h" export * }
 
 
   // Intrinsics.h
   module IR_CFG { header "IR/CFG.h" export * }
   module IR_ConstantRange { header "IR/ConstantRange.h" export * }
   module IR_Dominators { header "IR/Dominators.h" export * }
+  module Analysis_PostDominators { header "Analysis/PostDominators.h" export * }
+  module IR_DomTreeUpdater { header "IR/DomTreeUpdater.h" export * }
   module IR_IRBuilder { header "IR/IRBuilder.h" export * }
   module IR_PassManager { header "IR/PassManager.h" export * }
   module IR_PredIteratorCache { header "IR/PredIteratorCache.h" export * }
   module IR_Verifier { header "IR/Verifier.h" export * }
   module IR_InstIterator { header "IR/InstIterator.h" export * }
   module IR_InstVisitor { header "IR/InstVisitor.h" export * }
   module IR_Intrinsics { header "IR/Intrinsics.h" export * }
   module IR_IntrinsicInst { header "IR/IntrinsicInst.h" export * }

llvm/trunk/lib/IR/CMakeLists.txt

add_llvm_library(LLVMCore
   DataLayout.cpp
   DebugInfo.cpp
   DebugInfoMetadata.cpp
   DebugLoc.cpp
   DiagnosticHandler.cpp
   DiagnosticInfo.cpp
   DiagnosticPrinter.cpp
   Dominators.cpp
+  DomTreeUpdater.cpp
   Function.cpp
   GVMaterializer.cpp
   Globals.cpp
   IRBuilder.cpp
   IRPrintingPasses.cpp
   InlineAsm.cpp
   Instruction.cpp
   Instructions.cpp

llvm/trunk/lib/IR/DomTreeUpdater.cpp

+//===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the DomTreeUpdater class, which provides a uniform way
+// to update dominator tree related data structures.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/DomTreeUpdater.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/Support/GenericDomTree.h"
+#include <algorithm>
+#include <functional>
+
+namespace llvm {
+
+bool DomTreeUpdater::isUpdateValid(
+    const DominatorTree::UpdateType Update) const {
+  const auto *From = Update.getFrom();
+  const auto *To = Update.getTo();
+  const auto Kind = Update.getKind();
+
+  // Discard updates by inspecting the current state of successors of From.
+  // Since isUpdateValid() must be called *after* the Terminator of From is
+  // altered we can determine if the update is unnecessary for batch updates
+  // or invalid for a single update.
+  const bool HasEdge = llvm::any_of(
+      successors(From), [To](const BasicBlock *B) { return B == To; });
+
+  // If the IR does not match the update,
+  // 1. In batch updates, this update is unnecessary.
+  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
+  // Edge does not exist in IR.
+  if (Kind == DominatorTree::Insert && !HasEdge)
+    return false;
+
+  // Edge exists in IR.
+  if (Kind == DominatorTree::Delete && HasEdge)
+    return false;
+
+  return true;
+}
+
+bool DomTreeUpdater::isSelfDominance(
+    const DominatorTree::UpdateType Update) const {
+  // Won't affect DomTree and PostDomTree.
+  return Update.getFrom() == Update.getTo();
+}
+
+bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
+                                     BasicBlock *From, BasicBlock *To) {
+  assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
+         "Call applyLazyUpdate() with Eager strategy error");
+  // Analyze pending updates to determine if the update is unnecessary.
+  const DominatorTree::UpdateType Update = {Kind, From, To};
+  const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
+                                                ? DominatorTree::Insert
+                                                : DominatorTree::Delete,
+                                            From, To};
+  // Only check duplicates in updates that are not applied by both trees.
+  auto I =
+      PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
+  const auto E = PendUpdates.end();
+
+  assert(I <= E && "Iterator out of range.");
+
+  for (; I != E; ++I) {
+    if (Update == *I)
+      return false; // Discard duplicate updates.
+
+    if (Invert == *I) {
+      // Update and Invert are both valid (equivalent to a no-op). Remove
+      // Invert from PendUpdates and discard the Update.
+      PendUpdates.erase(I);
+      return false;
+    }
+  }
+
+  PendUpdates.push_back(Update); // Save the valid update.
+  return true;
+}
+
+void DomTreeUpdater::applyDomTreeUpdates() {
+  // No pending DomTreeUpdates.
+  if (Strategy != UpdateStrategy::Lazy || !DT)
+    return;
+
+  // Only apply updates not are applied by DomTree.
+  if (hasPendingDomTreeUpdates()) {
+    const auto I = PendUpdates.begin() + PendDTUpdateIndex;
+    const auto E = PendUpdates.end();
+    assert(I < E && "Iterator range invalid; there should be DomTree updates.");
+    DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
+    PendDTUpdateIndex = PendUpdates.size();
+  }
+}
+
+void DomTreeUpdater::flush() {
+  applyDomTreeUpdates();
+  applyPostDomTreeUpdates();
+  dropOutOfDateUpdates();
+}
+
+void DomTreeUpdater::applyPostDomTreeUpdates() {
+  // No pending PostDomTreeUpdates.
+  if (Strategy != UpdateStrategy::Lazy || !PDT)
+    return;
+
+  // Only apply updates not are applied by PostDomTree.
+  if (hasPendingPostDomTreeUpdates()) {
+    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
+    const auto E = PendUpdates.end();
+    assert(I < E &&
+           "Iterator range invalid; there should be PostDomTree updates.");
+    PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
+    PendPDTUpdateIndex = PendUpdates.size();
+  }
+}
+
+void DomTreeUpdater::tryFlushDeletedBB() {
+  if (!hasPendingUpdates())
+    forceFlushDeletedBB();
+}
+
+bool DomTreeUpdater::forceFlushDeletedBB() {
+  if (DeletedBBs.empty())
+    return false;
+
+  for (auto *BB : DeletedBBs) {
+    BB->removeFromParent();
+    eraseDelBBNode(BB);
+    delete BB;
+  }
+  DeletedBBs.clear();
+  Callbacks.clear();
+  return true;
+}
+
+bool DomTreeUpdater::recalculate(Function &F) {
+  if (!DT && !PDT)
+    return false;
+
+  if (Strategy == UpdateStrategy::Eager) {
+    if (DT)
+      DT->recalculate(F);
+    if (PDT)
+      PDT->recalculate(F);
+    return true;
+  }
+
+  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
+  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
+
+  // Because all trees are going to be up-to-date after recalculation,
+  // flush awaiting deleted BasicBlocks.
+  if (forceFlushDeletedBB() || hasPendingUpdates()) {
+    if (DT)
+      DT->recalculate(F);
+    if (PDT)
+      PDT->recalculate(F);
+
+    // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
+    IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
+    PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
+    dropOutOfDateUpdates();
+    return true;
+  }
+
+  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
+  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
+  return false;
+}
+
+bool DomTreeUpdater::hasPendingUpdates() const {
+  return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
+}
+
+bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
+  if (!DT)
+    return false;
+  return PendUpdates.size() != PendDTUpdateIndex;
+}
+
+bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
+  if (!PDT)
+    return false;
+  return PendUpdates.size() != PendPDTUpdateIndex;
+}
+
+bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
+  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
+    return false;
+  return DeletedBBs.count(DelBB) != 0;
+}
+
+// The DT and PDT require the nodes related to updates
+// are not deleted when update functions are called.
+// So BasicBlock deletions must be pended when the
+// UpdateStrategy is Lazy. When the UpdateStrategy is
+// Eager, the BasicBlock will be deleted immediately.
+void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
+  validateDeleteBB(DelBB);
+  if (Strategy == UpdateStrategy::Lazy) {
+    DeletedBBs.insert(DelBB);
+    return;
+  }
+
+  DelBB->removeFromParent();
+  eraseDelBBNode(DelBB);
+  delete DelBB;
+}
+
+void DomTreeUpdater::callbackDeleteBB(
+    BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
+  validateDeleteBB(DelBB);
+  if (Strategy == UpdateStrategy::Lazy) {
+    Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
+    DeletedBBs.insert(DelBB);
+    return;
+  }
+
+  DelBB->removeFromParent();
+  eraseDelBBNode(DelBB);
+  Callback(DelBB);
+  delete DelBB;
+}
+
+void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
+  if (DT && !IsRecalculatingDomTree)
+    if (DT->getNode(DelBB))
+      DT->eraseNode(DelBB);
+
+  if (PDT && !IsRecalculatingPostDomTree)
+    if (PDT->getNode(DelBB))
+      PDT->eraseNode(DelBB);
+}
+
+void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
+  assert(DelBB && "Invalid push_back of nullptr DelBB.");
+  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
+  // DelBB is unreachable and all its instructions are dead.
+  while (!DelBB->empty()) {
+    Instruction &I = DelBB->back();
+    // Replace used instructions with an arbitrary value (undef).
+    if (!I.use_empty())
+      I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
+    DelBB->getInstList().pop_back();
+  }
+  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
+  // Child of Function F it must contain valid IR.
+  new UnreachableInst(DelBB->getContext(), DelBB);
+}
+
+void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
+                                  bool ForceRemoveDuplicates) {
+  if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
+    SmallVector<DominatorTree::UpdateType, 8> Seen;
+    for (const auto U : Updates)
+      // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
+      // on analysis.
+      if (llvm::none_of(
+              Seen,
+              [U](const DominatorTree::UpdateType S) { return S == U; }) &&
+          isUpdateValid(U) && !isSelfDominance(U)) {
+        Seen.push_back(U);
+        if (Strategy == UpdateStrategy::Lazy)
+          applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
+      }
+    if (Strategy == UpdateStrategy::Lazy)
+      return;
+
+    if (DT)
+      DT->applyUpdates(Seen);
+    if (PDT)
+      PDT->applyUpdates(Seen);
+    return;
+  }
+
+  if (DT)
+    DT->applyUpdates(Updates);
+  if (PDT)
+    PDT->applyUpdates(Updates);
+}
+
+DominatorTree &DomTreeUpdater::getDomTree() {
+  assert(DT && "Invalid acquisition of a null DomTree");
+  applyDomTreeUpdates();
+  dropOutOfDateUpdates();
+  return *DT;
+}
+
+PostDominatorTree &DomTreeUpdater::getPostDomTree() {
+  assert(PDT && "Invalid acquisition of a null PostDomTree");
+  applyPostDomTreeUpdates();
+  dropOutOfDateUpdates();
+  return *PDT;
+}
+
+void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
+
+#ifndef NDEBUG
+  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
+         "Inserted edge does not appear in the CFG");
+#endif
+
+  // Won't affect DomTree and PostDomTree; discard update.
+  if (From == To)
+    return;
+
+  if (Strategy == UpdateStrategy::Eager) {
+    if (DT)
+      DT->insertEdge(From, To);
+    if (PDT)
+      PDT->insertEdge(From, To);
+    return;
+  }
+
+  applyLazyUpdate(DominatorTree::Insert, From, To);
+}
+
+bool DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
+  if (!isUpdateValid({DominatorTree::Insert, From, To}))
+    return false;
+
+  if (From == To)
+    return true;
+
+  if (Strategy == UpdateStrategy::Eager) {
+    if (DT)
+      DT->insertEdge(From, To);
+    if (PDT)
+      PDT->insertEdge(From, To);
+    return true;
+  }
+
+  applyLazyUpdate(DominatorTree::Insert, From, To);
+  return true;
+}
+
+void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
+
+#ifndef NDEBUG
+  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
+         "Deleted edge still exists in the CFG!");
+#endif
+
+  // Won't affect DomTree and PostDomTree; discard update.
+  if (From == To)
+    return;
+
+  if (Strategy == UpdateStrategy::Eager) {
+    if (DT)
+      DT->deleteEdge(From, To);
+    if (PDT)
+      PDT->deleteEdge(From, To);
+    return;
+  }
+
+  applyLazyUpdate(DominatorTree::Delete, From, To);
+}
+
+bool DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
+  if (!isUpdateValid({DominatorTree::Delete, From, To}))
+    return false;
+
+  if (From == To)
+    return true;
+
+  if (Strategy == UpdateStrategy::Eager) {
+    if (DT)
+      DT->deleteEdge(From, To);
+    if (PDT)
+      PDT->deleteEdge(From, To);
+    return true;
+  }
+
+  applyLazyUpdate(DominatorTree::Delete, From, To);
+  return true;
+}
+
+void DomTreeUpdater::dropOutOfDateUpdates() {
+  if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
+    return;
+
+  tryFlushDeletedBB();
+
+  // Drop all updates applied by both trees.
+  if (!DT)
+    PendDTUpdateIndex = PendUpdates.size();
+  if (!PDT)
+    PendPDTUpdateIndex = PendUpdates.size();
+
+  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
+  const auto B = PendUpdates.begin();
+  const auto E = PendUpdates.begin() + dropIndex;
+  assert(B <= E && "Iterator out of range.");
+  PendUpdates.erase(B, E);
+  // Calculate current index.
+  PendDTUpdateIndex -= dropIndex;
+  PendPDTUpdateIndex -= dropIndex;
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
+  raw_ostream &OS = llvm::dbgs();
+
+  OS << "Available Trees: ";
+  if (DT || PDT) {
+    if (DT)
+      OS << "DomTree ";
+    if (PDT)
+      OS << "PostDomTree ";
+    OS << "\n";
+  } else
+    OS << "None\n";
+
+  OS << "UpdateStrategy: ";
+  if (Strategy == UpdateStrategy::Eager) {
+    OS << "Eager\n";
+    return;
+  } else
+    OS << "Lazy\n";
+  int Index = 0;
+
+  auto printUpdates =
+      [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
+          ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
+        if (begin == end)
+          OS << "  None\n";
+        Index = 0;
+        for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
+          auto U = *It;
+          OS << "  " << Index << " : ";
+          ++Index;
+          if (U.getKind() == DominatorTree::Insert)
+            OS << "Insert, ";
+          else
+            OS << "Delete, ";
+          BasicBlock *From = U.getFrom();
+          if (From) {
+            auto S = From->getName();
+            if (!From->hasName())
+              S = "(no name)";
+            OS << S << "(" << From << "), ";
+          } else {
+            OS << "(badref), ";
+          }
+          BasicBlock *To = U.getTo();
+          if (To) {
+            auto S = To->getName();
+            if (!To->hasName())
+              S = "(no_name)";
+            OS << S << "(" << To << ")\n";
+          } else {
+            OS << "(badref)\n";
+          }
+        }
+      };
+
+  if (DT) {
+    const auto I = PendUpdates.begin() + PendDTUpdateIndex;
+    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
+           "Iterator out of range.");
+    OS << "Applied but not cleared DomTreeUpdates:\n";
+    printUpdates(PendUpdates.begin(), I);
+    OS << "Pending DomTreeUpdates:\n";
+    printUpdates(I, PendUpdates.end());
+  }
+
+  if (PDT) {
+    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
+    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
+           "Iterator out of range.");
+    OS << "Applied but not cleared PostDomTreeUpdates:\n";
+    printUpdates(PendUpdates.begin(), I);
+    OS << "Pending PostDomTreeUpdates:\n";
+    printUpdates(I, PendUpdates.end());
+  }
+
+  OS << "Pending DeletedBBs:\n";
+  Index = 0;
+  for (auto BB : DeletedBBs) {
+    OS << "  " << Index << " : ";
+    ++Index;
+    if (BB->hasName())
+      OS << BB->getName() << "(";
+    else
+      OS << "(no_name)(";
+    OS << BB << ")\n";
+  }
+
+  OS << "Pending Callbacks:\n";
+  Index = 0;
+  for (auto BB : Callbacks) {
+    OS << "  " << Index << " : ";
+    ++Index;
+    if (BB->hasName())
+      OS << BB->getName() << "(";
+    else
+      OS << "(no_name)(";
+    OS << BB << ")\n";
+  }
+}
+#endif
+} // namespace llvm

llvm/trunk/unittests/IR/CMakeLists.txt

add_llvm_unittest(IRTests
   CFGBuilder.cpp
   ConstantRangeTest.cpp
   ConstantsTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
   DeferredDominanceTest.cpp
   DominatorTreeTest.cpp
   DominatorTreeBatchUpdatesTest.cpp
+  DomTreeUpdaterTest.cpp
   FunctionTest.cpp
   PassBuilderCallbacksTest.cpp
   IRBuilderTest.cpp
   InstructionsTest.cpp
   IntrinsicsTest.cpp
   LegacyPassManagerTest.cpp
   MDBuilderTest.cpp
   ManglerTest.cpp

llvm/trunk/unittests/IR/DomTreeUpdaterTest.cpp

+//==- llvm/unittests/IR/DomTreeUpdaterTest.cpp - DomTreeUpdater unit tests ===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/DomTreeUpdater.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+#include <algorithm>
+
+using namespace llvm;
+
+static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
+                                              StringRef ModuleStr) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
+  assert(M && "Bad LLVM IR?");
+  return M;
+}
+
+TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %i, i32 *%p) {
+                          bb0:
+                             store i32 %i, i32 *%p
+                             switch i32 %i, label %bb1 [
+                               i32 1, label %bb2
+                               i32 2, label %bb3
+                             ]
+                          bb1:
+                             ret i32 1
+                          bb2:
+                             ret i32 2
+                          bb3:
+                             ret i32 3
+                          })";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DomTreeUpdater.
+  DominatorTree DT(*F);
+  PostDominatorTree PDT(*F);
+  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_TRUE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Eager);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+  BasicBlock *BB2 = &*FI++;
+  BasicBlock *BB3 = &*FI++;
+  SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
+  ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
+
+  ASSERT_FALSE(DTU.insertEdgeRelaxed(BB0, BB0));
+  ASSERT_TRUE(DTU.deleteEdgeRelaxed(BB0, BB0));
+
+  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
+  // entries are discarded.
+  std::vector<DominatorTree::UpdateType> Updates;
+  Updates.reserve(4);
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+
+  // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
+  Updates.push_back({DominatorTree::Insert, BB1, BB2});
+  // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
+  Updates.push_back({DominatorTree::Delete, BB0, BB1});
+
+  // CFG Change: remove edge bb0 -> bb3.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
+  BB3->removePredecessor(BB0);
+  for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
+    if (i->getCaseSuccessor() == BB3) {
+      SI->removeCase(i);
+      break;
+    }
+  }
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
+  // Deletion of a BasicBlock is an immediate event. We remove all uses to the
+  // contained Instructions and change the Terminator to "unreachable" when
+  // queued for deletion.
+  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
+  DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
+  ASSERT_FALSE(DTU.insertEdgeRelaxed(BB1, BB2));
+  // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
+  ASSERT_FALSE(DTU.deleteEdgeRelaxed(BB0, BB1));
+
+  // DTU working with Eager UpdateStrategy does not need to flush.
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+
+  // Test callback utils.
+  ASSERT_EQ(BB3->getParent(), F);
+  DTU.callbackDeleteBB(BB3,
+                       [&F](BasicBlock *BB) { ASSERT_NE(BB->getParent(), F); });
+
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  // Unnecessary flush() test
+  DTU.flush();
+  EXPECT_TRUE(DT.verify());
+  EXPECT_TRUE(PDT.verify());
+
+  // Remove all case branch to BB2 to test Eager recalculation.
+  // Code section from llvm::ConstantFoldTerminator
+  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
+    if (i->getCaseSuccessor() == BB2) {
+      // Remove this entry.
+      BB2->removePredecessor(BB0);
+      i = SI->removeCase(i);
+      e = SI->case_end();
+    } else
+      ++i;
+  }
+  ASSERT_FALSE(DT.verify());
+  ASSERT_FALSE(PDT.verify());
+  DTU.recalculate(*F);
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+}
+
+TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f() {
+                           bb0:
+                              br label %bb1
+                            bb1:
+                              ret i32 1
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  PostDominatorTree PDT(*F);
+  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_TRUE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Eager);
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+
+  // Add a block as the new function entry BB. We also link it to BB0.
+  BasicBlock *NewEntry =
+      BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
+  BranchInst::Create(BB0, NewEntry);
+  EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
+  EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
+
+  ASSERT_TRUE(DTU.insertEdgeRelaxed(NewEntry, BB0));
+
+  // Changing the Entry BB requires a full recalculation of DomTree.
+  DTU.recalculate(*F);
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+
+  // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
+  EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
+  NewEntry->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, NewEntry);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+
+  // Update the DTU. At this point bb0 now has no predecessors but is still a
+  // Child of F.
+  DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
+                    {DominatorTree::Insert, NewEntry, BB1}});
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+
+  // Now remove bb0 from F.
+  ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
+  DTU.deleteBB(BB0);
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+}
+
+TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f(i32 %i, i32 *%p) {
+                            bb0:
+                              store i32 %i, i32 *%p
+                              switch i32 %i, label %bb1 [
+                                i32 0, label %bb2
+                                i32 1, label %bb2
+                                i32 2, label %bb3
+                              ]
+                            bb1:
+                              ret i32 1
+                            bb2:
+                              ret i32 2
+                            bb3:
+                              ret i32 3
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_FALSE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+  BasicBlock *BB2 = &*FI++;
+  BasicBlock *BB3 = &*FI++;
+
+  // Test discards of self-domination update.
+  DTU.deleteEdge(BB0, BB0);
+  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+
+  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
+  // entries are discarded.
+  std::vector<DominatorTree::UpdateType> Updates;
+  Updates.reserve(4);
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+
+  // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
+  Updates.push_back({DominatorTree::Insert, BB1, BB2});
+  // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
+  Updates.push_back({DominatorTree::Delete, BB0, BB1});
+
+  // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
+  BB0->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
+
+  // Verify. Updates to DTU must be applied *after* all changes to the CFG
+  // (including block deletion).
+  DTU.applyUpdates(Updates);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+
+  // Deletion of a BasicBlock is an immediate event. We remove all uses to the
+  // contained Instructions and change the Terminator to "unreachable" when
+  // queued for deletion. Its parent is still F until all the pending updates
+  // are applied to all trees held by the DomTreeUpdater (DomTree/PostDomTree).
+  // We don't defer this action because it can cause problems for other
+  // transforms or analysis as it's part of the actual CFG. We only defer
+  // updates to the DominatorTrees. This code will crash if it is placed before
+  // the BranchInst::Create() call above. After a deletion of a BasicBlock. Only
+  // an explicit flush event can trigger the flushing of deleteBBs. Because some
+  // passes using Lazy UpdateStrategy rely on this behavior.
+
+  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
+  EXPECT_FALSE(DTU.hasPendingDeletedBB());
+  DTU.deleteBB(BB3);
+  EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
+  EXPECT_TRUE(DTU.hasPendingDeletedBB());
+  ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
+  EXPECT_EQ(BB3->getParent(), F);
+  DTU.recalculate(*F);
+
+  EXPECT_FALSE(DTU.hasPendingDeletedBB());
+}
+
+TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f(i32 %i, i32 *%p) {
+                            bb0:
+                              store i32 %i, i32 *%p
+                              switch i32 %i, label %bb1 [
+                                i32 2, label %bb2
+                                i32 3, label %bb3
+                              ]
+                            bb1:
+                              br label %bb3
+                            bb2:
+                              br label %bb3
+                            bb3:
+                              ret i32 3
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_FALSE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+  BasicBlock *BB2 = &*FI++;
+  BasicBlock *BB3 = &*FI++;
+
+  // There are several CFG locations where we have:
+  //
+  //   pred1..predN
+  //    |        |
+  //    +> curr <+    converted into:   pred1..predN curr
+  //        |                            |        |
+  //        v                            +> succ <+
+  //       succ
+  //
+  // There is a specific shape of this we have to be careful of:
+  //
+  //   pred1..predN
+  //   ||        |
+  //   |+> curr <+    converted into:   pred1..predN curr
+  //   |    |                            |        |
+  //   |    v                            +> succ <+
+  //   +-> succ
+  //
+  // While the final CFG form is functionally identical the updates to
+  // DTU are not. In the first case we must have DTU.insertEdge(Pred1, Succ)
+  // while in the latter case we must *NOT* have DTU.insertEdge(Pred1, Succ).
+
+  // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
+  // remove bb2.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
+  BB0->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
+
+  // Test callback utils.
+  std::vector<BasicBlock *> BasicBlocks;
+  BasicBlocks.push_back(BB1);
+  BasicBlocks.push_back(BB2);
+  auto Eraser = [&](BasicBlock *BB) {
+    BasicBlocks.erase(
+        std::remove_if(BasicBlocks.begin(), BasicBlocks.end(),
+                       [&](const BasicBlock *i) { return i == BB; }),
+        BasicBlocks.end());
+  };
+  ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
+  // Remove bb2 from F. This has to happen before the call to applyUpdates() for
+  // DTU to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
+  // method converts bb2's TI into "unreachable".
+  ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
+  DTU.callbackDeleteBB(BB2, Eraser);
+  EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));
+  ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
+  EXPECT_EQ(BB2->getParent(), F);
+
+  // Queue up the DTU updates.
+  std::vector<DominatorTree::UpdateType> Updates;
+  Updates.reserve(4);
+  Updates.push_back({DominatorTree::Delete, BB0, BB2});
+  Updates.push_back({DominatorTree::Delete, BB2, BB3});
+
+  // Handle the specific shape case next.
+  // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
+  BB0->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB3, BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+
+  // Remove bb1 from F. This has to happen before the call to applyUpdates() for
+  // DTU to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
+  // method converts bb1's TI into "unreachable".
+  ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
+  DTU.callbackDeleteBB(BB1, Eraser);
+  EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
+  ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
+  EXPECT_EQ(BB1->getParent(), F);
+
+  // Update the DTU. In this case we don't call DTU.insertEdge(BB0, BB3) because
+  // the edge previously existed at the start of this test when DT was first
+  // created.
+  Updates.push_back({DominatorTree::Delete, BB0, BB1});
+  Updates.push_back({DominatorTree::Delete, BB1, BB3});
+
+  // Verify everything.
+  DTU.applyUpdates(Updates);
+  ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
+  DTU.flush();
+  ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
+  ASSERT_TRUE(DT.verify());
+}
+
+TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f(i32 %i, i32 *%p) {
+                            bb0:
+                              store i32 %i, i32 *%p
+                              switch i32 %i, label %bb1 [
+                                i32 0, label %bb2
+                                i32 1, label %bb2
+                                i32 2, label %bb3
+                              ]
+                            bb1:
+                              ret i32 1
+                            bb2:
+                              ret i32 2
+                            bb3:
+                              ret i32 3
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  PostDominatorTree PDT(*F);
+  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_TRUE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+  BasicBlock *BB2 = &*FI++;
+  BasicBlock *BB3 = &*FI++;
+  // Test discards of self-domination update.
+  DTU.deleteEdge(BB0, BB0);
+
+  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
+  // entries are discarded.
+  std::vector<DominatorTree::UpdateType> Updates;
+  Updates.reserve(4);
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+
+  // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
+  Updates.push_back({DominatorTree::Insert, BB1, BB2});
+  // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
+  Updates.push_back({DominatorTree::Delete, BB0, BB1});
+
+  // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
+  BB0->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
+
+  // Deletion of a BasicBlock is an immediate event. We remove all uses to the
+  // contained Instructions and change the Terminator to "unreachable" when
+  // queued for deletion. Its parent is still F until DTU.flushDomTree is
+  // called. We don't defer this action because it can cause problems for other
+  // transforms or analysis as it's part of the actual CFG. We only defer
+  // updates to the DominatorTree. This code will crash if it is placed before
+  // the BranchInst::Create() call above.
+  bool CallbackFlag = false;
+  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
+  DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; });
+  EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
+  ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
+  EXPECT_EQ(BB3->getParent(), F);
+
+  // Verify. Updates to DTU must be applied *after* all changes to the CFG
+  // (including block deletion).
+  DTU.applyUpdates(Updates);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.hasPendingUpdates());
+  ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
+  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+  ASSERT_TRUE(DTU.hasPendingDeletedBB());
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+  ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
+  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+  ASSERT_FALSE(DTU.hasPendingDeletedBB());
+  ASSERT_EQ(CallbackFlag, true);
+}
+
+TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f() {
+                           bb0:
+                              br label %bb1
+                            bb1:
+                              ret i32 1
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  PostDominatorTree PDT(*F);
+  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_TRUE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+
+  // Add a block as the new function entry BB. We also link it to BB0.
+  BasicBlock *NewEntry =
+      BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
+  BranchInst::Create(BB0, NewEntry);
+  EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
+  EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
+
+  // Insert the new edge between new_entry -> bb0. Without this the
+  // recalculate() call below will not actually recalculate the DT as there
+  // are no changes pending and no blocks deleted.
+  DTU.insertEdge(NewEntry, BB0);
+
+  // Changing the Entry BB requires a full recalculation.
+  DTU.recalculate(*F);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+
+  // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
+  EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
+  NewEntry->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, NewEntry);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+
+  // Update the DTU. At this point bb0 now has no predecessors but is still a
+  // Child of F.
+  DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
+                    {DominatorTree::Insert, NewEntry, BB1}});
+  DTU.flush();
+  ASSERT_TRUE(DT.verify());
+  ASSERT_TRUE(PDT.verify());
+
+  // Now remove bb0 from F.
+  ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
+  DTU.deleteBB(BB0);
+  EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));
+  ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
+  EXPECT_EQ(BB0->getParent(), F);
+
+  // Perform a full recalculation of the DTU. It is not necessary here but we
+  // do this to test the case when there are no pending DT updates but there are
+  // pending deleted BBs.
+  ASSERT_TRUE(DTU.hasPendingDeletedBB());
+  DTU.recalculate(*F);
+  ASSERT_FALSE(DTU.hasPendingDeletedBB());
+}
+
+TEST(DomTreeUpdater, LazyUpdateStepTest) {
+  // This test focus on testing a DTU holding both trees applying multiple
+  // updates and DT/PDT not flushed together.
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f(i32 %i, i32 *%p) {
+                            bb0:
+                              store i32 %i, i32 *%p
+                              switch i32 %i, label %bb1 [
+                                i32 0, label %bb1
+                                i32 1, label %bb2
+                                i32 2, label %bb3
+                                i32 3, label %bb1
+                              ]
+                            bb1:
+                              ret i32 1
+                            bb2:
+                              ret i32 2
+                            bb3:
+                              ret i32 3
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DomTreeUpdater.
+  DominatorTree DT(*F);
+  PostDominatorTree PDT(*F);
+  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+
+  ASSERT_TRUE(DTU.hasDomTree());
+  ASSERT_TRUE(DTU.hasPostDomTree());
+  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  FI++;
+  BasicBlock *BB2 = &*FI++;
+  BasicBlock *BB3 = &*FI++;
+  SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
+  ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
+
+  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
+  // entries are discarded.
+  std::vector<DominatorTree::UpdateType> Updates;
+  Updates.reserve(1);
+  Updates.push_back({DominatorTree::Delete, BB0, BB3});
+
+  // CFG Change: remove edge bb0 -> bb3.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);
+  BB3->removePredecessor(BB0);
+  for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
+    if (i->getCaseIndex() == 2) {
+      SI->removeCase(i);
+      break;
+    }
+  }
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
+  // Deletion of a BasicBlock is an immediate event. We remove all uses to the
+  // contained Instructions and change the Terminator to "unreachable" when
+  // queued for deletion.
+  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
+  EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
+  DTU.applyUpdates(Updates);
+
+  // Only flush DomTree.
+  ASSERT_TRUE(DTU.getDomTree().verify());
+  ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
+  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+
+  ASSERT_EQ(BB3->getParent(), F);
+  DTU.deleteBB(BB3);
+
+  Updates.clear();
+
+  // Remove all case branch to BB2 to test Eager recalculation.
+  // Code section from llvm::ConstantFoldTerminator
+  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
+    if (i->getCaseSuccessor() == BB2) {
+      // Remove this entry.
+      BB2->removePredecessor(BB0);
+      i = SI->removeCase(i);
+      e = SI->case_end();
+      Updates.push_back({DominatorTree::Delete, BB0, BB2});
+    } else
+      ++i;
+  }
+
+  DTU.applyUpdates(Updates);
+  // flush PostDomTree
+  ASSERT_TRUE(DTU.getPostDomTree().verify());
+  ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
+  ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
+  // flush both trees
+  DTU.flush();
+  ASSERT_TRUE(DT.verify());
+}