Line data Source code
1 : // Copyright 2016 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/load-elimination.h"
6 : #include "src/compiler/access-builder.h"
7 : #include "src/compiler/js-graph.h"
8 : #include "src/compiler/node.h"
9 : #include "src/compiler/simplified-operator.h"
10 : #include "test/unittests/compiler/graph-reducer-unittest.h"
11 : #include "test/unittests/compiler/graph-unittest.h"
12 : #include "test/unittests/compiler/node-test-utils.h"
13 : #include "testing/gmock-support.h"
14 :
15 : using testing::_;
16 : using testing::StrictMock;
17 :
18 : namespace v8 {
19 : namespace internal {
20 : namespace compiler {
21 :
22 : class LoadEliminationTest : public TypedGraphTest {
23 : public:
24 14 : LoadEliminationTest()
25 : : TypedGraphTest(3),
26 : simplified_(zone()),
27 42 : jsgraph_(isolate(), graph(), common(), nullptr, simplified(), nullptr) {
28 14 : }
29 14 : ~LoadEliminationTest() override = default;
30 :
31 : protected:
32 14 : JSGraph* jsgraph() { return &jsgraph_; }
33 14 : SimplifiedOperatorBuilder* simplified() { return &simplified_; }
34 :
35 : private:
36 : SimplifiedOperatorBuilder simplified_;
37 : JSGraph jsgraph_;
38 : };
39 :
40 15444 : TEST_F(LoadEliminationTest, LoadElementAndLoadElement) {
41 1 : Node* object = Parameter(Type::Any(), 0);
42 : Node* effect = graph()->start();
43 : Node* control = graph()->start();
44 1 : Node* index = Parameter(Type::UnsignedSmall(), 1);
45 : ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
46 : MachineType::AnyTagged(), kNoWriteBarrier};
47 :
48 1 : StrictMock<MockAdvancedReducerEditor> editor;
49 : LoadElimination load_elimination(&editor, jsgraph(), zone());
50 :
51 1 : load_elimination.Reduce(graph()->start());
52 :
53 1 : Node* load1 = effect = graph()->NewNode(simplified()->LoadElement(access),
54 1 : object, index, effect, control);
55 1 : load_elimination.Reduce(load1);
56 :
57 1 : Node* load2 = effect = graph()->NewNode(simplified()->LoadElement(access),
58 : object, index, effect, control);
59 7 : EXPECT_CALL(editor, ReplaceWithValue(load2, load1, load1, _));
60 1 : Reduction r = load_elimination.Reduce(load2);
61 1 : ASSERT_TRUE(r.Changed());
62 2 : EXPECT_EQ(load1, r.replacement());
63 : }
64 :
65 15444 : TEST_F(LoadEliminationTest, StoreElementAndLoadElement) {
66 1 : Node* object = Parameter(Type::Any(), 0);
67 : Node* effect = graph()->start();
68 : Node* control = graph()->start();
69 1 : Node* index = Parameter(Type::UnsignedSmall(), 1);
70 1 : Node* value = Parameter(Type::Any(), 2);
71 : ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
72 : MachineType::AnyTagged(), kNoWriteBarrier};
73 :
74 1 : StrictMock<MockAdvancedReducerEditor> editor;
75 : LoadElimination load_elimination(&editor, jsgraph(), zone());
76 :
77 1 : load_elimination.Reduce(graph()->start());
78 :
79 : Node* store = effect =
80 2 : graph()->NewNode(simplified()->StoreElement(access), object, index, value,
81 : effect, control);
82 1 : load_elimination.Reduce(store);
83 :
84 1 : Node* load = effect = graph()->NewNode(simplified()->LoadElement(access),
85 : object, index, effect, control);
86 7 : EXPECT_CALL(editor, ReplaceWithValue(load, value, store, _));
87 1 : Reduction r = load_elimination.Reduce(load);
88 1 : ASSERT_TRUE(r.Changed());
89 2 : EXPECT_EQ(value, r.replacement());
90 : }
91 :
92 15444 : TEST_F(LoadEliminationTest, StoreElementAndStoreFieldAndLoadElement) {
93 1 : Node* object = Parameter(Type::Any(), 0);
94 : Node* effect = graph()->start();
95 : Node* control = graph()->start();
96 1 : Node* index = Parameter(Type::UnsignedSmall(), 1);
97 1 : Node* value = Parameter(Type::Any(), 2);
98 : ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
99 : MachineType::AnyTagged(), kNoWriteBarrier};
100 :
101 1 : StrictMock<MockAdvancedReducerEditor> editor;
102 : LoadElimination load_elimination(&editor, jsgraph(), zone());
103 :
104 1 : load_elimination.Reduce(graph()->start());
105 :
106 : Node* store1 = effect =
107 2 : graph()->NewNode(simplified()->StoreElement(access), object, index, value,
108 : effect, control);
109 1 : load_elimination.Reduce(store1);
110 :
111 : Node* store2 = effect =
112 2 : graph()->NewNode(simplified()->StoreField(AccessBuilder::ForMap()),
113 : object, value, effect, control);
114 1 : load_elimination.Reduce(store2);
115 :
116 1 : Node* load = effect = graph()->NewNode(simplified()->LoadElement(access),
117 : object, index, effect, control);
118 7 : EXPECT_CALL(editor, ReplaceWithValue(load, value, store2, _));
119 1 : Reduction r = load_elimination.Reduce(load);
120 1 : ASSERT_TRUE(r.Changed());
121 2 : EXPECT_EQ(value, r.replacement());
122 : }
123 :
124 15444 : TEST_F(LoadEliminationTest, LoadFieldAndLoadField) {
125 1 : Node* object = Parameter(Type::Any(), 0);
126 : Node* effect = graph()->start();
127 : Node* control = graph()->start();
128 : FieldAccess const access = {kTaggedBase, kTaggedSize,
129 : MaybeHandle<Name>(), MaybeHandle<Map>(),
130 : Type::Any(), MachineType::AnyTagged(),
131 : kNoWriteBarrier};
132 :
133 1 : StrictMock<MockAdvancedReducerEditor> editor;
134 : LoadElimination load_elimination(&editor, jsgraph(), zone());
135 :
136 1 : load_elimination.Reduce(graph()->start());
137 :
138 1 : Node* load1 = effect = graph()->NewNode(simplified()->LoadField(access),
139 1 : object, effect, control);
140 1 : load_elimination.Reduce(load1);
141 :
142 1 : Node* load2 = effect = graph()->NewNode(simplified()->LoadField(access),
143 : object, effect, control);
144 7 : EXPECT_CALL(editor, ReplaceWithValue(load2, load1, load1, _));
145 1 : Reduction r = load_elimination.Reduce(load2);
146 1 : ASSERT_TRUE(r.Changed());
147 2 : EXPECT_EQ(load1, r.replacement());
148 : }
149 :
150 15444 : TEST_F(LoadEliminationTest, StoreFieldAndLoadField) {
151 1 : Node* object = Parameter(Type::Any(), 0);
152 1 : Node* value = Parameter(Type::Any(), 1);
153 : Node* effect = graph()->start();
154 : Node* control = graph()->start();
155 : FieldAccess access = {kTaggedBase, kTaggedSize,
156 : MaybeHandle<Name>(), MaybeHandle<Map>(),
157 : Type::Any(), MachineType::AnyTagged(),
158 : kNoWriteBarrier};
159 :
160 1 : StrictMock<MockAdvancedReducerEditor> editor;
161 : LoadElimination load_elimination(&editor, jsgraph(), zone());
162 :
163 1 : load_elimination.Reduce(graph()->start());
164 :
165 2 : Node* store = effect = graph()->NewNode(simplified()->StoreField(access),
166 : object, value, effect, control);
167 1 : load_elimination.Reduce(store);
168 :
169 1 : Node* load = effect = graph()->NewNode(simplified()->LoadField(access),
170 : object, effect, control);
171 7 : EXPECT_CALL(editor, ReplaceWithValue(load, value, store, _));
172 1 : Reduction r = load_elimination.Reduce(load);
173 1 : ASSERT_TRUE(r.Changed());
174 2 : EXPECT_EQ(value, r.replacement());
175 : }
176 :
177 15444 : TEST_F(LoadEliminationTest, StoreFieldAndKillFields) {
178 1 : Node* object = Parameter(Type::Any(), 0);
179 1 : Node* value = Parameter(Type::Any(), 1);
180 : Node* effect = graph()->start();
181 : Node* control = graph()->start();
182 :
183 : FieldAccess access1 = {kTaggedBase, kTaggedSize,
184 : MaybeHandle<Name>(), MaybeHandle<Map>(),
185 : Type::Any(), MachineType::AnyTagged(),
186 : kNoWriteBarrier};
187 :
188 : // Offset that out of field cache size.
189 : FieldAccess access2 = {kTaggedBase, 2048 * kTaggedSize,
190 : MaybeHandle<Name>(), MaybeHandle<Map>(),
191 : Type::Any(), MachineType::AnyTagged(),
192 : kNoWriteBarrier};
193 :
194 1 : StrictMock<MockAdvancedReducerEditor> editor;
195 : LoadElimination load_elimination(&editor, jsgraph(), zone());
196 :
197 1 : load_elimination.Reduce(graph()->start());
198 :
199 1 : Node* store1 = effect = graph()->NewNode(simplified()->StoreField(access1),
200 : object, value, effect, control);
201 1 : load_elimination.Reduce(store1);
202 :
203 : // Invalidate caches of object.
204 1 : Node* store2 = effect = graph()->NewNode(simplified()->StoreField(access2),
205 : object, value, effect, control);
206 1 : load_elimination.Reduce(store2);
207 :
208 1 : Node* store3 = graph()->NewNode(simplified()->StoreField(access1),
209 1 : object, value, effect, control);
210 :
211 1 : Reduction r = load_elimination.Reduce(store3);
212 :
213 : // store3 shall not be replaced, since caches were invalidated.
214 2 : EXPECT_EQ(store3, r.replacement());
215 1 : }
216 :
217 15444 : TEST_F(LoadEliminationTest, StoreFieldAndStoreElementAndLoadField) {
218 1 : Node* object = Parameter(Type::Any(), 0);
219 1 : Node* value = Parameter(Type::Any(), 1);
220 1 : Node* index = Parameter(Type::UnsignedSmall(), 2);
221 : Node* effect = graph()->start();
222 : Node* control = graph()->start();
223 : FieldAccess access = {kTaggedBase, kTaggedSize,
224 : MaybeHandle<Name>(), MaybeHandle<Map>(),
225 : Type::Any(), MachineType::AnyTagged(),
226 : kNoWriteBarrier};
227 :
228 1 : StrictMock<MockAdvancedReducerEditor> editor;
229 : LoadElimination load_elimination(&editor, jsgraph(), zone());
230 :
231 1 : load_elimination.Reduce(graph()->start());
232 :
233 2 : Node* store1 = effect = graph()->NewNode(simplified()->StoreField(access),
234 : object, value, effect, control);
235 1 : load_elimination.Reduce(store1);
236 :
237 1 : Node* store2 = effect = graph()->NewNode(
238 2 : simplified()->StoreElement(AccessBuilder::ForFixedArrayElement()), object,
239 : index, object, effect, control);
240 1 : load_elimination.Reduce(store2);
241 :
242 1 : Node* load = effect = graph()->NewNode(simplified()->LoadField(access),
243 : object, effect, control);
244 7 : EXPECT_CALL(editor, ReplaceWithValue(load, value, store2, _));
245 1 : Reduction r = load_elimination.Reduce(load);
246 1 : ASSERT_TRUE(r.Changed());
247 2 : EXPECT_EQ(value, r.replacement());
248 : }
249 :
250 15444 : TEST_F(LoadEliminationTest, LoadElementOnTrueBranchOfDiamond) {
251 1 : Node* object = Parameter(Type::Any(), 0);
252 1 : Node* index = Parameter(Type::UnsignedSmall(), 1);
253 1 : Node* check = Parameter(Type::Boolean(), 2);
254 : Node* effect = graph()->start();
255 : Node* control = graph()->start();
256 : ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
257 : MachineType::AnyTagged(), kNoWriteBarrier};
258 :
259 1 : StrictMock<MockAdvancedReducerEditor> editor;
260 : LoadElimination load_elimination(&editor, jsgraph(), zone());
261 :
262 1 : load_elimination.Reduce(graph()->start());
263 :
264 1 : Node* branch = graph()->NewNode(common()->Branch(), check, control);
265 :
266 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
267 1 : Node* etrue = graph()->NewNode(simplified()->LoadElement(access), object,
268 : index, effect, if_true);
269 1 : load_elimination.Reduce(etrue);
270 :
271 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
272 : Node* efalse = effect;
273 :
274 1 : control = graph()->NewNode(common()->Merge(2), if_true, if_false);
275 1 : effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
276 1 : load_elimination.Reduce(effect);
277 :
278 1 : Node* load = graph()->NewNode(simplified()->LoadElement(access), object,
279 1 : index, effect, control);
280 1 : Reduction r = load_elimination.Reduce(load);
281 1 : ASSERT_TRUE(r.Changed());
282 2 : EXPECT_EQ(load, r.replacement());
283 : }
284 :
285 15444 : TEST_F(LoadEliminationTest, LoadElementOnFalseBranchOfDiamond) {
286 1 : Node* object = Parameter(Type::Any(), 0);
287 1 : Node* index = Parameter(Type::UnsignedSmall(), 1);
288 1 : Node* check = Parameter(Type::Boolean(), 2);
289 : Node* effect = graph()->start();
290 : Node* control = graph()->start();
291 : ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Any(),
292 : MachineType::AnyTagged(), kNoWriteBarrier};
293 :
294 1 : StrictMock<MockAdvancedReducerEditor> editor;
295 : LoadElimination load_elimination(&editor, jsgraph(), zone());
296 :
297 1 : load_elimination.Reduce(graph()->start());
298 :
299 1 : Node* branch = graph()->NewNode(common()->Branch(), check, control);
300 :
301 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
302 : Node* etrue = effect;
303 :
304 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
305 1 : Node* efalse = graph()->NewNode(simplified()->LoadElement(access), object,
306 : index, effect, if_false);
307 1 : load_elimination.Reduce(efalse);
308 :
309 1 : control = graph()->NewNode(common()->Merge(2), if_true, if_false);
310 1 : effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
311 1 : load_elimination.Reduce(effect);
312 :
313 1 : Node* load = graph()->NewNode(simplified()->LoadElement(access), object,
314 1 : index, effect, control);
315 1 : Reduction r = load_elimination.Reduce(load);
316 1 : ASSERT_TRUE(r.Changed());
317 2 : EXPECT_EQ(load, r.replacement());
318 : }
319 :
320 15444 : TEST_F(LoadEliminationTest, LoadFieldOnFalseBranchOfDiamond) {
321 1 : Node* object = Parameter(Type::Any(), 0);
322 1 : Node* check = Parameter(Type::Boolean(), 1);
323 : Node* effect = graph()->start();
324 : Node* control = graph()->start();
325 : FieldAccess const access = {kTaggedBase, kTaggedSize,
326 : MaybeHandle<Name>(), MaybeHandle<Map>(),
327 : Type::Any(), MachineType::AnyTagged(),
328 : kNoWriteBarrier};
329 :
330 1 : StrictMock<MockAdvancedReducerEditor> editor;
331 : LoadElimination load_elimination(&editor, jsgraph(), zone());
332 :
333 1 : load_elimination.Reduce(graph()->start());
334 :
335 1 : Node* branch = graph()->NewNode(common()->Branch(), check, control);
336 :
337 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
338 : Node* etrue = effect;
339 :
340 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
341 1 : Node* efalse = graph()->NewNode(simplified()->LoadField(access), object,
342 : effect, if_false);
343 1 : load_elimination.Reduce(efalse);
344 :
345 1 : control = graph()->NewNode(common()->Merge(2), if_true, if_false);
346 1 : effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
347 1 : load_elimination.Reduce(effect);
348 :
349 1 : Node* load = graph()->NewNode(simplified()->LoadField(access), object, effect,
350 1 : control);
351 1 : Reduction r = load_elimination.Reduce(load);
352 1 : ASSERT_TRUE(r.Changed());
353 2 : EXPECT_EQ(load, r.replacement());
354 : }
355 :
356 15444 : TEST_F(LoadEliminationTest, LoadFieldOnTrueBranchOfDiamond) {
357 1 : Node* object = Parameter(Type::Any(), 0);
358 1 : Node* check = Parameter(Type::Boolean(), 1);
359 : Node* effect = graph()->start();
360 : Node* control = graph()->start();
361 : FieldAccess const access = {kTaggedBase, kTaggedSize,
362 : MaybeHandle<Name>(), MaybeHandle<Map>(),
363 : Type::Any(), MachineType::AnyTagged(),
364 : kNoWriteBarrier};
365 :
366 1 : StrictMock<MockAdvancedReducerEditor> editor;
367 : LoadElimination load_elimination(&editor, jsgraph(), zone());
368 :
369 1 : load_elimination.Reduce(graph()->start());
370 :
371 1 : Node* branch = graph()->NewNode(common()->Branch(), check, control);
372 :
373 1 : Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
374 1 : Node* etrue = graph()->NewNode(simplified()->LoadField(access), object,
375 : effect, if_true);
376 1 : load_elimination.Reduce(etrue);
377 :
378 1 : Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
379 : Node* efalse = effect;
380 :
381 1 : control = graph()->NewNode(common()->Merge(2), if_true, if_false);
382 1 : effect = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, control);
383 1 : load_elimination.Reduce(effect);
384 :
385 1 : Node* load = graph()->NewNode(simplified()->LoadField(access), object, effect,
386 1 : control);
387 1 : Reduction r = load_elimination.Reduce(load);
388 1 : ASSERT_TRUE(r.Changed());
389 2 : EXPECT_EQ(load, r.replacement());
390 : }
391 :
392 15444 : TEST_F(LoadEliminationTest, LoadFieldWithTypeMismatch) {
393 1 : Node* object = Parameter(Type::Any(), 0);
394 1 : Node* value = Parameter(Type::Signed32(), 1);
395 : Node* effect = graph()->start();
396 : Node* control = graph()->start();
397 : FieldAccess const access = {kTaggedBase, kTaggedSize,
398 : MaybeHandle<Name>(), MaybeHandle<Map>(),
399 : Type::Unsigned31(), MachineType::AnyTagged(),
400 : kNoWriteBarrier};
401 :
402 1 : StrictMock<MockAdvancedReducerEditor> editor;
403 : LoadElimination load_elimination(&editor, jsgraph(), zone());
404 :
405 1 : load_elimination.Reduce(graph()->start());
406 :
407 1 : effect = graph()->NewNode(simplified()->StoreField(access), object, value,
408 : effect, control);
409 1 : load_elimination.Reduce(effect);
410 :
411 1 : Node* load = graph()->NewNode(simplified()->LoadField(access), object, effect,
412 : control);
413 9 : EXPECT_CALL(editor, ReplaceWithValue(load, IsTypeGuard(value, _), _, _));
414 1 : Reduction r = load_elimination.Reduce(load);
415 1 : ASSERT_TRUE(r.Changed());
416 7 : EXPECT_THAT(r.replacement(), IsTypeGuard(value, _));
417 : }
418 :
419 15444 : TEST_F(LoadEliminationTest, LoadElementWithTypeMismatch) {
420 1 : Node* object = Parameter(Type::Any(), 0);
421 1 : Node* index = Parameter(Type::UnsignedSmall(), 1);
422 1 : Node* value = Parameter(Type::Signed32(), 2);
423 : Node* effect = graph()->start();
424 : Node* control = graph()->start();
425 : ElementAccess const access = {kTaggedBase, kTaggedSize, Type::Unsigned31(),
426 : MachineType::AnyTagged(), kNoWriteBarrier};
427 :
428 1 : StrictMock<MockAdvancedReducerEditor> editor;
429 : LoadElimination load_elimination(&editor, jsgraph(), zone());
430 :
431 1 : load_elimination.Reduce(graph()->start());
432 :
433 1 : effect = graph()->NewNode(simplified()->StoreElement(access), object, index,
434 : value, effect, control);
435 1 : load_elimination.Reduce(effect);
436 :
437 1 : Node* load = graph()->NewNode(simplified()->LoadElement(access), object,
438 1 : index, effect, control);
439 1 : Reduction r = load_elimination.Reduce(load);
440 1 : ASSERT_TRUE(r.Changed());
441 2 : EXPECT_EQ(load, r.replacement());
442 : }
443 :
444 15444 : TEST_F(LoadEliminationTest, AliasAnalysisForFinishRegion) {
445 1 : Node* value0 = Parameter(Type::Signed32(), 0);
446 1 : Node* value1 = Parameter(Type::Signed32(), 1);
447 : Node* effect = graph()->start();
448 : Node* control = graph()->start();
449 : FieldAccess const access = {kTaggedBase, kTaggedSize,
450 : MaybeHandle<Name>(), MaybeHandle<Map>(),
451 : Type::Signed32(), MachineType::AnyTagged(),
452 : kNoWriteBarrier};
453 :
454 1 : StrictMock<MockAdvancedReducerEditor> editor;
455 : LoadElimination load_elimination(&editor, jsgraph(), zone());
456 :
457 1 : load_elimination.Reduce(effect);
458 :
459 1 : effect = graph()->NewNode(
460 : common()->BeginRegion(RegionObservability::kNotObservable), effect);
461 1 : load_elimination.Reduce(effect);
462 :
463 2 : Node* object0 = effect = graph()->NewNode(
464 : simplified()->Allocate(Type::Any(), AllocationType::kYoung),
465 : jsgraph()->Constant(16), effect, control);
466 1 : load_elimination.Reduce(effect);
467 :
468 : Node* region0 = effect =
469 1 : graph()->NewNode(common()->FinishRegion(), object0, effect);
470 1 : load_elimination.Reduce(effect);
471 :
472 1 : effect = graph()->NewNode(
473 : common()->BeginRegion(RegionObservability::kNotObservable), effect);
474 1 : load_elimination.Reduce(effect);
475 :
476 1 : Node* object1 = effect = graph()->NewNode(
477 : simplified()->Allocate(Type::Any(), AllocationType::kYoung),
478 : jsgraph()->Constant(16), effect, control);
479 1 : load_elimination.Reduce(effect);
480 :
481 : Node* region1 = effect =
482 1 : graph()->NewNode(common()->FinishRegion(), object1, effect);
483 1 : load_elimination.Reduce(effect);
484 :
485 1 : effect = graph()->NewNode(simplified()->StoreField(access), region0, value0,
486 : effect, control);
487 1 : load_elimination.Reduce(effect);
488 :
489 1 : effect = graph()->NewNode(simplified()->StoreField(access), region1, value1,
490 : effect, control);
491 1 : load_elimination.Reduce(effect);
492 :
493 1 : Node* load = graph()->NewNode(simplified()->LoadField(access), region0,
494 : effect, control);
495 7 : EXPECT_CALL(editor, ReplaceWithValue(load, value0, effect, _));
496 1 : Reduction r = load_elimination.Reduce(load);
497 1 : ASSERT_TRUE(r.Changed());
498 2 : EXPECT_EQ(value0, r.replacement());
499 : }
500 :
501 : } // namespace compiler
502 : } // namespace internal
503 9264 : } // namespace v8
|
