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
23
Reduce(Node * node)24 Reduction 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
ReduceEnd(Node * node)39 Reduction 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
ReduceLoopOrMerge(Node * node)64 Reduction 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
ReduceNode(Node * node)125 Reduction 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
TrimMergeOrPhi(Node * node,int size)137 void 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