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

runtime/vm/flow_graph_allocator.cc

 // 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.
 
 #include "vm/flow_graph_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 20 matching lines @@
 static const intptr_t kTempVirtualRegister = -2;
 static const intptr_t kIllegalPosition = -1;
 static const intptr_t kMaxPosition = 0x7FFFFFFF;
 
 
 static intptr_t MinPosition(intptr_t a, intptr_t b) {
   return (a < b) ? a : b;
 }
 
 
-static bool IsParallelMovePosition(intptr_t pos) {
-  return (pos & 1) == 0;
-}
-
-
 static bool IsInstructionStartPosition(intptr_t pos) {
   return (pos & 1) == 0;
 }
 
 
 static bool IsInstructionEndPosition(intptr_t pos) {
   return (pos & 1) == 1;
 }
 
 
@@ skipping 273 matching lines @@
 }
 
 
 void FlowGraphAllocator::BlockLocation(Location loc, intptr_t pos) {
   ASSERT(loc.IsRegister());
   const Register reg = loc.reg();
   if (blocked_cpu_regs_[reg]) return;
   if (cpu_regs_[reg].length() == 0) {
     cpu_regs_[reg].Add(new LiveRange(kNoVirtualRegister));
   }
-  cpu_regs_[reg][0]->AddUseInterval(pos, pos + 2);
+  cpu_regs_[reg][0]->AddUseInterval(pos, pos + 1);

[srdjan, 2012/07/31 15:58:35]

Please add comment about the interval range (beginning of instruction to end of
instruction?).

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

Done.

 }
 
 
 void LiveRange::Print() {
   OS::Print("  live range v%d [%d, %d)\n", vreg(), Start(), End());
   UsePosition* use_pos = uses_;
   for (UseInterval* interval = first_use_interval_;
        interval != NULL;
        interval = interval->next()) {
     OS::Print("    use interval [%d, %d)\n",
@@ skipping 123 matching lines @@
     BlockEntryInstr* block) {
   Instruction* last = block->last_instruction();
 
   GotoInstr* goto_instr = last->AsGoto();
   if (goto_instr == NULL) return last;
 
   // If we have a parallel move here then the successor block must be a
   // join with phis.  The phi inputs contribute uses to each predecessor
   // block (and the phi outputs contribute definitions in the successor
   // block).
-  ParallelMoveInstr* parallel_move = goto_instr->previous()->AsParallelMove();
-  if (parallel_move == NULL) return goto_instr->previous();
+  if (!goto_instr->HasParallelMove()) return goto_instr->previous();
+  ParallelMoveInstr* parallel_move = goto_instr->parallel_move();
 
   // All uses are recorded at the position of parallel move preceding goto.
   const intptr_t pos = goto_instr->lifetime_position();
-  ASSERT(parallel_move->lifetime_position() == pos);
 
   JoinEntryInstr* join = goto_instr->successor();
   ASSERT(join != NULL);
 
   // Search for the index of the current block in the predecessors of
   // the join.
   const intptr_t pred_idx = join->IndexOfPredecessor(block);
 
   // Record the corresponding phi input use for each phi.
   ZoneGrowableArray<PhiInstr*>* phis = join->phis();
@@ skipping 20 matching lines @@
       move->set_src(Location::PrefersRegister());
     } else {
       ASSERT(val->IsConstant());
       move->set_src(Location::Constant(val->AsConstant()->value()));
     }
     move_idx++;
   }
 
   // Begin backward iteration with the instruction before the parallel
   // move.
-  return parallel_move->previous();
+  return goto_instr->previous();
 }
 
 
 void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) {
   // If this block is a join we need to add destinations of phi
   // resolution moves to phi's live range so that register allocator will
   // fill them with moves.
   JoinEntryInstr* join = block->AsJoinEntry();
   if (join == NULL) return;
 
   // All uses are recorded at the start position in the block.
   const intptr_t pos = join->start_pos();
 
   ZoneGrowableArray<PhiInstr*>* phis = join->phis();
   if (phis != NULL) {
     intptr_t move_idx = 0;
     for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) {
       PhiInstr* phi = (*phis)[phi_idx];
       if (phi == NULL) continue;
 
       const intptr_t vreg = phi->ssa_temp_index();
       ASSERT(vreg != -1);
 
-      // Expected shape of live range:
+      // Expected sfhape of live range:

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

Accidental edit?

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

Done.

       //
       //                 B
       //      phi        [--------
       //
       LiveRange* range = GetLiveRange(vreg);
       range->DefineAt(pos);  // Shorten live range.
 
       for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) {
         BlockEntryInstr* pred = block->PredecessorAt(pred_idx);
-        ASSERT(pred->last_instruction()->IsGoto());
-        Instruction* move_instr = pred->last_instruction()->previous();
-        ASSERT(move_instr->IsParallelMove());
-
+        GotoInstr* goto_instr = pred->last_instruction()->AsGoto();
+        ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove()));
         MoveOperands* move =
