Allow deoptimization from states with spilled values.

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 25 matching lines @@
 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 IsInstructionPosition(intptr_t pos) {
+static bool IsInstructionStartPosition(intptr_t pos) {
+  return (pos & 1) == 0;
+}
+
+
+static bool IsInstructionEndPosition(intptr_t pos) {
   return (pos & 1) == 1;
 }
 
 
-static intptr_t ToParallelMove(intptr_t pos) {
+static intptr_t ToInstructionStart(intptr_t pos) {
   return (pos & ~1);
 }
 
+
 FlowGraphAllocator::FlowGraphAllocator(
   const GrowableArray<BlockEntryInstr*>& block_order,
   FlowGraphBuilder* builder)
   : builder_(builder),
     block_order_(block_order),
     postorder_(builder->postorder_block_entries()),
     live_out_(block_order.length()),
     kill_(block_order.length()),
     live_in_(block_order.length()),
     vreg_count_(builder->current_ssa_temp_index()),
@@ skipping 251 matching lines @@
 
 
 LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) {
   if (live_ranges_[vreg] == NULL) {
     live_ranges_[vreg] = new LiveRange(vreg);
   }
   return live_ranges_[vreg];
 }
 
 
-void FlowGraphAllocator::BlockLocation(Location loc,
-                                       intptr_t from,
-                                       intptr_t to) {
+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(from, to);
+  cpu_regs_[reg][0]->AddUseInterval(pos, pos + 2);
 }
 
 
 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 92 matching lines @@
       }
       ConvertAllUses(range);
     }
   }
 }
 
 //
 // When describing shape of live ranges in comments below we are going to use
 // the following notation:
 //
-//    B  block entry
-//    g  goto instruction
-//    m  parallel move
-//    i  any other instruction
-//
+//    B    block entry
+//    g g' start and end of goto instruction
+//    i i' start and end of any other instruction
+//    j j' start and end of any other instruction
+
 //    -  body of a use interval
 //    [  start of a use interval
 //    )  end of a use interval
 //    *  use
 //
 // For example diagram
 //
-//           m i
-//  value  --*-)
+//           i  i'
+//  value  --*--)
 //
-// can be read as: use interval for value starts somewhere before parallel move
+// can be read as: use interval for value starts somewhere before instruction
 // and extends until currently processed instruction, there is a use of value
