This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Remove the DeferredDominance class
ClosedPublic

Authored by NutshellySima on Jul 24 2018, 11:48 AM.

Download Raw Diff

Details

Reviewers

kuhar
brzycki
dmgreen
davide
grosser

Commits

rGce698a55866a: [Dominators] Remove the DeferredDominance class
rL339502: [Dominators] Remove the DeferredDominance class

Summary

After converting all existing passes to use the new DomTreeUpdater interface, there isn't any usage of the original DeferredDominance class. Thus, we can safely remove it from the codebase.

Diff Detail

Repository: rL LLVM

Event Timeline

NutshellySima created this revision.Jul 24 2018, 11:48 AM

Herald added subscribers: llvm-commits, mgorny. · View Herald TranscriptJul 24 2018, 11:48 AM

NutshellySima added a parent revision: D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.Jul 24 2018, 11:48 AM

Nit: It's removal and not deprecation.
Looks good otherwise.

This revision is now accepted and ready to land.Aug 2 2018, 8:42 AM

NutshellySima retitled this revision from [Dominators] Deprecate the DeferredDominance class to [Dominators] Remove the DeferredDominance class.Aug 2 2018, 8:44 AM

LGTM. DTU should be the only way to do Lazy or Eager updates to DT.

Closed by commit rL339502: [Dominators] Remove the DeferredDominance class (authored by sima). · Explain WhyAug 11 2018, 1:12 AM

This revision was automatically updated to reflect the committed changes.

Revision Contents

Path

Size

llvm/

trunk/

include/

llvm/

IR/

Dominators.h

88 lines

lib/

IR/

Dominators.cpp

190 lines

unittests/

IR/

CMakeLists.txt

1 line

DeferredDominanceTest.cpp

344 lines

Diff 160235

llvm/trunk/include/llvm/IR/Dominators.h

Show First 20 Lines • Show All 270 Lines • ▼ Show 20 Lines	public:
void getAnalysisUsage(AnalysisUsage &AU) const override {		void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();		AU.setPreservesAll();
}		}

void releaseMemory() override { DT.releaseMemory(); }		void releaseMemory() override { DT.releaseMemory(); }

void print(raw_ostream &OS, const Module *M = nullptr) const override;		void print(raw_ostream &OS, const Module *M = nullptr) const override;
};		};

//===-------------------------------------
/// Class to defer updates to a DominatorTree.
///
/// Definition: Applying updates to every edge insertion and deletion is
/// expensive and not necessary. When one needs the DominatorTree for analysis
/// they can request a flush() to perform a larger batch update. This has the
/// advantage of the DominatorTree inspecting the set of updates to find
/// duplicates or unnecessary subtree updates.
///
/// The scope of DeferredDominance operates at a Function level.
///
/// It is not necessary for the user to scrub the updates for duplicates or
/// updates that point to the same block (Delete, BB_A, BB_A). Performance
/// can be gained if the caller attempts to batch updates before submitting
/// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
/// occur.
///
/// It is required for the state of the LLVM IR to be applied before
/// submitting updates. The update routines must analyze the current state
/// between a pair of (From, To) basic blocks to determine if the update
/// needs to be queued.
/// Example (good):
/// TerminatorInstructionBB->removeFromParent();
/// DDT->deleteEdge(BB, Successor);
/// Example (bad):
/// DDT->deleteEdge(BB, Successor);
/// TerminatorInstructionBB->removeFromParent();
class DeferredDominance {
public:
DeferredDominance(DominatorTree &DT_) : DT(DT_) {}

/// Queues multiple updates and discards duplicates.
void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);

/// Helper method for a single edge insertion. It's almost always
/// better to batch updates and call applyUpdates to quickly remove duplicate
/// edges. This is best used when there is only a single insertion needed to
/// update Dominators.
void insertEdge(BasicBlock From, BasicBlock To);

/// Helper method for a single edge deletion. It's almost always better
/// to batch updates and call applyUpdates to quickly remove duplicate edges.
/// This is best used when there is only a single deletion needed to update
/// Dominators.
void deleteEdge(BasicBlock From, BasicBlock To);

/// Delays the deletion of a basic block until a flush() event.
void deleteBB(BasicBlock *DelBB);