-            move_instr->AsParallelMove()->MoveOperandsAt(move_idx);
+            goto_instr->parallel_move()->MoveOperandsAt(move_idx);
         move->set_dest(Location::PrefersRegister());
         range->AddUse(pos, move->dest_slot());
       }
 
       // All phi resolution moves are connected. Phi's live range is
       // complete.
       AddToUnallocated(range);
 
       move_idx++;
     }
@@ skipping 93 matching lines @@
       range->AddUseInterval(block->start_pos(), pos + 1);
       range->AddUse(pos + 1, in_ref);
     }
   }
 
   // Process temps.
   for (intptr_t j = 0; j < locs->temp_count(); j++) {
     // Expected shape of live range:
     //
     //              i  i'
-    //              [-----)
+    //              [--)
     //
 
     Location temp = locs->temp(j);
     if (temp.IsRegister()) {
       BlockLocation(temp, pos);
     } else if (temp.IsUnallocated()) {
       LiveRange* range = new LiveRange(kTempVirtualRegister);
       range->AddUseInterval(pos, pos + 1);
       range->AddUse(pos, locs->temp_slot(j));
       AddToUnallocated(range);
     } else {
       UNREACHABLE();
     }
   }
 
   // Block all allocatable registers for calls.
   if (locs->is_call()) {
     // Expected shape of live range:
     //
     //              i  i'
-    //              [-----)
+    //              [--)
     //
 
     for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
       BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
                     pos);
     }
 
 #ifdef DEBUG
     // Verify that temps, inputs and output were specified as fixed
     // locations.  Every register is blocked now so attempt to
@@ skipping 26 matching lines @@
   LiveRange* range = (def->ssa_temp_index() >= 0) ?
       GetLiveRange(def->ssa_temp_index()) :
       new LiveRange(kTempVirtualRegister);
   Location* out = locs->out_slot();
 
   // Process output and finalize its liverange.
   if (out->IsRegister()) {
     // Fixed output location. Expected shape of live range:
     //
     //                    i  i' j  j'
-    //    register        [-----)
+    //    register        [--)
     //    output             [-------
     //
     BlockLocation(*out, pos);
 
     if (range->vreg() == kTempVirtualRegister) return;
 
     // We need to emit move connecting fixed register with another location
     // that will be allocated for this output's live range.
     // Special case: fixed output followed by a fixed input last use.
     UsePosition* use = range->first_use();
-    if (use->pos() == (pos + 2)) {
+    if (use->pos() == (pos + 1)) {
       ASSERT(use->location_slot()->IsUnallocated());
       *(use->location_slot()) = *out;
 
       // Remove first use. It was allocated.
       range->set_first_use(range->first_use()->next());
     }
 
     // Shorten live range to the point of definition, this might make the range
     // empty (if the only use immediately follows). If range is not empty add
     // move from a fixed register to an unallocated location.
-    range->DefineAt(pos + 2);
+    range->DefineAt(pos + 1);
     if (range->Start() == range->End()) return;
 
-    MoveOperands* move = AddMoveAt(pos + 2, Location::PrefersRegister(), *out);
-    range->AddUse(pos + 2, move->dest_slot());
+    MoveOperands* move = AddMoveAt(pos + 1, Location::PrefersRegister(), *out);
+    range->AddUse(pos + 1, move->dest_slot());
   } else if (output_same_as_first_input) {
     // Output register will contain a value of the first input at instruction's
     // start. Expected shape of live ranges:
     //
     //                 i  i'
     //    input #0   --*
     //    output       [----
     //
     ASSERT(locs->in_slot(0)->Equals(Location::RequiresRegister()));
 
@@ skipping 104 matching lines @@
     JoinEntryInstr* join = block->AsJoinEntry();
     if ((join != NULL) && (join->phi_count() > 0)) {
       const intptr_t phi_count = join->phi_count();
       for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
         // Insert the move between the last two instructions of the
         // predecessor block (all such blocks have at least two instructions:
         // the block entry and goto instructions.)
         Instruction* last = block->PredecessorAt(i)->last_instruction();
         ASSERT(last->IsGoto());
 
-        ParallelMoveInstr* move =
-            CreateParallelMoveBefore(last, last->lifetime_position());
+        ParallelMoveInstr* move = last->AsGoto()->GetParallelMove();
 
         // Populate the ParallelMove with empty moves.
         for (intptr_t j = 0; j < phi_count; j++) {
           move->AddMove(Location::NoLocation(), Location::NoLocation());
         }
-
-        // Replace Goto instruction with the corresponding move in
-        // the array of instructions.  This is done to ensure that
-        // this parallel move will be treated as a normal instruction
-        // by AddMoveAt for the purpose of live ranges connections (i.e.
-        // a separate move will be inserted by AddMoveAt)
-        // This move can't be reused by AddMoveAt to insert
-        // moves at Goto position because such range connecting moves might
-        // come into a conflict with phi connecting moves due to implicit
-        // interference: phi-value's liferange starts only at successor block
-        // but the move is actually performed at the predecessor.
-        ASSERT(instructions_[last->lifetime_position() / 2] == last);
-        instructions_[last->lifetime_position() / 2] = move;
       }
     }
   }
 }
 
 
 Instruction* FlowGraphAllocator::InstructionAt(intptr_t pos) const {
   return instructions_[pos / 2];
 }
 
 
 bool FlowGraphAllocator::IsBlockEntry(intptr_t pos) const {
-  return InstructionAt(pos)->IsBlockEntry();
+  return IsInstructionStartPosition(pos) && InstructionAt(pos)->IsBlockEntry();
 }
 
 
 void AllocationFinger::Initialize(LiveRange* range) {
   first_pending_use_interval_ = range->first_use_interval();
   first_register_use_ = range->first_use();
   first_register_beneficial_use_ = range->first_use();
   first_hinted_use_ = range->first_use();
 }
 
