Skeleton of a linear scan register allocator.

runtime/vm/flow_graph_compiler.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_XXX.
 
 #include "vm/flow_graph_compiler.h"
 
 #include "vm/dart_entry.h"
 #include "vm/debugger.h"
@@ skipping 15 matching lines @@
 DECLARE_FLAG(bool, report_usage_count);
 DECLARE_FLAG(bool, trace_functions);
 DECLARE_FLAG(int, optimization_counter_threshold);
 
 
 FlowGraphCompiler::FlowGraphCompiler(
     Assembler* assembler,
     const ParsedFunction& parsed_function,
     const GrowableArray<BlockEntryInstr*>& block_order,
     bool is_optimizing,
+    bool is_ssa,
     bool is_leaf)
     : assembler_(assembler),
       parsed_function_(parsed_function),
       block_order_(block_order),
       current_block_(NULL),
       exception_handlers_list_(NULL),
       pc_descriptors_list_(NULL),
       stackmap_builder_(NULL),
       block_info_(block_order.length()),
       deopt_stubs_(),
       is_optimizing_(is_optimizing),
+      is_ssa_(is_ssa),
       is_dart_leaf_(is_leaf),
       bool_true_(Bool::ZoneHandle(Bool::True())),
       bool_false_(Bool::ZoneHandle(Bool::False())),
       double_class_(Class::ZoneHandle(
           Isolate::Current()->object_store()->double_class())),
-      frame_register_allocator_(this, is_optimizing) {
+      frame_register_allocator_(this, is_optimizing, is_ssa),
+      parallel_move_resolver_(this) {
   ASSERT(assembler != NULL);

[srdjan, 2012/07/10 23:27:54]

You could also ASSERT(is_optimizing_ || !is_ssa_);

[Vyacheslav Egorov (Google), 2012/07/11 13:27:58]

Done.

 }
 
 
 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());
     ASSERT(!block_info_[i]->label.HasNear());
   }
@@ skipping 30 matching lines @@
     assembler()->Comment("B%d", i);
     // Compile the block entry.
     BlockEntryInstr* entry = block_order()[i];
     set_current_block(entry);
     entry->PrepareEntry(this);
     // Compile all successors until an exit, branch, or a block entry.
     Instruction* instr = entry;
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       instr = it.Current();
       if (FLAG_code_comments) EmitComment(instr);
