blob: bab6b7b506e368b7b4219015cc34a84b156ccd2d [file] [log] [blame]
// 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/dead-code-elimination.h"
#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
#include "src/compiler/js-operator.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/operator-properties.h"
namespace v8 {
namespace internal {
namespace compiler {
DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
CommonOperatorBuilder* common,
Zone* temp_zone)
: AdvancedReducer(editor),
graph_(graph),
common_(common),
dead_(graph->NewNode(common->Dead())),
zone_(temp_zone) {
NodeProperties::SetType(dead_, Type::None());
}
namespace {
// True if we can guarantee that {node} will never actually produce a value or
// effect.
bool NoReturn(Node* node) {
return node->opcode() == IrOpcode::kDead ||
node->opcode() == IrOpcode::kUnreachable ||
node->opcode() == IrOpcode::kDeadValue ||
NodeProperties::GetTypeOrAny(node).IsNone();
}
Node* FindDeadInput(Node* node) {
for (Node* input : node->inputs()) {
if (NoReturn(input)) return input;
}
return nullptr;
}
} // namespace
Reduction DeadCodeElimination::Reduce(Node* node) {
DisallowHeapAccess no_heap_access;
switch (node->opcode()) {
case IrOpcode::kEnd:
return ReduceEnd(node);
case IrOpcode::kLoop:
case IrOpcode::kMerge:
return ReduceLoopOrMerge(node);
case IrOpcode::kLoopExit:
return ReduceLoopExit(node);
case IrOpcode::kUnreachable:
case IrOpcode::kIfException:
return ReduceUnreachableOrIfException(node);
case IrOpcode::kPhi:
return ReducePhi(node);
case IrOpcode::kEffectPhi:
return ReduceEffectPhi(node);
case IrOpcode::kDeoptimize:
case IrOpcode::kReturn:
case IrOpcode::kTerminate:
case IrOpcode::kTailCall:
return ReduceDeoptimizeOrReturnOrTerminateOrTailCall(node);
case IrOpcode::kThrow:
return PropagateDeadControl(node);
case IrOpcode::kBranch:
case IrOpcode::kSwitch:
return ReduceBranchOrSwitch(node);
default:
return ReduceNode(node);
}
UNREACHABLE();
}
Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
DCHECK_EQ(1, node->op()->ControlInputCount());
Node* control = NodeProperties::GetControlInput(node);
if (control->opcode() == IrOpcode::kDead) return Replace(control);
return NoChange();
}
Reduction DeadCodeElimination::ReduceEnd(Node* node) {
DCHECK_EQ(IrOpcode::kEnd, node->opcode());
Node::Inputs inputs = node->inputs();
DCHECK_LE(1, inputs.count());
int live_input_count = 0;
for (int i = 0; i < inputs.count(); ++i) {
Node* const input = inputs[i];
// Skip dead inputs.
if (input->opcode() == IrOpcode::kDead) continue;
// Compact live inputs.
if (i != live_input_count) node->ReplaceInput(live_input_count, input);
++live_input_count;
}
if (live_input_count == 0) {
return Replace(dead());
} else if (live_input_count < inputs.count()) {
node->TrimInputCount(live_input_count);
NodeProperties::ChangeOp(node, common()->End(live_input_count));
return Changed(node);
}
DCHECK_EQ(inputs.count(), live_input_count);
return NoChange();
}
Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
Node::Inputs inputs = node->inputs();
DCHECK_LE(1, inputs.count());
// Count the number of live inputs to {node} and compact them on the fly, also
// compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
// same time. We consider {Loop}s dead even if only the first control input
// is dead.
int live_input_count = 0;
if (node->opcode() != IrOpcode::kLoop ||
node->InputAt(0)->opcode() != IrOpcode::kDead) {
for (int i = 0; i < inputs.count(); ++i) {
Node* const input = inputs[i];
// Skip dead inputs.
if (input->opcode() == IrOpcode::kDead) continue;
// Compact live inputs.
if (live_input_count != i) {
node->ReplaceInput(live_input_count, input);
for (Node* const use : node->uses()) {
if (NodeProperties::IsPhi(use)) {
DCHECK_EQ(inputs.count() + 1, use->InputCount());
use->ReplaceInput(live_input_count, use->InputAt(i));
}
}
}
++live_input_count;
}
}
if (live_input_count == 0) {
return Replace(dead());
} else if (live_input_count == 1) {
NodeVector loop_exits(zone_);
// Due to compaction above, the live input is at offset 0.
for (Node* const use : node->uses()) {
if (NodeProperties::IsPhi(use)) {
Replace(use, use->InputAt(0));
} else if (use->opcode() == IrOpcode::kLoopExit &&
use->InputAt(1) == node) {
// Remember the loop exits so that we can mark their loop input dead.
// This has to be done after the use list iteration so that we do
// not mutate the use list while it is being iterated.
loop_exits.push_back(use);
} else if (use->opcode() == IrOpcode::kTerminate) {
DCHECK_EQ(IrOpcode::kLoop, node->opcode());
Replace(use, dead());
}
}
for (Node* loop_exit : loop_exits) {
loop_exit->ReplaceInput(1, dead());
Revisit(loop_exit);
}
return Replace(node->InputAt(0));
}
DCHECK_LE(2, live_input_count);
DCHECK_LE(live_input_count, inputs.count());
// Trim input count for the {Merge} or {Loop} node.
if (live_input_count < inputs.count()) {
// Trim input counts for all phi uses and revisit them.
for (Node* const use : node->uses()) {
if (NodeProperties::IsPhi(use)) {
use->ReplaceInput(live_input_count, node);
TrimMergeOrPhi(use, live_input_count);
Revisit(use);
}
}
TrimMergeOrPhi(node, live_input_count);
return Changed(node);
}
return NoChange();
}
Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
for (Node* const use : node->uses()) {
if (use->opcode() == IrOpcode::kLoopExitValue ||
use->opcode() == IrOpcode::kLoopExitEffect) {
Replace(use, use->InputAt(0));
}
}
Node* control = NodeProperties::GetControlInput(node, 0);
Replace(node, control);
return Replace(control);
}
Reduction DeadCodeElimination::ReduceNode(Node* node) {
DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
int const effect_input_count = node->op()->EffectInputCount();
int const control_input_count = node->op()->ControlInputCount();
DCHECK_LE(control_input_count, 1);
if (control_input_count == 1) {
Reduction reduction = PropagateDeadControl(node);
if (reduction.Changed()) return reduction;
}
if (effect_input_count == 0 &&
(control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
return ReducePureNode(node);
}
if (effect_input_count > 0) {
return ReduceEffectNode(node);
}
return NoChange();
}
Reduction DeadCodeElimination::ReducePhi(Node* node) {
DCHECK_EQ(IrOpcode::kPhi, node->opcode());
Reduction reduction = PropagateDeadControl(node);
if (reduction.Changed()) return reduction;
MachineRepresentation rep = PhiRepresentationOf(node->op());
if (rep == MachineRepresentation::kNone ||
NodeProperties::GetTypeOrAny(node).IsNone()) {
return Replace(DeadValue(node, rep));
}
int input_count = node->op()->ValueInputCount();
for (int i = 0; i < input_count; ++i) {
Node* input = NodeProperties::GetValueInput(node, i);
if (input->opcode() == IrOpcode::kDeadValue &&
DeadValueRepresentationOf(input->op()) != rep) {
NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
}
}
return NoChange();
}
Reduction DeadCodeElimination::ReduceEffectPhi(Node* node) {
DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
Reduction reduction = PropagateDeadControl(node);
if (reduction.Changed()) return reduction;
Node* merge = NodeProperties::GetControlInput(node);
DCHECK(merge->opcode() == IrOpcode::kMerge ||
merge->opcode() == IrOpcode::kLoop);
int input_count = node->op()->EffectInputCount();
for (int i = 0; i < input_count; ++i) {
Node* effect = NodeProperties::GetEffectInput(node, i);
if (effect->opcode() == IrOpcode::kUnreachable) {
// If Unreachable hits an effect phi, we can re-connect the effect chain
// to the graph end and delete the corresponding inputs from the merge and
// phi nodes.
Node* control = NodeProperties::GetControlInput(merge, i);
Node* throw_node = graph_->NewNode(common_->Throw(), effect, control);
NodeProperties::MergeControlToEnd(graph_, common_, throw_node);
NodeProperties::ReplaceEffectInput(node, dead_, i);
NodeProperties::ReplaceControlInput(merge, dead_, i);
Revisit(merge);
Revisit(graph_->end());
reduction = Changed(node);
}
}
return reduction;
}
Reduction DeadCodeElimination::ReducePureNode(Node* node) {
DCHECK_EQ(0, node->op()->EffectInputCount());
if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
if (Node* input = FindDeadInput(node)) {
return Replace(DeadValue(input));
}
return NoChange();
}
Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
DCHECK(node->opcode() == IrOpcode::kUnreachable ||
node->opcode() == IrOpcode::kIfException);
Reduction reduction = PropagateDeadControl(node);
if (reduction.Changed()) return reduction;
Node* effect = NodeProperties::GetEffectInput(node, 0);
if (effect->opcode() == IrOpcode::kDead) {
return Replace(effect);
}
if (effect->opcode() == IrOpcode::kUnreachable) {
return Replace(effect);
}
return NoChange();
}
Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
DCHECK_EQ(1, node->op()->EffectInputCount());
Node* effect = NodeProperties::GetEffectInput(node, 0);
if (effect->opcode() == IrOpcode::kDead) {
return Replace(effect);
}
if (Node* input = FindDeadInput(node)) {
if (effect->opcode() == IrOpcode::kUnreachable) {
RelaxEffectsAndControls(node);
return Replace(DeadValue(input));
}
Node* control = node->op()->ControlInputCount() == 1
? NodeProperties::GetControlInput(node, 0)
: graph()->start();
Node* unreachable =
graph()->NewNode(common()->Unreachable(), effect, control);
NodeProperties::SetType(unreachable, Type::None());
ReplaceWithValue(node, DeadValue(input), node, control);
return Replace(unreachable);
}
return NoChange();
}
Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
Node* node) {
DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
node->opcode() == IrOpcode::kReturn ||
node->opcode() == IrOpcode::kTerminate ||
node->opcode() == IrOpcode::kTailCall);
Reduction reduction = PropagateDeadControl(node);
if (reduction.Changed()) return reduction;
// Terminate nodes are not part of actual control flow, so they should never
// be replaced with Throw.
if (node->opcode() != IrOpcode::kTerminate &&
FindDeadInput(node) != nullptr) {
Node* effect = NodeProperties::GetEffectInput(node, 0);
Node* control = NodeProperties::GetControlInput(node, 0);
if (effect->opcode() != IrOpcode::kUnreachable) {
effect = graph()->NewNode(common()->Unreachable(), effect, control);
NodeProperties::SetType(effect, Type::None());
}
node->TrimInputCount(2);
node->ReplaceInput(0, effect);
node->ReplaceInput(1, control);
NodeProperties::ChangeOp(node, common()->Throw());
return Changed(node);
}
return NoChange();
}
Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
Node* control = NodeProperties::GetControlInput(node, 0);
Node* loop = NodeProperties::GetControlInput(node, 1);
if (control->opcode() == IrOpcode::kDead ||
loop->opcode() == IrOpcode::kDead) {
return RemoveLoopExit(node);
}
return NoChange();
}
Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
DCHECK(node->opcode() == IrOpcode::kBranch ||
node->opcode() == IrOpcode::kSwitch);
Reduction reduction = PropagateDeadControl(node);
if (reduction.Changed()) return reduction;
Node* condition = NodeProperties::GetValueInput(node, 0);
if (condition->opcode() == IrOpcode::kDeadValue) {
// Branches or switches on {DeadValue} must originate from unreachable code
// and cannot matter. Due to schedule freedom between the effect and the
// control chain, they might still appear in reachable code. Remove them by
// always choosing the first projection.
size_t const projection_cnt = node->op()->ControlOutputCount();
Node** projections = zone_->NewArray<Node*>(projection_cnt);
NodeProperties::CollectControlProjections(node, projections,
projection_cnt);
Replace(projections[0], NodeProperties::GetControlInput(node));
return Replace(dead());
}
return NoChange();
}
void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
NodeProperties::ChangeOp(node, op);
}
Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
if (node->opcode() == IrOpcode::kDeadValue) {
if (rep == DeadValueRepresentationOf(node->op())) return node;
node = NodeProperties::GetValueInput(node, 0);
}
Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
NodeProperties::SetType(dead_value, Type::None());
return dead_value;
}
} // namespace compiler
} // namespace internal
} // namespace v8