Eliminate temporary locals for some expressions

Eliminate temporary locals for some expressions

This CL affects a subset of expressions that use temporary locals: constructor
calls, array literals and and instance getter postfix-ops.

For expressions that are de-sugared in the parser I added LetNode.
It creates a scoped temporary local bound to an initializing expression.

For expressions where we need a temporary local at graph-building time,
I added a helper class TempLocalScope to easily create a single temporary
local in the graph builder since this is a frequently recurring pattern.

This simplifies code in the parser and the graph builder and also fixes a
bug with indexed-super invocation and NoSuchMethod.

BUG=dart:8918
R=kmillikin@google.com

Committed: https://code.google.com/p/dart/source/detail?r=23401

[Florian Schneider, 2013-05-28 13:21:59]

Request for comments:

I started migrating three expressions: constructor calls, array literals, and
instance-getter postfix-ops (e.x++).

[srdjan, 2013-05-28 13:30:43]

DBC

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
File runtime/vm/flow_graph_builder.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
runtime/vm/flow_graph_builder.cc:1845: ASSERT(value->definition()->temp_index()
== visitor->temp_index() - 1);
weird indent of body

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.h:3173: 
private:

[hausner, 2013-05-28 17:00:47]

DBC.

The idea of the change looks nice to me. The biggest issue IMO is that you are
handling only one particular case where temporary variables are needed. See
comment below.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.cc
File runtime/vm/ast.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.cc#newcode83
runtime/vm/ast.cc:83: OS::SNPrint(name, 64, ":lt%"Pd"_%"Pd, token_pos, i);
64 -> sizeof name

