Allow dispatch to use a range of Class-ids in tests

runtime/vm/flow_graph_inliner.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.
 #if !defined(DART_PRECOMPILED_RUNTIME)
 #include "vm/flow_graph_inliner.h"
 
 #include "vm/aot_optimizer.h"
 #include "vm/precompiler.h"
 #include "vm/block_scheduler.h"
 #include "vm/branch_optimizer.h"
@@ skipping 456 matching lines @@
                      PolymorphicInstanceCallInstr* call,
                      const Function& caller_function,
                      intptr_t caller_inlining_id);
 
   void Inline();
 
  private:
   bool CheckInlinedDuplicate(const Function& target);
   bool CheckNonInlinedDuplicate(const Function& target);
 
-  bool TryInliningPoly(intptr_t receiver_cid, const Function& target);
+  bool TryInliningPoly(const CidRangeTarget& target);
   bool TryInlineRecognizedMethod(intptr_t receiver_cid, const Function& target);
 
   TargetEntryInstr* BuildDecisionGraph();
 
   Isolate* isolate() const;
   Zone* zone() const;
+  intptr_t AllocateBlockId() const;
+  inline bool trace_inlining() const;
 
   CallSiteInliner* const owner_;
   PolymorphicInstanceCallInstr* const call_;
   const intptr_t num_variants_;
-  GrowableArray<CidTarget> variants_;
+  GrowableArray<CidRangeTarget> variants_;
 
