Reland "Use off-heap data for type feedback in PolymorphicInstanceCallInstr"

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 159 matching lines @@
           continue;
         }
         if (current->IsPolymorphicInstanceCall()) {
           PolymorphicInstanceCallInstr* call =
               current->AsPolymorphicInstanceCall();
           // These checks make sure that the number of call-sites counted does
           // not change relative to the time when the current set of inlining
           // parameters was fixed.
           // TODO(fschneider): Determine new heuristic parameters that avoid
           // these checks entirely.
-          if (!call->HasSingleRecognizedTarget() &&
+          if (!call->IsSureToCallSingleRecognizedTarget() &&
               (call->instance_call()->token_kind() != Token::kEQ)) {
             ++call_site_count_;
           }
         }
       }
     }
   }
 
   intptr_t call_site_count() const { return call_site_count_; }
   intptr_t instruction_count() const { return instruction_count_; }
@@ skipping 92 matching lines @@
                             intptr_t instance_call_start_ix) {
     const intptr_t num_static_calls =
         static_calls_.length() - static_call_start_ix;
     const intptr_t num_instance_calls =
         instance_calls_.length() - instance_call_start_ix;
 
     intptr_t max_count = 0;
     GrowableArray<intptr_t> instance_call_counts(num_instance_calls);
     for (intptr_t i = 0; i < num_instance_calls; ++i) {
       const intptr_t aggregate_count =
-          instance_calls_[i + instance_call_start_ix]
-              .call->ic_data()
-              .AggregateCount();
+          instance_calls_[i + instance_call_start_ix].call->CallCount();
       instance_call_counts.Add(aggregate_count);
       if (aggregate_count > max_count) max_count = aggregate_count;
     }
 
     GrowableArray<intptr_t> static_call_counts(num_static_calls);
     for (intptr_t i = 0; i < num_static_calls; ++i) {
       intptr_t aggregate_count = 0;
       if (static_calls_[i + static_call_start_ix].call->ic_data() == NULL) {
         aggregate_count = 0;
       } else {
@@ skipping 30 matching lines @@
     Function& target = Function::ZoneHandle();
     for (BlockIterator block_it = graph->postorder_iterator(); !block_it.Done();
          block_it.Advance()) {
       for (ForwardInstructionIterator it(block_it.Current()); !it.Done();
            it.Advance()) {
         Instruction* current = it.Current();
         Definition* call = NULL;
         if (current->IsPolymorphicInstanceCall()) {
           PolymorphicInstanceCallInstr* instance_call =
               current->AsPolymorphicInstanceCall();
-          target = instance_call->ic_data().GetTargetAt(0);
+          target ^= instance_call->targets().FirstTarget().raw();
           call = instance_call;
         } else if (current->IsStaticCall()) {
           StaticCallInstr* static_call = current->AsStaticCall();
-          target = static_call->function().raw();
+          target ^= static_call->function().raw();
           call = static_call;
         } else if (current->IsClosureCall()) {
           // TODO(srdjan): Add data for closure calls.
         }
         if (call != NULL) {
           inlined_info->Add(
               InlinedInfo(caller, &target, depth + 1, call, "Too deep"));
         }
       }
     }
@@ skipping 20 matching lines @@
     const intptr_t static_call_start_ix = static_calls_.length();
     for (BlockIterator block_it = graph->postorder_iterator(); !block_it.Done();
          block_it.Advance()) {
       for (ForwardInstructionIterator it(block_it.Current()); !it.Done();
            it.Advance()) {
         Instruction* current = it.Current();
         if (current->IsPolymorphicInstanceCall()) {
           PolymorphicInstanceCallInstr* instance_call =
               current->AsPolymorphicInstanceCall();
           if (!inline_only_recognized_methods ||
-              instance_call->HasSingleRecognizedTarget() ||
-              instance_call->ic_data()
-                  .HasOnlyDispatcherOrImplicitAccessorTargets()) {
+              instance_call->IsSureToCallSingleRecognizedTarget() ||
+              instance_call->HasOnlyDispatcherOrImplicitAccessorTargets()) {
             instance_calls_.Add(InstanceCallInfo(instance_call, graph));
           } else {
             // Method not inlined because inlining too deep and method
             // not recognized.
             if (FLAG_print_inlining_tree) {
               const Function* caller = &graph->function();
-              const Function* target = &Function::ZoneHandle(
-                  instance_call->ic_data().GetTargetAt(0));
+              const Function* target = &instance_call->targets().FirstTarget();
               inlined_info->Add(InlinedInfo(caller, target, depth + 1,
                                             instance_call, "Too deep"));
             }
           }
         } else if (current->IsStaticCall()) {
           StaticCallInstr* static_call = current->AsStaticCall();
           if (!inline_only_recognized_methods ||
               static_call->function().IsRecognized() ||
               static_call->function().IsDispatcherOrImplicitAccessor()) {
             static_calls_.Add(StaticCallInfo(static_call, graph));
@@ skipping 72 matching lines @@
   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<CidRangeTarget> variants_;
+  const CallTargets& variants_;
 
-  GrowableArray<CidRangeTarget> inlined_variants_;
-  GrowableArray<CidRangeTarget> non_inlined_variants_;
+  CallTargets inlined_variants_;
+  // The non_inlined_variants_ can be used in a long-lived instruction object,
+  // so they are not embedded into the shorter-lived PolymorphicInliner object.
+  CallTargets* 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 790 matching lines @@
           continue;
         }
         const Function& cl = call_info[call_idx].caller();
         intptr_t caller_inlining_id =
             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));
+      const Function& target = call->targets().MostPopularTarget();
       if (!inliner_->AlwaysInline(target) &&
           (call_info[call_idx].ratio * 100) < FLAG_inlining_hotness) {
         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);
@@ skipping 120 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
 };
 
 
 PolymorphicInliner::PolymorphicInliner(CallSiteInliner* owner,
                                        PolymorphicInstanceCallInstr* call,
                                        const Function& caller_function,
                                        intptr_t caller_inlining_id)
     : owner_(owner),
       call_(call),
-      num_variants_(call->ic_data().NumberOfChecks()),
-      variants_(num_variants_),
-      inlined_variants_(num_variants_),
-      non_inlined_variants_(num_variants_),
+      num_variants_(call->NumberOfChecks()),
+      variants_(call->targets_),
+      inlined_variants_(),
+      non_inlined_variants_(new (zone()) CallTargets()),
       inlined_entries_(num_variants_),
       exit_collector_(new (Z) InlineExitCollector(owner->caller_graph(), call)),
       caller_function_(caller_function),
       caller_inlining_id_(caller_inlining_id) {}
 
 
 Isolate* PolymorphicInliner::isolate() const {
   return owner_->caller_graph()->isolate();
 }
 
@@ skipping 63 matching lines @@
       inlined_entries_.Add(join);
       return true;
     }
   }
 
   return false;
 }
 
 
 bool PolymorphicInliner::CheckNonInlinedDuplicate(const Function& target) {
-  for (intptr_t i = 0; i < non_inlined_variants_.length(); ++i) {
-    if (target.raw() == non_inlined_variants_[i].target->raw()) {
+  for (intptr_t i = 0; i < non_inlined_variants_->length(); ++i) {
+    if (target.raw() == non_inlined_variants_->At(i).target->raw()) {
       return true;
     }
   }
 
   return false;
 }
 
 
 bool PolymorphicInliner::TryInliningPoly(const CidRangeTarget& range) {
   if ((!FLAG_precompiled_mode ||
        owner_->inliner_->use_speculative_inlining()) &&
       range.cid_start == range.cid_end &&
       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(*range.target,
-                           call_->instance_call()->argument_names(),
+  Function& target = Function::ZoneHandle(zone(), range.target->raw());
+  if (!owner_->TryInlining(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
@@ skipping 127 matching lines @@
   for (intptr_t i = 0; i < inlined_variants_.length(); ++i) {
     const CidRangeTarget& variant = inlined_variants_[i];
     bool test_is_range = (variant.cid_start != variant.cid_end);
     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()) {
+        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);
@@ skipping 155 matching lines @@
         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()) {
+  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) {
-      // 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());
+        new PolymorphicInstanceCallInstr(
+            call_->instance_call(), *non_inlined_variants_,
+            /* 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);
@@ skipping 29 matching lines @@
             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);
+  ASSERT(&variants_ == &call_->targets_);
+
   intptr_t total = call_->total_call_count();
   for (intptr_t var_idx = 0; var_idx < variants_.length(); ++var_idx) {
     if (variants_.length() > FLAG_max_polymorphic_checks) {
-      non_inlined_variants_.Add(variants_[var_idx]);
+      non_inlined_variants_->Add(variants_[var_idx]);
       continue;
     }
 
     // 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).
     const bool try_harder = (var_idx >= variants_.length() - 2) &&
-                            non_inlined_variants_.length() == 0;
+                            non_inlined_variants_->length() == 0;
     const Function& target = *variants_[var_idx].target;
     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]);
+      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]);
+      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]);
+      non_inlined_variants_->Add(variants_[var_idx]);
       continue;
     }
 
     // Make an inlining decision.
     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]);
+      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();
   exit_collector_->ReplaceCall(entry);
@@ skipping 1787 matching lines @@
     }
 
     default:
       return false;
   }
 }
 
 
 }  // namespace dart
 #endif  // !defined(DART_PRECOMPILED_RUNTIME)