Polymorphic inlining of [] operations.

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 142 matching lines @@
       (ic_data.GetReceiverClassIdAt(0) == cid)) {
     return ic_data;  // Nothing to do
   }
 
   const ICData& new_ic_data = ICData::ZoneHandle(ICData::New(
       Function::Handle(ic_data.function()),
       String::Handle(ic_data.target_name()),
       Object::empty_array(),  // Dummy argument descriptor.
       ic_data.deopt_id(),
       ic_data.num_args_tested()));
+  new_ic_data.set_deopt_reason(ic_data.deopt_reason());
 
   const Function& function =
       Function::Handle(ic_data.GetTargetForReceiverClassId(cid));
   if (!function.IsNull()) {
     new_ic_data.AddReceiverCheck(cid, function);
   }
 
   return new_ic_data;
 }
 
@@ skipping 609 matching lines @@
   length->set_recognized_kind(
       LoadFieldInstr::RecognizedKindFromArrayCid(class_id));
   InsertBefore(call, length, NULL, Definition::kValue);
   InsertBefore(call,
                new CheckArrayBoundInstr(new Value(length),
                                         new Value(*index),
                                         call->deopt_id()),
                call->env(),
                Definition::kEffect);
 
-
   if (class_id == kGrowableObjectArrayCid) {
     // Insert data elements load.
     LoadFieldInstr* elements =
         new LoadFieldInstr(new Value(*array),
                            GrowableObjectArray::data_offset(),
                            Type::ZoneHandle(Type::DynamicType()));
     elements->set_result_cid(kArrayCid);
     InsertBefore(call, elements, NULL, Definition::kValue);
     *array = elements;
     return kArrayCid;
@@ skipping 186 matching lines @@
                                                new Value(index),
                                                new Value(stored_value),
                                                needs_store_barrier,
                                                index_scale,
                                                array_cid,
                                                call->deopt_id());
   ReplaceCall(call, array_op);
 }
 
 
