[turbofan] remove hint aliasing

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/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 47 matching lines @@
          code->GetInstructionBlock(pos.ToInstructionIndex())->code_start() ==
              pos.ToInstructionIndex();
 }
 
 
 Instruction* GetLastInstruction(InstructionSequence* code,
                                 const InstructionBlock* block) {
   return code->InstructionAt(block->last_instruction_index());
 }
 
+
+bool IsOutputRegisterOf(Instruction* instr, int index) {
+  for (size_t i = 0; i < instr->OutputCount(); i++) {
+    auto output = instr->OutputAt(i);
+    if (output->IsRegister() &&
+        RegisterOperand::cast(output)->index() == index) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
+bool IsOutputDoubleRegisterOf(Instruction* instr, int index) {
+  for (size_t i = 0; i < instr->OutputCount(); i++) {
+    auto output = instr->OutputAt(i);
+    if (output->IsDoubleRegister() &&
+        DoubleRegisterOperand::cast(output)->index() == index) {
+      return true;
+    }
+  }
+  return false;
+}
+
 }  // namespace
 
 
 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand,
-                         InstructionOperand* hint)
-    : operand_(operand), hint_(hint), pos_(pos), next_(nullptr), flags_(0) {
+                         void* hint, UsePositionHintType hint_type)
+    : operand_(operand), hint_(hint), next_(nullptr), pos_(pos), flags_(0) {
+  DCHECK_IMPLIES(hint == nullptr, hint_type == UsePositionHintType::kNone);
   bool register_beneficial = true;
   UsePositionType type = UsePositionType::kAny;
   if (operand_ != nullptr && operand_->IsUnallocated()) {
     const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_);
     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);
+  flags_ = TypeField::encode(type) | HintTypeField::encode(hint_type) |
+           RegisterBeneficialField::encode(register_beneficial) |
+           AssignedRegisterField::encode(kUnassignedRegister);
   DCHECK(pos_.IsValid());
 }
 
 
 bool UsePosition::HasHint() const {
-  return hint_ != nullptr && !hint_->IsUnallocated();
+  int hint_register;
+  return HintRegister(&hint_register);
 }
 
 
+bool UsePosition::HintRegister(int* register_index) const {
+  if (hint_ == nullptr) return false;
+  switch (HintTypeField::decode(flags_)) {
+    case UsePositionHintType::kNone:
+    case UsePositionHintType::kUnresolved:
+      return false;
+    case UsePositionHintType::kUsePos: {
+      auto use_pos = reinterpret_cast<UsePosition*>(hint_);
+      int assigned_register = AssignedRegisterField::decode(use_pos->flags_);
+      if (assigned_register == kUnassignedRegister) return false;
+      *register_index = assigned_register;
+      return true;
+    }
+    case UsePositionHintType::kOperand: {
+      auto operand = reinterpret_cast<InstructionOperand*>(hint_);
+      int assigned_register = AllocatedOperand::cast(operand)->index();
+      *register_index = assigned_register;
+      return true;
+    }
+    case UsePositionHintType::kPhi: {
+      auto phi = reinterpret_cast<RegisterAllocationData::PhiMapValue*>(hint_);
+      int assigned_register = phi->assigned_register();
+      if (assigned_register == kUnassignedRegister) return false;
+      *register_index = assigned_register;
+      return true;
+    }
+  }
+  UNREACHABLE();
+  return false;
+}
+
+
+UsePositionHintType UsePosition::HintTypeForOperand(
+    const InstructionOperand& op) {
+  switch (op.kind()) {
+    case InstructionOperand::CONSTANT:
+    case InstructionOperand::IMMEDIATE:
+      return UsePositionHintType::kNone;
+    case InstructionOperand::UNALLOCATED:
+      return UsePositionHintType::kUnresolved;
+    case InstructionOperand::ALLOCATED:
+      switch (AllocatedOperand::cast(op).allocated_kind()) {
+        case AllocatedOperand::REGISTER:
+        case AllocatedOperand::DOUBLE_REGISTER:
+          return UsePositionHintType::kOperand;
+        case AllocatedOperand::STACK_SLOT:
+        case AllocatedOperand::DOUBLE_STACK_SLOT:
+          return UsePositionHintType::kNone;
+      }
+    case InstructionOperand::INVALID:
+      break;
+  }
+  UNREACHABLE();
+  return UsePositionHintType::kNone;
+}
+
+
+void UsePosition::ResolveHint(UsePosition* use_pos) {
+  DCHECK_NOT_NULL(use_pos);
+  if (HintTypeField::decode(flags_) != UsePositionHintType::kUnresolved) return;
+  hint_ = use_pos;
+  flags_ = HintTypeField::update(flags_, UsePositionHintType::kUsePos);
+}
+
+
 void UsePosition::set_type(UsePositionType type, bool register_beneficial) {
   DCHECK_IMPLIES(type == UsePositionType::kRequiresSlot, !register_beneficial);
   flags_ = TypeField::encode(type) |
            RegisterBeneficialField::encode(register_beneficial);
 }
 
 
 UseInterval* UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
   DCHECK(Contains(pos) && pos != start());
   auto after = new (zone) UseInterval(pos, end_);
