Enable polymorphic inlining of StringBase [] and StringBase codeUnitAt

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 1385 matching lines @@
     case MethodRecognizer::kByteArrayBaseSetFloat32x4:
       if (!ShouldInlineSimd()) return false;
       return InlineByteArrayViewStore(target, call, receiver, receiver_cid,
                                       kTypedDataFloat32x4ArrayCid,
                                       ic_data, entry, last);
     case MethodRecognizer::kByteArrayBaseSetInt32x4:
       if (!ShouldInlineSimd()) return false;
       return InlineByteArrayViewStore(target, call, receiver, receiver_cid,
                                       kTypedDataInt32x4ArrayCid,
                                       ic_data, entry, last);
+    case MethodRecognizer::kStringBaseCodeUnitAt:
+      return InlineStringCodeUnitAt(call, receiver_cid, entry, last);
+    case MethodRecognizer::kStringBaseCharAt:
+      return InlineStringBaseCharAt(call, receiver_cid, entry, last);
     default:
       return false;
   }
 }
 
 
 intptr_t FlowGraphOptimizer::PrepareInlineIndexedOp(Instruction* call,
                                                     intptr_t array_cid,
                                                     Definition** array,
                                                     Definition* index,
@@ skipping 988 matching lines @@
   if (target.kind() != RawFunction::kImplicitGetter) {
     // Non-implicit getters are inlined like normal methods by conventional
     // inlining in FlowGraphInliner.
     return false;
   }
   InlineImplicitInstanceGetter(call);
   return true;
 }
 
 
-LoadIndexedInstr* FlowGraphOptimizer::BuildStringCodeUnitAt(
-    InstanceCallInstr* call,
-    intptr_t cid) {
-  Definition* str = call->ArgumentAt(0);
-  Definition* index = call->ArgumentAt(1);
+bool FlowGraphOptimizer::TryReplaceInstanceCallWithInline(
+    InstanceCallInstr* call) {
+  ASSERT(call->HasICData());
+  Function& target = Function::Handle();
+  GrowableArray<intptr_t> class_ids;
+  call->ic_data()->GetCheckAt(0, &class_ids, &target);
+  const intptr_t receiver_cid = class_ids[0];
+
+  TargetEntryInstr* entry;
+  Definition* last;
+  if (!TryInlineRecognizedMethod(receiver_cid,
+                                 target,
+                                 call,
+                                 call->ArgumentAt(0),
+                                 call->token_pos(),
+                                 *call->ic_data(),
+                                 &entry, &last)) {
+    return false;
+  }
+
+  // Insert receiver class check.
   AddReceiverCheck(call);
-  InsertBefore(call,
-               new CheckSmiInstr(new Value(index), call->deopt_id()),
-               call->env(),
-               Definition::kEffect);
-  // If both index and string are constants, then do a compile-time check.
-  // TODO(srdjan): Remove once constant propagation handles bounds checks.
-  bool skip_check = false;
-  if (str->IsConstant() && index->IsConstant()) {
-    const String& constant_string =
-        String::Cast(str->AsConstant()->value());
-    const Object& constant_index = index->AsConstant()->value();
-    skip_check = constant_index.IsSmi() &&
-        (Smi::Cast(constant_index).Value() < constant_string.Length());
+  // Remove the original push arguments.
+  for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
+    PushArgumentInstr* push = call->PushArgumentAt(i);
+    push->ReplaceUsesWith(push->value()->definition());
+    push->RemoveFromGraph();
   }
-  if (!skip_check) {
-    // Insert bounds check.
-    LoadFieldInstr* length = BuildLoadStringLength(str);
-    InsertBefore(call, length, NULL, Definition::kValue);
-    InsertBefore(call,
-                 new CheckArrayBoundInstr(new Value(length),
-                                          new Value(index),
-                                          call->deopt_id()),
-                 call->env(),
-                 Definition::kEffect);
-  }
-  return new LoadIndexedInstr(new Value(str),
-                              new Value(index),
-                              FlowGraphCompiler::ElementSizeFor(cid),
-                              cid,
-                              Isolate::kNoDeoptId);  // Can't deoptimize.
+  // Replace all uses of this definition with the result.
+  call->ReplaceUsesWith(last);
+  // Finally insert the sequence other definition in place of this one in the
+  // graph.
+  call->previous()->LinkTo(entry->next());
+  entry->UnuseAllInputs();  // Entry block is not in the graph.
+  last->LinkTo(call);
+  // Remove through the iterator.
+  ASSERT(current_iterator()->Current() == call);
+  current_iterator()->RemoveCurrentFromGraph();
+  call->set_previous(NULL);
+  call->set_next(NULL);
+  return true;
 }
 
 
+// Returns the LoadIndexedInstr.
+Definition* FlowGraphOptimizer::PrepareInlineStringIndexOp(
+    Instruction* call,
+    intptr_t cid,
+    Definition* str,
+    Definition* index,
+    Instruction* cursor) {
+
+  cursor = flow_graph()->AppendTo(cursor,
+                                  new CheckSmiInstr(new Value(index),
+                                                    call->deopt_id()),
+                                  call->env(),
+                                  Definition::kEffect);
+
+  // Load the length of the string.
+  LoadFieldInstr* length = BuildLoadStringLength(str);
+  cursor = flow_graph()->AppendTo(cursor, length, NULL, Definition::kValue);
+  // Bounds check.
+  cursor = flow_graph()->AppendTo(cursor,
+                                   new CheckArrayBoundInstr(new Value(length),
+                                                            new Value(index),
+                                                            call->deopt_id()),
+                                   call->env(),
+                                   Definition::kEffect);
+
+  LoadIndexedInstr* load_indexed = new LoadIndexedInstr(
+      new Value(str),
+      new Value(index),
+      FlowGraphCompiler::ElementSizeFor(cid),
+      cid,
+      Isolate::kNoDeoptId);
+
+  cursor = flow_graph()->AppendTo(cursor,
+                                  load_indexed,
+                                  NULL,
+                                  Definition::kValue);
+  ASSERT(cursor == load_indexed);
+  return load_indexed;
+}
+
+
+bool FlowGraphOptimizer::InlineStringCodeUnitAt(
+    Instruction* call,
+    intptr_t cid,
+    TargetEntryInstr** entry,
+    Definition** last) {
+  if (RawObject::IsExternalStringClassId(cid)) {

[Florian Schneider, 2014/02/17 11:56:12]

Add a TODO for handling external strings in the same way.

[Cutch, 2014/02/18 17:00:30]

Done.

+    return false;
+  }
+
+  Definition* str = call->ArgumentAt(0);
+  Definition* index = call->ArgumentAt(1);
+
+  *entry = new TargetEntryInstr(flow_graph()->allocate_block_id(),
+                                call->GetBlock()->try_index());
+  (*entry)->InheritDeoptTarget(call);
+
+  *last = PrepareInlineStringIndexOp(call, cid, str, index, *entry);
+
+  return true;
+}
+
+
+bool FlowGraphOptimizer::InlineStringBaseCharAt(
+    Instruction* call,
+    intptr_t cid,
+    TargetEntryInstr** entry,
+    Definition** last) {
+  if (RawObject::IsExternalStringClassId(cid) || cid != kOneByteStringCid) {

[Florian Schneider, 2014/02/17 11:56:12]

Add a TODO for handling external strings in the same way.

[Cutch, 2014/02/18 17:00:30]

Done.

+    return false;
+  }
+  Definition* str = call->ArgumentAt(0);
+  Definition* index = call->ArgumentAt(1);
+
+  *entry = new TargetEntryInstr(flow_graph()->allocate_block_id(),
+                                call->GetBlock()->try_index());
+  (*entry)->InheritDeoptTarget(call);
+
+  *last = PrepareInlineStringIndexOp(call, cid, str, index, *entry);
+
+  StringFromCharCodeInstr* char_at =
+          new StringFromCharCodeInstr(new Value(*last), cid);
+
+  flow_graph()->AppendTo(*last, char_at, NULL, Definition::kValue);
+  *last = char_at;
+
+  return true;
+}
+
+
 void FlowGraphOptimizer::ReplaceWithMathCFunction(
     InstanceCallInstr* call,
     MethodRecognizer::Kind recognized_kind) {
   AddReceiverCheck(call);
   ZoneGrowableArray<Value*>* args =
       new ZoneGrowableArray<Value*>(call->ArgumentCount());
   for (intptr_t i = 0; i < call->ArgumentCount(); i++) {
     args->Add(new Value(call->ArgumentAt(i)));
   }
   InvokeMathCFunctionInstr* invoke =
@@ skipping 63 matching lines @@
     Definition* value = call->ArgumentAt(1);
     StoreVMFieldInstr* store = new StoreVMFieldInstr(
         new Value(array),
         GrowableObjectArray::length_offset(),
         new Value(value),
         Type::ZoneHandle());
     ReplaceCall(call, store);
     return true;
   }
 
-  if ((recognized_kind == MethodRecognizer::kStringBaseCodeUnitAt) &&
+  if (((recognized_kind == MethodRecognizer::kStringBaseCodeUnitAt) ||
+       (recognized_kind == MethodRecognizer::kStringBaseCharAt)) &&
       (ic_data.NumberOfChecks() == 1) &&
       ((class_ids[0] == kOneByteStringCid) ||
        (class_ids[0] == kTwoByteStringCid))) {
-    LoadIndexedInstr* instr = BuildStringCodeUnitAt(call, class_ids[0]);
-    ReplaceCall(call, instr);
-    return true;
+    return TryReplaceInstanceCallWithInline(call);
   }
+
   if ((class_ids[0] == kOneByteStringCid) && (ic_data.NumberOfChecks() == 1)) {
-    if (recognized_kind == MethodRecognizer::kStringBaseCharAt) {
-      // TODO(fschneider): Handle TwoByteString.
-      LoadIndexedInstr* load_char_code =
-          BuildStringCodeUnitAt(call, class_ids[0]);
-      InsertBefore(call, load_char_code, NULL, Definition::kValue);
-      StringFromCharCodeInstr* char_at =
-          new StringFromCharCodeInstr(new Value(load_char_code),
-                                      kOneByteStringCid);
-      ReplaceCall(call, char_at);
-      return true;
-    }
     if (recognized_kind == MethodRecognizer::kOneByteStringSetAt) {
       // This is an internal method, no need to check argument types nor
       // range.
       Definition* str = call->ArgumentAt(0);
       Definition* index = call->ArgumentAt(1);
       Definition* value = call->ArgumentAt(2);
       StoreIndexedInstr* store_op = new StoreIndexedInstr(
           new Value(str),
           new Value(index),
           new Value(value),
@@ skipping 723 matching lines @@
 }
 
 
 bool FlowGraphOptimizer::BuildByteArrayViewLoad(InstanceCallInstr* call,
                                                 intptr_t view_cid) {
   bool simd_view = (view_cid == kTypedDataFloat32x4ArrayCid) ||
                    (view_cid == kTypedDataInt32x4ArrayCid);
   if (simd_view && !ShouldInlineSimd()) {
     return false;
   }
-
-  ASSERT(call->HasICData());
-  Function& target = Function::Handle();
-  GrowableArray<intptr_t> class_ids;
-  call->ic_data()->GetCheckAt(0, &class_ids, &target);
-  const intptr_t receiver_cid = class_ids[0];
-
-  TargetEntryInstr* entry;
-  Definition* last;
-  if (!TryInlineRecognizedMethod(receiver_cid,
-                                 target,
-                                 call,
-                                 call->ArgumentAt(0),
-                                 call->token_pos(),
-                                 *call->ic_data(),
-                                 &entry, &last)) {
-    return false;
-  }
-
-  // Insert receiver class check.
-  AddReceiverCheck(call);
-  // Remove the original push arguments.
-  for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
-    PushArgumentInstr* push = call->PushArgumentAt(i);
-    push->ReplaceUsesWith(push->value()->definition());
-    push->RemoveFromGraph();
-  }
-  // Replace all uses of this definition with the result.
-  call->ReplaceUsesWith(last);
-  // Finally insert the sequence other definition in place of this one in the
-  // graph.
-  call->previous()->LinkTo(entry->next());
-  entry->UnuseAllInputs();  // Entry block is not in the graph.
-  last->LinkTo(call);
-  // Remove through the iterator.
-  ASSERT(current_iterator()->Current() == call);
-  current_iterator()->RemoveCurrentFromGraph();
-  call->set_previous(NULL);
-  call->set_next(NULL);
-  return true;
+  return TryReplaceInstanceCallWithInline(call);
 }
 
 
 bool FlowGraphOptimizer::BuildByteArrayViewStore(InstanceCallInstr* call,
                                                  intptr_t view_cid) {
   bool simd_view = (view_cid == kTypedDataFloat32x4ArrayCid) ||
                    (view_cid == kTypedDataInt32x4ArrayCid);
   if (simd_view && !ShouldInlineSimd()) {
     return false;
   }
-  ASSERT(call->HasICData());
-  Function& target = Function::Handle();
-  GrowableArray<intptr_t> class_ids;
-  call->ic_data()->GetCheckAt(0, &class_ids, &target);
-  const intptr_t receiver_cid = class_ids[0];
-
-  TargetEntryInstr* entry;
-  Definition* last;
-  if (!TryInlineRecognizedMethod(receiver_cid,
-                                 target,
-                                 call,
-                                 call->ArgumentAt(0),
-                                 call->token_pos(),
-                                 *call->ic_data(),
-                                 &entry, &last)) {
-    return false;
-  }
-
-  // Insert receiver class check.
-  AddReceiverCheck(call);
-  // Remove the original push arguments.
-  for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
-    PushArgumentInstr* push = call->PushArgumentAt(i);
-    push->ReplaceUsesWith(push->value()->definition());
-    push->RemoveFromGraph();
-  }
-  // Replace all uses of this definition with the result.
-  call->ReplaceUsesWith(last);
-  // Finally insert the sequence other definition in place of this one in the
-  // graph.
-  call->previous()->LinkTo(entry->next());
-  entry->UnuseAllInputs();  // Entry block is not in the graph.
-  last->LinkTo(call);
-  // Remove through the iterator.
-  ASSERT(current_iterator()->Current() == call);
-  current_iterator()->RemoveCurrentFromGraph();
-  call->set_previous(NULL);
-  call->set_next(NULL);
-  return true;
+  return TryReplaceInstanceCallWithInline(call);
 }
 
 
-void FlowGraphOptimizer::PrepareByteArrayViewOp(
-    InstanceCallInstr* call,
-    intptr_t receiver_cid,
-    intptr_t view_cid,
-    Definition** array) {
-  Definition* byte_index = call->ArgumentAt(1);
-
-  AddReceiverCheck(call);
-  const bool is_immutable = true;
-  LoadFieldInstr* length = new LoadFieldInstr(
-      new Value(*array),
-      CheckArrayBoundInstr::LengthOffsetFor(receiver_cid),
-      Type::ZoneHandle(Type::SmiType()),
-      is_immutable);
-  length->set_result_cid(kSmiCid);
-  length->set_recognized_kind(
-      LoadFieldInstr::RecognizedKindFromArrayCid(receiver_cid));
-  InsertBefore(call, length, NULL, Definition::kValue);
-
-  // len_in_bytes = length * kBytesPerElement(receiver)
-  intptr_t element_size = FlowGraphCompiler::ElementSizeFor(receiver_cid);
-  ConstantInstr* bytes_per_element =
-      flow_graph()->GetConstant(Smi::Handle(Smi::New(element_size)));
-  BinarySmiOpInstr* len_in_bytes =
-      new BinarySmiOpInstr(Token::kMUL,
-                           new Value(length),
-                           new Value(bytes_per_element),
-                           call->deopt_id());
-  InsertBefore(call, len_in_bytes, call->env(), Definition::kValue);
-
-  ConstantInstr* length_adjustment =
-      flow_graph()->GetConstant(Smi::Handle(Smi::New(
-          FlowGraphCompiler::ElementSizeFor(view_cid) - 1)));
-  // adjusted_length = len_in_bytes - (element_size - 1).
-  BinarySmiOpInstr* adjusted_length =
-      new BinarySmiOpInstr(Token::kSUB,
-                           new Value(len_in_bytes),
-                           new Value(length_adjustment),
-                           call->deopt_id());
-  InsertBefore(call, adjusted_length, call->env(), Definition::kValue);
-  // Check adjusted_length > 0.
-  ConstantInstr* zero = flow_graph()->GetConstant(Smi::Handle(Smi::New(0)));
-  InsertBefore(call,
-               new CheckArrayBoundInstr(new Value(adjusted_length),
-                                        new Value(zero),
-                                        call->deopt_id()),
-               call->env(),
-               Definition::kEffect);
-  // Check 0 <= byte_index < adjusted_length.
-  InsertBefore(call,
-               new CheckArrayBoundInstr(new Value(adjusted_length),
-                                        new Value(byte_index),
-                                        call->deopt_id()),
-               call->env(),
-               Definition::kEffect);
-
-  // Insert load of elements for external typed arrays.
-  if (RawObject::IsExternalTypedDataClassId(receiver_cid)) {
-    LoadUntaggedInstr* elements =
-        new LoadUntaggedInstr(new Value(*array),
-                              ExternalTypedData::data_offset());
-    InsertBefore(call, elements, NULL, Definition::kValue);
-    *array = elements;
-  }
-}
-
-
 // Returns a Boolean constant if all classes in ic_data yield the same type-test
 // result and the type tests do not depend on type arguments. Otherwise return
 // Bool::null().
 RawBool* FlowGraphOptimizer::InstanceOfAsBool(const ICData& ic_data,
                                               const AbstractType& type) const {
   ASSERT(ic_data.num_args_tested() == 1);  // Unary checks only.
   if (!type.IsInstantiated() || type.IsMalformedOrMalbounded()) {
     return Bool::null();
   }
   const Class& type_class = Class::Handle(type.type_class());
@@ skipping 5142 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