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/live-range-separator.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 namespace {
     20 
     21 
     22 void CreateSplinter(TopLevelLiveRange *range, RegisterAllocationData *data,
     23                     LifetimePosition first_cut, LifetimePosition last_cut) {
     24   DCHECK(!range->IsSplinter());
     25   // We can ignore ranges that live solely in deferred blocks.
     26   // If a range ends right at the end of a deferred block, it is marked by
     27   // the range builder as ending at gap start of the next block - since the
     28   // end is a position where the variable isn't live. We need to take that
     29   // into consideration.
     30   LifetimePosition max_allowed_end = last_cut.NextFullStart();
     31 
     32   if (first_cut <= range->Start() && max_allowed_end >= range->End()) {
     33     return;
     34   }
     35 
     36   LifetimePosition start = Max(first_cut, range->Start());
     37   LifetimePosition end = Min(last_cut, range->End());
     38 
     39   if (start < end) {
     40     // Ensure the original range has a spill range associated, before it gets
     41     // splintered. Splinters will point to it. This way, when attempting to
     42     // reuse spill slots of splinters, during allocation, we avoid clobbering
     43     // such slots.
     44     if (range->MayRequireSpillRange()) {
     45       data->CreateSpillRangeForLiveRange(range);
     46     }
     47     if (range->splinter() == nullptr) {
     48       TopLevelLiveRange *splinter =
     49           data->NextLiveRange(range->representation());
     50       DCHECK_NULL(data->live_ranges()[splinter->vreg()]);
     51       data->live_ranges()[splinter->vreg()] = splinter;
     52       range->SetSplinter(splinter);
     53     }
     54     Zone *zone = data->allocation_zone();
     55     TRACE("creating splinter for range %d between %d and %d\n", range->vreg(),
     56           start.ToInstructionIndex(), end.ToInstructionIndex());
     57     range->Splinter(start, end, zone);
     58   }
     59 }
     60 
     61 
     62 void SplinterLiveRange(TopLevelLiveRange *range, RegisterAllocationData *data) {
     63   const InstructionSequence *code = data->code();
     64   UseInterval *interval = range->first_interval();
     65 
     66   LifetimePosition first_cut = LifetimePosition::Invalid();
     67   LifetimePosition last_cut = LifetimePosition::Invalid();
     68 
     69   while (interval != nullptr) {
     70     UseInterval *next_interval = interval->next();
     71     const InstructionBlock *first_block =
     72         code->GetInstructionBlock(interval->FirstGapIndex());
     73     const InstructionBlock *last_block =
     74         code->GetInstructionBlock(interval->LastGapIndex());
     75     int first_block_nr = first_block->rpo_number().ToInt();
     76     int last_block_nr = last_block->rpo_number().ToInt();
     77     for (int block_id = first_block_nr; block_id <= last_block_nr; ++block_id) {
     78       const InstructionBlock *current_block =
     79           code->InstructionBlockAt(RpoNumber::FromInt(block_id));
     80       if (current_block->IsDeferred()) {
     81         if (!first_cut.IsValid()) {
     82           first_cut = LifetimePosition::GapFromInstructionIndex(
     83               current_block->first_instruction_index());
     84         }
     85         last_cut = LifetimePosition::GapFromInstructionIndex(
     86             current_block->last_instruction_index());
     87       } else {
     88         if (first_cut.IsValid()) {
     89           CreateSplinter(range, data, first_cut, last_cut);
     90           first_cut = LifetimePosition::Invalid();
     91           last_cut = LifetimePosition::Invalid();
     92         }
     93       }
     94     }
     95     interval = next_interval;
     96   }
     97   // When the range ends in deferred blocks, first_cut will be valid here.
     98   // Splinter from there to the last instruction that was in a deferred block.
     99   if (first_cut.IsValid()) {
    100     CreateSplinter(range, data, first_cut, last_cut);
    101   }
    102 }
    103 }  // namespace
    104 
    105 
    106 void LiveRangeSeparator::Splinter() {
    107   size_t virt_reg_count = data()->live_ranges().size();
    108   for (size_t vreg = 0; vreg < virt_reg_count; ++vreg) {
    109     TopLevelLiveRange *range = data()->live_ranges()[vreg];
    110     if (range == nullptr || range->IsEmpty() || range->IsSplinter()) {
    111       continue;
    112     }
    113     int first_instr = range->first_interval()->FirstGapIndex();
    114     if (!data()->code()->GetInstructionBlock(first_instr)->IsDeferred()) {
    115       SplinterLiveRange(range, data());
    116     }
    117   }
    118 }
    119 
    120 
    121 void LiveRangeMerger::MarkRangesSpilledInDeferredBlocks() {
    122   const InstructionSequence *code = data()->code();
    123   for (TopLevelLiveRange *top : data()->live_ranges()) {
    124     if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr ||
    125         top->HasSpillOperand() || !top->splinter()->HasSpillRange()) {
    126       continue;
    127     }
    128 
    129     LiveRange *child = top;
    130     for (; child != nullptr; child = child->next()) {
    131       if (child->spilled() ||
    132           child->NextSlotPosition(child->Start()) != nullptr) {
    133         break;
    134       }
    135     }
    136     if (child == nullptr) {
    137       top->TreatAsSpilledInDeferredBlock(data()->allocation_zone(),
    138                                          code->InstructionBlockCount());
    139     }
    140   }
    141 }
    142 
    143 
    144 void LiveRangeMerger::Merge() {
    145   MarkRangesSpilledInDeferredBlocks();
    146 
    147   int live_range_count = static_cast<int>(data()->live_ranges().size());
    148   for (int i = 0; i < live_range_count; ++i) {
    149     TopLevelLiveRange *range = data()->live_ranges()[i];
    150     if (range == nullptr || range->IsEmpty() || !range->IsSplinter()) {
    151       continue;
    152     }
    153     TopLevelLiveRange *splinter_parent = range->splintered_from();
    154 
    155     int to_remove = range->vreg();
    156     splinter_parent->Merge(range, data()->allocation_zone());
    157     data()->live_ranges()[to_remove] = nullptr;
    158   }
    159 }
    160 
    161 
    162 }  // namespace compiler
    163 }  // namespace internal
    164 }  // namespace v8
    165