Home | History | Annotate | Download | only in compiler
      1 // Copyright 2015 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/compiler/greedy-allocator.h"
      6 #include "src/compiler/register-allocator.h"
      7 
      8 namespace v8 {
      9 namespace internal {
     10 namespace compiler {
     11 
     12 
     13 #define TRACE(...)                             \
     14   do {                                         \
     15     if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
     16   } while (false)
     17 
     18 
     19 const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;
     20 
     21 
     22 namespace {
     23 
     24 void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
     25   int reg_id = range->assigned_register();
     26   range->SetUseHints(reg_id);
     27   if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
     28     data->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg_id);
     29   }
     30 }
     31 
     32 
     33 void UnsetOperands(LiveRange* range, RegisterAllocationData* data) {
     34   range->UnsetUseHints();
     35   if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
     36     data->GetPhiMapValueFor(range->TopLevel())->UnsetAssignedRegister();
     37   }
     38 }
     39 
     40 
     41 LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
     42                  LifetimePosition pos) {
     43   DCHECK(range->Start() < pos && pos < range->End());
     44   DCHECK(pos.IsStart() || pos.IsGapPosition() ||
     45          (data->code()
     46               ->GetInstructionBlock(pos.ToInstructionIndex())
     47               ->last_instruction_index() != pos.ToInstructionIndex()));
     48   LiveRange* result = range->SplitAt(pos, data->allocation_zone());
     49   return result;
     50 }
     51 
     52 
     53 }  // namespace
     54 
     55 
     56 AllocationCandidate AllocationScheduler::GetNext() {
     57   DCHECK(!queue_.empty());
     58   AllocationCandidate ret = queue_.top();
     59   queue_.pop();
     60   return ret;
     61 }
     62 
     63 
     64 void AllocationScheduler::Schedule(LiveRange* range) {
     65   TRACE("Scheduling live range %d:%d.\n", range->TopLevel()->vreg(),
     66         range->relative_id());
     67   queue_.push(AllocationCandidate(range));
     68 }
     69 
     70 
     71 void AllocationScheduler::Schedule(LiveRangeGroup* group) {
     72   queue_.push(AllocationCandidate(group));
     73 }
     74 
     75 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
     76                                  RegisterKind kind, Zone* local_zone)
     77     : RegisterAllocator(data, kind),
     78       local_zone_(local_zone),
     79       allocations_(local_zone),
     80       scheduler_(local_zone),
     81       groups_(local_zone) {}
     82 
     83 
     84 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
     85   TRACE("Assigning register %s to live range %d:%d\n", RegisterName(reg_id),
     86         range->TopLevel()->vreg(), range->relative_id());
     87 
     88   DCHECK(!range->HasRegisterAssigned());
     89 
     90   AllocateRegisterToRange(reg_id, range);
     91 
     92   TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
     93         range->TopLevel()->vreg(), range->relative_id());
     94   range->set_assigned_register(reg_id);
     95   UpdateOperands(range, data());
     96 }
     97 
     98 
     99 void GreedyAllocator::PreallocateFixedRanges() {
    100   allocations_.resize(num_registers());
    101   for (int i = 0; i < num_registers(); i++) {
    102     allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_zone());
    103   }
    104 
    105   for (LiveRange* fixed_range : GetFixedRegisters()) {
    106     if (fixed_range != nullptr) {
    107       DCHECK_EQ(mode(), fixed_range->kind());
    108       DCHECK(fixed_range->TopLevel()->IsFixed());
    109 
    110       int reg_nr = fixed_range->assigned_register();
    111       EnsureValidRangeWeight(fixed_range);
    112       AllocateRegisterToRange(reg_nr, fixed_range);
    113     }
    114   }
    115 }
    116 
    117 
    118 void GreedyAllocator::GroupLiveRanges() {
    119   CoalescedLiveRanges grouper(local_zone());
    120   for (TopLevelLiveRange* range : data()->live_ranges()) {
    121     grouper.clear();
    122     // Skip splinters, because we do not want to optimize for them, and moves
    123     // due to assigning them to different registers occur in deferred blocks.
    124     if (!CanProcessRange(range) || range->IsSplinter() || !range->is_phi()) {
    125       continue;
    126     }
    127 
    128     // A phi can't be a memory operand, so it couldn't have been split.
    129     DCHECK(!range->spilled());
    130 
    131     // Maybe this phi range is itself an input to another phi which was already
    132     // processed.
    133     LiveRangeGroup* latest_grp = range->group() != nullptr
    134                                      ? range->group()
    135                                      : new (local_zone())
    136                                            LiveRangeGroup(local_zone());
    137 
    138     // Populate the grouper.
    139     if (range->group() == nullptr) {
    140       grouper.AllocateRange(range);
    141     } else {
    142       for (LiveRange* member : range->group()->ranges()) {
    143         grouper.AllocateRange(member);
    144       }
    145     }
    146     for (int j : data()->GetPhiMapValueFor(range)->phi()->operands()) {
    147       // skip output also in input, which may happen for loops.
    148       if (j == range->vreg()) continue;
    149 
    150       TopLevelLiveRange* other_top = data()->live_ranges()[j];
    151 
    152       if (other_top->IsSplinter()) continue;
    153       // If the other was a memory operand, it might have been split.
    154       // So get the unsplit part.
    155       LiveRange* other =
    156           other_top->next() == nullptr ? other_top : other_top->next();
    157 
    158       if (other->spilled()) continue;
    159 
    160       LiveRangeGroup* other_group = other->group();
    161       if (other_group != nullptr) {
    162         bool can_merge = true;
    163         for (LiveRange* member : other_group->ranges()) {
    164           if (grouper.GetConflicts(member).Current() != nullptr) {
    165             can_merge = false;
    166             break;
    167           }
    168         }
    169         // If each member doesn't conflict with the current group, then since
    170         // the members don't conflict with eachother either, we can merge them.
    171         if (can_merge) {
    172           latest_grp->ranges().insert(latest_grp->ranges().end(),
    173                                       other_group->ranges().begin(),
    174                                       other_group->ranges().end());
    175           for (LiveRange* member : other_group->ranges()) {
    176             grouper.AllocateRange(member);
    177             member->set_group(latest_grp);
    178           }
    179           // Clear the other range, so we avoid scheduling it.
    180           other_group->ranges().clear();
    181         }
    182       } else if (grouper.GetConflicts(other).Current() == nullptr) {
    183         grouper.AllocateRange(other);
    184         latest_grp->ranges().push_back(other);
    185         other->set_group(latest_grp);
    186       }
    187     }
    188 
    189     if (latest_grp->ranges().size() > 0 && range->group() == nullptr) {
    190       latest_grp->ranges().push_back(range);
    191       DCHECK(latest_grp->ranges().size() > 1);
    192       groups().push_back(latest_grp);
    193       range->set_group(latest_grp);
    194     }
    195   }
    196 }
    197 
    198 
    199 void GreedyAllocator::ScheduleAllocationCandidates() {
    200   for (LiveRangeGroup* group : groups()) {
    201     if (group->ranges().size() > 0) {
    202       // We shouldn't have added single-range groups.
    203       DCHECK(group->ranges().size() != 1);
    204       scheduler().Schedule(group);
    205     }
    206   }
    207   for (LiveRange* range : data()->live_ranges()) {
    208     if (CanProcessRange(range)) {
    209       for (LiveRange* child = range; child != nullptr; child = child->next()) {
    210         if (!child->spilled() && child->group() == nullptr) {
    211           scheduler().Schedule(child);
    212         }
    213       }
    214     }
    215   }
    216 }
    217 
    218 
    219 void GreedyAllocator::TryAllocateCandidate(
    220     const AllocationCandidate& candidate) {
    221   if (candidate.is_group()) {
    222     TryAllocateGroup(candidate.group());
    223   } else {
    224     TryAllocateLiveRange(candidate.live_range());
    225   }
    226 }
    227 
    228 
    229 void GreedyAllocator::TryAllocateGroup(LiveRangeGroup* group) {
    230   float group_weight = 0.0;
    231   for (LiveRange* member : group->ranges()) {
    232     EnsureValidRangeWeight(member);
    233     group_weight = Max(group_weight, member->weight());
    234   }
    235 
    236   float eviction_weight = group_weight;
    237   int eviction_reg = -1;
    238   int free_reg = -1;
    239   for (int i = 0; i < num_allocatable_registers(); ++i) {
    240     int reg = allocatable_register_code(i);
    241     float weight = GetMaximumConflictingWeight(reg, group, group_weight);
    242     if (weight == LiveRange::kInvalidWeight) {
    243       free_reg = reg;
    244       break;
    245     }
    246     if (weight < eviction_weight) {
    247       eviction_weight = weight;
    248       eviction_reg = reg;
    249     }
    250   }
    251   if (eviction_reg < 0 && free_reg < 0) {
    252     for (LiveRange* member : group->ranges()) {
    253       scheduler().Schedule(member);
    254     }
    255     return;
    256   }
    257   if (free_reg < 0) {
    258     DCHECK(eviction_reg >= 0);
    259     for (LiveRange* member : group->ranges()) {
    260       EvictAndRescheduleConflicts(eviction_reg, member);
    261     }
    262     free_reg = eviction_reg;
    263   }
    264 
    265   DCHECK(free_reg >= 0);
    266   for (LiveRange* member : group->ranges()) {
    267     AssignRangeToRegister(free_reg, member);
    268   }
    269 }
    270 
    271 
    272 void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
    273   // TODO(mtrofin): once we introduce groups, we'll want to first try and
    274   // allocate at the preferred register.
    275   TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
    276         range->relative_id());
    277   int free_reg = -1;
    278   int evictable_reg = -1;
    279   int hinted_reg = -1;
    280 
    281   EnsureValidRangeWeight(range);
    282   float competing_weight = range->weight();
    283   DCHECK(competing_weight != LiveRange::kInvalidWeight);
    284 
    285   // Can we allocate at the hinted register?
    286   if (range->FirstHintPosition(&hinted_reg) != nullptr) {
    287     DCHECK(hinted_reg >= 0);
    288     float max_conflict_weight =
    289         GetMaximumConflictingWeight(hinted_reg, range, competing_weight);
    290     if (max_conflict_weight == LiveRange::kInvalidWeight) {
    291       free_reg = hinted_reg;
    292     } else if (max_conflict_weight < range->weight()) {
    293       evictable_reg = hinted_reg;
    294     }
    295   }
    296 
    297   if (free_reg < 0 && evictable_reg < 0) {
    298     // There was no hinted reg, or we cannot allocate there.
    299     float smallest_weight = LiveRange::kMaxWeight;
    300 
    301     // Seek either the first free register, or, from the set of registers
    302     // where the maximum conflict is lower than the candidate's weight, the one
    303     // with the smallest such weight.
    304     for (int i = 0; i < num_allocatable_registers(); i++) {
    305       int reg = allocatable_register_code(i);
    306       // Skip unnecessarily re-visiting the hinted register, if any.
    307       if (reg == hinted_reg) continue;
    308       float max_conflict_weight =
    309           GetMaximumConflictingWeight(reg, range, competing_weight);
    310       if (max_conflict_weight == LiveRange::kInvalidWeight) {
    311         free_reg = reg;
    312         break;
    313       }
    314       if (max_conflict_weight < range->weight() &&
    315           max_conflict_weight < smallest_weight) {
    316         smallest_weight = max_conflict_weight;
    317         evictable_reg = reg;
    318       }
    319     }
    320   }
    321 
    322   // We have a free register, so we use it.
    323   if (free_reg >= 0) {
    324     TRACE("Found free register %s for live range %d:%d.\n",
    325           RegisterName(free_reg), range->TopLevel()->vreg(),
    326           range->relative_id());
    327     AssignRangeToRegister(free_reg, range);
    328     return;
    329   }
    330 
    331   // We found a register to perform evictions, so we evict and allocate our
    332   // candidate.
    333   if (evictable_reg >= 0) {
    334     TRACE("Found evictable register %s for live range %d:%d.\n",
    335           RegisterName(free_reg), range->TopLevel()->vreg(),
    336           range->relative_id());
    337     EvictAndRescheduleConflicts(evictable_reg, range);
    338     AssignRangeToRegister(evictable_reg, range);
    339     return;
    340   }
    341 
    342   // The range needs to be split or spilled.
    343   SplitOrSpillBlockedRange(range);
    344 }
    345 
    346 
    347 void GreedyAllocator::EvictAndRescheduleConflicts(unsigned reg_id,
    348                                                   const LiveRange* range) {
    349   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
    350   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
    351        conflict = conflicts.RemoveCurrentAndGetNext()) {
    352     DCHECK(conflict->HasRegisterAssigned());
    353     CHECK(!conflict->TopLevel()->IsFixed());
    354     conflict->UnsetAssignedRegister();
    355     UnsetOperands(conflict, data());
    356     UpdateWeightAtEviction(conflict);
    357     scheduler().Schedule(conflict);
    358     TRACE("Evicted range %d%d.\n", conflict->TopLevel()->vreg(),
    359           conflict->relative_id());
    360   }
    361 }
    362 
    363 
    364 void GreedyAllocator::AllocateRegisters() {
    365   CHECK(scheduler().empty());
    366   CHECK(allocations_.empty());
    367 
    368   TRACE("Begin allocating function %s with the Greedy Allocator\n",
    369         data()->debug_name());
    370 
    371   SplitAndSpillRangesDefinedByMemoryOperand(true);
    372   GroupLiveRanges();
    373   ScheduleAllocationCandidates();
    374   PreallocateFixedRanges();
    375   while (!scheduler().empty()) {
    376     AllocationCandidate candidate = scheduler().GetNext();
    377     TryAllocateCandidate(candidate);
    378   }
    379 
    380   for (size_t i = 0; i < allocations_.size(); ++i) {
    381     if (!allocations_[i]->empty()) {
    382       data()->MarkAllocated(mode(), static_cast<int>(i));
    383     }
    384   }
    385   allocations_.clear();
    386 
    387   TryReuseSpillRangesForGroups();
    388 
    389   TRACE("End allocating function %s with the Greedy Allocator\n",
    390         data()->debug_name());
    391 }
    392 
    393 
    394 void GreedyAllocator::TryReuseSpillRangesForGroups() {
    395   for (TopLevelLiveRange* top : data()->live_ranges()) {
    396     if (!CanProcessRange(top) || !top->is_phi() || top->group() == nullptr) {
    397       continue;
    398     }
    399 
    400     SpillRange* spill_range = nullptr;
    401     for (LiveRange* member : top->group()->ranges()) {
    402       if (!member->TopLevel()->HasSpillRange()) continue;
    403       SpillRange* member_range = member->TopLevel()->GetSpillRange();
    404       if (spill_range == nullptr) {
    405         spill_range = member_range;
    406       } else {
    407         // This may not always succeed, because we group non-conflicting ranges
    408         // that may have been splintered, and the splinters may cause conflicts
    409         // in the spill ranges.
    410         // TODO(mtrofin): should the splinters own their own spill ranges?
    411         spill_range->TryMerge(member_range);
    412       }
    413     }
    414   }
    415 }
    416 
    417 
    418 float GreedyAllocator::GetMaximumConflictingWeight(
    419     unsigned reg_id, const LiveRange* range, float competing_weight) const {
    420   float ret = LiveRange::kInvalidWeight;
    421 
    422   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
    423   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
    424        conflict = conflicts.GetNext()) {
    425     DCHECK_NE(conflict->weight(), LiveRange::kInvalidWeight);
    426     if (competing_weight <= conflict->weight()) return LiveRange::kMaxWeight;
    427     ret = Max(ret, conflict->weight());
    428     DCHECK(ret < LiveRange::kMaxWeight);
    429   }
    430 
    431   return ret;
    432 }
    433 
    434 
    435 float GreedyAllocator::GetMaximumConflictingWeight(unsigned reg_id,
    436                                                    const LiveRangeGroup* group,
    437                                                    float group_weight) const {
    438   float ret = LiveRange::kInvalidWeight;
    439 
    440   for (LiveRange* member : group->ranges()) {
    441     float member_conflict_weight =
    442         GetMaximumConflictingWeight(reg_id, member, group_weight);
    443     if (member_conflict_weight == LiveRange::kMaxWeight) {
    444       return LiveRange::kMaxWeight;
    445     }
    446     if (member_conflict_weight > group_weight) return LiveRange::kMaxWeight;
    447     ret = Max(member_conflict_weight, ret);
    448   }
    449 
    450   return ret;
    451 }
    452 
    453 
    454 void GreedyAllocator::EnsureValidRangeWeight(LiveRange* range) {
    455   // The live range weight will be invalidated when ranges are created or split.
    456   // Otherwise, it is consistently updated when the range is allocated or
    457   // unallocated.
    458   if (range->weight() != LiveRange::kInvalidWeight) return;
    459 
    460   if (range->TopLevel()->IsFixed()) {
    461     range->set_weight(LiveRange::kMaxWeight);
    462     return;
    463   }
    464   if (!IsProgressPossible(range)) {
    465     range->set_weight(LiveRange::kMaxWeight);
    466     return;
    467   }
    468 
    469   float use_count = 0.0;
    470   for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
    471     ++use_count;
    472   }
    473   range->set_weight(use_count / static_cast<float>(range->GetSize()));
    474 }
    475 
    476 
    477 void GreedyAllocator::SpillRangeAsLastResort(LiveRange* range) {
    478   LifetimePosition start = range->Start();
    479   CHECK(range->CanBeSpilled(start));
    480 
    481   DCHECK(range->NextRegisterPosition(start) == nullptr);
    482   Spill(range);
    483 }
    484 
    485 
    486 LiveRange* GreedyAllocator::GetRemainderAfterSplittingAroundFirstCall(
    487     LiveRange* range) {
    488   LiveRange* ret = range;
    489   for (UseInterval* interval = range->first_interval(); interval != nullptr;
    490        interval = interval->next()) {
    491     LifetimePosition start = interval->start();
    492     LifetimePosition end = interval->end();
    493     // If the interval starts at instruction end, then the first instruction
    494     // in the interval is the next one.
    495     int first_full_instruction = (start.IsGapPosition() || start.IsStart())
    496                                      ? start.ToInstructionIndex()
    497                                      : start.ToInstructionIndex() + 1;
    498     // If the interval ends in a gap or at instruction start, then the last
    499     // instruction is the previous one.
    500     int last_full_instruction = (end.IsGapPosition() || end.IsStart())
    501                                     ? end.ToInstructionIndex() - 1
    502                                     : end.ToInstructionIndex();
    503 
    504     for (int instruction_index = first_full_instruction;
    505          instruction_index <= last_full_instruction; ++instruction_index) {
    506       if (!code()->InstructionAt(instruction_index)->IsCall()) continue;
    507 
    508       LifetimePosition before =
    509           GetSplitPositionForInstruction(range, instruction_index);
    510       LiveRange* second_part =
    511           before.IsValid() ? Split(range, data(), before) : range;
    512 
    513       if (range != second_part) scheduler().Schedule(range);
    514 
    515       LifetimePosition after =
    516           FindSplitPositionAfterCall(second_part, instruction_index);
    517 
    518       if (after.IsValid()) {
    519         ret = Split(second_part, data(), after);
    520       } else {
    521         ret = nullptr;
    522       }
    523       Spill(second_part);
    524       return ret;
    525     }
    526   }
    527   return ret;
    528 }
    529 
    530 
    531 bool GreedyAllocator::TrySplitAroundCalls(LiveRange* range) {
    532   bool modified = false;
    533 
    534   while (range != nullptr) {
    535     LiveRange* remainder = GetRemainderAfterSplittingAroundFirstCall(range);
    536     // If we performed no modification, we're done.
    537     if (remainder == range) {
    538       break;
    539     }
    540     // We performed a modification.
    541     modified = true;
    542     range = remainder;
    543   }
    544   // If we have a remainder and we made modifications, it means the remainder
    545   // has no calls and we should schedule it for further processing. If we made
    546   // no modifications, we will just return false, because we want the algorithm
    547   // to make progress by trying some other heuristic.
    548   if (modified && range != nullptr) {
    549     DCHECK(!range->spilled());
    550     DCHECK(!range->HasRegisterAssigned());
    551     scheduler().Schedule(range);
    552   }
    553   return modified;
    554 }
    555 
    556 
    557 LifetimePosition GreedyAllocator::FindSplitPositionAfterCall(
    558     const LiveRange* range, int call_index) {
    559   LifetimePosition after_call =
    560       Max(range->Start(),
    561           LifetimePosition::GapFromInstructionIndex(call_index + 1));
    562   UsePosition* next_use = range->NextRegisterPosition(after_call);
    563   if (!next_use) return LifetimePosition::Invalid();
    564 
    565   LifetimePosition split_pos = FindOptimalSplitPos(after_call, next_use->pos());
    566   split_pos =
    567       GetSplitPositionForInstruction(range, split_pos.ToInstructionIndex());
    568   return split_pos;
    569 }
    570 
    571 
    572 LifetimePosition GreedyAllocator::FindSplitPositionBeforeLoops(
    573     LiveRange* range) {
    574   LifetimePosition end = range->End();
    575   if (end.ToInstructionIndex() >= code()->LastInstructionIndex()) {
    576     end =
    577         LifetimePosition::GapFromInstructionIndex(end.ToInstructionIndex() - 1);
    578   }
    579   LifetimePosition pos = FindOptimalSplitPos(range->Start(), end);
    580   pos = GetSplitPositionForInstruction(range, pos.ToInstructionIndex());
    581   return pos;
    582 }
    583 
    584 
    585 void GreedyAllocator::SplitOrSpillBlockedRange(LiveRange* range) {
    586   if (TrySplitAroundCalls(range)) return;
    587 
    588   LifetimePosition pos = FindSplitPositionBeforeLoops(range);
    589 
    590   if (!pos.IsValid()) pos = GetLastResortSplitPosition(range);
    591   if (pos.IsValid()) {
    592     LiveRange* tail = Split(range, data(), pos);
    593     DCHECK(tail != range);
    594     scheduler().Schedule(tail);
    595     scheduler().Schedule(range);
    596     return;
    597   }
    598   SpillRangeAsLastResort(range);
    599 }
    600 
    601 
    602 // Basic heuristic for advancing the algorithm, if any other splitting heuristic
    603 // failed.
    604 LifetimePosition GreedyAllocator::GetLastResortSplitPosition(
    605     const LiveRange* range) {
    606   LifetimePosition previous = range->Start();
    607   for (UsePosition *pos = range->NextRegisterPosition(previous); pos != nullptr;
    608        previous = previous.NextFullStart(),
    609                    pos = range->NextRegisterPosition(previous)) {
    610     LifetimePosition optimal = FindOptimalSplitPos(previous, pos->pos());
    611     LifetimePosition before =
    612         GetSplitPositionForInstruction(range, optimal.ToInstructionIndex());
    613     if (before.IsValid()) return before;
    614     LifetimePosition after = GetSplitPositionForInstruction(
    615         range, pos->pos().ToInstructionIndex() + 1);
    616     if (after.IsValid()) return after;
    617   }
    618   return LifetimePosition::Invalid();
    619 }
    620 
    621 
    622 bool GreedyAllocator::IsProgressPossible(const LiveRange* range) {
    623   return range->CanBeSpilled(range->Start()) ||
    624          GetLastResortSplitPosition(range).IsValid();
    625 }
    626 
    627 }  // namespace compiler
    628 }  // namespace internal
    629 }  // namespace v8
    630