[turbofan] Stand-alone deferred block splitting - full.

src/compiler/register-allocator.cc

Index: src/compiler/register-allocator.cc
diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc
index 5bf858a86cf6e7551ce7a033603cc7c17990cbe2..d268b1f3b68cef2808a327771e8ba2702b60bcaf 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -256,7 +256,8 @@ LiveRange::LiveRange(int id, MachineType machine_type)
       last_processed_use_(nullptr),
       current_hint_position_(nullptr),
       size_(kInvalidSize),
-      weight_(kInvalidWeight) {
+      weight_(kInvalidWeight),
+      spilled_in_deferred_block_(false) {
   DCHECK(AllocatedOperand::IsSupportedMachineType(machine_type));
   bits_ = SpillTypeField::encode(SpillType::kNoSpillType) |
           AssignedRegisterField::encode(kUnassignedRegister) |
@@ -319,12 +320,94 @@ void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
 }
 
 
+bool LiveRange::TryCommitSpillInDeferredBlock(
+    InstructionSequence* code, const InstructionOperand& spill_operand) {
+  DCHECK(!IsChild());
+
+  if (!FLAG_turbo_preprocess_ranges || IsEmpty() || HasNoSpillType() ||
+      spill_operand.IsConstant() || spill_operand.IsImmediate()) {
+    return false;
+  }
+
+  int count = 0;
+  for (const LiveRange* child = this; child != nullptr; child = child->next()) {
+    int first_instr = child->Start().ToInstructionIndex();
+
+    // If the range starts at instruction end, the first instruction index is
+    // the next one.
+    if (!child->Start().IsGapPosition() && !child->Start().IsStart()) {
+      ++first_instr;
+    }
+
+    // We only look at where the range starts. It doesn't matter where it ends:
+    // if it ends past this block, then either there is a phi there already,
+    // or ResolveControlFlow will adapt the last instruction gap of this block
+    // as if there were a phi. In either case, data flow will be correct.
+    const InstructionBlock* block = code->GetInstructionBlock(first_instr);
+
+    // If we have slot uses in a subrange, bail out, because we need the value
+    // on the stack before that use.
+    bool has_slot_use = child->NextSlotPosition(child->Start()) != nullptr;
+    if (!block->IsDeferred()) {
+      if (child->spilled() || has_slot_use) {
+        TRACE(
+            "Live Range %d must be spilled at definition: found a "
+            "slot-requiring non-deferred child range %d.\n",
+            TopLevel()->id(), child->id());
+        return false;
+      }
+    } else {
+      if (child->spilled() || has_slot_use) ++count;
+    }
+  }
+  if (count == 0) return false;
+
+  spill_start_index_ = -1;
+  spilled_in_deferred_block_ = true;
+
+  TRACE("Live Range %d will be spilled only in deferred blocks.\n", id());
+  // If we have ranges that aren't spilled but require the operand on the stack,
+  // make sure we insert the spill.
+  for (const LiveRange* child = this; child != nullptr; child = child->next()) {
+    if (!child->spilled() &&
+        child->NextSlotPosition(child->Start()) != nullptr) {
+      auto instr = code->InstructionAt(child->Start().ToInstructionIndex());
+      // Insert spill at the end to let live range connections happen at START.
+      auto move =
+          instr->GetOrCreateParallelMove(Instruction::END, code->zone());
+      InstructionOperand assigned = child->GetAssignedOperand();
+      if (TopLevel()->has_slot_use()) {
+        bool found = false;
+        for (auto move_op : *move) {
+          if (move_op->IsEliminated()) continue;
+          if (move_op->source().Equals(assigned) &&
+              move_op->destination().Equals(spill_operand)) {
+            found = true;
+            break;
+          }
+        }
+        if (found) continue;
+      }
+
+      move->AddMove(assigned, spill_operand);

[Jarin, 2015/08/04 19:39:43]

Still confused about this - where do we actually spill the deferred block with a
call? This move seems to be only inserted for ranges that are not spilled.

[Mircea Trofin, 2015/08/04 20:34:46]

Correct. It sets up the stage for the register allocator. The register allocator
will make the decision of where to spill, but now it will treat the segments
over deferred ranges separately from the rest of the range.

[Jarin, 2015/08/05 14:04:16]

I am sorry, that explanation did not really help me understand. As far as I
understand, CommitSpillsAtDefinition runs after the actual allocation, so I do
not see how this can setup the stage for register allocation. Could you explain?
Where exactly is the place that adds the spilling move for deferred blocks with
calls?

Or are you saying that the pre-processing phase inserts live ranges for the
deferred blocks so that the register allocator can spill those ranges (and since
those ranges begin in deferred blocks, they would get the right spill)? I cannot
see how this would work either because the pre-processing seems to only create
child ranges, so they would not really get their own definitions.

+    }
+  }
+
+  return true;
+}
+
+
 void LiveRange::CommitSpillsAtDefinition(InstructionSequence* sequence,
                                          const InstructionOperand& op,
                                          bool might_be_duplicated) {
   DCHECK_IMPLIES(op.IsConstant(), spills_at_definition_ == nullptr);
   DCHECK(!IsChild());
   auto zone = sequence->zone();
+
+  // If this top level range has a child spilled in a deferred block, we use
+  // the range and control flow connection mechanism instead.
+  if (TryCommitSpillInDeferredBlock(sequence, op)) return;
+
   for (auto to_spill = spills_at_definition_; to_spill != nullptr;
        to_spill = to_spill->next) {
     auto instr = sequence->InstructionAt(to_spill->gap_index);
@@ -416,6 +499,16 @@ UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const {
 }
 
 
+UsePosition* LiveRange::NextSlotPosition(LifetimePosition start) const {
+  for (UsePosition* pos = NextUsePosition(start); pos != nullptr;
+       pos = pos->next()) {
+    if (pos->type() != UsePositionType::kRequiresSlot) continue;
+    return pos;
+  }
+  return nullptr;
+}
+
+
 bool LiveRange::CanBeSpilled(LifetimePosition pos) const {
   // We cannot spill a live range that has a use requiring a register
   // at the current or the immediate next position.
@@ -1493,7 +1586,15 @@ void LiveRangeBuilder::ProcessInstructions(const InstructionBlock* block,
         int out_vreg = ConstantOperand::cast(output)->virtual_register();
         live->Remove(out_vreg);
       }
-      Define(curr_position, output);
+      if (block->IsHandler() && index == block_start) {
+        // The register defined here is blocked from gap start - it is the
+        // exception value.
+        // TODO(mtrofin): should we explore an explicit opcode for
+        // the first instruction in the handler?
+        Define(LifetimePosition::GapFromInstructionIndex(index), output);
+      } else {
+        Define(curr_position, output);
+      }
     }
 
     if (instr->ClobbersRegisters()) {
@@ -2580,10 +2681,13 @@ void ReferenceMapPopulator::PopulateReferenceMaps() {
 
       // Check if the live range is spilled and the safe point is after
       // the spill position.
-      if (!spill_operand.IsInvalid() &&
-          safe_point >= range->spill_start_index()) {
+      int spill_index = range->IsSpilledInSingleDeferredBlock()
+                            ? cur->Start().ToInstructionIndex()
+                            : range->spill_start_index();
+
+      if (!spill_operand.IsInvalid() && safe_point >= spill_index) {
         TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
-              range->id(), range->spill_start_index(), safe_point);
+              range->id(), spill_index, safe_point);
         map->RecordReference(AllocatedOperand::cast(spill_operand));
       }
 
@@ -2780,7 +2884,8 @@ void LiveRangeConnector::ResolveControlFlow(Zone* local_zone) {
         const auto* pred_block = code()->InstructionBlockAt(pred);
         array->Find(block, pred_block, &result);
         if (result.cur_cover_ == result.pred_cover_ ||
-            result.cur_cover_->spilled())
+            (!result.cur_cover_->TopLevel()->IsSpilledInSingleDeferredBlock() &&
+             result.cur_cover_->spilled()))
           continue;
         auto pred_op = result.pred_cover_->GetAssignedOperand();
         auto cur_op = result.cur_cover_->GetAssignedOperand();
@@ -2819,12 +2924,13 @@ void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
   DelayedInsertionMap delayed_insertion_map(local_zone);
   for (auto first_range : data()->live_ranges()) {
     if (first_range == nullptr || first_range->IsChild()) continue;
+    bool connect_spilled = first_range->IsSpilledInSingleDeferredBlock();
     for (auto second_range = first_range->next(); second_range != nullptr;
          first_range = second_range, second_range = second_range->next()) {
       auto pos = second_range->Start();
       // Add gap move if the two live ranges touch and there is no block
       // boundary.
-      if (second_range->spilled()) continue;
+      if (!connect_spilled && second_range->spilled()) continue;
       if (first_range->End() != pos) continue;
       if (data()->IsBlockBoundary(pos) &&
           !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) {