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
40 namespace art {
41
42 using BlockSet = std::unordered_set<const HBasicBlock*>;
43
44 // Helper that checks validity directly.
CalculateValidity(HGraph * graph,const ExecutionSubgraph * esg)45 bool 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
79 class ExecutionSubgraphTest : public OptimizingUnitTest {
80 public:
ExecutionSubgraphTest()81 ExecutionSubgraphTest() : graph_(CreateGraph()) {}
82
SetupFromAdjacencyList(const std::string_view entry_name,const std::string_view exit_name,const std::vector<AdjacencyListGraph::Edge> & adj)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
IsValidSubgraph(const ExecutionSubgraph * esg)89 bool IsValidSubgraph(const ExecutionSubgraph* esg) {
90 return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg);
91 }
92
IsValidSubgraph(const ExecutionSubgraph & esg)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.
101 template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
operator ==(const BlockSet & bs,const BLKS & sas)102 bool operator==(const BlockSet& bs, const BLKS& sas) {
103 std::unordered_set<const HBasicBlock*> us(sas.begin(), sas.end());
104 return bs == us;
105 }
106 template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
operator ==(const BLKS & sas,const BlockSet & bs)107 bool operator==(const BLKS& sas, const BlockSet& bs) {
108 return bs == sas;
109 }
110 template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
operator !=(const BlockSet & bs,const BLKS & sas)111 bool operator!=(const BlockSet& bs, const BLKS& sas) {
112 return !(bs == sas);
113 }
114 template <typename BLKS, typename = std::enable_if_t<!std::is_same_v<BlockSet, BLKS>>>
operator !=(const BLKS & sas,const BlockSet & bs)115 bool 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 // +-------+
TEST_F(ExecutionSubgraphTest,Basic)139 TEST_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_, 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 // +-------+
TEST_F(ExecutionSubgraphTest,Propagation)216 TEST_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_, 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 // +-------+
TEST_F(ExecutionSubgraphTest,PropagationLoop)284 TEST_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_, 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 // +-------+
TEST_F(ExecutionSubgraphTest,PropagationLoop2)340 TEST_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_, 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 // +-------+
TEST_F(ExecutionSubgraphTest,PropagationLoop3)395 TEST_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_, 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
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
TEST_F(ExecutionSubgraphTest,PropagationLoop4)466 TEST_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_));
481 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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 // + - - - - - - - - +
TEST_F(ExecutionSubgraphTest,PropagationLoop5)534 TEST_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_));
548 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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
TEST_F(ExecutionSubgraphTest,Invalid)572 TEST_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_));
578 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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.
TEST_F(ExecutionSubgraphTest,Exclusions)591 TEST_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_));
601 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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 // +------------------------------------+
TEST_F(ExecutionSubgraphTest,ExclusionExtended)690 TEST_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_));
706 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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 // └────────────┘
TEST_F(ExecutionSubgraphTest,InAndOutEscape)778 TEST_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_));
790 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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.
TEST_F(ExecutionSubgraphTest,BigNodes)805 TEST_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_));
820 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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.
TEST_F(ExecutionSubgraphTest,BigNodesMissing)835 TEST_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_));
849 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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.
TEST_F(ExecutionSubgraphTest,BigNodesNoPath)866 TEST_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_));
880 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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
TEST_F(ExecutionSubgraphTest,CanAnalyseBig)890 TEST_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
910 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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
TEST_F(ExecutionSubgraphTest,CanAnalyseBig2)921 TEST_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_));
940 ExecutionSubgraph esg(graph_, GetScopedAllocator());
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
TEST_F(ExecutionSubgraphTest,CanNotAnalyseBig)960 TEST_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
976