A simpler scheme for garbage collection of ureachable phi inputs.

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 "vm/ast_printer.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
 #include "vm/flags.h"
@@ skipping 19 matching lines @@
 
 
 FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
   : parsed_function_(parsed_function),
     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()),
+    last_used_block_id_(0),  // 0 is used for the graph entry.
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
     graph_entry_(NULL),
     inlining_context_(kNotInlining),
     exits_(NULL) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(TargetEntryInstr* entry) {
   graph_entry_->AddCatchEntry(entry);
@@ skipping 103 matching lines @@
   Instruction* false_exit = AppendFragment(false_entry, false_fragment);
 
   // 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 {
-    JoinEntryInstr* join = new JoinEntryInstr(owner()->try_index());
+    JoinEntryInstr* join =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     true_exit->Goto(join);
     false_exit->Goto(join);
     exit_ = join;
     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).
   BlockEntryInstr* body_entry = test_fragment.CreateTrueSuccessor();
   Instruction* body_exit = AppendFragment(body_entry, body_fragment);
 
   // 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(owner()->try_index());
+    JoinEntryInstr* join =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     join->set_next(test_fragment.entry());
     Goto(join);
     body_exit->Goto(join);
   }
 
   // 3. Set the exit to the graph to be the false successor of the test, a
   // fresh target node
 
   exit_ = test_fragment.CreateFalseSuccessor();
 }
@@ skipping 90 matching lines @@
   Value* load_saved_context = Bind(BuildLoadLocal(variable));
   AddInstruction(new StoreContextInstr(load_saved_context));
 }
 
 
 void TestGraphVisitor::ConnectBranchesTo(
     const GrowableArray<TargetEntryInstr**>& branches,
     JoinEntryInstr* join) const {
   ASSERT(!branches.is_empty());
   for (intptr_t i = 0; i < branches.length(); i++) {
-    TargetEntryInstr* target = new TargetEntryInstr(owner()->try_index());
+    TargetEntryInstr* target =
+        new TargetEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     *(branches[i]) = target;
     target->Goto(join);
   }
 }
 
 
 void TestGraphVisitor::IfTrueGoto(JoinEntryInstr* join) const {
   ConnectBranchesTo(true_successor_addresses_, join);
 }
 
 
 void TestGraphVisitor::IfFalseGoto(JoinEntryInstr* join) const {
   ConnectBranchesTo(false_successor_addresses_, join);
 }
 
 
 BlockEntryInstr* TestGraphVisitor::CreateSuccessorFor(
     const GrowableArray<TargetEntryInstr**>& branches) const {
   ASSERT(!branches.is_empty());
 
   if (branches.length() == 1) {
-    TargetEntryInstr* target = new TargetEntryInstr(owner()->try_index());
+    TargetEntryInstr* target =
+        new TargetEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     *(branches[0]) = target;
     return target;
   }
 
-  JoinEntryInstr* join = new JoinEntryInstr(owner()->try_index());
+  JoinEntryInstr* join =
+      new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
   ConnectBranchesTo(branches, join);
   return join;
 }
 
 
 BlockEntryInstr* TestGraphVisitor::CreateTrueSuccessor() const {
   return CreateSuccessorFor(true_successor_addresses_);
 }
 
 
@@ skipping 750 matching lines @@
   const intptr_t len = node->case_expressions()->length();
   // Create case statements instructions.
   EffectGraphVisitor for_case_statements(owner(), temp_index());
   // Compute start of 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()->try_index());
+      statement_start =
+          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
       node->label()->set_join_for_continue(statement_start);
     }
   } else {
-    statement_start = new JoinEntryInstr(owner()->try_index());
+    statement_start =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
   }
   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 25 matching lines @@
   // Handle last (or only) case: false goes to exit or to statement if this
   // node contains default.
   if (len > 0) {
     ASSERT(next_target != NULL);
     if (node->contains_default()) {
       // True and false go to statement start.
       next_target->Goto(statement_start);
       exit_instruction = statement_exit;
     } else {
       if (statement_exit != NULL) {
-        JoinEntryInstr* join = new JoinEntryInstr(owner()->try_index());
+        JoinEntryInstr* join = new JoinEntryInstr(owner()->AllocateBlockId(),
+                                                  owner()->try_index());
         statement_exit->Goto(join);
         next_target->Goto(join);
         exit_instruction = join;
       } else {
         exit_instruction = next_target;
       }
     }
   } else {
     // A CaseNode without case expressions must contain default.
     ASSERT(node->contains_default());
@@ skipping 63 matching lines @@
       new CheckStackOverflowInstr(node->token_pos()));
   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(owner()->try_index());
+  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();
   if ((body_exit != NULL) || (join != NULL)) {
-    if (join == NULL) join = new JoinEntryInstr(owner()->try_index());
+    if (join == NULL) {
+      join =
+          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
+    }
     join->set_next(for_test.entry());
     if (body_exit != NULL) {
       body_exit->Goto(join);
     }
   }
 
 
   for_test.IfTrueGoto(body_entry_join);
   if (node->label()->join_for_break() == NULL) {
     exit_ = for_test.CreateFalseSuccessor();
@@ skipping 46 matching lines @@
     loop_increment_end = for_body.exit();
     // 'for_body' contains at least the stack check.
     ASSERT(loop_increment_end != NULL);
   } else {
     loop_increment_end = 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(owner()->try_index());
+    JoinEntryInstr* loop_start =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     Goto(loop_start);
     loop_increment_end->Goto(loop_start);
     exit_ = loop_start;
   }
 
   if (node->condition() == NULL) {
     // Endless loop, no test.
-    JoinEntryInstr* body_entry = new JoinEntryInstr(owner()->try_index());
+    JoinEntryInstr* body_entry =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     AppendFragment(body_entry, for_body);
     Goto(body_entry);
     if (node->label()->join_for_break() != NULL) {
       // Control flow of ForLoop continues into join_for_break.
       exit_ = node->label()->join_for_break();
     }
   } else {
     TestGraphVisitor for_test(owner(),
                               temp_index(),
                               node->condition()->token_pos());
@@ skipping 47 matching lines @@
   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) {
     if (node->label()->join_for_break() == NULL) {
       node->label()->set_join_for_break(
-          new JoinEntryInstr(owner()->try_index()));
+          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index()));
     }
     jump_target = node->label()->join_for_break();
   } else {
     if (node->label()->join_for_continue() == NULL) {
       node->label()->set_join_for_continue(
-          new JoinEntryInstr(owner()->try_index()));
+          new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index()));
     }
     jump_target = node->label()->join_for_continue();
   }
   Goto(jump_target);
 }
 
 
 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) {
   UNREACHABLE();
 }
@@ skipping 1066 matching lines @@
   intptr_t try_index = owner()->AllocateTryIndex();
   owner()->set_try_index(try_index);
 
   // Preserve CTX into local variable '%saved_context'.
   BuildStoreContext(node->context_var());
 
   EffectGraphVisitor for_try_block(owner(), temp_index());
   node->try_block()->Visit(&for_try_block);
 
   if (for_try_block.is_open()) {
-    JoinEntryInstr* after_try = new JoinEntryInstr(old_try_index);
+    JoinEntryInstr* after_try =
+        new JoinEntryInstr(owner()->AllocateBlockId(), old_try_index);
     for_try_block.Goto(after_try);
     for_try_block.exit_ = after_try;
   }
 
-  JoinEntryInstr* try_entry = new JoinEntryInstr(try_index);
+  JoinEntryInstr* try_entry =
+      new JoinEntryInstr(owner()->AllocateBlockId(), try_index);
 
   Goto(try_entry);
   AppendFragment(try_entry, for_try_block);
   exit_ = for_try_block.exit_;
 
   // We are done generating code for the try block.
   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());
     catch_block->Visit(&for_catch_block);
-    TargetEntryInstr* catch_entry = new TargetEntryInstr(old_try_index,
-                                                         try_index);
+    TargetEntryInstr* catch_entry =
+        new TargetEntryInstr(owner()->AllocateBlockId(), old_try_index);
+    catch_entry->set_catch_try_index(try_index);
     owner()->AddCatchEntry(catch_entry);
     ASSERT(!for_catch_block.is_open());
     AppendFragment(catch_entry, for_catch_block);
     if (node->end_catch_label() != NULL) {
       JoinEntryInstr* join = node->end_catch_label()->join_for_continue();
       if (join != NULL) {
         if (is_open()) Goto(join);
         exit_ = join;
       }
     }
@@ skipping 49 matching lines @@
   InlineBailout("EffectGraphVisitor::VisitInlinedFinallyNode (exception)");
   const intptr_t try_index = owner()->try_index();
   if (try_index >= 0) {
     // We are about to generate code for an inlined finally block. Exceptions
     // thrown in this block of code should be treated as though they are
     // thrown not from the current try block but the outer try block if any.
     owner()->set_try_index((try_index - 1));
   }
   BuildLoadContext(node->context_var());
 
-  JoinEntryInstr* finally_entry = new JoinEntryInstr(owner()->try_index());
+  JoinEntryInstr* finally_entry =
+      new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
   EffectGraphVisitor for_finally_block(owner(), temp_index());
   node->finally_block()->Visit(&for_finally_block);
 
   if (try_index >= 0) {
     owner()->set_try_index(try_index);
   }
 
   if (for_finally_block.is_open()) {
-    JoinEntryInstr* after_finally = new JoinEntryInstr(owner()->try_index());
+    JoinEntryInstr* after_finally =
+        new JoinEntryInstr(owner()->AllocateBlockId(), owner()->try_index());
     for_finally_block.Goto(after_finally);
     for_finally_block.exit_ = after_finally;
   }
 
   Goto(finally_entry);
   AppendFragment(finally_entry, for_finally_block);
   exit_ = for_finally_block.exit_;
 }
 
 
 FlowGraph* FlowGraphBuilder::BuildGraph(InliningContext context) {
   if (FLAG_print_ast) {
     // Print the function ast before IL generation.
     AstPrinter::PrintFunctionNodes(parsed_function());
   }
   // Set the inlining context.
   ASSERT(inlining_context_ == kNotInlining);
   inlining_context_ = context;
   if (InInliningContext()) exits_ = new ZoneGrowableArray<ReturnInstr*>();
   // Compilation can be nested, preserve the computation-id.
   const Function& function = parsed_function().function();
-  TargetEntryInstr* normal_entry = new TargetEntryInstr(
-      CatchClauseNode::kInvalidTryIndex);
+  TargetEntryInstr* normal_entry =
+      new TargetEntryInstr(AllocateBlockId(),
+                           CatchClauseNode::kInvalidTryIndex);
   graph_entry_ = new GraphEntryInstr(normal_entry);
   EffectGraphVisitor for_effect(this, 0);
   if (InInliningContext()) {
     exits_ = new ZoneGrowableArray<ReturnInstr*>();
   }
   // TODO(kmillikin): We can eliminate stack checks in some cases (e.g., the
   // stack check on entry for leaf routines).
   Instruction* check = new CheckStackOverflowInstr(function.token_pos());
   // If we are inlining don't actually attach the stack check. We must still
   // create the stack check inorder to allocate a deopt id.
@@ skipping 14 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