Revert of revert r25736

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/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
 namespace internal {
@@ skipping 56 matching lines @@
 
 void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
   DCHECK(Contains(pos) && pos.Value() != start().Value());
   auto after = new (zone) UseInterval(pos, end_);
   after->next_ = next_;
   next_ = after;
   end_ = pos;
 }
 
 
+struct LiveRange::SpillAtDefinitionList : ZoneObject {
+  SpillAtDefinitionList(int gap_index, InstructionOperand* operand,
+                        SpillAtDefinitionList* next)
+      : gap_index(gap_index), operand(operand), next(next) {}
+  const int gap_index;
+  InstructionOperand* const operand;
+  SpillAtDefinitionList* const next;
+};
+
+
 #ifdef DEBUG
 
 
 void LiveRange::Verify() const {
   UsePosition* cur = first_pos_;
   while (cur != nullptr) {
     DCHECK(Start().Value() <= cur->pos().Value() &&
            cur->pos().Value() <= End().Value());
     cur = cur->next();
   }
@@ skipping 25 matching lines @@
       kind_(UNALLOCATED_REGISTERS),
       assigned_register_(kInvalidAssignment),
       last_interval_(nullptr),
       first_interval_(nullptr),
       first_pos_(nullptr),
       parent_(nullptr),
       next_(nullptr),
       current_interval_(nullptr),
       last_processed_use_(nullptr),
       current_hint_operand_(nullptr),
-      spill_operand_(new (zone) InstructionOperand()),
       spill_start_index_(kMaxInt),
-      spill_range_(nullptr) {}
+      spill_type_(SpillType::kNoSpillType),
+      spill_operand_(nullptr),
+      spills_at_definition_(nullptr) {}
 
 
 void LiveRange::set_assigned_register(int reg, Zone* zone) {
   DCHECK(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
-  if (spill_range_ == nullptr) {
-    ConvertOperands(zone);
-  }
+  // TODO(dcarney): stop aliasing hint operands.
+  ConvertUsesToOperand(CreateAssignedOperand(zone));
 }
 
 
-void LiveRange::MakeSpilled(Zone* zone) {
+void LiveRange::MakeSpilled() {
   DCHECK(!IsSpilled());
-  DCHECK(TopLevel()->HasAllocatedSpillOperand());
+  DCHECK(!TopLevel()->HasNoSpillType());
   spilled_ = true;
   assigned_register_ = kInvalidAssignment;
-  ConvertOperands(zone);
 }
 
 
-bool LiveRange::HasAllocatedSpillOperand() const {
-  DCHECK(spill_operand_ != nullptr);
-  return !spill_operand_->IsIgnored() || spill_range_ != nullptr;
+void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
+                                  InstructionOperand* operand) {
+  DCHECK(HasNoSpillType());
+  spills_at_definition_ = new (zone)
+      SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
+}
+
+
+void LiveRange::CommitSpillsAtDefinition(InstructionSequence* sequence,
+                                         InstructionOperand* op) {
+  auto to_spill = TopLevel()->spills_at_definition_;
+  if (to_spill == nullptr) return;
+  auto zone = sequence->zone();
+  for (; to_spill != nullptr; to_spill = to_spill->next) {
+    auto gap = sequence->GapAt(to_spill->gap_index);
+    auto move = gap->GetOrCreateParallelMove(GapInstruction::START, zone);
+    move->AddMove(to_spill->operand, op, zone);
+  }
+  TopLevel()->spills_at_definition_ = nullptr;
 }
 
 
 void LiveRange::SetSpillOperand(InstructionOperand* operand) {
+  DCHECK(HasNoSpillType());
   DCHECK(!operand->IsUnallocated());
-  DCHECK(spill_operand_ != nullptr);
-  DCHECK(spill_operand_->IsIgnored());
-  spill_operand_->ConvertTo(operand->kind(), operand->index());
+  spill_type_ = SpillType::kSpillOperand;
+  spill_operand_ = operand;
+}
+
+
+void LiveRange::SetSpillRange(SpillRange* spill_range) {
+  DCHECK(HasNoSpillType() || HasSpillRange());
+  DCHECK_NE(spill_range, nullptr);
+  spill_type_ = SpillType::kSpillRange;
+  spill_range_ = spill_range;
 }
 
 
 void LiveRange::CommitSpillOperand(InstructionOperand* operand) {
-  DCHECK(spill_range_ != nullptr);
+  DCHECK(HasSpillRange());
+  DCHECK(!operand->IsUnallocated());
   DCHECK(!IsChild());
-  spill_range_ = nullptr;
-  SetSpillOperand(operand);
-  for (auto range = this; range != nullptr; range = range->next()) {
-    if (range->IsSpilled()) {
-      range->ConvertUsesToOperand(operand);
-    }
-  }
+  spill_type_ = SpillType::kSpillOperand;
+  spill_operand_ = operand;
 }
 
 
 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) {
   UsePosition* use_pos = last_processed_use_;
   if (use_pos == nullptr) use_pos = first_pos();
   while (use_pos != nullptr && use_pos->pos().Value() < start.Value()) {
     use_pos = use_pos->next();
   }
   last_processed_use_ = use_pos;
@@ skipping 49 matching lines @@
     switch (Kind()) {
       case GENERAL_REGISTERS:
         op = RegisterOperand::Create(assigned_register(), zone);
         break;
       case DOUBLE_REGISTERS:
         op = DoubleRegisterOperand::Create(assigned_register(), zone);
         break;
       default:
         UNREACHABLE();
     }
-  } else if (IsSpilled()) {
+  } else {
+    DCHECK(IsSpilled());
     DCHECK(!HasRegisterAssigned());
     op = TopLevel()->GetSpillOperand();
     DCHECK(!op->IsUnallocated());
-  } else {
-    UnallocatedOperand* unalloc =
-        new (zone) UnallocatedOperand(UnallocatedOperand::NONE);
-    unalloc->set_virtual_register(id_);
-    op = unalloc;
   }
   return op;
 }
 
 
 UseInterval* LiveRange::FirstSearchIntervalForPosition(
     LifetimePosition position) const {
   if (current_interval_ == nullptr) return first_interval_;
   if (current_interval_->start().Value() > position.Value()) {
     current_interval_ = nullptr;
@@ skipping 218 matching lines @@
     if (use_pos->HasOperand()) {
       DCHECK(op->IsRegister() || op->IsDoubleRegister() ||
              !use_pos->RequiresRegister());
       use_pos->operand()->ConvertTo(op->kind(), op->index());
     }
     use_pos = use_pos->next();
   }
 }
 
 
-void LiveRange::ConvertOperands(Zone* zone) {
-  ConvertUsesToOperand(CreateAssignedOperand(zone));
-}
-
-
 bool LiveRange::CanCover(LifetimePosition position) const {
   if (IsEmpty()) return false;
   return Start().Value() <= position.Value() &&
          position.Value() < End().Value();
 }
 
 
 bool LiveRange::Covers(LifetimePosition position) {
   if (!CanCover(position)) return false;
   auto start_search = FirstSearchIntervalForPosition(position);
@@ skipping 310 matching lines @@
       result = new_node;
     } else {
       node->set_next(new_node);
     }
     node = new_node;
     src = src->next();
   }
   use_interval_ = result;
   live_ranges().push_back(range);
   end_position_ = node->end();
