From bb6cda60e4418c0ab557ea4090e046bed8206763 Mon Sep 17 00:00:00 2001 From: Alex Light Date: Thu, 9 Jul 2020 13:24:56 -0700 Subject: Partial LSE analysis & store removal This is the first piece of partial LSE for art. This CL adds analysis tools needed to implement partial LSE. More immediately, it improves LSE so that it will remove stores that are provably non-observable based on the location they occur. For example: ``` Foo o = new Foo(); if (xyz) { check(foo); foo.x++; } else { foo.x = 12; } return foo.x; ``` The store of 12 can be removed because the only escape in this method is unreachable and was not executed by the point we reach the store. The main purpose of this CL is to add the analysis tools needed to implement partial Load-Store elimination. Namely it includes tracking of which blocks are escaping and the groups of blocks that we cannot remove allocations from. The actual impact of this change is incredibly minor, being triggered only once in a AOSP code. go/lem shows only minor effects to compile-time and no effect on the compiled code. See go/lem-allight-partial-lse-2 for numbers. Compile time shows an average of 1.4% regression (max regression is 7% with 0.2 noise). This CL adds a new 'reachability' concept to the HGraph. If this has been calculated it allows one to quickly query whether there is any execution path containing two blocks in a given order. This is used to define a notion of sections of graph from which the escape of some allocation is inevitable. Test: art_compiler_tests Test: treehugger Bug: 67037140 Change-Id: I0edc8d6b73f7dd329cb1ea7923080a0abe913ea6 --- compiler/optimizing/execution_subgraph_test.cc | 831 +++++++++++++++++++++++++ 1 file changed, 831 insertions(+) create mode 100644 compiler/optimizing/execution_subgraph_test.cc (limited to 'compiler/optimizing/execution_subgraph_test.cc') diff --git a/compiler/optimizing/execution_subgraph_test.cc b/compiler/optimizing/execution_subgraph_test.cc new file mode 100644 index 0000000000..1fc00d9f6b --- /dev/null +++ b/compiler/optimizing/execution_subgraph_test.cc @@ -0,0 +1,831 @@ +/* + * Copyright (C) 2020 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "execution_subgraph_test.h" + +#include +#include +#include +#include +#include + +#include "base/scoped_arena_allocator.h" +#include "base/stl_util.h" +#include "class_root.h" +#include "dex/dex_file_types.h" +#include "dex/method_reference.h" +#include "entrypoints/quick/quick_entrypoints_enum.h" +#include "execution_subgraph.h" +#include "gtest/gtest.h" +#include "handle.h" +#include "handle_scope.h" +#include "nodes.h" +#include "optimizing/data_type.h" +#include "optimizing_unit_test.h" +#include "scoped_thread_state_change.h" + +namespace art { + +using BlockSet = std::unordered_set; + +// Helper that checks validity directly. +bool ExecutionSubgraphTestHelper::CalculateValidity(HGraph* graph, const ExecutionSubgraph* esg) { + bool reached_end = false; + std::queue worklist; + std::unordered_set visited; + worklist.push(graph->GetEntryBlock()); + while (!worklist.empty()) { + const HBasicBlock* cur = worklist.front(); + worklist.pop(); + if (visited.find(cur) != visited.end()) { + continue; + } else { + visited.insert(cur); + } + if (cur == graph->GetExitBlock()) { + reached_end = true; + continue; + } + bool has_succ = false; + for (const HBasicBlock* succ : cur->GetSuccessors()) { + DCHECK(succ != nullptr) << "Bad successors on block " << cur->GetBlockId(); + if (!esg->ContainsBlock(succ)) { + continue; + } + has_succ = true; + worklist.push(succ); + } + if (!has_succ) { + // We aren't at the end and have nowhere to go so fail. + return false; + } + } + return reached_end; +} + +class ExecutionSubgraphTest : public OptimizingUnitTest { + public: + ExecutionSubgraphTest() : graph_(CreateGraph()) {} + + AdjacencyListGraph SetupFromAdjacencyList(const std::string_view entry_name, + const std::string_view exit_name, + const std::vector& adj) { + return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj); + } + + bool IsValidSubgraph(const ExecutionSubgraph* esg) { + return ExecutionSubgraphTestHelper::CalculateValidity(graph_, esg); + } + + bool IsValidSubgraph(const ExecutionSubgraph& esg) { + return ExecutionSubgraphTestHelper::CalculateValidity(graph_, &esg); + } + + HGraph* graph_; +}; + +// Some comparators used by these tests to avoid having to deal with various set types. +template >> +bool operator==(const BlockSet& bs, const BLKS& sas) { + std::unordered_set us(sas.begin(), sas.end()); + return bs == us; +} +template >> +bool operator==(const BLKS& sas, const BlockSet& bs) { + return bs == sas; +} +template >> +bool operator!=(const BlockSet& bs, const BLKS& sas) { + return !(bs == sas); +} +template >> +bool operator!=(const BLKS& sas, const BlockSet& bs) { + return !(bs == sas); +} + +// +-------+ +-------+ +// | right | <-- | entry | +// +-------+ +-------+ +// | | +// | | +// | v +// | + - - - - - + +// | ' removed ' +// | ' ' +// | ' +-------+ ' +// | ' | left | ' +// | ' +-------+ ' +// | ' ' +// | + - - - - - + +// | | +// | | +// | v +// | +-------+ +// +---------> | exit | +// +-------+ +TEST_F(ExecutionSubgraphTest, Basic) { + AdjacencyListGraph blks(SetupFromAdjacencyList( + "entry", + "exit", + { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("left")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 3u); + ASSERT_TRUE(contents.find(blks.Get("left")) == contents.end()); + + ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); + esg.RemoveBlock(blks.Get("right")); + esg.Finalize(); + std::unordered_set contents_2(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + ASSERT_EQ(contents_2.size(), 0u); +} + +// +-------+ +-------+ +// | right | <-- | entry | +// +-------+ +-------+ +// | | +// | | +// | v +// | + - - - - - - - - - - - - - - - - - - - -+ +// | ' indirectly_removed ' +// | ' ' +// | ' +-------+ +-----+ ' +// | ' | l1 | -------------------> | l1r | ' +// | ' +-------+ +-----+ ' +// | ' | | ' +// | ' | | ' +// | ' v | ' +// | ' +-------+ | ' +// | ' | l1l | | ' +// | ' +-------+ | ' +// | ' | | ' +// | ' | | ' +// | ' | | ' +// + - - - - - - - -+ | +- - - | | ' +// ' ' | +- v | ' +// ' +-----+ | +----------------+ | ' +// ' | l2r | <---------+-------------- | l2 (removed) | <-------------+ ' +// ' +-----+ | +----------------+ ' +// ' | ' | +- | ' +// ' | - - -+ | +- - - | - - - - - - - - - - - - - -+ +// ' | ' | ' | ' +// ' | ' | ' | ' +// ' | ' | ' v ' +// ' | ' | ' +-------+ ' +// ' | ' | ' | l2l | ' +// ' | ' | ' +-------+ ' +// ' | ' | ' | ' +// ' | ' | ' | ' +// ' | ' | ' | ' +// ' | - - -+ | +- - - | ' +// ' | ' | +- v ' +// ' | | +-------+ ' +// ' +---------------+-------------> | l3 | ' +// ' | +-------+ ' +// ' ' | +- ' +// + - - - - - - - -+ | +- - - - - - - - - + +// | | +// | | +// | v +// | +-------+ +// +-----------> | exit | +// +-------+ +TEST_F(ExecutionSubgraphTest, Propagation) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "l1" }, + { "l1", "l1l" }, + { "l1", "l1r" }, + { "l1l", "l2" }, + { "l1r", "l2" }, + { "l2", "l2l" }, + { "l2", "l2r" }, + { "l2l", "l3" }, + { "l2r", "l3" }, + { "l3", "exit" }, + { "entry", "right" }, + { "right", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("l2")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + // ASSERT_EQ(contents.size(), 3u); + // Not present, no path through. + ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l3")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1l")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1r")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l2l")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l2r")) == contents.end()); + + // present, path through. + ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); +} + +// +------------------------------------+ +// | | +// | +-------+ +-------+ | +// | | right | <-- | entry | | +// | +-------+ +-------+ | +// | | | | +// | | | | +// | | v | +// | | +-------+ +--------+ +// +----+---------> | l1 | --> | l1loop | +// | +-------+ +--------+ +// | | +// | | +// | v +// | +- - - - - -+ +// | ' removed ' +// | ' ' +// | ' +-------+ ' +// | ' | l2 | ' +// | ' +-------+ ' +// | ' ' +// | +- - - - - -+ +// | | +// | | +// | v +// | +-------+ +// +---------> | exit | +// +-------+ +TEST_F(ExecutionSubgraphTest, PropagationLoop) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "l1" }, + { "l1", "l2" }, + { "l1", "l1loop" }, + { "l1loop", "l1" }, + { "l2", "exit" }, + { "entry", "right" }, + { "right", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("l2")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 5u); + + // Not present, no path through. + ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end()); + + // present, path through. + // Since the loop can diverge we should leave it in the execution subgraph. + ASSERT_TRUE(contents.find(blks.Get("l1")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1loop")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); +} + +// +--------------------------------+ +// | | +// | +-------+ +-------+ | +// | | right | <-- | entry | | +// | +-------+ +-------+ | +// | | | | +// | | | | +// | | v | +// | | +-------+ +--------+ +// +----+---------> | l1 | --> | l1loop | +// | +-------+ +--------+ +// | | +// | | +// | v +// | +-------+ +// | | l2 | +// | +-------+ +// | | +// | | +// | v +// | +-------+ +// +---------> | exit | +// +-------+ +TEST_F(ExecutionSubgraphTest, PropagationLoop2) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "l1" }, + { "l1", "l2" }, + { "l1", "l1loop" }, + { "l1loop", "l1" }, + { "l2", "exit" }, + { "entry", "right" }, + { "right", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("l1")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 3u); + + // Not present, no path through. + ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end()); + + // present, path through. + ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); +} + +// +--------------------------------+ +// | | +// | +-------+ +-------+ | +// | | right | <-- | entry | | +// | +-------+ +-------+ | +// | | | | +// | | | | +// | | v | +// | | +-------+ +--------+ +// +----+---------> | l1 | --> | l1loop | +// | +-------+ +--------+ +// | | +// | | +// | v +// | +-------+ +// | | l2 | +// | +-------+ +// | | +// | | +// | v +// | +-------+ +// +---------> | exit | +// +-------+ +TEST_F(ExecutionSubgraphTest, PropagationLoop3) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "l1" }, + { "l1", "l2" }, + { "l1", "l1loop" }, + { "l1loop", "l1" }, + { "l2", "exit" }, + { "entry", "right" }, + { "right", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("l1loop")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 3u); + + // Not present, no path through. If we got to l1 loop then we must merge back + // with l1 and l2 so they're bad too. + ASSERT_TRUE(contents.find(blks.Get("l1loop")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l2")) == contents.end()); + + // present, path through. + ASSERT_TRUE(contents.find(blks.Get("right")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); +} + +TEST_F(ExecutionSubgraphTest, Invalid) { + AdjacencyListGraph blks(SetupFromAdjacencyList( + "entry", + "exit", + { { "entry", "left" }, { "entry", "right" }, { "left", "exit" }, { "right", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("left")); + esg.RemoveBlock(blks.Get("right")); + esg.Finalize(); + + ASSERT_FALSE(esg.IsValid()); + ASSERT_FALSE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 0u); +} +// Sibling branches are disconnected. +TEST_F(ExecutionSubgraphTest, Exclusions) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "a" }, + { "entry", "b" }, + { "entry", "c" }, + { "a", "exit" }, + { "b", "exit" }, + { "c", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("a")); + esg.RemoveBlock(blks.Get("c")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 3u); + // Not present, no path through. + ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("c")) == contents.end()); + + // present, path through. + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end()); + + ArrayRef exclusions(esg.GetExcludedCohorts()); + ASSERT_EQ(exclusions.size(), 2u); + std::unordered_set exclude_a({ blks.Get("a") }); + std::unordered_set exclude_c({ blks.Get("c") }); + ASSERT_TRUE(std::find_if(exclusions.cbegin(), + exclusions.cend(), + [&](const ExecutionSubgraph::ExcludedCohort& it) { + return it.Blocks() == exclude_a; + }) != exclusions.cend()); + ASSERT_TRUE(std::find_if(exclusions.cbegin(), + exclusions.cend(), + [&](const ExecutionSubgraph::ExcludedCohort& it) { + return it.Blocks() == exclude_c; + }) != exclusions.cend()); +} + +// Sibling branches are disconnected. +// +- - - - - - - - - - - - - - - - - - - - - - + +// ' remove_c ' +// ' ' +// ' +-----------+ ' +// ' | c_begin_2 | -------------------------+ ' +// ' +-----------+ | ' +// ' | ' +// +- - - - - - - - - - - - - - - - - - | ' +// ^ ' | ' +// | ' | ' +// | ' | ' +// + - - - - - -+ ' | ' +// ' remove_a ' ' | ' +// ' ' ' | ' +// ' +--------+ ' +-----------+ +---+' | ' +// ' | **a** | ' <-- | entry | --> | b |' | ' +// ' +--------+ ' +-----------+ +---+' | ' +// ' ' ' | ' +// + - - - - - -+ ' | ' +// | | | ' | ' +// | | | ' | ' +// | v | ' | ' +// | +- - - - - - - -+ | ' | ' +// | ' ' | ' | ' +// | ' +-----------+ ' | ' | ' +// | ' | c_begin_1 | ' | ' | ' +// | ' +-----------+ ' | ' | ' +// | ' | ' | ' | ' +// | ' | ' | ' | ' +// | ' | ' | ' | ' +// + - - - - - - - - -+ | + - - - | - - - - - - - + | ' | ' +// ' ' | + v ' | + | ' +// ' +---------+ | +-----------+ | | ' +// ' | c_end_2 | <-------+--------------- | **c_mid** | <-----------------+------+ ' +// ' +---------+ | +-----------+ | ' +// ' ' | + | ' | + ' +// + - - - - - - - - -+ | + - - - | - - - - - - - + | + - - - + +// | | ' | ' | +// | | ' | ' | +// | | ' v ' | +// | | ' +-----------+ ' | +// | | ' | c_end_1 | ' | +// | | ' +-----------+ ' | +// | | ' ' | +// | | +- - - - - - - -+ | +// | | | | +// | | | | +// | | v v +// | | +---------------------------------+ +// | +------------> | exit | +// | +---------------------------------+ +// | ^ +// +------------------------------------+ +TEST_F(ExecutionSubgraphTest, ExclusionExtended) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "a" }, + { "entry", "b" }, + { "entry", "c_begin_1" }, + { "entry", "c_begin_2" }, + { "c_begin_1", "c_mid" }, + { "c_begin_2", "c_mid" }, + { "c_mid", "c_end_1" }, + { "c_mid", "c_end_2" }, + { "a", "exit" }, + { "b", "exit" }, + { "c_end_1", "exit" }, + { "c_end_2", "exit" } })); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("a")); + esg.RemoveBlock(blks.Get("c_mid")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), 3u); + // Not present, no path through. + ASSERT_TRUE(contents.find(blks.Get("a")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("c_begin_1")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("c_begin_2")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("c_mid")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("c_end_1")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("c_end_2")) == contents.end()); + + // present, path through. + ASSERT_TRUE(contents.find(blks.Get("entry")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); + ASSERT_TRUE(contents.find(blks.Get("b")) != contents.end()); + + ArrayRef exclusions(esg.GetExcludedCohorts()); + ASSERT_EQ(exclusions.size(), 2u); + BlockSet exclude_a({ blks.Get("a") }); + BlockSet exclude_c({ blks.Get("c_begin_1"), + blks.Get("c_begin_2"), + blks.Get("c_mid"), + blks.Get("c_end_1"), + blks.Get("c_end_2") }); + ASSERT_TRUE(std::find_if(exclusions.cbegin(), + exclusions.cend(), + [&](const ExecutionSubgraph::ExcludedCohort& it) { + return it.Blocks() == exclude_a; + }) != exclusions.cend()); + ASSERT_TRUE( + std::find_if( + exclusions.cbegin(), exclusions.cend(), [&](const ExecutionSubgraph::ExcludedCohort& it) { + return it.Blocks() == exclude_c && + BlockSet({ blks.Get("c_begin_1"), blks.Get("c_begin_2") }) == it.EntryBlocks() && + BlockSet({ blks.Get("c_end_1"), blks.Get("c_end_2") }) == it.ExitBlocks(); + }) != exclusions.cend()); +} + +// ┌───────┐ ┌────────────┐ +// ┌─ │ right │ ◀── │ entry │ +// │ └───────┘ └────────────┘ +// │ │ +// │ │ +// │ ▼ +// │ ┌────────────┐ +// │ │ esc_top │ +// │ └────────────┘ +// │ │ +// │ │ +// │ ▼ +// │ ┌────────────┐ +// └──────────────▶ │ middle │ ─┐ +// └────────────┘ │ +// │ │ +// │ │ +// ▼ │ +// ┌────────────┐ │ +// │ esc_bottom │ │ +// └────────────┘ │ +// │ │ +// │ │ +// ▼ │ +// ┌────────────┐ │ +// │ exit │ ◀┘ +// └────────────┘ +TEST_F(ExecutionSubgraphTest, InAndOutEscape) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + { { "entry", "esc_top" }, + { "entry", "right" }, + { "esc_top", "middle" }, + { "right", "middle" }, + { "middle", "exit" }, + { "middle", "esc_bottom" }, + { "esc_bottom", "exit" } })); + + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("esc_top")); + esg.RemoveBlock(blks.Get("esc_bottom")); + esg.Finalize(); + + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + ASSERT_EQ(contents.size(), 0u); + ASSERT_FALSE(esg.IsValid()); + ASSERT_FALSE(IsValidSubgraph(esg)); + + ASSERT_EQ(contents.size(), 0u); +} + +// Test with max number of successors and no removals. +TEST_F(ExecutionSubgraphTest, BigNodes) { + std::vector mid_blocks; + for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) { + std::ostringstream oss; + oss << "blk" << i; + mid_blocks.push_back(oss.str().c_str()); + } + ASSERT_EQ(mid_blocks.size(), ExecutionSubgraph::kMaxFilterableSuccessors); + std::vector edges; + for (const auto& mid : mid_blocks) { + edges.emplace_back("entry", mid); + edges.emplace_back(mid, "exit"); + } + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges)); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + for (const auto& mid : mid_blocks) { + EXPECT_TRUE(contents.find(blks.Get(mid)) != contents.end()) << mid; + } + // + 2 for entry and exit nodes. + ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2); +} + +// Test with max number of successors and some removals. +TEST_F(ExecutionSubgraphTest, BigNodesMissing) { + std::vector mid_blocks; + for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) { + std::ostringstream oss; + oss << "blk" << i; + mid_blocks.push_back(oss.str()); + } + std::vector edges; + for (const auto& mid : mid_blocks) { + edges.emplace_back("entry", mid); + edges.emplace_back(mid, "exit"); + } + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges)); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("blk2")); + esg.RemoveBlock(blks.Get("blk4")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), ExecutionSubgraph::kMaxFilterableSuccessors + 2 - 2); + + // Not present, no path through. + ASSERT_TRUE(contents.find(blks.Get("blk2")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("blk4")) == contents.end()); +} + +// Test with max number of successors and all successors removed. +TEST_F(ExecutionSubgraphTest, BigNodesNoPath) { + std::vector mid_blocks; + for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors)) { + std::ostringstream oss; + oss << "blk" << i; + mid_blocks.push_back(oss.str()); + } + std::vector edges; + for (const auto& mid : mid_blocks) { + edges.emplace_back("entry", mid); + edges.emplace_back(mid, "exit"); + } + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges)); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + for (const auto& mid : mid_blocks) { + esg.RemoveBlock(blks.Get(mid)); + } + esg.Finalize(); + ASSERT_FALSE(esg.IsValid()); + ASSERT_FALSE(IsValidSubgraph(esg)); +} + +// Test with max number of successors +TEST_F(ExecutionSubgraphTest, CanAnalyseBig) { + // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario. + constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000; + std::vector mid_blocks; + for (auto i : Range(kNumBlocks)) { + std::ostringstream oss; + oss << "blk" << i; + mid_blocks.push_back(oss.str()); + } + std::vector edges; + for (auto cur : Range(kNumBlocks)) { + for (auto nxt : + Range(cur + 1, + std::min(cur + ExecutionSubgraph::kMaxFilterableSuccessors + 1, kNumBlocks))) { + edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]); + } + } + AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges)); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + ASSERT_EQ(contents.size(), kNumBlocks); +} + +// Test with many successors +TEST_F(ExecutionSubgraphTest, CanAnalyseBig2) { + // Make an absurdly huge and well connected graph. This should be pretty worst-case scenario. + constexpr size_t kNumBlocks = ExecutionSubgraph::kMaxFilterableSuccessors + 1000; + constexpr size_t kTestMaxSuccessors = ExecutionSubgraph::kMaxFilterableSuccessors - 1; + std::vector mid_blocks; + for (auto i : Range(kNumBlocks)) { + std::ostringstream oss; + oss << "blk" << i; + mid_blocks.push_back(oss.str()); + } + std::vector edges; + for (auto cur : Range(kNumBlocks)) { + for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) { + edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]); + } + } + edges.emplace_back(mid_blocks.front(), mid_blocks.back()); + AdjacencyListGraph blks(SetupFromAdjacencyList(mid_blocks.front(), mid_blocks.back(), edges)); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + constexpr size_t kToRemoveIdx = kNumBlocks / 2; + HBasicBlock* remove_implicit = blks.Get(mid_blocks[kToRemoveIdx]); + for (HBasicBlock* pred : remove_implicit->GetPredecessors()) { + esg.RemoveBlock(pred); + } + esg.Finalize(); + EXPECT_TRUE(esg.IsValid()); + EXPECT_TRUE(IsValidSubgraph(esg)); + std::unordered_set contents(esg.ReachableBlocks().begin(), + esg.ReachableBlocks().end()); + + // Only entry and exit. The middle ones should eliminate everything else. + EXPECT_EQ(contents.size(), 2u); + EXPECT_TRUE(contents.find(remove_implicit) == contents.end()); + EXPECT_TRUE(contents.find(blks.Get(mid_blocks.front())) != contents.end()); + EXPECT_TRUE(contents.find(blks.Get(mid_blocks.back())) != contents.end()); +} + +// Test with too many successors +TEST_F(ExecutionSubgraphTest, CanNotAnalyseBig) { + std::vector mid_blocks; + for (auto i : Range(ExecutionSubgraph::kMaxFilterableSuccessors + 4)) { + std::ostringstream oss; + oss << "blk" << i; + mid_blocks.push_back(oss.str()); + } + std::vector edges; + for (const auto& mid : mid_blocks) { + edges.emplace_back("entry", mid); + edges.emplace_back(mid, "exit"); + } + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", "exit", edges)); + ASSERT_FALSE(ExecutionSubgraph::CanAnalyse(graph_)); +} +} // namespace art -- cgit v1.2.3-59-g8ed1b