Introduce a nesting stack to the flow graph builder.

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/class_finalizer.h"
@@ skipping 24 matching lines @@
 DEFINE_FLAG(bool, print_ast, false, "Print abstract syntax tree.");
 DEFINE_FLAG(bool, print_scopes, false, "Print scopes of local variables.");
 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph.");
 DEFINE_FLAG(bool, print_flow_graph_optimized, false,
             "Print the IR flow graph when optimizing.");
 DEFINE_FLAG(bool, trace_type_check_elimination, false,
             "Trace type check elimination at compile time.");
 DECLARE_FLAG(bool, enable_type_checks);
 
 
+JoinEntryInstr* NestedStatement::BreakTargetFor(SourceLabel* label) {
+  if (label != label_) return NULL;
+  if (break_target_ == NULL) {
+    break_target_ =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
+  }
+  return break_target_;
+}
+
+
+JoinEntryInstr* NestedStatement::ContinueTargetFor(SourceLabel* label) {
+  return NULL;
+}
+
+
+// A nested statement that can be the target of a continue as well as a
+// break.
+class NestedLoop : public NestedStatement {
+ public:
+  NestedLoop(FlowGraphBuilder* owner, SourceLabel* label)
+      : NestedStatement(owner, label), continue_target_(NULL) { }
+
+  JoinEntryInstr* continue_target() const { return continue_target_; }
+
+  virtual JoinEntryInstr* ContinueTargetFor(SourceLabel* label);
+
+ private:
+  JoinEntryInstr* continue_target_;
+};
+
+
+JoinEntryInstr* NestedLoop::ContinueTargetFor(SourceLabel* label) {
+  if (label != this->label()) return NULL;
+  if (continue_target_ == NULL) {
+    continue_target_ =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
+  }
+  return continue_target_;
+}
+
+
+// A nested switch which can be the target of a break if labeled, and whose
+// cases can be the targets of continues.
+class NestedSwitch : public NestedStatement {
+ public:
+  NestedSwitch(FlowGraphBuilder* owner, SwitchNode* node);
+
+  virtual JoinEntryInstr* ContinueTargetFor(SourceLabel* label);
+
+ private:
+  GrowableArray<SourceLabel*> case_labels_;
+  GrowableArray<JoinEntryInstr*> case_targets_;
+};
+
+
+NestedSwitch::NestedSwitch(FlowGraphBuilder* owner, SwitchNode* node)
+    : NestedStatement(owner, node->label()),
+      case_labels_(node->body()->length()),
+      case_targets_(node->body()->length()) {
+  SequenceNode* body = node->body();
+  for (intptr_t i = 0; i < body->length(); ++i) {
+    CaseNode* case_node = body->NodeAt(i)->AsCaseNode();
+    if (case_node != NULL) {
+      case_labels_.Add(case_node->label());
+      case_targets_.Add(NULL);
+    }
+  }
+}
+
+
+JoinEntryInstr* NestedSwitch::ContinueTargetFor(SourceLabel* label) {
+  // Allocate a join for a case clause that matches the label.  This block
+  // is not necessarily targeted by a continue, but we always use a join in
+  // the graph anyway.
+  for (intptr_t i = 0; i < case_labels_.length(); ++i) {
+    if (label != case_labels_[i]) continue;
+    if (case_targets_[i] == NULL) {
+      case_targets_[i] =
+          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
+    }
+    return case_targets_[i];
+  }
+  return NULL;
+}
+
+
 FlowGraphBuilder::FlowGraphBuilder(ParsedFunction* parsed_function,
                                    const Array& ic_data_array,
                                    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),
     guarded_fields_(new ZoneGrowableArray<const Field*>()),
     last_used_block_id_(0),  // 0 is used for the graph entry.
     context_level_(0),
     try_index_(CatchClauseNode::kInvalidTryIndex),
     catch_try_index_(CatchClauseNode::kInvalidTryIndex),
     loop_depth_(0),
     graph_entry_(NULL),
     temp_count_(0),
     args_pushed_(0),
+    nesting_stack_(NULL),
     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);
@@ skipping 1483 matching lines @@
 
   node->true_branch()->Visit(&for_true);
   // The for_false graph fragment will be empty (default graph fragment) if
   // we do not call Visit.
   if (node->false_branch() != NULL) node->false_branch()->Visit(&for_false);
   Join(for_test, for_true, for_false);
 }
 
 
 void EffectGraphVisitor::VisitSwitchNode(SwitchNode* node) {
+  NestedSwitch nested_switch(owner(), node);
   EffectGraphVisitor switch_body(owner());
   node->body()->Visit(&switch_body);
   Append(switch_body);
-  if ((node->label() != NULL) && (node->label()->join_for_break() != NULL)) {
-    if (is_open()) Goto(node->label()->join_for_break());
-    exit_ = node->label()->join_for_break();
+  if (nested_switch.break_target() != NULL) {
+    if (is_open()) Goto(nested_switch.break_target());
+    exit_ = nested_switch.break_target();
   }
-  // No continue label allowed.
-  ASSERT((node->label() == NULL) ||
-         (node->label()->join_for_continue() == NULL));
 }
 
 
 // A case node contains zero or more case expressions, can contain default
 // and a case statement body.
 // Compose fragment as follows:
 // - if no case expressions, must have default:
 //   a) target
 //   b) [ case-statements ]
 //
 // - if has 1 or more case statements
 //   a) target-0
 //   b) [ case-expression-0 ] -> (true-target-0, target-1)
 //   c) target-1
 //   d) [ case-expression-1 ] -> (true-target-1, exit-target)
 //   e) true-target-0 -> case-statements-join
 //   f) true-target-1 -> case-statements-join
 //   g) case-statements-join
 //   h) [ case-statements ] -> exit-join
 //   i) exit-target -> exit-join
 //   j) exit-join
 //
 // Note: The specification of switch/case is under discussion and may change
 // drastically.
 void EffectGraphVisitor::VisitCaseNode(CaseNode* node) {
   const intptr_t len = node->case_expressions()->length();
   // Create case statements instructions.
   EffectGraphVisitor for_case_statements(owner());
-  // Compute start of statements fragment.
+  // Compute the start of the statements fragment.
   JoinEntryInstr* statement_start = NULL;
-  if ((node->label() != NULL) && node->label()->is_continue_target()) {
-    // Since a labeled jump continue statement occur in a different case node,
-    // allocate JoinNode here and use it as statement start.
-    statement_start = node->label()->join_for_continue();
-    if (statement_start == NULL) {
-      statement_start = new JoinEntryInstr(owner()->AllocateBlockId(),
-                                           owner()->try_index());
-      node->label()->set_join_for_continue(statement_start);
-    }
-  } else {
+  if (node->label() == NULL) {
     statement_start = new JoinEntryInstr(owner()->AllocateBlockId(),
                                          owner()->try_index());
+  } else {
+    // The case nodes are nested inside a SequenceNode that is the body of a
+    // SwitchNode.  The SwitchNode on the nesting stack contains the
+    // continue labels for all the case clauses.
+    statement_start =
+        owner()->nesting_stack()->outer()->ContinueTargetFor(node->label());
   }
+  ASSERT(statement_start != NULL);
   node->statements()->Visit(&for_case_statements);
   Instruction* statement_exit =
       AppendFragment(statement_start, for_case_statements);
   if (is_open() && (len == 0)) {
     ASSERT(node->contains_default());
     // Default only case node.
     Goto(statement_start);
     exit_ = statement_exit;
     return;
   }
@@ skipping 55 matching lines @@
 //                         body:      <Sequence> }
 // The fragment is composed as follows:
 // a) loop-join
 // b) [ test ] -> (body-entry-target, loop-exit-target)
 // c) body-entry-target
 // d) [ body ] -> (continue-join)
 // e) continue-join -> (loop-join)
 // f) loop-exit-target
 // g) break-join (optional)
 void EffectGraphVisitor::VisitWhileNode(WhileNode* node) {
+  NestedLoop nested_loop(owner(), node->label());
   owner()->IncrementLoopDepth();
+
   TestGraphVisitor for_test(owner(), node->condition()->token_pos());
   node->condition()->Visit(&for_test);
   ASSERT(!for_test.is_empty());  // Language spec.
 
   EffectGraphVisitor for_body(owner());
   node->body()->Visit(&for_body);
 
   // Labels are set after body traversal.
-  SourceLabel* lbl = node->label();
-  ASSERT(lbl != NULL);
-  JoinEntryInstr* join = lbl->join_for_continue();
+  JoinEntryInstr* join = nested_loop.continue_target();
   if (join != NULL) {
     if (for_body.is_open()) for_body.Goto(join);
     for_body.exit_ = join;
   }
   TieLoop(node->token_pos(), for_test, for_body);
-  join = lbl->join_for_break();
+  join = nested_loop.break_target();
   if (join != NULL) {
     Goto(join);
     exit_ = join;
   }
   owner()->DecrementLoopDepth();
 }
 
 
 // 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) {
+  NestedLoop nested_loop(owner(), node->label());
   owner()->IncrementLoopDepth();
-  // Traverse body first in order to generate continue and break labels.
+
+  // Traverse the body first in order to generate continue and break labels.
   EffectGraphVisitor for_body(owner());
   node->body()->Visit(&for_body);
 
   TestGraphVisitor for_test(owner(), 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();
+  JoinEntryInstr* join = nested_loop.continue_target();
   if ((body_exit != NULL) || (join != NULL)) {
     if (join == NULL) {
       join = new JoinEntryInstr(owner()->AllocateBlockId(),
                                 owner()->try_index());
     }
     CheckStackOverflowInstr* check =
         new CheckStackOverflowInstr(node->token_pos(), owner()->loop_depth());
     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();
+  join = nested_loop.break_target();
   if (join == NULL) {
     exit_ = for_test.CreateFalseSuccessor();
   } else {
     for_test.IfFalseGoto(join);
     exit_ = join;
   }
   owner()->DecrementLoopDepth();
 }
 
 
 // A ForNode can contain break and continue jumps. 'break' joins to
 // ForNode exit, 'continue' joins at increment entry. The fragment is composed
 // as follows:
 // a) [ initializer ]
 // b) loop-join
 // c) [ test ] -> (body-entry-target, loop-exit-target)
 // d) body-entry-target
 // e) [ body ]
 // f) continue-join (optional)
 // g) [ increment ] -> (loop-join)
 // h) loop-exit-target
 // i) break-join
 void EffectGraphVisitor::VisitForNode(ForNode* node) {
   EffectGraphVisitor for_initializer(owner());
   node->initializer()->Visit(&for_initializer);
   Append(for_initializer);
   ASSERT(is_open());
 
+  NestedLoop nested_loop(owner(), node->label());
   owner()->IncrementLoopDepth();
   // Compose body to set any jump labels.
   EffectGraphVisitor for_body(owner());
   node->body()->Visit(&for_body);
 
   EffectGraphVisitor for_increment(owner());
   node->increment()->Visit(&for_increment);
 
   // Join the loop body and increment and then tie the loop.
-  JoinEntryInstr* continue_join = node->label()->join_for_continue();
+  JoinEntryInstr* continue_join = nested_loop.continue_target();
   if ((continue_join != NULL) || for_body.is_open()) {
     JoinEntryInstr* loop_entry =
         new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     if (continue_join != NULL) {
       if (for_body.is_open()) for_body.Goto(continue_join);
       Instruction* current = AppendFragment(continue_join, for_increment);
       current->Goto(loop_entry);
     } else {
       for_body.Append(for_increment);
       for_body.Goto(loop_entry);
     }
     Goto(loop_entry);
     exit_ = loop_entry;
     AddInstruction(
         new CheckStackOverflowInstr(node->token_pos(), owner()->loop_depth()));
   }
 
   if (node->condition() == NULL) {
     // Endless loop, no test.
     Append(for_body);
-    exit_ = node->label()->join_for_break();  // May be NULL.
+    exit_ = nested_loop.break_target();  // May be NULL.
   } else {
     TestGraphVisitor for_test(owner(), node->condition()->token_pos());
     node->condition()->Visit(&for_test);
     Append(for_test);
 
     BlockEntryInstr* body_entry = for_test.CreateTrueSuccessor();
     AppendFragment(body_entry, for_body);
 
-    if (node->label()->join_for_break() == NULL) {
+    if (nested_loop.break_target() == NULL) {
       exit_ = for_test.CreateFalseSuccessor();
     } else {
-      for_test.IfFalseGoto(node->label()->join_for_break());
-      exit_ = node->label()->join_for_break();
+      for_test.IfFalseGoto(nested_loop.break_target());
+      exit_ = nested_loop.break_target();
     }
   }
   owner()->DecrementLoopDepth();
 }
 
 
 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
   for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) {
     EffectGraphVisitor for_effect(owner());
     node->InlinedFinallyNodeAt(i)->Visit(&for_effect);
@@ skipping 23 matching lines @@
     }
   }
   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();
   }
 
   JoinEntryInstr* jump_target = NULL;
   if (node->kind() == Token::kBREAK) {

[Florian Schneider, 2013/11/13 17:42:58]

For less duplicated code maybe move this condition inside the loop:

NestedStatement* current = owner()->nesting_stack();
while (current != NULL) {
  jump_target = node->kind() == Token::kBREAK
      ? current->BreakTargetFor(node->label())
      : current->ContinueTargetFor(node->label());
  if (jump_target != NULL) break;
  current = current->outer();
}

[Kevin Millikin (Google), 2013/11/13 17:47:22]

That sounds good to me.  I'll do it.

-    if (node->label()->join_for_break() == NULL) {
-      node->label()->set_join_for_break(
-          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index()));
+    NestedStatement* current = owner()->nesting_stack();
+    while (current != NULL) {
+      jump_target = current->BreakTargetFor(node->label());
+      if (jump_target != NULL) break;
+      current = current->outer();
     }
-    jump_target = node->label()->join_for_break();
   } else {
-    if (node->label()->join_for_continue() == NULL) {
-      node->label()->set_join_for_continue(
-          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index()));
+    NestedStatement* current = owner()->nesting_stack();
+    while (current != NULL) {
+      jump_target = current->ContinueTargetFor(node->label());
+      if (jump_target != NULL) break;
+      current = current->outer();
     }
-    jump_target = node->label()->join_for_continue();
   }
+  ASSERT(jump_target != NULL);
   Goto(jump_target);
 }
 
 
 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) {
   UNREACHABLE();
 }
 
 
 intptr_t EffectGraphVisitor::GetCurrentTempLocalIndex() const {
@@ skipping 1475 matching lines @@
 
 
 // <Statement> ::= Sequence { scope: LocalScope
 //                            nodes: <Statement>*
 //                            label: SourceLabel }
 void EffectGraphVisitor::VisitSequenceNode(SequenceNode* node) {
   LocalScope* scope = node->scope();
   const intptr_t num_context_variables =
       (scope != NULL) ? scope->num_context_variables() : 0;
   int previous_context_level = owner()->context_level();
+  // The outermost function sequence cannot contain a label.
+  ASSERT((node->label() == NULL) ||
+         (node != owner()->parsed_function()->node_sequence()));
+  NestedStatement nested_block(owner(), node->label());
+
   if (num_context_variables > 0) {
     // The loop local scope declares variables that are captured.
     // Allocate and chain a new context.
     // Allocate context computation (uses current CTX)
     Value* allocated_context =
         Bind(new AllocateContextInstr(node->token_pos(),
                                       num_context_variables));
     { LocalVariable* tmp_var = EnterTempLocalScope(allocated_context);
       // If this node_sequence is the body of the function being compiled, and
       // if this function allocates context variables, but none of its enclosing
       // functions do, the context on entry is not linked as parent of the
       // allocated context but saved on entry and restored on exit as to prevent
       // memory leaks.
       // In this case, the parser pre-allocates a variable to save the context.
       if (MustSaveRestoreContext(node)) {
         BuildSaveContext(
             *owner()->parsed_function()->saved_entry_context_var());
         Value* null_context = Bind(new ConstantInstr(Object::ZoneHandle()));
         AddInstruction(new StoreContextInstr(null_context));
       }
       Value* current_context = Bind(new CurrentContextInstr());
       Value* tmp_val = Bind(new LoadLocalInstr(*tmp_var));
       Do(new StoreVMFieldInstr(tmp_val,
                                Context::parent_offset(),
                                current_context,
                                Type::ZoneHandle()));
       AddInstruction(
           new StoreContextInstr(Bind(ExitTempLocalScope(tmp_var))));
     }
+
     owner()->set_context_level(scope->context_level());
 
     // If this node_sequence is the body of the function being compiled, copy
     // the captured parameters from the frame into the context.
     if (node == owner()->parsed_function()->node_sequence()) {
       ASSERT(scope->context_level() == 1);
       const Function& function = owner()->parsed_function()->function();
       const int num_params = function.NumParameters();
       int param_frame_index = (num_params == function.num_fixed_parameters()) ?
           (kParamEndSlotFromFp + num_params) : kFirstLocalSlotFromFp;
@@ skipping 74 matching lines @@
   if (is_open()) {
     if (MustSaveRestoreContext(node)) {
       ASSERT(num_context_variables > 0);
       BuildRestoreContext(
           *owner()->parsed_function()->saved_entry_context_var());
     } else if (num_context_variables > 0) {
       UnchainContext();
     }
   }
 
-  // No continue on sequence allowed.
-  ASSERT((node->label() == NULL) ||
-         (node->label()->join_for_continue() == NULL));
   // If this node sequence is labeled, a break out of the sequence will have
   // taken care of unchaining the context.
-  if ((node->label() != NULL) &&
-      (node->label()->join_for_break() != NULL)) {
-    if (is_open()) Goto(node->label()->join_for_break());
-    exit_ = node->label()->join_for_break();
+  if (nested_block.break_target() != NULL) {
+    if (is_open()) Goto(nested_block.break_target());
+    exit_ = nested_block.break_target();
   }
 
-  // The outermost function sequence cannot contain a label.
-  ASSERT((node->label() == NULL) ||
-         (node != owner()->parsed_function()->node_sequence()));
   owner()->set_context_level(previous_context_level);
 }
 
 
 void EffectGraphVisitor::VisitCatchClauseNode(CatchClauseNode* node) {
   InlineBailout("EffectGraphVisitor::VisitCatchClauseNode (exception)");
   // Restores CTX from local variable ':saved_context'.
   BuildRestoreContext(node->context_var());
 
   EffectGraphVisitor for_catch(owner());
@@ skipping 350 matching lines @@
   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