diff --git a/llvm/include/llvm/CodeGen/MachineDominators.h b/llvm/include/llvm/CodeGen/MachineDominators.h --- a/llvm/include/llvm/CodeGen/MachineDominators.h +++ b/llvm/include/llvm/CodeGen/MachineDominators.h @@ -80,6 +80,11 @@ public: static char ID; // Pass ID, replacement for typeid + using UpdateType = DomTreeT::UpdateType; + using UpdateKind = DomTreeT::UpdateKind; + static constexpr UpdateKind Insert = UpdateKind::Insert; + static constexpr UpdateKind Delete = UpdateKind::Delete; + MachineDominatorTree(); explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) { calculate(MF); @@ -221,10 +226,17 @@ return DT->isReachableFromEntry(A); } + void applyUpdates(ArrayRef Updates) { + applySplitCriticalEdges(); + DT->applyUpdates(Updates); + } + void releaseMemory() override; void verifyAnalysis() const override; + bool verify() const { return DT->verify(DomTreeT::VerificationLevel::Basic); } + void print(raw_ostream &OS, const Module*) const override; /// Record that the critical edge (FromBB, ToBB) has been diff --git a/llvm/include/llvm/CodeGen/MachinePostDominators.h b/llvm/include/llvm/CodeGen/MachinePostDominators.h --- a/llvm/include/llvm/CodeGen/MachinePostDominators.h +++ b/llvm/include/llvm/CodeGen/MachinePostDominators.h @@ -31,6 +31,11 @@ public: static char ID; + using UpdateType = PostDomTreeT::UpdateType; + using UpdateKind = PostDomTreeT::UpdateKind; + static constexpr UpdateKind Insert = UpdateKind::Insert; + static constexpr UpdateKind Delete = UpdateKind::Delete; + MachinePostDominatorTree(); FunctionPass *createMachinePostDominatorTreePass(); @@ -77,6 +82,22 @@ return PDT->findNearestCommonDominator(A, B); } + /// addNewBlock - Add a new node to the dominator tree information. This + /// creates a new node as a child of DomBB dominator node,linking it into + /// the children list of the immediate dominator. + MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, + MachineBasicBlock *DomBB) { + return PDT->addNewBlock(BB, DomBB); + } + + void applyUpdates(ArrayRef Updates) { + PDT->applyUpdates(Updates); + } + + bool verify() const { + return PDT->verify(PostDomTreeT::VerificationLevel::Basic); + } + /// Returns the nearest common dominator of the given blocks. /// If that tree node is a virtual root, a nullptr will be returned. MachineBasicBlock * diff --git a/llvm/lib/CodeGen/MachineDominators.cpp b/llvm/lib/CodeGen/MachineDominators.cpp --- a/llvm/lib/CodeGen/MachineDominators.cpp +++ b/llvm/lib/CodeGen/MachineDominators.cpp @@ -73,7 +73,7 @@ void MachineDominatorTree::verifyAnalysis() const { if (DT && VerifyMachineDomInfo) - if (!DT->verify(DomTreeT::VerificationLevel::Basic)) { + if (!verify()) { errs() << "MachineDominatorTree verification failed\n"; abort(); } diff --git a/llvm/lib/CodeGen/MachinePostDominators.cpp b/llvm/lib/CodeGen/MachinePostDominators.cpp --- a/llvm/lib/CodeGen/MachinePostDominators.cpp +++ b/llvm/lib/CodeGen/MachinePostDominators.cpp @@ -66,7 +66,7 @@ void MachinePostDominatorTree::verifyAnalysis() const { if (PDT && VerifyMachineDomInfo) - if (!PDT->verify(PostDomTreeT::VerificationLevel::Basic)) { + if (!verify()) { errs() << "MachinePostDominatorTree verification failed\n"; abort(); diff --git a/llvm/unittests/CodeGen/CMakeLists.txt b/llvm/unittests/CodeGen/CMakeLists.txt --- a/llvm/unittests/CodeGen/CMakeLists.txt +++ b/llvm/unittests/CodeGen/CMakeLists.txt @@ -17,9 +17,11 @@ DIEHashTest.cpp LowLevelTypeTest.cpp LexicalScopesTest.cpp + MachineDominatorTreeTest.cpp MachineInstrBundleIteratorTest.cpp MachineInstrTest.cpp MachineOperandTest.cpp + MachinePostDominatorTreeTest.cpp ScalableVectorMVTsTest.cpp TypeTraitsTest.cpp TargetOptionsTest.cpp diff --git a/llvm/unittests/CodeGen/MachineDominatorTreeTest.cpp b/llvm/unittests/CodeGen/MachineDominatorTreeTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/CodeGen/MachineDominatorTreeTest.cpp @@ -0,0 +1,225 @@ +//===- MachineDominatorTreeTest.cpp - MachineDominatorTree unit tests -----===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/TargetFrameLowering.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetLowering.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/Support/TargetRegistry.h" + +#include "llvm/CodeGen/MachineDominators.h" + +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { +#include "MFCommon.inc" +} + +TEST(MachineDominatorTreeTest, addNewBlock) { + LLVMContext Ctx; + Module Mod("test", Ctx); + + // Function: + // BB1 -> BB2 + auto MF = createMachineFunction(Ctx, Mod); + llvm::Function &F = const_cast(MF->getFunction()); + auto BB1 = BasicBlock::Create(Ctx, "a", &F); + auto BB2 = BasicBlock::Create(Ctx, "b", &F); + IRBuilder<> IRB1(BB1), IRB2(BB2); + IRB1.CreateBr(BB2); + IRB2.CreateRetVoid(); + auto MBB1 = MF->CreateMachineBasicBlock(BB1); + MF->insert(MF->end(), MBB1); + auto MBB2 = MF->CreateMachineBasicBlock(BB2); + MF->insert(MF->end(), MBB2); + MBB1->addSuccessor(MBB2); + + // Build tree and verify + auto MDT = new MachineDominatorTree(*MF); + EXPECT_TRUE(MDT->verify()); + + // Insert block + auto NewMBB = MF->CreateMachineBasicBlock(MBB1->getBasicBlock()); + MachineFunction::iterator MBBI(MBB1); + ++MBBI; + MF->insert(MBBI, NewMBB); + MBB1->addSuccessor(NewMBB); + NewMBB->addSuccessor(MBB2); + + // Update tree + MDT->addNewBlock(NewMBB, MBB1); + EXPECT_TRUE(MDT->verify()); +} + +TEST(MachineDominatorTreeTest, applyUpdates) { + LLVMContext Ctx; + Module Mod("test", Ctx); + + // Function: + // BB1 --------> BB3 --> BB4 + // \--> BB2 --^ + auto MF = createMachineFunction(Ctx, Mod); + llvm::Function &F = const_cast(MF->getFunction()); + auto BB1 = BasicBlock::Create(Ctx, "a", &F); + auto BB2 = BasicBlock::Create(Ctx, "b", &F); + auto BB3 = BasicBlock::Create(Ctx, "c", &F); + auto BB4 = BasicBlock::Create(Ctx, "d", &F); + IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4); + IRB1.CreateBr(BB2); + IRB2.CreateBr(BB3); + IRB3.CreateBr(BB4); + IRB4.CreateRetVoid(); + auto MBB1 = MF->CreateMachineBasicBlock(); + MF->insert(MF->end(), MBB1); + auto MBB2 = MF->CreateMachineBasicBlock(BB2); + MF->insert(MF->end(), MBB2); + auto MBB3 = MF->CreateMachineBasicBlock(BB3); + MF->insert(MF->end(), MBB3); + auto MBB4 = MF->CreateMachineBasicBlock(BB4); + MF->insert(MF->end(), MBB4); + MBB1->addSuccessor(MBB2); + MBB1->addSuccessor(MBB3); + MBB2->addSuccessor(MBB4); + MBB3->addSuccessor(MBB4); + + // Build tree and verify + auto MDT = new MachineDominatorTree(*MF); + EXPECT_TRUE(MDT->verify()); + + // Insert block splitting MBB1 (multiple sucessor) + auto NewMBB = MF->CreateMachineBasicBlock(MBB1->getBasicBlock()); + MachineFunction::iterator MBBI(MBB1); + ++MBBI; + MF->insert(MBBI, NewMBB); + NewMBB->transferSuccessorsAndUpdatePHIs(MBB1); + MBB1->addSuccessor(NewMBB); + + // Update tree + SmallVector DTUpdates; + for (MachineBasicBlock *Succ : NewMBB->successors()) { + DTUpdates.push_back({MachineDominatorTree::Insert, NewMBB, Succ}); + DTUpdates.push_back({MachineDominatorTree::Delete, MBB1, Succ}); + } + MDT->addNewBlock(NewMBB, MBB1); + MDT->applyUpdates(DTUpdates); + EXPECT_TRUE(MDT->verify()); +} + +static void buildCriticalFunction(LLVMContext &Ctx, llvm::Function &F, + llvm::MachineFunction *MF, + SmallVector &MBB) { + // Function: + // BB1 --> BB3 x BB4 --> BB6 + // \--> BB2 x BB5 ----^ + auto BB1 = BasicBlock::Create(Ctx, "a", &F); + auto BB2 = BasicBlock::Create(Ctx, "b", &F); + auto BB3 = BasicBlock::Create(Ctx, "c", &F); + auto BB4 = BasicBlock::Create(Ctx, "d", &F); + auto BB5 = BasicBlock::Create(Ctx, "e", &F); + auto BB6 = BasicBlock::Create(Ctx, "f", &F); + IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5), IRB6(BB6); + IRB1.CreateBr(BB2); + IRB1.CreateBr(BB3); + IRB2.CreateBr(BB4); + IRB2.CreateBr(BB5); + IRB3.CreateBr(BB4); + IRB3.CreateBr(BB5); + IRB4.CreateBr(BB6); + IRB5.CreateBr(BB6); + IRB6.CreateRetVoid(); + MBB.push_back(nullptr); // make block numbers match + auto MBB1 = MF->CreateMachineBasicBlock(BB1); + MF->insert(MF->end(), MBB1); + MBB.push_back(MBB1); + auto MBB2 = MF->CreateMachineBasicBlock(BB2); + MF->insert(MF->end(), MBB2); + MBB.push_back(MBB2); + auto MBB3 = MF->CreateMachineBasicBlock(BB3); + MF->insert(MF->end(), MBB3); + MBB.push_back(MBB3); + auto MBB4 = MF->CreateMachineBasicBlock(BB4); + MF->insert(MF->end(), MBB4); + MBB.push_back(MBB4); + auto MBB5 = MF->CreateMachineBasicBlock(BB5); + MF->insert(MF->end(), MBB5); + MBB.push_back(MBB5); + auto MBB6 = MF->CreateMachineBasicBlock(BB6); + MF->insert(MF->end(), MBB6); + MBB.push_back(MBB6); + MBB1->addSuccessor(MBB2); + MBB1->addSuccessor(MBB3); + MBB2->addSuccessor(MBB4); + MBB2->addSuccessor(MBB5); + MBB3->addSuccessor(MBB4); + MBB3->addSuccessor(MBB5); + MBB4->addSuccessor(MBB6); + MBB5->addSuccessor(MBB6); +} + +TEST(MachineDominatorTreeTest, addNewBlockWithCriticalEdges) { + LLVMContext Ctx; + Module Mod("test", Ctx); + + auto MF = createMachineFunction(Ctx, Mod); + SmallVector MBB; + llvm::Function &F = const_cast(MF->getFunction()); + buildCriticalFunction(Ctx, F, MF.get(), MBB); + + // Build tree and verify + auto MDT = new MachineDominatorTree(*MF); + EXPECT_TRUE(MDT->verify()); + + // Insert block splitting edge MBB2 -> MBB4 (critical edge) + auto NewMBB = MF->CreateMachineBasicBlock(MBB[2]->getBasicBlock()); + MachineFunction::iterator MBBI(MBB[2]); + ++MBBI; + MF->insert(MBBI, NewMBB); + NewMBB->addSuccessor(MBB[4]); + MBB[2]->replaceSuccessor(MBB[4], NewMBB); + + // Split block MBB6 + auto MBB7 = MF->CreateMachineBasicBlock(MBB[2]->getBasicBlock()); + MF->insert(MF->end(), MBB7); + MBB[6]->addSuccessor(MBB7); + + // Update tree + MDT->recordSplitCriticalEdge(MBB[2], MBB[4], NewMBB); + MDT->addNewBlock(MBB7, MBB[6]); + EXPECT_TRUE(MDT->verify()); +} + +TEST(MachineDominatorTreeTest, applyUpdatesWithCriticalEdges) { + LLVMContext Ctx; + Module Mod("test", Ctx); + + auto MF = createMachineFunction(Ctx, Mod); + SmallVector MBB; + llvm::Function &F = const_cast(MF->getFunction()); + buildCriticalFunction(Ctx, F, MF.get(), MBB); + + // Build tree and verify + auto MDT = new MachineDominatorTree(*MF); + EXPECT_TRUE(MDT->verify()); + + // Insert block splitting edge MBB2 -> MBB4 (critical edge) + auto NewMBB = MF->CreateMachineBasicBlock(MBB[2]->getBasicBlock()); + MachineFunction::iterator MBBI(MBB[2]); + ++MBBI; + MF->insert(MBBI, NewMBB); + NewMBB->addSuccessor(MBB[4]); + MBB[2]->replaceSuccessor(MBB[4], NewMBB); + + // Update tree + MDT->recordSplitCriticalEdge(MBB[2], MBB[4], NewMBB); + MDT->applyUpdates({}); + EXPECT_TRUE(MDT->verify()); +} diff --git a/llvm/unittests/CodeGen/MachinePostDominatorTreeTest.cpp b/llvm/unittests/CodeGen/MachinePostDominatorTreeTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/CodeGen/MachinePostDominatorTreeTest.cpp @@ -0,0 +1,117 @@ +//===- MachinePostDominatorTreeTest.cpp - MachinePostDominatorTree tests -===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/TargetFrameLowering.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetLowering.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/Support/TargetRegistry.h" + +#include "llvm/CodeGen/MachinePostDominators.h" + +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { +#include "MFCommon.inc" +} + +TEST(MachinePostDominatorTreeTest, addNewBlock) { + LLVMContext Ctx; + Module Mod("test", Ctx); + + // Function: + // BB1 -> BB2 + auto MF = createMachineFunction(Ctx, Mod); + llvm::Function &F = const_cast(MF->getFunction()); + auto BB1 = BasicBlock::Create(Ctx, "a", &F); + auto BB2 = BasicBlock::Create(Ctx, "b", &F); + IRBuilder<> IRB1(BB1), IRB2(BB2); + IRB1.CreateBr(BB2); + IRB2.CreateRetVoid(); + auto MBB1 = MF->CreateMachineBasicBlock(BB1); + MF->insert(MF->end(), MBB1); + auto MBB2 = MF->CreateMachineBasicBlock(BB2); + MF->insert(MF->end(), MBB2); + MBB1->addSuccessor(MBB2); + + // Build tree and verify + auto PDT = new MachinePostDominatorTree(); + PDT->runOnMachineFunction(*MF); + EXPECT_TRUE(PDT->verify()); + + // Insert block + auto NewMBB = MF->CreateMachineBasicBlock(MBB1->getBasicBlock()); + MachineFunction::iterator MBBI(MBB1); + ++MBBI; + MF->insert(MBBI, NewMBB); + MBB1->addSuccessor(NewMBB); + NewMBB->addSuccessor(MBB2); + + // Update tree + PDT->addNewBlock(NewMBB, MBB2); + EXPECT_TRUE(PDT->verify()); +} + +TEST(MachinePostDominatorTreeTest, applyUpdates) { + LLVMContext Ctx; + Module Mod("test", Ctx); + + // Function: + // BB1 --------> BB3 --> BB4 + // \--> BB2 --^ + auto MF = createMachineFunction(Ctx, Mod); + llvm::Function &F = const_cast(MF->getFunction()); + auto BB1 = BasicBlock::Create(Ctx, "a", &F); + auto BB2 = BasicBlock::Create(Ctx, "b", &F); + auto BB3 = BasicBlock::Create(Ctx, "c", &F); + auto BB4 = BasicBlock::Create(Ctx, "d", &F); + IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4); + IRB1.CreateBr(BB2); + IRB2.CreateBr(BB3); + IRB3.CreateBr(BB4); + IRB4.CreateRetVoid(); + auto MBB1 = MF->CreateMachineBasicBlock(); + MF->insert(MF->end(), MBB1); + auto MBB2 = MF->CreateMachineBasicBlock(BB2); + MF->insert(MF->end(), MBB2); + auto MBB3 = MF->CreateMachineBasicBlock(BB3); + MF->insert(MF->end(), MBB3); + auto MBB4 = MF->CreateMachineBasicBlock(BB4); + MF->insert(MF->end(), MBB4); + MBB1->addSuccessor(MBB2); + MBB1->addSuccessor(MBB3); + MBB2->addSuccessor(MBB4); + MBB3->addSuccessor(MBB4); + + // Build tree and verify + auto PDT = new MachinePostDominatorTree(); + PDT->runOnMachineFunction(*MF); + EXPECT_TRUE(PDT->verify()); + + // Insert block splitting MBB1 (multiple sucessor) + auto NewMBB = MF->CreateMachineBasicBlock(MBB1->getBasicBlock()); + MachineFunction::iterator MBBI(MBB1); + ++MBBI; + MF->insert(MBBI, NewMBB); + NewMBB->transferSuccessorsAndUpdatePHIs(MBB1); + MBB1->addSuccessor(NewMBB); + + // Update tree + SmallVector DTUpdates; + for (MachineBasicBlock *Succ : NewMBB->successors()) { + DTUpdates.push_back({MachineDominatorTree::Insert, NewMBB, Succ}); + DTUpdates.push_back({MachineDominatorTree::Delete, MBB1, Succ}); + } + PDT->addNewBlock(NewMBB, MBB1); + PDT->applyUpdates(DTUpdates); + EXPECT_TRUE(PDT->verify()); +}