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
CreateSplinter(TopLevelLiveRange * range,RegisterAllocationData * data,LifetimePosition first_cut,LifetimePosition last_cut)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
SplinterLiveRange(TopLevelLiveRange * range,RegisterAllocationData * data)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
Splinter()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
MarkRangesSpilledInDeferredBlocks()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
Merge()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