Cache parsed functions when inlining.

runtime/vm/flow_graph_inliner.cc

 // Copyright (c) 2012, 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/flow_graph_inliner.h"
 
 #include "vm/compiler.h"
 #include "vm/flags.h"
 #include "vm/flow_graph.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 28 matching lines @@
 // Test if a call is recursive by looking in the deoptimization environment.
 static bool IsCallRecursive(const Function& function, Definition* call) {
   Environment* env = call->env();
   while (env != NULL) {
     if (function.raw() == env->function().raw()) return true;
     env = env->outer();
   }
   return false;
 }
 
+// Cached function structure to reuse parsed ASTs for multiple inlining sites.
+class CachedFunction : public ZoneAllocated {

[Kevin Millikin (Google), 2012/10/22 10:52:16]

This seems unnecessary.  Couldn't we just make ParsedFunction be ZoneAllocated?

+ public:
+  explicit CachedFunction(const ParsedFunction& parsed_function)
+      : function_(Function::ZoneHandle(parsed_function.function().raw())),
+        node_sequence_(parsed_function.node_sequence()),
+        instantiator_(parsed_function.instantiator()),
+        default_parameter_values_(Array::ZoneHandle(
+            parsed_function.default_parameter_values().raw())),
+        expression_temp_var_(parsed_function.has_expression_temp_var()
+                             ? parsed_function.expression_temp_var()
+                             : NULL),
+        first_parameter_index_(parsed_function.first_parameter_index()),
+        first_stack_local_index_(parsed_function.first_stack_local_index()),
+        num_copied_params_(parsed_function.num_copied_params()),
+        num_stack_locals_(parsed_function.num_stack_locals()) { }
+
+  void ParseFunction(ParsedFunction* parsed_function) {
+    ASSERT(parsed_function->function().raw() == function_.raw());
+    parsed_function->SetNodeSequence(node_sequence_);
+    parsed_function->set_instantiator(instantiator_);
+    parsed_function->set_default_parameter_values(default_parameter_values_);
+    if (expression_temp_var_ != NULL) {
+      parsed_function->set_expression_temp_var(expression_temp_var_);
+    }
+    parsed_function->first_parameter_index_ = first_parameter_index_;
+    parsed_function->first_stack_local_index_ = first_stack_local_index_;
+    parsed_function->num_copied_params_ = num_copied_params_;
+    parsed_function->num_stack_locals_ = num_stack_locals_;
+    // Reset all source labels to null.
+    SourceLabelResetter reset;
+    node_sequence_->Visit(&reset);
+  }
+
+  bool Equals(const Function& function) {
+    return function_.raw() == function.raw();
+  }
+
+ private:
+  // TODO(zerny): Remove the following classes once we have moved the label/join
+  // map for control flow out of the AST an into the flow graph builder.
+
+  // Default visitor to traverse child nodes.
+  class ChildrenVisitor : public AstNodeVisitor {
+   public:
+    ChildrenVisitor() { }
+#define DEFINE_VISIT(type, name)                                               \
+    virtual void Visit##type(type* node) { node->VisitChildren(this); }
+    NODE_LIST(DEFINE_VISIT);
+#undef DEFINE_VISIT
+  };
+
+  // Visitor to clear each AST node containing source labels.
+  class SourceLabelResetter : public ChildrenVisitor {
+   public:
+    SourceLabelResetter() { }
+    void VisitSequenceNode(SequenceNode* node) { Reset(node, node->label()); }
+    void VisitCaseNode(CaseNode* node) { Reset(node, node->label()); }
+    void VisitSwitchNode(SwitchNode* node) { Reset(node, node->label()); }
+    void VisitWhileNode(WhileNode* node) { Reset(node, node->label()); }
+    void VisitDoWhileNode(DoWhileNode* node) { Reset(node, node->label()); }
+    void VisitForNode(ForNode* node) { Reset(node, node->label()); }
+    void VisitJumpNode(JumpNode* node) { Reset(node, node->label()); }
+    void Reset(AstNode* node, SourceLabel* lbl) {
+      node->VisitChildren(this);
+      if (lbl == NULL) return;
+      lbl->join_for_break_ = NULL;
+      lbl->join_for_continue_ = NULL;
+    }
+  };
+
+  const Function& function_;
+  SequenceNode* node_sequence_;
+  AstNode* instantiator_;
+  Array& default_parameter_values_;
+  LocalVariable* saved_context_var_;
+  LocalVariable* expression_temp_var_;
+  int first_parameter_index_;
+  int first_stack_local_index_;
+  int num_copied_params_;
+  int num_stack_locals_;
+
+  DISALLOW_COPY_AND_ASSIGN(CachedFunction);
+};
 
 // A collection of call sites to consider for inlining.
 class CallSites : public FlowGraphVisitor {
  public:
   explicit CallSites(FlowGraph* flow_graph)
       : FlowGraphVisitor(flow_graph->postorder()),  // We don't use this order.
         static_calls_(),
         closure_calls_(),
         instance_calls_() { }
 
@@ skipping 57 matching lines @@
 class CallSiteInliner : public ValueObject {
  public:
   explicit CallSiteInliner(FlowGraph* flow_graph)
       : caller_graph_(flow_graph),
         next_ssa_temp_index_(flow_graph->max_virtual_register_number()),
         inlined_(false),
         initial_size_(flow_graph->InstructionCount()),
         inlined_size_(0),
         inlining_depth_(1),
         collected_call_sites_(NULL),
-        inlining_call_sites_(NULL) { }
+        inlining_call_sites_(NULL),
+        function_cache() { }
 
   void InlineCalls() {
     // If inlining depth is less then one abort.
     if (FLAG_inlining_depth_threshold < 1) return;
     // Create two call site collections to swap between.
     CallSites sites1(caller_graph_);
     CallSites sites2(caller_graph_);
     CallSites* call_sites_temp = NULL;
     collected_call_sites_ = &sites1;
     inlining_call_sites_ = &sites2;
@@ skipping 76 matching lines @@
     // Save and clear deopt id.
     const intptr_t prev_deopt_id = isolate->deopt_id();
     isolate->set_deopt_id(0);
     // Install bailout jump.
     LongJump* base = isolate->long_jump_base();
     LongJump jump;
     isolate->set_long_jump_base(&jump);
     if (setjmp(*jump.Set()) == 0) {
       // Parse the callee function.
       ParsedFunction parsed_function(function);
-      Parser::ParseFunction(&parsed_function);
-      parsed_function.AllocateVariables();
+      bool in_cache = ParseFunction(&parsed_function);
 
       // Load IC data for the callee.
       if (function.HasCode()) {
         const Code& unoptimized_code =
             Code::Handle(function.unoptimized_code());
         isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray());
       }
 
       // Build the callee graph.
       FlowGraphBuilder builder(parsed_function);
@@ skipping 15 matching lines @@
       callee_graph->ComputeSSA(next_ssa_temp_index_);
       callee_graph->ComputeUseLists();
 
       // TODO(zerny): Do more optimization passes on the callee graph.
       FlowGraphOptimizer optimizer(callee_graph);
       optimizer.ApplyICData();
       callee_graph->ComputeUseLists();
 
       if (FLAG_trace_inlining && FLAG_print_flow_graph) {
         OS::Print("Callee graph for inlining %s\n",
-                  parsed_function.function().ToFullyQualifiedCString());
+                  function.ToFullyQualifiedCString());
         FlowGraphPrinter printer(*callee_graph);
         printer.PrintBlocks();
       }
 
       // If result is more than size threshold then abort.
       // TODO(zerny): Do this after CP and dead code elimination.
       intptr_t size = callee_graph->InstructionCount();
       if (size > FLAG_inlining_size_threshold) {
         function.set_is_inlinable(false);
         isolate->set_long_jump_base(base);
@@ skipping 30 matching lines @@
         }
       }
       ASSERT(arg_index == arguments->length());
 
       // Replace callee's null constant with caller's null constant.
       callee_graph->graph_entry()->constant_null()->ReplaceUsesWith(
           caller_graph_->graph_entry()->constant_null());
 
       TRACE_INLINING(OS::Print("     Success\n"));
 
+      // Add the function to the cache.
+      if (!in_cache) function_cache.Add(new CachedFunction(parsed_function));
+
       // Check that inlining maintains use lists.
       DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists());
 
       // Build succeeded so we restore the bailout jump.
       inlined_ = true;
       inlined_size_ += size;
       isolate->set_long_jump_base(base);
       isolate->set_deopt_id(prev_deopt_id);
       isolate->set_ic_data_array(prev_ic_data.raw());
       return true;
     } else {
       Error& error = Error::Handle();
       error = isolate->object_store()->sticky_error();
       isolate->object_store()->clear_sticky_error();
       isolate->set_long_jump_base(base);
       isolate->set_deopt_id(prev_deopt_id);
       isolate->set_ic_data_array(prev_ic_data.raw());
       TRACE_INLINING(OS::Print("     Bailout: %s\n", error.ToErrorCString()));
       return false;
     }
   }
 
