Compute preorder as well as postorder basic block orderings.

runtime/vm/flow_graph_compiler_x64.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/globals.h"  // Needed here to get TARGET_ARCH_X64.
 #if defined(TARGET_ARCH_X64)
 
 #include "vm/flow_graph_compiler.h"
 
 #include "vm/ast_printer.h"
 #include "vm/code_generator.h"
 #include "vm/disassembler.h"
 #include "vm/longjump.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/stub_code.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, print_ast);
 DECLARE_FLAG(bool, print_scopes);
 DECLARE_FLAG(bool, trace_functions);
 
 FlowGraphCompiler::FlowGraphCompiler(
     Assembler* assembler,
     const ParsedFunction& parsed_function,
-    const GrowableArray<BlockEntryInstr*>* blocks)
-    : assembler_(assembler),
+    const GrowableArray<BlockEntryInstr*>& block_order)
+    : FlowGraphVisitor(block_order),
+      assembler_(assembler),
       parsed_function_(parsed_function),
-      blocks_(blocks),
-      block_info_(blocks->length()),
+      block_info_(block_order.length()),
       current_block_(NULL),
       pc_descriptors_list_(new CodeGenerator::DescriptorList()) {
-  for (int i = 0; i < blocks->length(); ++i) {
+  for (int i = 0; i < block_order.length(); ++i) {
     block_info_.Add(new BlockInfo());
   }
 }
 
 
 FlowGraphCompiler::~FlowGraphCompiler() {
   // BlockInfos are zone-allocated, so their destructors are not called.
   // Verify the labels explicitly here.
   for (int i = 0; i < block_info_.length(); ++i) {
     ASSERT(!block_info_[i]->label.IsLinked());
@@ skipping 678 matching lines @@
     // instantiated type arguments, reset instantiator to null.
     __ movq(RAX, raw_null);  // Null instantiator.
     __ Bind(&use_instantiator);  // Use instantiator in RAX.
   }
   // In the non-factory case, we rely on the allocation stub to
   // instantiate the type arguments.
   // RAX: instantiator or null.
 }
 
 
-void FlowGraphCompiler::VisitBlocks(
-    const GrowableArray<BlockEntryInstr*>& blocks) {
-  for (intptr_t i = blocks.length() - 1; i >= 0; --i) {
+void FlowGraphCompiler::VisitBlocks() {
+  for (intptr_t i = 0; i < block_order_.length(); ++i) {
     // Compile the block entry.
-    current_block_ = blocks[i];
+    current_block_ = block_order_[i];
     Instruction* instr = current_block()->Accept(this);
     // Compile all successors until an exit, branch, or a block entry.
     while ((instr != NULL) && !instr->IsBlockEntry()) {
       instr = instr->Accept(this);
     }
 
     BlockEntryInstr* successor =
         (instr == NULL) ? NULL : instr->AsBlockEntry();
     if (successor != NULL) {
       // Block ended with a "goto".  We can fall through if it is the
       // next block in the list.  Otherwise, we need a jump.
-      if (i == 0 || (blocks[i - 1] != successor)) {
-        __ jmp(&block_info_[successor->block_number()]->label);
+      if ((i == block_order_.length() - 1) ||
+          (block_order_[i + 1] != successor)) {
+        __ jmp(&block_info_[successor->postorder_number()]->label);
       }
     }
   }
 }
 
 
 void FlowGraphCompiler::VisitJoinEntry(JoinEntryInstr* instr) {
-  __ Bind(&block_info_[instr->block_number()]->label);
+  __ Bind(&block_info_[instr->postorder_number()]->label);
 }
 
 
 void FlowGraphCompiler::VisitTargetEntry(TargetEntryInstr* instr) {
-  __ Bind(&block_info_[instr->block_number()]->label);
+  __ Bind(&block_info_[instr->postorder_number()]->label);
 }
 
 
 void FlowGraphCompiler::VisitPickTemp(PickTempInstr* instr) {
   // Semantics is to copy a stack-allocated temporary to the top of stack.
   // Destination index d is assumed the new top of stack after the
   // operation, so d-1 is the current top of stack and so d-s-1 is the
   // offset to source index s.
   intptr_t offset = instr->destination() - instr->source() - 1;
   ASSERT(offset >= 0);
@@ skipping 86 matching lines @@
   GenerateCallRuntime(
       instr->node_id(), instr->token_index(), kReThrowRuntimeEntry);
   Bailout("ReThrow Untested");
 }
 
 
 
 void FlowGraphCompiler::VisitBranch(BranchInstr* instr) {
   // Determine if the true branch is fall through (!negated) or the false
   // branch is.  They cannot both be backwards branches.
-  intptr_t index = blocks_->length() - current_block()->block_number() - 1;
-  ASSERT(index > 0);
-
-  bool negated = ((*blocks_)[index - 1] == instr->false_successor());
-  ASSERT(!negated == ((*blocks_)[index - 1] == instr->true_successor()));
+  intptr_t index = reverse_index(current_block()->postorder_number());
+  bool negated = (block_order_[index + 1] == instr->false_successor());
+  ASSERT(!negated == (block_order_[index + 1] == instr->true_successor()));
 
   LoadValue(RAX, instr->value());
   __ LoadObject(RDX, Bool::ZoneHandle(Bool::True()));
   __ cmpq(RAX, RDX);
   if (negated) {
-    __ j(EQUAL, &block_info_[instr->true_successor()->block_number()]->label);
+    intptr_t target_index = instr->true_successor()->postorder_number();
+    __ j(EQUAL, &block_info_[target_index]->label);
   } else {
-    __ j(NOT_EQUAL,
-         &block_info_[instr->false_successor()->block_number()]->label);
+    intptr_t target_index = instr->false_successor()->postorder_number();
+    __ j(NOT_EQUAL, &block_info_[target_index]->label);
   }
 }
 
 
 // Coped from CodeGenerator::CopyParameters (CodeGenerator will be deprecated).
 void FlowGraphCompiler::CopyParameters() {
   const Function& function = parsed_function_.function();
   LocalScope* scope = parsed_function_.node_sequence()->scope();
   const int num_fixed_params = function.num_fixed_parameters();
   const int num_opt_params = function.num_optional_parameters();
@@ skipping 235 matching lines @@
   if (FLAG_print_scopes) {
     // Print the function scope (again) after generating the prologue in order
     // to see annotations such as allocation indices of locals.
     if (FLAG_print_ast) {
       // Second printing.
       OS::Print("Annotated ");
     }
     AstPrinter::PrintFunctionScope(parsed_function_);
   }
 
-  VisitBlocks(*blocks_);
+  VisitBlocks();
 
   __ int3();
   // Emit function patching code. This will be swapped with the first 13 bytes
   // at entry point.
   pc_descriptors_list_->AddDescriptor(PcDescriptors::kPatchCode,
                                       assembler_->CodeSize(),
                                       AstNode::kNoId,
                                       0,
                                       -1);
   __ jmp(&StubCode::FixCallersTargetLabel());
@@ skipping 48 matching lines @@
 void FlowGraphCompiler::FinalizeExceptionHandlers(const Code& code) {
   // We don't compile exception handlers yet.
   code.set_exception_handlers(
       ExceptionHandlers::Handle(ExceptionHandlers::New(0)));
 }
 
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_X64