1 //===- unittests/Support/GenericDomTreeTest.cpp - GenericDomTree.h tests --===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Support/GenericDomTree.h" 10 #include "llvm/ADT/GraphTraits.h" 11 #include "llvm/Support/DataTypes.h" 12 #include "gtest/gtest.h" 13 using namespace llvm; 14 15 namespace { 16 17 // Very simple (fake) graph structure to test dominator tree on. 18 struct NumberedGraph; 19 20 struct NumberedNode { 21 NumberedGraph *Parent; 22 unsigned Number; 23 24 NumberedNode(NumberedGraph *Parent, unsigned Number) 25 : Parent(Parent), Number(Number) {} 26 27 NumberedGraph *getParent() const { return Parent; } 28 }; 29 30 struct NumberedGraph { 31 SmallVector<std::unique_ptr<NumberedNode>> Nodes; 32 unsigned NumberEpoch = 0; 33 34 NumberedNode *addNode() { 35 unsigned Num = Nodes.size(); 36 return Nodes.emplace_back(std::make_unique<NumberedNode>(this, Num)).get(); 37 } 38 }; 39 } // namespace 40 41 namespace llvm { 42 template <> struct GraphTraits<NumberedNode *> { 43 using NodeRef = NumberedNode *; 44 static unsigned getNumber(NumberedNode *Node) { return Node->Number; } 45 }; 46 47 template <> struct GraphTraits<const NumberedNode *> { 48 using NodeRef = NumberedNode *; 49 static unsigned getNumber(const NumberedNode *Node) { return Node->Number; } 50 }; 51 52 template <> struct GraphTraits<NumberedGraph *> { 53 using NodeRef = NumberedNode *; 54 static unsigned getMaxNumber(NumberedGraph *G) { return G->Nodes.size(); } 55 static unsigned getNumberEpoch(NumberedGraph *G) { return G->NumberEpoch; } 56 }; 57 58 namespace DomTreeBuilder { 59 // Dummy specialization. Only needed so that we can call recalculate(), which 60 // sets DT.Parent -- but we can't access DT.Parent here. 61 template <> void Calculate(DomTreeBase<NumberedNode> &DT) {} 62 } // end namespace DomTreeBuilder 63 } // end namespace llvm 64 65 namespace { 66 67 TEST(GenericDomTree, BlockNumbers) { 68 NumberedGraph G; 69 NumberedNode *N1 = G.addNode(); 70 NumberedNode *N2 = G.addNode(); 71 72 DomTreeBase<NumberedNode> DT; 73 DT.recalculate(G); // only sets parent 74 // Construct fake domtree: node 0 dominates all other nodes 75 DT.setNewRoot(N1); 76 DT.addNewBlock(N2, N1); 77 78 // Roundtrip is correct 79 for (auto &N : G.Nodes) 80 EXPECT_EQ(DT.getNode(N.get())->getBlock(), N.get()); 81 // If we manually change a number, we should get a different node. 82 ASSERT_EQ(N1->Number, 0u); 83 ASSERT_EQ(N2->Number, 1u); 84 N1->Number = 1; 85 EXPECT_EQ(DT.getNode(N1)->getBlock(), N2); 86 EXPECT_EQ(DT.getNode(N2)->getBlock(), N2); 87 N2->Number = 0; 88 EXPECT_EQ(DT.getNode(N2)->getBlock(), N1); 89 90 // Renumer blocks, should fix node domtree-internal node map 91 DT.updateBlockNumbers(); 92 for (auto &N : G.Nodes) 93 EXPECT_EQ(DT.getNode(N.get())->getBlock(), N.get()); 94 95 // Adding a new node with a higher number is no problem 96 NumberedNode *N3 = G.addNode(); 97 EXPECT_EQ(DT.getNode(N3), nullptr); 98 // ... even if it exceeds getMaxNumber() 99 NumberedNode *N4 = G.addNode(); 100 N4->Number = 1000; 101 EXPECT_EQ(DT.getNode(N4), nullptr); 102 103 DT.addNewBlock(N3, N1); 104 DT.addNewBlock(N4, N1); 105 for (auto &N : G.Nodes) 106 EXPECT_EQ(DT.getNode(N.get())->getBlock(), N.get()); 107 } 108 109 } // namespace 110