Skeleton of a linear scan register allocator.

runtime/vm/flow_graph_compiler.h

 // 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.
 
 #ifndef VM_FLOW_GRAPH_COMPILER_H_
 #define VM_FLOW_GRAPH_COMPILER_H_
 
 #include "vm/allocation.h"
 #include "vm/assembler.h"
 #include "vm/assembler_macros.h"
@@ skipping 14 matching lines @@
 // fact that IR is stack based and a value produced by a bind instruction
 // will be used only once.  For the register allocator every Bind is a push and
 // every UseVal of a bind is a pop.
 // It can also operate in a non-optimizing mode when every value is pushed
 // to the stack immediately after it is produced.
 // TODO(vegorov): replace with a linear scan register allocator once SSA is
 // available.
 class FrameRegisterAllocator : public ValueObject {
  public:
   FrameRegisterAllocator(FlowGraphCompiler* compiler,
-                         bool keep_values_in_registers)
+                         bool keep_values_in_registers,
+                         bool is_ssa)
       : compiler_(compiler),
         stack_(kNumberOfCpuRegisters),
         registers_(),
-        keep_values_in_registers_(keep_values_in_registers) {
+        keep_values_in_registers_(keep_values_in_registers && !is_ssa),
+        is_ssa_(is_ssa) {
     for (int i = 0; i < kNumberOfCpuRegisters; i++) {
       registers_[i] = NULL;
     }
   }
 
   // Notify register allocator that given instruction produced a value
   // in the given register.
   void Push(Register reg, BindInstr* val);
 
   // Perform a greedy local register allocation.  Consider all register free.
@@ skipping 33 matching lines @@
   FlowGraphCompiler* compiler_;
 
   // List of registers with live values in order from oldest to newest.
   GrowableArray<Register> stack_;
 
   // Mapping between live registers and instructions that produced values
   // in them.  Contains NULL for registers do not have corresponding live value.
   BindInstr* registers_[kNumberOfCpuRegisters];
 
   const bool keep_values_in_registers_;
+  const bool is_ssa_;
 
   DISALLOW_COPY_AND_ASSIGN(FrameRegisterAllocator);
 };
 
+
+class ParallelMoveResolver : public ValueObject {
+ public:
+  explicit ParallelMoveResolver(FlowGraphCompiler* compiler);
+
+  // Resolve a set of parallel moves, emitting assembler instructions.
+  void EmitNativeCode(ParallelMoveInstr* parallel_move);
+
+ private:
+  // Build the initial list of moves.
+  void BuildInitialMoveList(ParallelMoveInstr* parallel_move);
+
+  // Perform the move at the moves_ index in question (possibly requiring
+  // other moves to satisfy dependencies).
+  void PerformMove(int index);
+
+  // Emit a move and remove it from the move graph.
+  void EmitMove(int index);
+
+  // Execute a move by emitting a swap of two operands.  The move from
+  // source to destination is removed from the move graph.
+  void EmitSwap(int index);
+
+  // Verify the move list before performing moves.
+  void Verify();
+
+  FlowGraphCompiler* compiler_;
+
+  // List of moves not yet resolved.
+  GrowableArray<MoveOperands> moves_;
+};
+
+
+class DeoptimizationStub : public ZoneAllocated {
+ public:
+  DeoptimizationStub(intptr_t deopt_id,
+                     intptr_t deopt_token_pos,
+                     intptr_t try_index,
+                     DeoptReasonId reason)
+      : deopt_id_(deopt_id),
+        deopt_token_pos_(deopt_token_pos),
+        try_index_(try_index),
+        reason_(reason),
+        registers_(2),
+        deoptimization_env_(NULL),
+        entry_label_() {}
+
+  void Push(Register reg) { registers_.Add(reg); }
+  Label* entry_label() { return &entry_label_; }
+
+  // Implementation is in architecture specific file.
+  void GenerateCode(FlowGraphCompiler* compiler);
+
+  void set_deoptimization_env(Environment* env) {
+    deoptimization_env_ = env;
+  }
+
+ private:
+  const intptr_t deopt_id_;
+  const intptr_t deopt_token_pos_;
+  const intptr_t try_index_;
+  const DeoptReasonId reason_;
+  GrowableArray<Register> registers_;
+  const Environment* deoptimization_env_;
+  Label entry_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(DeoptimizationStub);
+};
+
 }  // namespace dart
 
 #if defined(TARGET_ARCH_IA32)
 #include "vm/flow_graph_compiler_ia32.h"
 #elif defined(TARGET_ARCH_X64)
 #include "vm/flow_graph_compiler_x64.h"
 #elif defined(TARGET_ARCH_ARM)
 #include "vm/flow_graph_compiler_arm.h"
 #else
 #error Unknown architecture.
 #endif
 
 #endif  // VM_FLOW_GRAPH_COMPILER_H_