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