Change == into an instance call to allow polymorphic inlining of ==.

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"
 #include "vm/flow_graph_compiler.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/resolver.h"
 #include "vm/scopes.h"
 #include "vm/stack_frame.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, array_bounds_check_elimination, true,
     "Eliminate redundant bounds checks.");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
 DEFINE_FLAG(int, max_polymorphic_checks, 4,
     "Maximum number of polymorphic check, otherwise it is megamorphic.");
+DEFINE_FLAG(int, max_equality_polymorphic_checks, 32,
+    "Maximum number of polymorphic checks in equality operator,"
+    " otherwise use megamorphic dispatch.");
 DEFINE_FLAG(bool, remove_redundant_phis, true, "Remove redundant phis.");
 DEFINE_FLAG(bool, trace_constant_propagation, false,
     "Print constant propagation and useless code elimination.");
 DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details.");
 DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress");
 DEFINE_FLAG(bool, truncating_left_shift, true,
     "Optimize left shift to truncate if possible");
 DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis.");
 DEFINE_FLAG(bool, trace_load_optimization, false,
     "Print live sets for load optimization pass.");
@@ skipping 39 matching lines @@
           }
         }
       } else if (instr->IsPolymorphicInstanceCall()) {
         SpecializePolymorphicInstanceCall(instr->AsPolymorphicInstanceCall());
       } else if (instr->IsStrictCompare()) {
         VisitStrictCompare(instr->AsStrictCompare());
       } else if (instr->IsBranch()) {
         ComparisonInstr* compare = instr->AsBranch()->comparison();
         if (compare->IsStrictCompare()) {
           VisitStrictCompare(compare->AsStrictCompare());
-        } else if (compare->IsEqualityCompare()) {
-          StrictifyEqualityCompare(compare->AsEqualityCompare(),
-                                   instr->AsBranch());
         }
       }
     }
     current_iterator_ = NULL;
   }
 }
 
 
 // Attempt to build ICData for call using propagated class-ids.
 bool FlowGraphOptimizer::TryCreateICData(InstanceCallInstr* call) {
@@ skipping 1166 matching lines @@
   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::TryReplaceWithEqualityOp(InstanceCallInstr* call,
+                                                  Token::Kind op_kind) {
+  const ICData& ic_data = *call->ic_data();
+  ASSERT(ic_data.num_args_tested() == 2);
+
+  ASSERT(call->ArgumentCount() == 2);
+  Definition* left = call->ArgumentAt(0);
+  Definition* right = call->ArgumentAt(1);
+
+  intptr_t cid = kIllegalCid;
+  if (HasOnlyTwoOf(ic_data, kSmiCid)) {
+    InsertBefore(call,
+                 new CheckSmiInstr(new Value(left), call->deopt_id()),
+                 call->env(),
+                 Definition::kEffect);
+    InsertBefore(call,
+                 new CheckSmiInstr(new Value(right), call->deopt_id()),
+                 call->env(),
+                 Definition::kEffect);
+    cid = kSmiCid;
+  } else if (HasTwoMintOrSmi(ic_data) &&
+             FlowGraphCompiler::SupportsUnboxedMints()) {
+    cid = kMintCid;
+  } else if (HasTwoDoubleOrSmi(ic_data)) {
+    // Use double comparison.
+    if (SmiFitsInDouble()) {
+      cid = kDoubleCid;
+    } else {
+      if (ICDataHasReceiverArgumentClassIds(ic_data, kSmiCid, kSmiCid)) {
+        // We cannot use double comparison on two smis. Need polymorphic
+        // call.
+        return false;
+      } else {
+        InsertBefore(call,
+                     new CheckEitherNonSmiInstr(new Value(left),
+                                                new Value(right),
+                                                call->deopt_id()),
+                     call->env(),
+                     Definition::kEffect);
+        cid = kDoubleCid;
+      }
+    }
+  } else {
+    // Check if ICDData contains checks with Smi/Null combinations. In that case
+    // we can still emit the optimized Smi equality operation but need to add
+    // checks for null or Smi.
+    GrowableArray<intptr_t> smi_or_null(2);
+    smi_or_null.Add(kSmiCid);
+    smi_or_null.Add(kNullCid);
+    if (ICDataHasOnlyReceiverArgumentClassIds(ic_data,
+                                              smi_or_null,
+                                              smi_or_null)) {
+      const ICData& unary_checks_0 =
+          ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecks());
+      AddCheckClass(left,
+                    unary_checks_0,
+                    call->deopt_id(),
+                    call->env(),
+                    call);
+
+      const ICData& unary_checks_1 =
+          ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecksForArgNr(1));
+      AddCheckClass(right,
+                    unary_checks_1,
+                    call->deopt_id(),
+                    call->env(),
+                    call);
+      cid = kSmiCid;
+    } else {
+      // Shortcut for equality with null.
+      ConstantInstr* right_const = right->AsConstant();
+      ConstantInstr* left_const = left->AsConstant();
+      if ((right_const != NULL && right_const->value().IsNull()) ||
+          (left_const != NULL && left_const->value().IsNull())) {
+        StrictCompareInstr* comp = new StrictCompareInstr(call->token_pos(),
+                                                          Token::kEQ_STRICT,
+                                                          new Value(left),
+                                                          new Value(right));
+        ReplaceCall(call, comp);
+        return true;
+      }
+      return false;
+    }
+  }
+  ASSERT(cid != kIllegalCid);
+  EqualityCompareInstr* comp = new EqualityCompareInstr(call->token_pos(),
+                                                        op_kind,
+                                                        new Value(left),
+                                                        new Value(right),
+                                                        cid,
+                                                        call->deopt_id());
+  ReplaceCall(call, comp);
+  return true;
+}
+
 
 bool FlowGraphOptimizer::TryReplaceWithRelationalOp(InstanceCallInstr* call,
                                                     Token::Kind op_kind) {
   const ICData& ic_data = *call->ic_data();
   ASSERT(ic_data.num_args_tested() == 2);
 
   ASSERT(call->ArgumentCount() == 2);
   Definition* left = call->ArgumentAt(0);
   Definition* right = call->ArgumentAt(1);
 
@@ skipping 1560 matching lines @@
     if (prev.IsNull()) {
       prev = Bool::Get(is_subtype).raw();
     } else {
       if (is_subtype != prev.value()) return Bool::null();
     }
   }
   return prev.raw();
 }
 
 
+static Definition* OriginalDefinition(Definition* defn) {
+  while (defn->IsRedefinition() || defn->IsAssertAssignable()) {
+    if (defn->IsRedefinition()) {
+      defn = defn->AsRedefinition()->value()->definition();
+    } else {
+      defn = defn->AsAssertAssignable()->value()->definition();
+    }
+  }
+  return defn;
+}
+
+
 // TODO(srdjan): Use ICData to check if always true or false.
 void FlowGraphOptimizer::ReplaceWithInstanceOf(InstanceCallInstr* call) {
   ASSERT(Token::IsTypeTestOperator(call->token_kind()));
   Definition* left = call->ArgumentAt(0);
   Definition* instantiator = call->ArgumentAt(1);
   Definition* type_args = call->ArgumentAt(2);
   const AbstractType& type =
       AbstractType::Cast(call->ArgumentAt(3)->AsConstant()->value());
-  const bool negate =
-      Bool::Cast(call->ArgumentAt(4)->AsConstant()->value()).value();
+  const bool negate = Bool::Cast(
+      OriginalDefinition(call->ArgumentAt(4))->AsConstant()->value()).value();
   const ICData& unary_checks =
       ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecks());
   if (unary_checks.NumberOfChecks() <= FLAG_max_polymorphic_checks) {
     Bool& as_bool = Bool::ZoneHandle(InstanceOfAsBool(unary_checks, type));
     if (!as_bool.IsNull()) {
       AddReceiverCheck(call);
       if (negate) {
         as_bool = Bool::Get(!as_bool.value()).raw();
       }
       ConstantInstr* bool_const = flow_graph()->GetConstant(as_bool);
@@ skipping 78 matching lines @@
   }
 
   if (Token::IsTypeCastOperator(op_kind)) {
     ReplaceWithTypeCast(instr);
     return;
   }
 
   const ICData& unary_checks =
       ICData::ZoneHandle(instr->ic_data()->AsUnaryClassChecks());
 
-  if ((unary_checks.NumberOfChecks() > FLAG_max_polymorphic_checks) &&
+  intptr_t max_checks = (op_kind == Token::kEQ)
+      ? FLAG_max_equality_polymorphic_checks
+      : FLAG_max_polymorphic_checks;
+  if ((unary_checks.NumberOfChecks() > max_checks) &&
       InstanceCallNeedsClassCheck(instr)) {
     // Too many checks, it will be megamorphic which needs unary checks.
     instr->set_ic_data(&unary_checks);
     return;
   }
 
   if ((op_kind == Token::kASSIGN_INDEX) && TryReplaceWithStoreIndexed(instr)) {
     return;
   }
   if ((op_kind == Token::kINDEX) && TryReplaceWithLoadIndexed(instr)) {
     return;
   }
 
+  if (op_kind == Token::kEQ && TryReplaceWithEqualityOp(instr, op_kind)) {
+    return;
+  }
+
   if (Token::IsRelationalOperator(op_kind) &&
       TryReplaceWithRelationalOp(instr, op_kind)) {
     return;
   }
 
   if (Token::IsBinaryOperator(op_kind) &&
       TryReplaceWithBinaryOp(instr, op_kind)) {
     return;
   }
   if (Token::IsPrefixOperator(op_kind) &&
@@ skipping 194 matching lines @@
       new Value(instr->ArgumentAt(1)),
       needs_store_barrier);
   // Discard the environment from the original instruction because the store
   // can't deoptimize.
   instr->RemoveEnvironment();
   ReplaceCall(instr, store);
   return true;
 }
 
 
-bool FlowGraphOptimizer::CanStrictifyEqualityCompare(
-    EqualityCompareInstr* compare) {
-  // If one of the inputs is null this is a strict comparison.
-  if (compare->left()->BindsToConstantNull() ||
-      compare->right()->BindsToConstantNull()) {
-    return true;
-  }
-
-  if (compare->left()->Type()->IsNone()) {
-    return false;  // We might be running prior to any type propagation passes.
-  }
-
-  // Try resolving target function using propagated cid for the receiver.
-  // If receiver is either null or has default equality operator then
-  // we can convert such comparison to a strict one.
-  const intptr_t receiver_cid =
-     compare->left()->Type()->ToNullableCid();
-
-  if (receiver_cid == kDynamicCid) {
-    return false;
-  }
-
-  const Class& receiver_class = Class::Handle(
-      Isolate::Current()->class_table()->At(receiver_cid));
-
-  // Resolve equality operator.
-  const intptr_t kNumArgs = 2;
-  ArgumentsDescriptor args_desc(
-      Array::Handle(ArgumentsDescriptor::New(kNumArgs)));
-  const Function& function = Function::Handle(
-      Resolver::ResolveDynamicForReceiverClass(
-          receiver_class,
-          Symbols::EqualOperator(),
-          args_desc));
-
-  if (function.IsNull()) {
-    return false;
-  }
-
-  // Default equality operator declared on the Object class just calls
-  // identical.
-  return (Class::Handle(function.Owner()).id() == kInstanceCid);
-}
-
-
-template <typename T>
-bool FlowGraphOptimizer::StrictifyEqualityCompare(
-    EqualityCompareInstr* compare,
-    T current_instruction) const {
-  if (CanStrictifyEqualityCompare(compare)) {
-    Token::Kind strict_kind = (compare->kind() == Token::kEQ) ?
-        Token::kEQ_STRICT : Token::kNE_STRICT;
-    StrictCompareInstr* strict_comp =
-        new StrictCompareInstr(compare->token_pos(),
-                               strict_kind,
-                               compare->left()->CopyWithType(),
-                               compare->right()->CopyWithType());
-    // Numbers override equality and are therefore not part of this conversion.
-    strict_comp->set_needs_number_check(false);
-    current_instruction->ReplaceWith(strict_comp, current_iterator());
-    return true;
-  }
-  return false;
-}
-
-
-// Returns true if we converted EqualityCompare to StrictCompare.
-template <typename T>
-bool FlowGraphOptimizer::StrictifyEqualityCompareWithICData(
-    EqualityCompareInstr* compare,
-    const ICData& unary_ic_data,
-    T current_instruction) {
-  ASSERT(unary_ic_data.num_args_tested() == 1);
-  if (unary_ic_data.NumberOfChecks() <= FLAG_max_polymorphic_checks) {
-    // If possible classes do not override Object's equality then replace
-    // with strict equality.
-    Function& target = Function::Handle();
-    Class& targets_class = Class::Handle();
-    for (intptr_t i = 0; i < unary_ic_data.NumberOfChecks(); i++) {
-      intptr_t cid = kIllegalCid;
-      unary_ic_data.GetOneClassCheckAt(i, &cid, &target);
-      targets_class = target.Owner();
-      if (targets_class.id() != kInstanceCid) {
-        // Overriden equality operator.
-        return false;
-      }
-    }
-    AddCheckClass(compare->left()->definition(),
-                  unary_ic_data,
-                  compare->deopt_id(),
-                  current_instruction->env(),
-                  current_instruction);
-    ASSERT((compare->kind() == Token::kEQ) || (compare->kind() == Token::kNE));
-    Token::Kind strict_kind = (compare->kind() == Token::kEQ) ?
-        Token::kEQ_STRICT : Token::kNE_STRICT;
-    StrictCompareInstr* strict_comp =
-        new StrictCompareInstr(compare->token_pos(),
-                               strict_kind,
-                               compare->left()->Copy(),
-                               compare->right()->Copy());
-    // Numbers override equality and are therefore not part of this conversion.
-    strict_comp->set_needs_number_check(false);
-    current_instruction->ReplaceWith(strict_comp, current_iterator());
-    return true;
-  }
-  return false;
-}
-
-
-template <typename T>
-void FlowGraphOptimizer::HandleEqualityCompare(EqualityCompareInstr* comp,
-                                               T current_instruction) {
-  if (StrictifyEqualityCompare(comp, current_instruction)) {
-    // Based on input types, equality converted to strict-equality.
-    return;
-  }
-
-  if (!comp->HasICData() || (comp->ic_data()->NumberOfChecks() == 0)) {
-    return;
-  }
-
-  const ICData& ic_data = *comp->ic_data();
-  ASSERT(ic_data.num_args_tested() == 2);
-  ASSERT(comp->operation_cid() == kIllegalCid);
-  if (HasOnlyTwoOf(ic_data, kSmiCid)) {
-    InsertBefore(current_instruction,
-                 new CheckSmiInstr(comp->left()->Copy(), comp->deopt_id()),
-                 current_instruction->env(),
-                 Definition::kEffect);
-    InsertBefore(current_instruction,
-                 new CheckSmiInstr(comp->right()->Copy(), comp->deopt_id()),
-                 current_instruction->env(),
-                 Definition::kEffect);
-    comp->set_operation_cid(kSmiCid);
-  } else if (HasTwoMintOrSmi(ic_data) &&
-             FlowGraphCompiler::SupportsUnboxedMints()) {
-    comp->set_operation_cid(kMintCid);
-  } else if (HasTwoDoubleOrSmi(ic_data)) {
-    // Use double comparison.
-    if (SmiFitsInDouble()) {
-      comp->set_operation_cid(kDoubleCid);
-    } else {
-      if (ICDataHasReceiverArgumentClassIds(ic_data, kSmiCid, kSmiCid)) {
-        // We cannot use double comparison on two smis.
-        ASSERT(comp->operation_cid() == kIllegalCid);
-      } else {
-        InsertBefore(current_instruction,
-                     new CheckEitherNonSmiInstr(comp->left()->Copy(),
-                                                comp->right()->Copy(),
-                                                comp->deopt_id()),
-                     current_instruction->env(),
-                     Definition::kEffect);
-        comp->set_operation_cid(kDoubleCid);
-      }
-    }
-  }
-
-  if (comp->operation_cid() != kIllegalCid) {
-    // Done.
-    return;
-  }
-
-  const ICData& unary_checks_0 =
-      ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecks());
-  if (StrictifyEqualityCompareWithICData(
-        comp, unary_checks_0, current_instruction)) {
-    // Based on ICData, equality converted to strict-equality.
-    return;
-  }
-
-  // Check if ICDData contains checks with Smi/Null combinations. In that case
-  // we can still emit the optimized Smi equality operation but need to add
-  // checks for null or Smi.
-  // TODO(srdjan): Add it for Double and Mint.
-  GrowableArray<intptr_t> smi_or_null(2);
-  smi_or_null.Add(kSmiCid);
-  smi_or_null.Add(kNullCid);
-  if (ICDataHasOnlyReceiverArgumentClassIds(ic_data,
-                                            smi_or_null,
-                                            smi_or_null)) {
-    AddCheckClass(comp->left()->definition(),
-                  unary_checks_0,
-                  comp->deopt_id(),
-                  current_instruction->env(),
-                  current_instruction);
-
-    const ICData& unary_checks_1 =
-        ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecksForArgNr(1));
-    AddCheckClass(comp->right()->definition(),
-                  unary_checks_1,
-                  comp->deopt_id(),
-                  current_instruction->env(),
-                  current_instruction);
-    comp->set_operation_cid(kSmiCid);
-  }
-}
-
-
-
-
-void FlowGraphOptimizer::VisitEqualityCompare(EqualityCompareInstr* instr) {
-  HandleEqualityCompare(instr, instr);
-}
-
-
-void FlowGraphOptimizer::VisitBranch(BranchInstr* instr) {
-  ComparisonInstr* comparison = instr->comparison();
-  if (comparison->IsEqualityCompare()) {
-    HandleEqualityCompare(comparison->AsEqualityCompare(), instr);
-  } else {
-    ASSERT(comparison->IsStrictCompare());
-    // Nothing to do.
-  }
-}
-
-
 // Range analysis for smi values.
 class RangeAnalysis : public ValueObject {
  public:
   explicit RangeAnalysis(FlowGraph* flow_graph)
       : flow_graph_(flow_graph),
         marked_defns_(NULL) { }
 
   // Infer ranges for all values and remove overflow checks from binary smi
   // operations when proven redundant.
   void Analyze();
@@ skipping 1075 matching lines @@
     return (kind_ == other->kind_) &&
         (representation_ == other->representation_) &&
         (instance_ == other->instance_) &&
         SameField(other);
   }
 
   // Create a zone allocated copy of this place.
   static Place* Wrap(const Place& place);
 
  private:
-  static Definition* OriginalDefinition(Definition* defn) {
-    while (defn->IsRedefinition() || defn->IsAssertAssignable()) {
-      if (defn->IsRedefinition()) {
-        defn = defn->AsRedefinition()->value()->definition();
-      } else {
-        defn = defn->AsAssertAssignable()->value()->definition();
-      }
-    }
-    return defn;
-  }
-
   bool SameField(Place* other) const {
     return (kind_ == kField) ? (field().raw() == other->field().raw())
                              : (offset_in_bytes_ == other->offset_in_bytes_);
   }
 
   intptr_t FieldHashcode() const {
     return (kind_ == kField) ? reinterpret_cast<intptr_t>(field().raw())
                              : offset_in_bytes_;
   }
 
@@ skipping 1822 matching lines @@
       return false;
   }
 }
 
 
 void ConstantPropagator::VisitEqualityCompare(EqualityCompareInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
   const Object& right = instr->right()->definition()->constant_value();
 
   if (instr->left()->definition() == instr->right()->definition()) {
-    // Fold x == x, and x != x to true/false for numbers and checked strict
-    // comparisons.
-    if (instr->IsCheckedStrictEqual() ||
-        RawObject::IsIntegerClassId(instr->operation_cid())) {
+    // Fold x == x, and x != x to true/false for numbers comparisons.
+    if (RawObject::IsIntegerClassId(instr->operation_cid())) {
       return SetValue(instr, Bool::Get(instr->kind() == Token::kEQ));
     }
   }
 
   if (IsNonConstant(left) || IsNonConstant(right)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
     if (left.IsInteger() && right.IsInteger()) {
       const bool result = CompareIntegers(instr->kind(),
                                           Integer::Cast(left),
@@ skipping 948 matching lines @@
                                             comparison->kind(),
                                             left,
                                             right);
   } else if (comparison->IsEqualityCompare()) {
     EqualityCompareInstr* equality_compare = comparison->AsEqualityCompare();
     EqualityCompareInstr* new_equality_compare =
         new EqualityCompareInstr(equality_compare->token_pos(),
                                  comparison->kind(),
                                  left,
                                  right,
-                                 Object::null_array());
-    new_equality_compare->set_ic_data(equality_compare->ic_data());
-    new_equality_compare->set_operation_cid(equality_compare->operation_cid());
+                                 equality_compare->operation_cid(),
+                                 equality_compare->deopt_id());
     new_comparison = new_equality_compare;
   } else {
     ASSERT(comparison->IsRelationalOp());
     RelationalOpInstr* relational_op = comparison->AsRelationalOp();
     RelationalOpInstr* new_relational_op =
         new RelationalOpInstr(relational_op->token_pos(),
                               comparison->kind(),
                               left,
                               right,
                               relational_op->operation_cid(),
@@ skipping 523 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