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/node-properties.h"
10 : #include "src/compiler/operator-properties.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 : namespace compiler {
15 :
16 2442026 : DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
17 : CommonOperatorBuilder* common)
18 : : AdvancedReducer(editor),
19 : graph_(graph),
20 : common_(common),
21 4884098 : dead_(graph->NewNode(common->Dead())) {
22 : NodeProperties::SetType(dead_, Type::None());
23 2442072 : }
24 :
25 260340419 : Reduction DeadCodeElimination::Reduce(Node* node) {
26 260340419 : switch (node->opcode()) {
27 : case IrOpcode::kEnd:
28 2512261 : return ReduceEnd(node);
29 : case IrOpcode::kLoop:
30 : case IrOpcode::kMerge:
31 7501352 : return ReduceLoopOrMerge(node);
32 : case IrOpcode::kLoopExit:
33 357834 : return ReduceLoopExit(node);
34 : default:
35 249968972 : return ReduceNode(node);
36 : }
37 : UNREACHABLE();
38 : return NoChange();
39 : }
40 :
41 :
42 2579805 : Reduction DeadCodeElimination::ReduceEnd(Node* node) {
43 : DCHECK_EQ(IrOpcode::kEnd, node->opcode());
44 : Node::Inputs inputs = node->inputs();
45 : DCHECK_LE(1, inputs.count());
46 : int live_input_count = 0;
47 7317701 : for (int i = 0; i < inputs.count(); ++i) {
48 4805459 : Node* const input = inputs[i];
49 : // Skip dead inputs.
50 4805459 : if (input->opcode() == IrOpcode::kDead) continue;
51 : // Compact live inputs.
52 4714341 : if (i != live_input_count) node->ReplaceInput(live_input_count, input);
53 4714410 : ++live_input_count;
54 : }
55 2512242 : if (live_input_count == 0) {
56 : return Replace(dead());
57 2512227 : } else if (live_input_count < inputs.count()) {
58 67617 : node->TrimInputCount(live_input_count);
59 135234 : NodeProperties::ChangeOp(node, common()->End(live_input_count));
60 : return Changed(node);
61 : }
62 : DCHECK_EQ(inputs.count(), live_input_count);
63 : return NoChange();
64 : }
65 :
66 :
67 15048380 : Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
68 : DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
69 : Node::Inputs inputs = node->inputs();
70 : DCHECK_LE(1, inputs.count());
71 : // Count the number of live inputs to {node} and compact them on the fly, also
72 : // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
73 : // same time. We consider {Loop}s dead even if only the first control input
74 : // is dead.
75 : int live_input_count = 0;
76 8011125 : if (node->opcode() != IrOpcode::kLoop ||
77 509936 : node->InputAt(0)->opcode() != IrOpcode::kDead) {
78 26511356 : for (int i = 0; i < inputs.count(); ++i) {
79 26511304 : Node* const input = inputs[i];
80 : // Skip dead inputs.
81 26511304 : if (input->opcode() == IrOpcode::kDead) continue;
82 : // Compact live inputs.
83 25844472 : if (live_input_count != i) {
84 625389 : node->ReplaceInput(live_input_count, input);
85 4559135 : for (Node* const use : node->uses()) {
86 3933694 : if (NodeProperties::IsPhi(use)) {
87 : DCHECK_EQ(inputs.count() + 1, use->InputCount());
88 2899864 : use->ReplaceInput(live_input_count, use->InputAt(i));
89 : }
90 : }
91 : }
92 25844524 : ++live_input_count;
93 : }
94 : }
95 7501241 : if (live_input_count == 0) {
96 : return Replace(dead());
97 7461840 : } else if (live_input_count == 1) {
98 : // Due to compaction above, the live input is at offset 0.
99 2259143 : for (Node* const use : node->uses()) {
100 1612379 : if (NodeProperties::IsPhi(use)) {
101 701794 : Replace(use, use->InputAt(0));
102 1316832 : } else if (use->opcode() == IrOpcode::kLoopExit &&
103 : use->InputAt(1) == node) {
104 2183 : RemoveLoopExit(use);
105 1308057 : } else if (use->opcode() == IrOpcode::kTerminate) {
106 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
107 : Replace(use, dead());
108 : }
109 : }
110 : return Replace(node->InputAt(0));
111 : }
112 : DCHECK_LE(2, live_input_count);
113 : DCHECK_LE(live_input_count, inputs.count());
114 : // Trim input count for the {Merge} or {Loop} node.
115 6815075 : if (live_input_count < inputs.count()) {
116 : // Trim input counts for all phi uses and revisit them.
117 911380 : for (Node* const use : node->uses()) {
118 727384 : if (NodeProperties::IsPhi(use)) {
119 393054 : use->ReplaceInput(live_input_count, node);
120 393053 : TrimMergeOrPhi(use, live_input_count);
121 : Revisit(use);
122 : }
123 : }
124 183996 : TrimMergeOrPhi(node, live_input_count);
125 : return Changed(node);
126 : }
127 : return NoChange();
128 : }
129 :
130 46890 : Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
131 : DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
132 1016760 : for (Node* const use : node->uses()) {
133 484935 : if (use->opcode() == IrOpcode::kLoopExitValue ||
134 : use->opcode() == IrOpcode::kLoopExitEffect) {
135 485283 : Replace(use, use->InputAt(0));
136 : }
137 : }
138 46890 : Node* control = NodeProperties::GetControlInput(node, 0);
139 : Replace(node, control);
140 46890 : return Replace(control);
141 : }
142 :
143 250014841 : Reduction DeadCodeElimination::ReduceNode(Node* node) {
144 : // If {node} has exactly one control input and this is {Dead},
145 : // replace {node} with {Dead}.
146 250014841 : int const control_input_count = node->op()->ControlInputCount();
147 250014841 : if (control_input_count == 0) return NoChange();
148 : DCHECK_EQ(1, control_input_count);
149 124474902 : Node* control = NodeProperties::GetControlInput(node);
150 124471116 : if (control->opcode() == IrOpcode::kDead) return Replace(control);
151 : return NoChange();
152 : }
153 :
154 357834 : Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
155 715668 : Node* control = NodeProperties::GetControlInput(node, 0);
156 675416 : Node* loop = NodeProperties::GetControlInput(node, 1);
157 675416 : if (control->opcode() == IrOpcode::kDead ||
158 : loop->opcode() == IrOpcode::kDead) {
159 44707 : return RemoveLoopExit(node);
160 : }
161 : return NoChange();
162 : }
163 :
164 577049 : void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
165 577049 : const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
166 577049 : node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
167 577049 : NodeProperties::ChangeOp(node, op);
168 577049 : }
169 :
170 : } // namespace compiler
171 : } // namespace internal
172 : } // namespace v8
|
