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),
+        lifetime_position_(-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 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_;
   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 14 matching lines @@
       : preorder_number_(-1),
         postorder_number_(-1),
         block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL) { }
 
  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_;
   Instruction* last_instruction_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class ForwardInstructionIterator : public ValueObject {
@@ skipping 392 matching lines @@
 };
 
 
 class MoveOperands : public ValueObject {
  public:
   MoveOperands(Location dest, Location src) : dest_(dest), src_(src) { }
 
   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_;
 };
 
 
 class ParallelMoveInstr : public Instruction {
  public:
-  ParallelMoveInstr() : moves_(1) { }
+  explicit ParallelMoveInstr() : moves_(4) {
+  }
 
   DECLARE_INSTRUCTION(ParallelMove)
 
   void AddMove(Location dest, Location src) {
     moves_.Add(MoveOperands(dest, src));
   }
 
   const GrowableArray<MoveOperands>& moves() { return moves_; }
 
  private:
   GrowableArray<MoveOperands> moves_;
 
   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 {
+    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_