Build and use stack maps in the SSA compiler.

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 464 matching lines @@
         ProcessOneInstruction(block, current);
       }
       current = current->previous();
     }
 
     ConnectIncomingPhiMoves(block);
   }
 
   const bool copied = builder_->copied_parameter_count() > 0;
 
-  // Process incoming parameters.
+  // Process incoming parameters.  Do this after all other instructions so
+  // that safepoints for all calls have already been found.
   const intptr_t fixed_parameters_count =
       builder_->parsed_function().function().num_fixed_parameters();
 
   GraphEntryInstr* graph_entry = postorder_[block_count - 1]->AsGraphEntry();
   for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) {
     Value* val = graph_entry->start_env()->values()[i];
     if (val->IsUse()) {
       ParameterInstr* param = val->AsUse()->definition()->AsParameter();
 
       LiveRange* range = GetLiveRange(param->ssa_temp_index());
@@ skipping 17 matching lines @@
       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);
       }
       ConvertAllUses(range);
+      if (copied) {
+        for (intptr_t i = 0; i < safepoints_.length(); ++i) {

[Vyacheslav Egorov (Google), 2012/08/13 12:54:46]

Please move this code into a separate function.

It is duplicated in two places.

[Kevin Millikin (Google), 2012/08/13 15:10:37]

OK.

+          if (range->Covers(safepoints_[i].position)) {
+            TRACE_ALLOC(OS::Print("  marking S[%d] in stack bitmap at %d\n",
+                                  slot_index,
+                                  safepoints_[i].position));
+            safepoints_[i].stack_bitmap->Set(slot_index, true);
+          }
+        }
+      }
     }
   }
 }
 
 //
 // When describing shape of live ranges in comments below we are going to use
 // the following notation:
 //
 //    B    block entry
 //    g g' start and end of goto instruction
@@ skipping 208 matching lines @@
     } else if (temp.IsUnallocated()) {
       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.
+  // Block all allocatable registers for calls and record the stack bitmap.
   if (locs->is_call()) {
     // Expected shape of live range:
     //
     //              i  i'
     //              [--)
     //
+    // The stack bitmap describes the position i.
+    Safepoint safepoint = { pos, locs->stack_bitmap() };
+    safepoints_.Add(safepoint);
 
     for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
       BlockLocation(Location::RegisterLocation(static_cast<Register>(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
@@ skipping 537 matching lines @@
   }
 
   spill_slots_[idx] = last_sibling->End();
 
   range->set_spill_slot(Location::StackSlot(idx));
 
   spilled_.Add(range);
 }
 
 
+bool LiveRange::Covers(intptr_t pos) const {
+  const LiveRange* current = this;
+  while (current != NULL) {
+    UseInterval* interval = current->first_use_interval_;
+    while (interval != NULL) {
+      if (interval->Contains(pos)) return true;
+      interval = interval->next();
+    }
+    current = current->next_sibling_;
+  }
+  return false;
+}
+
+
 void FlowGraphAllocator::Spill(LiveRange* range) {
   LiveRange* parent = GetLiveRange(range->vreg());
 
-  if (parent->spill_slot().IsInvalid()) AllocateSpillSlotFor(parent);
+  if (parent->spill_slot().IsInvalid()) {
+    AllocateSpillSlotFor(parent);
+    intptr_t stack_index = parent->spill_slot().stack_index();
+    ASSERT(stack_index >= 0);
+    for (intptr_t i = 0; i < safepoints_.length(); ++i) {
+      if (parent->Covers(safepoints_[i].position)) {
+        TRACE_ALLOC(OS::Print("  marking S[%d] in stack bitmap at %d\n",
+                              stack_index,
+                              safepoints_[i].position));
+        safepoints_[i].stack_bitmap->Set(stack_index, true);
+      }
+    }
+  }
 
   range->set_assigned_location(parent->spill_slot());
   ConvertAllUses(range);
 }
 
 
 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
-  Register reg, LiveRange* unallocated) {
+    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;
 
     UseInterval* allocated_head =
-      allocated->finger()->first_pending_use_interval();
+        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);
+        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 free_until = 0;
@@ skipping 18 matching lines @@
         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;
-
       const intptr_t intersection =
-        FirstIntersectionWithAllocated(static_cast<Register>(reg), unallocated);
-
+          FirstIntersectionWithAllocated(static_cast<Register>(reg),
+                                         unallocated);
       if (intersection > free_until) {
         candidate = static_cast<Register>(reg);
         free_until = intersection;
         if (free_until == kMaxPosition) break;
       }
     }
   }
 
   // All registers are blocked by active ranges.
   if (free_until <= unallocated->Start()) return false;
@@ skipping 76 matching lines @@
         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;
       }
 
       const UsePosition* use =
-        allocated->finger()->FirstRegisterBeneficialUse(unallocated->Start());
+          allocated->finger()->FirstRegisterBeneficialUse(unallocated->Start());
 
       if ((use != NULL) && ((use->pos() - start) <= 1)) {
         // This register is blocked by interval that is used
         // as register in the current instruction and can't
         // be spilled.
         return false;
       }
 
       const intptr_t use_pos = (use != NULL) ? use->pos()
                                              : allocated->End();
@@ skipping 53 matching lines @@
   if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
 
   cpu_regs_[reg].Add(unallocated);
   unallocated->set_assigned_location(Location::RegisterLocation(reg));
 }
 
 
 bool FlowGraphAllocator::EvictIntersection(LiveRange* allocated,
                                            LiveRange* unallocated) {
   UseInterval* first_unallocated =
-    unallocated->finger()->first_pending_use_interval();
+      unallocated->finger()->first_pending_use_interval();
   const intptr_t intersection = FirstIntersection(
       allocated->finger()->first_pending_use_interval(),
       first_unallocated);
   if (intersection == kMaxPosition) return false;
 
   const intptr_t spill_position = first_unallocated->start();
   UsePosition* use = allocated->finger()->FirstRegisterUse(spill_position);
   if (use == NULL) {
     // No register uses after this point.
     SpillAfter(allocated, spill_position);
   } else {
     const intptr_t restore_position =
-      (spill_position < intersection) ? MinPosition(intersection, use->pos())
-                                      : use->pos();
+        (spill_position < intersection) ? MinPosition(intersection, use->pos())
+                                        : use->pos();
 
     SpillBetween(allocated, spill_position, restore_position);
   }
 
   return true;
 }
 
 
 MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos,
                                             Location to,
@@ skipping 311 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart