Add a goto instruction to the IL use it to terminate basic blocks.

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 "vm/ast_printer.h"
 #include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 33 matching lines @@
 }
 
 
 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) {
   ASSERT(is_open());
   if (other_fragment.is_empty()) return;
   if (is_empty()) {
     entry_ = other_fragment.entry();
     exit_ = other_fragment.exit();
   } else {
-    exit()->SetSuccessor(other_fragment.entry());
+    Instruction* successor = other_fragment.entry();
+    exit()->SetSuccessor(successor->IsBlockEntry()
+                         ? new GotoInstr(successor->AsBlockEntry())
+                         : successor);
     exit_ = other_fragment.exit();
   }
   temp_index_ = other_fragment.temp_index();
 }
 
 
 void EffectGraphVisitor::AddInstruction(Instruction* instruction) {
   ASSERT(is_open());
+  ASSERT(!instruction->IsBlockEntry());
   DeallocateTempIndex(instruction->InputCount());
   if (instruction->IsDefinition()) {
     instruction->AsDefinition()->set_temp_index(AllocateTempIndex());
   }
   if (is_empty()) {
     entry_ = exit_ = instruction;
   } else {
     exit()->SetSuccessor(instruction);
     exit_ = instruction;
   }
 }
 
 
+void EffectGraphVisitor::AddBlockEntry(BlockEntryInstr* instruction) {
+  ASSERT(is_open());
+  if (is_empty()) {
+    entry_ = exit_ = instruction;
+  } else {
+    ASSERT(exit()->IsGraphEntry() ||
+           exit()->IsGoto());
+    exit()->SetSuccessor(instruction);
+    exit_ = instruction;
+  }
+}
+
+
 void EffectGraphVisitor::Join(const TestGraphVisitor& test_fragment,
                               const EffectGraphVisitor& true_fragment,
                               const EffectGraphVisitor& false_fragment) {
   // We have: a test graph fragment with zero, one, or two available exits;
   // and a pair of effect graph fragments with zero or one available exits.
   // We want to append the branch and (if necessary) a join node to this
   // graph fragment.
   ASSERT(is_open());
 
   // 1. Connect the test to this graph.
@@ skipping 15 matching lines @@
 
   // 3. Add a join or select one (or neither) of the arms as exit.
   if (true_exit == NULL) {
     exit_ = false_exit;  // May be NULL.
     if (false_exit != NULL) temp_index_ = false_fragment.temp_index();
   } else if (false_exit == NULL) {
     exit_ = true_exit;
     temp_index_ = true_fragment.temp_index();
   } else {
     exit_ = new JoinEntryInstr();
-    true_exit->SetSuccessor(exit_);
-    false_exit->SetSuccessor(exit_);
+    true_exit->SetSuccessor(new GotoInstr(exit_->AsBlockEntry()));
+    false_exit->SetSuccessor(new GotoInstr(exit_->AsBlockEntry()));
     ASSERT(true_fragment.temp_index() == false_fragment.temp_index());
     temp_index_ = true_fragment.temp_index();
   }
 }
 
 
 void EffectGraphVisitor::TieLoop(const TestGraphVisitor& test_fragment,
                                  const EffectGraphVisitor& body_fragment) {
   // We have: a test graph fragment with zero, one, or two available exits;
   // and an effect graph fragment with zero or one available exits.  We want
   // to append the 'while loop' consisting of the test graph fragment as
   // condition and the effect graph fragment as body.
   ASSERT(is_open());
 
   // 1. Connect the body to the test if it is reachable, and if so record
   // its exit (if any).
   Instruction* body_exit = NULL;
   TargetEntryInstr* body_entry = new TargetEntryInstr();
   *test_fragment.true_successor_address() = body_entry;
   body_entry->SetSuccessor(body_fragment.entry());
   body_exit = body_fragment.is_empty() ? body_entry : body_fragment.exit();
 
   // 2. Connect the test to this graph, including the body if reachable and
   // using a fresh join node if the body is reachable and has an open exit.
   if (body_exit == NULL) {
     Append(test_fragment);
   } else {
     JoinEntryInstr* join = new JoinEntryInstr();
-    AddInstruction(join);
+    AddInstruction(new GotoInstr(join));
+    AddBlockEntry(join);
     join->SetSuccessor(test_fragment.entry());
-    body_exit->SetSuccessor(join);
+    body_exit->SetSuccessor(new GotoInstr(join));
   }
 
   // 3. Set the exit to the graph to be the false successor of the test, a
   // fresh target node
   exit_ = *test_fragment.false_successor_address() = new TargetEntryInstr();
 }
 
 
 Computation* EffectGraphVisitor::BuildStoreLocal(
     const LocalVariable& local, Value* value) {
@@ skipping 802 matching lines @@
   Join(for_test, for_true, for_false);
 }
 
 
 void EffectGraphVisitor::VisitSwitchNode(SwitchNode* node) {
   EffectGraphVisitor switch_body(owner(), temp_index());
   node->body()->Visit(&switch_body);
   Append(switch_body);
   if ((node->label() != NULL) && (node->label()->join_for_break() != NULL)) {
     if (is_open()) {
-      AddInstruction(node->label()->join_for_break());
+      AddInstruction(new GotoInstr(node->label()->join_for_break()));
+      AddBlockEntry(node->label()->join_for_break());
     } else {
       exit_ = node->label()->join_for_break();
     }
   }
   // No continue label allowed.
   ASSERT((node->label() == NULL) ||
          (node->label()->join_for_continue() == NULL));
 }
 
 