@@ skipping 14 matching lines @@
 };
 
 
 LiveRange::LiveRange(int id)
     : id_(id),
       spilled_(false),
       has_slot_use_(false),
       is_phi_(false),
       is_non_loop_phi_(false),
       kind_(UNALLOCATED_REGISTERS),
-      assigned_register_(kInvalidAssignment),
+      assigned_register_(kUnassignedRegister),
       last_interval_(nullptr),
       first_interval_(nullptr),
       first_pos_(nullptr),
       parent_(nullptr),
       next_(nullptr),
       current_interval_(nullptr),
       last_processed_use_(nullptr),
-      current_hint_operand_(nullptr),
+      current_hint_position_(nullptr),
       spill_start_index_(kMaxInt),
       spill_type_(SpillType::kNoSpillType),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr) {}
 
 
 void LiveRange::Verify() const {
   // Walk the positions, verifying that each is in an interval.
   auto interval = first_interval_;
   for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
     CHECK(Start() <= pos->pos());
     CHECK(pos->pos() <= End());
     CHECK(interval != nullptr);
     while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) {
       interval = interval->next();
       CHECK(interval != nullptr);
     }
   }
 }
 
 
 void LiveRange::set_assigned_register(int reg) {
   DCHECK(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
 }
 
 
+void LiveRange::UnsetAssignedRegister() {
+  DCHECK(HasRegisterAssigned() && !IsSpilled());
+  assigned_register_ = kUnassignedRegister;
+}
+
+
 void LiveRange::MakeSpilled() {
   DCHECK(!IsSpilled());
   DCHECK(!TopLevel()->HasNoSpillType());
   spilled_ = true;
-  assigned_register_ = kInvalidAssignment;
+  assigned_register_ = kUnassignedRegister;
 }
 
 
 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
                                   InstructionOperand* operand) {
   DCHECK(HasNoSpillType());
   spills_at_definition_ = new (zone)
       SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
 }
 
@@ skipping 20 matching lines @@
           break;
         }
       }
       if (found) continue;
     }
     move->AddMove(*to_spill->operand, *op);
   }
 }
 
 
+UsePosition* LiveRange::FirstHintPosition(int* register_index) const {
+  for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
+    if (pos->HintRegister(register_index)) return pos;
+  }
+  return nullptr;
+}
+
+
 void LiveRange::SetSpillOperand(InstructionOperand* operand) {
   DCHECK(HasNoSpillType());
   DCHECK(!operand->IsUnallocated() && !operand->IsImmediate());
   spill_type_ = SpillType::kSpillOperand;
   spill_operand_ = operand;
 }
 
 
 void LiveRange::SetSpillRange(SpillRange* spill_range) {
   DCHECK(HasNoSpillType() || HasSpillRange());
@@ skipping 264 matching lines @@
       // that each new use interval either precedes or intersects with
       // last added interval.
       DCHECK(start < first_interval_->end());
       first_interval_->set_start(Min(start, first_interval_->start()));
       first_interval_->set_end(Max(end, first_interval_->end()));
     }
   }
 }
 
 
-void LiveRange::AddUsePosition(LifetimePosition pos,
-                               InstructionOperand* operand,
-                               InstructionOperand* hint, Zone* zone) {
+void LiveRange::AddUsePosition(UsePosition* use_pos) {
+  auto pos = use_pos->pos();
   TRACE("Add to live range %d use position %d\n", id_, pos.value());
-  auto use_pos = new (zone) UsePosition(pos, operand, hint);
   UsePosition* prev_hint = nullptr;
   UsePosition* prev = nullptr;
   auto current = first_pos_;
   while (current != nullptr && current->pos() < pos) {
     prev_hint = current->HasHint() ? current : prev_hint;
     prev = current;
     current = current->next();
   }
 
   if (prev == nullptr) {
     use_pos->set_next(first_pos_);
     first_pos_ = use_pos;
   } else {
     use_pos->set_next(prev->next());
     prev->set_next(use_pos);
   }
 
   if (prev_hint == nullptr && use_pos->HasHint()) {
-    current_hint_operand_ = hint;
+    current_hint_position_ = use_pos;
   }
 }
 
 
 void LiveRange::ConvertUsesToOperand(const InstructionOperand& op,
                                      InstructionOperand* spill_op) {
   for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
     DCHECK(Start() <= pos->pos() && pos->pos() <= End());
-    if (!pos->HasOperand()) {
-      continue;
-    }
+    if (!pos->HasOperand()) continue;
     switch (pos->type()) {
       case UsePositionType::kRequiresSlot:
         if (spill_op != nullptr) {
           InstructionOperand::ReplaceWith(pos->operand(), spill_op);
         }
         break;
       case UsePositionType::kRequiresRegister:
         DCHECK(op.IsRegister() || op.IsDoubleRegister());
       // Fall through.
       case UsePositionType::kAny:
         InstructionOperand::ReplaceWith(pos->operand(), &op);
         break;
     }
   }
 }
 
 
