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/js-operator.h"
10 #include "src/compiler/node-properties.h"
11 #include "src/compiler/operator-properties.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
DeadCodeElimination(Editor * editor,Graph * graph,CommonOperatorBuilder * common,Zone * temp_zone)17 DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
18 CommonOperatorBuilder* common,
19 Zone* temp_zone)
20 : AdvancedReducer(editor),
21 graph_(graph),
22 common_(common),
23 dead_(graph->NewNode(common->Dead())),
24 zone_(temp_zone) {
25 NodeProperties::SetType(dead_, Type::None());
26 }
27
28 namespace {
29
30 // True if we can guarantee that {node} will never actually produce a value or
31 // effect.
NoReturn(Node * node)32 bool NoReturn(Node* node) {
33 return node->opcode() == IrOpcode::kDead ||
34 node->opcode() == IrOpcode::kUnreachable ||
35 node->opcode() == IrOpcode::kDeadValue ||
36 NodeProperties::GetTypeOrAny(node).IsNone();
37 }
38
FindDeadInput(Node * node)39 Node* FindDeadInput(Node* node) {
40 for (Node* input : node->inputs()) {
41 if (NoReturn(input)) return input;
42 }
43 return nullptr;
44 }
45
46 } // namespace
47
Reduce(Node * node)48 Reduction DeadCodeElimination::Reduce(Node* node) {
49 DisallowHeapAccess no_heap_access;
50 switch (node->opcode()) {
51 case IrOpcode::kEnd:
52 return ReduceEnd(node);
53 case IrOpcode::kLoop:
54 case IrOpcode::kMerge:
55 return ReduceLoopOrMerge(node);
56 case IrOpcode::kLoopExit:
57 return ReduceLoopExit(node);
58 case IrOpcode::kUnreachable:
59 case IrOpcode::kIfException:
60 return ReduceUnreachableOrIfException(node);
61 case IrOpcode::kPhi:
62 return ReducePhi(node);
63 case IrOpcode::kEffectPhi:
64 return PropagateDeadControl(node);
65 case IrOpcode::kDeoptimize:
66 case IrOpcode::kReturn:
67 case IrOpcode::kTerminate:
68 return ReduceDeoptimizeOrReturnOrTerminate(node);
69 case IrOpcode::kThrow:
70 return PropagateDeadControl(node);
71 case IrOpcode::kBranch:
72 case IrOpcode::kSwitch:
73 return ReduceBranchOrSwitch(node);
74 default:
75 return ReduceNode(node);
76 }
77 UNREACHABLE();
78 }
79
PropagateDeadControl(Node * node)80 Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
81 DCHECK_EQ(1, node->op()->ControlInputCount());
82 Node* control = NodeProperties::GetControlInput(node);
83 if (control->opcode() == IrOpcode::kDead) return Replace(control);
84 return NoChange();
85 }
86
ReduceEnd(Node * node)87 Reduction DeadCodeElimination::ReduceEnd(Node* node) {
88 DCHECK_EQ(IrOpcode::kEnd, node->opcode());
89 Node::Inputs inputs = node->inputs();
90 DCHECK_LE(1, inputs.count());
91 int live_input_count = 0;
92 for (int i = 0; i < inputs.count(); ++i) {
93 Node* const input = inputs[i];
94 // Skip dead inputs.
95 if (input->opcode() == IrOpcode::kDead) continue;
96 // Compact live inputs.
97 if (i != live_input_count) node->ReplaceInput(live_input_count, input);
98 ++live_input_count;
99 }
100 if (live_input_count == 0) {
101 return Replace(dead());
102 } else if (live_input_count < inputs.count()) {
103 node->TrimInputCount(live_input_count);
104 NodeProperties::ChangeOp(node, common()->End(live_input_count));
105 return Changed(node);
106 }
107 DCHECK_EQ(inputs.count(), live_input_count);
108 return NoChange();
109 }
110
111
ReduceLoopOrMerge(Node * node)112 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
113 DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
114 Node::Inputs inputs = node->inputs();
115 DCHECK_LE(1, inputs.count());
116 // Count the number of live inputs to {node} and compact them on the fly, also
117 // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
118 // same time. We consider {Loop}s dead even if only the first control input
119 // is dead.
120 int live_input_count = 0;
121 if (node->opcode() != IrOpcode::kLoop ||
122 node->InputAt(0)->opcode() != IrOpcode::kDead) {
123 for (int i = 0; i < inputs.count(); ++i) {
124 Node* const input = inputs[i];
125 // Skip dead inputs.
126 if (input->opcode() == IrOpcode::kDead) continue;
127 // Compact live inputs.
128 if (live_input_count != i) {
129 node->ReplaceInput(live_input_count, input);
130 for (Node* const use : node->uses()) {
131 if (NodeProperties::IsPhi(use)) {
132 DCHECK_EQ(inputs.count() + 1, use->InputCount());
133 use->ReplaceInput(live_input_count, use->InputAt(i));
134 }
135 }
136 }
137 ++live_input_count;
138 }
139 }
140 if (live_input_count == 0) {
141 return Replace(dead());
142 } else if (live_input_count == 1) {
143 NodeVector loop_exits(zone_);
144 // Due to compaction above, the live input is at offset 0.
145 for (Node* const use : node->uses()) {
146 if (NodeProperties::IsPhi(use)) {
147 Replace(use, use->InputAt(0));
148 } else if (use->opcode() == IrOpcode::kLoopExit &&
149 use->InputAt(1) == node) {
150 // Remember the loop exits so that we can mark their loop input dead.
151 // This has to be done after the use list iteration so that we do
152 // not mutate the use list while it is being iterated.
153 loop_exits.push_back(use);
154 } else if (use->opcode() == IrOpcode::kTerminate) {
155 DCHECK_EQ(IrOpcode::kLoop, node->opcode());
156 Replace(use, dead());
157 }
158 }
159 for (Node* loop_exit : loop_exits) {
160 loop_exit->ReplaceInput(1, dead());
161 Revisit(loop_exit);
162 }
163 return Replace(node->InputAt(0));
164 }
165 DCHECK_LE(2, live_input_count);
166 DCHECK_LE(live_input_count, inputs.count());
167 // Trim input count for the {Merge} or {Loop} node.
168 if (live_input_count < inputs.count()) {
169 // Trim input counts for all phi uses and revisit them.
170 for (Node* const use : node->uses()) {
171 if (NodeProperties::IsPhi(use)) {
172 use->ReplaceInput(live_input_count, node);
173 TrimMergeOrPhi(use, live_input_count);
174 Revisit(use);
175 }
176 }
177 TrimMergeOrPhi(node, live_input_count);
178 return Changed(node);
179 }
180 return NoChange();
181 }
182
RemoveLoopExit(Node * node)183 Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
184 DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
185 for (Node* const use : node->uses()) {
186 if (use->opcode() == IrOpcode::kLoopExitValue ||
187 use->opcode() == IrOpcode::kLoopExitEffect) {
188 Replace(use, use->InputAt(0));
189 }
190 }
191 Node* control = NodeProperties::GetControlInput(node, 0);
192 Replace(node, control);
193 return Replace(control);
194 }
195
ReduceNode(Node * node)196 Reduction DeadCodeElimination::ReduceNode(Node* node) {
197 DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
198 int const effect_input_count = node->op()->EffectInputCount();
199 int const control_input_count = node->op()->ControlInputCount();
200 DCHECK_LE(control_input_count, 1);
201 if (control_input_count == 1) {
202 Reduction reduction = PropagateDeadControl(node);
203 if (reduction.Changed()) return reduction;
204 }
205 if (effect_input_count == 0 &&
206 (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
207 return ReducePureNode(node);
208 }
209 if (effect_input_count > 0) {
210 return ReduceEffectNode(node);
211 }
212 return NoChange();
213 }
214
ReducePhi(Node * node)215 Reduction DeadCodeElimination::ReducePhi(Node* node) {
216 DCHECK_EQ(IrOpcode::kPhi, node->opcode());
217 Reduction reduction = PropagateDeadControl(node);
218 if (reduction.Changed()) return reduction;
219 MachineRepresentation rep = PhiRepresentationOf(node->op());
220 if (rep == MachineRepresentation::kNone ||
221 NodeProperties::GetTypeOrAny(node).IsNone()) {
222 return Replace(DeadValue(node, rep));
223 }
224 int input_count = node->op()->ValueInputCount();
225 for (int i = 0; i < input_count; ++i) {
226 Node* input = NodeProperties::GetValueInput(node, i);
227 if (input->opcode() == IrOpcode::kDeadValue &&
228 DeadValueRepresentationOf(input->op()) != rep) {
229 NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
230 }
231 }
232 return NoChange();
233 }
234
ReducePureNode(Node * node)235 Reduction DeadCodeElimination::ReducePureNode(Node* node) {
236 DCHECK_EQ(0, node->op()->EffectInputCount());
237 if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
238 if (Node* input = FindDeadInput(node)) {
239 return Replace(DeadValue(input));
240 }
241 return NoChange();
242 }
243
ReduceUnreachableOrIfException(Node * node)244 Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
245 DCHECK(node->opcode() == IrOpcode::kUnreachable ||
246 node->opcode() == IrOpcode::kIfException);
247 Reduction reduction = PropagateDeadControl(node);
248 if (reduction.Changed()) return reduction;
249 Node* effect = NodeProperties::GetEffectInput(node, 0);
250 if (effect->opcode() == IrOpcode::kDead) {
251 return Replace(effect);
252 }
253 if (effect->opcode() == IrOpcode::kUnreachable) {
254 return Replace(effect);
255 }
256 return NoChange();
257 }
258
ReduceEffectNode(Node * node)259 Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
260 DCHECK_EQ(1, node->op()->EffectInputCount());
261 Node* effect = NodeProperties::GetEffectInput(node, 0);
262 if (effect->opcode() == IrOpcode::kDead) {
263 return Replace(effect);
264 }
265 if (Node* input = FindDeadInput(node)) {
266 if (effect->opcode() == IrOpcode::kUnreachable) {
267 RelaxEffectsAndControls(node);
268 return Replace(DeadValue(input));
269 }
270
271 Node* control = node->op()->ControlInputCount() == 1
272 ? NodeProperties::GetControlInput(node, 0)
273 : graph()->start();
274 Node* unreachable =
275 graph()->NewNode(common()->Unreachable(), effect, control);
276 NodeProperties::SetType(unreachable, Type::None());
277 ReplaceWithValue(node, DeadValue(input), node, control);
278 return Replace(unreachable);
279 }
280
281 return NoChange();
282 }
283
ReduceDeoptimizeOrReturnOrTerminate(Node * node)284 Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminate(Node* node) {
285 DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
286 node->opcode() == IrOpcode::kReturn ||
287 node->opcode() == IrOpcode::kTerminate);
288 Reduction reduction = PropagateDeadControl(node);
289 if (reduction.Changed()) return reduction;
290 if (FindDeadInput(node) != nullptr) {
291 Node* effect = NodeProperties::GetEffectInput(node, 0);
292 Node* control = NodeProperties::GetControlInput(node, 0);
293 if (effect->opcode() != IrOpcode::kUnreachable) {
294 effect = graph()->NewNode(common()->Unreachable(), effect, control);
295 NodeProperties::SetType(effect, Type::None());
296 }
297 node->TrimInputCount(2);
298 node->ReplaceInput(0, effect);
299 node->ReplaceInput(1, control);
300 NodeProperties::ChangeOp(node, common()->Throw());
301 return Changed(node);
302 }
303 return NoChange();
304 }
305
ReduceLoopExit(Node * node)306 Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
307 Node* control = NodeProperties::GetControlInput(node, 0);
308 Node* loop = NodeProperties::GetControlInput(node, 1);
309 if (control->opcode() == IrOpcode::kDead ||
310 loop->opcode() == IrOpcode::kDead) {
311 return RemoveLoopExit(node);
312 }
313 return NoChange();
314 }
315
ReduceBranchOrSwitch(Node * node)316 Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
317 DCHECK(node->opcode() == IrOpcode::kBranch ||
318 node->opcode() == IrOpcode::kSwitch);
319 Reduction reduction = PropagateDeadControl(node);
320 if (reduction.Changed()) return reduction;
321 Node* condition = NodeProperties::GetValueInput(node, 0);
322 if (condition->opcode() == IrOpcode::kDeadValue) {
323 // Branches or switches on {DeadValue} must originate from unreachable code
324 // and cannot matter. Due to schedule freedom between the effect and the
325 // control chain, they might still appear in reachable code. Remove them by
326 // always choosing the first projection.
327 size_t const projection_cnt = node->op()->ControlOutputCount();
328 Node** projections = zone_->NewArray<Node*>(projection_cnt);
329 NodeProperties::CollectControlProjections(node, projections,
330 projection_cnt);
331 Replace(projections[0], NodeProperties::GetControlInput(node));
332 return Replace(dead());
333 }
334 return NoChange();
335 }
336
TrimMergeOrPhi(Node * node,int size)337 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
338 const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
339 node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
340 NodeProperties::ChangeOp(node, op);
341 }
342
DeadValue(Node * node,MachineRepresentation rep)343 Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
344 if (node->opcode() == IrOpcode::kDeadValue) {
345 if (rep == DeadValueRepresentationOf(node->op())) return node;
346 node = NodeProperties::GetValueInput(node, 0);
347 }
348 Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
349 NodeProperties::SetType(dead_value, Type::None());
350 return dead_value;
351 }
352
353 } // namespace compiler
354 } // namespace internal
355 } // namespace v8
356