1 /* -*- mesa-c++ -*-
2 * Copyright 2022 Collabora LTD
3 * Author: Gert Wollny <[email protected]>
4 * SPDX-License-Identifier: MIT
5 */
6
7 #include "sfn_ra.h"
8
9 #include "sfn_alu_defines.h"
10 #include "sfn_debug.h"
11
12 #include <cassert>
13 #include <queue>
14
15 namespace r600 {
16
17 void
prepare_row(int row)18 ComponentInterference::prepare_row(int row)
19 {
20 m_rows.resize(row + 1);
21 }
22
23 void
add(size_t idx1,size_t idx2)24 ComponentInterference::add(size_t idx1, size_t idx2)
25 {
26 assert(idx1 > idx2);
27 assert(m_rows.size() > idx1);
28 m_rows[idx1].push_back(idx2);
29 m_rows[idx2].push_back(idx1);
30 }
31
Interference(LiveRangeMap & map)32 Interference::Interference(LiveRangeMap& map):
33 m_map(map)
34 {
35 initialize();
36 }
37
38 void
initialize()39 Interference::initialize()
40 {
41 for (int i = 0; i < 4; ++i) {
42 initialize(m_components_maps[i], m_map.component(i));
43 }
44 }
45
46 void
initialize(ComponentInterference & comp_interference,LiveRangeMap::ChannelLiveRange & clr)47 Interference::initialize(ComponentInterference& comp_interference,
48 LiveRangeMap::ChannelLiveRange& clr)
49 {
50 for (size_t row = 0; row < clr.size(); ++row) {
51 auto& row_entry = clr[row];
52 comp_interference.prepare_row(row);
53 for (size_t col = 0; col < row; ++col) {
54 auto& col_entry = clr[col];
55 if (row_entry.m_end >= col_entry.m_start && row_entry.m_start <= col_entry.m_end)
56 comp_interference.add(row, col);
57 }
58 }
59 }
60
61 struct Group {
62 int priority;
63 std::array<PRegister, 4> channels;
64 };
65
66 static inline bool
operator <(const Group & lhs,const Group & rhs)67 operator<(const Group& lhs, const Group& rhs)
68 {
69 return lhs.priority < rhs.priority;
70 }
71
72 using GroupRegisters = std::priority_queue<Group>;
73
74 static bool
group_allocation(LiveRangeMap & lrm,const Interference & interference,GroupRegisters & groups)75 group_allocation(LiveRangeMap& lrm,
76 const Interference& interference,
77 GroupRegisters& groups)
78 {
79 int color = 0;
80 // allocate grouped registers
81 while (!groups.empty()) {
82 auto group = groups.top();
83 groups.pop();
84
85 int start_comp = 0;
86 while (!group.channels[start_comp])
87 ++start_comp;
88
89 sfn_log << SfnLog::merge << "Color group with " << *group.channels[start_comp]
90 << "\n";
91
92 // don't restart registers for exports, we may be able tp merge the
93 // export calls, is fthe registers are consecutive
94 if (group.priority > 0)
95 color = 0;
96
97 while (color < g_registers_end) {
98 /* Find the coloring for the first channel */
99 bool color_in_use = false;
100 int comp = start_comp;
101
102 auto& adjecency = interference.row(start_comp, group.channels[comp]->index());
103 auto& regs = lrm.component(comp);
104
105 sfn_log << SfnLog::merge << "Try color " << color;
106
107 for (auto adj : adjecency) {
108 if (regs[adj].m_color == color) {
109 color_in_use = true;
110 sfn_log << SfnLog::merge << " in use\n";
111 break;
112 }
113 }
114
115 if (color_in_use) {
116 ++color;
117 continue;
118 }
119
120 /* First channel color found, check whether it can be used for all
121 * channels */
122 while (comp < 4) {
123 sfn_log << SfnLog::merge << " interference: ";
124 if (group.channels[comp]) {
125 auto& component_life_ranges = lrm.component(comp);
126 auto& adjecencies = interference.row(comp, group.channels[comp]->index());
127
128 for (auto adj_index : adjecencies) {
129 sfn_log << SfnLog::merge << *component_life_ranges[adj_index].m_register
130 << " ";
131 if (component_life_ranges[adj_index].m_color == color) {
132 color_in_use = true;
133 sfn_log << SfnLog::merge << "used";
134 break;
135 }
136 }
137
138 if (color_in_use)
139 break;
140 }
141 ++comp;
142 }
143
144 /* We couldn't allocate all channels with this color, so try next */
145 if (color_in_use) {
146 ++color;
147 sfn_log << SfnLog::merge << "\n";
148 continue;
149 }
150 sfn_log << SfnLog::merge << " success\n";
151
152 /* Coloring successful */
153 for (auto reg : group.channels) {
154 if (reg) {
155 auto& vregs = lrm.component(reg->chan());
156 auto& vreg_cmp = vregs[reg->index()];
157 assert(vreg_cmp.m_start != -1 || vreg_cmp.m_end != -1);
158 vreg_cmp.m_color = color;
159 }
160 }
161 break;
162 }
163
164 if (color == g_registers_end)
165 return false;
166 }
167
168 return true;
169 }
170
171 static bool
scalar_allocation(LiveRangeMap & lrm,const Interference & interference)172 scalar_allocation(LiveRangeMap& lrm, const Interference& interference)
173 {
174 for (int comp = 0; comp < 4; ++comp) {
175 auto& live_ranges = lrm.component(comp);
176 for (auto& r : live_ranges) {
177 if (r.m_color != -1)
178 continue;
179
180 if (r.m_start == -1 && r.m_end == -1)
181 continue;
182
183 sfn_log << SfnLog::merge << "Color " << *r.m_register << "\n";
184
185 auto& adjecency = interference.row(comp, r.m_register->index());
186
187 int color = 0;
188
189 while (color < g_registers_end) {
190 bool color_in_use = false;
191 for (auto adj : adjecency) {
192 if (live_ranges[adj].m_color == color) {
193 color_in_use = true;
194 break;
195 }
196 }
197
198 if (color_in_use) {
199 ++color;
200 continue;
201 }
202
203 r.m_color = color;
204 break;
205 }
206 if (color == g_registers_end)
207 return false;
208 }
209 }
210 return true;
211 }
212
213 struct AluRegister {
214 int lifetime;
215 LiveRangeEntry *lre;
216 };
217
operator <(const AluRegister & lhs,const AluRegister & rhs)218 static inline bool operator < (const AluRegister& lhs, const AluRegister& rhs)
219 {
220 return lhs.lifetime > rhs.lifetime;
221 }
222
223 using AluClauseRegisters = std::priority_queue<AluRegister>;
224
225
226 static void
scalar_clause_local_allocation(LiveRangeMap & lrm,const Interference & interference)227 scalar_clause_local_allocation (LiveRangeMap& lrm, const Interference& interference)
228 {
229 for (int comp = 0; comp < 4; ++comp) {
230 AluClauseRegisters clause_reg;
231 auto& live_ranges = lrm.component(comp);
232 for (auto& r : live_ranges) {
233
234 sfn_log << SfnLog::merge << "LR: " << *r.m_register
235 << "[ " << r.m_start << ", " << r.m_end
236 << " ], AC: " << r.m_alu_clause_local
237 << " Color; " << r.m_color << "\n";
238
239 if (r.m_color != -1)
240 continue;
241
242 if (r.m_start == -1 &&
243 r.m_end == -1)
244 continue;
245
246 if (!r.m_alu_clause_local)
247 continue;
248
249 int len = r.m_end - r.m_start;
250 if (len > 1) {
251 clause_reg.push({len, &r});
252 sfn_log << SfnLog::merge << "Consider " << *r.m_register
253 << " for clause local\n";
254 }
255 }
256
257 while (!clause_reg.empty()) {
258 auto& r = clause_reg.top().lre;
259 clause_reg.pop();
260
261 sfn_log << SfnLog::merge << "Color " << *r->m_register << "\n";
262
263 auto& adjecency = interference.row(comp, r->m_register->index());
264
265 int color = g_clause_local_start;
266
267 while (color < g_clause_local_end) {
268 bool color_in_use = false;
269 for (auto adj : adjecency) {
270 if (live_ranges[adj].m_color == color) {
271 color_in_use = true;
272 break;
273 }
274 }
275
276 if (color_in_use) {
277 ++color;
278 continue;
279 }
280
281 r->m_color = color;
282 break;
283 }
284 if (color == g_clause_local_end)
285 break;
286 }
287 }
288 }
289
290 bool
register_allocation(LiveRangeMap & lrm)291 register_allocation(LiveRangeMap& lrm)
292 {
293 Interference interference(lrm);
294
295 std::map<int, Group> groups;
296
297 // setup fixed colors and group relationships
298 for (int i = 0; i < 4; ++i) {
299 auto& comp = lrm.component(i);
300 for (auto& entry : comp) {
301 sfn_log << SfnLog::merge << "Prepare RA for " << *entry.m_register << " ["
302 << entry.m_start << ", " << entry.m_end << "]\n";
303 auto pin = entry.m_register->pin();
304 if (entry.m_start == -1 && entry.m_end == -1) {
305 if (pin == pin_group || pin == pin_chgr)
306 entry.m_register->set_chan(7);
307 continue;
308 }
309
310 auto sel = entry.m_register->sel();
311 /* fully pinned registers contain system values with the
312 * definite register index, and array values are allocated
313 * right after the system registers, so just reuse the IDs (for now) */
314 if (pin == pin_fully || pin == pin_array) {
315 /* Must set all array element entries */
316 sfn_log << SfnLog::merge << "Pin color " << sel << " to " << *entry.m_register
317 << "\n";
318 entry.m_color = sel;
319 } else if (pin == pin_group || pin == pin_chgr) {
320 /* Groups must all have the same sel() value, because they are
321 * used as vec4 registers */
322 auto igroup = groups.find(sel);
323 if (igroup != groups.end()) {
324 igroup->second.channels[i] = entry.m_register;
325 assert(comp[entry.m_register->index()].m_register->index() ==
326 entry.m_register->index());
327 } else {
328 int priority = entry.m_use.test(LiveRangeEntry::use_export)
329 ? -entry.m_end
330 : entry.m_start;
331 Group group{
332 priority, {nullptr, nullptr, nullptr, nullptr}
333 };
334 group.channels[i] = entry.m_register;
335 assert(comp[group.channels[i]->index()].m_register->index() ==
336 entry.m_register->index());
337 groups[sel] = group;
338 }
339 }
340 }
341 }
342
343 GroupRegisters groups_sorted;
344 for (auto& [sel, group] : groups)
345 groups_sorted.push(group);
346
347 if (!group_allocation(lrm, interference, groups_sorted))
348 return false;
349
350 scalar_clause_local_allocation(lrm, interference);
351
352 if (!scalar_allocation(lrm, interference))
353 return false;
354
355 for (int i = 0; i < 4; ++i) {
356 auto& comp = lrm.component(i);
357 for (auto& entry : comp) {
358 sfn_log << SfnLog::merge << "Set " << *entry.m_register << " to ";
359 entry.m_register->set_sel(entry.m_color);
360 entry.m_register->set_pin(pin_none);
361 sfn_log << SfnLog::merge << *entry.m_register << "\n";
362 }
363 }
364
365 return true;
366 }
367
368 } // namespace r600
369