Skeleton of a linear scan register allocator.

runtime/vm/intermediate_language.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_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 1703 matching lines @@
   virtual void SetInputAt(intptr_t i, Value* value);                           \
   virtual const char* DebugName() const { return #type; }                      \
   virtual void PrintTo(BufferFormatter* f) const;                              \
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
 
 class Instruction : public ZoneAllocated {
  public:
   Instruction()
       : cid_(-1),
+        pos_(-1),
         ic_data_(NULL),
         previous_(NULL),
         next_(NULL),
         env_(NULL) {
     Isolate* isolate = Isolate::Current();
     cid_ = Computation::GetNextCid(isolate);
     ic_data_ = Computation::GetICDataForCid(cid_, isolate);
   }
 
   // Unique computation/instruction id, used for deoptimization, e.g. for
@@ skipping 94 matching lines @@
     return NULL;
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) {
     UNIMPLEMENTED();
   }
 
   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_;
   Environment* env_;
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 class InstructionWithInputs : public Instruction {
  public:
@@ skipping 31 matching lines @@
 
   intptr_t preorder_number() const { return preorder_number_; }
   void set_preorder_number(intptr_t number) { preorder_number_ = number; }
 
   intptr_t postorder_number() const { return postorder_number_; }
   void set_postorder_number(intptr_t number) { postorder_number_ = number; }
 
   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; }
 
   const GrowableArray<BlockEntryInstr*>& dominated_blocks() {
     return dominated_blocks_;
   }
 
   void AddDominatedBlock(BlockEntryInstr* block) {
     dominated_blocks_.Add(block);
   }
@@ skipping 15 matching lines @@
         postorder_number_(-1),
         block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL) { }
 
  private:
   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_;
   Instruction* last_instruction_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class ForwardInstructionIterator : public ValueObject {
@@ skipping 387 matching lines @@
   TargetEntryInstr* false_successor_;
   bool is_fused_with_comparison_;
   bool is_negated_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };
 
 
 class MoveOperands : public ValueObject {
  public:
   MoveOperands(Location dest, Location src) : dest_(dest), src_(src) { }

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

Should you ASSERT which types of Location's are allowed?

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

It's pretty hard because register allocator fills most of it incrementally.

 
   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_;
 };
 
 
 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)
 
   void AddMove(Location dest, Location src) {
     moves_.Add(MoveOperands(dest, src));
   }
 
   const GrowableArray<MoveOperands>& moves() { return moves_; }
 
  private:
   GrowableArray<MoveOperands> moves_;

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

Why is this not MoveOperands* ?

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

I am not sure what additional indirection buys us here.

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

It is more fragile, since it can get suddenly really slow if somebody adds
fields to MoveOperands. How about adding a comment/warning to MoveOperands?

 
   DISALLOW_COPY_AND_ASSIGN(ParallelMoveInstr);
 };
 
 #undef DECLARE_INSTRUCTION
 
 
 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);
 };
 
 
 // Visitor base class to visit each instruction and computation in a flow
 // graph as defined by a reversed list of basic blocks.
 class FlowGraphVisitor : public ValueObject {
  public:
   explicit FlowGraphVisitor(const GrowableArray<BlockEntryInstr*>& block_order)
       : block_order_(block_order) { }
@@ skipping 21 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_