src/gallium/drivers/r300/compiler/radeon_emulate_loops.c

/*
 * Copyright 2010 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.
 *
 */

/**
 * \file
 */

#include "radeon_emulate_loops.h"

#include "radeon_compiler.h"
#include "radeon_compiler_util.h"
#include "radeon_dataflow.h"

#define VERBOSE 0

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

struct const_value {
	struct radeon_compiler * C;
	struct rc_src_register * Src;
	float Value;
	int HasValue;
};

struct count_inst {
	struct radeon_compiler * C;
	int Index;
	rc_swizzle Swz;
	float Amount;
	int Unknown;
	unsigned BranchDepth;
};

static unsigned int loop_max_possible_iterations(struct radeon_compiler *c,
			struct loop_info * loop)
{
	unsigned int total_i = rc_recompute_ips(c);
	unsigned int loop_i = (loop->EndLoop->IP - loop->BeginLoop->IP) - 1;
	/* +1 because the program already has one iteration of the loop. */
	return 1 + ((c->max_alu_insts - total_i) / loop_i);
}

static void unroll_loop(struct radeon_compiler * c, struct loop_info * loop,
						unsigned int iterations)
{
	unsigned int i;
	struct rc_instruction * ptr;
	struct rc_instruction * first = loop->BeginLoop->Next;
	struct rc_instruction * last = loop->EndLoop->Prev;
	struct rc_instruction * append_to = last;
	rc_remove_instruction(loop->BeginLoop);
	rc_remove_instruction(loop->EndLoop);
	for( i = 1; i < iterations; i++){
		for(ptr = first; ptr != last->Next; ptr = ptr->Next){
			struct rc_instruction *new = rc_alloc_instruction(c);
			memcpy(new, ptr, sizeof(struct rc_instruction));
			rc_insert_instruction(append_to, new);
			append_to = new;
		}
	}
}


static void update_const_value(void * data, struct rc_instruction * inst,
		rc_register_file file, unsigned int index, unsigned int mask)
{
	struct const_value * value = data;
	if(value->Src->File != file ||
	   value->Src->Index != index ||
	   !(1 << GET_SWZ(value->Src->Swizzle, 0) & mask)){
		return;
	}
	switch(inst->U.I.Opcode){
	case RC_OPCODE_MOV:
		if(!rc_src_reg_is_immediate(value->C, inst->U.I.SrcReg[0].File,
						inst->U.I.SrcReg[0].Index)){
			return;
		}
		value->HasValue = 1;
		value->Value =
			rc_get_constant_value(value->C,
					      inst->U.I.SrcReg[0].Index,
					      inst->U.I.SrcReg[0].Swizzle,
					      inst->U.I.SrcReg[0].Negate, 0);
		break;
	}
}

static void get_incr_amount(void * data, struct rc_instruction * inst,
		rc_register_file file, unsigned int index, unsigned int mask)
{
	struct count_inst * count_inst = data;
	int amnt_src_index;
	const struct rc_opcode_info * opcode;
	float amount;

	if(file != RC_FILE_TEMPORARY ||
	   count_inst->Index != index ||
	   (1 << GET_SWZ(count_inst->Swz,0) != mask)){
		return;
	}

	/* XXX: Give up if the counter is modified within an IF block.  We
	 * could handle this case with better analysis. */
	if (count_inst->BranchDepth > 0) {
		count_inst->Unknown = 1;
		return;
	}

	/* Find the index of the counter register. */
	opcode = rc_get_opcode_info(inst->U.I.Opcode);
	if(opcode->NumSrcRegs != 2){
		count_inst->Unknown = 1;
		return;
	}
	if(inst->U.I.SrcReg[0].File == RC_FILE_TEMPORARY &&
	   inst->U.I.SrcReg[0].Index == count_inst->Index &&
	   inst->U.I.SrcReg[0].Swizzle == count_inst->Swz){
		amnt_src_index = 1;
	} else if( inst->U.I.SrcReg[1].File == RC_FILE_TEMPORARY &&
		   inst->U.I.SrcReg[1].Index == count_inst->Index &&
		   inst->U.I.SrcReg[1].Swizzle == count_inst->Swz){
		amnt_src_index = 0;
	}
	else{
		count_inst->Unknown = 1;
		return;
	}
	if(rc_src_reg_is_immediate(count_inst->C,
				inst->U.I.SrcReg[amnt_src_index].File,
				inst->U.I.SrcReg[amnt_src_index].Index)){
		amount = rc_get_constant_value(count_inst->C,
				inst->U.I.SrcReg[amnt_src_index].Index,
				inst->U.I.SrcReg[amnt_src_index].Swizzle,
				inst->U.I.SrcReg[amnt_src_index].Negate, 0);
	}
	else{
		count_inst->Unknown = 1 ;
		return;
	}
	switch(inst->U.I.Opcode){
	case RC_OPCODE_ADD:
		count_inst->Amount += amount;
		break;
	case RC_OPCODE_SUB:
		if(amnt_src_index == 0){
			count_inst->Unknown = 0;
			return;
		}
		count_inst->Amount -= amount;
		break;
	default:
		count_inst->Unknown = 1;
		return;
	}
}

/**
 * If c->max_alu_inst is -1, then all eligible loops will be unrolled regardless
 * of how many iterations they have.
 */
static int try_unroll_loop(struct radeon_compiler * c, struct loop_info * loop)
{
	int end_loops;
	int iterations;
	struct count_inst count_inst;
	float limit_value;
	struct rc_src_register * counter;
	struct rc_src_register * limit;
	struct const_value counter_value;
	struct rc_instruction * inst;

	/* Find the counter and the upper limit */

	if(rc_src_reg_is_immediate(c, loop->Cond->U.I.SrcReg[0].File,
					loop->Cond->U.I.SrcReg[0].Index)){
		limit = &loop->Cond->U.I.SrcReg[0];
		counter = &loop->Cond->U.I.SrcReg[1];
	}
	else if(rc_src_reg_is_immediate(c, loop->Cond->U.I.SrcReg[1].File,
					loop->Cond->U.I.SrcReg[1].Index)){
		limit = &loop->Cond->U.I.SrcReg[1];
		counter = &loop->Cond->U.I.SrcReg[0];
	}
	else{
		DBG("No constant limit.\n");
		return 0;
	}

	/* Find the initial value of the counter */
	counter_value.Src = counter;
	counter_value.Value = 0.0f;
	counter_value.HasValue = 0;
	counter_value.C = c;
	for(inst = c->Program.Instructions.Next; inst != loop->BeginLoop;
							inst = inst->Next){
		rc_for_all_writes_mask(inst, update_const_value, &counter_value);
	}
	if(!counter_value.HasValue){
		DBG("Initial counter value cannot be determined.\n");
		return 0;
	}
	DBG("Initial counter value is %f\n", counter_value.Value);
	/* Determine how the counter is modified each loop */
	count_inst.C = c;
	count_inst.Index = counter->Index;
	count_inst.Swz = counter->Swizzle;
	count_inst.Amount = 0.0f;
	count_inst.Unknown = 0;
	count_inst.BranchDepth = 0;
	end_loops = 1;
	for(inst = loop->BeginLoop->Next; end_loops > 0; inst = inst->Next){
		switch(inst->U.I.Opcode){
		/* XXX In the future we might want to try to unroll nested
		 * loops here.*/
		case RC_OPCODE_BGNLOOP:
			end_loops++;
			break;
		case RC_OPCODE_ENDLOOP:
			loop->EndLoop = inst;
			end_loops--;
			break;
		case RC_OPCODE_BRK:
			/* Don't unroll loops if it has a BRK instruction
			 * other one used when testing the main conditional
			 * of the loop. */

			/* Make sure we haven't entered a nested loops. */
			if(inst != loop->Brk && end_loops == 1) {
				return 0;
			}
			break;
		case RC_OPCODE_IF:
			count_inst.BranchDepth++;
			break;
		case RC_OPCODE_ENDIF:
			count_inst.BranchDepth--;
			break;
		default:
			rc_for_all_writes_mask(inst, get_incr_amount, &count_inst);
			if(count_inst.Unknown){
				return 0;
			}
			break;
		}
	}
	/* Infinite loop */
	if(count_inst.Amount == 0.0f){
		return 0;
	}
	DBG("Counter is increased by %f each iteration.\n", count_inst.Amount);
	/* Calculate the number of iterations of this loop.  Keeping this
	 * simple, since we only support increment and decrement loops.
	 */
	limit_value = rc_get_constant_value(c, limit->Index, limit->Swizzle,
							limit->Negate, 0);
	DBG("Limit is %f.\n", limit_value);
	/* The iteration calculations are opposite of what you would expect.
	 * In a normal loop, if the condition is met, then loop continues, but
	 * with our loops, if the condition is met, the is exited. */
	switch(loop->Cond->U.I.Opcode){
	case RC_OPCODE_SGE:
	case RC_OPCODE_SLE:
		iterations = (int) ceilf((limit_value - counter_value.Value) /
							count_inst.Amount);
		break;

	case RC_OPCODE_SGT:
	case RC_OPCODE_SLT:
		iterations = (int) floorf((limit_value - counter_value.Value) /
							count_inst.Amount) + 1;
		break;
	default:
		return 0;
	}

	if (c->max_alu_insts > 0
		&& iterations > loop_max_possible_iterations(c, loop)) {
		return 0;
	}

	DBG("Loop will have %d iterations.\n", iterations);

	/* Prepare loop for unrolling */
	rc_remove_instruction(loop->Cond);
	rc_remove_instruction(loop->If);
	rc_remove_instruction(loop->Brk);
	rc_remove_instruction(loop->EndIf);

	unroll_loop(c, loop, iterations);
	loop->EndLoop = NULL;
	return 1;
}