+void LiveRange::SetUseHints(int register_index) {
+  for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
+    if (!pos->HasOperand()) continue;
+    switch (pos->type()) {
+      case UsePositionType::kRequiresSlot:
+        break;
+      case UsePositionType::kRequiresRegister:
+      case UsePositionType::kAny:
+        pos->set_assigned_register(register_index);
+        break;
+    }
+  }
+}
+
+
 bool LiveRange::CanCover(LifetimePosition position) const {
   if (IsEmpty()) return false;
   return Start() <= position && position < End();
 }
 
 
 bool LiveRange::Covers(LifetimePosition position) const {
   if (!CanCover(position)) return false;
   auto start_search = FirstSearchIntervalForPosition(position);
   for (auto interval = start_search; interval != nullptr;
@@ skipping 136 matching lines @@
     } else {
       tail->set_next(current);
     }
     tail = current;
     current = current->next();
   }
   // Other list is empty => we are done
 }
 
 
+RegisterAllocationData::PhiMapValue::PhiMapValue(PhiInstruction* phi,
+                                                 const InstructionBlock* block,
+                                                 Zone* zone)
+    : phi_(phi),
+      block_(block),
+      incoming_operands_(zone),
+      assigned_register_(kUnassignedRegister) {
+  incoming_operands_.reserve(phi->operands().size());
+}
+
+
+void RegisterAllocationData::PhiMapValue::AddOperand(
+    InstructionOperand* operand) {
+  incoming_operands_.push_back(operand);
+}
+
+
+void RegisterAllocationData::PhiMapValue::CommitAssignment(
+    const InstructionOperand& assigned) {
+  for (auto operand : incoming_operands_) {
+    InstructionOperand::ReplaceWith(operand, &assigned);
+  }
+}
+
+
 RegisterAllocationData::RegisterAllocationData(
     const RegisterConfiguration* config, Zone* zone, Frame* frame,
     InstructionSequence* code, const char* debug_name)
     : allocation_zone_(zone),
       frame_(frame),
       code_(code),
       debug_name_(debug_name),
       config_(config),
       phi_map_(allocation_zone()),
       live_in_sets_(code->InstructionBlockCount(), nullptr, allocation_zone()),
@@ skipping 35 matching lines @@
 
 MoveOperands* RegisterAllocationData::AddGapMove(
     int index, Instruction::GapPosition position,
     const InstructionOperand& from, const InstructionOperand& to) {
   auto instr = code()->InstructionAt(index);
   auto moves = instr->GetOrCreateParallelMove(position, code_zone());
   return moves->AddMove(from, to);
 }
 
 
-void RegisterAllocationData::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);
-  }
-}
-
-
 LiveRange* RegisterAllocationData::NewLiveRange(int index) {
   return new (allocation_zone()) LiveRange(index);
 }
 
 
+RegisterAllocationData::PhiMapValue* RegisterAllocationData::InitializePhiMap(
+    const InstructionBlock* block, PhiInstruction* phi) {
+  auto map_value = new (allocation_zone())
+      RegisterAllocationData::PhiMapValue(phi, block, allocation_zone());
+  auto res =
+      phi_map_.insert(std::make_pair(phi->virtual_register(), map_value));
+  DCHECK(res.second);
+  USE(res);
+  return map_value;
+}
+
+
+RegisterAllocationData::PhiMapValue* RegisterAllocationData::GetPhiMapValueFor(
+    int virtual_register) {
+  auto it = phi_map_.find(virtual_register);
+  DCHECK(it != phi_map_.end());
+  return it->second;
+}
+
+
 bool RegisterAllocationData::ExistsUseWithoutDefinition() {
   bool found = false;
   BitVector::Iterator iterator(live_in_sets()[0]);
   while (!iterator.Done()) {
     found = true;
     int operand_index = iterator.Current();
     PrintF("Register allocator error: live v%d reached first block.\n",
            operand_index);
     LiveRange* range = LiveRangeFor(operand_index);
     PrintF("  (first use is at %d)\n", range->first_pos()->pos().value());
@@ skipping 10 matching lines @@
 
 SpillRange* RegisterAllocationData::AssignSpillRangeToLiveRange(
     LiveRange* range) {
   auto spill_range =
       new (allocation_zone()) SpillRange(range, allocation_zone());
   spill_ranges().push_back(spill_range);
   return spill_range;
 }
 
 
-void RegisterAllocationData::SetLiveRangeAssignedRegister(LiveRange* range,
-                                                          int reg) {
-  if (range->Kind() == DOUBLE_REGISTERS) {
-    assigned_double_registers_->Add(reg);
+void RegisterAllocationData::MarkAllocated(RegisterKind kind, int index) {
+  if (kind == DOUBLE_REGISTERS) {
+    assigned_double_registers_->Add(index);
   } else {
-    DCHECK(range->Kind() == GENERAL_REGISTERS);
-    assigned_registers_->Add(reg);
+    DCHECK(kind == GENERAL_REGISTERS);
+    assigned_registers_->Add(index);
   }
-  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);
 }
 
 
 ConstraintBuilder::ConstraintBuilder(RegisterAllocationData* data)
     : data_(data) {}
 
 
 InstructionOperand* ConstraintBuilder::AllocateFixed(
     UnallocatedOperand* operand, int pos, bool is_tagged) {
   TRACE("Allocating fixed reg for op %d\n", operand->virtual_register());
@@ skipping 186 matching lines @@
   // Process the blocks in reverse order.
   for (InstructionBlock* block : base::Reversed(code()->instruction_blocks())) {
     ResolvePhis(block);
   }
 }
 
 
 void ConstraintBuilder::ResolvePhis(const InstructionBlock* block) {
   for (auto phi : block->phis()) {
     int phi_vreg = phi->virtual_register();
-    auto map_value = new (allocation_zone())
-        RegisterAllocationData::PhiMapValue(phi, block, allocation_zone());
-    auto res = data()->phi_map().insert(std::make_pair(phi_vreg, map_value));
-    DCHECK(res.second);
-    USE(res);
+    auto map_value = data()->InitializePhiMap(block, phi);
     auto& output = phi->output();
+    // Map the destination operands, so the commitment phase can find them.
     for (size_t i = 0; i < phi->operands().size(); ++i) {
       InstructionBlock* cur_block =
           code()->InstructionBlockAt(block->predecessors()[i]);
       UnallocatedOperand input(UnallocatedOperand::ANY, phi->operands()[i]);
       auto move = data()->AddGapMove(cur_block->last_instruction_index(),
                                      Instruction::END, input, output);
-      map_value->incoming_moves.push_back(move);
+      map_value->AddOperand(&move->destination());
       DCHECK(!InstructionAt(cur_block->last_instruction_index())
                   ->HasReferenceMap());
     }
     auto live_range = LiveRangeFor(phi_vreg);
     int gap_index = block->first_instruction_index();
     live_range->SpillAtDefinition(allocation_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());
   }
 }
 
 
-LiveRangeBuilder::LiveRangeBuilder(RegisterAllocationData* data)
-    : data_(data) {}
+LiveRangeBuilder::LiveRangeBuilder(RegisterAllocationData* data,
+                                   Zone* local_zone)
+    : data_(data), phi_hints_(local_zone) {}
 
 
 BitVector* LiveRangeBuilder::ComputeLiveOut(const InstructionBlock* block) {
   // Compute live out for the given block, except not including backward
   // successor edges.
   auto live_out = new (allocation_zone())
       BitVector(code()->VirtualRegisterCount(), allocation_zone());
 
   // Process all successor blocks.
   for (auto succ : block->successors()) {
@@ skipping 38 matching lines @@
 }
 
 
 LiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index) {
   DCHECK(index < config()->num_general_registers());
   auto result = data()->fixed_live_ranges()[index];
   if (result == nullptr) {
     result = data()->NewLiveRange(FixedLiveRangeID(index));
     DCHECK(result->IsFixed());
     result->set_kind(GENERAL_REGISTERS);
-    data()->SetLiveRangeAssignedRegister(result, index);
+    result->set_assigned_register(index);
+    data()->MarkAllocated(GENERAL_REGISTERS, index);
     data()->fixed_live_ranges()[index] = result;
   }
   return result;
 }
 
 
 LiveRange* LiveRangeBuilder::FixedDoubleLiveRangeFor(int index) {
   DCHECK(index < config()->num_aliased_double_registers());
   auto result = data()->fixed_double_live_ranges()[index];
   if (result == nullptr) {
     result = data()->NewLiveRange(FixedDoubleLiveRangeID(index));
     DCHECK(result->IsFixed());
     result->set_kind(DOUBLE_REGISTERS);
-    data()->SetLiveRangeAssignedRegister(result, index);
+    result->set_assigned_register(index);
+    data()->MarkAllocated(DOUBLE_REGISTERS, index);
     data()->fixed_double_live_ranges()[index] = result;
   }
   return result;
 }
 
 
 LiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand) {
   if (operand->IsUnallocated()) {
     return LiveRangeFor(UnallocatedOperand::cast(operand)->virtual_register());
   } else if (operand->IsConstant()) {
     return LiveRangeFor(ConstantOperand::cast(operand)->virtual_register());
   } else if (operand->IsRegister()) {
     return FixedLiveRangeFor(RegisterOperand::cast(operand)->index());
   } else if (operand->IsDoubleRegister()) {
     return FixedDoubleLiveRangeFor(
         DoubleRegisterOperand::cast(operand)->index());
   } else {
     return nullptr;
   }
 }
 
 
-void LiveRangeBuilder::Define(LifetimePosition position,
-                              InstructionOperand* operand,
-                              InstructionOperand* hint) {
+UsePosition* LiveRangeBuilder::NewUsePosition(LifetimePosition pos,
+                                              InstructionOperand* operand,
+                                              void* hint,
+                                              UsePositionHintType hint_type) {
+  return new (allocation_zone()) UsePosition(pos, operand, hint, hint_type);
+}
+
+
+UsePosition* LiveRangeBuilder::Define(LifetimePosition position,
+                                      InstructionOperand* operand, void* hint,
+                                      UsePositionHintType hint_type) {
   auto range = LiveRangeFor(operand);
-  if (range == nullptr) return;
+  if (range == nullptr) return nullptr;
 
   if (range->IsEmpty() || range->Start() > position) {
     // Can happen if there is a definition without use.
     range->AddUseInterval(position, position.NextStart(), allocation_zone());
-    range->AddUsePosition(position.NextStart(), nullptr, nullptr,
-                          allocation_zone());
+    range->AddUsePosition(NewUsePosition(position.NextStart()));
   } else {
     range->ShortenTo(position);
   }
-
-  if (operand->IsUnallocated()) {
-    auto unalloc_operand = UnallocatedOperand::cast(operand);
-    range->AddUsePosition(position, unalloc_operand, hint, allocation_zone());
-  }
+  if (!operand->IsUnallocated()) return nullptr;
+  auto unalloc_operand = UnallocatedOperand::cast(operand);
+  auto use_pos = NewUsePosition(position, unalloc_operand, hint, hint_type);
+  range->AddUsePosition(use_pos);
+  return use_pos;
 }
 
 
-void LiveRangeBuilder::Use(LifetimePosition block_start,
-                           LifetimePosition position,
-                           InstructionOperand* operand,
-                           InstructionOperand* hint) {
+UsePosition* LiveRangeBuilder::Use(LifetimePosition block_start,
+                                   LifetimePosition position,
+                                   InstructionOperand* operand, void* hint,
+                                   UsePositionHintType hint_type) {
   auto range = LiveRangeFor(operand);
-  if (range == nullptr) return;
+  if (range == nullptr) return nullptr;
+  UsePosition* use_pos = nullptr;
   if (operand->IsUnallocated()) {
     UnallocatedOperand* unalloc_operand = UnallocatedOperand::cast(operand);
-    range->AddUsePosition(position, unalloc_operand, hint, allocation_zone());
+    use_pos = NewUsePosition(position, unalloc_operand, hint, hint_type);
+    range->AddUsePosition(use_pos);
   }
   range->AddUseInterval(block_start, position, allocation_zone());
+  return use_pos;
 }
 
 
-bool LiveRangeBuilder::IsOutputRegisterOf(Instruction* instr, int index) {
-  for (size_t i = 0; i < instr->OutputCount(); i++) {
-    auto output = instr->OutputAt(i);
-    if (output->IsRegister() && RegisterOperand::cast(output)->index() == index)
-      return true;
-  }
-  return false;
-}
-
-
-bool LiveRangeBuilder::IsOutputDoubleRegisterOf(Instruction* instr, int index) {
-  for (size_t i = 0; i < instr->OutputCount(); i++) {
-    auto output = instr->OutputAt(i);
-    if (output->IsDoubleRegister() &&
-        DoubleRegisterOperand::cast(output)->index() == index)
-      return true;
-  }
-  return false;
-}
-
-
 void LiveRangeBuilder::ProcessInstructions(const InstructionBlock* block,
                                            BitVector* live) {
   int block_start = block->first_instruction_index();
   auto block_start_position =
       LifetimePosition::GapFromInstructionIndex(block_start);
 
   for (int index = block->last_instruction_index(); index >= block_start;
        index--) {
     auto curr_position =
         LifetimePosition::InstructionFromInstructionIndex(index);
     auto instr = code()->InstructionAt(index);
     DCHECK(instr != nullptr);
     DCHECK(curr_position.IsInstructionPosition());
     // Process output, inputs, and temps of this 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 = ConstantOperand::cast(output)->virtual_register();
         live->Remove(out_vreg);
       }
-      Define(curr_position, output, nullptr);
+      Define(curr_position, output);
     }
 
     if (instr->ClobbersRegisters()) {
       for (int i = 0; i < config()->num_general_registers(); ++i) {
         if (!IsOutputRegisterOf(instr, i)) {
           auto range = FixedLiveRangeFor(i);
           range->AddUseInterval(curr_position, curr_position.End(),
                                 allocation_zone());
         }
       }
@@ skipping 21 matching lines @@
       }
 
       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);
+      Use(block_start_position, use_pos, input);
     }
 
     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.End(), temp, nullptr);
-      Define(curr_position, temp, nullptr);
+      Use(block_start_position, curr_position.End(), temp);
+      Define(curr_position, temp);
     }
 
     // Process the moves of the instruction's gaps, making their sources live.
     const Instruction::GapPosition kPositions[] = {Instruction::END,
                                                    Instruction::START};
     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();
       }
       for (auto cur : *move) {
         auto& from = cur->source();
         auto& to = cur->destination();
-        auto hint = &to;
+        void* hint = &to;
+        UsePositionHintType hint_type = UsePosition::HintTypeForOperand(to);
+        UsePosition* to_use = nullptr;
+        int phi_vreg = -1;
         if (to.IsUnallocated()) {
           int to_vreg = UnallocatedOperand::cast(to).virtual_register();
           auto to_range = LiveRangeFor(to_vreg);
           if (to_range->is_phi()) {
+            phi_vreg = to_vreg;
             if (to_range->is_non_loop_phi()) {
-              hint = to_range->current_hint_operand();
+              hint = to_range->current_hint_position();
+              hint_type = hint == nullptr ? UsePositionHintType::kNone
+                                          : UsePositionHintType::kUsePos;
+            } else {
+              hint_type = UsePositionHintType::kPhi;
+              hint = data()->GetPhiMapValueFor(to_vreg);
             }
           } else {
             if (live->Contains(to_vreg)) {
-              Define(curr_position, &to, &from);
+              to_use = Define(curr_position, &to, &from,
+                              UsePosition::HintTypeForOperand(from));
               live->Remove(to_vreg);
             } else {
               cur->Eliminate();
               continue;
             }
           }
         } else {
-          Define(curr_position, &to, &from);
+          Define(curr_position, &to);
         }
-        Use(block_start_position, curr_position, &from, hint);
+        auto from_use =
+            Use(block_start_position, curr_position, &from, hint, hint_type);
+        // Mark range live.
         if (from.IsUnallocated()) {
           live->Add(UnallocatedOperand::cast(from).virtual_register());
         }
+        // Resolve use position hints just created.
+        if (to_use != nullptr && from_use != nullptr) {
+          to_use->ResolveHint(from_use);
+          from_use->ResolveHint(to_use);
+        }
+        DCHECK_IMPLIES(to_use != nullptr, to_use->IsResolved());
+        DCHECK_IMPLIES(from_use != nullptr, from_use->IsResolved());
+        // Potentially resolve phi hint.
+        if (phi_vreg != -1) ResolvePhiHint(&from, from_use);
       }
     }
   }
 }
 
 
