| // 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; |
| if (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 |