unittests/IR/DominatorTreeBatchUpdatesTest.cpp

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