/// Returns true if DelBB is awaiting deletion at a flush() event.
bool pendingDeletedBB(BasicBlock *DelBB);

/// Returns true if pending DT updates are queued for a flush() event.
bool pending();

/// Flushes all pending updates and block deletions. Returns a
/// correct DominatorTree reference to be used by the caller for analysis.
DominatorTree &flush();

/// Drops all internal state and forces a (slow) recalculation of the
/// DominatorTree based on the current state of the LLVM IR in F. This should
/// only be used in corner cases such as the Entry block of F being deleted.
void recalculate(Function &F);

/// Debug method to help view the state of pending updates.
LLVM_DUMP_METHOD void dump() const;

private:
DominatorTree &DT;
SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
SmallPtrSet<BasicBlock *, 8> DeletedBBs;

/// Apply an update (Kind, From, To) to the internal queued updates. The
/// update is only added when determined to be necessary. Checks for
/// self-domination, unnecessary updates, duplicate requests, and balanced
/// pairs of requests are all performed. Returns true if the update is
/// queued and false if it is discarded.
bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
BasicBlock *To);

/// Performs all pending basic block deletions. We have to defer the deletion
/// of these blocks until after the DominatorTree updates are applied. The
/// internal workings of the DominatorTree code expect every update's From
/// and To blocks to exist and to be a member of the same Function.
bool flushDelBB();
};

} // end namespace llvm		} // end namespace llvm

#endif // LLVM_IR_DOMINATORS_H		#endif // LLVM_IR_DOMINATORS_H

llvm/trunk/lib/IR/Dominators.cpp

Show First 20 Lines • Show All 366 Lines • ▼ Show 20 Lines	void DominatorTreeWrapperPass::verifyAnalysis() const {
else if (ExpensiveChecksEnabled)		else if (ExpensiveChecksEnabled)
assert(DT.verify(DominatorTree::VerificationLevel::Basic));		assert(DT.verify(DominatorTree::VerificationLevel::Basic));
}		}

void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {		void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
DT.print(OS);		DT.print(OS);
}		}

//===----------------------------------------------------------------------===//
// DeferredDominance Implementation
//===----------------------------------------------------------------------===//
//
// The implementation details of the DeferredDominance class which allows
// one to queue updates to a DominatorTree.
//
//===----------------------------------------------------------------------===//

/// Queues multiple updates and discards duplicates.
void DeferredDominance::applyUpdates(
ArrayRef<DominatorTree::UpdateType> Updates) {
SmallVector<DominatorTree::UpdateType, 8> Seen;
for (auto U : Updates)
// Avoid duplicates to applyUpdate() to save on analysis.
if (std::none_of(Seen.begin(), Seen.end(),
[U](DominatorTree::UpdateType S) { return S == U; })) {
Seen.push_back(U);
applyUpdate(U.getKind(), U.getFrom(), U.getTo());
}
}

/// Helper method for a single edge insertion. It's almost always better
/// to batch updates and call applyUpdates to quickly remove duplicate edges.
/// This is best used when there is only a single insertion needed to update
/// Dominators.
void DeferredDominance::insertEdge(BasicBlock From, BasicBlock To) {
applyUpdate(DominatorTree::Insert, From, To);
}

/// Helper method for a single edge deletion. It's almost always better
/// to batch updates and call applyUpdates to quickly remove duplicate edges.
/// This is best used when there is only a single deletion needed to update
/// Dominators.
void DeferredDominance::deleteEdge(BasicBlock From, BasicBlock To) {
applyUpdate(DominatorTree::Delete, From, To);
}

/// Delays the deletion of a basic block until a flush() event.
void DeferredDominance::deleteBB(BasicBlock *DelBB) {
assert(DelBB && "Invalid push_back of nullptr DelBB.");
assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
// DelBB is unreachable and all its instructions are dead.
while (!DelBB->empty()) {
Instruction &I = DelBB->back();
// Replace used instructions with an arbitrary value (undef).
if (!I.use_empty())
I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
DelBB->getInstList().pop_back();
}
// Make sure DelBB has a valid terminator instruction. As long as DelBB is a
// Child of Function F it must contain valid IR.
new UnreachableInst(DelBB->getContext(), DelBB);
DeletedBBs.insert(DelBB);
}

