[turbofan] add non fixed slot constraint to register allocator

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 21 matching lines @@
 
 static void RemoveElement(ZoneVector<LiveRange*>* v, LiveRange* range) {
   auto it = std::find(v->begin(), v->end(), range);
   DCHECK(it != v->end());
   v->erase(it);
 }
 
 
 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand,
                          InstructionOperand* hint)
-    : operand_(operand),
-      hint_(hint),
-      pos_(pos),
-      next_(nullptr),
-      requires_reg_(false),
-      register_beneficial_(true) {
+    : operand_(operand), hint_(hint), pos_(pos), next_(nullptr), flags_(0) {
+  bool register_beneficial = true;
+  UsePositionType type = UsePositionType::kAny;
   if (operand_ != nullptr && operand_->IsUnallocated()) {
     const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_);
-    requires_reg_ = unalloc->HasRegisterPolicy();
-    register_beneficial_ = !unalloc->HasAnyPolicy();
+    if (unalloc->HasRegisterPolicy()) {
+      type = UsePositionType::kRequiresRegister;
+    } else if (unalloc->HasSlotPolicy()) {
+      type = UsePositionType::kRequiresSlot;
+      register_beneficial = false;
+    } else {
+      register_beneficial = !unalloc->HasAnyPolicy();
+    }
   }
+  flags_ = TypeField::encode(type) |
+           RegisterBeneficialField::encode(register_beneficial);
   DCHECK(pos_.IsValid());
 }
 
 
 bool UsePosition::HasHint() const {
   return hint_ != nullptr && !hint_->IsUnallocated();
 }
 
 
-bool UsePosition::RequiresRegister() const { return requires_reg_; }
-
-
-bool UsePosition::RegisterIsBeneficial() const { return register_beneficial_; }
+void UsePosition::set_type(UsePositionType type, bool register_beneficial) {
+  DCHECK_IMPLIES(type == UsePositionType::kRequiresSlot, !register_beneficial);
+  flags_ = TypeField::encode(type) |
+           RegisterBeneficialField::encode(register_beneficial);
+}
 
 
 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;
 }
 
@@ skipping 34 matching lines @@
   return false;
 }
 
 
 #endif
 
 
 LiveRange::LiveRange(int id, Zone* zone)
     : id_(id),
       spilled_(false),
+      has_slot_use_(false),
       is_phi_(false),
       is_non_loop_phi_(false),
       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_start_index_(kMaxInt),
       spill_type_(SpillType::kNoSpillType),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr) {}
 
 
 void LiveRange::set_assigned_register(int reg,
                                       InstructionOperandCache* operand_cache) {
   DCHECK(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
   // TODO(dcarney): stop aliasing hint operands.
-  ConvertUsesToOperand(GetAssignedOperand(operand_cache));
+  ConvertUsesToOperand(GetAssignedOperand(operand_cache), nullptr);
 }
 
 
 void LiveRange::MakeSpilled() {
   DCHECK(!IsSpilled());
   DCHECK(!TopLevel()->HasNoSpillType());
   spilled_ = true;
   assigned_register_ = kInvalidAssignment;
 }
 
 
 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;
+                                         InstructionOperand* op,
+                                         bool might_be_duplicated) {
+  DCHECK(!IsChild());
   auto zone = sequence->zone();
-  for (; to_spill != nullptr; to_spill = to_spill->next) {
+  for (auto to_spill = spills_at_definition_; to_spill != nullptr;
+       to_spill = to_spill->next) {
     auto gap = sequence->GapAt(to_spill->gap_index);
     auto move = gap->GetOrCreateParallelMove(GapInstruction::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;
+      auto move_ops = move->move_operands();
+      for (auto move_op = move_ops->begin(); move_op != move_ops->end();
+           ++move_op) {
+        if (move_op->IsEliminated()) continue;
+        if (move_op->source()->Equals(to_spill->operand) &&
+            move_op->destination()->Equals(op)) {
+          found = true;
+          break;
+        }
+      }
+      if (found) continue;
+    }
     move->AddMove(to_spill->operand, op, zone);
   }
-  TopLevel()->spills_at_definition_ = nullptr;
 }
 
 
 void LiveRange::SetSpillOperand(InstructionOperand* operand) {
   DCHECK(HasNoSpillType());
   DCHECK(!operand->IsUnallocated());
   spill_type_ = SpillType::kSpillOperand;
   spill_operand_ = operand;
 }
 
@@ skipping 43 matching lines @@
   while (pos != nullptr && pos->pos().Value() < start.Value()) {
     if (pos->RegisterIsBeneficial()) prev = pos;
     pos = pos->next();
   }
   return prev;
 }
 
 
 UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) {
   UsePosition* pos = NextUsePosition(start);
-  while (pos != nullptr && !pos->RequiresRegister()) {
+  while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister) {
     pos = pos->next();
   }
   return pos;
 }
 
 
 bool LiveRange::CanBeSpilled(LifetimePosition pos) {
   // 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);
@@ skipping 254 matching lines @@
     use_pos->next_ = prev->next_;
     prev->next_ = use_pos;
   }
 
   if (prev_hint == nullptr && use_pos->HasHint()) {
     current_hint_operand_ = hint;
   }
 }
 
 
