Refine expression typing, esp. by propagating range information.

Refine expression typing, esp. by propagating range information.

R=rossberg@chromium.org
BUG=

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

[neis1, 2014-10-01 12:34:40]

Please have a look.  I removed the arithmetic range calculations from this. 
They were wrong and will go in a separate CL.

[rossberg, 2014-10-02 11:57:34]

Like it! However, I think there is an issue with lower bounds in some cases.
Also, some tests would be good...

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

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:165: typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
Is there a reason why we can't make these Visitor member pointers and get rid of
the explicit Typer argument?

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:186: static Type* JSEqualTyper(Type*, Type*, Typer*);
Can we create this list from macros as well?

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:333: : (upper->IsConstant() || input.lower == input.upper)
Check the latter condition first.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:382: if (type->Is(Type::Object())) return
t->singleton_true;
Receiver? In fact, you need to distinguish Detectable and Undetectable here (the
latter is some DOM abomination that converts to false).

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:384: if ((type->IsRange() || type->Is(Type::Integral32()))
&&
Why doesn't this apply to all numbers?

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:569: static Type* ESType(Type* type) {
Nit: call this JSType, since JS is what we say everywhere else.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:602: Type* Typer::Visitor::JSCompareTyper(Type* lhs, Type*
rhs, Typer* t) {
Add a comment saying that the comparison is <, returning undefined for
unordered.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:649: Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs,
Type* rhs, Typer* t) {
Shouldn't these functions also detect the cases where both inputs are constants
or singleton ranges? (Could be a TODO)

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:871: return TypeBinaryOp(node, JSLoadPropertyTyper);
This doesn't seem right. The lower bound would become Any most of the time.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:1011: return TypeUnaryOp(node, JSCallFunctionTyper);  //
We ignore argument types.
Same here.

[neis1, 2014-10-02 15:29:11]

I'm working on tests now.  Can they go into a separate CL?

More comments below:

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

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:165: typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
On 2014/10/02 11:57:33, rossberg wrote:
> Is there a reason why we can't make these Visitor member pointers and get rid
of
> the explicit Typer argument?

These functions need access to the private members of Typer.  From what I
understand, this is only guaranteed by C++11.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:186: static Type* JSEqualTyper(Type*, Type*, Typer*);
On 2014/10/02 11:57:33, rossberg wrote:
> Can we create this list from macros as well?

Done.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:333: : (upper->IsConstant() || input.lower == input.upper)
On 2014/10/02 11:57:33, rossberg wrote:
> Check the latter condition first.

Done.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:382: if (type->Is(Type::Object())) return
t->singleton_true;
On 2014/10/02 11:57:33, rossberg wrote:
> Receiver? In fact, you need to distinguish Detectable and Undetectable here
(the
> latter is some DOM abomination that converts to false).

Right, I meant Receiver.

Okay, I wasn't aware of Detectable vs Undetectable.  It's not mentioned in
http://people.mozilla.org/~jorendorff/es6-draft.html#sec-toboolean. Any other
weird creatures that I should know about?

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:384: if ((type->IsRange() || type->Is(Type::Integral32()))
&&
On 2014/10/02 11:57:33, rossberg wrote:
> Why doesn't this apply to all numbers?

Because of nan (e.g. if type is e.g. SignedSmall|NaN, then the Min/Max condition
holds because Max() is -1 but of course the argument might be nan, which is
converted to false).

However, I can just use OrderedNumber here.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:569: static Type* ESType(Type* type) {
On 2014/10/02 11:57:34, rossberg wrote:
> Nit: call this JSType, since JS is what we say everywhere else.

Done.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:602: Type* Typer::Visitor::JSCompareTyper(Type* lhs, Type*
rhs, Typer* t) {
On 2014/10/02 11:57:33, rossberg wrote:
> Add a comment saying that the comparison is <, returning undefined for
> unordered.

Done.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:649: Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs,
Type* rhs, Typer* t) {
On 2014/10/02 11:57:33, rossberg wrote:
> Shouldn't these functions also detect the cases where both inputs are
constants
> or singleton ranges? (Could be a TODO)

Yes, that's a natural extension.  Added a TODO.

https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:871: return TypeBinaryOp(node, JSLoadPropertyTyper);
On 2014/10/02 11:57:33, rossberg wrote:
> This doesn't seem right. The lower bound would become Any most of the time.

Yep, I expected this complaint.  I don't really understand what we require of
the lower bound.  Does it make sense to say that for operators that return a
number, the return type's lower bound should be at most SignedSmall?  What about
non-numerical operators like LoadProperty?  When should the lower bound be None?

[rossberg, 2014-10-02 15:46:00]

On 2014/10/02 15:29:11, neis1 wrote:
> I'm working on tests now.  Can they go into a separate CL?

Well, we usually shouldn't land non-trivial stuff without at least some relevant
tests. So I'd prefer to have some first.

> These functions need access to the private members of Typer.  From what I
> understand, this is only guaranteed by C++11.

Interesting. 8-/

> Okay, I wasn't aware of Detectable vs Undetectable.  It's not mentioned in
> http://people.mozilla.org/~jorendorff/es6-draft.html#sec-toboolean. Any other
> weird creatures that I should know about?

Yeah, it's one of these fabulous DOM "features" that break even the last
invariants that JavaScript still has.

But I don't think there is any other that's relevant here.

>
https://codereview.chromium.org/618803003/diff/40001/src/compiler/typer.cc#ne...
> src/compiler/typer.cc:871: return TypeBinaryOp(node, JSLoadPropertyTyper);
> On 2014/10/02 11:57:33, rossberg wrote:
> > This doesn't seem right. The lower bound would become Any most of the time.
> 
> Yep, I expected this complaint.  I don't really understand what we require of
> the lower bound.  Does it make sense to say that for operators that return a
> number, the return type's lower bound should be at most SignedSmall?  What
about
> non-numerical operators like LoadProperty?  When should the lower bound be
None?

In general, when we don't know for sure (like with constants, or when implied by
lower bounds on operands), the synthesized lower bound should be None. The Smi
thing for numbers was rather a hack. It's fine to drop that for now in favour of
None as well.

[neis1, 2014-10-06 10:23:03]

Please have a look at the latest patch set.  Regarding the lower bound, I didn't
have a better idea.

[rossberg, 2014-10-06 11:28:00]

Looks good, but the lower bound thing still seems off. See comment below.

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

https://codereview.chromium.org/618803003/diff/50001/src/compiler/typer.cc#ne...
src/compiler/typer.cc:322: lower = Type::Any()->Is(lower) ? Type::None() :
lower;  // Keep it low.
Hm, this seems hacky and incomplete. What about the case where the default upper
bound is Number, but the lower still should be None (or Smi)? Or imagine you had
an operator that returns a pair (if we had such a thing), then you'd still get
(Any,Any) where the lower bound should be (None,None).

I'm not sure what a correct generic solution would be, perhaps passing the
"don't know anything" default type as a parameter?

[neis1, 2014-10-13 09:41:17]

On 2014/10/06 11:28:00, rossberg wrote:
> Looks good, but the lower bound thing still seems off. See comment below.
> 
> https://codereview.chromium.org/618803003/diff/50001/src/compiler/typer.cc
> File src/compiler/typer.cc (right):
> 
>
https://codereview.chromium.org/618803003/diff/50001/src/compiler/typer.cc#ne...
> src/compiler/typer.cc:322: lower = Type::Any()->Is(lower) ? Type::None() :
> lower;  // Keep it low.
> Hm, this seems hacky and incomplete. What about the case where the default
upper
> bound is Number, but the lower still should be None (or Smi)? Or imagine you
had
> an operator that returns a pair (if we had such a thing), then you'd still get
> (Any,Any) where the lower bound should be (None,None).
> 
> I'm not sure what a correct generic solution would be, perhaps passing the
> "don't know anything" default type as a parameter?

As discussed, reverted handling of lower bound to previous patchset and marked
as TODO.

[rossberg, 2014-10-13 09:48:03]

lgtm

[neis, 2014-10-13 10:40:41]

Committed patchset #5 (id:70001) manually as 24552 (presubmit successful).