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

src/compiler/register-allocator.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 238 matching lines @@
       first_interval_(nullptr),
       first_pos_(nullptr),
       parent_(nullptr),
       next_(nullptr),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr),
       current_interval_(nullptr),
       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) |
           MachineTypeField::encode(machine_type);
 }
 
 
 void LiveRange::Verify() const {
   // Walk the positions, verifying that each is in an interval.
   auto interval = first_interval_;
@@ skipping 42 matching lines @@
 
 
 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
                                   InstructionOperand* operand) {
   DCHECK(HasNoSpillType());
   spills_at_definition_ = new (zone)
       SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
 }
 
 
+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);
     auto move = instr->GetOrCreateParallelMove(Instruction::START, zone);
     // Skip insertion if it's possible that the move exists already as a
     // constraint move from a fixed output register to a slot.
     if (might_be_duplicated) {
       bool found = false;
       for (auto move_op : *move) {
         if (move_op->IsEliminated()) continue;
@@ skipping 71 matching lines @@
 
 UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const {
   UsePosition* pos = NextUsePosition(start);
   while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister) {
     pos = pos->next();
   }
   return pos;
 }
 
 
+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.
   auto use_pos = NextRegisterPosition(pos);
   if (use_pos == nullptr) return true;
   return use_pos->pos() > pos.NextStart().End();
 }
 
 
 InstructionOperand LiveRange::GetAssignedOperand() const {
@@ skipping 1057 matching lines @@
       auto output = instr->OutputAt(i);
       if (output->IsUnallocated()) {
         // Unsupported.
         DCHECK(!UnallocatedOperand::cast(output)->HasSlotPolicy());
         int out_vreg = UnallocatedOperand::cast(output)->virtual_register();
         live->Remove(out_vreg);
       } else if (output->IsConstant()) {
         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()) {
       for (int i = 0; i < config()->num_general_registers(); ++i) {
         if (!IsOutputRegisterOf(instr, i)) {
           auto range = FixedLiveRangeFor(i);
           range->AddUseInterval(curr_position, curr_position.End(),
                                 allocation_zone());
         }
       }
@@ skipping 1066 matching lines @@
       auto safe_point_pos =
           LifetimePosition::InstructionFromInstructionIndex(safe_point);
       auto cur = range;
       while (cur != nullptr && !cur->Covers(safe_point_pos)) {
         cur = cur->next();
       }
       if (cur == nullptr) continue;
 
       // 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));
       }
 
       if (!cur->spilled()) {
         TRACE(
             "Pointer in register for range %d (start at %d) "
             "at safe point %d\n",
             cur->id(), cur->Start().value(), safe_point);
         auto operand = cur->GetAssignedOperand();
         DCHECK(!operand.IsStackSlot());
@@ skipping 176 matching lines @@
     if (CanEagerlyResolveControlFlow(block)) continue;
     auto live = live_in_sets[block->rpo_number().ToInt()];
     BitVector::Iterator iterator(live);
     while (!iterator.Done()) {
       auto* array = finder.ArrayFor(iterator.Current());
       for (auto pred : block->predecessors()) {
         FindResult result;
         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();
         if (pred_op.Equals(cur_op)) continue;
         ResolveControlFlow(block, cur_op, pred_block, pred_op);
       }
       iterator.Advance();
     }
   }
 }
@@ skipping 18 matching lines @@
     position = Instruction::END;
   }
   data()->AddGapMove(gap_index, position, pred_op, cur_op);
 }
 
 
 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))) {
         continue;
       }
       auto prev_operand = first_range->GetAssignedOperand();
       auto cur_operand = second_range->GetAssignedOperand();
       if (prev_operand.Equals(cur_operand)) continue;
       bool delay_insertion = false;
       Instruction::GapPosition gap_pos;
@@ skipping 46 matching lines @@
     auto eliminate = moves->PrepareInsertAfter(move);
     to_insert.push_back(move);
     if (eliminate != nullptr) to_eliminate.push_back(eliminate);
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8