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 switch (node->opcode()) {
50 case IrOpcode::kEnd:
51 return ReduceEnd(node);
52 case IrOpcode::kLoop:
53 case IrOpcode::kMerge:
54 return ReduceLoopOrMerge(node);
55 case IrOpcode::kLoopExit:
56 return ReduceLoopExit(node);
57 case IrOpcode::kUnreachable:
58 case IrOpcode::kIfException:
59 return ReduceUnreachableOrIfException(node);
60 case IrOpcode::kPhi:
61 return ReducePhi(node);
62 case IrOpcode::kEffectPhi:
63 return ReduceEffectPhi(node);
64 case IrOpcode::kDeoptimize:
65 case IrOpcode::kReturn:
66 case IrOpcode::kTerminate:
67 case IrOpcode::kTailCall:
68 return ReduceDeoptimizeOrReturnOrTerminateOrTailCall(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
ReduceLoopOrMerge(Node * node)111 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
112 DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
113 Node::Inputs inputs = node->inputs();
114 DCHECK_LE(1, inputs.count());
115 // Count the number of live inputs to {node} and compact them on the fly, also
116 // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
117 // same time. We consider {Loop}s dead even if only the first control input
118 // is dead.
119 int live_input_count = 0;
120 if (node->opcode() != IrOpcode::kLoop ||
121 node->InputAt(0)->opcode() != IrOpcode::kDead) {
122 for (int i = 0; i < inputs.count(); ++i) {
123 Node* const input = inputs[i];
124 // Skip dead inputs.
125 if (input->opcode() == IrOpcode::kDead) continue;
126 // Compact live inputs.
127 if (live_input_count != i) {
128 node->ReplaceInput(live_input_count, input);
129 for (Node* const use : node->uses()) {
130 if (NodeProperties::IsPhi(use)) {
131 DCHECK_EQ(inputs.count() + 1, use->InputCount());
132 use->ReplaceInput(live_input_count, use->InputAt(i));
133 }
134 }
135 }
136 ++live_input_count;
137 }
138 }
139 if (live_input_count == 0) {
140 return Replace(dead());
141 } else if (live_input_count == 1) {
142 NodeVector loop_exits(zone_);
143 // Due to compaction above, the live input is at offset 0.
144 for (Node* const use : node->uses()) {
145 if (NodeProperties::IsPhi(use)) {
146 Replace(use, use->InputAt(0));
147 } else if (use->opcode() == IrOpcode::kLoopExit &&
148 use->InputAt(1) == node) {
149 // Remember the loop exits so that we can mark their loop input dead.
150 // This has to be done after the use list iteration so that we do
151 // not mutate the use list while it is being iterated.
152 loop_exits.push_back(use);
153 } else if (use->opcode() == IrOpcode::kTerminate) {
154 DCHECK_EQ(IrOpcode::kLoop, node->opcode());
155 Replace(use, dead());
156 }
157 }
158 for (Node* loop_exit : loop_exits) {
159 loop_exit->ReplaceInput(1, dead());
160 Revisit(loop_exit);
161 }
162 return Replace(node->InputAt(0));
163 }
164 DCHECK_LE(2, live_input_count);
165 DCHECK_LE(live_input_count, inputs.count());
166 // Trim input count for the {Merge} or {Loop} node.
167 if (live_input_count < inputs.count()) {
168 // Trim input counts for all phi uses and revisit them.
169 for (Node* const use : node->uses()) {
170 if (NodeProperties::IsPhi(use)) {
171 use->ReplaceInput(live_input_count, node);
172 TrimMergeOrPhi(use, live_input_count);
173 Revisit(use);
174 }
175 }
176 TrimMergeOrPhi(node, live_input_count);
177 return Changed(node);
178 }
179 return NoChange();
180 }
181
RemoveLoopExit(Node * node)182 Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
183 DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
184 for (Node* const use : node->uses()) {
185 if (use->opcode() == IrOpcode::kLoopExitValue ||
186 use->opcode() == IrOpcode::kLoopExitEffect) {
187 Replace(use, use->InputAt(0));
188 }
189 }
190 Node* control = NodeProperties::GetControlInput(node, 0);
191 Replace(node, control);
192 return Replace(control);
193 }
194
ReduceNode(Node * node)195 Reduction DeadCodeElimination::ReduceNode(Node* node) {
196 DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
197 int const effect_input_count = node->op()->EffectInputCount();
198 int const control_input_count = node->op()->ControlInputCount();
199 DCHECK_LE(control_input_count, 1);
200 if (control_input_count == 1) {
201 Reduction reduction = PropagateDeadControl(node);
202 if (reduction.Changed()) return reduction;
203 }
204 if (effect_input_count == 0 &&
205 (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
206 return ReducePureNode(node);
207 }
208 if (effect_input_count > 0) {
209 return ReduceEffectNode(node);
210 }
211 return NoChange();
212 }
213
ReducePhi(Node * node)214 Reduction DeadCodeElimination::ReducePhi(Node* node) {
215 DCHECK_EQ(IrOpcode::kPhi, node->opcode());
216 Reduction reduction = PropagateDeadControl(node);
217 if (reduction.Changed()) return reduction;
218 MachineRepresentation rep = PhiRepresentationOf(node->op());
219 if (rep == MachineRepresentation::kNone ||
220 NodeProperties::GetTypeOrAny(node).IsNone()) {
221 return Replace(DeadValue(node, rep));
222 }
223 int input_count = node->op()->ValueInputCount();
224 for (int i = 0; i < input_count; ++i) {
225 Node* input = NodeProperties::GetValueInput(node, i);
226 if (input->opcode() == IrOpcode::kDeadValue &&
227 DeadValueRepresentationOf(input->op()) != rep) {
228 NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
229 }
230 }
231 return NoChange();
232 }
233
ReduceEffectPhi(Node * node)234 Reduction DeadCodeElimination::ReduceEffectPhi(Node* node) {
235 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
236 Reduction reduction = PropagateDeadControl(node);
237 if (reduction.Changed()) return reduction;
238
239 Node* merge = NodeProperties::GetControlInput(node);
240 DCHECK(merge->opcode() == IrOpcode::kMerge ||
241 merge->opcode() == IrOpcode::kLoop);
242 int input_count = node->op()->EffectInputCount();
243 for (int i = 0; i < input_count; ++i) {
244 Node* effect = NodeProperties::GetEffectInput(node, i);
245 if (effect->opcode() == IrOpcode::kUnreachable) {
246 // If Unreachable hits an effect phi, we can re-connect the effect chain
247 // to the graph end and delete the corresponding inputs from the merge and
248 // phi nodes.
249 Node* control = NodeProperties::GetControlInput(merge, i);
250 Node* throw_node = graph_->NewNode(common_->Throw(), effect, control);
251 NodeProperties::MergeControlToEnd(graph_, common_, throw_node);
252 NodeProperties::ReplaceEffectInput(node, dead_, i);
253 NodeProperties::ReplaceControlInput(merge, dead_, i);
254 Revisit(merge);
255 Revisit(graph_->end());
256 reduction = Changed(node);
257 }
258 }
259 return reduction;
260 }
261
ReducePureNode(Node * node)262 Reduction DeadCodeElimination::ReducePureNode(Node* node) {
263 DCHECK_EQ(0, node->op()->EffectInputCount());
264 if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
265 if (Node* input = FindDeadInput(node)) {
266 return Replace(DeadValue(input));
267 }
268 return NoChange();
269 }
270
ReduceUnreachableOrIfException(Node * node)271 Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
272 DCHECK(node->opcode() == IrOpcode::kUnreachable ||
273 node->opcode() == IrOpcode::kIfException);
274 Reduction reduction = PropagateDeadControl(node);
275 if (reduction.Changed()) return reduction;
276 Node* effect = NodeProperties::GetEffectInput(node, 0);
277 if (effect->opcode() == IrOpcode::kDead) {
278 return Replace(effect);
279 }
280 if (effect->opcode() == IrOpcode::kUnreachable) {
281 return Replace(effect);
282 }
283 return NoChange();
284 }
285
ReduceEffectNode(Node * node)286 Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
287 DCHECK_EQ(1, node->op()->EffectInputCount());
288 Node* effect = NodeProperties::GetEffectInput(node, 0);
289 if (effect->opcode() == IrOpcode::kDead) {
290 return Replace(effect);
291 }
292 if (Node* input = FindDeadInput(node)) {
293 if (effect->opcode() == IrOpcode::kUnreachable) {
294 RelaxEffectsAndControls(node);
295 return Replace(DeadValue(input));
296 }
297
298 Node* control = node->op()->ControlInputCount() == 1
299 ? NodeProperties::GetControlInput(node, 0)
300 : graph()->start();
301 Node* unreachable =
302 graph()->NewNode(common()->Unreachable(), effect, control);
303 NodeProperties::SetType(unreachable, Type::None());
304 ReplaceWithValue(node, DeadValue(input), node, control);
305 return Replace(unreachable);
306 }
307
308 return NoChange();
309 }
310
ReduceDeoptimizeOrReturnOrTerminateOrTailCall(Node * node)311 Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
312 Node* node) {
313 DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
314 node->opcode() == IrOpcode::kReturn ||
315 node->opcode() == IrOpcode::kTerminate ||
316 node->opcode() == IrOpcode::kTailCall);
317 Reduction reduction = PropagateDeadControl(node);
318 if (reduction.Changed()) return reduction;
319 // Terminate nodes are not part of actual control flow, so they should never
320 // be replaced with Throw.
321 if (node->opcode() != IrOpcode::kTerminate &&
322 FindDeadInput(node) != nullptr) {
323 Node* effect = NodeProperties::GetEffectInput(node, 0);
324 Node* control = NodeProperties::GetControlInput(node, 0);
325 if (effect->opcode() != IrOpcode::kUnreachable) {
326 effect = graph()->NewNode(common()->Unreachable(), effect, control);
327 NodeProperties::SetType(effect, Type::None());
328 }
329 node->TrimInputCount(2);
330 node->ReplaceInput(0, effect);
331 node->ReplaceInput(1, control);
332 NodeProperties::ChangeOp(node, common()->Throw());
333 return Changed(node);
334 }
335 return NoChange();
336 }
337
ReduceLoopExit(Node * node)338 Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
339 Node* control = NodeProperties::GetControlInput(node, 0);
340 Node* loop = NodeProperties::GetControlInput(node, 1);
341 if (control->opcode() == IrOpcode::kDead ||
342 loop->opcode() == IrOpcode::kDead) {
343 return RemoveLoopExit(node);
344 }
345 return NoChange();
346 }
347
ReduceBranchOrSwitch(Node * node)348 Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
349 DCHECK(node->opcode() == IrOpcode::kBranch ||
350 node->opcode() == IrOpcode::kSwitch);
351 Reduction reduction = PropagateDeadControl(node);
352 if (reduction.Changed()) return reduction;
353 Node* condition = NodeProperties::GetValueInput(node, 0);
354 if (condition->opcode() == IrOpcode::kDeadValue) {
355 // Branches or switches on {DeadValue} must originate from unreachable code
356 // and cannot matter. Due to schedule freedom between the effect and the
357 // control chain, they might still appear in reachable code. Remove them by
358 // always choosing the first projection.
359 size_t const projection_cnt = node->op()->ControlOutputCount();
360 Node** projections = zone_->NewArray<Node*>(projection_cnt);
361 NodeProperties::CollectControlProjections(node, projections,
362 projection_cnt);
363 Replace(projections[0], NodeProperties::GetControlInput(node));
364 return Replace(dead());
365 }
366 return NoChange();
367 }
368
TrimMergeOrPhi(Node * node,int size)369 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
370 const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
371 node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
372 NodeProperties::ChangeOp(node, op);
373 }
374
DeadValue(Node * node,MachineRepresentation rep)375 Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
376 if (node->opcode() == IrOpcode::kDeadValue) {
377 if (rep == DeadValueRepresentationOf(node->op())) return node;
378 node = NodeProperties::GetValueInput(node, 0);
379 }
380 Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
381 NodeProperties::SetType(dead_value, Type::None());
382 return dead_value;
383 }
384
385 } // namespace compiler
386 } // namespace internal
387 } // namespace v8
388