+  // Parse a function reusing the cache if possible. Returns true if the
+  // function was in the cache.
+  bool ParseFunction(ParsedFunction* parsed_function) {
+    // TODO(zerny): Use a hash map for the cache.
+    for (intptr_t i = 0; i < function_cache.length(); ++i) {
+      if (function_cache[i]->Equals(parsed_function->function())) {
+        function_cache[i]->ParseFunction(parsed_function);
+        return true;
+      }
+    }
+    Parser::ParseFunction(parsed_function);
+    parsed_function->AllocateVariables();
+    return false;
+  }
+
   void InlineStaticCalls() {
     const GrowableArray<StaticCallInstr*>& calls =
         *inlining_call_sites_->static_calls();
     TRACE_INLINING(OS::Print("  Static Calls (%d)\n", calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       StaticCallInstr* call = calls[i];
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->ArgumentAt(i)->value());
       }
@@ skipping 26 matching lines @@
   void InlineInstanceCalls() {
     const GrowableArray<PolymorphicInstanceCallInstr*>& calls =
         *inlining_call_sites_->instance_calls();
     TRACE_INLINING(OS::Print("  Polymorphic Instance Calls (%d)\n",
                              calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       PolymorphicInstanceCallInstr* instr = calls[i];
       const ICData& ic_data = instr->ic_data();
       const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
       if (instr->with_checks()) {
-        TRACE_INLINING(OS::Print("     Bailout: %"Pd" checks target '%s'\n",
-                                 ic_data.NumberOfChecks(),
-                                 target.ToCString()));
+        TRACE_INLINING(OS::Print(
+          "  => %s (deopt count %d)\n     Bailout: %"Pd" checks\n",
+          target.ToCString(),
+          target.deoptimization_counter(),
+          ic_data.NumberOfChecks()));
         continue;
       }
       GrowableArray<Value*> arguments(instr->ArgumentCount());
       for (int i = 0; i < instr->ArgumentCount(); ++i) {
         arguments.Add(instr->ArgumentAt(i)->value());
       }
       TryInlining(target, &arguments, instr);
     }
   }
 
   FlowGraph* caller_graph_;
   intptr_t next_ssa_temp_index_;
   bool inlined_;
   intptr_t initial_size_;
   intptr_t inlined_size_;
   intptr_t inlining_depth_;
   CallSites* collected_call_sites_;
   CallSites* inlining_call_sites_;
+  GrowableArray<CachedFunction*> function_cache;
 
   DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
 };
 
 
 void FlowGraphInliner::Inline() {
   if ((FLAG_inlining_filter != NULL) &&
       (strstr(flow_graph_->
               parsed_function().function().ToFullyQualifiedCString(),
               FLAG_inlining_filter) == NULL)) {
@@ skipping 21 matching lines @@
         OS::Print("After Inlining of %s\n", flow_graph_->
                   parsed_function().function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
 }
 
 }  // namespace dart