Recognize basic block entries in the flow graph.

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/flags.h"
 #include "vm/intermediate_language.h"
 #include "vm/os.h"
 #include "vm/parser.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, trace_bailout, false, "Print bailout from graph builder.");
 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph.");
 DECLARE_FLAG(bool, enable_type_checks);
 
 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()->set_successor(other_fragment.entry());
+    exit()->SetSuccessor(other_fragment.entry());
     exit_ = other_fragment.exit();
   }
 }
 
 
 void EffectGraphVisitor::AddInstruction(Instruction* instruction) {
   ASSERT(is_open());
   if (is_empty()) {
     entry_ = exit_ = instruction;
   } else {
-    exit()->set_successor(instruction);
+    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.
   Append(test_fragment);
 
   // 2. Connect the true and false bodies to the test if they are reachable,
   // and if so record their exits (if any).
   if (test_fragment.can_be_true()) {
     Instruction* true_exit = NULL;
     Instruction* false_exit = NULL;
     TargetEntryInstr* true_entry = new TargetEntryInstr();
     *test_fragment.true_successor_address() = true_entry;
-    true_entry->set_successor(true_fragment.entry());
+    true_entry->SetSuccessor(true_fragment.entry());
     true_exit = true_fragment.is_empty() ? true_entry : true_fragment.exit();
 
     TargetEntryInstr* false_entry = new TargetEntryInstr();
     *test_fragment.false_successor_address() = false_entry;
-    false_entry->set_successor(false_fragment.entry());
+    false_entry->SetSuccessor(false_fragment.entry());
     false_exit =
         false_fragment.is_empty() ? false_entry : false_fragment.exit();
 
     exit_ = new JoinEntryInstr();
-    true_exit->set_successor(exit_);
-    false_exit->set_successor(exit_);
+    true_exit->SetSuccessor(exit_);
+    false_exit->SetSuccessor(exit_);
   }
 }
 
 
 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;
   if (test_fragment.can_be_true()) {
     TargetEntryInstr* body_entry = new TargetEntryInstr();
     *test_fragment.true_successor_address() = body_entry;
-    body_entry->set_successor(body_fragment.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);
-    join->set_successor(test_fragment.entry());
-    body_exit->set_successor(join);
+    join->SetSuccessor(test_fragment.entry());
+    body_exit->SetSuccessor(join);
   }
 
   // 3. Set the exit to the graph to be empty or a fresh target node
   // depending on whether the false branch of the test is reachable.
   if (test_fragment.can_be_false()) {
     exit_ = *test_fragment.false_successor_address() = new TargetEntryInstr();
   } else {
     exit_ = NULL;
   }
 }
@@ skipping 750 matching lines @@
   }
 }
 
 
 void FlowGraphBuilder::PrintGraph() const {
   if (!FLAG_print_flow_graph || HasBailedOut()) return;
 
   OS::Print("==== %s\n",
             parsed_function().function().ToFullyQualifiedCString());
 
-  for (intptr_t i = postorder_.length() - 1; i >= 0; --i) {
-    OS::Print("%8d: ", postorder_.length() - i);
-    postorder_[i]->Print(i, postorder_);
+  for (intptr_t i = postorder_block_entries_.length() - 1; i >= 0; --i) {
+    // Print the block entry.
+    Instruction* current = postorder_block_entries_[i]->Print();
+    // And all the successors until an exit, branch, or a block entry.
+    while (current != NULL && !current->IsBlockEntry()) {

[srdjan, 2012/02/22 17:41:10]

More parenthesis, please

[Kevin Millikin (Google), 2012/02/23 09:08:04]

Thanks for the reminder.

+      OS::Print("\n");
+      current = current->Print();
+    }
+    if (current != NULL && current->IsBlockEntry()) {
+      OS::Print(" goto %d", current->GetBlockNumber());
+    }
     OS::Print("\n");
   }
-  OS::Print("\n");
 }
 
 
 void FlowGraphBuilder::BuildGraph() {
   EffectGraphVisitor for_effect(this, 0);
+  for_effect.AddInstruction(new TargetEntryInstr());
   parsed_function().node_sequence()->Visit(&for_effect);
   TraceBailout();
   if (!HasBailedOut() && (for_effect.entry() != NULL)) {
-    for_effect.entry()->Postorder(&postorder_);
+    // Accumulate basic block entries via postorder traversal.
+    for_effect.entry()->Postorder(&postorder_block_entries_);
+    // Number the blocks in reverse postorder starting with 0.
+    intptr_t index = postorder_block_entries_.length() - 1;

[srdjan, 2012/02/22 17:41:10]

AS a for loop maybe?

intptr_t number = 0;
for (intptr_t index = postorder_block_entries_.length() - 1;
    i >=0; index--) {

}

[Kevin Millikin (Google), 2012/02/23 09:08:04]

Done.

+    intptr_t number = 0;
+    while (index >= 0) {
+      postorder_block_entries_[index--]->SetBlockNumber(number++);
+    }
   }
   PrintGraph();
 }
 
 }  // namespace dart