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

 /*
  * Copyright (C) 2009 Nicolai Haehnle.
  * 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_program_pair.h"

 #include <stdio.h>

 #include "main/glheader.h"
 #include "program/register_allocate.h"
 #include "ralloc.h"

 #include "r300_fragprog_swizzle.h"
 #include "radeon_compiler.h"
 #include "radeon_compiler_util.h"
 #include "radeon_dataflow.h"
 #include "radeon_list.h"
 #include "radeon_variable.h"

 #define VERBOSE 0

 #define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)


 struct register_info {
 	struct live_intervals Live[4];

 	unsigned int Used:1;
 	unsigned int Allocated:1;
 	unsigned int File:3;
 	unsigned int Index:RC_REGISTER_INDEX_BITS;
 	unsigned int Writemask;
 };

 struct regalloc_state {
 	struct radeon_compiler * C;

 	struct register_info * Input;
 	unsigned int NumInputs;

 	struct register_info * Temporary;
 	unsigned int NumTemporaries;

 	unsigned int Simple;
 	int LoopEnd;
 };

 enum rc_reg_class {
 	RC_REG_CLASS_SINGLE,
 	RC_REG_CLASS_DOUBLE,
 	RC_REG_CLASS_TRIPLE,
 	RC_REG_CLASS_ALPHA,
 	RC_REG_CLASS_SINGLE_PLUS_ALPHA,
 	RC_REG_CLASS_DOUBLE_PLUS_ALPHA,
 	RC_REG_CLASS_TRIPLE_PLUS_ALPHA,
 	RC_REG_CLASS_X,
 	RC_REG_CLASS_Y,
 	RC_REG_CLASS_Z,
 	RC_REG_CLASS_XY,
 	RC_REG_CLASS_YZ,
 	RC_REG_CLASS_XZ,
 	RC_REG_CLASS_XW,
 	RC_REG_CLASS_YW,
 	RC_REG_CLASS_ZW,
 	RC_REG_CLASS_XYW,
 	RC_REG_CLASS_YZW,
 	RC_REG_CLASS_XZW,
 	RC_REG_CLASS_COUNT
 };

 struct rc_class {
 	enum rc_reg_class Class;

 	unsigned int WritemaskCount;

 	/** This is 1 if this class is being used by the register allocator
 	 * and 0 otherwise */
 	unsigned int Used;

 	/** This is the ID number assigned to this class by ra. */
 	unsigned int Id;

 	/** List of writemasks that belong to this class */
 	unsigned int Writemasks[3];


 };

 static void print_live_intervals(struct live_intervals * src)
 {
 	if (!src || !src->Used) {
 		DBG("(null)");
 		return;
 	}

 	DBG("(%i,%i)", src->Start, src->End);
 }

 static int overlap_live_intervals(struct live_intervals * a, struct live_intervals * b)
 {
 	if (VERBOSE) {
 		DBG("overlap_live_intervals: ");
 		print_live_intervals(a);
 		DBG(" to ");
 		print_live_intervals(b);
 		DBG("\n");
 	}

 	if (!a->Used || !b->Used) {
 		DBG("    unused interval\n");
 		return 0;
 	}

 	if (a->Start > b->Start) {
 		if (a->Start < b->End) {
 			DBG("    overlap\n");
 			return 1;
 		}
 	} else if (b->Start > a->Start) {
 		if (b->Start < a->End) {
 			DBG("    overlap\n");
 			return 1;
 		}
 	} else { /* a->Start == b->Start */
 		if (a->Start != a->End && b->Start != b->End) {
 			DBG("    overlap\n");
 			return 1;
 		}
 	}

 	DBG("    no overlap\n");

 	return 0;
 }

 static void scan_read_callback(void * data, struct rc_instruction * inst,
 		rc_register_file file, unsigned int index, unsigned int mask)
 {
 	struct regalloc_state * s = data;
 	struct register_info * reg;
 	unsigned int i;

 	if (file != RC_FILE_INPUT)
 		return;

 	s->Input[index].Used = 1;
 	reg = &s->Input[index];

 	for (i = 0; i < 4; i++) {
 		if (!((mask >> i) & 0x1)) {
 			continue;
 		}
 		reg->Live[i].Used = 1;
 		reg->Live[i].Start = 0;
 		reg->Live[i].End =
 			s->LoopEnd > inst->IP ? s->LoopEnd : inst->IP;
 	}
 }

 static void remap_register(void * data, struct rc_instruction * inst,
 		rc_register_file * file, unsigned int * index)
 {
 	struct regalloc_state * s = data;
 	const struct register_info * reg;

 	if (*file == RC_FILE_TEMPORARY && s->Simple)
 		reg = &s->Temporary[*index];
 	else if (*file == RC_FILE_INPUT)
 		reg = &s->Input[*index];
 	else
 		return;

 	if (reg->Allocated) {
 		*index = reg->Index;
 	}
 }

 static void alloc_input_simple(void * data, unsigned int input,
 							unsigned int hwreg)
 {
 	struct regalloc_state * s = data;

 	if (input >= s->NumInputs)
 		return;

 	s->Input[input].Allocated = 1;
 	s->Input[input].File = RC_FILE_TEMPORARY;
 	s->Input[input].Index = hwreg;
 }

 /* This functions offsets the temporary register indices by the number
  * of input registers, because input registers are actually temporaries and
  * should not occupy the same space.
  *
  * This pass is supposed to be used to maintain correct allocation of inputs
  * if the standard register allocation is disabled. */
 static void do_regalloc_inputs_only(struct regalloc_state * s)
 {
 	for (unsigned i = 0; i < s->NumTemporaries; i++) {
 		s->Temporary[i].Allocated = 1;
 		s->Temporary[i].File = RC_FILE_TEMPORARY;
 		s->Temporary[i].Index = i + s->NumInputs;
 	}
 }

 static unsigned int is_derivative(rc_opcode op)
 {
 	return (op == RC_OPCODE_DDX || op == RC_OPCODE_DDY);
 }

 static int find_class(
 	struct rc_class * classes,
 	unsigned int writemask,
 	unsigned int max_writemask_count)
 {
 	unsigned int i;
 	for (i = 0; i < RC_REG_CLASS_COUNT; i++) {
 		unsigned int j;
 		if (classes[i].WritemaskCount > max_writemask_count) {
 			continue;
 		}
 		for (j = 0; j < 3; j++) {
 			if (classes[i].Writemasks[j] == writemask) {
 				return i;
 			}
 		}
 	}
 	return -1;
 }

 struct variable_get_class_cb_data {
 	unsigned int * can_change_writemask;
 	unsigned int conversion_swizzle;
 };

 static void variable_get_class_read_cb(
 	void * userdata,
 	struct rc_instruction * inst,
 	struct rc_pair_instruction_arg * arg,
 	struct rc_pair_instruction_source * src)
 {
 	struct variable_get_class_cb_data * d = userdata;
 	unsigned int new_swizzle = rc_adjust_channels(arg->Swizzle,
 							d->conversion_swizzle);
 	if (!r300_swizzle_is_native_basic(new_swizzle)) {
 		*d->can_change_writemask = 0;
 	}
 }

 static enum rc_reg_class variable_get_class(
 	struct rc_variable * variable,
 	struct rc_class * classes)
 {
 	unsigned int i;
 	unsigned int can_change_writemask= 1;
 	unsigned int writemask = rc_variable_writemask_sum(variable);
 	struct rc_list * readers = rc_variable_readers_union(variable);
 	int class_index;

 	if (!variable->C->is_r500) {
 		struct rc_class c;
 		struct rc_variable * var_ptr;
 		/* The assumption here is that if an instruction has type
 		 * RC_INSTRUCTION_NORMAL then it is a TEX instruction.
 		 * r300 and r400 can't swizzle the result of a TEX lookup. */
 		for (var_ptr = variable; var_ptr; var_ptr = var_ptr->Friend) {
 			if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) {
 				writemask = RC_MASK_XYZW;
 			}
 		}

 		/* Check if it is possible to do swizzle packing for r300/r400
 		 * without creating non-native swizzles. */
 		class_index = find_class(classes, writemask, 3);
 		if (class_index < 0) {
 			goto error;
 		}
 		c = classes[class_index];
 		if (c.WritemaskCount == 1) {
 			goto done;
 		}
 		for (i = 0; i < c.WritemaskCount; i++) {
 			struct rc_variable * var_ptr;
 			for (var_ptr = variable; var_ptr;
 						var_ptr = var_ptr->Friend) {
 				int j;
 				unsigned int conversion_swizzle =
 						rc_make_conversion_swizzle(
 						writemask, c.Writemasks[i]);
 				struct variable_get_class_cb_data d;
 				d.can_change_writemask = &can_change_writemask;
 				d.conversion_swizzle = conversion_swizzle;
 				/* If we get this far var_ptr->Inst has to
 				 * be a pair instruction.  If variable or any
 				 * of its friends are normal instructions,
 				 * then the writemask will be set to RC_MASK_XYZW
 				 * and the function will return before it gets
 				 * here. */
 				rc_pair_for_all_reads_arg(var_ptr->Inst,
 					variable_get_class_read_cb, &d);

 				for (j = 0; j < var_ptr->ReaderCount; j++) {
 					unsigned int old_swizzle;
 					unsigned int new_swizzle;
 					struct rc_reader r = var_ptr->Readers[j];
 					if (r.Inst->Type ==
 							RC_INSTRUCTION_PAIR ) {
 						old_swizzle = r.U.P.Arg->Swizzle;
 					} else {
 						old_swizzle = r.U.I.Src->Swizzle;
 					}
 					new_swizzle = rc_adjust_channels(
 						old_swizzle, conversion_swizzle);
 					if (!r300_swizzle_is_native_basic(
 								new_swizzle)) {
 						can_change_writemask = 0;
 						break;
 					}
 				}
 				if (!can_change_writemask) {
 					break;
 				}
 			}
 			if (!can_change_writemask) {
 				break;
 			}
 		}
 	}

 	if (variable->Inst->Type == RC_INSTRUCTION_PAIR) {
 		/* DDX/DDY seem to always fail when their writemasks are
 		 * changed.*/
 		if (is_derivative(variable->Inst->U.P.RGB.Opcode)
 		    || is_derivative(variable->Inst->U.P.Alpha.Opcode)) {
 			can_change_writemask = 0;
 		}
 	}
 	for ( ; readers; readers = readers->Next) {
 		struct rc_reader * r = readers->Item;
 		if (r->Inst->Type == RC_INSTRUCTION_PAIR) {
 			if (r->U.P.Arg->Source == RC_PAIR_PRESUB_SRC) {
 				can_change_writemask = 0;
 				break;
 			}
 			/* DDX/DDY also fail when their swizzles are changed. */
 			if (is_derivative(r->Inst->U.P.RGB.Opcode)
 			    || is_derivative(r->Inst->U.P.Alpha.Opcode)) {
 				can_change_writemask = 0;
 				break;
 			}
 		}
 	}

 	class_index = find_class(classes, writemask,
 						can_change_writemask ? 3 : 1);
 done:
 	if (class_index > -1) {
 		return classes[class_index].Class;
 	} else {
 error:
 		rc_error(variable->C,
 				"Could not find class for index=%u mask=%u\n",
 				variable->Dst.Index, writemask);
 		return 0;
 	}
 }

 static unsigned int overlap_live_intervals_array(
 	struct live_intervals * a,
 	struct live_intervals * b)
 {
 	unsigned int a_chan, b_chan;
 	for (a_chan = 0; a_chan < 4; a_chan++) {
 		for (b_chan = 0; b_chan < 4; b_chan++) {
 			if (overlap_live_intervals(&a[a_chan], &b[b_chan])) {
 					return 1;
 			}
 		}
 	}
 	return 0;
 }

 static unsigned int reg_get_index(int reg)
 {
 	return reg / RC_MASK_XYZW;
 }

 static unsigned int reg_get_writemask(int reg)
 {
 	return (reg % RC_MASK_XYZW) + 1;
 }

 static int get_reg_id(unsigned int index, unsigned int writemask)
 {
 	assert(writemask);
 	if (writemask == 0) {
 		return 0;
 	}
 	return (index * RC_MASK_XYZW) + (writemask - 1);
 }

 #if VERBOSE
 static void print_reg(int reg)
 {
 	unsigned int index = reg_get_index(reg);
 	unsigned int mask = reg_get_writemask(reg);
 	fprintf(stderr, "Temp[%u].%c%c%c%c", index,
 		mask & RC_MASK_X ? 'x' : '_',
 		mask & RC_MASK_Y ? 'y' : '_',
 		mask & RC_MASK_Z ? 'z' : '_',
 		mask & RC_MASK_W ? 'w' : '_');
 }
 #endif

 static void add_register_conflicts(
 	struct ra_regs * regs,
 	unsigned int max_temp_regs)
 {
 	unsigned int index, a_mask, b_mask;
 	for (index = 0; index < max_temp_regs; index++) {
 		for(a_mask = 1; a_mask <= RC_MASK_XYZW; a_mask++) {
 			for (b_mask = a_mask + 1; b_mask <= RC_MASK_XYZW;
 								b_mask++) {
 				if (a_mask & b_mask) {
 					ra_add_reg_conflict(regs,
 						get_reg_id(index, a_mask),
 						get_reg_id(index, b_mask));
 				}
 			}
 		}
 	}
 }

 static void do_advanced_regalloc(struct regalloc_state * s)
 {
 	struct rc_class rc_class_list [] = {
 		{RC_REG_CLASS_SINGLE, 3, 0, 0,
 			{RC_MASK_X,
 			 RC_MASK_Y,
 			 RC_MASK_Z}},
 		{RC_REG_CLASS_DOUBLE, 3, 0, 0,
 			{RC_MASK_X | RC_MASK_Y,
 			 RC_MASK_X | RC_MASK_Z,
 			 RC_MASK_Y | RC_MASK_Z}},
 		{RC_REG_CLASS_TRIPLE, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_Y | RC_MASK_Z,
 			 RC_MASK_NONE,
 			 RC_MASK_NONE}},
 		{RC_REG_CLASS_ALPHA, 1, 0, 0,
 			{RC_MASK_W,
 			 RC_MASK_NONE,
 			 RC_MASK_NONE}},
 		{RC_REG_CLASS_SINGLE_PLUS_ALPHA, 3, 0, 0,
 			{RC_MASK_X | RC_MASK_W,
 			 RC_MASK_Y | RC_MASK_W,
 			 RC_MASK_Z | RC_MASK_W}},
 		{RC_REG_CLASS_DOUBLE_PLUS_ALPHA, 3, 0, 0,
 			{RC_MASK_X | RC_MASK_Y | RC_MASK_W,
 			 RC_MASK_X | RC_MASK_Z | RC_MASK_W,
 			 RC_MASK_Y | RC_MASK_Z | RC_MASK_W}},
 		{RC_REG_CLASS_TRIPLE_PLUS_ALPHA, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_Y | RC_MASK_Z | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_X, 1, 0, 0,
 			{RC_MASK_X,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_Y, 1, 0, 0,
 			{RC_MASK_Y,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_Z, 1, 0, 0,
 			{RC_MASK_Z,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_XY, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_Y,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_YZ, 1, 0, 0,
 			{RC_MASK_Y | RC_MASK_Z,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_XZ, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_Z,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_XW, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_YW, 1, 0, 0,
 			{RC_MASK_Y | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_ZW, 1, 0, 0,
 			{RC_MASK_Z | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_XYW, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_Y | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_YZW, 1, 0, 0,
 			{RC_MASK_Y | RC_MASK_Z | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}},
 		{RC_REG_CLASS_XZW, 1, 0, 0,
 			{RC_MASK_X | RC_MASK_Z | RC_MASK_W,
 			RC_MASK_NONE,
 			RC_MASK_NONE}}
 	};

 	unsigned int i, j, index, input_node, node_count, node_index;
 	unsigned int * node_classes;
 	unsigned int * input_classes;
 	struct rc_instruction * inst;
 	struct rc_list * var_ptr;
 	struct rc_list * variables;
 	struct ra_regs * regs;
 	struct ra_graph * graph;

 	/* Allocate the main ra data structure */
 	regs = ra_alloc_reg_set(NULL, s->C->max_temp_regs * RC_MASK_XYZW);

 	/* Get list of program variables */
 	variables = rc_get_variables(s->C);
 	node_count = rc_list_count(variables);
 	node_classes = memory_pool_malloc(&s->C->Pool,
 			node_count * sizeof(unsigned int));
 	input_classes = memory_pool_malloc(&s->C->Pool,
 			s->NumInputs * sizeof(unsigned int));

 	for (var_ptr = variables, node_index = 0; var_ptr;
 					var_ptr = var_ptr->Next, node_index++) {
 		unsigned int class_index;
 		/* Compute the live intervals */
 		rc_variable_compute_live_intervals(var_ptr->Item);

 		class_index = variable_get_class(var_ptr->Item,	rc_class_list);

 		/* If we haven't used this register class yet, mark it
 		 * as used and allocate space for it. */
 		if (!rc_class_list[class_index].Used) {
 			rc_class_list[class_index].Used = 1;
 			rc_class_list[class_index].Id = ra_alloc_reg_class(regs);
 		}

 		node_classes[node_index] = rc_class_list[class_index].Id;
 	}


 	/* Assign registers to the classes */
 	for (i = 0; i < RC_REG_CLASS_COUNT; i++) {
 		struct rc_class class = rc_class_list[i];
 		if (!class.Used) {
 			continue;
 		}

 		for (index = 0; index < s->C->max_temp_regs; index++) {
 			for (j = 0; j < class.WritemaskCount; j++) {
 				int reg_id = get_reg_id(index,
 							class.Writemasks[j]);
 				ra_class_add_reg(regs, class.Id, reg_id);
 			}
 		}
 	}

 	/* Add register conflicts */
 	add_register_conflicts(regs, s->C->max_temp_regs);

 	/* Calculate live intervals for input registers */
 	for (inst = s->C->Program.Instructions.Next;
 					inst != &s->C->Program.Instructions;
 					inst = inst->Next) {
 		rc_opcode op = rc_get_flow_control_inst(inst);
 		if (op == RC_OPCODE_BGNLOOP) {
 			struct rc_instruction * endloop =
 							rc_match_bgnloop(inst);
 			if (endloop->IP > s->LoopEnd) {
 				s->LoopEnd = endloop->IP;
 			}
 		}
 		rc_for_all_reads_mask(inst, scan_read_callback, s);
 	}

 	/* Create classes for input registers */
 	for (i = 0; i < s->NumInputs; i++) {
 		unsigned int chan, class_id, writemask = 0;
 		for (chan = 0; chan < 4; chan++) {
 			if (s->Input[i].Live[chan].Used) {
 				writemask |= (1 << chan);
 			}
 		}
 		s->Input[i].Writemask = writemask;
 		if (!writemask) {
 			continue;
 		}

 		class_id = ra_alloc_reg_class(regs);
 		input_classes[i] = class_id;
 		ra_class_add_reg(regs, class_id,
 				get_reg_id(s->Input[i].Index, writemask));
 	}

 	ra_set_finalize(regs);

 	graph = ra_alloc_interference_graph(regs, node_count + s->NumInputs);

 	/* Build the interference graph */
 	for (var_ptr = variables, node_index = 0; var_ptr;
 					var_ptr = var_ptr->Next,node_index++) {
 		struct rc_list * a, * b;
 		unsigned int b_index;

 		ra_set_node_class(graph, node_index, node_classes[node_index]);

 		for (a = var_ptr, b = var_ptr->Next, b_index = node_index + 1;
 						b; b = b->Next, b_index++) {
 			struct rc_variable * var_a = a->Item;
 			while (var_a) {
 				struct rc_variable * var_b = b->Item;
 				while (var_b) {
 					if (overlap_live_intervals_array(var_a->Live, var_b->Live)) {
 						ra_add_node_interference(graph,
 							node_index, b_index);
 					}
 					var_b = var_b->Friend;
 				}
 				var_a = var_a->Friend;
 			}
 		}
 	}

 	/* Add input registers to the interference graph */
 	for (i = 0, input_node = 0; i< s->NumInputs; i++) {
 		if (!s->Input[i].Writemask) {
 			continue;
 		}
 		ra_set_node_class(graph, node_count + input_node,
 							input_classes[i]);
 		for (var_ptr = variables, node_index = 0;
 				var_ptr; var_ptr = var_ptr->Next, node_index++) {
 			struct rc_variable * var = var_ptr->Item;
 			if (overlap_live_intervals_array(s->Input[i].Live,
 								var->Live)) {
 				ra_add_node_interference(graph, node_index,
 						node_count + input_node);
 			}
 		}
 		/* Manually allocate a register for this input */
 		ra_set_node_reg(graph, node_count + input_node, get_reg_id(
 				s->Input[i].Index, s->Input[i].Writemask));
 		input_node++;
 	}

 	if (!ra_allocate_no_spills(graph)) {
 		rc_error(s->C, "Ran out of hardware temporaries\n");
 		return;
 	}

 	/* Rewrite the registers */
 	for (var_ptr = variables, node_index = 0; var_ptr;
 				var_ptr = var_ptr->Next, node_index++) {
 		int reg = ra_get_node_reg(graph, node_index);
 		unsigned int writemask = reg_get_writemask(reg);
 		unsigned int index = reg_get_index(reg);
 		struct rc_variable * var = var_ptr->Item;

 		if (!s->C->is_r500 && var->Inst->Type == RC_INSTRUCTION_NORMAL) {
 			writemask = rc_variable_writemask_sum(var);
 		}

 		if (var->Dst.File == RC_FILE_INPUT) {
 			continue;
 		}
 		rc_variable_change_dst(var, index, writemask);
 	}

 	ralloc_free(graph);
 	ralloc_free(regs);
 }

 /**
  * @param user This parameter should be a pointer to an integer value.  If this
  * integer value is zero, then a simple register allocator will be used that
  * only allocates space for input registers (\sa do_regalloc_inputs_only).  If
  * user is non-zero, then the regular register allocator will be used
  * (\sa do_regalloc).
   */
 void rc_pair_regalloc(struct radeon_compiler *cc, void *user)
 {
 	struct r300_fragment_program_compiler *c =
 				(struct r300_fragment_program_compiler*)cc;
 	struct regalloc_state s;
 	int * do_full_regalloc = (int*)user;

 	memset(&s, 0, sizeof(s));
 	s.C = cc;
 	s.NumInputs = rc_get_max_index(cc, RC_FILE_INPUT) + 1;
 	s.Input = memory_pool_malloc(&cc->Pool,
 			s.NumInputs * sizeof(struct register_info));
 	memset(s.Input, 0, s.NumInputs * sizeof(struct register_info));

 	s.NumTemporaries = rc_get_max_index(cc, RC_FILE_TEMPORARY) + 1;
 	s.Temporary = memory_pool_malloc(&cc->Pool,
 			s.NumTemporaries * sizeof(struct register_info));
 	memset(s.Temporary, 0, s.NumTemporaries * sizeof(struct register_info));

 	rc_recompute_ips(s.C);

 	c->AllocateHwInputs(c, &alloc_input_simple, &s);
 	if (*do_full_regalloc) {
 		do_advanced_regalloc(&s);
 	} else {
 		s.Simple = 1;
 		do_regalloc_inputs_only(&s);
 	}

 	/* Rewrite inputs and if we are doing the simple allocation, rewrite
 	 * temporaries too. */
 	for (struct rc_instruction *inst = s.C->Program.Instructions.Next;
 					inst != &s.C->Program.Instructions;
 					inst = inst->Next) {
 		rc_remap_registers(inst, &remap_register, &s);
 	}
 }
	/*
	* Copyright (C) 2009 Nicolai Haehnle.
	* 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_program_pair.h"

	#include <stdio.h>

	#include "main/glheader.h"
	#include "program/register_allocate.h"
	#include "ralloc.h"

	#include "r300_fragprog_swizzle.h"
	#include "radeon_compiler.h"
	#include "radeon_compiler_util.h"
	#include "radeon_dataflow.h"
	#include "radeon_list.h"
	#include "radeon_variable.h"

	#define VERBOSE 0

	#define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)



	struct register_info {
	struct live_intervals Live[4];

	unsigned int Used:1;
	unsigned int Allocated:1;
	unsigned int File:3;
	unsigned int Index:RC_REGISTER_INDEX_BITS;
	unsigned int Writemask;
	};

	struct regalloc_state {
	struct radeon_compiler * C;

	struct register_info * Input;
	unsigned int NumInputs;

	struct register_info * Temporary;
	unsigned int NumTemporaries;

	unsigned int Simple;
	int LoopEnd;
	};

	enum rc_reg_class {
	RC_REG_CLASS_SINGLE,
	RC_REG_CLASS_DOUBLE,
	RC_REG_CLASS_TRIPLE,
	RC_REG_CLASS_ALPHA,
	RC_REG_CLASS_SINGLE_PLUS_ALPHA,
	RC_REG_CLASS_DOUBLE_PLUS_ALPHA,
	RC_REG_CLASS_TRIPLE_PLUS_ALPHA,
	RC_REG_CLASS_X,
	RC_REG_CLASS_Y,
	RC_REG_CLASS_Z,
	RC_REG_CLASS_XY,
	RC_REG_CLASS_YZ,
	RC_REG_CLASS_XZ,
	RC_REG_CLASS_XW,
	RC_REG_CLASS_YW,
	RC_REG_CLASS_ZW,
	RC_REG_CLASS_XYW,
	RC_REG_CLASS_YZW,
	RC_REG_CLASS_XZW,
	RC_REG_CLASS_COUNT
	};

	struct rc_class {
	enum rc_reg_class Class;

	unsigned int WritemaskCount;

	/** This is 1 if this class is being used by the register allocator
	* and 0 otherwise */
	unsigned int Used;

	/** This is the ID number assigned to this class by ra. */
	unsigned int Id;

	/** List of writemasks that belong to this class */
	unsigned int Writemasks[3];


	};

	static void print_live_intervals(struct live_intervals * src)
	{
	if (!src \|\| !src->Used) {
	DBG("(null)");
	return;
	}

	DBG("(%i,%i)", src->Start, src->End);
	}

	static int overlap_live_intervals(struct live_intervals * a, struct live_intervals * b)
	{
	if (VERBOSE) {
	DBG("overlap_live_intervals: ");
	print_live_intervals(a);
	DBG(" to ");
	print_live_intervals(b);
	DBG("\n");
	}

	if (!a->Used \|\| !b->Used) {
	DBG(" unused interval\n");
	return 0;
	}

	if (a->Start > b->Start) {
	if (a->Start < b->End) {
	DBG(" overlap\n");
	return 1;
	}
	} else if (b->Start > a->Start) {
	if (b->Start < a->End) {
	DBG(" overlap\n");
	return 1;
	}
	} else { /* a->Start == b->Start */
	if (a->Start != a->End && b->Start != b->End) {
	DBG(" overlap\n");
	return 1;
	}
	}

	DBG(" no overlap\n");

	return 0;
	}

	static void scan_read_callback(void * data, struct rc_instruction * inst,
	rc_register_file file, unsigned int index, unsigned int mask)
	{
	struct regalloc_state * s = data;
	struct register_info * reg;
	unsigned int i;

	if (file != RC_FILE_INPUT)
	return;

	s->Input[index].Used = 1;
	reg = &s->Input[index];

	for (i = 0; i < 4; i++) {
	if (!((mask >> i) & 0x1)) {
	continue;
	}
	reg->Live[i].Used = 1;
	reg->Live[i].Start = 0;
	reg->Live[i].End =
	s->LoopEnd > inst->IP ? s->LoopEnd : inst->IP;
	}
	}

	static void remap_register(void * data, struct rc_instruction * inst,
	rc_register_file * file, unsigned int * index)
	{
	struct regalloc_state * s = data;
	const struct register_info * reg;

	if (*file == RC_FILE_TEMPORARY && s->Simple)
	reg = &s->Temporary[*index];
	else if (*file == RC_FILE_INPUT)
	reg = &s->Input[*index];
	else
	return;

	if (reg->Allocated) {
	*index = reg->Index;
	}
	}

	static void alloc_input_simple(void * data, unsigned int input,
	unsigned int hwreg)
	{
	struct regalloc_state * s = data;

	if (input >= s->NumInputs)
	return;

	s->Input[input].Allocated = 1;
	s->Input[input].File = RC_FILE_TEMPORARY;
	s->Input[input].Index = hwreg;
	}

	/* This functions offsets the temporary register indices by the number
	* of input registers, because input registers are actually temporaries and
	* should not occupy the same space.
	*
	* This pass is supposed to be used to maintain correct allocation of inputs
	* if the standard register allocation is disabled. */
	static void do_regalloc_inputs_only(struct regalloc_state * s)
	{
	for (unsigned i = 0; i < s->NumTemporaries; i++) {
	s->Temporary[i].Allocated = 1;
	s->Temporary[i].File = RC_FILE_TEMPORARY;
	s->Temporary[i].Index = i + s->NumInputs;
	}
	}

	static unsigned int is_derivative(rc_opcode op)
	{
	return (op == RC_OPCODE_DDX \|\| op == RC_OPCODE_DDY);
	}

	static int find_class(
	struct rc_class * classes,
	unsigned int writemask,
	unsigned int max_writemask_count)
	{
	unsigned int i;
	for (i = 0; i < RC_REG_CLASS_COUNT; i++) {
	unsigned int j;
	if (classes[i].WritemaskCount > max_writemask_count) {
	continue;
	}
	for (j = 0; j < 3; j++) {
	if (classes[i].Writemasks[j] == writemask) {
	return i;
	}
	}
	}
	return -1;
	}

	struct variable_get_class_cb_data {
	unsigned int * can_change_writemask;
	unsigned int conversion_swizzle;
	};

	static void variable_get_class_read_cb(
	void * userdata,
	struct rc_instruction * inst,
	struct rc_pair_instruction_arg * arg,
	struct rc_pair_instruction_source * src)
	{
	struct variable_get_class_cb_data * d = userdata;
	unsigned int new_swizzle = rc_adjust_channels(arg->Swizzle,
	d->conversion_swizzle);
	if (!r300_swizzle_is_native_basic(new_swizzle)) {
	*d->can_change_writemask = 0;
	}
	}

	static enum rc_reg_class variable_get_class(
	struct rc_variable * variable,
	struct rc_class * classes)
	{
	unsigned int i;
	unsigned int can_change_writemask= 1;
	unsigned int writemask = rc_variable_writemask_sum(variable);
	struct rc_list * readers = rc_variable_readers_union(variable);
	int class_index;

	if (!variable->C->is_r500) {
	struct rc_class c;
	struct rc_variable * var_ptr;
	/* The assumption here is that if an instruction has type
	* RC_INSTRUCTION_NORMAL then it is a TEX instruction.
	* r300 and r400 can't swizzle the result of a TEX lookup. */
	for (var_ptr = variable; var_ptr; var_ptr = var_ptr->Friend) {
	if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) {
	writemask = RC_MASK_XYZW;
	}
	}

	/* Check if it is possible to do swizzle packing for r300/r400
	* without creating non-native swizzles. */
	class_index = find_class(classes, writemask, 3);
	if (class_index < 0) {
	goto error;
	}
	c = classes[class_index];
	if (c.WritemaskCount == 1) {
	goto done;
	}
	for (i = 0; i < c.WritemaskCount; i++) {
	struct rc_variable * var_ptr;
	for (var_ptr = variable; var_ptr;
	var_ptr = var_ptr->Friend) {
	int j;
	unsigned int conversion_swizzle =
	rc_make_conversion_swizzle(
	writemask, c.Writemasks[i]);
	struct variable_get_class_cb_data d;
	d.can_change_writemask = &can_change_writemask;
	d.conversion_swizzle = conversion_swizzle;
	/* If we get this far var_ptr->Inst has to
	* be a pair instruction. If variable or any
	* of its friends are normal instructions,
	* then the writemask will be set to RC_MASK_XYZW
	* and the function will return before it gets
	* here. */
	rc_pair_for_all_reads_arg(var_ptr->Inst,
	variable_get_class_read_cb, &d);

	for (j = 0; j < var_ptr->ReaderCount; j++) {
	unsigned int old_swizzle;
	unsigned int new_swizzle;
	struct rc_reader r = var_ptr->Readers[j];
	if (r.Inst->Type ==
	RC_INSTRUCTION_PAIR ) {
	old_swizzle = r.U.P.Arg->Swizzle;
	} else {
	old_swizzle = r.U.I.Src->Swizzle;
	}
	new_swizzle = rc_adjust_channels(
	old_swizzle, conversion_swizzle);
	if (!r300_swizzle_is_native_basic(
	new_swizzle)) {
	can_change_writemask = 0;
	break;
	}
	}
	if (!can_change_writemask) {
	break;
	}
	}
	if (!can_change_writemask) {
	break;
	}
	}
	}

	if (variable->Inst->Type == RC_INSTRUCTION_PAIR) {
	/* DDX/DDY seem to always fail when their writemasks are
	* changed.*/
	if (is_derivative(variable->Inst->U.P.RGB.Opcode)
	\|\| is_derivative(variable->Inst->U.P.Alpha.Opcode)) {
	can_change_writemask = 0;
	}
	}
	for ( ; readers; readers = readers->Next) {
	struct rc_reader * r = readers->Item;
	if (r->Inst->Type == RC_INSTRUCTION_PAIR) {
	if (r->U.P.Arg->Source == RC_PAIR_PRESUB_SRC) {
	can_change_writemask = 0;
	break;
	}
	/* DDX/DDY also fail when their swizzles are changed. */
	if (is_derivative(r->Inst->U.P.RGB.Opcode)
	\|\| is_derivative(r->Inst->U.P.Alpha.Opcode)) {
	can_change_writemask = 0;
	break;
	}
	}
	}

	class_index = find_class(classes, writemask,
	can_change_writemask ? 3 : 1);
	done:
	if (class_index > -1) {
	return classes[class_index].Class;
	} else {
	error:
	rc_error(variable->C,
	"Could not find class for index=%u mask=%u\n",
	variable->Dst.Index, writemask);
	return 0;
	}
	}

	static unsigned int overlap_live_intervals_array(
	struct live_intervals * a,
	struct live_intervals * b)
	{
	unsigned int a_chan, b_chan;
	for (a_chan = 0; a_chan < 4; a_chan++) {
	for (b_chan = 0; b_chan < 4; b_chan++) {
	if (overlap_live_intervals(&a[a_chan], &b[b_chan])) {
	return 1;
	}
	}
	}
	return 0;
	}

	static unsigned int reg_get_index(int reg)
	{
	return reg / RC_MASK_XYZW;
	}

	static unsigned int reg_get_writemask(int reg)
	{
	return (reg % RC_MASK_XYZW) + 1;
	}

	static int get_reg_id(unsigned int index, unsigned int writemask)
	{
	assert(writemask);
	if (writemask == 0) {
	return 0;
	}
	return (index * RC_MASK_XYZW) + (writemask - 1);
	}

	#if VERBOSE
	static void print_reg(int reg)
	{
	unsigned int index = reg_get_index(reg);
	unsigned int mask = reg_get_writemask(reg);
	fprintf(stderr, "Temp[%u].%c%c%c%c", index,
	mask & RC_MASK_X ? 'x' : '_',
	mask & RC_MASK_Y ? 'y' : '_',
	mask & RC_MASK_Z ? 'z' : '_',
	mask & RC_MASK_W ? 'w' : '_');
	}
	#endif

	static void add_register_conflicts(
	struct ra_regs * regs,
	unsigned int max_temp_regs)
	{
	unsigned int index, a_mask, b_mask;
	for (index = 0; index < max_temp_regs; index++) {
	for(a_mask = 1; a_mask <= RC_MASK_XYZW; a_mask++) {
	for (b_mask = a_mask + 1; b_mask <= RC_MASK_XYZW;
	b_mask++) {
	if (a_mask & b_mask) {
	ra_add_reg_conflict(regs,
	get_reg_id(index, a_mask),
	get_reg_id(index, b_mask));
	}
	}
	}
	}
	}

	static void do_advanced_regalloc(struct regalloc_state * s)
	{
	struct rc_class rc_class_list [] = {
	{RC_REG_CLASS_SINGLE, 3, 0, 0,
	{RC_MASK_X,
	RC_MASK_Y,
	RC_MASK_Z}},
	{RC_REG_CLASS_DOUBLE, 3, 0, 0,
	{RC_MASK_X \| RC_MASK_Y,
	RC_MASK_X \| RC_MASK_Z,
	RC_MASK_Y \| RC_MASK_Z}},
	{RC_REG_CLASS_TRIPLE, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_Y \| RC_MASK_Z,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_ALPHA, 1, 0, 0,
	{RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_SINGLE_PLUS_ALPHA, 3, 0, 0,
	{RC_MASK_X \| RC_MASK_W,
	RC_MASK_Y \| RC_MASK_W,
	RC_MASK_Z \| RC_MASK_W}},
	{RC_REG_CLASS_DOUBLE_PLUS_ALPHA, 3, 0, 0,
	{RC_MASK_X \| RC_MASK_Y \| RC_MASK_W,
	RC_MASK_X \| RC_MASK_Z \| RC_MASK_W,
	RC_MASK_Y \| RC_MASK_Z \| RC_MASK_W}},
	{RC_REG_CLASS_TRIPLE_PLUS_ALPHA, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_Y \| RC_MASK_Z \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_X, 1, 0, 0,
	{RC_MASK_X,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_Y, 1, 0, 0,
	{RC_MASK_Y,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_Z, 1, 0, 0,
	{RC_MASK_Z,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_XY, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_Y,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_YZ, 1, 0, 0,
	{RC_MASK_Y \| RC_MASK_Z,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_XZ, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_Z,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_XW, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_YW, 1, 0, 0,
	{RC_MASK_Y \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_ZW, 1, 0, 0,
	{RC_MASK_Z \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_XYW, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_Y \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_YZW, 1, 0, 0,
	{RC_MASK_Y \| RC_MASK_Z \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}},
	{RC_REG_CLASS_XZW, 1, 0, 0,
	{RC_MASK_X \| RC_MASK_Z \| RC_MASK_W,
	RC_MASK_NONE,
	RC_MASK_NONE}}
	};

	unsigned int i, j, index, input_node, node_count, node_index;
	unsigned int * node_classes;
	unsigned int * input_classes;
	struct rc_instruction * inst;
	struct rc_list * var_ptr;
	struct rc_list * variables;
	struct ra_regs * regs;
	struct ra_graph * graph;

	/* Allocate the main ra data structure */
	regs = ra_alloc_reg_set(NULL, s->C->max_temp_regs * RC_MASK_XYZW);

	/* Get list of program variables */
	variables = rc_get_variables(s->C);
	node_count = rc_list_count(variables);
	node_classes = memory_pool_malloc(&s->C->Pool,
	node_count * sizeof(unsigned int));
	input_classes = memory_pool_malloc(&s->C->Pool,
	s->NumInputs * sizeof(unsigned int));

	for (var_ptr = variables, node_index = 0; var_ptr;
	var_ptr = var_ptr->Next, node_index++) {
	unsigned int class_index;
	/* Compute the live intervals */
	rc_variable_compute_live_intervals(var_ptr->Item);

	class_index = variable_get_class(var_ptr->Item, rc_class_list);

	/* If we haven't used this register class yet, mark it
	* as used and allocate space for it. */
	if (!rc_class_list[class_index].Used) {
	rc_class_list[class_index].Used = 1;
	rc_class_list[class_index].Id = ra_alloc_reg_class(regs);
	}

	node_classes[node_index] = rc_class_list[class_index].Id;
	}


	/* Assign registers to the classes */
	for (i = 0; i < RC_REG_CLASS_COUNT; i++) {
	struct rc_class class = rc_class_list[i];
	if (!class.Used) {
	continue;
	}

	for (index = 0; index < s->C->max_temp_regs; index++) {
	for (j = 0; j < class.WritemaskCount; j++) {
	int reg_id = get_reg_id(index,
	class.Writemasks[j]);
	ra_class_add_reg(regs, class.Id, reg_id);
	}
	}
	}

	/* Add register conflicts */
	add_register_conflicts(regs, s->C->max_temp_regs);

	/* Calculate live intervals for input registers */
	for (inst = s->C->Program.Instructions.Next;
	inst != &s->C->Program.Instructions;
	inst = inst->Next) {
	rc_opcode op = rc_get_flow_control_inst(inst);
	if (op == RC_OPCODE_BGNLOOP) {
	struct rc_instruction * endloop =
	rc_match_bgnloop(inst);
	if (endloop->IP > s->LoopEnd) {
	s->LoopEnd = endloop->IP;
	}
	}
	rc_for_all_reads_mask(inst, scan_read_callback, s);
	}

	/* Create classes for input registers */
	for (i = 0; i < s->NumInputs; i++) {
	unsigned int chan, class_id, writemask = 0;
	for (chan = 0; chan < 4; chan++) {
	if (s->Input[i].Live[chan].Used) {
	writemask \|= (1 << chan);
	}
	}
	s->Input[i].Writemask = writemask;
	if (!writemask) {
	continue;
	}

	class_id = ra_alloc_reg_class(regs);
	input_classes[i] = class_id;
	ra_class_add_reg(regs, class_id,
	get_reg_id(s->Input[i].Index, writemask));
	}

	ra_set_finalize(regs);

	graph = ra_alloc_interference_graph(regs, node_count + s->NumInputs);

	/* Build the interference graph */
	for (var_ptr = variables, node_index = 0; var_ptr;
	var_ptr = var_ptr->Next,node_index++) {
	struct rc_list * a, * b;
	unsigned int b_index;

	ra_set_node_class(graph, node_index, node_classes[node_index]);

	for (a = var_ptr, b = var_ptr->Next, b_index = node_index + 1;
	b; b = b->Next, b_index++) {
	struct rc_variable * var_a = a->Item;
	while (var_a) {
	struct rc_variable * var_b = b->Item;
	while (var_b) {
	if (overlap_live_intervals_array(var_a->Live, var_b->Live)) {
	ra_add_node_interference(graph,
	node_index, b_index);
	}
	var_b = var_b->Friend;
	}
	var_a = var_a->Friend;
	}
	}
	}

	/* Add input registers to the interference graph */
	for (i = 0, input_node = 0; i< s->NumInputs; i++) {
	if (!s->Input[i].Writemask) {
	continue;
	}
	ra_set_node_class(graph, node_count + input_node,
	input_classes[i]);
	for (var_ptr = variables, node_index = 0;
	var_ptr; var_ptr = var_ptr->Next, node_index++) {
	struct rc_variable * var = var_ptr->Item;
	if (overlap_live_intervals_array(s->Input[i].Live,
	var->Live)) {
	ra_add_node_interference(graph, node_index,
	node_count + input_node);
	}
	}
	/* Manually allocate a register for this input */
	ra_set_node_reg(graph, node_count + input_node, get_reg_id(
	s->Input[i].Index, s->Input[i].Writemask));
	input_node++;
	}

	if (!ra_allocate_no_spills(graph)) {
	rc_error(s->C, "Ran out of hardware temporaries\n");
	return;
	}

	/* Rewrite the registers */
	for (var_ptr = variables, node_index = 0; var_ptr;
	var_ptr = var_ptr->Next, node_index++) {
	int reg = ra_get_node_reg(graph, node_index);
	unsigned int writemask = reg_get_writemask(reg);
	unsigned int index = reg_get_index(reg);
	struct rc_variable * var = var_ptr->Item;

	if (!s->C->is_r500 && var->Inst->Type == RC_INSTRUCTION_NORMAL) {
	writemask = rc_variable_writemask_sum(var);
	}

	if (var->Dst.File == RC_FILE_INPUT) {
	continue;
	}
	rc_variable_change_dst(var, index, writemask);
	}

	ralloc_free(graph);
	ralloc_free(regs);
	}

	/**
	* @param user This parameter should be a pointer to an integer value. If this
	* integer value is zero, then a simple register allocator will be used that
	* only allocates space for input registers (\sa do_regalloc_inputs_only). If
	* user is non-zero, then the regular register allocator will be used
	* (\sa do_regalloc).
	*/
	void rc_pair_regalloc(struct radeon_compiler cc, void user)
	{
	struct r300_fragment_program_compiler *c =
	(struct r300_fragment_program_compiler*)cc;
	struct regalloc_state s;
	int * do_full_regalloc = (int*)user;

	memset(&s, 0, sizeof(s));
	s.C = cc;
	s.NumInputs = rc_get_max_index(cc, RC_FILE_INPUT) + 1;
	s.Input = memory_pool_malloc(&cc->Pool,
	s.NumInputs * sizeof(struct register_info));
	memset(s.Input, 0, s.NumInputs * sizeof(struct register_info));

	s.NumTemporaries = rc_get_max_index(cc, RC_FILE_TEMPORARY) + 1;
	s.Temporary = memory_pool_malloc(&cc->Pool,
	s.NumTemporaries * sizeof(struct register_info));
	memset(s.Temporary, 0, s.NumTemporaries * sizeof(struct register_info));

	rc_recompute_ips(s.C);

	c->AllocateHwInputs(c, &alloc_input_simple, &s);
	if (*do_full_regalloc) {
	do_advanced_regalloc(&s);
	} else {
	s.Simple = 1;
	do_regalloc_inputs_only(&s);
	}

	/* Rewrite inputs and if we are doing the simple allocation, rewrite
	* temporaries too. */
	for (struct rc_instruction *inst = s.C->Program.Instructions.Next;
	inst != &s.C->Program.Instructions;
	inst = inst->Next) {
	rc_remap_registers(inst, &remap_register, &s);
	}
	}