1 /*
2 * Copyright 2011 Tom Stellard <tstellar@gmail.com>
3 *
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial
16 * portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
21 * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 */
27
28 #include "radeon_variable.h"
29
30 #include "memory_pool.h"
31 #include "radeon_compiler_util.h"
32 #include "radeon_dataflow.h"
33 #include "radeon_list.h"
34 #include "radeon_opcodes.h"
35 #include "radeon_program.h"
36
37 /**
38 * Rewrite the index and writemask for the destination register of var
39 * and its friends to new_index and new_writemask. This function also takes
40 * care of rewriting the swizzles for the sources of var.
41 */
rc_variable_change_dst(struct rc_variable * var,unsigned int new_index,unsigned int new_writemask)42 void rc_variable_change_dst(
43 struct rc_variable * var,
44 unsigned int new_index,
45 unsigned int new_writemask)
46 {
47 struct rc_variable * var_ptr;
48 struct rc_list * readers;
49 unsigned int old_mask = rc_variable_writemask_sum(var);
50 unsigned int conversion_swizzle =
51 rc_make_conversion_swizzle(old_mask, new_writemask);
52
53 for (var_ptr = var; var_ptr; var_ptr = var_ptr->Friend) {
54 if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) {
55 rc_normal_rewrite_writemask(var_ptr->Inst,
56 conversion_swizzle);
57 var_ptr->Inst->U.I.DstReg.Index = new_index;
58 } else {
59 struct rc_pair_sub_instruction * sub;
60 if (var_ptr->Dst.WriteMask == RC_MASK_W) {
61 assert(new_writemask & RC_MASK_W);
62 sub = &var_ptr->Inst->U.P.Alpha;
63 } else {
64 sub = &var_ptr->Inst->U.P.RGB;
65 rc_pair_rewrite_writemask(sub,
66 conversion_swizzle);
67 }
68 sub->DestIndex = new_index;
69 }
70 }
71
72 readers = rc_variable_readers_union(var);
73
74 for ( ; readers; readers = readers->Next) {
75 struct rc_reader * reader = readers->Item;
76 if (reader->Inst->Type == RC_INSTRUCTION_NORMAL) {
77 reader->U.I.Src->Index = new_index;
78 reader->U.I.Src->Swizzle = rc_rewrite_swizzle(
79 reader->U.I.Src->Swizzle, conversion_swizzle);
80 } else {
81 struct rc_pair_instruction * pair_inst =
82 &reader->Inst->U.P;
83 unsigned int src_type = rc_source_type_swz(
84 reader->U.P.Arg->Swizzle);
85
86 int src_index = reader->U.P.Arg->Source;
87 if (src_index == RC_PAIR_PRESUB_SRC) {
88 src_index = rc_pair_get_src_index(
89 pair_inst, reader->U.P.Src);
90 }
91 /* Try to delete the old src, it is OK if this fails,
92 * because rc_pair_alloc_source might be able to
93 * find a source the ca be reused.
94 */
95 if (rc_pair_remove_src(reader->Inst, src_type,
96 src_index, old_mask)) {
97 /* Reuse the source index of the source that
98 * was just deleted and set its register
99 * index. We can't use rc_pair_alloc_source
100 * for this becuase it might return a source
101 * index that is already being used. */
102 if (src_type & RC_SOURCE_RGB) {
103 pair_inst->RGB.Src[src_index]
104 .Used = 1;
105 pair_inst->RGB.Src[src_index]
106 .Index = new_index;
107 pair_inst->RGB.Src[src_index]
108 .File = RC_FILE_TEMPORARY;
109 }
110 if (src_type & RC_SOURCE_ALPHA) {
111 pair_inst->Alpha.Src[src_index]
112 .Used = 1;
113 pair_inst->Alpha.Src[src_index]
114 .Index = new_index;
115 pair_inst->Alpha.Src[src_index]
116 .File = RC_FILE_TEMPORARY;
117 }
118 } else {
119 src_index = rc_pair_alloc_source(
120 &reader->Inst->U.P,
121 src_type & RC_SOURCE_RGB,
122 src_type & RC_SOURCE_ALPHA,
123 RC_FILE_TEMPORARY,
124 new_index);
125 if (src_index < 0) {
126 rc_error(var->C, "Rewrite of inst %u failed "
127 "Can't allocate source for "
128 "Inst %u src_type=%x "
129 "new_index=%u new_mask=%u\n",
130 var->Inst->IP, reader->Inst->IP, src_type, new_index, new_writemask);
131 continue;
132 }
133 }
134 reader->U.P.Arg->Swizzle = rc_rewrite_swizzle(
135 reader->U.P.Arg->Swizzle, conversion_swizzle);
136 if (reader->U.P.Arg->Source != RC_PAIR_PRESUB_SRC) {
137 reader->U.P.Arg->Source = src_index;
138 }
139 }
140 }
141 }
142
143 /**
144 * Compute the live intervals for var and its friends.
145 */
rc_variable_compute_live_intervals(struct rc_variable * var)146 void rc_variable_compute_live_intervals(struct rc_variable * var)
147 {
148 while(var) {
149 unsigned int i;
150 unsigned int start = var->Inst->IP;
151
152 for (i = 0; i < var->ReaderCount; i++) {
153 unsigned int chan;
154 unsigned int chan_start = start;
155 unsigned int chan_end = var->Readers[i].Inst->IP;
156 unsigned int mask = var->Readers[i].WriteMask;
157 struct rc_instruction * inst;
158
159 /* Extend the live interval of T0 to the start of the
160 * loop for sequences like:
161 * BGNLOOP
162 * read T0
163 * ...
164 * write T0
165 * ENDLOOP
166 */
167 if (var->Readers[i].Inst->IP < start) {
168 struct rc_instruction * bgnloop =
169 rc_match_endloop(var->Readers[i].Inst);
170 chan_start = bgnloop->IP;
171 }
172
173 /* Extend the live interval of T0 to the start of the
174 * loop in case there is a BRK instruction in the loop
175 * (we don't actually check for a BRK instruction we
176 * assume there is one somewhere in the loop, which
177 * there usually is) for sequences like:
178 * BGNLOOP
179 * ...
180 * conditional BRK
181 * ...
182 * write T0
183 * ENDLOOP
184 * read T0
185 ***************************************************
186 * Extend the live interval of T0 to the end of the
187 * loop for sequences like:
188 * write T0
189 * BGNLOOP
190 * ...
191 * read T0
192 * ENDLOOP
193 */
194 for (inst = var->Inst; inst != var->Readers[i].Inst;
195 inst = inst->Next) {
196 rc_opcode op = rc_get_flow_control_inst(inst);
197 if (op == RC_OPCODE_ENDLOOP) {
198 struct rc_instruction * bgnloop =
199 rc_match_endloop(inst);
200 if (bgnloop->IP < chan_start) {
201 chan_start = bgnloop->IP;
202 }
203 } else if (op == RC_OPCODE_BGNLOOP) {
204 struct rc_instruction * endloop =
205 rc_match_bgnloop(inst);
206 if (endloop->IP > chan_end) {
207 chan_end = endloop->IP;
208 }
209 }
210 }
211
212 for (chan = 0; chan < 4; chan++) {
213 if ((mask >> chan) & 0x1) {
214 if (!var->Live[chan].Used
215 || chan_start < var->Live[chan].Start) {
216 var->Live[chan].Start =
217 chan_start;
218 }
219 if (!var->Live[chan].Used
220 || chan_end > var->Live[chan].End) {
221 var->Live[chan].End = chan_end;
222 }
223 var->Live[chan].Used = 1;
224 }
225 }
226 }
227 var = var->Friend;
228 }
229 }
230
231 /**
232 * @return 1 if a and b share a reader
233 * @return 0 if they do not
234 */
readers_intersect(struct rc_variable * a,struct rc_variable * b)235 static unsigned int readers_intersect(
236 struct rc_variable * a,
237 struct rc_variable * b)
238 {
239 unsigned int a_index, b_index;
240 for (a_index = 0; a_index < a->ReaderCount; a_index++) {
241 struct rc_reader reader_a = a->Readers[a_index];
242 for (b_index = 0; b_index < b->ReaderCount; b_index++) {
243 struct rc_reader reader_b = b->Readers[b_index];
244 if (reader_a.Inst->Type == RC_INSTRUCTION_NORMAL
245 && reader_b.Inst->Type == RC_INSTRUCTION_NORMAL
246 && reader_a.U.I.Src == reader_b.U.I.Src) {
247
248 return 1;
249 }
250 if (reader_a.Inst->Type == RC_INSTRUCTION_PAIR
251 && reader_b.Inst->Type == RC_INSTRUCTION_PAIR
252 && reader_a.U.P.Src == reader_b.U.P.Src) {
253
254 return 1;
255 }
256 }
257 }
258 return 0;
259 }
260
rc_variable_add_friend(struct rc_variable * var,struct rc_variable * friend)261 void rc_variable_add_friend(
262 struct rc_variable * var,
263 struct rc_variable * friend)
264 {
265 assert(var->Dst.Index == friend->Dst.Index);
266 while(var->Friend) {
267 var = var->Friend;
268 }
269 var->Friend = friend;
270 }
271
rc_variable(struct radeon_compiler * c,unsigned int DstFile,unsigned int DstIndex,unsigned int DstWriteMask,struct rc_reader_data * reader_data)272 struct rc_variable * rc_variable(
273 struct radeon_compiler * c,
274 unsigned int DstFile,
275 unsigned int DstIndex,
276 unsigned int DstWriteMask,
277 struct rc_reader_data * reader_data)
278 {
279 struct rc_variable * new =
280 memory_pool_malloc(&c->Pool, sizeof(struct rc_variable));
281 memset(new, 0, sizeof(struct rc_variable));
282 new->C = c;
283 new->Dst.File = DstFile;
284 new->Dst.Index = DstIndex;
285 new->Dst.WriteMask = DstWriteMask;
286 if (reader_data) {
287 new->Inst = reader_data->Writer;
288 new->ReaderCount = reader_data->ReaderCount;
289 new->Readers = reader_data->Readers;
290 }
291 return new;
292 }
293
get_variable_helper(struct rc_list ** variable_list,struct rc_variable * variable)294 static void get_variable_helper(
295 struct rc_list ** variable_list,
296 struct rc_variable * variable)
297 {
298 struct rc_list * list_ptr;
299 for (list_ptr = *variable_list; list_ptr; list_ptr = list_ptr->Next) {
300 struct rc_variable * var;
301 for (var = list_ptr->Item; var; var = var->Friend) {
302 if (readers_intersect(var, variable)) {
303 rc_variable_add_friend(var, variable);
304 return;
305 }
306 }
307 }
308 rc_list_add(variable_list, rc_list(&variable->C->Pool, variable));
309 }
310
get_variable_pair_helper(struct rc_list ** variable_list,struct radeon_compiler * c,struct rc_instruction * inst,struct rc_pair_sub_instruction * sub_inst)311 static void get_variable_pair_helper(
312 struct rc_list ** variable_list,
313 struct radeon_compiler * c,
314 struct rc_instruction * inst,
315 struct rc_pair_sub_instruction * sub_inst)
316 {
317 struct rc_reader_data reader_data;
318 struct rc_variable * new_var;
319 rc_register_file file;
320 unsigned int writemask;
321
322 if (sub_inst->Opcode == RC_OPCODE_NOP) {
323 return;
324 }
325 memset(&reader_data, 0, sizeof(struct rc_reader_data));
326 rc_get_readers_sub(c, inst, sub_inst, &reader_data, NULL, NULL, NULL);
327
328 if (reader_data.ReaderCount == 0) {
329 return;
330 }
331
332 if (sub_inst->WriteMask) {
333 file = RC_FILE_TEMPORARY;
334 writemask = sub_inst->WriteMask;
335 } else if (sub_inst->OutputWriteMask) {
336 file = RC_FILE_OUTPUT;
337 writemask = sub_inst->OutputWriteMask;
338 } else {
339 writemask = 0;
340 file = RC_FILE_NONE;
341 }
342 new_var = rc_variable(c, file, sub_inst->DestIndex, writemask,
343 &reader_data);
344 get_variable_helper(variable_list, new_var);
345 }
346
347 /**
348 * Generate a list of variables used by the shader program. Each instruction
349 * that writes to a register is considered a variable. The struct rc_variable
350 * data structure includes a list of readers and is essentially a
351 * definition-use chain. Any two variables that share a reader are considered
352 * "friends" and they are linked together via the Friend attribute.
353 */
rc_get_variables(struct radeon_compiler * c)354 struct rc_list * rc_get_variables(struct radeon_compiler * c)
355 {
356 struct rc_instruction * inst;
357 struct rc_list * variable_list = NULL;
358
359 for (inst = c->Program.Instructions.Next;
360 inst != &c->Program.Instructions;
361 inst = inst->Next) {
362 struct rc_reader_data reader_data;
363 struct rc_variable * new_var;
364 memset(&reader_data, 0, sizeof(reader_data));
365
366 if (inst->Type == RC_INSTRUCTION_NORMAL) {
367 rc_get_readers(c, inst, &reader_data, NULL, NULL, NULL);
368 if (reader_data.ReaderCount == 0) {
369 continue;
370 }
371 new_var = rc_variable(c, inst->U.I.DstReg.File,
372 inst->U.I.DstReg.Index,
373 inst->U.I.DstReg.WriteMask, &reader_data);
374 get_variable_helper(&variable_list, new_var);
375 } else {
376 get_variable_pair_helper(&variable_list, c, inst,
377 &inst->U.P.RGB);
378 get_variable_pair_helper(&variable_list, c, inst,
379 &inst->U.P.Alpha);
380 }
381 }
382
383 return variable_list;
384 }
385
386 /**
387 * @return The bitwise or of the writemasks of a variable and all of its
388 * friends.
389 */
rc_variable_writemask_sum(struct rc_variable * var)390 unsigned int rc_variable_writemask_sum(struct rc_variable * var)
391 {
392 unsigned int writemask = 0;
393 while(var) {
394 writemask |= var->Dst.WriteMask;
395 var = var->Friend;
396 }
397 return writemask;
398 }
399
400 /*
401 * @return A list of readers for a variable and its friends. Readers
402 * that read from two different variable friends are only included once in
403 * this list.
404 */
rc_variable_readers_union(struct rc_variable * var)405 struct rc_list * rc_variable_readers_union(struct rc_variable * var)
406 {
407 struct rc_list * list = NULL;
408 while (var) {
409 unsigned int i;
410 for (i = 0; i < var->ReaderCount; i++) {
411 struct rc_list * temp;
412 struct rc_reader * a = &var->Readers[i];
413 unsigned int match = 0;
414 for (temp = list; temp; temp = temp->Next) {
415 struct rc_reader * b = temp->Item;
416 if (a->Inst->Type != b->Inst->Type) {
417 continue;
418 }
419 if (a->Inst->Type == RC_INSTRUCTION_NORMAL) {
420 if (a->U.I.Src == b->U.I.Src) {
421 match = 1;
422 break;
423 }
424 }
425 if (a->Inst->Type == RC_INSTRUCTION_PAIR) {
426 if (a->U.P.Arg == b->U.P.Arg
427 && a->U.P.Src == b->U.P.Src) {
428 match = 1;
429 break;
430 }
431 }
432 }
433 if (match) {
434 continue;
435 }
436 rc_list_add(&list, rc_list(&var->C->Pool, a));
437 }
438 var = var->Friend;
439 }
440 return list;
441 }
442
reader_equals_src(struct rc_reader reader,unsigned int src_type,void * src)443 static unsigned int reader_equals_src(
444 struct rc_reader reader,
445 unsigned int src_type,
446 void * src)
447 {
448 if (reader.Inst->Type != src_type) {
449 return 0;
450 }
451 if (src_type == RC_INSTRUCTION_NORMAL) {
452 return reader.U.I.Src == src;
453 } else {
454 return reader.U.P.Src == src;
455 }
456 }
457
variable_writes_src(struct rc_variable * var,unsigned int src_type,void * src)458 static unsigned int variable_writes_src(
459 struct rc_variable * var,
460 unsigned int src_type,
461 void * src)
462 {
463 unsigned int i;
464 for (i = 0; i < var->ReaderCount; i++) {
465 if (reader_equals_src(var->Readers[i], src_type, src)) {
466 return 1;
467 }
468 }
469 return 0;
470 }
471
472
rc_variable_list_get_writers(struct rc_list * var_list,unsigned int src_type,void * src)473 struct rc_list * rc_variable_list_get_writers(
474 struct rc_list * var_list,
475 unsigned int src_type,
476 void * src)
477 {
478 struct rc_list * list_ptr;
479 struct rc_list * writer_list = NULL;
480 for (list_ptr = var_list; list_ptr; list_ptr = list_ptr->Next) {
481 struct rc_variable * var = list_ptr->Item;
482 if (variable_writes_src(var, src_type, src)) {
483 struct rc_variable * friend;
484 rc_list_add(&writer_list, rc_list(&var->C->Pool, var));
485 for (friend = var->Friend; friend;
486 friend = friend->Friend) {
487 if (variable_writes_src(friend, src_type, src)) {
488 rc_list_add(&writer_list,
489 rc_list(&var->C->Pool, friend));
490 }
491 }
492 /* Once we have indentifed the variable and its
493 * friends that write this source, we can stop
494 * stop searching, because we know know of the
495 * other variables in the list will write this source.
496 * If they did they would be friends of var.
497 */
498 break;
499 }
500 }
501 return writer_list;
502 }
503
rc_variable_list_get_writers_one_reader(struct rc_list * var_list,unsigned int src_type,void * src)504 struct rc_list * rc_variable_list_get_writers_one_reader(
505 struct rc_list * var_list,
506 unsigned int src_type,
507 void * src)
508 {
509 struct rc_list * writer_list =
510 rc_variable_list_get_writers(var_list, src_type, src);
511 struct rc_list * reader_list =
512 rc_variable_readers_union(writer_list->Item);
513 if (rc_list_count(reader_list) > 1) {
514 return NULL;
515 } else {
516 return writer_list;
517 }
518 }
519
rc_variable_print(struct rc_variable * var)520 void rc_variable_print(struct rc_variable * var)
521 {
522 unsigned int i;
523 while (var) {
524 fprintf(stderr, "%u: TEMP[%u].%u: ",
525 var->Inst->IP, var->Dst.Index, var->Dst.WriteMask);
526 for (i = 0; i < 4; i++) {
527 fprintf(stderr, "chan %u: start=%u end=%u ", i,
528 var->Live[i].Start, var->Live[i].End);
529 }
530 fprintf(stderr, "%u readers\n", var->ReaderCount);
531 if (var->Friend) {
532 fprintf(stderr, "Friend: \n\t");
533 }
534 var = var->Friend;
535 }
536 }
537