Gitiles
Code Review Sign In
review.shift-gmbh.com / SHIFTPHONES / android_art / 4ae09d45271f1646b54c8f50859bcd88b7e844f7 / . / compiler / optimizing / execution_subgraph_test.cc
blob: 74c243b5b472a3f3049c51fc52666e3cf39218ed [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_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]145 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]232 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]295 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]351 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]406 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]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
Alex Light3a73ffb2021-01-25 14:11:05 +0000[diff] [blame]428// ┌───────┐ ┌──────────────┐
429// │ right │ ◀── │ entry │
430// └───────┘ └──────────────┘
431// │ │
432// │ │
433// ▼ ▼
434// ┌────┐ ┌───────┐ ┌──────────────┐
435// │ l2 │ ──▶ │ exit │ ┌─ │ l1 │ ◀┐
436// └────┘ └───────┘ │ └──────────────┘ │
437// ▲ │ │ │
438// └───────────────────┘ │ │
439// ▼ │
440// ┌──────────────┐ │ ┌──────────────┐
441// ┌─ │ l1loop │ │ │ l1loop_right │ ◀┐
442// │ └──────────────┘ │ └──────────────┘ │
443// │ │ │ │ │
444// │ │ │ │ │
445// │ ▼ │ │ │
446// │ ┌−−−−−−−−−−−−−−−−−−┐ │ │ │
447// │ ╎ removed ╎ │ │ │
448// │ ╎ ╎ │ │ │
449// │ ╎ ┌──────────────┐ ╎ │ │ │
450// │ ╎ │ l1loop_left │ ╎ │ │ │
451// │ ╎ └──────────────┘ ╎ │ │ │
452// │ ╎ ╎ │ │ │
453// │ └−−−−−−−−−−−−−−−−−−┘ │ │ │
454// │ │ │ │ │
455// │ │ │ │ │
456// │ ▼ │ │ │
457// │ ┌──────────────┐ │ │ │
458// │ │ l1loop_merge │ ─┘ │ │
459// │ └──────────────┘ │ │
460// │ ▲ │ │
461// │ └──────────────────────┘ │
462// │ │
463// │ │
464// └─────────────────────────────────────────────┘
465
466TEST_F(ExecutionSubgraphTest, PropagationLoop4) {
467 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
468 "exit",
469 {{"entry", "l1"},
470 {"l1", "l2"},
471 {"l1", "l1loop"},
472 {"l1loop", "l1loop_left"},
473 {"l1loop", "l1loop_right"},
474 {"l1loop_left", "l1loop_merge"},
475 {"l1loop_right", "l1loop_merge"},
476 {"l1loop_merge", "l1"},
477 {"l2", "exit"},
478 {"entry", "right"},
479 {"right", "exit"}}));
480 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]481 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light3a73ffb2021-01-25 14:11:05 +0000[diff] [blame]482 esg.RemoveBlock(blks.Get("l1loop_left"));
483 esg.Finalize();
484 ASSERT_TRUE(esg.IsValid());
485 ASSERT_TRUE(IsValidSubgraph(esg));
486 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
487 esg.ReachableBlocks().end());
488
489 ASSERT_EQ(contents.size(), 3u);
490
491 // Not present, no path through. If we got to l1 loop then we must merge back
492 // with l1 and l2 so they're bad too.
493 ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end());
494 ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
495 ASSERT_TRUE(contents.find(blks.Get("l1loop_left")) == contents.end());
496 ASSERT_TRUE(contents.find(blks.Get("l1loop_right")) == contents.end());
497 ASSERT_TRUE(contents.find(blks.Get("l1loop_merge")) == contents.end());
498 ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
499
500 // present, path through.
501 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
502 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
503 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
504}
505
506// +------------------------------------------------------+
507// | |
508// | +--------------+ +-------------+ |
509// | | right | <-- | entry | |
510// | +--------------+ +-------------+ |
511// | | | |
512// | | | |
513// | v v |
514// | +--------------+ +--------------------+ +----+
515// +> | exit | +> | l1 | --> | l2 |
516// +--------------+ | +--------------------+ +----+
517// | | ^
518// +---------------+ | |
519// | v |
520// +--------------+ +-------------+ |
521// | l1loop_right | <-- | l1loop | |
522// +--------------+ +-------------+ |
523// | |
524// | |
525// v |
526// + - - - - - - - - + |
527// ' removed ' |
528// ' ' |
529// ' +-------------+ ' |
530// ' | l1loop_left | ' -+
531// ' +-------------+ '
532// ' '
533// + - - - - - - - - +
534TEST_F(ExecutionSubgraphTest, PropagationLoop5) {
535 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
536 "exit",
537 {{"entry", "l1"},
538 {"l1", "l2"},
539 {"l1", "l1loop"},
540 {"l1loop", "l1loop_left"},
541 {"l1loop", "l1loop_right"},
542 {"l1loop_left", "l1"},
543 {"l1loop_right", "l1"},
544 {"l2", "exit"},
545 {"entry", "right"},
546 {"right", "exit"}}));
547 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]548 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light3a73ffb2021-01-25 14:11:05 +0000[diff] [blame]549 esg.RemoveBlock(blks.Get("l1loop_left"));
550 esg.Finalize();
551 ASSERT_TRUE(esg.IsValid());
552 ASSERT_TRUE(IsValidSubgraph(esg));
553 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
554 esg.ReachableBlocks().end());
555
556 ASSERT_EQ(contents.size(), 3u);
557
558 // Not present, no path through. If we got to l1 loop then we must merge back
559 // with l1 and l2 so they're bad too.
560 ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end());
561 ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end());
562 ASSERT_TRUE(contents.find(blks.Get("l1loop_left")) == contents.end());
563 ASSERT_TRUE(contents.find(blks.Get("l1loop_right")) == contents.end());
564 ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end());
565
566 // present, path through.
567 ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end());
568 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
569 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
570}
571
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]572TEST_F(ExecutionSubgraphTest, Invalid) {
573 AdjacencyListGraph blks(SetupFromAdjacencyList(
574 "entry",
575 "exit",
576 { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } }));
577 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]578 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]579 esg.RemoveBlock(blks.Get("left"));
580 esg.RemoveBlock(blks.Get("right"));
581 esg.Finalize();
582
583 ASSERT_FALSE(esg.IsValid());
584 ASSERT_FALSE(IsValidSubgraph(esg));
585 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
586 esg.ReachableBlocks().end());
587
588 ASSERT_EQ(contents.size(), 0u);
589}
590// Sibling branches are disconnected.
591TEST_F(ExecutionSubgraphTest, Exclusions) {
592 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
593 "exit",
594 { { "entry", "a" },
595 { "entry", "b" },
596 { "entry", "c" },
597 { "a", "exit" },
598 { "b", "exit" },
599 { "c", "exit" } }));
600 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]601 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]602 esg.RemoveBlock(blks.Get("a"));
603 esg.RemoveBlock(blks.Get("c"));
604 esg.Finalize();
605 ASSERT_TRUE(esg.IsValid());
606 ASSERT_TRUE(IsValidSubgraph(esg));
607 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
608 esg.ReachableBlocks().end());
609
610 ASSERT_EQ(contents.size(), 3u);
611 // Not present, no path through.
612 ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end());
613 ASSERT_TRUE(contents.find(blks.Get("c")) == contents.end());
614
615 // present, path through.
616 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
617 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
618 ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end());
619
620 ArrayRef<const ExecutionSubgraph::ExcludedCohort> exclusions(esg.GetExcludedCohorts());
621 ASSERT_EQ(exclusions.size(), 2u);
622 std::unordered_set<const HBasicBlock*> exclude_a({ blks.Get("a") });
623 std::unordered_set<const HBasicBlock*> exclude_c({ blks.Get("c") });
624 ASSERT_TRUE(std::find_if(exclusions.cbegin(),
625 exclusions.cend(),
626 [&](const ExecutionSubgraph::ExcludedCohort& it) {
627 return it.Blocks() == exclude_a;
628 }) != exclusions.cend());
629 ASSERT_TRUE(std::find_if(exclusions.cbegin(),
630 exclusions.cend(),
631 [&](const ExecutionSubgraph::ExcludedCohort& it) {
632 return it.Blocks() == exclude_c;
633 }) != exclusions.cend());
634}
635
636// Sibling branches are disconnected.
637// +- - - - - - - - - - - - - - - - - - - - - - +
638// ' remove_c '
639// ' '
640// ' +-----------+ '
641// ' | c_begin_2 | -------------------------+ '
642// ' +-----------+ | '
643// ' | '
644// +- - - - - - - - - - - - - - - - - - | '
645// ^ ' | '
646// | ' | '
647// | ' | '
648// + - - - - - -+ ' | '
649// ' remove_a ' ' | '
650// ' ' ' | '
651// ' +--------+ ' +-----------+ +---+' | '
652// ' | **a** | ' <-- | entry | --> | b |' | '
653// ' +--------+ ' +-----------+ +---+' | '
654// ' ' ' | '
655// + - - - - - -+ ' | '
656// | | | ' | '
657// | | | ' | '
658// | v | ' | '
659// | +- - - - - - - -+ | ' | '
660// | ' ' | ' | '
661// | ' +-----------+ ' | ' | '
662// | ' | c_begin_1 | ' | ' | '
663// | ' +-----------+ ' | ' | '
664// | ' | ' | ' | '
665// | ' | ' | ' | '
666// | ' | ' | ' | '
667// + - - - - - - - - -+ | + - - - | - - - - - - - + | ' | '
668// ' ' | + v ' | + | '
669// ' +---------+ | +-----------+ | | '
670// ' | c_end_2 | <-------+--------------- | **c_mid** | <-----------------+------+ '
671// ' +---------+ | +-----------+ | '
672// ' ' | + | ' | + '
673// + - - - - - - - - -+ | + - - - | - - - - - - - + | + - - - +
674// | | ' | ' |
675// | | ' | ' |
676// | | ' v ' |
677// | | ' +-----------+ ' |
678// | | ' | c_end_1 | ' |
679// | | ' +-----------+ ' |
680// | | ' ' |
681// | | +- - - - - - - -+ |
682// | | | |
683// | | | |
684// | | v v
685// | | +---------------------------------+
686// | +------------> | exit |
687// | +---------------------------------+
688// | ^
689// +------------------------------------+
690TEST_F(ExecutionSubgraphTest, ExclusionExtended) {
691 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
692 "exit",
693 { { "entry", "a" },
694 { "entry", "b" },
695 { "entry", "c_begin_1" },
696 { "entry", "c_begin_2" },
697 { "c_begin_1", "c_mid" },
698 { "c_begin_2", "c_mid" },
699 { "c_mid", "c_end_1" },
700 { "c_mid", "c_end_2" },
701 { "a", "exit" },
702 { "b", "exit" },
703 { "c_end_1", "exit" },
704 { "c_end_2", "exit" } }));
705 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]706 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]707 esg.RemoveBlock(blks.Get("a"));
708 esg.RemoveBlock(blks.Get("c_mid"));
709 esg.Finalize();
710 ASSERT_TRUE(esg.IsValid());
711 ASSERT_TRUE(IsValidSubgraph(esg));
712 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
713 esg.ReachableBlocks().end());
714
715 ASSERT_EQ(contents.size(), 3u);
716 // Not present, no path through.
717 ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end());
718 ASSERT_TRUE(contents.find(blks.Get("c_begin_1")) == contents.end());
719 ASSERT_TRUE(contents.find(blks.Get("c_begin_2")) == contents.end());
720 ASSERT_TRUE(contents.find(blks.Get("c_mid")) == contents.end());
721 ASSERT_TRUE(contents.find(blks.Get("c_end_1")) == contents.end());
722 ASSERT_TRUE(contents.find(blks.Get("c_end_2")) == contents.end());
723
724 // present, path through.
725 ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end());
726 ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end());
727 ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end());
728
729 ArrayRef<const ExecutionSubgraph::ExcludedCohort> exclusions(esg.GetExcludedCohorts());
730 ASSERT_EQ(exclusions.size(), 2u);
731 BlockSet exclude_a({ blks.Get("a") });
732 BlockSet exclude_c({ blks.Get("c_begin_1"),
733 blks.Get("c_begin_2"),
734 blks.Get("c_mid"),
735 blks.Get("c_end_1"),
736 blks.Get("c_end_2") });
737 ASSERT_TRUE(std::find_if(exclusions.cbegin(),
738 exclusions.cend(),
739 [&](const ExecutionSubgraph::ExcludedCohort& it) {
740 return it.Blocks() == exclude_a;
741 }) != exclusions.cend());
742 ASSERT_TRUE(
743 std::find_if(
744 exclusions.cbegin(), exclusions.cend(), [&](const ExecutionSubgraph::ExcludedCohort& it) {
745 return it.Blocks() == exclude_c &&
746 BlockSet({ blks.Get("c_begin_1"), blks.Get("c_begin_2") }) == it.EntryBlocks() &&
747 BlockSet({ blks.Get("c_end_1"), blks.Get("c_end_2") }) == it.ExitBlocks();
748 }) != exclusions.cend());
749}
750
751// ┌───────┐ ┌────────────┐
752// ┌─ │ right │ ◀── │ entry │
753// │ └───────┘ └────────────┘
754// │ │
755// │ │
756// │ ▼
757// │ ┌────────────┐
758// │ │ esc_top │
759// │ └────────────┘
760// │ │
761// │ │
762// │ ▼
763// │ ┌────────────┐
764// └──────────────▶ │ middle │ ─┐
765// └────────────┘ │
766// │ │
767// │ │
768// ▼ │
769// ┌────────────┐ │
770// │ esc_bottom │ │
771// └────────────┘ │
772// │ │
773// │ │
774// ▼ │
775// ┌────────────┐ │
776// │ exit │ ◀┘
777// └────────────┘
778TEST_F(ExecutionSubgraphTest, InAndOutEscape) {
779 AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
780 "exit",
781 { { "entry", "esc_top" },
782 { "entry", "right" },
783 { "esc_top", "middle" },
784 { "right", "middle" },
785 { "middle", "exit" },
786 { "middle", "esc_bottom" },
787 { "esc_bottom", "exit" } }));
788
789 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]790 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]791 esg.RemoveBlock(blks.Get("esc_top"));
792 esg.RemoveBlock(blks.Get("esc_bottom"));
793 esg.Finalize();
794
795 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
796 esg.ReachableBlocks().end());
797 ASSERT_EQ(contents.size(), 0u);
798 ASSERT_FALSE(esg.IsValid());
799 ASSERT_FALSE(IsValidSubgraph(esg));
800
801 ASSERT_EQ(contents.size(), 0u);
802}
803
804// Test with max number of successors and no removals.
805TEST_F(ExecutionSubgraphTest, BigNodes) {
806 std::vector<std::string> mid_blocks;
807 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
808 std::ostringstream oss;
809 oss << "blk" << i;
810 mid_blocks.push_back(oss.str().c_str());
811 }
812 ASSERT_EQ(mid_blocks.size(), ExecutionSubgraph::kMaxFilterableSuccessors);
813 std::vector<AdjacencyListGraph::Edge> edges;
814 for (const auto& mid : mid_blocks) {
815 edges.emplace_back("entry", mid);
816 edges.emplace_back(mid, "exit");
817 }
818 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
819 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]820 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]821 esg.Finalize();
822 ASSERT_TRUE(esg.IsValid());
823 ASSERT_TRUE(IsValidSubgraph(esg));
824 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
825 esg.ReachableBlocks().end());
826
827 for (const auto& mid : mid_blocks) {
828 EXPECT_TRUE(contents.find(blks.Get(mid)) != contents.end()) << mid;
829 }
830 // + 2 for entry and exit nodes.
831 ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2);
832}
833
834// Test with max number of successors and some removals.
835TEST_F(ExecutionSubgraphTest, BigNodesMissing) {
836 std::vector<std::string> mid_blocks;
837 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
838 std::ostringstream oss;
839 oss << "blk" << i;
840 mid_blocks.push_back(oss.str());
841 }
842 std::vector<AdjacencyListGraph::Edge> edges;
843 for (const auto& mid : mid_blocks) {
844 edges.emplace_back("entry", mid);
845 edges.emplace_back(mid, "exit");
846 }
847 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
848 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]849 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]850 esg.RemoveBlock(blks.Get("blk2"));
851 esg.RemoveBlock(blks.Get("blk4"));
852 esg.Finalize();
853 ASSERT_TRUE(esg.IsValid());
854 ASSERT_TRUE(IsValidSubgraph(esg));
855 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
856 esg.ReachableBlocks().end());
857
858 ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2 - 2);
859
860 // Not present, no path through.
861 ASSERT_TRUE(contents.find(blks.Get("blk2")) == contents.end());
862 ASSERT_TRUE(contents.find(blks.Get("blk4")) == contents.end());
863}
864
865// Test with max number of successors and all successors removed.
866TEST_F(ExecutionSubgraphTest, BigNodesNoPath) {
867 std::vector<std::string> mid_blocks;
868 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) {
869 std::ostringstream oss;
870 oss << "blk" << i;
871 mid_blocks.push_back(oss.str());
872 }
873 std::vector<AdjacencyListGraph::Edge> edges;
874 for (const auto& mid : mid_blocks) {
875 edges.emplace_back("entry", mid);
876 edges.emplace_back(mid, "exit");
877 }
878 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
879 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]880 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]881 for (const auto& mid : mid_blocks) {
882 esg.RemoveBlock(blks.Get(mid));
883 }
884 esg.Finalize();
885 ASSERT_FALSE(esg.IsValid());
886 ASSERT_FALSE(IsValidSubgraph(esg));
887}
888
889// Test with max number of successors
890TEST_F(ExecutionSubgraphTest, CanAnalyseBig) {
891 // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario.
892 constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000;
893 std::vector<std::string> mid_blocks;
894 for (auto i : Range(kNumBlocks)) {
895 std::ostringstream oss;
896 oss << "blk" << i;
897 mid_blocks.push_back(oss.str());
898 }
899 std::vector<AdjacencyListGraph::Edge> edges;
900 for (auto cur : Range(kNumBlocks)) {
901 for (auto nxt :
902 Range(cur + 1,
903 std::min(cur + ExecutionSubgraph::kMaxFilterableSuccessors + 1, kNumBlocks))) {
904 edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
905 }
906 }
907 AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges));
908 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
909
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]910 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]911 esg.Finalize();
912 ASSERT_TRUE(esg.IsValid());
913 ASSERT_TRUE(IsValidSubgraph(esg));
914 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
915 esg.ReachableBlocks().end());
916
917 ASSERT_EQ(contents.size(), kNumBlocks);
918}
919
920// Test with many successors
921TEST_F(ExecutionSubgraphTest, CanAnalyseBig2) {
922 // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario.
923 constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000;
924 constexpr size_t kTestMaxSuccessors = ExecutionSubgraph::kMaxFilterableSuccessors - 1;
925 std::vector<std::string> mid_blocks;
926 for (auto i : Range(kNumBlocks)) {
927 std::ostringstream oss;
928 oss << "blk" << i;
929 mid_blocks.push_back(oss.str());
930 }
931 std::vector<AdjacencyListGraph::Edge> edges;
932 for (auto cur : Range(kNumBlocks)) {
933 for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
934 edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
935 }
936 }
937 edges.emplace_back(mid_blocks.front(), mid_blocks.back());
938 AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges));
939 ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_));
Vladimir Marko5c824932021-06-02 15:54:17 +0100[diff] [blame]940 ExecutionSubgraph esg(graph_, GetScopedAllocator());
Alex Light86fe9b82020-11-16 16:54:01 +0000[diff] [blame]941 constexpr size_t kToRemoveIdx = kNumBlocks / 2;
942 HBasicBlock* remove_implicit = blks.Get(mid_blocks[kToRemoveIdx]);
943 for (HBasicBlock* pred : remove_implicit->GetPredecessors()) {
944 esg.RemoveBlock(pred);
945 }
946 esg.Finalize();
947 EXPECT_TRUE(esg.IsValid());
948 EXPECT_TRUE(IsValidSubgraph(esg));
949 std::unordered_set<const HBasicBlock*> contents(esg.ReachableBlocks().begin(),
950 esg.ReachableBlocks().end());
951
952 // Only entry and exit. The middle ones should eliminate everything else.
953 EXPECT_EQ(contents.size(), 2u);
954 EXPECT_TRUE(contents.find(remove_implicit) == contents.end());
955 EXPECT_TRUE(contents.find(blks.Get(mid_blocks.front())) != contents.end());
956 EXPECT_TRUE(contents.find(blks.Get(mid_blocks.back())) != contents.end());
957}
958
959// Test with too many successors
960TEST_F(ExecutionSubgraphTest, CanNotAnalyseBig) {
961 std::vector<std::string> mid_blocks;
962 for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors + 4)) {
963 std::ostringstream oss;
964 oss << "blk" << i;
965 mid_blocks.push_back(oss.str());
966 }
967 std::vector<AdjacencyListGraph::Edge> edges;
968 for (const auto& mid : mid_blocks) {
969 edges.emplace_back("entry", mid);
970 edges.emplace_back(mid, "exit");
971 }
972 AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges));
973 ASSERT_FALSE(ExecutionSubgraph::CanAnalyse(graph_));
974}
975} // namespace art