[Dominators] Convert existing passes and utils to use the DomTreeUpdater class

[NutshellySima]

Summary

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

It converts passes (e.g. adce/jump-threading) and various functions which currently accept DDT in local.cpp and BasicBlockUtils.cpp to use the new DomTreeUpdater class.
These converted functions in utils can accept DomTreeUpdater with either UpdateStrategy and can deal with both DT and PDT held by the DomTreeUpdater.

[brzycki]

Hello @NutshellySima , my comments are inline below. These changes are a good real-world usage of the new DTU class and should help us find any bugs or deficiencies. I'm curious to know what kind of testing you've done on this code: ninja check, test-suite, and/or test-suite for compile time?

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

It's not obvious here the reasoning behind this statement. I recommend either changing this to DTU->flush() or adding a comment stating the call will force all updates to the internal DT/PDT trees.

996 ↗

(On Diff #154220)

So much cleaner!

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2540 ↗

(On Diff #154220)

Same as other flush() comment.

lib/Transforms/Utils/BasicBlockUtils.cpp

160 ↗

(On Diff #154220)

It might be a good idea to add a comment here why you're only adding these updates for UpdateStrategy::Lazy. Even I can't remember why this is the case, and I did this change. :)

(BTW, this routine is one of the most difficult and I struggled with it for weeks. Keep an eye on changes in here.)

198 ↗

(On Diff #154220)

Why did you move the LI and MemDep calls up?

206 ↗

(On Diff #154220)

I'm seeing several statements of this long form. Maybe add query methods like isUpdateEager() and isUpdateLazy() to simplify long comparison statements like these?

223 ↗

(On Diff #154220)

Please add {} here. Even though it's only one statement the if section uses them and it's a long block. Putting a small amount of distance between the two next statements makes it clear that we always call deleteBB.

You might also want to add a comment here denoting this as the Lazy path. With the outer if/else it's a little hard to read.

lib/Transforms/Utils/Local.cpp

746 ↗

(On Diff #154220)

Have you verified this does not need to be done for the Eager strategy? From what I can tell no one in LLVM is calling to RemovePredecessorAndSimplify. I wouldn't have added support for DDT here unless I absolutely needed it so I suspect the changes to JumpThreading have removed the need for it. I am nervous about this change because I am uncertain it's correct.

1062 ↗

(On Diff #154220)

Why are you always zapping the block here instead of relying on the deleteBB routine and the knowledge of your current UpdateStrategy within the DTU class?

1890 ↗

(On Diff #154220)

I have concerns about code coverage here (and the sole user of this routine, removeUnreachableBlocks below). JumpThreading no longer makes use of this routine and the sole user of it now is RewriteStatepointsForGC.cpp. I don't know how much actual testing of your new code paths is actually happening.

2126 ↗

(On Diff #154220)

Same question here as the similar zap blocks comment above.

[NutshellySima]

In D48967#1154447, @brzycki wrote:

Hello @NutshellySima , my comments are inline below. These changes are a good real-world usage of the new DTU class and should help us find any bugs or deficiencies. I'm curious to know what kind of testing you've done on this code: ninja check, test-suite, and/or test-suite for compile time?

I ran ninja check-llvm with assertions enabled.

lib/Transforms/Utils/BasicBlockUtils.cpp

198 ↗

(On Diff #154220)

Previously, this function accepts DT/DDT. In the DT case, it calls DT->eraseNode(BB) then call BB->eraseFromParent() after calling LI->removeBlock(BB); In the DDT case, it calls DDT.deleteBB(BB) before calling LI->removeBlock(BB).

Since outside users can pass a DTU working under Eager UpdateStrategy (that is to say, calling DTU.deleteBB(BB) will immediately do both DT/PDT.eraseNode(BB) and BB->eraseFromParent()) which obviously has conflicts with LI->removeBlock(BB), so I move them up.

lib/Transforms/Utils/Local.cpp

746 ↗

(On Diff #154220)

This part of the code reuses the DT handling code before to be the Eager UpdateStrategy ones and the DDT handling code to the Lazy ones. The only perhaps uncertain change is whether my PDT handling code under Eager strategy (L729-L737) is correct and whether the previous code of DDT can also handle the PDT case.
I modified the unittest of local.cpp to cover the change and it seems correct.

1062 ↗

(On Diff #154220)

I'm quite uncertain here because I have to call deleteBB after applyUpdates to make this utility works under Eager strategy. But it asserts when running the unittest, so I add these zapping block codes here.

[brzycki]

In D48967#1154501, @NutshellySima wrote:

I ran ninja check-llvm with assertions enabled.

That is definitely not sufficient. The .ll test cases are only a small subset of real-world code and people only add to them to verify a new feature or to prove a bug is fixed. I recommend running test-suite to get a better representation of code out in the world. If you are uncertain how to do so please e-mail me and I'll provide detailed instructions. I'm hoping we can avoid stressful bug report debugging and LLVM code reverts/reapplies.

lib/Transforms/Utils/BasicBlockUtils.cpp

198 ↗

(On Diff #154220)

That makes sense. Thanks!

lib/Transforms/Utils/Local.cpp

746 ↗

(On Diff #154220)

Understood. One way I verified coverage during testing was adding assert(0 && "tracking string 1") on code paths I was uncertain were being exercised. After running ninja check and test-suite I'd grep for the string.

1062 ↗

(On Diff #154220)

Your response makes me even less comfortable with this code. Users will not be aware this zapping is to prepare the code for DTU eager updates and it's also done on every block, even if a DTU isn't passed in which is unnecessary. I recommend debugging this more to see if you can find a way to hide this kind of BB manipulation and tie it to the eager strategy better.

[NutshellySima]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

I think DTU->flush() should only be called when people need either

1. Flush all deleteBB awaiting deletion.
2. Do queries on both DT and PDT.

In the future, if DTU holds both DT and PDT in JumpThreading, call DTU->getDomTree which only flushes DT can pend updates on PDT as lazy as possible.

lib/Transforms/Utils/BasicBlockUtils.cpp

160 ↗

(On Diff #154220)

OK. The reason why only these updates are only added for UpdateStrategy::Lazy is that I reuse the codes handling DT previously to handle the Eager case. If the performance impact is negligible, we can combine these two ways together into only using the incremental way in the future.

206 ↗

(On Diff #154220)

Sure. It can be added in another patch.

lib/Transforms/Utils/Local.cpp

1062 ↗

(On Diff #154220)

I understand why these zapping codes are needed. DTU.applyUpdates() do simple checks on whether the edge exists in the CFG. However, the TerminatorInst of delBB isn't removed, so the check just discard the update if applyUpdates is called before deleteBB. I'll modify this part of code into the logic of removing the TerminatorInst before calling applyUpdates.

[NutshellySima]

1. Add DTU to LoopUtils
2. Address comments
3. rebase

[brzycki]

Hello @NutshellySima , comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

I'm concerned the complexity of updates will become unmanageable if you decide to take this route. Some questions I have:

• How do you preserve the list of updates for one vs the other? Two separate queues?
• How do you decide to delete unnecessary updates from one and not the other?
• How do you manage the list of delted BBs? Are they only really deleted when both DT and PDT are flushed?
• How do you make sure you don't actually delete a BB early?
• How do you handle Eager vs Lazy updates?
• How do you handle *Relaxed() updates?

The longer you avoid flushing the further your updates become from the real CFG's shape. Debugging an assert where DT and PDT update at different times means the developer has to also carefully keep the state of DTU in mind instead of just the IR and the trees. I'm not sure if the possible saved overhead of updates to one or the other tree is worth all that added complexity.

lib/Transforms/Utils/BasicBlockUtils.cpp

160 ↗

(On Diff #154220)

I always prefer simpler code if the performance impact is negligible. You'll be glad you did when you're furiously debugging a problem and an LLVM release window is coming up. :)

206 ↗

(On Diff #154220)

Sounds good, thanks!

lib/Transforms/Utils/Local.cpp

1062 ↗

(On Diff #154220)

Sounds like a cleaner solution, thank you for looking into this. I'll review the code when you update the change.

[kuhar]

A general high-level question/suggestion: would it be possible to split this patch such that we don't change all of the uses of DDT and plain updates at once? I'm afraid this can subtly break in many places, and the patch will have to be reverted a couple of times before you get them right. If you do it with more granularity, then it should be easier to land each part and test it in isolation.
Is it possible, or do you have a dependency on the utility functions from Local.cpp and other helper files?

lib/Transforms/Scalar/JumpThreading.cpp

364 ↗

(On Diff #154489)

Can DTU have no DomTree here? Maybe we should assert for that?

409 ↗

(On Diff #154489)

nit: I think formatting is a bit off here. Can you run clang-format on this snippet?

[kuhar]

lib/Transforms/Scalar/JumpThreading.cpp

409 ↗

(On Diff #154489)

Ah, it's because of the really long if condition...

[NutshellySima]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

How do you preserve the list of updates for one vs the other? Two separate queues?

There is only one queue and two index to record the updates that have been applied and not applied yet.

Index	0	1	2	3
PendUpdates	o	o	o	o
DTUpdateIndex			↑
PDTUpdateIndex	↑

How do you decide to delete unnecessary updates from one and not the other?

If an update is applied by all available trees, it will be purged.

How do you manage the list of deleted BBs? Are they only really deleted when both DT and PDT are flushed?

Yes, more specifically DTUpdateIndex == PDTUpdateIndex == PendUpdates.size(). It's impossible to judge whether a specific DelBB is feasible to be deleted at a specific time point because some callers of delBB just

BasicBlock *BB0 = ...;
DTU.delBB (BB0);
// Then do some actions on BB0
... ...
DTU.flush(); // The caller expects BB0 be deleted now.

How do you make sure you don't actually delete a BB early?

Mentioned above.

How do you handle Eager vs Lazy updates?

applyUpdates:
Lazy/Eager+ForceRemoveDuplicates - Works the same as DDT, more specifically

1. Deduplicate, which is the main functionality of DDT.
2. Inspect whether an edge is presented in CFG and decide whether to discard it. It is a must because the update sequence is unbalanced.

Eager - Works the same as raw DT/PDT.
insertEdge/deleteEdge:
Eager: Works the same as raw DT/PDT and adds inspection whether the update is valid.
Lazy: then submits into the list of updates rather than apply it.
recalculate:
Lazy: flush() + raw recalculate()
Eager: raw recalculate()

How do you handle *Relaxed() updates?

It behaves the same as the ones in DDT. It discards invalid updates quietly.

The longer you avoid flushing the further your updates become from the real CFG's shape. Debugging an assert where DT and PDT update at different times means the developer has to also carefully keep the state of DTU in mind instead of just the IR and the trees. I'm not sure if the possible saved overhead of updates to one or the other tree is worth all that added complexity.

I don't think so. With current DDT, let me show an example

// Changing the state of CFG begins. 
... // Modify CFG
MergeBasicBlockIntoOnlyPred (..., &DDT); // Some error happens !
// (You cannot do verification after MergeBasicBlockIntoOnlyPred because the CFG and DT is unsynced)
... // Modify DomTree
... // Modify CFG
// Changing the state of CFG ends.
...
DDT.flush().verify(); // Asserts !

Now with DTU,

// Changing the state of CFG begins.
... // Modify CFG
MergeBasicBlockIntoOnlyPred (..., &DTU); // Some error happens !
//  (You cannot do verification after MergeBasicBlockIntoOnlyPred because the CFG and DT is unsynced)
... // Modify DomTree
... // Modify CFG
// Changing the state of CFG ends.
...
DTU.getDomTree().verify(); // Asserts !

I can't see the difference. They'll assert at the same location and all far away from where the bug happens.

[brzycki]

Hello @NutshellySima , comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

Let's say you have a DTU using the Lazy strategy. The current set of internally queued pending updates are the following:

[0] {Insert, A, B}
[1] {Delete, B, C}
[2] {Insert, B, D}

And you have both a DT and PDT. Their Indicies are the following:

DTU->IndexDT = 0;
DTU->IndexPDT = 0;

And you flush just the DT:

DTU->getDomTree(); // flush DT only

Now your indicies are the following:

DTU->IndexDT = 3;
DTU0>IndexPDT = 0;

And now the following update comes along:

DTU->deleteEdgeRelaxed(A,B);

In the case of PDT you want nothing to happen: this update will remove the inverted update [0] from the queue and result in a no-op to PDT. But in the case of the DT you need the update to happen: it's a change past the flush. How do you reconcile this internally with only one queue?

[NutshellySima]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

In the case of PDT you want nothing to happen: this update will remove the inverted update [0] from the queue and result in a no-op to PDT. But in the case of the DT you need the update to happen: it's a change past the flush. How do you reconcile this internally with only one queue?

In this case, DTU will only inspect updates after std::max(IndexDT, IndexPDT) and try to remove no-ops in that range.

Q: Why I choose this way, but not flush both trees when calling getDT/getPDT/flush?
A: In include/llvm/Support/GenericDomTree.h, comments of applyUpdates:

/// Batch updates should be generally faster when performing longer sequences
/// of updates than calling insertEdge/deleteEdge manually multiple times, as
/// it can reorder the updates and remove redundant ones internally.

It seems that there is performance gain. So I prefer to preserve a longer sequence of updates.

[NutshellySima]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

More info added to the above comment:
I think the only thing users of both DDT and DTU need to be careful is that they mustn't submit any updates that is already in the CFG + already known by the DT/PDT before submitting updates.
An example:

// Lazy DTU/DDT
// Edge A->B already in the CFG + DT knows that
DTU.insertEdge(A, B); // Get queued
... // delete A->B in the CFG
DTU.deleteEdge(A, B); // Cancel with the above one

This behavior is not supposed to be a functionality at least in DTU now. I'm not sure whether there are people using the DDT APIs like this.

[brzycki]

Hello @NutshellySima , comment are again inline.

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

Understood, you are pessimizing early removal of paired updates. I strongly recommend you testing your assumptions about performance of long updates using the CTMark option of test-suite to reduce the chance of reverts due to performance degradation:

cd path/to/cloned/test-suite
cmake ... \
    ... \
    -D TEST_SUITE_SUBDIRS=CTMark \
    -D TEST_SUITE_RUN_BENCHMARKS=0" \
    ... \
    $PWD

Note I recommend this in addition to regular test-suite runs designed to detect crashes and assert()s.

420 ↗

(On Diff #154220)

This behavior is not supposed to be a functionality at least in DTU now. I'm not sure whether there are people using the DDT APIs like this.

I can guarantee you this happens all over JumpThreading. The pass contains no information about prior state or previous failed attempts. I have seen cases where the same edge is inserted and removed 3 or more times across one complete run of the pass. There is a reason why I was forced to implement DDT with the default as Relaxed. :)

[NutshellySima]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

I understand the case when trying to inspect the CFG to remove the not really happened ones in jump-threading because it won't be queued and affect following updates.
And I'm thinking whether there is anyone submitting already happened and DT/PDT also knew ones.
I'm confused with your reply. In the example I mentioned (DT already got notified before that A->B exists but we still submit one {Insert, A, B})

// Lazy DTU/DDT
// Edge A->B already in the CFG + DT knows that
DTU.insertEdge(A, B); // Get queued {Insert, A, B}
... // delete A->B in the CFG
DTU.deleteEdge(A, B); // Cancel with the above one {Delete, A, B} cancels {Insert, A, B}
assert (DTU.getDT().verify()); // Asserts! (DT doesn't know A->B is gone!)

It can cause the state of DT not matching the state of the CFG.

420 ↗

(On Diff #154220)

Thanks for your advice.
But I doubt whether this test can show the performance degradation in the *current* LLVM codebase because
first, this behavior only affects

1. a DTU under Lazy UpdateStrategy with both DT and PDT
2. trying to perform a long sequence of updates

second, in the current LLVM codebase, only adce incrementally updates PDT with an extremely small update vector.

[brzycki]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

CTMark is a decent indicator of compile-time performance. It can help prevent patches being reverted due to compile-time benchmarks run by others. I understand that this specific case is not exercised by anything other than your test cases, but when you (or someone else) actually starts using it this will be invaluable to verifying your hypothesis.

420 ↗

(On Diff #154220)

The longer you defer a flush the higher the chance of seeing very strange updates and changes between the CFG and the state of DT. I cannot give you a specific example at this time but I do recall state changes just as you described. Here is one code path I am concerned about:

• JumpThreading::ProcessBlock() decides to split A into A -> A' with a single unconditional branch between them.
• The rest of ProcessBlock() is unable to thread the jump and exits with failure.
• Another, unrelated block Q is evaluated and ProcessBlock() successfully calls ThreadEdge(). With the SSA updates they added a DDT->flush() inside ThreadEdge() and would flush to DT. This patch is currently reverted, but can come back. It's also possible anyone can add a patch to add DDT->flush() on another call path under ProcessBlock().
• runImpl() comes back to processing A again and goes to the end of JumpThreading::runImpl(). It sees A has a single successor A' and calls TryToSimplifyUncondBranchFromEmptyBlock() which re-fuses A.

If you defer your updates across this entire set of changes you will see:

// CreateBB(A');
DTU.insertEdge(A, A');
// Give up on A
...
// Work on Q, call a flush() in ThreadEdge() or somehwere else under ProcessBlock()
...
// Back on A
DTU.deleteEdge(A, A');
DTU.deleteBB(A');

The interactions between JumpThreading, the state of the IR, the current state of the DT, and the state of pending DDT updates can lead to very complex states between them. You cannot safely assume no one will do updates that don't make sense or seem to be extra work. It's also why I added the Inversion check early on. For large functions detecting those early helped save a few percent of performance time. The more real world code you run through your algorithm will verify if your assumptions are valid.

420 ↗

(On Diff #154220)

Further comments on your hypothetical code:

// Lazy DTU/DDT
// Edge A->B already in the CFG + DT knows that
DTU.insertEdge(A, B); // Get queued {Insert, A, B}
... // delete A->B in the CFG
DTU.deleteEdge(A, B); // Cancel with the above one {Delete, A, B} cancels {Insert, A, B}
assert (DTU.getDT().verify()); // Asserts! (DT doesn't know A->B is gone!)

The reason I added the silent checks against the CFG were exactly because of cases like this. I don't remember if they were in ProcessBlock() or somewhere under Local.cpp (which is called less in the current implementation).

This is why applyUpdates checked things in a specific order:

1. do not enqueue duplicates within the ArrayRef. The call to applyUpdate() is expensive and if we can avoid 1 or 2 calls it's worth checking first.
2. Check edge state in the cfg and silent discard updates that don't reflect the current IR state
3. Check for duplicated update: discard. The internal queue might have the update that the batch call did not.
4. Check for the inverted update: discard both.

Every one of these checks I hit with code through JumpThreading and some of them are there to prevent assert() failures.

I hope this answers your concern and I apologize if I did not answer your question. I'm struggling a bit to understand why we may not be understanding each other.

[NutshellySima]

lib/Transforms/Scalar/JumpThreading.cpp

420 ↗

(On Diff #154220)

Thanks for your detailed explanation. I think now I understand your concern.
Now I understand it's safe do a full flush when aggressive pass like JumpThreading request flush, but it's not safe to do a partial flush because it's complex and it's hard to know whether there will be anyone doing updates that have side-effects and cancels with any update before flush(), which may cause a bug hard to find out and get fixed.
I'll look into whether there are ways to simplify the update method of DomTree in aggressive pass like JumpThreading these days.

[NutshellySima]

Marked as done because this problem should be addressed separately.
The problem:
Currently DTU assumes updates submitted after getDomTree()/getPostDomTree()/flush() won't affect the updates submitted before it.
More specifically, it assumes that the caller should not submit updates that already knew by the DT/PDT.
This problem can cause bugs when aggressive passes like jump-threading try to preserve PDT in the future.

[NutshellySima]

1. Address comments.
2. Replace previous raw DT operations into incremental updates to simplify logic.
3. Implement a simple unit-test for RemoveUnreachableBlocks.

[NutshellySima]

1. Amend comments.
2. Fix issues on clearing the successor list of DelBB.

[NutshellySima]

Fix minor issues.

[NutshellySima]

Fix minor issues.

[NutshellySima]

The patch converts passes and utils as the following
A. Pass Convertions

Eager (It's functionally equivalent)
DT/PDT.insertEdge/deleteEdge/applyUpdates -> DTU.insertEdge/deleteEdge/applyUpdates
Lazy
DDT.applyUpdates -> DTU.applyUpdates (because pass can control the UpdateStrategy it uses)
DDT.insert/deleteEdge -> DTU.insert/deleteEdgeRelaxed
DDT.pendingDeletedBB -> DTU.isBBPendingDeletion
DDT.flush -> DTU.getDomTree (DTU will auto-flush on destruction)
DDT.deleteBB -> DTU.deleteBB

B. Util Transforms
Despite transforms above,
a. DDT.applyUpdates is replaced with DTU.applyUpdates(..., /*ForceRemoveDuplicates*/ true) to make Eager Strategy DTU passed into can also do deduplication like DDT does.
b.

DDT.deleteBB(...);
DDT.applyUpdates(...);

is replaced with

... // Make sure the successor list of BB is cleared!
DTU.applyUpdates(..., /*ForceRemoveDuplicates*/ true);
DTU.deleteBB(BB);

c. Eager Strategy recalculation

DDT.deleteBB(BB);
DDT.recalculate(F);

is replaced with

DTU.deleteBB(BB, /*DisableNodeErasing*/)
DTU.recalculate(F);

d. All code not using the incremental update method is removed.
C. Unittest

1. Modify the unittest to check MergeBasicBlockIntoOnlyPred in Local.cpp (12 [2*3*2] patterns)

UpdateStrategy
a. Eager UpdateStrategy
b. Lazy UpdateStrategy
DT/PDT
a. only DT
b. only PDT
c. DT+PDT
IR
a. replace the Entry BB
b. does not replace entry BB

2. Modify the unittest for ConstantFoldTerminator to test both DT and PDT under Eager/Lazy UpdateStrategy.
3. Add a unittest for RemoveUnreachableBlocks to test DT and PDT under Eager/Lazy UpdateStrategy

[NutshellySima]

Now the utils after conversion is functionally equivalent with the current DDT implementation and I think the patch is ready.

[kuhar]

Thanks for the changes, Chijun!

@brzycki Can you please run run you test suites on this patch and confirm you don't see any new regressions? Chijun has only 2 weeks left until his GSoC and it would be best commit this as soon as possible, unless we discover some problems. Right now, like mentioned above, the patch is functionally equivalent to DDT and shouldn't cause any disruption.

Chijun developed 2 alternative abstractions that make the update code much cleaner in JT, but there won't be enough time to fully test it and commit by the end of his internship. Because of that, we decided to first be done with the transition to the unified interface which is the main artifact of his project.

[NutshellySima]

Remove the dependency of D49802

[brzycki]

LGTM. I like how this revision of the patch is minimally invasive and most of the hard work is hidden in DTU. I strongly recommend running ninja check, ninja check-all, and a standard test-suite run on tip before committing.

Thank you for your hard work and patience on refactoring this interface @NutshellySima .

[NutshellySima]

In D48967#1185987, @brzycki wrote:

LGTM. I like how this revision of the patch is minimally invasive and most of the hard work is hidden in DTU. I strongly recommend running ninja check, ninja check-all, and a standard test-suite run on tip before committing.

Thank you for your hard work and patience on refactoring this interface @NutshellySima .

Thanks for reviewing. I'll sure to test before committing.

[NutshellySima]

Fix a nit in Local.cpp of dealing with the TerminatorInst.

[NutshellySima]

Fix the IR that the entryBB cannot have any pred.

llvm/trunk/include/llvm/Transforms/Scalar/JumpThreading.h

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/ValueHandle.h"
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
 class BasicBlock;
 class BinaryOperator;
 class BranchInst;
 class CmpInst;
 class Constant;
-class DeferredDominance;
+class DomTreeUpdater;
 class Function;
 class Instruction;
 class IntrinsicInst;
 class LazyValueInfo;
 class LoadInst;
 class PHINode;
 class TargetLibraryInfo;
 class Value;

 ///   if (X < 3) {
 ///
 /// In this case, the unconditional branch at the end of the first if can be
 /// revectored to the false side of the second if.
 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   TargetLibraryInfo *TLI;
   LazyValueInfo *LVI;
   AliasAnalysis *AA;
-  DeferredDominance *DDT;
+  DomTreeUpdater *DTU;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = false;
   bool HasGuards = false;
 #ifdef NDEBUG
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
struct RecursionSetRemover {
     ~RecursionSetRemover() { TheSet.erase(ThePair); }
   };
 
 public:
   JumpThreadingPass(int T = -1);
 
   // Glue for old PM.
   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
-               AliasAnalysis *AA_, DeferredDominance *DDT_,
-               bool HasProfileData_, std::unique_ptr<BlockFrequencyInfo> BFI_,
+               AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
+               std::unique_ptr<BlockFrequencyInfo> BFI_,
                std::unique_ptr<BranchProbabilityInfo> BPI_);
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();
   }

llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h

 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
 
 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/InstrTypes.h"
 #include <cassert>
 
 namespace llvm {
 
 class BlockFrequencyInfo;
 class BranchProbabilityInfo;
-class DeferredDominance;
 class DominatorTree;
+class DomTreeUpdater;
 class Function;
 class Instruction;
 class LoopInfo;
 class MDNode;
 class MemoryDependenceResults;
 class ReturnInst;
 class TargetLibraryInfo;
 class Value;
 
 /// Delete the specified block, which must have no predecessors.
-void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr);
+void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr);
 
 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
 /// in it, fold them away. This handles the case when all entries to the PHI
 /// nodes in a block are guaranteed equal, such as when the block has exactly
 /// one predecessor.
 void FoldSingleEntryPHINodes(BasicBlock *BB,
                              MemoryDependenceResults *MemDep = nullptr);
 
 /// Examine each PHI in the given block and delete it if it is dead. Also
 /// recursively delete any operands that become dead as a result. This includes
 /// tracing the def-use list from the PHI to see if it is ultimately unused or
 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
 
 /// Attempts to merge a block into its predecessor, if possible. The return
 /// value indicates success or failure.
-bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
+bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
                                LoopInfo *LI = nullptr,
-                               MemoryDependenceResults *MemDep = nullptr,
-                               DeferredDominance *DDT = nullptr);
+                               MemoryDependenceResults *MemDep = nullptr);
 
 /// Replace all uses of an instruction (specified by BI) with a value, then
 /// remove and delete the original instruction.
 void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
                           BasicBlock::iterator &BI, Value *V);
 
 /// Replace the instruction specified by BI with the instruction specified by I.
 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The

llvm/trunk/include/llvm/Transforms/Utils/Local.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include <cstdint>

 /// into an unconditional branch to the constant destination.
 /// This is a nontrivial operation because the successors of this basic block
 /// must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
                             const TargetLibraryInfo *TLI = nullptr,
-                            DeferredDominance *DDT = nullptr);
+                            DomTreeUpdater *DTU = nullptr);
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
 //
 
 /// Return true if the result produced by the instruction is not used, and the
 /// instruction has no side effects.
 bool isInstructionTriviallyDead(Instruction *I,

 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
 /// nodes that collapse into identity values.  For example, if we have:
 ///   x = phi(1, 0, 0, 0)
 ///   y = and x, z
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the 'and' to 0.
 void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
-                                  DeferredDominance *DDT = nullptr);
+                                  DomTreeUpdater *DTU = nullptr);
 
 /// BB is a block with one predecessor and its predecessor is known to have one
 /// successor (BB!). Eliminate the edge between them, moving the instructions in
 /// the predecessor into BB. This deletes the predecessor block.
-void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr,
-                                 DeferredDominance *DDT = nullptr);
+void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU = nullptr);
 
 /// BB is known to contain an unconditional branch, and contains no instructions
 /// other than PHI nodes, potential debug intrinsics and the branch. If
 /// possible, eliminate BB by rewriting all the predecessors to branch to the
 /// successor block and return true. If we can't transform, return false.
 bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
-                                             DeferredDominance *DDT = nullptr);
+                                             DomTreeUpdater *DTU = nullptr);
 
 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
 /// to be clever about PHI nodes which differ only in the order of the incoming
 /// values, but instcombine orders them so it usually won't matter.
 bool EliminateDuplicatePHINodes(BasicBlock *BB);
 
 /// This function is used to do simplification of a CFG.  For example, it
 /// adjusts branches to branches to eliminate the extra hop, it eliminates

 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
                              bool PreserveLCSSA = false,
-                             DeferredDominance *DDT = nullptr);
+                             DomTreeUpdater *DTU = nullptr);
 
 /// Convert the CallInst to InvokeInst with the specified unwind edge basic
 /// block.  This also splits the basic block where CI is located, because
 /// InvokeInst is a terminator instruction.  Returns the newly split basic
 /// block.
 BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                              BasicBlock *UnwindEdge);
 
 /// Replace 'BB's terminator with one that does not have an unwind successor
 /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
 /// successor.
 ///
 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
-void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr);
+void removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
 /// Returns true if any basic block was removed.
 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
-                             DeferredDominance *DDT = nullptr);
+                             DomTreeUpdater *DTU = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.

llvm/trunk/lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
-#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
for (auto *Succ : RemovedSuccessors) {
       if (Succ != PreferredSucc->BB) {
         LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
                           << BB->getName() << " -> " << Succ->getName()
                           << "\n");
         DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
       }
     }
 
-    DT.applyUpdates(DeletedEdges);
-    PDT.applyUpdates(DeletedEdges);
+    DomTreeUpdater(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager)
+        .applyUpdates(DeletedEdges);
 
     NumBranchesRemoved += 1;
   }
 }
 
 // reverse top-sort order
 void AggressiveDeadCodeElimination::computeReversePostOrder() {
   // This provides a post-order numbering of the reverse control flow graph

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "correlated-value-propagation"
 
 STATISTIC(NumPhis,      "Number of phis propagated");

 /// Simplify a switch instruction by removing cases which can never fire. If the
 /// uselessness of a case could be determined locally then constant propagation
 /// would already have figured it out. Instead, walk the predecessors and
 /// statically evaluate cases based on information available on that edge. Cases
 /// that cannot fire no matter what the incoming edge can safely be removed. If
 /// a case fires on every incoming edge then the entire switch can be removed
 /// and replaced with a branch to the case destination.
 static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI, DominatorTree *DT) {
+  DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
   Value *Cond = SI->getCondition();
   BasicBlock *BB = SI->getParent();
 
   // If the condition was defined in same block as the switch then LazyValueInfo
   // currently won't say anything useful about it, though in theory it could.
   if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
     return false;
 
if (State == LazyValueInfo::False) {
 
       // The condition can be modified by removePredecessor's PHI simplification
       // logic.
       Cond = SI->getCondition();
 
       ++NumDeadCases;
       Changed = true;
       if (--SuccessorsCount[Succ] == 0)
-        DT->deleteEdge(BB, Succ);
+        DTU.deleteEdge(BB, Succ);
       continue;
     }
     if (State == LazyValueInfo::True) {
       // This case always fires.  Arrange for the switch to be turned into an
       // unconditional branch by replacing the switch condition with the case
       // value.
       SI->setCondition(Case);
       NumDeadCases += SI->getNumCases();
       Changed = true;
       break;
     }
 
     // Increment the case iterator since we didn't delete it.
     ++CI;
   }
 
-  if (Changed) {
+  if (Changed)
     // If the switch has been simplified to the point where it can be replaced
     // by a branch then do so now.
-    DeferredDominance DDT(*DT);
     ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
-                           /*TLI = */ nullptr, &DDT);
-    DDT.flush();
-  }
-
+                           /*TLI = */ nullptr, &DTU);
   return Changed;
 }
 
 // See if we can prove that the given overflow intrinsic will not overflow.
 static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI) {
   using OBO = OverflowingBinaryOperator;
   auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
     Value *RHS = II->getOperand(1);

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/VNCoercion.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <utility>
 #include <vector>
 
bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
   OrderedInstructions OrderedInstrs(DT);
   OI = &OrderedInstrs;
   VN.setMemDep(MD);
   ORE = RunORE;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
     BasicBlock *BB = &*FI++;
 
-    bool removedBlock = MergeBlockIntoPredecessor(BB, DT, LI, MD);
+    bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, MD);
     if (removedBlock)
       ++NumGVNBlocks;
 
     Changed |= removedBlock;
   }
 
   unsigned Iteration = 0;
   while (ShouldContinue) {

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"

 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <memory>
bool JumpThreading::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
   auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   // Get DT analysis before LVI. When LVI is initialized it conditionally adds
   // DT if it's available.
   auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
   auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-  DeferredDominance DDT(*DT);
+  DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = F.hasProfileData();
   if (HasProfileData) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = Impl.runImpl(F, TLI, LVI, AA, &DDT, HasProfileData,
+  bool Changed = Impl.runImpl(F, TLI, LVI, AA, &DTU, HasProfileData,
                               std::move(BFI), std::move(BPI));
   if (PrintLVIAfterJumpThreading) {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
     LVI->printLVI(F, *DT, dbgs());
   }
   return Changed;
 }
 
 PreservedAnalyses JumpThreadingPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   // Get DT analysis before LVI. When LVI is initialized it conditionally adds
   // DT if it's available.
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &LVI = AM.getResult<LazyValueAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
-  DeferredDominance DDT(DT);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   if (F.hasProfileData()) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = runImpl(F, &TLI, &LVI, &AA, &DDT, HasProfileData,
+  bool Changed = runImpl(F, &TLI, &LVI, &AA, &DTU, HasProfileData,
                          std::move(BFI), std::move(BPI));
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LazyValueAnalysis>();
   return PA;
 }
 
 bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
                                 LazyValueInfo *LVI_, AliasAnalysis *AA_,
-                                DeferredDominance *DDT_, bool HasProfileData_,
+                                DomTreeUpdater *DTU_, bool HasProfileData_,
                                 std::unique_ptr<BlockFrequencyInfo> BFI_,
                                 std::unique_ptr<BranchProbabilityInfo> BPI_) {
   LLVM_DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
   TLI = TLI_;
   LVI = LVI_;
   AA = AA_;
-  DDT = DDT_;
+  DTU = DTU_;
   BFI.reset();
   BPI.reset();
   // When profile data is available, we need to update edge weights after
   // successful jump threading, which requires both BPI and BFI being available.
   HasProfileData = HasProfileData_;
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
   if (HasProfileData) {
     BPI = std::move(BPI_);
     BFI = std::move(BFI_);
   }
 
   // JumpThreading must not processes blocks unreachable from entry. It's a
   // waste of compute time and can potentially lead to hangs.
   SmallPtrSet<BasicBlock *, 16> Unreachable;
-  DominatorTree &DT = DDT->flush();
+  assert(DTU && "DTU isn't passed into JumpThreading before using it.");
+  assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
+  DominatorTree &DT = DTU->getDomTree();
   for (auto &BB : F)
     if (!DT.isReachableFromEntry(&BB))
       Unreachable.insert(&BB);
 
   FindLoopHeaders(F);
 
   bool EverChanged = false;
   bool Changed;
   do {
     Changed = false;
     for (auto &BB : F) {
       if (Unreachable.count(&BB))
         continue;
       while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = true;
       // Stop processing BB if it's the entry or is now deleted. The following
       // routines attempt to eliminate BB and locating a suitable replacement
       // for the entry is non-trivial.
-      if (&BB == &F.getEntryBlock() || DDT->pendingDeletedBB(&BB))
+      if (&BB == &F.getEntryBlock() || DTU->isBBPendingDeletion(&BB))
         continue;
 
       if (pred_empty(&BB)) {
         // When ProcessBlock makes BB unreachable it doesn't bother to fix up
         // the instructions in it. We must remove BB to prevent invalid IR.
         LLVM_DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
                           << "' with terminator: " << *BB.getTerminator()
                           << '\n');
         LoopHeaders.erase(&BB);
         LVI->eraseBlock(&BB);
-        DeleteDeadBlock(&BB, DDT);
+        DeleteDeadBlock(&BB, DTU);
         Changed = true;
         continue;
       }
 
       // ProcessBlock doesn't thread BBs with unconditional TIs. However, if BB
       // is "almost empty", we attempt to merge BB with its sole successor.
       auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
       if (BI && BI->isUnconditional() &&
           // The terminator must be the only non-phi instruction in BB.
           BB.getFirstNonPHIOrDbg()->isTerminator() &&
           // Don't alter Loop headers and latches to ensure another pass can
           // detect and transform nested loops later.
           !LoopHeaders.count(&BB) && !LoopHeaders.count(BI->getSuccessor(0)) &&
-          TryToSimplifyUncondBranchFromEmptyBlock(&BB, DDT)) {
-        // BB is valid for cleanup here because we passed in DDT. F remains
-        // BB's parent until a DDT->flush() event.
+          TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU)) {
+        // BB is valid for cleanup here because we passed in DTU. F remains
+        // BB's parent until a DTU->getDomTree() event.
         LVI->eraseBlock(&BB);
         Changed = true;
       }
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
-  DDT->flush();
+  // Flush only the Dominator Tree.
+  DTU->getDomTree();
   LVI->enableDT();
   return EverChanged;
 }
 
 // Replace uses of Cond with ToVal when safe to do so. If all uses are
 // replaced, we can remove Cond. We cannot blindly replace all uses of Cond
 // because we may incorrectly replace uses when guards/assumes are uses of
 // of `Cond` and we used the guards/assume to reason about the `Cond` value
if (!I || I->getParent() != BB) {
     /// predecessor based on its terminator.
     //
     // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if
     // "I" is a non-local compare-with-a-constant instruction.  This would be
     // able to handle value inequalities better, for example if the compare is
     // "X < 4" and "X < 3" is known true but "X < 4" itself is not available.
     // Perhaps getConstantOnEdge should be smart enough to do this?
 
-    if (DDT->pending())
+    if (DTU->hasPendingDomTreeUpdates())
       LVI->disableDT();
     else
       LVI->enableDT();
     for (BasicBlock *P : predecessors(BB)) {
       // If the value is known by LazyValueInfo to be a constant in a
       // predecessor, use that information to try to thread this block.
       Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);
       if (Constant *KC = getKnownConstant(PredCst, Preference))
         Result.push_back(std::make_pair(KC, P));
     }
 
     return !Result.empty();
   }
 
   /// If I is a PHI node, then we know the incoming values for any constants.
   if (PHINode *PN = dyn_cast<PHINode>(I)) {
-    if (DDT->pending())
+    if (DTU->hasPendingDomTreeUpdates())
       LVI->disableDT();
     else
       LVI->enableDT();
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
       Value *InVal = PN->getIncomingValue(i);
       if (Constant *KC = getKnownConstant(InVal, Preference)) {
         Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i)));
       } else {
if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
 
     PHINode *PN = dyn_cast<PHINode>(CmpLHS);
     if (!PN)
       PN = dyn_cast<PHINode>(CmpRHS);
     if (PN && PN->getParent() == BB) {
       const DataLayout &DL = PN->getModule()->getDataLayout();
       // We can do this simplification if any comparisons fold to true or false.
       // See if any do.
-      if (DDT->pending())
+      if (DTU->hasPendingDomTreeUpdates())
         LVI->disableDT();
       else
         LVI->enableDT();
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         BasicBlock *PredBB = PN->getIncomingBlock(i);
         Value *LHS, *RHS;
         if (PN == CmpLHS) {
           LHS = PN->getIncomingValue(i);
if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
 
     // If comparing a live-in value against a constant, see if we know the
     // live-in value on any predecessors.
     if (isa<Constant>(CmpRHS) && !CmpType->isVectorTy()) {
       Constant *CmpConst = cast<Constant>(CmpRHS);
 
       if (!isa<Instruction>(CmpLHS) ||
           cast<Instruction>(CmpLHS)->getParent() != BB) {
-        if (DDT->pending())
+        if (DTU->hasPendingDomTreeUpdates())
           LVI->disableDT();
         else
           LVI->enableDT();
         for (BasicBlock *P : predecessors(BB)) {
           // If the value is known by LazyValueInfo to be a constant in a
           // predecessor, use that information to try to thread this block.
           LazyValueInfo::Tristate Res =
             LVI->getPredicateOnEdge(Pred, CmpLHS,
if (isa<Constant>(CmpRHS) && !CmpType->isVectorTy()) {
         using namespace PatternMatch;
 
         Value *AddLHS;
         ConstantInt *AddConst;
         if (isa<ConstantInt>(CmpConst) &&
             match(CmpLHS, m_Add(m_Value(AddLHS), m_ConstantInt(AddConst)))) {
           if (!isa<Instruction>(AddLHS) ||
               cast<Instruction>(AddLHS)->getParent() != BB) {
-            if (DDT->pending())
+            if (DTU->hasPendingDomTreeUpdates())
               LVI->disableDT();
             else
               LVI->enableDT();
             for (BasicBlock *P : predecessors(BB)) {
               // If the value is known by LazyValueInfo to be a ConstantRange in
               // a predecessor, use that information to try to thread this
               // block.
               ConstantRange CR = LVI->getConstantRangeOnEdge(
if ((TrueVal || FalseVal) &&
           Result.push_back(std::make_pair(Val, C.second));
       }
 
       return !Result.empty();
     }
   }
 
   // If all else fails, see if LVI can figure out a constant value for us.
-  if (DDT->pending())
+  if (DTU->hasPendingDomTreeUpdates())
     LVI->disableDT();
   else
     LVI->enableDT();
   Constant *CI = LVI->getConstant(V, BB, CxtI);
   if (Constant *KC = getKnownConstant(CI, Preference)) {
     for (BasicBlock *Pred : predecessors(BB))
       Result.push_back(std::make_pair(KC, Pred));
   }
static bool hasAddressTakenAndUsed(BasicBlock *BB) {
   return !BA->use_empty();
 }
 
 /// ProcessBlock - If there are any predecessors whose control can be threaded
 /// through to a successor, transform them now.
 bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
   // If the block is trivially dead, just return and let the caller nuke it.
   // This simplifies other transformations.
-  if (DDT->pendingDeletedBB(BB) ||
+  if (DTU->isBBPendingDeletion(BB) ||
       (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
     return false;
 
   // If this block has a single predecessor, and if that pred has a single
   // successor, merge the blocks.  This encourages recursive jump threading
   // because now the condition in this block can be threaded through
   // predecessors of our predecessor block.
   if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
     const TerminatorInst *TI = SinglePred->getTerminator();
     if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
         SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
       // If SinglePred was a loop header, BB becomes one.
       if (LoopHeaders.erase(SinglePred))
         LoopHeaders.insert(BB);
 
       LVI->eraseBlock(SinglePred);
-      MergeBasicBlockIntoOnlyPred(BB, nullptr, DDT);
+      MergeBasicBlockIntoOnlyPred(BB, DTU);
 
       // Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
       // BB code within one basic block `BB`), we need to invalidate the LVI
       // information associated with BB, because the LVI information need not be
       // true for all of BB after the merge. For example,
       // Before the merge, LVI info and code is as follows:
       // SinglePred: <LVI info1 for %p val>
       // %y = use of %p
for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
       Succ->removePredecessor(BB, true);
       Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
                       << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
-    DDT->applyUpdates(Updates);
+    DTU->applyUpdates(Updates);
     return true;
   }
 
   // If the terminator of this block is branching on a constant, simplify the
   // terminator to an unconditional branch.  This can occur due to threading in
   // other blocks.
   if (getKnownConstant(Condition, Preference)) {
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
                       << "' folding terminator: " << *BB->getTerminator()
                       << '\n');
     ++NumFolds;
-    ConstantFoldTerminator(BB, true, nullptr, DDT);
+    ConstantFoldTerminator(BB, true, nullptr, DTU);
     return true;
   }
 
   Instruction *CondInst = dyn_cast<Instruction>(Condition);
 
   // All the rest of our checks depend on the condition being an instruction.
   if (!CondInst) {
     // FIXME: Unify this with code below.
if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
     BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
     Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
     if (CondBr && CondConst) {
       // We should have returned as soon as we turn a conditional branch to
       // unconditional. Because its no longer interesting as far as jump
       // threading is concerned.
       assert(CondBr->isConditional() && "Threading on unconditional terminator");
 
-      if (DDT->pending())
+      if (DTU->hasPendingDomTreeUpdates())
         LVI->disableDT();
       else
         LVI->enableDT();
       LazyValueInfo::Tristate Ret =
         LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
                             CondConst, CondBr);
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
if (CondBr && CondConst) {
         // including the guards/assumes themselves and the uses before the
         // guard/assume.
         else if (CondCmp->getParent() == BB) {
           auto *CI = Ret == LazyValueInfo::True ?
             ConstantInt::getTrue(CondCmp->getType()) :
             ConstantInt::getFalse(CondCmp->getType());
           ReplaceFoldableUses(CondCmp, CI);
         }
-        DDT->deleteEdge(BB, ToRemoveSucc);
+        DTU->deleteEdgeRelaxed(BB, ToRemoveSucc);
         return true;
       }
 
       // We did not manage to simplify this branch, try to see whether
       // CondCmp depends on a known phi-select pattern.
       if (TryToUnfoldSelect(CondCmp, BB))
         return true;
     }
while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
       BranchInst::Create(KeepSucc, BI);
       BI->eraseFromParent();
-      DDT->deleteEdge(BB, RemoveSucc);
+      DTU->deleteEdgeRelaxed(BB, RemoveSucc);
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }
if (PredWithKnownDest == (size_t)pred_size(BB)) {
           Updates.push_back({DominatorTree::Delete, BB, SuccBB});
         }
       }
 
       // Finally update the terminator.
       TerminatorInst *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
-      DDT->applyUpdates(Updates);
+      DTU->applyUpdates(Updates);
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
         if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
           CondInst->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   }
 
   // And finally, do it!
   LLVM_DEBUG(dbgs() << "  Threading edge from '" << PredBB->getName()
                     << "' to '" << SuccBB->getName()
                     << "' with cost: " << JumpThreadCost
                     << ", across block:\n    " << *BB << "\n");
 
-  if (DDT->pending())
+  if (DTU->hasPendingDomTreeUpdates())
     LVI->disableDT();
   else
     LVI->enableDT();
   LVI->threadEdge(PredBB, BB, SuccBB);
 
   // We are going to have to map operands from the original BB block to the new
   // copy of the block 'NewBB'.  If there are PHI nodes in BB, evaluate them to
   // account for entry from PredBB.
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   TerminatorInst *PredTerm = PredBB->getTerminator();
   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
     if (PredTerm->getSuccessor(i) == BB) {
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
   // Enqueue required DT updates.
-  DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
+  DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
                      {DominatorTree::Insert, PredBB, NewBB},
                      {DominatorTree::Delete, PredBB, BB}});
 
   // If there were values defined in BB that are used outside the block, then we
   // now have to update all uses of the value to use either the original value,
   // the cloned value, or some PHI derived value.  This can require arbitrary
   // PHI insertion, of which we are prepared to do, clean these up now.
   SSAUpdater SSAUpdate;
for (auto Pred : predecessors(NewBB)) {
       Updates.push_back({DominatorTree::Insert, Pred, NewBB});
       if (HasProfileData) // Update frequencies between Pred -> NewBB.
         NewBBFreq += FreqMap.lookup(Pred);
     }
     if (HasProfileData) // Apply the summed frequency to NewBB.
       BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
   }
 
-  DDT->applyUpdates(Updates);
+  DTU->applyUpdates(Updates);
   return NewBBs[0];
 }
 
 bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
   const TerminatorInst *TI = BB->getTerminator();
   assert(TI->getNumSuccessors() > 1 && "not a split");
 
   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   }
 
   // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
   // that we nuked.
   BB->removePredecessor(PredBB, true);
 
   // Remove the unconditional branch at the end of the PredBB block.
   OldPredBranch->eraseFromParent();
-  DDT->applyUpdates(Updates);
+  DTU->applyUpdates(Updates);
 
   ++NumDupes;
   return true;
 }
 
 /// TryToUnfoldSelect - Look for blocks of the form
 /// bb1:
 ///   %a = select
for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
 
     BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
     if (!PredTerm || !PredTerm->isUnconditional())
       continue;
 
     // Now check if one of the select values would allow us to constant fold the
     // terminator in BB. We don't do the transform if both sides fold, those
     // cases will be threaded in any case.
-    if (DDT->pending())
+    if (DTU->hasPendingDomTreeUpdates())
       LVI->disableDT();
     else
       LVI->enableDT();
     LazyValueInfo::Tristate LHSFolds =
         LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),
                                 CondRHS, Pred, BB, CondCmp);
     LazyValueInfo::Tristate RHSFolds =
         LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),
if ((LHSFolds != LazyValueInfo::Unknown ||
       NewBB->getInstList().insert(NewBB->end(), PredTerm);
       // Create a conditional branch and update PHI nodes.
       BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
       CondLHS->setIncomingValue(I, SI->getFalseValue());
       CondLHS->addIncoming(SI->getTrueValue(), NewBB);
       // The select is now dead.
       SI->eraseFromParent();
 
-      DDT->applyUpdates({{DominatorTree::Insert, NewBB, BB},
+      DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB},
                          {DominatorTree::Insert, Pred, NewBB}});
       // Update any other PHI nodes in BB.
       for (BasicBlock::iterator BI = BB->begin();
            PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
         if (Phi != CondLHS)
           Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
       return true;
     }
for (BasicBlock::iterator BI = BB->begin();
     SI->replaceAllUsesWith(NewPN);
     SI->eraseFromParent();
     // NewBB and SplitBB are newly created blocks which require insertion.
     std::vector<DominatorTree::UpdateType> Updates;
     Updates.reserve((2 * SplitBB->getTerminator()->getNumSuccessors()) + 3);
     Updates.push_back({DominatorTree::Insert, BB, SplitBB});
     Updates.push_back({DominatorTree::Insert, BB, NewBB});
     Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
-    // BB's successors were moved to SplitBB, update DDT accordingly.
+    // BB's successors were moved to SplitBB, update DTU accordingly.
     for (auto *Succ : successors(SplitBB)) {
       Updates.push_back({DominatorTree::Delete, BB, Succ});
       Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
     }
-    DDT->applyUpdates(Updates);
+    DTU->applyUpdates(Updates);
     return true;
   }
   return false;
 }
 
 /// Try to propagate a guard from the current BB into one of its predecessors
 /// in case if another branch of execution implies that the condition of this
 /// guard is always true. Currently we only process the simplest case that
bool JumpThreadingPass::ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard,
   BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween(
       BB, PredUnguardedBlock, Guard, UnguardedMapping);
   assert(UnguardedBlock && "Could not create the unguarded block?");
   LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
                     << GuardedBlock->getName() << "\n");
   // DuplicateInstructionsInSplitBetween inserts a new block "BB.split" between
   // PredBB and BB. We need to perform two inserts and one delete for each of
   // the above calls to update Dominators.
-  DDT->applyUpdates(
+  DTU->applyUpdates(
       {// Guarded block split.
        {DominatorTree::Delete, PredGuardedBlock, BB},
        {DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
        {DominatorTree::Insert, GuardedBlock, BB},
        // Unguarded block split.
        {DominatorTree::Delete, PredUnguardedBlock, BB},
        {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
        {DominatorTree::Insert, UnguardedBlock, BB}});

llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplifycfg"
 
 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
                             ScalarEvolution &SE) {
   bool Changed = false;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Copy blocks into a temporary array to avoid iterator invalidation issues
   // as we remove them.
   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
 
   for (auto &Block : Blocks) {
     // Attempt to merge blocks in the trivial case. Don't modify blocks which
     // belong to other loops.
     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
     if (!Succ)
       continue;
 
     BasicBlock *Pred = Succ->getSinglePredecessor();
     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
       continue;
 
     // Merge Succ into Pred and delete it.
-    MergeBlockIntoPredecessor(Succ, &DT, &LI);
+    MergeBlockIntoPredecessor(Succ, &DTU, &LI);
 
     SE.forgetLoop(&L);
     Changed = true;
   }
 
   return Changed;
 }
 

llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <set>
 #include <string>
if (ImmutableCallSite CS = ImmutableCallSite(&I))
       return !callsGCLeafFunction(CS, TLI) && !isStatepoint(CS);
     return false;
   };
 
 
   // Delete any unreachable statepoints so that we don't have unrewritten
   // statepoints surviving this pass.  This makes testing easier and the
   // resulting IR less confusing to human readers.
-  DeferredDominance DD(DT);
-  bool MadeChange = removeUnreachableBlocks(F, nullptr, &DD);
-  DD.flush();
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  bool MadeChange = removeUnreachableBlocks(F, nullptr, &DTU);
+  // Flush the Dominator Tree.
+  DTU.getDomTree();
 
   // Gather all the statepoints which need rewritten.  Be careful to only
   // consider those in reachable code since we need to ask dominance queries
   // when rewriting.  We'll delete the unreachable ones in a moment.
   SmallVector<CallSite, 64> ParsePointNeeded;
   for (Instruction &I : instructions(F)) {
     // TODO: only the ones with the flag set!
     if (NeedsRewrite(I)) {

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
-#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <cassert>
 #include <cstdint>
 #include <string>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
-void llvm::DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT) {
+void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU) {
   assert((pred_begin(BB) == pred_end(BB) ||
          // Can delete self loop.
          BB->getSinglePredecessor() == BB) && "Block is not dead!");
   TerminatorInst *BBTerm = BB->getTerminator();
   std::vector<DominatorTree::UpdateType> Updates;
 
   // Loop through all of our successors and make sure they know that one
   // of their predecessors is going away.
-  if (DDT)
+  if (DTU)
     Updates.reserve(BBTerm->getNumSuccessors());
   for (BasicBlock *Succ : BBTerm->successors()) {
     Succ->removePredecessor(BB);
-    if (DDT)
+    if (DTU)
       Updates.push_back({DominatorTree::Delete, BB, Succ});
   }
 
   // Zap all the instructions in the block.
   while (!BB->empty()) {
     Instruction &I = BB->back();
     // If this instruction is used, replace uses with an arbitrary value.
     // Because control flow can't get here, we don't care what we replace the
     // value with.  Note that since this block is unreachable, and all values
     // contained within it must dominate their uses, that all uses will
     // eventually be removed (they are themselves dead).
     if (!I.use_empty())
       I.replaceAllUsesWith(UndefValue::get(I.getType()));
     BB->getInstList().pop_back();
   }
-
-  if (DDT) {
-    DDT->applyUpdates(Updates);
-    DDT->deleteBB(BB); // Deferred deletion of BB.
+  new UnreachableInst(BB->getContext(), BB);
+  assert(BB->getInstList().size() == 1 &&
+         isa<UnreachableInst>(BB->getTerminator()) &&
+         "The successor list of BB isn't empty before "
+         "applying corresponding DTU updates.");
+
+  if (DTU) {
+    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->deleteBB(BB);
   } else {
     BB->eraseFromParent(); // Zap the block!
   }
 }
 
 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
                                    MemoryDependenceResults *MemDep) {
   if (!isa<PHINode>(BB->begin())) return;
bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) {
   bool Changed = false;
   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
       Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
 
   return Changed;
 }
 
-bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
+bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
                                      LoopInfo *LI,
-                                     MemoryDependenceResults *MemDep,
-                                     DeferredDominance *DDT) {
-  assert(!(DT && DDT) && "Cannot call with both DT and DDT.");
+                                     MemoryDependenceResults *MemDep) {
 
   if (BB->hasAddressTaken())
     return false;
 
   // Can't merge if there are multiple predecessors, or no predecessors.
   BasicBlock *PredBB = BB->getUniquePredecessor();
   if (!PredBB) return false;
 
bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
   if (isa<PHINode>(BB->front())) {
     for (PHINode &PN : BB->phis())
       if (!isa<PHINode>(PN.getIncomingValue(0)) ||
           cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
         IncomingValues.push_back(PN.getIncomingValue(0));
     FoldSingleEntryPHINodes(BB, MemDep);
   }
 
-  // Deferred DT update: Collect all the edges that exit BB. These
-  // dominator edges will be redirected from Pred.
+  // DTU update: Collect all the edges that exit BB.
+  // These dominator edges will be redirected from Pred.
   std::vector<DominatorTree::UpdateType> Updates;
-  if (DDT) {
+  if (DTU) {
     Updates.reserve(1 + (2 * succ_size(BB)));
     Updates.push_back({DominatorTree::Delete, PredBB, BB});
     for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
       Updates.push_back({DominatorTree::Delete, BB, *I});
       Updates.push_back({DominatorTree::Insert, PredBB, *I});
     }
   }
 
   // Delete the unconditional branch from the predecessor...
   PredBB->getInstList().pop_back();
 
   // Make all PHI nodes that referred to BB now refer to Pred as their
   // source...
   BB->replaceAllUsesWith(PredBB);
 
   // Move all definitions in the successor to the predecessor...
   PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
+  new UnreachableInst(BB->getContext(), BB);
 
   // Eliminate duplicate dbg.values describing the entry PHI node post-splice.
   for (auto Incoming : IncomingValues) {
     if (isa<Instruction>(*Incoming)) {
       SmallVector<DbgValueInst *, 2> DbgValues;
       SmallDenseSet<std::pair<DILocalVariable *, DIExpression *>, 2>
           DbgValueSet;
       llvm::findDbgValues(DbgValues, Incoming);
       for (auto &DVI : DbgValues) {
         auto R = DbgValueSet.insert({DVI->getVariable(), DVI->getExpression()});
         if (!R.second)
           DVI->eraseFromParent();
       }
     }
   }
 
   // Inherit predecessors name if it exists.
   if (!PredBB->hasName())
     PredBB->takeName(BB);
 
-  // Finally, erase the old block and update dominator info.
-  if (DT)
-    if (DomTreeNode *DTN = DT->getNode(BB)) {
-      DomTreeNode *PredDTN = DT->getNode(PredBB);
-      SmallVector<DomTreeNode *, 8> Children(DTN->begin(), DTN->end());
-      for (DomTreeNode *DI : Children)
-        DT->changeImmediateDominator(DI, PredDTN);
-
-      DT->eraseNode(BB);
-    }
-
   if (LI)
     LI->removeBlock(BB);
 
   if (MemDep)
     MemDep->invalidateCachedPredecessors();
 
-  if (DDT) {
-    DDT->deleteBB(BB); // Deferred deletion of BB.
-    DDT->applyUpdates(Updates);
-  } else {
-    BB->eraseFromParent(); // Nuke BB.
+  // Finally, erase the old block and update dominator info.
+  if (DTU) {
+    assert(BB->getInstList().size() == 1 &&
+           isa<UnreachableInst>(BB->getTerminator()) &&
+           "The successor list of BB isn't empty before "
+           "applying corresponding DTU updates.");
+    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->deleteBB(BB);
+  }
+
+  else {
+    BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
   }
   return true;
 }
 
 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
                                 BasicBlock::iterator &BI, Value *V) {
   Instruction &I = *BI;
   // Replaces all of the uses of the instruction with uses of the value

llvm/trunk/lib/Transforms/Utils/Local.cpp

 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"

 /// constant value, convert it into an unconditional branch to the constant
 /// destination.  This is a nontrivial operation because the successors of this
 /// basic block must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
                                   const TargetLibraryInfo *TLI,
-                                  DeferredDominance *DDT) {
+                                  DomTreeUpdater *DTU) {
   TerminatorInst *T = BB->getTerminator();
   IRBuilder<> Builder(T);
 
   // Branch - See if we are conditional jumping on constant
   if (auto *BI = dyn_cast<BranchInst>(T)) {
     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
     BasicBlock *Dest1 = BI->getSuccessor(0);
     BasicBlock *Dest2 = BI->getSuccessor(1);
 
     if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
       // Are we branching on constant?
       // YES.  Change to unconditional branch...
       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
 
       // Let the basic block know that we are letting go of it.  Based on this,
       // it will adjust it's PHI nodes.
       OldDest->removePredecessor(BB);
 
       // Replace the conditional branch with an unconditional one.
       Builder.CreateBr(Destination);
       BI->eraseFromParent();
-      if (DDT)
-        DDT->deleteEdge(BB, OldDest);
+      if (DTU)
+        DTU->deleteEdgeRelaxed(BB, OldDest);
       return true;
     }
 
     if (Dest2 == Dest1) {       // Conditional branch to same location?
       // This branch matches something like this:
       //     br bool %cond, label %Dest, label %Dest
       // and changes it into:  br label %Dest
 
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
                           MDBuilder(BB->getContext()).
                           createBranchWeights(Weights));
         }
         // Remove this entry.
         BasicBlock *ParentBB = SI->getParent();
         DefaultDest->removePredecessor(ParentBB);
         i = SI->removeCase(i);
         e = SI->case_end();
-        if (DDT)
-          DDT->deleteEdge(ParentBB, DefaultDest);
+        if (DTU)
+          DTU->deleteEdgeRelaxed(ParentBB, DefaultDest);
         continue;
       }
 
       // Otherwise, check to see if the switch only branches to one destination.
       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
       // destinations.
       if (i->getCaseSuccessor() != TheOnlyDest)
         TheOnlyDest = nullptr;
if (auto *SI = dyn_cast<SwitchInst>(T)) {
 
     // If we found a single destination that we can fold the switch into, do so
     // now.
     if (TheOnlyDest) {
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
       BasicBlock *BB = SI->getParent();
       std::vector <DominatorTree::UpdateType> Updates;
-      if (DDT)
+      if (DTU)
         Updates.reserve(SI->getNumSuccessors() - 1);
 
       // Remove entries from PHI nodes which we no longer branch to...
       for (BasicBlock *Succ : SI->successors()) {
         // Found case matching a constant operand?
         if (Succ == TheOnlyDest) {
           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
         } else {
           Succ->removePredecessor(BB);
-          if (DDT)
+          if (DTU)
             Updates.push_back({DominatorTree::Delete, BB, Succ});
         }
       }
 
       // Delete the old switch.
       Value *Cond = SI->getCondition();
       SI->eraseFromParent();
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
-      if (DDT)
-        DDT->applyUpdates(Updates);
+      if (DTU)
+        DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
       return true;
     }
 
     if (SI->getNumCases() == 1) {
       // Otherwise, we can fold this switch into a conditional branch
       // instruction if it has only one non-default destination.
       auto FirstCase = *SI->case_begin();
       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
   }
 
   if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
     // indirectbr blockaddress(@F, @BB) -> br label @BB
     if (auto *BA =
           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
       BasicBlock *TheOnlyDest = BA->getBasicBlock();
       std::vector <DominatorTree::UpdateType> Updates;
-      if (DDT)
+      if (DTU)
         Updates.reserve(IBI->getNumDestinations() - 1);
 
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
 
       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
         if (IBI->getDestination(i) == TheOnlyDest) {
           TheOnlyDest = nullptr;
         } else {
           BasicBlock *ParentBB = IBI->getParent();
           BasicBlock *DestBB = IBI->getDestination(i);
           DestBB->removePredecessor(ParentBB);
-          if (DDT)
+          if (DTU)
             Updates.push_back({DominatorTree::Delete, ParentBB, DestBB});
         }
       }
       Value *Address = IBI->getAddress();
       IBI->eraseFromParent();
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
 
       // If we didn't find our destination in the IBI successor list, then we
       // have undefined behavior.  Replace the unconditional branch with an
       // 'unreachable' instruction.
       if (TheOnlyDest) {
         BB->getTerminator()->eraseFromParent();
         new UnreachableInst(BB->getContext(), BB);
       }
 
-      if (DDT)
-        DDT->applyUpdates(Updates);
+      if (DTU)
+        DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
       return true;
     }
   }
 
   return false;
 }
 
 //===----------------------------------------------------------------------===//

 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
 /// nodes that collapse into identity values.  For example, if we have:
 ///   x = phi(1, 0, 0, 0)
 ///   y = and x, z
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the and to 0.
 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
