Gitiles
Code Review Sign In
gerrit.witaqua.org / art / 86fe9b85c5243debe5f695c1625bae03bf738452 / . / compiler / optimizing / execution_subgraph_test.cc
blob: 1fc00d9f6bb89e8796828947b39de13592e8f29a [file] [log] [blame]
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame^]1/*
2 * Copyright (C) 2020 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "execution_subgraph_test.h"
18
19#include <array>
20#include <sstream>
21#include <string_view>
22#include <unordered_map>
23#include <unordered_set>
24
25#include "base/scoped_arena_allocator.h"
26#include "base/stl_util.h"
27#include "class_root.h"
28#include "dex/dex_file_types.h"
29#include "dex/method_reference.h"
30#include "entrypoints/quick/quick_entrypoints_enum.h"
31#include "execution_subgraph.h"
32#include "gtest/gtest.h"
33#include "handle.h"
34#include "handle_scope.h"
35#include "nodes.h"
36#include "optimizing/data_type.h"
37#include "optimizing_unit_test.h"
38#include "scoped_thread_state_change.h"
39
40namespace art {
41
42using BlockSet = std::unordered_set<const HBasicBlock*>;
43
44// Helper that checks validity directly.
45bool ExecutionSubgraphTestHelper::CalculateValidity(HGraph* graph, const ExecutionSubgraph* esg) {
46 bool reached_end = false;
47 std::queue<const HBasicBlock*> worklist;
48 std::unordered_set<const HBasicBlock*> visited;
49 worklist.push(graph->GetEntryBlock());
50 while (!worklist.empty()) {
51 const HBasicBlock* cur = worklist.front();
52 worklist.pop();
53 if (visited.find(cur) != visited.end()) {
54 continue;
55 } else {
56 visited.insert(cur);
57 }
58 if (cur == graph->GetExitBlock()) {
59 reached_end = true;
60 continue;
61 }
62 bool has_succ = false;
63 for (const HBasicBlock* succ : cur->GetSuccessors()) {
64 DCHECK(succ != nullptr) << "Bad successors on block " << cur->GetBlockId();
65 if (!esg->ContainsBlock(succ)) {
66 continue;
67 }
68 has_succ = true;
69 worklist.push(succ);
70 }
71 if (!has_succ) {
72 // We aren't at the end and have nowhere to go so fail.
73 return false;
74 }
75 }
76 return reached_end;
77}
78
79class ExecutionSubgraphTest : public OptimizingUnitTest {
80 public:
81 ExecutionSubgraphTest() : graph_(CreateGraph()) {}
82
83 AdjacencyListGraph SetupFromAdjacencyList(const std::string_view entry_name,
84 const std::string_view exit_name,
85 const std::vector<AdjacencyListGraph::Edge>& adj) {
86 return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
87 }
88
89 bool IsValidSubgraph(const ExecutionSubgraph* esg) {
90 return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg);
91 }
92
93 bool IsValidSubgraph(const ExecutionSubgraph& esg) {
94 return ExecutionSubgraphTestHelper::CalculateValidity(graph_, &esg);
95 }
96
97 HGraph* graph_;
98};
99
100// Some comparators used by these tests to avoid having to deal with various set types.
101template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
102bool operator==(const BlockSet& bs, const BLKS& sas) {
103 std::unordered_set<const HBasicBlock*> us(sas.begin(), sas.end());
104 return bs == us;
105}
106template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
107bool operator==(const BLKS& sas, const BlockSet& bs) {
108 return bs == sas;
109}
110template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
111bool operator!=(const BlockSet& bs, const BLKS& sas) {
112 return !(bs == sas);
113}
114template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
115bool operator!=(const BLKS& sas, const BlockSet& bs) {
116 return !(bs == sas);
117}
118
119// +-------+ +-------+
120// | right | <-- | entry |
121// +-------+ +-------+
122// | |
123// | |
124// | v
125// | + - - - - - +
126// | ' removed '
127// | ' '
128// | ' +-------+ '
129// | ' | left | '
130// | ' +-------+ '
131// | ' '
132// | + - - - - - +
133// | |
134// | |
135// | v
136// | +-------+
137// +---------> | exit |
138// +-------+
139TEST_F(ExecutionSubgraphTest, Basic) {
140 AdjacencyListGraph blks(SetupFromAdjacencyList(
141 "entry",
142 "exit",
143 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
144 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
145 ExecutionSubgraph esg(graph_, true, GetScopedAllocator());
146 esg.RemoveBlock(blks.Get("left"));
147 esg.Finalize();
148 ASSERT_TRUE(esg.IsValid());
149 ASSERT_TRUE(IsValidSubgraph(esg));
150 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
151 esg.ReachableBlocks().end());
152
153 ASSERT_EQ(contents.size(), 3u);
154 ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end());
155
156 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
157 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
158 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
159 esg.RemoveBlock(blks.Get("right"));
160 esg.Finalize();
161 std::unordered_set<const HBasicBlock*> contents_2(esg.ReachableBlocks().begin(),
162 esg.ReachableBlocks().end());
163 ASSERT_EQ(contents_2.size(), 0u);
164}
165
166// +-------+ +-------+
167// | right | <-- | entry |
168// +-------+ +-------+
169// | |
170// | |
171// | v
172// | + - - - - - - - - - - - - - - - - - - - -+
173// | ' indirectly_removed '
174// | ' '
175// | ' +-------+ +-----+ '
176// | ' | l1 | -------------------> | l1r | '
177// | ' +-------+ +-----+ '
178// | ' | | '
179// | ' | | '
180// | ' v | '
181// | ' +-------+ | '
182// | ' | l1l | | '
183// | ' +-------+ | '
184// | ' | | '
185// | ' | | '
186// | ' | | '
187// + - - - - - - - -+ | +- - - | | '
188// ' ' | +- v | '
189// ' +-----+ | +----------------+ | '
190// ' | l2r | <---------+-------------- | l2 (removed) | <-------------+ '
191// ' +-----+ | +----------------+ '
192// ' | ' | +- | '
193// ' | - - -+ | +- - - | - - - - - - - - - - - - - -+
194// ' | ' | ' | '
195// ' | ' | ' | '
196// ' | ' | ' v '
197// ' | ' | ' +-------+ '
198// ' | ' | ' | l2l | '
199// ' | ' | ' +-------+ '
200// ' | ' | ' | '
201// ' | ' | ' | '
202// ' | ' | ' | '
203// ' | - - -+ | +- - - | '
204// ' | ' | +- v '
205// ' | | +-------+ '
206// ' +---------------+-------------> | l3 | '
207// ' | +-------+ '
208// ' ' | +- '
209// + - - - - - - - -+ | +- - - - - - - - - +
210// | |
211// | |
212// | v
213// | +-------+
214// +-----------> | exit |
215// +-------+
216TEST_F(ExecutionSubgraphTest, Propagation) {
217 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
218 "exit",
219 { { "entry", "l1" },
220 { "l1", "l1l" },
221 { "l1", "l1r" },
222 { "l1l", "l2" },
223 { "l1r", "l2" },
224 { "l2", "l2l" },
225 { "l2", "l2r" },
226 { "l2l", "l3" },
227 { "l2r", "l3" },
228 { "l3", "exit" },
229 { "entry", "right" },
230 { "right", "exit" } }));
231 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
232 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
233 esg.RemoveBlock(blks.Get("l2"));
234 esg.Finalize();
235 ASSERT_TRUE(esg.IsValid());
236 ASSERT_TRUE(IsValidSubgraph(esg));
237 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
238 esg.ReachableBlocks().end());
239
240 // ASSERT_EQ(contents.size(), 3u);
241 // Not present, no path through.
242 ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
243 ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
244 ASSERT_TRUE(contents.find(blks.Get("l3")) == contents.end());
245 ASSERT_TRUE(contents.find(blks.Get("l1l")) == contents.end());
246 ASSERT_TRUE(contents.find(blks.Get("l1r")) == contents.end());
247 ASSERT_TRUE(contents.find(blks.Get("l2l")) == contents.end());
248 ASSERT_TRUE(contents.find(blks.Get("l2r")) == contents.end());
249
250 // present, path through.
251 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
252 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
253 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
254}
255
256// +------------------------------------+
257// | |
258// | +-------+ +-------+ |
259// | | right | <-- | entry | |
260// | +-------+ +-------+ |
261// | | | |
262// | | | |
263// | | v |
264// | | +-------+ +--------+
265// +----+---------> | l1 | --> | l1loop |
266// | +-------+ +--------+
267// | |
268// | |
269// | v
270// | +- - - - - -+
271// | ' removed '
272// | ' '
273// | ' +-------+ '
274// | ' | l2 | '
275// | ' +-------+ '
276// | ' '
277// | +- - - - - -+
278// | |
279// | |
280// | v
281// | +-------+
282// +---------> | exit |
283// +-------+
284TEST_F(ExecutionSubgraphTest, PropagationLoop) {
285 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
286 "exit",
287 { { "entry", "l1" },
288 { "l1", "l2" },
289 { "l1", "l1loop" },
290 { "l1loop", "l1" },
291 { "l2", "exit" },
292 { "entry", "right" },
293 { "right", "exit" } }));
294 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
295 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
296 esg.RemoveBlock(blks.Get("l2"));
297 esg.Finalize();
298 ASSERT_TRUE(esg.IsValid());
299 ASSERT_TRUE(IsValidSubgraph(esg));
300 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
301 esg.ReachableBlocks().end());
302
303 ASSERT_EQ(contents.size(), 5u);
304
305 // Not present, no path through.
306 ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
307
308 // present, path through.
309 // Since the loop can diverge we should leave it in the execution subgraph.
310 ASSERT_TRUE(contents.find(blks.Get("l1")) != contents.end());
311 ASSERT_TRUE(contents.find(blks.Get("l1loop")) != contents.end());
312 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
313 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
314 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
315}
316
317// +--------------------------------+
318// | |
319// | +-------+ +-------+ |
320// | | right | <-- | entry | |
321// | +-------+ +-------+ |
322// | | | |
323// | | | |
324// | | v |
325// | | +-------+ +--------+
326// +----+---------> | l1 | --> | l1loop |
327// | +-------+ +--------+
328// | |
329// | |
330// | v
331// | +-------+
332// | | l2 |
333// | +-------+
334// | |
335// | |
336// | v
337// | +-------+
338// +---------> | exit |
339// +-------+
340TEST_F(ExecutionSubgraphTest, PropagationLoop2) {
341 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
342 "exit",
343 { { "entry", "l1" },
344 { "l1", "l2" },
345 { "l1", "l1loop" },
346 { "l1loop", "l1" },
347 { "l2", "exit" },
348 { "entry", "right" },
349 { "right", "exit" } }));
350 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
351 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
352 esg.RemoveBlock(blks.Get("l1"));
353 esg.Finalize();
354 ASSERT_TRUE(esg.IsValid());
355 ASSERT_TRUE(IsValidSubgraph(esg));
356 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
357 esg.ReachableBlocks().end());
358
359 ASSERT_EQ(contents.size(), 3u);
360
361 // Not present, no path through.
362 ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
363 ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end());
364 ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
365
366 // present, path through.
367 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
368 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
369 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
370}
371
372// +--------------------------------+
373// | |
374// | +-------+ +-------+ |
375// | | right | <-- | entry | |
376// | +-------+ +-------+ |
377// | | | |
378// | | | |
379// | | v |
380// | | +-------+ +--------+
381// +----+---------> | l1 | --> | l1loop |
382// | +-------+ +--------+
383// | |
384// | |
385// | v
386// | +-------+
387// | | l2 |
388// | +-------+
389// | |
390// | |
391// | v
392// | +-------+
393// +---------> | exit |
394// +-------+
395TEST_F(ExecutionSubgraphTest, PropagationLoop3) {
396 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
397 "exit",
398 { { "entry", "l1" },
399 { "l1", "l2" },
400 { "l1", "l1loop" },
401 { "l1loop", "l1" },
402 { "l2", "exit" },
403 { "entry", "right" },
404 { "right", "exit" } }));
405 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
406 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
407 esg.RemoveBlock(blks.Get("l1loop"));
408 esg.Finalize();
409 ASSERT_TRUE(esg.IsValid());
410 ASSERT_TRUE(IsValidSubgraph(esg));
411 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
412 esg.ReachableBlocks().end());
413
414 ASSERT_EQ(contents.size(), 3u);
415
416 // Not present, no path through. If we got to l1 loop then we must merge back
417 // with l1 and l2 so they're bad too.
418 ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end());
419 ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
420 ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
421
422 // present, path through.
423 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
424 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
425 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
426}
427
428TEST_F(ExecutionSubgraphTest, Invalid) {
429 AdjacencyListGraph blks(SetupFromAdjacencyList(
430 "entry",
431 "exit",
432 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
433 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
434 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
435 esg.RemoveBlock(blks.Get("left"));
436 esg.RemoveBlock(blks.Get("right"));
437 esg.Finalize();
438
439 ASSERT_FALSE(esg.IsValid());
440 ASSERT_FALSE(IsValidSubgraph(esg));
441 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
442 esg.ReachableBlocks().end());
443
444 ASSERT_EQ(contents.size(), 0u);
445}
446// Sibling branches are disconnected.
447TEST_F(ExecutionSubgraphTest, Exclusions) {
448 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
449 "exit",
450 { { "entry", "a" },
451 { "entry", "b" },
452 { "entry", "c" },
453 { "a", "exit" },
454 { "b", "exit" },
455 { "c", "exit" } }));
456 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
457 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
458 esg.RemoveBlock(blks.Get("a"));
459 esg.RemoveBlock(blks.Get("c"));
460 esg.Finalize();
461 ASSERT_TRUE(esg.IsValid());
462 ASSERT_TRUE(IsValidSubgraph(esg));
463 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
464 esg.ReachableBlocks().end());
465
466 ASSERT_EQ(contents.size(), 3u);
467 // Not present, no path through.
468 ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end());
469 ASSERT_TRUE(contents.find(blks.Get("c")) == contents.end());
470
471 // present, path through.
472 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
473 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
474 ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end());
475
476 ArrayRef<const ExecutionSubgraph::ExcludedCohort> exclusions(esg.GetExcludedCohorts());
477 ASSERT_EQ(exclusions.size(), 2u);
478 std::unordered_set<const HBasicBlock*> exclude_a({ blks.Get("a") });
479 std::unordered_set<const HBasicBlock*> exclude_c({ blks.Get("c") });
480 ASSERT_TRUE(std::find_if(exclusions.cbegin(),
481 exclusions.cend(),
482 [&](const ExecutionSubgraph::ExcludedCohort& it) {
483 return it.Blocks() == exclude_a;
484 }) != exclusions.cend());
485 ASSERT_TRUE(std::find_if(exclusions.cbegin(),
486 exclusions.cend(),
487 [&](const ExecutionSubgraph::ExcludedCohort& it) {
488 return it.Blocks() == exclude_c;
489 }) != exclusions.cend());
490}
491
492// Sibling branches are disconnected.
493// +- - - - - - - - - - - - - - - - - - - - - - +
494// ' remove_c '
495// ' '
496// ' +-----------+ '
497// ' | c_begin_2 | -------------------------+ '
498// ' +-----------+ | '
499// ' | '
500// +- - - - - - - - - - - - - - - - - - | '
501// ^ ' | '
502// | ' | '
503// | ' | '
504// + - - - - - -+ ' | '
505// ' remove_a ' ' | '
506// ' ' ' | '
507// ' +--------+ ' +-----------+ +---+' | '
508// ' | **a** | ' <-- | entry | --> | b |' | '
509// ' +--------+ ' +-----------+ +---+' | '
510// ' ' ' | '
511// + - - - - - -+ ' | '
512// | | | ' | '
513// | | | ' | '
514// | v | ' | '
515// | +- - - - - - - -+ | ' | '
516// | ' ' | ' | '
517// | ' +-----------+ ' | ' | '
518// | ' | c_begin_1 | ' | ' | '
519// | ' +-----------+ ' | ' | '
520// | ' | ' | ' | '
521// | ' | ' | ' | '
522// | ' | ' | ' | '
523// + - - - - - - - - -+ | + - - - | - - - - - - - + | ' | '
524// ' ' | + v ' | + | '
525// ' +---------+ | +-----------+ | | '
526// ' | c_end_2 | <-------+--------------- | **c_mid** | <-----------------+------+ '
527// ' +---------+ | +-----------+ | '
528// ' ' | + | ' | + '
529// + - - - - - - - - -+ | + - - - | - - - - - - - + | + - - - +
530// | | ' | ' |
531// | | ' | ' |
532// | | ' v ' |
533// | | ' +-----------+ ' |
534// | | ' | c_end_1 | ' |
535// | | ' +-----------+ ' |
536// | | ' ' |
537// | | +- - - - - - - -+ |
538// | | | |
539// | | | |
540// | | v v
541// | | +---------------------------------+
542// | +------------> | exit |
543// | +---------------------------------+
544// | ^
545// +------------------------------------+
546TEST_F(ExecutionSubgraphTest, ExclusionExtended) {
547 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
548 "exit",
549 { { "entry", "a" },
550 { "entry", "b" },
551 { "entry", "c_begin_1" },
552 { "entry", "c_begin_2" },
553 { "c_begin_1", "c_mid" },
554 { "c_begin_2", "c_mid" },
555 { "c_mid", "c_end_1" },
556 { "c_mid", "c_end_2" },
557 { "a", "exit" },
558 { "b", "exit" },
559 { "c_end_1", "exit" },
560 { "c_end_2", "exit" } }));
561 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
562 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
563 esg.RemoveBlock(blks.Get("a"));
564 esg.RemoveBlock(blks.Get("c_mid"));
565 esg.Finalize();
566 ASSERT_TRUE(esg.IsValid());
567 ASSERT_TRUE(IsValidSubgraph(esg));
568 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
569 esg.ReachableBlocks().end());
570
571 ASSERT_EQ(contents.size(), 3u);
572 // Not present, no path through.
573 ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end());
574 ASSERT_TRUE(contents.find(blks.Get("c_begin_1")) == contents.end());
575 ASSERT_TRUE(contents.find(blks.Get("c_begin_2")) == contents.end());
576 ASSERT_TRUE(contents.find(blks.Get("c_mid")) == contents.end());
577 ASSERT_TRUE(contents.find(blks.Get("c_end_1")) == contents.end());
578 ASSERT_TRUE(contents.find(blks.Get("c_end_2")) == contents.end());
579
580 // present, path through.
581 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
582 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
583 ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end());
584
585 ArrayRef<const ExecutionSubgraph::ExcludedCohort> exclusions(esg.GetExcludedCohorts());
586 ASSERT_EQ(exclusions.size(), 2u);
587 BlockSet exclude_a({ blks.Get("a") });
588 BlockSet exclude_c({ blks.Get("c_begin_1"),
589 blks.Get("c_begin_2"),
590 blks.Get("c_mid"),
591 blks.Get("c_end_1"),
592 blks.Get("c_end_2") });
593 ASSERT_TRUE(std::find_if(exclusions.cbegin(),
594 exclusions.cend(),
595 [&](const ExecutionSubgraph::ExcludedCohort& it) {
596 return it.Blocks() == exclude_a;
597 }) != exclusions.cend());
598 ASSERT_TRUE(
599 std::find_if(
600 exclusions.cbegin(), exclusions.cend(), [&](const ExecutionSubgraph::ExcludedCohort& it) {
601 return it.Blocks() == exclude_c &&
602 BlockSet({ blks.Get("c_begin_1"), blks.Get("c_begin_2") }) == it.EntryBlocks() &&
603 BlockSet({ blks.Get("c_end_1"), blks.Get("c_end_2") }) == it.ExitBlocks();
604 }) != exclusions.cend());
605}
606
607// ┌───────┐ ┌────────────┐
608// ┌─ │ right │ ◀── │ entry │
609// │ └───────┘ └────────────┘
610// │ │
611// │ │
612// │ ▼
613// │ ┌────────────┐
614// │ │ esc_top │
615// │ └────────────┘
616// │ │
617// │ │
618// │ ▼
619// │ ┌────────────┐
620// └──────────────▶ │ middle │ ─┐
621// └────────────┘ │
622// │ │
623// │ │
624// ▼ │
625// ┌────────────┐ │
626// │ esc_bottom │ │
627// └────────────┘ │
628// │ │
629// │ │
630// ▼ │
631// ┌────────────┐ │
632// │ exit │ ◀┘
633// └────────────┘
634TEST_F(ExecutionSubgraphTest, InAndOutEscape) {
635 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
636 "exit",
637 { { "entry", "esc_top" },
638 { "entry", "right" },
639 { "esc_top", "middle" },
640 { "right", "middle" },
641 { "middle", "exit" },
642 { "middle", "esc_bottom" },
643 { "esc_bottom", "exit" } }));
644
645 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
646 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
647 esg.RemoveBlock(blks.Get("esc_top"));
648 esg.RemoveBlock(blks.Get("esc_bottom"));
649 esg.Finalize();
650
651 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
652 esg.ReachableBlocks().end());
653 ASSERT_EQ(contents.size(), 0u);
654 ASSERT_FALSE(esg.IsValid());
655 ASSERT_FALSE(IsValidSubgraph(esg));
656
657 ASSERT_EQ(contents.size(), 0u);
658}
659
660// Test with max number of successors and no removals.
661TEST_F(ExecutionSubgraphTest, BigNodes) {
662 std::vector<std::string> mid_blocks;
663 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
664 std::ostringstream oss;
665 oss << "blk" << i;
666 mid_blocks.push_back(oss.str().c_str());
667 }
668 ASSERT_EQ(mid_blocks.size(), ExecutionSubgraph::kMaxFilterableSuccessors);
669 std::vector<AdjacencyListGraph::Edge> edges;
670 for (const auto& mid : mid_blocks) {
671 edges.emplace_back("entry", mid);
672 edges.emplace_back(mid, "exit");
673 }
674 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
675 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
676 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
677 esg.Finalize();
678 ASSERT_TRUE(esg.IsValid());
679 ASSERT_TRUE(IsValidSubgraph(esg));
680 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
681 esg.ReachableBlocks().end());
682
683 for (const auto& mid : mid_blocks) {
684 EXPECT_TRUE(contents.find(blks.Get(mid)) != contents.end()) << mid;
685 }
686 // + 2 for entry and exit nodes.
687 ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2);
688}
689
690// Test with max number of successors and some removals.
691TEST_F(ExecutionSubgraphTest, BigNodesMissing) {
692 std::vector<std::string> mid_blocks;
693 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
694 std::ostringstream oss;
695 oss << "blk" << i;
696 mid_blocks.push_back(oss.str());
697 }
698 std::vector<AdjacencyListGraph::Edge> edges;
699 for (const auto& mid : mid_blocks) {
700 edges.emplace_back("entry", mid);
701 edges.emplace_back(mid, "exit");
702 }
703 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
704 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
705 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
706 esg.RemoveBlock(blks.Get("blk2"));
707 esg.RemoveBlock(blks.Get("blk4"));
708 esg.Finalize();
709 ASSERT_TRUE(esg.IsValid());
710 ASSERT_TRUE(IsValidSubgraph(esg));
711 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
712 esg.ReachableBlocks().end());
713
714 ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2 - 2);
715
716 // Not present, no path through.
717 ASSERT_TRUE(contents.find(blks.Get("blk2")) == contents.end());
718 ASSERT_TRUE(contents.find(blks.Get("blk4")) == contents.end());
719}
720
721// Test with max number of successors and all successors removed.
722TEST_F(ExecutionSubgraphTest, BigNodesNoPath) {
723 std::vector<std::string> mid_blocks;
724 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
725 std::ostringstream oss;
726 oss << "blk" << i;
727 mid_blocks.push_back(oss.str());
728 }
729 std::vector<AdjacencyListGraph::Edge> edges;
730 for (const auto& mid : mid_blocks) {
731 edges.emplace_back("entry", mid);
732 edges.emplace_back(mid, "exit");
733 }
734 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
735 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
736 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
737 for (const auto& mid : mid_blocks) {
738 esg.RemoveBlock(blks.Get(mid));
739 }
740 esg.Finalize();
741 ASSERT_FALSE(esg.IsValid());
742 ASSERT_FALSE(IsValidSubgraph(esg));
743}
744
745// Test with max number of successors
746TEST_F(ExecutionSubgraphTest, CanAnalyseBig) {
747 // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario.
748 constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000;
749 std::vector<std::string> mid_blocks;
750 for (auto i : Range(kNumBlocks)) {
751 std::ostringstream oss;
752 oss << "blk" << i;
753 mid_blocks.push_back(oss.str());
754 }
755 std::vector<AdjacencyListGraph::Edge> edges;
756 for (auto cur : Range(kNumBlocks)) {
757 for (auto nxt :
758 Range(cur + 1,
759 std::min(cur + ExecutionSubgraph::kMaxFilterableSuccessors + 1, kNumBlocks))) {
760 edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
761 }
762 }
763 AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges));
764 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
765
766 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
767 esg.Finalize();
768 ASSERT_TRUE(esg.IsValid());
769 ASSERT_TRUE(IsValidSubgraph(esg));
770 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
771 esg.ReachableBlocks().end());
772
773 ASSERT_EQ(contents.size(), kNumBlocks);
774}
775
776// Test with many successors
777TEST_F(ExecutionSubgraphTest, CanAnalyseBig2) {
778 // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario.
779 constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000;
780 constexpr size_t kTestMaxSuccessors = ExecutionSubgraph::kMaxFilterableSuccessors - 1;
781 std::vector<std::string> mid_blocks;
782 for (auto i : Range(kNumBlocks)) {
783 std::ostringstream oss;
784 oss << "blk" << i;
785 mid_blocks.push_back(oss.str());
786 }
787 std::vector<AdjacencyListGraph::Edge> edges;
788 for (auto cur : Range(kNumBlocks)) {
789 for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
790 edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
791 }
792 }
793 edges.emplace_back(mid_blocks.front(), mid_blocks.back());
794 AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges));
795 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
796 ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator());
797 constexpr size_t kToRemoveIdx = kNumBlocks / 2;
798 HBasicBlock* remove_implicit = blks.Get(mid_blocks[kToRemoveIdx]);
799 for (HBasicBlock* pred : remove_implicit->GetPredecessors()) {
800 esg.RemoveBlock(pred);
801 }
802 esg.Finalize();
803 EXPECT_TRUE(esg.IsValid());
804 EXPECT_TRUE(IsValidSubgraph(esg));
805 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
806 esg.ReachableBlocks().end());
807
808 // Only entry and exit. The middle ones should eliminate everything else.
809 EXPECT_EQ(contents.size(), 2u);
810 EXPECT_TRUE(contents.find(remove_implicit) == contents.end());
811 EXPECT_TRUE(contents.find(blks.Get(mid_blocks.front())) != contents.end());
812 EXPECT_TRUE(contents.find(blks.Get(mid_blocks.back())) != contents.end());
813}
814
815// Test with too many successors
816TEST_F(ExecutionSubgraphTest, CanNotAnalyseBig) {
817 std::vector<std::string> mid_blocks;
818 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors + 4)) {
819 std::ostringstream oss;
820 oss << "blk" << i;
821 mid_blocks.push_back(oss.str());
822 }
823 std::vector<AdjacencyListGraph::Edge> edges;
824 for (const auto& mid : mid_blocks) {
825 edges.emplace_back("entry", mid);
826 edges.emplace_back(mid, "exit");
827 }
828 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
829 ASSERT_FALSE(ExecutionSubgraph::CanAnalyse(graph_));
830}
831} // namespace art