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