OLD | NEW |
(Empty) | |
| 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 <functional> |
| 6 |
| 7 #include "src/compiler/node-properties-inl.h" |
| 8 #include "src/compiler/typer.h" |
| 9 #include "test/cctest/cctest.h" |
| 10 #include "test/cctest/compiler/graph-builder-tester.h" |
| 11 #include "test/cctest/types.h" |
| 12 |
| 13 using namespace v8::internal; |
| 14 using namespace v8::internal::compiler; |
| 15 |
| 16 |
| 17 |
| 18 class TyperTester : public HandleAndZoneScope, public GraphAndBuilders { |
| 19 public: |
| 20 TyperTester() |
| 21 : GraphAndBuilders(main_zone()), |
| 22 types_(main_zone(), isolate()), |
| 23 typer_(main_zone()), |
| 24 javascript_(main_zone()) { |
| 25 Node* s = graph()->NewNode(common()->Start(3)); |
| 26 graph()->SetStart(s); |
| 27 context_node_ = graph()->NewNode(common()->Parameter(2), graph()->start()); |
| 28 rng_ = isolate()->random_number_generator(); |
| 29 |
| 30 integers.push_back(0); |
| 31 integers.push_back(0); |
| 32 integers.push_back(-1); |
| 33 integers.push_back(+1); |
| 34 integers.push_back(-V8_INFINITY); |
| 35 integers.push_back(+V8_INFINITY); |
| 36 for (int i = 0; i < 5; ++i) { |
| 37 double x = rng_->NextInt(); |
| 38 integers.push_back(x); |
| 39 x *= rng_->NextInt(); |
| 40 if (!IsMinusZero(x)) integers.push_back(x); |
| 41 } |
| 42 |
| 43 int32s.push_back(0); |
| 44 int32s.push_back(0); |
| 45 int32s.push_back(-1); |
| 46 int32s.push_back(+1); |
| 47 int32s.push_back(kMinInt); |
| 48 int32s.push_back(kMaxInt); |
| 49 for (int i = 0; i < 10; ++i) { |
| 50 int32s.push_back(rng_->NextInt()); |
| 51 } |
| 52 } |
| 53 |
| 54 Types<Type, Type*, Zone> types_; |
| 55 Typer typer_; |
| 56 JSOperatorBuilder javascript_; |
| 57 Node* context_node_; |
| 58 v8::base::RandomNumberGenerator* rng_; |
| 59 std::vector<double> integers; |
| 60 std::vector<double> int32s; |
| 61 |
| 62 Isolate* isolate() { return main_isolate(); } |
| 63 Graph* graph() { return main_graph_; } |
| 64 CommonOperatorBuilder* common() { return &main_common_; } |
| 65 |
| 66 Node* Parameter(int index = 0) { |
| 67 return graph()->NewNode(common()->Parameter(index), graph()->start()); |
| 68 } |
| 69 |
| 70 Type* TypeBinaryOp(const Operator* op, Type* lhs, Type* rhs) { |
| 71 Node* p0 = Parameter(0); |
| 72 Node* p1 = Parameter(1); |
| 73 NodeProperties::SetBounds(p0, Bounds(lhs)); |
| 74 NodeProperties::SetBounds(p1, Bounds(rhs)); |
| 75 Node* n = graph()->NewNode( |
| 76 op, p0, p1, context_node_, graph()->start(), graph()->start()); |
| 77 typer_.Init(n); |
| 78 return NodeProperties::GetBounds(n).upper; |
| 79 } |
| 80 |
| 81 Type* RandomRange(bool int32 = false) { |
| 82 std::vector<double>& numbers = int32 ? int32s : integers; |
| 83 Factory* f = isolate()->factory(); |
| 84 int i = rng_->NextInt(static_cast<int>(numbers.size())); |
| 85 int j = rng_->NextInt(static_cast<int>(numbers.size())); |
| 86 i::Handle<i::Object> min = f->NewNumber(numbers[i]); |
| 87 i::Handle<i::Object> max = f->NewNumber(numbers[j]); |
| 88 if (min->Number() > max->Number()) std::swap(min, max); |
| 89 return Type::Range(min, max, main_zone()); |
| 90 } |
| 91 |
| 92 double RandomInt(double min, double max) { |
| 93 switch (rng_->NextInt(4)) { |
| 94 case 0: return min; |
| 95 case 1: return max; |
| 96 default: break; |
| 97 } |
| 98 if (min == +V8_INFINITY) return +V8_INFINITY; |
| 99 if (max == -V8_INFINITY) return -V8_INFINITY; |
| 100 if (min == -V8_INFINITY && max == +V8_INFINITY) { |
| 101 return rng_->NextInt() * static_cast<double>(rng_->NextInt()); |
| 102 } |
| 103 double result = nearbyint(min + (max - min) * rng_->NextDouble()); |
| 104 if (IsMinusZero(result)) return 0; |
| 105 if (std::isnan(result)) return rng_->NextInt(2) ? min : max; |
| 106 DCHECK(min <= result && result <= max); |
| 107 return result; |
| 108 } |
| 109 |
| 110 double RandomInt(Type::RangeType* range) { |
| 111 return RandomInt(range->Min()->Number(), range->Max()->Number()); |
| 112 } |
| 113 |
| 114 template <class BinaryFunction> |
| 115 void TestBinaryArithOp(const Operator* op, BinaryFunction opfun) { |
| 116 for (int i = 0; i < 100; ++i) { |
| 117 Type::RangeType* r1 = RandomRange()->AsRange(); |
| 118 Type::RangeType* r2 = RandomRange()->AsRange(); |
| 119 Type* expected_type = TypeBinaryOp(op, r1, r2); |
| 120 double x1 = RandomInt(r1); |
| 121 double x2 = RandomInt(r2); |
| 122 double result_value = opfun(x1, x2); |
| 123 Type* result_type = Type::Constant( |
| 124 isolate()->factory()->NewNumber(result_value), main_zone()); |
| 125 CHECK(result_type->Is(expected_type)); |
| 126 } |
| 127 } |
| 128 |
| 129 template <class BinaryFunction> |
| 130 void TestBinaryCompareOp(const Operator* op, BinaryFunction opfun) { |
| 131 for (int i = 0; i < 100; ++i) { |
| 132 Type::RangeType* r1 = RandomRange()->AsRange(); |
| 133 Type::RangeType* r2 = RandomRange()->AsRange(); |
| 134 Type* expected_type = TypeBinaryOp(op, r1, r2); |
| 135 double x1 = RandomInt(r1); |
| 136 double x2 = RandomInt(r2); |
| 137 bool result_value = opfun(x1, x2); |
| 138 Type* result_type = Type::Constant(result_value ? |
| 139 isolate()->factory()->true_value() : |
| 140 isolate()->factory()->false_value(), main_zone()); |
| 141 CHECK(result_type->Is(expected_type)); |
| 142 } |
| 143 } |
| 144 |
| 145 template <class BinaryFunction> |
| 146 void TestBinaryBitOp(const Operator* op, BinaryFunction opfun) { |
| 147 for (int i = 0; i < 100; ++i) { |
| 148 Type::RangeType* r1 = RandomRange(true)->AsRange(); |
| 149 Type::RangeType* r2 = RandomRange(true)->AsRange(); |
| 150 Type* expected_type = TypeBinaryOp(op, r1, r2); |
| 151 int32_t x1 = static_cast<int32_t>(RandomInt(r1)); |
| 152 int32_t x2 = static_cast<int32_t>(RandomInt(r2)); |
| 153 double result_value = opfun(x1, x2); |
| 154 Type* result_type = Type::Constant( |
| 155 isolate()->factory()->NewNumber(result_value), main_zone()); |
| 156 CHECK(result_type->Is(expected_type)); |
| 157 } |
| 158 } |
| 159 |
| 160 Type* RandomSubtype(Type* type) { |
| 161 Type* subtype; |
| 162 do { |
| 163 subtype = types_.Fuzz(); |
| 164 } while (!subtype->Is(type)); |
| 165 return subtype; |
| 166 } |
| 167 |
| 168 void TestBinaryMonotonicity(const Operator* op) { |
| 169 for (int i = 0; i < 50; ++i) { |
| 170 Type* type1 = types_.Fuzz(); |
| 171 Type* type2 = types_.Fuzz(); |
| 172 Type* type = TypeBinaryOp(op, type1, type2); |
| 173 Type* subtype1 = RandomSubtype(type1);; |
| 174 Type* subtype2 = RandomSubtype(type2);; |
| 175 Type* subtype = TypeBinaryOp(op, subtype1, subtype2); |
| 176 CHECK(subtype->Is(type)); |
| 177 } |
| 178 } |
| 179 }; |
| 180 |
| 181 |
| 182 static int32_t shift_left(int32_t x, int32_t y) { return x << y; } |
| 183 static int32_t shift_right(int32_t x, int32_t y) { return x >> y; } |
| 184 static int32_t bit_or(int32_t x, int32_t y) { return x | y; } |
| 185 static int32_t bit_and(int32_t x, int32_t y) { return x & y; } |
| 186 static int32_t bit_xor(int32_t x, int32_t y) { return x ^ y; } |
| 187 |
| 188 |
| 189 //------------------------------------------------------------------------------ |
| 190 // Soundness |
| 191 // For simplicity, we currently only test soundness on expression operators |
| 192 // that have a direct equivalent in C++. Also, testing is currently limited |
| 193 // to ranges as input types. |
| 194 |
| 195 |
| 196 TEST(TypeJSAdd) { |
| 197 TyperTester t; |
| 198 t.TestBinaryArithOp(t.javascript_.Subtract(), std::plus<double>()); |
| 199 } |
| 200 |
| 201 |
| 202 TEST(TypeJSSubtract) { |
| 203 TyperTester t; |
| 204 t.TestBinaryArithOp(t.javascript_.Subtract(), std::minus<double>()); |
| 205 } |
| 206 |
| 207 |
| 208 TEST(TypeJSMultiply) { |
| 209 TyperTester t; |
| 210 t.TestBinaryArithOp(t.javascript_.Multiply(), std::multiplies<double>()); |
| 211 } |
| 212 |
| 213 |
| 214 TEST(TypeJSDivide) { |
| 215 TyperTester t; |
| 216 t.TestBinaryArithOp(t.javascript_.Divide(), std::divides<double>()); |
| 217 } |
| 218 |
| 219 |
| 220 TEST(TypeJSBitwiseOr) { |
| 221 TyperTester t; |
| 222 t.TestBinaryBitOp(t.javascript_.BitwiseOr(), bit_or); |
| 223 } |
| 224 |
| 225 |
| 226 TEST(TypeJSBitwiseAnd) { |
| 227 TyperTester t; |
| 228 t.TestBinaryBitOp(t.javascript_.BitwiseAnd(), bit_and); |
| 229 } |
| 230 |
| 231 |
| 232 TEST(TypeJSBitwiseXor) { |
| 233 TyperTester t; |
| 234 t.TestBinaryBitOp(t.javascript_.BitwiseXor(), bit_xor); |
| 235 } |
| 236 |
| 237 |
| 238 TEST(TypeJSShiftLeft) { |
| 239 TyperTester t; |
| 240 t.TestBinaryBitOp(t.javascript_.ShiftLeft(), shift_left); |
| 241 } |
| 242 |
| 243 |
| 244 TEST(TypeJSShiftRight) { |
| 245 TyperTester t; |
| 246 t.TestBinaryBitOp(t.javascript_.ShiftRight(), shift_right); |
| 247 } |
| 248 |
| 249 |
| 250 TEST(TypeJSLessThan) { |
| 251 TyperTester t; |
| 252 t.TestBinaryCompareOp(t.javascript_.LessThan(), std::less<double>()); |
| 253 } |
| 254 |
| 255 |
| 256 TEST(TypeJSLessThanOrEqual) { |
| 257 TyperTester t; |
| 258 t.TestBinaryCompareOp( |
| 259 t.javascript_.LessThanOrEqual(), std::less_equal<double>()); |
| 260 } |
| 261 |
| 262 |
| 263 TEST(TypeJSGreaterThan) { |
| 264 TyperTester t; |
| 265 t.TestBinaryCompareOp(t.javascript_.GreaterThan(), std::greater<double>()); |
| 266 } |
| 267 |
| 268 |
| 269 TEST(TypeJSGreaterThanOrEqual) { |
| 270 TyperTester t; |
| 271 t.TestBinaryCompareOp( |
| 272 t.javascript_.GreaterThanOrEqual(), std::greater_equal<double>()); |
| 273 } |
| 274 |
| 275 |
| 276 TEST(TypeJSEqual) { |
| 277 TyperTester t; |
| 278 t.TestBinaryCompareOp(t.javascript_.Equal(), std::equal_to<double>()); |
| 279 } |
| 280 |
| 281 |
| 282 TEST(TypeJSNotEqual) { |
| 283 TyperTester t; |
| 284 t.TestBinaryCompareOp(t.javascript_.NotEqual(), std::not_equal_to<double>()); |
| 285 } |
| 286 |
| 287 |
| 288 // For numbers there's no difference between strict and non-strict equality. |
| 289 TEST(TypeJSStrictEqual) { |
| 290 TyperTester t; |
| 291 t.TestBinaryCompareOp(t.javascript_.StrictEqual(), std::equal_to<double>()); |
| 292 } |
| 293 |
| 294 |
| 295 TEST(TypeJSStrictNotEqual) { |
| 296 TyperTester t; |
| 297 t.TestBinaryCompareOp( |
| 298 t.javascript_.StrictNotEqual(), std::not_equal_to<double>()); |
| 299 } |
| 300 |
| 301 |
| 302 //------------------------------------------------------------------------------ |
| 303 // Monotonicity |
| 304 |
| 305 |
| 306 // List must be in sync with JS_SIMPLE_BINOP_LIST. |
| 307 #define JSBINOP_LIST(V) \ |
| 308 V(Equal) \ |
| 309 V(NotEqual) \ |
| 310 V(StrictEqual) \ |
| 311 V(StrictNotEqual) \ |
| 312 V(LessThan) \ |
| 313 V(GreaterThan) \ |
| 314 V(LessThanOrEqual) \ |
| 315 V(GreaterThanOrEqual) \ |
| 316 V(BitwiseOr) \ |
| 317 V(BitwiseXor) \ |
| 318 V(BitwiseAnd) \ |
| 319 V(ShiftLeft) \ |
| 320 V(ShiftRight) \ |
| 321 V(ShiftRightLogical) \ |
| 322 V(Add) \ |
| 323 V(Subtract) \ |
| 324 V(Multiply) \ |
| 325 V(Divide) \ |
| 326 V(Modulus) |
| 327 |
| 328 |
| 329 TEST(Monotonicity) { |
| 330 TyperTester t; |
| 331 #define TEST_TYPE(name) \ |
| 332 t.TestBinaryMonotonicity(t.javascript_.name()); |
| 333 JSBINOP_LIST(TEST_TYPE) |
| 334 #undef TEST_TYPE |
| 335 } |
OLD | NEW |