Use the VM's graph builder nesting stack for loop depth and context level.

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);
 
 
+// Base class for a stack of enclosing statements of interest (e.g.,
+// blocks (breakable) and loops (continuable)).
+class NestedStatement : public ValueObject {
+ public:
+  NestedStatement(FlowGraphBuilder* owner, const SourceLabel* label)

[Florian Schneider, 2013/11/19 10:37:05]

Since only subclasses of NestedStatement exist (NestedBlock/NestedLoop), I'd
disallow allocation of this class by make this constructor protected, and the
default constructor private.

[Kevin Millikin (Google), 2013/11/19 11:36:54]

OK.

+      : owner_(owner),
+        label_(label),
+        outer_(owner->nesting_stack_),
+        break_target_(NULL) {
+    // Push on the owner's nesting stack.
+    owner->nesting_stack_ = this;
+  }
+
+  virtual ~NestedStatement() {
+    // Pop from the owner's nesting stack.
+    ASSERT(owner_->nesting_stack_ == this);
+    owner_->nesting_stack_ = outer_;
+  }
+
+  FlowGraphBuilder* owner() const { return owner_; }
+  const SourceLabel* label() const { return label_; }
+  NestedStatement* outer() const { return outer_; }
+  JoinEntryInstr* break_target() const { return break_target_; }
+
+  virtual intptr_t ContextLevel() const;
+
+  virtual JoinEntryInstr* BreakTargetFor(SourceLabel* label);
+  virtual JoinEntryInstr* ContinueTargetFor(SourceLabel* label);
+
+ private:
+  FlowGraphBuilder* owner_;
+  const SourceLabel* label_;
+  NestedStatement* outer_;
+
+  JoinEntryInstr* break_target_;
+};
+
+
+intptr_t NestedStatement::ContextLevel() const {
+  // Context level is determined by the innermost nested statement having one.
+  return (outer() == NULL) ? 0 : outer()->ContextLevel();
+}
+
+
+intptr_t FlowGraphBuilder::context_level() const {
+  return (nesting_stack() == NULL) ? 0 : nesting_stack()->ContextLevel();
+}
+
+
 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 has its own context level.
+class NestedBlock : public NestedStatement {
+ public:
+  NestedBlock(FlowGraphBuilder* owner, SequenceNode* node)
+      : NestedStatement(owner, node->label()), scope_(node->scope()) {}
+
+  virtual intptr_t ContextLevel() const;
+
+ private:
+  LocalScope* scope_;
+};
+
+
+intptr_t NestedBlock::ContextLevel() const {
+  return ((scope_ == NULL) || (scope_->num_context_variables() == 0))
+      ? NestedStatement::ContextLevel()
+      : scope_->context_level();
+}
+
+
 // 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) { }
+      : NestedStatement(owner, label), continue_target_(NULL) {
+    owner->IncrementLoopDepth();
+  }
+
+  virtual ~NestedLoop() {
+    owner()->DecrementLoopDepth();
+  }
 
   JoinEntryInstr* continue_target() const { return continue_target_; }
 
   virtual JoinEntryInstr* ContinueTargetFor(SourceLabel* label);
 
  private:
   JoinEntryInstr* continue_target_;
 };
 
 
@@ skipping 60 matching lines @@
     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) { }
 
 
@@ skipping 752 matching lines @@
                                           Symbols::FunctionResult());
     }
   }
 
   intptr_t current_context_level = owner()->context_level();
   ASSERT(current_context_level >= 0);
   if (owner()->parsed_function()->saved_entry_context_var() != NULL) {
     // CTX on entry was saved, but not linked as context parent.
     BuildRestoreContext(*owner()->parsed_function()->saved_entry_context_var());
   } else {
-    while (current_context_level-- > 0) {
-      UnchainContext();
-    }
+    UnchainContexts(current_context_level);
   }
 
   AddReturnExit(node->token_pos(), return_value);
 }
 
 
 // <Expression> ::= Literal { literal: Instance }
 void EffectGraphVisitor::VisitLiteralNode(LiteralNode* node) {
   return;
 }
@@ skipping 840 matching lines @@
 // 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.
   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 = 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 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).
@@ skipping 19 matching lines @@
   }
 
   for_test.IfTrueGoto(body_entry_join);
   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 = nested_loop.continue_target();
   if ((continue_join != NULL) || for_body.is_open()) {
@@ skipping 25 matching lines @@
     BlockEntryInstr* body_entry = for_test.CreateTrueSuccessor();
     AppendFragment(body_entry, for_body);
 
     if (nested_loop.break_target() == NULL) {
       exit_ = for_test.CreateFalseSuccessor();
     } else {
       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);
     Append(for_effect);
     if (!is_open()) return;
   }
@@ skipping 15 matching lines @@
            (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();
-  }
+  UnchainContexts(current_context_level - target_context_level);
 
   JoinEntryInstr* jump_target = NULL;
-  if (node->kind() == Token::kBREAK) {
-    NestedStatement* current = owner()->nesting_stack();
-    while (current != NULL) {
-      jump_target = current->BreakTargetFor(node->label());
-      if (jump_target != NULL) break;
-      current = current->outer();
-    }
-  } else {
-    NestedStatement* current = owner()->nesting_stack();
-    while (current != NULL) {
-      jump_target = current->ContinueTargetFor(node->label());
-      if (jump_target != NULL) break;
-      current = current->outer();
-    }
+  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();
   }
   ASSERT(jump_target != NULL);
   Goto(jump_target);
 }
 
 
 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) {
   UNREACHABLE();
 }
 
@@ skipping 1459 matching lines @@
   ReturnDefinition(BuildStoreIndexedValues(node, kResultNeeded));
 }
 
 
 bool EffectGraphVisitor::MustSaveRestoreContext(SequenceNode* node) const {
   return (node == owner()->parsed_function()->node_sequence()) &&
          (owner()->parsed_function()->saved_entry_context_var() != NULL);
 }
 
 
-void EffectGraphVisitor::UnchainContext() {
-  Value* context = Bind(new CurrentContextInstr());
-  Value* parent = Bind(
-      new LoadFieldInstr(context,
-                         Context::parent_offset(),
-                         Type::ZoneHandle()));  // Not an instance, no type.
-  AddInstruction(new StoreContextInstr(parent));
+void EffectGraphVisitor::UnchainContexts(intptr_t n) {
+  if (n > 0) {
+    Value* context = Bind(new CurrentContextInstr());
+    while (n-- > 0) {
+      context = Bind(
+          new LoadFieldInstr(context,
+                             Context::parent_offset(),
+                             Type::ZoneHandle()));  // Not an instance, no type.
+    }
+    AddInstruction(new StoreContextInstr(context));
+  }
 }
 
 
 // <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());
+  NestedBlock nested_block(owner(), node);
 
   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
@@ skipping 11 matching lines @@
       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;
       for (int pos = 0; pos < num_params; param_frame_index--, pos++) {
         const LocalVariable& parameter = *scope->VariableAt(pos);
@@ skipping 68 matching lines @@
       break;
     }
   }
 
   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();
+      UnchainContexts(1);
     }
   }
 
   // If this node sequence is labeled, a break out of the sequence will have
   // taken care of unchaining the context.
   if (nested_block.break_target() != NULL) {
     if (is_open()) Goto(nested_block.break_target());
     exit_ = nested_block.break_target();
   }
-
-  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());
   node->VisitChildren(&for_catch);
@@ skipping 352 matching lines @@
                                   LanguageError::kError,
                                   Heap::kNew,
                                   "FlowGraphBuilder Bailout: %s %s",
                                   String::Handle(function.name()).ToCString(),
                                   reason));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart