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 DomSNCA::LegalizeUpdates(Updates, Legalized); 62 LLVM_DEBUG(dbgs() << "Legalized updates:\t"); 63 LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); 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 PostDomSNCA::LegalizeUpdates(Updates, Legalized); 85 LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t"); 86 LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); 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 } 353