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   for (TopLevelLiveRange *top : data()->live_ranges()) {
    123     if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr) {
    124       continue;
    125     }
    126 
    127     LiveRange *child = top;
    128     for (; child != nullptr; child = child->next()) {
    129       if (child->spilled() ||
    130           child->NextSlotPosition(child->Start()) != nullptr) {
    131         break;
    132       }
    133     }
    134     if (child == nullptr) top->MarkSpilledInDeferredBlock();
    135   }
    136 }
    137 
    138 
    139 void LiveRangeMerger::Merge() {
    140   MarkRangesSpilledInDeferredBlocks();
    141 
    142   int live_range_count = static_cast<int>(data()->live_ranges().size());
    143   for (int i = 0; i < live_range_count; ++i) {
    144     TopLevelLiveRange *range = data()->live_ranges()[i];
    145     if (range == nullptr || range->IsEmpty() || !range->IsSplinter()) {
    146       continue;
    147     }
    148     TopLevelLiveRange *splinter_parent = range->splintered_from();
    149 
    150     int to_remove = range->vreg();
    151     splinter_parent->Merge(range, data()->allocation_zone());
    152     data()->live_ranges()[to_remove] = nullptr;
    153   }
    154 }
    155 
    156 
    157 }  // namespace compiler
    158 }  // namespace internal
    159 }  // namespace v8
    160