Implement simple spill store elimination.

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"
 #include "vm/flow_graph_compiler.h"
 #include "vm/parser.h"
 
 namespace dart {
 
 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)
 #else
 #define TRACE_ALLOC(m)
 #endif
 
 
 static const intptr_t kNoVirtualRegister = -1;
 static const intptr_t kTempVirtualRegister = -2;
@@ skipping 300 matching lines @@
 
 
 LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) {
   if (live_ranges_[vreg] == NULL) {
     live_ranges_[vreg] = new LiveRange(vreg);
   }
   return live_ranges_[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());
   ASSERT(IsInstructionStartPosition(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;
        interval = interval->next()) {
     OS::Print("    use interval [%d, %d)\n",
               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();
     }
   }
 
   if (next_sibling() != NULL) {
     next_sibling()->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();
+    }
   }
 }
 
 
 void FlowGraphAllocator::BuildLiveRanges() {
   NumberInstructions();
 
   const intptr_t block_count = postorder_.length();
   ASSERT(postorder_[block_count - 1]->IsGraphEntry());
   for (intptr_t i = 0; i < (block_count - 1); i++) {
@@ skipping 33 matching lines @@
     if (val->IsUse()) {
       ParameterInstr* param = val->AsUse()->definition()->AsParameter();
 
       LiveRange* range = GetLiveRange(param->ssa_temp_index());
       range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos());
       range->DefineAt(graph_entry->start_pos());
 
       // 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(
           graph_entry->start_pos());
       if (use != NULL) {
         LiveRange* tail = SplitBetween(range,
                                        graph_entry->start_pos(),
                                        use->pos());
         AddToUnallocated(tail);
       }
@@ skipping 233 matching lines @@
     // 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);
+      LiveRange* range = MakeLiveRangeForTemporary();
       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
+#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++) {
       ASSERT(!locs->temp(j).IsUnallocated());
     }
 
     for (intptr_t j = 0; j < locs->input_count(); j++) {
       ASSERT(!locs->in(j).IsUnallocated());
     }
@@ skipping 10 matching lines @@
 
   if (locs->out().IsInvalid()) {
     ASSERT(def->ssa_temp_index() < 0);
     return;
   }
 
   // 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()) :
-      new LiveRange(kTempVirtualRegister);
+      MakeLiveRangeForTemporary();
   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        [--)
     //    output             [-------
     //
@@ skipping 386 matching lines @@
 
 
 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) {
   TRACE_ALLOC(("spill %d [%d, %d) after %d\n",
                range->vreg(), range->Start(), range->End(), from));
   LiveRange* tail = range->SplitAt(from);
   Spill(tail);
 }
 
 
-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);
 }
 
 
 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
   Register reg, LiveRange* unallocated) {
   intptr_t intersection = kMaxPosition;
   for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
     LiveRange* allocated = cpu_regs_[reg][i];
     if (allocated == NULL) continue;
@@ skipping 320 matching lines @@
   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);
 }
 
 
-#ifdef DEBUG
+#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() {
-#ifdef DEBUG
+#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);
     }
   }
 
@@ skipping 15 matching lines @@
 
   // All allocation decisions were done.
   ASSERT(unallocated_.is_empty());
 
   // Finish allocation.
   AdvanceActiveIntervals(kMaxPosition);
   TRACE_ALLOC(("Allocation completed\n"));
 }
 
 
-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;
   }
 
   const intptr_t source_pos = source_block->end_pos() - 1;
   ASSERT(IsInstructionEndPosition(source_pos));
 
   const intptr_t target_pos = target_block->start_pos();
 
   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
     }
 
     range = range->next_sibling();
   }
 
   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;
 
+  // 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());
     last->AsGoto()->GetParallelMove()->AddMove(target, source);
   } else {
     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()) &&
+          !sibling->assigned_location().IsStackSlot() &&
           !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()) {
+      ASSERT(range->assigned_location().Equals(range->spill_slot()));
+    } else {
+      AddMoveAt(range->Start() + 1,
+                range->spill_slot(),
+                range->assigned_location());
+    }
+  }
 }
 
 
 void FlowGraphAllocator::AllocateRegisters() {
   EliminateEnvironmentUses();
 
   AnalyzeLiveness();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
     DumpLiveness();
   }
 
-  if (FLAG_trace_ssa_allocator) {
-    PrintLiveRanges();
-  }
-
   AllocateCPURegisters();
 
   ResolveControlFlow();
 
   GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
   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");
   }
 }
 
 
 }  // namespace dart