For our own debugging purposes, might be nice to separate the token position and
the temp index with an _ or some other character.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h
File runtime/vm/ast.h (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h#newcode305
runtime/vm/ast.h:305: void SetTempExpression(intptr_t i, AstNode* node) {
We typically use the ending -At for setters that are indexed:
SetTempExpressionAt(i, node).

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (left):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/bit_vector.h#o...
runtime/vm/bit_vector.h:51: ASSERT(length > 0);
Why remove this?

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7738: const intptr_t token_pos = TokenPos();
Why are you renaming this? The old name expresses what is at that particular
token position.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7749: if (postfix_expr->IsInstanceGetterNode()) {
I think this special case needs to be handled in
PrepareCompoundAssignmentNodes(), not here. If you do it just here, you only
handle o.x++, but not o.x += 1, nor ++o.x, and neither cascades.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7805: const LocalVariable* temp = GetIncrementTempLocal();
Can this temporary local variable be handled with your new LetNode construct? If
so, please at least add TODOs where simplification is possible.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/scopes.h
File runtime/vm/scopes.h (left):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/scopes.h#oldco...
runtime/vm/scopes.h:66: ASSERT(!HasIndex());
Why are you removing these asserts? Does your change depend on being able to set
an index on a variable that has already been allocated? That would seem wrong to
me.

[Kevin Millikin (Google), 2013-05-29 11:28:23]

This looks like a good approach.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h
File runtime/vm/ast.h (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h#newcode302
runtime/vm/ast.h:302: const GrowableArray<AstNode*>& temp_expressions() const {
'temp_expression' sounds like the expression is temporary.  I would use
something more like 'initializer'.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h#newcode323
runtime/vm/ast.h:323: AstNode* body_;
I think you should: (1) allow a list of AstNode* in the body instead of just
one, (2) eliminate CommaNode and replace all occurrences with a LetNode with 0
bindings.

It should just work in the graph builder and compiler (provided __ Drop(0) has
special handling), except for some wartiness about LetNode in effect contexts
(which I think should be fixed anyway).

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
File runtime/vm/flow_graph_builder.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
runtime/vm/flow_graph_builder.cc:1888: ReturnDefinition(new
DropTempsInstr(num_temps, result_value));
It's a bit unfortunate that DropTempsInstr has a use of the value on top the the
expression stack --- it serves as a renaming instruction for this value.  I
can't imagine a case where it would be any other value, due to the semantics of
LetNode and TempLocalScope.

I wish DropTempsInstr were not a definition with uses, but rather an instruction
with side effects and we could just use the original definition instead of this
one.  That would allow us to do the right thing for let in effect context (i.e.,
visit the last subexpression in effect context).

Is it the non-optimizing register allocator that won't allow a value to be live
across a purely side-effecting instruction?  If so, that seems like a huge wart
that should be fixed.

[Florian Schneider, 2013-05-29 15:30:13]

On 2013/05/28 17:00:47, hausner wrote:
> DBC.
> 
> The idea of the change looks nice to me. The biggest issue IMO is that you are
> handling only one particular case where temporary variables are needed. See
> comment below.
> 

Yes, I'm working on extending the CL to handle all compound assignments, prefix
and postfix operators by 
changing PrepareCompoundAssignmentNodes() to use the new LetNode.

[Florian Schneider, 2013-05-30 09:29:31]

New version uploaded with comments addressed.

The main diff is that now all prefix-, postfix-, compound assignment, and
cascade expressions use LetNode and avoid permanent temporary locals.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.cc
File runtime/vm/ast.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.cc#newcode83
runtime/vm/ast.cc:83: OS::SNPrint(name, 64, ":lt%"Pd"_%"Pd, token_pos, i);
On 2013/05/28 17:00:47, hausner wrote:
> 64 -> sizeof name
> 
> For our own debugging purposes, might be nice to separate the token position
and
> the temp index with an _ or some other character.

Done.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h
File runtime/vm/ast.h (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h#newcode302
runtime/vm/ast.h:302: const GrowableArray<AstNode*>& temp_expressions() const {
On 2013/05/29 11:28:23, kmillikin wrote:
> 'temp_expression' sounds like the expression is temporary.  I would use
> something more like 'initializer'.

Done.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h#newcode305
runtime/vm/ast.h:305: void SetTempExpression(intptr_t i, AstNode* node) {
On 2013/05/28 17:00:47, hausner wrote:
> We typically use the ending -At for setters that are indexed:
> SetTempExpressionAt(i, node). 

Redesigned to add expressions instead of preallocating and setting.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/ast.h#newcode323
runtime/vm/ast.h:323: AstNode* body_;
On 2013/05/29 11:28:23, kmillikin wrote:
> I think you should: (1) allow a list of AstNode* in the body instead of just
> one, (2) eliminate CommaNode and replace all occurrences with a LetNode with 0
> bindings.
> 
> It should just work in the graph builder and compiler (provided __ Drop(0) has
> special handling), except for some wartiness about LetNode in effect contexts
> (which I think should be fixed anyway).

Yes, I'll do that as a separate CL and added a TODO to replace CommaNode.
LetNode works with zero temp vars, the code generated should be the same. e.g.
in ParseCascades, we can simply use a LetNode instead of
LetNode+SequenceNode+CommaNode

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/bit_vector.h
File runtime/vm/bit_vector.h (left):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/bit_vector.h#o...
runtime/vm/bit_vector.h:51: ASSERT(length > 0);
On 2013/05/28 17:00:47, hausner wrote:
> Why remove this?

Bitvectors used by liveness analysis can now be of length zero. Before there was
always at least the array_literal_var in each function.

I removed this assert so that I don't need to handle the zero-length case in a
lot of places in the optimizer. The BitVector class works otherwise just fine
with a zero-length.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
File runtime/vm/flow_graph_builder.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
runtime/vm/flow_graph_builder.cc:1845: ASSERT(value->definition()->temp_index()
== visitor->temp_index() - 1);
On 2013/05/28 13:30:43, srdjan wrote:
> weird indent of body

Done.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/flow_graph_bui...
runtime/vm/flow_graph_builder.cc:1888: ReturnDefinition(new
DropTempsInstr(num_temps, result_value));
On 2013/05/29 11:28:23, kmillikin wrote:
> It's a bit unfortunate that DropTempsInstr has a use of the value on top the
the
> expression stack --- it serves as a renaming instruction for this value.  I
> can't imagine a case where it would be any other value, due to the semantics
of
> LetNode and TempLocalScope.
> 
> I wish DropTempsInstr were not a definition with uses, but rather an
instruction
> with side effects and we could just use the original definition instead of
this
> one.  That would allow us to do the right thing for let in effect context
(i.e.,
> visit the last subexpression in effect context).
> 
> Is it the non-optimizing register allocator that won't allow a value to be
live
> across a purely side-effecting instruction?  If so, that seems like a huge
wart
> that should be fixed.

I generally agree, but making them just Instructions (as opposed to Definition)
adds quite a bit of complexity. We could generate more compact code for the case
of effect contexts. I'll add a TODO for now.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/intermediate_l...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/intermediate_l...
runtime/vm/intermediate_language.h:3173: 
On 2013/05/28 13:30:43, srdjan wrote:
> private:

Done.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7738: const intptr_t token_pos = TokenPos();
On 2013/05/28 17:00:47, hausner wrote:
> Why are you renaming this? The old name expresses what is at that particular
> token position.

I found it too long so that it caused some ugly line breaks, but I can undo
renaming it.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7749: if (postfix_expr->IsInstanceGetterNode()) {
On 2013/05/28 17:00:47, hausner wrote:
> I think this special case needs to be handled in
> PrepareCompoundAssignmentNodes(), not here. If you do it just here, you only
> handle o.x++, but not o.x += 1, nor ++o.x, and neither cascades.

Yes, I'll handle this and the other cases in PrepareCompoundAssignmentNodes().

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7805: const LocalVariable* temp = GetIncrementTempLocal();
On 2013/05/28 17:00:47, hausner wrote:
> Can this temporary local variable be handled with your new LetNode construct?
If
> so, please at least add TODOs where simplification is possible.

Yes, definitely. The plan is to replace it here as well.

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/scopes.h
File runtime/vm/scopes.h (left):

https://codereview.chromium.org/14942010/diff/35001/runtime/vm/scopes.h#oldco...
runtime/vm/scopes.h:66: ASSERT(!HasIndex());
On 2013/05/28 17:00:47, hausner wrote:
> Why are you removing these asserts? Does your change depend on being able to
set
> an index on a variable that has already been allocated? That would seem wrong
to
> me.

I'm setting the index of the new dynamically allocated temps in the graph
builder where I track the stack height used for the index calculation. I could
make the graph builder a friend class of LocalVariable to keep the assert for
the existing uses of set_index.

Since the inliner uses a cache of ASTs we may encounter a local variable
multiple times when inlining at two call-sites that call the same function.

I agree this is a little brittle. I think a better solution would be to avoid
re-using the LocalVariable class for my purpose, but that would involve a lot of
changes, so I didn't want to do that in the first step.

The second ASSERT can actually stay. I removed it over-eagerly.

[Kevin Millikin (Google), 2013-05-30 11:30:55]

LGTM, considering the further improvements we discussed to be made in another
CL.

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/ast.h
File runtime/vm/ast.h (right):

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/ast.h#newcode301
runtime/vm/ast.h:301: LocalVariable* temp(intptr_t i) const { return vars_[i]; }
It's inconsistent to have two different ways to look up a var or an initializer:

node->temp(i), vs.
node->initializers()[i]

I prefer not exposing the list and having 'TempAt' and 'InitializerAt'
functions.

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7038: token_pos,
I bet this works:

*expr = new InstanceGetterNode(token_pos,
                               receiver,
                               getter->field_name());

If it doesn't, I prefer to break at the lowest precedence operator that works,
so:

*expr =
    new InstanceGetterNode(token_pos,
                           receiver,
                           getter->field_name());

is the same number of lines and avoids the unsightly hanging '('.

[Florian Schneider, 2013-05-30 11:46:57]

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/ast.h
File runtime/vm/ast.h (right):

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/ast.h#newcode301
runtime/vm/ast.h:301: LocalVariable* temp(intptr_t i) const { return vars_[i]; }
On 2013/05/30 11:30:55, kmillikin wrote:
> It's inconsistent to have two different ways to look up a var or an
initializer:
> 
> node->temp(i), vs.
> node->initializers()[i]
> 
> I prefer not exposing the list and having 'TempAt' and 'InitializerAt'
> functions.

Done.

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/14942010/diff/60004/runtime/vm/parser.cc#newc...
runtime/vm/parser.cc:7038: token_pos,
On 2013/05/30 11:30:55, kmillikin wrote:
> I bet this works:
> 
> *expr = new InstanceGetterNode(token_pos,
>                                receiver,
>                                getter->field_name());
> 
> If it doesn't, I prefer to break at the lowest precedence operator that works,
> so:
> 
> *expr =
>     new InstanceGetterNode(token_pos,
>                            receiver,
>                            getter->field_name());
> 
> is the same number of lines and avoids the unsightly hanging '('.

It does work.

[Florian Schneider, 2013-05-30 12:19:37]

Committed patchset #9 manually as r23401 (presubmit successful).