[turbofan] cleanup ParallelMove

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 122 matching lines @@
       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) {
   DCHECK(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
-  // TODO(dcarney): stop aliasing hint operands.
-  ConvertUsesToOperand(GetAssignedOperand(), nullptr);
 }
 
 
 void LiveRange::MakeSpilled() {
   DCHECK(!IsSpilled());
   DCHECK(!TopLevel()->HasNoSpillType());
   spilled_ = true;
   assigned_register_ = kInvalidAssignment;
 }
 
@@ skipping 13 matching lines @@
   DCHECK(!IsChild());
   auto zone = sequence->zone();
   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;
-      auto move_ops = move->move_operands();
-      for (auto move_op = move_ops->begin(); move_op != move_ops->end();
-           ++move_op) {
+      for (auto move_op : *move) {
         if (move_op->IsEliminated()) continue;
-        if (move_op->source()->Equals(to_spill->operand) &&
-            move_op->destination()->Equals(op)) {
+        if (move_op->source() == *to_spill->operand &&
+            move_op->destination() == *op) {
           found = true;
           break;
         }
       }
       if (found) continue;
     }
-    move->AddMove(to_spill->operand, op, zone);
+    move->AddMove(*to_spill->operand, *op);
   }
 }
 
 
 void LiveRange::SetSpillOperand(InstructionOperand* operand) {
   DCHECK(HasNoSpillType());
   DCHECK(!operand->IsUnallocated() && !operand->IsImmediate());
   spill_type_ = SpillType::kSpillOperand;
   spill_operand_ = operand;
 }
@@ skipping 595 matching lines @@
   auto range = LiveRangeFor(operand);
   if (range == nullptr) return;
   if (operand->IsUnallocated()) {
     UnallocatedOperand* unalloc_operand = UnallocatedOperand::cast(operand);
     range->AddUsePosition(position, unalloc_operand, hint, local_zone());
   }
   range->AddUseInterval(block_start, position, local_zone());
 }
 
 