-// at a position of the parallel move.
+// at the start of the instruction.
 //
 
 Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves(
     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();
 
   // All uses are recorded at the position of parallel move preceding goto.
-  const intptr_t pos = goto_instr->lifetime_position() - 1;
-  ASSERT((pos >= 0) && IsParallelMovePosition(pos));
+  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();
   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;
 
     Value* val = phi->InputAt(pred_idx);
     MoveOperands* move = parallel_move->MoveOperandsAt(move_idx);
     if (val->IsUse()) {
       // Expected shape of live ranges:
       //
-      //                 m  g
+      //                 g  g'
       //      value    --*
       //
 
       LiveRange* range = GetLiveRange(
           val->AsUse()->definition()->ssa_temp_index());
 
       range->AddUseInterval(block->start_pos(), pos);
       range->AddUse(pos, move->src_slot());
 
       move->set_src(Location::PrefersRegister());
@@ skipping 58 matching lines @@
     }
   }
 }
 
 
 // Create and update live ranges corresponding to instruction's inputs,
 // temporaries and output.
 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
                                                Instruction* current) {
   const intptr_t pos = current->lifetime_position();
-  ASSERT(IsInstructionPosition(pos));
+  ASSERT(IsInstructionStartPosition(pos));
 
   LocationSummary* locs = current->locs();
 
   // TODO(vegorov): number of inputs must match number of input locations.
   if (locs->input_count() != current->InputCount()) {
     builder_->Bailout("ssa allocator: number of input locations mismatch");
   }
 
   // Normalize same-as-first-input output if input is specified as
   // fixed register.
   if (locs->out().IsUnallocated() &&
       (locs->out().policy() == Location::kSameAsFirstInput) &&
       (locs->in(0).IsRegister())) {
     locs->set_out(locs->in(0));
   }
 
   const bool output_same_as_first_input =
       locs->out().IsUnallocated() &&
       (locs->out().policy() == Location::kSameAsFirstInput);
 
   // Add uses from the deoptimization environment.
   if (current->env() != NULL) {
     // Any value mentioned in the deoptimization environment should survive
     // until the end of instruction but it does not need to be in the register.
     // Expected shape of live range:
     //
-    //                 m  i  m
-    //      value    -----*--)
+    //                 i  i'
+    //      value    -----*
     //
 
     Environment* env = current->env();
     const GrowableArray<Value*>& values = env->values();
 
     for (intptr_t j = 0; j < values.length(); j++) {
       Value* val = values[j];
       if (val->IsUse()) {
         env->AddLocation(Location::Any());
         const intptr_t vreg = val->AsUse()->definition()->ssa_temp_index();
 
         LiveRange* range = GetLiveRange(vreg);
         range->AddUseInterval(block->start_pos(), pos + 1);
-        range->AddUse(pos, env->LocationSlotAt(j));
+        range->AddUse(pos + 1, env->LocationSlotAt(j));
       } else {
         ASSERT(val->IsConstant());
         env->AddLocation(Location::NoLocation());
       }
     }
   }
 
   // Process inputs.
   // Skip the first input if output is specified with kSameAsFirstInput policy,
   // they will be processed together at the very end.
   for (intptr_t j = output_same_as_first_input ? 1 : 0;
        j < current->InputCount();
        j++) {
     Value* input = current->InputAt(j);
     ASSERT(input->IsUse());  // Can not be a constant currently.
     const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index();
     LiveRange* range = GetLiveRange(vreg);
 
     Location* in_ref = locs->in_slot(j);
 
     if (in_ref->IsRegister()) {
       // Input is expected in a fixed register. Expected shape of
       // live ranges:
       //
-      //                 m  i  m
+      //                 i  i'
       //      value    --*
-      //      register   [-----)
+      //      register   [--)
       //
       MoveOperands* move =
-          AddMoveAt(pos - 1, *in_ref, Location::PrefersRegister());
-      BlockLocation(*in_ref, pos - 1, pos + 1);
-      range->AddUseInterval(block->start_pos(), pos - 1);
-      range->AddUse(pos - 1, move->src_slot());
+          AddMoveAt(pos, *in_ref, Location::PrefersRegister());
+      BlockLocation(*in_ref, pos);
+      range->AddUseInterval(block->start_pos(), pos);
+      range->AddUse(pos, move->src_slot());
     } else {
       // Normal unallocated input. Expected shape of
       // live ranges:
       //
-      //                 m  i  m
-      //      value    -----*--)
+      //                 i  i'
+      //      value    -----*
       //
       ASSERT(in_ref->IsUnallocated());
       range->AddUseInterval(block->start_pos(), pos + 1);
-      range->AddUse(pos, in_ref);
+      range->AddUse(pos + 1, in_ref);
     }
   }
 
   // Process temps.
   for (intptr_t j = 0; j < locs->temp_count(); j++) {
     // Expected shape of live range:
     //
-    //           m  i  m
-    //              [--)
+    //              i  i'
+    //              [-----)
     //
 
     Location temp = locs->temp(j);
     if (temp.IsRegister()) {
-      BlockLocation(temp, pos, pos + 1);
+      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:
     //
-    //           m  i  m
-    //              [--)
+    //              i  i'
+    //              [-----)
     //
 
     for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
       BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
-                    pos,
-                    pos + 1);
+                    pos);
     }
 
 #ifdef DEBUG
     // Verify that temps, inputs and output were specified as fixed
     // locations.  Every register is blocked now so attempt to
     // allocate will not succeed.
     for (intptr_t j = 0; j < locs->temp_count(); j++) {
       ASSERT(!locs->temp(j).IsUnallocated());
     }
 
@@ skipping 20 matching lines @@
   // such definitions.
   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:
     //
-    //                 m  i  m
-    //    register        [--)
+    //                    i  i' j  j'
+    //    register        [-----)
     //    output             [-------
     //
-    BlockLocation(*out, pos, pos + 1);
+    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 + 1)) {
-      // We have a use position on the parallel move.
+    if (use->pos() == (pos + 2)) {
       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 + 1);
+    range->DefineAt(pos + 2);
     if (range->Start() == range->End()) return;
 
-    MoveOperands* move = AddMoveAt(pos + 1, Location::PrefersRegister(), *out);
-    range->AddUse(pos + 1, move->dest_slot());
+    MoveOperands* move = AddMoveAt(pos + 2, Location::PrefersRegister(), *out);
+    range->AddUse(pos + 2, 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:
     //
-    //                 m  i  m
+    //                 i  i'
     //    input #0   --*
-    //    output       [--*----
+    //    output       [----
     //
     ASSERT(locs->in_slot(0)->Equals(Location::RequiresRegister()));
 
     // Create move that will copy value between input and output.
     locs->set_out(Location::RequiresRegister());
-    MoveOperands* move = AddMoveAt(pos - 1,
+    MoveOperands* move = AddMoveAt(pos,
                                    Location::RequiresRegister(),
                                    Location::PrefersRegister());
 
     // Add uses to the live range of the input.
     Value* input = current->InputAt(0);
     ASSERT(input->IsUse());  // Can not be a constant currently.
     LiveRange* input_range = GetLiveRange(
       input->AsUse()->definition()->ssa_temp_index());
-    input_range->AddUseInterval(block->start_pos(), pos - 1);
-    input_range->AddUse(pos - 1, move->src_slot());
+    input_range->AddUseInterval(block->start_pos(), pos);
+    input_range->AddUse(pos, move->src_slot());
 
     // Shorten output live range to the point of definition and add both input
     // and output uses slots to be filled by allocator.
-    range->DefineAt(pos - 1);
-    range->AddUse(pos - 1, out);
-    range->AddUse(pos - 1, move->dest_slot());
+    range->DefineAt(pos);
+    range->AddUse(pos, out);
+    range->AddUse(pos, move->dest_slot());
     range->AddUse(pos, locs->in_slot(0));
   } else {
     // Normal unallocated location that requires a register. Expected shape of
     // live range:
     //
-    //                 m  i  m
+    //                    i  i'
     //    output          [-------
     //
     ASSERT(out->IsUnallocated() &&
            (out->policy() == Location::kRequiresRegister));
 
     // Shorten live range to the point of definition and add use to be filled by
     // allocator.
     range->DefineAt(pos);
     range->AddUse(pos, out);
   }
@@ skipping 37 matching lines @@
 void FlowGraphAllocator::NumberInstructions() {
   intptr_t pos = 0;
 
   // The basic block order is reverse postorder.
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = block_count - 1; i >= 0; i--) {
     BlockEntryInstr* block = postorder_[i];
 
     instructions_.Add(block);
     block->set_start_pos(pos);
-    block->set_lifetime_position(pos + 1);
+    block->set_lifetime_position(pos);
     pos += 2;
 
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
       // Do not assign numbers to parallel move instructions.
       if (!current->IsParallelMove()) {
         instructions_.Add(current);
-        current->set_lifetime_position(pos + 1);
+        current->set_lifetime_position(pos);
         pos += 2;
       }
     }
     block->set_end_pos(pos);
   }
 
   // Create parallel moves in join predecessors.  This must be done after
   // all instructions are numbered.
   for (intptr_t i = block_count - 1; i >= 0; i--) {
     BlockEntryInstr* block = postorder_[i];
 
     // For join entry predecessors create phi resolution moves if
     // necessary. They will be populated by the register allocator.
     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() - 1);
+            CreateParallelMoveBefore(last, last->lifetime_position());
 
         // 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];
 }
 
@@ skipping 102 matching lines @@
 
 LiveRange* LiveRange::MakeTemp(intptr_t pos, Location* location_slot) {
   UNREACHABLE();
   return NULL;
 }
 
 
 LiveRange* LiveRange::SplitAt(intptr_t split_pos) {
   if (Start() == split_pos) return this;
 
-  // Ranges can only be connected by parallel moves.
-  split_pos = ToParallelMove(split_pos);
-
   UseInterval* interval = finger_.first_pending_use_interval();
   ASSERT(interval->start() < split_pos);
 
   // Corner case. We need to start over to find previous interval.
   if (interval->start() == split_pos) interval = first_use_interval_;
 
   UseInterval* last_before_split = NULL;
   while (interval->end() <= split_pos) {
     last_before_split = interval;
     interval = interval->next();
@@ skipping 55 matching lines @@
   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);
+  }
+
   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 98 matching lines @@
         FirstIntersectionWithAllocated(static_cast<Register>(reg), unallocated);
 
       if (intersection > free_until) {
         candidate = static_cast<Register>(reg);
         free_until = intersection;
         if (free_until == kMaxPosition) break;
       }
     }
   }
 
