llvm/unittests/Support/GenericDomTreeTest.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-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