Change the translation of break/continue into Hydrogen.

src/hydrogen.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 484 matching lines @@
   } else if (then_graph->HasExit()) {
     exit_block_ = then_graph->exit_block_;
   } else if (else_graph->HasExit()) {
     exit_block_ = else_graph->exit_block_;
   } else {
     exit_block_ = NULL;
   }
 }
 
 
-void HSubgraph::ResolveContinue(IterationStatement* statement) {
-  HBasicBlock* continue_block = BundleContinue(statement);
+void HSubgraph::ResolveContinue(IterationStatement* statement,

[Kevin Millikin (Chromium), 2011/02/21 15:41:07]

I have tried to keep these helpers and their use as close as possible to the
original.  There is further refactoring to be done on subgraphs.

+                                HBasicBlock* continue_block) {
   if (continue_block != NULL) {
-    exit_block_ = JoinBlocks(exit_block(),
-                             continue_block,
-                             statement->ContinueId());
+    continue_block->SetJoinId(statement->ContinueId());
   }
+  exit_block_ =
+      JoinBlocks(exit_block(), continue_block, statement->ContinueId());
 }
 
 
-HBasicBlock* HSubgraph::BundleBreak(BreakableStatement* statement) {
-  return BundleBreakContinue(statement, false, statement->ExitId());
-}
-
-
-HBasicBlock* HSubgraph::BundleContinue(IterationStatement* statement) {
-  return BundleBreakContinue(statement, true, statement->ContinueId());
-}
-
-
-HBasicBlock* HSubgraph::BundleBreakContinue(BreakableStatement* statement,
-                                            bool is_continue,
-                                            int join_id) {
-  HBasicBlock* result = NULL;
-  const ZoneList<BreakContinueInfo*>* infos = break_continue_info();

[Kevin Millikin (Chromium), 2011/02/21 15:41:07]

Before, we kept this zone-allocated list of blocks ending with break or
continue, per subgraph.  We searched it when we built a breakable statement's
graph to find all the breaks or continues, to allocate basic blocks where
necessary, and to set join ids.

Now, break and continue is resolved immediately when seen.  An annoying wrinkle
is that we can't set the join id until after all the predecessors are added (I'd
like to get rid of that, too).

-  for (int i = 0; i < infos->length(); ++i) {
-    BreakContinueInfo* info = infos->at(i);
-    if (info->is_continue() == is_continue &&
-        info->target() == statement &&
-        !info->IsResolved()) {
-      if (result == NULL) {
-        result = graph_->CreateBasicBlock();
-      }
-      info->block()->Goto(result);
-      info->Resolve();
-    }
-  }
-
-  if (result != NULL) result->SetJoinId(join_id);
-
-  return result;
-}
-
-
 HBasicBlock* HSubgraph::JoinBlocks(HBasicBlock* a, HBasicBlock* b, int id) {
   if (a == NULL) return b;
   if (b == NULL) return a;
   HBasicBlock* target = graph_->CreateBasicBlock();
   a->Goto(target);
   b->Goto(target);
   target->SetJoinId(id);
   return target;
 }
 
 
-void HSubgraph::AppendEndless(HSubgraph* body, IterationStatement* statement) {
+void HSubgraph::AppendEndless(HSubgraph* body,

[Kevin Millikin (Chromium), 2011/02/21 15:41:07]

Everywhere we used to call ResolveContinue or BundleBreak, we now have the block
already in hand and just pass it in.

+                              IterationStatement* statement,
+                              HBasicBlock* break_block) {
   ConnectExitTo(body->entry_block());
-  body->ResolveContinue(statement);

[Kevin Millikin (Chromium), 2011/02/21 15:41:07]

This call was actually unnecessary, because all the callers of AppendEndless
already did it.

   body->ConnectExitTo(body->entry_block(), true);
-  exit_block_ = body->BundleBreak(statement);
+  if (break_block != NULL) break_block->SetJoinId(statement->ExitId());
+  exit_block_ = break_block;
   body->entry_block()->PostProcessLoopHeader(statement);
 }
 
 
 void HSubgraph::AppendDoWhile(HSubgraph* body,
                               IterationStatement* statement,
                               HSubgraph* go_back,
-                              HSubgraph* exit) {
+                              HSubgraph* exit,
+                              HBasicBlock* break_block) {
   ConnectExitTo(body->entry_block());
   go_back->ConnectExitTo(body->entry_block(), true);
-
-  HBasicBlock* break_block = body->BundleBreak(statement);
+  if (break_block != NULL) break_block->SetJoinId(statement->ExitId());
   exit_block_ =
       JoinBlocks(exit->exit_block(), break_block, statement->ExitId());
   body->entry_block()->PostProcessLoopHeader(statement);
 }
 
 
 void HSubgraph::AppendWhile(HSubgraph* condition,
                             HSubgraph* body,
                             IterationStatement* statement,
                             HSubgraph* continue_subgraph,
-                            HSubgraph* exit) {
+                            HSubgraph* exit,
+                            HBasicBlock* break_block) {
   ConnectExitTo(condition->entry_block());
 
-  HBasicBlock* break_block = body->BundleBreak(statement);
+  if (break_block != NULL) break_block->SetJoinId(statement->ExitId());
   exit_block_ =
       JoinBlocks(exit->exit_block(), break_block, statement->ExitId());
 
   if (continue_subgraph != NULL) {
     body->ConnectExitTo(continue_subgraph->entry_block(), true);
     continue_subgraph->entry_block()->SetJoinId(statement->EntryId());
     exit_block_ = JoinBlocks(exit_block_,
                              continue_subgraph->exit_block(),
                              statement->ExitId());
   } else {
     body->ConnectExitTo(condition->entry_block(), true);
   }
   condition->entry_block()->PostProcessLoopHeader(statement);
 }
 
 
-void HSubgraph::Append(HSubgraph* next, BreakableStatement* stmt) {
+void HSubgraph::Append(HSubgraph* next,
+                       BreakableStatement* stmt,
+                       HBasicBlock* break_block) {
   exit_block_->Goto(next->entry_block());
   exit_block_ = next->exit_block_;
 
   if (stmt != NULL) {
     next->entry_block()->SetJoinId(stmt->EntryId());
-    HBasicBlock* break_block = next->BundleBreak(stmt);
+    if (break_block != NULL) break_block->SetJoinId(stmt->EntryId());
     exit_block_ = JoinBlocks(exit_block(), break_block, stmt->ExitId());
   }
 }
 
 
 void HSubgraph::FinishExit(HControlInstruction* instruction) {
   ASSERT(HasExit());
   exit_block_->Finish(instruction);
   exit_block_->ClearEnvironment();
   exit_block_ = NULL;
 }
 
 
-void HSubgraph::FinishBreakContinue(BreakableStatement* target,
-                                    bool is_continue) {
-  ASSERT(!exit_block_->IsFinished());
-  BreakContinueInfo* info = new BreakContinueInfo(target, exit_block_,
-                                                  is_continue);
-  break_continue_info_.Add(info);
-  exit_block_ = NULL;
-}
-
-
 HGraph::HGraph(CompilationInfo* info)
     : HSubgraph(this),
       next_block_id_(0),
       info_(info),
       blocks_(8),
       values_(16),
       phi_list_(NULL) {
   start_environment_ = new HEnvironment(NULL, info->scope(), info->closure());
   start_environment_->set_ast_id(info->function()->id());
 }
@@ skipping 1459 matching lines @@
 class HGraphBuilder::SubgraphScope BASE_EMBEDDED {
  public:
   SubgraphScope(HGraphBuilder* builder, HSubgraph* new_subgraph)
       : builder_(builder) {
     old_subgraph_ = builder_->current_subgraph_;
     subgraph_ = new_subgraph;
     builder_->current_subgraph_ = subgraph_;
   }
 
   ~SubgraphScope() {
-    old_subgraph_->AddBreakContinueInfo(subgraph_);

[Kevin Millikin (Chromium), 2011/02/21 15:41:07]

Here we copied all the unhandled breaks and continues to the subgraph captured
by this scope.

This was unsafe: we risked losing break or continue wherever the current
subgraph was changed without using a subgraph scope.

It was also wasteful, potentially copying a list every time we used a subgraph
scope for something other than a breakable target.

     builder_->current_subgraph_ = old_subgraph_;
   }
 
   HSubgraph* subgraph() const { return subgraph_; }
 
  private:
   HGraphBuilder* builder_;
   HSubgraph* old_subgraph_;
   HSubgraph* subgraph_;
 };
@@ skipping 53 matching lines @@
     Scope* scope = info->scope();
     SetupScope(scope);
     VisitDeclarations(scope->declarations());
 
     AddInstruction(new HStackCheck());
 
     ZoneList<Statement*>* stmts = info->function()->body();
     HSubgraph* body = CreateGotoSubgraph(environment());
     AddToSubgraph(body, stmts);
     if (HasStackOverflow()) return NULL;
-    current_subgraph_->Append(body, NULL);
+    current_subgraph_->Append(body, NULL, NULL);
     body->entry_block()->SetJoinId(info->function()->id());
 
     if (graph_->HasExit()) {
       graph_->FinishExit(new HReturn(graph_->GetConstantUndefined()));
     }
   }
 
   graph_->OrderBlocks();
   graph_->AssignDominators();
   graph_->EliminateRedundantPhis();
@@ skipping 181 matching lines @@
   block->SetInitialEnvironment(new_env);
   subgraph->Initialize(block);
   subgraph->entry_block()->AttachLoopInformation();
   return subgraph;
 }
 
 
 void HGraphBuilder::VisitBlock(Block* stmt) {
   if (stmt->labels() != NULL) {
     HSubgraph* block_graph = CreateGotoSubgraph(environment());
-    ADD_TO_SUBGRAPH(block_graph, stmt->statements());
-    current_subgraph_->Append(block_graph, stmt);
+    BreakAndContinueInfo break_info(stmt);
+    { BreakStackEntry push(&break_info, this);
+      ADD_TO_SUBGRAPH(block_graph, stmt->statements());
+    }
+    subgraph()->Append(block_graph, stmt, break_info.break_block());
   } else {
     VisitStatements(stmt->statements());
   }
 }
 
 
 void HGraphBuilder::VisitExpressionStatement(ExpressionStatement* stmt) {
   VisitForEffect(stmt->expression());
 }
 
@@ skipping 20 matching lines @@
     ADD_TO_SUBGRAPH(then_graph, stmt->then_statement());
 
     else_graph->entry_block()->SetJoinId(stmt->ElseId());
     ADD_TO_SUBGRAPH(else_graph, stmt->else_statement());
 
     current_subgraph_->AppendJoin(then_graph, else_graph, stmt);
   }
 }
 
 
+HBasicBlock* HGraphBuilder::BreakStackEntry::Get(BreakableStatement* stmt,
+                                                 BreakType type) {
+  BreakStackEntry* current = this;
+  while (current != NULL && current->info()->target() != stmt) {
+    current = current->next();
+  }
+  ASSERT(current != NULL);  // Always found (unless stack is malformed).
+  HBasicBlock* block = NULL;
+  switch (type) {
+    case BREAK:
+      block = current->info()->break_block();
+      if (block == NULL) {
+        block = current->owner()->graph()->CreateBasicBlock();
+        current->info()->set_break_block(block);
+      }
+      break;
+
+    case CONTINUE:
+      block = current->info()->continue_block();
+      if (block == NULL) {
+        block = current->owner()->graph()->CreateBasicBlock();
+        current->info()->set_continue_block(block);
+      }
+      break;
+  }
+
+  return block;
+}
+
+
 void HGraphBuilder::VisitContinueStatement(ContinueStatement* stmt) {
-  current_subgraph_->FinishBreakContinue(stmt->target(), true);
+  HBasicBlock* continue_block = break_stack()->Get(stmt->target(), CONTINUE);
+  subgraph()->exit_block()->Goto(continue_block);
+  subgraph()->set_exit_block(NULL);
 }
 
 
 void HGraphBuilder::VisitBreakStatement(BreakStatement* stmt) {
-  current_subgraph_->FinishBreakContinue(stmt->target(), false);
+  HBasicBlock* break_block = break_stack()->Get(stmt->target(), BREAK);
+  subgraph()->exit_block()->Goto(break_block);
+  subgraph()->set_exit_block(NULL);
 }
 
 
 void HGraphBuilder::VisitReturnStatement(ReturnStatement* stmt) {
   AstContext* context = call_context();
   if (context == NULL) {
     // Not an inlined return, so an actual one.
     VISIT_FOR_VALUE(stmt->expression());
     HValue* result = environment()->Pop();
     subgraph()->FinishExit(new HReturn(result));
@@ skipping 162 matching lines @@
     }
 
     // Check for fall-through from previous statement block.
     if (previous_subgraph != NULL && previous_subgraph->HasExit()) {
       if (subgraph == NULL) subgraph = CreateEmptySubgraph();
       previous_subgraph->exit_block()->
           Finish(new HGoto(subgraph->entry_block()));
     }
 
     if (subgraph != NULL) {
-      ADD_TO_SUBGRAPH(subgraph, clause->statements());
-      HBasicBlock* break_block = subgraph->BundleBreak(stmt);
-      if (break_block != NULL) {
-        break_block->Finish(new HGoto(single_exit_block));
+      BreakAndContinueInfo break_info(stmt);
+      { BreakStackEntry push(&break_info, this);
+        ADD_TO_SUBGRAPH(subgraph, clause->statements());
+      }
+      if (break_info.break_block() != NULL) {
+        break_info.break_block()->SetJoinId(stmt->ExitId());
+        break_info.break_block()->Finish(new HGoto(single_exit_block));
       }
     }
 
     previous_subgraph = subgraph;
   }
 
   // If the last statement block has a fall-through, connect it to the
   // single exit block.
   if (previous_subgraph != NULL && previous_subgraph->HasExit()) {
     previous_subgraph->exit_block()->Finish(new HGoto(single_exit_block));
@@ skipping 46 matching lines @@
   loop_predecessor->SetJoinId(statement->EntryId());
   set_exit_block(loop_predecessor);
 }
 
 
 void HGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) {
   ASSERT(subgraph()->HasExit());
   subgraph()->PreProcessOsrEntry(stmt);
 
   HSubgraph* body_graph = CreateLoopHeaderSubgraph(environment());
-  ADD_TO_SUBGRAPH(body_graph, stmt->body());
-  body_graph->ResolveContinue(stmt);
+  BreakAndContinueInfo break_info(stmt);
+  { BreakStackEntry push(&break_info, this);
+    ADD_TO_SUBGRAPH(body_graph, stmt->body());
+  }
+  body_graph->ResolveContinue(stmt, break_info.continue_block());
 
   if (!body_graph->HasExit() || stmt->cond()->ToBooleanIsTrue()) {
-    current_subgraph_->AppendEndless(body_graph, stmt);
+    subgraph()->AppendEndless(body_graph, stmt, break_info.break_block());
   } else {
     HSubgraph* go_back = CreateEmptySubgraph();
     HSubgraph* exit = CreateEmptySubgraph();
     {
       SubgraphScope scope(this, body_graph);
       VISIT_FOR_CONTROL(stmt->cond(),
                         go_back->entry_block(),
                         exit->entry_block());
       go_back->entry_block()->SetJoinId(stmt->BackEdgeId());
       exit->entry_block()->SetJoinId(stmt->ExitId());
     }
-    current_subgraph_->AppendDoWhile(body_graph, stmt, go_back, exit);
+    subgraph()->AppendDoWhile(body_graph, stmt, go_back, exit,
+                              break_info.break_block());
   }
 }
 
 
 bool HGraphBuilder::ShouldPeel(HSubgraph* cond, HSubgraph* body) {
   return FLAG_use_peeling;
 }
 
 
 void HGraphBuilder::VisitWhileStatement(WhileStatement* stmt) {
   ASSERT(subgraph()->HasExit());
   subgraph()->PreProcessOsrEntry(stmt);
 
   HSubgraph* cond_graph = NULL;
   HSubgraph* body_graph = NULL;
   HSubgraph* exit_graph = NULL;
 
   // If the condition is constant true, do not generate a condition subgraph.
   if (stmt->cond()->ToBooleanIsTrue()) {
     body_graph = CreateLoopHeaderSubgraph(environment());
-    ADD_TO_SUBGRAPH(body_graph, stmt->body());
   } else {
     cond_graph = CreateLoopHeaderSubgraph(environment());
     body_graph = CreateEmptySubgraph();
     exit_graph = CreateEmptySubgraph();
     {
       SubgraphScope scope(this, cond_graph);
       VISIT_FOR_CONTROL(stmt->cond(),
                         body_graph->entry_block(),
                         exit_graph->entry_block());
       body_graph->entry_block()->SetJoinId(stmt->BodyId());
       exit_graph->entry_block()->SetJoinId(stmt->ExitId());
     }
+  }
+
+  BreakAndContinueInfo break_info(stmt);
+  { BreakStackEntry push(&break_info, this);
     ADD_TO_SUBGRAPH(body_graph, stmt->body());
   }
-
-  body_graph->ResolveContinue(stmt);
+  body_graph->ResolveContinue(stmt, break_info.continue_block());
 
   if (cond_graph != NULL) {
-    AppendPeeledWhile(stmt, cond_graph, body_graph, exit_graph);
+    AppendPeeledWhile(stmt, cond_graph, body_graph, exit_graph,
+                      break_info.break_block());
   } else {
     // TODO(fschneider): Implement peeling for endless loops as well.
-    current_subgraph_->AppendEndless(body_graph, stmt);
+    subgraph()->AppendEndless(body_graph, stmt, break_info.break_block());
   }
 }
 
 
 void HGraphBuilder::AppendPeeledWhile(IterationStatement* stmt,
                                       HSubgraph* cond_graph,
                                       HSubgraph* body_graph,
-                                      HSubgraph* exit_graph) {
+                                      HSubgraph* exit_graph,
+                                      HBasicBlock* break_block) {
   HSubgraph* loop = NULL;
   if (body_graph->HasExit() && stmt != peeled_statement_ &&
       ShouldPeel(cond_graph, body_graph)) {
     // Save the last peeled iteration statement to prevent infinite recursion.
     IterationStatement* outer_peeled_statement = peeled_statement_;
     peeled_statement_ = stmt;
     loop = CreateGotoSubgraph(body_graph->environment());
     ADD_TO_SUBGRAPH(loop, stmt);
     peeled_statement_ = outer_peeled_statement;
   }
-  current_subgraph_->AppendWhile(cond_graph, body_graph, stmt, loop,
-                                 exit_graph);
+  subgraph()->AppendWhile(cond_graph, body_graph, stmt, loop, exit_graph,
+                          break_block);
 }
 
 
 void HGraphBuilder::VisitForStatement(ForStatement* stmt) {
   // Only visit the init statement in the peeled part of the loop.
   if (stmt->init() != NULL && peeled_statement_ != stmt) {
     Visit(stmt->init());
     CHECK_BAILOUT;
   }
   ASSERT(subgraph()->HasExit());
@@ skipping 10 matching lines @@
       SubgraphScope scope(this, cond_graph);
       VISIT_FOR_CONTROL(stmt->cond(),
                         body_graph->entry_block(),
                         exit_graph->entry_block());
       body_graph->entry_block()->SetJoinId(stmt->BodyId());
       exit_graph->entry_block()->SetJoinId(stmt->ExitId());
     }
   } else {
     body_graph = CreateLoopHeaderSubgraph(environment());
   }
-  ADD_TO_SUBGRAPH(body_graph, stmt->body());
+  BreakAndContinueInfo break_info(stmt);
+  { BreakStackEntry push(&break_info, this);
+    ADD_TO_SUBGRAPH(body_graph, stmt->body());
+  }
 
   HSubgraph* next_graph = NULL;
-  body_graph->ResolveContinue(stmt);
+  body_graph->ResolveContinue(stmt, break_info.continue_block());
 
   if (stmt->next() != NULL && body_graph->HasExit()) {
     next_graph = CreateGotoSubgraph(body_graph->environment());
     ADD_TO_SUBGRAPH(next_graph, stmt->next());
-    body_graph->Append(next_graph, NULL);
+    body_graph->Append(next_graph, NULL, NULL);
     next_graph->entry_block()->SetJoinId(stmt->ContinueId());
   }
 
   if (cond_graph != NULL) {
-    AppendPeeledWhile(stmt, cond_graph, body_graph, exit_graph);
+    AppendPeeledWhile(stmt, cond_graph, body_graph, exit_graph,
+                      break_info.break_block());
   } else {
-    current_subgraph_->AppendEndless(body_graph, stmt);
+    subgraph()->AppendEndless(body_graph, stmt, break_info.break_block());
   }
 }
 
 
 void HGraphBuilder::VisitForInStatement(ForInStatement* stmt) {
   BAILOUT("ForInStatement");
 }
 
 
 void HGraphBuilder::VisitTryCatchStatement(TryCatchStatement* stmt) {
@@ skipping 3212 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify();
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal