aboutsummaryrefslogtreecommitdiff
path: root/unittests/IR
diff options
context:
space:
mode:
Diffstat (limited to 'unittests/IR')
-rw-r--r--unittests/IR/CFGBuilder.cpp269
-rw-r--r--unittests/IR/CFGBuilder.h94
-rw-r--r--unittests/IR/CMakeLists.txt1
-rw-r--r--unittests/IR/DominatorTreeTest.cpp300
-rw-r--r--unittests/IR/IRBuilderTest.cpp11
-rw-r--r--unittests/IR/MetadataTest.cpp24
6 files changed, 674 insertions, 25 deletions
diff --git a/unittests/IR/CFGBuilder.cpp b/unittests/IR/CFGBuilder.cpp
new file mode 100644
index 000000000000..50494ab5c7ca
--- /dev/null
+++ b/unittests/IR/CFGBuilder.cpp
@@ -0,0 +1,269 @@
+//===- llvm/Testing/Support/CFGBuilder.cpp --------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "CFGBuilder.h"
+
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/TypeBuilder.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest.h"
+
+#define DEBUG_TYPE "cfg-builder"
+
+using namespace llvm;
+
+CFGHolder::CFGHolder(StringRef ModuleName, StringRef FunctionName)
+ : Context(llvm::make_unique<LLVMContext>()),
+ M(llvm::make_unique<Module>(ModuleName, *Context)) {
+ FunctionType *FTy = TypeBuilder<void(), false>::get(*Context);
+ F = cast<Function>(M->getOrInsertFunction(FunctionName, FTy));
+}
+CFGHolder::~CFGHolder() = default;
+
+CFGBuilder::CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
+ std::vector<Update> Updates)
+ : F(F), Updates(std::move(Updates)) {
+ assert(F);
+ buildCFG(InitialArcs);
+}
+
+static void ConnectBlocks(BasicBlock *From, BasicBlock *To) {
+ DEBUG(dbgs() << "Creating BB arc " << From->getName() << " -> "
+ << To->getName() << "\n";
+ dbgs().flush());
+ auto *IntTy = IntegerType::get(From->getContext(), 32);
+
+ if (isa<UnreachableInst>(From->getTerminator()))
+ From->getTerminator()->eraseFromParent();
+ if (!From->getTerminator()) {
+ IRBuilder<> IRB(From);
+ IRB.CreateSwitch(ConstantInt::get(IntTy, 0), To);
+ return;
+ }
+
+ SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
+ const auto Last = SI->getNumCases();
+
+ auto *IntVal = ConstantInt::get(IntTy, Last);
+ SI->addCase(IntVal, To);
+}
+
+static void DisconnectBlocks(BasicBlock *From, BasicBlock *To) {
+ DEBUG(dbgs() << "Deleting BB arc " << From->getName() << " -> "
+ << To->getName() << "\n";
+ dbgs().flush());
+ SwitchInst *SI = cast<SwitchInst>(From->getTerminator());
+
+ if (SI->getNumCases() == 0) {
+ SI->eraseFromParent();
+ IRBuilder<> IRB(From);
+ IRB.CreateUnreachable();
+ return;
+ }
+
+ if (SI->getDefaultDest() == To) {
+ auto FirstC = SI->case_begin();
+ SI->setDefaultDest(FirstC->getCaseSuccessor());
+ SI->removeCase(FirstC);
+ return;
+ }
+
+ for (auto CIt = SI->case_begin(); CIt != SI->case_end(); ++CIt)
+ if (CIt->getCaseSuccessor() == To) {
+ SI->removeCase(CIt);
+ return;
+ }
+}
+
+BasicBlock *CFGBuilder::getOrAddBlock(StringRef BlockName) {
+ auto BIt = NameToBlock.find(BlockName);
+ if (BIt != NameToBlock.end())
+ return BIt->second;
+
+ auto *BB = BasicBlock::Create(F->getParent()->getContext(), BlockName, F);
+ IRBuilder<> IRB(BB);
+ IRB.CreateUnreachable();
+ NameToBlock[BlockName] = BB;
+ return BB;
+}
+
+bool CFGBuilder::connect(const Arc &A) {
+ BasicBlock *From = getOrAddBlock(A.From);
+ BasicBlock *To = getOrAddBlock(A.To);
+ if (Arcs.count(A) != 0)
+ return false;
+
+ Arcs.insert(A);
+ ConnectBlocks(From, To);
+ return true;
+}
+
+bool CFGBuilder::disconnect(const Arc &A) {
+ assert(NameToBlock.count(A.From) != 0 && "No block to disconnect (From)");
+ assert(NameToBlock.count(A.To) != 0 && "No block to disconnect (To)");
+ if (Arcs.count(A) == 0)
+ return false;
+
+ BasicBlock *From = getOrAddBlock(A.From);
+ BasicBlock *To = getOrAddBlock(A.To);
+ Arcs.erase(A);
+ DisconnectBlocks(From, To);
+ return true;
+}
+
+void CFGBuilder::buildCFG(const std::vector<Arc> &NewArcs) {
+ for (const auto &A : NewArcs) {
+ const bool Connected = connect(A);
+ (void)Connected;
+ assert(Connected);
+ }
+}
+
+Optional<CFGBuilder::Update> CFGBuilder::getNextUpdate() const {
+ if (UpdateIdx == Updates.size())
+ return None;
+ return Updates[UpdateIdx];
+}
+
+Optional<CFGBuilder::Update> CFGBuilder::applyUpdate() {
+ if (UpdateIdx == Updates.size())
+ return None;
+ Update NextUpdate = Updates[UpdateIdx++];
+ if (NextUpdate.Action == ActionKind::Insert)
+ connect(NextUpdate.Edge);
+ else
+ disconnect(NextUpdate.Edge);
+
+ return NextUpdate;
+}
+
+void CFGBuilder::dump(raw_ostream &OS) const {
+ OS << "Arcs:\n";
+ size_t i = 0;
+ for (const auto &A : Arcs)
+ OS << " " << i++ << ":\t" << A.From << " -> " << A.To << "\n";
+
+ OS << "Updates:\n";
+ i = 0;
+ for (const auto &U : Updates) {
+ OS << (i + 1 == UpdateIdx ? "->" : " ") << i
+ << ((U.Action == ActionKind::Insert) ? "\tIns " : "\tDel ")
+ << U.Edge.From << " -> " << U.Edge.To << "\n";
+ ++i;
+ }
+}
+
+//---- CFGBuilder tests ---------------------------------------------------===//
+
+TEST(CFGBuilder, Construction) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {{"entry", "a"}, {"a", "b"}, {"a", "c"},
+ {"c", "d"}, {"d", "b"}, {"d", "e"},
+ {"d", "f"}, {"e", "f"}};
+ CFGBuilder B(Holder.F, Arcs, {});
+
+ EXPECT_TRUE(B.getOrAddBlock("entry") == &Holder.F->getEntryBlock());
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+ EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("b")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+
+ auto *DSwitch = cast<SwitchInst>(B.getOrAddBlock("d")->getTerminator());
+ // d has 3 successors, but one of them if going to be a default case
+ EXPECT_EQ(DSwitch->getNumCases(), 2U);
+ EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.
+}
+
+TEST(CFGBuilder, Insertions) {
+ CFGHolder Holder;
+ const auto Insert = CFGBuilder::ActionKind::Insert;
+ std::vector<CFGBuilder::Update> Updates = {
+ {Insert, {"entry", "a"}}, {Insert, {"a", "b"}}, {Insert, {"a", "c"}},
+ {Insert, {"c", "d"}}, {Insert, {"d", "b"}}, {Insert, {"d", "e"}},
+ {Insert, {"d", "f"}}, {Insert, {"e", "f"}}};
+ const size_t NumUpdates = Updates.size();
+
+ CFGBuilder B(Holder.F, {}, Updates);
+
+ size_t i = 0;
+ while (B.applyUpdate())
+ ++i;
+ EXPECT_EQ(i, NumUpdates);
+
+ EXPECT_TRUE(B.getOrAddBlock("entry") == &Holder.F->getEntryBlock());
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+ EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("b")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+
+ auto *DSwitch = cast<SwitchInst>(B.getOrAddBlock("d")->getTerminator());
+ // d has 3 successors, but one of them if going to be a default case
+ EXPECT_EQ(DSwitch->getNumCases(), 2U);
+ EXPECT_FALSE(B.getNextUpdate()); // No updates to apply.
+}
+
+TEST(CFGBuilder, Deletions) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
+ const auto Delete = CFGBuilder::ActionKind::Delete;
+ std::vector<CFGBuilder::Update> Updates = {
+ {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
+ };
+ const size_t NumUpdates = Updates.size();
+
+ CFGBuilder B(Holder.F, Arcs, Updates);
+
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("c")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+
+ auto UpdateC = B.applyUpdate();
+
+ EXPECT_TRUE(UpdateC);
+ EXPECT_EQ(UpdateC->Action, CFGBuilder::ActionKind::Delete);
+ EXPECT_EQ(UpdateC->Edge.From, "c");
+ EXPECT_EQ(UpdateC->Edge.To, "d");
+ EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("c")->getTerminator()));
+
+ size_t i = 1;
+ while (B.applyUpdate())
+ ++i;
+ EXPECT_EQ(i, NumUpdates);
+
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+ EXPECT_TRUE(isa<UnreachableInst>(B.getOrAddBlock("entry")->getTerminator()));
+}
+
+TEST(CFGBuilder, Rebuild) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"entry", "a"}, {"a", "b"}, {"a", "c"}, {"c", "d"}, {"d", "b"}};
+ const auto Insert = CFGBuilder::ActionKind::Insert;
+ const auto Delete = CFGBuilder::ActionKind::Delete;
+ std::vector<CFGBuilder::Update> Updates = {
+ {Delete, {"c", "d"}}, {Delete, {"a", "c"}}, {Delete, {"entry", "a"}},
+ {Insert, {"c", "d"}}, {Insert, {"a", "c"}}, {Insert, {"entry", "a"}},
+ };
+ const size_t NumUpdates = Updates.size();
+
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ size_t i = 0;
+ while (B.applyUpdate())
+ ++i;
+ EXPECT_EQ(i, NumUpdates);
+
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("entry")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("a")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("c")->getTerminator()));
+ EXPECT_TRUE(isa<SwitchInst>(B.getOrAddBlock("d")->getTerminator()));
+}
diff --git a/unittests/IR/CFGBuilder.h b/unittests/IR/CFGBuilder.h
new file mode 100644
index 000000000000..d9d9c378e110
--- /dev/null
+++ b/unittests/IR/CFGBuilder.h
@@ -0,0 +1,94 @@
+//===- CFGBuilder.h - CFG building and updating utility ----------*- C++ -*-==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// CFGBuilders provides utilities fo building and updating CFG for testing
+/// purposes.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_CFG_BUILDER_H
+#define LLVM_UNITTESTS_CFG_BUILDER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Debug.h"
+
+#include <memory>
+#include <set>
+#include <tuple>
+#include <vector>
+
+namespace llvm {
+
+class LLVMContext;
+class Module;
+class Function;
+class BasicBlock;
+class raw_ostream;
+
+struct CFGHolder {
+ std::unique_ptr<LLVMContext> Context;
+ std::unique_ptr<Module> M;
+ Function *F;
+
+ CFGHolder(StringRef ModuleName = "m", StringRef FunctionName = "foo");
+ ~CFGHolder(); // Defined in the .cpp file so we can use forward declarations.
+};
+
+/// \brief
+/// CFGBuilder builds IR with specific CFG, based on the supplied list of arcs.
+/// It's able to apply the provided updates and automatically modify the IR.
+///
+/// Internally it makes every basic block end with either SwitchInst or with
+/// UnreachableInst. When all arc to a BB are deleted, the BB remains in the
+/// function and doesn't get deleted.
+///
+class CFGBuilder {
+public:
+ struct Arc {
+ StringRef From;
+ StringRef To;
+
+ friend bool operator<(const Arc &LHS, const Arc &RHS) {
+ return std::tie(LHS.From, LHS.To) <
+ std::tie(RHS.From, RHS.To);
+ }
+ };
+
+ enum class ActionKind { Insert, Delete };
+ struct Update {
+ ActionKind Action;
+ Arc Edge;
+ };
+
+ CFGBuilder(Function *F, const std::vector<Arc> &InitialArcs,
+ std::vector<Update> Updates);
+
+ BasicBlock *getOrAddBlock(StringRef BlockName);
+ Optional<Update> getNextUpdate() const;
+ Optional<Update> applyUpdate();
+ void dump(raw_ostream &OS = dbgs()) const;
+
+private:
+ void buildCFG(const std::vector<Arc> &Arcs);
+ bool connect(const Arc &A);
+ bool disconnect(const Arc &A);
+
+ Function *F;
+ unsigned UpdateIdx = 0;
+ StringMap<BasicBlock *> NameToBlock;
+ std::set<Arc> Arcs;
+ std::vector<Update> Updates;
+};
+
+} // namespace llvm
+
+#endif
diff --git a/unittests/IR/CMakeLists.txt b/unittests/IR/CMakeLists.txt
index d76ebfa64d88..92c9f8d3788d 100644
--- a/unittests/IR/CMakeLists.txt
+++ b/unittests/IR/CMakeLists.txt
@@ -10,6 +10,7 @@ set(IRSources
AsmWriterTest.cpp
AttributesTest.cpp
BasicBlockTest.cpp
+ CFGBuilder.cpp
ConstantRangeTest.cpp
ConstantsTest.cpp
DebugInfoTest.cpp
diff --git a/unittests/IR/DominatorTreeTest.cpp b/unittests/IR/DominatorTreeTest.cpp
index fa3dad8a2ab1..df1e2993dc85 100644
--- a/unittests/IR/DominatorTreeTest.cpp
+++ b/unittests/IR/DominatorTreeTest.cpp
@@ -7,6 +7,7 @@
//
//===----------------------------------------------------------------------===//
+#include <random>
#include "llvm/Analysis/PostDominators.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Constants.h"
@@ -15,22 +16,24 @@
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/SourceMgr.h"
+#include "CFGBuilder.h"
#include "gtest/gtest.h"
using namespace llvm;
+struct PostDomTree : PostDomTreeBase<BasicBlock> {
+ PostDomTree(Function &F) { recalculate(F); }
+};
+
/// Build the dominator tree for the function and run the Test.
-static void
-runWithDomTree(Module &M, StringRef FuncName,
- function_ref<void(Function &F, DominatorTree *DT,
- DominatorTreeBase<BasicBlock> *PDT)>
- Test) {
+static void runWithDomTree(
+ Module &M, StringRef FuncName,
+ function_ref<void(Function &F, DominatorTree *DT, PostDomTree *PDT)> Test) {
auto *F = M.getFunction(FuncName);
ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
// Compute the dominator tree for the function.
DominatorTree DT(*F);
- DominatorTreeBase<BasicBlock> PDT(/*isPostDom*/ true);
- PDT.recalculate(*F);
+ PostDomTree PDT(*F);
Test(*F, &DT, &PDT);
}
@@ -72,8 +75,7 @@ TEST(DominatorTree, Unreachable) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f",
- [&](Function &F, DominatorTree *DT, DominatorTreeBase<BasicBlock> *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
Function::iterator FI = F.begin();
BasicBlock *BB0 = &*FI++;
@@ -293,8 +295,7 @@ TEST(DominatorTree, NonUniqueEdges) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f",
- [&](Function &F, DominatorTree *DT, DominatorTreeBase<BasicBlock> *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
Function::iterator FI = F.begin();
BasicBlock *BB0 = &*FI++;
@@ -324,3 +325,280 @@ TEST(DominatorTree, NonUniqueEdges) {
EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2));
});
}
+
+namespace {
+const auto Insert = CFGBuilder::ActionKind::Insert;
+const auto Delete = CFGBuilder::ActionKind::Delete;
+
+bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) {
+ return std::tie(A.Action, A.Edge.From, A.Edge.To) <
+ std::tie(B.Action, B.Edge.From, B.Edge.To);
+}
+} // namespace
+
+TEST(DominatorTree, InsertReachable) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+ std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}},
+ {Insert, {"10", "9"}},
+ {Insert, {"7", "6"}},
+ {Insert, {"7", "5"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Insert);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.insertEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.insertEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertReachable2) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"},
+ {"10", "9"}, {"9", "10"}};
+
+ std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
+ EXPECT_TRUE(LastUpdate);
+
+ EXPECT_EQ(LastUpdate->Action, Insert);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.insertEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.insertEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTree, InsertUnreachable) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"},
+ {"5", "6"}, {"5", "7"}, {"3", "8"},
+ {"9", "10"}, {"11", "12"}};
+
+ std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},
+ {Insert, {"8", "9"}},
+ {Insert, {"10", "12"}},
+ {Insert, {"10", "11"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Insert);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.insertEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.insertEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertMixed) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"},
+ {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}},
+ {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}},
+ {Insert, {"7", "5"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Insert);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.insertEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.insertEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertPermut) {
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"},
+ {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};
+
+ std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},
+ {Insert, {"2", "5"}},
+ {Insert, {"10", "9"}},
+ {Insert, {"12", "10"}}};
+
+ while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) {
+ CFGHolder Holder;
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Insert);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.insertEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.insertEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+ }
+}
+
+TEST(DominatorTree, DeleteReachable) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"},
+ {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Delete);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.deleteEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.deleteEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, DeleteUnreachable) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Delete);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.deleteEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.deleteEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertDelete) {
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
+ {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}},
+ {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}},
+ {Delete, {"8", "9"}}, {Delete, {"11", "12"}}};
+
+ CFGHolder Holder;
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ if (LastUpdate->Action == Insert) {
+ DT.insertEdge(From, To);
+ PDT.insertEdge(From, To);
+ } else {
+ DT.deleteEdge(From, To);
+ PDT.deleteEdge(From, To);
+ }
+
+ EXPECT_TRUE(DT.verify());
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertDeleteExhaustive) {
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
+ {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}},
+ {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}},
+ {Delete, {"8", "9"}}, {Delete, {"11", "12"}}};
+
+ std::mt19937 Generator(0);
+ for (unsigned i = 0; i < 16; ++i) {
+ std::shuffle(Updates.begin(), Updates.end(), Generator);
+ CFGHolder Holder;
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ if (LastUpdate->Action == Insert) {
+ DT.insertEdge(From, To);
+ PDT.insertEdge(From, To);
+ } else {
+ DT.deleteEdge(From, To);
+ PDT.deleteEdge(From, To);
+ }
+
+ EXPECT_TRUE(DT.verify());
+ EXPECT_TRUE(PDT.verify());
+ }
+ }
+}
diff --git a/unittests/IR/IRBuilderTest.cpp b/unittests/IR/IRBuilderTest.cpp
index 186330f10573..d361107cc0d2 100644
--- a/unittests/IR/IRBuilderTest.cpp
+++ b/unittests/IR/IRBuilderTest.cpp
@@ -463,13 +463,14 @@ TEST_F(IRBuilderTest, DebugLoc) {
TEST_F(IRBuilderTest, DIImportedEntity) {
IRBuilder<> Builder(BB);
DIBuilder DIB(*M);
+ auto F = DIB.createFile("F.CBL", "/");
auto CU = DIB.createCompileUnit(dwarf::DW_LANG_Cobol74,
- DIB.createFile("F.CBL", "/"), "llvm-cobol74",
+ F, "llvm-cobol74",
true, "", 0);
- DIB.createImportedDeclaration(CU, nullptr, 1);
- DIB.createImportedDeclaration(CU, nullptr, 1);
- DIB.createImportedModule(CU, (DIImportedEntity *)nullptr, 2);
- DIB.createImportedModule(CU, (DIImportedEntity *)nullptr, 2);
+ DIB.createImportedDeclaration(CU, nullptr, F, 1);
+ DIB.createImportedDeclaration(CU, nullptr, F, 1);
+ DIB.createImportedModule(CU, (DIImportedEntity *)nullptr, F, 2);
+ DIB.createImportedModule(CU, (DIImportedEntity *)nullptr, F, 2);
DIB.finalize();
EXPECT_TRUE(verifyModule(*M));
EXPECT_TRUE(CU->getImportedEntities().size() == 2);
diff --git a/unittests/IR/MetadataTest.cpp b/unittests/IR/MetadataTest.cpp
index cb38b30f43e6..e47afca532d2 100644
--- a/unittests/IR/MetadataTest.cpp
+++ b/unittests/IR/MetadataTest.cpp
@@ -2116,29 +2116,35 @@ TEST_F(DIImportedEntityTest, get) {
unsigned Tag = dwarf::DW_TAG_imported_module;
DIScope *Scope = getSubprogram();
DINode *Entity = getCompositeType();
+ DIFile *File = getFile();
unsigned Line = 5;
StringRef Name = "name";
- auto *N = DIImportedEntity::get(Context, Tag, Scope, Entity, Line, Name);
+ auto *N =
+ DIImportedEntity::get(Context, Tag, Scope, Entity, File, Line, Name);
EXPECT_EQ(Tag, N->getTag());
EXPECT_EQ(Scope, N->getScope());
EXPECT_EQ(Entity, N->getEntity());
+ EXPECT_EQ(File, N->getFile());
EXPECT_EQ(Line, N->getLine());
EXPECT_EQ(Name, N->getName());
- EXPECT_EQ(N, DIImportedEntity::get(Context, Tag, Scope, Entity, Line, Name));
+ EXPECT_EQ(
+ N, DIImportedEntity::get(Context, Tag, Scope, Entity, File, Line, Name));
EXPECT_NE(N,
DIImportedEntity::get(Context, dwarf::DW_TAG_imported_declaration,
- Scope, Entity, Line, Name));
+ Scope, Entity, File, Line, Name));
EXPECT_NE(N, DIImportedEntity::get(Context, Tag, getSubprogram(), Entity,
- Line, Name));
+ File, Line, Name));
EXPECT_NE(N, DIImportedEntity::get(Context, Tag, Scope, getCompositeType(),
- Line, Name));
- EXPECT_NE(N,
- DIImportedEntity::get(Context, Tag, Scope, Entity, Line + 1, Name));
- EXPECT_NE(N,
- DIImportedEntity::get(Context, Tag, Scope, Entity, Line, "other"));
+ File, Line, Name));
+ EXPECT_NE(N, DIImportedEntity::get(Context, Tag, Scope, Entity, nullptr, Line,
+ Name));
+ EXPECT_NE(N, DIImportedEntity::get(Context, Tag, Scope, Entity, File,
+ Line + 1, Name));
+ EXPECT_NE(N, DIImportedEntity::get(Context, Tag, Scope, Entity, File, Line,
+ "other"));
TempDIImportedEntity Temp = N->clone();
EXPECT_EQ(N, MDNode::replaceWithUniqued(std::move(Temp)));
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-23 15:30:47 +0000