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 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(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* r1 = RandomRange(); 153 Type* r2 = RandomRange(); 154 Type* expected_type = TypeBinaryOp(op, r1, r2); 155 for (int i = 0; i < 10; i++) { 156 double x1 = RandomInt(r1->AsRange()); 157 double x2 = RandomInt(r2->AsRange()); 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* r1 = RandomRange(); 170 Type* r2 = RandomRange(); 171 Type* expected_type = TypeBinaryOp(op, r1, r2); 172 for (int i = 0; i < 10; i++) { 173 double x1 = RandomInt(r1->AsRange()); 174 double x2 = RandomInt(r2->AsRange()); 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* r1 = RandomRange(true); 189 Type* r2 = RandomRange(true); 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->AsRange())); 193 int32_t x2 = static_cast<int32_t>(RandomInt(r2->AsRange())); 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(hints_), std::plus<double>()); 244 } 245 246 247 TEST_F(TyperTest, TypeJSSubtract) { 248 TestBinaryArithOp(javascript_.Subtract(hints_), std::minus<double>()); 249 } 250 251 252 TEST_F(TyperTest, TypeJSMultiply) { 253 TestBinaryArithOp(javascript_.Multiply(hints_), std::multiplies<double>()); 254 } 255 256 257 TEST_F(TyperTest, TypeJSDivide) { 258 TestBinaryArithOp(javascript_.Divide(hints_), std::divides<double>()); 259 } 260 261 262 TEST_F(TyperTest, TypeJSModulus) { 263 TestBinaryArithOp(javascript_.Modulus(hints_), modulo); 264 } 265 266 267 TEST_F(TyperTest, TypeJSBitwiseOr) { 268 TestBinaryBitOp(javascript_.BitwiseOr(hints_), bit_or); 269 } 270 271 272 TEST_F(TyperTest, TypeJSBitwiseAnd) { 273 TestBinaryBitOp(javascript_.BitwiseAnd(hints_), bit_and); 274 } 275 276 277 TEST_F(TyperTest, TypeJSBitwiseXor) { 278 TestBinaryBitOp(javascript_.BitwiseXor(hints_), bit_xor); 279 } 280 281 282 TEST_F(TyperTest, TypeJSShiftLeft) { 283 TestBinaryBitOp(javascript_.ShiftLeft(hints_), shift_left); 284 } 285 286 287 TEST_F(TyperTest, TypeJSShiftRight) { 288 TestBinaryBitOp(javascript_.ShiftRight(hints_), shift_right); 289 } 290 291 292 TEST_F(TyperTest, TypeJSLessThan) { 293 TestBinaryCompareOp(javascript_.LessThan(CompareOperationHints::Any()), 294 std::less<double>()); 295 } 296 297 298 TEST_F(TyperTest, TypeJSLessThanOrEqual) { 299 TestBinaryCompareOp(javascript_.LessThanOrEqual(CompareOperationHints::Any()), 300 std::less_equal<double>()); 301 } 302 303 304 TEST_F(TyperTest, TypeJSGreaterThan) { 305 TestBinaryCompareOp(javascript_.GreaterThan(CompareOperationHints::Any()), 306 std::greater<double>()); 307 } 308 309 310 TEST_F(TyperTest, TypeJSGreaterThanOrEqual) { 311 TestBinaryCompareOp( 312 javascript_.GreaterThanOrEqual(CompareOperationHints::Any()), 313 std::greater_equal<double>()); 314 } 315 316 317 TEST_F(TyperTest, TypeJSEqual) { 318 TestBinaryCompareOp(javascript_.Equal(CompareOperationHints::Any()), 319 std::equal_to<double>()); 320 } 321 322 323 TEST_F(TyperTest, TypeJSNotEqual) { 324 TestBinaryCompareOp(javascript_.NotEqual(CompareOperationHints::Any()), 325 std::not_equal_to<double>()); 326 } 327 328 329 // For numbers there's no difference between strict and non-strict equality. 330 TEST_F(TyperTest, TypeJSStrictEqual) { 331 TestBinaryCompareOp(javascript_.StrictEqual(CompareOperationHints::Any()), 332 std::equal_to<double>()); 333 } 334 335 336 TEST_F(TyperTest, TypeJSStrictNotEqual) { 337 TestBinaryCompareOp(javascript_.StrictNotEqual(CompareOperationHints::Any()), 338 std::not_equal_to<double>()); 339 } 340 341 342 //------------------------------------------------------------------------------ 343 // Monotonicity 344 345 #define TEST_BINARY_MONOTONICITY(name) \ 346 TEST_F(TyperTest, Monotonicity_##name) { \ 347 TestBinaryMonotonicity(javascript_.name(CompareOperationHints::Any())); \ 348 } 349 TEST_BINARY_MONOTONICITY(Equal) 350 TEST_BINARY_MONOTONICITY(NotEqual) 351 TEST_BINARY_MONOTONICITY(StrictEqual) 352 TEST_BINARY_MONOTONICITY(StrictNotEqual) 353 TEST_BINARY_MONOTONICITY(LessThan) 354 TEST_BINARY_MONOTONICITY(GreaterThan) 355 TEST_BINARY_MONOTONICITY(LessThanOrEqual) 356 TEST_BINARY_MONOTONICITY(GreaterThanOrEqual) 357 #undef TEST_BINARY_MONOTONICITY 358 359 #define TEST_BINARY_MONOTONICITY(name) \ 360 TEST_F(TyperTest, Monotonicity_##name) { \ 361 TestBinaryMonotonicity(javascript_.name(BinaryOperationHints::Any())); \ 362 } 363 TEST_BINARY_MONOTONICITY(BitwiseOr) 364 TEST_BINARY_MONOTONICITY(BitwiseXor) 365 TEST_BINARY_MONOTONICITY(BitwiseAnd) 366 TEST_BINARY_MONOTONICITY(ShiftLeft) 367 TEST_BINARY_MONOTONICITY(ShiftRight) 368 TEST_BINARY_MONOTONICITY(ShiftRightLogical) 369 TEST_BINARY_MONOTONICITY(Add) 370 TEST_BINARY_MONOTONICITY(Subtract) 371 TEST_BINARY_MONOTONICITY(Multiply) 372 TEST_BINARY_MONOTONICITY(Divide) 373 TEST_BINARY_MONOTONICITY(Modulus) 374 #undef TEST_BINARY_MONOTONICITY 375 376 377 //------------------------------------------------------------------------------ 378 // Regression tests 379 380 381 TEST_F(TyperTest, TypeRegressInt32Constant) { 382 int values[] = {-5, 10}; 383 for (auto i : values) { 384 Node* c = graph()->NewNode(common()->Int32Constant(i)); 385 Type* type = NodeProperties::GetType(c); 386 EXPECT_TRUE(type->Is(NewRange(i, i))); 387 } 388 } 389 390 } // namespace compiler 391 } // namespace internal 392 } // namespace v8 393