/// Returns true if DelBB is awaiting deletion at a flush() event.
bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
if (DeletedBBs.empty())
return false;
return DeletedBBs.count(DelBB) != 0;
}

/// Returns true if pending DT updates are queued for a flush() event.
bool DeferredDominance::pending() { return !PendUpdates.empty(); }

/// Flushes all pending updates and block deletions. Returns a
/// correct DominatorTree reference to be used by the caller for analysis.
DominatorTree &DeferredDominance::flush() {
// Updates to DT must happen before blocks are deleted below. Otherwise the
// DT traversal will encounter badref blocks and assert.
if (!PendUpdates.empty()) {
DT.applyUpdates(PendUpdates);
PendUpdates.clear();
}
flushDelBB();
return DT;
}

/// Drops all internal state and forces a (slow) recalculation of the
/// DominatorTree based on the current state of the LLVM IR in F. This should
/// only be used in corner cases such as the Entry block of F being deleted.
void DeferredDominance::recalculate(Function &F) {
// flushDelBB must be flushed before the recalculation. The state of the IR
// must be consistent before the DT traversal algorithm determines the
// actual DT.
if (flushDelBB() \|\| !PendUpdates.empty()) {
DT.recalculate(F);
PendUpdates.clear();
}
}

/// Debug method to help view the state of pending updates.
#if !defined(NDEBUG) \|\| defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void DeferredDominance::dump() const {
raw_ostream &OS = llvm::dbgs();
OS << "PendUpdates:\n";
int I = 0;
for (auto U : PendUpdates) {
OS << " " << I << " : ";
++I;
if (U.getKind() == DominatorTree::Insert)
OS << "Insert, ";
else
OS << "Delete, ";
BasicBlock *From = U.getFrom();
if (From) {
auto S = From->getName();
if (!From->hasName())
S = "(no name)";
OS << S << "(" << From << "), ";
} else {
OS << "(badref), ";
}
BasicBlock *To = U.getTo();
if (To) {
auto S = To->getName();
if (!To->hasName())
S = "(no_name)";
OS << S << "(" << To << ")\n";
} else {
OS << "(badref)\n";
}
}
OS << "DeletedBBs:\n";
I = 0;
for (auto BB : DeletedBBs) {
OS << " " << I << " : ";
++I;
if (BB->hasName())
OS << BB->getName() << "(";
else
OS << "(no_name)(";
OS << BB << ")\n";
}
}
#endif

/// Apply an update (Kind, From, To) to the internal queued updates. The
/// update is only added when determined to be necessary. Checks for
/// self-domination, unnecessary updates, duplicate requests, and balanced
/// pairs of requests are all performed. Returns true if the update is
/// queued and false if it is discarded.
bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
BasicBlock From, BasicBlock To) {
if (From == To)
return false; // Cannot dominate self; discard update.

// Discard updates by inspecting the current state of successors of From.
// Since applyUpdate() must be called after the Terminator of From is
// altered we can determine if the update is unnecessary.
bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
[To](BasicBlock *B) { return B == To; });
if (Kind == DominatorTree::Insert && !HasEdge)
return false; // Unnecessary Insert: edge does not exist in IR.
if (Kind == DominatorTree::Delete && HasEdge)
return false; // Unnecessary Delete: edge still exists in IR.

// Analyze pending updates to determine if the update is unnecessary.
DominatorTree::UpdateType Update = {Kind, From, To};
DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
? DominatorTree::Insert
: DominatorTree::Delete,
From, To};
for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
if (Update == *I)
return false; // Discard duplicate updates.
if (Invert == *I) {
// Update and Invert are both valid (equivalent to a no-op). Remove
// Invert from PendUpdates and discard the Update.
PendUpdates.erase(I);
return false;
}
}
PendUpdates.push_back(Update); // Save the valid update.
return true;
}

/// Performs all pending basic block deletions. We have to defer the deletion
/// of these blocks until after the DominatorTree updates are applied. The
/// internal workings of the DominatorTree code expect every update's From
/// and To blocks to exist and to be a member of the same Function.
bool DeferredDominance::flushDelBB() {
if (DeletedBBs.empty())
return false;
for (auto *BB : DeletedBBs)
BB->eraseFromParent();
DeletedBBs.clear();
return true;
}

