Introduce number type information in the virtual frame.

Introduce number type information in the virtual frame. 

Each frame element gets a new attribute with number type information. A frame element can be: 

- smi 
- heap number 
- number (i.e. either of the above) 
- or something else. 

The type information is propagated along with all virtual frame operations. 
Results popped from the frame carry the number information with them.

Two optimizations in the code generator make use of the new 
information: 
- GenericBinaryOpSyub omits map checks if input operands are numbers. 
- Boolean conversion for numbers: Emit inline code for converting a number (smi or heap number) to boolean. Do not emit call to ToBoolean stub in this case.



Committed: http://code.google.com/p/v8/source/detail?r=3861

[fschneider, 2010-01-12 11:39:33]

This is a first version.

[fschneider, 2010-01-14 14:00:07]

Uploaded new version:

- Refactored NumberInfo to be a separate class
- Make use of order of enum values when merging type information

[Kevin Millikin (Chromium), 2010-01-14 15:47:30]

http://codereview.chromium.org/545007/diff/5033/6018
File src/frame-element.h (right):

http://codereview.chromium.org/545007/diff/5033/6018#newcode56
src/frame-element.h:56: NumberInfo::Type number_info() {
For functions like this, where every case returns, I prefer:

if (!is_constant) return NumberInfoField::decode(value_);
Handle<Object> value = handle();
if (value->IsSmi()) return NumberInfo::kSmi;
if (value->IsHeapNumber()) return NumberInfo::kHeapNumber;
return NumberInfo::kUnknown;

You might also consider that this function is big enough that we don't want to
inline it.

http://codereview.chromium.org/545007/diff/5033/6018#newcode210
src/frame-element.h:210: FrameElement(Type type, Register reg, SyncFlag
is_synced, NumberInfo::Type info) {
Long line.

http://codereview.chromium.org/545007/diff/5033/6018#newcode253
src/frame-element.h:253: class DataField: public BitField<uint32_t, 8, 32 - 9>
{};
I think you've got 24 bits for this field (32 - 8).

http://codereview.chromium.org/545007/diff/5033/6013
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/545007/diff/5033/6013#newcode709
src/ia32/codegen-ia32.cc:709: if (frame_->IsNumberAt(0)) {
I think results should have number_info too.  If they don't then we lose info
about values as soon as they leave the frame, and there's no way to associate
info with values that aren't on (or never will be on) the frame.

The common code here is:

Result value = frame_->Pop();
value.ToRegister();
if(value.IsNumber()) {
  ...
} else {
  ...
}

You might also consider emitting debug code that verifies that we always have a
number at runtime in the only number case.

http://codereview.chromium.org/545007/diff/5033/6013#newcode790
src/ia32/codegen-ia32.cc:790: static void LoadSse2Operands(MacroAssembler*
masm);
I like LoadSSE2Operands better.

http://codereview.chromium.org/545007/diff/5033/6014
File src/ia32/codegen-ia32.h (right):

http://codereview.chromium.org/545007/diff/5033/6014#newcode715
src/ia32/codegen-ia32.h:715: // Minor key encoding in 16 bits NFRASOOOOOOOOOMM.
OK, and just delete the comment about the previous minor key encoding.

http://codereview.chromium.org/545007/diff/5033/6015
File src/ia32/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/545007/diff/5033/6015#newcode191
src/ia32/virtual-frame-ia32.cc:191: NumberInfo::kUnknownType);   // Forget
number info.
Long line.

http://codereview.chromium.org/545007/diff/5033/6015#newcode224
src/ia32/virtual-frame-ia32.cc:224:
elements_[i].set_number_info(NumberInfo::kUnknownType);   // Forget number info.
Long line.

http://codereview.chromium.org/545007/diff/5033/6016
File src/ia32/virtual-frame-ia32.h (right):

http://codereview.chromium.org/545007/diff/5033/6016#newcode399
src/ia32/virtual-frame-ia32.h:399: NumberInfo::Type GetNumberInfoAt(int index);
We don't usually provide an interface for clients to inspect elements of the
frame.  The biggest reason is that a lot of things (like simply binding a label)
can change the frame's state and invalidate client assumptions.

http://codereview.chromium.org/545007/diff/5033/6017
File src/jump-target.cc (right):

http://codereview.chromium.org/545007/diff/5033/6017#newcode105
src/jump-target.cc:105: FrameElement* other =
&reaching_frames_[j]->elements_[i];
I think this is safe but it seems fishy.  FrameElement::Combine returns a
pointer to one of its arguments.  Binding a label should not change what we know
about the frames coming into the label.

http://codereview.chromium.org/545007/diff/5033/6017#newcode136
src/jump-target.cc:136:
entry_frame_->elements_.Add(FrameElement::MemoryElement(NumberInfo::kUninitializedType));
Long line.

It seems strange that after this loop, the NULL elements are memory frame
elements with Unknown type if they are arguments or local variables, and
Uninitialized type if they are in the expression stack.

You always reset them anyway, but this seems like a potential bug down the line.

http://codereview.chromium.org/545007/diff/5033/6017#newcode171
src/jump-target.cc:171: // If the value is synced on all frames, put it in
memory.  This
You might consider asserting that the type is not uninitialized here.

http://codereview.chromium.org/545007/diff/5033/6017#newcode199
src/jump-target.cc:199: FrameElement::NOT_SYNCED,
NumberInfo::kUninitializedType);
Long line.

http://codereview.chromium.org/545007/diff/5033/6017#newcode209
src/jump-target.cc:209: if (direction_ == BIDIRECTIONAL) {
I'd get rid of this extra loop.  You can check the frame's direction when you
combine elements in the very first loop, and also when you set the info for
reallocated elements.

http://codereview.chromium.org/545007/diff/5033/6012
File src/numberinfo.h (right):

http://codereview.chromium.org/545007/diff/5033/6012#newcode1
src/numberinfo.h:1: // Copyright 2010 the V8 project authors. All rights
reserved.
Can you rename this file to number-info.h?

http://codereview.chromium.org/545007/diff/5033/6012#newcode37
src/numberinfo.h:37: kUnknownType = 0,
I prefer kUnknown, kSmi, kHeapNumber, etc.  "Type" seems redundant.

http://codereview.chromium.org/545007/diff/5033/6012#newcode44
src/numberinfo.h:44: static Type Combine(Type a, Type b) {
As we discussed, you could simplify this a bit more.

http://codereview.chromium.org/545007/diff/5033/6019
File src/virtual-frame.cc (right):

http://codereview.chromium.org/545007/diff/5033/6019#newcode102
src/virtual-frame.cc:102:
elements_.Add(FrameElement::MemoryElement(NumberInfo::kUninitializedType));
You mean kUnknown?

http://codereview.chromium.org/545007/diff/5033/6019#newcode307
src/virtual-frame.cc:307: original.number_info());
This can't be right, you are overwriting the original.  I think you have to have
Unknown number info here (unless you put number info on Results).

http://codereview.chromium.org/545007/diff/5033/6019#newcode333
src/virtual-frame.cc:333: FrameElement::NOT_SYNCED, info);
The line breaks here look weird.

[fschneider, 2010-01-19 19:01:51]

Uploaded new version (ia-32 only). Tests pass. Needs another round of cleanup.
- Results have number information, too.
- Copied frame elements do not have number information.
- Added a few asserts
- Refactored binary operation helpers to return results in all places.

http://codereview.chromium.org/545007/diff/5033/6018
File src/frame-element.h (right):

http://codereview.chromium.org/545007/diff/5033/6018#newcode56
src/frame-element.h:56: NumberInfo::Type number_info() {
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> For functions like this, where every case returns, I prefer:
> 
> if (!is_constant) return NumberInfoField::decode(value_);
> Handle<Object> value = handle();
> if (value->IsSmi()) return NumberInfo::kSmi;
> if (value->IsHeapNumber()) return NumberInfo::kHeapNumber;
> return NumberInfo::kUnknown;
> 
> You might also consider that this function is big enough that we don't want to
> inline it.

Done. Moved to frame-element.cc.

http://codereview.chromium.org/545007/diff/5033/6018#newcode210
src/frame-element.h:210: FrameElement(Type type, Register reg, SyncFlag
is_synced, NumberInfo::Type info) {
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> Long line.

Done.

http://codereview.chromium.org/545007/diff/5033/6018#newcode253
src/frame-element.h:253: class DataField: public BitField<uint32_t, 8, 32 - 9>
{};
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> I think you've got 24 bits for this field (32 - 8).

Correct, but the current BitField implemenations computes the mask in way that
requires a shift-value > 31 in this case. It gives an compiler error when using
(32 - 8).

I think the mask computation could be corrected so that we can actually use all
bits of a 32-bit value for a bitfield.

http://codereview.chromium.org/545007/diff/5033/6013
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/545007/diff/5033/6013#newcode709
src/ia32/codegen-ia32.cc:709: if (frame_->IsNumberAt(0)) {
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> I think results should have number_info too.  If they don't then we lose info
> about values as soon as they leave the frame, and there's no way to associate
> info with values that aren't on (or never will be on) the frame.
> 
> The common code here is:
> 
> Result value = frame_->Pop();
> value.ToRegister();
> if(value.IsNumber()) {
>   ...
> } else {
>   ...
> }
> 
> You might also consider emitting debug code that verifies that we always have
a
> number at runtime in the only number case.

Agree. I'm removing the public interface to the number type information from the
virtual frame.

Also adding debug code with FLAG_debug_code.

http://codereview.chromium.org/545007/diff/5033/6013#newcode790
src/ia32/codegen-ia32.cc:790: static void LoadSse2Operands(MacroAssembler*
masm);
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> I like LoadSSE2Operands better.

Yes :)

http://codereview.chromium.org/545007/diff/5033/6014
File src/ia32/codegen-ia32.h (right):

http://codereview.chromium.org/545007/diff/5033/6014#newcode715
src/ia32/codegen-ia32.h:715: // Minor key encoding in 16 bits NFRASOOOOOOOOOMM.
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> OK, and just delete the comment about the previous minor key encoding.

Done.

http://codereview.chromium.org/545007/diff/5033/6015
File src/ia32/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/545007/diff/5033/6015#newcode191
src/ia32/virtual-frame-ia32.cc:191: NumberInfo::kUnknownType);   // Forget
number info.
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> Long line.

Done.

http://codereview.chromium.org/545007/diff/5033/6015#newcode224
src/ia32/virtual-frame-ia32.cc:224:
elements_[i].set_number_info(NumberInfo::kUnknownType);   // Forget number info.
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> Long line.

Done.

http://codereview.chromium.org/545007/diff/5033/6016
File src/ia32/virtual-frame-ia32.h (right):

http://codereview.chromium.org/545007/diff/5033/6016#newcode399
src/ia32/virtual-frame-ia32.h:399: NumberInfo::Type GetNumberInfoAt(int index);
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> We don't usually provide an interface for clients to inspect elements of the
> frame.  The biggest reason is that a lot of things (like simply binding a
label)
> can change the frame's state and invalidate client assumptions.

Done. Removed these methods. Instead added a number info interface to the Result
class.

http://codereview.chromium.org/545007/diff/5033/6017
File src/jump-target.cc (right):

http://codereview.chromium.org/545007/diff/5033/6017#newcode105
src/jump-target.cc:105: FrameElement* other =
&reaching_frames_[j]->elements_[i];
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> I think this is safe but it seems fishy.  FrameElement::Combine returns a
> pointer to one of its arguments.  Binding a label should not change what we
know
> about the frames coming into the label.

Done. I'm making computeEntryFrame non-destructive for the number type
information of the incoming frames.

http://codereview.chromium.org/545007/diff/5033/6017#newcode136
src/jump-target.cc:136:
entry_frame_->elements_.Add(FrameElement::MemoryElement(NumberInfo::kUninitializedType));
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> Long line.
> 
> It seems strange that after this loop, the NULL elements are memory frame
> elements with Unknown type if they are arguments or local variables, and
> Uninitialized type if they are in the expression stack.
> 
> You always reset them anyway, but this seems like a potential bug down the
line.

Yes. The elements should be either uninitialized or set to their correct type.

http://codereview.chromium.org/545007/diff/5033/6017#newcode171
src/jump-target.cc:171: // If the value is synced on all frames, put it in
memory.  This
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> You might consider asserting that the type is not uninitialized here.

Done.

http://codereview.chromium.org/545007/diff/5033/6017#newcode199
src/jump-target.cc:199: FrameElement::NOT_SYNCED,
NumberInfo::kUninitializedType);
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> Long line.

Done.

http://codereview.chromium.org/545007/diff/5033/6017#newcode209
src/jump-target.cc:209: if (direction_ == BIDIRECTIONAL) {
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> I'd get rid of this extra loop.  You can check the frame's direction when you
> combine elements in the very first loop, and also when you set the info for
> reallocated elements.

Agree. This loop is not the right way to do it. I'm adding an assert here to
make sure we handle bidirectional correctly.

http://codereview.chromium.org/545007/diff/5033/6012
File src/numberinfo.h (right):

http://codereview.chromium.org/545007/diff/5033/6012#newcode1
src/numberinfo.h:1: // Copyright 2010 the V8 project authors. All rights
reserved.
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> Can you rename this file to number-info.h?

Done.

http://codereview.chromium.org/545007/diff/5033/6012#newcode37
src/numberinfo.h:37: kUnknownType = 0,
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> I prefer kUnknown, kSmi, kHeapNumber, etc.  "Type" seems redundant.

Done. It saves typing characters, too.

http://codereview.chromium.org/545007/diff/5033/6012#newcode44
src/numberinfo.h:44: static Type Combine(Type a, Type b) {
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> As we discussed, you could simplify this a bit more.

Done.

http://codereview.chromium.org/545007/diff/5033/6019
File src/virtual-frame.cc (right):

http://codereview.chromium.org/545007/diff/5033/6019#newcode102
src/virtual-frame.cc:102:
elements_.Add(FrameElement::MemoryElement(NumberInfo::kUninitializedType));
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> You mean kUnknown?

Done. So if I understand correct, Adjust is called when we want the virtual
frame to match the state of the stack. In this case we don't know what has been
put on the stack. (-> kUnknown)

http://codereview.chromium.org/545007/diff/5033/6019#newcode307
src/virtual-frame.cc:307: original.number_info());
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> This can't be right, you are overwriting the original.  I think you have to
have
> Unknown number info here (unless you put number info on Results).

Done.

Will be replaced with the number type of the result passed as an argument to
SetElementAt.

http://codereview.chromium.org/545007/diff/5033/6019#newcode333
src/virtual-frame.cc:333: FrameElement::NOT_SYNCED, info);
On 2010/01/14 15:47:30, Kevin Millikin wrote:
> The line breaks here look weird.

Done.

[fschneider, 2010-01-28 17:34:11]

Uploaded new version:
+Merged with latest revision.
+Added debug code to verify assumptions about numbers.

[fschneider, 2010-02-11 12:55:04]

Uploaded x64 version.

[Kevin Millikin (Chromium), 2010-02-15 13:02:09]

A few comments below.  It basically LGTM.

http://codereview.chromium.org/545007/diff/16001/17008
File src/frame-element.h (right):

http://codereview.chromium.org/545007/diff/16001/17008#newcode240
src/frame-element.h:240: class CopiedField: public BitField<uint32_t, 3, 1> {};
Could you change the type to "bool" on this field and the next?

http://codereview.chromium.org/545007/diff/16001/17002
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/545007/diff/16001/17002#newcode1005
src/ia32/codegen-ia32.cc:1005: bool left_is_non_smi = left.is_constant() &&
!left.handle()->IsSmi();
This should probably be renamed to left_is_non_smi_constant.

http://codereview.chromium.org/545007/diff/16001/17002#newcode1059
src/ia32/codegen-ia32.cc:1059: if (only_numbers)
All on one line like

if (only_numbers) info = NumberInfo::kNumber;

or else braces like

if (only_numbers) {
  info = NumberInfo::kNumber;
}

http://codereview.chromium.org/545007/diff/16001/17002#newcode7573
src/ia32/codegen-ia32.cc:7573: if (only_numbers_in_stub_) {
You could also optimize the non-sse version, no?

http://codereview.chromium.org/545007/diff/16001/17002#newcode7604
src/ia32/codegen-ia32.cc:7604: GenerateHeapResultAllocation(masm,
&call_runtime);
In the only numbers case, you can do the allocation before the XMM register load
(because the xmm load can't fail).  I think you would have to preserve eax for
the heap allocation or (better yet) pass a desired result register to
GenerateHeapResultAllocation.

http://codereview.chromium.org/545007/diff/16001/17002#newcode8079
src/ia32/codegen-ia32.cc:8079: void
FloatingPointHelper::LoadSSE2Operands(MacroAssembler* masm) {
If this takes a scratch register you can use the scratch register for smi
untagging, then you don't have to retag.

http://codereview.chromium.org/545007/diff/21001/22007
File src/jump-target.cc (right):

http://codereview.chromium.org/545007/diff/21001/22007#newcode109
src/jump-target.cc:109:
element->set_number_info(NumberInfo::Combine(element->number_info(),
I'd like a short comment here to point out that we're changing the number info
on one of the incoming frames but that it's safe because we only use that frame
for emitting merge code.

http://codereview.chromium.org/545007/diff/21001/22006
File src/number-info.h (right):

http://codereview.chromium.org/545007/diff/21001/22006#newcode28
src/number-info.h:28: #ifndef V8_NUMBERINFO_H_
The include guard should be V8_NUMBER_INFO_H_

http://codereview.chromium.org/545007/diff/21001/22006#newcode54
src/number-info.h:54: #endif  // V8_kNumberTypeINFO_H_
Too much search and replace.

[fschneider, 2010-02-15 14:07:41]

Addressed comment + fixed lint errors.

http://codereview.chromium.org/545007/diff/16001/17008
File src/frame-element.h (right):

http://codereview.chromium.org/545007/diff/16001/17008#newcode240
src/frame-element.h:240: class CopiedField: public BitField<uint32_t, 3, 1> {};
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> Could you change the type to "bool" on this field and the next?

Done.

http://codereview.chromium.org/545007/diff/16001/17002
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/545007/diff/16001/17002#newcode1005
src/ia32/codegen-ia32.cc:1005: bool left_is_non_smi = left.is_constant() &&
!left.handle()->IsSmi();
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> This should probably be renamed to left_is_non_smi_constant.

Done.

http://codereview.chromium.org/545007/diff/16001/17002#newcode1059
src/ia32/codegen-ia32.cc:1059: if (only_numbers)
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> All on one line like
> 
> if (only_numbers) info = NumberInfo::kNumber;
> 
> or else braces like
> 
> if (only_numbers) {
>   info = NumberInfo::kNumber;
> }

Done.

http://codereview.chromium.org/545007/diff/16001/17002#newcode7573
src/ia32/codegen-ia32.cc:7573: if (only_numbers_in_stub_) {
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> You could also optimize the non-sse version, no?

Done. I also added a macro assembler function to emit the debug-code to avoid
code duplication for this check.

http://codereview.chromium.org/545007/diff/16001/17002#newcode7604
src/ia32/codegen-ia32.cc:7604: GenerateHeapResultAllocation(masm,
&call_runtime);
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> In the only numbers case, you can do the allocation before the XMM register
load
> (because the xmm load can't fail).  I think you would have to preserve eax for
> the heap allocation or (better yet) pass a desired result register to
> GenerateHeapResultAllocation.

Doing as a separate change.

http://codereview.chromium.org/545007/diff/16001/17002#newcode8079
src/ia32/codegen-ia32.cc:8079: void
FloatingPointHelper::LoadSSE2Operands(MacroAssembler* masm) {
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> If this takes a scratch register you can use the scratch register for smi
> untagging, then you don't have to retag.

Good point. I'll do this as a separate change.

http://codereview.chromium.org/545007/diff/21001/22007
File src/jump-target.cc (right):

http://codereview.chromium.org/545007/diff/21001/22007#newcode109
src/jump-target.cc:109:
element->set_number_info(NumberInfo::Combine(element->number_info(),
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> I'd like a short comment here to point out that we're changing the number info
> on one of the incoming frames but that it's safe because we only use that
frame
> for emitting merge code.

Done.

http://codereview.chromium.org/545007/diff/21001/22006
File src/number-info.h (right):

http://codereview.chromium.org/545007/diff/21001/22006#newcode28
src/number-info.h:28: #ifndef V8_NUMBERINFO_H_
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> The include guard should be V8_NUMBER_INFO_H_

Done.

http://codereview.chromium.org/545007/diff/21001/22006#newcode54
src/number-info.h:54: #endif  // V8_kNumberTypeINFO_H_
On 2010/02/15 13:02:09, Kevin Millikin wrote:
> Too much search and replace.

Indeed :)

Done.