[turbofan]: delay ssa deconstruction in 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 82 matching lines @@
   return false;
 }
 
 
 #endif
 
 
 LiveRange::LiveRange(int id, Zone* zone)
     : id_(id),
       spilled_(false),
-      is_phi_(false),
-      is_non_loop_phi_(false),
       kind_(UNALLOCATED_REGISTERS),
       assigned_register_(kInvalidAssignment),
       last_interval_(NULL),
       first_interval_(NULL),
       first_pos_(NULL),
       parent_(NULL),
       next_(NULL),
       current_interval_(NULL),
       last_processed_use_(NULL),
       current_hint_operand_(NULL),
@@ skipping 868 matching lines @@
           gap->GetOrCreateParallelMove(GapInstruction::START, code_zone());
       const ZoneList<MoveOperands>* move_operands = move->move_operands();
       for (int i = 0; i < move_operands->length(); ++i) {
         MoveOperands* cur = &move_operands->at(i);
         if (cur->IsIgnored()) continue;
         InstructionOperand* from = cur->source();
         InstructionOperand* to = cur->destination();
         InstructionOperand* hint = to;
         if (to->IsUnallocated()) {
           int to_vreg = UnallocatedOperand::cast(to)->virtual_register();
-          LiveRange* to_range = LiveRangeFor(to_vreg);
-          if (to_range->is_phi()) {
-            if (to_range->is_non_loop_phi()) {
-              hint = to_range->current_hint_operand();
-            }
+          if (live->Contains(to_vreg)) {
+            Define(curr_position, to, from);
+            live->Remove(to_vreg);
           } else {
-            if (live->Contains(to_vreg)) {
-              Define(curr_position, to, from);
-              live->Remove(to_vreg);
-            } else {
-              cur->Eliminate();
-              continue;
-            }
+            cur->Eliminate();
+            continue;
           }
         } else {
           Define(curr_position, to, from);
         }
         Use(block_start_position, curr_position, from, hint);
         if (from->IsUnallocated()) {
           live->Add(UnallocatedOperand::cast(from)->virtual_register());
         }
       }
     } else {
@@ skipping 59 matching lines @@
           }
         }
         Use(block_start_position, curr_position.InstructionEnd(), temp, NULL);
         Define(curr_position, temp, NULL);
       }
     }
   }
 }
 
 
-void RegisterAllocator::ResolvePhis(const InstructionBlock* block) {
+void RegisterAllocator::ProcessPhis(const InstructionBlock* block) {
   for (auto phi : block->phis()) {
-    UnallocatedOperand* phi_operand =
-        new (code_zone()) UnallocatedOperand(UnallocatedOperand::NONE);
+    auto output = phi->output();
     int phi_vreg = phi->virtual_register();
-    phi_operand->set_virtual_register(phi_vreg);
-
-    for (size_t i = 0; i < phi->operands().size(); ++i) {
-      UnallocatedOperand* operand =
-          new (code_zone()) UnallocatedOperand(UnallocatedOperand::ANY);
-      operand->set_virtual_register(phi->operands()[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, operand,
-                         phi_operand);
-
-      Instruction* branch = InstructionAt(cur_block->last_instruction_index());
-      DCHECK(!branch->HasPointerMap());
-      USE(branch);
-    }
-
     LiveRange* live_range = LiveRangeFor(phi_vreg);
     BlockStartInstruction* block_start =
         code()->GetBlockStart(block->rpo_number());
-    block_start->GetOrCreateParallelMove(GapInstruction::START, code_zone())
-        ->AddMove(phi_operand, live_range->GetSpillOperand(), code_zone());
+    block_start->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone())
+        ->AddMove(output, live_range->GetSpillOperand(), code_zone());
     live_range->SetSpillStartIndex(block->first_instruction_index());
-
-    // We use the phi-ness of some nodes in some later heuristics.
-    live_range->set_is_phi(true);
-    if (!block->IsLoopHeader()) {
-      live_range->set_is_non_loop_phi(true);
-    }
   }
 }
 
 
 void RegisterAllocator::MeetRegisterConstraints() {
   for (auto block : code()->instruction_blocks()) {
+    ProcessPhis(block);
     MeetRegisterConstraints(block);
-    if (!AllocationOk()) return;
   }
 }
 
-
-void RegisterAllocator::ResolvePhis() {
-  // Process the blocks in reverse order.
-  for (auto i = code()->instruction_blocks().rbegin();
-       i != code()->instruction_blocks().rend(); ++i) {
-    ResolvePhis(*i);
-  }
-}
-
 
 ParallelMove* RegisterAllocator::GetConnectingParallelMove(
     LifetimePosition pos) {
   int index = pos.InstructionIndex();
   if (code()->IsGapAt(index)) {
     GapInstruction* gap = code()->GapAt(index);
     return gap->GetOrCreateParallelMove(
         pos.IsInstructionStart() ? GapInstruction::START : GapInstruction::END,
         code_zone());
   }
@@ skipping 109 matching lines @@
       if (bound->start_.Value() <= position.Value()) {
         if (position.Value() < bound->end_.Value()) return bound;
         DCHECK(left_index < current_index);
         left_index = current_index;
       } else {
         right_index = current_index;
       }
     }
   }
 
