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 } 351