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