/**
 * @param c
 * @param loop
 * @param inst A pointer to a BGNLOOP instruction.
 * @return 1 if all of the members of loop where set.
 * @return 0 if there was an error and some members of loop are still NULL.
 */
static int build_loop_info(struct radeon_compiler * c, struct loop_info * loop,
						struct rc_instruction * inst)
{
	struct rc_instruction * ptr;

	if(inst->U.I.Opcode != RC_OPCODE_BGNLOOP){
		rc_error(c, "%s: expected BGNLOOP", __FUNCTION__);
		return 0;
	}

	memset(loop, 0, sizeof(struct loop_info));

	loop->BeginLoop = inst;

	for(ptr = loop->BeginLoop->Next; !loop->EndLoop; ptr = ptr->Next) {

		if (ptr == &c->Program.Instructions) {
			rc_error(c, "%s: BGNLOOP without an ENDLOOOP.\n",
								__FUNCTION__);
			return 0;
		}

		switch(ptr->U.I.Opcode){
		case RC_OPCODE_BGNLOOP:
		{
			/* Nested loop, skip ahead to the end. */
			unsigned int loop_depth = 1;
			for(ptr = ptr->Next; ptr != &c->Program.Instructions;
							ptr = ptr->Next){
				if (ptr->U.I.Opcode == RC_OPCODE_BGNLOOP) {
					loop_depth++;
				} else if (ptr->U.I.Opcode == RC_OPCODE_ENDLOOP) {
					if (!--loop_depth) {
						break;
					}
				}
			}
			if (ptr == &c->Program.Instructions) {
				rc_error(c, "%s: BGNLOOP without an ENDLOOOP\n",
								__FUNCTION__);
					return 0;
			}
			break;
		}
		case RC_OPCODE_BRK:
			if(ptr->Next->U.I.Opcode != RC_OPCODE_ENDIF
					|| ptr->Prev->U.I.Opcode != RC_OPCODE_IF
					|| loop->Brk){
				continue;
			}
			loop->Brk = ptr;
			loop->If = ptr->Prev;
			loop->EndIf = ptr->Next;
			switch(loop->If->Prev->U.I.Opcode){
			case RC_OPCODE_SLT:
			case RC_OPCODE_SGE:
			case RC_OPCODE_SGT:
			case RC_OPCODE_SLE:
			case RC_OPCODE_SEQ:
			case RC_OPCODE_SNE:
				break;
			default:
				return 0;
			}
			loop->Cond = loop->If->Prev;
			break;

		case RC_OPCODE_ENDLOOP:
			loop->EndLoop = ptr;
			break;
		}
	}

	if (loop->BeginLoop && loop->Brk && loop->If && loop->EndIf
					&& loop->Cond && loop->EndLoop) {
		return 1;
	}
	return 0;
}

/**
 * This function prepares a loop to be unrolled by converting it into an if
 * statement.  Here is an outline of the conversion process:
 * BGNLOOP;                         	-> BGNLOOP;
 * <Additional conditional code>	-> <Additional conditional code>
 * SGE/SLT temp[0], temp[1], temp[2];	-> SLT/SGE temp[0], temp[1], temp[2];
 * IF temp[0];                      	-> IF temp[0];
 * BRK;                             	->
 * ENDIF;                           	-> <Loop Body>
 * <Loop Body>                      	-> ENDIF;
 * ENDLOOP;                         	-> ENDLOOP
 *
 * @param inst A pointer to a BGNLOOP instruction.
 * @return 1 for success, 0 for failure
 */
static int transform_loop(struct emulate_loop_state * s,
						struct rc_instruction * inst)
{
	struct loop_info * loop;

	memory_pool_array_reserve(&s->C->Pool, struct loop_info,
			s->Loops, s->LoopCount, s->LoopReserved, 1);

	loop = &s->Loops[s->LoopCount++];

	if (!build_loop_info(s->C, loop, inst)) {
		rc_error(s->C, "Failed to build loop info\n");
		return 0;
	}

	if(try_unroll_loop(s->C, loop)){
		return 1;
	}

	/* Reverse the conditional instruction */
	switch(loop->Cond->U.I.Opcode){
	case RC_OPCODE_SGE:
		loop->Cond->U.I.Opcode = RC_OPCODE_SLT;
		break;
	case RC_OPCODE_SLT:
		loop->Cond->U.I.Opcode = RC_OPCODE_SGE;
		break;
	case RC_OPCODE_SLE:
		loop->Cond->U.I.Opcode = RC_OPCODE_SGT;
		break;
	case RC_OPCODE_SGT:
		loop->Cond->U.I.Opcode = RC_OPCODE_SLE;
		break;
	case RC_OPCODE_SEQ:
		loop->Cond->U.I.Opcode = RC_OPCODE_SNE;
		break;
	case RC_OPCODE_SNE:
		loop->Cond->U.I.Opcode = RC_OPCODE_SEQ;
		break;
	default:
		rc_error(s->C, "loop->Cond is not a conditional.\n");
		return 0;
	}

	/* Prepare the loop to be emulated */
	rc_remove_instruction(loop->Brk);
	rc_remove_instruction(loop->EndIf);
	rc_insert_instruction(loop->EndLoop->Prev, loop->EndIf);
	return 1;
}

void rc_transform_loops(struct radeon_compiler *c, void *user)
{
	struct emulate_loop_state * s = &c->loop_state;
	struct rc_instruction * ptr;

	memset(s, 0, sizeof(struct emulate_loop_state));
	s->C = c;
	for(ptr = s->C->Program.Instructions.Next;
			ptr != &s->C->Program.Instructions; ptr = ptr->Next) {
		if(ptr->Type == RC_INSTRUCTION_NORMAL &&
					ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
			if (!transform_loop(s, ptr))
				return;
		}
	}
}

void rc_unroll_loops(struct radeon_compiler *c, void *user)
{
	struct rc_instruction * inst;
	struct loop_info loop;

	for(inst = c->Program.Instructions.Next;
			inst != &c->Program.Instructions; inst = inst->Next) {

		if (inst->U.I.Opcode == RC_OPCODE_BGNLOOP) {
			if (build_loop_info(c, &loop, inst)) {
				try_unroll_loop(c, &loop);
			}
		}
	}
}

void rc_emulate_loops(struct radeon_compiler *c, void *user)
{
	struct emulate_loop_state * s = &c->loop_state;
	int i;
	/* Iterate backwards of the list of loops so that loops that nested
	 * loops are unrolled first.
	 */
	for( i = s->LoopCount - 1; i >= 0; i-- ){
		unsigned int iterations;

		if(!s->Loops[i].EndLoop){
			continue;
		}
		iterations = loop_max_possible_iterations(s->C, &s->Loops[i]);
		unroll_loop(s->C, &s->Loops[i], iterations);
	}
}