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