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