-      ASSERT(instr->locs() != NULL);
-      EmitInstructionPrologue(instr);
-      instr->EmitNativeCode(this);
+      if (instr->IsParallelMove()) {
+        parallel_move_resolver_.EmitNativeCode(instr->AsParallelMove());
+      } else {
+        ASSERT(instr->locs() != NULL);
+        EmitInstructionPrologue(instr);
+        pending_deoptimization_env_ = instr->env();
+        instr->EmitNativeCode(this);
+      }
     }
     if (instr->next() != NULL) {
       BlockEntryInstr* successor = instr->next()->AsBlockEntry();
       ASSERT(successor != NULL);
       frame_register_allocator()->Spill();
       // The 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)) {
         assembler()->jmp(GetBlockLabel(successor));
@@ skipping 65 matching lines @@
 
 Label* FlowGraphCompiler::AddDeoptStub(intptr_t deopt_id,
                                        intptr_t deopt_token_pos,
                                        intptr_t try_index,
                                        DeoptReasonId reason,
                                        Register reg1,
                                        Register reg2,
                                        Register reg3) {
   DeoptimizationStub* stub =
       new DeoptimizationStub(deopt_id, deopt_token_pos, try_index, reason);
-  frame_register_allocator()->SpillInDeoptStub(stub);
-  if (reg1 != kNoRegister) stub->Push(reg1);
-  if (reg2 != kNoRegister) stub->Push(reg2);
-  if (reg3 != kNoRegister) stub->Push(reg3);
+  if (pending_deoptimization_env_ == NULL) {
+    frame_register_allocator()->SpillInDeoptStub(stub);
+    if (reg1 != kNoRegister) stub->Push(reg1);
+    if (reg2 != kNoRegister) stub->Push(reg2);
+    if (reg3 != kNoRegister) stub->Push(reg3);
+  } else {
+    stub->set_deoptimization_env(pending_deoptimization_env_);
+  }
   deopt_stubs_.Add(stub);
   return stub->entry_label();
 }
 
 
 void FlowGraphCompiler::FinalizeExceptionHandlers(const Code& code) {
   ASSERT(exception_handlers_list_ != NULL);
   const ExceptionHandlers& handlers = ExceptionHandlers::Handle(
       exception_handlers_list_->FinalizeExceptionHandlers(code.EntryPoint()));
   code.set_exception_handlers(handlers);
@@ skipping 263 matching lines @@
   return reg;
 }
 
 
 void FrameRegisterAllocator::SpillRegister(Register reg) {
   while (registers_[reg] != NULL) SpillFirst();
 }
 
 
 void FrameRegisterAllocator::AllocateRegisters(Instruction* instr) {
+  if (is_ssa_) return;
+
   LocationSummary* locs = instr->locs();
 
   bool blocked_registers[kNumberOfCpuRegisters];
   bool blocked_temp_registers[kNumberOfCpuRegisters];
 
   bool spill = false;
 
   // Mark all available registers free.
   for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) {
     blocked_registers[i] = false;
     blocked_temp_registers[i] = false;
   }
 
   // Mark all fixed input, temp and output registers as used.
   for (intptr_t i = 0; i < locs->input_count(); i++) {
     Location loc = locs->in(i);
-    if (loc.kind() == Location::kRegister) {
+    if (loc.IsRegister()) {
       ASSERT(!blocked_registers[loc.reg()]);
       blocked_registers[loc.reg()] = true;
       if (registers_[loc.reg()] != NULL) {
         intptr_t stack_index = stack_.length() - (locs->input_count() - i);
         if ((stack_index < 0) || (stack_[stack_index] != loc.reg())) {
           spill = true;
         }
       }
     }
   }
 
   if (spill) Spill();
 
   for (intptr_t i = 0; i < locs->temp_count(); i++) {
     Location loc = locs->temp(i);
-    if (loc.kind() == Location::kRegister) {
+    if (loc.IsRegister()) {
       ASSERT(!blocked_registers[loc.reg()]);
       blocked_registers[loc.reg()] = true;
       blocked_temp_registers[loc.reg()] = true;
     }
   }
 
-  if (locs->out().kind() == Location::kRegister) {
+  if (locs->out().IsRegister()) {
     // Fixed output registers are allowed to overlap with
     // temps and inputs.
     blocked_registers[locs->out().reg()] = true;
   }
 
   // Do not allocate known registers.
   blocked_registers[CTX] = true;
   blocked_registers[SPREG] = true;
   blocked_registers[FPREG] = true;
   if (TMP != kNoRegister) {
     blocked_registers[TMP] = true;
   }
 
   // Allocate all unallocated input locations.
   for (intptr_t i = locs->input_count() - 1; i >= 0; i--) {
     Location loc = locs->in(i);
     Register reg = kNoRegister;
-    if (loc.kind() == Location::kRegister) {
+    if (loc.IsRegister()) {
       reg = loc.reg();
-    } else if (loc.kind() == Location::kUnallocated) {
+    } else if (loc.IsUnallocated()) {
       ASSERT(loc.policy() == Location::kRequiresRegister);
       if ((stack_.length() > 0) && !blocked_temp_registers[stack_.Last()]) {
         reg = stack_.Last();
         blocked_registers[reg] = true;
       } else {
         reg = AllocateFreeRegister(blocked_registers);
       }
       locs->set_in(i, Location::RegisterLocation(reg));
     }
 
     Pop(reg, instr->InputAt(i));
   }
 
   // If this instruction is call spill everything that was not consumed by
   // input locations.
   if (locs->is_call() || locs->is_branch()) {
     Spill();
   }
 
   // Allocate all unallocated temp locations.
   for (intptr_t i = 0; i < locs->temp_count(); i++) {
     Location loc = locs->temp(i);
-    if (loc.kind() == Location::kUnallocated) {
+    if (loc.IsUnallocated()) {
       ASSERT(loc.policy() == Location::kRequiresRegister);
       loc = Location::RegisterLocation(
         AllocateFreeRegister(blocked_registers));
       locs->set_temp(i, loc);
     }
     SpillRegister(loc.reg());
   }
 
   Location result_location = locs->out();
-  if (result_location.kind() == Location::kUnallocated) {
+  if (result_location.IsUnallocated()) {
     switch (result_location.policy()) {
       case Location::kRequiresRegister:
         result_location = Location::RegisterLocation(
             AllocateFreeRegister(blocked_registers));
         break;
       case Location::kSameAsFirstInput:
         result_location = locs->in(0);
         break;
     }
     locs->set_out(result_location);
   }
 
-  if (result_location.kind() == Location::kRegister) {
+  if (result_location.IsRegister()) {
     SpillRegister(result_location.reg());
   }
 }
 
 
 void FrameRegisterAllocator::Pop(Register dst, Value* val) {
+  if (is_ssa_) return;
+
   if (stack_.length() > 0) {
     ASSERT(keep_values_in_registers_);
     Register src = stack_.Last();
     ASSERT(val->AsUse()->definition() == registers_[src]);
     stack_.RemoveLast();
     registers_[src] = NULL;
     compiler()->assembler()->MoveRegister(dst, src);
   } else {
     compiler()->assembler()->PopRegister(dst);
   }
 }
 
 
 void FrameRegisterAllocator::Push(Register reg, BindInstr* val) {
+  if (is_ssa_) return;
+
   ASSERT(registers_[reg] == NULL);
   if (keep_values_in_registers_) {
     registers_[reg] = val;
     stack_.Add(reg);
   } else {
     compiler()->assembler()->PushRegister(reg);
   }
 }
 
 
 void FrameRegisterAllocator::Spill() {
+  if (is_ssa_) return;
+
   for (int i = 0; i < stack_.length(); i++) {
     Register r = stack_[i];
     registers_[r] = NULL;
     compiler()->assembler()->PushRegister(r);
   }
   stack_.Clear();
 }
 
 
 void FrameRegisterAllocator::SpillInDeoptStub(DeoptimizationStub* stub) {
+  if (is_ssa_) return;
+
   for (int i = 0; i < stack_.length(); i++) {
     stub->Push(stack_[i]);
   }
 }
 
 
 }  // namespace dart