Add support for XMM registers in SSA code generation pipeline.

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.h"
@@ skipping 48 matching lines @@
 FlowGraphAllocator::FlowGraphAllocator(const FlowGraph& flow_graph)
   : flow_graph_(flow_graph),
     block_order_(flow_graph.reverse_postorder()),
     postorder_(flow_graph.postorder()),
     live_out_(block_order_.length()),
     kill_(block_order_.length()),
     live_in_(block_order_.length()),
     vreg_count_(flow_graph.max_virtual_register_number()),
     live_ranges_(flow_graph.max_virtual_register_number()),
     cpu_regs_(),
-    blocked_cpu_regs_() {
+    xmm_regs_(),
+    blocked_cpu_registers_(),
+    blocked_xmm_registers_(),
+    cpu_spill_slot_count_(0) {
   for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL);
 
-  blocked_cpu_regs_[CTX] = true;
+  blocked_cpu_registers_[CTX] = true;
   if (TMP != kNoRegister) {
-    blocked_cpu_regs_[TMP] = true;
+    blocked_cpu_registers_[TMP] = true;
   }
-  blocked_cpu_regs_[SPREG] = true;
-  blocked_cpu_regs_[FPREG] = true;
+  blocked_cpu_registers_[SPREG] = true;
+  blocked_cpu_registers_[FPREG] = true;
+
+  // XMM0 is used as scratch by optimized code and parallel move resolver.
+  blocked_xmm_registers_[XMM0] = true;
 }
 
 
 // Remove environments from the instructions which can't deoptimize.
 // Replace dead phis uses with null values in environments.
 void FlowGraphAllocator::EliminateEnvironmentUses() {
   ConstantVal* null_value = new ConstantVal(Object::ZoneHandle());
 
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* block = block_order_[i];
@@ skipping 203 matching lines @@
     OS::Print("\n");
 
     PrintBitVector("  live out", live_out_[i]);
     PrintBitVector("  kill", kill_[i]);
     PrintBitVector("  live in", live_in_[i]);
   }
 }
 
 
 void LiveRange::AddUse(intptr_t pos, Location* location_slot) {
+  ASSERT(location_slot != NULL);
   ASSERT((first_use_interval_->start_ <= pos) &&
          (pos <= first_use_interval_->end_));
-  if ((uses_ != NULL) && (uses_->pos() == pos)) {
-    if ((location_slot == NULL) || (uses_->location_slot() == location_slot)) {
-      return;
-    } else if (uses_->location_slot() == NULL) {
-      uses_->set_location_slot(location_slot);
-      return;
-    }
+  if ((uses_ != NULL) &&
+      (uses_->pos() == pos) &&
+      (uses_->location_slot() == location_slot)) {
+    return;
   }
   uses_ = new UsePosition(pos, uses_, location_slot);
 }
 
 
 void LiveRange::AddSafepoint(intptr_t pos, LocationSummary* locs) {
   SafepointPosition* safepoint = new SafepointPosition(pos, locs);
 
   if (first_safepoint_ == NULL) {
     ASSERT(last_safepoint_ == NULL);
@@ skipping 82 matching lines @@
 
 LiveRange* FlowGraphAllocator::MakeLiveRangeForTemporary() {
   LiveRange* range = new LiveRange(kTempVirtualRegister);
 #if defined(DEBUG)
   temporaries_.Add(range);
 #endif
   return range;
 }
 
 
+void FlowGraphAllocator::BlockRegisterLocation(Location loc,
+                                               intptr_t from,
+                                               intptr_t to,
+                                               bool* blocked_registers,
+                                               LiveRange** blocking_ranges) {
+  if (blocked_registers[loc.register_code()]) {
+    return;
+  }
+
+  if (blocking_ranges[loc.register_code()] == NULL) {
+    LiveRange* range = new LiveRange(kNoVirtualRegister);
+    blocking_ranges[loc.register_code()] = range;
+    range->set_assigned_location(loc);
+#if defined(DEBUG)
+    temporaries_.Add(range);
+#endif
+  }
+
+  blocking_ranges[loc.register_code()]->AddUseInterval(from, to);
+}
+
+
 // Block location from the start of the instruction to its end.
 void FlowGraphAllocator::BlockLocation(Location loc,
                                        intptr_t from,
                                        intptr_t to) {
-  ASSERT(loc.IsRegister());
-  const Register reg = loc.reg();
-  if (blocked_cpu_regs_[reg]) return;
-  if (cpu_regs_[reg].length() == 0) {
-    LiveRange* range = new LiveRange(kNoVirtualRegister);
-    cpu_regs_[reg].Add(range);
-    range->set_assigned_location(loc);
-#if defined(DEBUG)
-    temporaries_.Add(range);
-#endif
+  if (loc.IsRegister()) {
+    BlockRegisterLocation(loc, from, to, blocked_cpu_registers_, cpu_regs_);
+  } else if (loc.IsXmmRegister()) {

[Florian Schneider, 2012/08/24 11:09:28]

A little shorter:

} else {
  ASSERT(loc.IsXmmRegister());
  BlockRegisterLocation(loc, from, to, blocked_xmm_registers_, xmm_regs_);
}

[Vyacheslav Egorov (Google), 2012/08/24 13:23:01]

Done.

+    BlockRegisterLocation(loc, from, to, blocked_xmm_registers_, xmm_regs_);
+  } else {
+    UNREACHABLE();
   }
-  cpu_regs_[reg][0]->AddUseInterval(from, to);
 }
 
 
 void LiveRange::Print() {
   if (first_use_interval() == NULL) {
     return;
   }
 
   OS::Print("  live range v%d [%d, %d) in ", vreg(), Start(), End());
   assigned_location().Print();
@@ skipping 98 matching lines @@
 
       AssignSafepoints(range);
 
       range->finger()->Initialize(range);
       UsePosition* use = range->finger()->FirstRegisterBeneficialUse(
           graph_entry->start_pos());
       if (use != NULL) {
         LiveRange* tail = SplitBetween(range,
                                        graph_entry->start_pos(),
                                        use->pos());
-        AddToUnallocated(tail);
+
+        // All incomming parameters are tagged.

[Florian Schneider, 2012/08/24 11:09:28]

s/incomming/incoming/

+        CompleteRange(tail, Location::kRegister);
       }
       ConvertAllUses(range);
       if (flow_graph_.copied_parameter_count() > 0) {
         MarkAsObjectAtSafepoints(range);
       }
     }
   }
 }
 
 //
@@ skipping 114 matching lines @@
         ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove()));
         MoveOperands* move =
             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.
       AssignSafepoints(range);
