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

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 10885)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -5,6 +5,7 @@
 #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"
@@ -81,9 +82,9 @@
 
 
 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;
     }
   }
@@ -93,8 +94,8 @@
 
 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();
@@ -125,10 +126,10 @@
 // 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);
 }
 
 
@@ -363,9 +364,27 @@
         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;
@@ -489,7 +508,7 @@
     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);
@@ -868,4 +887,31 @@
   }
 }
 
+
+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