From b8686ce4c93eba7192ed7ef89e7ffd9f3aa6cd07 Mon Sep 17 00:00:00 2001 From: Alex Light Date: Mon, 2 Nov 2020 08:48:33 -0800 Subject: 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 --- compiler/optimizing/execution_subgraph_test.cc | 144 +++++++++++++++++++++++++ 1 file changed, 144 insertions(+) (limited to 'compiler/optimizing/execution_subgraph_test.cc') 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 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 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", -- cgit v1.2.3-59-g8ed1b