Initial implementation of on-stack replacement (OSR).

runtime/vm/flow_graph_builder.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_builder.h"
 
 #include "lib/invocation_mirror.h"
 #include "vm/ast_printer.h"
+#include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
 #include "vm/flags.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/parser.h"
@@ skipping 17 matching lines @@
 
 static const String& PrivateCoreLibName(const String& str) {
   const Library& core_lib = Library::Handle(Library::CoreLibrary());
   const String& private_name = String::ZoneHandle(core_lib.PrivateName(str));
   return private_name;
 }
 
 
 FlowGraphBuilder::FlowGraphBuilder(ParsedFunction* parsed_function,
                                    const Array& ic_data_array,
-                                   InlineExitCollector* exit_collector)
+                                   InlineExitCollector* exit_collector,
+                                   intptr_t osr_id)
   : parsed_function_(parsed_function),
     ic_data_array_(ic_data_array),
     num_copied_params_(parsed_function->num_copied_params()),
     // All parameters are copied if any parameter is.
     num_non_copied_params_((num_copied_params_ == 0)
         ? parsed_function->function().num_fixed_parameters()
         : 0),
     num_stack_locals_(parsed_function->num_stack_locals()),
     exit_collector_(exit_collector),
     last_used_block_id_(0),  // 0 is used for the graph entry.
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
     graph_entry_(NULL),
-    args_pushed_(0) { }
+    args_pushed_(0),
+    osr_id_(osr_id) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(CatchBlockEntryInstr* entry) {
   graph_entry_->AddCatchEntry(entry);
 }
 
 
 void InlineExitCollector::PrepareGraphs(FlowGraph* callee_graph) {
   ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
   ASSERT(callee_graph->max_block_id() > caller_graph_->max_block_id());
@@ skipping 395 matching lines @@
         new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     true_exit->Goto(join);
     false_exit->Goto(join);
     exit_ = join;
     ASSERT(true_fragment.temp_index() == false_fragment.temp_index());
     temp_index_ = true_fragment.temp_index();
   }
 }
 
 
