Implement basic support for deferred slow path code with calls that save and restore live registers.

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 293 matching lines @@
       return;
     } else if (uses_->location_slot() == NULL) {
       uses_->set_location_slot(location_slot);
       return;
     }
   }
   uses_ = new UsePosition(pos, uses_, location_slot);
 }
 
 
+void LiveRange::AddSafepoint(intptr_t pos, LocationSummary* locs) {
+  SafepointPosition* new_pos = new SafepointPosition(pos, locs, NULL);

[Kevin Millikin (Google), 2012/08/14 11:18:16]

Weird that new_pos has a different type than pos.  Suggestion new_pos =>
safepoint.

[Vyacheslav Egorov (Google), 2012/08/14 12:31:13]

Done.

+
+  if (safepoints_ == NULL) {
+    ASSERT(safepoints_tail_ == NULL);
+    safepoints_ = safepoints_tail_ = new_pos;
+  } else {
+    ASSERT(safepoints_tail_ != NULL);
+    ASSERT(safepoints_tail_->pos() < pos);

[Kevin Millikin (Google), 2012/08/14 11:18:16]

Comment that we assume the list is sorted by position when splitting it.

[Vyacheslav Egorov (Google), 2012/08/14 12:31:13]

Done.

+    safepoints_tail_->set_next(new_pos);
+    safepoints_tail_ = new_pos;
+  }
+}
+
+
 void LiveRange::AddHintedUse(intptr_t pos,
                              Location* location_slot,
                              Location* hint) {
   ASSERT(hint != NULL);
   AddUse(pos, location_slot);
   uses_->set_hint(hint);
 }
 
 
 void LiveRange::AddUseInterval(intptr_t start, intptr_t end) {
@@ skipping 188 matching lines @@
         slot_index -= fixed_parameters_count;
       }
 
       range->set_assigned_location(Location::StackSlot(slot_index));
       range->set_spill_slot(Location::StackSlot(slot_index));
       if (copied) {
         ASSERT(spill_slots_.length() == slot_index);
         spill_slots_.Add(range->End());
       }
 
+      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);
       }
       ConvertAllUses(range);
@@ skipping 119 matching lines @@
         GotoInstr* goto_instr = pred->last_instruction()->AsGoto();
         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);
 
       move_idx++;
     }
   }
 }
 
 
 void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block,
                                                 Instruction* current) {
@@ skipping 134 matching lines @@
   }
 
   // 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
     // 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());
     }
 
     ASSERT(!locs->out().IsUnallocated());
 #endif
   }
 
+  if (locs->contains_call() != LocationSummary::kNoCall) {
+    safepoints_.Add(current);
+  }
+
   Definition* def = current->AsDefinition();
   if (def == NULL) {
     ASSERT(locs->out().IsInvalid());
     return;
   }
 
   if (locs->out().IsInvalid()) {
     ASSERT(def->ssa_temp_index() < 0);
     return;
   }
@@ skipping 80 matching lines @@
     //
     ASSERT(out->IsUnallocated() &&
            (out->policy() == Location::kRequiresRegister));
 
     // 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);
 }
 
 
 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)) {
@@ skipping 247 matching lines @@
   return kMaxPosition;
 }
 
 
 LiveRange* LiveRange::MakeTemp(intptr_t pos, Location* location_slot) {
   UNREACHABLE();
   return NULL;
 }
 
 
+template<typename PositionType>
+PositionType* SplitListOfPositions(PositionType** head,
+                                   intptr_t split_pos,
+                                   bool split_at_start) {
+  PositionType* last_before_split = NULL;
+  PositionType* pos = *head;
+  if (split_at_start) {
+    while ((pos != NULL) && (pos->pos() < split_pos)) {
+      last_before_split = pos;
+      pos = pos->next();
+    }
+  } else {
+    while ((pos != NULL) && (pos->pos() <= split_pos)) {
+      last_before_split = pos;
+      pos = pos->next();
+    }
+  }
+
+  if (last_before_split == NULL) {
+    *head = NULL;
+  } else {
+    last_before_split->set_next(NULL);
+  }
+
+  return pos;
+}
+
+
 LiveRange* LiveRange::SplitAt(intptr_t split_pos) {
   if (Start() == split_pos) return this;
 
   UseInterval* interval = finger_.first_pending_use_interval();
   if (interval == NULL) {
     finger_.Initialize(this);
     interval = finger_.first_pending_use_interval();
   }
 
   ASSERT(split_pos < End());
@@ skipping 16 matching lines @@
                                         interval->next());
     interval->end_ = split_pos;
     interval->next_ = first_after_split;
     last_before_split = interval;
   }
 
   ASSERT(last_before_split->next() == first_after_split);
   ASSERT(last_before_split->end() <= split_pos);
   ASSERT(split_pos <= first_after_split->start());
 
-  UsePosition* last_use_before_split = NULL;
-  UsePosition* use = uses_;
-  if (split_at_start) {
-    while ((use != NULL) && (use->pos() < split_pos)) {
-      last_use_before_split = use;
-      use = use->next();
-    }
-  } else {
-    while ((use != NULL) && (use->pos() <= split_pos)) {
-      last_use_before_split = use;
-      use = use->next();
-    }
-  }
-  UsePosition* first_use_after_split = use;
+  UsePosition* first_use_after_split =
+      SplitListOfPositions(&uses_, split_pos, split_at_start);
 
-  if (last_use_before_split == NULL) {
-    uses_ = NULL;
-  } else {
-    last_use_before_split->set_next(NULL);
-  }
+  SafepointPosition* first_safepoint_after_split =
+      SplitListOfPositions(&safepoints_, split_pos, split_at_start);
 
   UseInterval* last_use_interval = (last_before_split == last_use_interval_) ?
     first_after_split : last_use_interval_;
   next_sibling_ = new LiveRange(vreg(),
                                 first_use_after_split,
                                 first_after_split,
                                 last_use_interval,
+                                first_safepoint_after_split,
                                 next_sibling_);
 
   TRACE_ALLOC(OS::Print("  split sibling [%d, %d)\n",
                         next_sibling_->Start(), next_sibling_->End()));
 
   last_use_interval_ = last_before_split;
   last_use_interval_->next_ = NULL;
 
   if (first_use_after_split != NULL) {
     finger_.UpdateAfterSplit(first_use_after_split->pos());
@@ skipping 84 matching lines @@
   }
 
   spill_slots_[idx] = last_sibling->End();
 
   range->set_spill_slot(Location::StackSlot(idx));
 
   spilled_.Add(range);
 }
 
 
-bool LiveRange::Contains(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::MarkAsObjectAtSafepoints(LiveRange* range) {
   intptr_t stack_index = range->spill_slot().stack_index();
   ASSERT(stack_index >= 0);
-  for (intptr_t i = 0; i < safepoints_.length(); ++i) {
-    if (range->Contains(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);
+
+  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);
   }
@@ skipping 288 matching lines @@
   if (range->vreg() == kNoVirtualRegister) return;
   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(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();
+    for (SafepointPosition* safepoint = range->first_safepoint();
+         safepoint != NULL;
+         safepoint = safepoint->next()) {
+      safepoint->locs()->live_registers()->Add(reg);
+    }
+  }
 }
 
 
 void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) {
   for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
     if (cpu_regs_[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];
       if (range->finger()->Advance(start)) {
         ConvertAllUses(range);
         cpu_regs_[reg][i] = NULL;
         first_evicted = i;
       }
     }
 
     if (first_evicted != -1) {
       RemoveEvicted(static_cast<Register>(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());
+  }
+}
+
+
 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])) {
@@ skipping 231 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