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/common-operator.h"
6 : #include "src/compiler/dead-code-elimination.h"
7 : #include "test/unittests/compiler/graph-reducer-unittest.h"
8 : #include "test/unittests/compiler/graph-unittest.h"
9 : #include "test/unittests/compiler/node-test-utils.h"
10 : #include "testing/gmock-support.h"
11 :
12 : using testing::StrictMock;
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 : namespace dead_code_elimination_unittest {
18 :
19 : class DeadCodeEliminationTest : public GraphTest {
20 : public:
21 : explicit DeadCodeEliminationTest(int num_parameters = 4)
22 18 : : GraphTest(num_parameters) {}
23 18 : ~DeadCodeEliminationTest() override = default;
24 :
25 : protected:
26 218 : Reduction Reduce(AdvancedReducer::Editor* editor, Node* node) {
27 218 : DeadCodeElimination reducer(editor, graph(), common(), zone());
28 436 : return reducer.Reduce(node);
29 : }
30 :
31 214 : Reduction Reduce(Node* node) {
32 214 : StrictMock<MockAdvancedReducerEditor> editor;
33 428 : return Reduce(&editor, node);
34 : }
35 : };
36 :
37 :
38 : namespace {
39 :
40 : const MachineRepresentation kMachineRepresentations[] = {
41 : MachineRepresentation::kBit, MachineRepresentation::kWord8,
42 : MachineRepresentation::kWord16, MachineRepresentation::kWord32,
43 : MachineRepresentation::kWord64, MachineRepresentation::kFloat32,
44 : MachineRepresentation::kFloat64, MachineRepresentation::kTagged};
45 :
46 :
47 : const int kMaxInputs = 16;
48 :
49 :
50 3083 : const Operator kOp0(0, Operator::kNoProperties, "Op0", 1, 1, 1, 1, 1, 1);
51 :
52 : } // namespace
53 :
54 :
55 : // -----------------------------------------------------------------------------
56 : // General dead propagation
57 :
58 :
59 15419 : TEST_F(DeadCodeEliminationTest, GeneralDeadPropagation) {
60 1 : Node* const value = Parameter(0);
61 : Node* const effect = graph()->start();
62 1 : Node* const dead = graph()->NewNode(common()->Dead());
63 : Node* const node = graph()->NewNode(&kOp0, value, effect, dead);
64 1 : Reduction const r = Reduce(node);
65 1 : ASSERT_TRUE(r.Changed());
66 4 : EXPECT_THAT(r.replacement(), IsDead());
67 : }
68 :
69 :
70 : // -----------------------------------------------------------------------------
71 : // Branch
72 :
73 :
74 15419 : TEST_F(DeadCodeEliminationTest, BranchWithDeadControlInput) {
75 : BranchHint const kHints[] = {BranchHint::kNone, BranchHint::kTrue,
76 1 : BranchHint::kFalse};
77 13 : TRACED_FOREACH(BranchHint, hint, kHints) {
78 : Reduction const r =
79 : Reduce(graph()->NewNode(common()->Branch(hint), Parameter(0),
80 9 : graph()->NewNode(common()->Dead())));
81 3 : ASSERT_TRUE(r.Changed());
82 12 : EXPECT_THAT(r.replacement(), IsDead());
83 : }
84 : }
85 :
86 :
87 : // -----------------------------------------------------------------------------
88 : // IfTrue
89 :
90 :
91 15419 : TEST_F(DeadCodeEliminationTest, IfTrueWithDeadInput) {
92 : Reduction const r = Reduce(
93 3 : graph()->NewNode(common()->IfTrue(), graph()->NewNode(common()->Dead())));
94 1 : ASSERT_TRUE(r.Changed());
95 4 : EXPECT_THAT(r.replacement(), IsDead());
96 : }
97 :
98 :
99 : // -----------------------------------------------------------------------------
100 : // IfFalse
101 :
102 :
103 15419 : TEST_F(DeadCodeEliminationTest, IfFalseWithDeadInput) {
104 : Reduction const r = Reduce(graph()->NewNode(
105 3 : common()->IfFalse(), graph()->NewNode(common()->Dead())));
106 1 : ASSERT_TRUE(r.Changed());
107 4 : EXPECT_THAT(r.replacement(), IsDead());
108 : }
109 :
110 :
111 : // -----------------------------------------------------------------------------
112 : // IfSuccess
113 :
114 :
115 15419 : TEST_F(DeadCodeEliminationTest, IfSuccessWithDeadInput) {
116 : Reduction const r = Reduce(graph()->NewNode(
117 3 : common()->IfSuccess(), graph()->NewNode(common()->Dead())));
118 1 : ASSERT_TRUE(r.Changed());
119 4 : EXPECT_THAT(r.replacement(), IsDead());
120 : }
121 :
122 :
123 : // -----------------------------------------------------------------------------
124 : // IfException
125 :
126 :
127 15419 : TEST_F(DeadCodeEliminationTest, IfExceptionWithDeadControlInput) {
128 : Reduction const r =
129 : Reduce(graph()->NewNode(common()->IfException(), graph()->start(),
130 3 : graph()->NewNode(common()->Dead())));
131 1 : ASSERT_TRUE(r.Changed());
132 4 : EXPECT_THAT(r.replacement(), IsDead());
133 : }
134 :
135 :
136 : // -----------------------------------------------------------------------------
137 : // End
138 :
139 :
140 15419 : TEST_F(DeadCodeEliminationTest, EndWithDeadAndStart) {
141 1 : Node* const dead = graph()->NewNode(common()->Dead());
142 : Node* const start = graph()->start();
143 2 : Reduction const r = Reduce(graph()->NewNode(common()->End(2), dead, start));
144 1 : ASSERT_TRUE(r.Changed());
145 5 : EXPECT_THAT(r.replacement(), IsEnd(start));
146 : }
147 :
148 :
149 15419 : TEST_F(DeadCodeEliminationTest, EndWithOnlyDeadInputs) {
150 : Node* inputs[kMaxInputs];
151 61 : TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
152 255 : for (int i = 0; i < input_count; ++i) {
153 240 : inputs[i] = graph()->NewNode(common()->Dead());
154 : }
155 : Reduction const r = Reduce(
156 45 : graph()->NewNode(common()->End(input_count), input_count, inputs));
157 15 : ASSERT_TRUE(r.Changed());
158 60 : EXPECT_THAT(r.replacement(), IsDead());
159 : }
160 : }
161 :
162 :
163 : // -----------------------------------------------------------------------------
164 : // Merge
165 :
166 :
167 15419 : TEST_F(DeadCodeEliminationTest, MergeWithOnlyDeadInputs) {
168 : Node* inputs[kMaxInputs + 1];
169 61 : TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
170 255 : for (int i = 0; i < input_count; ++i) {
171 240 : inputs[i] = graph()->NewNode(common()->Dead());
172 : }
173 : Reduction const r = Reduce(
174 30 : graph()->NewNode(common()->Merge(input_count), input_count, inputs));
175 15 : ASSERT_TRUE(r.Changed());
176 60 : EXPECT_THAT(r.replacement(), IsDead());
177 : }
178 : }
179 :
180 :
181 15419 : TEST_F(DeadCodeEliminationTest, MergeWithOneLiveAndOneDeadInput) {
182 1 : Node* const v0 = Parameter(0);
183 1 : Node* const v1 = Parameter(1);
184 : Node* const c0 =
185 1 : graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
186 1 : Node* const c1 = graph()->NewNode(common()->Dead());
187 1 : Node* const e0 = graph()->NewNode(&kOp0, v0, graph()->start(), c0);
188 : Node* const e1 = graph()->NewNode(&kOp0, v1, graph()->start(), c1);
189 1 : Node* const merge = graph()->NewNode(common()->Merge(2), c0, c1);
190 1 : Node* const phi = graph()->NewNode(
191 : common()->Phi(MachineRepresentation::kTagged, 2), v0, v1, merge);
192 1 : Node* const ephi = graph()->NewNode(common()->EffectPhi(2), e0, e1, merge);
193 1 : StrictMock<MockAdvancedReducerEditor> editor;
194 4 : EXPECT_CALL(editor, Replace(phi, v0));
195 4 : EXPECT_CALL(editor, Replace(ephi, e0));
196 1 : Reduction const r = Reduce(&editor, merge);
197 1 : ASSERT_TRUE(r.Changed());
198 2 : EXPECT_EQ(c0, r.replacement());
199 : }
200 :
201 :
202 15419 : TEST_F(DeadCodeEliminationTest, MergeWithTwoLiveAndTwoDeadInputs) {
203 1 : Node* const v0 = Parameter(0);
204 1 : Node* const v1 = Parameter(1);
205 1 : Node* const v2 = Parameter(2);
206 1 : Node* const v3 = Parameter(3);
207 : Node* const c0 =
208 : graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
209 1 : Node* const c1 = graph()->NewNode(common()->Dead());
210 1 : Node* const c2 = graph()->NewNode(common()->Dead());
211 : Node* const c3 = graph()->NewNode(&kOp0, v3, graph()->start(), c0);
212 : Node* const e0 = graph()->start();
213 : Node* const e1 = graph()->NewNode(&kOp0, v1, e0, c0);
214 : Node* const e2 = graph()->NewNode(&kOp0, v2, e1, c0);
215 : Node* const e3 = graph()->NewNode(&kOp0, v3, graph()->start(), c3);
216 1 : Node* const merge = graph()->NewNode(common()->Merge(4), c0, c1, c2, c3);
217 1 : Node* const phi = graph()->NewNode(
218 1 : common()->Phi(MachineRepresentation::kTagged, 4), v0, v1, v2, v3, merge);
219 : Node* const ephi =
220 2 : graph()->NewNode(common()->EffectPhi(4), e0, e1, e2, e3, merge);
221 1 : StrictMock<MockAdvancedReducerEditor> editor;
222 3 : EXPECT_CALL(editor, Revisit(phi));
223 3 : EXPECT_CALL(editor, Revisit(ephi));
224 1 : Reduction const r = Reduce(&editor, merge);
225 1 : ASSERT_TRUE(r.Changed());
226 6 : EXPECT_THAT(r.replacement(), IsMerge(c0, c3));
227 8 : EXPECT_THAT(phi,
228 0 : IsPhi(MachineRepresentation::kTagged, v0, v3, r.replacement()));
229 7 : EXPECT_THAT(ephi, IsEffectPhi(e0, e3, r.replacement()));
230 : }
231 :
232 :
233 : // -----------------------------------------------------------------------------
234 : // Loop
235 :
236 :
237 15419 : TEST_F(DeadCodeEliminationTest, LoopWithDeadFirstInput) {
238 : Node* inputs[kMaxInputs + 1];
239 61 : TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
240 30 : inputs[0] = graph()->NewNode(common()->Dead());
241 225 : for (int i = 1; i < input_count; ++i) {
242 105 : inputs[i] = graph()->start();
243 : }
244 : Reduction const r = Reduce(
245 15 : graph()->NewNode(common()->Loop(input_count), input_count, inputs));
246 15 : ASSERT_TRUE(r.Changed());
247 60 : EXPECT_THAT(r.replacement(), IsDead());
248 : }
249 : }
250 :
251 :
252 15419 : TEST_F(DeadCodeEliminationTest, LoopWithOnlyDeadInputs) {
253 : Node* inputs[kMaxInputs + 1];
254 61 : TRACED_FORRANGE(int, input_count, 1, kMaxInputs - 1) {
255 255 : for (int i = 0; i < input_count; ++i) {
256 240 : inputs[i] = graph()->NewNode(common()->Dead());
257 : }
258 : Reduction const r = Reduce(
259 30 : graph()->NewNode(common()->Loop(input_count), input_count, inputs));
260 15 : ASSERT_TRUE(r.Changed());
261 60 : EXPECT_THAT(r.replacement(), IsDead());
262 : }
263 : }
264 :
265 :
266 15419 : TEST_F(DeadCodeEliminationTest, LoopWithOneLiveAndOneDeadInput) {
267 1 : Node* const v0 = Parameter(0);
268 1 : Node* const v1 = Parameter(1);
269 : Node* const c0 =
270 1 : graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
271 1 : Node* const c1 = graph()->NewNode(common()->Dead());
272 1 : Node* const e0 = graph()->NewNode(&kOp0, v0, graph()->start(), c0);
273 : Node* const e1 = graph()->NewNode(&kOp0, v1, graph()->start(), c1);
274 1 : Node* const loop = graph()->NewNode(common()->Loop(2), c0, c1);
275 1 : Node* const phi = graph()->NewNode(
276 : common()->Phi(MachineRepresentation::kTagged, 2), v0, v1, loop);
277 1 : Node* const ephi = graph()->NewNode(common()->EffectPhi(2), e0, e1, loop);
278 1 : Node* const terminate = graph()->NewNode(common()->Terminate(), ephi, loop);
279 1 : StrictMock<MockAdvancedReducerEditor> editor;
280 4 : EXPECT_CALL(editor, Replace(phi, v0));
281 4 : EXPECT_CALL(editor, Replace(ephi, e0));
282 4 : EXPECT_CALL(editor, Replace(terminate, IsDead()));
283 1 : Reduction const r = Reduce(&editor, loop);
284 1 : ASSERT_TRUE(r.Changed());
285 2 : EXPECT_EQ(c0, r.replacement());
286 : }
287 :
288 :
289 15419 : TEST_F(DeadCodeEliminationTest, LoopWithTwoLiveAndTwoDeadInputs) {
290 1 : Node* const v0 = Parameter(0);
291 1 : Node* const v1 = Parameter(1);
292 1 : Node* const v2 = Parameter(2);
293 1 : Node* const v3 = Parameter(3);
294 : Node* const c0 =
295 : graph()->NewNode(&kOp0, v0, graph()->start(), graph()->start());
296 1 : Node* const c1 = graph()->NewNode(common()->Dead());
297 1 : Node* const c2 = graph()->NewNode(common()->Dead());
298 : Node* const c3 = graph()->NewNode(&kOp0, v3, graph()->start(), c0);
299 : Node* const e0 = graph()->start();
300 : Node* const e1 = graph()->NewNode(&kOp0, v1, e0, c0);
301 : Node* const e2 = graph()->NewNode(&kOp0, v2, e1, c0);
302 : Node* const e3 = graph()->NewNode(&kOp0, v3, graph()->start(), c3);
303 1 : Node* const loop = graph()->NewNode(common()->Loop(4), c0, c1, c2, c3);
304 1 : Node* const phi = graph()->NewNode(
305 1 : common()->Phi(MachineRepresentation::kTagged, 4), v0, v1, v2, v3, loop);
306 : Node* const ephi =
307 2 : graph()->NewNode(common()->EffectPhi(4), e0, e1, e2, e3, loop);
308 1 : StrictMock<MockAdvancedReducerEditor> editor;
309 3 : EXPECT_CALL(editor, Revisit(phi));
310 3 : EXPECT_CALL(editor, Revisit(ephi));
311 1 : Reduction const r = Reduce(&editor, loop);
312 1 : ASSERT_TRUE(r.Changed());
313 6 : EXPECT_THAT(r.replacement(), IsLoop(c0, c3));
314 8 : EXPECT_THAT(phi,
315 0 : IsPhi(MachineRepresentation::kTagged, v0, v3, r.replacement()));
316 7 : EXPECT_THAT(ephi, IsEffectPhi(e0, e3, r.replacement()));
317 : }
318 :
319 :
320 : // -----------------------------------------------------------------------------
321 : // Phi
322 :
323 :
324 15419 : TEST_F(DeadCodeEliminationTest, PhiWithDeadControlInput) {
325 : Node* inputs[kMaxInputs + 1];
326 33 : TRACED_FOREACH(MachineRepresentation, rep, kMachineRepresentations) {
327 520 : TRACED_FORRANGE(int, input_count, 1, kMaxInputs) {
328 2304 : for (int i = 0; i < input_count; ++i) {
329 1088 : inputs[i] = Parameter(i);
330 : }
331 256 : inputs[input_count] = graph()->NewNode(common()->Dead());
332 : Reduction const r = Reduce(graph()->NewNode(
333 128 : common()->Phi(rep, input_count), input_count + 1, inputs));
334 128 : ASSERT_TRUE(r.Changed());
335 512 : EXPECT_THAT(r.replacement(), IsDead());
336 : }
337 : }
338 : }
339 :
340 :
341 : // -----------------------------------------------------------------------------
342 : // EffectPhi
343 :
344 :
345 15419 : TEST_F(DeadCodeEliminationTest, EffectPhiWithDeadControlInput) {
346 : Node* inputs[kMaxInputs + 1];
347 65 : TRACED_FORRANGE(int, input_count, 1, kMaxInputs) {
348 288 : for (int i = 0; i < input_count; ++i) {
349 136 : inputs[i] = graph()->start();
350 : }
351 32 : inputs[input_count] = graph()->NewNode(common()->Dead());
352 : Reduction const r = Reduce(graph()->NewNode(
353 16 : common()->EffectPhi(input_count), input_count + 1, inputs));
354 16 : ASSERT_TRUE(r.Changed());
355 64 : EXPECT_THAT(r.replacement(), IsDead());
356 : }
357 : }
358 :
359 :
360 : // -----------------------------------------------------------------------------
361 : // Terminate
362 :
363 :
364 15419 : TEST_F(DeadCodeEliminationTest, TerminateWithDeadControlInput) {
365 : Reduction const r =
366 : Reduce(graph()->NewNode(common()->Terminate(), graph()->start(),
367 3 : graph()->NewNode(common()->Dead())));
368 1 : ASSERT_TRUE(r.Changed());
369 4 : EXPECT_THAT(r.replacement(), IsDead());
370 : }
371 :
372 : } // namespace dead_code_elimination_unittest
373 : } // namespace compiler
374 : } // namespace internal
375 9249 : } // namespace v8
|
