Strengthen type assertions post-dominated by checks during type propagation.

runtime/vm/flow_graph_type_propagator.cc

Index: runtime/vm/flow_graph_type_propagator.cc
diff --git a/runtime/vm/flow_graph_type_propagator.cc b/runtime/vm/flow_graph_type_propagator.cc
index d16e382f1076a0752d7af6b197d037f75583a2be..62bfa0e876c220f422bcc1d8ad5b9f19d0c5706f 100644
--- a/runtime/vm/flow_graph_type_propagator.cc
+++ b/runtime/vm/flow_graph_type_propagator.cc
@@ -21,10 +21,22 @@ FlowGraphTypePropagator::FlowGraphTypePropagator(FlowGraph* flow_graph)
     : FlowGraphVisitor(flow_graph->reverse_postorder()),
       flow_graph_(flow_graph),
       types_(flow_graph->current_ssa_temp_index()),
-      in_worklist_(new BitVector(flow_graph->current_ssa_temp_index())) {
+      in_worklist_(new BitVector(flow_graph->current_ssa_temp_index())),
+      asserts_(NULL),
+      collected_asserts_(NULL) {
   for (intptr_t i = 0; i < flow_graph->current_ssa_temp_index(); i++) {
     types_.Add(NULL);
   }
+
+  if (FLAG_enable_type_checks) {
+    asserts_ = new ZoneGrowableArray<AssertAssignableInstr*>(
+        flow_graph->current_ssa_temp_index());
+    for (intptr_t i = 0; i < flow_graph->current_ssa_temp_index(); i++) {
+      asserts_->Add(NULL);
+    }
+
+    collected_asserts_ = new ZoneGrowableArray<intptr_t>(10);
+  }
 }
 
 
@@ -82,6 +94,10 @@ void FlowGraphTypePropagator::Propagate() {
 void FlowGraphTypePropagator::PropagateRecursive(BlockEntryInstr* block) {
   const intptr_t rollback_point = rollback_.length();
 
+  if (FLAG_enable_type_checks) {
+    StrengthenAsserts(block);
+  }
+
   block->Accept(this);
 
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
@@ -203,6 +219,86 @@ Definition* FlowGraphTypePropagator::RemoveLastFromWorklist() {
 }
 
 
+// Unwrap all assert assignable and get a real definition of the value.
+static Definition* UnwrapAsserts(Definition* defn) {
+  while (defn->IsAssertAssignable()) {
+    defn = defn->AsAssertAssignable()->value()->definition();
+  }
+  return defn;
+}
+
+
+// Marker that is used to mark values that already had type assertion
+// strengthened.
+static AssertAssignableInstr* kStrengthenedAssertMarker =

[Florian Schneider, 2013/02/20 17:57:38]

does it need to be global?

[Vyacheslav Egorov (Google), 2013/02/20 19:35:10]

Done.

+    reinterpret_cast<AssertAssignableInstr*>(-1);
+
+
+// In the given block strengthen type assertions by hoisting first class or smi
+// check over the same value up to the point before the assertion. This allows
+// to eliminate type assertions that are postdominated by class or smi checks as
+// these checks are strongly stricter than type assertions.
+void FlowGraphTypePropagator::StrengthenAsserts(BlockEntryInstr* block) {
+  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+    Instruction* instr = it.Current();
+
+    if (instr->IsCheckSmi() || instr->IsCheckClass()) {
+      StrengthenAssertWith(instr);
+    }
+
+    // If this is the first type assertion checking given value record it.
+    AssertAssignableInstr* assert = instr->AsAssertAssignable();
+    if (assert != NULL) {
+      Definition* defn = UnwrapAsserts(assert->value()->definition());
+      if ((*asserts_)[defn->ssa_temp_index()] == NULL) {
+        (*asserts_)[defn->ssa_temp_index()] = assert;
+        collected_asserts_->Add(defn->ssa_temp_index());
+      }
+    }
+  }
+
+  for (intptr_t i = 0; i < collected_asserts_->length(); i++) {
+    (*asserts_)[(*collected_asserts_)[i]] = NULL;
+  }
+
+  collected_asserts_->TruncateTo(0);
+}
+
+
+void FlowGraphTypePropagator::StrengthenAssertWith(Instruction* check) {
+  Definition* defn = UnwrapAsserts(check->InputAt(0)->definition());
+

[Florian Schneider, 2013/02/20 17:57:38]

const AssertAssignableInstr* kStrengthenedAssertMarker = 
    reinterpret_cast<AssertAssignableInstr*>(-1);

[Vyacheslav Egorov (Google), 2013/02/20 19:35:10]

Done.

+  AssertAssignableInstr* assert = (*asserts_)[defn->ssa_temp_index()];
+  if ((assert == NULL) || (assert == kStrengthenedAssertMarker)) {
+    return;
+  }
+

[Florian Schneider, 2013/02/20 17:57:38]

You can also use deopt_id() of the AssertAssignableInstr itself. It should
always match the environmnent though. Maybe add here

ASSERT(assert->deopt_id() == assert->env()->deopt_id());

[Vyacheslav Egorov (Google), 2013/02/20 19:35:10]

Done.

+  Instruction* check_clone = NULL;
+  if (check->IsCheckSmi()) {
+    check_clone =
+        new CheckSmiInstr(assert->value()->Copy(),
+                          assert->env()->deopt_id());
+  } else {
+    ASSERT(check->IsCheckClass());
+    check_clone =
+        new CheckClassInstr(assert->value()->Copy(),
+                            assert->env()->deopt_id(),
+                            check->AsCheckClass()->unary_checks());
+  }
+  ASSERT(check_clone != NULL);
+
+  Value* use = check_clone->InputAt(0);
+  use->set_instruction(check_clone);
+  use->set_use_index(0);
+  use->definition()->AddInputUse(use);
+
+  assert->env()->DeepCopyTo(check_clone);
+  check_clone->InsertBefore(assert);
+
+  (*asserts_)[defn->ssa_temp_index()] = kStrengthenedAssertMarker;
+}
+
+
 void CompileType::Union(CompileType* other) {
   if (other->IsNone()) {
     return;