@@ skipping 31 matching lines @@
     // allocate JoinNode here and use it as statement start.
     if (node->label()->join_for_continue() == NULL) {
       node->label()->set_join_for_continue(new JoinEntryInstr());
     }
     statement_start = node->label()->join_for_continue();
   } else if (needs_join_at_statement_entry) {
     statement_start = new JoinEntryInstr();
   } else {
     statement_start = new TargetEntryInstr();
   }
-  for_case_statements.AddInstruction(statement_start);
+  for_case_statements.AddBlockEntry(statement_start);
   node->statements()->Visit(&for_case_statements);
   if (is_open() && (len == 0)) {
     ASSERT(node->contains_default());
     // Default only case node.
     Append(for_case_statements);
     return;
   }
 
   // Generate instructions for all case expressions and collect data to
   // connect them.
   GrowableArray<TargetEntryInstr**> case_true_addresses;
   GrowableArray<TargetEntryInstr**> case_false_addresses;
   GrowableArray<TargetEntryInstr*> case_entries;
   for (intptr_t i = 0; i < len; i++) {
     AstNode* case_expr = node->case_expressions()->NodeAt(i);
     TestGraphVisitor for_case_expression(owner(),
                                          temp_index(),
                                          case_expr->token_pos());
     if (i == 0) {
       case_entries.Add(NULL);  // Not to be used
       case_expr->Visit(&for_case_expression);
       // Append only the first one, everything else is connected from it.
       Append(for_case_expression);
     } else {
       TargetEntryInstr* case_entry_target = new TargetEntryInstr();
       case_entries.Add(case_entry_target);
-      for_case_expression.AddInstruction(case_entry_target);
+      for_case_expression.AddBlockEntry(case_entry_target);
       case_expr->Visit(&for_case_expression);
     }
     case_true_addresses.Add(for_case_expression.true_successor_address());
     case_false_addresses.Add(for_case_expression.false_successor_address());
   }
 
   // Once a test fragment has been added, this fragment is closed.
   ASSERT(!is_open());
 
   // Connect all test cases except the last one.
   for (intptr_t i = 0; i < (len - 1); i++) {
     ASSERT(needs_join_at_statement_entry);
     *case_false_addresses[i] = case_entries[i + 1];
     TargetEntryInstr* true_target = new TargetEntryInstr();
     *case_true_addresses[i] = true_target;
-    true_target->SetSuccessor(statement_start);
+    true_target->SetSuccessor(new GotoInstr(statement_start));
   }
 
   BlockEntryInstr* exit_instruction = NULL;
   // Handle last (or only) case: false goes to exit or to statement if this
   // node contains default.
   if (len > 0) {
     if (statement_start->IsTargetEntry()) {
       *case_true_addresses[len - 1] = statement_start->AsTargetEntry();
     } else {
       TargetEntryInstr* true_target = new TargetEntryInstr();
       *case_true_addresses[len - 1] = true_target;
-      true_target->SetSuccessor(statement_start);
+      true_target->SetSuccessor(new GotoInstr(statement_start));
     }
     TargetEntryInstr* false_target = new TargetEntryInstr();
     *case_false_addresses[len - 1] = false_target;
     if (node->contains_default()) {
       // True and false go to statement start.
-      false_target->SetSuccessor(statement_start);
+      false_target->SetSuccessor(new GotoInstr(statement_start));
       if (for_case_statements.is_open()) {
         exit_instruction = new TargetEntryInstr();
-        for_case_statements.exit()->SetSuccessor(exit_instruction);
+        for_case_statements.exit()->SetSuccessor(
+            new GotoInstr(exit_instruction));
       }
     } else {
       if (for_case_statements.is_open()) {
         exit_instruction = new JoinEntryInstr();
-        for_case_statements.exit()->SetSuccessor(exit_instruction);
+        for_case_statements.exit()->SetSuccessor(
+            new GotoInstr(exit_instruction));
       } else {
         exit_instruction = new TargetEntryInstr();
       }
-      false_target->SetSuccessor(exit_instruction);
+      false_target->SetSuccessor(new GotoInstr(exit_instruction));
     }
   } else {
     // A CaseNode without case expressions must contain default.
     ASSERT(node->contains_default());
-    AddInstruction(statement_start);
+    AddInstruction(new GotoInstr(statement_start));
+    AddBlockEntry(statement_start);
   }
 
   ASSERT(!is_open());
   exit_ = exit_instruction;
 }
 
 
 // <Statement> ::= While { label:     SourceLabel
 //                         condition: <Expression>
 //                         body:      <Sequence> }
