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