Optimize string interpolation by running it at compile time if all inputs are constant. This is don…

Optimize string interpolation by running it at compile time if all inputs are constant. This is done during constant propagation, however, the argument construction instructions must be removed manually. It is unclear how safe it is to modify graph during constant propagation.

R=kmillikin@google.com

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

[Kevin Millikin (Google), 2013-09-27 10:22:39]

Cool.  We should be able to fold other known calls too, if we choose (though
this pass runs after inlining).

There are a few fixes we need to make:

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6065:
instr->PushArgumentAt(0)->InputAt(0)->definition()->AsCreateArray();
PushArgumentAt(0)->InputAt(0)->definition() can be spelled ArgumentAt(0).

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6068:
Array::Handle(Array::New(create_array->num_elements()));
I don't think we should create this array in the heap here.  First, check that
all the arguments are constant.  Once we've decided to fold, we can allocate the
array.

Otherwise, we have heap allocation for every interpolation in optimized code
(even non-constant ones), on every iteration of the algorithm (values can take
two steps up the lattice, once to known constant and once to non-constant, and
that can happen for each input separately causing the call to be revisited), on
every time we run this pass in the pipeline (three times now?  four?).

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6083: if (!store->value()->BindsToConstant())
{
We actually want to ask what is the analysis's computed constant value, not
whether this is syntactically a constant.  Otherwise we don't get any benefit
from pushing constants through variables, constant phis, constant folding of
other operations, etc.

That is, ask IsConstant(store->value()->definition()->constant_value()) and use
store->value()->definition()->constant_value() instead of
store->value()->BoundConstant().

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6100:
instr->PushArgumentAt(0)->RemoveFromGraph();
This is not safe.  Remember the lattice is unknown constant -> known constant ->
non-constant.  Suppose the analysis later learns that one of the arguments was
actually not constant at all.  There is no way to reinsert the arguments and put
the call back in.

The way this analysis works is to mark the call as having a constant value. 
After the analysis completes, we can replace it.  You probably have to verify
that when we remove call instructions in ConstantPropagator::Transform we also
remove their arguments (I don't think we do right now, because we never
determined that calls were constant before this change).

[srdjan, 2013-10-01 19:36:49]

Thanks for the comments. PTAL.

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6065:
instr->PushArgumentAt(0)->InputAt(0)->definition()->AsCreateArray();
On 2013/09/27 10:22:39, kmillikin wrote:
> PushArgumentAt(0)->InputAt(0)->definition() can be spelled ArgumentAt(0).

Done.

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6068:
Array::Handle(Array::New(create_array->num_elements()));
On 2013/09/27 10:22:39, kmillikin wrote:
> I don't think we should create this array in the heap here.  First, check that
> all the arguments are constant.  Once we've decided to fold, we can allocate
the
> array.
> 
> Otherwise, we have heap allocation for every interpolation in optimized code
> (even non-constant ones), on every iteration of the algorithm (values can take
> two steps up the lattice, once to known constant and once to non-constant, and
> that can happen for each input separately causing the call to be revisited),
on
> every time we run this pass in the pipeline (three times now?  four?).

Done.

https://codereview.chromium.org/24837002/diff/13001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6083: if (!store->value()->BindsToConstant())
{
On 2013/09/27 10:22:39, kmillikin wrote:
> We actually want to ask what is the analysis's computed constant value, not
> whether this is syntactically a constant.  Otherwise we don't get any benefit
> from pushing constants through variables, constant phis, constant folding of
> other operations, etc.
> 
> That is, ask IsConstant(store->value()->definition()->constant_value()) and
use
> store->value()->definition()->constant_value() instead of
> store->value()->BoundConstant().

Done.

[Kevin Millikin (Google), 2013-10-02 14:09:37]

LGTM after changing !IsConstant to IsNonConstant (I know, the difference is very
subtle).

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_bui...
File runtime/vm/flow_graph_builder.h (left):

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_bui...
runtime/vm/flow_graph_builder.h:281: void TranslateArgumentList(const
ArgumentListNode& node,
It's strange that this is still hanging around.

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6032: if (recognized_kind ==
MethodRecognizer::kStringBaseInterpolate) {
You might also make sure !IsNonConstant(instr->constant_value()) before going
into the if body.

We don't usually bother to check that, but the code below does a lot of work so
we might avoid it in the case we already know it's not constant.

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6053:
(!IsConstant(store->value()->definition()->constant_value()))) {
Change !IsConstant to IsNonConstant.

We don't want to conclude (yet) that the call is non-constant when the inputs
are all constant or unknown.  We definitely don't want constant values to ever
move downward in the lattice, and this looks like it could.

[srdjan, 2013-10-02 16:35:23]

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_opt...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6032: if (recognized_kind ==
MethodRecognizer::kStringBaseInterpolate) {
On 2013/10/02 14:09:38, kmillikin wrote:
> You might also make sure !IsNonConstant(instr->constant_value()) before going
> into the if body.
> 
> We don't usually bother to check that, but the code below does a lot of work
so
> we might avoid it in the case we already know it's not constant.

Done.

https://codereview.chromium.org/24837002/diff/24001/runtime/vm/flow_graph_opt...
runtime/vm/flow_graph_optimizer.cc:6053:
(!IsConstant(store->value()->definition()->constant_value()))) {
On 2013/10/02 14:09:38, kmillikin wrote:
> Change !IsConstant to IsNonConstant.
> 
> We don't want to conclude (yet) that the call is non-constant when the inputs
> are all constant or unknown.  We definitely don't want constant values to ever
> move downward in the lattice, and this looks like it could.

Done.

[srdjan, 2013-10-02 17:49:22]

Committed patchset #8 manually as r28175 (presubmit successful).