summaryrefslogtreecommitdiff
path: root/compiler/optimizing/execution_subgraph_test.cc
diff options
context:
space:
mode:
author Alex Light <allight@google.com> 2020-11-02 08:48:33 -0800
committer Alex Light <allight@google.com> 2021-01-21 17:58:10 +0000
commitb8686ce4c93eba7192ed7ef89e7ffd9f3aa6cd07 (patch)
tree1721ee940f978736a2212d693271ee698897cb0b /compiler/optimizing/execution_subgraph_test.cc
parent625048049558d394d50b6e98885b8c210e481bf1 (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.cc144
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",