-      AddToUnallocated(range);
+
+      // TODO(vegorov): unboxed double phis.
+      CompleteRange(range, Location::kRegister);
 
       move_idx++;
     }
   }
 }
 
 
 void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block,
                                                 Instruction* current) {
   ASSERT(current->env() != NULL);
@@ skipping 36 matching lines @@
     } else {
       ASSERT(value->IsConstant());
       locations[i] = Location::NoLocation();
     }
   }
 
   env->set_locations(locations);
 }
 
 
+static Location::Kind RegisterKindFromPolicy(Location loc) {
+  if (loc.policy() == Location::kRequiresXmmRegister) {
+    return Location::kXmmRegister;
+  } else {

[Florian Schneider, 2012/08/24 11:09:28]

Maybe add 

ASSERT(loc.policy() == Location::kRequiresRegister)

here.

+    return Location::kRegister;
+  }
+}
+
+
+static Location::Kind RegisterKindForResult(Instruction* instr) {
+  if (instr->representation() == kUnboxedDouble) {
+    return Location::kXmmRegister;
+  } else {
+    return Location::kRegister;
+  }
+}
+
+
 // 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(IsInstructionStartPosition(pos));
 
   LocationSummary* locs = current->locs();
 
   // Number of input locations and number of input operands have to agree.
   ASSERT(locs->input_count() == current->InputCount());
 
   // 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->in(0).IsMachineRegister())) {
     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) ProcessEnvironmentUses(block, current);
 
   // 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()) {