+static intptr_t MethodKindToCid(MethodRecognizer::Kind kind) {
+  switch (kind) {
+    case MethodRecognizer::kImmutableArrayGetIndexed:
+      return kImmutableArrayCid;
+
+    case MethodRecognizer::kObjectArrayGetIndexed:
+      return kArrayCid;
+
+    case MethodRecognizer::kGrowableArrayGetIndexed:
+      return kGrowableObjectArrayCid;
+
+    case MethodRecognizer::kFloat32ArrayGetIndexed:
+      return kTypedDataFloat32ArrayCid;
+
+    case MethodRecognizer::kFloat64ArrayGetIndexed:
+      return kTypedDataFloat64ArrayCid;
+
+    case MethodRecognizer::kInt8ArrayGetIndexed:
+      return kTypedDataInt8ArrayCid;
+
+    case MethodRecognizer::kUint8ArrayGetIndexed:
+      return kTypedDataUint8ArrayCid;
+
+    case MethodRecognizer::kUint8ClampedArrayGetIndexed:
+      return kTypedDataUint8ClampedArrayCid;
+
+    case MethodRecognizer::kExternalUint8ArrayGetIndexed:
+      return kExternalTypedDataUint8ArrayCid;
+
+    case MethodRecognizer::kExternalUint8ClampedArrayGetIndexed:
+      return kExternalTypedDataUint8ClampedArrayCid;
+
+    case MethodRecognizer::kInt16ArrayGetIndexed:
+      return kTypedDataInt16ArrayCid;
+
+    case MethodRecognizer::kUint16ArrayGetIndexed:
+      return kTypedDataUint16ArrayCid;
+
+    case MethodRecognizer::kInt32ArrayGetIndexed:
+      return kTypedDataInt32ArrayCid;
+
+    case MethodRecognizer::kUint32ArrayGetIndexed:
+      return kTypedDataUint32ArrayCid;
+
+    case MethodRecognizer::kFloat32x4ArrayGetIndexed:
+      return kTypedDataFloat32x4ArrayCid;
+
+    default:
+      break;
+  }
+  return kIllegalCid;
+}
+
+
+// Explicit instantiation because this variant used in flow_graph_inliner.cc.
+template bool FlowGraphOptimizer::
+TryInlineRecognizedMethod<PolymorphicInstanceCallInstr*>(
+    const Function&,
+    PolymorphicInstanceCallInstr*,
+    const ICData&,
+    TargetEntryInstr**,
+    Definition**);
+
+
+template <typename T>
+bool FlowGraphOptimizer::TryInlineRecognizedMethod(const Function& target,
+                                                   T call,
+                                                   const ICData& ic_data,
+                                                   TargetEntryInstr** entry,
+                                                   Definition** last) {
+  // TODO(fschneider): Extend to other recognized methods.

[Cutch, 2013/09/17 16:08:47]

The below code is specific to preparing an indexed operation, can it be factored
out now in anticipation of supporting other recognized methods inside
::TryInlineRecognizedMethod?

[Florian Schneider, 2013/09/18 14:00:36]

Yes, I'd have to do that for the next CL anyway.

+  MethodRecognizer::Kind kind = MethodRecognizer::RecognizeKind(target);
+  intptr_t array_cid = MethodKindToCid(kind);
+  if (array_cid == kIllegalCid) return false;
+
+  // Insert index smi checks and attach a copy of the
+  // original environment because the operation can still deoptimize.
+  Definition* array = call->ArgumentAt(0);
+  Definition* index = call->ArgumentAt(1);
+  *entry = new TargetEntryInstr(flow_graph()->allocate_block_id(),
+                                call->GetBlock()->try_index());
+  (*entry)->InheritDeoptTarget(call);
+
+  Instruction* cursor = *entry;
+  cursor = flow_graph()->AppendTo(cursor,
+                                  new CheckSmiInstr(new Value(index),
+                                                    call->deopt_id()),
+                                  call->env(),
+                                  Definition::kEffect);
+
+  // Insert array length load and bounds check.
+  const bool is_immutable =
+      CheckArrayBoundInstr::IsFixedLengthArrayType(array_cid);
+  LoadFieldInstr* length =
+      new LoadFieldInstr(new Value(array),
+                         CheckArrayBoundInstr::LengthOffsetFor(array_cid),
+                         Type::ZoneHandle(Type::SmiType()),
+                         is_immutable);
+  length->set_result_cid(kSmiCid);
+  length->set_recognized_kind(
+      LoadFieldInstr::RecognizedKindFromArrayCid(array_cid));
+  cursor = flow_graph()->AppendTo(cursor,
+                                  length,
+                                  NULL,
+                                  Definition::kValue);
+
+  cursor = flow_graph()->AppendTo(cursor,
+                                  new CheckArrayBoundInstr(
+                                      new Value(length),
+                                      new Value(index),
+                                      call->deopt_id()),
+                                  call->env(),
+                                  Definition::kEffect);
+
+  if (array_cid == kGrowableObjectArrayCid) {
+    // Insert data elements load.
+    LoadFieldInstr* elements =
+        new LoadFieldInstr(new Value(array),
+                           GrowableObjectArray::data_offset(),
+                           Type::ZoneHandle(Type::DynamicType()));
+    elements->set_result_cid(kArrayCid);
+    cursor = flow_graph()->AppendTo(cursor,
+                                    elements,
+                                    NULL,
+                                    Definition::kValue);
+    // Load from the data from backing store which is a fixed-length array.
+    array = elements;
+    array_cid = kArrayCid;
+  } else if (RawObject::IsExternalTypedDataClassId(array_cid)) {
+    LoadUntaggedInstr* elements =
+        new LoadUntaggedInstr(new Value(array),
+                              ExternalTypedData::data_offset());
+    cursor = flow_graph()->AppendTo(cursor,
+                                    elements,
+                                    NULL,
+                                    Definition::kValue);
+    array = elements;
+  }
+
+  intptr_t deopt_id = Isolate::kNoDeoptId;
+  if ((array_cid == kTypedDataInt32ArrayCid) ||
+      (array_cid == kTypedDataUint32ArrayCid)) {
+    // Set deopt_id if we can optimistically assume that the result is Smi.
+    // Assume mixed Mint/Smi if this instruction caused deoptimization once.

[Cutch, 2013/09/17 16:08:47]

Shouldn't this include kTypedDataInt64ArrayCid and kTypedDataUint64ArrayCid?
They can be outside of the Smi range.

+    deopt_id = (ic_data.deopt_reason() == kDeoptUnknown) ?
+        call->deopt_id() : Isolate::kNoDeoptId;
+  }
+
+  // Array load and return.
+  intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(array_cid);
+  *last = new LoadIndexedInstr(new Value(array),
+                               new Value(index),
+                               index_scale,
+                               array_cid,
+                               deopt_id);
+  flow_graph()->AppendTo(cursor,
+                         *last,
+                         deopt_id != Isolate::kNoDeoptId ? call->env() : NULL,
+                         Definition::kValue);
+  return true;
+}
+
 
 bool FlowGraphOptimizer::TryReplaceWithLoadIndexed(InstanceCallInstr* call) {
   const intptr_t class_id = ReceiverClassId(call);
-  // Set deopt_id to a valid id if the LoadIndexedInstr can cause deopt.
-  intptr_t deopt_id = Isolate::kNoDeoptId;
   switch (class_id) {
     case kArrayCid:
     case kImmutableArrayCid:
     case kGrowableObjectArrayCid:
     case kTypedDataFloat32ArrayCid:
     case kTypedDataFloat64ArrayCid:
     case kTypedDataInt8ArrayCid:
     case kTypedDataUint8ArrayCid:
     case kTypedDataUint8ClampedArrayCid:
     case kExternalTypedDataUint8ArrayCid:
     case kExternalTypedDataUint8ClampedArrayCid:
     case kTypedDataInt16ArrayCid:
     case kTypedDataUint16ArrayCid:
       break;
     case kTypedDataFloat32x4ArrayCid:
       if (!ShouldInlineSimd()) {
         return false;
       }
       break;
     case kTypedDataInt32ArrayCid:
-    case kTypedDataUint32ArrayCid: {
+    case kTypedDataUint32ArrayCid:

[Cutch, 2013/09/17 16:08:47]

Ahh, I see we never supported unboxed loads from 64-bit integer lists.

         if (!CanUnboxInt32()) return false;
-
-        // Set deopt_id if we can optimistically assume that the result is Smi.
-        // Assume mixed Mint/Smi if this instruction caused deoptimization once.
-        ASSERT(call->HasICData());
-        const ICData& ic_data = *call->ic_data();
-        deopt_id = (ic_data.deopt_reason() == kDeoptUnknown) ?
-            call->deopt_id() : Isolate::kNoDeoptId;
-      }
       break;
     default:
       return false;
   }
-  Definition* array = call->ArgumentAt(0);
-  Definition* index = call->ArgumentAt(1);
-  intptr_t array_cid = PrepareIndexedOp(call, class_id, &array, &index);
-  intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(array_cid);
-  Definition* array_op =
-      new LoadIndexedInstr(new Value(array),
-                           new Value(index),
-                           index_scale,
-                           array_cid,
-                           deopt_id);
-  ReplaceCall(call, array_op);
+
+  const Function& target =
+      Function::Handle(call->ic_data()->GetTargetAt(0));
+  TargetEntryInstr* entry;
+  Definition* last;
+  ASSERT(class_id == MethodKindToCid(MethodRecognizer::RecognizeKind(target)));
+  bool success = TryInlineRecognizedMethod(target,
+                                           call,
+                                           *call->ic_data(),
+                                           &entry, &last);
+  ASSERT(success);
+  // 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;
 }
 
 
 static bool SmiFitsInDouble() { return kSmiBits < 53; }
 
 
 bool FlowGraphOptimizer::TryReplaceWithRelationalOp(InstanceCallInstr* call,
                                                     Token::Kind op_kind) {
   const ICData& ic_data = *call->ic_data();
@@ skipping 6424 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