Fix bug in ParallelMoveResolver::EmitSwap: implement swaps of FPU spill slots.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2013, 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.h"
@@ skipping 588 matching lines @@
       // Slot index for the leftmost copied parameter is 0.
       intptr_t slot_index = param->index();
       // Slot index for the rightmost fixed parameter is -1.
       slot_index -= flow_graph_.num_non_copied_params();
 
       range->set_assigned_location(Location::StackSlot(slot_index));
       range->set_spill_slot(Location::StackSlot(slot_index));
       if (flow_graph_.num_copied_params() > 0) {
         ASSERT(spill_slots_.length() == slot_index);
         spill_slots_.Add(range->End());
+        quad_spill_slots_.Add(false);
       }
       AssignSafepoints(range);
     } else {
       ConstantInstr* constant = defn->AsConstant();
       ASSERT(constant != NULL);
       range->set_assigned_location(Location::Constant(constant->value()));
       range->set_spill_slot(Location::Constant(constant->value()));
     }
     range->finger()->Initialize(range);
     UsePosition* use =
@@ skipping 367 matching lines @@
     //              [--)
     //
     // The stack bitmap describes the position i.
     for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
       BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
                     pos,
                     pos + 1);
     }
 
     for (intptr_t reg = 0; reg < kNumberOfFpuRegisters; reg++) {
-      Representation ignored = kNoRepresentation;
       BlockLocation(
-          Location::FpuRegisterLocation(static_cast<FpuRegister>(reg), ignored),
+          Location::FpuRegisterLocation(static_cast<FpuRegister>(reg)),
           pos,
           pos + 1);
     }
 
 
 #if defined(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++) {