+    if (in_ref->IsMachineRegister()) {
       // Input is expected in a fixed register. Expected shape of
       // live ranges:
       //
       //                 j' i  i'
       //      value    --*
       //      register   [-----)
       //
       MoveOperands* move =
           AddMoveAt(pos - 1, *in_ref, Location::Any());
       BlockLocation(*in_ref, pos - 1, pos + 1);
@@ skipping 14 matching lines @@
 
   // 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()) {
+    if (temp.IsMachineRegister()) {
       BlockLocation(temp, pos, pos + 1);
     } else if (temp.IsUnallocated()) {
       LiveRange* range = MakeLiveRangeForTemporary();
       range->AddUseInterval(pos, pos + 1);
       range->AddUse(pos, locs->temp_slot(j));
-      AddToUnallocated(range);
+      CompleteRange(range, RegisterKindFromPolicy(temp));
     } else {
       UNREACHABLE();
     }
   }
 
   // Block all allocatable registers for calls and record the stack bitmap.
   if (locs->always_calls()) {
     // Expected shape of live range:
     //
     //              i  i'
@@ skipping 38 matching lines @@
   }
 
   // We might have a definition without use.  We do not assign SSA index to
   // such definitions.
   LiveRange* range = (def->ssa_temp_index() >= 0) ?
       GetLiveRange(def->ssa_temp_index()) :
       MakeLiveRangeForTemporary();
   Location* out = locs->out_slot();
 
   // Process output and finalize its liverange.
-  if (out->IsRegister()) {
+  if (out->IsMachineRegister()) {
     // Fixed output location. Expected shape of live range:
     //
     //                    i  i' j  j'
     //    register        [--)
     //    output             [-------
     //
     BlockLocation(*out, pos, pos + 1);
 
     if (range->vreg() == kTempVirtualRegister) return;
 
@@ skipping 22 matching lines @@
     MoveOperands* move = AddMoveAt(pos + 1, Location::Any(), *out);
     range->AddHintedUse(pos + 1, move->dest_slot(), out);
   } 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()));
+    ASSERT(locs->in(0).Equals(Location::RequiresRegister()) ||
+           locs->in(0).Equals(Location::RequiresXmmRegister()));
 
     // Create move that will copy value between input and output.
     locs->set_out(Location::RequiresRegister());
     MoveOperands* move = AddMoveAt(pos,
                                    Location::RequiresRegister(),
                                    Location::Any());
 
     // 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);
     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);
-    range->AddUse(pos, out);
+    range->AddHintedUse(pos, out, move->src_slot());
     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:
     //
     //                    i  i'
     //    output          [-------
     //
-    ASSERT(out->IsUnallocated() &&
-           (out->policy() == Location::kRequiresRegister));
+    ASSERT(locs->out().Equals(Location::RequiresRegister()) ||
+           locs->out().Equals(Location::RequiresXmmRegister()));
 
     // Shorten live range to the point of definition and add use to be filled by
     // allocator.
     range->DefineAt(pos);
     range->AddUse(pos, out);
   }
 
   AssignSafepoints(range);
