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 */
42void 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 */
146void 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 */
235static 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
261void 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
272struct 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
294static 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
311static 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 */
354struct 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 */
390unsigned 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 */
405struct 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
443static 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
458static 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
473struct 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
504struct 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
520void 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