Convert compiler cctest to unittests: TyperTest

test/unittests/compiler/typer-unittest.cc

+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <functional>
+
+#include "src/codegen.h"
+#include "src/compiler/js-operator.h"
+#include "src/compiler/node-properties-inl.h"
+#include "src/compiler/typer.h"
+#include "src/isolate-inl.h"
+#include "test/unittests/compiler/graph-unittest.h"
+#include "testing/gmock-support.h"
+
+using namespace v8::internal;
+using namespace v8::internal::compiler;
+
+namespace {
+
+template <class Type, class TypeHandle, class Region>
+class Types {
+ public:
+  Types(Region* region, Isolate* isolate)
+      : region_(region), rng_(isolate->random_number_generator()) {
+#define DECLARE_TYPE(name, value) \
+  name = Type::name(region);      \
+  types.push_back(name);
+    PROPER_BITSET_TYPE_LIST(DECLARE_TYPE)
+#undef DECLARE_TYPE
+
+    object_map =
+        isolate->factory()->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize);
+    array_map = isolate->factory()->NewMap(JS_ARRAY_TYPE, JSArray::kSize);
+    number_map =
+        isolate->factory()->NewMap(HEAP_NUMBER_TYPE, HeapNumber::kSize);
+    uninitialized_map = isolate->factory()->uninitialized_map();
+    ObjectClass = Type::Class(object_map, region);
+    ArrayClass = Type::Class(array_map, region);
+    NumberClass = Type::Class(number_map, region);
+    UninitializedClass = Type::Class(uninitialized_map, region);
+
+    maps.push_back(object_map);
+    maps.push_back(array_map);
+    maps.push_back(uninitialized_map);
+    for (MapVector::iterator it = maps.begin(); it != maps.end(); ++it) {
+      types.push_back(Type::Class(*it, region));
+    }
+
+    smi = handle(Smi::FromInt(666), isolate);
+    signed32 = isolate->factory()->NewHeapNumber(0x40000000);
+    object1 = isolate->factory()->NewJSObjectFromMap(object_map);
+    object2 = isolate->factory()->NewJSObjectFromMap(object_map);
+    array = isolate->factory()->NewJSArray(20);
+    uninitialized = isolate->factory()->uninitialized_value();
+    SmiConstant = Type::Constant(smi, region);
+    Signed32Constant = Type::Constant(signed32, region);
+    ObjectConstant1 = Type::Constant(object1, region);
+    ObjectConstant2 = Type::Constant(object2, region);
+    ArrayConstant = Type::Constant(array, region);
+    UninitializedConstant = Type::Constant(uninitialized, region);
+
+    values.push_back(smi);
+    values.push_back(signed32);
+    values.push_back(object1);
+    values.push_back(object2);
+    values.push_back(array);
+    values.push_back(uninitialized);
+    for (ValueVector::iterator it = values.begin(); it != values.end(); ++it) {
+      types.push_back(Type::Constant(*it, region));
+    }
+
+    integers.push_back(isolate->factory()->NewNumber(-V8_INFINITY));
+    integers.push_back(isolate->factory()->NewNumber(+V8_INFINITY));
+    integers.push_back(isolate->factory()->NewNumber(-rng_->NextInt(10)));
+    integers.push_back(isolate->factory()->NewNumber(+rng_->NextInt(10)));
+    for (int i = 0; i < 10; ++i) {
+      double x = rng_->NextInt();
+      integers.push_back(isolate->factory()->NewNumber(x));
+      x *= rng_->NextInt();
+      if (!IsMinusZero(x)) integers.push_back(isolate->factory()->NewNumber(x));
+    }
+
+    Integer = Type::Range(isolate->factory()->NewNumber(-V8_INFINITY),
+                          isolate->factory()->NewNumber(+V8_INFINITY), region);
+
+    NumberArray = Type::Array(Number, region);
+    StringArray = Type::Array(String, region);
+    AnyArray = Type::Array(Any, region);
+
+    SignedFunction1 = Type::Function(SignedSmall, SignedSmall, region);
+    NumberFunction1 = Type::Function(Number, Number, region);
+    NumberFunction2 = Type::Function(Number, Number, Number, region);
+    MethodFunction = Type::Function(String, Object, 0, region);
+
+    for (int i = 0; i < 30; ++i) {
+      types.push_back(Fuzz());
+    }
+  }
+
+  Handle<i::Map> object_map;
+  Handle<i::Map> array_map;
+  Handle<i::Map> number_map;
+  Handle<i::Map> uninitialized_map;
+
+  Handle<i::Smi> smi;
+  Handle<i::HeapNumber> signed32;
+  Handle<i::JSObject> object1;
+  Handle<i::JSObject> object2;
+  Handle<i::JSArray> array;
+  Handle<i::Oddball> uninitialized;
+
+#define DECLARE_TYPE(name, value) TypeHandle name;
+  PROPER_BITSET_TYPE_LIST(DECLARE_TYPE)
+#undef DECLARE_TYPE
+
+  TypeHandle ObjectClass;
+  TypeHandle ArrayClass;
+  TypeHandle NumberClass;
+  TypeHandle UninitializedClass;
+
+  TypeHandle SmiConstant;
+  TypeHandle Signed32Constant;
+  TypeHandle ObjectConstant1;
+  TypeHandle ObjectConstant2;
+  TypeHandle ArrayConstant;
+  TypeHandle UninitializedConstant;
+
+  TypeHandle Integer;
+
+  TypeHandle NumberArray;
+  TypeHandle StringArray;
+  TypeHandle AnyArray;
+
+  TypeHandle SignedFunction1;
+  TypeHandle NumberFunction1;
+  TypeHandle NumberFunction2;
+  TypeHandle MethodFunction;
+
+  typedef std::vector<TypeHandle> TypeVector;
+  typedef std::vector<Handle<i::Map> > MapVector;
+  typedef std::vector<Handle<i::Object> > ValueVector;
+
+  TypeVector types;
+  MapVector maps;
+  ValueVector values;
+  ValueVector integers;  // "Integer" values used for range limits.
+
+  TypeHandle Of(Handle<i::Object> value) { return Type::Of(value, region_); }
+
+  TypeHandle NowOf(Handle<i::Object> value) {
+    return Type::NowOf(value, region_);
+  }
+
+  TypeHandle Class(Handle<i::Map> map) { return Type::Class(map, region_); }
+
+  TypeHandle Constant(Handle<i::Object> value) {
+    return Type::Constant(value, region_);
+  }
+
+  TypeHandle Range(Handle<i::Object> min, Handle<i::Object> max) {
+    return Type::Range(min, max, region_);
+  }
+
+  TypeHandle Context(TypeHandle outer) { return Type::Context(outer, region_); }
+
+  TypeHandle Array1(TypeHandle element) {
+    return Type::Array(element, region_);
+  }
+
+  TypeHandle Function0(TypeHandle result, TypeHandle receiver) {
+    return Type::Function(result, receiver, 0, region_);
+  }
+
+  TypeHandle Function1(TypeHandle result, TypeHandle receiver, TypeHandle arg) {
+    TypeHandle type = Type::Function(result, receiver, 1, region_);
+    type->AsFunction()->InitParameter(0, arg);
+    return type;
+  }
+
+  TypeHandle Function2(TypeHandle result, TypeHandle arg1, TypeHandle arg2) {
+    return Type::Function(result, arg1, arg2, region_);
+  }
+
+  TypeHandle Union(TypeHandle t1, TypeHandle t2) {
+    return Type::Union(t1, t2, region_);
+  }
+  TypeHandle Intersect(TypeHandle t1, TypeHandle t2) {
+    return Type::Intersect(t1, t2, region_);
+  }
+
+  template <class Type2, class TypeHandle2>
+  TypeHandle Convert(TypeHandle2 t) {
+    return Type::template Convert<Type2>(t, region_);
+  }
+
+  TypeHandle Random() {
+    return types[rng_->NextInt(static_cast<int>(types.size()))];
+  }
+
+  TypeHandle Fuzz(int depth = 4) {
+    switch (rng_->NextInt(depth == 0 ? 3 : 20)) {
+      case 0: {  // bitset
+#define COUNT_BITSET_TYPES(type, value) +1
+        int n = 0 PROPER_BITSET_TYPE_LIST(COUNT_BITSET_TYPES);
+#undef COUNT_BITSET_TYPES
+        // Pick a bunch of named bitsets and return their intersection.
+        TypeHandle result = Type::Any(region_);
+        for (int i = 0, m = 1 + rng_->NextInt(3); i < m; ++i) {
+          int j = rng_->NextInt(n);
+#define PICK_BITSET_TYPE(type, value)                                       \
+  if (j-- == 0) {                                                           \
+    TypeHandle tmp = Type::Intersect(result, Type::type(region_), region_); \
+    if (tmp->Is(Type::None()) && i != 0) {                                  \
+      break;                                                                \
+    } else {                                                                \
+      result = tmp;                                                         \
+      continue;                                                             \
+    }                                                                       \
+  }
+          PROPER_BITSET_TYPE_LIST(PICK_BITSET_TYPE)
+#undef PICK_BITSET_TYPE
+        }
+        return result;
+      }
+      case 1: {  // class
+        int i = rng_->NextInt(static_cast<int>(maps.size()));
+        return Type::Class(maps[i], region_);
+      }
+      case 2: {  // constant
+        int i = rng_->NextInt(static_cast<int>(values.size()));
+        return Type::Constant(values[i], region_);
+      }
+      case 3: {  // range
+        int i = rng_->NextInt(static_cast<int>(integers.size()));
+        int j = rng_->NextInt(static_cast<int>(integers.size()));
+        i::Handle<i::Object> min = integers[i];
+        i::Handle<i::Object> max = integers[j];
+        if (min->Number() > max->Number()) std::swap(min, max);
+        return Type::Range(min, max, region_);
+      }
+      case 4: {  // context
+        int depth = rng_->NextInt(3);
+        TypeHandle type = Type::Internal(region_);
+        for (int i = 0; i < depth; ++i) type = Type::Context(type, region_);
+        return type;
+      }
+      case 5: {  // array
+        TypeHandle element = Fuzz(depth / 2);
+        return Type::Array(element, region_);
+      }
+      case 6:
+      case 7: {  // function
+        TypeHandle result = Fuzz(depth / 2);
+        TypeHandle receiver = Fuzz(depth / 2);
+        int arity = rng_->NextInt(3);
+        TypeHandle type = Type::Function(result, receiver, arity, region_);
+        for (int i = 0; i < type->AsFunction()->Arity(); ++i) {
+          TypeHandle parameter = Fuzz(depth / 2);
+          type->AsFunction()->InitParameter(i, parameter);
+        }
+        return type;
+      }
+      default: {  // union
+        int n = rng_->NextInt(10);
+        TypeHandle type = None;
+        for (int i = 0; i < n; ++i) {
+          TypeHandle operand = Fuzz(depth - 1);
+          type = Type::Union(type, operand, region_);
+        }
+        return type;
+      }
+    }
+    UNREACHABLE();
+  }
+
+  Region* region() { return region_; }
+
+ private:
+  Region* region_;
+  v8::base::RandomNumberGenerator* rng_;
+};
+
+
+// TODO(titzer): generate a large set of deterministic inputs for these tests.
+class TyperTest : public GraphTest {
+ public:
+  TyperTest()
+      : types_(zone(), isolate()),
+        typer_(graph(), MaybeHandle<Context>()),
+        javascript_(zone()) {
+    Node* s = graph()->NewNode(common()->Start(3));
+    graph()->SetStart(s);
+    context_node_ = graph()->NewNode(common()->Parameter(2), graph()->start());
+    rng_ = isolate()->random_number_generator();
+
+    integers.push_back(0);
+    integers.push_back(0);
+    integers.push_back(-1);
+    integers.push_back(+1);
+    integers.push_back(-V8_INFINITY);
+    integers.push_back(+V8_INFINITY);
+    for (int i = 0; i < 5; ++i) {
+      double x = rng_->NextInt();
+      integers.push_back(x);
+      x *= rng_->NextInt();
+      if (!IsMinusZero(x)) integers.push_back(x);
+    }
+
+    int32s.push_back(0);
+    int32s.push_back(0);
+    int32s.push_back(-1);
+    int32s.push_back(+1);
+    int32s.push_back(kMinInt);
+    int32s.push_back(kMaxInt);
+    for (int i = 0; i < 10; ++i) {
+      int32s.push_back(rng_->NextInt());
+    }
+  }
+
+  Types<Type, Type*, Zone> types_;
+  Typer typer_;
+  JSOperatorBuilder javascript_;
+  Node* context_node_;
+  v8::base::RandomNumberGenerator* rng_;
+  std::vector<double> integers;
+  std::vector<double> int32s;
+
+  Type* TypeBinaryOp(const Operator* op, Type* lhs, Type* rhs) {
+    Node* p0 = Parameter(0);
+    Node* p1 = Parameter(1);
+    NodeProperties::SetBounds(p0, Bounds(lhs));
+    NodeProperties::SetBounds(p1, Bounds(rhs));
+    Node* n = graph()->NewNode(op, p0, p1, context_node_, graph()->start(),
+                               graph()->start());
+    return NodeProperties::GetBounds(n).upper;
+  }
+
+  Type* RandomRange(bool int32 = false) {
+    std::vector<double>& numbers = int32 ? int32s : integers;
+    double i = numbers[rng_->NextInt(static_cast<int>(numbers.size()))];
+    double j = numbers[rng_->NextInt(static_cast<int>(numbers.size()))];
+    return NewRange(i, j);
+  }
+
+  Type* NewRange(double i, double j) {
+    Factory* f = isolate()->factory();
+    i::Handle<i::Object> min = f->NewNumber(i);
+    i::Handle<i::Object> max = f->NewNumber(j);
+    if (min->Number() > max->Number()) std::swap(min, max);
+    return Type::Range(min, max, zone());
+  }
+
+  double RandomInt(double min, double max) {
+    switch (rng_->NextInt(4)) {
+      case 0:
+        return min;
+      case 1:
+        return max;
+      default:
+        break;
+    }
+    if (min == +V8_INFINITY) return +V8_INFINITY;
+    if (max == -V8_INFINITY) return -V8_INFINITY;
+    if (min == -V8_INFINITY && max == +V8_INFINITY) {
+      return rng_->NextInt() * static_cast<double>(rng_->NextInt());
+    }
+    double result = nearbyint(min + (max - min) * rng_->NextDouble());
+    if (IsMinusZero(result)) return 0;
+    if (std::isnan(result)) return rng_->NextInt(2) ? min : max;
+    DCHECK(min <= result && result <= max);
+    return result;
+  }
+
+  double RandomInt(Type::RangeType* range) {
+    return RandomInt(range->Min()->Number(), range->Max()->Number());
+  }
+
+  // Careful, this function runs O(max_width^5) trials.
+  template <class BinaryFunction>
+  void TestBinaryArithOpCloseToZero(const Operator* op, BinaryFunction opfun,
+                                    int max_width) {
+    const int min_min = -2 - max_width / 2;
+    const int max_min = 2 + max_width / 2;
+    for (int width = 0; width < max_width; width++) {
+      for (int lmin = min_min; lmin <= max_min; lmin++) {
+        for (int rmin = min_min; rmin <= max_min; rmin++) {
+          Type* r1 = NewRange(lmin, lmin + width);
+          Type* r2 = NewRange(rmin, rmin + width);
+          Type* expected_type = TypeBinaryOp(op, r1, r2);
+
+          for (int x1 = lmin; x1 < lmin + width; x1++) {
+            for (int x2 = rmin; x2 < rmin + width; x2++) {
+              double result_value = opfun(x1, x2);
+              Type* result_type = Type::Constant(
+                  isolate()->factory()->NewNumber(result_value), zone());
+              EXPECT_TRUE(result_type->Is(expected_type));
+            }
+          }
+        }
+      }
+    }
+  }
+
+  template <class BinaryFunction>
+  void TestBinaryArithOp(const Operator* op, BinaryFunction opfun) {
+    TestBinaryArithOpCloseToZero(op, opfun, 8);
+    for (int i = 0; i < 100; ++i) {
+      Type::RangeType* r1 = RandomRange()->AsRange();
+      Type::RangeType* r2 = RandomRange()->AsRange();
+      Type* expected_type = TypeBinaryOp(op, r1, r2);
+      for (int i = 0; i < 10; i++) {
+        double x1 = RandomInt(r1);
+        double x2 = RandomInt(r2);
+        double result_value = opfun(x1, x2);
+        Type* result_type = Type::Constant(
+            isolate()->factory()->NewNumber(result_value), zone());
+        EXPECT_TRUE(result_type->Is(expected_type));
+      }
+    }
+  }
+
+  template <class BinaryFunction>
+  void TestBinaryCompareOp(const Operator* op, BinaryFunction opfun) {
+    for (int i = 0; i < 100; ++i) {
+      Type::RangeType* r1 = RandomRange()->AsRange();
+      Type::RangeType* r2 = RandomRange()->AsRange();
+      Type* expected_type = TypeBinaryOp(op, r1, r2);
+      for (int i = 0; i < 10; i++) {
+        double x1 = RandomInt(r1);
+        double x2 = RandomInt(r2);
+        bool result_value = opfun(x1, x2);
+        Type* result_type =
+            Type::Constant(result_value ? isolate()->factory()->true_value()
+                                        : isolate()->factory()->false_value(),
+                           zone());
+        EXPECT_TRUE(result_type->Is(expected_type));
+      }
+    }
+  }
+
+  template <class BinaryFunction>
+  void TestBinaryBitOp(const Operator* op, BinaryFunction opfun) {
+    for (int i = 0; i < 100; ++i) {
+      Type::RangeType* r1 = RandomRange(true)->AsRange();
+      Type::RangeType* r2 = RandomRange(true)->AsRange();
+      Type* expected_type = TypeBinaryOp(op, r1, r2);
+      for (int i = 0; i < 10; i++) {
+        int32_t x1 = static_cast<int32_t>(RandomInt(r1));
+        int32_t x2 = static_cast<int32_t>(RandomInt(r2));
+        double result_value = opfun(x1, x2);
+        Type* result_type = Type::Constant(
+            isolate()->factory()->NewNumber(result_value), zone());
+        EXPECT_TRUE(result_type->Is(expected_type));
+      }
+    }
+  }
+
+  Type* RandomSubtype(Type* type) {
+    Type* subtype;
+    do {
+      subtype = types_.Fuzz();
+    } while (!subtype->Is(type));
+    return subtype;
+  }
+
+  void TestBinaryMonotonicity(const Operator* op) {
+    for (int i = 0; i < 50; ++i) {
+      Type* type1 = types_.Fuzz();
+      Type* type2 = types_.Fuzz();
+      Type* type = TypeBinaryOp(op, type1, type2);
+      Type* subtype1 = RandomSubtype(type1);
+      ;
+      Type* subtype2 = RandomSubtype(type2);
+      ;
+      Type* subtype = TypeBinaryOp(op, subtype1, subtype2);
+      EXPECT_TRUE(subtype->Is(type));
+    }
+  }
+};
+
+
+static int32_t shift_left(int32_t x, int32_t y) { return x << y; }
+static int32_t shift_right(int32_t x, int32_t y) { return x >> y; }
+static int32_t bit_or(int32_t x, int32_t y) { return x | y; }
+static int32_t bit_and(int32_t x, int32_t y) { return x & y; }
+static int32_t bit_xor(int32_t x, int32_t y) { return x ^ y; }
+}
+
+
+//------------------------------------------------------------------------------
+// Soundness
+//   For simplicity, we currently only test soundness on expression operators
+//   that have a direct equivalent in C++.  Also, testing is currently limited
+//   to ranges as input types.
+
+
+TEST_F(TyperTest, TypeJSAdd2) {
+  TestBinaryArithOp(javascript_.Add(), std::plus<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSSubtract) {
+  TestBinaryArithOp(javascript_.Subtract(), std::minus<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSMultiply) {
+  TestBinaryArithOp(javascript_.Multiply(), std::multiplies<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSDivide) {
+  TestBinaryArithOp(javascript_.Divide(), std::divides<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSModulus) {
+  TestBinaryArithOp(javascript_.Modulus(), modulo);
+}
+
+
+TEST_F(TyperTest, TypeJSBitwiseOr) {
+  TestBinaryBitOp(javascript_.BitwiseOr(), bit_or);
+}
+
+
+TEST_F(TyperTest, TypeJSBitwiseAnd) {
+  TestBinaryBitOp(javascript_.BitwiseAnd(), bit_and);
+}
+
+
+TEST_F(TyperTest, TypeJSBitwiseXor) {
+  TestBinaryBitOp(javascript_.BitwiseXor(), bit_xor);
+}
+
+
+TEST_F(TyperTest, TypeJSShiftLeft) {
+  TestBinaryBitOp(javascript_.ShiftLeft(), shift_left);
+}
+
+
+TEST_F(TyperTest, TypeJSShiftRight) {
+  TestBinaryBitOp(javascript_.ShiftRight(), shift_right);
+}
+
+
+TEST_F(TyperTest, TypeJSLessThan) {
+  TestBinaryCompareOp(javascript_.LessThan(), std::less<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSLessThanOrEqual) {
+  TestBinaryCompareOp(javascript_.LessThanOrEqual(), std::less_equal<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSGreaterThan) {
+  TestBinaryCompareOp(javascript_.GreaterThan(), std::greater<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSGreaterThanOrEqual) {
+  TestBinaryCompareOp(javascript_.GreaterThanOrEqual(),
+                      std::greater_equal<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSEqual) {
+  TestBinaryCompareOp(javascript_.Equal(), std::equal_to<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSNotEqual) {
+  TestBinaryCompareOp(javascript_.NotEqual(), std::not_equal_to<double>());
+}
+
+
+// For numbers there's no difference between strict and non-strict equality.
+TEST_F(TyperTest, TypeJSStrictEqual) {
+  TestBinaryCompareOp(javascript_.StrictEqual(), std::equal_to<double>());
+}
+
+
+TEST_F(TyperTest, TypeJSStrictNotEqual) {
+  TestBinaryCompareOp(javascript_.StrictNotEqual(),
+                      std::not_equal_to<double>());
+}
+
+
+//------------------------------------------------------------------------------
+// Monotonicity
+
+
+// List should be in sync with JS_SIMPLE_BINOP_LIS
+#define JSBINOP_LIST(V) \
+  V(Equal)              \
+  V(NotEqual)           \
+  V(StrictEqual)        \
+  V(StrictNotEqual)     \
+  V(LessThan)           \
+  V(GreaterThan)        \
+  V(LessThanOrEqual)    \
+  V(GreaterThanOrEqual) \
+  V(BitwiseOr)          \
+  V(BitwiseXor)         \
+  V(BitwiseAnd)         \
+  V(ShiftLeft)          \
+  V(ShiftRight)         \
+  V(ShiftRightLogical)  \
+  V(Add)                \
+  V(Subtract)           \
+  V(Multiply)           \
+  V(Divide)             \
+  V(Modulus)
+
+
+#define TEST_FUNC(name)                         \
+  TEST_F(TyperTest, Monotonicity_##name) {      \
+    TestBinaryMonotonicity(javascript_.name()); \
+  }
+JSBINOP_LIST(TEST_FUNC)
+#undef TEST_FUNC