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* safepoint = new SafepointPosition(pos, locs);
+
+  if (first_safepoint_ == NULL) {
+    ASSERT(last_safepoint_ == NULL);
+    first_safepoint_ = last_safepoint_ = safepoint;
+  } else {
+    ASSERT(last_safepoint_ != NULL);
+    // We assume that safepoints list is sorted by position and that
+    // safepoints are added in this order.
+    ASSERT(last_safepoint_->pos() < pos);
+    last_safepoint_->set_next(safepoint);
+    last_safepoint_ = safepoint;
+  }
+}
+
+
 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()) {
+    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>

[srdjan, 2012/08/15 00:12:03]

I think this kind of code sharing makes code less maintainable, and would prefer
to use subclassing instead.

[Vyacheslav Egorov (Google), 2012/08/15 13:08:07]

I keep in mind that we try to avoid using templates and tried subclassing first.
Unfortunately in this particular case it does not fit well because return type
and head pointer will require additional ugly casts: Derived** is not actually
assignable to Base** for obvious reasons, handling of return value will also
require cast. 

+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(&first_safepoint_, 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