+  LiveRangeBound* FindPred(const InstructionBlock* pred) {
+    const LifetimePosition pred_end =
+        LifetimePosition::FromInstructionIndex(pred->last_instruction_index());
+    return Find(pred_end);
+  }
+
+  LiveRangeBound* FindSucc(const InstructionBlock* succ) {
+    const LifetimePosition succ_start =
+        LifetimePosition::FromInstructionIndex(succ->first_instruction_index());
+    return Find(succ_start);
+  }
+
   void Find(const InstructionBlock* block, const InstructionBlock* pred,
             FindResult* result) const {
     const LifetimePosition pred_end =
         LifetimePosition::FromInstructionIndex(pred->last_instruction_index());
     LiveRangeBound* bound = Find(pred_end);
     result->pred_cover_ = bound->range_;
     const LifetimePosition cur_start = LifetimePosition::FromInstructionIndex(
         block->first_instruction_index());
     // Common case.
     if (bound->CanCover(cur_start)) {
@@ skipping 44 matching lines @@
 };
 
 }  // namespace
 
 
 void RegisterAllocator::ResolveControlFlow() {
   // Lazily linearize live ranges in memory for fast lookup.
   LiveRangeFinder finder(*this);
   for (auto block : code()->instruction_blocks()) {
     if (CanEagerlyResolveControlFlow(block)) continue;
+    // resolve phis
+    for (auto phi : block->phis()) {
+      auto* block_bound =
+          finder.ArrayFor(phi->virtual_register())->FindSucc(block);
+      auto phi_output = block_bound->range_->CreateAssignedOperand(code_zone());
+      phi->output()->ConvertTo(phi_output->kind(), phi_output->index());
+      size_t pred_index = 0;
+      for (auto pred : block->predecessors()) {
+        const InstructionBlock* pred_block = code()->InstructionBlockAt(pred);
+        auto* pred_bound =
+            finder.ArrayFor(phi->operands()[pred_index])->FindPred(pred_block);
+        auto pred_op = pred_bound->range_->CreateAssignedOperand(code_zone());
+        phi->inputs()[pred_index] = pred_op;
+        ResolveControlFlow(block, phi_output, pred_block, pred_op);
+        pred_index++;
+      }
+    }
     BitVector* live = live_in_sets_[block->rpo_number().ToInt()];
     BitVector::Iterator iterator(live);
     while (!iterator.Done()) {
-      LiveRangeBoundArray* array = finder.ArrayFor(iterator.Current());
+      auto* array = finder.ArrayFor(iterator.Current());
       for (auto pred : block->predecessors()) {
         FindResult result;
-        const InstructionBlock* pred_block = code()->InstructionBlockAt(pred);
+        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;
-        ResolveControlFlow(block, result.cur_cover_, pred_block,
-                           result.pred_cover_);
+        InstructionOperand* pred_op =
+            result.pred_cover_->CreateAssignedOperand(code_zone());
+        InstructionOperand* cur_op =
+            result.cur_cover_->CreateAssignedOperand(code_zone());
+        ResolveControlFlow(block, cur_op, pred_block, pred_op);
       }
       iterator.Advance();
     }
   }
 }
 
 
 void RegisterAllocator::ResolveControlFlow(const InstructionBlock* block,
-                                           const LiveRange* cur_cover,
+                                           InstructionOperand* cur_op,
                                            const InstructionBlock* pred,
-                                           const LiveRange* pred_cover) {
-  InstructionOperand* pred_op = pred_cover->CreateAssignedOperand(code_zone());
-  InstructionOperand* cur_op = cur_cover->CreateAssignedOperand(code_zone());
-  if (!pred_op->Equals(cur_op)) {
-    GapInstruction* gap = NULL;
-    if (block->PredecessorCount() == 1) {
-      gap = code()->GapAt(block->first_instruction_index());
-    } else {
-      DCHECK(pred->SuccessorCount() == 1);
-      gap = GetLastGap(pred);
+                                           InstructionOperand* pred_op) {
+  if (pred_op->Equals(cur_op)) return;
+  GapInstruction* gap = nullptr;
+  if (block->PredecessorCount() == 1) {
+    gap = code()->GapAt(block->first_instruction_index());
+  } else {
+    DCHECK(pred->SuccessorCount() == 1);
+    gap = GetLastGap(pred);
 
-      Instruction* branch = InstructionAt(pred->last_instruction_index());
-      DCHECK(!branch->HasPointerMap());
-      USE(branch);
-    }
-    gap->GetOrCreateParallelMove(GapInstruction::START, code_zone())
-        ->AddMove(pred_op, cur_op, code_zone());
+    Instruction* branch = InstructionAt(pred->last_instruction_index());
+    DCHECK(!branch->HasPointerMap());
+    USE(branch);
   }
+  gap->GetOrCreateParallelMove(GapInstruction::START, code_zone())
+      ->AddMove(pred_op, cur_op, code_zone());
 }
 
 
 void RegisterAllocator::BuildLiveRanges() {
   InitializeLivenessAnalysis();
   // Process the blocks in reverse order.
   for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0;
        --block_id) {
     const InstructionBlock* block =
         code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id));
     BitVector* 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);
