Reviewers: jarin,
Message:
PTAL
Description:
[turbofan] Fix select lowering.
Select lowering must not merge Select nodes that depend on each other,
because the resulting graph is not schedulable.
TEST=unittests
Please review this at https://codereview.chromium.org/717473002/
Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+59, -15 lines):
M src/compiler/node.h
M src/compiler/select-lowering.h
M src/compiler/select-lowering.cc
M test/unittests/compiler/select-lowering-unittest.cc
Index: src/compiler/node.h
diff --git a/src/compiler/node.h b/src/compiler/node.h
index
3a5afd25dad800d070a901eecce8ca2591b0c7e8..8a442cedbc7aed407eda1e7f88d6388df58cdba3
100644
--- a/src/compiler/node.h
+++ b/src/compiler/node.h
@@ -68,6 +68,8 @@ typedef std::set<Node*, std::less<Node*>,
zone_allocator<Node*> > NodeSet;
typedef NodeSet::iterator NodeSetIter;
typedef NodeSet::reverse_iterator NodeSetRIter;
+typedef ZoneDeque<Node*> NodeDeque;
+
typedef ZoneVector<Node*> NodeVector;
typedef NodeVector::iterator NodeVectorIter;
typedef NodeVector::const_iterator NodeVectorConstIter;
Index: src/compiler/select-lowering.cc
diff --git a/src/compiler/select-lowering.cc
b/src/compiler/select-lowering.cc
index
2e51d72024bb8f96e3f82850352b132c682209bd..f1decd9ba27fff3b3870789f09f1e0ca34614366
100644
--- a/src/compiler/select-lowering.cc
+++ b/src/compiler/select-lowering.cc
@@ -26,26 +26,56 @@ 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* cond = node->InputAt(0);
+ Node* vthen = node->InputAt(1);
+ Node* velse = node->InputAt(2);
+ Node* merge = nullptr;
// 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.
- Diamond d(graph(), common(), cond, p.hint());
- i = merges_.insert(std::make_pair(cond, d.merge)).first;
- }
+ auto range = merges_.equal_range(cond);
+ for (auto i = range.first;; ++i) {
+ if (i == range.second) {
+ // Create a new diamond for this condition and remember its merge
node.
+ Diamond d(graph(), common(), cond, p.hint());
+ merges_.insert(std::make_pair(cond, d.merge));
+ merge = d.merge;
+ break;
+ }
- DCHECK_EQ(cond, i->first);
+ // If the diamond is reachable from the Select, merging them would
result in
+ // an unschedulable graph, so we cannot reuse the diamond in that case.
+ merge = i->second;
+ if (!ReachableFrom(merge, node)) {
+ break;
+ }
+ }
// 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);
+ node->ReplaceInput(0, vthen);
+ node->ReplaceInput(1, velse);
+ node->ReplaceInput(2, merge);
return Changed(node);
}
+
+bool SelectLowering::ReachableFrom(Node* const sink, Node* const source) {
+ Zone zone(graph()->zone()->isolate());
+ std::queue<Node*, NodeDeque> pending((NodeDeque(&zone)));
+ BoolVector visited(graph()->NodeCount(), false, &zone);
+ pending.push(source);
+ while (!pending.empty()) {
+ Node* current = pending.front();
+ if (current == sink) return true;
+ pending.pop();
+ visited[current->id()] = true;
+ for (auto input : current->inputs()) {
+ if (!visited[input->id()]) pending.push(input);
+ }
+ }
+ return false;
+}
+
} // namespace compiler
} // namespace internal
} // namespace v8
Index: src/compiler/select-lowering.h
diff --git a/src/compiler/select-lowering.h b/src/compiler/select-lowering.h
index
ae22cade84420584cd21bb41140b343c51213c33..05ea0e0c75869c8063362cef35276fbb70491daf
100644
--- a/src/compiler/select-lowering.h
+++ b/src/compiler/select-lowering.h
@@ -28,8 +28,10 @@ class SelectLowering FINAL : public Reducer {
Reduction Reduce(Node* node) OVERRIDE;
private:
- typedef std::map<Node*, Node*, std::less<Node*>,
- zone_allocator<std::pair<Node* const, Node*>>> Merges;
+ typedef std::multimap<Node*, Node*, std::less<Node*>,
+ zone_allocator<std::pair<Node* const, Node*>>>
Merges;
+
+ bool ReachableFrom(Node* const sink, Node* const source);
CommonOperatorBuilder* common() const { return common_; }
Graph* graph() const { return graph_; }
Index: test/unittests/compiler/select-lowering-unittest.cc
diff --git a/test/unittests/compiler/select-lowering-unittest.cc
b/test/unittests/compiler/select-lowering-unittest.cc
index
6dbd7ad73d99608931c8a6d06c1781b656b38bd3..51efc83f87c2eb15d4d8f6edfe3ac3a7ef77a34b
100644
--- a/test/unittests/compiler/select-lowering-unittest.cc
+++ b/test/unittests/compiler/select-lowering-unittest.cc
@@ -10,6 +10,7 @@
using testing::AllOf;
using testing::Capture;
using testing::CaptureEq;
+using testing::Not;
namespace v8 {
namespace internal {
@@ -33,12 +34,12 @@ TEST_F(SelectLoweringTest, SelectWithSameConditions) {
Node* const p2 = Parameter(2);
Node* const p3 = Parameter(3);
Node* const p4 = Parameter(4);
+ Node* const s0 = graph()->NewNode(common()->Select(kMachInt32), p0, p1,
p2);
Capture<Node*> branch;
Capture<Node*> merge;
{
- Reduction const r =
- Reduce(graph()->NewNode(common()->Select(kMachInt32), p0, p1, p2));
+ Reduction const r = Reduce(s0);
ASSERT_TRUE(r.Changed());
EXPECT_THAT(
r.replacement(),
@@ -55,6 +56,15 @@ TEST_F(SelectLoweringTest, SelectWithSameConditions) {
ASSERT_TRUE(r.Changed());
EXPECT_THAT(r.replacement(), IsPhi(kMachInt32, p3, p4,
CaptureEq(&merge)));
}
+ {
+ // We must not reuse the diamond if it is reachable from either
else/then
+ // values of the Select, because the resulting graph can not be
scheduled.
+ Reduction const r =
+ Reduce(graph()->NewNode(common()->Select(kMachInt32), p0, s0, p0));
+ ASSERT_TRUE(r.Changed());
+ EXPECT_THAT(r.replacement(),
+ IsPhi(kMachInt32, s0, p0, Not(CaptureEq(&merge))));
+ }
}
} // namespace compiler
--
--
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.
