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 <functional>
6
7 #include "src/codegen.h"
8 #include "src/compiler/js-operator.h"
9 #include "src/compiler/node-properties.h"
10 #include "src/compiler/operator-properties.h"
11 #include "test/cctest/types-fuzz.h"
12 #include "test/unittests/compiler/graph-unittest.h"
13
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17
18 // TODO(titzer): generate a large set of deterministic inputs for these tests.
19 class TyperTest : public TypedGraphTest {
20 public:
TyperTest()21 TyperTest()
22 : TypedGraphTest(3),
23 types_(zone(), isolate(), random_number_generator()),
24 javascript_(zone()) {
25 context_node_ = graph()->NewNode(common()->Parameter(2), graph()->start());
26 rng_ = random_number_generator();
27
28 integers.push_back(0);
29 integers.push_back(0);
30 integers.push_back(-1);
31 integers.push_back(+1);
32 integers.push_back(-V8_INFINITY);
33 integers.push_back(+V8_INFINITY);
34 for (int i = 0; i < 5; ++i) {
35 double x = rng_->NextInt();
36 integers.push_back(x);
37 x *= rng_->NextInt();
38 if (!IsMinusZero(x)) integers.push_back(x);
39 }
40
41 int32s.push_back(0);
42 int32s.push_back(0);
43 int32s.push_back(-1);
44 int32s.push_back(+1);
45 int32s.push_back(kMinInt);
46 int32s.push_back(kMaxInt);
47 for (int i = 0; i < 10; ++i) {
48 int32s.push_back(rng_->NextInt());
49 }
50 }
51
52 Types<Type, Type*, Zone> types_;
53 JSOperatorBuilder javascript_;
54 BinaryOperationHints const hints_ = BinaryOperationHints::Any();
55 Node* context_node_;
56 v8::base::RandomNumberGenerator* rng_;
57 std::vector<double> integers;
58 std::vector<double> int32s;
59
TypeBinaryOp(const Operator * op,Type * lhs,Type * rhs)60 Type* TypeBinaryOp(const Operator* op, Type* lhs, Type* rhs) {
61 Node* p0 = Parameter(0);
62 Node* p1 = Parameter(1);
63 NodeProperties::SetType(p0, lhs);
64 NodeProperties::SetType(p1, rhs);
65 std::vector<Node*> inputs;
66 inputs.push_back(p0);
67 inputs.push_back(p1);
68 if (OperatorProperties::HasContextInput(op)) {
69 inputs.push_back(context_node_);
70 }
71 for (int i = 0; i < OperatorProperties::GetFrameStateInputCount(op); i++) {
72 inputs.push_back(EmptyFrameState());
73 }
74 for (int i = 0; i < op->EffectInputCount(); i++) {
75 inputs.push_back(graph()->start());
76 }
77 for (int i = 0; i < op->ControlInputCount(); i++) {
78 inputs.push_back(graph()->start());
79 }
80 Node* n = graph()->NewNode(op, static_cast<int>(inputs.size()),
81 &(inputs.front()));
82 return NodeProperties::GetType(n);
83 }
84
RandomRange(bool int32=false)85 Type* RandomRange(bool int32 = false) {
86 std::vector<double>& numbers = int32 ? int32s : integers;
87 double i = numbers[rng_->NextInt(static_cast<int>(numbers.size()))];
88 double j = numbers[rng_->NextInt(static_cast<int>(numbers.size()))];
89 return NewRange(i, j);
90 }
91
NewRange(double i,double j)92 Type* NewRange(double i, double j) {
93 if (i > j) std::swap(i, j);
94 return Type::Range(i, j, zone());
95 }
96
RandomInt(double min,double max)97 double RandomInt(double min, double max) {
98 switch (rng_->NextInt(4)) {
99 case 0:
100 return min;
101 case 1:
102 return max;
103 default:
104 break;
105 }
106 if (min == +V8_INFINITY) return +V8_INFINITY;
107 if (max == -V8_INFINITY) return -V8_INFINITY;
108 if (min == -V8_INFINITY && max == +V8_INFINITY) {
109 return rng_->NextInt() * static_cast<double>(rng_->NextInt());
110 }
111 double result = nearbyint(min + (max - min) * rng_->NextDouble());
112 if (IsMinusZero(result)) return 0;
113 if (std::isnan(result)) return rng_->NextInt(2) ? min : max;
114 DCHECK(min <= result && result <= max);
115 return result;
116 }
117
RandomInt(Type::RangeType * range)118 double RandomInt(Type::RangeType* range) {
119 return RandomInt(range->Min(), range->Max());
120 }
121
122 // Careful, this function runs O(max_width^5) trials.
123 template <class BinaryFunction>
TestBinaryArithOpCloseToZero(const Operator * op,BinaryFunction opfun,int max_width)124 void TestBinaryArithOpCloseToZero(const Operator* op, BinaryFunction opfun,
125 int max_width) {
126 const int min_min = -2 - max_width / 2;
127 const int max_min = 2 + max_width / 2;
128 for (int width = 0; width < max_width; width++) {
129 for (int lmin = min_min; lmin <= max_min; lmin++) {
130 for (int rmin = min_min; rmin <= max_min; rmin++) {
131 Type* r1 = NewRange(lmin, lmin + width);
132 Type* r2 = NewRange(rmin, rmin + width);
133 Type* expected_type = TypeBinaryOp(op, r1, r2);
134
135 for (int x1 = lmin; x1 < lmin + width; x1++) {
136 for (int x2 = rmin; x2 < rmin + width; x2++) {
137 double result_value = opfun(x1, x2);
138 Type* result_type = Type::Constant(
139 isolate()->factory()->NewNumber(result_value), zone());
140 EXPECT_TRUE(result_type->Is(expected_type));
141 }
142 }
143 }
144 }
145 }
146 }
147
148 template <class BinaryFunction>
TestBinaryArithOp(const Operator * op,BinaryFunction opfun)149 void TestBinaryArithOp(const Operator* op, BinaryFunction opfun) {
150 TestBinaryArithOpCloseToZero(op, opfun, 8);
151 for (int i = 0; i < 100; ++i) {
152 Type::RangeType* r1 = RandomRange()->AsRange();
153 Type::RangeType* r2 = RandomRange()->AsRange();
154 Type* expected_type = TypeBinaryOp(op, r1, r2);
155 for (int i = 0; i < 10; i++) {
156 double x1 = RandomInt(r1);
157 double x2 = RandomInt(r2);
158 double result_value = opfun(x1, x2);
159 Type* result_type = Type::Constant(
160 isolate()->factory()->NewNumber(result_value), zone());
161 EXPECT_TRUE(result_type->Is(expected_type));
162 }
163 }
164 }
165
166 template <class BinaryFunction>
TestBinaryCompareOp(const Operator * op,BinaryFunction opfun)167 void TestBinaryCompareOp(const Operator* op, BinaryFunction opfun) {
168 for (int i = 0; i < 100; ++i) {
169 Type::RangeType* r1 = RandomRange()->AsRange();
170 Type::RangeType* r2 = RandomRange()->AsRange();
171 Type* expected_type = TypeBinaryOp(op, r1, r2);
172 for (int i = 0; i < 10; i++) {
173 double x1 = RandomInt(r1);
174 double x2 = RandomInt(r2);
175 bool result_value = opfun(x1, x2);
176 Type* result_type =
177 Type::Constant(result_value ? isolate()->factory()->true_value()
178 : isolate()->factory()->false_value(),
179 zone());
180 EXPECT_TRUE(result_type->Is(expected_type));
181 }
182 }
183 }
184
185 template <class BinaryFunction>
TestBinaryBitOp(const Operator * op,BinaryFunction opfun)186 void TestBinaryBitOp(const Operator* op, BinaryFunction opfun) {
187 for (int i = 0; i < 100; ++i) {
188 Type::RangeType* r1 = RandomRange(true)->AsRange();
189 Type::RangeType* r2 = RandomRange(true)->AsRange();
190 Type* expected_type = TypeBinaryOp(op, r1, r2);
191 for (int i = 0; i < 10; i++) {
192 int32_t x1 = static_cast<int32_t>(RandomInt(r1));
193 int32_t x2 = static_cast<int32_t>(RandomInt(r2));
194 double result_value = opfun(x1, x2);
195 Type* result_type = Type::Constant(
196 isolate()->factory()->NewNumber(result_value), zone());
197 EXPECT_TRUE(result_type->Is(expected_type));
198 }
199 }
200 }
201
RandomSubtype(Type * type)202 Type* RandomSubtype(Type* type) {
203 Type* subtype;
204 do {
205 subtype = types_.Fuzz();
206 } while (!subtype->Is(type));
207 return subtype;
208 }
209
TestBinaryMonotonicity(const Operator * op)210 void TestBinaryMonotonicity(const Operator* op) {
211 for (int i = 0; i < 50; ++i) {
212 Type* type1 = types_.Fuzz();
213 Type* type2 = types_.Fuzz();
214 Type* type = TypeBinaryOp(op, type1, type2);
215 Type* subtype1 = RandomSubtype(type1);
216 Type* subtype2 = RandomSubtype(type2);
217 Type* subtype = TypeBinaryOp(op, subtype1, subtype2);
218 EXPECT_TRUE(subtype->Is(type));
219 }
220 }
221 };
222
223
224 namespace {
225
shift_left(int32_t x,int32_t y)226 int32_t shift_left(int32_t x, int32_t y) { return x << y; }
shift_right(int32_t x,int32_t y)227 int32_t shift_right(int32_t x, int32_t y) { return x >> y; }
bit_or(int32_t x,int32_t y)228 int32_t bit_or(int32_t x, int32_t y) { return x | y; }
bit_and(int32_t x,int32_t y)229 int32_t bit_and(int32_t x, int32_t y) { return x & y; }
bit_xor(int32_t x,int32_t y)230 int32_t bit_xor(int32_t x, int32_t y) { return x ^ y; }
231
232 } // namespace
233
234
235 //------------------------------------------------------------------------------
236 // Soundness
237 // For simplicity, we currently only test soundness on expression operators
238 // that have a direct equivalent in C++. Also, testing is currently limited
239 // to ranges as input types.
240
241
TEST_F(TyperTest,TypeJSAdd)242 TEST_F(TyperTest, TypeJSAdd) {
243 TestBinaryArithOp(javascript_.Add(LanguageMode::SLOPPY, hints_),
244 std::plus<double>());
245 TestBinaryArithOp(javascript_.Add(LanguageMode::STRONG, hints_),
246 std::plus<double>());
247 }
248
249
TEST_F(TyperTest,TypeJSSubtract)250 TEST_F(TyperTest, TypeJSSubtract) {
251 TestBinaryArithOp(javascript_.Subtract(LanguageMode::SLOPPY, hints_),
252 std::minus<double>());
253 TestBinaryArithOp(javascript_.Subtract(LanguageMode::STRONG, hints_),
254 std::minus<double>());
255 }
256
257
TEST_F(TyperTest,TypeJSMultiply)258 TEST_F(TyperTest, TypeJSMultiply) {
259 TestBinaryArithOp(javascript_.Multiply(LanguageMode::SLOPPY, hints_),
260 std::multiplies<double>());
261 TestBinaryArithOp(javascript_.Multiply(LanguageMode::STRONG, hints_),
262 std::multiplies<double>());
263 }
264
265
TEST_F(TyperTest,TypeJSDivide)266 TEST_F(TyperTest, TypeJSDivide) {
267 TestBinaryArithOp(javascript_.Divide(LanguageMode::SLOPPY, hints_),
268 std::divides<double>());
269 TestBinaryArithOp(javascript_.Divide(LanguageMode::STRONG, hints_),
270 std::divides<double>());
271 }
272
273
TEST_F(TyperTest,TypeJSModulus)274 TEST_F(TyperTest, TypeJSModulus) {
275 TestBinaryArithOp(javascript_.Modulus(LanguageMode::SLOPPY, hints_), modulo);
276 TestBinaryArithOp(javascript_.Modulus(LanguageMode::STRONG, hints_), modulo);
277 }
278
279
TEST_F(TyperTest,TypeJSBitwiseOr)280 TEST_F(TyperTest, TypeJSBitwiseOr) {
281 TestBinaryBitOp(javascript_.BitwiseOr(LanguageMode::SLOPPY, hints_), bit_or);
282 TestBinaryBitOp(javascript_.BitwiseOr(LanguageMode::STRONG, hints_), bit_or);
283 }
284
285
TEST_F(TyperTest,TypeJSBitwiseAnd)286 TEST_F(TyperTest, TypeJSBitwiseAnd) {
287 TestBinaryBitOp(javascript_.BitwiseAnd(LanguageMode::SLOPPY, hints_),
288 bit_and);
289 TestBinaryBitOp(javascript_.BitwiseAnd(LanguageMode::STRONG, hints_),
290 bit_and);
291 }
292
293
TEST_F(TyperTest,TypeJSBitwiseXor)294 TEST_F(TyperTest, TypeJSBitwiseXor) {
295 TestBinaryBitOp(javascript_.BitwiseXor(LanguageMode::SLOPPY, hints_),
296 bit_xor);
297 TestBinaryBitOp(javascript_.BitwiseXor(LanguageMode::STRONG, hints_),
298 bit_xor);
299 }
300
301
TEST_F(TyperTest,TypeJSShiftLeft)302 TEST_F(TyperTest, TypeJSShiftLeft) {
303 TestBinaryBitOp(javascript_.ShiftLeft(LanguageMode::SLOPPY, hints_),
304 shift_left);
305 TestBinaryBitOp(javascript_.ShiftLeft(LanguageMode::STRONG, hints_),
306 shift_left);
307 }
308
309
TEST_F(TyperTest,TypeJSShiftRight)310 TEST_F(TyperTest, TypeJSShiftRight) {
311 TestBinaryBitOp(javascript_.ShiftRight(LanguageMode::SLOPPY, hints_),
312 shift_right);
313 TestBinaryBitOp(javascript_.ShiftRight(LanguageMode::STRONG, hints_),
314 shift_right);
315 }
316
317
TEST_F(TyperTest,TypeJSLessThan)318 TEST_F(TyperTest, TypeJSLessThan) {
319 TestBinaryCompareOp(javascript_.LessThan(LanguageMode::SLOPPY),
320 std::less<double>());
321 TestBinaryCompareOp(javascript_.LessThan(LanguageMode::STRONG),
322 std::less<double>());
323 }
324
325
TEST_F(TyperTest,TypeJSLessThanOrEqual)326 TEST_F(TyperTest, TypeJSLessThanOrEqual) {
327 TestBinaryCompareOp(javascript_.LessThanOrEqual(LanguageMode::SLOPPY),
328 std::less_equal<double>());
329 TestBinaryCompareOp(javascript_.LessThanOrEqual(LanguageMode::STRONG),
330 std::less_equal<double>());
331 }
332
333
TEST_F(TyperTest,TypeJSGreaterThan)334 TEST_F(TyperTest, TypeJSGreaterThan) {
335 TestBinaryCompareOp(javascript_.GreaterThan(LanguageMode::SLOPPY),
336 std::greater<double>());
337 TestBinaryCompareOp(javascript_.GreaterThan(LanguageMode::STRONG),
338 std::greater<double>());
339 }
340
341
TEST_F(TyperTest,TypeJSGreaterThanOrEqual)342 TEST_F(TyperTest, TypeJSGreaterThanOrEqual) {
343 TestBinaryCompareOp(javascript_.GreaterThanOrEqual(LanguageMode::SLOPPY),
344 std::greater_equal<double>());
345 TestBinaryCompareOp(javascript_.GreaterThanOrEqual(LanguageMode::STRONG),
346 std::greater_equal<double>());
347 }
348
349
TEST_F(TyperTest,TypeJSEqual)350 TEST_F(TyperTest, TypeJSEqual) {
351 TestBinaryCompareOp(javascript_.Equal(), std::equal_to<double>());
352 }
353
354
TEST_F(TyperTest,TypeJSNotEqual)355 TEST_F(TyperTest, TypeJSNotEqual) {
356 TestBinaryCompareOp(javascript_.NotEqual(), std::not_equal_to<double>());
357 }
358
359
360 // For numbers there's no difference between strict and non-strict equality.
TEST_F(TyperTest,TypeJSStrictEqual)361 TEST_F(TyperTest, TypeJSStrictEqual) {
362 TestBinaryCompareOp(javascript_.StrictEqual(), std::equal_to<double>());
363 }
364
365
TEST_F(TyperTest,TypeJSStrictNotEqual)366 TEST_F(TyperTest, TypeJSStrictNotEqual) {
367 TestBinaryCompareOp(javascript_.StrictNotEqual(),
368 std::not_equal_to<double>());
369 }
370
371
372 //------------------------------------------------------------------------------
373 // Monotonicity
374
375
376 #define TEST_BINARY_MONOTONICITY(name) \
377 TEST_F(TyperTest, Monotonicity_##name) { \
378 TestBinaryMonotonicity(javascript_.name()); \
379 }
380 TEST_BINARY_MONOTONICITY(Equal)
TEST_BINARY_MONOTONICITY(NotEqual)381 TEST_BINARY_MONOTONICITY(NotEqual)
382 TEST_BINARY_MONOTONICITY(StrictEqual)
383 TEST_BINARY_MONOTONICITY(StrictNotEqual)
384 #undef TEST_BINARY_MONOTONICITY
385
386
387 #define TEST_BINARY_MONOTONICITY(name) \
388 TEST_F(TyperTest, Monotonicity_##name) { \
389 TestBinaryMonotonicity(javascript_.name(LanguageMode::SLOPPY)); \
390 TestBinaryMonotonicity(javascript_.name(LanguageMode::STRONG)); \
391 }
392 TEST_BINARY_MONOTONICITY(LessThan)
393 TEST_BINARY_MONOTONICITY(GreaterThan)
394 TEST_BINARY_MONOTONICITY(LessThanOrEqual)
395 TEST_BINARY_MONOTONICITY(GreaterThanOrEqual)
396 #undef TEST_BINARY_MONOTONICITY
397
398
399 #define TEST_BINARY_MONOTONICITY(name) \
400 TEST_F(TyperTest, Monotonicity_##name) { \
401 TestBinaryMonotonicity( \
402 javascript_.name(LanguageMode::SLOPPY, BinaryOperationHints::Any())); \
403 TestBinaryMonotonicity( \
404 javascript_.name(LanguageMode::STRONG, BinaryOperationHints::Any())); \
405 }
406 TEST_BINARY_MONOTONICITY(BitwiseOr)
407 TEST_BINARY_MONOTONICITY(BitwiseXor)
408 TEST_BINARY_MONOTONICITY(BitwiseAnd)
409 TEST_BINARY_MONOTONICITY(ShiftLeft)
410 TEST_BINARY_MONOTONICITY(ShiftRight)
411 TEST_BINARY_MONOTONICITY(ShiftRightLogical)
412 TEST_BINARY_MONOTONICITY(Add)
413 TEST_BINARY_MONOTONICITY(Subtract)
414 TEST_BINARY_MONOTONICITY(Multiply)
415 TEST_BINARY_MONOTONICITY(Divide)
416 TEST_BINARY_MONOTONICITY(Modulus)
417 #undef TEST_BINARY_MONOTONICITY
418
419
420 //------------------------------------------------------------------------------
421 // Regression tests
422
423
424 TEST_F(TyperTest, TypeRegressInt32Constant) {
425 int values[] = {-5, 10};
426 for (auto i : values) {
427 Node* c = graph()->NewNode(common()->Int32Constant(i));
428 Type* type = NodeProperties::GetType(c);
429 EXPECT_TRUE(type->Is(NewRange(i, i)));
430 }
431 }
432
433 } // namespace compiler
434 } // namespace internal
435 } // namespace v8
436