-
-      InstructionOperand* hint = NULL;
-      InstructionOperand* phi_operand = NULL;
-      GapInstruction* gap =
-          GetLastGap(code()->InstructionBlockAt(block->predecessors()[0]));
-
-      // TODO(titzer): no need to create the parallel move if it doesn't exit.
-      ParallelMove* move =
-          gap->GetOrCreateParallelMove(GapInstruction::START, code_zone());
-      for (int j = 0; j < move->move_operands()->length(); ++j) {
-        InstructionOperand* 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 != NULL);
-
-      LifetimePosition block_start = LifetimePosition::FromInstructionIndex(
-          block->first_instruction_index());
-      Define(block_start, phi_operand, 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 24 matching lines @@
       // 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.
       LiveRange* range = live_ranges_[i];
       if (range->HasAllocatedSpillOperand() &&
           range->GetSpillOperand()->IsConstant()) {
         for (UsePosition* pos = range->first_pos(); pos != NULL;
              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;
-          }
+          pos->requires_reg_ = true;
         }
       }
     }
   }
 }
 
 
 bool RegisterAllocator::ExistsUseWithoutDefinition() {
   bool found = false;
   BitVector::Iterator iterator(live_in_sets_[0]);
@@ skipping 794 matching lines @@
   } else {
     DCHECK(range->Kind() == GENERAL_REGISTERS);
     assigned_registers_->Add(reg);
   }
   range->set_assigned_register(reg, code_zone());
 }
 
 }
 }
 }  // namespace v8::internal::compiler