Mercurial > hg > CbC > CbC_llvm

comparison unittests/IR/DominatorTreeBatchUpdatesTest.cpp @ 147:c2174574ed3a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 10
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 14 Aug 2019 16:55:33 +0900
parents 3a76565eade5
children
comparison
equal deleted inserted replaced
134:3a76565eade5 147:c2174574ed3a
1 //===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===// 1 //===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // 4 // See https://llvm.org/LICENSE.txt for license information.
5 // This file is distributed under the University of Illinois Open Source 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 // License. See LICENSE.TXT for details.
7 // 6 //
8 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
9 8
10 #include <random> 9 #include <random>
11 #include "CFGBuilder.h" 10 #include "CFGBuilder.h"
20 19
21 namespace { 20 namespace {
22 const auto CFGInsert = CFGBuilder::ActionKind::Insert; 21 const auto CFGInsert = CFGBuilder::ActionKind::Insert;
23 const auto CFGDelete = CFGBuilder::ActionKind::Delete; 22 const auto CFGDelete = CFGBuilder::ActionKind::Delete;
24 23
25 struct PostDomTree : PostDomTreeBase<BasicBlock> {
26 PostDomTree(Function &F) { recalculate(F); }
27 };
28 24
29 using DomUpdate = DominatorTree::UpdateType; 25 using DomUpdate = DominatorTree::UpdateType;
30 static_assert( 26 static_assert(
31 std::is_same<DomUpdate, PostDomTree::UpdateType>::value, 27 std::is_same<DomUpdate, PostDominatorTree::UpdateType>::value,
32 "Trees differing only in IsPostDom should have the same update types"); 28 "Trees differing only in IsPostDom should have the same update types");
33 using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>; 29 using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
34 using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>; 30 using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
35 const auto Insert = DominatorTree::Insert; 31 const auto Insert = DominatorTree::Insert;
36 const auto Delete = DominatorTree::Delete; 32 const auto Delete = DominatorTree::Delete;
59 55
60 std::vector<DomUpdate> Updates = { 56 std::vector<DomUpdate> Updates = {
61 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, 57 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
62 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; 58 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
63 SmallVector<DomUpdate, 4> Legalized; 59 SmallVector<DomUpdate, 4> Legalized;
64 DomSNCA::LegalizeUpdates(Updates, Legalized); 60 cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, false);
65 DEBUG(dbgs() << "Legalized updates:\t"); 61 LLVM_DEBUG(dbgs() << "Legalized updates:\t");
66 DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); 62 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
67 DEBUG(dbgs() << "\n"); 63 LLVM_DEBUG(dbgs() << "\n");
68 EXPECT_EQ(Legalized.size(), 3UL); 64 EXPECT_EQ(Legalized.size(), 3UL);
69 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end()); 65 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end());
70 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end()); 66 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end());
71 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end()); 67 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end());
72 } 68 }
82 78
83 std::vector<DomUpdate> Updates = { 79 std::vector<DomUpdate> Updates = {
84 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, 80 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
85 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; 81 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
86 SmallVector<DomUpdate, 4> Legalized; 82 SmallVector<DomUpdate, 4> Legalized;
87 PostDomSNCA::LegalizeUpdates(Updates, Legalized); 83 cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, true);
88 DEBUG(dbgs() << "Legalized postdom updates:\t"); 84 LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");
89 DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); 85 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
90 DEBUG(dbgs() << "\n"); 86 LLVM_DEBUG(dbgs() << "\n");
91 EXPECT_EQ(Legalized.size(), 3UL); 87 EXPECT_EQ(Legalized.size(), 3UL);
92 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end()); 88 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());
93 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end()); 89 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end());
94 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end()); 90 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end());
95 } 91 }
98 CFGHolder Holder; 94 CFGHolder Holder;
99 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}}); 95 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});
100 96
101 DominatorTree DT(*Holder.F); 97 DominatorTree DT(*Holder.F);
102 EXPECT_TRUE(DT.verify()); 98 EXPECT_TRUE(DT.verify());
103 PostDomTree PDT(*Holder.F); 99 PostDominatorTree PDT(*Holder.F);
104 EXPECT_TRUE(DT.verify()); 100 EXPECT_TRUE(PDT.verify());
105 101
106 BasicBlock *B = Builder.getOrAddBlock("B"); 102 BasicBlock *B = Builder.getOrAddBlock("B");
107 BasicBlock *C = Builder.getOrAddBlock("C"); 103 BasicBlock *C = Builder.getOrAddBlock("C");
108 std::vector<DomUpdate> Updates = {{Insert, B, C}}; 104 std::vector<DomUpdate> Updates = {{Insert, B, C}};
109 105
120 CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}}, 116 CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},
121 {{CFGDelete, {"B", "C"}}}); 117 {{CFGDelete, {"B", "C"}}});
122 118
123 DominatorTree DT(*Holder.F); 119 DominatorTree DT(*Holder.F);
124 EXPECT_TRUE(DT.verify()); 120 EXPECT_TRUE(DT.verify());
125 PostDomTree PDT(*Holder.F); 121 PostDominatorTree PDT(*Holder.F);
126 EXPECT_TRUE(DT.verify()); 122 EXPECT_TRUE(PDT.verify());
127 123
128 BasicBlock *B = Builder.getOrAddBlock("B"); 124 BasicBlock *B = Builder.getOrAddBlock("B");
129 BasicBlock *C = Builder.getOrAddBlock("C"); 125 BasicBlock *C = Builder.getOrAddBlock("C");
130 std::vector<DomUpdate> Updates = {{Delete, B, C}}; 126 std::vector<DomUpdate> Updates = {{Delete, B, C}};
131 127
146 CFGHolder Holder; 142 CFGHolder Holder;
147 CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates); 143 CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);
148 144
149 DominatorTree DT(*Holder.F); 145 DominatorTree DT(*Holder.F);
150 EXPECT_TRUE(DT.verify()); 146 EXPECT_TRUE(DT.verify());
151 PostDomTree PDT(*Holder.F); 147 PostDominatorTree PDT(*Holder.F);
152 EXPECT_TRUE(PDT.verify()); 148 EXPECT_TRUE(PDT.verify());
153 149
154 BasicBlock *B = Builder.getOrAddBlock("B"); 150 BasicBlock *B = Builder.getOrAddBlock("B");
155 BasicBlock *C = Builder.getOrAddBlock("C"); 151 BasicBlock *C = Builder.getOrAddBlock("C");
156 BasicBlock *D = Builder.getOrAddBlock("D"); 152 BasicBlock *D = Builder.getOrAddBlock("D");
179 Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}}, 175 Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},
180 CFGUpdates); 176 CFGUpdates);
181 177
182 DominatorTree DT(*Holder.F); 178 DominatorTree DT(*Holder.F);
183 EXPECT_TRUE(DT.verify()); 179 EXPECT_TRUE(DT.verify());
184 PostDomTree PDT(*Holder.F); 180 PostDominatorTree PDT(*Holder.F);
185 EXPECT_TRUE(PDT.verify()); 181 EXPECT_TRUE(PDT.verify());
186 182
187 auto Updates = ToDomUpdates(Builder, CFGUpdates); 183 auto Updates = ToDomUpdates(Builder, CFGUpdates);
188 184
189 while (Builder.applyUpdate()) 185 while (Builder.applyUpdate())
210 206
211 CFGHolder Holder; 207 CFGHolder Holder;
212 CFGBuilder B(Holder.F, Arcs, Updates); 208 CFGBuilder B(Holder.F, Arcs, Updates);
213 DominatorTree DT(*Holder.F); 209 DominatorTree DT(*Holder.F);
214 EXPECT_TRUE(DT.verify()); 210 EXPECT_TRUE(DT.verify());
215 PostDomTree PDT(*Holder.F); 211 PostDominatorTree PDT(*Holder.F);
216 EXPECT_TRUE(PDT.verify()); 212 EXPECT_TRUE(PDT.verify());
217 213
218 while (B.applyUpdate()) 214 while (B.applyUpdate())
219 ; 215 ;
220 216
243 std::shuffle(Updates.begin(), Updates.end(), Generator); 239 std::shuffle(Updates.begin(), Updates.end(), Generator);
244 CFGHolder Holder; 240 CFGHolder Holder;
245 CFGBuilder B(Holder.F, Arcs, Updates); 241 CFGBuilder B(Holder.F, Arcs, Updates);
246 DominatorTree DT(*Holder.F); 242 DominatorTree DT(*Holder.F);
247 EXPECT_TRUE(DT.verify()); 243 EXPECT_TRUE(DT.verify());
248 PostDomTree PDT(*Holder.F); 244 PostDominatorTree PDT(*Holder.F);
249 EXPECT_TRUE(PDT.verify()); 245 EXPECT_TRUE(PDT.verify());
250 246
251 while (B.applyUpdate()) 247 while (B.applyUpdate())
252 ; 248 ;
253 249
276 272
277 CFGHolder Holder; 273 CFGHolder Holder;
278 CFGBuilder B(Holder.F, Arcs, Updates); 274 CFGBuilder B(Holder.F, Arcs, Updates);
279 DominatorTree DT(*Holder.F); 275 DominatorTree DT(*Holder.F);
280 EXPECT_TRUE(DT.verify()); 276 EXPECT_TRUE(DT.verify());
281 PostDomTree PDT(*Holder.F); 277 PostDominatorTree PDT(*Holder.F);
282 EXPECT_TRUE(PDT.verify()); 278 EXPECT_TRUE(PDT.verify());
283 279
284 while (B.applyUpdate()) 280 while (B.applyUpdate())
285 ; 281 ;
286 282
309 305
310 CFGHolder Holder; 306 CFGHolder Holder;
311 CFGBuilder B(Holder.F, Arcs, Updates); 307 CFGBuilder B(Holder.F, Arcs, Updates);
312 DominatorTree DT(*Holder.F); 308 DominatorTree DT(*Holder.F);
313 EXPECT_TRUE(DT.verify()); 309 EXPECT_TRUE(DT.verify());
314 PostDomTree PDT(*Holder.F); 310 PostDominatorTree PDT(*Holder.F);
315 EXPECT_TRUE(PDT.verify()); 311 EXPECT_TRUE(PDT.verify());
316 312
317 while (B.applyUpdate()) 313 while (B.applyUpdate())
318 ; 314 ;
319 315
339 335
340 CFGHolder Holder; 336 CFGHolder Holder;
341 CFGBuilder B(Holder.F, Arcs, Updates); 337 CFGBuilder B(Holder.F, Arcs, Updates);
342 DominatorTree DT(*Holder.F); 338 DominatorTree DT(*Holder.F);
343 EXPECT_TRUE(DT.verify()); 339 EXPECT_TRUE(DT.verify());
344 PostDomTree PDT(*Holder.F); 340 PostDominatorTree PDT(*Holder.F);
345 EXPECT_TRUE(PDT.verify()); 341 EXPECT_TRUE(PDT.verify());
346 342
347 while (B.applyUpdate()) 343 while (B.applyUpdate())
348 ; 344 ;
349 345