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
SetSlotUse(TopLevelLiveRange * range)61 void SetSlotUse(TopLevelLiveRange *range) {
62 range->set_has_slot_use(false);
63 for (const UsePosition *pos = range->first_pos();
64 !range->has_slot_use() && pos != nullptr; pos = pos->next()) {
65 if (pos->type() == UsePositionType::kRequiresSlot) {
66 range->set_has_slot_use(true);
67 }
68 }
69 }
70
SplinterLiveRange(TopLevelLiveRange * range,RegisterAllocationData * data)71 void SplinterLiveRange(TopLevelLiveRange *range, RegisterAllocationData *data) {
72 const InstructionSequence *code = data->code();
73 UseInterval *interval = range->first_interval();
74
75 LifetimePosition first_cut = LifetimePosition::Invalid();
76 LifetimePosition last_cut = LifetimePosition::Invalid();
77
78 while (interval != nullptr) {
79 UseInterval *next_interval = interval->next();
80 const InstructionBlock *first_block =
81 code->GetInstructionBlock(interval->FirstGapIndex());
82 const InstructionBlock *last_block =
83 code->GetInstructionBlock(interval->LastGapIndex());
84 int first_block_nr = first_block->rpo_number().ToInt();
85 int last_block_nr = last_block->rpo_number().ToInt();
86 for (int block_id = first_block_nr; block_id <= last_block_nr; ++block_id) {
87 const InstructionBlock *current_block =
88 code->InstructionBlockAt(RpoNumber::FromInt(block_id));
89 if (current_block->IsDeferred()) {
90 if (!first_cut.IsValid()) {
91 first_cut = LifetimePosition::GapFromInstructionIndex(
92 current_block->first_instruction_index());
93 }
94 last_cut = LifetimePosition::GapFromInstructionIndex(
95 current_block->last_instruction_index());
96 } else {
97 if (first_cut.IsValid()) {
98 CreateSplinter(range, data, first_cut, last_cut);
99 first_cut = LifetimePosition::Invalid();
100 last_cut = LifetimePosition::Invalid();
101 }
102 }
103 }
104 interval = next_interval;
105 }
106 // When the range ends in deferred blocks, first_cut will be valid here.
107 // Splinter from there to the last instruction that was in a deferred block.
108 if (first_cut.IsValid()) {
109 CreateSplinter(range, data, first_cut, last_cut);
110 }
111
112 // Redo has_slot_use
113 if (range->has_slot_use() && range->splinter() != nullptr) {
114 SetSlotUse(range);
115 SetSlotUse(range->splinter());
116 }
117 }
118
119 } // namespace
120
121
Splinter()122 void LiveRangeSeparator::Splinter() {
123 size_t virt_reg_count = data()->live_ranges().size();
124 for (size_t vreg = 0; vreg < virt_reg_count; ++vreg) {
125 TopLevelLiveRange *range = data()->live_ranges()[vreg];
126 if (range == nullptr || range->IsEmpty() || range->IsSplinter()) {
127 continue;
128 }
129 int first_instr = range->first_interval()->FirstGapIndex();
130 if (!data()->code()->GetInstructionBlock(first_instr)->IsDeferred()) {
131 SplinterLiveRange(range, data());
132 }
133 }
134 }
135
136
MarkRangesSpilledInDeferredBlocks()137 void LiveRangeMerger::MarkRangesSpilledInDeferredBlocks() {
138 const InstructionSequence *code = data()->code();
139 for (TopLevelLiveRange *top : data()->live_ranges()) {
140 if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr ||
141 top->HasSpillOperand() || !top->splinter()->HasSpillRange()) {
142 continue;
143 }
144
145 LiveRange *child = top;
146 for (; child != nullptr; child = child->next()) {
147 if (child->spilled() ||
148 child->NextSlotPosition(child->Start()) != nullptr) {
149 break;
150 }
151 }
152 if (child == nullptr) {
153 top->TreatAsSpilledInDeferredBlock(data()->allocation_zone(),
154 code->InstructionBlockCount());
155 }
156 }
157 }
158
159
Merge()160 void LiveRangeMerger::Merge() {
161 MarkRangesSpilledInDeferredBlocks();
162
163 int live_range_count = static_cast<int>(data()->live_ranges().size());
164 for (int i = 0; i < live_range_count; ++i) {
165 TopLevelLiveRange *range = data()->live_ranges()[i];
166 if (range == nullptr || range->IsEmpty() || !range->IsSplinter()) {
167 continue;
168 }
169 TopLevelLiveRange *splinter_parent = range->splintered_from();
170
171 int to_remove = range->vreg();
172 splinter_parent->Merge(range, data()->allocation_zone());
173 data()->live_ranges()[to_remove] = nullptr;
174 }
175 }
176
177 #undef TRACE
178
179 } // namespace compiler
180 } // namespace internal
181 } // namespace v8
182