Skeleton of a linear scan register allocator.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
diff --git a/runtime/vm/intermediate_language.h b/runtime/vm/intermediate_language.h
index 407e181af3fcb7cd029e8dec6953a0327ad5fd95..3577e2d4c9c27b663146ac867513dcb1d3b3c20c 100644
--- a/runtime/vm/intermediate_language.h
+++ b/runtime/vm/intermediate_language.h
@@ -1721,6 +1721,7 @@ class Instruction : public ZoneAllocated {
  public:
   Instruction()
       : cid_(-1),
+        lifetime_position_(-1),
         ic_data_(NULL),
         previous_(NULL),
         next_(NULL),
@@ -1835,8 +1836,14 @@ FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
   Environment* env() const { return env_; }
   void set_env(Environment* env) { env_ = env; }
 
+  intptr_t lifetime_position() const { return lifetime_position_; }
+  void set_lifetime_position(intptr_t pos) {
+    lifetime_position_ = pos;
+  }
+
  private:
-  intptr_t cid_;
+  intptr_t cid_;  // Computation id.
+  intptr_t lifetime_position_;  // Position used by register allocator.
   ICData* ic_data_;
   Instruction* previous_;
   Instruction* next_;
@@ -1888,6 +1895,11 @@ class BlockEntryInstr : public Instruction {
   intptr_t block_id() const { return block_id_; }
   void set_block_id(intptr_t value) { block_id_ = value; }
 
+  void set_start_pos(intptr_t pos) { start_pos_ = pos; }
+  intptr_t start_pos() const { return start_pos_; }
+  void  set_end_pos(intptr_t pos) { end_pos_ = pos; }
+  intptr_t end_pos() const { return end_pos_; }
+
   BlockEntryInstr* dominator() const { return dominator_; }
   void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
 
@@ -1922,7 +1934,11 @@ class BlockEntryInstr : public Instruction {
  private:
   intptr_t preorder_number_;
   intptr_t postorder_number_;
+  // Starting and ending lifetime positions for this block.  Used by
+  // the linear scan register allocator.
   intptr_t block_id_;
+  intptr_t start_pos_;
+  intptr_t end_pos_;
   BlockEntryInstr* dominator_;  // Immediate dominator, NULL for graph entry.
   // TODO(fschneider): Optimize the case of one child to save space.
   GrowableArray<BlockEntryInstr*> dominated_blocks_;
@@ -2335,6 +2351,48 @@ class MoveOperands : public ValueObject {
   Location src() const { return src_; }
   Location dest() const { return dest_; }
 
+  Location* src_slot() { return &src_; }
+  Location* dest_slot() { return &dest_; }
+
+  void set_src(Location src) { src_ = src; }
+
+  // The parallel move resolver marks moves as "in-progress" by clearing the
+  // destination (but not the source).
+  Location MarkPending() {
+    ASSERT(!IsPending());
+    Location dest = dest_;
+    dest_ = Location::NoLocation();
+    return dest;
+  }
+
+  void ClearPending(Location dest) {
+    ASSERT(IsPending());
+    dest_ = dest;
+  }
+
+  bool IsPending() const {
+    ASSERT(!src_.IsInvalid() || dest_.IsInvalid());
+    return dest_.IsInvalid() && !src_.IsInvalid();
+  }
+
+  // True if this move a move from the given location.
+  bool Blocks(Location loc) const {
+    return !IsEliminated() && src_.Equals(loc);
+  }
+
+  // A move is redundant if it's been eliminated, if its source and
+  // destination are the same, or if its destination is unneeded.
+  bool IsRedundant() const {
+    return IsEliminated() || dest_.IsInvalid() || src_.Equals(dest_);
+  }
+
+  // We clear both operands to indicate move that's been eliminated.
+  void Eliminate() { src_ = dest_ = Location::NoLocation(); }
+  bool IsEliminated() const {
+    ASSERT(!src_.IsInvalid() || dest_.IsInvalid());
+    return src_.IsInvalid();
+  }
+
  private:
   Location dest_;
   Location src_;
@@ -2343,7 +2401,8 @@ class MoveOperands : public ValueObject {
 
 class ParallelMoveInstr : public Instruction {
  public:
-  ParallelMoveInstr() : moves_(1) { }
+  explicit ParallelMoveInstr() : moves_(4) {
+  }
 
   DECLARE_INSTRUCTION(ParallelMove)
 
@@ -2366,18 +2425,27 @@ class Environment : public ZoneAllocated {
  public:
   // Construct an environment by copying from an array of values.
   explicit Environment(ZoneGrowableArray<Value*>* values)
-      : values_(values->length()) {
-          values_.AddArray(*values);
-        }
+      : values_(values->length()), locations_(values->length()) {
+    values_.AddArray(*values);
+  }
 
   const ZoneGrowableArray<Value*>& values() const {
     return values_;
   }
 
+  GrowableArray<Location>* locations() {
+    return &locations_;
+  }
+
+  const GrowableArray<Location>* locations() const {
+    return &locations_;
+  }
+
   void PrintTo(BufferFormatter* f) const;
 
  private:
   ZoneGrowableArray<Value*> values_;
+  GrowableArray<Location> locations_;
   DISALLOW_COPY_AND_ASSIGN(Environment);
 };