[turbofan] Use range types to type and lower arithmetic ops.

[turbofan] Use range types to type and lower arithmetic ops.

This is based on Georg's work on typing arithmetic operations (https://codereview.chromium.org/658743002/).

Instead of weakening to bitset types, we weaken to the closest 2^n
limit if we see that we are re-typing a node with a range type (which
means that the node can be part of a cycle, so we might need
to speed up the fixpoint there).

BUG=
R=rossberg@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=24848

[Jarin, 2014-10-22 09:26:52]

jarin@chromium.org changed reviewers:
+ bmeurer@chromium.org

[Jarin, 2014-10-23 05:38:26]

Could you take a look, please?

[Benedikt Meurer, 2014-10-23 10:33:26]

https://codereview.chromium.org/636283009/diff/100001/src/compiler/representa...
File src/compiler/representation-change.h (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/representa...
src/compiler/representation-change.h:237: op =
machine()->TruncateFloat64ToInt32();
The op is always the same in the end, probably no need to assign it inside the
conditional blocks.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:1090: for (auto i = typer_->weaken_min_limits_.begin();
range based for loops: for (const auto val : weaken_min_limits_) {...}

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:1103: for (auto i = typer_->weaken_max_limits_.begin();
range based for loops: for (const auto val : weaken_max_limits_) {...}

https://codereview.chromium.org/636283009/diff/100001/test/cctest/types-fuzz.h
File test/cctest/types-fuzz.h (right):

https://codereview.chromium.org/636283009/diff/100001/test/cctest/types-fuzz....
test/cctest/types-fuzz.h:106: Integer =
Type::Range(isolate->factory()->NewNumber(-V8_INFINITY),
Shouldn't that be -inf..inf ?

[Jarin, 2014-10-23 11:14:52]

https://codereview.chromium.org/636283009/diff/100001/src/compiler/representa...
File src/compiler/representation-change.h (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/representa...
src/compiler/representation-change.h:237: op =
machine()->TruncateFloat64ToInt32();
On 2014/10/23 10:33:26, Benedikt Meurer wrote:
> The op is always the same in the end, probably no need to assign it inside the
> conditional blocks.

While that's true, I would prefer to keep this separate.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:1090: for (auto i = typer_->weaken_min_limits_.begin();
On 2014/10/23 10:33:26, Benedikt Meurer wrote:
> range based for loops: for (const auto val : weaken_min_limits_) {...}

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:1103: for (auto i = typer_->weaken_max_limits_.begin();
On 2014/10/23 10:33:26, Benedikt Meurer wrote:
> range based for loops: for (const auto val : weaken_max_limits_) {...}

Done.

https://codereview.chromium.org/636283009/diff/100001/test/cctest/types-fuzz.h
File test/cctest/types-fuzz.h (right):

https://codereview.chromium.org/636283009/diff/100001/test/cctest/types-fuzz....
test/cctest/types-fuzz.h:106: Integer =
Type::Range(isolate->factory()->NewNumber(-V8_INFINITY),
On 2014/10/23 10:33:26, Benedikt Meurer wrote:
> Shouldn't that be -inf..inf ?

Indeed... Great catch!

[rossberg, 2014-10-23 11:50:32]

rossberg@chromium.org changed reviewers:
+ rossberg@chromium.org

[rossberg, 2014-10-23 11:50:32]

rossberg@chromium.org changed reviewers:
+ rossberg@chromium.org

[rossberg, 2014-10-23 11:50:33]

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:124: double limit = 1;
Wouldn't it make sense to go a bit faster at first? There doesn't seem much
reason to single-step through the first 30 bits, you can probably fast forward
to 2^30 directly.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:292: Type* MaybeWeaken(Type* current, Type* previous) {
Move this to Typer::Visitor as protected, to avoid duplicating it.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:430: if (type->IsRange()) return type;        // Shortcut.
Nit: put this first.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:822: double x = a[0];
What if this is already a NaN? As discussed offline, as a fix you could
initialise with -inf and start the loop from 0.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:824: x = std::min(std::isnan(a[i]) ? +V8_INFINITY : a[i],
x);
Simplify to

  if (!std::isnan(a[i])) x = std::min(x, a[i]);

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:834: static double array_max(double a[], size_t n) {
Same here.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:889: // TODO(neis): Deal with numeric bitsets here and
elsewhere.
This seems to be subsumed by Rangify.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:982: rhs->Maybe(t->singleton_zero) ||
I think this needs to check for -0 as well.

Also, instead of doing all the rhs->Maybe's separately, do one on a (predefined)
union type.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:997: rhs->Maybe(t->singleton_zero) ||
Same here.

[rossberg, 2014-10-23 11:50:34]

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:124: double limit = 1;
Wouldn't it make sense to go a bit faster at first? There doesn't seem much
reason to single-step through the first 30 bits, you can probably fast forward
to 2^30 directly.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:292: Type* MaybeWeaken(Type* current, Type* previous) {
Move this to Typer::Visitor as protected, to avoid duplicating it.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:430: if (type->IsRange()) return type;        // Shortcut.
Nit: put this first.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:822: double x = a[0];
What if this is already a NaN? As discussed offline, as a fix you could
initialise with -inf and start the loop from 0.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:824: x = std::min(std::isnan(a[i]) ? +V8_INFINITY : a[i],
x);
Simplify to

  if (!std::isnan(a[i])) x = std::min(x, a[i]);

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:834: static double array_max(double a[], size_t n) {
Same here.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:889: // TODO(neis): Deal with numeric bitsets here and
elsewhere.
This seems to be subsumed by Rangify.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:982: rhs->Maybe(t->singleton_zero) ||
I think this needs to check for -0 as well.

Also, instead of doing all the rhs->Maybe's separately, do one on a (predefined)
union type.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:997: rhs->Maybe(t->singleton_zero) ||
Same here.

[neis, 2014-10-23 12:43:05]

neis@chromium.org changed reviewers:
+ neis@chromium.org

[neis, 2014-10-23 12:43:06]

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:292: Type* MaybeWeaken(Type* current, Type* previous) {
On 2014/10/23 11:50:33, rossberg wrote:
> Move this to Typer::Visitor as protected, to avoid duplicating it.

Also the comment no longer matches the code.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:822: double x = a[0];
On 2014/10/23 11:50:33, rossberg wrote:
> What if this is already a NaN? As discussed offline, as a fix you could
> initialise with -inf and start the loop from 0.

If x is nan initially, the result of the first min() will be whatever the first
argument is, i.e. not nan.

So I think the code is correct, although I also admit it's not the clearest.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:889: // TODO(neis): Deal with numeric bitsets here and
elsewhere.
On 2014/10/23 11:50:33, rossberg wrote:
> This seems to be subsumed by Rangify.

Rangify converts a union of integer constants and possibly a range to a range. 
Its result is always a supertype of its argument.  It does not deal with
bitsets, although it might be possible to do that here as well.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:982: rhs->Maybe(t->singleton_zero) ||
On 2014/10/23 11:50:33, rossberg wrote:
> I think this needs to check for -0 as well.
> 
> Also, instead of doing all the rhs->Maybe's separately, do one on a
(predefined)
> union type.

Acknowledged.

[Jarin, 2014-10-23 13:32:37]

All should be done now. Thanks for detailed comments!

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:124: double limit = 1;
On 2014/10/23 11:50:33, rossberg wrote:
> Wouldn't it make sense to go a bit faster at first? There doesn't seem much
> reason to single-step through the first 30 bits, you can probably fast forward
> to 2^30 directly.

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:292: Type* MaybeWeaken(Type* current, Type* previous) {
On 2014/10/23 11:50:33, rossberg wrote:
> Move this to Typer::Visitor as protected, to avoid duplicating it.

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:430: if (type->IsRange()) return type;        // Shortcut.
On 2014/10/23 11:50:33, rossberg wrote:
> Nit: put this first.

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:822: double x = a[0];
On 2014/10/23 11:50:33, rossberg wrote:
> What if this is already a NaN? As discussed offline, as a fix you could
> initialise with -inf and start the loop from 0.

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:824: x = std::min(std::isnan(a[i]) ? +V8_INFINITY : a[i],
x);
On 2014/10/23 11:50:33, rossberg wrote:
> Simplify to
> 
>   if (!std::isnan(a[i])) x = std::min(x, a[i]);

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:834: static double array_max(double a[], size_t n) {
On 2014/10/23 11:50:33, rossberg wrote:
> Same here.

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:982: rhs->Maybe(t->singleton_zero) ||
On 2014/10/23 12:43:06, neis wrote:
> On 2014/10/23 11:50:33, rossberg wrote:
> > I think this needs to check for -0 as well.
> > 
> > Also, instead of doing all the rhs->Maybe's separately, do one on a
> (predefined)
> > union type.
> 
> Acknowledged.

Done.

https://codereview.chromium.org/636283009/diff/100001/src/compiler/typer.cc#n...
src/compiler/typer.cc:997: rhs->Maybe(t->singleton_zero) ||
On 2014/10/23 11:50:33, rossberg wrote:
> Same here.

Done.

[rossberg, 2014-10-23 13:44:27]

https://codereview.chromium.org/636283009/diff/140001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/140001/src/compiler/typer.cc#n...
src/compiler/typer.cc:1066: Type* Typer::Visitor::MaybeWeaken(Type* current,
Type* previous) {
Is there any reason left not to merge the Weaken function into this one?

[Jarin, 2014-10-23 13:55:00]

https://codereview.chromium.org/636283009/diff/140001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/140001/src/compiler/typer.cc#n...
src/compiler/typer.cc:1066: Type* Typer::Visitor::MaybeWeaken(Type* current,
Type* previous) {
On 2014/10/23 13:44:27, rossberg wrote:
> Is there any reason left not to merge the Weaken function into this one?

Done.

[rossberg, 2014-10-23 14:17:15]

lgtm

https://codereview.chromium.org/636283009/diff/160001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/636283009/diff/160001/src/compiler/typer.cc#n...
src/compiler/typer.cc:203: Type* MaybeWeaken(Type* current_type, Type*
previous_type);
Nit: perhaps rename to simply Weaken now.

[Jarin, 2014-10-23 14:40:57]

Committed patchset #10 (id:180001) manually as 24848 (presubmit successful).