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