// 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/branch-elimination.h"
|
|
#include "src/compiler/js-graph.h"
|
#include "src/compiler/node-properties.h"
|
#include "src/compiler/simplified-operator.h"
|
|
namespace v8 {
|
namespace internal {
|
namespace compiler {
|
|
BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
|
Zone* zone)
|
: AdvancedReducer(editor),
|
jsgraph_(js_graph),
|
node_conditions_(js_graph->graph()->NodeCount(), zone),
|
reduced_(js_graph->graph()->NodeCount(), zone),
|
zone_(zone),
|
dead_(js_graph->Dead()) {}
|
|
BranchElimination::~BranchElimination() {}
|
|
|
Reduction BranchElimination::Reduce(Node* node) {
|
switch (node->opcode()) {
|
case IrOpcode::kDead:
|
return NoChange();
|
case IrOpcode::kDeoptimizeIf:
|
case IrOpcode::kDeoptimizeUnless:
|
return ReduceDeoptimizeConditional(node);
|
case IrOpcode::kMerge:
|
return ReduceMerge(node);
|
case IrOpcode::kLoop:
|
return ReduceLoop(node);
|
case IrOpcode::kBranch:
|
return ReduceBranch(node);
|
case IrOpcode::kIfFalse:
|
return ReduceIf(node, false);
|
case IrOpcode::kIfTrue:
|
return ReduceIf(node, true);
|
case IrOpcode::kStart:
|
return ReduceStart(node);
|
default:
|
if (node->op()->ControlOutputCount() > 0) {
|
return ReduceOtherControl(node);
|
}
|
break;
|
}
|
return NoChange();
|
}
|
|
|
Reduction BranchElimination::ReduceBranch(Node* node) {
|
Node* condition = node->InputAt(0);
|
Node* control_input = NodeProperties::GetControlInput(node, 0);
|
ControlPathConditions from_input = node_conditions_.Get(control_input);
|
Node* branch;
|
bool condition_value;
|
// If we know the condition we can discard the branch.
|
if (from_input.LookupCondition(condition, &branch, &condition_value)) {
|
// Mark the branch as a safety check if necessary.
|
// Check if {branch} is dead because we might have a stale side-table entry.
|
if (!branch->IsDead()) {
|
IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
|
IsSafetyCheck combined_safety =
|
CombineSafetyChecks(branch_safety, IsSafetyCheckOf(node->op()));
|
if (branch_safety != combined_safety) {
|
NodeProperties::ChangeOp(
|
branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
|
}
|
}
|
|
for (Node* const use : node->uses()) {
|
switch (use->opcode()) {
|
case IrOpcode::kIfTrue:
|
Replace(use, condition_value ? control_input : dead());
|
break;
|
case IrOpcode::kIfFalse:
|
Replace(use, condition_value ? dead() : control_input);
|
break;
|
default:
|
UNREACHABLE();
|
}
|
}
|
return Replace(dead());
|
}
|
return TakeConditionsFromFirstControl(node);
|
}
|
|
Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
|
DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
|
node->opcode() == IrOpcode::kDeoptimizeUnless);
|
bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
|
DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
|
Node* condition = NodeProperties::GetValueInput(node, 0);
|
Node* frame_state = NodeProperties::GetValueInput(node, 1);
|
Node* effect = NodeProperties::GetEffectInput(node);
|
Node* control = NodeProperties::GetControlInput(node);
|
// If we do not know anything about the predecessor, do not propagate just
|
// yet because we will have to recompute anyway once we compute the
|
// predecessor.
|
if (!reduced_.Get(control)) {
|
return NoChange();
|
}
|
|
ControlPathConditions conditions = node_conditions_.Get(control);
|
bool condition_value;
|
Node* branch;
|
if (conditions.LookupCondition(condition, &branch, &condition_value)) {
|
// Mark the branch as a safety check.
|
IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
|
IsSafetyCheck combined_safety =
|
CombineSafetyChecks(branch_safety, p.is_safety_check());
|
if (branch_safety != combined_safety) {
|
NodeProperties::ChangeOp(
|
branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
|
}
|
|
// If we know the condition we can discard the branch.
|
if (condition_is_true == condition_value) {
|
// We don't update the conditions here, because we're replacing {node}
|
// with the {control} node that already contains the right information.
|
ReplaceWithValue(node, dead(), effect, control);
|
} else {
|
control = graph()->NewNode(
|
common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
|
effect, control);
|
// TODO(bmeurer): This should be on the AdvancedReducer somehow.
|
NodeProperties::MergeControlToEnd(graph(), common(), control);
|
Revisit(graph()->end());
|
}
|
return Replace(dead());
|
}
|
return UpdateConditions(node, conditions, condition, node, condition_is_true);
|
}
|
|
Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
|
// Add the condition to the list arriving from the input branch.
|
Node* branch = NodeProperties::GetControlInput(node, 0);
|
ControlPathConditions from_branch = node_conditions_.Get(branch);
|
// If we do not know anything about the predecessor, do not propagate just
|
// yet because we will have to recompute anyway once we compute the
|
// predecessor.
|
if (!reduced_.Get(branch)) {
|
return NoChange();
|
}
|
Node* condition = branch->InputAt(0);
|
return UpdateConditions(node, from_branch, condition, branch, is_true_branch);
|
}
|
|
|
Reduction BranchElimination::ReduceLoop(Node* node) {
|
// Here we rely on having only reducible loops:
|
// The loop entry edge always dominates the header, so we can just use
|
// the information from the loop entry edge.
|
return TakeConditionsFromFirstControl(node);
|
}
|
|
|
Reduction BranchElimination::ReduceMerge(Node* node) {
|
// Shortcut for the case when we do not know anything about some
|
// input.
|
Node::Inputs inputs = node->inputs();
|
for (Node* input : inputs) {
|
if (!reduced_.Get(input)) {
|
return NoChange();
|
}
|
}
|
|
auto input_it = inputs.begin();
|
|
DCHECK_GT(inputs.count(), 0);
|
|
ControlPathConditions conditions = node_conditions_.Get(*input_it);
|
++input_it;
|
// Merge the first input's conditions with the conditions from the other
|
// inputs.
|
auto input_end = inputs.end();
|
for (; input_it != input_end; ++input_it) {
|
// Change the current condition list to a longest common tail
|
// of this condition list and the other list. (The common tail
|
// should correspond to the list from the common dominator.)
|
conditions.ResetToCommonAncestor(node_conditions_.Get(*input_it));
|
}
|
return UpdateConditions(node, conditions);
|
}
|
|
|
Reduction BranchElimination::ReduceStart(Node* node) {
|
return UpdateConditions(node, {});
|
}
|
|
|
Reduction BranchElimination::ReduceOtherControl(Node* node) {
|
DCHECK_EQ(1, node->op()->ControlInputCount());
|
return TakeConditionsFromFirstControl(node);
|
}
|
|
|
Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
|
// We just propagate the information from the control input (ideally,
|
// we would only revisit control uses if there is change).
|
Node* input = NodeProperties::GetControlInput(node, 0);
|
if (!reduced_.Get(input)) return NoChange();
|
return UpdateConditions(node, node_conditions_.Get(input));
|
}
|
|
Reduction BranchElimination::UpdateConditions(
|
Node* node, ControlPathConditions conditions) {
|
// Only signal that the node has Changed if the condition information has
|
// changed.
|
if (reduced_.Set(node, true) | node_conditions_.Set(node, conditions)) {
|
return Changed(node);
|
}
|
return NoChange();
|
}
|
|
Reduction BranchElimination::UpdateConditions(
|
Node* node, ControlPathConditions prev_conditions, Node* current_condition,
|
Node* current_branch, bool is_true_branch) {
|
ControlPathConditions original = node_conditions_.Get(node);
|
// The control path for the node is the path obtained by appending the
|
// current_condition to the prev_conditions. Use the original control path as
|
// a hint to avoid allocations.
|
prev_conditions.AddCondition(zone_, current_condition, current_branch,
|
is_true_branch, original);
|
return UpdateConditions(node, prev_conditions);
|
}
|
|
void BranchElimination::ControlPathConditions::AddCondition(
|
Zone* zone, Node* condition, Node* branch, bool is_true,
|
ControlPathConditions hint) {
|
DCHECK_EQ(false, LookupCondition(condition, nullptr, nullptr));
|
PushFront({condition, branch, is_true}, zone, hint);
|
}
|
|
bool BranchElimination::ControlPathConditions::LookupCondition(
|
Node* condition, Node** branch, bool* is_true) const {
|
for (BranchCondition element : *this) {
|
if (element.condition == condition) {
|
*is_true = element.is_true;
|
*branch = element.branch;
|
return true;
|
}
|
}
|
return false;
|
}
|
|
Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
|
|
Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }
|
|
CommonOperatorBuilder* BranchElimination::common() const {
|
return jsgraph()->common();
|
}
|
|
} // namespace compiler
|
} // namespace internal
|
} // namespace v8
|
