Revision: 25193
Author: [email protected]
Date: Thu Nov 6 13:10:20 2014 UTC
Log: [turbofan] (reland) Compute tighter ranges for modulus in Typer.
[email protected]
BUG=
Review URL: https://codereview.chromium.org/694703004
https://code.google.com/p/v8/source/detail?r=25193
Modified:
/branches/bleeding_edge/src/compiler/typer.cc
/branches/bleeding_edge/test/cctest/compiler/test-typer.cc
=======================================
--- /branches/bleeding_edge/src/compiler/typer.cc Wed Nov 5 15:19:30 2014
UTC
+++ /branches/bleeding_edge/src/compiler/typer.cc Thu Nov 6 13:10:20 2014
UTC
@@ -232,6 +232,7 @@
static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*,
Typer*);
static Type* JSMultiplyRanger(Type::RangeType*, Type::RangeType*,
Typer*);
static Type* JSDivideRanger(Type::RangeType*, Type::RangeType*, Typer*);
+ static Type* JSModulusRanger(Type::RangeType*, Type::RangeType*, Typer*);
static Type* JSCompareTyper(Type*, Type*, Typer*);
@@ -982,19 +983,59 @@
(rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
return maybe_nan ? Type::Number() : Type::OrderedNumber();
}
+
+
+Type* Typer::Visitor::JSModulusRanger(Type::RangeType* lhs,
+ Type::RangeType* rhs, Typer* t) {
+ double lmin = lhs->Min()->Number();
+ double lmax = lhs->Max()->Number();
+ double rmin = rhs->Min()->Number();
+ double rmax = rhs->Max()->Number();
+
+ double labs = std::max(std::abs(lmin), std::abs(lmax));
+ double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1;
+ double abs = std::min(labs, rabs);
+ bool maybe_minus_zero = false;
+ double omin = 0;
+ double omax = 0;
+ if (lmin >= 0) { // {lhs} positive.
+ omin = 0;
+ omax = abs;
+ } else if (lmax <= 0) { // {lhs} negative.
+ omin = 0 - abs;
+ omax = 0;
+ maybe_minus_zero = true;
+ } else {
+ omin = 0 - abs;
+ omax = abs;
+ maybe_minus_zero = true;
+ }
+
+ Factory* f = t->isolate()->factory();
+ Type* result = Type::Range(f->NewNumber(omin), f->NewNumber(omax),
t->zone());
+ if (maybe_minus_zero)
+ result = Type::Union(result, Type::MinusZero(), t->zone());
+ return result;
+}
Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) {
lhs = ToNumber(lhs, t);
rhs = ToNumber(rhs, t);
if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
- // Division is tricky, so all we do is try ruling out nan.
- // TODO(neis): try ruling out -0 as well?
- bool maybe_nan =
- lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
- ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
- (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
- return maybe_nan ? Type::Number() : Type::OrderedNumber();
+
+ if (lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
+ lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) {
+ // Result maybe NaN.
+ return Type::Number();
+ }
+
+ lhs = Rangify(lhs, t);
+ rhs = Rangify(rhs, t);
+ if (lhs->IsRange() && rhs->IsRange()) {
+ return JSModulusRanger(lhs->AsRange(), rhs->AsRange(), t);
+ }
+ return Type::OrderedNumber();
}
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-typer.cc Wed Nov 5
15:19:30 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-typer.cc Thu Nov 6
13:10:20 2014 UTC
@@ -4,6 +4,7 @@
#include <functional>
+#include "src/codegen.h"
#include "src/compiler/node-properties-inl.h"
#include "src/compiler/typer.h"
#include "test/cctest/cctest.h"
@@ -14,7 +15,7 @@
using namespace v8::internal::compiler;
-
+// TODO(titzer): generate a large set of deterministic inputs for these
tests.
class TyperTester : public HandleAndZoneScope, public GraphAndBuilders {
public:
TyperTester()
@@ -79,11 +80,15 @@
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();
- int i = rng_->NextInt(static_cast<int>(numbers.size()));
- int j = rng_->NextInt(static_cast<int>(numbers.size()));
- i::Handle<i::Object> min = f->NewNumber(numbers[i]);
- i::Handle<i::Object> max = f->NewNumber(numbers[j]);
+ 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, main_zone());
}
@@ -110,18 +115,47 @@
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),
main_zone());
+ CHECK(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);
- double x1 = RandomInt(r1);
- double x2 = RandomInt(r2);
- double result_value = opfun(x1, x2);
- Type* result_type = Type::Constant(
- isolate()->factory()->NewNumber(result_value), main_zone());
- CHECK(result_type->Is(expected_type));
+ 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), main_zone());
+ CHECK(result_type->Is(expected_type));
+ }
}
}
@@ -131,13 +165,16 @@
Type::RangeType* r1 = RandomRange()->AsRange();
Type::RangeType* r2 = RandomRange()->AsRange();
Type* expected_type = TypeBinaryOp(op, r1, r2);
- 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(), main_zone());
- CHECK(result_type->Is(expected_type));
+ 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(),
+ main_zone());
+ CHECK(result_type->Is(expected_type));
+ }
}
}
@@ -147,12 +184,14 @@
Type::RangeType* r1 = RandomRange(true)->AsRange();
Type::RangeType* r2 = RandomRange(true)->AsRange();
Type* expected_type = TypeBinaryOp(op, r1, r2);
- 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), main_zone());
- CHECK(result_type->Is(expected_type));
+ 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), main_zone());
+ CHECK(result_type->Is(expected_type));
+ }
}
}
@@ -214,6 +253,12 @@
TyperTester t;
t.TestBinaryArithOp(t.javascript_.Divide(), std::divides<double>());
}
+
+
+TEST(TypeJSModulus) {
+ TyperTester t;
+ t.TestBinaryArithOp(t.javascript_.Modulus(), modulo);
+}
TEST(TypeJSBitwiseOr) {
@@ -325,10 +370,10 @@
V(Modulus)
-TEST(Monotonicity) {
- TyperTester t;
- #define TEST_OP(name) \
- t.TestBinaryMonotonicity(t.javascript_.name());
- JSBINOP_LIST(TEST_OP)
- #undef TEST_OP
-}
+#define TEST_FUNC(name) \
+ TEST(Monotonicity_##name) { \
+ TyperTester t; \
+ t.TestBinaryMonotonicity(t.javascript_.name()); \
+ }
+JSBINOP_LIST(TEST_FUNC)
+#undef TEST_FUNC
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