-void EffectGraphVisitor::TieLoop(const TestGraphVisitor& test_fragment,
+void EffectGraphVisitor::TieLoop(intptr_t token_pos,
+                                 const TestGraphVisitor& test_fragment,
                                  const EffectGraphVisitor& body_fragment) {
   // We have: a test graph fragment with zero, one, or two available exits;
   // and an effect graph fragment with zero or one available exits.  We want
   // to append the 'while loop' consisting of the test graph fragment as
   // condition and the effect graph fragment as body.
   ASSERT(is_open());
 
   // 1. Connect the body to the test if it is reachable, and if so record
   // its exit (if any).
   BlockEntryInstr* body_entry = test_fragment.CreateTrueSuccessor();
   Instruction* body_exit = AppendFragment(body_entry, body_fragment);
 
   // 2. Connect the test to this graph, including the body if reachable and
   // using a fresh join node if the body is reachable and has an open exit.
   if (body_exit == NULL) {
     Append(test_fragment);
   } else {
     JoinEntryInstr* join =
         new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
-    join->LinkTo(test_fragment.entry());
+    CheckStackOverflowInstr* check =
+        new CheckStackOverflowInstr(token_pos, true);
+    join->LinkTo(check);
+    check->LinkTo(test_fragment.entry());
     Goto(join);
     body_exit->Goto(join);
   }
 
   // 3. Set the exit to the graph to be the false successor of the test, a
   // fresh target node
-
   exit_ = test_fragment.CreateFalseSuccessor();
 }
 
 
 PushArgumentInstr* EffectGraphVisitor::PushArgument(Value* value) {
   owner_->add_args_pushed(1);
   PushArgumentInstr* result = new PushArgumentInstr(value);
   AddInstruction(result);
   return result;
 }
@@ skipping 1080 matching lines @@
 // f) loop-exit-target
 // g) break-join (optional)
 void EffectGraphVisitor::VisitWhileNode(WhileNode* node) {
   TestGraphVisitor for_test(owner(),
                             temp_index(),
                             node->condition()->token_pos());
   node->condition()->Visit(&for_test);
   ASSERT(!for_test.is_empty());  // Language spec.
 
   EffectGraphVisitor for_body(owner(), temp_index());
-  for_body.AddInstruction(
-      new CheckStackOverflowInstr(node->token_pos()));
   node->body()->Visit(&for_body);
 
   // Labels are set after body traversal.
   SourceLabel* lbl = node->label();
   ASSERT(lbl != NULL);
   JoinEntryInstr* join = lbl->join_for_continue();
   if (join != NULL) {
     if (for_body.is_open()) for_body.Goto(join);
     for_body.exit_ = join;
   }
-  TieLoop(for_test, for_body);
+  TieLoop(node->token_pos(), for_test, for_body);
   join = lbl->join_for_break();
   if (join != NULL) {
     Goto(join);
     exit_ = join;
   }
 }
 
 
 // The fragment is composed as follows:
 // a) body-entry-join
 // b) [ body ]
 // c) test-entry (continue-join or body-exit-target)
 // d) [ test-entry ] -> (back-target, loop-exit-target)
 // e) back-target -> (body-entry-join)
 // f) loop-exit-target
 // g) break-join
 void EffectGraphVisitor::VisitDoWhileNode(DoWhileNode* node) {
   // Traverse body first in order to generate continue and break labels.
   EffectGraphVisitor for_body(owner(), temp_index());
-  for_body.AddInstruction(
-      new CheckStackOverflowInstr(node->token_pos()));
   node->body()->Visit(&for_body);
 
   TestGraphVisitor for_test(owner(),
                             temp_index(),
                             node->condition()->token_pos());
   node->condition()->Visit(&for_test);
   ASSERT(is_open());
 
   // Tie do-while loop (test is after the body).
   JoinEntryInstr* body_entry_join =
       new JoinEntryInstr(owner()->AllocateBlockId(),
                          owner()->try_index());
   Goto(body_entry_join);
   Instruction* body_exit = AppendFragment(body_entry_join, for_body);
 
   JoinEntryInstr* join = node->label()->join_for_continue();
   if ((body_exit != NULL) || (join != NULL)) {
     if (join == NULL) {
       join = new JoinEntryInstr(owner()->AllocateBlockId(),
                                 owner()->try_index());
     }
-    join->LinkTo(for_test.entry());
+    CheckStackOverflowInstr* check =
+        new CheckStackOverflowInstr(node->token_pos(), true);
+    join->LinkTo(check);
+    check->LinkTo(for_test.entry());
     if (body_exit != NULL) {
       body_exit->Goto(join);
     }
   }
 
   for_test.IfTrueGoto(body_entry_join);
   join = node->label()->join_for_break();
   if (join == NULL) {
     exit_ = for_test.CreateFalseSuccessor();
   } else {
@@ skipping 16 matching lines @@
 // h) loop-exit-target
 // i) break-join
 void EffectGraphVisitor::VisitForNode(ForNode* node) {
   EffectGraphVisitor for_initializer(owner(), temp_index());
   node->initializer()->Visit(&for_initializer);
   Append(for_initializer);
   ASSERT(is_open());
 
   // Compose body to set any jump labels.
   EffectGraphVisitor for_body(owner(), temp_index());
-  for_body.AddInstruction(
-      new CheckStackOverflowInstr(node->token_pos()));
   node->body()->Visit(&for_body);
 
-  // Join loop body, increment and compute their end instruction.
-  ASSERT(!for_body.is_empty());
-  Instruction* loop_increment_end = NULL;
   EffectGraphVisitor for_increment(owner(), temp_index());
   node->increment()->Visit(&for_increment);
+
+  // Join the loop body and increment and then tie the loop.
   JoinEntryInstr* join = node->label()->join_for_continue();
-  if (join != NULL) {
-    // Insert the join between the body and increment.
-    if (for_body.is_open()) for_body.Goto(join);
-    loop_increment_end = AppendFragment(join, for_increment);
-    ASSERT(loop_increment_end != NULL);
-  } else if (for_body.is_open()) {
-    // Do not insert an extra basic block.
-    for_body.Append(for_increment);
-    loop_increment_end = for_body.exit();
-    // 'for_body' contains at least the stack check.
-    ASSERT(loop_increment_end != NULL);
-  } else {
-    loop_increment_end = NULL;
-  }
-
-  // 'loop_increment_end' is NULL only if there is no join for continue and the
-  // body is not open, i.e., no backward branch exists.
-  if (loop_increment_end != NULL) {
+  if ((join != NULL) || for_body.is_open()) {
     JoinEntryInstr* loop_start =
         new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
+    if (join != NULL) {
+      if (for_body.is_open()) for_body.Goto(join);
+      AppendFragment(join, for_increment);
+      for_increment.Goto(loop_start);
+    } else {
+      for_body.Append(for_increment);
+      for_body.Goto(loop_start);
+    }
     Goto(loop_start);
-    loop_increment_end->Goto(loop_start);
     exit_ = loop_start;
+    AddInstruction(new CheckStackOverflowInstr(node->token_pos(), true));
   }
 
   if (node->condition() == NULL) {
     // Endless loop, no test.
     JoinEntryInstr* body_entry =
         new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     AppendFragment(body_entry, for_body);
     Goto(body_entry);
     if (node->label()->join_for_break() != NULL) {
       // Control flow of ForLoop continues into join_for_break.
@@ skipping 1715 matching lines @@
   AppendFragment(finally_entry, for_finally_block);
   exit_ = for_finally_block.exit_;
 }
 
 
 FlowGraph* FlowGraphBuilder::BuildGraph() {
   if (FLAG_print_ast) {
     // Print the function ast before IL generation.
     AstPrinter::PrintFunctionNodes(*parsed_function());
   }
-  // Compilation can be nested, preserve the computation-id.
   const Function& function = parsed_function()->function();
   TargetEntryInstr* normal_entry =
       new TargetEntryInstr(AllocateBlockId(),
                            CatchClauseNode::kInvalidTryIndex);
-  graph_entry_ = new GraphEntryInstr(*parsed_function(), normal_entry);
+  graph_entry_ = new GraphEntryInstr(*parsed_function(), normal_entry, osr_id_);
   EffectGraphVisitor for_effect(this, 0);
   // This check may be deleted if the generated code is leaf.
   CheckStackOverflowInstr* check =
-      new CheckStackOverflowInstr(function.token_pos());
+      new CheckStackOverflowInstr(function.token_pos(), false);
   // If we are inlining don't actually attach the stack check. We must still
   // create the stack check in order to allocate a deopt id.
   if (!IsInlining()) for_effect.AddInstruction(check);
   parsed_function()->node_sequence()->Visit(&for_effect);
   AppendFragment(normal_entry, for_effect);
   // Check that the graph is properly terminated.
   ASSERT(!for_effect.is_open());
+
+  // When compiling for OSR, use a depth first search to prune instructions
+  // unreachable from the OSR entry.  Catch entries are not (yet) properly
+  // recognized as reachable.
+  if (osr_id_ != Isolate::kNoDeoptId) {
+    if (graph_entry_->SuccessorCount() > 1) {
+      Bailout("try/catch when compiling for OSR");

[Florian Schneider, 2013/06/12 08:25:24]

Add a TODO to enable OSR for such functions. What is missing to enable it now?

[Kevin Millikin (Google), 2013/06/14 10:10:42]

I think they might just work but generate unreachable code in the case of
unreachable catch entries.

We have a similar problem with unreachable code elimination which can eliminate
try/catch.  I'll tackle both issues as a separate change.

+    }
+    PruneUnreachable();
+  }
+
   FlowGraph* graph = new FlowGraph(*this, graph_entry_, last_used_block_id_);
   return graph;
 }
 
 
+void FlowGraphBuilder::PruneUnreachable() {
+  ASSERT(osr_id_ != Isolate::kNoDeoptId);
+  BitVector* block_marks = new BitVector(last_used_block_id_ + 1);
+  bool found = graph_entry_->PruneUnreachable(this, graph_entry_, osr_id_,
+                                              block_marks);
+  ASSERT(found);
+}
+
+
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_->function().ToCString();
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart