Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(93)

Unified Diff: src/compiler/control-flow-optimizer.cc

Issue 931623002: [turbofan] Optimize certain chains of Branch into a Switch. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Addrssed comments. Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/control-flow-optimizer.h ('k') | src/compiler/ia32/code-generator-ia32.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/control-flow-optimizer.cc
diff --git a/src/compiler/control-flow-optimizer.cc b/src/compiler/control-flow-optimizer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c75d09f0cef09f3edc8297c13ce3ef451abb98f5
--- /dev/null
+++ b/src/compiler/control-flow-optimizer.cc
@@ -0,0 +1,147 @@
+// Copyright 2015 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/control-flow-optimizer.h"
+
+#include "src/compiler/js-graph.h"
+#include "src/compiler/node-matchers.h"
+#include "src/compiler/node-properties.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+ControlFlowOptimizer::ControlFlowOptimizer(JSGraph* jsgraph, Zone* zone)
+ : jsgraph_(jsgraph),
+ queue_(zone),
+ queued_(jsgraph->graph(), 2),
+ zone_(zone) {}
+
+
+void ControlFlowOptimizer::Optimize() {
+ Enqueue(graph()->start());
+ while (!queue_.empty()) {
+ Node* node = queue_.front();
+ queue_.pop();
+ if (node->IsDead()) continue;
+ switch (node->opcode()) {
+ case IrOpcode::kBranch:
+ VisitBranch(node);
+ break;
+ default:
+ VisitNode(node);
+ break;
+ }
+ }
+}
+
+
+void ControlFlowOptimizer::Enqueue(Node* node) {
+ DCHECK_NOT_NULL(node);
+ if (node->IsDead() || queued_.Get(node)) return;
+ queued_.Set(node, true);
+ queue_.push(node);
+}
+
+
+void ControlFlowOptimizer::VisitNode(Node* node) {
+ for (Node* use : node->uses()) {
+ if (NodeProperties::IsControl(use)) Enqueue(use);
+ }
+}
+
+
+void ControlFlowOptimizer::VisitBranch(Node* node) {
+ DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+
+ Node* branch = node;
+ Node* cond = NodeProperties::GetValueInput(branch, 0);
+ if (cond->opcode() != IrOpcode::kWord32Equal) return VisitNode(node);
+ Int32BinopMatcher m(cond);
+ Node* index = m.left().node();
+ if (!m.right().HasValue()) return VisitNode(node);
+ int32_t value = m.right().Value();
+ ZoneSet<int32_t> values(zone());
+ values.insert(value);
+
+ Node* if_false;
+ Node* if_true;
+ while (true) {
+ // TODO(turbofan): use NodeProperties::CollectSuccessorProjections() here
+ // once available.
+ auto it = branch->uses().begin();
+ DCHECK(it != branch->uses().end());
+ if_true = *it++;
+ DCHECK(it != branch->uses().end());
+ if_false = *it++;
+ DCHECK(it == branch->uses().end());
+ if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
+ DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
+ DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
+
+ it = if_false->uses().begin();
+ if (it == if_false->uses().end()) break;
+ Node* branch1 = *it++;
+ if (branch1->opcode() != IrOpcode::kBranch) break;
+ if (it != if_false->uses().end()) break;
+ Node* cond1 = branch1->InputAt(0);
+ if (cond1->opcode() != IrOpcode::kWord32Equal) break;
+ Int32BinopMatcher m1(cond1);
+ if (m1.left().node() != index) break;
+ if (!m1.right().HasValue()) break;
+ int32_t value1 = m1.right().Value();
+ if (values.find(value1) != values.end()) break;
+ DCHECK_NE(value, value1);
+
+ if (branch != node) {
+ branch->RemoveAllInputs();
+ if_true->ReplaceInput(0, node);
+ }
+ if_true->set_op(common()->IfValue(value));
+ if_false->RemoveAllInputs();
+ Enqueue(if_true);
+
+ branch = branch1;
+ value = value1;
+ values.insert(value);
+ }
+
+ DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+ DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
+ DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
+ DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
+ if (branch == node) {
+ DCHECK_EQ(1u, values.size());
+ Enqueue(if_true);
+ Enqueue(if_false);
+ } else {
+ DCHECK_LT(1u, values.size());
+ node->set_op(common()->Switch(values.size() + 1));
+ node->ReplaceInput(0, index);
+ if_true->set_op(common()->IfValue(value));
+ if_true->ReplaceInput(0, node);
+ Enqueue(if_true);
+ if_false->set_op(common()->IfDefault());
+ if_false->ReplaceInput(0, node);
+ Enqueue(if_false);
+ branch->RemoveAllInputs();
+ }
+}
+
+
+CommonOperatorBuilder* ControlFlowOptimizer::common() const {
+ return jsgraph()->common();
+}
+
+
+Graph* ControlFlowOptimizer::graph() const { return jsgraph()->graph(); }
+
+
+MachineOperatorBuilder* ControlFlowOptimizer::machine() const {
+ return jsgraph()->machine();
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
« no previous file with comments | « src/compiler/control-flow-optimizer.h ('k') | src/compiler/ia32/code-generator-ia32.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698