-                                        DeferredDominance *DDT) {
+                                        DomTreeUpdater *DTU) {
   // This only adjusts blocks with PHI nodes.
   if (!isa<PHINode>(BB->begin()))
     return;
 
   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
   // them down.  This will leave us with single entry phi nodes and other phis
   // that can be removed.
   BB->removePredecessor(Pred, true);
 
   WeakTrackingVH PhiIt = &BB->front();
   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
     Value *OldPhiIt = PhiIt;
 
     if (!recursivelySimplifyInstruction(PN))
       continue;
 
     // If recursive simplification ended up deleting the next PHI node we would
     // iterate to, then our iterator is invalid, restart scanning from the top
     // of the block.
     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
   }
-  if (DDT)
-    DDT->deleteEdge(Pred, BB);
+  if (DTU)
+    DTU->deleteEdgeRelaxed(Pred, BB);
 }
 
 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
-void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT,
-                                       DeferredDominance *DDT) {
-  assert(!(DT && DDT) && "Cannot call with both DT and DDT.");
+void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
+                                       DomTreeUpdater *DTU) {
 
   // If BB has single-entry PHI nodes, fold them.
   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
     Value *NewVal = PN->getIncomingValue(0);
     // Replace self referencing PHI with undef, it must be dead.
     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
     PN->replaceAllUsesWith(NewVal);
     PN->eraseFromParent();
   }
 
   BasicBlock *PredBB = DestBB->getSinglePredecessor();
   assert(PredBB && "Block doesn't have a single predecessor!");
 
   bool ReplaceEntryBB = false;
   if (PredBB == &DestBB->getParent()->getEntryBlock())
     ReplaceEntryBB = true;
 