@@ skipping 565 matching lines @@
   }
 
   LiveRange* tail = range->SplitAt(from);
   Spill(tail);
 }
 
 
 void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) {
   ASSERT(range->spill_slot().IsInvalid());
 
-  intptr_t idx = 0;
-  for (; idx < spill_slots_.length(); idx++) {
-    if (spill_slots_[idx] <= range->Start()) break;
-  }
-
-  if (idx == spill_slots_.length()) spill_slots_.Add(0);
-
+  // Compute range start and end.
   LiveRange* last_sibling = range;
   while (last_sibling->next_sibling() != NULL) {
     last_sibling = last_sibling->next_sibling();
   }
 
-  spill_slots_[idx] = last_sibling->End();
+  const intptr_t start = range->Start();
+  const intptr_t end = last_sibling->End();
 
+  // During fpu register allocation spill slot indices are computed in terms of
+  // double (64bit) stack slots. We treat quad stack slot (128bit) as a
+  // consecutive pair of two double spill slots.
+  // Special care is taken to never allocate the same index to both
+  // double and quad spill slots as it complicates disambiguation during
+  // parallel move resolution.
+  const bool need_quad = (register_kind_ == Location::kFpuRegister) &&
+      ((range->representation() == kUnboxedFloat32x4) ||
+       (range->representation() == kUnboxedUint32x4));
+
+  // Search for a free spill slot among allocated: the value in it should be
+  // dead and its type should match (e.g. it should not be a part of the quad if
+  // we are allocating normal double slot).
+  intptr_t idx = 0;
+  for (; idx < spill_slots_.length(); idx++) {
+    if ((need_quad == quad_spill_slots_[idx]) &&
+        (spill_slots_[idx] <= start)) {
+      break;
+    }
+  }
+
+  if (idx == spill_slots_.length()) {
+    // No free spill slot found. Allocate a new one.
+    spill_slots_.Add(0);
+    quad_spill_slots_.Add(need_quad);
+    if (need_quad) {  // Allocate two double stack slots if we need quad slot.
+      spill_slots_.Add(0);
+      quad_spill_slots_.Add(need_quad);
+    }
+  }
+
+
+  // Set spill slot expiration boundary to the live range's end.
+  spill_slots_[idx] = end;
+  if (need_quad) {
+    ASSERT(quad_spill_slots_[idx] && quad_spill_slots_[idx + 1]);
+    idx++;  // Use the higher index it corresponds to the lower stack address.
+    spill_slots_[idx] = end;
+  } else {
+    ASSERT(!quad_spill_slots_[idx]);
+  }
+
+  // Assign spill slot to the range.
   if (register_kind_ == Location::kRegister) {
     range->set_spill_slot(Location::StackSlot(idx));
   } else {
-    // FPU register spill slots are essentially two (x64) or four (ia32) normal
-    // word size spill slots.  We use the index of the slot with the lowest
-    // address as an index for the FPU register spill slot. In terms of indexes
-    // this relation is inverted: so we have to take the highest index.
+    // We use the index of the slot with the lowest address as an index for the
+    // FPU register spill slot. In terms of indexes this relation is inverted:
+    // so we have to take the highest index.
     const intptr_t slot_idx = cpu_spill_slot_count_ +
-        idx * kFpuRegisterSpillFactor + (kFpuRegisterSpillFactor - 1);
+        idx * kDoubleSpillFactor + (kDoubleSpillFactor - 1);
 
     Location location;
-    if (range->representation() == kUnboxedFloat32x4) {
-      location = Location::Float32x4StackSlot(slot_idx);
-    } else if (range->representation() == kUnboxedUint32x4) {
-      location = Location::Uint32x4StackSlot(slot_idx);
+    if ((range->representation() == kUnboxedFloat32x4) ||
+        (range->representation() == kUnboxedUint32x4)) {
+      ASSERT(need_quad);
+      location = Location::QuadStackSlot(slot_idx);
     } else {
       ASSERT((range->representation() == kUnboxedDouble) ||
              (range->representation() == kUnboxedMint));
-      location = Location::DoubleStackSlot(slot_idx,
-                                           range->representation());
+      location = Location::DoubleStackSlot(slot_idx);
     }
     range->set_spill_slot(location);
   }
 
   spilled_.Add(range);
 }
 
 
 void FlowGraphAllocator::MarkAsObjectAtSafepoints(LiveRange* range) {
   intptr_t stack_index = range->spill_slot().stack_index();
@@ skipping 180 matching lines @@
         if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
           used_on_backedge[reg] = true;
         }
       }
     }
 
     if (used_on_backedge[candidate]) {
       TRACE_ALLOC(OS::Print(
           "considering %s for v%"Pd": has interference on the back edge"
           " {loop [%"Pd", %"Pd")}\n",
-          MakeRegisterLocation(candidate, kUnboxedDouble).Name(),
+          MakeRegisterLocation(candidate).Name(),
           unallocated->vreg(),
           loop_header->entry()->start_pos(),
           loop_header->last_block()->end_pos()));
       for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
         if (blocked_registers_[reg] ||
             (reg == candidate) ||
             used_on_backedge[reg]) {
           continue;
         }
 
         const intptr_t intersection =
             FirstIntersectionWithAllocated(reg, unallocated);
         if (intersection >= free_until) {
           candidate = reg;
           free_until = intersection;
           TRACE_ALLOC(OS::Print(
               "found %s for v%"Pd" with no interference on the back edge\n",
-              MakeRegisterLocation(candidate, kUnboxedDouble).Name(),
+              MakeRegisterLocation(candidate).Name(),
               candidate));
           break;
         }
       }
     }
   }
 
   TRACE_ALLOC(OS::Print("assigning free register "));
-  TRACE_ALLOC(MakeRegisterLocation(candidate, kUnboxedDouble).Print());
+  TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
   TRACE_ALLOC(OS::Print(" to v%"Pd"\n", unallocated->vreg()));
 
   if (free_until != kMaxPosition) {
     // There was an intersection. Split unallocated.
     TRACE_ALLOC(OS::Print("  splitting at %"Pd"\n", free_until));
     LiveRange* tail = unallocated->SplitAt(free_until);
     AddToUnallocated(tail);
   }
 
   registers_[candidate].Add(unallocated);
