// 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/common-operator.h" #include "src/compiler/graph.h" #include "src/compiler/node-matchers.h" #include "src/compiler/node-properties.h" namespace v8 { namespace internal { namespace compiler { ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph, CommonOperatorBuilder* common, MachineOperatorBuilder* machine, Zone* zone) : graph_(graph), common_(common), machine_(machine), queue_(zone), queued_(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 (Edge edge : node->use_edges()) { if (NodeProperties::IsControlEdge(edge)) { Enqueue(edge.from()); } } } void ControlFlowOptimizer::VisitBranch(Node* node) { DCHECK_EQ(IrOpcode::kBranch, node->opcode()); if (TryBuildSwitch(node)) return; if (TryCloneBranch(node)) return; VisitNode(node); } bool ControlFlowOptimizer::TryCloneBranch(Node* node) { DCHECK_EQ(IrOpcode::kBranch, node->opcode()); // This optimization is a special case of (super)block cloning. It takes an // input graph as shown below and clones the Branch node for every predecessor // to the Merge, essentially removing the Merge completely. This avoids // materializing the bit for the Phi and may offer potential for further // branch folding optimizations (i.e. because one or more inputs to the Phi is // a constant). Note that there may be more Phi nodes hanging off the Merge, // but we can only a certain subset of them currently (actually only Phi and // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control // input). // Control1 ... ControlN // ^ ^ // | | Cond1 ... CondN // +----+ +----+ ^ ^ // | | | | // | | +----+ | // Merge<--+ | +------------+ // ^ \|/ // | Phi // | | // Branch----+ // ^ // | // +-----+-----+ // | | // IfTrue IfFalse // ^ ^ // | | // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this: // Control1 Cond1 ... ControlN CondN // ^ ^ ^ ^ // \ / \ / // Branch ... Branch // ^ ^ // | | // +---+---+ +---+----+ // | | | | // IfTrue IfFalse ... IfTrue IfFalse // ^ ^ ^ ^ // | | | | // +--+ +-------------+ | // | | +--------------+ +--+ // | | | | // Merge Merge // ^ ^ // | | Node* branch = node; Node* cond = NodeProperties::GetValueInput(branch, 0); if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return false; Node* merge = NodeProperties::GetControlInput(branch); if (merge->opcode() != IrOpcode::kMerge || NodeProperties::GetControlInput(cond) != merge) { return false; } // Grab the IfTrue/IfFalse projections of the Branch. BranchMatcher matcher(branch); // Check/collect other Phi/EffectPhi nodes hanging off the Merge. NodeVector phis(zone()); for (Node* const use : merge->uses()) { if (use == branch || use == cond) continue; // We cannot currently deal with non-Phi/EffectPhi nodes hanging off the // Merge. Ideally, we would just clone the nodes (and everything that // depends on it to some distant join point), but that requires knowledge // about dominance/post-dominance. if (!NodeProperties::IsPhi(use)) return false; for (Edge edge : use->use_edges()) { // Right now we can only handle Phi/EffectPhi nodes whose uses are // directly control-dependend on either the IfTrue or the IfFalse // successor, because we know exactly how to update those uses. // TODO(turbofan): Generalize this to all Phi/EffectPhi nodes using // dominance/post-dominance on the sea of nodes. if (edge.from()->op()->ControlInputCount() != 1) return false; Node* control = NodeProperties::GetControlInput(edge.from()); if (NodeProperties::IsPhi(edge.from())) { control = NodeProperties::GetControlInput(control, edge.index()); } if (control != matcher.IfTrue() && control != matcher.IfFalse()) return false; } phis.push_back(use); } BranchHint const hint = BranchHintOf(branch->op()); int const input_count = merge->op()->ControlInputCount(); DCHECK_LE(1, input_count); Node** const inputs = zone()->NewArray<Node*>(2 * input_count); Node** const merge_true_inputs = &inputs[0]; Node** const merge_false_inputs = &inputs[input_count]; for (int index = 0; index < input_count; ++index) { Node* cond1 = NodeProperties::GetValueInput(cond, index); Node* control1 = NodeProperties::GetControlInput(merge, index); Node* branch1 = graph()->NewNode(common()->Branch(hint), cond1, control1); merge_true_inputs[index] = graph()->NewNode(common()->IfTrue(), branch1); merge_false_inputs[index] = graph()->NewNode(common()->IfFalse(), branch1); Enqueue(branch1); } Node* const merge_true = graph()->NewNode(common()->Merge(input_count), input_count, merge_true_inputs); Node* const merge_false = graph()->NewNode(common()->Merge(input_count), input_count, merge_false_inputs); for (Node* const phi : phis) { for (int index = 0; index < input_count; ++index) { inputs[index] = phi->InputAt(index); } inputs[input_count] = merge_true; Node* phi_true = graph()->NewNode(phi->op(), input_count + 1, inputs); inputs[input_count] = merge_false; Node* phi_false = graph()->NewNode(phi->op(), input_count + 1, inputs); for (Edge edge : phi->use_edges()) { Node* control = NodeProperties::GetControlInput(edge.from()); if (NodeProperties::IsPhi(edge.from())) { control = NodeProperties::GetControlInput(control, edge.index()); } DCHECK(control == matcher.IfTrue() || control == matcher.IfFalse()); edge.UpdateTo((control == matcher.IfTrue()) ? phi_true : phi_false); } phi->Kill(); } // Fix up IfTrue and IfFalse and kill all dead nodes. matcher.IfFalse()->ReplaceUses(merge_false); matcher.IfTrue()->ReplaceUses(merge_true); matcher.IfFalse()->Kill(); matcher.IfTrue()->Kill(); branch->Kill(); cond->Kill(); merge->Kill(); return true; } bool ControlFlowOptimizer::TryBuildSwitch(Node* node) { DCHECK_EQ(IrOpcode::kBranch, node->opcode()); Node* branch = node; if (BranchHintOf(branch->op()) != BranchHint::kNone) return false; Node* cond = NodeProperties::GetValueInput(branch, 0); if (cond->opcode() != IrOpcode::kWord32Equal) return false; Int32BinopMatcher m(cond); Node* index = m.left().node(); if (!m.right().HasValue()) return false; int32_t value = m.right().Value(); ZoneSet<int32_t> values(zone()); values.insert(value); Node* if_false; Node* if_true; while (true) { BranchMatcher matcher(branch); DCHECK(matcher.Matched()); if_true = matcher.IfTrue(); if_false = matcher.IfFalse(); auto it = if_false->uses().begin(); if (it == if_false->uses().end()) break; Node* branch1 = *it++; if (branch1->opcode() != IrOpcode::kBranch) break; if (BranchHintOf(branch1->op()) != BranchHint::kNone) 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->NullAllInputs(); if_true->ReplaceInput(0, node); } NodeProperties::ChangeOp(if_true, common()->IfValue(value)); if_false->NullAllInputs(); Enqueue(if_true); branch = branch1; value = value1; values.insert(value); } DCHECK_EQ(IrOpcode::kBranch, node->opcode()); DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); if (branch == node) { DCHECK_EQ(1u, values.size()); return false; } DCHECK_LT(1u, values.size()); node->ReplaceInput(0, index); NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1)); if_true->ReplaceInput(0, node); NodeProperties::ChangeOp(if_true, common()->IfValue(value)); Enqueue(if_true); if_false->ReplaceInput(0, node); NodeProperties::ChangeOp(if_false, common()->IfDefault()); Enqueue(if_false); branch->NullAllInputs(); return true; } } // namespace compiler } // namespace internal } // namespace v8