1 : // Copyright 2013 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Unittests for control flow analysis.
16 :
17 : #include "syzygy/block_graph/analysis/control_flow_analysis.h"
18 :
19 : #include "base/bind.h"
20 : #include "base/strings/stringprintf.h"
21 : #include "gmock/gmock.h"
22 : #include "gtest/gtest.h"
23 :
24 : namespace block_graph {
25 : namespace analysis {
26 :
27 : // This operator is used to serialize the actual tree for error reporting.
28 : std::ostream& operator <<(std::ostream& stream,
29 E : const ControlFlowAnalysis::StructuralNode* tree) {
30 : DCHECK_NE(reinterpret_cast<const ControlFlowAnalysis::StructuralNode*>(NULL),
31 E : tree);
32 E : switch (tree->kind()) {
33 : case ControlFlowAnalysis::StructuralNode::kBaseNode: {
34 E : stream << "Base(";
35 E : if (tree->root() == NULL) {
36 i : stream << "NULL";
37 i : } else {
38 E : stream << tree->root()->name();
39 : }
40 E : stream << ")";
41 E : break;
42 : }
43 : case ControlFlowAnalysis::StructuralNode::kSequenceNode: {
44 : stream << "Sequence("
45 : << tree->entry_node()
46 : << ","
47 : << tree->sequence_node()
48 E : << ")";
49 E : break;
50 : }
51 : case ControlFlowAnalysis::StructuralNode::kIfThenNode: {
52 E : stream << "IfThen(" << tree->entry_node() << tree->then_node() << ")";
53 E : break;
54 : }
55 : case ControlFlowAnalysis::StructuralNode::kIfThenElseNode: {
56 : stream << "IfThenElse("
57 : << tree->entry_node()
58 : << ","
59 : << tree->then_node()
60 : << ","
61 : << tree->else_node()
62 E : << ")";
63 E : break;
64 : }
65 : case ControlFlowAnalysis::StructuralNode::kRepeatNode: {
66 E : stream << "Repeat(" << tree->entry_node() << ")";
67 E : break;
68 : }
69 : case ControlFlowAnalysis::StructuralNode::kWhileNode: {
70 E : stream << "While(" << tree->entry_node() << ")";
71 E : break;
72 : }
73 : case ControlFlowAnalysis::StructuralNode::kLoopNode: {
74 E : stream << "Loop(" << tree->entry_node() << ")";
75 E : break;
76 : }
77 : default: {
78 i : stream << "ERROR(" << tree->entry_node() << ")";
79 : break;
80 : }
81 : }
82 E : return stream;
83 E : }
84 :
85 : namespace {
86 :
87 : using testing::ElementsAre;
88 : typedef BasicBlockSubGraph::BBCollection BBCollection;
89 : typedef block_graph::BasicBlockSubGraph::BasicBlock::Successors Successors;
90 : typedef block_graph::BasicBlockSubGraph::BasicCodeBlock BasicCodeBlock;
91 :
92 : class ControlFlowAnalysisTest : public testing::Test {
93 : public:
94 E : ControlFlowAnalysisTest() {}
95 :
96 : protected:
97 : void BuildReversePostOrder();
98 : bool BuildStructuralTree(BasicCodeBlock* root);
99 :
100 : void AddSuccessorBetween(Successor::Condition condition,
101 : BasicCodeBlock* from,
102 : BasicCodeBlock* to);
103 :
104 : void Connect(BasicCodeBlock* from,
105 : BasicCodeBlock* to);
106 :
107 : void MakeIf(BasicCodeBlock* root,
108 : BasicCodeBlock* true_stm,
109 : BasicCodeBlock* end_stm);
110 :
111 : BasicBlockSubGraph subgraph_;
112 : std::vector<const BasicCodeBlock*> order_;
113 : ControlFlowAnalysis::StructuralTree tree_;
114 : };
115 :
116 E : void ControlFlowAnalysisTest::BuildReversePostOrder() {
117 : ControlFlowAnalysis::FlattenBasicBlocksInPostOrder(subgraph_.basic_blocks(),
118 E : &order_);
119 E : ASSERT_EQ(subgraph_.basic_blocks().size(), order_.size());
120 E : }
121 :
122 E : bool ControlFlowAnalysisTest::BuildStructuralTree(BasicCodeBlock* entry) {
123 : // Add the entry block in the block description.
124 : BasicBlockSubGraph::BlockDescription* description =
125 : subgraph_.AddBlockDescription("bb1", "test.obj", BlockGraph::CODE_BLOCK,
126 E : 7, 2, 42);
127 E : description->basic_block_order.push_back(entry);
128 :
129 : // Analyze the subgraph.
130 E : bool result = ControlFlowAnalysis::BuildStructuralTree(&subgraph_, &tree_);
131 E : return result;
132 E : }
133 :
134 : void ControlFlowAnalysisTest::AddSuccessorBetween(
135 : Successor::Condition condition,
136 : BasicCodeBlock* from,
137 E : BasicCodeBlock* to) {
138 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), from);
139 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), to);
140 E : DCHECK_LT(from->successors().size(), 2U);
141 :
142 : from->successors().push_back(
143 : Successor(condition,
144 : BasicBlockReference(BlockGraph::RELATIVE_REF,
145 : BlockGraph::Reference::kMaximumSize,
146 : to),
147 E : 0));
148 E : }
149 :
150 : void ControlFlowAnalysisTest::Connect(BasicCodeBlock* from,
151 E : BasicCodeBlock* to) {
152 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), from);
153 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), to);
154 E : DCHECK_LT(from->successors().size(), 1U);
155 :
156 E : AddSuccessorBetween(Successor::kConditionTrue, from, to);
157 E : }
158 :
159 : void ControlFlowAnalysisTest::MakeIf(
160 : BasicCodeBlock* root,
161 : BasicCodeBlock* true_stm,
162 E : BasicCodeBlock* false_stm) {
163 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), root);
164 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), true_stm);
165 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), false_stm);
166 :
167 E : Successor::Condition condition = Successor::kConditionAbove;
168 E : AddSuccessorBetween(condition, root, true_stm);
169 E : AddSuccessorBetween(Successor::InvertCondition(condition), root, false_stm);
170 E : }
171 :
172 E : MATCHER_P(Base, node, "Base(...)") {
173 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kBaseNode &&
174 E : arg->root() == node;
175 E : }
176 :
177 E : MATCHER_P2(Sequence, node1, node2, "Sequence(...)") {
178 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kSequenceNode &&
179 : testing::Value(arg->entry_node(), node1) &&
180 E : testing::Value(arg->sequence_node(), node2);
181 E : }
182 :
183 E : MATCHER_P2(IfThen, node1, node2, "IfThen(...)") {
184 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kIfThenNode &&
185 : testing::Value(arg->entry_node(), node1) &&
186 E : testing::Value(arg->then_node(), node2);
187 E : }
188 :
189 E : MATCHER_P3(IfThenElse, node1, node2, node3, "IfThenElse(...)") {
190 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kIfThenElseNode &&
191 : testing::Value(arg->entry_node(), node1) &&
192 : testing::Value(arg->then_node(), node2) &&
193 E : testing::Value(arg->else_node(), node3);
194 E : }
195 :
196 E : MATCHER_P(Repeat, node1, "Repeat(...)") {
197 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kRepeatNode &&
198 E : testing::Value(arg->entry_node(), node1);
199 E : }
200 :
201 E : MATCHER_P2(While, node1, node2, "While(...)") {
202 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kWhileNode &&
203 : testing::Value(arg->entry_node(), node1) &&
204 E : testing::Value(arg->body_node(), node2);
205 E : }
206 :
207 E : MATCHER_P(Loop, node1, "Loop(...)") {
208 : return arg->kind() == ControlFlowAnalysis::StructuralNode::kLoopNode &&
209 E : testing::Value(arg->entry_node(), node1);
210 E : }
211 :
212 E : TEST_F(ControlFlowAnalysisTest, SingleIfOneBranchOrdering) {
213 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
214 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
215 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
216 :
217 E : MakeIf(if1, true1, end1);
218 E : Connect(true1, end1);
219 :
220 E : ASSERT_NO_FATAL_FAILURE(BuildReversePostOrder());
221 E : EXPECT_THAT(order_, testing::ElementsAre(end1, true1, if1));
222 E : }
223 :
224 E : TEST_F(ControlFlowAnalysisTest, SingleIfTwoBranchOrdering) {
225 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
226 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
227 E : BasicCodeBlock* false1 = subgraph_.AddBasicCodeBlock("false1");
228 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
229 :
230 E : MakeIf(if1, true1, false1);
231 E : Connect(true1, end1);
232 E : Connect(false1, end1);
233 :
234 E : ASSERT_NO_FATAL_FAILURE(BuildReversePostOrder());
235 E : EXPECT_THAT(order_, testing::ElementsAre(end1, true1, false1, if1));
236 E : }
237 :
238 E : TEST_F(ControlFlowAnalysisTest, TwoIfOneBranchOrdering) {
239 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
240 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
241 E : BasicCodeBlock* if2 = subgraph_.AddBasicCodeBlock("if2");
242 E : BasicCodeBlock* true2 = subgraph_.AddBasicCodeBlock("true2");
243 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
244 :
245 E : MakeIf(if1, true1, if2);
246 E : Connect(true1, if2);
247 E : MakeIf(if2, true2, end);
248 E : Connect(true2, end);
249 :
250 E : ASSERT_NO_FATAL_FAILURE(BuildReversePostOrder());
251 E : EXPECT_THAT(order_, testing::ElementsAre(end, true2, if2, true1, if1));
252 E : }
253 :
254 E : TEST_F(ControlFlowAnalysisTest, SimpleLoopOrdering) {
255 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
256 E : BasicCodeBlock* body1 = subgraph_.AddBasicCodeBlock("body1");
257 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
258 :
259 E : MakeIf(if1, body1, end1);
260 E : Connect(body1, if1);
261 :
262 E : ASSERT_NO_FATAL_FAILURE(BuildReversePostOrder());
263 E : EXPECT_THAT(order_, testing::ElementsAre(body1, end1, if1));
264 E : }
265 :
266 E : TEST_F(ControlFlowAnalysisTest, ComplexLoopOrdering) {
267 E : BasicCodeBlock* if0 = subgraph_.AddBasicCodeBlock("if0");
268 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
269 E : BasicCodeBlock* body1 = subgraph_.AddBasicCodeBlock("body1");
270 E : BasicCodeBlock* if2 = subgraph_.AddBasicCodeBlock("if2");
271 E : BasicCodeBlock* body2 = subgraph_.AddBasicCodeBlock("body2");
272 E : BasicCodeBlock* body3 = subgraph_.AddBasicCodeBlock("body3");
273 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
274 :
275 E : MakeIf(if0, if1, if2);
276 :
277 E : MakeIf(if1, body1, end);
278 E : Connect(body1, if1);
279 :
280 E : MakeIf(if2, body2, body3);
281 E : Connect(body2, end);
282 E : Connect(body3, if2);
283 :
284 E : ASSERT_NO_FATAL_FAILURE(BuildReversePostOrder());
285 : EXPECT_THAT(order_,
286 E : testing::ElementsAre(body1, end, if1, body2, body3, if2, if0));
287 E : }
288 :
289 E : TEST_F(ControlFlowAnalysisTest, SequenceStructure) {
290 E : BasicCodeBlock* seq1 = subgraph_.AddBasicCodeBlock("seq1");
291 E : BasicCodeBlock* seq2 = subgraph_.AddBasicCodeBlock("seq2");
292 E : BasicCodeBlock* seq3 = subgraph_.AddBasicCodeBlock("seq3");
293 :
294 E : Connect(seq1, seq2);
295 E : Connect(seq2, seq3);
296 :
297 E : ASSERT_TRUE(BuildStructuralTree(seq1));
298 : EXPECT_THAT(tree_.get(), Sequence(Base(seq1),
299 : Sequence(Base(seq2),
300 E : Base(seq3))));
301 E : }
302 :
303 E : TEST_F(ControlFlowAnalysisTest, IfThenStructure) {
304 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
305 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
306 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
307 :
308 E : MakeIf(if1, true1, end1);
309 E : Connect(true1, end1);
310 :
311 E : ASSERT_TRUE(BuildStructuralTree(if1));
312 : EXPECT_THAT(tree_.get(), Sequence(IfThen(Base(if1), Base(true1)),
313 E : Base(end1)));
314 E : }
315 :
316 E : TEST_F(ControlFlowAnalysisTest, IfThenFlippedStructure) {
317 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
318 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
319 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
320 :
321 E : MakeIf(if1, end1, true1);
322 E : Connect(true1, end1);
323 :
324 E : ASSERT_TRUE(BuildStructuralTree(if1));
325 : EXPECT_THAT(tree_.get(), Sequence(IfThen(Base(if1), Base(true1)),
326 E : Base(end1)));
327 E : }
328 :
329 E : TEST_F(ControlFlowAnalysisTest, IfThenElseStructure) {
330 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
331 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
332 E : BasicCodeBlock* false1 = subgraph_.AddBasicCodeBlock("false1");
333 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
334 :
335 E : MakeIf(if1, true1, false1);
336 E : Connect(true1, end1);
337 E : Connect(false1, end1);
338 :
339 E : ASSERT_TRUE(BuildStructuralTree(if1));
340 : EXPECT_THAT(tree_.get(), Sequence(IfThenElse(Base(if1),
341 : Base(true1),
342 : Base(false1)),
343 E : Base(end1)));
344 E : }
345 :
346 E : TEST_F(ControlFlowAnalysisTest, IfThenIfThenElseStructure) {
347 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
348 E : BasicCodeBlock* if2 = subgraph_.AddBasicCodeBlock("if2");
349 E : BasicCodeBlock* true2 = subgraph_.AddBasicCodeBlock("true2");
350 E : BasicCodeBlock* false2 = subgraph_.AddBasicCodeBlock("false2");
351 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
352 :
353 E : MakeIf(if1, if2, end1);
354 E : MakeIf(if2, true2, false2);
355 E : Connect(true2, end1);
356 E : Connect(false2, end1);
357 :
358 E : ASSERT_TRUE(BuildStructuralTree(if1));
359 : EXPECT_THAT(tree_.get(), Sequence(IfThen(Base(if1),
360 : IfThenElse(Base(if2),
361 : Base(true2),
362 : Base(false2))),
363 E : Base(end1)));
364 E : }
365 :
366 E : TEST_F(ControlFlowAnalysisTest, SequenceOfTwoIfThenStructure) {
367 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
368 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
369 E : BasicCodeBlock* if2 = subgraph_.AddBasicCodeBlock("if2");
370 E : BasicCodeBlock* true2 = subgraph_.AddBasicCodeBlock("true2");
371 E : BasicCodeBlock* end2 = subgraph_.AddBasicCodeBlock("end2");
372 :
373 E : MakeIf(if1, true1, if2);
374 E : Connect(true1, if2);
375 E : MakeIf(if2, true2, end2);
376 E : Connect(true2, end2);
377 :
378 E : ASSERT_TRUE(BuildStructuralTree(if1));
379 : EXPECT_THAT(tree_.get(), Sequence(IfThen(Base(if1),
380 : Base(true1)),
381 : Sequence(IfThen(Base(if2),
382 : Base(true2)),
383 E : Base(end2))));
384 E : }
385 :
386 E : TEST_F(ControlFlowAnalysisTest, NestedIfThenStructure) {
387 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
388 E : BasicCodeBlock* if2 = subgraph_.AddBasicCodeBlock("if2");
389 E : BasicCodeBlock* true2 = subgraph_.AddBasicCodeBlock("true2");
390 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
391 :
392 E : MakeIf(if1, if2, end1);
393 E : MakeIf(if2, true2, end1);
394 E : Connect(true2, end1);
395 :
396 E : ASSERT_TRUE(BuildStructuralTree(if1));
397 : EXPECT_THAT(tree_.get(), Sequence(IfThen(Base(if1),
398 : IfThen(Base(if2),
399 : Base(true2))),
400 E : Base(end1)));
401 E : }
402 :
403 E : TEST_F(ControlFlowAnalysisTest, IfThenLongSequenceStructure) {
404 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
405 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
406 E : BasicCodeBlock* true2 = subgraph_.AddBasicCodeBlock("true2");
407 E : BasicCodeBlock* true3 = subgraph_.AddBasicCodeBlock("true3");
408 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
409 :
410 E : MakeIf(if1, true1, end1);
411 E : Connect(true1, true2);
412 E : Connect(true2, true3);
413 E : Connect(true3, end1);
414 :
415 E : ASSERT_TRUE(BuildStructuralTree(if1));
416 : EXPECT_THAT(tree_.get(), Sequence(IfThen(Base(if1),
417 : Sequence(Base(true1),
418 : Sequence(Base(true2),
419 : Base(true3)))),
420 E : Base(end1)));
421 E : }
422 :
423 E : TEST_F(ControlFlowAnalysisTest, ComplexNestedIfStructure) {
424 E : BasicCodeBlock* if1 = subgraph_.AddBasicCodeBlock("if1");
425 E : BasicCodeBlock* true1 = subgraph_.AddBasicCodeBlock("true1");
426 E : BasicCodeBlock* end1 = subgraph_.AddBasicCodeBlock("end1");
427 E : MakeIf(if1, true1, end1);
428 E : Connect(true1, end1);
429 :
430 E : BasicCodeBlock* if2 = subgraph_.AddBasicCodeBlock("if2");
431 E : BasicCodeBlock* true2 = subgraph_.AddBasicCodeBlock("true2");
432 E : BasicCodeBlock* end2 = subgraph_.AddBasicCodeBlock("end2");
433 E : MakeIf(if2, end2, true2);
434 E : Connect(true2, end2);
435 :
436 E : BasicCodeBlock* if3 = subgraph_.AddBasicCodeBlock("if3");
437 E : MakeIf(if3, if1, if2);
438 E : Connect(end1, end2);
439 :
440 E : BasicCodeBlock* if4 = subgraph_.AddBasicCodeBlock("if4");
441 E : MakeIf(if4, end2, if3);
442 :
443 E : ASSERT_TRUE(BuildStructuralTree(if4));
444 : EXPECT_THAT(tree_.get(),
445 : Sequence(IfThen(Base(if4),
446 : IfThenElse(Base(if3),
447 : Sequence(IfThen(Base(if1),
448 : Base(true1)),
449 : Base(end1)),
450 : IfThen(Base(if2),
451 : Base(true2)))),
452 E : Base(end2)));
453 E : }
454 :
455 E : TEST_F(ControlFlowAnalysisTest, RepeatStructure) {
456 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
457 E : BasicCodeBlock* test = subgraph_.AddBasicCodeBlock("test");
458 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
459 :
460 E : Connect(loop, test);
461 E : MakeIf(test, loop, end);
462 :
463 E : ASSERT_TRUE(BuildStructuralTree(loop));
464 : EXPECT_THAT(tree_.get(), Sequence(Repeat(Sequence(Base(loop), Base(test))),
465 E : Base(end)));
466 E : }
467 :
468 E : TEST_F(ControlFlowAnalysisTest, RepeatFlippedStructure) {
469 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
470 E : BasicCodeBlock* test = subgraph_.AddBasicCodeBlock("test");
471 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
472 :
473 E : Connect(loop, test);
474 E : MakeIf(test, end, loop);
475 :
476 E : ASSERT_TRUE(BuildStructuralTree(loop));
477 : EXPECT_THAT(tree_.get(), Sequence(Repeat(Sequence(Base(loop), Base(test))),
478 E : Base(end)));
479 E : }
480 :
481 E : TEST_F(ControlFlowAnalysisTest, RepeatSeqStructure) {
482 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
483 E : BasicCodeBlock* body = subgraph_.AddBasicCodeBlock("body");
484 E : BasicCodeBlock* test = subgraph_.AddBasicCodeBlock("test");
485 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
486 :
487 E : Connect(loop, body);
488 E : Connect(body, test);
489 E : MakeIf(test, loop, end);
490 :
491 E : ASSERT_TRUE(BuildStructuralTree(loop));
492 : EXPECT_THAT(tree_.get(),
493 : Sequence(Repeat(Sequence(Base(loop),
494 : Sequence(Base(body), Base(test)))),
495 E : Base(end)));
496 E : }
497 :
498 E : TEST_F(ControlFlowAnalysisTest, RepeatIfThenStructure) {
499 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
500 E : BasicCodeBlock* then = subgraph_.AddBasicCodeBlock("then");
501 E : BasicCodeBlock* test = subgraph_.AddBasicCodeBlock("test");
502 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
503 :
504 E : MakeIf(loop, test, then);
505 E : Connect(then, test);
506 E : MakeIf(test, loop, end);
507 :
508 E : ASSERT_TRUE(BuildStructuralTree(loop));
509 : EXPECT_THAT(tree_.get(),
510 : Sequence(Repeat(Sequence(IfThen(Base(loop), Base(then)),
511 : Base(test))),
512 E : Base(end)));
513 E : }
514 :
515 E : TEST_F(ControlFlowAnalysisTest, WhileStructure) {
516 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
517 E : BasicCodeBlock* body = subgraph_.AddBasicCodeBlock("body");
518 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
519 :
520 E : MakeIf(loop, body, end);
521 E : Connect(body, loop);
522 :
523 E : ASSERT_TRUE(BuildStructuralTree(loop));
524 : EXPECT_THAT(tree_.get(), Sequence(While(Base(loop), Base(body)),
525 E : Base(end)));
526 E : }
527 :
528 E : TEST_F(ControlFlowAnalysisTest, WhileFlippedStructure) {
529 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
530 E : BasicCodeBlock* body = subgraph_.AddBasicCodeBlock("body");
531 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
532 :
533 E : MakeIf(loop, end, body);
534 E : Connect(body, loop);
535 :
536 E : ASSERT_TRUE(BuildStructuralTree(loop));
537 : EXPECT_THAT(tree_.get(), Sequence(While(Base(loop), Base(body)),
538 E : Base(end)));
539 E : }
540 :
541 E : TEST_F(ControlFlowAnalysisTest, LoopStructure) {
542 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
543 :
544 E : Connect(loop, loop);
545 :
546 E : ASSERT_TRUE(BuildStructuralTree(loop));
547 E : EXPECT_THAT(tree_.get(), Loop(Base(loop)));
548 E : }
549 :
550 E : TEST_F(ControlFlowAnalysisTest, ComplexLoopStructure) {
551 E : BasicCodeBlock* loop = subgraph_.AddBasicCodeBlock("loop");
552 E : BasicCodeBlock* then = subgraph_.AddBasicCodeBlock("then");
553 E : BasicCodeBlock* end = subgraph_.AddBasicCodeBlock("end");
554 :
555 E : MakeIf(loop, then, end);
556 E : Connect(then, end);
557 E : Connect(end, loop);
558 :
559 E : ASSERT_TRUE(BuildStructuralTree(loop));
560 : EXPECT_THAT(tree_.get(), Loop(Sequence(IfThen(Base(loop), Base(then)),
561 E : Base(end))));
562 E : }
563 :
564 E : TEST_F(ControlFlowAnalysisTest, IfInnerLoopStructure) {
565 E : BasicCodeBlock* head = subgraph_.AddBasicCodeBlock("head");
566 E : BasicCodeBlock* loop1 = subgraph_.AddBasicCodeBlock("loop1");
567 E : BasicCodeBlock* loop2 = subgraph_.AddBasicCodeBlock("loop2");
568 :
569 E : MakeIf(head, loop1, loop2);
570 E : Connect(loop1, loop1);
571 E : Connect(loop2, loop2);
572 :
573 E : ASSERT_TRUE(BuildStructuralTree(head));
574 E : }
575 :
576 E : TEST_F(ControlFlowAnalysisTest, IrreductibleStructure) {
577 E : BasicCodeBlock* head = subgraph_.AddBasicCodeBlock("head");
578 E : BasicCodeBlock* body1 = subgraph_.AddBasicCodeBlock("body1");
579 E : BasicCodeBlock* body2 = subgraph_.AddBasicCodeBlock("body2");
580 E : subgraph_.AddBasicCodeBlock("end");
581 :
582 E : MakeIf(head, body1, body2);
583 E : Connect(body1, body2);
584 E : Connect(body2, body1);
585 :
586 : // This control flow cannot be reduced.
587 E : ASSERT_FALSE(BuildStructuralTree(head));
588 E : }
589 :
590 : } // namespace
591 :
592 : } // namespace analysis
593 : } // namespace block_graph
|