Implement branching control flow in the non-optimizing graph compiler.

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/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),
+      parsed_function_(parsed_function),
+      blocks_(blocks),
+      block_info_(blocks->length()),
+      current_block_(NULL),
+      pc_descriptors_list_(new CodeGenerator::DescriptorList()),
+      stack_local_count_(0) {
+  for (int i = 0; i < blocks->length(); ++i) {
+    block_info_.Add(new BlockInfo());
+  }
+}
+
+
 void FlowGraphCompiler::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphCompiler 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);
@@ skipping 220 matching lines @@
   __ popq(RBX);  // Reciever.
   __ pushq(RAX);
   __ pushq(RBX);
   __ pushq(RAX);
   EmitInstanceCall(comp->node_id(), comp->token_index(), function_name, 2,
                    Array::ZoneHandle(), 1);
   __ popq(RAX);
 }
 
 
+void FlowGraphCompiler::VisitBlocks(
+    const GrowableArray<BlockEntryInstr*>& blocks) {
+  for (intptr_t i = blocks.length() - 1; i >= 0; --i) {
+    // Compile the block entry.
+    current_block_ = blocks[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);
+    }
+
+    if ((instr != NULL) && instr->IsBlockEntry()) {
+      // 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] != instr)) {
+        int number = BlockEntryInstr::cast(instr)->block_number();

[srdjan, 2012/03/07 22:23:06]

Discussed in the team and talked with Ivan: Please use AsXXX style instead of
::cast. The former is the DartVM style the second is V8 style. We do not use the
cast-like-style, and it is confusing if we use both.

[Kevin Millikin (Google), 2012/03/08 09:59:53]

Removed the static member function from class BlockEntryInstr.  Rewrote it with
As.

+        __ jmp(&block_info_[number]->label);
+      }
+    }
+  }
+}
+
+
 void FlowGraphCompiler::VisitJoinEntry(JoinEntryInstr* instr) {
-  Bailout("JoinEntryInstr");
+  __ Bind(&block_info_[instr->block_number()]->label);
 }
 
 
 void FlowGraphCompiler::VisitTargetEntry(TargetEntryInstr* instr) {
-  // Since we don't handle branching control flow yet, there is nothing to do.
+  __ Bind(&block_info_[instr->block_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 62 matching lines @@
   __ nop(1);
   __ nop(1);
   __ nop(1);
   AddCurrentDescriptor(PcDescriptors::kReturn,
                        AstNode::kNoId,
                        instr->token_index());
 }
 
 
 void FlowGraphCompiler::VisitBranch(BranchInstr* instr) {
-  Bailout("BranchInstr");
+  // Determine if the true branch is fall through (!negated) or the false
+  // branch is.  They cannot both be backwards branches.
+  int index = blocks_->length() - current_block()->block_number() - 1;

[srdjan, 2012/03/07 22:23:06]

intptr_t

[Kevin Millikin (Google), 2012/03/08 09:59:53]

Done.

+  ASSERT(index != 0);

[srdjan, 2012/03/07 22:23:06]

Maybe safer: (index > 0).

[Kevin Millikin (Google), 2012/03/08 09:59:53]

Done.

+
+  bool negated = ((*blocks_)[index - 1] == instr->false_successor());
+  ASSERT(!negated == ((*blocks_)[index - 1] == instr->true_successor()));
+
+  LoadValue(instr->value());
+  __ LoadObject(RDX, Bool::ZoneHandle(Bool::True()));
+  __ cmpq(RAX, RDX);
+  if (negated) {
+    __ j(EQUAL, &block_info_[instr->true_successor()->block_number()]->label);
+

[srdjan, 2012/03/07 22:23:06]

Empty line?

[Kevin Millikin (Google), 2012/03/08 09:59:53]

Deleted.

+  } else {
+    __ j(NOT_EQUAL,
+         &block_info_[instr->false_successor()->block_number()]->label);
+  }
 }
 
 
 void FlowGraphCompiler::CompileGraph() {
   const Function& function = parsed_function_.function();
   if ((function.num_optional_parameters() != 0)) {
     Bailout("function has optional parameters");
   }
   LocalScope* scope = parsed_function_.node_sequence()->scope();
   LocalScope* context_owner = NULL;
   const int parameter_count = function.num_fixed_parameters();
   const int first_parameter_index = 1 + parameter_count;
   const int first_local_index = -1;
   int first_free_frame_index =
       scope->AllocateVariables(first_parameter_index,
                                parameter_count,
                                first_local_index,
                                scope,
                                &context_owner);
   set_stack_local_count(first_local_index - first_free_frame_index);
 
-  if (blocks_->length() != 1) Bailout("more than 1 basic block");
-
   // Specialized version of entry code from CodeGenerator::GenerateEntryCode.
   __ EnterFrame(stack_local_count() * kWordSize);
 #ifdef DEBUG
   const bool check_arguments = true;
 #else
   const bool check_arguments = function.IsClosureFunction();
 #endif
   if (check_arguments) {
     // Check that num_fixed <= argc <= num_params.
     Label argc_in_range;
@@ skipping 102 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