-  if (free_until != kMaxPosition) free_until = ToParallelMove(free_until);
-
   // All registers are blocked by active ranges.
   if (free_until <= unallocated->Start()) return false;
 
   TRACE_ALLOC(("assigning free register %s to %d\n",
                Location::RegisterLocation(candidate).Name(),
                unallocated->vreg()));
 
   if (free_until != kMaxPosition) {
     // There was an intersection. Split unallocated.
     TRACE_ALLOC(("  splitting at %d\n", free_until));
@@ skipping 25 matching lines @@
     if (UpdateFreeUntil(static_cast<Register>(reg),
                         unallocated,
                         &free_until,
                         &blocked_at)) {
       candidate = static_cast<Register>(reg);
     }
   }
 
   if (free_until < register_use->pos()) {
     // Can't acquire free register. Spill until we really need one.
-    ASSERT(unallocated->Start() < ToParallelMove(register_use->pos()));
+    ASSERT(unallocated->Start() < ToInstructionStart(register_use->pos()));
     SpillBetween(unallocated, unallocated->Start(), register_use->pos());
     return;
   }
 
   if (blocked_at < unallocated->End()) {
     LiveRange* tail = SplitBetween(unallocated,
                                    unallocated->Start(),
                                    blocked_at);
     AddToUnallocated(tail);
   }
@@ skipping 118 matching lines @@
     SpillBetween(allocated, spill_position, restore_position);
   }
 
   return true;
 }
 
 
 MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos,
                                             Location to,
                                             Location from) {
-  ASSERT(IsParallelMovePosition(pos));
   Instruction* instr = InstructionAt(pos);
   ASSERT(!instr->IsBlockEntry());
-  return CreateParallelMoveBefore(instr, pos)->AddMove(to, from);
+
+  ParallelMoveInstr* parallel_move = NULL;
+  if (IsInstructionStartPosition(pos)) {
+    parallel_move = CreateParallelMoveBefore(instr, pos);
+  } else {
+    parallel_move = CreateParallelMoveAfter(instr, pos);
+  }
+
+  return parallel_move->AddMove(to, from);
 }
 
 
 void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) {
   ASSERT(use->location_slot() != NULL);
   Location* slot = use->location_slot();
   ASSERT(slot->IsUnallocated());
   ASSERT((slot->policy() == Location::kRequiresRegister) ||
          (slot->policy() == Location::kPrefersRegister) ||
          (slot->policy() == Location::kAny));
@@ skipping 116 matching lines @@
   TRACE_ALLOC(("Connect source_block=%d, target_block=%d\n",
                source_block->block_id(),
                target_block->block_id()));
   if (range->next_sibling() == NULL) {
     // Nothing to connect. The whole range was allocated to the same location.
     TRACE_ALLOC(("range %d has no siblings\n", range->vreg()));
     return;
   }
 
   const intptr_t source_pos = source_block->end_pos() - 1;
-  ASSERT(IsInstructionPosition(source_pos));
+  ASSERT(IsInstructionEndPosition(source_pos));
 
   const intptr_t target_pos = target_block->start_pos();
 
   Location target;
   Location source;
 
 #ifdef DEBUG
   LiveRange* source_cover = NULL;
   LiveRange* target_cover = NULL;
 #endif
@@ skipping 19 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() - 1)->
+    CreateParallelMoveBefore(last, last->lifetime_position())->
       AddMove(target, source);
   } else {
     CreateParallelMoveAfter(target_block, target_block->start_pos())->
       AddMove(target, source);
   }
 }
 
 
 void FlowGraphAllocator::ResolveControlFlow() {
   // Resolve linear control flow between touching split siblings
@@ skipping 52 matching lines @@
 
   if (FLAG_trace_ssa_allocator) {
     OS::Print("-- ir after allocation -------------------------\n");
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart