From 14e185b31b322b518c586ef8fd9c4445fa8e6dbb Mon Sep 17 00:00:00 2001 From: "kmillikin@chromium.org" Date: Tue, 22 Feb 2011 08:40:10 +0000 Subject: [PATCH] Change the translation of break/continue into Hydrogen. Resolve break and continue when we see them, rather then deferring them until later. Review URL: http://codereview.chromium.org/6541060 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@6878 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen.cc | 185 ++++++++++++++++++++++++++++++-------------------------- src/hydrogen.h | 112 +++++++++++++++++++++------------- 2 files changed, 168 insertions(+), 129 deletions(-) diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 1aa05e5..6c4035c 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -502,47 +502,13 @@ void HSubgraph::AppendJoin(HSubgraph* then_graph, } -void HSubgraph::ResolveContinue(IterationStatement* statement) { - HBasicBlock* continue_block = BundleContinue(statement); +void HSubgraph::ResolveContinue(IterationStatement* statement, + HBasicBlock* continue_block) { if (continue_block != NULL) { - exit_block_ = JoinBlocks(exit_block(), - continue_block, - statement->ContinueId()); + continue_block->SetJoinId(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* infos = break_continue_info(); - 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; + exit_block_ = + JoinBlocks(exit_block(), continue_block, statement->ContinueId()); } @@ -557,11 +523,13 @@ HBasicBlock* HSubgraph::JoinBlocks(HBasicBlock* a, HBasicBlock* b, int id) { } -void HSubgraph::AppendEndless(HSubgraph* body, IterationStatement* statement) { +void HSubgraph::AppendEndless(HSubgraph* body, + IterationStatement* statement, + HBasicBlock* break_block) { ConnectExitTo(body->entry_block()); - body->ResolveContinue(statement); 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); } @@ -569,11 +537,11 @@ void HSubgraph::AppendEndless(HSubgraph* body, IterationStatement* 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); @@ -584,10 +552,11 @@ 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()); @@ -604,13 +573,15 @@ void HSubgraph::AppendWhile(HSubgraph* condition, } -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()); } } @@ -624,16 +595,6 @@ void HSubgraph::FinishExit(HControlInstruction* instruction) { } -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), @@ -2113,7 +2074,6 @@ class HGraphBuilder::SubgraphScope BASE_EMBEDDED { } ~SubgraphScope() { - old_subgraph_->AddBreakContinueInfo(subgraph_); builder_->current_subgraph_ = old_subgraph_; } @@ -2195,7 +2155,7 @@ HGraph* HGraphBuilder::CreateGraph(CompilationInfo* info) { 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()) { @@ -2397,8 +2357,11 @@ HSubgraph* HGraphBuilder::CreateLoopHeaderSubgraph(HEnvironment* env) { 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); + { BreakAndContinueScope push(&break_info, this); + ADD_TO_SUBGRAPH(block_graph, stmt->statements()); + } + subgraph()->Append(block_graph, stmt, break_info.break_block()); } else { VisitStatements(stmt->statements()); } @@ -2439,13 +2402,48 @@ void HGraphBuilder::VisitIfStatement(IfStatement* stmt) { } +HBasicBlock* HGraphBuilder::BreakAndContinueScope::Get( + BreakableStatement* stmt, + BreakType type) { + BreakAndContinueScope* 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_scope()->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_scope()->Get(stmt->target(), BREAK); + subgraph()->exit_block()->Goto(break_block); + subgraph()->set_exit_block(NULL); } @@ -2628,10 +2626,13 @@ void HGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) { } 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); + { BreakAndContinueScope 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)); } } @@ -2698,11 +2699,14 @@ void HGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) { subgraph()->PreProcessOsrEntry(stmt); HSubgraph* body_graph = CreateLoopHeaderSubgraph(environment()); - ADD_TO_SUBGRAPH(body_graph, stmt->body()); - body_graph->ResolveContinue(stmt); + BreakAndContinueInfo break_info(stmt); + { BreakAndContinueScope 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(); @@ -2714,7 +2718,8 @@ void HGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) { 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()); } } @@ -2735,7 +2740,6 @@ void HGraphBuilder::VisitWhileStatement(WhileStatement* stmt) { // 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(); @@ -2748,16 +2752,20 @@ void HGraphBuilder::VisitWhileStatement(WhileStatement* stmt) { body_graph->entry_block()->SetJoinId(stmt->BodyId()); exit_graph->entry_block()->SetJoinId(stmt->ExitId()); } - ADD_TO_SUBGRAPH(body_graph, stmt->body()); } - body_graph->ResolveContinue(stmt); + BreakAndContinueInfo break_info(stmt); + { BreakAndContinueScope push(&break_info, this); + ADD_TO_SUBGRAPH(body_graph, stmt->body()); + } + 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()); } } @@ -2765,7 +2773,8 @@ void HGraphBuilder::VisitWhileStatement(WhileStatement* stmt) { 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)) { @@ -2776,8 +2785,8 @@ void HGraphBuilder::AppendPeeledWhile(IterationStatement* stmt, 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); } @@ -2808,22 +2817,26 @@ void HGraphBuilder::VisitForStatement(ForStatement* stmt) { } else { body_graph = CreateLoopHeaderSubgraph(environment()); } - ADD_TO_SUBGRAPH(body_graph, stmt->body()); + BreakAndContinueInfo break_info(stmt); + { BreakAndContinueScope 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()); } } diff --git a/src/hydrogen.h b/src/hydrogen.h index f8ec150..8a5e8df 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -196,8 +196,7 @@ class HSubgraph: public ZoneObject { explicit HSubgraph(HGraph* graph) : graph_(graph), entry_block_(NULL), - exit_block_(NULL), - break_continue_info_(4) { + exit_block_(NULL) { } HGraph* graph() const { return graph_; } @@ -215,23 +214,24 @@ class HSubgraph: public ZoneObject { HSubgraph* body, IterationStatement* statement, HSubgraph* continue_subgraph, - HSubgraph* exit); + HSubgraph* exit, + HBasicBlock* break_block); void AppendDoWhile(HSubgraph* body, IterationStatement* statement, HSubgraph* go_back, - HSubgraph* exit); - void AppendEndless(HSubgraph* body, IterationStatement* statement); - void Append(HSubgraph* next, BreakableStatement* statement); - void ResolveContinue(IterationStatement* statement); - HBasicBlock* BundleBreak(BreakableStatement* statement); - HBasicBlock* BundleContinue(IterationStatement* statement); - HBasicBlock* BundleBreakContinue(BreakableStatement* statement, - bool is_continue, - int join_id); + HSubgraph* exit, + HBasicBlock* break_block); + void AppendEndless(HSubgraph* body, + IterationStatement* statement, + HBasicBlock* break_block); + void Append(HSubgraph* next, + BreakableStatement* stmt, + HBasicBlock* break_block); + void ResolveContinue(IterationStatement* statement, + HBasicBlock* continue_block); HBasicBlock* JoinBlocks(HBasicBlock* a, HBasicBlock* b, int id); void FinishExit(HControlInstruction* instruction); - void FinishBreakContinue(BreakableStatement* target, bool is_continue); void Initialize(HBasicBlock* block) { ASSERT(entry_block_ == NULL); entry_block_ = block; @@ -249,38 +249,10 @@ class HSubgraph: public ZoneObject { } } - void AddBreakContinueInfo(HSubgraph* other) { - break_continue_info_.AddAll(other->break_continue_info_); - } - protected: - class BreakContinueInfo: public ZoneObject { - public: - BreakContinueInfo(BreakableStatement* target, HBasicBlock* block, - bool is_continue) - : target_(target), block_(block), continue_(is_continue) {} - BreakableStatement* target() const { return target_; } - HBasicBlock* block() const { return block_; } - bool is_continue() const { return continue_; } - bool IsResolved() const { return block_ == NULL; } - void Resolve() { block_ = NULL; } - - private: - BreakableStatement* target_; - HBasicBlock* block_; - bool continue_; - }; - - const ZoneList* break_continue_info() const { - return &break_continue_info_; - } - HGraph* graph_; // The graph this is a subgraph of. HBasicBlock* entry_block_; HBasicBlock* exit_block_; - - private: - ZoneList break_continue_info_; }; @@ -618,6 +590,53 @@ class TestContext: public AstContext { class HGraphBuilder: public AstVisitor { public: + enum BreakType { BREAK, CONTINUE }; + + // A class encapsulating (lazily-allocated) break and continue blocks for + // a breakable statement. Separated from BreakAndContinueScope so that it + // can have a separate lifetime. + class BreakAndContinueInfo BASE_EMBEDDED { + public: + explicit BreakAndContinueInfo(BreakableStatement* target) + : target_(target), break_block_(NULL), continue_block_(NULL) { + } + + BreakableStatement* target() { return target_; } + HBasicBlock* break_block() { return break_block_; } + void set_break_block(HBasicBlock* block) { break_block_ = block; } + HBasicBlock* continue_block() { return continue_block_; } + void set_continue_block(HBasicBlock* block) { continue_block_ = block; } + + private: + BreakableStatement* target_; + HBasicBlock* break_block_; + HBasicBlock* continue_block_; + }; + + // A helper class to maintain a stack of current BreakAndContinueInfo + // structures mirroring BreakableStatement nesting. + class BreakAndContinueScope BASE_EMBEDDED { + public: + BreakAndContinueScope(BreakAndContinueInfo* info, HGraphBuilder* owner) + : info_(info), owner_(owner), next_(owner->break_scope()) { + owner->set_break_scope(this); + } + + ~BreakAndContinueScope() { owner_->set_break_scope(next_); } + + BreakAndContinueInfo* info() { return info_; } + HGraphBuilder* owner() { return owner_; } + BreakAndContinueScope* next() { return next_; } + + // Search the break stack for a break or continue target. + HBasicBlock* Get(BreakableStatement* stmt, BreakType type); + + private: + BreakAndContinueInfo* info_; + HGraphBuilder* owner_; + BreakAndContinueScope* next_; + }; + explicit HGraphBuilder(TypeFeedbackOracle* oracle) : oracle_(oracle), graph_(NULL), @@ -626,13 +645,17 @@ class HGraphBuilder: public AstVisitor { ast_context_(NULL), call_context_(NULL), function_return_(NULL), - inlined_count_(0) { } + inlined_count_(0), + break_scope_(NULL) { + } HGraph* CreateGraph(CompilationInfo* info); // Simple accessors. HGraph* graph() const { return graph_; } HSubgraph* subgraph() const { return current_subgraph_; } + BreakAndContinueScope* break_scope() const { return break_scope_; } + void set_break_scope(BreakAndContinueScope* head) { break_scope_ = head; } HEnvironment* environment() const { return subgraph()->environment(); } HBasicBlock* CurrentBlock() const { return subgraph()->exit_block(); } @@ -682,7 +705,8 @@ class HGraphBuilder: public AstVisitor { void AppendPeeledWhile(IterationStatement* stmt, HSubgraph* cond_graph, HSubgraph* body_graph, - HSubgraph* exit_graph); + HSubgraph* exit_graph, + HBasicBlock* break_block); void AddToSubgraph(HSubgraph* graph, ZoneList* stmts); void AddToSubgraph(HSubgraph* graph, Statement* stmt); @@ -858,6 +882,8 @@ class HGraphBuilder: public AstVisitor { int inlined_count_; + BreakAndContinueScope* break_scope_; + friend class AstContext; // Pushes and pops the AST context stack. DISALLOW_COPY_AND_ASSIGN(HGraphBuilder); -- 2.7.4