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/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 32058652 : 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 27225427 : if (first_cut <= range->Start() && max_allowed_end >= range->End()) {
33 11729971 : return;
34 : }
35 :
36 : LifetimePosition start = Max(first_cut, range->Start());
37 : LifetimePosition end = Min(last_cut, range->End());
38 :
39 11729970 : 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 10164389 : if (range->MayRequireSpillRange()) {
45 1137467 : data->CreateSpillRangeForLiveRange(range);
46 : }
47 10164365 : if (range->splinter() == nullptr) {
48 3765471 : TopLevelLiveRange *splinter =
49 3765519 : data->NextLiveRange(range->representation());
50 : DCHECK_NULL(data->live_ranges()[splinter->vreg()]);
51 7530942 : data->live_ranges()[splinter->vreg()] = splinter;
52 3765471 : range->SetSplinter(splinter);
53 : }
54 : Zone *zone = data->allocation_zone();
55 10164349 : TRACE("creating splinter for range %d between %d and %d\n", range->vreg(),
56 : start.ToInstructionIndex(), end.ToInstructionIndex());
57 10164349 : range->Splinter(start, end, zone);
58 : }
59 : }
60 :
61 13287890 : void SetSlotUse(TopLevelLiveRange *range) {
62 : range->set_has_slot_use(false);
63 20089128 : for (const UsePosition *pos = range->first_pos();
64 10044564 : !range->has_slot_use() && pos != nullptr; pos = pos->next()) {
65 6801238 : if (pos->type() == UsePositionType::kRequiresSlot) {
66 : range->set_has_slot_use(true);
67 : }
68 : }
69 3243326 : }
70 :
71 47593636 : void SplinterLiveRange(TopLevelLiveRange *range, RegisterAllocationData *data) {
72 106119683 : const InstructionSequence *code = data->code();
73 48943784 : UseInterval *interval = range->first_interval();
74 :
75 : LifetimePosition first_cut = LifetimePosition::Invalid();
76 21982129 : LifetimePosition last_cut = LifetimePosition::Invalid();
77 :
78 70925746 : while (interval != nullptr) {
79 : UseInterval *next_interval = interval->next();
80 : const InstructionBlock *first_block =
81 26961655 : code->GetInstructionBlock(interval->FirstGapIndex());
82 : const InstructionBlock *last_block =
83 26961676 : 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 133081171 : for (int block_id = first_block_nr; block_id <= last_block_nr; ++block_id) {
87 142857277 : const InstructionBlock *current_block =
88 106119683 : code->InstructionBlockAt(RpoNumber::FromInt(block_id));
89 106119266 : if (current_block->IsDeferred()) {
90 25007984 : if (!first_cut.IsValid()) {
91 : first_cut = LifetimePosition::GapFromInstructionIndex(
92 : current_block->first_instruction_index());
93 : }
94 : last_cut = LifetimePosition::GapFromInstructionIndex(
95 25007984 : current_block->last_instruction_index());
96 : } else {
97 81111282 : if (first_cut.IsValid()) {
98 10471661 : CreateSplinter(range, data, first_cut, last_cut);
99 : first_cut = LifetimePosition::Invalid();
100 10471911 : 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 21981962 : if (first_cut.IsValid()) {
109 1258331 : CreateSplinter(range, data, first_cut, last_cut);
110 : }
111 :
112 : // Redo has_slot_use
113 23989844 : if (range->has_slot_use() && range->splinter() != nullptr) {
114 1621661 : SetSlotUse(range);
115 1621663 : SetSlotUse(range->splinter());
116 : }
117 21982027 : }
118 :
119 : } // namespace
120 :
121 :
122 78205533 : void LiveRangeSeparator::Splinter() {
123 1301620 : size_t virt_reg_count = data()->live_ranges().size();
124 56223510 : for (size_t vreg = 0; vreg < virt_reg_count; ++vreg) {
125 139016835 : TopLevelLiveRange *range = data()->live_ranges()[vreg];
126 114900355 : if (range == nullptr || range->IsEmpty() || range->IsSplinter()) {
127 : continue;
128 : }
129 : int first_instr = range->first_interval()->FirstGapIndex();
130 25407574 : if (!data()->code()->GetInstructionBlock(first_instr)->IsDeferred()) {
131 21981992 : SplinterLiveRange(range, data());
132 : }
133 : }
134 1301589 : }
135 :
136 :
137 2126009 : void LiveRangeMerger::MarkRangesSpilledInDeferredBlocks() {
138 2126009 : const InstructionSequence *code = data()->code();
139 86698410 : for (TopLevelLiveRange *top : data()->live_ranges()) {
140 118666312 : if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr ||
141 56803402 : top->HasSpillOperand() || !top->splinter()->HasSpillRange()) {
142 : continue;
143 : }
144 :
145 3190907 : LiveRange *child = top;
146 2811431 : for (; child != nullptr; child = child->next()) {
147 3191677 : if (child->spilled() ||
148 1204652 : child->NextSlotPosition(child->Start()) != nullptr) {
149 : break;
150 : }
151 : }
152 1607549 : if (child == nullptr) {
153 : top->TreatAsSpilledInDeferredBlock(data()->allocation_zone(),
154 824408 : code->InstructionBlockCount());
155 : }
156 : }
157 1301593 : }
158 :
159 :
160 61291142 : void LiveRangeMerger::Merge() {
161 1301591 : MarkRangesSpilledInDeferredBlocks();
162 :
163 2603250 : int live_range_count = static_cast<int>(data()->live_ranges().size());
164 56223997 : for (int i = 0; i < live_range_count; ++i) {
165 197705931 : TopLevelLiveRange *range = data()->live_ranges()[i];
166 114901295 : 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 3765554 : splinter_parent->Merge(range, data()->allocation_zone());
173 11296584 : data()->live_ranges()[to_remove] = nullptr;
174 : }
175 1301599 : }
176 :
177 : #undef TRACE
178 :
179 : } // namespace compiler
180 : } // namespace internal
181 : } // namespace v8
|
