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
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
15
DeadCodeElimination(Editor * editor,Graph * graph,CommonOperatorBuilder * common)16 DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
17 CommonOperatorBuilder* common)
18 : AdvancedReducer(editor),
19 graph_(graph),
20 common_(common),
21 dead_(graph->NewNode(common->Dead())) {
22 NodeProperties::SetType(dead_, Type::None());
23 }
24
Reduce(Node * node)25 Reduction DeadCodeElimination::Reduce(Node* node) {
26 switch (node->opcode()) {
27 case IrOpcode::kEnd:
28 return ReduceEnd(node);
29 case IrOpcode::kLoop:
30 case IrOpcode::kMerge:
31 return ReduceLoopOrMerge(node);
32 case IrOpcode::kLoopExit:
33 return ReduceLoopExit(node);
34 default:
35 return ReduceNode(node);
36 }
37 UNREACHABLE();
38 return NoChange();
39 }
40
41
ReduceEnd(Node * node)42 Reduction DeadCodeElimination::ReduceEnd(Node* node) {
43 DCHECK_EQ(IrOpcode::kEnd, node->opcode());
44 Node::Inputs inputs = node->inputs();
45 DCHECK_LE(1, inputs.count());
46 int live_input_count = 0;
47 for (int i = 0; i < inputs.count(); ++i) {
48 Node* const input = inputs[i];
49 // Skip dead inputs.
50 if (input->opcode() == IrOpcode::kDead) continue;
51 // Compact live inputs.
52 if (i != live_input_count) node->ReplaceInput(live_input_count, input);
53 ++live_input_count;
54 }
55 if (live_input_count == 0) {
56 return Replace(dead());
57 } else if (live_input_count < inputs.count()) {
58 node->TrimInputCount(live_input_count);
59 NodeProperties::ChangeOp(node, common()->End(live_input_count));
60 return Changed(node);
61 }
62 DCHECK_EQ(inputs.count(), live_input_count);
63 return NoChange();
64 }
65
66
ReduceLoopOrMerge(Node * node)67 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
68 DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
69 Node::Inputs inputs = node->inputs();
70 DCHECK_LE(1, inputs.count());
71 // Count the number of live inputs to {node} and compact them on the fly, also
72 // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
73 // same time. We consider {Loop}s dead even if only the first control input
74 // is dead.
75 int live_input_count = 0;
76 if (node->opcode() != IrOpcode::kLoop ||
77 node->InputAt(0)->opcode() != IrOpcode::kDead) {
78 for (int i = 0; i < inputs.count(); ++i) {
79 Node* const input = inputs[i];
80 // Skip dead inputs.
81 if (input->opcode() == IrOpcode::kDead) continue;
82 // Compact live inputs.
83 if (live_input_count != i) {
84 node->ReplaceInput(live_input_count, input);
85 for (Node* const use : node->uses()) {
86 if (NodeProperties::IsPhi(use)) {
87 DCHECK_EQ(inputs.count() + 1, use->InputCount());
88 use->ReplaceInput(live_input_count, use->InputAt(i));
89 }
90 }
91 }
92 ++live_input_count;
93 }
94 }
95 if (live_input_count == 0) {
96 return Replace(dead());
97 } else if (live_input_count == 1) {
98 // Due to compaction above, the live input is at offset 0.
99 for (Node* const use : node->uses()) {
100 if (NodeProperties::IsPhi(use)) {
101 Replace(use, use->InputAt(0));
102 } else if (use->opcode() == IrOpcode::kLoopExit &&
103 use->InputAt(1) == node) {
104 RemoveLoopExit(use);
105 } else if (use->opcode() == IrOpcode::kTerminate) {
106 DCHECK_EQ(IrOpcode::kLoop, node->opcode());
107 Replace(use, dead());
108 }
109 }
110 return Replace(node->InputAt(0));
111 }
112 DCHECK_LE(2, live_input_count);
113 DCHECK_LE(live_input_count, inputs.count());
114 // Trim input count for the {Merge} or {Loop} node.
115 if (live_input_count < inputs.count()) {
116 // Trim input counts for all phi uses and revisit them.
117 for (Node* const use : node->uses()) {
118 if (NodeProperties::IsPhi(use)) {
119 use->ReplaceInput(live_input_count, node);
120 TrimMergeOrPhi(use, live_input_count);
121 Revisit(use);
122 }
123 }
124 TrimMergeOrPhi(node, live_input_count);
125 return Changed(node);
126 }
127 return NoChange();
128 }
129
RemoveLoopExit(Node * node)130 Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
131 DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
132 for (Node* const use : node->uses()) {
133 if (use->opcode() == IrOpcode::kLoopExitValue ||
134 use->opcode() == IrOpcode::kLoopExitEffect) {
135 Replace(use, use->InputAt(0));
136 }
137 }
138 Node* control = NodeProperties::GetControlInput(node, 0);
139 Replace(node, control);
140 return Replace(control);
141 }
142
ReduceNode(Node * node)143 Reduction DeadCodeElimination::ReduceNode(Node* node) {
144 // If {node} has exactly one control input and this is {Dead},
145 // replace {node} with {Dead}.
146 int const control_input_count = node->op()->ControlInputCount();
147 if (control_input_count == 0) return NoChange();
148 DCHECK_EQ(1, control_input_count);
149 Node* control = NodeProperties::GetControlInput(node);
150 if (control->opcode() == IrOpcode::kDead) return Replace(control);
151 return NoChange();
152 }
153
ReduceLoopExit(Node * node)154 Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
155 Node* control = NodeProperties::GetControlInput(node, 0);
156 Node* loop = NodeProperties::GetControlInput(node, 1);
157 if (control->opcode() == IrOpcode::kDead ||
158 loop->opcode() == IrOpcode::kDead) {
159 return RemoveLoopExit(node);
160 }
161 return NoChange();
162 }
163
TrimMergeOrPhi(Node * node,int size)164 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
165 const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
166 node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
167 NodeProperties::ChangeOp(node, op);
168 }
169
170 } // namespace compiler
171 } // namespace internal
172 } // namespace v8
173