Cache parsed functions when inlining.

runtime/vm/flow_graph_inliner.cc

Index: runtime/vm/flow_graph_inliner.cc
diff --git a/runtime/vm/flow_graph_inliner.cc b/runtime/vm/flow_graph_inliner.cc
index 134184ef147bfcff5591de2a7ed0ffd992aa99f1..b82aade65b17c03fe184010f724c7086054a00e9 100644
--- a/runtime/vm/flow_graph_inliner.cc
+++ b/runtime/vm/flow_graph_inliner.cc
@@ -46,6 +46,90 @@ static bool IsCallRecursive(const Function& function, Definition* call) {
   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 {
@@ -123,7 +207,8 @@ class CallSiteInliner : public ValueObject {
         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.
@@ -220,8 +305,7 @@ class CallSiteInliner : public ValueObject {
     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()) {
@@ -257,7 +341,7 @@ class CallSiteInliner : public ValueObject {
 
       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();
       }
@@ -308,6 +392,9 @@ class CallSiteInliner : public ValueObject {
 
       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());
 
@@ -330,6 +417,21 @@ class CallSiteInliner : public ValueObject {
     }
   }
 
+  // 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();
@@ -376,9 +478,11 @@ class CallSiteInliner : public ValueObject {
       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());
@@ -397,6 +501,7 @@ class CallSiteInliner : public ValueObject {
   intptr_t inlining_depth_;
   CallSites* collected_call_sites_;
   CallSites* inlining_call_sites_;
+  GrowableArray<CachedFunction*> function_cache;
 
   DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
 };