-  unallocated->set_assigned_location(
-      MakeRegisterLocation(candidate, unallocated->representation()));
+  unallocated->set_assigned_location(MakeRegisterLocation(candidate));
 
   return true;
 }
 
 
 bool FlowGraphAllocator::RangeHasOnlyUnconstrainedUsesInLoop(LiveRange* range,
                                                              intptr_t loop_id) {
   if (range->vreg() >= 0) {
     return GetLiveRange(range->vreg())->HasOnlyUnconstrainedUsesInLoop(loop_id);
   }
@@ skipping 70 matching lines @@
       (register_use != NULL) ? register_use->pos()
                              : unallocated->Start();
   if (free_until < register_use_pos) {
     // Can't acquire free register. Spill until we really need one.
     ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos));
     SpillBetween(unallocated, unallocated->Start(), register_use->pos());
     return;
   }
 
   TRACE_ALLOC(OS::Print("assigning blocked register "));
-  TRACE_ALLOC(MakeRegisterLocation(candidate, kUnboxedDouble).Print());
+  TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
   TRACE_ALLOC(OS::Print(" to live range v%"Pd" until %"Pd"\n",
                         unallocated->vreg(), blocked_at));
 
   if (blocked_at < unallocated->End()) {
     // Register is blocked before the end of the live range.  Split the range
     // at latest at blocked_at position.
     LiveRange* tail = SplitBetween(unallocated,
                                    unallocated->Start(),
                                    blocked_at + 1);
     AddToUnallocated(tail);
@@ skipping 85 matching lines @@
       }
       registers_[reg][i] = NULL;
       first_evicted = i;
     }
   }
 
   // Remove evicted ranges from the array.
   if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
 
   registers_[reg].Add(unallocated);
-  unallocated->set_assigned_location(
-      MakeRegisterLocation(reg, unallocated->representation()));
+  unallocated->set_assigned_location(MakeRegisterLocation(reg));
 }
 
 
 bool FlowGraphAllocator::EvictIntersection(LiveRange* allocated,
                                            LiveRange* unallocated) {
   UseInterval* first_unallocated =
       unallocated->finger()->first_pending_use_interval();
   const intptr_t intersection = FirstIntersection(
       allocated->finger()->first_pending_use_interval(),
       first_unallocated);
@@ skipping 449 matching lines @@
 
   PrepareForAllocation(Location::kRegister,
                        kNumberOfCpuRegisters,
                        unallocated_cpu_,
                        cpu_regs_,
                        blocked_cpu_registers_);
   AllocateUnallocatedRanges();
 
   cpu_spill_slot_count_ = spill_slots_.length();
   spill_slots_.Clear();
+  quad_spill_slots_.Clear();
 
   PrepareForAllocation(Location::kFpuRegister,
                        kNumberOfFpuRegisters,
                        unallocated_xmm_,
                        fpu_regs_,
                        blocked_fpu_registers_);
   AllocateUnallocatedRanges();
 
   ResolveControlFlow();
 
   GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
   ASSERT(entry != NULL);
-  intptr_t double_spill_slot_count =
-      spill_slots_.length() * kFpuRegisterSpillFactor;
+  intptr_t double_spill_slot_count = spill_slots_.length() * kDoubleSpillFactor;
   entry->set_spill_slot_count(cpu_spill_slot_count_ + double_spill_slot_count);
 
   if (FLAG_print_ssa_liveranges) {
     const Function& function = flow_graph_.parsed_function().function();
 
     OS::Print("-- [after ssa allocator] ranges [%s] ---------\n",
               function.ToFullyQualifiedCString());
     PrintLiveRanges();
     OS::Print("----------------------------------------------\n");
 
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart