Implement representation selection as part of SimplifiedLowering. Representation selection also req…

Implement representation selection as part of SimplifiedLowering. Representation selection also
requires inserting explicit representation change nodes to be inserted in the graph. Such nodes
are pure, but also need to be lowered to machine operators. They need to be scheduled first, to
determine the control input for any branches inside.

This CL requires extensive testing. More tests to follow.

R=rossberg@chromium.org
BUG=

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

[rossberg, 2014-08-06 13:04:08]

https://codereview.chromium.org/425003004/diff/20001/src/compiler/js-typed-lo...
File src/compiler/js-typed-lowering.cc (right):

https://codereview.chromium.org/425003004/diff/20001/src/compiler/js-typed-lo...
src/compiler/js-typed-lowering.cc:518: if (input_type->Is(Type::Number())) {
Why is this duplicated?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
File src/compiler/simplified-lowering.cc (left):

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:322: case IrOpcode::kLoadField:
Why did these cases disappear?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
File src/compiler/simplified-lowering.cc (right):

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:32: enum Phase {
I wish we could somehow factor this using some form of parameterisation, and not
a mode flag... :(

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:60: RepTypeUnion output : 16;  // Output
type of the node.
Why is this bitset larger than the other?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:232: // Helpers for specific types of
binops.
Nit: not sure these are worth it, but I leave it up to you.

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:247: int values = node->op()->InputCount();
Doesn't this include non-values?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:252: ProcessInput(node, iter.index(), values
> 0 ? use : 0);
Oh, this breaks the node properties abstraction quite nastily.

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:310: return VisitLeaf(node, rBit);
Nit: could combine these two cases.

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:312: return VisitLeaf(node, rBit);
Why rBit?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:343:
//------------------------------------------------------------------
Nit: weird indentation

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:369: // BooleanNot(x: rTagged) =>
WordEqual(x, #false)
Wait, why is BooleanNot overloaded on JS Booleans?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:446: // Propage a type to the input, but not
a representation.
Typo: Propagate

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:552: // We use unsigned int32 as the output
type for shift right, though
This comment is confusing. Unsigned seems adequate here. Is this a bogus copy &
paste from the next case, perhaps?

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:957: void SimplifiedLowering::Lower(Node*
node) {}
What's this still good for?

[titzer, 2014-08-07 10:51:33]

On 2014/08/06 13:04:08, rossberg wrote:
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/js-typed-lo...
> File src/compiler/js-typed-lowering.cc (right):
> 
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/js-typed-lo...
> src/compiler/js-typed-lowering.cc:518: if (input_type->Is(Type::Number())) {
> Why is this duplicated?
> 

Oversight. I think I had a special case for Int32 there before.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> File src/compiler/simplified-lowering.cc (left):
> 
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:322: case IrOpcode::kLoadField:
> Why did these cases disappear?
> 

This method only lowers Change operators now. Loads and stores of fields and
elements are handled in the VisitNode() now.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> File src/compiler/simplified-lowering.cc (right):
> 
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:32: enum Phase {
> I wish we could somehow factor this using some form of parameterisation, and
not
> a mode flag... :(

As discussed, there are a couple ways to do parameterization.

1. With a template parameter, either at the class or the method level. The code
duplication that results concerns me a little, since the entire switch and
everything would be duplicated. If at the method level, then it has to appear
through the entire chain of Visit* methods. If at the class level, then there is
even more code duplication.

2. With a boolean flag. If at the class level, then you have what I have now. If
you have it at the method level, then you have to pass it down through all the
layers.

3. With virtual methods for places where the behavior is different, either on a
passed in object, or on subclass of this class.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:60: RepTypeUnion output : 16;  // Output
> type of the node.
> Why is this bitset larger than the other?
> 

Doesn't have to be. I just steal 2 bits for the traversal state.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:232: // Helpers for specific types of
> binops.
> Nit: not sure these are worth it, but I leave it up to you.
> 

I think it helps reduce the duplication in the big-ole switch.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:247: int values =
node->op()->InputCount();
> Doesn't this include non-values?
> 

It was correct but it's clearer now with OperatorProperties.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:252: ProcessInput(node, iter.index(),
values
> > 0 ? use : 0);
> Oh, this breaks the node properties abstraction quite nastily.
> 

Well yeah if it was a proper abstraction it could tell the kinds of the edges
it's iterating over.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:310: return VisitLeaf(node, rBit);
> Nit: could combine these two cases.
> 

Done.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:312: return VisitLeaf(node, rBit);
> Why rBit?
> 

It shouldn't really matter, as they are leaf nodes and shouldn't flow into
anything except as a control or effect dependency, whose representations
_should_ be ignored. *fingers crossed*

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:343:
> //------------------------------------------------------------------
> Nit: weird indentation
> 

clang-format'd. Thaz how it iz

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:369: // BooleanNot(x: rTagged) =>
> WordEqual(x, #false)
> Wait, why is BooleanNot overloaded on JS Booleans?
> 

It's representation independent so that word32 / float64 comparisons don't have
to make a round trip to tagged when flowing through BooleanNot to a branch.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:446: // Propage a type to the input, but
not
> a representation.
> Typo: Propagate
> 

Done.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:552: // We use unsigned int32 as the
output
> type for shift right, though
> This comment is confusing. Unsigned seems adequate here. Is this a bogus copy
&
> paste from the next case, perhaps?
> 

What do you mean? The output representation is word32 and the value is
definitely an unsigned32. If it flows into a numbery thing, it needs to be
converted to a positive number.

>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> src/compiler/simplified-lowering.cc:957: void SimplifiedLowering::Lower(Node*
> node) {}
> What's this still good for?

Because LoweringBuilder.

[rossberg, 2014-08-07 13:26:47]

On 2014/08/07 10:51:33, titzer wrote:
> On 2014/08/06 13:04:08, rossberg wrote:
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > File src/compiler/simplified-lowering.cc (right):
> > 
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > src/compiler/simplified-lowering.cc:32: enum Phase {
> > I wish we could somehow factor this using some form of parameterisation, and
> not
> > a mode flag... :(
> 
> As discussed, there are a couple ways to do parameterization.
> 
> 1. With a template parameter, either at the class or the method level. The
code
> duplication that results concerns me a little, since the entire switch and
> everything would be duplicated. If at the method level, then it has to appear
> through the entire chain of Visit* methods. If at the class level, then there
is
> even more code duplication.
> 
> 2. With a boolean flag. If at the class level, then you have what I have now.
If
> you have it at the method level, then you have to pass it down through all the
> layers.
> 
> 3. With virtual methods for places where the behavior is different, either on
a
> passed in object, or on subclass of this class.

I'm actually warming up to using virtual methods here... :)


>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > src/compiler/simplified-lowering.cc:60: RepTypeUnion output : 16;  // Output
> > type of the node.
> > Why is this bitset larger than the other?
> 
> Doesn't have to be. I just steal 2 bits for the traversal state.

OK, but if RepTypeUnion fits into 14 bits, then why not make this 14 as well?


>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > src/compiler/simplified-lowering.cc:252: ProcessInput(node, iter.index(),
> values
> > > 0 ? use : 0);
> > Oh, this breaks the node properties abstraction quite nastily.
> 
> Well yeah if it was a proper abstraction it could tell the kinds of the edges
> it's iterating over.

Maybe add a TODO. At least a comment documenting the assumption.


>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > src/compiler/simplified-lowering.cc:312: return VisitLeaf(node, rBit);
> > Why rBit?
> 
> It shouldn't really matter, as they are leaf nodes and shouldn't flow into
> anything except as a control or effect dependency, whose representations
> _should_ be ignored. *fingers crossed*

Can't you use 0 then?


>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > src/compiler/simplified-lowering.cc:343:
> > //------------------------------------------------------------------
> > Nit: weird indentation
> 
> clang-format'd. Thaz how it iz

Dude, you're a big boy. Authorities only have to be respected when they behave
sanely.


>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > src/compiler/simplified-lowering.cc:552: // We use unsigned int32 as the
> output
> > type for shift right, though
> > This comment is confusing. Unsigned seems adequate here. Is this a bogus
copy
> &
> > paste from the next case, perhaps?
> 
> What do you mean? The output representation is word32 and the value is
> definitely an unsigned32. If it flows into a numbery thing, it needs to be
> converted to a positive number.

The comment essentially says "we use unsigned although there is no sign bit". I
don't get the "although".

[rossberg, 2014-08-07 14:00:45]

https://codereview.chromium.org/425003004/diff/60001/src/compiler/node-proper...
File src/compiler/node-properties.h (left):

https://codereview.chromium.org/425003004/diff/60001/src/compiler/node-proper...
src/compiler/node-properties.h:43: private:
Wait, why?

https://codereview.chromium.org/425003004/diff/60001/src/compiler/node-sketch.cc
File src/compiler/node-sketch.cc (right):

https://codereview.chromium.org/425003004/diff/60001/src/compiler/node-sketch...
src/compiler/node-sketch.cc:41: Output* target() { return target_; }
Isn't this rather a source than a target? The data is flowing from that output
to this input.

https://codereview.chromium.org/425003004/diff/60001/src/compiler/node-sketch...
src/compiler/node-sketch.cc:45: if (out == target_) return;  // Redundant.
Hm, when would you willingly connect the same edge twice?

[titzer, 2014-08-08 09:15:52]

On 2014/08/07 13:26:47, rossberg wrote:
> On 2014/08/07 10:51:33, titzer wrote:
> > On 2014/08/06 13:04:08, rossberg wrote:
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > File src/compiler/simplified-lowering.cc (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > src/compiler/simplified-lowering.cc:32: enum Phase {
> > > I wish we could somehow factor this using some form of parameterisation,
and
> > not
> > > a mode flag... :(
> > 
> > As discussed, there are a couple ways to do parameterization.
> > 
> > 1. With a template parameter, either at the class or the method level. The
> code
> > duplication that results concerns me a little, since the entire switch and
> > everything would be duplicated. If at the method level, then it has to
appear
> > through the entire chain of Visit* methods. If at the class level, then
there
> is
> > even more code duplication.
> > 
> > 2. With a boolean flag. If at the class level, then you have what I have
now.
> If
> > you have it at the method level, then you have to pass it down through all
the
> > layers.
> > 
> > 3. With virtual methods for places where the behavior is different, either
on
> a
> > passed in object, or on subclass of this class.
> 
> I'm actually warming up to using virtual methods here... :)
> 
> 
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > src/compiler/simplified-lowering.cc:60: RepTypeUnion output : 16;  //
Output
> > > type of the node.
> > > Why is this bitset larger than the other?
> > 
> > Doesn't have to be. I just steal 2 bits for the traversal state.
> 
> OK, but if RepTypeUnion fits into 14 bits, then why not make this 14 as well?
> 
> 
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > src/compiler/simplified-lowering.cc:252: ProcessInput(node, iter.index(),
> > values
> > > > 0 ? use : 0);
> > > Oh, this breaks the node properties abstraction quite nastily.
> > 
> > Well yeah if it was a proper abstraction it could tell the kinds of the
edges
> > it's iterating over.
> 
> Maybe add a TODO. At least a comment documenting the assumption.
> 
> 
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > src/compiler/simplified-lowering.cc:312: return VisitLeaf(node, rBit);
> > > Why rBit?
> > 
> > It shouldn't really matter, as they are leaf nodes and shouldn't flow into
> > anything except as a control or effect dependency, whose representations
> > _should_ be ignored. *fingers crossed*
> 
> Can't you use 0 then?
> 
> 
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > src/compiler/simplified-lowering.cc:343:
> > > //------------------------------------------------------------------
> > > Nit: weird indentation
> > 
> > clang-format'd. Thaz how it iz
> 
> Dude, you're a big boy. Authorities only have to be respected when they behave
> sanely.
> 
> 
> >
>
https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
> > > src/compiler/simplified-lowering.cc:552: // We use unsigned int32 as the
> > output
> > > type for shift right, though
> > > This comment is confusing. Unsigned seems adequate here. Is this a bogus
> copy
> > &
> > > paste from the next case, perhaps?
> > 
> > What do you mean? The output representation is word32 and the value is
> > definitely an unsigned32. If it flows into a numbery thing, it needs to be
> > converted to a positive number.
> 
> The comment essentially says "we use unsigned although there is no sign bit".
I
> don't get the "although".

I've reworded this and the other comment to be clearer (hopefully).

[titzer, 2014-08-08 09:16:14]

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
File src/compiler/simplified-lowering.cc (right):

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:32: enum Phase {
On 2014/08/06 13:04:07, rossberg wrote:
> I wish we could somehow factor this using some form of parameterisation, and
not
> a mode flag... :(

As discussed, the virtual method thing is going to result in pulling out major
portions into their own methods...

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:60: RepTypeUnion output : 16;  // Output
type of the node.
On 2014/08/06 13:04:07, rossberg wrote:
> Why is this bitset larger than the other?

Done.

https://codereview.chromium.org/425003004/diff/20001/src/compiler/simplified-...
src/compiler/simplified-lowering.cc:343:
//------------------------------------------------------------------
On 2014/08/06 13:04:07, rossberg wrote:
> Nit: weird indentation

clang-format keeps putting it back, so I'll just leave it.

[rossberg, 2014-08-08 11:33:30]

lgtm

[titzer, 2014-08-11 09:40:13]

Committed patchset #12 manually as 23026 (presubmit successful).