AOT: Use a cid range check when possible to implement type tests.

runtime/vm/aot_optimizer.cc

Index: runtime/vm/aot_optimizer.cc
diff --git a/runtime/vm/aot_optimizer.cc b/runtime/vm/aot_optimizer.cc
index 2dc0be48ad8acfaa668b5c703f871ef0bbf3de88..9b39040428ae8ae28171bc70f161c2898df0f3c4 100644
--- a/runtime/vm/aot_optimizer.cc
+++ b/runtime/vm/aot_optimizer.cc
@@ -37,6 +37,8 @@ DEFINE_FLAG(int, max_exhaustive_polymorphic_checks, 5,
 #define I (isolate())
 #define Z (zone())
 
+#ifdef DART_PRECOMPILER
+
 static bool ShouldInlineSimd() {
   return FlowGraphCompiler::SupportsUnboxedSimd128();
 }
@@ -414,6 +416,52 @@ void AotOptimizer::ReplaceCall(Definition* call,
 }
 
 
+void AotOptimizer::ReplaceCallWithSubgraph(Definition* call,
+                                           TargetEntryInstr* entry,
+                                           Definition* last) {
+  // We are splitting block A into a subgraph starting at A and ending at B.
+  // Give the original block id to B to maintain the order of phi inputs at its
+  // successors consistent with block ids.
+  BlockEntryInstr* a = call->GetBlock();
+  BlockEntryInstr* b = last->GetBlock();
+  intptr_t block_id_temp = a->block_id();
+  a->set_block_id(b->block_id());
+  b->set_block_id(block_id_temp);
+
+  // Remove the original push arguments.
+  for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
+    PushArgumentInstr* push = call->PushArgumentAt(i);
+    push->ReplaceUsesWith(push->value()->definition());
+    push->RemoveFromGraph();
+  }
+  // Replace all uses of this definition with the result.
+  if (call->HasUses()) {
+    call->ReplaceUsesWith(last);
+  }
+  // Finally insert the sequence other definition in place of this one in the
+  // graph.
+  if (entry->next() != NULL) {
+    call->previous()->LinkTo(entry->next());
+  }
+  entry->UnuseAllInputs();  // Entry block is not in the graph.
+  if (last != NULL) {
+    if (last->IsPhi()) {
+      last->AsPhi()->block()->LinkTo(call);
+    } else {
+      last->LinkTo(call);
+    }
+  }
+  call->RemoveFromGraph();
+  call->set_previous(NULL);
+  call->set_next(NULL);
+
+  // Discover new predecessors and recompute dominators.
+  flow_graph()->DiscoverBlocks();
+  GrowableArray<BitVector*> dominance_frontier;
+  flow_graph()->ComputeDominators(&dominance_frontier);
+}
+
+
 void AotOptimizer::AddCheckSmi(Definition* to_check,
                                intptr_t deopt_id,
                                Environment* deopt_environment,
@@ -1540,6 +1588,14 @@ void AotOptimizer::ReplaceWithInstanceOf(InstanceCallInstr* call) {
     return;
   }
 
+  TypeRangeCache* cache = thread()->type_range_cache();
+  intptr_t lower_limit, upper_limit;
+  if (cache != NULL &&
+      cache->InstanceOfHasClassRange(type, &lower_limit, &upper_limit)) {
+    ReplaceWithClassRangeCheck(call, left, negate, lower_limit, upper_limit);
+    return;
+  }
+
   const ICData& unary_checks =
       ICData::ZoneHandle(Z, call->ic_data()->AsUnaryClassChecks());
   if ((unary_checks.NumberOfChecks() > 0) &&
@@ -1576,6 +1632,119 @@ void AotOptimizer::ReplaceWithInstanceOf(InstanceCallInstr* call) {
 }
 
 
+void AotOptimizer::ReplaceWithClassRangeCheck(InstanceCallInstr* call,

[Florian Schneider, 2016/09/07 16:35:57]

I wonder if it would be easier to replace the call with another call to a
internal static top-level Dart function:

bool _classRangeCheck(int cid, int lower, int upper) {
  return cid >= lower && cid <= upper;
}

(or the negated version of it)

If you add this method to the always-inline list, the result after inlining
should be the same. The advantage would be that only straight-line code has to
be inserted into the graph (LoadClassId followed by StaticCall). What do you
think?

[rmacnak, 2016/09/07 22:21:27]

Yes, I like that better.

+                                              Definition* left,
+                                              bool negate,
+                                              intptr_t lower_limit,
+                                              intptr_t upper_limit) {
+  // left.instanceof(type) =>
+  // t = left.cid,
+  // t < lower_limit ? negate : (t > upper_limit ? negate, !negate)
+  TargetEntryInstr* entry =
+      new(Z) TargetEntryInstr(flow_graph()->allocate_block_id(),
+                              call->GetBlock()->try_index());
+  entry->InheritDeoptTarget(Z, call);
+  TargetEntryInstr* check_upper =
+      new(Z) TargetEntryInstr(flow_graph()->allocate_block_id(),
+                              call->GetBlock()->try_index());
+  check_upper->InheritDeoptTarget(Z, call);
+  TargetEntryInstr* too_low =
+      new(Z) TargetEntryInstr(flow_graph()->allocate_block_id(),
+                              call->GetBlock()->try_index());
+  too_low->InheritDeoptTarget(Z, call);
+  TargetEntryInstr* too_high =
+      new(Z) TargetEntryInstr(flow_graph()->allocate_block_id(),
+                              call->GetBlock()->try_index());
+  too_high->InheritDeoptTarget(Z, call);
+  TargetEntryInstr* match =
+      new(Z) TargetEntryInstr(flow_graph()->allocate_block_id(),
+                              call->GetBlock()->try_index());
+  match->InheritDeoptTarget(Z, call);
+  JoinEntryInstr* result =
+      new(Z) JoinEntryInstr(flow_graph()->allocate_block_id(),
+                            call->GetBlock()->try_index());
+  result->InheritDeoptTargetAfter(flow_graph(), call, NULL);
+
+  LoadClassIdInstr* left_cid = new(Z) LoadClassIdInstr(new(Z) Value(left));
+  ConstantInstr* lower_cid =
+      flow_graph()->GetConstant(Smi::Handle(Z, Smi::New(lower_limit)));
+  RelationalOpInstr* compare_lower =
+      new(Z) RelationalOpInstr(call->token_pos(),
+                               Token::kLT,
+                               new(Z) Value(left_cid),
+                               new(Z) Value(lower_cid),
+                               kSmiCid,
+                               call->deopt_id());
+  BranchInstr* branch_lower = new(Z) BranchInstr(compare_lower);
+  flow_graph()->AppendTo(entry,
+                         left_cid,
+                         call->env(),
+                         FlowGraph::kValue);
+  flow_graph()->AppendTo(left_cid,
+                         branch_lower,
+                         call->env(),
+                         FlowGraph::kEffect);
+
+  ConstantInstr* upper_cid =
+      flow_graph()->GetConstant(Smi::Handle(Z, Smi::New(upper_limit)));
+  RelationalOpInstr* compare_upper =
+      new(Z) RelationalOpInstr(call->token_pos(),
+                               Token::kGT,
+                               new(Z) Value(left_cid),
+                               new(Z) Value(upper_cid),
+                               kSmiCid,
+                               call->deopt_id());
+  BranchInstr* branch_upper = new(Z) BranchInstr(compare_upper);
+  flow_graph()->AppendTo(check_upper,
+                         branch_upper,
+                         call->env(),
+                         FlowGraph::kEffect);
+
+  *branch_lower->true_successor_address() = too_low;
+  *branch_lower->false_successor_address() = check_upper;
+
+  *branch_upper->true_successor_address() = too_high;
+  *branch_upper->false_successor_address() = match;
+
+  flow_graph()->AppendTo(too_low,
+                         new(Z) GotoInstr(result),
+                         call->env(),
+                         FlowGraph::kEffect);
+  flow_graph()->AppendTo(too_high,
+                         new(Z) GotoInstr(result),
+                         call->env(),
+                         FlowGraph::kEffect);
+  flow_graph()->AppendTo(match,
+                         new(Z) GotoInstr(result),
+                         call->env(),
+                         FlowGraph::kEffect);
+
+  PhiInstr* result_phi = new(Z) PhiInstr(result, 3);
+  flow_graph()->AllocateSSAIndexes(result_phi);
+  result_phi->mark_alive();
+
+  // Discovers predecessors for the 'result' block.
+  ReplaceCallWithSubgraph(call, entry, result_phi);
+
+  Value* v;
+  v = new(Z) Value(flow_graph()->GetConstant(Bool::Get(negate)));
+  v->definition()->AddInputUse(v);
+  result_phi->SetInputAt(result->IndexOfPredecessor(too_low), v);
+
+  v = new(Z) Value(flow_graph()->GetConstant(Bool::Get(negate)));
+  v->definition()->AddInputUse(v);
+  result_phi->SetInputAt(result->IndexOfPredecessor(too_high), v);
+
+  v = new(Z) Value(flow_graph()->GetConstant(Bool::Get(!negate)));
+  v->definition()->AddInputUse(v);
+  result_phi->SetInputAt(result->IndexOfPredecessor(match), v);
+
+  result->InsertPhi(result_phi);
+
+  flow_graph()->VerifyUseLists();
+}
+
+
 // TODO(srdjan): Apply optimizations as in ReplaceWithInstanceOf (TestCids).
 void AotOptimizer::ReplaceWithTypeCast(InstanceCallInstr* call) {
   ASSERT(Token::IsTypeCastOperator(call->token_kind()));
@@ -2138,5 +2307,6 @@ void AotOptimizer::ReplaceArrayBoundChecks() {
   }
 }
 
+#endif  // DART_PRECOMPILER
 
 }  // namespace dart