Home | History | Annotate | Download | only in compiler 
      1 /*
      2  * Copyright 2010 Tom Stellard <tstellar (at) 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 /**
     29  * \file
     30  */
     31 
     32 #include <stdio.h>
     33 #include "c99_math.h"
     34 #include "radeon_emulate_loops.h"
     35 #include "radeon_compiler.h"
     36 #include "radeon_compiler_util.h"
     37 #include "radeon_dataflow.h"
     38 
     39 #define VERBOSE 0
     40 
     41 #define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)
     42 
     43 struct const_value {
     44 	struct radeon_compiler * C;
     45 	struct rc_src_register * Src;
     46 	float Value;
     47 	int HasValue;
     48 };
     49 
     50 struct count_inst {
     51 	struct radeon_compiler * C;
     52 	int Index;
     53 	rc_swizzle Swz;
     54 	float Amount;
     55 	int Unknown;
     56 	unsigned BranchDepth;
     57 };
     58 
     59 static unsigned int loop_max_possible_iterations(struct radeon_compiler *c,
     60 			struct loop_info * loop)
     61 {
     62 	unsigned int total_i = rc_recompute_ips(c);
     63 	unsigned int loop_i = (loop->EndLoop->IP - loop->BeginLoop->IP) - 1;
     64 	/* +1 because the program already has one iteration of the loop. */
     65 	return 1 + ((c->max_alu_insts - total_i) / loop_i);
     66 }
     67 
     68 static void unroll_loop(struct radeon_compiler * c, struct loop_info * loop,
     69 						unsigned int iterations)
     70 {
     71 	unsigned int i;
     72 	struct rc_instruction * ptr;
     73 	struct rc_instruction * first = loop->BeginLoop->Next;
     74 	struct rc_instruction * last = loop->EndLoop->Prev;
     75 	struct rc_instruction * append_to = last;
     76 	rc_remove_instruction(loop->BeginLoop);
     77 	rc_remove_instruction(loop->EndLoop);
     78 	for( i = 1; i < iterations; i++){
     79 		for(ptr = first; ptr != last->Next; ptr = ptr->Next){
     80 			struct rc_instruction *new = rc_alloc_instruction(c);
     81 			memcpy(new, ptr, sizeof(struct rc_instruction));
     82 			rc_insert_instruction(append_to, new);
     83 			append_to = new;
     84 		}
     85 	}
     86 }
     87 
     88 
     89 static void update_const_value(void * data, struct rc_instruction * inst,
     90 		rc_register_file file, unsigned int index, unsigned int mask)
     91 {
     92 	struct const_value * value = data;
     93 	if(value->Src->File != file ||
     94 	   value->Src->Index != index ||
     95 	   !(1 << GET_SWZ(value->Src->Swizzle, 0) & mask)){
     96 		return;
     97 	}
     98 	switch(inst->U.I.Opcode){
     99 	case RC_OPCODE_MOV:
    100 		if(!rc_src_reg_is_immediate(value->C, inst->U.I.SrcReg[0].File,
    101 						inst->U.I.SrcReg[0].Index)){
    102 			return;
    103 		}
    104 		value->HasValue = 1;
    105 		value->Value =
    106 			rc_get_constant_value(value->C,
    107 					      inst->U.I.SrcReg[0].Index,
    108 					      inst->U.I.SrcReg[0].Swizzle,
    109 					      inst->U.I.SrcReg[0].Negate, 0);
    110 		break;
    111 	}
    112 }
    113 
    114 static void get_incr_amount(void * data, struct rc_instruction * inst,
    115 		rc_register_file file, unsigned int index, unsigned int mask)
    116 {
    117 	struct count_inst * count_inst = data;
    118 	int amnt_src_index;
    119 	const struct rc_opcode_info * opcode;
    120 	float amount;
    121 
    122 	if(file != RC_FILE_TEMPORARY ||
    123 	   count_inst->Index != index ||
    124 	   (1 << GET_SWZ(count_inst->Swz,0) != mask)){
    125 		return;
    126 	}
    127 
    128 	/* XXX: Give up if the counter is modified within an IF block.  We
    129 	 * could handle this case with better analysis. */
    130 	if (count_inst->BranchDepth > 0) {
    131 		count_inst->Unknown = 1;
    132 		return;
    133 	}
    134 
    135 	/* Find the index of the counter register. */
    136 	opcode = rc_get_opcode_info(inst->U.I.Opcode);
    137 	if(opcode->NumSrcRegs != 2){
    138 		count_inst->Unknown = 1;
    139 		return;
    140 	}
    141 	if(inst->U.I.SrcReg[0].File == RC_FILE_TEMPORARY &&
    142 	   inst->U.I.SrcReg[0].Index == count_inst->Index &&
    143 	   inst->U.I.SrcReg[0].Swizzle == count_inst->Swz){
    144 		amnt_src_index = 1;
    145 	} else if( inst->U.I.SrcReg[1].File == RC_FILE_TEMPORARY &&
    146 		   inst->U.I.SrcReg[1].Index == count_inst->Index &&
    147 		   inst->U.I.SrcReg[1].Swizzle == count_inst->Swz){
    148 		amnt_src_index = 0;
    149 	}
    150 	else{
    151 		count_inst->Unknown = 1;
    152 		return;
    153 	}
    154 	if(rc_src_reg_is_immediate(count_inst->C,
    155 				inst->U.I.SrcReg[amnt_src_index].File,
    156 				inst->U.I.SrcReg[amnt_src_index].Index)){
    157 		amount = rc_get_constant_value(count_inst->C,
    158 				inst->U.I.SrcReg[amnt_src_index].Index,
    159 				inst->U.I.SrcReg[amnt_src_index].Swizzle,
    160 				inst->U.I.SrcReg[amnt_src_index].Negate, 0);
    161 	}
    162 	else{
    163 		count_inst->Unknown = 1 ;
    164 		return;
    165 	}
    166 	switch(inst->U.I.Opcode){
    167 	case RC_OPCODE_ADD:
    168 		count_inst->Amount += amount;
    169 		break;
    170 	case RC_OPCODE_SUB:
    171 		if(amnt_src_index == 0){
    172 			count_inst->Unknown = 0;
    173 			return;
    174 		}
    175 		count_inst->Amount -= amount;
    176 		break;
    177 	default:
    178 		count_inst->Unknown = 1;
    179 		return;
    180 	}
    181 }
    182 
    183 /**
    184  * If c->max_alu_inst is -1, then all eligible loops will be unrolled regardless
    185  * of how many iterations they have.
    186  */
    187 static int try_unroll_loop(struct radeon_compiler * c, struct loop_info * loop)
    188 {
    189 	int end_loops;
    190 	int iterations;
    191 	struct count_inst count_inst;
    192 	float limit_value;
    193 	struct rc_src_register * counter;
    194 	struct rc_src_register * limit;
    195 	struct const_value counter_value;
    196 	struct rc_instruction * inst;
    197 
    198 	/* Find the counter and the upper limit */
    199 
    200 	if(rc_src_reg_is_immediate(c, loop->Cond->U.I.SrcReg[0].File,
    201 					loop->Cond->U.I.SrcReg[0].Index)){
    202 		limit = &loop->Cond->U.I.SrcReg[0];
    203 		counter = &loop->Cond->U.I.SrcReg[1];
    204 	}
    205 	else if(rc_src_reg_is_immediate(c, loop->Cond->U.I.SrcReg[1].File,
    206 					loop->Cond->U.I.SrcReg[1].Index)){
    207 		limit = &loop->Cond->U.I.SrcReg[1];
    208 		counter = &loop->Cond->U.I.SrcReg[0];
    209 	}
    210 	else{
    211 		DBG("No constant limit.\n");
    212 		return 0;
    213 	}
    214 
    215 	/* Find the initial value of the counter */
    216 	counter_value.Src = counter;
    217 	counter_value.Value = 0.0f;
    218 	counter_value.HasValue = 0;
    219 	counter_value.C = c;
    220 	for(inst = c->Program.Instructions.Next; inst != loop->BeginLoop;
    221 							inst = inst->Next){
    222 		rc_for_all_writes_mask(inst, update_const_value, &counter_value);
    223 	}
    224 	if(!counter_value.HasValue){
    225 		DBG("Initial counter value cannot be determined.\n");
    226 		return 0;
    227 	}
    228 	DBG("Initial counter value is %f\n", counter_value.Value);
    229 	/* Determine how the counter is modified each loop */
    230 	count_inst.C = c;
    231 	count_inst.Index = counter->Index;
    232 	count_inst.Swz = counter->Swizzle;
    233 	count_inst.Amount = 0.0f;
    234 	count_inst.Unknown = 0;
    235 	count_inst.BranchDepth = 0;
    236 	end_loops = 1;
    237 	for(inst = loop->BeginLoop->Next; end_loops > 0; inst = inst->Next){
    238 		switch(inst->U.I.Opcode){
    239 		/* XXX In the future we might want to try to unroll nested
    240 		 * loops here.*/
    241 		case RC_OPCODE_BGNLOOP:
    242 			end_loops++;
    243 			break;
    244 		case RC_OPCODE_ENDLOOP:
    245 			loop->EndLoop = inst;
    246 			end_loops--;
    247 			break;
    248 		case RC_OPCODE_BRK:
    249 			/* Don't unroll loops if it has a BRK instruction
    250 			 * other one used when testing the main conditional
    251 			 * of the loop. */
    252 
    253 			/* Make sure we haven't entered a nested loops. */
    254 			if(inst != loop->Brk && end_loops == 1) {
    255 				return 0;
    256 			}
    257 			break;
    258 		case RC_OPCODE_IF:
    259 			count_inst.BranchDepth++;
    260 			break;
    261 		case RC_OPCODE_ENDIF:
    262 			count_inst.BranchDepth--;
    263 			break;
    264 		default:
    265 			rc_for_all_writes_mask(inst, get_incr_amount, &count_inst);
    266 			if(count_inst.Unknown){
    267 				return 0;
    268 			}
    269 			break;
    270 		}
    271 	}
    272 	/* Infinite loop */
    273 	if(count_inst.Amount == 0.0f){
    274 		return 0;
    275 	}
    276 	DBG("Counter is increased by %f each iteration.\n", count_inst.Amount);
    277 	/* Calculate the number of iterations of this loop.  Keeping this
    278 	 * simple, since we only support increment and decrement loops.
    279 	 */
    280 	limit_value = rc_get_constant_value(c, limit->Index, limit->Swizzle,
    281 							limit->Negate, 0);
    282 	DBG("Limit is %f.\n", limit_value);
    283 	/* The iteration calculations are opposite of what you would expect.
    284 	 * In a normal loop, if the condition is met, then loop continues, but
    285 	 * with our loops, if the condition is met, the is exited. */
    286 	switch(loop->Cond->U.I.Opcode){
    287 	case RC_OPCODE_SGE:
    288 	case RC_OPCODE_SLE:
    289 		iterations = (int) ceilf((limit_value - counter_value.Value) /
    290 							count_inst.Amount);
    291 		break;
    292 
    293 	case RC_OPCODE_SGT:
    294 	case RC_OPCODE_SLT:
    295 		iterations = (int) floorf((limit_value - counter_value.Value) /
    296 							count_inst.Amount) + 1;
    297 		break;
    298 	default:
    299 		return 0;
    300 	}
    301 
    302 	if (c->max_alu_insts > 0
    303 		&& iterations > loop_max_possible_iterations(c, loop)) {
    304 		return 0;
    305 	}
    306 
    307 	DBG("Loop will have %d iterations.\n", iterations);
    308 
    309 	/* Prepare loop for unrolling */
    310 	rc_remove_instruction(loop->Cond);
    311 	rc_remove_instruction(loop->If);
    312 	rc_remove_instruction(loop->Brk);
    313 	rc_remove_instruction(loop->EndIf);
    314 
    315 	unroll_loop(c, loop, iterations);
    316 	loop->EndLoop = NULL;
    317 	return 1;
    318 }
    319 
    320 /**
    321  * @param c
    322  * @param loop
    323  * @param inst A pointer to a BGNLOOP instruction.
    324  * @return 1 if all of the members of loop where set.
    325  * @return 0 if there was an error and some members of loop are still NULL.
    326  */
    327 static int build_loop_info(struct radeon_compiler * c, struct loop_info * loop,
    328 						struct rc_instruction * inst)
    329 {
    330 	struct rc_instruction * ptr;
    331 
    332 	if(inst->U.I.Opcode != RC_OPCODE_BGNLOOP){
    333 		rc_error(c, "%s: expected BGNLOOP", __FUNCTION__);
    334 		return 0;
    335 	}
    336 
    337 	memset(loop, 0, sizeof(struct loop_info));
    338 
    339 	loop->BeginLoop = inst;
    340 
    341 	for(ptr = loop->BeginLoop->Next; !loop->EndLoop; ptr = ptr->Next) {
    342 
    343 		if (ptr == &c->Program.Instructions) {
    344 			rc_error(c, "%s: BGNLOOP without an ENDLOOOP.\n",
    345 								__FUNCTION__);
    346 			return 0;
    347 		}
    348 
    349 		switch(ptr->U.I.Opcode){
    350 		case RC_OPCODE_BGNLOOP:
    351 		{
    352 			/* Nested loop, skip ahead to the end. */
    353 			unsigned int loop_depth = 1;
    354 			for(ptr = ptr->Next; ptr != &c->Program.Instructions;
    355 							ptr = ptr->Next){
    356 				if (ptr->U.I.Opcode == RC_OPCODE_BGNLOOP) {
    357 					loop_depth++;
    358 				} else if (ptr->U.I.Opcode == RC_OPCODE_ENDLOOP) {
    359 					if (!--loop_depth) {
    360 						break;
    361 					}
    362 				}
    363 			}
    364 			if (ptr == &c->Program.Instructions) {
    365 				rc_error(c, "%s: BGNLOOP without an ENDLOOOP\n",
    366 								__FUNCTION__);
    367 					return 0;
    368 			}
    369 			break;
    370 		}
    371 		case RC_OPCODE_BRK:
    372 		{
    373 			struct rc_src_register *src;
    374 			if(ptr->Next->U.I.Opcode != RC_OPCODE_ENDIF
    375 					|| ptr->Prev->U.I.Opcode != RC_OPCODE_IF
    376 					|| loop->Brk){
    377 				continue;
    378 			}
    379 			loop->Brk = ptr;
    380 			loop->If = ptr->Prev;
    381 			loop->EndIf = ptr->Next;
    382 			src = &loop->If->U.I.SrcReg[0];
    383 
    384 			for (loop->Cond = loop->If->Prev;
    385 				loop->Cond->U.I.Opcode != RC_OPCODE_BGNLOOP;
    386 				loop->Cond = loop->Cond->Prev) {
    387 
    388 				const struct rc_dst_register *dst = &loop->Cond->U.I.DstReg;
    389 				if (dst->File == src->File &&
    390 						dst->Index == src->Index &&
    391 						dst->WriteMask & (rc_swizzle_to_writemask(src->Swizzle))) {
    392 					if (loop->Cond->U.I.Opcode == RC_OPCODE_CMP) {
    393 						src = &loop->Cond->U.I.SrcReg[0];
    394 						continue;
    395 					}
    396 					break;
    397 				}
    398 			}
    399 
    400 			if (loop->Cond->U.I.Opcode == RC_OPCODE_BGNLOOP) {
    401 				rc_error(c, "%s: Cannot find condition for if\n", __FUNCTION__);
    402 				return 0;
    403 			}
    404 			break;
    405 		}
    406 		case RC_OPCODE_ENDLOOP:
    407 			loop->EndLoop = ptr;
    408 			break;
    409 		}
    410 	}
    411 
    412 	if (loop->BeginLoop && loop->Brk && loop->If && loop->EndIf
    413 					&& loop->Cond && loop->EndLoop) {
    414 		return 1;
    415 	}
    416 	return 0;
    417 }
    418 
    419 /**
    420  * This function prepares a loop to be unrolled by converting it into an if
    421  * statement.  Here is an outline of the conversion process:
    422  * BGNLOOP;                         	-> BGNLOOP;
    423  * <Additional conditional code>	-> <Additional conditional code>
    424  * SGE/SLT temp[0], temp[1], temp[2];	-> SLT/SGE temp[0], temp[1], temp[2];
    425  * IF temp[0];                      	-> IF temp[0];
    426  * BRK;                             	->
    427  * ENDIF;                           	-> <Loop Body>
    428  * <Loop Body>                      	-> ENDIF;
    429  * ENDLOOP;                         	-> ENDLOOP
    430  *
    431  * @param inst A pointer to a BGNLOOP instruction.
    432  * @return 1 for success, 0 for failure
    433  */
    434 static int transform_loop(struct emulate_loop_state * s,
    435 						struct rc_instruction * inst)
    436 {
    437 	struct loop_info * loop;
    438 
    439 	memory_pool_array_reserve(&s->C->Pool, struct loop_info,
    440 			s->Loops, s->LoopCount, s->LoopReserved, 1);
    441 
    442 	loop = &s->Loops[s->LoopCount++];
    443 
    444 	if (!build_loop_info(s->C, loop, inst)) {
    445 		rc_error(s->C, "Failed to build loop info\n");
    446 		return 0;
    447 	}
    448 
    449 	if(try_unroll_loop(s->C, loop)){
    450 		return 1;
    451 	}
    452 
    453 	/* Reverse the conditional instruction */
    454 	switch(loop->Cond->U.I.Opcode){
    455 	case RC_OPCODE_SGE:
    456 		loop->Cond->U.I.Opcode = RC_OPCODE_SLT;
    457 		break;
    458 	case RC_OPCODE_SLT:
    459 		loop->Cond->U.I.Opcode = RC_OPCODE_SGE;
    460 		break;
    461 	case RC_OPCODE_SLE:
    462 		loop->Cond->U.I.Opcode = RC_OPCODE_SGT;
    463 		break;
    464 	case RC_OPCODE_SGT:
    465 		loop->Cond->U.I.Opcode = RC_OPCODE_SLE;
    466 		break;
    467 	case RC_OPCODE_SEQ:
    468 		loop->Cond->U.I.Opcode = RC_OPCODE_SNE;
    469 		break;
    470 	case RC_OPCODE_SNE:
    471 		loop->Cond->U.I.Opcode = RC_OPCODE_SEQ;
    472 		break;
    473 	default:
    474 		rc_error(s->C, "loop->Cond is not a conditional.\n");
    475 		return 0;
    476 	}
    477 
    478 	/* Prepare the loop to be emulated */
    479 	rc_remove_instruction(loop->Brk);
    480 	rc_remove_instruction(loop->EndIf);
    481 	rc_insert_instruction(loop->EndLoop->Prev, loop->EndIf);
    482 	return 1;
    483 }
    484 
    485 void rc_transform_loops(struct radeon_compiler *c, void *user)
    486 {
    487 	struct emulate_loop_state * s = &c->loop_state;
    488 	struct rc_instruction * ptr;
    489 
    490 	memset(s, 0, sizeof(struct emulate_loop_state));
    491 	s->C = c;
    492 	for(ptr = s->C->Program.Instructions.Next;
    493 			ptr != &s->C->Program.Instructions; ptr = ptr->Next) {
    494 		if(ptr->Type == RC_INSTRUCTION_NORMAL &&
    495 					ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
    496 			if (!transform_loop(s, ptr))
    497 				return;
    498 		}
    499 	}
    500 }
    501 
    502 void rc_unroll_loops(struct radeon_compiler *c, void *user)
    503 {
    504 	struct rc_instruction * inst;
    505 	struct loop_info loop;
    506 
    507 	for(inst = c->Program.Instructions.Next;
    508 			inst != &c->Program.Instructions; inst = inst->Next) {
    509 
    510 		if (inst->U.I.Opcode == RC_OPCODE_BGNLOOP) {
    511 			if (build_loop_info(c, &loop, inst)) {
    512 				try_unroll_loop(c, &loop);
    513 			}
    514 		}
    515 	}
    516 }
    517 
    518 void rc_emulate_loops(struct radeon_compiler *c, void *user)
    519 {
    520 	struct emulate_loop_state * s = &c->loop_state;
    521 	int i;
    522 	/* Iterate backwards of the list of loops so that loops that nested
    523 	 * loops are unrolled first.
    524 	 */
    525 	for( i = s->LoopCount - 1; i >= 0; i-- ){
    526 		unsigned int iterations;
    527 
    528 		if(!s->Loops[i].EndLoop){
    529 			continue;
    530 		}
    531 		iterations = loop_max_possible_iterations(s->C, &s->Loops[i]);
    532 		unroll_loop(s->C, &s->Loops[i], iterations);
    533 	}
    534 }
    535