-  // Deferred DT update: Collect all the edges that enter PredBB. These
-  // dominator edges will be redirected to DestBB.
+  // DTU updates: Collect all the edges that enter
+  // PredBB. These dominator edges will be redirected to DestBB.
   std::vector <DominatorTree::UpdateType> Updates;
-  if (DDT && !ReplaceEntryBB) {
+
+  if (DTU) {
     Updates.reserve(1 + (2 * pred_size(PredBB)));
     Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
     for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
       Updates.push_back({DominatorTree::Delete, *I, PredBB});
       // This predecessor of PredBB may already have DestBB as a successor.
       if (llvm::find(successors(*I), DestBB) == succ_end(*I))
         Updates.push_back({DominatorTree::Insert, *I, DestBB});
     }
void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
   }
 
   // Anything that branched to PredBB now branches to DestBB.
   PredBB->replaceAllUsesWith(DestBB);
 
   // Splice all the instructions from PredBB to DestBB.
   PredBB->getTerminator()->eraseFromParent();
   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
+  new UnreachableInst(PredBB->getContext(), PredBB);
 
   // If the PredBB is the entry block of the function, move DestBB up to
   // become the entry block after we erase PredBB.
   if (ReplaceEntryBB)
     DestBB->moveAfter(PredBB);
 
