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 6009 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) {

[Kevin Millikin (Google), 2013/10/02 14:09:38]

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.

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

Done.

+    // 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->ArgumentAt(0)->AsCreateArray();
+    ASSERT(create_array != NULL);
+    // Check if the string interpolation has only constant inputs.
+    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) &&
+          (!IsConstant(store->value()->definition()->constant_value()))) {

[Kevin Millikin (Google), 2013/10/02 14:09:38]

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]

Done.

+        SetValue(instr, non_constant_);
+        return;
+      }
+    }
+    // Interpolate string at compile time.
+    const Array& value_arr =
+        Array::Handle(Array::New(create_array->num_elements()));
+    // 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);
+        Value* index_value = store->index();
+        ASSERT(index_value->BindsToConstant() && index_value->IsSmiValue());
+        const intptr_t ix = Smi::Cast(index_value->BoundConstant()).Value();
+        ASSERT(IsConstant(store->value()->definition()->constant_value()));
+        value_arr.SetAt(ix, store->value()->definition()->constant_value());
+      }
+    }
+    // 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);
+    if (concatenated.IsUnhandledException()) {
+      SetValue(instr, non_constant_);
+      return;
+    }
+
+    concatenated = Symbols::New(concatenated);
+    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 802 matching lines @@
       } else {
         // No new information: Assume both targets are reachable.
         SetReachable(branch->true_successor());
         SetReachable(branch->false_successor());
       }
     }
   }
 }
 
 
+// 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)
+// Remove the inputs.
+void ConstantPropagator::RemoveInterpolationInputs(
+    const StaticCallInstr& call) {
+  ASSERT(call.ArgumentCount() == 1);
+  CreateArrayInstr* create_array = call.ArgumentAt(0)->AsCreateArray();
+  ASSERT(create_array != NULL);
+  for (Value* use = create_array->input_use_list();
+      use != NULL;
+      use = create_array->input_use_list()) {
+    use->instruction()->RemoveFromGraph();
+  }
+  create_array->RemoveFromGraph();
+}
+
+
 void ConstantPropagator::Transform() {
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== Before constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 
   GrowableArray<PhiInstr*> redundant_phis(10);
 
   // We will recompute dominators, block ordering, block ids, block last
@@ skipping 87 matching lines @@
           !defn->IsStoreStaticField() &&
           !defn->IsStoreVMField()) {
         if (FLAG_trace_constant_propagation) {
           OS::Print("Constant v%" Pd " = %s\n",
                     defn->ssa_temp_index(),
                     defn->constant_value().ToCString());
         }
         ConstantInstr* constant = graph_->GetConstant(defn->constant_value());
         defn->ReplaceUsesWith(constant);
         i.RemoveCurrentFromGraph();
+        if (defn->IsStaticCall()) {
+          MethodRecognizer::Kind recognized_kind =
+              MethodRecognizer::RecognizeKind(defn->AsStaticCall()->function());
+          if (recognized_kind == MethodRecognizer::kStringBaseInterpolate) {
+            RemoveInterpolationInputs(*defn->AsStaticCall());
+          }
+        }
       }
     }
 
     // Replace branches where one target is unreachable with jumps.
     BranchInstr* branch = block->last_instruction()->AsBranch();
     if (branch != NULL) {
       TargetEntryInstr* if_true = branch->true_successor();
       TargetEntryInstr* if_false = branch->false_successor();
       JoinEntryInstr* join = NULL;
       Instruction* next = NULL;
@@ skipping 665 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