src/compiler/greedy-allocator.cc - fp2-dev/platform/external/v8 - Gitiles

 // Copyright 2015 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/greedy-allocator.h"
 #include "src/compiler/register-allocator.h"

 namespace v8 {
 namespace internal {
 namespace compiler {


 #define TRACE(...)                             \
   do {                                         \
     if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
   } while (false)


 const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;


 namespace {

 void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
   int reg_id = range->assigned_register();
   range->SetUseHints(reg_id);
   if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
     data->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg_id);
   }
 }


 void UnsetOperands(LiveRange* range, RegisterAllocationData* data) {
   range->UnsetUseHints();
   if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
     data->GetPhiMapValueFor(range->TopLevel())->UnsetAssignedRegister();
   }
 }


 LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
                  LifetimePosition pos) {
   DCHECK(range->Start() < pos && pos < range->End());
   DCHECK(pos.IsStart() || pos.IsGapPosition() ||
          (data->code()
               ->GetInstructionBlock(pos.ToInstructionIndex())
               ->last_instruction_index() != pos.ToInstructionIndex()));
   LiveRange* result = range->SplitAt(pos, data->allocation_zone());
   return result;
 }


 }  // namespace


 AllocationCandidate AllocationScheduler::GetNext() {
   DCHECK(!queue_.empty());
   AllocationCandidate ret = queue_.top();
   queue_.pop();
   return ret;
 }


 void AllocationScheduler::Schedule(LiveRange* range) {
   TRACE("Scheduling live range %d:%d.\n", range->TopLevel()->vreg(),
         range->relative_id());
   queue_.push(AllocationCandidate(range));
 }


 void AllocationScheduler::Schedule(LiveRangeGroup* group) {
   queue_.push(AllocationCandidate(group));
 }

 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
                                  RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       local_zone_(local_zone),
       allocations_(local_zone),
       scheduler_(local_zone),
       groups_(local_zone) {}


 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
   TRACE("Assigning register %s to live range %d:%d\n", RegisterName(reg_id),
         range->TopLevel()->vreg(), range->relative_id());

   DCHECK(!range->HasRegisterAssigned());

   AllocateRegisterToRange(reg_id, range);

   TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
         range->TopLevel()->vreg(), range->relative_id());
   range->set_assigned_register(reg_id);
   UpdateOperands(range, data());
 }


 void GreedyAllocator::PreallocateFixedRanges() {
   allocations_.resize(num_registers());
   for (int i = 0; i < num_registers(); i++) {
     allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_zone());
   }

   for (LiveRange* fixed_range : GetFixedRegisters()) {
     if (fixed_range != nullptr) {
       DCHECK_EQ(mode(), fixed_range->kind());
       DCHECK(fixed_range->TopLevel()->IsFixed());

       int reg_nr = fixed_range->assigned_register();
       EnsureValidRangeWeight(fixed_range);
       AllocateRegisterToRange(reg_nr, fixed_range);
     }
   }
 }


 void GreedyAllocator::GroupLiveRanges() {
   CoalescedLiveRanges grouper(local_zone());
   for (TopLevelLiveRange* range : data()->live_ranges()) {
     grouper.clear();
     // Skip splinters, because we do not want to optimize for them, and moves
     // due to assigning them to different registers occur in deferred blocks.
     if (!CanProcessRange(range) || range->IsSplinter() || !range->is_phi()) {
       continue;
     }

     // A phi can't be a memory operand, so it couldn't have been split.
     DCHECK(!range->spilled());

     // Maybe this phi range is itself an input to another phi which was already
     // processed.
     LiveRangeGroup* latest_grp = range->group() != nullptr
                                      ? range->group()
                                      : new (local_zone())
                                            LiveRangeGroup(local_zone());

     // Populate the grouper.
     if (range->group() == nullptr) {
       grouper.AllocateRange(range);
     } else {
       for (LiveRange* member : range->group()->ranges()) {
         grouper.AllocateRange(member);
       }
     }
     for (int j : data()->GetPhiMapValueFor(range)->phi()->operands()) {
       // skip output also in input, which may happen for loops.
       if (j == range->vreg()) continue;

       TopLevelLiveRange* other_top = data()->live_ranges()[j];

       if (other_top->IsSplinter()) continue;
       // If the other was a memory operand, it might have been split.
       // So get the unsplit part.
       LiveRange* other =
           other_top->next() == nullptr ? other_top : other_top->next();

       if (other->spilled()) continue;

       LiveRangeGroup* other_group = other->group();
       if (other_group != nullptr) {
         bool can_merge = true;
         for (LiveRange* member : other_group->ranges()) {
           if (grouper.GetConflicts(member).Current() != nullptr) {
             can_merge = false;
             break;
           }
         }
         // If each member doesn't conflict with the current group, then since
         // the members don't conflict with eachother either, we can merge them.
         if (can_merge) {
           latest_grp->ranges().insert(latest_grp->ranges().end(),
                                       other_group->ranges().begin(),
                                       other_group->ranges().end());
           for (LiveRange* member : other_group->ranges()) {
             grouper.AllocateRange(member);
             member->set_group(latest_grp);
           }
           // Clear the other range, so we avoid scheduling it.
           other_group->ranges().clear();
         }
       } else if (grouper.GetConflicts(other).Current() == nullptr) {
         grouper.AllocateRange(other);
         latest_grp->ranges().push_back(other);
         other->set_group(latest_grp);
       }
     }

     if (latest_grp->ranges().size() > 0 && range->group() == nullptr) {
       latest_grp->ranges().push_back(range);
       DCHECK(latest_grp->ranges().size() > 1);
       groups().push_back(latest_grp);
       range->set_group(latest_grp);
     }
   }
 }


 void GreedyAllocator::ScheduleAllocationCandidates() {
   for (LiveRangeGroup* group : groups()) {
     if (group->ranges().size() > 0) {
       // We shouldn't have added single-range groups.
       DCHECK(group->ranges().size() != 1);
       scheduler().Schedule(group);
     }
   }
   for (LiveRange* range : data()->live_ranges()) {
     if (CanProcessRange(range)) {
       for (LiveRange* child = range; child != nullptr; child = child->next()) {
         if (!child->spilled() && child->group() == nullptr) {
           scheduler().Schedule(child);
         }
       }
     }
   }
 }


 void GreedyAllocator::TryAllocateCandidate(
     const AllocationCandidate& candidate) {
   if (candidate.is_group()) {
     TryAllocateGroup(candidate.group());
   } else {
     TryAllocateLiveRange(candidate.live_range());
   }
 }


 void GreedyAllocator::TryAllocateGroup(LiveRangeGroup* group) {
   float group_weight = 0.0;
   for (LiveRange* member : group->ranges()) {
     EnsureValidRangeWeight(member);
     group_weight = Max(group_weight, member->weight());
   }

   float eviction_weight = group_weight;
   int eviction_reg = -1;
   int free_reg = -1;
   for (int i = 0; i < num_allocatable_registers(); ++i) {
     int reg = allocatable_register_code(i);
     float weight = GetMaximumConflictingWeight(reg, group, group_weight);
     if (weight == LiveRange::kInvalidWeight) {
       free_reg = reg;
       break;
     }
     if (weight < eviction_weight) {
       eviction_weight = weight;
       eviction_reg = reg;
     }
   }
   if (eviction_reg < 0 && free_reg < 0) {
     for (LiveRange* member : group->ranges()) {
       scheduler().Schedule(member);
     }
     return;
   }
   if (free_reg < 0) {
     DCHECK(eviction_reg >= 0);
     for (LiveRange* member : group->ranges()) {
       EvictAndRescheduleConflicts(eviction_reg, member);
     }
     free_reg = eviction_reg;
   }

   DCHECK(free_reg >= 0);
   for (LiveRange* member : group->ranges()) {
     AssignRangeToRegister(free_reg, member);
   }
 }


 void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
   // TODO(mtrofin): once we introduce groups, we'll want to first try and
   // allocate at the preferred register.
   TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
         range->relative_id());
   int free_reg = -1;
   int evictable_reg = -1;
   int hinted_reg = -1;

   EnsureValidRangeWeight(range);
   float competing_weight = range->weight();
   DCHECK(competing_weight != LiveRange::kInvalidWeight);

   // Can we allocate at the hinted register?
   if (range->FirstHintPosition(&hinted_reg) != nullptr) {
     DCHECK(hinted_reg >= 0);
     float max_conflict_weight =
         GetMaximumConflictingWeight(hinted_reg, range, competing_weight);
     if (max_conflict_weight == LiveRange::kInvalidWeight) {
       free_reg = hinted_reg;
     } else if (max_conflict_weight < range->weight()) {
       evictable_reg = hinted_reg;
     }
   }

   if (free_reg < 0 && evictable_reg < 0) {
     // There was no hinted reg, or we cannot allocate there.
     float smallest_weight = LiveRange::kMaxWeight;

     // Seek either the first free register, or, from the set of registers
     // where the maximum conflict is lower than the candidate's weight, the one
     // with the smallest such weight.
     for (int i = 0; i < num_allocatable_registers(); i++) {
       int reg = allocatable_register_code(i);
       // Skip unnecessarily re-visiting the hinted register, if any.
       if (reg == hinted_reg) continue;
       float max_conflict_weight =
           GetMaximumConflictingWeight(reg, range, competing_weight);
       if (max_conflict_weight == LiveRange::kInvalidWeight) {
         free_reg = reg;
         break;
       }
       if (max_conflict_weight < range->weight() &&
           max_conflict_weight < smallest_weight) {
         smallest_weight = max_conflict_weight;
         evictable_reg = reg;
       }
     }
   }

   // We have a free register, so we use it.
   if (free_reg >= 0) {
     TRACE("Found free register %s for live range %d:%d.\n",
           RegisterName(free_reg), range->TopLevel()->vreg(),
           range->relative_id());
     AssignRangeToRegister(free_reg, range);
     return;
   }

   // We found a register to perform evictions, so we evict and allocate our
   // candidate.
   if (evictable_reg >= 0) {
     TRACE("Found evictable register %s for live range %d:%d.\n",
           RegisterName(free_reg), range->TopLevel()->vreg(),
           range->relative_id());
     EvictAndRescheduleConflicts(evictable_reg, range);
     AssignRangeToRegister(evictable_reg, range);
     return;
   }

   // The range needs to be split or spilled.
   SplitOrSpillBlockedRange(range);
 }


 void GreedyAllocator::EvictAndRescheduleConflicts(unsigned reg_id,
                                                   const LiveRange* range) {
   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
        conflict = conflicts.RemoveCurrentAndGetNext()) {
     DCHECK(conflict->HasRegisterAssigned());
     CHECK(!conflict->TopLevel()->IsFixed());
     conflict->UnsetAssignedRegister();
     UnsetOperands(conflict, data());
     UpdateWeightAtEviction(conflict);
     scheduler().Schedule(conflict);
     TRACE("Evicted range %d%d.\n", conflict->TopLevel()->vreg(),
           conflict->relative_id());
   }
 }


 void GreedyAllocator::AllocateRegisters() {
   CHECK(scheduler().empty());
   CHECK(allocations_.empty());

   TRACE("Begin allocating function %s with the Greedy Allocator\n",
         data()->debug_name());

   SplitAndSpillRangesDefinedByMemoryOperand(true);
   GroupLiveRanges();
   ScheduleAllocationCandidates();
   PreallocateFixedRanges();
   while (!scheduler().empty()) {
     AllocationCandidate candidate = scheduler().GetNext();
     TryAllocateCandidate(candidate);
   }

   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->empty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
   allocations_.clear();

   TryReuseSpillRangesForGroups();

   TRACE("End allocating function %s with the Greedy Allocator\n",
         data()->debug_name());
 }


 void GreedyAllocator::TryReuseSpillRangesForGroups() {
   for (TopLevelLiveRange* top : data()->live_ranges()) {
     if (!CanProcessRange(top) || !top->is_phi() || top->group() == nullptr) {
       continue;
     }

     SpillRange* spill_range = nullptr;
     for (LiveRange* member : top->group()->ranges()) {
       if (!member->TopLevel()->HasSpillRange()) continue;
       SpillRange* member_range = member->TopLevel()->GetSpillRange();
       if (spill_range == nullptr) {
         spill_range = member_range;
       } else {
         // This may not always succeed, because we group non-conflicting ranges
         // that may have been splintered, and the splinters may cause conflicts
         // in the spill ranges.
         // TODO(mtrofin): should the splinters own their own spill ranges?
         spill_range->TryMerge(member_range);
       }
     }
   }
 }


 float GreedyAllocator::GetMaximumConflictingWeight(
     unsigned reg_id, const LiveRange* range, float competing_weight) const {
   float ret = LiveRange::kInvalidWeight;

   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
        conflict = conflicts.GetNext()) {
     DCHECK_NE(conflict->weight(), LiveRange::kInvalidWeight);
     if (competing_weight <= conflict->weight()) return LiveRange::kMaxWeight;
     ret = Max(ret, conflict->weight());
     DCHECK(ret < LiveRange::kMaxWeight);
   }

   return ret;
 }


 float GreedyAllocator::GetMaximumConflictingWeight(unsigned reg_id,
                                                    const LiveRangeGroup* group,
                                                    float group_weight) const {
   float ret = LiveRange::kInvalidWeight;

   for (LiveRange* member : group->ranges()) {
     float member_conflict_weight =
         GetMaximumConflictingWeight(reg_id, member, group_weight);
     if (member_conflict_weight == LiveRange::kMaxWeight) {
       return LiveRange::kMaxWeight;
     }
     if (member_conflict_weight > group_weight) return LiveRange::kMaxWeight;
     ret = Max(member_conflict_weight, ret);
   }

   return ret;
 }


 void GreedyAllocator::EnsureValidRangeWeight(LiveRange* range) {
   // The live range weight will be invalidated when ranges are created or split.
   // Otherwise, it is consistently updated when the range is allocated or
   // unallocated.
   if (range->weight() != LiveRange::kInvalidWeight) return;

   if (range->TopLevel()->IsFixed()) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }
   if (!IsProgressPossible(range)) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }

   float use_count = 0.0;
   for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
     ++use_count;
   }
   range->set_weight(use_count / static_cast<float>(range->GetSize()));
 }


 void GreedyAllocator::SpillRangeAsLastResort(LiveRange* range) {
   LifetimePosition start = range->Start();
   CHECK(range->CanBeSpilled(start));

   DCHECK(range->NextRegisterPosition(start) == nullptr);
   Spill(range);
 }


 LiveRange* GreedyAllocator::GetRemainderAfterSplittingAroundFirstCall(
     LiveRange* range) {
   LiveRange* ret = range;
   for (UseInterval* interval = range->first_interval(); interval != nullptr;
        interval = interval->next()) {
     LifetimePosition start = interval->start();
     LifetimePosition end = interval->end();
     // If the interval starts at instruction end, then the first instruction
     // in the interval is the next one.
     int first_full_instruction = (start.IsGapPosition() || start.IsStart())
                                      ? start.ToInstructionIndex()
                                      : start.ToInstructionIndex() + 1;
     // If the interval ends in a gap or at instruction start, then the last
     // instruction is the previous one.
     int last_full_instruction = (end.IsGapPosition() || end.IsStart())
                                     ? end.ToInstructionIndex() - 1
                                     : end.ToInstructionIndex();

     for (int instruction_index = first_full_instruction;
          instruction_index <= last_full_instruction; ++instruction_index) {
       if (!code()->InstructionAt(instruction_index)->IsCall()) continue;

       LifetimePosition before =
           GetSplitPositionForInstruction(range, instruction_index);
       LiveRange* second_part =
           before.IsValid() ? Split(range, data(), before) : range;

       if (range != second_part) scheduler().Schedule(range);

       LifetimePosition after =
           FindSplitPositionAfterCall(second_part, instruction_index);

       if (after.IsValid()) {
         ret = Split(second_part, data(), after);
       } else {
         ret = nullptr;
       }
       Spill(second_part);
       return ret;
     }
   }
   return ret;
 }


 bool GreedyAllocator::TrySplitAroundCalls(LiveRange* range) {
   bool modified = false;

   while (range != nullptr) {
     LiveRange* remainder = GetRemainderAfterSplittingAroundFirstCall(range);
     // If we performed no modification, we're done.
     if (remainder == range) {
       break;
     }
     // We performed a modification.
     modified = true;
     range = remainder;
   }
   // If we have a remainder and we made modifications, it means the remainder
   // has no calls and we should schedule it for further processing. If we made
   // no modifications, we will just return false, because we want the algorithm
   // to make progress by trying some other heuristic.
   if (modified && range != nullptr) {
     DCHECK(!range->spilled());
     DCHECK(!range->HasRegisterAssigned());
     scheduler().Schedule(range);
   }
   return modified;
 }


 LifetimePosition GreedyAllocator::FindSplitPositionAfterCall(
     const LiveRange* range, int call_index) {
   LifetimePosition after_call =
       Max(range->Start(),
           LifetimePosition::GapFromInstructionIndex(call_index + 1));
   UsePosition* next_use = range->NextRegisterPosition(after_call);
   if (!next_use) return LifetimePosition::Invalid();

   LifetimePosition split_pos = FindOptimalSplitPos(after_call, next_use->pos());
   split_pos =
       GetSplitPositionForInstruction(range, split_pos.ToInstructionIndex());
   return split_pos;
 }


 LifetimePosition GreedyAllocator::FindSplitPositionBeforeLoops(
     LiveRange* range) {
   LifetimePosition end = range->End();
   if (end.ToInstructionIndex() >= code()->LastInstructionIndex()) {
     end =
         LifetimePosition::GapFromInstructionIndex(end.ToInstructionIndex() - 1);
   }
   LifetimePosition pos = FindOptimalSplitPos(range->Start(), end);
   pos = GetSplitPositionForInstruction(range, pos.ToInstructionIndex());
   return pos;
 }


 void GreedyAllocator::SplitOrSpillBlockedRange(LiveRange* range) {
   if (TrySplitAroundCalls(range)) return;

   LifetimePosition pos = FindSplitPositionBeforeLoops(range);

   if (!pos.IsValid()) pos = GetLastResortSplitPosition(range);
   if (pos.IsValid()) {
     LiveRange* tail = Split(range, data(), pos);
     DCHECK(tail != range);
     scheduler().Schedule(tail);
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }


 // Basic heuristic for advancing the algorithm, if any other splitting heuristic
 // failed.
 LifetimePosition GreedyAllocator::GetLastResortSplitPosition(
     const LiveRange* range) {
   LifetimePosition previous = range->Start();
   for (UsePosition *pos = range->NextRegisterPosition(previous); pos != nullptr;
        previous = previous.NextFullStart(),
                    pos = range->NextRegisterPosition(previous)) {
     LifetimePosition optimal = FindOptimalSplitPos(previous, pos->pos());
     LifetimePosition before =
         GetSplitPositionForInstruction(range, optimal.ToInstructionIndex());
     if (before.IsValid()) return before;
     LifetimePosition after = GetSplitPositionForInstruction(
         range, pos->pos().ToInstructionIndex() + 1);
     if (after.IsValid()) return after;
   }
   return LifetimePosition::Invalid();
 }


 bool GreedyAllocator::IsProgressPossible(const LiveRange* range) {
   return range->CanBeSpilled(range->Start()) ||
          GetLastResortSplitPosition(range).IsValid();
 }

 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
	// Copyright 2015 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/greedy-allocator.h"
	#include "src/compiler/register-allocator.h"

	namespace v8 {
	namespace internal {
	namespace compiler {


	#define TRACE(...) \
	do { \
	if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
	} while (false)


	const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;


	namespace {

	void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
	int reg_id = range->assigned_register();
	range->SetUseHints(reg_id);
	if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
	data->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg_id);
	}
	}


	void UnsetOperands(LiveRange* range, RegisterAllocationData* data) {
	range->UnsetUseHints();
	if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
	data->GetPhiMapValueFor(range->TopLevel())->UnsetAssignedRegister();
	}
	}


	LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
	LifetimePosition pos) {
	DCHECK(range->Start() < pos && pos < range->End());
	DCHECK(pos.IsStart() \|\| pos.IsGapPosition() \|\|
	(data->code()
	->GetInstructionBlock(pos.ToInstructionIndex())
	->last_instruction_index() != pos.ToInstructionIndex()));
	LiveRange* result = range->SplitAt(pos, data->allocation_zone());
	return result;
	}


	} // namespace


	AllocationCandidate AllocationScheduler::GetNext() {
	DCHECK(!queue_.empty());
	AllocationCandidate ret = queue_.top();
	queue_.pop();
	return ret;
	}


	void AllocationScheduler::Schedule(LiveRange* range) {
	TRACE("Scheduling live range %d:%d.\n", range->TopLevel()->vreg(),
	range->relative_id());
	queue_.push(AllocationCandidate(range));
	}


	void AllocationScheduler::Schedule(LiveRangeGroup* group) {
	queue_.push(AllocationCandidate(group));
	}

	GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
	RegisterKind kind, Zone* local_zone)
	: RegisterAllocator(data, kind),
	local_zone_(local_zone),
	allocations_(local_zone),
	scheduler_(local_zone),
	groups_(local_zone) {}


	void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
	TRACE("Assigning register %s to live range %d:%d\n", RegisterName(reg_id),
	range->TopLevel()->vreg(), range->relative_id());

	DCHECK(!range->HasRegisterAssigned());

	AllocateRegisterToRange(reg_id, range);

	TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
	range->TopLevel()->vreg(), range->relative_id());
	range->set_assigned_register(reg_id);
	UpdateOperands(range, data());
	}


	void GreedyAllocator::PreallocateFixedRanges() {
	allocations_.resize(num_registers());
	for (int i = 0; i < num_registers(); i++) {
	allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_zone());
	}

	for (LiveRange* fixed_range : GetFixedRegisters()) {
	if (fixed_range != nullptr) {
	DCHECK_EQ(mode(), fixed_range->kind());
	DCHECK(fixed_range->TopLevel()->IsFixed());

	int reg_nr = fixed_range->assigned_register();
	EnsureValidRangeWeight(fixed_range);
	AllocateRegisterToRange(reg_nr, fixed_range);
	}
	}
	}


	void GreedyAllocator::GroupLiveRanges() {
	CoalescedLiveRanges grouper(local_zone());
	for (TopLevelLiveRange* range : data()->live_ranges()) {
	grouper.clear();
	// Skip splinters, because we do not want to optimize for them, and moves
	// due to assigning them to different registers occur in deferred blocks.
	if (!CanProcessRange(range) \|\| range->IsSplinter() \|\| !range->is_phi()) {
	continue;
	}

	// A phi can't be a memory operand, so it couldn't have been split.
	DCHECK(!range->spilled());

	// Maybe this phi range is itself an input to another phi which was already
	// processed.
	LiveRangeGroup* latest_grp = range->group() != nullptr
	? range->group()
	: new (local_zone())
	LiveRangeGroup(local_zone());

	// Populate the grouper.
	if (range->group() == nullptr) {
	grouper.AllocateRange(range);
	} else {
	for (LiveRange* member : range->group()->ranges()) {
	grouper.AllocateRange(member);
	}
	}
	for (int j : data()->GetPhiMapValueFor(range)->phi()->operands()) {
	// skip output also in input, which may happen for loops.
	if (j == range->vreg()) continue;

	TopLevelLiveRange* other_top = data()->live_ranges()[j];

	if (other_top->IsSplinter()) continue;
	// If the other was a memory operand, it might have been split.
	// So get the unsplit part.
	LiveRange* other =
	other_top->next() == nullptr ? other_top : other_top->next();

	if (other->spilled()) continue;

	LiveRangeGroup* other_group = other->group();
	if (other_group != nullptr) {
	bool can_merge = true;
	for (LiveRange* member : other_group->ranges()) {
	if (grouper.GetConflicts(member).Current() != nullptr) {
	can_merge = false;
	break;
	}
	}
	// If each member doesn't conflict with the current group, then since
	// the members don't conflict with eachother either, we can merge them.
	if (can_merge) {
	latest_grp->ranges().insert(latest_grp->ranges().end(),
	other_group->ranges().begin(),
	other_group->ranges().end());
	for (LiveRange* member : other_group->ranges()) {
	grouper.AllocateRange(member);
	member->set_group(latest_grp);
	}
	// Clear the other range, so we avoid scheduling it.
	other_group->ranges().clear();
	}
	} else if (grouper.GetConflicts(other).Current() == nullptr) {
	grouper.AllocateRange(other);
	latest_grp->ranges().push_back(other);
	other->set_group(latest_grp);
	}
	}

	if (latest_grp->ranges().size() > 0 && range->group() == nullptr) {
	latest_grp->ranges().push_back(range);
	DCHECK(latest_grp->ranges().size() > 1);
	groups().push_back(latest_grp);
	range->set_group(latest_grp);
	}
	}
	}


	void GreedyAllocator::ScheduleAllocationCandidates() {
	for (LiveRangeGroup* group : groups()) {
	if (group->ranges().size() > 0) {
	// We shouldn't have added single-range groups.
	DCHECK(group->ranges().size() != 1);
	scheduler().Schedule(group);
	}
	}
	for (LiveRange* range : data()->live_ranges()) {
	if (CanProcessRange(range)) {
	for (LiveRange* child = range; child != nullptr; child = child->next()) {
	if (!child->spilled() && child->group() == nullptr) {
	scheduler().Schedule(child);
	}
	}
	}
	}
	}


	void GreedyAllocator::TryAllocateCandidate(
	const AllocationCandidate& candidate) {
	if (candidate.is_group()) {
	TryAllocateGroup(candidate.group());
	} else {
	TryAllocateLiveRange(candidate.live_range());
	}
	}


	void GreedyAllocator::TryAllocateGroup(LiveRangeGroup* group) {
	float group_weight = 0.0;
	for (LiveRange* member : group->ranges()) {
	EnsureValidRangeWeight(member);
	group_weight = Max(group_weight, member->weight());
	}

	float eviction_weight = group_weight;
	int eviction_reg = -1;
	int free_reg = -1;
	for (int i = 0; i < num_allocatable_registers(); ++i) {
	int reg = allocatable_register_code(i);
	float weight = GetMaximumConflictingWeight(reg, group, group_weight);
	if (weight == LiveRange::kInvalidWeight) {
	free_reg = reg;
	break;
	}
	if (weight < eviction_weight) {
	eviction_weight = weight;
	eviction_reg = reg;
	}
	}
	if (eviction_reg < 0 && free_reg < 0) {
	for (LiveRange* member : group->ranges()) {
	scheduler().Schedule(member);
	}
	return;
	}
	if (free_reg < 0) {
	DCHECK(eviction_reg >= 0);
	for (LiveRange* member : group->ranges()) {
	EvictAndRescheduleConflicts(eviction_reg, member);
	}
	free_reg = eviction_reg;
	}

	DCHECK(free_reg >= 0);
	for (LiveRange* member : group->ranges()) {
	AssignRangeToRegister(free_reg, member);
	}
	}


	void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
	// TODO(mtrofin): once we introduce groups, we'll want to first try and
	// allocate at the preferred register.
	TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
	range->relative_id());
	int free_reg = -1;
	int evictable_reg = -1;
	int hinted_reg = -1;

	EnsureValidRangeWeight(range);
	float competing_weight = range->weight();
	DCHECK(competing_weight != LiveRange::kInvalidWeight);

	// Can we allocate at the hinted register?
	if (range->FirstHintPosition(&hinted_reg) != nullptr) {
	DCHECK(hinted_reg >= 0);
	float max_conflict_weight =
	GetMaximumConflictingWeight(hinted_reg, range, competing_weight);
	if (max_conflict_weight == LiveRange::kInvalidWeight) {
	free_reg = hinted_reg;
	} else if (max_conflict_weight < range->weight()) {
	evictable_reg = hinted_reg;
	}
	}

	if (free_reg < 0 && evictable_reg < 0) {
	// There was no hinted reg, or we cannot allocate there.
	float smallest_weight = LiveRange::kMaxWeight;

	// Seek either the first free register, or, from the set of registers
	// where the maximum conflict is lower than the candidate's weight, the one
	// with the smallest such weight.
	for (int i = 0; i < num_allocatable_registers(); i++) {
	int reg = allocatable_register_code(i);
	// Skip unnecessarily re-visiting the hinted register, if any.
	if (reg == hinted_reg) continue;
	float max_conflict_weight =
	GetMaximumConflictingWeight(reg, range, competing_weight);
	if (max_conflict_weight == LiveRange::kInvalidWeight) {
	free_reg = reg;
	break;
	}
	if (max_conflict_weight < range->weight() &&
	max_conflict_weight < smallest_weight) {
	smallest_weight = max_conflict_weight;
	evictable_reg = reg;
	}
	}
	}

	// We have a free register, so we use it.
	if (free_reg >= 0) {
	TRACE("Found free register %s for live range %d:%d.\n",
	RegisterName(free_reg), range->TopLevel()->vreg(),
	range->relative_id());
	AssignRangeToRegister(free_reg, range);
	return;
	}

	// We found a register to perform evictions, so we evict and allocate our
	// candidate.
	if (evictable_reg >= 0) {
	TRACE("Found evictable register %s for live range %d:%d.\n",
	RegisterName(free_reg), range->TopLevel()->vreg(),
	range->relative_id());
	EvictAndRescheduleConflicts(evictable_reg, range);
	AssignRangeToRegister(evictable_reg, range);
	return;
	}

	// The range needs to be split or spilled.
	SplitOrSpillBlockedRange(range);
	}


	void GreedyAllocator::EvictAndRescheduleConflicts(unsigned reg_id,
	const LiveRange* range) {
	auto conflicts = current_allocations(reg_id)->GetConflicts(range);
	for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
	conflict = conflicts.RemoveCurrentAndGetNext()) {
	DCHECK(conflict->HasRegisterAssigned());
	CHECK(!conflict->TopLevel()->IsFixed());
	conflict->UnsetAssignedRegister();
	UnsetOperands(conflict, data());
	UpdateWeightAtEviction(conflict);
	scheduler().Schedule(conflict);
	TRACE("Evicted range %d%d.\n", conflict->TopLevel()->vreg(),
	conflict->relative_id());
	}
	}


	void GreedyAllocator::AllocateRegisters() {
	CHECK(scheduler().empty());
	CHECK(allocations_.empty());

	TRACE("Begin allocating function %s with the Greedy Allocator\n",
	data()->debug_name());

	SplitAndSpillRangesDefinedByMemoryOperand(true);
	GroupLiveRanges();
	ScheduleAllocationCandidates();
	PreallocateFixedRanges();
	while (!scheduler().empty()) {
	AllocationCandidate candidate = scheduler().GetNext();
	TryAllocateCandidate(candidate);
	}

	for (size_t i = 0; i < allocations_.size(); ++i) {
	if (!allocations_[i]->empty()) {
	data()->MarkAllocated(mode(), static_cast<int>(i));
	}
	}
	allocations_.clear();

	TryReuseSpillRangesForGroups();

	TRACE("End allocating function %s with the Greedy Allocator\n",
	data()->debug_name());
	}


	void GreedyAllocator::TryReuseSpillRangesForGroups() {
	for (TopLevelLiveRange* top : data()->live_ranges()) {
	if (!CanProcessRange(top) \|\| !top->is_phi() \|\| top->group() == nullptr) {
	continue;
	}

	SpillRange* spill_range = nullptr;
	for (LiveRange* member : top->group()->ranges()) {
	if (!member->TopLevel()->HasSpillRange()) continue;
	SpillRange* member_range = member->TopLevel()->GetSpillRange();
	if (spill_range == nullptr) {
	spill_range = member_range;
	} else {
	// This may not always succeed, because we group non-conflicting ranges
	// that may have been splintered, and the splinters may cause conflicts
	// in the spill ranges.
	// TODO(mtrofin): should the splinters own their own spill ranges?
	spill_range->TryMerge(member_range);
	}
	}
	}
	}


	float GreedyAllocator::GetMaximumConflictingWeight(
	unsigned reg_id, const LiveRange* range, float competing_weight) const {
	float ret = LiveRange::kInvalidWeight;

	auto conflicts = current_allocations(reg_id)->GetConflicts(range);
	for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
	conflict = conflicts.GetNext()) {
	DCHECK_NE(conflict->weight(), LiveRange::kInvalidWeight);
	if (competing_weight <= conflict->weight()) return LiveRange::kMaxWeight;
	ret = Max(ret, conflict->weight());
	DCHECK(ret < LiveRange::kMaxWeight);
	}

	return ret;
	}


	float GreedyAllocator::GetMaximumConflictingWeight(unsigned reg_id,
	const LiveRangeGroup* group,
	float group_weight) const {
	float ret = LiveRange::kInvalidWeight;

	for (LiveRange* member : group->ranges()) {
	float member_conflict_weight =
	GetMaximumConflictingWeight(reg_id, member, group_weight);
	if (member_conflict_weight == LiveRange::kMaxWeight) {
	return LiveRange::kMaxWeight;
	}
	if (member_conflict_weight > group_weight) return LiveRange::kMaxWeight;
	ret = Max(member_conflict_weight, ret);
	}

	return ret;
	}


	void GreedyAllocator::EnsureValidRangeWeight(LiveRange* range) {
	// The live range weight will be invalidated when ranges are created or split.
	// Otherwise, it is consistently updated when the range is allocated or
	// unallocated.
	if (range->weight() != LiveRange::kInvalidWeight) return;

	if (range->TopLevel()->IsFixed()) {
	range->set_weight(LiveRange::kMaxWeight);
	return;
	}
	if (!IsProgressPossible(range)) {
	range->set_weight(LiveRange::kMaxWeight);
	return;
	}

	float use_count = 0.0;
	for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
	++use_count;
	}
	range->set_weight(use_count / static_cast<float>(range->GetSize()));
	}


	void GreedyAllocator::SpillRangeAsLastResort(LiveRange* range) {
	LifetimePosition start = range->Start();
	CHECK(range->CanBeSpilled(start));

	DCHECK(range->NextRegisterPosition(start) == nullptr);
	Spill(range);
	}


	LiveRange* GreedyAllocator::GetRemainderAfterSplittingAroundFirstCall(
	LiveRange* range) {
	LiveRange* ret = range;
	for (UseInterval* interval = range->first_interval(); interval != nullptr;
	interval = interval->next()) {
	LifetimePosition start = interval->start();
	LifetimePosition end = interval->end();
	// If the interval starts at instruction end, then the first instruction
	// in the interval is the next one.
	int first_full_instruction = (start.IsGapPosition() \|\| start.IsStart())
	? start.ToInstructionIndex()
	: start.ToInstructionIndex() + 1;
	// If the interval ends in a gap or at instruction start, then the last
	// instruction is the previous one.
	int last_full_instruction = (end.IsGapPosition() \|\| end.IsStart())
	? end.ToInstructionIndex() - 1
	: end.ToInstructionIndex();

	for (int instruction_index = first_full_instruction;
	instruction_index <= last_full_instruction; ++instruction_index) {
	if (!code()->InstructionAt(instruction_index)->IsCall()) continue;

	LifetimePosition before =
	GetSplitPositionForInstruction(range, instruction_index);
	LiveRange* second_part =
	before.IsValid() ? Split(range, data(), before) : range;

	if (range != second_part) scheduler().Schedule(range);

	LifetimePosition after =
	FindSplitPositionAfterCall(second_part, instruction_index);

	if (after.IsValid()) {
	ret = Split(second_part, data(), after);
	} else {
	ret = nullptr;
	}
	Spill(second_part);
	return ret;
	}
	}
	return ret;
	}


	bool GreedyAllocator::TrySplitAroundCalls(LiveRange* range) {
	bool modified = false;

	while (range != nullptr) {
	LiveRange* remainder = GetRemainderAfterSplittingAroundFirstCall(range);
	// If we performed no modification, we're done.
	if (remainder == range) {
	break;
	}
	// We performed a modification.
	modified = true;
	range = remainder;
	}
	// If we have a remainder and we made modifications, it means the remainder
	// has no calls and we should schedule it for further processing. If we made
	// no modifications, we will just return false, because we want the algorithm
	// to make progress by trying some other heuristic.
	if (modified && range != nullptr) {
	DCHECK(!range->spilled());
	DCHECK(!range->HasRegisterAssigned());
	scheduler().Schedule(range);
	}
	return modified;
	}


	LifetimePosition GreedyAllocator::FindSplitPositionAfterCall(
	const LiveRange* range, int call_index) {
	LifetimePosition after_call =
	Max(range->Start(),
	LifetimePosition::GapFromInstructionIndex(call_index + 1));
	UsePosition* next_use = range->NextRegisterPosition(after_call);
	if (!next_use) return LifetimePosition::Invalid();

	LifetimePosition split_pos = FindOptimalSplitPos(after_call, next_use->pos());
	split_pos =
	GetSplitPositionForInstruction(range, split_pos.ToInstructionIndex());
	return split_pos;
	}


	LifetimePosition GreedyAllocator::FindSplitPositionBeforeLoops(
	LiveRange* range) {
	LifetimePosition end = range->End();
	if (end.ToInstructionIndex() >= code()->LastInstructionIndex()) {
	end =
	LifetimePosition::GapFromInstructionIndex(end.ToInstructionIndex() - 1);
	}
	LifetimePosition pos = FindOptimalSplitPos(range->Start(), end);
	pos = GetSplitPositionForInstruction(range, pos.ToInstructionIndex());
	return pos;
	}


	void GreedyAllocator::SplitOrSpillBlockedRange(LiveRange* range) {
	if (TrySplitAroundCalls(range)) return;

	LifetimePosition pos = FindSplitPositionBeforeLoops(range);

	if (!pos.IsValid()) pos = GetLastResortSplitPosition(range);
	if (pos.IsValid()) {
	LiveRange* tail = Split(range, data(), pos);
	DCHECK(tail != range);
	scheduler().Schedule(tail);
	scheduler().Schedule(range);
	return;
	}
	SpillRangeAsLastResort(range);
	}


	// Basic heuristic for advancing the algorithm, if any other splitting heuristic
	// failed.
	LifetimePosition GreedyAllocator::GetLastResortSplitPosition(
	const LiveRange* range) {
	LifetimePosition previous = range->Start();
	for (UsePosition *pos = range->NextRegisterPosition(previous); pos != nullptr;
	previous = previous.NextFullStart(),
	pos = range->NextRegisterPosition(previous)) {
	LifetimePosition optimal = FindOptimalSplitPos(previous, pos->pos());
	LifetimePosition before =
	GetSplitPositionForInstruction(range, optimal.ToInstructionIndex());
	if (before.IsValid()) return before;
	LifetimePosition after = GetSplitPositionForInstruction(
	range, pos->pos().ToInstructionIndex() + 1);
	if (after.IsValid()) return after;
	}
	return LifetimePosition::Invalid();
	}


	bool GreedyAllocator::IsProgressPossible(const LiveRange* range) {
	return range->CanBeSpilled(range->Start()) \|\|
	GetLastResortSplitPosition(range).IsValid();
	}

	} // namespace compiler
	} // namespace internal
	} // namespace v8