-  AddToUnallocated(range);
+  CompleteRange(range, RegisterKindForResult(current));
 }
 
 
 static ParallelMoveInstr* CreateParallelMoveBefore(Instruction* instr,
                                                    intptr_t pos) {
   ASSERT(pos > 0);
   Instruction* prev = instr->previous();
   ParallelMoveInstr* move = prev->AsParallelMove();
   if ((move == NULL) || (move->lifetime_position() != pos)) {
     move = new ParallelMoveInstr();
@@ skipping 174 matching lines @@
   }
   return use;
 }
 
 
 UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) {
   for (UsePosition* use = FirstUseAfter(first_register_use_, after);
        use != NULL;
        use = use->next()) {
     Location* loc = use->location_slot();
-    if ((loc != NULL) &&
-        loc->IsUnallocated() &&
+    if (loc->IsUnallocated() &&
         (loc->policy() == Location::kRequiresRegister)) {
       first_register_use_ = use;
       return use;
     }
   }
   return NULL;
 }
 
 
 UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) {
   for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after);
        use != NULL;
        use = use->next()) {
     Location* loc = use->location_slot();
-    if ((loc != NULL) &&
-        (loc->IsRegister() ||
-         (loc->IsUnallocated() && loc->IsRegisterBeneficial()))) {
+    if (loc->IsUnallocated() && loc->IsRegisterBeneficial()) {
       first_register_beneficial_use_ = use;
       return use;
     }
   }
   return NULL;
 }
 
 
 void AllocationFinger::UpdateAfterSplit(intptr_t first_use_after_split_pos) {
   if ((first_register_use_ != NULL) &&
@@ skipping 208 matching lines @@
 
   if (idx == spill_slots_.length()) spill_slots_.Add(0);
 
   LiveRange* last_sibling = range;
   while (last_sibling->next_sibling() != NULL) {
     last_sibling = last_sibling->next_sibling();
   }
 
   spill_slots_[idx] = last_sibling->End();
 
-  range->set_spill_slot(Location::StackSlot(idx));
+  if (register_kind_ == Location::kRegister) {
+    range->set_spill_slot(Location::StackSlot(idx));
+  } else {
+    range->set_spill_slot(
+        Location::DoubleStackSlot(cpu_spill_slot_count_ + idx * 2));

[Florian Schneider, 2012/08/24 11:09:28]

Why always times 2? Use sizeof instead. double spill slot is 64bit. Normal spill
slot is 32 or 64.

+  }
 
   spilled_.Add(range);
 }
 
 
 void FlowGraphAllocator::MarkAsObjectAtSafepoints(LiveRange* range) {
   intptr_t stack_index = range->spill_slot().stack_index();
   ASSERT(stack_index >= 0);
 
   while (range != NULL) {
     for (SafepointPosition* safepoint = range->first_safepoint();
          safepoint != NULL;
          safepoint = safepoint->next()) {
       safepoint->locs()->stack_bitmap()->Set(stack_index, true);
     }
     range = range->next_sibling();
   }
 }
 
 
 void FlowGraphAllocator::Spill(LiveRange* range) {
   LiveRange* parent = GetLiveRange(range->vreg());
   if (parent->spill_slot().IsInvalid()) {
     AllocateSpillSlotFor(parent);
-    MarkAsObjectAtSafepoints(parent);
+    if (register_kind_ == Location::kRegister) {
+      MarkAsObjectAtSafepoints(parent);
+    }
   }
   range->set_assigned_location(parent->spill_slot());
   ConvertAllUses(range);
 }
 
 
 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
-    Register reg, LiveRange* unallocated) {
+    intptr_t reg, LiveRange* unallocated) {
   intptr_t intersection = kMaxPosition;
-  for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
-    LiveRange* allocated = cpu_regs_[reg][i];
+  for (intptr_t i = 0; i < registers_[reg].length(); i++) {
+    LiveRange* allocated = registers_[reg][i];
     if (allocated == NULL) continue;
 
     UseInterval* allocated_head =
         allocated->finger()->first_pending_use_interval();
     if (allocated_head->start() >= intersection) continue;
 
     const intptr_t pos = FirstIntersection(
         unallocated->finger()->first_pending_use_interval(),
         allocated_head);
     if (pos < intersection) intersection = pos;
   }
   return intersection;
 }
 
 
