Revision: 25236
Author: [email protected]
Date: Mon Nov 10 10:29:37 2014 UTC
Log: [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
[email protected]
Review URL: https://codereview.chromium.org/717473002
https://code.google.com/p/v8/source/detail?r=25236
Modified:
/branches/bleeding_edge/src/compiler/node.h
/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
=======================================
--- /branches/bleeding_edge/src/compiler/node.h Mon Oct 27 22:33:52 2014 UTC
+++ /branches/bleeding_edge/src/compiler/node.h Mon Nov 10 10:29:37 2014 UTC
@@ -68,6 +68,8 @@
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;
=======================================
--- /branches/bleeding_edge/src/compiler/select-lowering.cc Tue Nov 4
16:15:44 2014 UTC
+++ /branches/bleeding_edge/src/compiler/select-lowering.cc Mon Nov 10
10:29:37 2014 UTC
@@ -26,25 +26,57 @@
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;
+ }
+
+ // 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;
+ }
}
-
- 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);
+ node->ReplaceInput(0, vthen);
+ node->ReplaceInput(1, velse);
+ node->ReplaceInput(2, merge);
return Changed(node);
}
+
+
+bool SelectLowering::ReachableFrom(Node* const sink, Node* const source) {
+ // TODO(turbofan): This is probably horribly expensive, and it should be
moved
+ // into node.h or somewhere else?!
+ 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
=======================================
--- /branches/bleeding_edge/src/compiler/select-lowering.h Mon Nov 3
15:17:08 2014 UTC
+++ /branches/bleeding_edge/src/compiler/select-lowering.h Mon Nov 10
10:29:37 2014 UTC
@@ -28,8 +28,10 @@
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_; }
=======================================
---
/branches/bleeding_edge/test/unittests/compiler/select-lowering-unittest.cc
Mon Nov 3 15:17:08 2014 UTC
+++
/branches/bleeding_edge/test/unittests/compiler/select-lowering-unittest.cc
Mon Nov 10 10:29:37 2014 UTC
@@ -10,6 +10,7 @@
using testing::AllOf;
using testing::Capture;
using testing::CaptureEq;
+using testing::Not;
namespace v8 {
namespace internal {
@@ -33,12 +34,12 @@
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 @@
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.
