1// Copyright 2015 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/dead-code-elimination.h"
6
7#include "src/compiler/common-operator.h"
8#include "src/compiler/graph.h"
9#include "src/compiler/node-properties.h"
10#include "src/compiler/operator-properties.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
17                                         CommonOperatorBuilder* common)
18    : AdvancedReducer(editor),
19      graph_(graph),
20      common_(common),
21      dead_(graph->NewNode(common->Dead())) {}
22
23
24Reduction DeadCodeElimination::Reduce(Node* node) {
25  switch (node->opcode()) {
26    case IrOpcode::kEnd:
27      return ReduceEnd(node);
28    case IrOpcode::kLoop:
29    case IrOpcode::kMerge:
30      return ReduceLoopOrMerge(node);
31    default:
32      return ReduceNode(node);
33  }
34  UNREACHABLE();
35  return NoChange();
36}
37
38
39Reduction DeadCodeElimination::ReduceEnd(Node* node) {
40  DCHECK_EQ(IrOpcode::kEnd, node->opcode());
41  int const input_count = node->InputCount();
42  DCHECK_LE(1, input_count);
43  int live_input_count = 0;
44  for (int i = 0; i < input_count; ++i) {
45    Node* const input = node->InputAt(i);
46    // Skip dead inputs.
47    if (input->opcode() == IrOpcode::kDead) continue;
48    // Compact live inputs.
49    if (i != live_input_count) node->ReplaceInput(live_input_count, input);
50    ++live_input_count;
51  }
52  if (live_input_count == 0) {
53    return Replace(dead());
54  } else if (live_input_count < input_count) {
55    node->TrimInputCount(live_input_count);
56    NodeProperties::ChangeOp(node, common()->End(live_input_count));
57    return Changed(node);
58  }
59  DCHECK_EQ(input_count, live_input_count);
60  return NoChange();
61}
62
63
64Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
65  DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
66  int const input_count = node->InputCount();
67  DCHECK_LE(1, input_count);
68  // Count the number of live inputs to {node} and compact them on the fly, also
69  // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
70  // same time.  We consider {Loop}s dead even if only the first control input
71  // is dead.
72  int live_input_count = 0;
73  if (node->opcode() != IrOpcode::kLoop ||
74      node->InputAt(0)->opcode() != IrOpcode::kDead) {
75    for (int i = 0; i < input_count; ++i) {
76      Node* const input = node->InputAt(i);
77      // Skip dead inputs.
78      if (input->opcode() == IrOpcode::kDead) continue;
79      // Compact live inputs.
80      if (live_input_count != i) {
81        node->ReplaceInput(live_input_count, input);
82        for (Node* const use : node->uses()) {
83          if (NodeProperties::IsPhi(use)) {
84            DCHECK_EQ(input_count + 1, use->InputCount());
85            use->ReplaceInput(live_input_count, use->InputAt(i));
86          }
87        }
88      }
89      ++live_input_count;
90    }
91  }
92  if (live_input_count == 0) {
93    return Replace(dead());
94  } else if (live_input_count == 1) {
95    // Due to compaction above, the live input is at offset 0.
96    for (Node* const use : node->uses()) {
97      if (NodeProperties::IsPhi(use)) {
98        Replace(use, use->InputAt(0));
99      } else if (use->opcode() == IrOpcode::kTerminate) {
100        DCHECK_EQ(IrOpcode::kLoop, node->opcode());
101        Replace(use, dead());
102      }
103    }
104    return Replace(node->InputAt(0));
105  }
106  DCHECK_LE(2, live_input_count);
107  DCHECK_LE(live_input_count, input_count);
108  // Trim input count for the {Merge} or {Loop} node.
109  if (live_input_count < input_count) {
110    // Trim input counts for all phi uses and revisit them.
111    for (Node* const use : node->uses()) {
112      if (NodeProperties::IsPhi(use)) {
113        use->ReplaceInput(live_input_count, node);
114        TrimMergeOrPhi(use, live_input_count);
115        Revisit(use);
116      }
117    }
118    TrimMergeOrPhi(node, live_input_count);
119    return Changed(node);
120  }
121  return NoChange();
122}
123
124
125Reduction DeadCodeElimination::ReduceNode(Node* node) {
126  // If {node} has exactly one control input and this is {Dead},
127  // replace {node} with {Dead}.
128  int const control_input_count = node->op()->ControlInputCount();
129  if (control_input_count == 0) return NoChange();
130  DCHECK_EQ(1, control_input_count);
131  Node* control = NodeProperties::GetControlInput(node);
132  if (control->opcode() == IrOpcode::kDead) return Replace(control);
133  return NoChange();
134}
135
136
137void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
138  const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
139  node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
140  NodeProperties::ChangeOp(node, op);
141}
142
143}  // namespace compiler
144}  // namespace internal
145}  // namespace v8
146