-void RegisterAllocator::AddGapMove(int index, Instruction::GapPosition position,
-                                   InstructionOperand* from,
-                                   InstructionOperand* to) {
+MoveOperands* RegisterAllocator::AddGapMove(int index,
+                                            Instruction::GapPosition position,
+                                            const InstructionOperand& from,
+                                            const InstructionOperand& to) {
   auto instr = code()->InstructionAt(index);
-  auto move = instr->GetOrCreateParallelMove(position, code_zone());
-  move->AddMove(from, to, code_zone());
+  auto moves = instr->GetOrCreateParallelMove(position, code_zone());
+  return moves->AddMove(from, to);
 }
 
 
 static bool AreUseIntervalsIntersecting(UseInterval* interval1,
                                         UseInterval* interval2) {
   while (interval1 != nullptr && interval2 != nullptr) {
     if (interval1->start().Value() < interval2->start().Value()) {
       if (interval1->end().Value() > interval2->start().Value()) {
         return true;
       }
@@ skipping 131 matching lines @@
 
 void RegisterAllocator::CommitAssignment() {
   for (auto range : live_ranges()) {
     if (range == nullptr || range->IsEmpty()) continue;
     InstructionOperand* spill_operand = nullptr;
     if (!range->TopLevel()->HasNoSpillType()) {
       spill_operand = range->TopLevel()->GetSpillOperand();
     }
     auto assigned = range->GetAssignedOperand();
     range->ConvertUsesToOperand(assigned, spill_operand);
+    if (range->is_phi()) AssignPhiInput(range, assigned);
     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->HasSpillOperand());
 
   auto lookup = phi_map_.find(range->id());
   DCHECK(lookup != phi_map_.end());
-  auto phi = lookup->second.phi;
-  auto block = lookup->second.block;
+  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];
     LiveRange* op_range = LiveRangeFor(op);
     if (op_range->GetSpillRange() == nullptr) continue;
     auto pred = code()->InstructionBlockAt(block->predecessors()[i]);
     auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
         pred->last_instruction_index());
@@ skipping 95 matching lines @@
         range->SetSpillStartIndex(end);
         assigned = true;
       }
 
       for (auto succ : block->successors()) {
         const InstructionBlock* successor = code()->InstructionBlockAt(succ);
         DCHECK(successor->PredecessorCount() == 1);
         int gap_index = successor->first_instruction_index();
         // Create an unconstrained operand for the same virtual register
         // and insert a gap move from the fixed output to the operand.
-        UnallocatedOperand* output_copy =
-            UnallocatedOperand(UnallocatedOperand::ANY, output_vreg)
-                .Copy(code_zone());
-        AddGapMove(gap_index, Instruction::START, output, output_copy);
+        UnallocatedOperand output_copy(UnallocatedOperand::ANY, output_vreg);
+        AddGapMove(gap_index, Instruction::START, *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();
         range->SpillAtDefinition(local_zone(), gap_index, output);
         range->SetSpillStartIndex(gap_index);
@@ skipping 17 matching lines @@
       int output_vreg = ConstantOperand::cast(output)->virtual_register();
       auto range = LiveRangeFor(output_vreg);
       range->SetSpillStartIndex(instr_index + 1);
       range->SetSpillOperand(output);
       continue;
     }
     auto first_output = UnallocatedOperand::cast(output);
     auto range = LiveRangeFor(first_output->virtual_register());
     bool assigned = false;
     if (first_output->HasFixedPolicy()) {
-      auto output_copy = first_output->CopyUnconstrained(code_zone());
-      bool is_tagged = HasTaggedValue(first_output->virtual_register());
+      int output_vreg = first_output->virtual_register();
+      UnallocatedOperand output_copy(UnallocatedOperand::ANY, output_vreg);
+      bool is_tagged = HasTaggedValue(output_vreg);
       AllocateFixed(first_output, instr_index, is_tagged);
 
       // This value is produced on the stack, we never need to spill it.
       if (first_output->IsStackSlot()) {
         DCHECK(StackSlotOperand::cast(first_output)->index() <
                frame_->GetSpillSlotCount());
         range->SetSpillOperand(StackSlotOperand::cast(first_output));
         range->SetSpillStartIndex(instr_index + 1);
         assigned = true;
       }
-      AddGapMove(instr_index + 1, Instruction::START, first_output,
+      AddGapMove(instr_index + 1, Instruction::START, *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(), instr_index + 1, first_output);
       range->SetSpillStartIndex(instr_index + 1);
     }
   }
 }
 
 
 void RegisterAllocator::MeetConstraintsBefore(int instr_index) {
   auto second = InstructionAt(instr_index);
   // 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.
     auto cur_input = UnallocatedOperand::cast(input);
     if (cur_input->HasFixedPolicy()) {
-      auto input_copy = cur_input->CopyUnconstrained(code_zone());
-      bool is_tagged = HasTaggedValue(cur_input->virtual_register());
+      int input_vreg = cur_input->virtual_register();
+      UnallocatedOperand input_copy(UnallocatedOperand::ANY, input_vreg);
+      bool is_tagged = HasTaggedValue(input_vreg);
       AllocateFixed(cur_input, instr_index, is_tagged);
-      AddGapMove(instr_index, Instruction::END, input_copy, cur_input);
+      AddGapMove(instr_index, Instruction::END, input_copy, *cur_input);
     }
   }
   // Handle "output same as input" for second instruction.
   for (size_t i = 0; i < second->OutputCount(); i++) {
     auto output = second->OutputAt(i);
     if (!output->IsUnallocated()) continue;
     auto second_output = UnallocatedOperand::cast(output);
     if (!second_output->HasSameAsInputPolicy()) continue;
     DCHECK(i == 0);  // Only valid for first output.
     UnallocatedOperand* cur_input =
         UnallocatedOperand::cast(second->InputAt(0));
     int output_vreg = second_output->virtual_register();
     int input_vreg = cur_input->virtual_register();
-    auto input_copy = cur_input->CopyUnconstrained(code_zone());
+    UnallocatedOperand input_copy(UnallocatedOperand::ANY, input_vreg);
     cur_input->set_virtual_register(second_output->virtual_register());
-    AddGapMove(instr_index, Instruction::END, input_copy, cur_input);
+    AddGapMove(instr_index, Instruction::END, input_copy, *cur_input);
     if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) {
       if (second->HasReferenceMap()) {
-        second->reference_map()->RecordReference(*input_copy);
+        second->reference_map()->RecordReference(input_copy);
       }
     } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) {
       // The input is assumed to immediately have a tagged representation,
       // before the pointer map can be used. I.e. the pointer map at the
       // instruction will include the output operand (whose value at the
       // beginning of the instruction is equal to the input operand). If
       // this is not desired, then the pointer map at this instruction needs
       // to be adjusted manually.
     }
   }
@@ skipping 116 matching lines @@
     curr_position = curr_position.PrevStart();
     DCHECK(curr_position.IsGapPosition());
     for (auto position : kPositions) {
       auto move = instr->GetParallelMove(position);
       if (move == nullptr) continue;
       if (position == Instruction::END) {
         curr_position = curr_position.End();
       } else {
         curr_position = curr_position.Start();
       }
-      auto move_ops = move->move_operands();
-      for (auto cur = move_ops->begin(); cur != move_ops->end(); ++cur) {
-        auto from = cur->source();
-        auto to = cur->destination();
-        auto hint = to;
-        if (to->IsUnallocated()) {
-          int to_vreg = UnallocatedOperand::cast(to)->virtual_register();
+      for (auto cur : *move) {
+        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()) {
             if (to_range->is_non_loop_phi()) {
               hint = to_range->current_hint_operand();
             }
           } else {
             if (live->Contains(to_vreg)) {
-              Define(curr_position, to, from);
+              Define(curr_position, &to, &from);
               live->Remove(to_vreg);
             } else {
               cur->Eliminate();
               continue;
             }
           }
         } else {
-          Define(curr_position, to, from);
+          Define(curr_position, &to, &from);
         }
-        Use(block_start_position, curr_position, from, hint);
-        if (from->IsUnallocated()) {
-          live->Add(UnallocatedOperand::cast(from)->virtual_register());
+        Use(block_start_position, curr_position, &from, hint);
+        if (from.IsUnallocated()) {
+          live->Add(UnallocatedOperand::cast(from).virtual_register());
         }
       }
     }
   }
 }
 
 
 void RegisterAllocator::ResolvePhis(const InstructionBlock* block) {
   for (auto phi : block->phis()) {
     int phi_vreg = phi->virtual_register();
-    auto res =
-        phi_map_.insert(std::make_pair(phi_vreg, PhiMapValue(phi, block)));
+    auto map_value = new (local_zone()) PhiMapValue(phi, block, local_zone());
+    auto res = phi_map_.insert(std::make_pair(phi_vreg, map_value));
     DCHECK(res.second);
     USE(res);
     auto& output = phi->output();
     for (size_t i = 0; i < phi->operands().size(); ++i) {
       InstructionBlock* cur_block =
           code()->InstructionBlockAt(block->predecessors()[i]);
-      AddGapMove(cur_block->last_instruction_index(), Instruction::END,
-                 &phi->inputs()[i], &output);
+      UnallocatedOperand input(UnallocatedOperand::ANY, phi->operands()[i]);
+      auto move = AddGapMove(cur_block->last_instruction_index(),
+                             Instruction::END, input, output);
+      map_value->incoming_moves.push_back(move);
       DCHECK(!InstructionAt(cur_block->last_instruction_index())
                   ->HasReferenceMap());
     }
     auto live_range = LiveRangeFor(phi_vreg);
     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::AssignPhiInput(LiveRange* range,
+                                       const InstructionOperand& assignment) {
+  DCHECK(range->is_phi());
+  auto it = phi_map_.find(range->id());
+  DCHECK(it != phi_map_.end());
+  for (auto move : it->second->incoming_moves) {
+    move->set_destination(assignment);
+  }
+}
+
+
 void RegisterAllocator::MeetRegisterConstraints() {
   for (auto block : code()->instruction_blocks()) {
     MeetRegisterConstraints(block);
   }
 }
 
 
 void RegisterAllocator::ResolvePhis() {
   // Process the blocks in reverse order.
   for (auto i = code()->instruction_blocks().rbegin();
        i != code()->instruction_blocks().rend(); ++i) {
     ResolvePhis(*i);
   }
 }
 
 
 const InstructionBlock* RegisterAllocator::GetInstructionBlock(
     LifetimePosition pos) {
   return code()->GetInstructionBlock(pos.ToInstructionIndex());
 }
 
 
 void RegisterAllocator::ConnectRanges() {
-  ZoneMap<std::pair<ParallelMove*, InstructionOperand*>, InstructionOperand*>
+  ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand>
       delayed_insertion_map(local_zone());
   for (auto first_range : live_ranges()) {
     if (first_range == nullptr || first_range->IsChild()) continue;
     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->IsSpilled()) continue;
       if (first_range->End().Value() != pos.Value()) continue;
       if (IsBlockBoundary(pos) &&
           !CanEagerlyResolveControlFlow(GetInstructionBlock(pos))) {
         continue;
       }
-      auto prev = first_range->GetAssignedOperand();
-      auto cur = second_range->GetAssignedOperand();
-      if (prev == cur) continue;
+      auto prev_operand = first_range->GetAssignedOperand();
+      auto cur_operand = second_range->GetAssignedOperand();
+      if (prev_operand == cur_operand) continue;
       bool delay_insertion = false;
       Instruction::GapPosition gap_pos;
       int gap_index = pos.ToInstructionIndex();
       if (pos.IsGapPosition()) {
         gap_pos = pos.IsStart() ? Instruction::START : Instruction::END;
       } else {
         if (pos.IsStart()) {
           delay_insertion = true;
         } else {
           gap_index++;
         }
         gap_pos = delay_insertion ? Instruction::END : Instruction::START;
       }
       auto move = code()->InstructionAt(gap_index)->GetOrCreateParallelMove(
           gap_pos, code_zone());
-      auto prev_operand = InstructionOperand::New(code_zone(), prev);
-      auto cur_operand = InstructionOperand::New(code_zone(), cur);
       if (!delay_insertion) {
-        move->AddMove(prev_operand, cur_operand, code_zone());
+        move->AddMove(prev_operand, cur_operand);
       } else {
         delayed_insertion_map.insert(
             std::make_pair(std::make_pair(move, prev_operand), cur_operand));
       }
     }
   }
   if (delayed_insertion_map.empty()) return;
   // Insert all the moves which should occur after the stored move.
-  ZoneVector<MoveOperands> to_insert(local_zone());
+  ZoneVector<MoveOperands*> to_insert(local_zone());
   ZoneVector<MoveOperands*> to_eliminate(local_zone());
   to_insert.reserve(4);
   to_eliminate.reserve(4);
-  auto move = delayed_insertion_map.begin()->first.first;
+  auto moves = delayed_insertion_map.begin()->first.first;
   for (auto it = delayed_insertion_map.begin();; ++it) {
     bool done = it == delayed_insertion_map.end();
-    if (done || it->first.first != move) {
+    if (done || it->first.first != moves) {
       // Commit the MoveOperands for current ParallelMove.
-      for (auto move_ops : to_eliminate) {
-        move_ops->Eliminate();
+      for (auto move : to_eliminate) {
+        move->Eliminate();
       }
-      for (auto move_ops : to_insert) {
-        move->AddMove(move_ops.source(), move_ops.destination(), code_zone());
+      for (auto move : to_insert) {
+        moves->push_back(move);
       }
       if (done) break;
       // Reset state.
       to_eliminate.clear();
       to_insert.clear();
-      move = it->first.first;
+      moves = it->first.first;
     }
     // Gather all MoveOperands for a single ParallelMove.
-    MoveOperands move_ops(it->first.second, it->second);
-    auto eliminate = move->PrepareInsertAfter(&move_ops);
-    to_insert.push_back(move_ops);
+    auto move = new (code_zone()) MoveOperands(it->first.second, it->second);
+    auto eliminate = moves->PrepareInsertAfter(move);
+    to_insert.push_back(move);
     if (eliminate != nullptr) to_eliminate.push_back(eliminate);
   }
 }
 
 
 bool RegisterAllocator::CanEagerlyResolveControlFlow(
     const InstructionBlock* block) const {
   if (block->PredecessorCount() != 1) return false;
   return block->predecessors()[0].IsNext(block->rpo_number());
 }
@@ skipping 145 matching lines @@
       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_->IsSpilled())
           continue;
         auto pred_op = result.pred_cover_->GetAssignedOperand();
         auto cur_op = result.cur_cover_->GetAssignedOperand();
         if (pred_op == cur_op) continue;
-        auto pred_ptr = InstructionOperand::New(code_zone(), pred_op);
-        auto cur_ptr = InstructionOperand::New(code_zone(), cur_op);
-        ResolveControlFlow(block, cur_ptr, pred_block, pred_ptr);
+        ResolveControlFlow(block, cur_op, pred_block, pred_op);
       }
       iterator.Advance();
     }
   }
 }
 
 
 void RegisterAllocator::ResolveControlFlow(const InstructionBlock* block,
-                                           InstructionOperand* cur_op,
+                                           const InstructionOperand& cur_op,
                                            const InstructionBlock* pred,
-                                           InstructionOperand* pred_op) {
-  DCHECK(!pred_op->Equals(cur_op));
+                                           const InstructionOperand& pred_op) {
+  DCHECK(pred_op != cur_op);
   int gap_index;
   Instruction::GapPosition position;
   if (block->PredecessorCount() == 1) {
     gap_index = block->first_instruction_index();
     position = Instruction::START;
   } else {
     DCHECK(pred->SuccessorCount() == 1);
     DCHECK(!InstructionAt(pred->last_instruction_index())->HasReferenceMap());
     gap_index = pred->last_instruction_index();
     position = Instruction::END;
@@ skipping 15 matching lines @@
     // Process the instructions in reverse order, generating and killing
     // live values.
     ProcessInstructions(block, live);
     // All phi output operands are killed by this block.
     for (auto phi : block->phis()) {
       // The live range interval already ends at the first instruction of the
       // block.
       int phi_vreg = phi->virtual_register();
       live->Remove(phi_vreg);
       InstructionOperand* hint = nullptr;
-      InstructionOperand* phi_operand = nullptr;
       auto instr = GetLastInstruction(
           code()->InstructionBlockAt(block->predecessors()[0]));
-      auto move = instr->GetParallelMove(Instruction::END);
-      for (int j = 0; j < move->move_operands()->length(); ++j) {
-        auto to = move->move_operands()->at(j).destination();
-        if (to->IsUnallocated() &&
-            UnallocatedOperand::cast(to)->virtual_register() == phi_vreg) {
-          hint = move->move_operands()->at(j).source();
-          phi_operand = to;
+      for (auto move : *instr->GetParallelMove(Instruction::END)) {
+        auto& to = move->destination();
+        if (to.IsUnallocated() &&
+            UnallocatedOperand::cast(to).virtual_register() == phi_vreg) {
+          hint = &move->source();
           break;
         }
       }
       DCHECK(hint != nullptr);
       auto block_start = LifetimePosition::GapFromInstructionIndex(
           block->first_instruction_index());
-      Define(block_start, phi_operand, hint);
+      Define(block_start, &phi->output(), hint);
     }
 
     // Now live is live_in for this block except not including values live
     // out on backward successor edges.
     live_in_sets_[block_id] = live;
 
     if (block->IsLoopHeader()) {
       // Add a live range stretching from the first loop instruction to the last
       // for each value live on entry to the header.
       BitVector::Iterator iterator(live);
@@ skipping 770 matching lines @@
 
 void RegisterAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
                                                      int reg) {
   if (range->Kind() == DOUBLE_REGISTERS) {
     assigned_double_registers_->Add(reg);
   } else {
     DCHECK(range->Kind() == GENERAL_REGISTERS);
     assigned_registers_->Add(reg);
   }
   range->set_assigned_register(reg);
+  auto assignment = range->GetAssignedOperand();
+  // TODO(dcarney): stop aliasing hint operands.
+  range->ConvertUsesToOperand(assignment, nullptr);
+  if (range->is_phi()) AssignPhiInput(range, assignment);
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8