diff options
author | 2020-11-02 08:48:33 -0800 | |
---|---|---|
committer | 2021-01-21 17:58:10 +0000 | |
commit | b8686ce4c93eba7192ed7ef89e7ffd9f3aa6cd07 (patch) | |
tree | 1721ee940f978736a2212d693271ee698897cb0b /compiler/optimizing/execution_subgraph_test.cc | |
parent | 625048049558d394d50b6e98885b8c210e481bf1 (diff) |
Partial Load Store Elimination
Add partial load-store elimination to the LSE pass. Partial LSE will
move object allocations which only escape along certain execution
paths closer to the escape point and allow more values to be
eliminated. It does this by creating new predicated load and store
instructions that are used when an object has only escaped some of the
time. In cases where the object has not escaped a default value will
be used.
Test: ./test.py --host
Test: ./test.py --target
Bug: 67037140
Change-Id: Idde67eb59ec90de79747cde17b552eec05b58497
Diffstat (limited to 'compiler/optimizing/execution_subgraph_test.cc')
-rw-r--r-- | compiler/optimizing/execution_subgraph_test.cc | 144 |
1 files changed, 144 insertions, 0 deletions
diff --git a/compiler/optimizing/execution_subgraph_test.cc b/compiler/optimizing/execution_subgraph_test.cc index 1fc00d9f6b..98e642f1a7 100644 --- a/compiler/optimizing/execution_subgraph_test.cc +++ b/compiler/optimizing/execution_subgraph_test.cc @@ -425,6 +425,150 @@ TEST_F(ExecutionSubgraphTest, PropagationLoop3) { ASSERT_TRUE(contents.find(blks.Get("exit")) != contents.end()); } +// ┌───────┐ ┌──────────────┐ +// │ right │ ◀── │ entry │ +// └───────┘ └──────────────┘ +// │ │ +// │ │ +// ▼ ▼ +// ┌────┐ ┌───────┐ ┌──────────────┐ +// │ l2 │ ──▶ │ exit │ ┌─ │ l1 │ ◀┐ +// └────┘ └───────┘ │ └──────────────┘ │ +// ▲ │ │ │ +// └───────────────────┘ │ │ +// ▼ │ +// ┌──────────────┐ │ ┌──────────────┐ +// ┌─ │ l1loop │ │ │ l1loop_right │ ◀┐ +// │ └──────────────┘ │ └──────────────┘ │ +// │ │ │ │ │ +// │ │ │ │ │ +// │ ▼ │ │ │ +// │ ┌−−−−−−−−−−−−−−−−−−┐ │ │ │ +// │ ╎ removed ╎ │ │ │ +// │ ╎ ╎ │ │ │ +// │ ╎ ┌──────────────┐ ╎ │ │ │ +// │ ╎ │ l1loop_left │ ╎ │ │ │ +// │ ╎ └──────────────┘ ╎ │ │ │ +// │ ╎ ╎ │ │ │ +// │ └−−−−−−−−−−−−−−−−−−┘ │ │ │ +// │ │ │ │ │ +// │ │ │ │ │ +// │ ▼ │ │ │ +// │ ┌──────────────┐ │ │ │ +// │ │ l1loop_merge │ ─┘ │ │ +// │ └──────────────┘ │ │ +// │ ▲ │ │ +// │ └──────────────────────┘ │ +// │ │ +// │ │ +// └─────────────────────────────────────────────┘ + +TEST_F(ExecutionSubgraphTest, PropagationLoop4) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + {{"entry", "l1"}, + {"l1", "l2"}, + {"l1", "l1loop"}, + {"l1loop", "l1loop_left"}, + {"l1loop", "l1loop_right"}, + {"l1loop_left", "l1loop_merge"}, + {"l1loop_right", "l1loop_merge"}, + {"l1loop_merge", "l1"}, + {"l2", "exit"}, + {"entry", "right"}, + {"right", "exit"}})); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("l1loop_left")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set<const HBasicBlock*> 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("l1loop_left")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1loop_right")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1loop_merge")) == 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 v | +// | +--------------+ +--------------------+ +----+ +// +> | exit | +> | l1 | --> | l2 | +// +--------------+ | +--------------------+ +----+ +// | | ^ +// +---------------+ | | +// | v | +// +--------------+ +-------------+ | +// | l1loop_right | <-- | l1loop | | +// +--------------+ +-------------+ | +// | | +// | | +// v | +// + - - - - - - - - + | +// ' removed ' | +// ' ' | +// ' +-------------+ ' | +// ' | l1loop_left | ' -+ +// ' +-------------+ ' +// ' ' +// + - - - - - - - - + +TEST_F(ExecutionSubgraphTest, PropagationLoop5) { + AdjacencyListGraph blks(SetupFromAdjacencyList("entry", + "exit", + {{"entry", "l1"}, + {"l1", "l2"}, + {"l1", "l1loop"}, + {"l1loop", "l1loop_left"}, + {"l1loop", "l1loop_right"}, + {"l1loop_left", "l1"}, + {"l1loop_right", "l1"}, + {"l2", "exit"}, + {"entry", "right"}, + {"right", "exit"}})); + ASSERT_TRUE(ExecutionSubgraph::CanAnalyse(graph_)); + ExecutionSubgraph esg(graph_, /*analysis_possible=*/true, GetScopedAllocator()); + esg.RemoveBlock(blks.Get("l1loop_left")); + esg.Finalize(); + ASSERT_TRUE(esg.IsValid()); + ASSERT_TRUE(IsValidSubgraph(esg)); + std::unordered_set<const HBasicBlock*> 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("l1loop_left")) == contents.end()); + ASSERT_TRUE(contents.find(blks.Get("l1loop_right")) == 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", |