-  GrowableArray<CidTarget> inlined_variants_;
-  GrowableArray<CidTarget> non_inlined_variants_;
+  GrowableArray<CidRangeTarget> inlined_variants_;
+  GrowableArray<CidRangeTarget> non_inlined_variants_;
   GrowableArray<BlockEntryInstr*> inlined_entries_;
   InlineExitCollector* exit_collector_;
 
   const Function& caller_function_;
   const intptr_t caller_inlining_id_;
 };
 
 
 static bool HasAnnotation(const Function& function, const char* annotation) {
   const Class& owner = Class::Handle(function.Owner());
@@ skipping 136 matching lines @@
     } else {
       ParameterInstr* param = new (Z) ParameterInstr(i, graph->graph_entry());
       param->UpdateType(*argument->Type());
       return param;
     }
   }
 
   bool TryInlining(const Function& function,
                    const Array& argument_names,
                    InlinedCallData* call_data) {
-    TRACE_INLINING(THR_Print("  => %s (deopt count %d)\n", function.ToCString(),
-                             function.deoptimization_counter()));
+    if (trace_inlining()) {
+      String& name = String::Handle(function.QualifiedUserVisibleName());
+      THR_Print("  => %s (deopt count %d)\n", name.ToCString(),
+                function.deoptimization_counter());
+    }
 
     // Abort if the inlinable bit on the function is low.
     if (!function.CanBeInlined()) {
       TRACE_INLINING(THR_Print("     Bailout: not inlinable\n"));
       PRINT_INLINING_TREE("Not inlinable", &call_data->caller, &function,
                           call_data->call);
       return false;
     }
 
     // Don't inline any intrinsified functions in precompiled mode
@@ skipping 345 matching lines @@
         // caller's list of deferred prefixes.
         caller_graph()->AddToDeferredPrefixes(
             callee_graph->deferred_prefixes());
 
         FlowGraphInliner::SetInliningId(
             callee_graph,
             inliner_->NextInlineId(callee_graph->function(),
                                    call_data->call->token_pos(),
                                    call_data->caller_inlining_id_));
         TRACE_INLINING(THR_Print("     Success\n"));
+        TRACE_INLINING(THR_Print("       with size %" Pd "\n",
+                                 function.optimized_instruction_count()));
         PRINT_INLINING_TREE(NULL, &call_data->caller, &function, call);
         return true;
       } else {
         error = thread()->sticky_error();
         thread()->clear_sticky_error();
 
         if (error.IsLanguageError() &&
             (LanguageError::Cast(error).kind() == Report::kBailout)) {
           if (error.raw() == Object::background_compilation_error().raw()) {
             // Fall through to exit the compilation, and retry it later.
@@ skipping 19 matching lines @@
     // later.
     ASSERT(FLAG_precompiled_mode || Compiler::IsBackgroundCompilation() ||
            error.IsUnhandledException());
     Thread::Current()->long_jump_base()->Jump(1, error);
     UNREACHABLE();
     return false;
   }
 
   void PrintInlinedInfo(const Function& top) {
     if (inlined_info_.length() > 0) {
-      THR_Print("Inlining into: '%s' growth: %f (%" Pd " -> %" Pd ")\n",
+      THR_Print("Inlining into: '%s'\n    growth: %f (%" Pd " -> %" Pd ")\n",
                 top.ToFullyQualifiedCString(), GrowthFactor(), initial_size_,
                 inlined_size_);
       PrintInlinedInfoFor(top, 1);
     }
   }
 
  private:
   friend class PolymorphicInliner;
 
   static bool Contains(const GrowableArray<intptr_t>& a, intptr_t deopt_id) {
@@ skipping 129 matching lines @@
 
   void InlineStaticCalls() {
     const GrowableArray<CallSites::StaticCallInfo>& call_info =
         inlining_call_sites_->static_calls();
     TRACE_INLINING(THR_Print("  Static Calls (%" Pd ")\n", call_info.length()));
     for (intptr_t call_idx = 0; call_idx < call_info.length(); ++call_idx) {
       StaticCallInstr* call = call_info[call_idx].call;
       const Function& target = call->function();
       if (!inliner_->AlwaysInline(target) &&
           (call_info[call_idx].ratio * 100) < FLAG_inlining_hotness) {
-        TRACE_INLINING(
-            THR_Print("  => %s (deopt count %d)\n     Bailout: cold %f\n",
-                      target.ToCString(), target.deoptimization_counter(),
-                      call_info[call_idx].ratio));
+        if (trace_inlining()) {
+          String& name = String::Handle(target.QualifiedUserVisibleName());
+          THR_Print("  => %s (deopt count %d)\n     Bailout: cold %f\n",
+                    name.ToCString(), target.deoptimization_counter(),
+                    call_info[call_idx].ratio);
+        }
         PRINT_INLINING_TREE("Too cold", &call_info[call_idx].caller(),
                             &call->function(), call);
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->PushArgumentAt(i)->value());
       }
       InlinedCallData call_data(
           call, &arguments, call_info[call_idx].caller(),
@@ skipping 63 matching lines @@
             call_info[call_idx].caller_graph->inlining_id();
         PolymorphicInliner inliner(this, call, cl, caller_inlining_id);
         inliner.Inline();
         continue;
       }
 
       const ICData& ic_data = call->ic_data();
       const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
       if (!inliner_->AlwaysInline(target) &&
           (call_info[call_idx].ratio * 100) < FLAG_inlining_hotness) {
-        TRACE_INLINING(
-            THR_Print("  => %s (deopt count %d)\n     Bailout: cold %f\n",
-                      target.ToCString(), target.deoptimization_counter(),
-                      call_info[call_idx].ratio));
+        if (trace_inlining()) {
+          String& name = String::Handle(target.QualifiedUserVisibleName());
+          THR_Print("  => %s (deopt count %d)\n     Bailout: cold %f\n",
+                    name.ToCString(), target.deoptimization_counter(),
+                    call_info[call_idx].ratio);
+        }
         PRINT_INLINING_TREE("Too cold", &call_info[call_idx].caller(), &target,
                             call);
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int arg_i = 0; arg_i < call->ArgumentCount(); ++arg_i) {
         arguments.Add(call->PushArgumentAt(arg_i)->value());
       }
       InlinedCallData call_data(
           call, &arguments, call_info[call_idx].caller(),
@@ skipping 132 matching lines @@
 Isolate* PolymorphicInliner::isolate() const {
   return owner_->caller_graph()->isolate();
 }
 
 
 Zone* PolymorphicInliner::zone() const {
   return owner_->caller_graph()->zone();
 }
 
 
+intptr_t PolymorphicInliner::AllocateBlockId() const {
+  return owner_->caller_graph()->allocate_block_id();
+}
+
+
 // Inlined bodies are shared if two different class ids have the same
 // inlined target.  This sharing is represented by using three different
 // types of entries in the inlined_entries_ array:
 //
 //   * GraphEntry: the inlined body is not shared.
 //
 //   * TargetEntry: the inlined body is shared and this is the first variant.
 //
 //   * JoinEntry: the inlined body is shared and this is a subsequent variant.
 bool PolymorphicInliner::CheckInlinedDuplicate(const Function& target) {
@@ skipping 16 matching lines @@
 
         JoinEntryInstr* new_join =
             BranchSimplifier::ToJoinEntry(zone(), old_target);
         old_target->ReplaceAsPredecessorWith(new_join);
         for (intptr_t j = 0; j < old_target->dominated_blocks().length(); ++j) {
           BlockEntryInstr* block = old_target->dominated_blocks()[j];
           new_join->AddDominatedBlock(block);
         }
         // Create a new target with the join as unconditional successor.
         TargetEntryInstr* new_target =
-            new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(),
-                                 old_target->try_index());
+            new TargetEntryInstr(AllocateBlockId(), old_target->try_index());
         new_target->InheritDeoptTarget(zone(), new_join);
         GotoInstr* new_goto = new (Z) GotoInstr(new_join);
         new_goto->InheritDeoptTarget(zone(), new_join);
         new_target->LinkTo(new_goto);
         new_target->set_last_instruction(new_goto);
         new_join->predecessors_.Add(new_target);
 
         // Record the new target for the first variant.
         inlined_entries_[i] = new_target;
       }
@@ skipping 15 matching lines @@
   for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) {
     if (target.raw() == non_inlined_variants_[i].target->raw()) {
       return true;
     }
   }
 
   return false;
 }
 
 
-bool PolymorphicInliner::TryInliningPoly(intptr_t receiver_cid,
-                                         const Function& target) {
+bool PolymorphicInliner::TryInliningPoly(const CidRangeTarget& range) {
   if ((!FLAG_precompiled_mode ||
        owner_->inliner_->use_speculative_inlining()) &&
-      TryInlineRecognizedMethod(receiver_cid, target)) {
+      range.cid_start == range.cid_end &&

[Vyacheslav Egorov (Google), 2017/03/13 11:59:10]

Maybe CidRangeTarget needs a helper method

range.is_singularity()

or something like that.

+      TryInlineRecognizedMethod(range.cid_start, *range.target)) {
     owner_->inlined_ = true;
     return true;
   }
 
   GrowableArray<Value*> arguments(call_->ArgumentCount());
   for (int i = 0; i < call_->ArgumentCount(); ++i) {
     arguments.Add(call_->PushArgumentAt(i)->value());
   }
   InlinedCallData call_data(call_, &arguments, caller_function_,
                             caller_inlining_id_);
-  if (!owner_->TryInlining(target, call_->instance_call()->argument_names(),
+  if (!owner_->TryInlining(*range.target,
+                           call_->instance_call()->argument_names(),
                            &call_data)) {
     return false;
   }
 
   FlowGraph* callee_graph = call_data.callee_graph;
   call_data.exit_collector->PrepareGraphs(callee_graph);
   inlined_entries_.Add(callee_graph->graph_entry());
   exit_collector_->Union(call_data.exit_collector);
 
   // Replace parameter stubs and constants.  Replace the receiver argument
   // with a redefinition to prevent code from the inlined body from being
   // hoisted above the inlined entry.
   ASSERT(arguments.length() > 0);
   Value* actual = arguments[0];
   RedefinitionInstr* redefinition = new (Z) RedefinitionInstr(actual->Copy(Z));
   redefinition->set_ssa_temp_index(
       owner_->caller_graph()->alloc_ssa_temp_index());
-  redefinition->UpdateType(CompileType::FromCid(receiver_cid));
+  if (range.cid_start == range.cid_end) {
+    redefinition->UpdateType(CompileType::FromCid(range.cid_start));
+  }
   redefinition->InsertAfter(callee_graph->graph_entry()->normal_entry());
   Definition* stub = (*call_data.parameter_stubs)[0];
   stub->ReplaceUsesWith(redefinition);
 
   for (intptr_t i = 1; i < arguments.length(); ++i) {
     actual = arguments[i];
     if (actual != NULL) {
       stub = (*call_data.parameter_stubs)[i];
       stub->ReplaceUsesWith(actual->definition());
     }
@@ skipping 76 matching lines @@
 }
 
 
 // Build a DAG to dispatch to the inlined function bodies.  Load the class
 // id of the receiver and make explicit comparisons for each inlined body,
 // in frequency order.  If all variants are inlined, the entry to the last
 // inlined body is guarded by a CheckClassId instruction which can deopt.
 // If not all variants are inlined, we add a PolymorphicInstanceCall
 // instruction to handle the non-inlined variants.
 TargetEntryInstr* PolymorphicInliner::BuildDecisionGraph() {
+  const intptr_t try_idx = call_->GetBlock()->try_index();
+
   // Start with a fresh target entry.
   TargetEntryInstr* entry =
-      new (Z) TargetEntryInstr(owner_->caller_graph()->allocate_block_id(),
-                               call_->GetBlock()->try_index());
+      new (Z) TargetEntryInstr(AllocateBlockId(), try_idx);
   entry->InheritDeoptTarget(zone(), call_);
 
   // This function uses a cursor (a pointer to the 'current' instruction) to
   // build the graph.  The next instruction will be inserted after the
   // cursor.
-  TargetEntryInstr* current_block = entry;
+  BlockEntryInstr* current_block = entry;
   Instruction* cursor = entry;
 
   Definition* receiver = call_->ArgumentAt(0);
   // There are at least two variants including non-inlined ones, so we have
   // at least one branch on the class id.
   LoadClassIdInstr* load_cid =
       new (Z) LoadClassIdInstr(new (Z) Value(receiver));
   load_cid->set_ssa_temp_index(owner_->caller_graph()->alloc_ssa_temp_index());
   cursor = AppendInstruction(cursor, load_cid);
+  bool follow_with_deopt = false;
   for (intptr_t i = 0; i < inlined_variants_.length(); ++i) {
-    // 1. Guard the body with a class id check.
-    if ((i == (inlined_variants_.length() - 1)) &&
+    const CidRangeTarget& variant = inlined_variants_[i];
+    bool test_is_range = (variant.cid_start != variant.cid_end);

[Vyacheslav Egorov (Google), 2017/03/13 11:59:10]

try to make more variable cost - this helps readability of such gigantic
functions.

+    bool is_last_test = (i == inlined_variants_.length() - 1);
+    // 1. Guard the body with a class id check.  We don't need any check if
+    // it's the last test and global analysis has told us that the call is
+    // complete.  TODO(erikcorry): Enhance CheckClassIdInstr so it can take an
+    // arbitrary CidRangeTarget.  Currently we don't go into this branch if the
+    // last test is a range test - instead we set the follow_with_deopt flag.
+    if (is_last_test && (!test_is_range || call_->complete()) &&
         non_inlined_variants_.is_empty()) {
       // If it is the last variant use a check class id instruction which can
       // deoptimize, followed unconditionally by the body. Omit the check if
       // we know that we have covered all possible classes.
       if (!call_->complete()) {
+        ASSERT(!test_is_range);  // See condition above.
         RedefinitionInstr* cid_redefinition =
             new RedefinitionInstr(new (Z) Value(load_cid));
         cid_redefinition->set_ssa_temp_index(
             owner_->caller_graph()->alloc_ssa_temp_index());
         cursor = AppendInstruction(cursor, cid_redefinition);
-        CheckClassIdInstr* check_class_id = new (Z)
-            CheckClassIdInstr(new (Z) Value(cid_redefinition),
-                              inlined_variants_[i].cid, call_->deopt_id());
+        CheckClassIdInstr* check_class_id =
+            new (Z) CheckClassIdInstr(new (Z) Value(cid_redefinition),
+                                      variant.cid_start, call_->deopt_id());
         check_class_id->InheritDeoptTarget(zone(), call_);
         cursor = AppendInstruction(cursor, check_class_id);
       }
 
       // The next instruction is the first instruction of the inlined body.
       // Handle the two possible cases (unshared and shared subsequent
       // predecessors) separately.
       BlockEntryInstr* callee_entry = inlined_entries_[i];
       if (callee_entry->IsGraphEntry()) {
         // Unshared.  Graft the normal entry on after the check class
@@ skipping 21 matching lines @@
         goto_join->InheritDeoptTarget(zone(), join);
         cursor->LinkTo(goto_join);
         current_block->set_last_instruction(goto_join);
       } else {
         // There is no possibility of a TargetEntry (the first entry to a
         // shared inlined body) because this is the last inlined entry.
         UNREACHABLE();
       }
       cursor = NULL;
     } else {
+      if (is_last_test && test_is_range) follow_with_deopt = true;
       // For all variants except the last, use a branch on the loaded class
       // id.
-      const Smi& cid = Smi::ZoneHandle(Smi::New(inlined_variants_[i].cid));
-      ConstantInstr* cid_constant = new ConstantInstr(cid);
-      cid_constant->set_ssa_temp_index(
-          owner_->caller_graph()->alloc_ssa_temp_index());
-      StrictCompareInstr* compare = new StrictCompareInstr(
-          call_->instance_call()->token_pos(), Token::kEQ_STRICT,
-          new Value(load_cid), new Value(cid_constant),
-          false);  // No number check.
-      BranchInstr* branch = new BranchInstr(compare);
+      const Smi& cid = Smi::ZoneHandle(Smi::New(variant.cid_start));
+      ConstantInstr* cid_constant = owner_->caller_graph()->GetConstant(cid);
+      BranchInstr* branch;
+      BranchInstr* upper_limit_branch = NULL;
+      BlockEntryInstr* cid_test_entry_block = current_block;
+      if (test_is_range) {
+        // Double branch for testing a range of Cids.  TODO(erikcorry): Make a
+        // special instruction that uses subtraction and unsigned comparison to
+        // do this with a single branch.
+        const Smi& cid_end = Smi::ZoneHandle(Smi::New(variant.cid_end));
+        ConstantInstr* cid_constant_end =
+            owner_->caller_graph()->GetConstant(cid_end);
+        RelationalOpInstr* compare_top = new RelationalOpInstr(

[Florian Schneider, 2017/03/16 20:31:40]

dbc: Have you tried using _classRangeCheck from internal_patch.dart? We use it
for cid-range checks in the AOT compiler.

v <- classRangeCheck(cid, lower, upper)
Branch if StrictCompare (v == true)

And then rely on the next round of inlining to inline the range check.

+            call_->instance_call()->token_pos(), Token::kLTE,
+            new Value(load_cid), new Value(cid_constant_end), kSmiCid,
+            call_->deopt_id());
+        BranchInstr* branch_top = upper_limit_branch =
+            new BranchInstr(compare_top);
+        branch_top->InheritDeoptTarget(zone(), call_);
+        cursor = AppendInstruction(cursor, branch_top);
+        current_block->set_last_instruction(branch_top);
+
+        TargetEntryInstr* below_target =
+            new TargetEntryInstr(AllocateBlockId(), try_idx);
+        below_target->InheritDeoptTarget(zone(), call_);
+        current_block->AddDominatedBlock(below_target);
+        cursor = current_block = below_target;
+        *branch_top->true_successor_address() = below_target;
+
+        RelationalOpInstr* compare_bottom = new RelationalOpInstr(
+            call_->instance_call()->token_pos(), Token::kGTE,
+            new Value(load_cid), new Value(cid_constant), kSmiCid,
+            call_->deopt_id());
+        branch = new BranchInstr(compare_bottom);
+      } else {
+        StrictCompareInstr* compare = new StrictCompareInstr(
+            call_->instance_call()->token_pos(), Token::kEQ_STRICT,
+            new Value(load_cid), new Value(cid_constant),
+            false);  // No number check.
+        branch = new BranchInstr(compare);
+      }
+
       branch->InheritDeoptTarget(zone(), call_);
-      AppendInstruction(AppendInstruction(cursor, cid_constant), branch);
+      cursor = AppendInstruction(cursor, branch);
       current_block->set_last_instruction(branch);
       cursor = NULL;
 
       // 2. Handle a match by linking to the inlined body.  There are three
       // cases (unshared, shared first predecessor, and shared subsequent
       // predecessors).
       BlockEntryInstr* callee_entry = inlined_entries_[i];
       TargetEntryInstr* true_target = NULL;
       if (callee_entry->IsGraphEntry()) {
         // Unshared.
         true_target = callee_entry->AsGraphEntry()->normal_entry();
         // Unuse all inputs of the graph entry. It is not in the graph anymore.
         callee_entry->UnuseAllInputs();
       } else if (callee_entry->IsTargetEntry()) {
         // Shared inlined body and this is the first entry.  We have already
         // constructed a join and this target jumps to it.
         true_target = callee_entry->AsTargetEntry();
         BlockEntryInstr* join = true_target->last_instruction()->SuccessorAt(0);
         current_block->AddDominatedBlock(join);
       } else {
         // Shared inlined body and this is a subsequent entry.  We have
         // already constructed a join.  We need a fresh target that jumps to
         // the join.
         JoinEntryInstr* join = callee_entry->AsJoinEntry();
         ASSERT(join != NULL);
         ASSERT(join->dominator() != NULL);
-        true_target =
-            new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(),
-                                 call_->GetBlock()->try_index());
+        true_target = new TargetEntryInstr(AllocateBlockId(), try_idx);
         true_target->InheritDeoptTarget(zone(), join);
         GotoInstr* goto_join = new GotoInstr(join);
         goto_join->InheritDeoptTarget(zone(), join);
         true_target->LinkTo(goto_join);
         true_target->set_last_instruction(goto_join);
       }
       *branch->true_successor_address() = true_target;
       current_block->AddDominatedBlock(true_target);
 
       // 3. Prepare to handle a match failure on the next iteration or the
       // fall-through code below for non-inlined variants.
+
       TargetEntryInstr* false_target =
-          new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(),
-                               call_->GetBlock()->try_index());
+          new TargetEntryInstr(AllocateBlockId(), try_idx);
       false_target->InheritDeoptTarget(zone(), call_);
       *branch->false_successor_address() = false_target;
-      current_block->AddDominatedBlock(false_target);
+      cid_test_entry_block->AddDominatedBlock(false_target);
+
       cursor = current_block = false_target;
+
+      if (test_is_range) {
+        // If we tested against a range of Cids there are two different tests
+        // that can go to the no-cid-match target.
+        JoinEntryInstr* join = new JoinEntryInstr(AllocateBlockId(), try_idx);
+        TargetEntryInstr* false_target2 =
+            new TargetEntryInstr(AllocateBlockId(), try_idx);
+        *upper_limit_branch->false_successor_address() = false_target2;
+        cid_test_entry_block->AddDominatedBlock(false_target2);
+        cid_test_entry_block->AddDominatedBlock(join);
+        GotoInstr* goto_1 = new GotoInstr(join);
+        GotoInstr* goto_2 = new GotoInstr(join);
+        false_target->LinkTo(goto_1);
+        false_target2->LinkTo(goto_2);
+        false_target->set_last_instruction(goto_1);
+        false_target2->set_last_instruction(goto_2);
+
+        join->InheritDeoptTarget(zone(), call_);
+        false_target2->InheritDeoptTarget(zone(), call_);
+        goto_1->InheritDeoptTarget(zone(), call_);
+        goto_2->InheritDeoptTarget(zone(), call_);
+
+        cursor = current_block = join;
+      }
     }
   }
 
   // Handle any non-inlined variants.
   if (!non_inlined_variants_.is_empty()) {
     // Move push arguments of the call.
     for (intptr_t i = 0; i < call_->ArgumentCount(); ++i) {
       PushArgumentInstr* push = call_->PushArgumentAt(i);
       push->ReplaceUsesWith(push->value()->definition());
       push->previous()->LinkTo(push->next());
       cursor->LinkTo(push);
       cursor = push;
     }
     const ICData& old_checks = call_->ic_data();
     const ICData& new_checks = ICData::ZoneHandle(ICData::New(
         Function::Handle(old_checks.Owner()),
         String::Handle(old_checks.target_name()),
         Array::Handle(old_checks.arguments_descriptor()), old_checks.deopt_id(),
         1,        // Number of args tested.
         false));  // is_static_call
     for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) {
-      new_checks.AddReceiverCheck(non_inlined_variants_[i].cid,
-                                  *non_inlined_variants_[i].target,
-                                  non_inlined_variants_[i].count);
+      // We are adding all the cids in each range. They will be joined
+      // together again by the PolymorphicInstanceCall instruction, which is a
+      // bit messy.
+      intptr_t count = non_inlined_variants_[i].count;
+
+      for (intptr_t j = non_inlined_variants_[i].cid_start;
+           j <= non_inlined_variants_[i].cid_end; j++) {
+        new_checks.AddReceiverCheck(j, *non_inlined_variants_[i].target, count);
+        count = 0;
+      }
     }
     PolymorphicInstanceCallInstr* fallback_call =
         new PolymorphicInstanceCallInstr(call_->instance_call(), new_checks,
                                          /* with_checks = */ true,
                                          call_->complete());
     fallback_call->set_ssa_temp_index(
         owner_->caller_graph()->alloc_ssa_temp_index());
     fallback_call->InheritDeoptTarget(zone(), call_);
+    fallback_call->set_total_call_count(call_->CallCount());
     ReturnInstr* fallback_return = new ReturnInstr(
         call_->instance_call()->token_pos(), new Value(fallback_call));
     fallback_return->InheritDeoptTargetAfter(owner_->caller_graph(), call_,
                                              fallback_call);
     AppendInstruction(AppendInstruction(cursor, fallback_call),
                       fallback_return);
     exit_collector_->AddExit(fallback_return);
     cursor = NULL;
   } else {
+    if (follow_with_deopt) {
+      DeoptimizeInstr* deopt = new DeoptimizeInstr(
+          ICData::kDeoptPolymorphicInstanceCallTestFail, call_->deopt_id());
+      deopt->InheritDeoptTarget(zone(), call_);
+      cursor = AppendInstruction(cursor, deopt);
+      cursor = NULL;
+    }
+
     // Remove push arguments of the call.
     for (intptr_t i = 0; i < call_->ArgumentCount(); ++i) {
       PushArgumentInstr* push = call_->PushArgumentAt(i);
       push->ReplaceUsesWith(push->value()->definition());
       push->RemoveFromGraph();
     }
   }
   return entry;
 }
 
 
+static void TracePolyInlining(const CidRangeTarget& crt,
+                              intptr_t total,
+                              const char* message) {
+  String& name = String::Handle(crt.target->QualifiedUserVisibleName());
+  int percent = total == 0 ? 0 : (100 * crt.count) / total;
+  THR_Print("%s cid %" Pd "-%" Pd ": %" Pd "/%" Pd " %d%% %s\n",
+            name.ToCString(), crt.cid_start, crt.cid_end, crt.count, total,
+            percent, message);
+}
+
+
+bool PolymorphicInliner::trace_inlining() const {
+  return owner_->trace_inlining();
+}
+
+
 void PolymorphicInliner::Inline() {
   // Consider the polymorphic variants in order by frequency.
   FlowGraphCompiler::SortICDataByCount(call_->ic_data(), &variants_,
                                        /* drop_smi = */ false);
+  intptr_t total = call_->total_call_count();
   for (intptr_t var_idx = 0; var_idx < variants_.length(); ++var_idx) {
+    // We we almost inlined all the cases then try a little harder to inline
+    // the last two, because it's a big win if we inline all of them (compiler
+    // can see all side effects).
+    bool try_harder = (var_idx >= variants_.length() - 2) &&
+                      non_inlined_variants_.length() == 0;
     const Function& target = *variants_[var_idx].target;
-    const intptr_t receiver_cid = variants_[var_idx].cid;
+    const intptr_t count = variants_[var_idx].count;
+
+    intptr_t size = target.optimized_instruction_count();
+    bool small = (size != 0 && size < FLAG_inlining_size_threshold);
+
+    // If it's less than 3% of the dispatches, we won't even consider
+    // checking for the class ID and branching to another already-inlined
+    // version.
+    if (!try_harder && count < (total >> 5)) {
+      TRACE_INLINING(
+          TracePolyInlining(variants_[var_idx], total, "way too infrequent"));
+      non_inlined_variants_.Add(variants_[var_idx]);
+      continue;
+    }
 
     // First check if this is the same target as an earlier inlined variant.
     if (CheckInlinedDuplicate(target)) {
+      TRACE_INLINING(TracePolyInlining(variants_[var_idx], total,
+                                       "duplicate already inlined"));
       inlined_variants_.Add(variants_[var_idx]);
       continue;
     }
 
+    // If it's less than 12% of the dispatches and it's not already inlined, we
+    // don't consider inlining.  For very small functions we are willing to
+    // consider inlining for 6% of the cases.
+    if (!try_harder && count < (total >> (small ? 4 : 3))) {
+      TRACE_INLINING(
+          TracePolyInlining(variants_[var_idx], total, "too infrequent"));
+      non_inlined_variants_.Add(variants_[var_idx]);
+      continue;
+    }
+
     // Also check if this is the same target as an earlier non-inlined
     // variant.  If so and since inlining decisions are costly, do not try
     // to inline this variant.
     if (CheckNonInlinedDuplicate(target)) {
+      TRACE_INLINING(
+          TracePolyInlining(variants_[var_idx], total, "already not inlined"));
       non_inlined_variants_.Add(variants_[var_idx]);
       continue;
     }
 
     // Make an inlining decision.
-    if (TryInliningPoly(receiver_cid, target)) {
+    if (TryInliningPoly(variants_[var_idx])) {
+      TRACE_INLINING(TracePolyInlining(variants_[var_idx], total, "inlined"));
       inlined_variants_.Add(variants_[var_idx]);
     } else {
+      TRACE_INLINING(
+          TracePolyInlining(variants_[var_idx], total, "not inlined"));
       non_inlined_variants_.Add(variants_[var_idx]);
     }
   }
 
   // If there are no inlined variants, leave the call in place.
   if (inlined_variants_.is_empty()) return;
 
   // Now build a decision tree (a DAG because of shared inline variants) and
   // inline it at the call site.
   TargetEntryInstr* entry = BuildDecisionGraph();
@@ skipping 110 matching lines @@
   // Collect graph info and store it on the function.
   // We might later use it for an early bailout from the inlining.
   CollectGraphInfo(flow_graph_);
 
   const Function& top = flow_graph_->function();
   if ((FLAG_inlining_filter != NULL) &&
       (strstr(top.ToFullyQualifiedCString(), FLAG_inlining_filter) == NULL)) {
     return;
   }
 
-  TRACE_INLINING(THR_Print("Inlining calls in %s\n", top.ToCString()));
+  if (trace_inlining()) {
+    String& name = String::Handle(top.QualifiedUserVisibleName());
+    THR_Print("Inlining calls in %s\n", name.ToCString());
+  }
 
   if (FLAG_support_il_printer && trace_inlining() &&
       (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) {
     THR_Print("Before Inlining of %s\n",
               flow_graph_->function().ToFullyQualifiedCString());
     FlowGraphPrinter printer(*flow_graph_);
     printer.PrintBlocks();
   }
 
   intptr_t inlining_depth_threshold = FLAG_inlining_depth_threshold;
@@ skipping 735 matching lines @@
   *entry = new (Z) TargetEntryInstr(flow_graph->allocate_block_id(),
                                     call->GetBlock()->try_index());
   (*entry)->InheritDeoptTarget(Z, call);
 
   *last = PrepareInlineStringIndexOp(flow_graph, call, cid, str, index, *entry);
 
   return true;
 }
 
 
+// Only used for monomorphic calls.
 bool FlowGraphInliner::TryReplaceInstanceCallWithInline(
     FlowGraph* flow_graph,
     ForwardInstructionIterator* iterator,
     InstanceCallInstr* call) {
   Function& target = Function::Handle(Z);
   GrowableArray<intptr_t> class_ids;
   call->ic_data()->GetCheckAt(0, &class_ids, &target);
   const intptr_t receiver_cid = class_ids[0];
 
   TargetEntryInstr* entry;
@@ skipping 897 matching lines @@
     }
 
     default:
       return false;
   }
 }
 
 
 }  // namespace dart
 #endif  // !defined(DART_PRECOMPILED_RUNTIME)