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;
 }
 
+// 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()); }

[Kevin Millikin (Google), 2012/10/22 13:56:29]

I guess these Visit functions should all be virtual.

+  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;
+  }
+};
 
 // 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 75 matching lines @@
     isolate->set_ic_data_array(Array::null());
     // 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;
+      ParsedFunction* parsed_function = ParseFunction(function, &in_cache);
 
       // 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);
+      FlowGraphBuilder builder(*parsed_function);
       builder.SetInitialBlockId(caller_graph_->max_block_id());
       FlowGraph* callee_graph =
           builder.BuildGraph(FlowGraphBuilder::kValueContext);
 
       // Abort if the callee graph contains control flow.
       if (!FLAG_inline_control_flow &&
           (callee_graph->preorder().length() != 2)) {
         function.set_is_inlinable(false);
         isolate->set_long_jump_base(base);
         isolate->set_ic_data_array(prev_ic_data.raw());
         TRACE_INLINING(OS::Print("     Bailout: control flow\n"));
         return false;
       }
 
       // Compute SSA on the callee graph, catching bailouts.
       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(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.
+  ParsedFunction* ParseFunction(const Function& function, bool* in_cache) {
+    // TODO(zerny): Use a hash map for the cache.
+    for (intptr_t i = 0; i < function_cache.length(); ++i) {
+      ParsedFunction* parsed_function = function_cache[i];
+      if (parsed_function->function().raw() == function.raw()) {
+        *in_cache = true;
+        SourceLabelResetter reset;
+        parsed_function->node_sequence()->Visit(&reset);
+        return parsed_function;
+      }
+    }
+    *in_cache = false;
+    ParsedFunction* parsed_function = new ParsedFunction(function);
+    Parser::ParseFunction(parsed_function);
+    parsed_function->AllocateVariables();
+    return parsed_function;
+  }
+
   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<ParsedFunction*> 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