Compute preorder as well as postorder basic block orderings.

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/flags.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
@@ skipping 1310 matching lines @@
 
 
 void EffectGraphVisitor::VisitInlinedFinallyNode(InlinedFinallyNode* node) {
   Bailout("EffectGraphVisitor::VisitInlinedFinallyNode");
 }
 
 
 // Graph printing.
 class FlowGraphPrinter : public FlowGraphVisitor {
  public:
-  explicit FlowGraphPrinter(const Function& function) : function_(function) { }
+  explicit FlowGraphPrinter(const Function& function,
+                            const GrowableArray<BlockEntryInstr*>& block_order)

[srdjan, 2012/03/16 22:01:17]

remove explicit. 

[Kevin Millikin (Google), 2012/03/16 22:18:32]

Thanks.

+      : FlowGraphVisitor(block_order), function_(function) { }
 
   virtual ~FlowGraphPrinter() {}
 
   // Print the instructions in a block terminated by newlines.  Add "goto N"
   // to the end of the block if it ends with an unconditional jump to
   // another block and that block is not next in reverse postorder.
-  void VisitBlocks(const GrowableArray<BlockEntryInstr*>& block_order);
+  void VisitBlocks();
 
   // Visiting a computation prints it with no indentation or newline.
 #define DECLARE_VISIT_COMPUTATION(ShortName, ClassName)                        \
   virtual void Visit##ShortName(ClassName* comp);
 
   // Visiting an instruction prints it with a four space indent and no
   // trailing newline.  Basic block entries are labeled with their block
   // number.
 #define DECLARE_VISIT_INSTRUCTION(ShortName)                                   \
   virtual void Visit##ShortName(ShortName##Instr* instr);
 
   FOR_EACH_COMPUTATION(DECLARE_VISIT_COMPUTATION)
   FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
 
 #undef DECLARE_VISIT_COMPUTATION
 #undef DECLARE_VISIT_INSTRUCTION
 
  private:
   const Function& function_;
 
   DISALLOW_COPY_AND_ASSIGN(FlowGraphPrinter);
 };
 
 
-void FlowGraphPrinter::VisitBlocks(
-    const GrowableArray<BlockEntryInstr*>& block_order) {
+void FlowGraphPrinter::VisitBlocks() {
   OS::Print("==== %s\n", function_.ToFullyQualifiedCString());
 
-  for (intptr_t i = block_order.length() - 1; i >= 0; --i) {
+  for (intptr_t i = 0; i < block_order_.length(); ++i) {
     // Print the block entry.
-    Instruction* current = block_order[i]->Accept(this);
+    Instruction* current = block_order_[i]->Accept(this);
     // And all the successors until an exit, branch, or a block entry.
     while ((current != NULL) && !current->IsBlockEntry()) {
       OS::Print("\n");
       current = current->Accept(this);
     }
     BlockEntryInstr* successor =
         (current == NULL) ? NULL : current->AsBlockEntry();
     if (successor != NULL) {
-      OS::Print(" goto %d", successor->block_number());
+      // For readability label blocks with their reverse postorder index,
+      // not their postorder block number, so the first block is 0 (not
+      // n-1).
+      OS::Print(" goto %d", reverse_index(successor->postorder_number()));
     }
     OS::Print("\n");
   }
 }
 
 
 void FlowGraphPrinter::VisitTemp(TempVal* val) {
   OS::Print("t%d", val->index());
 }
 
@@ skipping 193 matching lines @@
     ExtractConstructorInstantiatorComp* comp) {
   OS::Print("ExtractConstructorInstantiator(");
   comp->instantiator()->Accept(this);
   OS::Print(", ");
   comp->discard_value()->Accept(this);
   OS::Print(")");
 }
 
 
 void FlowGraphPrinter::VisitJoinEntry(JoinEntryInstr* instr) {
-  OS::Print("%2d: [join]", instr->block_number());
+  OS::Print("%2d: [join]", reverse_index(instr->postorder_number()));
 }
 
 
 void FlowGraphPrinter::VisitTargetEntry(TargetEntryInstr* instr) {
-  OS::Print("%2d: [target]", instr->block_number());
+  OS::Print("%2d: [target]", reverse_index(instr->postorder_number()));
 }
 
 
 void FlowGraphPrinter::VisitPickTemp(PickTempInstr* instr) {
   OS::Print("    t%d <- Pick(t%d)", instr->destination(), instr->source());
 }
 
 
 void FlowGraphPrinter::VisitTuckTemp(TuckTempInstr* instr) {
   OS::Print("    t%d := t%d", instr->destination(), instr->source());
@@ skipping 30 matching lines @@
   instr->exception()->Accept(this);
   OS::Print(", ");
   instr->stack_trace()->Accept(this);
   OS::Print(")");
 }
 
 
 void FlowGraphPrinter::VisitBranch(BranchInstr* instr) {
   OS::Print("    if ");
   instr->value()->Accept(this);
-  OS::Print(" goto(%d, %d)", instr->true_successor()->block_number(),
-            instr->false_successor()->block_number());
+  OS::Print(" goto(%d, %d)",
+            reverse_index(instr->true_successor()->postorder_number()),
+            reverse_index(instr->false_successor()->postorder_number()));
 }
 
 
 void FlowGraphBuilder::BuildGraph() {
   if (FLAG_print_ast) {
     // Print the function ast before IL generation.
     AstPrinter::PrintFunctionNodes(parsed_function());
   }
   const Function& function = parsed_function().function();
   EffectGraphVisitor for_effect(this, 0);
   for_effect.AddInstruction(new TargetEntryInstr());
   parsed_function().node_sequence()->Visit(&for_effect);
   // Check that the graph is properly terminated.
   ASSERT(!for_effect.is_open());
   if (for_effect.entry() != NULL) {
-    // 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 last_index = postorder_block_entries_.length() - 1;
-    for (intptr_t i = last_index; i >= 0; --i) {
-      postorder_block_entries_[i]->set_block_number(last_index - i);
-    }
+    // Perform a depth-first traversal of the graph to build preorder and
+    // postorder block orders.
+    for_effect.entry()->DepthFirstSearch(&preorder_block_entries_,
+                                         &postorder_block_entries_);
   }
   if (FLAG_print_flow_graph) {
-    FlowGraphPrinter printer(function);
-    printer.VisitBlocks(postorder_block_entries_);
+    intptr_t length = postorder_block_entries_.length();
+    GrowableArray<BlockEntryInstr*> reverse_postorder(length);
+    for (intptr_t i = length - 1; i >= 0; --i) {
+      reverse_postorder.Add(postorder_block_entries_[i]);
+    }
+    FlowGraphPrinter printer(function, reverse_postorder);
+    printer.VisitBlocks();
   }
 }
 
 
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   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