Line data Source code
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/backend/live-range-separator.h"
6 : #include "src/compiler/backend/register-allocator.h"
7 :
8 : namespace v8 {
9 : namespace internal {
10 : namespace compiler {
11 :
12 : #define TRACE(...) \
13 : do { \
14 : if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
15 : } while (false)
16 :
17 : namespace {
18 :
19 38808068 : void CreateSplinter(TopLevelLiveRange* range, RegisterAllocationData* data,
20 : LifetimePosition first_cut, LifetimePosition last_cut) {
21 : DCHECK(!range->IsSplinter());
22 : // We can ignore ranges that live solely in deferred blocks.
23 : // If a range ends right at the end of a deferred block, it is marked by
24 : // the range builder as ending at gap start of the next block - since the
25 : // end is a position where the variable isn't live. We need to take that
26 : // into consideration.
27 : LifetimePosition max_allowed_end = last_cut.NextFullStart();
28 :
29 36642546 : if (first_cut <= range->Start() && max_allowed_end >= range->End()) {
30 16027221 : return;
31 : }
32 :
33 : LifetimePosition start = Max(first_cut, range->Start());
34 : LifetimePosition end = Min(last_cut, range->End());
35 :
36 16027088 : if (start < end) {
37 : // Ensure the original range has a spill range associated, before it gets
38 : // splintered. Splinters will point to it. This way, when attempting to
39 : // reuse spill slots of splinters, during allocation, we avoid clobbering
40 : // such slots.
41 11390447 : if (range->MayRequireSpillRange()) {
42 1590554 : data->CreateSpillRangeForLiveRange(range);
43 : }
44 11390513 : if (range->splinter() == nullptr) {
45 4588340 : TopLevelLiveRange* splinter =
46 4588403 : data->NextLiveRange(range->representation());
47 : DCHECK_NULL(data->live_ranges()[splinter->vreg()]);
48 9176680 : data->live_ranges()[splinter->vreg()] = splinter;
49 4588340 : range->SetSplinter(splinter);
50 : }
51 : Zone* zone = data->allocation_zone();
52 11390500 : TRACE("creating splinter for range %d between %d and %d\n", range->vreg(),
53 : start.ToInstructionIndex(), end.ToInstructionIndex());
54 11390500 : range->Splinter(start, end, zone);
55 : }
56 : }
57 :
58 12734250 : void SetSlotUse(TopLevelLiveRange* range) {
59 : range->set_has_slot_use(false);
60 19030834 : for (const UsePosition* pos = range->first_pos();
61 9515417 : !range->has_slot_use() && pos != nullptr; pos = pos->next()) {
62 6296584 : if (pos->type() == UsePositionType::kRequiresSlot) {
63 : range->set_has_slot_use(true);
64 : }
65 : }
66 3218833 : }
67 :
68 67327343 : void SplinterLiveRange(TopLevelLiveRange* range, RegisterAllocationData* data) {
69 157506855 : const InstructionSequence* code = data->code();
70 71090422 : UseInterval* interval = range->first_interval();
71 :
72 : LifetimePosition first_cut = LifetimePosition::Invalid();
73 31911720 : LifetimePosition last_cut = LifetimePosition::Invalid();
74 :
75 103001822 : while (interval != nullptr) {
76 : UseInterval* next_interval = interval->next();
77 : const InstructionBlock* first_block =
78 39178702 : code->GetInstructionBlock(interval->FirstGapIndex());
79 : const InstructionBlock* last_block =
80 39178772 : code->GetInstructionBlock(interval->LastGapIndex());
81 : int first_block_nr = first_block->rpo_number().ToInt();
82 : int last_block_nr = last_block->rpo_number().ToInt();
83 196685237 : for (int block_id = first_block_nr; block_id <= last_block_nr; ++block_id) {
84 211313329 : const InstructionBlock* current_block =
85 157506855 : code->InstructionBlockAt(RpoNumber::FromInt(block_id));
86 157506260 : if (current_block->IsDeferred()) {
87 37779869 : if (!first_cut.IsValid()) {
88 : first_cut = LifetimePosition::GapFromInstructionIndex(
89 : current_block->first_instruction_index());
90 : }
91 : last_cut = LifetimePosition::GapFromInstructionIndex(
92 37779869 : current_block->last_instruction_index());
93 : } else {
94 119726391 : if (first_cut.IsValid()) {
95 14343185 : CreateSplinter(range, data, first_cut, last_cut);
96 : first_cut = LifetimePosition::Invalid();
97 14343359 : last_cut = LifetimePosition::Invalid();
98 : }
99 : }
100 : }
101 : interval = next_interval;
102 : }
103 : // When the range ends in deferred blocks, first_cut will be valid here.
104 : // Splinter from there to the last instruction that was in a deferred block.
105 31911400 : if (first_cut.IsValid()) {
106 1683933 : CreateSplinter(range, data, first_cut, last_cut);
107 : }
108 :
109 : // Redo has_slot_use
110 33806204 : if (range->has_slot_use() && range->splinter() != nullptr) {
111 1609417 : SetSlotUse(range);
112 1609419 : SetSlotUse(range->splinter());
113 : }
114 31911353 : }
115 :
116 : } // namespace
117 :
118 117829307 : void LiveRangeSeparator::Splinter() {
119 2949387 : size_t virt_reg_count = data()->live_ranges().size();
120 85918216 : for (size_t vreg = 0; vreg < virt_reg_count; ++vreg) {
121 207651400 : TopLevelLiveRange* range = data()->live_ranges()[vreg];
122 168185343 : if (range == nullptr || range->IsEmpty() || range->IsSplinter()) {
123 : continue;
124 : }
125 : int first_instr = range->first_interval()->FirstGapIndex();
126 37126070 : if (!data()->code()->GetInstructionBlock(first_instr)->IsDeferred()) {
127 31911329 : SplinterLiveRange(range, data());
128 : }
129 : }
130 2949625 : }
131 :
132 3830880 : void LiveRangeMerger::MarkRangesSpilledInDeferredBlocks() {
133 3830880 : const InstructionSequence* code = data()->code();
134 130581719 : for (TopLevelLiveRange* top : data()->live_ranges()) {
135 172772940 : if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr ||
136 85273277 : top->HasSpillOperand() || !top->splinter()->HasSpillRange()) {
137 : continue;
138 : }
139 :
140 4166969 : LiveRange* child = top;
141 3465049 : for (; child != nullptr; child = child->next()) {
142 4167604 : if (child->spilled() ||
143 1583589 : child->NextSlotPosition(child->Start()) != nullptr) {
144 : break;
145 : }
146 : }
147 1882095 : if (child == nullptr) {
148 : top->TreatAsSpilledInDeferredBlock(data()->allocation_zone(),
149 881044 : code->InstructionBlockCount());
150 : }
151 : }
152 2949634 : }
153 :
154 93456632 : void LiveRangeMerger::Merge() {
155 2949485 : MarkRangesSpilledInDeferredBlocks();
156 :
157 5900320 : int live_range_count = static_cast<int>(data()->live_ranges().size());
158 85918239 : for (int i = 0; i < live_range_count; ++i) {
159 295208758 : TopLevelLiveRange* range = data()->live_ranges()[i];
160 168185116 : if (range == nullptr || range->IsEmpty() || !range->IsSplinter()) {
161 : continue;
162 : }
163 : TopLevelLiveRange* splinter_parent = range->splintered_from();
164 :
165 : int to_remove = range->vreg();
166 4588908 : splinter_parent->Merge(range, data()->allocation_zone());
167 13765263 : data()->live_ranges()[to_remove] = nullptr;
168 : }
169 2949673 : }
170 :
171 : #undef TRACE
172 :
173 : } // namespace compiler
174 : } // namespace internal
175 183867 : } // namespace v8
|
