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

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 6029 matching lines @@
 }
 
 
 void ConstantPropagator::VisitPolymorphicInstanceCall(
     PolymorphicInstanceCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitStaticCall(StaticCallInstr* instr) {
-  SetValue(instr, non_constant_);
+  MethodRecognizer::Kind recognized_kind =
+      MethodRecognizer::RecognizeKind(instr->function());
+  if (recognized_kind == MethodRecognizer::kStringBaseInterpolate) {
+    // static String _interpolate(List values)
+    //
+    // Code for calling interpolate is generated by the compiler:
+    //   v2 <- CreateArray(v0)
+    //   StoreIndexed(v2, v3, v4)   -- v3:constant index, v4: value.
+    //   ..
+    //   PushArgument(v2)
+    //   v8 <- StaticCall(_interpolate, v2)
+    // Detect that all values are constant, interpolate at compile
+    // time.
+    ASSERT(instr->ArgumentCount() == 1);
+    CreateArrayInstr* create_array =
+        instr->PushArgumentAt(0)->InputAt(0)->definition()->AsCreateArray();

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

PushArgumentAt(0)->InputAt(0)->definition() can be spelled ArgumentAt(0).

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

Done.

+    ASSERT(create_array != NULL);
+    const Array& value_arr =
+        Array::Handle(Array::New(create_array->num_elements()));

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

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?).

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

Done.

+    GrowableArray<StoreIndexedInstr*> store_instructions;
+    // Build the array of literal values to interpolate, abort if a value is
+    // not literal.
+    for (Value::Iterator it(create_array->input_use_list());
+         !it.Done();
+         it.Advance()) {
+      Instruction* curr = it.Current()->instruction();
+      StoreIndexedInstr* store = curr->AsStoreIndexed();
+      if (store == NULL) {
+        ASSERT(curr == instr->PushArgumentAt(0));
+      } else {
+        store_instructions.Add(store);
+        ASSERT(store->index()->BindsToConstant() &&
+               store->index()->IsSmiValue());
+        if (!store->value()->BindsToConstant()) {

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

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().

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

Done.

+          SetValue(instr, non_constant_);
+          return;
+        }
+        const intptr_t i = Smi::Cast(store->index()->BoundConstant()).Value();
+        value_arr.SetAt(i, store->value()->BoundConstant());
+      }
+    }
+    // Build argument array to pass to the interpolation function.
+    const Array& interpolate_arg = Array::Handle(Array::New(1));
+    interpolate_arg.SetAt(0, value_arr);
+    // Call interpolation function.
+    String& concatenated = String::ZoneHandle();
+    concatenated ^=
+        DartEntry::InvokeFunction(instr->function(), interpolate_arg);
+    concatenated ^= concatenated.CheckAndCanonicalize(NULL);
+    // Remove unnecessary instructions.
+    instr->PushArgumentAt(0)->RemoveFromGraph();

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

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).

+    for (intptr_t i = 0; i < store_instructions.length(); i++) {
+      store_instructions[i]->RemoveFromGraph();
+    }
+    create_array->RemoveFromGraph();
+
+    SetValue(instr, concatenated);
+  } else {
+    SetValue(instr, non_constant_);
+  }
 }
 
 
 void ConstantPropagator::VisitLoadLocal(LoadLocalInstr* instr) {
   // Instruction is eliminated when translating to SSA.
   UNREACHABLE();
 }
 
 
 void ConstantPropagator::VisitPushTemp(PushTempInstr* instr) {
@@ skipping 1594 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *fields);
   }
 }
 
 
 }  // namespace dart