+void LiveRangeBuilder::ProcessPhis(const InstructionBlock* block,
+                                   BitVector* live) {
+  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;
+    auto instr = GetLastInstruction(
+        code(), code()->InstructionBlockAt(block->predecessors()[0]));
+    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());
+    auto use_pos = Define(block_start, &phi->output(), hint,
+                          UsePosition::HintTypeForOperand(*hint));
+    MapPhiHint(hint, use_pos);
+  }
+}
+
+
+void LiveRangeBuilder::ProcessLoopHeader(const InstructionBlock* block,
+                                         BitVector* live) {
+  DCHECK(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);
+  auto start = LifetimePosition::GapFromInstructionIndex(
+      block->first_instruction_index());
+  auto end = LifetimePosition::GapFromInstructionIndex(
+                 code()->LastLoopInstructionIndex(block)).NextFullStart();
+  while (!iterator.Done()) {
+    int operand_index = iterator.Current();
+    auto range = LiveRangeFor(operand_index);
+    range->EnsureInterval(start, end, allocation_zone());
+    iterator.Advance();
+  }
+  // Insert all values into the live in sets of all blocks in the loop.
+  for (int i = block->rpo_number().ToInt() + 1; i < block->loop_end().ToInt();
+       ++i) {
+    live_in_sets()[i]->Union(*live);
+  }
+}
+
+
 void LiveRangeBuilder::BuildLiveRanges() {
   // Process the blocks in reverse order.
   for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0;
        --block_id) {
     auto block = code()->InstructionBlockAt(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);
-      InstructionOperand* hint = nullptr;
-      auto instr = GetLastInstruction(
-          code(), code()->InstructionBlockAt(block->predecessors()[0]));
-      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->output(), hint);
-    }
-
+    ProcessPhis(block, live);
     // Now live is live_in for this block except not including values live
     // out on backward successor edges.
+    if (block->IsLoopHeader()) ProcessLoopHeader(block, live);
     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);
-      auto start = LifetimePosition::GapFromInstructionIndex(
-          block->first_instruction_index());
-      auto end = LifetimePosition::GapFromInstructionIndex(
-                     code()->LastLoopInstructionIndex(block)).NextFullStart();
-      while (!iterator.Done()) {
-        int operand_index = iterator.Current();
-        auto range = LiveRangeFor(operand_index);
-        range->EnsureInterval(start, end, allocation_zone());
-        iterator.Advance();
-      }
-      // Insert all values into the live in sets of all blocks in the loop.
-      for (int i = block->rpo_number().ToInt() + 1;
-           i < block->loop_end().ToInt(); ++i) {
-        live_in_sets()[i]->Union(*live);
-      }
-    }
   }
-
+  // Postprocess the ranges.
   for (auto range : data()->live_ranges()) {
     if (range == nullptr) continue;
     range->set_kind(RequiredRegisterKind(range->id()));
     // Give slots to all ranges with a non fixed slot use.
     if (range->has_slot_use() && range->HasNoSpillType()) {
       data()->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()) {
         if (pos->type() == UsePositionType::kRequiresSlot) continue;
         UsePositionType new_type = UsePositionType::kAny;
         // Can't mark phis as needing a register.
         if (!pos->pos().IsGapPosition()) {
           new_type = UsePositionType::kRequiresRegister;
         }
         pos->set_type(new_type, true);
       }
     }
   }
-
 #ifdef DEBUG
   Verify();
 #endif
 }
 
 
+void LiveRangeBuilder::MapPhiHint(InstructionOperand* operand,
+                                  UsePosition* use_pos) {
+  DCHECK(!use_pos->IsResolved());
+  auto res = phi_hints_.insert(std::make_pair(operand, use_pos));
+  DCHECK(res.second);
+  USE(res);
+}
+
+
+void LiveRangeBuilder::ResolvePhiHint(InstructionOperand* operand,
+                                      UsePosition* use_pos) {
+  auto it = phi_hints_.find(operand);
+  if (it == phi_hints_.end()) return;
+  DCHECK(!it->second->IsResolved());
+  it->second->ResolveHint(use_pos);
+}
+
+
 RegisterKind LiveRangeBuilder::RequiredRegisterKind(
     int virtual_register) const {
   return (code()->IsDouble(virtual_register)) ? DOUBLE_REGISTERS
                                               : GENERAL_REGISTERS;
 }
 
 
 void LiveRangeBuilder::Verify() const {
+  for (auto& hint : phi_hints_) {
+    CHECK(hint.second->IsResolved());
+  }
   for (auto current : data()->live_ranges()) {
     if (current != nullptr) current->Verify();
   }
 }
 
 
 RegisterAllocator::RegisterAllocator(RegisterAllocationData* data,
                                      RegisterKind kind)
     : data_(data),
       mode_(kind),
@@ skipping 220 matching lines @@
 
 const char* LinearScanAllocator::RegisterName(int allocation_index) const {
   if (mode() == GENERAL_REGISTERS) {
     return data()->config()->general_register_name(allocation_index);
   } else {
     return data()->config()->double_register_name(allocation_index);
   }
 }
 
 
+void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
+                                                       int reg) {
+  data()->MarkAllocated(range->Kind(), reg);
+  range->set_assigned_register(reg);
+  range->SetUseHints(reg);
+  if (range->is_phi()) {
+    data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg);
+  }
+}
+
+
 void LinearScanAllocator::AddToActive(LiveRange* range) {
   TRACE("Add live range %d to active\n", range->id());
   active_live_ranges().push_back(range);
 }
 
 
 void LinearScanAllocator::AddToInactive(LiveRange* range) {
   TRACE("Add live range %d to inactive\n", range->id());
   inactive_live_ranges().push_back(range);
 }
@@ skipping 95 matching lines @@
   }
 
   for (auto cur_inactive : inactive_live_ranges()) {
     DCHECK(cur_inactive->End() > current->Start());
     auto next_intersection = cur_inactive->FirstIntersection(current);
     if (!next_intersection.IsValid()) continue;
     int cur_reg = cur_inactive->assigned_register();
     free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
   }
 
-  auto hint = current->FirstHint();
-  if (hint != nullptr && (hint->IsRegister() || hint->IsDoubleRegister())) {
-    int register_index = AllocatedOperand::cast(hint)->index();
+  int hint_register;
+  if (current->FirstHintPosition(&hint_register) != nullptr) {
     TRACE("Found reg hint %s (free until [%d) for live range %d (end %d[).\n",
-          RegisterName(register_index), free_until_pos[register_index].value(),
+          RegisterName(hint_register), free_until_pos[hint_register].value(),
           current->id(), current->End().value());
 
     // The desired register is free until the end of the current live range.
-    if (free_until_pos[register_index] >= current->End()) {
+    if (free_until_pos[hint_register] >= current->End()) {
       TRACE("Assigning preferred reg %s to live range %d\n",
-            RegisterName(register_index), current->id());
-      data()->SetLiveRangeAssignedRegister(current, register_index);
+            RegisterName(hint_register), current->id());
+      SetLiveRangeAssignedRegister(current, hint_register);
       return true;
     }
   }
 
   // Find the register which stays free for the longest time.
   int reg = 0;
   for (int i = 1; i < num_registers(); ++i) {
     if (free_until_pos[i] > free_until_pos[reg]) {
       reg = i;
     }
@@ skipping 11 matching lines @@
     // the range end. Split current at position where it becomes blocked.
     auto tail = SplitRangeAt(current, pos);
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is available at the range start and is free until
   // the range end.
   DCHECK(pos >= current->End());
   TRACE("Assigning free reg %s to live range %d\n", RegisterName(reg),
         current->id());
-  data()->SetLiveRangeAssignedRegister(current, reg);
+  SetLiveRangeAssignedRegister(current, reg);
 
   return true;
 }
 
 
 void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) {
   auto register_use = current->NextRegisterPosition(current->Start());
   if (register_use == nullptr) {
     // There is no use in the current live range that requires a register.
     // We can just spill it.
@@ skipping 58 matching lines @@
     // position.
     LiveRange* tail =
         SplitBetween(current, current->Start(), block_pos[reg].Start());
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is not blocked for the whole range.
   DCHECK(block_pos[reg] >= current->End());
   TRACE("Assigning blocked reg %s to live range %d\n", RegisterName(reg),
         current->id());
-  data()->SetLiveRangeAssignedRegister(current, reg);
+  SetLiveRangeAssignedRegister(current, reg);
 
   // This register was not free. Thus we need to find and spill
   // parts of active and inactive live regions that use the same register
   // at the same lifetime positions as current.
   SplitAndSpillIntersecting(current);
 }
 
 
 void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
   DCHECK(current->HasRegisterAssigned());
@@ skipping 39 matching lines @@
         --i;
       }
     }
   }
 }
 
 
 bool LinearScanAllocator::TryReuseSpillForPhi(LiveRange* range) {
   if (range->IsChild() || !range->is_phi()) return false;
   DCHECK(!range->HasSpillOperand());
-
-  auto lookup = data()->phi_map().find(range->id());
-  DCHECK(lookup != data()->phi_map().end());
-  auto phi = lookup->second->phi;
-  auto block = lookup->second->block;
+  auto phi_map_value = data()->GetPhiMapValueFor(range->id());
+  auto phi = phi_map_value->phi();
+  auto block = phi_map_value->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->HasSpillRange()) continue;
     auto pred = code()->InstructionBlockAt(block->predecessors()[i]);
     auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
         pred->last_instruction_index());
@@ skipping 200 matching lines @@
 }
 
 
 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
   allocations_[reg_id]->Insert(range);
   if (range->HasRegisterAssigned()) {
     DCHECK_EQ(reg_id, range->assigned_register());
     return;
   }
   range->set_assigned_register(reg_id);
+  range->SetUseHints(reg_id);
+  if (range->is_phi()) {
+    data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg_id);
+  }
 }
 
 
 float GreedyAllocator::CalculateSpillWeight(LiveRange* range) {
   if (range->IsFixed()) return std::numeric_limits<float>::max();
 
-  if (range->FirstHint() != nullptr && range->FirstHint()->IsRegister()) {
+  int hint_register;
+  if (range->FirstHintPosition(&hint_register) != nullptr) {
     return std::numeric_limits<float>::max();
   }
 
   unsigned use_count = 0;
   auto* pos = range->first_pos();
   while (pos != nullptr) {
     use_count++;
     pos = pos->next();
   }
 
@@ skipping 11 matching lines @@
   for (auto* r : ranges) {
     max = std::max(max, CalculateSpillWeight(r));
   }
   return max;
 }
 
 
 void GreedyAllocator::Evict(LiveRange* range) {
   bool removed = allocations_[range->assigned_register()]->Remove(range);
   CHECK(removed);
+  range->UnsetUseHints();
+  range->UnsetAssignedRegister();
+  if (range->is_phi()) {
+    data()->GetPhiMapValueFor(range->id())->UnsetAssignedRegister();
+  }
 }
 
 
 bool GreedyAllocator::TryAllocatePhysicalRegister(
     unsigned reg_id, LiveRange* range, ZoneSet<LiveRange*>* conflicting) {
   auto* segment = range->first_interval();
 
   auto* alloc_info = allocations_[reg_id];
   while (segment != nullptr) {
     if (auto* existing = alloc_info->Find(segment)) {
@@ skipping 148 matching lines @@
         CHECK(allocated);
         DCHECK(conflicting.empty());
       } else {
         DCHECK(!current->IsFixed() || current->CanBeSpilled(current->Start()));
         bool allocated = AllocateBlockedRange(current, conflicting);
         CHECK(allocated);
       }
     }
   }
 
-  BitVector* assigned_registers = new (zone) BitVector(num_registers(), zone);
   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->IsEmpty()) {
-      assigned_registers->Add(static_cast<int>(i));
+      data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
-  data()->frame()->SetAllocatedRegisters(assigned_registers);
 }
 
 
 bool GreedyAllocator::AllocateBlockedRange(
     LiveRange* current, const ZoneSet<LiveRange*>& conflicts) {
   auto register_use = current->NextRegisterPosition(current->Start());
   if (register_use == nullptr) {
     // There is no use in the current live range that requires a register.
     // We can just spill it.
     Spill(current);
@@ skipping 40 matching lines @@
 
 void OperandAssigner::CommitAssignment() {
   for (auto range : data()->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()) data()->AssignPhiInput(range, assigned);
+    if (range->is_phi()) {
+      data()->GetPhiMapValueFor(range->id())->CommitAssignment(assigned);
+    }
     if (!range->IsChild() && spill_operand != nullptr) {
       range->CommitSpillsAtDefinition(data()->code(), spill_operand,
                                       range->has_slot_use());
     }
   }
 }
 
 
 ReferenceMapPopulator::ReferenceMapPopulator(RegisterAllocationData* data)
     : data_(data) {}
@@ skipping 355 matching lines @@
     auto eliminate = moves->PrepareInsertAfter(move);
     to_insert.push_back(move);
     if (eliminate != nullptr) to_eliminate.push_back(eliminate);
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8