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

runtime/vm/aot_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/aot_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/branch_optimizer.h"
 #include "vm/cha.h"
 #include "vm/compiler.h"
@@ skipping 396 matching lines @@
   // 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();
   }
   call->ReplaceWith(replacement, current_iterator());
 }
 
 
+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,
                                Instruction* insert_before) {
   if (to_check->Type()->ToCid() != kSmiCid) {
     InsertBefore(insert_before,
                  new(Z) CheckSmiInstr(new(Z) Value(to_check),
                                       deopt_id,
                                       insert_before->token_pos()),
                  deopt_environment,
@@ skipping 1106 matching lines @@
         new(Z) StrictCompareInstr(
             call->token_pos(),
             negate ? Token::kNE_STRICT : Token::kEQ_STRICT,
             new(Z) Value(left_cid),
             new(Z) Value(cid),
             false);  // No number check.
     ReplaceCall(call, check_cid);
     return;
   }
 
+#ifdef DART_PRECOMPILER
+  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;
+  }
+#endif  // DART_PRECOMPILER
+
   const ICData& unary_checks =
       ICData::ZoneHandle(Z, call->ic_data()->AsUnaryClassChecks());
   if ((unary_checks.NumberOfChecks() > 0) &&
       (unary_checks.NumberOfChecks() <= FLAG_max_polymorphic_checks)) {
     ZoneGrowableArray<intptr_t>* results =
         new(Z) ZoneGrowableArray<intptr_t>(unary_checks.NumberOfChecks() * 2);
     InstanceOfAsBool(unary_checks, type, results);
     if (results->length() == unary_checks.NumberOfChecks() * 2) {
       const bool can_deopt = TryExpandTestCidsResult(results, type);
       if (can_deopt && !IsAllowedForInlining(call->deopt_id())) {
@@ skipping 16 matching lines @@
       new(Z) InstanceOfInstr(call->token_pos(),
                              new(Z) Value(left),
                              new(Z) Value(type_args),
                              type,
                              negate,
                              call->deopt_id());
   ReplaceCall(call, instance_of);
 }
 
 
+void AotOptimizer::ReplaceWithClassRangeCheck(InstanceCallInstr* call,
+                                              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()));
   Definition* left = call->ArgumentAt(0);
   Definition* type_args = call->ArgumentAt(1);
   const AbstractType& type =
       AbstractType::Cast(call->ArgumentAt(2)->AsConstant()->value());
   ASSERT(!type.IsMalformedOrMalbounded());
   const ICData& unary_checks =
       ICData::ZoneHandle(Z, call->ic_data()->AsUnaryClassChecks());
@@ skipping 544 matching lines @@
         flow_graph_->InsertBefore(check, new_check,
                                   check->env(), FlowGraph::kEffect);
         current_iterator()->RemoveCurrentFromGraph();
       }
     }
   }
 }
 
 
 }  // namespace dart