llvm/trunk/unittests/IR/CMakeLists.txt

Show All 9 Lines	add_llvm_unittest(IRTests
AsmWriterTest.cpp		AsmWriterTest.cpp
AttributesTest.cpp		AttributesTest.cpp
BasicBlockTest.cpp		BasicBlockTest.cpp
CFGBuilder.cpp		CFGBuilder.cpp
ConstantRangeTest.cpp		ConstantRangeTest.cpp
ConstantsTest.cpp		ConstantsTest.cpp
DebugInfoTest.cpp		DebugInfoTest.cpp
DebugTypeODRUniquingTest.cpp		DebugTypeODRUniquingTest.cpp
DeferredDominanceTest.cpp
DominatorTreeTest.cpp		DominatorTreeTest.cpp
DominatorTreeBatchUpdatesTest.cpp		DominatorTreeBatchUpdatesTest.cpp
DomTreeUpdaterTest.cpp		DomTreeUpdaterTest.cpp
FunctionTest.cpp		FunctionTest.cpp
PassBuilderCallbacksTest.cpp		PassBuilderCallbacksTest.cpp
IRBuilderTest.cpp		IRBuilderTest.cpp
InstructionsTest.cpp		InstructionsTest.cpp
IntrinsicsTest.cpp		IntrinsicsTest.cpp
Show All 17 Lines

llvm/trunk/unittests/IR/DeferredDominanceTest.cpp

	//===- llvm/unittests/IR/DeferredDominanceTest.cpp - DDT unit tests -------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/AsmParser/Parser.h"
	#include "llvm/IR/Constants.h"
	#include "llvm/IR/Dominators.h"
	#include "llvm/IR/Instructions.h"
	#include "llvm/IR/LLVMContext.h"
	#include "llvm/IR/Module.h"
	#include "llvm/Support/SourceMgr.h"
	#include "gtest/gtest.h"

	using namespace llvm;

	static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
	StringRef ModuleStr) {
	SMDiagnostic Err;
	std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
	assert(M && "Bad LLVM IR?");
	return M;
	}

	TEST(DeferredDominance, BasicOperations) {
	StringRef FuncName = "f";
	StringRef ModuleString =
	"define i32 @f(i32 %i, i32 *%p) {\n"
	" bb0:\n"
	" store i32 %i, i32 *%p\n"
	" switch i32 %i, label %bb1 [\n"
	" i32 0, label %bb2\n"
	" i32 1, label %bb2\n"
	" i32 2, label %bb3\n"
	" ]\n"
	" bb1:\n"
	" ret i32 1\n"
	" bb2:\n"
	" ret i32 2\n"
	" bb3:\n"
	" ret i32 3\n"
	"}\n";
	// Make the module.
	LLVMContext Context;
	std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
	Function *F = M->getFunction(FuncName);
	ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

	// Make the DDT.
	DominatorTree DT(*F);
	DeferredDominance DDT(DT);
	ASSERT_TRUE(DDT.flush().verify());

	Function::iterator FI = F->begin();
	BasicBlock BB0 = &FI++;
	BasicBlock BB1 = &FI++;
	BasicBlock BB2 = &FI++;
	BasicBlock BB3 = &FI++;

	// Test discards of invalid self-domination updates. These use the single
	// short-hand interface but are still queued inside DDT.
	DDT.deleteEdge(BB0, BB0);
	DDT.insertEdge(BB1, BB1);

	// Delete edge bb0 -> bb3 and push the update twice to verify duplicate
	// entries are discarded.
	std::vector<DominatorTree::UpdateType> Updates;
	Updates.reserve(4);
	Updates.push_back({DominatorTree::Delete, BB0, BB3});
	Updates.push_back({DominatorTree::Delete, BB0, BB3});

	// Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
	Updates.push_back({DominatorTree::Insert, BB1, BB2});
	// Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
	Updates.push_back({DominatorTree::Delete, BB0, BB1});

	// CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
	BB0->getTerminator()->eraseFromParent();
	BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);

	// Deletion of a BasicBlock is an immediate event. We remove all uses to the
	// contained Instructions and change the Terminator to "unreachable" when
	// queued for deletion. Its parent is still F until DDT.flush() is called. We
	// don't defer this action because it can cause problems for other transforms
	// or analysis as it's part of the actual CFG. We only defer updates to the
	// DominatorTree. This code will crash if it is placed before the
	// BranchInst::Create() call above.
	ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
	EXPECT_FALSE(DDT.pendingDeletedBB(BB3));
	DDT.deleteBB(BB3);
	EXPECT_TRUE(DDT.pendingDeletedBB(BB3));
	ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
	EXPECT_EQ(BB3->getParent(), F);

	// Verify. Updates to DDT must be applied after all changes to the CFG
	// (including block deletion).
	DDT.applyUpdates(Updates);
	ASSERT_TRUE(DDT.flush().verify());
	}

	TEST(DeferredDominance, PairedUpdate) {
	StringRef FuncName = "f";
	StringRef ModuleString =
	"define i32 @f(i32 %i, i32 *%p) {\n"
	" bb0:\n"
	" store i32 %i, i32 *%p\n"
	" switch i32 %i, label %bb1 [\n"
	" i32 0, label %bb2\n"
	" i32 1, label %bb2\n"
	" ]\n"
	" bb1:\n"
	" ret i32 1\n"
	" bb2:\n"
	" ret i32 2\n"
	"}\n";
	// Make the module.
	LLVMContext Context;
	std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
	Function *F = M->getFunction(FuncName);
	ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

	// Make the DDT.
	DominatorTree DT(*F);
	DeferredDominance DDT(DT);
	ASSERT_TRUE(DDT.flush().verify());

	Function::iterator FI = F->begin();
	BasicBlock BB0 = &FI++;
	BasicBlock BB1 = &FI++;
	BasicBlock BB2 = &FI++;

	// CFG Change: only edge from bb0 is bb0 -> bb1.
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
	BB0->getTerminator()->eraseFromParent();
	BranchInst::Create(BB1, BB0);
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);

	// Must be done after the CFG change. The applyUpdate() routine analyzes the
	// current state of the CFG.
	DDT.deleteEdge(BB0, BB2);

	// CFG Change: bb0 now has bb0 -> bb1 and bb0 -> bb2.
	// With this change no dominance has been altered from the original IR. DT
	// doesn't care if the type of TerminatorInstruction changed, only if the
	// unique edges have.
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
	BB0->getTerminator()->eraseFromParent();
	BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);

	// Must be done after the CFG change. The applyUpdate() routine analyzes the
	// current state of the CFG. This DDT update pairs with the previous one and
	// is cancelled out before ever applying updates to DT.
	DDT.insertEdge(BB0, BB2);

	// Test the empty DeletedBB list.
	EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
	EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
	EXPECT_FALSE(DDT.pendingDeletedBB(BB2));

	// The DT has no changes, this flush() simply returns a reference to the
	// internal DT calculated at the beginning of this test.
	ASSERT_TRUE(DDT.flush().verify());
	}

	TEST(DeferredDominance, ReplaceEntryBB) {
	StringRef FuncName = "f";
	StringRef ModuleString =
	"define i32 @f() {\n"
	"bb0:\n"
	" br label %bb1\n"
	" bb1:\n"
	" ret i32 1\n"
	"}\n";
	// Make the module.
	LLVMContext Context;
	std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
	Function *F = M->getFunction(FuncName);
	ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

	// Make the DDT.
	DominatorTree DT(*F);
	DeferredDominance DDT(DT);
	ASSERT_TRUE(DDT.flush().verify());

	Function::iterator FI = F->begin();
	BasicBlock BB0 = &FI++;
	BasicBlock BB1 = &FI++;

	// Add a block as the new function entry BB. We also link it to BB0.
	BasicBlock *NewEntry =
	BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
	BranchInst::Create(BB0, NewEntry);
	EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
	EXPECT_TRUE(&F->getEntryBlock() == NewEntry);

	// Insert the new edge between new_eentry -> bb0. Without this the
	// recalculate() call below will not actually recalculate the DT as there
	// are no changes pending and no blocks deleted.
	DDT.insertEdge(NewEntry, BB0);

	// Changing the Entry BB requires a full recalulation.
	DDT.recalculate(*F);
	ASSERT_TRUE(DDT.flush().verify());

	// CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
	EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
	NewEntry->getTerminator()->eraseFromParent();
	BranchInst::Create(BB1, NewEntry);
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);

	// Update the DDT. At this point bb0 now has no predecessors but is still a
	// Child of F.
	DDT.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
	{DominatorTree::Insert, NewEntry, BB1}});
	ASSERT_TRUE(DDT.flush().verify());

	// Now remove bb0 from F.
	ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
	EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
	DDT.deleteBB(BB0);
	EXPECT_TRUE(DDT.pendingDeletedBB(BB0));
	ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
	EXPECT_EQ(BB0->getParent(), F);

	// Perform a full recalculation of the DDT. It is not necessary here but we
	// do this to test the case when there are no pending DT updates but there are
	// pending deleted BBs.
	DDT.recalculate(*F);
	ASSERT_TRUE(DDT.flush().verify());
	}

	TEST(DeferredDominance, InheritedPreds) {
	StringRef FuncName = "f";
	StringRef ModuleString =
	"define i32 @f(i32 %i, i32 *%p) {\n"
	" bb0:\n"
	" store i32 %i, i32 *%p\n"
	" switch i32 %i, label %bb1 [\n"
	" i32 2, label %bb2\n"
	" i32 3, label %bb3\n"
	" ]\n"
	" bb1:\n"
	" br label %bb3\n"
	" bb2:\n"
	" br label %bb3\n"
	" bb3:\n"
	" ret i32 3\n"
	"}\n";
	// Make the module.
	LLVMContext Context;
	std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
	Function *F = M->getFunction(FuncName);
	ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";

	// Make the DDT.
	DominatorTree DT(*F);
	DeferredDominance DDT(DT);
	ASSERT_TRUE(DDT.flush().verify());

	Function::iterator FI = F->begin();
	BasicBlock BB0 = &FI++;
	BasicBlock BB1 = &FI++;
	BasicBlock BB2 = &FI++;
	BasicBlock BB3 = &FI++;

	// There are several CFG locations where we have:
	//
	// pred1..predN
	// \| \|
	// +> curr <+ converted into: pred1..predN curr
	// \| \| \|
	// v +> succ <+
	// succ
	//
	// There is a specific shape of this we have to be careful of:
	//
	// pred1..predN
	// \|\| \|
	// \|+> curr <+ converted into: pred1..predN curr
	// \| \| \| \|
	// \| v +> succ <+
	// +-> succ
	//
	// While the final CFG form is functionally identical the updates to
	// DDT are not. In the first case we must have DDT.insertEdge(Pred1, Succ)
	// while in the latter case we must NOT have DDT.insertEdge(Pred1, Succ).

	// CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
	// remove bb2.
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
	BB0->getTerminator()->eraseFromParent();
	BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);

	// Remove bb2 from F. This has to happen before the call to applyUpdates() for
	// DDT to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
	// method converts bb2's TI into "unreachable".
	ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
	EXPECT_FALSE(DDT.pendingDeletedBB(BB2));
	DDT.deleteBB(BB2);
	EXPECT_TRUE(DDT.pendingDeletedBB(BB2));
	ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
	EXPECT_EQ(BB2->getParent(), F);

	// Queue up the DDT updates.
	std::vector<DominatorTree::UpdateType> Updates;
	Updates.reserve(4);
	Updates.push_back({DominatorTree::Delete, BB0, BB2});
	Updates.push_back({DominatorTree::Delete, BB2, BB3});

	// Handle the specific shape case next.
	// CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
	BB0->getTerminator()->eraseFromParent();
	BranchInst::Create(BB3, BB0);
	EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);

	// Remove bb1 from F. This has to happen before the call to applyUpdates() for
	// DDT to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
	// method converts bb1's TI into "unreachable".
	ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
	EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
	DDT.deleteBB(BB1);
	EXPECT_TRUE(DDT.pendingDeletedBB(BB1));
	ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
	EXPECT_EQ(BB1->getParent(), F);

	// Update the DDT. In this case we don't call DDT.insertEdge(BB0, BB3) because
	// the edge previously existed at the start of this test when DT was first
	// created.
	Updates.push_back({DominatorTree::Delete, BB0, BB1});
	Updates.push_back({DominatorTree::Delete, BB1, BB3});

	// Verify everything.
	DDT.applyUpdates(Updates);
	ASSERT_TRUE(DDT.flush().verify());
	}