Implement JumpNode for break/continue in for loops.

runtime/vm/flow_graph_builder.cc

Index: runtime/vm/flow_graph_builder.cc
===================================================================
--- runtime/vm/flow_graph_builder.cc	(revision 5935)
+++ runtime/vm/flow_graph_builder.cc	(working copy)
@@ -748,47 +748,128 @@
 }
 
 
+// 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);
 
-  // Degenerate cases.  An absent condition is implicitly true.  No
-  // normal exit from loop => no back edge.
-  if (!for_body.is_open()) {
+    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);
-    return;
+    for_increment.exit()->SetSuccessor(loop_start);
+    if (node->label()->is_break_jump_target()) {
+      exit_ = for_break_join;
+    } else {
+      CloseFragment();
+    }
   }
-  JoinEntryInstr* join = new JoinEntryInstr();
-  AddInstruction(join);
-  if (for_body.is_empty()) {
-    join->SetSuccessor(join);
-  } else {
-    join->SetSuccessor(for_body.entry());
-    for_body.exit()->SetSuccessor(join);
-  }
-  CloseFragment();
 }
 
 
 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
-  Bailout("EffectGraphVisitor::VisitJumpNode");
+  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;
+  }
+
+  // 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();
+    }
+  }
+  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 {
+    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();
 }
 
 
@@ -1413,6 +1494,10 @@
     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()) {