Ensure that we never try to split range at its end position.

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 1868 matching lines @@
   }
 
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
  private:
   LocationSummary* locs_;
   DISALLOW_COPY_AND_ASSIGN(InstructionWithInputs);
 };
 
 
+class MoveOperands : public ZoneAllocated {
+ 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(const Location& value) { src_ = value; }
+  void set_dest(const Location& value) { dest_ = value; }
+
+  // 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_;
+
+  DISALLOW_COPY_AND_ASSIGN(MoveOperands);
+};
+
+
+class ParallelMoveInstr : public Instruction {
+ public:
+  ParallelMoveInstr() : moves_(4) {
+  }
+
+  DECLARE_INSTRUCTION(ParallelMove)
+
+  virtual intptr_t ArgumentCount() const { return 0; }
+
+  MoveOperands* AddMove(Location dest, Location src) {
+    MoveOperands* move = new MoveOperands(dest, src);
+    moves_.Add(move);
+    return move;
+  }
+
+  MoveOperands* MoveOperandsAt(intptr_t index) const { return moves_[index]; }
+
+  void SetSrcSlotAt(intptr_t index, const Location& loc);
+  void SetDestSlotAt(intptr_t index, const Location& loc);
+
+  intptr_t NumMoves() const { return moves_.length(); }
+
+ private:
+  GrowableArray<MoveOperands*> moves_;   // Elements cannot be null.
+
+  DISALLOW_COPY_AND_ASSIGN(ParallelMoveInstr);
+};
+
+
 // Basic block entries are administrative nodes.  There is a distinguished
 // graph entry with no predecessor.  Joins are the only nodes with multiple
 // predecessors.  Targets are all other basic block entries.  The types
 // enforce edge-split form---joins are forbidden as the successors of
 // branches.
 class BlockEntryInstr : public Instruction {
  public:
   virtual bool IsBlockEntry() const { return true; }
 
   virtual intptr_t PredecessorCount() const = 0;
@@ skipping 22 matching lines @@
     return dominated_blocks_;
   }
 
   void AddDominatedBlock(BlockEntryInstr* block) {
     dominated_blocks_.Add(block);
   }
 
   Instruction* last_instruction() const { return last_instruction_; }
   void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
 
+  ParallelMoveInstr* parallel_move() const {
+    return parallel_move_;
+  }
+
+  bool HasParallelMove() const {
+    return parallel_move_ != NULL;
+  }
+
+  ParallelMoveInstr* GetParallelMove() {
+    if (parallel_move_ == NULL) {
+      parallel_move_ = new ParallelMoveInstr();
+    }
+    return parallel_move_;
+  }
+
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
       GrowableArray<intptr_t>* parent,
       GrowableArray<BitVector*>* assigned_vars,
       intptr_t variable_count,
       intptr_t fixed_parameter_count);
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
  protected:
   BlockEntryInstr()
       : preorder_number_(-1),
         postorder_number_(-1),
         block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
-        last_instruction_(NULL) { }
+        last_instruction_(NULL),
+        parallel_move_(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_;
 
+  // Parallel move that will be used by linear scan register allocator to
+  // connect live ranges at the start of the block.
+  ParallelMoveInstr* parallel_move_;
+
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class ForwardInstructionIterator : public ValueObject {
  public:
   explicit ForwardInstructionIterator(BlockEntryInstr* block_entry)
       : block_entry_(block_entry), current_(block_entry) {
     ASSERT(block_entry_->last_instruction()->next() == NULL);
     Advance();
@@ skipping 400 matching lines @@
   const intptr_t try_index_;
   Value* exception_;
   Value* stack_trace_;
 
   DISALLOW_COPY_AND_ASSIGN(ReThrowInstr);
 };
 
 
 class GotoInstr : public InstructionWithInputs {
  public:
-  explicit GotoInstr(JoinEntryInstr* entry) : successor_(entry) { }
+  explicit GotoInstr(JoinEntryInstr* entry)
+    : successor_(entry),
+      parallel_move_(NULL) {
+  }
 
   DECLARE_INSTRUCTION(Goto)
 
   JoinEntryInstr* successor() const { return successor_; }
   void set_successor(JoinEntryInstr* successor) { successor_ = successor; }
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   virtual LocationSummary* MakeLocationSummary() const;
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
+  ParallelMoveInstr* parallel_move() const {
+    return parallel_move_;
+  }
+
+  bool HasParallelMove() const {
+    return parallel_move_ != NULL;
+  }
+
+  ParallelMoveInstr* GetParallelMove() {
+    if (parallel_move_ == NULL) {
+      parallel_move_ = new ParallelMoveInstr();
+    }
+    return parallel_move_;
+  }
+
  private:
   JoinEntryInstr* successor_;
+
+  // Parallel move that will be used by linear scan register allocator to
+  // connect live ranges at the start of the block.

[Florian Schneider, 2012/07/31 15:31:59]

s/start/end/

[Vyacheslav Egorov (Google), 2012/07/31 16:18:49]

Done.

+  ParallelMoveInstr* parallel_move_;
 };
 
 
 class BranchInstr : public InstructionWithInputs {
  public:
   BranchInstr(intptr_t token_pos,
               intptr_t try_index,
                Value* left,
              Value* right,
               Token::Kind kind)
@@ skipping 57 matching lines @@
   Value* left_;
   Value* right_;
   Token::Kind kind_;
   TargetEntryInstr* true_successor_;
   TargetEntryInstr* false_successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };
 
 
-class MoveOperands : public ZoneAllocated {
- 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(const Location& value) { src_ = value; }
-  void set_dest(const Location& value) { dest_ = value; }
-
-  // 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_;
-
-  DISALLOW_COPY_AND_ASSIGN(MoveOperands);
-};
-
-
-class ParallelMoveInstr : public Instruction {
- public:
-  ParallelMoveInstr() : moves_(4) {
-  }
-
-  DECLARE_INSTRUCTION(ParallelMove)
-
-  virtual intptr_t ArgumentCount() const { return 0; }
-
-  MoveOperands* AddMove(Location dest, Location src) {
-    MoveOperands* move = new MoveOperands(dest, src);
-    moves_.Add(move);
-    return move;
-  }
-
-  MoveOperands* MoveOperandsAt(intptr_t index) const { return moves_[index]; }
-
-  void SetSrcSlotAt(intptr_t index, const Location& loc);
-  void SetDestSlotAt(intptr_t index, const Location& loc);
-
-  intptr_t NumMoves() const { return moves_.length(); }
-
- private:
-  GrowableArray<MoveOperands*> moves_;   // Elements cannot be null.
-
-  DISALLOW_COPY_AND_ASSIGN(ParallelMoveInstr);
-};
-
 #undef DECLARE_INSTRUCTION
 
 
 class Environment : public ZoneAllocated {
  public:
   // Construct an environment by copying from an array of values.
   // TODO(vegorov): it's absolutely crucial that locations_ backing store
   // is preallocated and never reallocated.  We use pointers into it
   // during register allocation.
   explicit Environment(const GrowableArray<Value*>& values,
@@ skipping 65 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_