Implement class id checks as a separate instruction and add a local CSE optimization pass.

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/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/scopes.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(bool, enable_type_checks);
@@ skipping 56 matching lines @@
     if ((class_ids[0] == receiver_class_id) &&
         (class_ids[1] == argument_class_id)) {
       return true;
     }
   }
   return false;
 }
 
 
 static bool ClassIdIsOneOf(intptr_t class_id,
-                           GrowableArray<intptr_t>* class_ids) {
-  for (intptr_t i = 0; i < class_ids->length(); i++) {
-    if ((*class_ids)[i] == class_id) {
+                           const GrowableArray<intptr_t>& class_ids) {
+  for (intptr_t i = 0; i < class_ids.length(); i++) {
+    if (class_ids[i] == class_id) {
       return true;
     }
   }
   return false;
 }
 
 
 static bool ICDataHasOnlyReceiverArgumentClassIds(
     const ICData& ic_data,
-    GrowableArray<intptr_t>* receiver_class_ids,
-    GrowableArray<intptr_t>* argument_class_ids) {
+    const GrowableArray<intptr_t>& receiver_class_ids,
+    const GrowableArray<intptr_t>& argument_class_ids) {
   if (ic_data.num_args_tested() != 2) return false;
 
   Function& target = Function::Handle();
   for (intptr_t i = 0; i < ic_data.NumberOfChecks(); i++) {
     GrowableArray<intptr_t> class_ids;
     ic_data.GetCheckAt(i, &class_ids, &target);
     ASSERT(class_ids.length() == 2);
     if (!ClassIdIsOneOf(class_ids[0], receiver_class_ids) ||
         !ClassIdIsOneOf(class_ids[1], argument_class_ids)) {
       return false;
@@ skipping 10 matching lines @@
 
 static bool HasOnlyTwoSmi(const ICData& ic_data) {
   return (ic_data.NumberOfChecks() == 1) &&
       ICDataHasReceiverArgumentClassIds(ic_data, kSmiCid, kSmiCid);
 }
 
 
 // Returns false if the ICData contains anything other than the 4 combinations
 // of Mint and Smi for the receiver and argument classes.
 static bool HasTwoMintOrSmi(const ICData& ic_data) {
-  GrowableArray<intptr_t> class_ids;
+  GrowableArray<intptr_t> class_ids(2);
   class_ids.Add(kSmiCid);
   class_ids.Add(kMintCid);
-  return ICDataHasOnlyReceiverArgumentClassIds(ic_data, &class_ids, &class_ids);
+  return ICDataHasOnlyReceiverArgumentClassIds(ic_data, class_ids, class_ids);
 }
 
 
 static bool HasOneDouble(const ICData& ic_data) {
   return ICDataHasReceiverClassId(ic_data, kDoubleCid);
 }
 
 
 static bool HasOnlyTwoDouble(const ICData& ic_data) {
   return (ic_data.NumberOfChecks() == 1) &&
@@ skipping 214 matching lines @@
   if (target.kind() == RawFunction::kImplicitGetter) {
     if (!HasOneTarget(ic_data)) {
       // TODO(srdjan): Implement for mutiple targets.
       return false;
     }
     // Inline implicit instance getter.
     const String& field_name =
         String::Handle(Field::NameFromGetter(comp->function_name()));
     const Field& field = Field::Handle(GetField(class_ids[0], field_name));
     ASSERT(!field.IsNull());
-    LoadInstanceFieldComp* load = new LoadInstanceFieldComp(
-        field, comp->ArgumentAt(0)->value(), comp);
-    load->set_ic_data(comp->ic_data());
+
+    LoadInstanceFieldComp* load;
+    if (!use_ssa_) {
+      load = new LoadInstanceFieldComp(
+          field, comp->ArgumentAt(0)->value(), comp);
+      load->set_ic_data(comp->ic_data());
+    } else {

[srdjan, 2012/08/17 22:30:22]

The code below is probably going to be quite common, you may want to factor it
out in next CL, once you start applying it to other operations.

[Florian Schneider, 2012/08/20 12:09:37]

Yes, this will be similar for inserting other checks. I'll factor it out once we
have a second example. 

+      CheckClassComp* check =
+          new CheckClassComp(comp->ArgumentAt(0)->value(), comp);

[srdjan, 2012/08/17 22:30:22]

You may want to check if the CheckClassComp is needed at all by looking at
ResultCid of value.  TODO OK for now.

[Florian Schneider, 2012/08/20 12:09:37]

I'll add a TODO. The only thing required for that is that we already have
propagated cid information. Currently, we won't have propagated the info across
blocks at this point. The other possibility would be to have a separate check
elimination pass after type propagation.

+      const ICData& unary_checks =
+          ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecks());
+      check->set_ic_data(&unary_checks);
+      BindInstr* check_instr = new BindInstr(BindInstr::kUnused, check);
+      ASSERT(instr->env() != NULL);  // Always the case with SSA.
+      check_instr->set_env(
+          new Environment(instr->env()->values(),
+                          instr->env()->fixed_parameter_count()));
+      check_instr->InsertBefore(instr);
+      load = new LoadInstanceFieldComp(
+          field, comp->ArgumentAt(0)->value(), NULL);
+    }
     instr->set_computation(load);
     RemovePushArguments(comp);
     return true;
   }
 
   // Not an implicit getter.
   MethodRecognizer::Kind recognized_kind =
       MethodRecognizer::RecognizeKind(target);
 
   // VM objects length getter.
@@ skipping 103 matching lines @@
     }
     if ((op_kind == Token::kSET) && TryInlineInstanceSetter(instr, comp)) {
       return;
     }
     if (TryInlineInstanceMethod(instr, comp)) {
       return;
     }
     const intptr_t kMaxChecks = 4;
     if (comp->ic_data()->NumberOfChecks() <= kMaxChecks) {
       PolymorphicInstanceCallComp* call = new PolymorphicInstanceCallComp(comp);
-      ICData& unary_checks =
+      const ICData& unary_checks =
           ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecks());
       call->set_ic_data(&unary_checks);
       instr->set_computation(call);
     }
   }
   // An instance call without ICData should continue calling via IC calls
   // which should trigger reoptimization of optimized code.
 }
 
 
@@ skipping 358 matching lines @@
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       LocationSummary* locs = it.Current()->locs();
       if ((locs != NULL) && locs->can_call()) {
         is_leaf_ = false;
         return;
       }
     }
   }
 }
 
+
+void LocalCSE::Optimize() {
+  for (intptr_t i = 0; i < blocks_.length(); ++i) {
+    BlockEntryInstr* entry = blocks_[i];
+    DirectChainedHashMap<BindInstr> map;
+    ASSERT(map.IsEmpty());
+    for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
+      BindInstr* instr = it.Current()->AsBind();
+      if (instr == NULL || instr->computation()->HasSideEffect()) continue;
+      BindInstr* result = map.Lookup(instr);
+      if (result == NULL) {
+        map.Insert(instr);
+        continue;
+      }
+      // Replace current with lookup result.
+      instr->ReplaceUsesWith(result);
+      it.RemoveCurrentFromGraph();
+      if (FLAG_trace_optimization) {
+        OS::Print("Replacing v%d with v%d\n",
+                  instr->ssa_temp_index(),
+                  result->ssa_temp_index());
+      }
+    }
+  }
+}
+
+
 }  // namespace dart