Revision: 25078
Author: [email protected]
Date: Mon Nov 3 15:17:08 2014 UTC
Log: [turbofan] Introduce separate SelectLowering reducer.
Split lowering of Select nodes into a separate graph reducer and be more
clever when lowering to diamonds, i.e. reuse diamonds that have the same
condition and only add more phis to it.
TEST=unittests
[email protected]
Review URL: https://codereview.chromium.org/702463002
https://code.google.com/p/v8/source/detail?r=25078
Added:
/branches/bleeding_edge/src/compiler/select-lowering.cc
/branches/bleeding_edge/src/compiler/select-lowering.h
/branches/bleeding_edge/test/unittests/compiler/select-lowering-unittest.cc
Modified:
/branches/bleeding_edge/BUILD.gn
/branches/bleeding_edge/src/compiler/js-generic-lowering.cc
/branches/bleeding_edge/src/compiler/pipeline.cc
/branches/bleeding_edge/test/unittests/unittests.gyp
/branches/bleeding_edge/tools/gyp/v8.gyp
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/compiler/select-lowering.cc Mon Nov 3
15:17:08 2014 UTC
@@ -0,0 +1,54 @@
+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/compiler/select-lowering.h"
+
+#include "src/compiler/common-operator.h"
+#include "src/compiler/generic-node-inl.h"
+#include "src/compiler/graph.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+SelectLowering::SelectLowering(Graph* graph, CommonOperatorBuilder* common)
+ : common_(common),
+ graph_(graph),
+ merges_(Merges::key_compare(),
Merges::allocator_type(graph->zone())) {}
+
+
+SelectLowering::~SelectLowering() {}
+
+
+Reduction SelectLowering::Reduce(Node* node) {
+ if (node->opcode() != IrOpcode::kSelect) return NoChange();
+ SelectParameters const p = SelectParametersOf(node->op());
+
+ Node* const cond = node->InputAt(0);
+ Node* const control = graph()->start();
+
+ // Check if we already have a diamond for this condition.
+ auto i = merges_.find(cond);
+ if (i == merges_.end()) {
+ // Create a new diamond for this condition and remember its merge node.
+ Node* branch = graph()->NewNode(common()->Branch(p.hint()), cond,
control);
+ Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
+ Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
+ Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
+ i = merges_.insert(std::make_pair(cond, merge)).first;
+ }
+
+ DCHECK_EQ(cond, i->first);
+
+ // Create a Phi hanging off the previously determined merge.
+ node->set_op(common()->Phi(p.type(), 2));
+ node->ReplaceInput(0, node->InputAt(1));
+ node->ReplaceInput(1, node->InputAt(2));
+ node->ReplaceInput(2, i->second);
+ return Changed(node);
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/compiler/select-lowering.h Mon Nov 3
15:17:08 2014 UTC
@@ -0,0 +1,46 @@
+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef V8_COMPILER_SELECT_LOWERING_H_
+#define V8_COMPILER_SELECT_LOWERING_H_
+
+#include <map>
+
+#include "src/compiler/graph-reducer.h"
+#include "src/zone-allocator.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// Forward declarations.
+class CommonOperatorBuilder;
+class Graph;
+
+
+// Lowers Select nodes to diamonds.
+class SelectLowering FINAL : public Reducer {
+ public:
+ SelectLowering(Graph* graph, CommonOperatorBuilder* common);
+ ~SelectLowering();
+
+ Reduction Reduce(Node* node) OVERRIDE;
+
+ private:
+ typedef std::map<Node*, Node*, std::less<Node*>,
+ zone_allocator<std::pair<Node* const, Node*>>> Merges;
+
+ CommonOperatorBuilder* common() const { return common_; }
+ Graph* graph() const { return graph_; }
+
+ CommonOperatorBuilder* common_;
+ Graph* graph_;
+ Merges merges_;
+};
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
+
+#endif // V8_COMPILER_SELECT_LOWERING_H_
=======================================
--- /dev/null
+++
/branches/bleeding_edge/test/unittests/compiler/select-lowering-unittest.cc
Mon Nov 3 15:17:08 2014 UTC
@@ -0,0 +1,62 @@
+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/compiler/select-lowering.h"
+#include "test/unittests/compiler/graph-unittest.h"
+#include "test/unittests/compiler/node-test-utils.h"
+#include "testing/gmock-support.h"
+
+using testing::AllOf;
+using testing::Capture;
+using testing::CaptureEq;
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class SelectLoweringTest : public GraphTest {
+ public:
+ SelectLoweringTest() : GraphTest(5), lowering_(graph(), common()) {}
+
+ protected:
+ Reduction Reduce(Node* node) { return lowering_.Reduce(node); }
+
+ private:
+ SelectLowering lowering_;
+};
+
+
+TEST_F(SelectLoweringTest, SelectWithSameConditions) {
+ Node* const p0 = Parameter(0);
+ Node* const p1 = Parameter(1);
+ Node* const p2 = Parameter(2);
+ Node* const p3 = Parameter(3);
+ Node* const p4 = Parameter(4);
+
+ Capture<Node*> branch;
+ Capture<Node*> merge;
+ {
+ Reduction const r =
+ Reduce(graph()->NewNode(common()->Select(kMachInt32), p0, p1, p2));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(
+ r.replacement(),
+ IsPhi(
+ kMachInt32, p1, p2,
+ AllOf(CaptureEq(&merge),
+ IsMerge(IsIfTrue(CaptureEq(&branch)),
+ IsIfFalse(AllOf(CaptureEq(&branch),
+ IsBranch(p0,
graph()->start())))))));
+ }
+ {
+ Reduction const r =
+ Reduce(graph()->NewNode(common()->Select(kMachInt32), p0, p3, p4));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(), IsPhi(kMachInt32, p3, p4,
CaptureEq(&merge)));
+ }
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
=======================================
--- /branches/bleeding_edge/BUILD.gn Fri Oct 31 10:44:04 2014 UTC
+++ /branches/bleeding_edge/BUILD.gn Mon Nov 3 15:17:08 2014 UTC
@@ -576,6 +576,8 @@
"src/compiler/schedule.h",
"src/compiler/scheduler.cc",
"src/compiler/scheduler.h",
+ "src/compiler/select-lowering.cc",
+ "src/compiler/select-lowering.h",
"src/compiler/simplified-lowering.cc",
"src/compiler/simplified-lowering.h",
"src/compiler/simplified-operator-reducer.cc",
=======================================
--- /branches/bleeding_edge/src/compiler/js-generic-lowering.cc Mon Nov 3
10:21:59 2014 UTC
+++ /branches/bleeding_edge/src/compiler/js-generic-lowering.cc Mon Nov 3
15:17:08 2014 UTC
@@ -65,7 +65,6 @@
Lower##x(node); \
break;
DECLARE_CASE(Branch)
- DECLARE_CASE(Select)
JS_OP_LIST(DECLARE_CASE)
#undef DECLARE_CASE
default:
@@ -241,23 +240,6 @@
node->ReplaceInput(0, test);
}
}
-
-
-void JSGenericLowering::LowerSelect(Node* node) {
- // TODO(bmeurer): This should probably be moved into a separate file.
- SelectParameters const& p = SelectParametersOf(node->op());
- Node* branch = graph()->NewNode(common()->Branch(p.hint()),
node->InputAt(0),
- graph()->start());
- Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
- Node* vtrue = node->InputAt(1);
- Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
- Node* vfalse = node->InputAt(2);
- Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
- node->set_op(common()->Phi(p.type(), 2));
- node->ReplaceInput(0, vtrue);
- node->ReplaceInput(1, vfalse);
- node->ReplaceInput(2, merge);
-}
void JSGenericLowering::LowerJSUnaryNot(Node* node) {
=======================================
--- /branches/bleeding_edge/src/compiler/pipeline.cc Mon Nov 3 13:26:46
2014 UTC
+++ /branches/bleeding_edge/src/compiler/pipeline.cc Mon Nov 3 15:17:08
2014 UTC
@@ -26,6 +26,7 @@
#include "src/compiler/register-allocator.h"
#include "src/compiler/schedule.h"
#include "src/compiler/scheduler.h"
+#include "src/compiler/select-lowering.h"
#include "src/compiler/simplified-lowering.h"
#include "src/compiler/simplified-operator-reducer.h"
#include "src/compiler/typer.h"
@@ -450,9 +451,11 @@
PhaseScope phase_scope(pipeline_statistics.get(), "generic lowering");
SourcePositionTable::Scope pos(data.source_positions(),
SourcePosition::Unknown());
- JSGenericLowering lowering(info(), data.jsgraph());
+ JSGenericLowering generic(info(), data.jsgraph());
+ SelectLowering select(data.jsgraph()->graph(),
data.jsgraph()->common());
GraphReducer graph_reducer(data.graph());
- graph_reducer.AddReducer(&lowering);
+ graph_reducer.AddReducer(&generic);
+ graph_reducer.AddReducer(&select);
graph_reducer.ReduceGraph();
// TODO(jarin, rossberg): Remove UNTYPED once machine typing works.
=======================================
--- /branches/bleeding_edge/test/unittests/unittests.gyp Mon Nov 3
13:26:46 2014 UTC
+++ /branches/bleeding_edge/test/unittests/unittests.gyp Mon Nov 3
15:17:08 2014 UTC
@@ -52,6 +52,7 @@
'compiler/node-test-utils.cc',
'compiler/node-test-utils.h',
'compiler/register-allocator-unittest.cc',
+ 'compiler/select-lowering-unittest.cc',
'compiler/simplified-operator-reducer-unittest.cc',
'compiler/simplified-operator-unittest.cc',
'compiler/value-numbering-reducer-unittest.cc',
=======================================
--- /branches/bleeding_edge/tools/gyp/v8.gyp Fri Oct 31 10:44:04 2014 UTC
+++ /branches/bleeding_edge/tools/gyp/v8.gyp Mon Nov 3 15:17:08 2014 UTC
@@ -489,6 +489,8 @@
'../../src/compiler/schedule.h',
'../../src/compiler/scheduler.cc',
'../../src/compiler/scheduler.h',
+ '../../src/compiler/select-lowering.cc',
+ '../../src/compiler/select-lowering.h',
'../../src/compiler/simplified-lowering.cc',
'../../src/compiler/simplified-lowering.h',
'../../src/compiler/simplified-operator-reducer.cc',
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
