llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp

   1 //===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
   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 "CFGBuilder.h"
  10 #include "llvm/Analysis/PostDominators.h"
  11 #include "llvm/IR/Dominators.h"
  12 #include "llvm/Support/GenericDomTreeConstruction.h"
  13 #include "gtest/gtest.h"
  14 #include <random>
  15
  16 #define DEBUG_TYPE "batch-update-tests"
  17
  18 using namespace llvm;
  19
  20 namespace {
  21 const auto CFGInsert = CFGBuilder::ActionKind::Insert;
  22 const auto CFGDelete = CFGBuilder::ActionKind::Delete;
  23
  24 using DomUpdate = DominatorTree::UpdateType;
  25 static_assert(
  26     std::is_same_v<DomUpdate, PostDominatorTree::UpdateType>,
  27     "Trees differing only in IsPostDom should have the same update types");
  28 using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
  29 using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
  30 const auto Insert = DominatorTree::Insert;
  31 const auto Delete = DominatorTree::Delete;
  32
  33 std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,
  34                                     std::vector<CFGBuilder::Update> &In) {
  35   std::vector<DomUpdate> Res;
  36   Res.reserve(In.size());
  37
  38   for (const auto &CFGU : In)
  39     Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete,
  40                    B.getOrAddBlock(CFGU.Edge.From),
  41                    B.getOrAddBlock(CFGU.Edge.To)});
  42   return Res;
  43 }
  44 }  // namespace
  45
  46 TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
  47   CFGHolder Holder;
  48   CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
  49
  50   BasicBlock *A = Builder.getOrAddBlock("A");
  51   BasicBlock *B = Builder.getOrAddBlock("B");
  52   BasicBlock *C = Builder.getOrAddBlock("C");
  53   BasicBlock *D = Builder.getOrAddBlock("D");
  54
  55   std::vector<DomUpdate> Updates = {
  56       {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
  57       {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
  58   SmallVector<DomUpdate, 4> Legalized;
  59   cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, false);
  60   LLVM_DEBUG(dbgs() << "Legalized updates:\t");
  61   LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
  62   LLVM_DEBUG(dbgs() << "\n");
  63   EXPECT_EQ(Legalized.size(), 3UL);
  64   EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, B, C}));
  65   EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, B, D}));
  66   EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Delete, A, B}));
  67 }
  68
  69 TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
  70   CFGHolder Holder;
  71   CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
  72
  73   BasicBlock *A = Builder.getOrAddBlock("A");
  74   BasicBlock *B = Builder.getOrAddBlock("B");
  75   BasicBlock *C = Builder.getOrAddBlock("C");
  76   BasicBlock *D = Builder.getOrAddBlock("D");
  77
  78   std::vector<DomUpdate> Updates = {
  79       {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
  80       {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
  81   SmallVector<DomUpdate, 4> Legalized;
  82   cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, true);
  83   LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");
  84   LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
  85   LLVM_DEBUG(dbgs() << "\n");
  86   EXPECT_EQ(Legalized.size(), 3UL);
  87   EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, C, B}));
  88   EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, D, B}));
  89   EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Delete, B, A}));
  90 }
  91
  92 TEST(DominatorTreeBatchUpdates, SingleInsertion) {
  93   CFGHolder Holder;
  94   CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});
  95
  96   DominatorTree DT(*Holder.F);
  97   EXPECT_TRUE(DT.verify());
  98   PostDominatorTree PDT(*Holder.F);
  99   EXPECT_TRUE(PDT.verify());
 100
 101   BasicBlock *B = Builder.getOrAddBlock("B");
 102   BasicBlock *C = Builder.getOrAddBlock("C");
 103   std::vector<DomUpdate> Updates = {{Insert, B, C}};
 104
 105   ASSERT_TRUE(Builder.applyUpdate());
 106
 107   DT.applyUpdates(Updates);
 108   EXPECT_TRUE(DT.verify());
 109   PDT.applyUpdates(Updates);
 110   EXPECT_TRUE(PDT.verify());
 111 }
 112
 113 TEST(DominatorTreeBatchUpdates, SingleDeletion) {
 114   CFGHolder Holder;
 115   CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},
 116                      {{CFGDelete, {"B", "C"}}});
 117
 118   DominatorTree DT(*Holder.F);
 119   EXPECT_TRUE(DT.verify());
 120   PostDominatorTree PDT(*Holder.F);
 121   EXPECT_TRUE(PDT.verify());
 122
 123   BasicBlock *B = Builder.getOrAddBlock("B");
 124   BasicBlock *C = Builder.getOrAddBlock("C");
 125   std::vector<DomUpdate> Updates = {{Delete, B, C}};
 126
 127   ASSERT_TRUE(Builder.applyUpdate());
 128
 129   DT.applyUpdates(Updates);
 130   EXPECT_TRUE(DT.verify());
 131   PDT.applyUpdates(Updates);
 132   EXPECT_TRUE(PDT.verify());
 133 }
 134
 135 TEST(DominatorTreeBatchUpdates, FewInsertion) {
 136   std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}},
 137                                                 {CFGInsert, {"C", "B"}},
 138                                                 {CFGInsert, {"C", "D"}},
 139                                                 {CFGInsert, {"D", "E"}}};
 140
 141   CFGHolder Holder;
 142   CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);
 143
 144   DominatorTree DT(*Holder.F);
 145   EXPECT_TRUE(DT.verify());
 146   PostDominatorTree PDT(*Holder.F);
 147   EXPECT_TRUE(PDT.verify());
 148
 149   BasicBlock *B = Builder.getOrAddBlock("B");
 150   BasicBlock *C = Builder.getOrAddBlock("C");
 151   BasicBlock *D = Builder.getOrAddBlock("D");
 152   BasicBlock *E = Builder.getOrAddBlock("E");
 153
 154   std::vector<DomUpdate> Updates = {
 155       {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}};
 156
 157   while (Builder.applyUpdate())
 158     ;
 159
 160   DT.applyUpdates(Updates);
 161   EXPECT_TRUE(DT.verify());
 162   PDT.applyUpdates(Updates);
 163   EXPECT_TRUE(PDT.verify());
 164 }
 165
 166 TEST(DominatorTreeBatchUpdates, FewDeletions) {
 167   std::vector<CFGBuilder::Update> CFGUpdates = {{CFGDelete, {"B", "C"}},
 168                                                 {CFGDelete, {"C", "B"}},
 169                                                 {CFGDelete, {"B", "D"}},
 170                                                 {CFGDelete, {"D", "E"}}};
 171
 172   CFGHolder Holder;
 173   CFGBuilder Builder(
 174       Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},
 175       CFGUpdates);
 176
 177   DominatorTree DT(*Holder.F);
 178   EXPECT_TRUE(DT.verify());
 179   PostDominatorTree PDT(*Holder.F);
 180   EXPECT_TRUE(PDT.verify());
 181
 182   auto Updates = ToDomUpdates(Builder, CFGUpdates);
 183
 184   while (Builder.applyUpdate())
 185     ;
 186
 187   DT.applyUpdates(Updates);
 188   EXPECT_TRUE(DT.verify());
 189   PDT.applyUpdates(Updates);
 190   EXPECT_TRUE(PDT.verify());
 191 }
 192
 193 TEST(DominatorTreeBatchUpdates, InsertDelete) {
 194   std::vector<CFGBuilder::Arc> Arcs = {
 195       {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
 196       {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
 197
 198   std::vector<CFGBuilder::Update> Updates = {
 199       {CFGInsert, {"2", "4"}},  {CFGInsert, {"12", "10"}},
 200       {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
 201       {CFGInsert, {"7", "5"}},  {CFGDelete, {"3", "8"}},
 202       {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
 203       {CFGDelete, {"3", "4"}},  {CFGDelete, {"8", "9"}},
 204       {CFGDelete, {"11", "12"}}};
 205
 206   CFGHolder Holder;
 207   CFGBuilder B(Holder.F, Arcs, Updates);
 208   DominatorTree DT(*Holder.F);
 209   EXPECT_TRUE(DT.verify());
 210   PostDominatorTree PDT(*Holder.F);
 211   EXPECT_TRUE(PDT.verify());
 212
 213   while (B.applyUpdate())
 214     ;
 215
 216   auto DomUpdates = ToDomUpdates(B, Updates);
 217   DT.applyUpdates(DomUpdates);
 218   EXPECT_TRUE(DT.verify());
 219   PDT.applyUpdates(DomUpdates);
 220   EXPECT_TRUE(PDT.verify());
 221 }
 222
 223 TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
 224   std::vector<CFGBuilder::Arc> Arcs = {
 225       {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
 226       {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
 227
 228   std::vector<CFGBuilder::Update> Updates = {
 229       {CFGInsert, {"2", "4"}},  {CFGInsert, {"12", "10"}},
 230       {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
 231       {CFGInsert, {"7", "5"}},  {CFGDelete, {"3", "8"}},
 232       {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
 233       {CFGDelete, {"3", "4"}},  {CFGDelete, {"8", "9"}},
 234       {CFGDelete, {"11", "12"}}};
 235
 236   std::mt19937 Generator(0);
 237   for (unsigned i = 0; i < 16; ++i) {
 238     std::shuffle(Updates.begin(), Updates.end(), Generator);
 239     CFGHolder Holder;
 240     CFGBuilder B(Holder.F, Arcs, Updates);
 241     DominatorTree DT(*Holder.F);
 242     EXPECT_TRUE(DT.verify());
 243     PostDominatorTree PDT(*Holder.F);
 244     EXPECT_TRUE(PDT.verify());
 245
 246     while (B.applyUpdate())
 247       ;
 248
 249     auto DomUpdates = ToDomUpdates(B, Updates);
 250     DT.applyUpdates(DomUpdates);
 251     EXPECT_TRUE(DT.verify());
 252     PDT.applyUpdates(DomUpdates);
 253     EXPECT_TRUE(PDT.verify());
 254   }
 255 }
 256
 257 // These are some odd flowgraphs, usually generated from csmith cases,
 258 // which are difficult on post dom trees.
 259 TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
 260   std::vector<CFGBuilder::Arc> Arcs = {
 261       {"1", "2"},
 262       {"2", "3"},
 263       {"3", "6"}, {"3", "5"},
 264       {"4", "5"},
 265       {"5", "2"},
 266       {"6", "3"}, {"6", "4"}};
 267
 268   // SplitBlock on 3 -> 5
 269   std::vector<CFGBuilder::Update> Updates = {
 270       {CFGInsert, {"N", "5"}},  {CFGInsert, {"3", "N"}}, {CFGDelete, {"3", "5"}}};
 271
 272   CFGHolder Holder;
 273   CFGBuilder B(Holder.F, Arcs, Updates);
 274   DominatorTree DT(*Holder.F);
 275   EXPECT_TRUE(DT.verify());
 276   PostDominatorTree PDT(*Holder.F);
 277   EXPECT_TRUE(PDT.verify());
 278
 279   while (B.applyUpdate())
 280     ;
 281
 282   auto DomUpdates = ToDomUpdates(B, Updates);
 283   DT.applyUpdates(DomUpdates);
 284   EXPECT_TRUE(DT.verify());
 285   PDT.applyUpdates(DomUpdates);
 286   EXPECT_TRUE(PDT.verify());
 287 }
 288
 289 TEST(DominatorTreeBatchUpdates, DeadBlocks) {
 290   std::vector<CFGBuilder::Arc> Arcs = {
 291       {"1", "2"},
 292       {"2", "3"},
 293       {"3", "4"}, {"3", "7"},
 294       {"4", "4"},
 295       {"5", "6"}, {"5", "7"},
 296       {"6", "7"},
 297       {"7", "2"}, {"7", "8"}};
 298
 299   // Remove dead 5 and 7,
 300   // plus SplitBlock on 7 -> 8
 301   std::vector<CFGBuilder::Update> Updates = {
 302       {CFGDelete, {"6", "7"}},  {CFGDelete, {"5", "7"}}, {CFGDelete, {"5", "6"}},
 303       {CFGInsert, {"N", "8"}},  {CFGInsert, {"7", "N"}}, {CFGDelete, {"7", "8"}}};
 304
 305   CFGHolder Holder;
 306   CFGBuilder B(Holder.F, Arcs, Updates);
 307   DominatorTree DT(*Holder.F);
 308   EXPECT_TRUE(DT.verify());
 309   PostDominatorTree PDT(*Holder.F);
 310   EXPECT_TRUE(PDT.verify());
 311
 312   while (B.applyUpdate())
 313     ;
 314
 315   auto DomUpdates = ToDomUpdates(B, Updates);
 316   DT.applyUpdates(DomUpdates);
 317   EXPECT_TRUE(DT.verify());
 318   PDT.applyUpdates(DomUpdates);
 319   EXPECT_TRUE(PDT.verify());
 320 }
 321
 322 TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
 323   std::vector<CFGBuilder::Arc> Arcs = {
 324       {"1", "2"},
 325       {"2", "6"}, {"2", "3"},
 326       {"3", "4"},
 327       {"4", "5"}, {"4", "6"},
 328       {"5", "4"},
 329       {"6", "2"}};
 330
 331   // SplitBlock on 4 -> 6
 332   std::vector<CFGBuilder::Update> Updates = {
 333       {CFGInsert, {"N", "6"}},  {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};
 334
 335   CFGHolder Holder;
 336   CFGBuilder B(Holder.F, Arcs, Updates);
 337   DominatorTree DT(*Holder.F);
 338   EXPECT_TRUE(DT.verify());
 339   PostDominatorTree PDT(*Holder.F);
 340   EXPECT_TRUE(PDT.verify());
 341
 342   while (B.applyUpdate())
 343     ;
 344
 345   auto DomUpdates = ToDomUpdates(B, Updates);
 346   DT.applyUpdates(DomUpdates);
 347   EXPECT_TRUE(DT.verify());
 348   PDT.applyUpdates(DomUpdates);
 349   EXPECT_TRUE(PDT.verify());
 350 }