Implement JumpNode for break/continue in for loops.

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 "vm/ast_printer.h"
 #include "vm/flags.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
@@ skipping 730 matching lines @@
     body_exit->SetSuccessor(target_entry);
   }
 
   TargetEntryInstr* back_target_entry = new TargetEntryInstr();
   *for_test.true_successor_address() = back_target_entry;
   back_target_entry->SetSuccessor(join);
   exit_ = *for_test.false_successor_address() = new TargetEntryInstr();
 }
 
 
+// A ForNode can contain break and continue jumps. 'break' joins to
+// ForNode exit, 'continue' joins at iteration entry.
 void EffectGraphVisitor::VisitForNode(ForNode* node) {
   EffectGraphVisitor for_initializer(owner(), temp_index());
   node->initializer()->Visit(&for_initializer);
   Append(for_initializer);
   ASSERT(is_open());
 
+  JoinEntryInstr* for_break_join = NULL;
+  if (node->label()->is_break_jump_target()) {

[Kevin Millikin (Google), 2012/03/29 11:38:31]

You could do this lazily in VisitJumpNode:

if ((node->kind() == Token::kBREAK) &&
    (node->label()->join_for_break() == NULL)) {
  node->label()->join_for_break() = new Join...;
}

It has two small advantages that I can see: avoids a join for unreachable breaks
(rare) and keeps the logic for break and continue out the logic for looping
graph structure, which is already kind of complicated.

+    for_break_join = new JoinEntryInstr();
+    // Must be set-up before body is traversed.
+    node->label()->set_join_for_break(for_break_join);
+  }
+
+  // Increment entry is either target or join.
+  BlockEntryInstr* increment_entry = NULL;

[Kevin Millikin (Google), 2012/03/29 11:38:31]

You could also do this lazily in VisitJumpNode.

+  if (node->label()->is_continue_jump_target()) {
+    JoinEntryInstr* join = new JoinEntryInstr();
+    // Must be set-up before body is traversed.
+    node->label()->set_join_for_continue(join);
+    increment_entry = join;
+  } else {
+    increment_entry = new TargetEntryInstr();
+  }
+
+  EffectGraphVisitor for_increment(owner(), temp_index());

[Kevin Millikin (Google), 2012/03/29 11:38:31]

Then you can:

1. Visit the body first.  After visiting the body, ask if
node->label()->join_for_continue() is NULL.  If so and the body is open, set its
exit's successor to the join for continue.

If there is no join for continue, then we can accumulate the increment
instructions in the same block as the body (avoiding an unnecessary basic block
in the common case) as before.

2. Visit the condition.  Tie it to the body, and a false successor to a fresh
target (if there is no join for break) or an edge (split by a target) to the
join for break.

Does that make sense?

+  for_increment.AddInstruction(increment_entry);
+  node->increment()->Visit(&for_increment);
+
   EffectGraphVisitor for_body(owner(), temp_index());
+  TargetEntryInstr* body_entry = new TargetEntryInstr();
+  for_body.AddInstruction(body_entry);
   node->body()->Visit(&for_body);
+
   if (for_body.is_open()) {
-    EffectGraphVisitor for_increment(owner(), temp_index());
-    node->increment()->Visit(&for_increment);
-    for_body.Append(for_increment);
+    ASSERT(!for_body.is_empty());
+    for_body.exit()->SetSuccessor(increment_entry);
   }
 
   if (node->condition() != NULL) {
+    JoinEntryInstr* test_entry = new JoinEntryInstr();
+    AddInstruction(test_entry);
     TestGraphVisitor for_test(owner(), temp_index());
     node->condition()->Visit(&for_test);
-    TieLoop(for_test, for_body);
-    return;
+    Append(for_test);
+    *for_test.true_successor_address() = body_entry;
+    for_increment.exit()->SetSuccessor(test_entry);
+
+    TargetEntryInstr* target_entry = new TargetEntryInstr();
+    *for_test.false_successor_address() = target_entry;
+    if (for_break_join == NULL) {
+      exit_ = target_entry;
+    } else {
+      target_entry->SetSuccessor(for_break_join);
+      exit_ = for_break_join;
+    }
+  } else {
+    // Endless loop
+    JoinEntryInstr* loop_start = new JoinEntryInstr();
+    AddInstruction(loop_start);
+    Append(for_body);
+    for_increment.exit()->SetSuccessor(loop_start);
+    if (node->label()->is_break_jump_target()) {
+      exit_ = for_break_join;
+    } else {
+      CloseFragment();
+    }
+  }
+}
+
+
+void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
+  for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) {
+    EffectGraphVisitor for_effect(owner(), temp_index());
+    node->InlinedFinallyNodeAt(i)->Visit(&for_effect);
+    Append(for_effect);
+    if (!is_open()) return;
   }
 
-  // Degenerate cases.  An absent condition is implicitly true.  No
-  // normal exit from loop => no back edge.
-  if (!for_body.is_open()) {
-    Append(for_body);
-    return;
+  // Unchain the context(s) up to the outer context level of the scope which
+  // contains the destination label.
+  SourceLabel* label = node->label();
+  ASSERT(label->owner() != NULL);
+  int target_context_level = 0;
+  LocalScope* target_scope = label->owner();
+  if (target_scope->num_context_variables() > 0) {
+    // The scope of the target label allocates a context, therefore its outer
+    // scope is at a lower context level.
+    target_context_level = target_scope->context_level() - 1;
+  } else {
+    // The scope of the target label does not allocate a context, so its outer
+    // scope is at the same context level. Find it.
+    while ((target_scope != NULL) &&
+           (target_scope->num_context_variables() == 0)) {
+      target_scope = target_scope->parent();
+    }
+    if (target_scope != NULL) {
+      target_context_level = target_scope->context_level();
+    }
   }
-  JoinEntryInstr* join = new JoinEntryInstr();
-  AddInstruction(join);
-  if (for_body.is_empty()) {
-    join->SetSuccessor(join);
+  ASSERT(target_context_level >= 0);
+  intptr_t current_context_level = owner()->context_level();
+  ASSERT(current_context_level >= target_context_level);
+  while (current_context_level-- > target_context_level) {
+    UnchainContext();
+  }
+
+  if (node->kind() == Token::kBREAK) {
+    ASSERT(node->label()->is_break_jump_target());
+    if (node->label()->join_for_break() == NULL) {
+      Bailout("Join for JUMP BREAK not implemented");
+    }
+    entry_ = exit_ = node->label()->join_for_break();

[Kevin Millikin (Google), 2012/03/29 11:38:31]

Hmm.  We don't need to set exit_, because CloseFragment will just clear it (the
jump node has no fall through).

I'm not sure it's right to set entry_ either.  Won't that leave the inlined
finally blocks and the context unchaining instructions dangling when the caller
tries to Append the result of translating the JumpNode?

   } else {
-    join->SetSuccessor(for_body.entry());
-    for_body.exit()->SetSuccessor(join);
+    ASSERT(node->label()->is_continue_jump_target());
+    if (node->label()->join_for_continue() == NULL) {
+      Bailout("Join for JUMP CONTINUE not implemented");
+    }
+    entry_ = exit_ = node->label()->join_for_continue();
   }
   CloseFragment();
 }
 
 
-void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
-  Bailout("EffectGraphVisitor::VisitJumpNode");
-}
-
-
 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) {
   UNREACHABLE();
 }
 
 
 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) {
   // Translate the array elements and collect their values.
   ZoneGrowableArray<Value*>* values =
       new ZoneGrowableArray<Value*>(node->length());
   int index = temp_index();
@@ skipping 601 matching lines @@
   if (FLAG_enable_type_checks &&
       (node == owner()->parsed_function().node_sequence())) {
     Bailout("VisitSequenceNode GenerateArgumentTypeChecks()");
   }
 
   intptr_t i = 0;
   while (is_open() && (i < node->length())) {
     EffectGraphVisitor for_effect(owner(), temp_index());
     node->NodeAt(i++)->Visit(&for_effect);
     Append(for_effect);
+    if (!is_open()) {
+      // E.g., because of a JumpNode.
+      break;
+    }
   }
 
   if (is_open()) {
     if (MustSaveRestoreContext(node)) {
       ASSERT(num_context_variables > 0);
       LoadLocalComp* load_comp =
           new LoadLocalComp(*owner()->parsed_function().saved_context_var(), 0);
       AddInstruction(new BindInstr(temp_index(), load_comp));
       TempVal* local_value = new TempVal(temp_index());
       StoreContextComp* store_context = new StoreContextComp(local_value);
@@ skipping 534 matching lines @@
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(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