Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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: |
| 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 | |
| 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 | |
| 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 | |
| 92 | Type* NewRange(double i, double j) { |
| 93 | if (i > j) std::swap(i, j); |
| 94 | return Type::Range(i, j, zone()); |
| 95 | } |
| 96 | |
| 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 | |
| 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> |
| 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> |
| 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> |
| 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> |
| 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 | |
| 202 | Type* RandomSubtype(Type* type) { |
| 203 | Type* subtype; |
| 204 | do { |
| 205 | subtype = types_.Fuzz(); |
| 206 | } while (!subtype->Is(type)); |
| 207 | return subtype; |
| 208 | } |
| 209 | |
| 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 | |
| 226 | int32_t shift_left(int32_t x, int32_t y) { return x << y; } |
| 227 | int32_t shift_right(int32_t x, int32_t y) { return x >> y; } |
| 228 | int32_t bit_or(int32_t x, int32_t y) { return x | y; } |
| 229 | int32_t bit_and(int32_t x, int32_t y) { return x & 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 274 | TEST_F(TyperTest, TypeJSModulus) { |
| 275 | TestBinaryArithOp(javascript_.Modulus(LanguageMode::SLOPPY, hints_), modulo); |
| 276 | TestBinaryArithOp(javascript_.Modulus(LanguageMode::STRONG, hints_), modulo); |
| 277 | } |
| 278 | |
| 279 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 350 | TEST_F(TyperTest, TypeJSEqual) { |
| 351 | TestBinaryCompareOp(javascript_.Equal(), std::equal_to<double>()); |
| 352 | } |
| 353 | |
| 354 | |
| 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. |
| 361 | TEST_F(TyperTest, TypeJSStrictEqual) { |
| 362 | TestBinaryCompareOp(javascript_.StrictEqual(), std::equal_to<double>()); |
| 363 | } |
| 364 | |
| 365 | |
| 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) |
| 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 |