-void LiveRange::ConvertUsesToOperand(InstructionOperand* op) {
-  auto use_pos = first_pos();
-  while (use_pos != nullptr) {
-    DCHECK(Start().Value() <= use_pos->pos().Value() &&
-           use_pos->pos().Value() <= End().Value());
-
-    if (use_pos->HasOperand()) {
-      DCHECK(op->IsRegister() || op->IsDoubleRegister() ||
-             !use_pos->RequiresRegister());
-      use_pos->operand()->ConvertTo(op->kind(), op->index());
+void LiveRange::ConvertUsesToOperand(InstructionOperand* op,
+                                     InstructionOperand* spill_op) {
+  for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
+    DCHECK(Start().Value() <= pos->pos().Value() &&
+           pos->pos().Value() <= End().Value());
+    if (!pos->HasOperand()) {
+      continue;
     }
-    use_pos = use_pos->next();
+    switch (pos->type()) {
+      case UsePositionType::kRequiresSlot:
+        if (spill_op != nullptr) {
+          pos->operand()->ConvertTo(spill_op->kind(), spill_op->index());
+        }
+        break;
+      case UsePositionType::kRequiresRegister:
+        DCHECK(op->IsRegister() || op->IsDoubleRegister());
+      // Fall through.
+      case UsePositionType::kAny:
+        pos->operand()->ConvertTo(op->kind(), op->index());
+        break;
+    }
   }
 }
 
 
 bool LiveRange::CanCover(LifetimePosition position) const {
   if (IsEmpty()) return false;
   return Start().Value() <= position.Value() &&
          position.Value() < End().Value();
 }
 
@@ skipping 416 matching lines @@
                        : InstructionOperand::STACK_SLOT;
     auto op = InstructionOperand::New(code_zone(), 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->GetAssignedOperand(operand_cache());
-    range->ConvertUsesToOperand(assigned);
-    if (range->IsSpilled()) {
-      range->CommitSpillsAtDefinition(code(), assigned);
+    InstructionOperand* spill_operand = nullptr;
+    if (!range->TopLevel()->HasNoSpillType()) {
+      spill_operand = range->TopLevel()->GetSpillOperand();
+    }
+    range->ConvertUsesToOperand(assigned, spill_operand);
+    if (!range->IsChild() && spill_operand != nullptr) {
+      range->CommitSpillsAtDefinition(code(), spill_operand,
+                                      range->has_slot_use());
     }
   }
 }
 
 
 SpillRange* RegisterAllocator::AssignSpillRangeToLiveRange(LiveRange* range) {
   auto spill_range = new (local_zone()) SpillRange(range, local_zone());
   spill_ranges().push_back(spill_range);
   return spill_range;
 }
 
 
 bool RegisterAllocator::TryReuseSpillForPhi(LiveRange* range) {
   if (range->IsChild() || !range->is_phi()) return false;
-  DCHECK(range->HasNoSpillType());
+  DCHECK(!range->HasSpillOperand());
 
   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++) {
     int op = phi->operands()[i];
@@ skipping 42 matching lines @@
   }
 
   // If the range does not need register soon, spill it to the merged
   // spill range.
   auto next_pos = range->Start();
   if (code()->IsGapAt(next_pos.InstructionIndex())) {
     next_pos = next_pos.NextInstruction();
   }
   auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
   if (pos == nullptr) {
-    auto spill_range = AssignSpillRangeToLiveRange(range->TopLevel());
+    auto spill_range = range->TopLevel()->HasSpillRange()
+                           ? range->TopLevel()->GetSpillRange()
+                           : AssignSpillRangeToLiveRange(range->TopLevel());
     CHECK(first_op_spill->TryMerge(spill_range));
     Spill(range);
     return true;
   } else if (pos->pos().Value() > range->Start().NextInstruction().Value()) {
-    auto spill_range = AssignSpillRangeToLiveRange(range->TopLevel());
+    auto spill_range = range->TopLevel()->HasSpillRange()
+                           ? range->TopLevel()->GetSpillRange()
+                           : AssignSpillRangeToLiveRange(range->TopLevel());
     CHECK(first_op_spill->TryMerge(spill_range));
     SpillBetween(range, range->Start(), pos->pos());
     DCHECK(UnhandledIsSorted());
     return true;
   }
   return false;
 }
 
 
 void RegisterAllocator::MeetRegisterConstraints(const InstructionBlock* block) {
@@ skipping 238 matching lines @@
           if (from->IsUnallocated()) {
             live->Add(UnallocatedOperand::cast(from)->virtual_register());
           }
         }
       }
     } else {
       // Process output, inputs, and temps of this non-gap instruction.
       for (size_t i = 0; i < instr->OutputCount(); i++) {
         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 = output->index();
           live->Remove(out_vreg);
         }
         Define(curr_position, output, nullptr);
       }
 
       if (instr->ClobbersRegisters()) {
@@ skipping 20 matching lines @@
         auto input = instr->InputAt(i);
         if (input->IsImmediate()) continue;  // Ignore immediates.
         LifetimePosition use_pos;
         if (input->IsUnallocated() &&
             UnallocatedOperand::cast(input)->IsUsedAtStart()) {
           use_pos = curr_position;
         } else {
           use_pos = curr_position.InstructionEnd();
         }
 
+        if (input->IsUnallocated()) {
+          UnallocatedOperand* unalloc = UnallocatedOperand::cast(input);
+          int vreg = unalloc->virtual_register();
+          live->Add(vreg);
+          if (unalloc->HasSlotPolicy()) {
+            LiveRangeFor(vreg)->set_has_slot_use(true);
+          }
+        }
         Use(block_start_position, use_pos, input, nullptr);
-        if (input->IsUnallocated()) {
-          live->Add(UnallocatedOperand::cast(input)->virtual_register());
-        }
       }
 
       for (size_t i = 0; i < instr->TempCount(); i++) {
         auto temp = instr->TempAt(i);
+        // Unsupported.
+        DCHECK_IMPLIES(temp->IsUnallocated(),
+                       !UnallocatedOperand::cast(temp)->HasSlotPolicy());
         if (instr->ClobbersTemps()) {
           if (temp->IsRegister()) continue;
           if (temp->IsUnallocated()) {
             UnallocatedOperand* temp_unalloc = UnallocatedOperand::cast(temp);
             if (temp_unalloc->HasFixedPolicy()) {
               continue;
             }
           }
         }
         Use(block_start_position, curr_position.InstructionEnd(), temp,
@@ skipping 401 matching lines @@
       for (int i = block->rpo_number().ToInt() + 1;
            i < block->loop_end().ToInt(); ++i) {
         live_in_sets_[i]->Union(*live);
       }
     }
   }
 
   for (auto range : live_ranges()) {
     if (range == nullptr) continue;
     range->kind_ = RequiredRegisterKind(range->id());
+    // Give slots to all ranges with a non fixed slot use.
+    if (range->has_slot_use() && range->HasNoSpillType()) {
+      AssignSpillRangeToLiveRange(range);
+    }
     // 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->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?
+        if (pos->type() == UsePositionType::kRequiresSlot) continue;
+        UsePositionType new_type = UsePositionType::kAny;
         // Can't mark phis as needing a register.
         if (!code()
                  ->InstructionAt(pos->pos().InstructionIndex())
                  ->IsGapMoves()) {
-          pos->requires_reg_ = true;
+          new_type = UsePositionType::kRequiresRegister;
         }
+        pos->set_type(new_type, true);
       }
     }
   }
 }
 
 
 bool RegisterAllocator::ExistsUseWithoutDefinition() {
   bool found = false;
   BitVector::Iterator iterator(live_in_sets_[0]);
   while (!iterator.Done()) {
@@ skipping 728 matching lines @@
   } else {
     DCHECK(range->Kind() == GENERAL_REGISTERS);
     assigned_registers_->Add(reg);
   }
   range->set_assigned_register(reg, operand_cache());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8