Implement simple spill store elimination.

runtime/vm/flow_graph_allocator.cc

Index: runtime/vm/flow_graph_allocator.cc
diff --git a/runtime/vm/flow_graph_allocator.cc b/runtime/vm/flow_graph_allocator.cc
index 50e3c2560086ac27b85011a418e99e5b4ab692f7..aa1b9416fd291947fc9bd2063541b92e5fe46270 100644
--- a/runtime/vm/flow_graph_allocator.cc
+++ b/runtime/vm/flow_graph_allocator.cc
@@ -17,8 +17,10 @@ DEFINE_FLAG(bool, print_ssa_liveness, false,
             "Print liveness for ssa variables.");
 DEFINE_FLAG(bool, trace_ssa_allocator, false,
             "Trace register allocation over SSA.");
+DEFINE_FLAG(bool, print_ssa_liveranges, false,
+            "Print live ranges after allocation.");
 
-#ifdef DEBUG
+#if defined(DEBUG)
 #define TRACE_ALLOC(m) do {                     \
     if (FLAG_trace_ssa_allocator) OS::Print m ; \
   } while (0)
@@ -339,6 +341,15 @@ LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) {
 }
 
 
+LiveRange* FlowGraphAllocator::MakeLiveRangeForTemporary() {
+  LiveRange* range = new LiveRange(kTempVirtualRegister);
+#if defined(DEBUG)
+  temporaries_.Add(range);
+#endif
+  return range;
+}
+
+
 // Block location from the start of the instruction to its end.
 void FlowGraphAllocator::BlockLocation(Location loc, intptr_t pos) {
   ASSERT(loc.IsRegister());
@@ -346,14 +357,26 @@ void FlowGraphAllocator::BlockLocation(Location loc, intptr_t pos) {
   const Register reg = loc.reg();
   if (blocked_cpu_regs_[reg]) return;
   if (cpu_regs_[reg].length() == 0) {
-    cpu_regs_[reg].Add(new LiveRange(kNoVirtualRegister));
+    LiveRange* range = new LiveRange(kNoVirtualRegister);
+    cpu_regs_[reg].Add(range);
+    range->set_assigned_location(loc);
+#if defined(DEBUG)
+    temporaries_.Add(range);
+#endif
   }
   cpu_regs_[reg][0]->AddUseInterval(pos, pos + 1);
 }
 
 
 void LiveRange::Print() {
-  OS::Print("  live range v%d [%d, %d)\n", vreg(), Start(), End());
+  if (first_use_interval() == NULL) {
+    return;
+  }
+
+  OS::Print("  live range v%d [%d, %d) in ", vreg(), Start(), End());
+  assigned_location().Print();
+  OS::Print("\n");
+
   UsePosition* use_pos = uses_;
   for (UseInterval* interval = first_use_interval_;
        interval != NULL;
@@ -362,10 +385,12 @@ void LiveRange::Print() {
               interval->start(),
               interval->end());
     while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) {
-      OS::Print("      use at %d as %s\n",
-                use_pos->pos(),
-                (use_pos->location_slot() == NULL)
-                ? "-" : use_pos->location_slot()->Name());
+      OS::Print("      use at %d", use_pos->pos());
+      if (use_pos->location_slot() != NULL) {
+        OS::Print(" as ");
+        use_pos->location_slot()->Print();
+      }
+      OS::Print("\n");
       use_pos = use_pos->next();
     }
   }
@@ -377,18 +402,16 @@ void LiveRange::Print() {
 
 
 void FlowGraphAllocator::PrintLiveRanges() {
-  for (intptr_t i = 0; i < unallocated_.length(); i++) {
-    unallocated_[i]->Print();
+#if defined(DEBUG)
+  for (intptr_t i = 0; i < temporaries_.length(); i++) {
+    temporaries_[i]->Print();
   }
+#endif
 
-  for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
-    if (blocked_cpu_regs_[reg]) continue;
-    if (cpu_regs_[reg].length() == 0) continue;
-
-    ASSERT(cpu_regs_[reg].length() == 1);
-    OS::Print("blocking live range for %s\n",
-              Location::RegisterLocation(static_cast<Register>(reg)).Name());
-    cpu_regs_[reg][0]->Print();
+  for (intptr_t i = 0; i < live_ranges_.length(); i++) {
+    if (live_ranges_[i] != NULL) {
+      live_ranges_[i]->Print();
+    }
   }
 }
 
@@ -442,6 +465,7 @@ void FlowGraphAllocator::BuildLiveRanges() {
       // Slot index for the rightmost parameter is -1.
       const intptr_t slot_index = param->index() - fixed_parameters_count;
       range->set_assigned_location(Location::StackSlot(slot_index));
+      range->set_spill_slot(Location::StackSlot(slot_index));
 
       range->finger()->Initialize(range);
       UsePosition* use = range->finger()->FirstRegisterBeneficialUse(
@@ -695,7 +719,7 @@ void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
     if (temp.IsRegister()) {
       BlockLocation(temp, pos);
     } else if (temp.IsUnallocated()) {
-      LiveRange* range = new LiveRange(kTempVirtualRegister);
+      LiveRange* range = MakeLiveRangeForTemporary();
       range->AddUseInterval(pos, pos + 1);
       range->AddUse(pos, locs->temp_slot(j));
       AddToUnallocated(range);
@@ -717,7 +741,7 @@ void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
                     pos);
     }
 
-#ifdef DEBUG
+#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.
@@ -748,7 +772,7 @@ void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
   // such definitions.
   LiveRange* range = (def->ssa_temp_index() >= 0) ?
       GetLiveRange(def->ssa_temp_index()) :
-      new LiveRange(kTempVirtualRegister);
+      MakeLiveRangeForTemporary();
   Location* out = locs->out_slot();
 
   // Process output and finalize its liverange.
@@ -1155,22 +1179,35 @@ void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) {
 }
 
 
-intptr_t FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) {
-  for (intptr_t i = 0; i < spill_slots_.length(); i++) {
-    if (spill_slots_[i] <= range->Start()) {
-      return i;
-    }
+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;
   }
-  spill_slots_.Add(0);
-  return spill_slots_.length() - 1;
+
+  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));
+
+  spilled_.Add(range);
 }
 
 
 void FlowGraphAllocator::Spill(LiveRange* range) {
-  const intptr_t spill_index = AllocateSpillSlotFor(range);
-  ASSERT(spill_slots_[spill_index] <= range->Start());
-  spill_slots_[spill_index] = range->End();
-  range->set_assigned_location(Location::StackSlot(spill_index));
+  LiveRange* parent = GetLiveRange(range->vreg());
+
+  if (parent->spill_slot().IsInvalid()) AllocateSpillSlotFor(parent);
+
+  range->set_assigned_location(parent->spill_slot());
   ConvertAllUses(range);
 }
 