-  if (DT) {
-    // For some irreducible CFG we end up having forward-unreachable blocks
-    // so check if getNode returns a valid node before updating the domtree.
-    if (DomTreeNode *DTN = DT->getNode(PredBB)) {
-      BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();
-      DT->changeImmediateDominator(DestBB, PredBBIDom);
-      DT->eraseNode(PredBB);
+  if (DTU) {
+    assert(PredBB->getInstList().size() == 1 &&
+           isa<UnreachableInst>(PredBB->getTerminator()) &&
+           "The successor list of PredBB isn't empty before "
+           "applying corresponding DTU updates.");
+    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->deleteBB(PredBB);
+    // Recalculation of DomTree is needed when updating a forward DomTree and
+    // the Entry BB is replaced.
+    if (ReplaceEntryBB && DTU->hasDomTree()) {
+      // The entry block was removed and there is no external interface for
+      // the dominator tree to be notified of this change. In this corner-case
+      // we recalculate the entire tree.
+      DTU->recalculate(*(DestBB->getParent()));
     }
   }
 
-  if (DDT) {
-    DDT->deleteBB(PredBB); // Deferred deletion of BB.
-    if (ReplaceEntryBB)
-      // The entry block was removed and there is no external interface for the
-      // dominator tree to be notified of this change. In this corner-case we
-      // recalculate the entire tree.
-      DDT->recalculate(*(DestBB->getParent()));
-    else
-      DDT->applyUpdates(Updates);
-  } else {
-    PredBB->eraseFromParent(); // Nuke BB.
+  else {
+    PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
   }
 }
 
 /// CanMergeValues - Return true if we can choose one of these values to use
 /// in place of the other. Note that we will always choose the non-undef
 /// value to keep.
 static bool CanMergeValues(Value *First, Value *Second) {
   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);

 }
 
 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
 /// unconditional branch, and contains no instructions other than PHI nodes,
 /// potential side-effect free intrinsics and the branch.  If possible,
 /// eliminate BB by rewriting all the predecessors to branch to the successor
 /// block and return true.  If we can't transform, return false.
 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
-                                                   DeferredDominance *DDT) {
+                                                   DomTreeUpdater *DTU) {
   assert(BB != &BB->getParent()->getEntryBlock() &&
          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
 
   // We can't eliminate infinite loops.
   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
   if (BB == Succ) return false;
 
   // Check to see if merging these blocks would cause conflicts for any of the
while (isa<PHINode>(*BBI)) {
       }
       ++BBI;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
   std::vector<DominatorTree::UpdateType> Updates;
-  if (DDT) {
+  if (DTU) {
     Updates.reserve(1 + (2 * pred_size(BB)));
     Updates.push_back({DominatorTree::Delete, BB, Succ});
     // All predecessors of BB will be moved to Succ.
     for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
       Updates.push_back({DominatorTree::Delete, *I, BB});
       // This predecessor of BB may already have Succ as a successor.
       if (llvm::find(successors(*I), Succ) == succ_end(*I))
         Updates.push_back({DominatorTree::Insert, *I, Succ});
if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
         BasicBlock *Pred = *PI;
         Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
       }
 
   // Everything that jumped to BB now goes to Succ.
   BB->replaceAllUsesWith(Succ);
   if (!Succ->hasName()) Succ->takeName(BB);
 
-  if (DDT) {
-    DDT->deleteBB(BB); // Deferred deletion of the old basic block.
-    DDT->applyUpdates(Updates);
+  // Clear the successor list of BB to match updates applying to DTU later.
+  if (BB->getTerminator())
+    BB->getInstList().pop_back();
+  new UnreachableInst(BB->getContext(), BB);
+  assert(succ_empty(BB) && "The successor list of BB isn't empty before "
+                           "applying corresponding DTU updates.");
+
+  if (DTU) {
+    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->deleteBB(BB);
   } else {
     BB->eraseFromParent(); // Delete the old basic block.
   }
   return true;
 }
 
 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
 /// nodes in this block. This doesn't try to be clever about PHI nodes
while (EndInst != &BB->front()) {
     if (!isa<DbgInfoIntrinsic>(Inst))
       ++NumDeadInst;
     Inst->eraseFromParent();
   }
   return NumDeadInst;
 }
 
 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                                   bool PreserveLCSSA, DeferredDominance *DDT) {
+                                   bool PreserveLCSSA, DomTreeUpdater *DTU) {
   BasicBlock *BB = I->getParent();
   std::vector <DominatorTree::UpdateType> Updates;
 
   // Loop over all of the successors, removing BB's entry from any PHI
   // nodes.
-  if (DDT)
+  if (DTU)
     Updates.reserve(BB->getTerminator()->getNumSuccessors());
   for (BasicBlock *Successor : successors(BB)) {
     Successor->removePredecessor(BB, PreserveLCSSA);
-    if (DDT)
+    if (DTU)
       Updates.push_back({DominatorTree::Delete, BB, Successor});
   }
   // Insert a call to llvm.trap right before this.  This turns the undefined
   // behavior into a hard fail instead of falling through into random code.
   if (UseLLVMTrap) {
     Function *TrapFn =
       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
     CallTrap->setDebugLoc(I->getDebugLoc());
   }
   new UnreachableInst(I->getContext(), I);
 
   // All instructions after this are dead.
   unsigned NumInstrsRemoved = 0;
   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
   while (BBI != BBE) {
     if (!BBI->use_empty())
       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
     BB->getInstList().erase(BBI++);
     ++NumInstrsRemoved;
   }
-  if (DDT)
-    DDT->applyUpdates(Updates);
+  if (DTU)
+    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
   return NumInstrsRemoved;
 }
 
 /// changeToCall - Convert the specified invoke into a normal call.
-static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) {
+static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
   SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
   SmallVector<OperandBundleDef, 1> OpBundles;
   II->getOperandBundlesAsDefs(OpBundles);
   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
                                        "", II);
   NewCall->takeName(II);
   NewCall->setCallingConv(II->getCallingConv());
   NewCall->setAttributes(II->getAttributes());
   NewCall->setDebugLoc(II->getDebugLoc());
   II->replaceAllUsesWith(NewCall);
 
   // Follow the call by a branch to the normal destination.
   BasicBlock *NormalDestBB = II->getNormalDest();
   BranchInst::Create(NormalDestBB, II);
 
   // Update PHI nodes in the unwind destination
   BasicBlock *BB = II->getParent();
   BasicBlock *UnwindDestBB = II->getUnwindDest();
   UnwindDestBB->removePredecessor(BB);
   II->eraseFromParent();
-  if (DDT)
-    DDT->deleteEdge(BB, UnwindDestBB);
+  if (DTU)
+    DTU->deleteEdgeRelaxed(BB, UnwindDestBB);
 }
 
 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                    BasicBlock *UnwindEdge) {
   BasicBlock *BB = CI->getParent();
 
   // Convert this function call into an invoke instruction.  First, split the
   // basic block.
BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
   CI->replaceAllUsesWith(II);
 
   // Delete the original call
   Split->getInstList().pop_front();
   return Split;
 }
 
 static bool markAliveBlocks(Function &F,
-                            SmallPtrSetImpl<BasicBlock*> &Reachable,
-                            DeferredDominance *DDT = nullptr) {
+                            SmallPtrSetImpl<BasicBlock *> &Reachable,
+                            DomTreeUpdater *DTU = nullptr) {
   SmallVector<BasicBlock*, 128> Worklist;
   BasicBlock *BB = &F.front();
   Worklist.push_back(BB);
   Reachable.insert(BB);
   bool Changed = false;
   do {
     BB = Worklist.pop_back_val();
 
     // Do a quick scan of the basic block, turning any obviously unreachable
     // instructions into LLVM unreachable insts.  The instruction combining pass
     // canonicalizes unreachable insts into stores to null or undef.
     for (Instruction &I : *BB) {
       if (auto *CI = dyn_cast<CallInst>(&I)) {
         Value *Callee = CI->getCalledValue();
         // Handle intrinsic calls.
         if (Function *F = dyn_cast<Function>(Callee)) {
           auto IntrinsicID = F->getIntrinsicID();
           // Assumptions that are known to be false are equivalent to
           // unreachable. Also, if the condition is undefined, then we make the
           // choice most beneficial to the optimizer, and choose that to also be
           // unreachable.
           if (IntrinsicID == Intrinsic::assume) {
             if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
               // Don't insert a call to llvm.trap right before the unreachable.
-              changeToUnreachable(CI, false, false, DDT);
+              changeToUnreachable(CI, false, false, DTU);
               Changed = true;
               break;
             }
           } else if (IntrinsicID == Intrinsic::experimental_guard) {
             // A call to the guard intrinsic bails out of the current
             // compilation unit if the predicate passed to it is false. If the
             // predicate is a constant false, then we know the guard will bail
             // out of the current compile unconditionally, so all code following
             // it is dead.
             //
             // Note: unlike in llvm.assume, it is not "obviously profitable" for
             // guards to treat `undef` as `false` since a guard on `undef` can
             // still be useful for widening.
             if (match(CI->getArgOperand(0), m_Zero()))
               if (!isa<UnreachableInst>(CI->getNextNode())) {
                 changeToUnreachable(CI->getNextNode(), /*UseLLVMTrap=*/false,
-                                    false, DDT);
+                                    false, DTU);
                 Changed = true;
                 break;
               }
           }
         } else if ((isa<ConstantPointerNull>(Callee) &&
                     !NullPointerIsDefined(CI->getFunction())) ||
                    isa<UndefValue>(Callee)) {
-          changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT);
+          changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DTU);
           Changed = true;
           break;
         }
         if (CI->doesNotReturn()) {
           // If we found a call to a no-return function, insert an unreachable
           // instruction after it.  Make sure there isn't *already* one there
           // though.
           if (!isa<UnreachableInst>(CI->getNextNode())) {
             // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(CI->getNextNode(), false, false, DDT);
+            changeToUnreachable(CI->getNextNode(), false, false, DTU);
             Changed = true;
           }
           break;
         }
       } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
         // Store to undef and store to null are undefined and used to signal
         // that they should be changed to unreachable by passes that can't
         // modify the CFG.
 
         // Don't touch volatile stores.
         if (SI->isVolatile()) continue;
 
         Value *Ptr = SI->getOperand(1);
 
         if (isa<UndefValue>(Ptr) ||
             (isa<ConstantPointerNull>(Ptr) &&
              !NullPointerIsDefined(SI->getFunction(),
                                    SI->getPointerAddressSpace()))) {
-          changeToUnreachable(SI, true, false, DDT);
+          changeToUnreachable(SI, true, false, DTU);
           Changed = true;
           break;
         }
       }
     }
 
     TerminatorInst *Terminator = BB->getTerminator();
     if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
       // Turn invokes that call 'nounwind' functions into ordinary calls.
       Value *Callee = II->getCalledValue();
       if ((isa<ConstantPointerNull>(Callee) &&
            !NullPointerIsDefined(BB->getParent())) ||
           isa<UndefValue>(Callee)) {
-        changeToUnreachable(II, true, false, DDT);
+        changeToUnreachable(II, true, false, DTU);
         Changed = true;
       } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
         if (II->use_empty() && II->onlyReadsMemory()) {
           // jump to the normal destination branch.
           BasicBlock *NormalDestBB = II->getNormalDest();
           BasicBlock *UnwindDestBB = II->getUnwindDest();
           BranchInst::Create(NormalDestBB, II);
           UnwindDestBB->removePredecessor(II->getParent());
           II->eraseFromParent();
-          if (DDT)
-            DDT->deleteEdge(BB, UnwindDestBB);
+          if (DTU)
+            DTU->deleteEdgeRelaxed(BB, UnwindDestBB);
         } else