@@ skipping 149 matching lines @@
     first_after_split : last_use_interval_;
   next_sibling_ = new LiveRange(vreg(),
                                 first_use_after_split,
                                 first_after_split,
                                 last_use_interval,
                                 next_sibling_);
 
   TRACE_ALLOC(("  split sibling [%d, %d)\n",
                next_sibling_->Start(), next_sibling_->End()));
 
-  // Split sibling can only start at a parallel move.
-  ASSERT(IsParallelMovePosition(next_sibling_->Start()));
-
   last_use_interval_ = last_before_split;
   last_use_interval_->next_ = NULL;
   return next_sibling_;
 }
 
 
 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range,
                                             intptr_t from,
                                             intptr_t to) {
   // TODO(vegorov): select optimal split position based on loop structure.
   TRACE_ALLOC(("split %d [%d, %d) between [%d, %d)\n",
                range->vreg(), range->Start(), range->End(), from, to));
 
   // Prefer spliting at instruction starts if possible.
   if (from < ToInstructionStart(to)) {
     to = ToInstructionStart(to);
   }
 
+  if (to == range->End()) to -= 1;

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

A comment would be good here.

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

Done.

+
   return range->SplitAt(to);
 }
 
 
 void FlowGraphAllocator::SpillBetween(LiveRange* range,
                                       intptr_t from,
                                       intptr_t to) {
   ASSERT(from < to);
   TRACE_ALLOC(("spill %d [%d, %d) between [%d, %d)\n",
                range->vreg(), range->Start(), range->End(), from, to));
@@ skipping 282 matching lines @@
     SpillBetween(allocated, spill_position, restore_position);
   }
 
   return true;
 }
 
 
 MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos,
                                             Location to,
                                             Location from) {
+  ASSERT(!IsBlockEntry(pos));
+
   Instruction* instr = InstructionAt(pos);
-  ASSERT(!instr->IsBlockEntry());
 
   ParallelMoveInstr* parallel_move = NULL;
   if (IsInstructionStartPosition(pos)) {
     parallel_move = CreateParallelMoveBefore(instr, pos);
   } else {
     parallel_move = CreateParallelMoveAfter(instr, pos);
   }
 
   return parallel_move->AddMove(to, from);
 }
@@ skipping 165 matching lines @@
 
   TRACE_ALLOC(("connecting [%d, %d) [%s] to [%d, %d) [%s]\n",
                source_cover->Start(), source_cover->End(), source.Name(),
                target_cover->Start(), target_cover->End(), target.Name()));
 
   // Siblings were allocated to the same register.
   if (source.Equals(target)) return;
 
   Instruction* last = source_block->last_instruction();
   if (last->SuccessorCount() == 1) {
-    CreateParallelMoveBefore(last, last->lifetime_position())->
-      AddMove(target, source);
+    ASSERT(last->IsGoto());
+    last->AsGoto()->GetParallelMove()->AddMove(target, source);
   } else {
-    CreateParallelMoveAfter(target_block, target_block->start_pos())->
-      AddMove(target, source);
+    target_block->GetParallelMove()->AddMove(target, source);
   }
 }
 
 
 void FlowGraphAllocator::ResolveControlFlow() {
   // Resolve linear control flow between touching split siblings
   // inside basic blocks.
   for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) {
     LiveRange* range = live_ranges_[vreg];
     if (range == NULL) continue;
 
     while (range->next_sibling() != NULL) {
       LiveRange* sibling = range->next_sibling();
+      TRACE_ALLOC(("connecting [%d, %d) [%s] to [%d, %d) [%s]\n",
+                  range->Start(), range->End(),
+                  range->assigned_location().Name(),
+                  sibling->Start(), sibling->End(),
+                  sibling->assigned_location().Name()));
       if ((range->End() == sibling->Start()) &&
           !range->assigned_location().Equals(sibling->assigned_location()) &&
           !IsBlockEntry(range->End())) {
         AddMoveAt(sibling->Start(),
                   sibling->assigned_location(),
                   range->assigned_location());
       }
       range = sibling;
     }
   }
@@ skipping 35 matching lines @@
 
   if (FLAG_trace_ssa_allocator) {
     OS::Print("-- ir after allocation -------------------------\n");
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart