Some cleanups, started implementing checked instance calls, better equality operation.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2012, 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/flow_graph_builder.h"
 #include "vm/il_printer.h"
 #include "vm/object_store.h"
 
@@ skipping 140 matching lines @@
 }
 
 
 static bool HasTwoDouble(const ICData& ic_data) {
   const Class& double_class =
       Class::Handle(Isolate::Current()->object_store()->double_class());
   return ICDataHasTwoReceiverClasses(ic_data, double_class, double_class);
 }
 
 
-void FlowGraphOptimizer::TryReplaceWithBinaryOp(InstanceCallComp* comp,
+bool FlowGraphOptimizer::TryReplaceWithBinaryOp(InstanceCallComp* comp,
                                                 Token::Kind op_kind) {
   if (comp->ic_data()->NumberOfChecks() != 1) {
     // TODO(srdjan): Not yet supported.
-    return;
+    return false;
   }
 
   BinaryOpComp::OperandsType operands_type;
 
   if (HasTwoSmi(*comp->ic_data())) {
     if (op_kind == Token::kDIV ||
         op_kind == Token::kMOD) {
       // TODO(srdjan): Not yet supported.
-      return;
+      return false;
     }
 
     operands_type = BinaryOpComp::kSmiOperands;
   } else if (HasTwoDouble(*comp->ic_data())) {
     if (op_kind != Token::kADD &&
         op_kind != Token::kSUB &&
         op_kind != Token::kMUL &&
         op_kind != Token::kDIV) {
       // TODO(vegorov): Not yet supported.
-      return;
+      return false;
     }
 
     operands_type = BinaryOpComp::kDoubleOperands;
   } else {
     // TODO(srdjan): Not yet supported.
-    return;
+    return false;
   }
 
   ASSERT(comp->instr() != NULL);
   ASSERT(comp->InputCount() == 2);
   Value* left = comp->InputAt(0);
   Value* right = comp->InputAt(1);
   BinaryOpComp* bin_op =
       new BinaryOpComp(op_kind,
                        operands_type,
                        comp,
                        left,
                        right);
-  ASSERT(bin_op->ic_data() == NULL);
   bin_op->set_ic_data(comp->ic_data());
-  bin_op->set_instr(comp->instr());
-  comp->instr()->replace_computation(bin_op);
+  comp->ReplaceWith(bin_op);
+  return true;
 }
 
 
-void FlowGraphOptimizer::TryReplaceWithUnaryOp(InstanceCallComp* comp,
-                                              Token::Kind op_kind) {
+bool FlowGraphOptimizer::TryReplaceWithUnaryOp(InstanceCallComp* comp,
+                                               Token::Kind op_kind) {
   if (comp->ic_data()->NumberOfChecks() != 1) {
     // TODO(srdjan): Not yet supported.
-    return;
+    return false;
   }
   ASSERT(comp->instr() != NULL);
   ASSERT(comp->InputCount() == 1);
   Computation* unary_op = NULL;
   if (HasOneSmi(*comp->ic_data())) {
     unary_op = new UnarySmiOpComp(op_kind, comp, comp->InputAt(0));
   } else if (HasOneDouble(*comp->ic_data()) && (op_kind == Token::kNEGATE)) {
     unary_op = new NumberNegateComp(comp, comp->InputAt(0));
   }
   if (unary_op != NULL) {
-    ASSERT(unary_op->ic_data() == NULL);
     unary_op->set_ic_data(comp->ic_data());
-    unary_op->set_instr(comp->instr());
-    comp->instr()->replace_computation(unary_op);
+    comp->ReplaceWith(unary_op);
+    return true;
   }
+  return false;
 }
 
 
 // Returns true if all targets are the same.
 // TODO(srdjan): if targets are native use their C_function to compare.
 static bool HasOneTarget(const ICData& ic_data) {
   ASSERT(ic_data.NumberOfChecks() > 0);
   Function& prev_target = Function::Handle();
   GrowableArray<const Class*> classes;
   ic_data.GetCheckAt(0, &classes, &prev_target);
@@ skipping 19 matching lines @@
     field = cls.LookupInstanceField(field_name);
     if (!field.IsNull()) {
       return field.raw();
     }
     cls = cls.SuperClass();
   }
   return Field::null();
 }
 
 
+// Returns all receiver class-ids and corresponding tagets for the given
+// 'ic_data', sorted so that a smi class id is at index[0] if it exists.
+static void ExtractClassIdsAndTargets(const ICData& ic_data,
+                                      ZoneGrowableArray<intptr_t>* class_ids,
+                                      ZoneGrowableArray<Function*>* targets) {
+  ASSERT(class_ids != NULL);
+  ASSERT(targets != NULL);
+  class_ids->Clear();
+  targets->Clear();
+  intptr_t smi_index = -1;
+  Function& target = Function::Handle();
+  GrowableArray<const Class*> classes;
+  for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) {
+    ic_data.GetCheckAt(i, &classes, &target);
+    // Collect receiver class only.
+    const intptr_t class_id = (*classes[0]).id();
+    if (ic_data.num_args_tested() > 1) {
+      // Check if we have not already entered the class-id.
+      Function* target_found = NULL;
+      for (intptr_t k = 0; k < class_ids->length(); k++) {
+        if ((*class_ids)[k] == class_id) {
+          target_found = (*targets)[k];
+          break;
+        }
+      }
+      if (target_found != NULL) {
+        ASSERT(target_found->raw() == target.raw());
+        continue;
+      }
+    }
+    if (class_id == kSmi) {
+      ASSERT(smi_index < 0);  // Classes entered only once in ic_data.
+      smi_index = class_ids->length();
+    }
+    class_ids->Add(class_id);
+    targets->Add(&Function::ZoneHandle(target.raw()));
+  }
+  if (smi_index >= 0) {
+    // Smi class id must be at index 0.
+    intptr_t temp_id = (*class_ids)[0];
+    Function* temp_func = (*targets)[0];
+    (*class_ids)[0] =  (*class_ids)[smi_index];
+    (*targets)[0] =  (*targets)[smi_index];
+    (*class_ids)[smi_index] = temp_id;
+    (*targets)[smi_index] = temp_func;
+  }
+}
+
+
 // Returns array of all class ids that are in ic_data. The result is
 // normalized so that a smi class is at index 0 if it exists in the ic_data.
 static ZoneGrowableArray<intptr_t>*  ExtractClassIds(const ICData& ic_data) {
   if (ic_data.NumberOfChecks() == 0) return NULL;
   ZoneGrowableArray<intptr_t>* result =
       new ZoneGrowableArray<intptr_t>(ic_data.NumberOfChecks());
-  intptr_t smi_index = -1;
-  Function& target = Function::Handle();
-  Class& cls = Class::Handle();
-  for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) {
-    ic_data.GetOneClassCheckAt(i, &cls, &target);
-    result->Add(cls.id());
-    if (cls.id() == kSmi) {
-      ASSERT(smi_index < 0);  // Classes entered only once in ic_data.
-      smi_index = i;
-    }
-  }
-  if (smi_index >= 0) {
-    // Smi class id must be at index 0.
-    intptr_t temp = (*result)[0];
-    (*result)[0] =  (*result)[smi_index];
-    (*result)[smi_index] = temp;
-  }
+  ZoneGrowableArray<Function*>* dummy =
+      new ZoneGrowableArray<Function*>(ic_data.NumberOfChecks());
+  ExtractClassIdsAndTargets(ic_data, result, dummy);

