src/gallium/drivers/r300/compiler/radeon_variable.c - platform/external/mesa3d - Git at Google

 /*
  * Copyright 2011 Tom Stellard <tstellar@gmail.com>
  *
  * All Rights Reserved.
  *
  * Permission is hereby granted, free of charge, to any person obtaining
  * a copy of this software and associated documentation files (the
  * "Software"), to deal in the Software without restriction, including
  * without limitation the rights to use, copy, modify, merge, publish,
  * distribute, sublicense, and/or sell copies of the Software, and to
  * permit persons to whom the Software is furnished to do so, subject to
  * the following conditions:
  *
  * The above copyright notice and this permission notice (including the
  * next paragraph) shall be included in all copies or substantial
  * portions of the Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  *
  */

 #include "radeon_variable.h"

 #include "memory_pool.h"
 #include "radeon_compiler_util.h"
 #include "radeon_dataflow.h"
 #include "radeon_list.h"
 #include "radeon_opcodes.h"
 #include "radeon_program.h"

 /**
  * Rewrite the index and writemask for the destination register of var
  * and its friends to new_index and new_writemask.  This function also takes
  * care of rewriting the swizzles for the sources of var.
  */
 void rc_variable_change_dst(
 	struct rc_variable * var,
 	unsigned int new_index,
 	unsigned int new_writemask)
 {
 	struct rc_variable * var_ptr;
 	struct rc_list * readers;
 	unsigned int old_mask = rc_variable_writemask_sum(var);
 	unsigned int conversion_swizzle =
 			rc_make_conversion_swizzle(old_mask, new_writemask);

 	for (var_ptr = var; var_ptr; var_ptr = var_ptr->Friend) {
 		if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) {
 			rc_normal_rewrite_writemask(var_ptr->Inst,
 							conversion_swizzle);
 			var_ptr->Inst->U.I.DstReg.Index = new_index;
 		} else {
 			struct rc_pair_sub_instruction * sub;
 			if (var_ptr->Dst.WriteMask == RC_MASK_W) {
 				assert(new_writemask & RC_MASK_W);
 				sub = &var_ptr->Inst->U.P.Alpha;
 			} else {
 				sub = &var_ptr->Inst->U.P.RGB;
 				rc_pair_rewrite_writemask(sub,
 							conversion_swizzle);
 			}
 			sub->DestIndex = new_index;
 		}
 	}

 	readers = rc_variable_readers_union(var);

 	for ( ; readers; readers = readers->Next) {
 		struct rc_reader * reader = readers->Item;
 		if (reader->Inst->Type == RC_INSTRUCTION_NORMAL) {
 			reader->U.I.Src->Index = new_index;
 			reader->U.I.Src->Swizzle = rc_rewrite_swizzle(
 				reader->U.I.Src->Swizzle, conversion_swizzle);
 		} else {
 			struct rc_pair_instruction * pair_inst =
 							&reader->Inst->U.P;
 			unsigned int src_type = rc_source_type_swz(
 							reader->U.P.Arg->Swizzle);

 			int src_index = reader->U.P.Arg->Source;
 			if (src_index == RC_PAIR_PRESUB_SRC) {
 				src_index = rc_pair_get_src_index(
 						pair_inst, reader->U.P.Src);
 			}
 			/* Try to delete the old src, it is OK if this fails,
 			 * because rc_pair_alloc_source might be able to
 			 * find a source the ca be reused.
 			 */
 			if (rc_pair_remove_src(reader->Inst, src_type,
 							src_index, old_mask)) {
 				/* Reuse the source index of the source that
 				 * was just deleted and set its register
 				 * index.  We can't use rc_pair_alloc_source
 				 * for this becuase it might return a source
 				 * index that is already being used. */
 				if (src_type & RC_SOURCE_RGB) {
 					pair_inst->RGB.Src[src_index]
 						.Used =	1;
 					pair_inst->RGB.Src[src_index]
 						.Index = new_index;
 					pair_inst->RGB.Src[src_index]
 						.File = RC_FILE_TEMPORARY;
 				}
 				if (src_type & RC_SOURCE_ALPHA) {
 					pair_inst->Alpha.Src[src_index]
 						.Used = 1;
 					pair_inst->Alpha.Src[src_index]
 						.Index = new_index;
 					pair_inst->Alpha.Src[src_index]
 						.File = RC_FILE_TEMPORARY;
 				}
 			} else {
 				src_index = rc_pair_alloc_source(
 						&reader->Inst->U.P,
 						src_type & RC_SOURCE_RGB,
 						src_type & RC_SOURCE_ALPHA,
 						RC_FILE_TEMPORARY,
 						new_index);
 				if (src_index < 0) {
 					rc_error(var->C, "Rewrite of inst %u failed "
 						"Can't allocate source for "
 						"Inst %u src_type=%x "
 						"new_index=%u new_mask=%u\n",
 						var->Inst->IP, reader->Inst->IP, src_type, new_index, new_writemask);
 						continue;
 				}
 			}
 			reader->U.P.Arg->Swizzle = rc_rewrite_swizzle(
 				reader->U.P.Arg->Swizzle, conversion_swizzle);
 			if (reader->U.P.Arg->Source != RC_PAIR_PRESUB_SRC) {
 				reader->U.P.Arg->Source = src_index;
 			}
 		}
 	}
 }

 /**
  * Compute the live intervals for var and its friends.
  */
 void rc_variable_compute_live_intervals(struct rc_variable * var)
 {
 	while(var) {
 		unsigned int i;
 		unsigned int start = var->Inst->IP;

 		for (i = 0; i < var->ReaderCount; i++) {
 			unsigned int chan;
 			unsigned int chan_start = start;
 			unsigned int chan_end = var->Readers[i].Inst->IP;
 			unsigned int mask = var->Readers[i].WriteMask;
 			struct rc_instruction * inst;

 			/* Extend the live interval of T0 to the start of the
 			 * loop for sequences like:
 			 * BGNLOOP
 			 * read T0
 			 * ...
 			 * write T0
 			 * ENDLOOP
 			 */
 			if (var->Readers[i].Inst->IP < start) {
 				struct rc_instruction * bgnloop =
 					rc_match_endloop(var->Readers[i].Inst);
 				chan_start = bgnloop->IP;
 			}

 			/* Extend the live interval of T0 to the start of the
 			 * loop in case there is a BRK instruction in the loop
 			 * (we don't actually check for a BRK instruction we
 			 * assume there is one somewhere in the loop, which
 			 * there usually is) for sequences like:
 			 * BGNLOOP
 			 * ...
 			 * conditional BRK
 			 * ...
 			 * write T0
 			 * ENDLOOP
 			 * read T0
 			 ***************************************************
 			 * Extend the live interval of T0 to the end of the
 			 * loop for sequences like:
 			 * write T0
 			 * BGNLOOP
 			 * ...
 			 * read T0
 			 * ENDLOOP
 			 */
 			for (inst = var->Inst; inst != var->Readers[i].Inst;
 							inst = inst->Next) {
 				rc_opcode op = rc_get_flow_control_inst(inst);
 				if (op == RC_OPCODE_ENDLOOP) {
 					struct rc_instruction * bgnloop =
 						rc_match_endloop(inst);
 					if (bgnloop->IP < chan_start) {
 						chan_start = bgnloop->IP;
 					}
 				} else if (op == RC_OPCODE_BGNLOOP) {
 					struct rc_instruction * endloop =
 						rc_match_bgnloop(inst);
 					if (endloop->IP > chan_end) {
 						chan_end = endloop->IP;
 					}
 				}
 			}

 			for (chan = 0; chan < 4; chan++) {
 				if ((mask >> chan) & 0x1) {
 					if (!var->Live[chan].Used
 					|| chan_start < var->Live[chan].Start) {
 						var->Live[chan].Start =
 								chan_start;
 					}
 					if (!var->Live[chan].Used
 					|| chan_end > var->Live[chan].End) {
 						var->Live[chan].End = chan_end;
 					}
 					var->Live[chan].Used = 1;
 				}
 			}
 		}
 		var = var->Friend;
 	}
 }

 /**
  * @return 1 if a and b share a reader
  * @return 0 if they do not
  */
 static unsigned int readers_intersect(
 	struct rc_variable * a,
 	struct rc_variable * b)
 {
 	unsigned int a_index, b_index;
 	for (a_index = 0; a_index < a->ReaderCount; a_index++) {
 		struct rc_reader reader_a = a->Readers[a_index];
 		for (b_index = 0; b_index < b->ReaderCount; b_index++) {
 			struct rc_reader reader_b = b->Readers[b_index];
 			if (reader_a.Inst->Type == RC_INSTRUCTION_NORMAL
 				&& reader_b.Inst->Type == RC_INSTRUCTION_NORMAL
 				&& reader_a.U.I.Src == reader_b.U.I.Src) {

 				return 1;
 			}
 			if (reader_a.Inst->Type == RC_INSTRUCTION_PAIR
 				&& reader_b.Inst->Type == RC_INSTRUCTION_PAIR
 				&& reader_a.U.P.Src == reader_b.U.P.Src) {

 				return 1;
 			}
 		}
 	}
 	return 0;
 }

 void rc_variable_add_friend(
 	struct rc_variable * var,
 	struct rc_variable * friend)
 {
 	assert(var->Dst.Index == friend->Dst.Index);
 	while(var->Friend) {
 		var = var->Friend;
 	}
 	var->Friend = friend;
 }

 struct rc_variable * rc_variable(
 	struct radeon_compiler * c,
 	unsigned int DstFile,
 	unsigned int DstIndex,
 	unsigned int DstWriteMask,
 	struct rc_reader_data * reader_data)
 {
 	struct rc_variable * new =
 			memory_pool_malloc(&c->Pool, sizeof(struct rc_variable));
 	memset(new, 0, sizeof(struct rc_variable));
 	new->C = c;
 	new->Dst.File = DstFile;
 	new->Dst.Index = DstIndex;
 	new->Dst.WriteMask = DstWriteMask;
 	if (reader_data) {
 		new->Inst = reader_data->Writer;
 		new->ReaderCount = reader_data->ReaderCount;
 		new->Readers = reader_data->Readers;
 	}
 	return new;
 }

 static void get_variable_helper(
 	struct rc_list ** variable_list,
 	struct rc_variable * variable)
 {
 	struct rc_list * list_ptr;
 	for (list_ptr = *variable_list; list_ptr; list_ptr = list_ptr->Next) {
 		struct rc_variable * var;
 		for (var = list_ptr->Item; var; var = var->Friend) {
 			if (readers_intersect(var, variable)) {
 				rc_variable_add_friend(var, variable);
 				return;
 			}
 		}
 	}
 	rc_list_add(variable_list, rc_list(&variable->C->Pool, variable));
 }

 static void get_variable_pair_helper(
 	struct rc_list ** variable_list,
 	struct radeon_compiler * c,
 	struct rc_instruction * inst,
 	struct rc_pair_sub_instruction * sub_inst)
 {
 	struct rc_reader_data reader_data;
 	struct rc_variable * new_var;
 	rc_register_file file;
 	unsigned int writemask;

 	if (sub_inst->Opcode == RC_OPCODE_NOP) {
 		return;
 	}
 	memset(&reader_data, 0, sizeof(struct rc_reader_data));
 	rc_get_readers_sub(c, inst, sub_inst, &reader_data, NULL, NULL, NULL);

 	if (reader_data.ReaderCount == 0) {
 		return;
 	}

 	if (sub_inst->WriteMask) {
 		file = RC_FILE_TEMPORARY;
 		writemask = sub_inst->WriteMask;
 	} else if (sub_inst->OutputWriteMask) {
 		file = RC_FILE_OUTPUT;
 		writemask = sub_inst->OutputWriteMask;
 	} else {
 		writemask = 0;
 		file = RC_FILE_NONE;
 	}
 	new_var = rc_variable(c, file, sub_inst->DestIndex, writemask,
 								&reader_data);
 	get_variable_helper(variable_list, new_var);
 }

 /**
  * Generate a list of variables used by the shader program.  Each instruction
  * that writes to a register is considered a variable.  The struct rc_variable
  * data structure includes a list of readers and is essentially a
  * definition-use chain.  Any two variables that share a reader are considered
  * "friends" and they are linked together via the Friend attribute.
  */
 struct rc_list * rc_get_variables(struct radeon_compiler * c)
 {
 	struct rc_instruction * inst;
 	struct rc_list * variable_list = NULL;

 	for (inst = c->Program.Instructions.Next;
 					inst != &c->Program.Instructions;
 					inst = inst->Next) {
 		struct rc_reader_data reader_data;
 		struct rc_variable * new_var;
 		memset(&reader_data, 0, sizeof(reader_data));

 		if (inst->Type == RC_INSTRUCTION_NORMAL) {
 			rc_get_readers(c, inst, &reader_data, NULL, NULL, NULL);
 			if (reader_data.ReaderCount == 0) {
 				continue;
 			}
 			new_var = rc_variable(c, inst->U.I.DstReg.File,
 				inst->U.I.DstReg.Index,
 				inst->U.I.DstReg.WriteMask, &reader_data);
 			get_variable_helper(&variable_list, new_var);
 		} else {
 			get_variable_pair_helper(&variable_list, c, inst,
 							&inst->U.P.RGB);
 			get_variable_pair_helper(&variable_list, c, inst,
 							&inst->U.P.Alpha);
 		}
 	}

 	return variable_list;
 }

 /**
  * @return The bitwise or of the writemasks of a variable and all of its
  * friends.
  */
 unsigned int rc_variable_writemask_sum(struct rc_variable * var)
 {
 	unsigned int writemask = 0;
 	while(var) {
 		writemask |= var->Dst.WriteMask;
 		var = var->Friend;
 	}
 	return writemask;
 }

 /*
  * @return A list of readers for a variable and its friends.  Readers
  * that read from two different variable friends are only included once in
  * this list.
  */
 struct rc_list * rc_variable_readers_union(struct rc_variable * var)
 {
 	struct rc_list * list = NULL;
 	while (var) {
 		unsigned int i;
 		for (i = 0; i < var->ReaderCount; i++) {
 			struct rc_list * temp;
 			struct rc_reader * a = &var->Readers[i];
 			unsigned int match = 0;
 			for (temp = list; temp; temp = temp->Next) {
 				struct rc_reader * b = temp->Item;
 				if (a->Inst->Type != b->Inst->Type) {
 					continue;
 				}
 				if (a->Inst->Type == RC_INSTRUCTION_NORMAL) {
 					if (a->U.I.Src == b->U.I.Src) {
 						match = 1;
 						break;
 					}
 				}
 				if (a->Inst->Type == RC_INSTRUCTION_PAIR) {
 					if (a->U.P.Arg == b->U.P.Arg
 					    && a->U.P.Src == b->U.P.Src) {
 						match = 1;
 						break;
 					}
 				}
 			}
 			if (match) {
 				continue;
 			}
 			rc_list_add(&list, rc_list(&var->C->Pool, a));
 		}
 		var = var->Friend;
 	}
 	return list;
 }

 static unsigned int reader_equals_src(
 	struct rc_reader reader,
 	unsigned int src_type,
 	void * src)
 {
 	if (reader.Inst->Type != src_type) {
 		return 0;
 	}
 	if (src_type == RC_INSTRUCTION_NORMAL) {
 		return reader.U.I.Src == src;
 	} else {
 		return reader.U.P.Src == src;
 	}
 }

 static unsigned int variable_writes_src(
 	struct rc_variable * var,
 	unsigned int src_type,
 	void * src)
 {
 	unsigned int i;
 	for (i = 0; i < var->ReaderCount; i++) {
 		if (reader_equals_src(var->Readers[i], src_type, src)) {
 			return 1;
 		}
 	}
 	return 0;
 }


 struct rc_list * rc_variable_list_get_writers(
 	struct rc_list * var_list,
 	unsigned int src_type,
 	void * src)
 {
 	struct rc_list * list_ptr;
 	struct rc_list * writer_list = NULL;
 	for (list_ptr = var_list; list_ptr; list_ptr = list_ptr->Next) {
 		struct rc_variable * var = list_ptr->Item;
 		if (variable_writes_src(var, src_type, src)) {
 			struct rc_variable * friend;
 			rc_list_add(&writer_list, rc_list(&var->C->Pool, var));
 			for (friend = var->Friend; friend;
 						friend = friend->Friend) {
 				if (variable_writes_src(friend, src_type, src)) {
 					rc_list_add(&writer_list,
 						rc_list(&var->C->Pool, friend));
 				}
 			}
 			/* Once we have indentifed the variable and its
 			 * friends that write this source, we can stop
 			 * stop searching, because we know know of the
 			 * other variables in the list will write this source.
 			 * If they did they would be friends of var.
 			 */
 			break;
 		}
 	}
 	return writer_list;
 }

 struct rc_list * rc_variable_list_get_writers_one_reader(
 	struct rc_list * var_list,
 	unsigned int src_type,
 	void * src)
 {
 	struct rc_list * writer_list =
 		rc_variable_list_get_writers(var_list, src_type, src);
 	struct rc_list * reader_list =
 		rc_variable_readers_union(writer_list->Item);
 	if (rc_list_count(reader_list) > 1) {
 		return NULL;
 	} else {
 		return writer_list;
 	}
 }

 void rc_variable_print(struct rc_variable * var)
 {
 	unsigned int i;
 	while (var) {
 		fprintf(stderr, "%u: TEMP[%u].%u: ",
 			var->Inst->IP, var->Dst.Index, var->Dst.WriteMask);
 		for (i = 0; i < 4; i++) {
 			fprintf(stderr, "chan %u: start=%u end=%u ", i,
 					var->Live[i].Start, var->Live[i].End);
 		}
 		fprintf(stderr, "%u readers\n", var->ReaderCount);
 		if (var->Friend) {
 			fprintf(stderr, "Friend: \n\t");
 		}
 		var = var->Friend;
 	}
 }
	/*
	* Copyright 2011 Tom Stellard <tstellar@gmail.com>
	*
	* All Rights Reserved.
	*
	* Permission is hereby granted, free of charge, to any person obtaining
	* a copy of this software and associated documentation files (the
	* "Software"), to deal in the Software without restriction, including
	* without limitation the rights to use, copy, modify, merge, publish,
	* distribute, sublicense, and/or sell copies of the Software, and to
	* permit persons to whom the Software is furnished to do so, subject to
	* the following conditions:
	*
	* The above copyright notice and this permission notice (including the
	* next paragraph) shall be included in all copies or substantial
	* portions of the Software.
	*
	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
	* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
	* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
	* IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
	* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
	* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
	* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	*
	*/

	#include "radeon_variable.h"

	#include "memory_pool.h"
	#include "radeon_compiler_util.h"
	#include "radeon_dataflow.h"
	#include "radeon_list.h"
	#include "radeon_opcodes.h"
	#include "radeon_program.h"

	/**
	* Rewrite the index and writemask for the destination register of var
	* and its friends to new_index and new_writemask. This function also takes
	* care of rewriting the swizzles for the sources of var.
	*/
	void rc_variable_change_dst(
	struct rc_variable * var,
	unsigned int new_index,
	unsigned int new_writemask)
	{
	struct rc_variable * var_ptr;
	struct rc_list * readers;
	unsigned int old_mask = rc_variable_writemask_sum(var);
	unsigned int conversion_swizzle =
	rc_make_conversion_swizzle(old_mask, new_writemask);

	for (var_ptr = var; var_ptr; var_ptr = var_ptr->Friend) {
	if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) {
	rc_normal_rewrite_writemask(var_ptr->Inst,
	conversion_swizzle);
	var_ptr->Inst->U.I.DstReg.Index = new_index;
	} else {
	struct rc_pair_sub_instruction * sub;
	if (var_ptr->Dst.WriteMask == RC_MASK_W) {
	assert(new_writemask & RC_MASK_W);
	sub = &var_ptr->Inst->U.P.Alpha;
	} else {
	sub = &var_ptr->Inst->U.P.RGB;
	rc_pair_rewrite_writemask(sub,
	conversion_swizzle);
	}
	sub->DestIndex = new_index;
	}
	}

	readers = rc_variable_readers_union(var);

	for ( ; readers; readers = readers->Next) {
	struct rc_reader * reader = readers->Item;
	if (reader->Inst->Type == RC_INSTRUCTION_NORMAL) {
	reader->U.I.Src->Index = new_index;
	reader->U.I.Src->Swizzle = rc_rewrite_swizzle(
	reader->U.I.Src->Swizzle, conversion_swizzle);
	} else {
	struct rc_pair_instruction * pair_inst =
	&reader->Inst->U.P;
	unsigned int src_type = rc_source_type_swz(
	reader->U.P.Arg->Swizzle);

	int src_index = reader->U.P.Arg->Source;
	if (src_index == RC_PAIR_PRESUB_SRC) {
	src_index = rc_pair_get_src_index(
	pair_inst, reader->U.P.Src);
	}
	/* Try to delete the old src, it is OK if this fails,
	* because rc_pair_alloc_source might be able to
	* find a source the ca be reused.
	*/
	if (rc_pair_remove_src(reader->Inst, src_type,
	src_index, old_mask)) {
	/* Reuse the source index of the source that
	* was just deleted and set its register
	* index. We can't use rc_pair_alloc_source
	* for this becuase it might return a source
	* index that is already being used. */
	if (src_type & RC_SOURCE_RGB) {
	pair_inst->RGB.Src[src_index]
	.Used = 1;
	pair_inst->RGB.Src[src_index]
	.Index = new_index;
	pair_inst->RGB.Src[src_index]
	.File = RC_FILE_TEMPORARY;
	}
	if (src_type & RC_SOURCE_ALPHA) {
	pair_inst->Alpha.Src[src_index]
	.Used = 1;
	pair_inst->Alpha.Src[src_index]
	.Index = new_index;
	pair_inst->Alpha.Src[src_index]
	.File = RC_FILE_TEMPORARY;
	}
	} else {
	src_index = rc_pair_alloc_source(
	&reader->Inst->U.P,
	src_type & RC_SOURCE_RGB,
	src_type & RC_SOURCE_ALPHA,
	RC_FILE_TEMPORARY,
	new_index);
	if (src_index < 0) {
	rc_error(var->C, "Rewrite of inst %u failed "
	"Can't allocate source for "
	"Inst %u src_type=%x "
	"new_index=%u new_mask=%u\n",
	var->Inst->IP, reader->Inst->IP, src_type, new_index, new_writemask);
	continue;
	}
	}
	reader->U.P.Arg->Swizzle = rc_rewrite_swizzle(
	reader->U.P.Arg->Swizzle, conversion_swizzle);
	if (reader->U.P.Arg->Source != RC_PAIR_PRESUB_SRC) {
	reader->U.P.Arg->Source = src_index;
	}
	}
	}
	}

	/**
	* Compute the live intervals for var and its friends.
	*/
	void rc_variable_compute_live_intervals(struct rc_variable * var)
	{
	while(var) {
	unsigned int i;
	unsigned int start = var->Inst->IP;

	for (i = 0; i < var->ReaderCount; i++) {
	unsigned int chan;
	unsigned int chan_start = start;
	unsigned int chan_end = var->Readers[i].Inst->IP;
	unsigned int mask = var->Readers[i].WriteMask;
	struct rc_instruction * inst;

	/* Extend the live interval of T0 to the start of the
	* loop for sequences like:
	* BGNLOOP
	* read T0
	* ...
	* write T0
	* ENDLOOP
	*/
	if (var->Readers[i].Inst->IP < start) {
	struct rc_instruction * bgnloop =
	rc_match_endloop(var->Readers[i].Inst);
	chan_start = bgnloop->IP;
	}

	/* Extend the live interval of T0 to the start of the
	* loop in case there is a BRK instruction in the loop
	* (we don't actually check for a BRK instruction we
	* assume there is one somewhere in the loop, which
	* there usually is) for sequences like:
	* BGNLOOP
	* ...
	* conditional BRK
	* ...
	* write T0
	* ENDLOOP
	* read T0
	***************************************************
	* Extend the live interval of T0 to the end of the
	* loop for sequences like:
	* write T0
	* BGNLOOP
	* ...
	* read T0
	* ENDLOOP
	*/
	for (inst = var->Inst; inst != var->Readers[i].Inst;
	inst = inst->Next) {
	rc_opcode op = rc_get_flow_control_inst(inst);
	if (op == RC_OPCODE_ENDLOOP) {
	struct rc_instruction * bgnloop =
	rc_match_endloop(inst);
	if (bgnloop->IP < chan_start) {
	chan_start = bgnloop->IP;
	}
	} else if (op == RC_OPCODE_BGNLOOP) {
	struct rc_instruction * endloop =
	rc_match_bgnloop(inst);
	if (endloop->IP > chan_end) {
	chan_end = endloop->IP;
	}
	}
	}

	for (chan = 0; chan < 4; chan++) {
	if ((mask >> chan) & 0x1) {
	if (!var->Live[chan].Used
	\|\| chan_start < var->Live[chan].Start) {
	var->Live[chan].Start =
	chan_start;
	}
	if (!var->Live[chan].Used
	\|\| chan_end > var->Live[chan].End) {
	var->Live[chan].End = chan_end;
	}
	var->Live[chan].Used = 1;
	}
	}
	}
	var = var->Friend;
	}
	}

	/**
	* @return 1 if a and b share a reader
	* @return 0 if they do not
	*/
	static unsigned int readers_intersect(
	struct rc_variable * a,
	struct rc_variable * b)
	{
	unsigned int a_index, b_index;
	for (a_index = 0; a_index < a->ReaderCount; a_index++) {
	struct rc_reader reader_a = a->Readers[a_index];
	for (b_index = 0; b_index < b->ReaderCount; b_index++) {
	struct rc_reader reader_b = b->Readers[b_index];
	if (reader_a.Inst->Type == RC_INSTRUCTION_NORMAL
	&& reader_b.Inst->Type == RC_INSTRUCTION_NORMAL
	&& reader_a.U.I.Src == reader_b.U.I.Src) {

	return 1;
	}
	if (reader_a.Inst->Type == RC_INSTRUCTION_PAIR
	&& reader_b.Inst->Type == RC_INSTRUCTION_PAIR
	&& reader_a.U.P.Src == reader_b.U.P.Src) {

	return 1;
	}
	}
	}
	return 0;
	}

	void rc_variable_add_friend(
	struct rc_variable * var,
	struct rc_variable * friend)
	{
	assert(var->Dst.Index == friend->Dst.Index);
	while(var->Friend) {
	var = var->Friend;
	}
	var->Friend = friend;
	}

	struct rc_variable * rc_variable(
	struct radeon_compiler * c,
	unsigned int DstFile,
	unsigned int DstIndex,
	unsigned int DstWriteMask,
	struct rc_reader_data * reader_data)
	{
	struct rc_variable * new =
	memory_pool_malloc(&c->Pool, sizeof(struct rc_variable));
	memset(new, 0, sizeof(struct rc_variable));
	new->C = c;
	new->Dst.File = DstFile;
	new->Dst.Index = DstIndex;
	new->Dst.WriteMask = DstWriteMask;
	if (reader_data) {
	new->Inst = reader_data->Writer;
	new->ReaderCount = reader_data->ReaderCount;
	new->Readers = reader_data->Readers;
	}
	return new;
	}

	static void get_variable_helper(
	struct rc_list ** variable_list,
	struct rc_variable * variable)
	{
	struct rc_list * list_ptr;
	for (list_ptr = *variable_list; list_ptr; list_ptr = list_ptr->Next) {
	struct rc_variable * var;
	for (var = list_ptr->Item; var; var = var->Friend) {
	if (readers_intersect(var, variable)) {
	rc_variable_add_friend(var, variable);
	return;
	}
	}
	}
	rc_list_add(variable_list, rc_list(&variable->C->Pool, variable));
	}

	static void get_variable_pair_helper(
	struct rc_list ** variable_list,
	struct radeon_compiler * c,
	struct rc_instruction * inst,
	struct rc_pair_sub_instruction * sub_inst)
	{
	struct rc_reader_data reader_data;
	struct rc_variable * new_var;
	rc_register_file file;
	unsigned int writemask;

	if (sub_inst->Opcode == RC_OPCODE_NOP) {
	return;
	}
	memset(&reader_data, 0, sizeof(struct rc_reader_data));
	rc_get_readers_sub(c, inst, sub_inst, &reader_data, NULL, NULL, NULL);

	if (reader_data.ReaderCount == 0) {
	return;
	}

	if (sub_inst->WriteMask) {
	file = RC_FILE_TEMPORARY;
	writemask = sub_inst->WriteMask;
	} else if (sub_inst->OutputWriteMask) {
	file = RC_FILE_OUTPUT;
	writemask = sub_inst->OutputWriteMask;
	} else {
	writemask = 0;
	file = RC_FILE_NONE;
	}
	new_var = rc_variable(c, file, sub_inst->DestIndex, writemask,
	&reader_data);
	get_variable_helper(variable_list, new_var);
	}

	/**
	* Generate a list of variables used by the shader program. Each instruction
	* that writes to a register is considered a variable. The struct rc_variable
	* data structure includes a list of readers and is essentially a
	* definition-use chain. Any two variables that share a reader are considered
	* "friends" and they are linked together via the Friend attribute.
	*/
	struct rc_list * rc_get_variables(struct radeon_compiler * c)
	{
	struct rc_instruction * inst;
	struct rc_list * variable_list = NULL;

	for (inst = c->Program.Instructions.Next;
	inst != &c->Program.Instructions;
	inst = inst->Next) {
	struct rc_reader_data reader_data;
	struct rc_variable * new_var;
	memset(&reader_data, 0, sizeof(reader_data));

	if (inst->Type == RC_INSTRUCTION_NORMAL) {
	rc_get_readers(c, inst, &reader_data, NULL, NULL, NULL);
	if (reader_data.ReaderCount == 0) {
	continue;
	}
	new_var = rc_variable(c, inst->U.I.DstReg.File,
	inst->U.I.DstReg.Index,
	inst->U.I.DstReg.WriteMask, &reader_data);
	get_variable_helper(&variable_list, new_var);
	} else {
	get_variable_pair_helper(&variable_list, c, inst,
	&inst->U.P.RGB);
	get_variable_pair_helper(&variable_list, c, inst,
	&inst->U.P.Alpha);
	}
	}

	return variable_list;
	}

	/**
	* @return The bitwise or of the writemasks of a variable and all of its
	* friends.
	*/
	unsigned int rc_variable_writemask_sum(struct rc_variable * var)
	{
	unsigned int writemask = 0;
	while(var) {
	writemask \|= var->Dst.WriteMask;
	var = var->Friend;
	}
	return writemask;
	}

	/*
	* @return A list of readers for a variable and its friends. Readers
	* that read from two different variable friends are only included once in
	* this list.
	*/
	struct rc_list * rc_variable_readers_union(struct rc_variable * var)
	{
	struct rc_list * list = NULL;
	while (var) {
	unsigned int i;
	for (i = 0; i < var->ReaderCount; i++) {
	struct rc_list * temp;
	struct rc_reader * a = &var->Readers[i];
	unsigned int match = 0;
	for (temp = list; temp; temp = temp->Next) {
	struct rc_reader * b = temp->Item;
	if (a->Inst->Type != b->Inst->Type) {
	continue;
	}
	if (a->Inst->Type == RC_INSTRUCTION_NORMAL) {
	if (a->U.I.Src == b->U.I.Src) {
	match = 1;
	break;
	}
	}
	if (a->Inst->Type == RC_INSTRUCTION_PAIR) {
	if (a->U.P.Arg == b->U.P.Arg
	&& a->U.P.Src == b->U.P.Src) {
	match = 1;
	break;
	}
	}
	}
	if (match) {
	continue;
	}
	rc_list_add(&list, rc_list(&var->C->Pool, a));
	}
	var = var->Friend;
	}
	return list;
	}

	static unsigned int reader_equals_src(
	struct rc_reader reader,
	unsigned int src_type,
	void * src)
	{
	if (reader.Inst->Type != src_type) {
	return 0;
	}
	if (src_type == RC_INSTRUCTION_NORMAL) {
	return reader.U.I.Src == src;
	} else {
	return reader.U.P.Src == src;
	}
	}

	static unsigned int variable_writes_src(
	struct rc_variable * var,
	unsigned int src_type,
	void * src)
	{
	unsigned int i;
	for (i = 0; i < var->ReaderCount; i++) {
	if (reader_equals_src(var->Readers[i], src_type, src)) {
	return 1;
	}
	}
	return 0;
	}


	struct rc_list * rc_variable_list_get_writers(
	struct rc_list * var_list,
	unsigned int src_type,
	void * src)
	{
	struct rc_list * list_ptr;
	struct rc_list * writer_list = NULL;
	for (list_ptr = var_list; list_ptr; list_ptr = list_ptr->Next) {
	struct rc_variable * var = list_ptr->Item;
	if (variable_writes_src(var, src_type, src)) {
	struct rc_variable * friend;
	rc_list_add(&writer_list, rc_list(&var->C->Pool, var));
	for (friend = var->Friend; friend;
	friend = friend->Friend) {
	if (variable_writes_src(friend, src_type, src)) {
	rc_list_add(&writer_list,
	rc_list(&var->C->Pool, friend));
	}
	}
	/* Once we have indentifed the variable and its
	* friends that write this source, we can stop
	* stop searching, because we know know of the
	* other variables in the list will write this source.
	* If they did they would be friends of var.
	*/
	break;
	}
	}
	return writer_list;
	}

	struct rc_list * rc_variable_list_get_writers_one_reader(
	struct rc_list * var_list,
	unsigned int src_type,
	void * src)
	{
	struct rc_list * writer_list =
	rc_variable_list_get_writers(var_list, src_type, src);
	struct rc_list * reader_list =
	rc_variable_readers_union(writer_list->Item);
	if (rc_list_count(reader_list) > 1) {
	return NULL;
	} else {
	return writer_list;
	}
	}

	void rc_variable_print(struct rc_variable * var)
	{
	unsigned int i;
	while (var) {
	fprintf(stderr, "%u: TEMP[%u].%u: ",
	var->Inst->IP, var->Dst.Index, var->Dst.WriteMask);
	for (i = 0; i < 4; i++) {
	fprintf(stderr, "chan %u: start=%u end=%u ", i,
	var->Live[i].Start, var->Live[i].End);
	}
	fprintf(stderr, "%u readers\n", var->ReaderCount);
	if (var->Friend) {
	fprintf(stderr, "Friend: \n\t");
	}
	var = var->Friend;
	}
	}