[turbofan] use START and END gap positions for constraints

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 759 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::AddConstraintsGapMove(int index,
-                                              InstructionOperand* from,
-                                              InstructionOperand* to) {
+void RegisterAllocator::AddGapMove(int index,
+                                   GapInstruction::InnerPosition position,
+                                   InstructionOperand* from,
+                                   InstructionOperand* to) {
   auto gap = code()->GapAt(index);
-  auto move = gap->GetOrCreateParallelMove(GapInstruction::START, code_zone());
-  if (from->IsUnallocated()) {
-    const ZoneList<MoveOperands>* move_operands = move->move_operands();
-    for (int i = 0; i < move_operands->length(); ++i) {
-      auto cur = move_operands->at(i);
-      auto cur_to = cur.destination();
-      if (cur_to->IsUnallocated()) {
-        if (UnallocatedOperand::cast(cur_to)->virtual_register() ==
-            UnallocatedOperand::cast(from)->virtual_register()) {
-          move->AddMove(cur.source(), to, code_zone());
-          return;
-        }
-      }
-    }
-  }
+  auto move = gap->GetOrCreateParallelMove(position, code_zone());
   move->AddMove(from, to, code_zone());
 }
 
 
 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 284 matching lines @@
         DCHECK(successor->PredecessorCount() == 1);
         int gap_index = successor->first_instruction_index() + 1;
         DCHECK(code()->IsGapAt(gap_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 =
             new (code_zone()) UnallocatedOperand(UnallocatedOperand::ANY);
         output_copy->set_virtual_register(output_vreg);
 
-        code()->AddGapMove(gap_index, output, output_copy);
+        AddGapMove(gap_index, GapInstruction::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() + 1;
         range->SpillAtDefinition(local_zone(), gap_index, output);
         range->SetSpillStartIndex(gap_index);
@@ skipping 32 matching lines @@
           bool is_tagged = HasTaggedValue(first_output->virtual_register());
           AllocateFixed(first_output, gap_index, is_tagged);
 
           // This value is produced on the stack, we never need to spill it.
           if (first_output->IsStackSlot()) {
             DCHECK(first_output->index() < 0);
             range->SetSpillOperand(first_output);
             range->SetSpillStartIndex(gap_index - 1);
             assigned = true;
           }
-          code()->AddGapMove(gap_index, first_output, output_copy);
+          AddGapMove(gap_index, GapInstruction::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(), gap_index, first_output);
           range->SetSpillStartIndex(gap_index);
         }
       }
     }
   }
 
   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.
       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());
         AllocateFixed(cur_input, gap_index + 1, is_tagged);
-        AddConstraintsGapMove(gap_index, input_copy, cur_input);
+        AddGapMove(gap_index, GapInstruction::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()) {
         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());
         cur_input->set_virtual_register(second_output->virtual_register());
-        AddConstraintsGapMove(gap_index, input_copy, cur_input);
+        AddGapMove(gap_index, GapInstruction::END, input_copy, cur_input);
 
         if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) {
           int index = gap_index + 1;
           Instruction* instr = InstructionAt(index);
           if (instr->HasPointerMap()) {
             instr->pointer_map()->RecordPointer(input_copy, code_zone());
           }
         } 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
@@ skipping 34 matching lines @@
       LifetimePosition::FromInstructionIndex(block_start);
 
   for (int index = block->last_instruction_index(); index >= block_start;
        index--) {
     auto curr_position = LifetimePosition::FromInstructionIndex(index);
     auto instr = InstructionAt(index);
     DCHECK(instr != nullptr);
     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);
-        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();
+      const GapInstruction::InnerPosition kPositions[] = {
+          GapInstruction::END, GapInstruction::START};
+      for (auto position : kPositions) {
+        auto move = gap->GetParallelMove(position);
+        if (move == nullptr) continue;
+        if (position == GapInstruction::END) {
+          curr_position = curr_position.InstructionEnd();
+        } else {
+          curr_position = curr_position.InstructionStart();
+        }
+        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();
+            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();
+              }
+            } else {
+              if (live->Contains(to_vreg)) {
+                Define(curr_position, to, from);
+                live->Remove(to_vreg);
+              } else {
+                cur->Eliminate();
+                continue;
+              }
             }
           } else {
-            if (live->Contains(to_vreg)) {
-              Define(curr_position, to, from);
-              live->Remove(to_vreg);
-            } else {
-              cur->Eliminate();
-              continue;
-            }
+            Define(curr_position, to, from);
           }
-        } else {
-          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());
+          }
         }
       }
     } 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()) {
           int out_vreg = UnallocatedOperand::cast(output)->virtual_register();
           live->Remove(out_vreg);
         } else if (output->IsConstant()) {
@@ skipping 67 matching lines @@
           std::make_pair(phi->virtual_register(), PhiMapValue(phi, block)));
       DCHECK(res.second);
       USE(res);
     }
     auto output = phi->output();
     int phi_vreg = phi->virtual_register();
     if (!FLAG_turbo_delay_ssa_decon) {
       for (size_t i = 0; i < phi->operands().size(); ++i) {
         InstructionBlock* cur_block =
             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);
+        AddGapMove(cur_block->last_instruction_index() - 1, GapInstruction::END,
+                   phi->inputs()[i], output);
         DCHECK(!InstructionAt(cur_block->last_instruction_index())
                     ->HasPointerMap());
       }
     }
     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);
@@ skipping 255 matching lines @@
     }
   }
 }
 
 
 void RegisterAllocator::ResolveControlFlow(const InstructionBlock* block,
                                            InstructionOperand* cur_op,
                                            const InstructionBlock* pred,
                                            InstructionOperand* pred_op) {
   if (pred_op->Equals(cur_op)) return;
-  GapInstruction* gap = nullptr;
+  int gap_index;
+  GapInstruction::InnerPosition position;
   if (block->PredecessorCount() == 1) {
-    gap = code()->GapAt(block->first_instruction_index());
+    gap_index = block->first_instruction_index();
+    position = GapInstruction::START;
   } else {
     DCHECK(pred->SuccessorCount() == 1);
-    gap = GetLastGap(pred);
-    auto branch = InstructionAt(pred->last_instruction_index());
-    DCHECK(!branch->HasPointerMap());
-    USE(branch);
+    DCHECK(!InstructionAt(pred->last_instruction_index())->HasPointerMap());
+    gap_index = pred->last_instruction_index() - 1;
+    position = GapInstruction::END;
   }
-  gap->GetOrCreateParallelMove(GapInstruction::START, code_zone())
-      ->AddMove(pred_op, cur_op, code_zone());
+  AddGapMove(gap_index, position, pred_op, cur_op);
 }
 
 
 void RegisterAllocator::BuildLiveRanges() {
   // Process the blocks in reverse order.
   for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0;
        --block_id) {
     auto block =
         code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id));
     auto live = ComputeLiveOut(block);
     // Initially consider all live_out values live for the entire block. We
     // will shorten these intervals if necessary.
     AddInitialIntervals(block, live);
 
     // 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);
       if (!FLAG_turbo_delay_ssa_decon) {
         InstructionOperand* hint = nullptr;
         InstructionOperand* phi_operand = nullptr;
         auto gap =
             GetLastGap(code()->InstructionBlockAt(block->predecessors()[0]));
         auto move =
-            gap->GetOrCreateParallelMove(GapInstruction::START, code_zone());
+            gap->GetOrCreateParallelMove(GapInstruction::END, code_zone());
         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;
             break;
           }
         }
         DCHECK(hint != nullptr);
@@ skipping 844 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