-          changeToCall(II, DDT);
+          changeToCall(II, DTU);
         Changed = true;
       }
     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
       // Remove catchpads which cannot be reached.
       struct CatchPadDenseMapInfo {
         static CatchPadInst *getEmptyKey() {
           return DenseMapInfo<CatchPadInst *>::getEmptyKey();
         }
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
           CatchSwitch->removeHandler(I);
           --I;
           --E;
           Changed = true;
         }
       }
     }
 
-    Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT);
+    Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
     for (BasicBlock *Successor : successors(BB))
       if (Reachable.insert(Successor).second)
         Worklist.push_back(Successor);
   } while (!Worklist.empty());
   return Changed;
 }
 
-void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) {
+void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
   TerminatorInst *TI = BB->getTerminator();
 
   if (auto *II = dyn_cast<InvokeInst>(TI)) {
-    changeToCall(II, DDT);
+    changeToCall(II, DTU);
     return;
   }
 
   TerminatorInst *NewTI;
   BasicBlock *UnwindDest;
 
   if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
     NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
     llvm_unreachable("Could not find unwind successor");
   }
 
   NewTI->takeName(TI);
   NewTI->setDebugLoc(TI->getDebugLoc());
   UnwindDest->removePredecessor(BB);
   TI->replaceAllUsesWith(NewTI);
   TI->eraseFromParent();
-  if (DDT)
-    DDT->deleteEdge(BB, UnwindDest);
+  if (DTU)
+    DTU->deleteEdgeRelaxed(BB, UnwindDest);
 }
 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
-                                   DeferredDominance *DDT) {
+                                   DomTreeUpdater *DTU) {
   SmallPtrSet<BasicBlock*, 16> Reachable;
-  bool Changed = markAliveBlocks(F, Reachable, DDT);
+  bool Changed = markAliveBlocks(F, Reachable, DTU);
 
   // If there are unreachable blocks in the CFG...
   if (Reachable.size() == F.size())
     return Changed;
 
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();
 
   // Loop over all of the basic blocks that are not reachable, dropping all of
-  // their internal references. Update DDT and LVI if available.
+  // their internal references. Update DTU and LVI if available.
   std::vector <DominatorTree::UpdateType> Updates;
   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
     auto *BB = &*I;
     if (Reachable.count(BB))
       continue;
     for (BasicBlock *Successor : successors(BB)) {
       if (Reachable.count(Successor))
         Successor->removePredecessor(BB);
-      if (DDT)
+      if (DTU)
         Updates.push_back({DominatorTree::Delete, BB, Successor});
     }
     if (LVI)
       LVI->eraseBlock(BB);
     BB->dropAllReferences();
   }
-
+  SmallVector<BasicBlock *, 8> ToDeleteBBs;
   for (Function::iterator I = ++F.begin(); I != F.end();) {
     auto *BB = &*I;
     if (Reachable.count(BB)) {
       ++I;
       continue;
     }
-    if (DDT) {
-      DDT->deleteBB(BB); // deferred deletion of BB.
+    if (DTU) {
+      ToDeleteBBs.push_back(BB);
+
+      // Remove the TerminatorInst of BB to clear the successor list of BB.
+      if (BB->getTerminator())
+        BB->getInstList().pop_back();
+      new UnreachableInst(BB->getContext(), BB);
+      assert(succ_empty(BB) && "The successor list of BB isn't empty before "
+                               "applying corresponding DTU updates.");
       ++I;
     } else {
       I = F.getBasicBlockList().erase(I);
     }
   }
 
-  if (DDT)
-    DDT->applyUpdates(Updates);
+  if (DTU) {
+    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    for (auto *BB : ToDeleteBBs)
+      DTU->deleteBB(BB);
+  }
   return true;
 }
 
 void llvm::combineMetadata(Instruction *K, const Instruction *J,
                            ArrayRef<unsigned> KnownIDs) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   K->dropUnknownNonDebugMetadata(KnownIDs);
   K->getAllMetadataOtherThanDebugLoc(Metadata);

llvm/trunk/lib/Transforms/Utils/LoopRotationUtils.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
 STATISTIC(NumRotated, "Number of loops rotated");
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
 
   assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
   assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
 
   // Now that the CFG and DomTree are in a consistent state again, try to merge
   // the OrigHeader block into OrigLatch.  This will succeed if they are
   // connected by an unconditional branch.  This is just a cleanup so the
   // emitted code isn't too gross in this common case.
-  MergeBlockIntoPredecessor(OrigHeader, DT, LI);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  MergeBlockIntoPredecessor(OrigHeader, &DTU, LI);
 
   LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
 
   ++NumRotated;
   return true;
 }
 
 /// Determine whether the instructions in this range may be safely and cheaply

llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp

 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
   }
 
   // Disconnect the loop body by branching directly to its exit.
   Builder.SetInsertPoint(Preheader->getTerminator());
   Builder.CreateBr(ExitBlock);
   // Remove the old branch.
   Preheader->getTerminator()->eraseFromParent();
 
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   if (DT) {
     // Update the dominator tree by informing it about the new edge from the
     // preheader to the exit.
-    DT->insertEdge(Preheader, ExitBlock);
+    DTU.insertEdge(Preheader, ExitBlock);
     // Inform the dominator tree about the removed edge.
-    DT->deleteEdge(Preheader, L->getHeader());
+    DTU.deleteEdge(Preheader, L->getHeader());
   }
 
   // Given LCSSA form is satisfied, we should not have users of instructions
   // within the dead loop outside of the loop. However, LCSSA doesn't take
   // unreachable uses into account. We handle them here.
   // We could do it after drop all references (in this case all users in the
   // loop will be already eliminated and we have less work to do but according
   // to API doc of User::dropAllReferences only valid operation after dropping

llvm/trunk/unittests/Transforms/Utils/Local.cpp

 //===- Local.cpp - Unit tests for Local -----------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
static void runWithDomTree(
   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
   // Compute the dominator tree for the function.
   DominatorTree DT(*F);
   Test(*F, &DT);
 }
 
 TEST(Local, MergeBasicBlockIntoOnlyPred) {
   LLVMContext C;
-
-  std::unique_ptr<Module> M = parseIR(C,
-                                      R"(
+  std::unique_ptr<Module> M;
+  auto resetIR = [&]() {
+    M = parseIR(C,
       define i32 @f(i8* %str) {
       entry:
         br label %bb2.i
       bb2.i:                                            ; preds = %bb4.i, %entry
         br i1 false, label %bb4.i, label %base2flt.exit204
       bb4.i:                                            ; preds = %bb2.i
         br i1 false, label %base2flt.exit204, label %bb2.i
       bb10.i196.bb7.i197_crit_edge:                     ; No predecessors!
         br label %bb7.i197
       bb7.i197:                                         ; preds = %bb10.i196.bb7.i197_crit_edge
         %.reg2mem.0 = phi i32 [ %.reg2mem.0, %bb10.i196.bb7.i197_crit_edge ]
         br i1 undef, label %base2flt.exit204, label %base2flt.exit204
       base2flt.exit204:                                 ; preds = %bb7.i197, %bb7.i197, %bb2.i, %bb4.i
         ret i32 0
       }
       )");
-  runWithDomTree(
-      *M, "f", [&](Function &F, DominatorTree *DT) {
-        for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
-          BasicBlock *BB = &*I++;
-          BasicBlock *SinglePred = BB->getSinglePredecessor();
-          if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
-          BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
-          if (Term && !Term->isConditional())
-            MergeBasicBlockIntoOnlyPred(BB, DT);
-        }
-        EXPECT_TRUE(DT->verify());
-      });
+  };
+
+  auto resetIRReplaceEntry = [&]() {
+    M = parseIR(C,
+                R"(
+      define i32 @f() {
+      entry:
+        br label %bb2.i
+      bb2.i:                                            ; preds = %entry
+        ret i32 0
+      }
+      )");
+  };
+
+  auto Test = [&](Function &F, DomTreeUpdater &DTU) {
+      if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
+        continue;
+        MergeBasicBlockIntoOnlyPred(BB, &DTU);
+    if (DTU.hasDomTree())
+      EXPECT_TRUE(DTU.getDomTree().verify());
+    if (DTU.hasPostDomTree())
+      EXPECT_TRUE(DTU.getPostDomTree().verify());
+  };
+
+  // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
+  // both DT and PDT.
+  resetIR();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
+  // DT.
+  resetIR();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
+  // PDT.
+  resetIR();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
+  // both DT and PDT.
+  resetIR();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
+  // PDT.
+  resetIR();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with DT.
+  resetIR();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
+  // both DT and PDT.
+  resetIRReplaceEntry();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
+  // DT.
+  resetIRReplaceEntry();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with
+  // PDT.
+  resetIRReplaceEntry();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
+  // both DT and PDT.
+  resetIRReplaceEntry();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with
+  // PDT.
+  resetIRReplaceEntry();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+    Test(F, DTU);
+  });
+
+  // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with DT.
+  resetIRReplaceEntry();
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
+    Test(F, DTU);
 }
 
 TEST(Local, ConstantFoldTerminator) {
   LLVMContext C;
 
   std::unique_ptr<Module> M = parseIR(C,
                                       R"(
       define void @br_same_dest() {
std::unique_ptr<Module> M = parseIR(C,
         indirectbr i8* blockaddress(@indirectbr_unreachable, %bb0), [label %bb1]
       bb0:
         ret void
       bb1:
         ret void
       }
         )");
 
-  auto CFAllTerminators = [&](Function &F, DominatorTree *DT) {
-    DeferredDominance DDT(*DT);
+  auto CFAllTerminatorsEager = [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
+      BasicBlock *BB = &*I++;
+      ConstantFoldTerminator(BB, true, nullptr, &DTU);
+    }
+
+    EXPECT_TRUE(DTU.getDomTree().verify());
+    EXPECT_TRUE(DTU.getPostDomTree().verify());
+  };
+
+  auto CFAllTerminatorsLazy = [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
       BasicBlock *BB = &*I++;
-      ConstantFoldTerminator(BB, true, nullptr, &DDT);
+      ConstantFoldTerminator(BB, true, nullptr, &DTU);
     }
 
-    EXPECT_TRUE(DDT.flush().verify());
+    EXPECT_TRUE(DTU.getDomTree().verify());
+    EXPECT_TRUE(DTU.getPostDomTree().verify());
   };
 
-  runWithDomTree(*M, "br_same_dest", CFAllTerminators);
-  runWithDomTree(*M, "br_different_dest", CFAllTerminators);
-  runWithDomTree(*M, "switch_2_different_dest", CFAllTerminators);
-  runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminators);
-  runWithDomTree(*M, "switch_3_different_dest", CFAllTerminators);
-  runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminators);
-  runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminators);
-  runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminators);
-  runWithDomTree(*M, "indirectbr", CFAllTerminators);
-  runWithDomTree(*M, "indirectbr_repeated", CFAllTerminators);
-  runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminators);
+  // Test ConstantFoldTerminator under Eager UpdateStrategy.
+  runWithDomTree(*M, "br_same_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "br_different_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "switch_2_different_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminatorsEager);
+  runWithDomTree(*M, "switch_3_different_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminatorsEager);
+  runWithDomTree(*M, "indirectbr", CFAllTerminatorsEager);
+  runWithDomTree(*M, "indirectbr_repeated", CFAllTerminatorsEager);
+  runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminatorsEager);
+
+  // Test ConstantFoldTerminator under Lazy UpdateStrategy.
+  runWithDomTree(*M, "br_same_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "br_different_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "switch_2_different_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "switch_3_different_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "indirectbr", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "indirectbr_repeated", CFAllTerminatorsLazy);
+  runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminatorsLazy);
 }
 
 struct SalvageDebugInfoTest : ::testing::Test {
   LLVMContext C;
   std::unique_ptr<Module> M;
   Function *F = nullptr;
 
   void SetUp() {
EXPECT_TRUE(
                   DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
   EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_dup, DW_OP_constu, 31,
                           DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or,
                           DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8}));
 
   verifyModule(*M, &errs(), &BrokenDebugInfo);
   ASSERT_FALSE(BrokenDebugInfo);
 }
+
+TEST(Local, RemoveUnreachableBlocks) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(C,
+                                      R"(
+      define void @br_simple() {
+      entry:
+        br label %bb0
+      bb0:
+        ret void
+      bb1:
+        ret void
+      }
+
+      define void @br_self_loop() {
+      entry:
+        br label %bb0
+      bb0:
+        br i1 true, label %bb1, label %bb0
+      bb1:
+        br i1 true, label %bb0, label %bb2
+      bb2:
+        br label %bb2
+      }
+
+      define void @br_constant() {
+      entry:
+        br label %bb0
+      bb0:
+        br i1 true, label %bb1, label %bb2
+      bb1:
+        br i1 true, label %bb0, label %bb2
+      bb2:
+        br label %bb2
+      }
+
+      define void @br_loop() {
+      entry:
+        br label %bb0
+      bb0:
+        br label %bb0
+      bb1:
+        br label %bb2
+      bb2:
+        br label %bb1
+      }
+      )");
+
+  auto runEager = [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
+    removeUnreachableBlocks(F, nullptr, &DTU);
+    EXPECT_TRUE(DTU.getDomTree().verify());
+    EXPECT_TRUE(DTU.getPostDomTree().verify());
+  };
+
+  auto runLazy = [&](Function &F, DominatorTree *DT) {
+    PostDominatorTree PDT = PostDominatorTree(F);
+    DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
+    removeUnreachableBlocks(F, nullptr, &DTU);
+    EXPECT_TRUE(DTU.getDomTree().verify());
+    EXPECT_TRUE(DTU.getPostDomTree().verify());
+  };
+
+  // Test removeUnreachableBlocks under Eager UpdateStrategy.
+  runWithDomTree(*M, "br_simple", runEager);
+  runWithDomTree(*M, "br_self_loop", runEager);
+  runWithDomTree(*M, "br_constant", runEager);
+  runWithDomTree(*M, "br_loop", runEager);
+
+  // Test removeUnreachableBlocks under Lazy UpdateStrategy.
+  runWithDomTree(*M, "br_simple", runLazy);
+  runWithDomTree(*M, "br_self_loop", runLazy);
+  runWithDomTree(*M, "br_constant", runLazy);
+  runWithDomTree(*M, "br_loop", runLazy);
+}
 No newline at end of file