-
 bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) {
-  Register candidate = kNoRegister;
+  intptr_t candidate = kNoRegister;
   intptr_t free_until = 0;
 
   // If hint is available try hint first.
   // TODO(vegorov): ensure that phis are hinted on the back edge.
   Location hint = unallocated->finger()->FirstHint();
-  if (hint.IsRegister()) {
-    if (!blocked_cpu_regs_[hint.reg()]) {
-      free_until = FirstIntersectionWithAllocated(hint.reg(), unallocated);
-      candidate = hint.reg();
+  if (hint.IsMachineRegister()) {
+    if (!blocked_registers_[hint.register_code()]) {
+      free_until = FirstIntersectionWithAllocated(hint.register_code(),
+                                                  unallocated);
+      candidate = hint.register_code();
     }
 
     TRACE_ALLOC(OS::Print("found hint "));
     TRACE_ALLOC(hint.Print());
     TRACE_ALLOC(OS::Print(" for %d: free until %d\n",
                           unallocated->vreg(), free_until));
   } else if (free_until != kMaxPosition) {
-    for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
-      if (!blocked_cpu_regs_[reg] && cpu_regs_[reg].length() == 0) {
-        candidate = static_cast<Register>(reg);
+    for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
+      if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) {
+        candidate = reg;
         free_until = kMaxPosition;
         break;
       }
     }
   }
 
   ASSERT(0 <= kMaxPosition);
   if (free_until != kMaxPosition) {
-    for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
-      if (blocked_cpu_regs_[reg] || (reg == candidate)) continue;
+    for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
+      if (blocked_registers_[reg] || (reg == candidate)) continue;
       const intptr_t intersection =
-          FirstIntersectionWithAllocated(static_cast<Register>(reg),
-                                         unallocated);
+          FirstIntersectionWithAllocated(reg, unallocated);
       if (intersection > free_until) {
-        candidate = static_cast<Register>(reg);
+        candidate = reg;
         free_until = intersection;
         if (free_until == kMaxPosition) break;
       }
     }
   }
 
   // All registers are blocked by active ranges.
   if (free_until <= unallocated->Start()) return false;
 
   TRACE_ALLOC(OS::Print("assigning free register "));
-  TRACE_ALLOC(Location::RegisterLocation(candidate).Print());
+  TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
   TRACE_ALLOC(OS::Print(" to %d\n", unallocated->vreg()));
 
   if (free_until != kMaxPosition) {
     // There was an intersection. Split unallocated.
     TRACE_ALLOC(OS::Print("  splitting at %d\n", free_until));
     LiveRange* tail = unallocated->SplitAt(free_until);
     AddToUnallocated(tail);
   }
 
-  cpu_regs_[candidate].Add(unallocated);
-  unallocated->set_assigned_location(Location::RegisterLocation(candidate));
+  registers_[candidate].Add(unallocated);
+  unallocated->set_assigned_location(MakeRegisterLocation(candidate));
 
   return true;
 }
 
 
 void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) {
   UsePosition* register_use =
       unallocated->finger()->FirstRegisterUse(unallocated->Start());
   if (register_use == NULL) {
     Spill(unallocated);
     return;
   }
 
-  Register candidate = kNoRegister;
+  intptr_t candidate = kNoRegister;
   intptr_t free_until = 0;
   intptr_t blocked_at = kMaxPosition;
 
-  for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) {
-    if (blocked_cpu_regs_[reg]) continue;
-    if (UpdateFreeUntil(static_cast<Register>(reg),
-                        unallocated,
-                        &free_until,
-                        &blocked_at)) {
-      candidate = static_cast<Register>(reg);
+  for (int reg = 0; reg < NumberOfRegisters(); ++reg) {
+    if (blocked_registers_[reg]) continue;
+    if (UpdateFreeUntil(reg, unallocated, &free_until, &blocked_at)) {
+      candidate = reg;
     }
   }
 
   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(Location::RegisterLocation(candidate).Print());
+  TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
   TRACE_ALLOC(OS::Print(" to live range %d until %d\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);
   }
 
   AssignNonFreeRegister(unallocated, candidate);
 }
 
 
-bool FlowGraphAllocator::UpdateFreeUntil(Register reg,
+bool FlowGraphAllocator::UpdateFreeUntil(intptr_t reg,
                                          LiveRange* unallocated,
                                          intptr_t* cur_free_until,
                                          intptr_t* cur_blocked_at) {
   intptr_t free_until = kMaxPosition;
   intptr_t blocked_at = kMaxPosition;
   const intptr_t start = unallocated->Start();
 
-  for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
-    LiveRange* allocated = cpu_regs_[reg][i];
+  for (intptr_t i = 0; i < registers_[reg].length(); i++) {
+    LiveRange* allocated = registers_[reg][i];
 
     UseInterval* first_pending_use_interval =
         allocated->finger()->first_pending_use_interval();
     if (first_pending_use_interval->Contains(start)) {
       // This is an active interval.
       if (allocated->vreg() < 0) {
         // This register blocked by an interval that
         // can't be spilled.
         return false;
       }
@@ skipping 27 matching lines @@
     }
   }
 
   ASSERT(free_until > *cur_free_until);
   *cur_free_until = free_until;
   *cur_blocked_at = blocked_at;
   return true;
 }
 
 
-void FlowGraphAllocator::RemoveEvicted(Register reg, intptr_t first_evicted) {
+void FlowGraphAllocator::RemoveEvicted(intptr_t reg, intptr_t first_evicted) {
   intptr_t to = first_evicted;
   intptr_t from = first_evicted + 1;
-  while (from < cpu_regs_[reg].length()) {
-    LiveRange* allocated = cpu_regs_[reg][from++];
-    if (allocated != NULL) cpu_regs_[reg][to++] = allocated;
+  while (from < registers_[reg].length()) {
+    LiveRange* allocated = registers_[reg][from++];
+    if (allocated != NULL) registers_[reg][to++] = allocated;
   }
-  cpu_regs_[reg].TruncateTo(to);
+  registers_[reg].TruncateTo(to);
 }
 
 
 void FlowGraphAllocator::AssignNonFreeRegister(LiveRange* unallocated,
-                                               Register reg) {
+                                               intptr_t reg) {
   intptr_t first_evicted = -1;
-  for (intptr_t i = cpu_regs_[reg].length() - 1; i >= 0; i--) {
-    LiveRange* allocated = cpu_regs_[reg][i];
+  for (intptr_t i = registers_[reg].length() - 1; i >= 0; i--) {
+    LiveRange* allocated = registers_[reg][i];
     if (allocated->vreg() < 0) continue;  // Can't be evicted.
     if (EvictIntersection(allocated, unallocated)) {
       // If allocated was not spilled convert all pending uses.
       if (allocated->assigned_location().IsRegister()) {
         ASSERT(allocated->End() <= unallocated->Start());
         ConvertAllUses(allocated);
       }
-      cpu_regs_[reg][i] = NULL;
+      registers_[reg][i] = NULL;
       first_evicted = i;
     }
   }
 
   // Remove evicted ranges from the array.
   if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
 
-  cpu_regs_[reg].Add(unallocated);
-  unallocated->set_assigned_location(Location::RegisterLocation(reg));
+  registers_[reg].Add(unallocated);
+  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 31 matching lines @@
   }
 
   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));
   TRACE_ALLOC(OS::Print("  use at %d converted to ", use->pos()));
   TRACE_ALLOC(loc.Print());
   TRACE_ALLOC(OS::Print("\n"));
   *slot = loc;
 }
 
 
 void FlowGraphAllocator::ConvertAllUses(LiveRange* range) {
   if (range->vreg() == kNoVirtualRegister) return;
+
+  const Location loc = range->assigned_location();
+  ASSERT(!loc.IsInvalid());
+
   TRACE_ALLOC(OS::Print("range [%d, %d) for v%d has been allocated to ",
                         range->Start(), range->End(), range->vreg()));
-  TRACE_ALLOC(range->assigned_location().Print());
+  TRACE_ALLOC(loc.Print());
   TRACE_ALLOC(OS::Print(":\n"));
-  ASSERT(!range->assigned_location().IsInvalid());
-  const Location loc = range->assigned_location();
+
   for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) {
     ConvertUseTo(use, loc);
   }
 
-  if (range->assigned_location().IsRegister()) {
-    Register reg = range->assigned_location().reg();
+  if (loc.IsMachineRegister()) {
     for (SafepointPosition* safepoint = range->first_safepoint();
          safepoint != NULL;
          safepoint = safepoint->next()) {
-      safepoint->locs()->live_registers()->Add(reg);
+      safepoint->locs()->live_registers()->Add(loc);
     }
   }
 }
 
 
 void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) {
-  for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
-    if (cpu_regs_[reg].is_empty()) continue;
+  for (intptr_t reg = 0; reg < NumberOfRegisters(); reg++) {
+    if (registers_[reg].is_empty()) continue;
 
     intptr_t first_evicted = -1;
-    for (intptr_t i = cpu_regs_[reg].length() - 1; i >= 0; i--) {
-      LiveRange* range = cpu_regs_[reg][i];
+    for (intptr_t i = registers_[reg].length() - 1; i >= 0; i--) {
+      LiveRange* range = registers_[reg][i];
       if (range->finger()->Advance(start)) {
         ConvertAllUses(range);
-        cpu_regs_[reg][i] = NULL;
+        registers_[reg][i] = NULL;
         first_evicted = i;
       }
     }
 
-    if (first_evicted != -1) {
-      RemoveEvicted(static_cast<Register>(reg), first_evicted);
-    }
+    if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
   }
 }
 
 
-static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) {
-  return a->Start() <= b->Start();
-}
-
-
 bool LiveRange::Contains(intptr_t pos) const {
   if (!CanCover(pos)) return false;
 
   for (UseInterval* interval = first_use_interval_;
        interval != NULL;
        interval = interval->next()) {
     if (interval->Contains(pos)) {
       return true;
     }
   }
 
   return false;
 }
 
 
 void FlowGraphAllocator::AssignSafepoints(LiveRange* range) {
   for (intptr_t i = safepoints_.length() - 1; i >= 0; i--) {
     Instruction* instr = safepoints_[i];
 
     const intptr_t pos = instr->lifetime_position();
     if (range->End() <= pos) break;
 
     if (range->Contains(pos)) range->AddSafepoint(pos, instr->locs());
   }
 }
 
 
+static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) {
+  // TODO(vegorov): consider first hint position when ordering live ranges.
+  return a->Start() <= b->Start();
+}
+
+
+static void AddToSortedListOfRanges(GrowableArray<LiveRange*>* list,
+                                    LiveRange* range) {
+  range->finger()->Initialize(range);
+
+  if (list->is_empty()) {
+    list->Add(range);
+    return;
+  }
+
+  for (intptr_t i = list->length() - 1; i >= 0; i--) {
+    if (ShouldBeAllocatedBefore(range, (*list)[i])) {
+      list->InsertAt(i + 1, range);
+      return;
+    }
+  }
+  list->InsertAt(0, range);
+}
+
+
 void FlowGraphAllocator::AddToUnallocated(LiveRange* range) {
-  range->finger()->Initialize(range);
-
-  if (unallocated_.is_empty()) {
-    unallocated_.Add(range);
-    return;
-  }
-
-  for (intptr_t i = unallocated_.length() - 1; i >= 0; i--) {
-    if (ShouldBeAllocatedBefore(range, unallocated_[i])) {
-      unallocated_.InsertAt(i + 1, range);
-      return;
-    }
-  }
-  unallocated_.InsertAt(0, range);
+  AddToSortedListOfRanges(&unallocated_, range);
 }
 
 
+void FlowGraphAllocator::CompleteRange(LiveRange* range, Location::Kind kind) {
+  switch (kind) {
+    case Location::kRegister:
+      AddToSortedListOfRanges(&unallocated_cpu_, range);
+      break;
+
+    case Location::kXmmRegister:
+      AddToSortedListOfRanges(&unallocated_xmm_, range);
+      break;
+
+    default:
+      UNREACHABLE();
+  }
+}
+
+
 #if defined(DEBUG)
 bool FlowGraphAllocator::UnallocatedIsSorted() {
   for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) {
     LiveRange* a = unallocated_[i];
     LiveRange* b = unallocated_[i - 1];
     if (!ShouldBeAllocatedBefore(a, b)) return false;
   }
   return true;
 }
 #endif
 
 
-void FlowGraphAllocator::AllocateCPURegisters() {
+void FlowGraphAllocator::PrepareForAllocation(
+  Location::Kind register_kind,
+  intptr_t number_of_registers,
+  const GrowableArray<LiveRange*>& unallocated,
+  LiveRange** blocking_ranges,
+  bool* blocked_registers) {
+  register_kind_ = register_kind;
+  number_of_registers_ = number_of_registers;
+
+  ASSERT(unallocated_.is_empty());
+  unallocated_.AddArray(unallocated);
+
+  for (intptr_t reg = 0; reg < number_of_registers; reg++) {
+    blocked_registers_[reg] = blocked_registers[reg];
+    ASSERT(registers_[reg].is_empty());
+
+    LiveRange* range = blocking_ranges[reg];
+    if (range != NULL) {
+      range->finger()->Initialize(range);
+      registers_[reg].Add(range);
+    }
+  }
+}
+
+
+void FlowGraphAllocator::AllocateUnallocatedRanges() {
 #if defined(DEBUG)
   ASSERT(UnallocatedIsSorted());
 #endif
 
-  for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) {
-    if (cpu_regs_[i].length() == 1) {
-      LiveRange* range = cpu_regs_[i][0];
-      range->finger()->Initialize(range);
-    }
-  }
-
   while (!unallocated_.is_empty()) {
     LiveRange* range = unallocated_.Last();
     unallocated_.RemoveLast();
     const intptr_t start = range->Start();
     TRACE_ALLOC(OS::Print("Processing live range for vreg %d starting at %d\n",
                           range->vreg(),
                           start));
 
     // TODO(vegorov): eagerly spill liveranges without register uses.
     AdvanceActiveIntervals(start);
@@ skipping 62 matching lines @@
   TRACE_ALLOC(source.Print());
   TRACE_ALLOC(OS::Print("] to [%d, %d) [",
                         target_cover->Start(), target_cover->End()));
   TRACE_ALLOC(target.Print());
   TRACE_ALLOC(OS::Print("]\n"));
 
   // Siblings were allocated to the same register.
   if (source.Equals(target)) return;
 
   // Values are eagerly spilled. Spill slot already contains appropriate value.
-  if (target.IsStackSlot()) {
+  if (target.IsStackSlot() || target.IsDoubleStackSlot()) {
     ASSERT(parent->spill_slot().Equals(target));
     return;
   }
 
   Instruction* last = source_block->last_instruction();
   if ((last->SuccessorCount() == 1) && !source_block->IsGraphEntry()) {
     ASSERT(last->IsGoto());
     last->AsGoto()->GetParallelMove()->AddMove(target, source);
   } else {
     target_block->GetParallelMove()->AddMove(target, source);
@@ skipping 12 matching lines @@
       LiveRange* sibling = range->next_sibling();
       TRACE_ALLOC(OS::Print("connecting [%d, %d) [",
                             range->Start(), range->End()));
       TRACE_ALLOC(range->assigned_location().Print());
       TRACE_ALLOC(OS::Print("] to [%d, %d) [",
                             sibling->Start(), sibling->End()));
       TRACE_ALLOC(sibling->assigned_location().Print());
       TRACE_ALLOC(OS::Print("]\n"));
       if ((range->End() == sibling->Start()) &&
           !sibling->assigned_location().IsStackSlot() &&
+          !sibling->assigned_location().IsDoubleStackSlot() &&
           !range->assigned_location().Equals(sibling->assigned_location()) &&
           !IsBlockEntry(range->End())) {
         AddMoveAt(sibling->Start(),
                   sibling->assigned_location(),
                   range->assigned_location());
       }
       range = sibling;
     }
   }
 
   // Resolve non-linear control flow across branches.
   for (intptr_t i = 1; i < block_order_.length(); i++) {
     BlockEntryInstr* block = block_order_[i];
     BitVector* live = live_in_[block->postorder_number()];
     for (BitVector::Iterator it(live); !it.Done(); it.Advance()) {
       LiveRange* range = GetLiveRange(it.Current());
       for (intptr_t j = 0; j < block->PredecessorCount(); j++) {
         ConnectSplitSiblings(range, block->PredecessorAt(j), block);
       }
     }
   }
 
   // Eagerly spill values.
   // TODO(vegorov): if value is spilled on the cold path (e.g. by the call)
   // this will cause spilling to occur on the fast path (at the definition).
   for (intptr_t i = 0; i < spilled_.length(); i++) {
     LiveRange* range = spilled_[i];
-    if (range->assigned_location().IsStackSlot()) {
+    if (range->assigned_location().IsStackSlot() ||
+        range->assigned_location().IsDoubleStackSlot()) {
       ASSERT(range->assigned_location().Equals(range->spill_slot()));
     } else {
       AddMoveAt(range->Start() + 1,
                 range->spill_slot(),
                 range->assigned_location());
     }
   }
 }
 
 
@@ skipping 20 matching lines @@
     PrintLiveRanges();
     OS::Print("----------------------------------------------\n");
 
     OS::Print("-- [before ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 
-  AllocateCPURegisters();
+  PrepareForAllocation(Location::kRegister,
+                       kNumberOfCpuRegisters,
+                       unallocated_cpu_,
+                       cpu_regs_,
+                       blocked_cpu_registers_);
+  AllocateUnallocatedRanges();
+
+  cpu_spill_slot_count_ = spill_slots_.length();
+  spill_slots_.Clear();
+
+  PrepareForAllocation(Location::kXmmRegister,
+                       kNumberOfXmmRegisters,
+                       unallocated_xmm_,
+                       xmm_regs_,
+                       blocked_xmm_registers_);
+  AllocateUnallocatedRanges();
 
   ResolveControlFlow();
 
+  // Reserve spill slots for XMM registers alive across slow path code.
+  // TODO(vegorov): remove this code when safepoints with registers are
+  // implemented.
+  intptr_t deferred_xmm_spills = 0;
+  for (intptr_t i = 0; i < safepoints_.length(); i++) {
+    if (!safepoints_[i]->locs()->always_calls()) {
+      const intptr_t count =
+          safepoints_[i]->locs()->live_registers()->xmm_regs_count();
+      if (count > deferred_xmm_spills) deferred_xmm_spills = count;
+    }
+  }
+
   GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
   ASSERT(entry != NULL);
-  entry->set_spill_slot_count(spill_slots_.length());
+  entry->set_spill_slot_count(
+      (deferred_xmm_spills + spill_slots_.length()) * 2 +

[Florian Schneider, 2012/08/24 11:09:28]

Why times 2?

+      cpu_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