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 struct PostDomTree : PostDomTreeBase<BasicBlock> { 26 PostDomTree(Function &F) { recalculate(F); } 27 }; 28 29 using DomUpdate = DominatorTree::UpdateType; 30 static_assert( 31 std::is_same<DomUpdate, PostDomTree::UpdateType>::value, 32 "Trees differing only in IsPostDom should have the same update types"); 33 using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>; 34 using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>; 35 const auto Insert = DominatorTree::Insert; 36 const auto Delete = DominatorTree::Delete; 37 38 std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B, 39 std::vector<CFGBuilder::Update> &In) { 40 std::vector<DomUpdate> Res; 41 Res.reserve(In.size()); 42 43 for (const auto &CFGU : In) 44 Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete, 45 B.getOrAddBlock(CFGU.Edge.From), 46 B.getOrAddBlock(CFGU.Edge.To)}); 47 return Res; 48 } 49 } // namespace 50 51 TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) { 52 CFGHolder Holder; 53 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {}); 54 55 BasicBlock *A = Builder.getOrAddBlock("A"); 56 BasicBlock *B = Builder.getOrAddBlock("B"); 57 BasicBlock *C = Builder.getOrAddBlock("C"); 58 BasicBlock *D = Builder.getOrAddBlock("D"); 59 60 std::vector<DomUpdate> Updates = { 61 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, 62 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; 63 SmallVector<DomUpdate, 4> Legalized; 64 DomSNCA::LegalizeUpdates(Updates, Legalized); 65 DEBUG(dbgs() << "Legalized updates:\t"); 66 DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); 67 DEBUG(dbgs() << "\n"); 68 EXPECT_EQ(Legalized.size(), 3UL); 69 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end()); 70 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end()); 71 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end()); 72 } 73 74 TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) { 75 CFGHolder Holder; 76 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {}); 77 78 BasicBlock *A = Builder.getOrAddBlock("A"); 79 BasicBlock *B = Builder.getOrAddBlock("B"); 80 BasicBlock *C = Builder.getOrAddBlock("C"); 81 BasicBlock *D = Builder.getOrAddBlock("D"); 82 83 std::vector<DomUpdate> Updates = { 84 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, 85 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; 86 SmallVector<DomUpdate, 4> Legalized; 87 PostDomSNCA::LegalizeUpdates(Updates, Legalized); 88 DEBUG(dbgs() << "Legalized postdom updates:\t"); 89 DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); 90 DEBUG(dbgs() << "\n"); 91 EXPECT_EQ(Legalized.size(), 3UL); 92 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end()); 93 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end()); 94 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end()); 95 } 96 97 TEST(DominatorTreeBatchUpdates, SingleInsertion) { 98 CFGHolder Holder; 99 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}}); 100 101 DominatorTree DT(*Holder.F); 102 EXPECT_TRUE(DT.verify()); 103 PostDomTree PDT(*Holder.F); 104 EXPECT_TRUE(DT.verify()); 105 106 BasicBlock *B = Builder.getOrAddBlock("B"); 107 BasicBlock *C = Builder.getOrAddBlock("C"); 108 std::vector<DomUpdate> Updates = {{Insert, B, C}}; 109 110 ASSERT_TRUE(Builder.applyUpdate()); 111 112 DT.applyUpdates(Updates); 113 EXPECT_TRUE(DT.verify()); 114 PDT.applyUpdates(Updates); 115 EXPECT_TRUE(PDT.verify()); 116 } 117 118 TEST(DominatorTreeBatchUpdates, SingleDeletion) { 119 CFGHolder Holder; 120 CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}}, 121 {{CFGDelete, {"B", "C"}}}); 122 123 DominatorTree DT(*Holder.F); 124 EXPECT_TRUE(DT.verify()); 125 PostDomTree PDT(*Holder.F); 126 EXPECT_TRUE(DT.verify()); 127 128 BasicBlock *B = Builder.getOrAddBlock("B"); 129 BasicBlock *C = Builder.getOrAddBlock("C"); 130 std::vector<DomUpdate> Updates = {{Delete, B, C}}; 131 132 ASSERT_TRUE(Builder.applyUpdate()); 133 134 DT.applyUpdates(Updates); 135 EXPECT_TRUE(DT.verify()); 136 PDT.applyUpdates(Updates); 137 EXPECT_TRUE(PDT.verify()); 138 } 139 140 TEST(DominatorTreeBatchUpdates, FewInsertion) { 141 std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}}, 142 {CFGInsert, {"C", "B"}}, 143 {CFGInsert, {"C", "D"}}, 144 {CFGInsert, {"D", "E"}}}; 145 146 CFGHolder Holder; 147 CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates); 148 149 DominatorTree DT(*Holder.F); 150 EXPECT_TRUE(DT.verify()); 151 PostDomTree PDT(*Holder.F); 152 EXPECT_TRUE(PDT.verify()); 153 154 BasicBlock *B = Builder.getOrAddBlock("B"); 155 BasicBlock *C = Builder.getOrAddBlock("C"); 156 BasicBlock *D = Builder.getOrAddBlock("D"); 157 BasicBlock *E = Builder.getOrAddBlock("E"); 158 159 std::vector<DomUpdate> Updates = { 160 {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}}; 161 162 while (Builder.applyUpdate()) 163 ; 164 165 DT.applyUpdates(Updates); 166 EXPECT_TRUE(DT.verify()); 167 PDT.applyUpdates(Updates); 168 EXPECT_TRUE(PDT.verify()); 169 } 170 171 TEST(DominatorTreeBatchUpdates, FewDeletions) { 172 std::vector<CFGBuilder::Update> CFGUpdates = {{CFGDelete, {"B", "C"}}, 173 {CFGDelete, {"C", "B"}}, 174 {CFGDelete, {"B", "D"}}, 175 {CFGDelete, {"D", "E"}}}; 176 177 CFGHolder Holder; 178 CFGBuilder Builder( 179 Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}}, 180 CFGUpdates); 181 182 DominatorTree DT(*Holder.F); 183 EXPECT_TRUE(DT.verify()); 184 PostDomTree PDT(*Holder.F); 185 EXPECT_TRUE(PDT.verify()); 186 187 auto Updates = ToDomUpdates(Builder, CFGUpdates); 188 189 while (Builder.applyUpdate()) 190 ; 191 192 DT.applyUpdates(Updates); 193 EXPECT_TRUE(DT.verify()); 194 PDT.applyUpdates(Updates); 195 EXPECT_TRUE(PDT.verify()); 196 } 197 198 TEST(DominatorTreeBatchUpdates, InsertDelete) { 199 std::vector<CFGBuilder::Arc> Arcs = { 200 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 201 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 202 203 std::vector<CFGBuilder::Update> Updates = { 204 {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}}, 205 {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}}, 206 {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}}, 207 {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}}, 208 {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}}, 209 {CFGDelete, {"11", "12"}}}; 210 211 CFGHolder Holder; 212 CFGBuilder B(Holder.F, Arcs, Updates); 213 DominatorTree DT(*Holder.F); 214 EXPECT_TRUE(DT.verify()); 215 PostDomTree PDT(*Holder.F); 216 EXPECT_TRUE(PDT.verify()); 217 218 while (B.applyUpdate()) 219 ; 220 221 auto DomUpdates = ToDomUpdates(B, Updates); 222 DT.applyUpdates(DomUpdates); 223 EXPECT_TRUE(DT.verify()); 224 PDT.applyUpdates(DomUpdates); 225 EXPECT_TRUE(PDT.verify()); 226 } 227 228 TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) { 229 std::vector<CFGBuilder::Arc> Arcs = { 230 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 231 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 232 233 std::vector<CFGBuilder::Update> Updates = { 234 {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}}, 235 {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}}, 236 {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}}, 237 {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}}, 238 {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}}, 239 {CFGDelete, {"11", "12"}}}; 240 241 std::mt19937 Generator(0); 242 for (unsigned i = 0; i < 16; ++i) { 243 std::shuffle(Updates.begin(), Updates.end(), Generator); 244 CFGHolder Holder; 245 CFGBuilder B(Holder.F, Arcs, Updates); 246 DominatorTree DT(*Holder.F); 247 EXPECT_TRUE(DT.verify()); 248 PostDomTree PDT(*Holder.F); 249 EXPECT_TRUE(PDT.verify()); 250 251 while (B.applyUpdate()) 252 ; 253 254 auto DomUpdates = ToDomUpdates(B, Updates); 255 DT.applyUpdates(DomUpdates); 256 EXPECT_TRUE(DT.verify()); 257 PDT.applyUpdates(DomUpdates); 258 EXPECT_TRUE(PDT.verify()); 259 } 260 } 261