Introduce locations based code generation.

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 "lib/error.h"
@@ skipping 14 matching lines @@
 DEFINE_FLAG(bool, print_scopes, false, "Print scopes of local variables.");
 DEFINE_FLAG(bool, trace_functions, false, "Trace entry of each function.");
 DECLARE_FLAG(bool, enable_type_checks);
 DECLARE_FLAG(bool, intrinsify);
 DECLARE_FLAG(bool, optimization_counter_threshold);
 DECLARE_FLAG(bool, print_ast);
 DECLARE_FLAG(bool, report_usage_count);
 DECLARE_FLAG(bool, code_comments);
 
 
+static Register ToRegister(Location loc) {
+  return RegisterLocation::Cast(loc).reg();
+}
+
+
 FlowGraphCompiler::FlowGraphCompiler(
     Assembler* assembler,
     const ParsedFunction& parsed_function,
     const GrowableArray<BlockEntryInstr*>& block_order,
     bool is_optimizing)
     : FlowGraphVisitor(block_order),
       assembler_(assembler),
       parsed_function_(parsed_function),
       block_info_(block_order.length()),
       current_block_(NULL),
@@ skipping 494 matching lines @@
   EmitInstanceCall(comp->cid(),
                    comp->token_index(),
                    comp->try_index(),
                    comp->function_name(),
                    comp->ArgumentCount(),
                    comp->argument_names(),
                    comp->checked_argument_count());
 }
 
 
+LocationSummary* StrictCompareComp::MakeLocationSummary() {

[srdjan, 2012/05/18 18:00:14]

In unoptimizing compiler this is the same for all StrictCompareComps. Instead of
allocating every time, maybe preallocate and reuse the LocationSummary.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Preallocating and reusing proves to be hard because it's a zone object so I
can't just save it into some static field inside the instruction class.

The only way to share it apparently is to introduce opcodes and store
precomputes location summaries in a table (opcode -> locs) inside the compiler.
Seems a bit complicated but I could not come up with anything better. What do
you think?

[srdjan, 2012/05/21 16:05:22]

Valid points, good suggestion. Let's not do anything now.

+  LocationSummary* summary = new LocationSummary(2);
+  summary->SetInputLocationAt(
+      0, UnallocatedLocation(UnallocatedLocation::REGISTER));
+  summary->SetInputLocationAt(
+      1, UnallocatedLocation(UnallocatedLocation::REGISTER));

[srdjan, 2012/05/18 18:00:14]

Too verbose.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

introduced a helper function and shortened method names

+  summary->set_result_location(
+      UnallocatedLocation(UnallocatedLocation::SAME_AS_FIRST_INPUT));
+  return summary;

[srdjan, 2012/05/18 18:00:14]

As you said, this does not belong here. Maybe in an architecture dependent
location or intermediate_language_xxx.cc file.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

moved to intermediate_language_x64.cc

+}
+
+
 void FlowGraphCompiler::VisitStrictCompare(StrictCompareComp* comp) {
   const Bool& bool_true = Bool::ZoneHandle(Bool::True());
   const Bool& bool_false = Bool::ZoneHandle(Bool::False());
-  LoadValue(RDX, comp->right());
-  LoadValue(RAX, comp->left());
-  __ cmpq(RAX, RDX);
+
+  Register left = ToRegister(comp->GetLocationSummary()->InputLocationAt(0));
+  Register right = ToRegister(comp->GetLocationSummary()->InputLocationAt(1));
+  Register result = ToRegister(comp->GetLocationSummary()->result_location());

[srdjan, 2012/05/18 18:00:14]

Too verbose, maybe:
comp->locs()->in(0)->AsRegister();

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Done.

+
+  __ cmpq(left, right);
   Label load_true, done;
   if (comp->kind() == Token::kEQ_STRICT) {
     __ j(EQUAL, &load_true, Assembler::kNearJump);
   } else {
     __ j(NOT_EQUAL, &load_true, Assembler::kNearJump);
   }
-  __ LoadObject(RAX, bool_false);
+  __ LoadObject(result, bool_false);
   __ jmp(&done, Assembler::kNearJump);
   __ Bind(&load_true);
-  __ LoadObject(RAX, bool_true);
+  __ LoadObject(result, bool_true);
   __ Bind(&done);
 }
 
 
 void FlowGraphCompiler::VisitEqualityCompare(EqualityCompareComp* comp) {
   const Bool& bool_true = Bool::ZoneHandle(Bool::True());
   const Bool& bool_false = Bool::ZoneHandle(Bool::False());
   const Immediate raw_null =
       Immediate(reinterpret_cast<intptr_t>(Object::null()));
   Label done, load_true, non_null_compare;
@@ skipping 540 matching lines @@
 
   ASSERT(!comp->exception_var().is_captured());
   ASSERT(!comp->stacktrace_var().is_captured());
   __ movq(Address(RBP, comp->exception_var().index() * kWordSize),
           kExceptionObjectReg);
   __ movq(Address(RBP, comp->stacktrace_var().index() * kWordSize),
           kStackTraceObjectReg);
 }
 
 
+static Register AllocateFreeRegister(bool* blocked_registers) {

[srdjan, 2012/05/18 18:00:14]

I would rather use BitVector or GrowableArray since they have range checks.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

both are zone allocated which seems unnecessary expensive to me (will require
allocation per instruction)

decided to use EmbeddedVector instead.

+  for (int regno = 0; regno < kNumberOfCpuRegisters; regno++) {
+    if (!blocked_registers[regno]) {
+      blocked_registers[regno] = true;
+      return static_cast<Register>(regno);

[srdjan, 2012/05/18 18:00:14]

The register allocation needs also to move out of code generator.

[Vyacheslav Egorov (Google), 2012/05/20 12:07:46]

Moved simple register allocator into LocationSummary itself (and LocationSummary
was moved into locations.{h,cc}

+    }
+  }
+  UNREACHABLE();
+  return kNoRegister;
+}
+
+
+static void AllocateRegisters(LocationSummary* summary) {
+  bool blocked_registers[kNumberOfCpuRegisters] = { false };
+
+  for (intptr_t i = 0; i < summary->InputLocationsCount(); i++) {
+    Location loc = summary->InputLocationAt(i);
+    if (loc.kind() == Location::REGISTER) {
+      ASSERT(!blocked_registers[ToRegister(loc)]);
+      blocked_registers[loc.value()] = true;
+    }
+  }
+
+  for (intptr_t i = 0; i < summary->InputLocationsCount(); i++) {
+    Location loc = summary->InputLocationAt(i);
+    if (loc.kind() == Location::UNALLOCATED) {
+      ASSERT(UnallocatedLocation::Cast(loc).policy() ==
+             UnallocatedLocation::REGISTER);
+      summary->SetInputLocationAt(i, RegisterLocation(
+          AllocateFreeRegister(blocked_registers)));
+    }
+  }
+
+  Location result_location = summary->result_location();
+  if (result_location.kind() == Location::UNALLOCATED) {
+    switch (UnallocatedLocation::Cast(result_location).policy()) {
+      case UnallocatedLocation::REGISTER:
+        result_location = RegisterLocation(
+            AllocateFreeRegister(blocked_registers));
+        break;
+      case UnallocatedLocation::SAME_AS_FIRST_INPUT:
+        result_location = summary->InputLocationAt(0);
+        break;
+    }
+    summary->set_result_location(result_location);
+  }
+}
+
+
+void FlowGraphCompiler::EmitInstructionPrologue(Instruction* instr) {
+  LocationSummary* summary = instr->GetLocationSummary();
+
+  // Check if current instruction has any special location requirements.
+  if (summary == NULL) return;
+
+  AllocateRegisters(summary);
+
+  // Load instruction inputs into allocated registers.
+  for (intptr_t i = summary->InputLocationsCount() - 1; i >= 0; i--) {
+    Location loc = summary->InputLocationAt(i);
+    if (loc.kind() == Location::REGISTER) {
+      __ popq(ToRegister(loc));
+    }
+  }
+}
+
+
 void FlowGraphCompiler::VisitBlocks() {
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     __ Comment("B%d", i);
     // Compile the block entry.
     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()) {
       if (FLAG_code_comments) EmitComment(instr);
+      EmitInstructionPrologue(instr);
       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 == block_order_.length() - 1) ||
           (block_order_[i + 1] != successor)) {
@@ skipping 31 matching lines @@
 }
 
 
 void FlowGraphCompiler::VisitDo(DoInstr* instr) {
   instr->computation()->Accept(this);
 }
 
 
 void FlowGraphCompiler::VisitBind(BindInstr* instr) {
   instr->computation()->Accept(this);
-  __ pushq(RAX);
+
+  if (instr->GetLocationSummary() == NULL) {
+    // If instruction does not have special location requirements
+    // then it returns result in register RAX.
+    __ pushq(RAX);
+  } else {
+    __ pushq(ToRegister(instr->GetLocationSummary()->result_location()));
+  }
 }
 
 
 void FlowGraphCompiler::VisitReturn(ReturnInstr* instr) {
   LoadValue(RAX, instr->value());
   if (!is_optimizing()) {
     // Count only in unoptimized code.
     // TODO(srdjan): Replace the counting code with a type feedback
     // collection and counting stub.
     const Function& function =
@@ skipping 518 matching lines @@
 
 
 void FlowGraphCompiler::FinalizeComments(const Code& code) {
   code.set_comments(assembler_->GetCodeComments());
 }
 
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_X64