[Vyacheslav Egorov (Google), 2012/06/13 09:02:27]

how about passing NULL instead of dummy? Collecting stuff that is not used is a
bit wasteful.

[srdjan, 2012/06/13 18:34:24]

Done.

   return result;
 }
 
 
 // Only unique implicit instance getters can be currently handled.
-void FlowGraphOptimizer::TryInlineInstanceGetter(InstanceCallComp* comp) {
+bool FlowGraphOptimizer::TryInlineInstanceGetter(InstanceCallComp* comp) {
   ASSERT(comp->HasICData());
   const ICData& ic_data = *comp->ic_data();
   if (ic_data.NumberOfChecks() == 0) {
     // No type feedback collected.
-    return;
+    return false;
   }
   Function& target = Function::Handle();
   GrowableArray<const Class*> classes;
   ic_data.GetCheckAt(0, &classes, &target);
   ASSERT(classes.length() == 1);
 
   if (target.kind() == RawFunction::kImplicitGetter) {
     if (!HasOneTarget(ic_data)) {
       // TODO(srdjan): Implement for mutiple targets.
-      return;
+      return false;
     }
     // Inline implicit instance getter.
     const String& field_name =
         String::Handle(Field::NameFromGetter(comp->function_name()));
     const Field& field = Field::Handle(GetField(*classes[0], field_name));
     ASSERT(!field.IsNull());
     LoadInstanceFieldComp* load = new LoadInstanceFieldComp(
         field, comp->InputAt(0), comp, ExtractClassIds(ic_data));
-    // Replace 'comp' with 'load'.
-    load->set_instr(comp->instr());
-    comp->instr()->replace_computation(load);
-    return;
+    comp->ReplaceWith(load);
+    return true;
   }
 
   // Not an implicit getter.
   MethodRecognizer::Kind recognized_kind =
       MethodRecognizer::RecognizeKind(target);
 
   // VM objects length getter.
   if ((recognized_kind == MethodRecognizer::kObjectArrayLength) ||
       (recognized_kind == MethodRecognizer::kImmutableArrayLength) ||
       (recognized_kind == MethodRecognizer::kGrowableArrayLength)) {
     if (!HasOneTarget(ic_data)) {
       // TODO(srdjan): Implement for mutiple targets.
-      return;
+      return false;
     }
     intptr_t length_offset = -1;
     switch (recognized_kind) {
       case MethodRecognizer::kObjectArrayLength:
       case MethodRecognizer::kImmutableArrayLength:
         length_offset = Array::length_offset();
         break;
       case MethodRecognizer::kGrowableArrayLength:
         length_offset = GrowableObjectArray::length_offset();
         break;
       default:
         UNREACHABLE();
     }
     LoadVMFieldComp* load = new LoadVMFieldComp(
         comp->InputAt(0),
         length_offset,
         Type::ZoneHandle(Type::IntInterface()),
         comp,
         ExtractClassIds(ic_data));
-    load->set_instr(comp->instr());
-    comp->instr()->replace_computation(load);
-    return;
+    comp->ReplaceWith(load);
+    return true;
   }
 
   if (recognized_kind == MethodRecognizer::kStringBaseLength) {
     ASSERT(HasOneTarget(ic_data));
     LoadVMFieldComp* load = new LoadVMFieldComp(
         comp->InputAt(0),
         String::length_offset(),
         Type::ZoneHandle(Type::IntInterface()),
         comp,
         ExtractClassIds(ic_data));
-    load->set_instr(comp->instr());
-    comp->instr()->replace_computation(load);
-    return;
+    comp->ReplaceWith(load);
+    return true;
   }
+  return false;
 }
 
 
 // Inline only simple, frequently called core library methods.
-void FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallComp* comp) {
+bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallComp* comp) {
   ASSERT(comp->HasICData());
   const ICData& ic_data = *comp->ic_data();
   if ((ic_data.NumberOfChecks() == 0) || !HasOneTarget(ic_data)) {
     // No type feedback collected.
-    return;
+    return false;
   }
   Function& target = Function::Handle();
   GrowableArray<const Class*> classes;
   ic_data.GetCheckAt(0, &classes, &target);
-  ASSERT(classes.length() == 1);
   MethodRecognizer::Kind recognized_kind =
       MethodRecognizer::RecognizeKind(target);
   if (recognized_kind == MethodRecognizer::kDoubleToDouble) {
     // TODO(srdjan): Implement.
   }
   if (recognized_kind == MethodRecognizer::kIntegerToDouble) {
     // TODO(srdjan): Implement.
   }
+  return false;
 }
 
 
 void FlowGraphOptimizer::VisitInstanceCall(InstanceCallComp* comp) {
-  if (comp->HasICData()) {
+  if (comp->HasICData() && (comp->ic_data()->NumberOfChecks() > 0)) {
     const String& function_name = comp->function_name();
     Token::Kind op_kind = Token::GetBinaryOp(function_name);

[Vyacheslav Egorov (Google), 2012/06/13 09:02:27]

Can we just store op_kind in the InstanceCallComp produced from binary/unary
ops? Parsing it seems so strange when builder actually knew what kind of token
was there.

The same for getter (we can mark them with kGet token)

[srdjan, 2012/06/13 18:34:24]

Yes, next CL.

-    if (op_kind != Token::kILLEGAL) {
-      TryReplaceWithBinaryOp(comp, op_kind);
+    if ((op_kind != Token::kILLEGAL) && TryReplaceWithBinaryOp(comp, op_kind)) {
       return;
     }
     op_kind = Token::GetUnaryOp(function_name);
-    if (op_kind != Token::kILLEGAL) {
-      TryReplaceWithUnaryOp(comp, op_kind);
+    if ((op_kind != Token::kILLEGAL) && TryReplaceWithUnaryOp(comp, op_kind)) {
       return;
     }
-    if (Field::IsGetterName(function_name)) {
-      TryInlineInstanceGetter(comp);
+    if ((Field::IsGetterName(function_name)) && TryInlineInstanceGetter(comp)) {
       return;
     }
-    TryInlineInstanceMethod(comp);
+    if (TryInlineInstanceMethod(comp)) {
+      return;
+    }
+    const intptr_t kMaxChecks = 4;
+    if (comp->ic_data()->num_args_tested() <= kMaxChecks) {
+      ZoneGrowableArray<intptr_t>* class_ids =
+          new ZoneGrowableArray<intptr_t>();
+      ZoneGrowableArray<Function*>* targets =
+          new ZoneGrowableArray<Function*>();
+      ExtractClassIdsAndTargets(*comp->ic_data(), class_ids, targets);
+      CheckedInstanceCallComp* call =
+          new CheckedInstanceCallComp(comp, *class_ids, *targets);
+      comp->ReplaceWith(call);
+    }
   }
 }
 
 
 void FlowGraphOptimizer::VisitStaticCall(StaticCallComp* comp) {
   MethodRecognizer::Kind recognized_kind =
       MethodRecognizer::RecognizeKind(comp->function());
   if (recognized_kind == MethodRecognizer::kMathSqrt) {
     // TODO(srdjan): Implement this.
   }
 }
 
 
-void FlowGraphOptimizer::TryInlineInstanceSetter(InstanceSetterComp* comp) {
+bool FlowGraphOptimizer::TryInlineInstanceSetter(InstanceSetterComp* comp) {
   ASSERT(comp->HasICData());
   const ICData& ic_data = *comp->ic_data();
   if (ic_data.NumberOfChecks() == 0) {
     // No type feedback collected.
-    return;
+    return false;
   }
   if (!HasOneTarget(ic_data)) {
     // TODO(srdjan): Implement when not all targets are the sa,e.
-    return;
+    return false;
   }
   Function& target = Function::Handle();
   Class& cls = Class::Handle();
   ic_data.GetOneClassCheckAt(0, &cls, &target);
   if (target.kind() != RawFunction::kImplicitSetter) {
     // Not an implicit setter.
     // TODO(srdjan): Inline special setters.
-    return;
+    return false;
   }
   // Inline implicit instance setter.
   const Field& field = Field::Handle(GetField(cls, comp->field_name()));
   ASSERT(!field.IsNull());
   StoreInstanceFieldComp* store = new StoreInstanceFieldComp(
       field,
       comp->InputAt(0),
       comp->InputAt(1),
       comp,
       ExtractClassIds(ic_data));
-  // Replace 'comp' with 'store'.
-  store->set_instr(comp->instr());
-  comp->instr()->replace_computation(store);
+  comp->ReplaceWith(store);
+  return true;
 }
 
 
 
 void FlowGraphOptimizer::VisitInstanceSetter(InstanceSetterComp* comp) {
   // TODO(srdjan): Add assigneable check node if --enable_type_checks.
   if (comp->HasICData() && !FLAG_enable_type_checks) {
     TryInlineInstanceSetter(comp);
   }
 }
@@ skipping 31 matching lines @@
   ASSERT(HasOneTarget(ic_data));
 
   if (HasTwoSmi(ic_data)) {
     comp->set_operands_class_id(kSmi);
   } else if (HasTwoDouble(ic_data)) {
     comp->set_operands_class_id(kDouble);
   }
 }
 
 
+void FlowGraphOptimizer::VisitEqualityCompare(EqualityCompareComp* comp) {
+  if (!comp->HasICData()) return;
+  const ICData& ic_data = *comp->ic_data();
+  if (ic_data.NumberOfChecks() != 1) return;
+  ASSERT(HasOneTarget(ic_data));
+  if (HasTwoSmi(ic_data)) {
+    comp->set_operands_class_id(kSmi);
+  }
+}
+
+
 void FlowGraphOptimizer::VisitDo(DoInstr* instr) {
   instr->computation()->Accept(this);
 }
 
 
 void FlowGraphOptimizer::VisitBind(BindInstr* instr) {
   instr->computation()->Accept(this);
 }
 
 
 }  // namespace dart