110 lines · cpp
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-exception6//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"13using namespace llvm;14 15namespace {16 17// Very simple (fake) graph structure to test dominator tree on.18struct NumberedGraph;19 20struct 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 30struct 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} // namespace40 41namespace llvm {42template <> struct GraphTraits<NumberedNode *> {43 using NodeRef = NumberedNode *;44 static unsigned getNumber(NumberedNode *Node) { return Node->Number; }45};46 47template <> struct GraphTraits<const NumberedNode *> {48 using NodeRef = NumberedNode *;49 static unsigned getNumber(const NumberedNode *Node) { return Node->Number; }50};51 52template <> 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 58namespace DomTreeBuilder {59// Dummy specialization. Only needed so that we can call recalculate(), which60// sets DT.Parent -- but we can't access DT.Parent here.61template <> void Calculate(DomTreeBase<NumberedNode> &DT) {}62} // end namespace DomTreeBuilder63} // end namespace llvm64 65namespace {66 67TEST(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 parent74 // Construct fake domtree: node 0 dominates all other nodes75 DT.setNewRoot(N1);76 DT.addNewBlock(N2, N1);77 78 // Roundtrip is correct79 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 map91 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 problem96 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} // namespace110