@@ -1511,7 +1548,7 @@ void FlowGraphAllocator::AddToUnallocated(LiveRange* range) {
 }
 
 
-#ifdef DEBUG
+#if defined(DEBUG)
 bool FlowGraphAllocator::UnallocatedIsSorted() {
   for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) {
     LiveRange* a = unallocated_[i];
@@ -1524,7 +1561,7 @@ bool FlowGraphAllocator::UnallocatedIsSorted() {
 
 
 void FlowGraphAllocator::AllocateCPURegisters() {
-#ifdef DEBUG
+#if defined(DEBUG)
   ASSERT(UnallocatedIsSorted());
 #endif
 
@@ -1560,15 +1597,15 @@ void FlowGraphAllocator::AllocateCPURegisters() {
 }
 
 
-void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* range,
+void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent,
                                               BlockEntryInstr* source_block,
                                               BlockEntryInstr* target_block) {
   TRACE_ALLOC(("Connect source_block=%d, target_block=%d\n",
                source_block->block_id(),
                target_block->block_id()));
-  if (range->next_sibling() == NULL) {
+  if (parent->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()));
+    TRACE_ALLOC(("range %d has no siblings\n", parent->vreg()));
     return;
   }
 
@@ -1580,23 +1617,24 @@ void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* range,
   Location target;
   Location source;
 
-#ifdef DEBUG
+#if defined(DEBUG)
   LiveRange* source_cover = NULL;
   LiveRange* target_cover = NULL;
 #endif
 
+  LiveRange* range = parent;
   while ((range != NULL) && (source.IsInvalid() || target.IsInvalid())) {
     if (range->CanCover(source_pos)) {
       ASSERT(source.IsInvalid());
       source = range->assigned_location();
-#ifdef DEBUG
+#if defined(DEBUG)
       source_cover = range;
 #endif
     }
     if (range->CanCover(target_pos)) {
       ASSERT(target.IsInvalid());
       target = range->assigned_location();
-#ifdef DEBUG
+#if defined(DEBUG)
       target_cover = range;
 #endif
     }
@@ -1611,6 +1649,12 @@ void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* range,
   // 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()) {
+    ASSERT(parent->spill_slot().Equals(target));
+    return;
+  }
+
   Instruction* last = source_block->last_instruction();
   if (last->SuccessorCount() == 1) {
     ASSERT(last->IsGoto());
@@ -1636,6 +1680,7 @@ void FlowGraphAllocator::ResolveControlFlow() {
                   sibling->Start(), sibling->End(),
                   sibling->assigned_location().Name()));
       if ((range->End() == sibling->Start()) &&
+          !sibling->assigned_location().IsStackSlot() &&
           !range->assigned_location().Equals(sibling->assigned_location()) &&
           !IsBlockEntry(range->End())) {
         AddMoveAt(sibling->Start(),
@@ -1657,6 +1702,20 @@ void FlowGraphAllocator::ResolveControlFlow() {
       }
     }
   }
+
+  // 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()) {
+      ASSERT(range->assigned_location().Equals(range->spill_slot()));
+    } else {
+      AddMoveAt(range->Start() + 1,
+                range->spill_slot(),
+                range->assigned_location());
+    }
+  }
 }
 
 
@@ -1671,10 +1730,6 @@ void FlowGraphAllocator::AllocateRegisters() {
     DumpLiveness();
   }
 
-  if (FLAG_trace_ssa_allocator) {
-    PrintLiveRanges();
-  }
-
   AllocateCPURegisters();
 
   ResolveControlFlow();
@@ -1683,10 +1738,19 @@ void FlowGraphAllocator::AllocateRegisters() {
   ASSERT(entry != NULL);
   entry->set_spill_slot_count(spill_slots_.length());
 
-  if (FLAG_trace_ssa_allocator) {
-    OS::Print("-- ir after allocation -------------------------\n");
+  if (FLAG_print_ssa_liveranges) {
+    const Function& function = builder_->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(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
+    OS::Print("----------------------------------------------\n");
   }
 }