@@ skipping 15 matching lines @@
   EffectGraphVisitor for_body(owner(), temp_index());
   CheckStackOverflowComp* comp =
       new CheckStackOverflowComp(node->token_pos(), owner()->try_index());
   for_body.AddInstruction(new DoInstr(comp));
   node->body()->Visit(&for_body);
 
   // Labels are set after body traversal.
   SourceLabel* lbl = node->label();
   ASSERT(lbl != NULL);
   if (lbl->join_for_continue() != NULL) {
-    AddInstruction(lbl->join_for_continue());
+    AddInstruction(new GotoInstr(lbl->join_for_continue()));
+    AddBlockEntry(lbl->join_for_continue());
   }
   TieLoop(for_test, for_body);
   if (lbl->join_for_break() != NULL) {
-    AddInstruction(lbl->join_for_break());
+    AddInstruction(new GotoInstr(lbl->join_for_break()));
+    AddBlockEntry(lbl->join_for_break());
   }
 }
 
 
 // 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) {
   // Traverse body first in order to generate continue and break labels.
   EffectGraphVisitor for_body(owner(), temp_index());
   CheckStackOverflowComp* comp =
       new CheckStackOverflowComp(node->token_pos(), owner()->try_index());
   for_body.AddInstruction(new DoInstr(comp));
   node->body()->Visit(&for_body);
 
   TestGraphVisitor for_test(owner(),
                             temp_index(),
                             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();
-  AddInstruction(body_entry_join);
+  AddInstruction(new GotoInstr(body_entry_join));
+  AddBlockEntry(body_entry_join);
   body_entry_join->SetSuccessor(for_body.entry());
   Instruction* body_exit =
       for_body.is_empty() ? body_entry_join : for_body.exit();
 
   if (for_body.is_open() || (node->label()->join_for_continue() != NULL)) {
     BlockEntryInstr* test_entry = NULL;
     if (node->label()->join_for_continue() == NULL) {
       test_entry = new TargetEntryInstr();
     } else {
       test_entry = node->label()->join_for_continue();
     }
     test_entry->SetSuccessor(for_test.entry());
     if (body_exit != NULL) {
-      body_exit->SetSuccessor(test_entry);
+      body_exit->SetSuccessor(new GotoInstr(test_entry));
     }
   }
 
   TargetEntryInstr* back_target_entry = new TargetEntryInstr();
   *for_test.true_successor_address() = back_target_entry;
-  back_target_entry->SetSuccessor(body_entry_join);
+  back_target_entry->SetSuccessor(new GotoInstr(body_entry_join));
   TargetEntryInstr* loop_exit_target = new TargetEntryInstr();
   *for_test.false_successor_address() = loop_exit_target;
   if (node->label()->join_for_break() == NULL) {
     exit_ = loop_exit_target;
   } else {
-    loop_exit_target->SetSuccessor(node->label()->join_for_break());
+    loop_exit_target->SetSuccessor(
+        new GotoInstr(node->label()->join_for_break()));
     exit_ = node->label()->join_for_break();
   }
 }
 
 
 // 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(), temp_index());
   node->initializer()->Visit(&for_initializer);
   Append(for_initializer);
   ASSERT(is_open());
 
   // Compose body to set any jump labels.
   EffectGraphVisitor for_body(owner(), temp_index());
   TargetEntryInstr* body_entry = new TargetEntryInstr();
-  for_body.AddInstruction(body_entry);
+  for_body.AddBlockEntry(body_entry);
   CheckStackOverflowComp* comp =
       new CheckStackOverflowComp(node->token_pos(), owner()->try_index());
   for_body.AddInstruction(new DoInstr(comp));
   node->body()->Visit(&for_body);
 
   // Join loop body, increment and compute their end instruction.
   ASSERT(!for_body.is_empty());
   Instruction* loop_increment_end = NULL;
   EffectGraphVisitor for_increment(owner(), temp_index());
   if ((node->label()->join_for_continue() == NULL) && for_body.is_open()) {
     // Do not insert an extra basic block.
     node->increment()->Visit(&for_increment);
     for_body.Append(for_increment);
     loop_increment_end = for_body.exit();
     // 'for_body' contains at least the TargetInstruction 'body_entry'.
     ASSERT(loop_increment_end != NULL);
   } else if (node->label()->join_for_continue() != NULL) {
     // Insert join between body and increment.
     if (for_body.is_open()) {
-      for_body.exit()->SetSuccessor(node->label()->join_for_continue());
+      for_body.exit()->SetSuccessor(
+          new GotoInstr(node->label()->join_for_continue()));
     }
-    for_increment.AddInstruction(node->label()->join_for_continue());
+    for_increment.AddBlockEntry(node->label()->join_for_continue());
     node->increment()->Visit(&for_increment);
     loop_increment_end = for_increment.exit();
     ASSERT(loop_increment_end != NULL);
   } else {
     loop_increment_end = NULL;
     ASSERT(!for_body.is_open() && node->label()->join_for_continue() == NULL);
   }
 
   // 'loop_increment_end' is NULL only if there is no join for continue and the
   // body is not open, i.e., no backward branch exists.
   if (loop_increment_end != NULL) {
     JoinEntryInstr* loop_start = new JoinEntryInstr();
-    AddInstruction(loop_start);
-    loop_increment_end->SetSuccessor(loop_start);
+    AddInstruction(new GotoInstr(loop_start));
+    AddBlockEntry(loop_start);
+    loop_increment_end->SetSuccessor(new GotoInstr(loop_start));
   }
 
   if (node->condition() == NULL) {
     // Endless loop, no test.
     Append(for_body);
     if (node->label()->join_for_break() == NULL) {
       CloseFragment();
     } else {
       // Control flow of ForLoop continues into join_for_break.
       exit_ = node->label()->join_for_break();
     }
   } else {
     TargetEntryInstr* loop_exit = new TargetEntryInstr();
     TestGraphVisitor for_test(owner(),
                               temp_index(),
                               node->condition()->token_pos());
     node->condition()->Visit(&for_test);
     Append(for_test);
     *for_test.true_successor_address() = body_entry;
     *for_test.false_successor_address() = loop_exit;
     if (node->label()->join_for_break() == NULL) {
       exit_ = loop_exit;
     } else {
-      loop_exit->SetSuccessor(node->label()->join_for_break());
+      loop_exit->SetSuccessor(new GotoInstr(node->label()->join_for_break()));
       exit_ = node->label()->join_for_break();
     }
   }
 }
 
 
 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
   for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) {
     EffectGraphVisitor for_effect(owner(), temp_index());
     node->InlinedFinallyNodeAt(i)->Visit(&for_effect);
@@ skipping 22 matching lines @@
       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();
   }
 
-  Instruction* jump_target = NULL;
+  BlockEntryInstr* jump_target = NULL;
   if (node->kind() == Token::kBREAK) {
     if (node->label()->join_for_break() == NULL) {
       node->label()->set_join_for_break(new JoinEntryInstr());
     }
     jump_target = node->label()->join_for_break();
   } else {
     if (node->label()->join_for_continue() == NULL) {
       node->label()->set_join_for_continue(new JoinEntryInstr());
     }
     jump_target = node->label()->join_for_continue();
   }
-  AddInstruction(jump_target);
+  AddInstruction(new GotoInstr(jump_target));
+  AddBlockEntry(jump_target);
   CloseFragment();
 }
 
 
 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) {
   UNREACHABLE();
 }
 
 
 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) {
@@ skipping 875 matching lines @@
   }
 
   // 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()) {
-      AddInstruction(node->label()->join_for_break());
+      AddInstruction(new GotoInstr(node->label()->join_for_break()));
+      AddBlockEntry(node->label()->join_for_break());
     } else {
       exit_ = node->label()->join_for_break();
     }
   }
 
   // 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);
 }
@@ skipping 30 matching lines @@
   owner()->set_try_index(old_try_index);
 
   CatchClauseNode* catch_block = node->catch_block();
   if (catch_block != NULL) {
     // Set the corresponding try index for this catch block so
     // that we can set the appropriate handler pc when we generate
     // code for this catch block.
     catch_block->set_try_index(try_index);
     EffectGraphVisitor for_catch_block(owner(), temp_index());
     TargetEntryInstr* catch_entry = new TargetEntryInstr(try_index);
-    for_catch_block.AddInstruction(catch_entry);
+    for_catch_block.AddBlockEntry(catch_entry);
     catch_block->Visit(&for_catch_block);
     owner()->AddCatchEntry(catch_entry);
     ASSERT(!for_catch_block.is_open());
     if ((node->end_catch_label() != NULL) &&
         (node->end_catch_label()->join_for_continue() != NULL)) {
       if (is_open()) {
-        AddInstruction(node->end_catch_label()->join_for_continue());
+        AddInstruction(
+            new GotoInstr(node->end_catch_label()->join_for_continue()));
+        AddBlockEntry(node->end_catch_label()->join_for_continue());
       } else {
         exit_ = node->end_catch_label()->join_for_continue();
       }
     }
   }
 
   // Generate code for the finally block if one exists.
   if ((node->finally_block() != NULL) && is_open()) {
     EffectGraphVisitor for_finally_block(owner(), temp_index());
     node->finally_block()->Visit(&for_finally_block);
@@ skipping 60 matching lines @@
 void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) {
   if (FLAG_print_ast) {
     // Print the function ast before IL generation.
     AstPrinter::PrintFunctionNodes(parsed_function());
   }
   // Compilation can be nested, preserve the computation-id.
   const Function& function = parsed_function().function();
   TargetEntryInstr* normal_entry = new TargetEntryInstr();
   graph_entry_ = new GraphEntryInstr(normal_entry);
   EffectGraphVisitor for_effect(this, 0);
-  for_effect.AddInstruction(normal_entry);
+  for_effect.AddBlockEntry(normal_entry);
   parsed_function().node_sequence()->Visit(&for_effect);
   // Check that the graph is properly terminated.
   ASSERT(!for_effect.is_open());
   GrowableArray<intptr_t> parent;
   GrowableArray<BitVector*> assigned_vars;
   intptr_t variable_count = parsed_function_.function().num_fixed_parameters() +
       parsed_function_.copied_parameter_count() +
       parsed_function_.stack_local_count();
   // Perform a depth-first traversal of the graph to build preorder and
   // postorder block orders.
@@ skipping 388 matching lines @@
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(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