Line data Source code
1 : // Copyright 2014 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/base/overflowing-math.h"
6 : #include "src/base/utils/random-number-generator.h"
7 : #include "src/compiler/js-graph.h"
8 : #include "src/compiler/machine-operator-reducer.h"
9 : #include "src/compiler/operator-properties.h"
10 : #include "src/compiler/typer.h"
11 : #include "src/objects-inl.h"
12 : #include "test/cctest/cctest.h"
13 : #include "test/cctest/compiler/value-helper.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace compiler {
18 :
19 : template <typename T>
20 : const Operator* NewConstantOperator(CommonOperatorBuilder* common,
21 : volatile T value);
22 :
23 : template <>
24 0 : const Operator* NewConstantOperator<int32_t>(CommonOperatorBuilder* common,
25 : volatile int32_t value) {
26 559150 : return common->Int32Constant(value);
27 : }
28 :
29 : template <>
30 0 : const Operator* NewConstantOperator<int64_t>(CommonOperatorBuilder* common,
31 : volatile int64_t value) {
32 286770 : return common->Int64Constant(value);
33 : }
34 :
35 : template <>
36 0 : const Operator* NewConstantOperator<double>(CommonOperatorBuilder* common,
37 : volatile double value) {
38 24015 : return common->Float64Constant(value);
39 : }
40 :
41 : template <>
42 0 : const Operator* NewConstantOperator<float>(CommonOperatorBuilder* common,
43 : volatile float value) {
44 132255 : return common->Float32Constant(value);
45 : }
46 :
47 : template <typename T>
48 : T ValueOfOperator(const Operator* op);
49 :
50 : template <>
51 0 : int32_t ValueOfOperator<int32_t>(const Operator* op) {
52 279665 : CHECK_EQ(IrOpcode::kInt32Constant, op->opcode());
53 279665 : return OpParameter<int32_t>(op);
54 : }
55 :
56 : template <>
57 0 : int64_t ValueOfOperator<int64_t>(const Operator* op) {
58 143380 : CHECK_EQ(IrOpcode::kInt64Constant, op->opcode());
59 143380 : return OpParameter<int64_t>(op);
60 : }
61 :
62 : template <>
63 0 : float ValueOfOperator<float>(const Operator* op) {
64 66135 : CHECK_EQ(IrOpcode::kFloat32Constant, op->opcode());
65 66135 : return OpParameter<float>(op);
66 : }
67 :
68 : template <>
69 0 : double ValueOfOperator<double>(const Operator* op) {
70 12015 : CHECK_EQ(IrOpcode::kFloat64Constant, op->opcode());
71 12015 : return OpParameter<double>(op);
72 : }
73 :
74 :
75 270 : class ReducerTester : public HandleAndZoneScope {
76 : public:
77 135 : explicit ReducerTester(int num_parameters = 0,
78 : MachineOperatorBuilder::Flags flags =
79 : MachineOperatorBuilder::kAllOptionalOps)
80 : : isolate(main_isolate()),
81 : binop(nullptr),
82 : unop(nullptr),
83 : machine(main_zone(), MachineType::PointerRepresentation(), flags),
84 : common(main_zone()),
85 : graph(main_zone()),
86 : javascript(main_zone()),
87 : jsgraph(isolate, &graph, &common, &javascript, nullptr, &machine),
88 135 : maxuint32(Constant<int32_t>(kMaxUInt32)),
89 945 : graph_reducer(main_zone(), &graph, jsgraph.Dead()) {
90 135 : Node* s = graph.NewNode(common.Start(num_parameters));
91 : graph.SetStart(s);
92 135 : }
93 :
94 : Isolate* isolate;
95 : const Operator* binop;
96 : const Operator* unop;
97 : MachineOperatorBuilder machine;
98 : CommonOperatorBuilder common;
99 : Graph graph;
100 : JSOperatorBuilder javascript;
101 : JSGraph jsgraph;
102 : Node* maxuint32;
103 : GraphReducer graph_reducer;
104 :
105 : template <typename T>
106 1002190 : Node* Constant(volatile T value) {
107 3006570 : return graph.NewNode(NewConstantOperator<T>(&common, value));
108 : }
109 :
110 : template <typename T>
111 : const T ValueOf(const Operator* op) {
112 : return ValueOfOperator<T>(op);
113 : }
114 :
115 : // Check that the reduction of this binop applied to constants {a} and {b}
116 : // yields the {expect} value.
117 : template <typename T>
118 500480 : void CheckFoldBinop(volatile T expect, volatile T a, volatile T b) {
119 500480 : CheckFoldBinop<T>(expect, Constant<T>(a), Constant<T>(b));
120 500480 : }
121 :
122 : // Check that the reduction of this binop applied to {a} and {b} yields
123 : // the {expect} value.
124 : template <typename T>
125 500565 : void CheckFoldBinop(volatile T expect, Node* a, Node* b) {
126 500565 : CHECK(binop);
127 500565 : Node* n = CreateBinopNode(a, b);
128 1001130 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
129 500565 : Reduction reduction = reducer.Reduce(n);
130 500565 : CHECK(reduction.Changed());
131 500565 : CHECK_NE(n, reduction.replacement());
132 : // Deal with NaNs.
133 500565 : if (expect == expect) {
134 : // We do not expect a NaN, check for equality.
135 497285 : CHECK_EQ(expect, ValueOf<T>(reduction.replacement()->op()));
136 : } else {
137 : // Check for NaN.
138 : T result = ValueOf<T>(reduction.replacement()->op());
139 3280 : CHECK_NE(result, result);
140 : }
141 500565 : }
142 :
143 : // Check that the reduction of this binop applied to {a} and {b} yields
144 : // the {expect} node.
145 150 : void CheckBinop(Node* expect, Node* a, Node* b) {
146 150 : CHECK(binop);
147 150 : Node* n = CreateBinopNode(a, b);
148 300 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
149 150 : Reduction reduction = reducer.Reduce(n);
150 150 : CHECK(reduction.Changed());
151 150 : CHECK_EQ(expect, reduction.replacement());
152 150 : }
153 :
154 : // Check that the reduction of this binop applied to {left} and {right} yields
155 : // this binop applied to {left_expect} and {right_expect}.
156 25 : void CheckFoldBinop(Node* left_expect, Node* right_expect, Node* left,
157 : Node* right) {
158 25 : CHECK(binop);
159 25 : Node* n = CreateBinopNode(left, right);
160 50 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
161 25 : Reduction reduction = reducer.Reduce(n);
162 25 : CHECK(reduction.Changed());
163 25 : CHECK_EQ(binop, reduction.replacement()->op());
164 25 : CHECK_EQ(left_expect, reduction.replacement()->InputAt(0));
165 25 : CHECK_EQ(right_expect, reduction.replacement()->InputAt(1));
166 25 : }
167 :
168 : // Check that the reduction of this binop applied to {left} and {right} yields
169 : // the {op_expect} applied to {left_expect} and {right_expect}.
170 : template <typename T>
171 15 : void CheckFoldBinop(volatile T left_expect, const Operator* op_expect,
172 : Node* right_expect, Node* left, Node* right) {
173 15 : CHECK(binop);
174 15 : Node* n = CreateBinopNode(left, right);
175 30 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
176 15 : Reduction r = reducer.Reduce(n);
177 15 : CHECK(r.Changed());
178 15 : CHECK_EQ(op_expect->opcode(), r.replacement()->op()->opcode());
179 15 : CHECK_EQ(left_expect, ValueOf<T>(r.replacement()->InputAt(0)->op()));
180 15 : CHECK_EQ(right_expect, r.replacement()->InputAt(1));
181 15 : }
182 :
183 : // Check that the reduction of this binop applied to {left} and {right} yields
184 : // the {op_expect} applied to {left_expect} and {right_expect}.
185 : template <typename T>
186 615 : void CheckFoldBinop(Node* left_expect, const Operator* op_expect,
187 : volatile T right_expect, Node* left, Node* right) {
188 615 : CHECK(binop);
189 615 : Node* n = CreateBinopNode(left, right);
190 1230 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
191 615 : Reduction r = reducer.Reduce(n);
192 615 : CHECK(r.Changed());
193 615 : CHECK_EQ(op_expect->opcode(), r.replacement()->op()->opcode());
194 615 : CHECK_EQ(OperatorProperties::GetTotalInputCount(op_expect),
195 : r.replacement()->InputCount());
196 615 : CHECK_EQ(left_expect, r.replacement()->InputAt(0));
197 615 : CHECK_EQ(right_expect, ValueOf<T>(r.replacement()->InputAt(1)->op()));
198 615 : }
199 :
200 : // Check that if the given constant appears on the left, the reducer will
201 : // swap it to be on the right.
202 : template <typename T>
203 65 : void CheckPutConstantOnRight(volatile T constant) {
204 : // TODO(titzer): CHECK(binop->HasProperty(Operator::kCommutative));
205 65 : Node* p = Parameter();
206 65 : Node* k = Constant<T>(constant);
207 : {
208 65 : Node* n = CreateBinopNode(k, p);
209 130 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
210 65 : Reduction reduction = reducer.Reduce(n);
211 65 : CHECK(!reduction.Changed() || reduction.replacement() == n);
212 65 : CHECK_EQ(p, n->InputAt(0));
213 65 : CHECK_EQ(k, n->InputAt(1));
214 : }
215 : {
216 65 : Node* n = CreateBinopNode(p, k);
217 130 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
218 65 : Reduction reduction = reducer.Reduce(n);
219 65 : CHECK(!reduction.Changed());
220 65 : CHECK_EQ(p, n->InputAt(0));
221 65 : CHECK_EQ(k, n->InputAt(1));
222 : }
223 65 : }
224 :
225 : // Check that if the given constant appears on the left, the reducer will
226 : // *NOT* swap it to be on the right.
227 : template <typename T>
228 400 : void CheckDontPutConstantOnRight(volatile T constant) {
229 800 : CHECK(!binop->HasProperty(Operator::kCommutative));
230 400 : Node* p = Parameter();
231 400 : Node* k = Constant<T>(constant);
232 400 : Node* n = CreateBinopNode(k, p);
233 800 : MachineOperatorReducer reducer(&graph_reducer, &jsgraph);
234 400 : Reduction reduction = reducer.Reduce(n);
235 400 : CHECK(!reduction.Changed());
236 400 : CHECK_EQ(k, n->InputAt(0));
237 400 : CHECK_EQ(p, n->InputAt(1));
238 400 : }
239 :
240 625 : Node* Parameter(int32_t index = 0) {
241 1250 : return graph.NewNode(common.Parameter(index), graph.start());
242 : }
243 :
244 : private:
245 501900 : Node* CreateBinopNode(Node* left, Node* right) {
246 1003800 : if (binop->ControlInputCount() > 0) {
247 132990 : return graph.NewNode(binop, left, right, graph.start());
248 : } else {
249 870810 : return graph.NewNode(binop, left, right);
250 : }
251 : }
252 : };
253 :
254 :
255 26644 : TEST(ReduceWord32And) {
256 5 : ReducerTester R;
257 5 : R.binop = R.machine.Word32And();
258 :
259 585 : FOR_INT32_INPUTS(x) {
260 17110 : FOR_INT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x & y, x, y); }
261 : }
262 :
263 5 : R.CheckPutConstantOnRight(33);
264 5 : R.CheckPutConstantOnRight(44000);
265 :
266 5 : Node* x = R.Parameter();
267 5 : Node* zero = R.Constant<int32_t>(0);
268 5 : Node* minus_1 = R.Constant<int32_t>(-1);
269 :
270 5 : R.CheckBinop(zero, x, zero); // x & 0 => 0
271 5 : R.CheckBinop(zero, zero, x); // 0 & x => 0
272 5 : R.CheckBinop(x, x, minus_1); // x & -1 => 0
273 5 : R.CheckBinop(x, minus_1, x); // -1 & x => 0
274 5 : R.CheckBinop(x, x, x); // x & x => x
275 5 : }
276 :
277 :
278 26644 : TEST(ReduceWord32Or) {
279 5 : ReducerTester R;
280 5 : R.binop = R.machine.Word32Or();
281 :
282 585 : FOR_INT32_INPUTS(x) {
283 17110 : FOR_INT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x | y, x, y); }
284 : }
285 :
286 5 : R.CheckPutConstantOnRight(36);
287 5 : R.CheckPutConstantOnRight(44001);
288 :
289 5 : Node* x = R.Parameter();
290 5 : Node* zero = R.Constant<int32_t>(0);
291 5 : Node* minus_1 = R.Constant<int32_t>(-1);
292 :
293 5 : R.CheckBinop(x, x, zero); // x & 0 => x
294 5 : R.CheckBinop(x, zero, x); // 0 & x => x
295 5 : R.CheckBinop(minus_1, x, minus_1); // x & -1 => -1
296 5 : R.CheckBinop(minus_1, minus_1, x); // -1 & x => -1
297 5 : R.CheckBinop(x, x, x); // x & x => x
298 5 : }
299 :
300 :
301 26644 : TEST(ReduceWord32Xor) {
302 5 : ReducerTester R;
303 5 : R.binop = R.machine.Word32Xor();
304 :
305 585 : FOR_INT32_INPUTS(x) {
306 17110 : FOR_INT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x ^ y, x, y); }
307 : }
308 :
309 5 : R.CheckPutConstantOnRight(39);
310 5 : R.CheckPutConstantOnRight(4403);
311 :
312 5 : Node* x = R.Parameter();
313 5 : Node* zero = R.Constant<int32_t>(0);
314 :
315 5 : R.CheckBinop(x, x, zero); // x ^ 0 => x
316 5 : R.CheckBinop(x, zero, x); // 0 ^ x => x
317 5 : R.CheckFoldBinop<int32_t>(0, x, x); // x ^ x => 0
318 5 : }
319 :
320 :
321 26644 : TEST(ReduceWord32Shl) {
322 5 : ReducerTester R;
323 5 : R.binop = R.machine.Word32Shl();
324 :
325 : // TODO(titzer): out of range shifts
326 585 : FOR_INT32_INPUTS(x) {
327 18850 : for (int y = 0; y < 32; y++) {
328 9280 : R.CheckFoldBinop<int32_t>(base::ShlWithWraparound(x, y), x, y);
329 : }
330 : }
331 :
332 5 : R.CheckDontPutConstantOnRight(44);
333 :
334 5 : Node* x = R.Parameter();
335 5 : Node* zero = R.Constant<int32_t>(0);
336 :
337 5 : R.CheckBinop(x, x, zero); // x << 0 => x
338 5 : }
339 :
340 26644 : TEST(ReduceWord64Shl) {
341 5 : ReducerTester R;
342 5 : R.binop = R.machine.Word64Shl();
343 :
344 815 : FOR_INT64_INPUTS(x) {
345 52245 : for (int64_t y = 0; y < 64; y++) {
346 25920 : R.CheckFoldBinop<int64_t>(base::ShlWithWraparound(x, y), x, y);
347 : }
348 : }
349 :
350 5 : R.CheckDontPutConstantOnRight(44);
351 :
352 5 : Node* x = R.Parameter();
353 5 : Node* zero = R.Constant<int64_t>(0);
354 :
355 5 : R.CheckBinop(x, x, zero); // x << 0 => x
356 5 : }
357 :
358 26644 : TEST(ReduceWord32Shr) {
359 5 : ReducerTester R;
360 5 : R.binop = R.machine.Word32Shr();
361 :
362 : // TODO(titzer): test out of range shifts
363 585 : FOR_UINT32_INPUTS(x) {
364 18850 : for (uint32_t y = 0; y < 32; y++) {
365 9280 : R.CheckFoldBinop<int32_t>(x >> y, x, y);
366 : }
367 : }
368 :
369 5 : R.CheckDontPutConstantOnRight(44);
370 :
371 5 : Node* x = R.Parameter();
372 5 : Node* zero = R.Constant<int32_t>(0);
373 :
374 5 : R.CheckBinop(x, x, zero); // x >>> 0 => x
375 5 : }
376 :
377 26644 : TEST(ReduceWord64Shr) {
378 5 : ReducerTester R;
379 5 : R.binop = R.machine.Word64Shr();
380 :
381 815 : FOR_UINT64_INPUTS(x) {
382 52245 : for (uint64_t y = 0; y < 64; y++) {
383 25920 : R.CheckFoldBinop<int64_t>(x >> y, x, y);
384 : }
385 : }
386 :
387 5 : R.CheckDontPutConstantOnRight(44);
388 :
389 5 : Node* x = R.Parameter();
390 5 : Node* zero = R.Constant<int64_t>(0);
391 :
392 5 : R.CheckBinop(x, x, zero); // x >>> 0 => x
393 5 : }
394 :
395 26644 : TEST(ReduceWord32Sar) {
396 5 : ReducerTester R;
397 5 : R.binop = R.machine.Word32Sar();
398 :
399 : // TODO(titzer): test out of range shifts
400 585 : FOR_INT32_INPUTS(x) {
401 18850 : for (int32_t y = 0; y < 32; y++) {
402 9280 : R.CheckFoldBinop<int32_t>(x >> y, x, y);
403 : }
404 : }
405 :
406 5 : R.CheckDontPutConstantOnRight(44);
407 :
408 5 : Node* x = R.Parameter();
409 5 : Node* zero = R.Constant<int32_t>(0);
410 :
411 5 : R.CheckBinop(x, x, zero); // x >> 0 => x
412 5 : }
413 :
414 26644 : TEST(ReduceWord64Sar) {
415 5 : ReducerTester R;
416 5 : R.binop = R.machine.Word64Sar();
417 :
418 815 : FOR_INT64_INPUTS(x) {
419 52245 : for (int64_t y = 0; y < 64; y++) {
420 25920 : R.CheckFoldBinop<int64_t>(x >> y, x, y);
421 : }
422 : }
423 :
424 5 : R.CheckDontPutConstantOnRight(44);
425 :
426 5 : Node* x = R.Parameter();
427 5 : Node* zero = R.Constant<int64_t>(0);
428 :
429 5 : R.CheckBinop(x, x, zero); // x >> 0 => x
430 5 : }
431 :
432 15 : static void CheckJsShift(ReducerTester* R) {
433 15 : CHECK(R->machine.Word32ShiftIsSafe());
434 :
435 15 : Node* x = R->Parameter(0);
436 15 : Node* y = R->Parameter(1);
437 15 : Node* thirty_one = R->Constant<int32_t>(0x1F);
438 : Node* y_and_thirty_one =
439 15 : R->graph.NewNode(R->machine.Word32And(), y, thirty_one);
440 :
441 : // If the underlying machine shift instructions 'and' their right operand
442 : // with 0x1F then: x << (y & 0x1F) => x << y
443 15 : R->CheckFoldBinop(x, y, x, y_and_thirty_one);
444 15 : }
445 :
446 :
447 26644 : TEST(ReduceJsShifts) {
448 5 : ReducerTester R(0, MachineOperatorBuilder::kWord32ShiftIsSafe);
449 :
450 5 : R.binop = R.machine.Word32Shl();
451 5 : CheckJsShift(&R);
452 :
453 5 : R.binop = R.machine.Word32Shr();
454 5 : CheckJsShift(&R);
455 :
456 5 : R.binop = R.machine.Word32Sar();
457 5 : CheckJsShift(&R);
458 5 : }
459 :
460 :
461 26644 : TEST(Word32Equal) {
462 5 : ReducerTester R;
463 5 : R.binop = R.machine.Word32Equal();
464 :
465 585 : FOR_INT32_INPUTS(x) {
466 17110 : FOR_INT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x == y ? 1 : 0, x, y); }
467 : }
468 :
469 5 : R.CheckPutConstantOnRight(48);
470 5 : R.CheckPutConstantOnRight(-48);
471 :
472 5 : Node* x = R.Parameter(0);
473 5 : Node* y = R.Parameter(1);
474 5 : Node* zero = R.Constant<int32_t>(0);
475 5 : Node* sub = R.graph.NewNode(R.machine.Int32Sub(), x, y);
476 :
477 5 : R.CheckFoldBinop<int32_t>(1, x, x); // x == x => 1
478 5 : R.CheckFoldBinop(x, y, sub, zero); // x - y == 0 => x == y
479 5 : R.CheckFoldBinop(x, y, zero, sub); // 0 == x - y => x == y
480 5 : }
481 :
482 :
483 26644 : TEST(ReduceInt32Add) {
484 5 : ReducerTester R;
485 5 : R.binop = R.machine.Int32Add();
486 :
487 585 : FOR_INT32_INPUTS(x) {
488 33930 : FOR_INT32_INPUTS(y) {
489 16820 : R.CheckFoldBinop<int32_t>(base::AddWithWraparound(x, y), x, y);
490 : }
491 : }
492 :
493 5 : R.CheckPutConstantOnRight(41);
494 5 : R.CheckPutConstantOnRight(4407);
495 :
496 5 : Node* x = R.Parameter();
497 5 : Node* zero = R.Constant<int32_t>(0);
498 :
499 5 : R.CheckBinop(x, x, zero); // x + 0 => x
500 5 : R.CheckBinop(x, zero, x); // 0 + x => x
501 5 : }
502 :
503 26644 : TEST(ReduceInt64Add) {
504 5 : ReducerTester R;
505 5 : R.binop = R.machine.Int64Add();
506 :
507 815 : FOR_INT64_INPUTS(x) {
508 66015 : FOR_INT64_INPUTS(y) {
509 32805 : R.CheckFoldBinop<int64_t>(base::AddWithWraparound(x, y), x, y);
510 : }
511 : }
512 :
513 5 : R.CheckPutConstantOnRight(41);
514 :
515 5 : Node* x = R.Parameter();
516 5 : Node* zero = R.Constant<int64_t>(0);
517 5 : R.CheckBinop(x, x, zero); // x + 0 => x
518 5 : R.CheckBinop(x, zero, x); // 0 + x => x
519 5 : }
520 :
521 26644 : TEST(ReduceInt32Sub) {
522 5 : ReducerTester R;
523 5 : R.binop = R.machine.Int32Sub();
524 :
525 585 : FOR_INT32_INPUTS(x) {
526 33930 : FOR_INT32_INPUTS(y) {
527 16820 : R.CheckFoldBinop<int32_t>(base::SubWithWraparound(x, y), x, y);
528 : }
529 : }
530 :
531 5 : R.CheckDontPutConstantOnRight(412);
532 :
533 5 : Node* x = R.Parameter();
534 5 : Node* zero = R.Constant<int32_t>(0);
535 :
536 5 : R.CheckBinop(x, x, zero); // x - 0 => x
537 5 : }
538 :
539 26644 : TEST(ReduceInt64Sub) {
540 5 : ReducerTester R;
541 5 : R.binop = R.machine.Int64Sub();
542 :
543 815 : FOR_INT64_INPUTS(x) {
544 66015 : FOR_INT64_INPUTS(y) {
545 32805 : R.CheckFoldBinop<int64_t>(base::SubWithWraparound(x, y), x, y);
546 : }
547 : }
548 :
549 5 : R.CheckDontPutConstantOnRight(42);
550 :
551 5 : Node* x = R.Parameter();
552 5 : Node* zero = R.Constant<int64_t>(0);
553 :
554 5 : R.CheckBinop(x, x, zero); // x - 0 => x
555 5 : R.CheckFoldBinop<int64_t>(0, x, x); // x - x => 0
556 :
557 5 : Node* k = R.Constant<int64_t>(6);
558 :
559 5 : R.CheckFoldBinop<int64_t>(x, R.machine.Int64Add(), -6, x,
560 5 : k); // x - K => x + -K
561 5 : }
562 :
563 26644 : TEST(ReduceInt32Mul) {
564 5 : ReducerTester R;
565 5 : R.binop = R.machine.Int32Mul();
566 :
567 585 : FOR_INT32_INPUTS(x) {
568 33930 : FOR_INT32_INPUTS(y) {
569 16820 : R.CheckFoldBinop<int32_t>(base::MulWithWraparound(x, y), x, y);
570 : }
571 : }
572 :
573 5 : R.CheckPutConstantOnRight(4111);
574 5 : R.CheckPutConstantOnRight(-4407);
575 :
576 5 : Node* x = R.Parameter();
577 5 : Node* zero = R.Constant<int32_t>(0);
578 5 : Node* one = R.Constant<int32_t>(1);
579 5 : Node* minus_one = R.Constant<int32_t>(-1);
580 :
581 5 : R.CheckBinop(zero, x, zero); // x * 0 => 0
582 5 : R.CheckBinop(zero, zero, x); // 0 * x => 0
583 5 : R.CheckBinop(x, x, one); // x * 1 => x
584 5 : R.CheckBinop(x, one, x); // 1 * x => x
585 5 : R.CheckFoldBinop<int32_t>(0, R.machine.Int32Sub(), x, minus_one,
586 5 : x); // -1 * x => 0 - x
587 5 : R.CheckFoldBinop<int32_t>(0, R.machine.Int32Sub(), x, x,
588 5 : minus_one); // x * -1 => 0 - x
589 :
590 305 : for (int32_t n = 1; n < 31; ++n) {
591 150 : Node* multiplier = R.Constant<int32_t>(1 << n);
592 150 : R.CheckFoldBinop<int32_t>(x, R.machine.Word32Shl(), n, x,
593 150 : multiplier); // x * 2^n => x << n
594 150 : R.CheckFoldBinop<int32_t>(x, R.machine.Word32Shl(), n, multiplier,
595 150 : x); // 2^n * x => x << n
596 : }
597 5 : }
598 :
599 :
600 26644 : TEST(ReduceInt32Div) {
601 5 : ReducerTester R;
602 5 : R.binop = R.machine.Int32Div();
603 :
604 585 : FOR_INT32_INPUTS(x) {
605 33930 : FOR_INT32_INPUTS(y) {
606 16820 : if (y == 0) continue; // TODO(titzer): test / 0
607 : int32_t r = y == -1 ? base::NegateWithWraparound(x)
608 32770 : : x / y; // INT_MIN / -1 may explode in C
609 16530 : R.CheckFoldBinop<int32_t>(r, x, y);
610 : }
611 : }
612 :
613 5 : R.CheckDontPutConstantOnRight(41111);
614 5 : R.CheckDontPutConstantOnRight(-44071);
615 :
616 5 : Node* x = R.Parameter();
617 5 : Node* one = R.Constant<int32_t>(1);
618 5 : Node* minus_one = R.Constant<int32_t>(-1);
619 :
620 5 : R.CheckBinop(x, x, one); // x / 1 => x
621 : // TODO(titzer): // 0 / x => 0 if x != 0
622 : // TODO(titzer): // x / 2^n => x >> n and round
623 5 : R.CheckFoldBinop<int32_t>(0, R.machine.Int32Sub(), x, x,
624 5 : minus_one); // x / -1 => 0 - x
625 5 : }
626 :
627 :
628 26644 : TEST(ReduceUint32Div) {
629 5 : ReducerTester R;
630 5 : R.binop = R.machine.Uint32Div();
631 :
632 585 : FOR_UINT32_INPUTS(x) {
633 33930 : FOR_UINT32_INPUTS(y) {
634 16820 : if (y == 0) continue; // TODO(titzer): test / 0
635 16530 : R.CheckFoldBinop<int32_t>(x / y, x, y);
636 : }
637 : }
638 :
639 5 : R.CheckDontPutConstantOnRight(41311);
640 5 : R.CheckDontPutConstantOnRight(-44371);
641 :
642 5 : Node* x = R.Parameter();
643 5 : Node* one = R.Constant<int32_t>(1);
644 :
645 5 : R.CheckBinop(x, x, one); // x / 1 => x
646 : // TODO(titzer): // 0 / x => 0 if x != 0
647 :
648 315 : for (uint32_t n = 1; n < 32; ++n) {
649 155 : Node* divisor = R.Constant<int32_t>(1u << n);
650 155 : R.CheckFoldBinop<int32_t>(x, R.machine.Word32Shr(), n, x,
651 155 : divisor); // x / 2^n => x >> n
652 : }
653 5 : }
654 :
655 :
656 26644 : TEST(ReduceInt32Mod) {
657 5 : ReducerTester R;
658 5 : R.binop = R.machine.Int32Mod();
659 :
660 585 : FOR_INT32_INPUTS(x) {
661 33930 : FOR_INT32_INPUTS(y) {
662 16820 : if (y == 0) continue; // TODO(titzer): test % 0
663 16530 : int32_t r = y == -1 ? 0 : x % y; // INT_MIN % -1 may explode in C
664 16530 : R.CheckFoldBinop<int32_t>(r, x, y);
665 : }
666 : }
667 :
668 5 : R.CheckDontPutConstantOnRight(413);
669 5 : R.CheckDontPutConstantOnRight(-4401);
670 :
671 5 : Node* x = R.Parameter();
672 5 : Node* one = R.Constant<int32_t>(1);
673 :
674 5 : R.CheckFoldBinop<int32_t>(0, x, one); // x % 1 => 0
675 : // TODO(titzer): // x % 2^n => x & 2^n-1 and round
676 5 : }
677 :
678 :
679 26644 : TEST(ReduceUint32Mod) {
680 5 : ReducerTester R;
681 5 : R.binop = R.machine.Uint32Mod();
682 :
683 585 : FOR_UINT32_INPUTS(x) {
684 33930 : FOR_UINT32_INPUTS(y) {
685 16820 : if (y == 0) continue; // TODO(titzer): test x % 0
686 16530 : R.CheckFoldBinop<int32_t>(x % y, x, y);
687 : }
688 : }
689 :
690 5 : R.CheckDontPutConstantOnRight(417);
691 5 : R.CheckDontPutConstantOnRight(-4371);
692 :
693 5 : Node* x = R.Parameter();
694 5 : Node* one = R.Constant<int32_t>(1);
695 :
696 5 : R.CheckFoldBinop<int32_t>(0, x, one); // x % 1 => 0
697 :
698 315 : for (uint32_t n = 1; n < 32; ++n) {
699 155 : Node* divisor = R.Constant<int32_t>(1u << n);
700 155 : R.CheckFoldBinop<int32_t>(x, R.machine.Word32And(), (1u << n) - 1, x,
701 155 : divisor); // x % 2^n => x & 2^n-1
702 : }
703 5 : }
704 :
705 :
706 26644 : TEST(ReduceInt32LessThan) {
707 5 : ReducerTester R;
708 5 : R.binop = R.machine.Int32LessThan();
709 :
710 585 : FOR_INT32_INPUTS(x) {
711 17110 : FOR_INT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x < y ? 1 : 0, x, y); }
712 : }
713 :
714 5 : R.CheckDontPutConstantOnRight(41399);
715 5 : R.CheckDontPutConstantOnRight(-440197);
716 :
717 5 : Node* x = R.Parameter(0);
718 :
719 5 : R.CheckFoldBinop<int32_t>(0, x, x); // x < x => 0
720 5 : }
721 :
722 :
723 26644 : TEST(ReduceInt32LessThanOrEqual) {
724 5 : ReducerTester R;
725 5 : R.binop = R.machine.Int32LessThanOrEqual();
726 :
727 585 : FOR_INT32_INPUTS(x) {
728 17110 : FOR_INT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x <= y ? 1 : 0, x, y); }
729 : }
730 :
731 295 : FOR_INT32_INPUTS(i) { R.CheckDontPutConstantOnRight<int32_t>(i); }
732 :
733 5 : Node* x = R.Parameter(0);
734 :
735 5 : R.CheckFoldBinop<int32_t>(1, x, x); // x <= x => 1
736 5 : }
737 :
738 :
739 26644 : TEST(ReduceUint32LessThan) {
740 5 : ReducerTester R;
741 5 : R.binop = R.machine.Uint32LessThan();
742 :
743 585 : FOR_UINT32_INPUTS(x) {
744 17110 : FOR_UINT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x < y ? 1 : 0, x, y); }
745 : }
746 :
747 5 : R.CheckDontPutConstantOnRight(41399);
748 5 : R.CheckDontPutConstantOnRight(-440197);
749 :
750 5 : Node* x = R.Parameter();
751 5 : Node* max = R.maxuint32;
752 5 : Node* zero = R.Constant<int32_t>(0);
753 :
754 5 : R.CheckFoldBinop<int32_t>(0, max, x); // M < x => 0
755 5 : R.CheckFoldBinop<int32_t>(0, x, zero); // x < 0 => 0
756 5 : R.CheckFoldBinop<int32_t>(0, x, x); // x < x => 0
757 5 : }
758 :
759 :
760 26644 : TEST(ReduceUint32LessThanOrEqual) {
761 5 : ReducerTester R;
762 5 : R.binop = R.machine.Uint32LessThanOrEqual();
763 :
764 585 : FOR_UINT32_INPUTS(x) {
765 17110 : FOR_UINT32_INPUTS(y) { R.CheckFoldBinop<int32_t>(x <= y ? 1 : 0, x, y); }
766 : }
767 :
768 5 : R.CheckDontPutConstantOnRight(41399);
769 5 : R.CheckDontPutConstantOnRight(-440197);
770 :
771 5 : Node* x = R.Parameter();
772 5 : Node* max = R.maxuint32;
773 5 : Node* zero = R.Constant<int32_t>(0);
774 :
775 5 : R.CheckFoldBinop<int32_t>(1, x, max); // x <= M => 1
776 5 : R.CheckFoldBinop<int32_t>(1, zero, x); // 0 <= x => 1
777 5 : R.CheckFoldBinop<int32_t>(1, x, x); // x <= x => 1
778 5 : }
779 :
780 :
781 26644 : TEST(ReduceLoadStore) {
782 5 : ReducerTester R;
783 :
784 5 : Node* base = R.Constant<int32_t>(11);
785 5 : Node* index = R.Constant<int32_t>(4);
786 5 : Node* load = R.graph.NewNode(R.machine.Load(MachineType::Int32()), base,
787 : index, R.graph.start(), R.graph.start());
788 :
789 : {
790 10 : MachineOperatorReducer reducer(&R.graph_reducer, &R.jsgraph);
791 5 : Reduction reduction = reducer.Reduce(load);
792 5 : CHECK(!reduction.Changed()); // loads should not be reduced.
793 : }
794 :
795 : {
796 : Node* store =
797 10 : R.graph.NewNode(R.machine.Store(StoreRepresentation(
798 : MachineRepresentation::kWord32, kNoWriteBarrier)),
799 : base, index, load, load, R.graph.start());
800 10 : MachineOperatorReducer reducer(&R.graph_reducer, &R.jsgraph);
801 5 : Reduction reduction = reducer.Reduce(store);
802 5 : CHECK(!reduction.Changed()); // stores should not be reduced.
803 : }
804 5 : }
805 :
806 26644 : TEST(ReduceFloat32Sub) {
807 5 : ReducerTester R;
808 5 : R.binop = R.machine.Float32Sub();
809 :
810 1155 : FOR_FLOAT32_INPUTS(x) {
811 66700 : FOR_FLOAT32_INPUTS(y) { R.CheckFoldBinop<float>(x - y, x, y); }
812 : }
813 :
814 5 : Node* x = R.Parameter();
815 5 : Node* nan = R.Constant<float>(std::numeric_limits<float>::quiet_NaN());
816 :
817 : // nan - x => nan
818 5 : R.CheckFoldBinop(std::numeric_limits<float>::quiet_NaN(), nan, x);
819 : // x - nan => nan
820 5 : R.CheckFoldBinop(std::numeric_limits<float>::quiet_NaN(), x, nan);
821 5 : }
822 :
823 26644 : TEST(ReduceFloat64Sub) {
824 5 : ReducerTester R;
825 5 : R.binop = R.machine.Float64Sub();
826 :
827 495 : FOR_FLOAT64_INPUTS(x) {
828 12250 : FOR_FLOAT64_INPUTS(y) { R.CheckFoldBinop<double>(x - y, x, y); }
829 : }
830 :
831 5 : Node* x = R.Parameter();
832 5 : Node* nan = R.Constant<double>(std::numeric_limits<double>::quiet_NaN());
833 :
834 : // nan - x => nan
835 5 : R.CheckFoldBinop(std::numeric_limits<double>::quiet_NaN(), nan, x);
836 : // x - nan => nan
837 5 : R.CheckFoldBinop(std::numeric_limits<double>::quiet_NaN(), x, nan);
838 5 : }
839 :
840 : // TODO(titzer): test MachineOperatorReducer for Word64And
841 : // TODO(titzer): test MachineOperatorReducer for Word64Or
842 : // TODO(titzer): test MachineOperatorReducer for Word64Xor
843 : // TODO(titzer): test MachineOperatorReducer for Word64Equal
844 : // TODO(titzer): test MachineOperatorReducer for Word64Not
845 : // TODO(titzer): test MachineOperatorReducer for Int64Mul
846 : // TODO(titzer): test MachineOperatorReducer for Int64UMul
847 : // TODO(titzer): test MachineOperatorReducer for Int64Div
848 : // TODO(titzer): test MachineOperatorReducer for Uint64Div
849 : // TODO(titzer): test MachineOperatorReducer for Int64Mod
850 : // TODO(titzer): test MachineOperatorReducer for Uint64Mod
851 : // TODO(titzer): test MachineOperatorReducer for Int64Neg
852 : // TODO(titzer): test MachineOperatorReducer for ChangeInt32ToFloat64
853 : // TODO(titzer): test MachineOperatorReducer for ChangeFloat64ToInt32
854 : // TODO(titzer): test MachineOperatorReducer for Float64Compare
855 : // TODO(titzer): test MachineOperatorReducer for Float64Add
856 : // TODO(titzer): test MachineOperatorReducer for Float64Sub
857 : // TODO(titzer): test MachineOperatorReducer for Float64Mul
858 : // TODO(titzer): test MachineOperatorReducer for Float64Div
859 : // TODO(titzer): test MachineOperatorReducer for Float64Mod
860 :
861 : } // namespace compiler
862 : } // namespace internal
863 79917 : } // namespace v8
|