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 2672029 : DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
17 : CommonOperatorBuilder* common)
18 : : AdvancedReducer(editor),
19 : graph_(graph),
20 : common_(common),
21 5344061 : dead_(graph->NewNode(common->Dead())) {
22 : NodeProperties::SetType(dead_, Type::None());
23 2672032 : }
24 :
25 262218719 : Reduction DeadCodeElimination::Reduce(Node* node) {
26 262218719 : switch (node->opcode()) {
27 : case IrOpcode::kEnd:
28 2776519 : return ReduceEnd(node);
29 : case IrOpcode::kLoop:
30 : case IrOpcode::kMerge:
31 6067673 : return ReduceLoopOrMerge(node);
32 : case IrOpcode::kLoopExit:
33 233291 : return ReduceLoopExit(node);
34 : default:
35 253141236 : return ReduceNode(node);
36 : }
37 : UNREACHABLE();
38 : }
39 :
40 :
41 2851926 : Reduction DeadCodeElimination::ReduceEnd(Node* node) {
42 : DCHECK_EQ(IrOpcode::kEnd, node->opcode());
43 : Node::Inputs inputs = node->inputs();
44 : DCHECK_LE(1, inputs.count());
45 : int live_input_count = 0;
46 9929469 : for (int i = 0; i < inputs.count(); ++i) {
47 7152955 : Node* const input = inputs[i];
48 : // Skip dead inputs.
49 7152955 : if (input->opcode() == IrOpcode::kDead) continue;
50 : // Compact live inputs.
51 7035754 : if (i != live_input_count) node->ReplaceInput(live_input_count, input);
52 7035757 : ++live_input_count;
53 : }
54 2776514 : if (live_input_count == 0) {
55 : return Replace(dead());
56 2776499 : } else if (live_input_count < inputs.count()) {
57 75400 : node->TrimInputCount(live_input_count);
58 150800 : NodeProperties::ChangeOp(node, common()->End(live_input_count));
59 : return Changed(node);
60 : }
61 : DCHECK_EQ(inputs.count(), live_input_count);
62 : return NoChange();
63 : }
64 :
65 :
66 12155033 : Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
67 : DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
68 : Node::Inputs inputs = node->inputs();
69 : DCHECK_LE(1, inputs.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 6521014 : if (node->opcode() != IrOpcode::kLoop ||
76 453290 : node->InputAt(0)->opcode() != IrOpcode::kDead) {
77 16278392 : for (int i = 0; i < inputs.count(); ++i) {
78 16278333 : Node* const input = inputs[i];
79 : // Skip dead inputs.
80 16278333 : if (input->opcode() == IrOpcode::kDead) continue;
81 : // Compact live inputs.
82 15850218 : if (live_input_count != i) {
83 426069 : node->ReplaceInput(live_input_count, input);
84 2042169 : for (Node* const use : node->uses()) {
85 1616041 : if (NodeProperties::IsPhi(use)) {
86 : DCHECK_EQ(inputs.count() + 1, use->InputCount());
87 886004 : use->ReplaceInput(live_input_count, use->InputAt(i));
88 : }
89 : }
90 : }
91 15850277 : ++live_input_count;
92 : }
93 : }
94 6067783 : if (live_input_count == 0) {
95 : return Replace(dead());
96 6056159 : } else if (live_input_count == 1) {
97 : // Due to compaction above, the live input is at offset 0.
98 2117219 : for (Node* const use : node->uses()) {
99 1576047 : if (NodeProperties::IsPhi(use)) {
100 485714 : Replace(use, use->InputAt(0));
101 1273053 : } else if (use->opcode() == IrOpcode::kLoopExit &&
102 : use->InputAt(1) == node) {
103 3216 : RemoveLoopExit(use);
104 1264794 : } 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, inputs.count());
113 : // Trim input count for the {Merge} or {Loop} node.
114 5514986 : if (live_input_count < inputs.count()) {
115 : // Trim input counts for all phi uses and revisit them.
116 518246 : for (Node* const use : node->uses()) {
117 396353 : if (NodeProperties::IsPhi(use)) {
118 169716 : use->ReplaceInput(live_input_count, node);
119 169716 : TrimMergeOrPhi(use, live_input_count);
120 : Revisit(use);
121 : }
122 : }
123 121893 : TrimMergeOrPhi(node, live_input_count);
124 : return Changed(node);
125 : }
126 : return NoChange();
127 : }
128 :
129 23653 : Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
130 : DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
131 214093 : for (Node* const use : node->uses()) {
132 95220 : if (use->opcode() == IrOpcode::kLoopExitValue ||
133 : use->opcode() == IrOpcode::kLoopExitEffect) {
134 95082 : Replace(use, use->InputAt(0));
135 : }
136 : }
137 23653 : Node* control = NodeProperties::GetControlInput(node, 0);
138 : Replace(node, control);
139 23653 : return Replace(control);
140 : }
141 :
142 253185951 : Reduction DeadCodeElimination::ReduceNode(Node* node) {
143 : // If {node} has exactly one control input and this is {Dead},
144 : // replace {node} with {Dead}.
145 253185951 : int const control_input_count = node->op()->ControlInputCount();
146 253185951 : if (control_input_count == 0) return NoChange();
147 : DCHECK_EQ(1, control_input_count);
148 124211575 : Node* control = NodeProperties::GetControlInput(node);
149 124207650 : if (control->opcode() == IrOpcode::kDead) return Replace(control);
150 : return NoChange();
151 : }
152 :
153 233291 : Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
154 466582 : Node* control = NodeProperties::GetControlInput(node, 0);
155 446168 : Node* loop = NodeProperties::GetControlInput(node, 1);
156 446168 : if (control->opcode() == IrOpcode::kDead ||
157 : loop->opcode() == IrOpcode::kDead) {
158 20437 : return RemoveLoopExit(node);
159 : }
160 : return NoChange();
161 : }
162 :
163 291609 : void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
164 291609 : const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
165 291609 : node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
166 291609 : NodeProperties::ChangeOp(node, op);
167 291609 : }
168 :
169 : } // namespace compiler
170 : } // namespace internal
171 : } // namespace v8
|