-  DCHECK(range->GetSpillRange() == nullptr);
+  DCHECK(!range->HasSpillRange());
   range->SetSpillRange(this);
 }
 
 
 bool SpillRange::IsIntersectingWith(SpillRange* other) const {
   if (this->use_interval_ == nullptr || other->use_interval_ == nullptr ||
       this->End().Value() <= other->use_interval_->start().Value() ||
       other->End().Value() <= this->use_interval_->start().Value()) {
     return false;
   }
@@ skipping 83 matching lines @@
     int index = frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS);
     auto op_kind = kind == DOUBLE_REGISTERS
                        ? InstructionOperand::DOUBLE_STACK_SLOT
                        : InstructionOperand::STACK_SLOT;
     auto op = new (code_zone()) InstructionOperand(op_kind, index);
     range->SetOperand(op);
   }
 }
 
 
+void RegisterAllocator::CommitAssignment() {
+  for (auto range : live_ranges()) {
+    if (range == nullptr || range->IsEmpty()) continue;
+    // Register assignments were committed in set_assigned_register.
+    if (range->HasRegisterAssigned()) continue;
+    auto assigned = range->CreateAssignedOperand(code_zone());
+    range->ConvertUsesToOperand(assigned);
+    if (range->IsSpilled()) {
+      range->CommitSpillsAtDefinition(code(), assigned);
+    }
+  }
+}
+
+
 SpillRange* RegisterAllocator::AssignSpillRangeToLiveRange(LiveRange* range) {
   DCHECK(FLAG_turbo_reuse_spill_slots);
   auto spill_range = new (local_zone()) SpillRange(range, local_zone());
   spill_ranges().push_back(spill_range);
   return spill_range;
 }
 
 
 bool RegisterAllocator::TryReuseSpillForPhi(LiveRange* range) {
   DCHECK(FLAG_turbo_reuse_spill_slots);
-  DCHECK(!range->HasAllocatedSpillOperand());
+  DCHECK(range->HasNoSpillType());
   if (range->IsChild() || !range->is_phi()) return false;
 
   auto lookup = phi_map_.find(range->id());
   DCHECK(lookup != phi_map_.end());
   auto phi = lookup->second.phi;
   auto block = lookup->second.block;
   // Count the number of spilled operands.
   size_t spilled_count = 0;
   LiveRange* first_op = nullptr;
   for (size_t i = 0; i < phi->operands().size(); i++) {
@@ skipping 123 matching lines @@
 
         code()->AddGapMove(gap_index, output, output_copy);
       }
     }
 
     if (!assigned) {
       for (auto succ : block->successors()) {
         const InstructionBlock* successor = code()->InstructionBlockAt(succ);
         DCHECK(successor->PredecessorCount() == 1);
         int gap_index = successor->first_instruction_index() + 1;
+        range->SpillAtDefinition(local_zone(), gap_index, output);
         range->SetSpillStartIndex(gap_index);
-
-        // This move to spill operand is not a real use. Liveness analysis
-        // and splitting of live ranges do not account for it.
-        // Thus it should be inserted to a lifetime position corresponding to
-        // the instruction end.
-        auto gap = code()->GapAt(gap_index);
-        auto move =
-            gap->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone());
-        move->AddMove(output, range->GetSpillOperand(), code_zone());
       }
     }
   }
 }
 
 
 void RegisterAllocator::MeetConstraintsBetween(Instruction* first,
                                                Instruction* second,
                                                int gap_index) {
   if (first != nullptr) {
@@ skipping 28 matching lines @@
             range->SetSpillOperand(first_output);
             range->SetSpillStartIndex(gap_index - 1);
             assigned = true;
           }
           code()->AddGapMove(gap_index, first_output, output_copy);
         }
 
         // Make sure we add a gap move for spilling (if we have not done
         // so already).
         if (!assigned) {
+          range->SpillAtDefinition(local_zone(), gap_index, first_output);
           range->SetSpillStartIndex(gap_index);
-
-          // This move to spill operand is not a real use. Liveness analysis
-          // and splitting of live ranges do not account for it.
-          // Thus it should be inserted to a lifetime position corresponding to
-          // the instruction end.
-          auto gap = code()->GapAt(gap_index);
-          auto move =
-              gap->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone());
-          move->AddMove(first_output, range->GetSpillOperand(), code_zone());
         }
       }
     }
   }
 
   if (second != nullptr) {
     // Handle fixed input operands of second instruction.
     for (size_t i = 0; i < second->InputCount(); i++) {
       auto input = second->InputAt(i);
       if (input->IsImmediate()) continue;  // Ignore immediates.
@@ skipping 75 matching lines @@
     if (instr->IsGapMoves()) {
       // Process the moves of the gap instruction, making their sources live.
       auto gap = code()->GapAt(index);
 
       // TODO(titzer): no need to create the parallel move if it doesn't exist.
       auto move =
           gap->GetOrCreateParallelMove(GapInstruction::START, code_zone());
       const ZoneList<MoveOperands>* move_operands = move->move_operands();
       for (int i = 0; i < move_operands->length(); ++i) {
         auto cur = &move_operands->at(i);
-        if (cur->IsIgnored()) continue;
         auto from = cur->source();
         auto to = cur->destination();
         auto hint = to;
         if (to->IsUnallocated()) {
           int to_vreg = UnallocatedOperand::cast(to)->virtual_register();
           auto to_range = LiveRangeFor(to_vreg);
           if (to_range->is_phi()) {
             DCHECK(!FLAG_turbo_delay_ssa_decon);
             if (to_range->is_non_loop_phi()) {
               hint = to_range->current_hint_operand();
@@ skipping 102 matching lines @@
             code()->InstructionBlockAt(block->predecessors()[i]);
         // The gap move must be added without any special processing as in
         // the AddConstraintsGapMove.
         code()->AddGapMove(cur_block->last_instruction_index() - 1,
                            phi->inputs()[i], output);
         DCHECK(!InstructionAt(cur_block->last_instruction_index())
                     ->HasPointerMap());
       }
     }
     auto live_range = LiveRangeFor(phi_vreg);
-    auto block_start = code()->GetBlockStart(block->rpo_number());
-    block_start->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone())
-        ->AddMove(output, live_range->GetSpillOperand(), code_zone());
-    live_range->SetSpillStartIndex(block->first_instruction_index());
+    int gap_index = block->first_instruction_index();
+    live_range->SpillAtDefinition(local_zone(), gap_index, output);
+    live_range->SetSpillStartIndex(gap_index);
     // We use the phi-ness of some nodes in some later heuristics.
     live_range->set_is_phi(true);
     live_range->set_is_non_loop_phi(!block->IsLoopHeader());
   }
 }
 
 
 void RegisterAllocator::MeetRegisterConstraints() {
   for (auto block : code()->instruction_blocks()) {
     MeetRegisterConstraints(block);
@@ skipping 338 matching lines @@
     }
   }
 
   for (auto range : live_ranges()) {
     if (range == nullptr) continue;
     range->kind_ = RequiredRegisterKind(range->id());
     // TODO(bmeurer): This is a horrible hack to make sure that for constant
     // live ranges, every use requires the constant to be in a register.
     // Without this hack, all uses with "any" policy would get the constant
     // operand assigned.
-    if (range->HasAllocatedSpillOperand() &&
-        range->GetSpillOperand()->IsConstant()) {
+    if (range->HasSpillOperand() && range->GetSpillOperand()->IsConstant()) {
       for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next_) {
         pos->register_beneficial_ = true;
         // TODO(dcarney): should the else case assert requires_reg_ == false?
         // Can't mark phis as needing a register.
         if (!code()
                  ->InstructionAt(pos->pos().InstructionIndex())
                  ->IsGapMoves()) {
           pos->requires_reg_ = true;
         }
       }
@@ skipping 83 matching lines @@
       // safe point position.
       auto safe_point_pos = LifetimePosition::FromInstructionIndex(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 (range->HasAllocatedSpillOperand() &&
+      if (range->HasSpillOperand() &&
           safe_point >= range->spill_start_index() &&
           !range->GetSpillOperand()->IsConstant()) {
         TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n",
                    range->id(), range->spill_start_index(), safe_point);
         map->RecordPointer(range->GetSpillOperand(), code_zone());
       }
 
       if (!cur->IsSpilled()) {
         TraceAlloc(
             "Pointer in register for range %d (start at %d) "
@@ skipping 59 matching lines @@
     auto current = unhandled_live_ranges().back();
     unhandled_live_ranges().pop_back();
     DCHECK(UnhandledIsSorted());
     auto position = current->Start();
 #ifdef DEBUG
     allocation_finger_ = position;
 #endif
     TraceAlloc("Processing interval %d start=%d\n", current->id(),
                position.Value());
 
-    if (current->HasAllocatedSpillOperand()) {
+    if (!current->HasNoSpillType()) {
       TraceAlloc("Live range %d already has a spill operand\n", current->id());
       auto next_pos = position;
       if (code()->IsGapAt(next_pos.InstructionIndex())) {
         next_pos = next_pos.NextInstruction();
       }
       auto pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
       // If the range already has a spill operand and it doesn't need a
       // register immediately, split it and spill the first part of the range.
       if (pos == nullptr) {
         Spill(current);
@@ skipping 144 matching lines @@
     if (a->Start().Value() < b->Start().Value()) return false;
   }
   return true;
 }
 
 
 void RegisterAllocator::FreeSpillSlot(LiveRange* range) {
   DCHECK(!FLAG_turbo_reuse_spill_slots);
   // Check that we are the last range.
   if (range->next() != nullptr) return;
-  if (!range->TopLevel()->HasAllocatedSpillOperand()) return;
+  if (!range->TopLevel()->HasSpillOperand()) return;
   auto spill_operand = range->TopLevel()->GetSpillOperand();
   if (spill_operand->IsConstant()) return;
   if (spill_operand->index() >= 0) {
     reusable_slots().push_back(range);
   }
 }
 
 
 InstructionOperand* RegisterAllocator::TryReuseSpillSlot(LiveRange* range) {
   DCHECK(!FLAG_turbo_reuse_spill_slots);
@@ skipping 394 matching lines @@
     // Nothing to spill. Just put it to unhandled as whole.
     AddToUnhandledSorted(second_part);
   }
 }
 
 
 void RegisterAllocator::Spill(LiveRange* range) {
   DCHECK(!range->IsSpilled());
   TraceAlloc("Spilling live range %d\n", range->id());
   auto first = range->TopLevel();
-  if (!first->HasAllocatedSpillOperand()) {
+  if (first->HasNoSpillType()) {
     if (FLAG_turbo_reuse_spill_slots) {
       AssignSpillRangeToLiveRange(first);
     } else {
       auto op = TryReuseSpillSlot(range);
       if (op == nullptr) {
         // Allocate a new operand referring to the spill slot.
         RegisterKind kind = range->Kind();
         int index = frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS);
-        if (kind == DOUBLE_REGISTERS) {
-          op = DoubleStackSlotOperand::Create(index, local_zone());
-        } else {
-          DCHECK(kind == GENERAL_REGISTERS);
-          op = StackSlotOperand::Create(index, local_zone());
-        }
+        auto op_kind = kind == DOUBLE_REGISTERS
+                           ? InstructionOperand::DOUBLE_STACK_SLOT
+                           : InstructionOperand::STACK_SLOT;
+        op = new (code_zone()) InstructionOperand(op_kind, index);
       }
       first->SetSpillOperand(op);
     }
   }
-  range->MakeSpilled(code_zone());
+  range->MakeSpilled();
 }
 
 
 int RegisterAllocator::RegisterCount() const { return num_registers_; }
 
 
 #ifdef DEBUG
 
 
 void RegisterAllocator::Verify() const {
@@ skipping 13 matching lines @@
   } else {
     DCHECK(range->Kind() == GENERAL_REGISTERS);
     assigned_registers_->Add(reg);
   }
   range->set_assigned_register(reg, code_zone());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8