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..226448ca3e03cd5629cc2e1b2cf18041b11e8850 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),
+        pos_(-1),
         ic_data_(NULL),
         previous_(NULL),
         next_(NULL),
@@ -1835,8 +1836,12 @@ FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
   Environment* env() const { return env_; }
   void set_env(Environment* env) { env_ = env; }
 
+  intptr_t pos() const { return pos_; }
+  void set_pos(intptr_t pos) { pos_ = pos; }
+
  private:
   intptr_t cid_;
+  intptr_t pos_;

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

Please add comments:
cid_;   // Computation id.
pos_;  // ??

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

Done. Actually currently this positions are rarely needed. 
So we might eliminate them entirely instead of making every instructions one
word bigger.

   ICData* ic_data_;
   Instruction* previous_;
   Instruction* next_;
@@ -1888,6 +1893,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; }
 
@@ -1923,6 +1933,8 @@ class BlockEntryInstr : public Instruction {
   intptr_t preorder_number_;
   intptr_t postorder_number_;
   intptr_t block_id_;
+  intptr_t start_pos_;
+  intptr_t end_pos_;

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

Please add comment what the two fields are good for.

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

Done.

   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 +2347,50 @@ class MoveOperands : public ValueObject {
   Location src() const { return src_; }
   Location dest() const { return dest_; }
 
+  Location* src_slot() { return &src_; }
+  Location* dest_slot() { return &dest_; }

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

Why are those called slots? Since src() and dest(), I would rather call the
getters src_ptr and dest_ptr.

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

I called them _ptr before but then changed to slot to better convey semantics:
return a place where a real location will be placed by the allocator hence
"slot".

+
+  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() {
+    Location dest = dest_;
+    dest_ = Location::NoLocation();
+    return dest;

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

Wouldn't it be much simpler to use a field bool is_pending_?  Should it be
called MarkInProgress instead? I would read Pending as something that has to
happen yet, maybe has not started yet or is in progress.

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

I suspect it will be simpler, but bool will waste a word in every parallel move.


(implementation of parallel move resolution is copied from V8 keeping names sans
differences between Dart VM Location and V8's LOperands).

[srdjan, 2012/07/11 17:22:31]

OK

+  }
+
+  void ClearPending(Location dest) {
+    ASSERT(IsPending());
+    dest_ = dest;
+  }
+
+  bool IsPending() const {
+    return dest_.IsInvalid() && !src_.IsInvalid();
+  }
+
+  // True if this move a move into the given destination location.

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

Fix comment.

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

Oh, yeah, this cost me some pain in debugging. Initially I implemented the
method based on the comment, which did not work, but once I fixed implementation
I forgot to fix the comment.

+  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() || src_.Equals(dest_) || IsIgnored();
+  }
+
+  bool IsIgnored() const {
+    return dest_.IsInvalid();
+  }

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

This means that every IsPending is also IsIgnored?

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

yes.

removed IsIgnored, it was only used from IsRedundant which is used only to form
list of initial moves.

+
+  // 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());

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

Can you add this assert to MarkPending, ClearPending as well?

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

Done.

+    return src_.IsInvalid();
+  }
+
  private:
   Location dest_;
   Location src_;
@@ -2343,7 +2399,8 @@ class MoveOperands : public ValueObject {
 
 class ParallelMoveInstr : public Instruction {
  public:
-  ParallelMoveInstr() : moves_(1) { }
+  explicit ParallelMoveInstr(intptr_t move_count) : moves_(move_count) {

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

I think passing the move_count for optimization purposes does not bring much,
instead you could give it default value of 4 or similar.  Unless you want to
check that we do not emit more moves than move_count, in which case I would add
an ASSERT to AddMove (and which would require to add a capacity getter to
GrowableArray). Maybe we could add a limited GrowableArray that cannot grow past
its capacity?

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

Changed to 4 for now. Can optimize memory usage later.

+  }
 
   DECLARE_INSTRUCTION(ParallelMove)
 
@@ -2366,18 +2423,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 {

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

Is it really necessary to have const overloaded getters?

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

Deoptimization stub references const Environment* so I need a const version of
this getter. I can't remove non-const getter because register allocator want to
get hold of non-const slots inside the array.

[srdjan, 2012/07/11 17:22:31]

How about renaming it to const_locations() then ?

+    return &locations_;
+  }
+
   void PrintTo(BufferFormatter* f) const;
 
  private:
   ZoneGrowableArray<Value*> values_;
+  GrowableArray<Location> locations_;
   DISALLOW_COPY_AND_ASSIGN(Environment);
 };