Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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() { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 122 | const InstructionSequence *code = data()->code(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 123 | for (TopLevelLiveRange *top : data()->live_ranges()) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 124 | if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr || |
| 125 | top->HasSpillOperand() || !top->splinter()->HasSpillRange()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 136 | if (child == nullptr) { |
| 137 | top->TreatAsSpilledInDeferredBlock(data()->allocation_zone(), |
| 138 | code->InstructionBlockCount()); |
| 139 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 |