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 2446342 : DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
17 : CommonOperatorBuilder* common)
18 : : AdvancedReducer(editor),
19 : graph_(graph),
20 : common_(common),
21 4892695 : dead_(graph->NewNode(common->Dead())) {
22 : NodeProperties::SetType(dead_, Type::None());
23 2446353 : }
24 :
25 260404383 : Reduction DeadCodeElimination::Reduce(Node* node) {
26 260404383 : switch (node->opcode()) {
27 : case IrOpcode::kEnd:
28 2515734 : return ReduceEnd(node);
29 : case IrOpcode::kLoop:
30 : case IrOpcode::kMerge:
31 7497544 : return ReduceLoopOrMerge(node);
32 : case IrOpcode::kLoopExit:
33 355291 : return ReduceLoopExit(node);
34 : default:
35 250035814 : return ReduceNode(node);
36 : }
37 : UNREACHABLE();
38 : return NoChange();
39 : }
40 :
41 :
42 2583240 : 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 7306942 : for (int i = 0; i < inputs.count(); ++i) {
48 4791210 : Node* const input = inputs[i];
49 : // Skip dead inputs.
50 4791210 : if (input->opcode() == IrOpcode::kDead) continue;
51 : // Compact live inputs.
52 4700163 : if (i != live_input_count) node->ReplaceInput(live_input_count, input);
53 4700207 : ++live_input_count;
54 : }
55 2515732 : if (live_input_count == 0) {
56 : return Replace(dead());
57 2515717 : } else if (live_input_count < inputs.count()) {
58 67537 : node->TrimInputCount(live_input_count);
59 135074 : 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 15040975 : 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 8006322 : if (node->opcode() != IrOpcode::kLoop ||
77 508816 : node->InputAt(0)->opcode() != IrOpcode::kDead) {
78 26493401 : for (int i = 0; i < inputs.count(); ++i) {
79 26493320 : Node* const input = inputs[i];
80 : // Skip dead inputs.
81 26493320 : if (input->opcode() == IrOpcode::kDead) continue;
82 : // Compact live inputs.
83 25826855 : if (live_input_count != i) {
84 625267 : node->ReplaceInput(live_input_count, input);
85 4552025 : for (Node* const use : node->uses()) {
86 3926677 : if (NodeProperties::IsPhi(use)) {
87 : DCHECK_EQ(inputs.count() + 1, use->InputCount());
88 2893377 : use->ReplaceInput(live_input_count, use->InputAt(i));
89 : }
90 : }
91 : }
92 25826936 : ++live_input_count;
93 : }
94 : }
95 7497587 : if (live_input_count == 0) {
96 : return Replace(dead());
97 7458227 : } else if (live_input_count == 1) {
98 : // Due to compaction above, the live input is at offset 0.
99 2317749 : for (Node* const use : node->uses()) {
100 1672080 : if (NodeProperties::IsPhi(use)) {
101 701728 : Replace(use, use->InputAt(0));
102 1375601 : } else if (use->opcode() == IrOpcode::kLoopExit &&
103 : use->InputAt(1) == node) {
104 2185 : RemoveLoopExit(use);
105 1366901 : } 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 6812558 : if (live_input_count < inputs.count()) {
116 : // Trim input counts for all phi uses and revisit them.
117 910801 : for (Node* const use : node->uses()) {
118 726626 : if (NodeProperties::IsPhi(use)) {
119 392131 : use->ReplaceInput(live_input_count, node);
120 392131 : TrimMergeOrPhi(use, live_input_count);
121 : Revisit(use);
122 : }
123 : }
124 184175 : TrimMergeOrPhi(node, live_input_count);
125 : return Changed(node);
126 : }
127 : return NoChange();
128 : }
129 :
130 46148 : Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
131 : DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
132 1003204 : for (Node* const use : node->uses()) {
133 478528 : if (use->opcode() == IrOpcode::kLoopExitValue ||
134 : use->opcode() == IrOpcode::kLoopExitEffect) {
135 478876 : Replace(use, use->InputAt(0));
136 : }
137 : }
138 46148 : Node* control = NodeProperties::GetControlInput(node, 0);
139 : Replace(node, control);
140 46148 : return Replace(control);
141 : }
142 :
143 250079661 : Reduction DeadCodeElimination::ReduceNode(Node* node) {
144 : // If {node} has exactly one control input and this is {Dead},
145 : // replace {node} with {Dead}.
146 250079661 : int const control_input_count = node->op()->ControlInputCount();
147 250079661 : if (control_input_count == 0) return NoChange();
148 : DCHECK_EQ(1, control_input_count);
149 124444824 : Node* control = NodeProperties::GetControlInput(node);
150 124439832 : if (control->opcode() == IrOpcode::kDead) return Replace(control);
151 : return NoChange();
152 : }
153 :
154 355291 : Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
155 710582 : Node* control = NodeProperties::GetControlInput(node, 0);
156 671073 : Node* loop = NodeProperties::GetControlInput(node, 1);
157 671073 : if (control->opcode() == IrOpcode::kDead ||
158 : loop->opcode() == IrOpcode::kDead) {
159 43963 : return RemoveLoopExit(node);
160 : }
161 : return NoChange();
162 : }
163 :
164 576306 : void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
165 576306 : const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
166 576306 : node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
167 576306 : NodeProperties::ChangeOp(node, op);
168 576306 : }
169 :
170 : } // namespace compiler
171 : } // namespace internal
172 : } // namespace v8
|