2 * Copyright 2010 Tom Stellard <tstellar@gmail.com>
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:
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.
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.
32 #include "radeon_emulate_loops.h"
34 #include "radeon_compiler.h"
35 #include "radeon_dataflow.h"
39 #define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)
42 struct radeon_compiler * C;
43 struct rc_src_register * Src;
49 struct radeon_compiler * C;
56 static float get_constant_value(struct radeon_compiler * c,
57 struct rc_src_register * src,
61 int swz = GET_SWZ(src->Swizzle, chan);
62 if(swz >= 4 || src->Index >= c->Program.Constants.Count ){
63 rc_error(c, "get_constant_value: Can't find a value.\n");
66 if(GET_BIT(src->Negate, chan)){
70 c->Program.Constants.Constants[src->Index].u.Immediate[swz];
73 static int src_reg_is_immediate(struct rc_src_register * src,
74 struct radeon_compiler * c)
76 return src->File == RC_FILE_CONSTANT &&
77 c->Program.Constants.Constants[src->Index].Type==RC_CONSTANT_IMMEDIATE;
80 static unsigned int loop_max_possible_iterations(struct radeon_compiler *c,
81 struct loop_info * loop)
83 unsigned int total_i = rc_recompute_ips(c);
84 unsigned int loop_i = (loop->EndLoop->IP - loop->BeginLoop->IP) - 1;
85 /* +1 because the program already has one iteration of the loop. */
86 return 1 + ((c->max_alu_insts - total_i) / loop_i);
89 static void unroll_loop(struct radeon_compiler * c, struct loop_info * loop,
90 unsigned int iterations)
93 struct rc_instruction * ptr;
94 struct rc_instruction * first = loop->BeginLoop->Next;
95 struct rc_instruction * last = loop->EndLoop->Prev;
96 struct rc_instruction * append_to = last;
97 rc_remove_instruction(loop->BeginLoop);
98 rc_remove_instruction(loop->EndLoop);
99 for( i = 1; i < iterations; i++){
100 for(ptr = first; ptr != last->Next; ptr = ptr->Next){
101 struct rc_instruction *new = rc_alloc_instruction(c);
102 memcpy(new, ptr, sizeof(struct rc_instruction));
103 rc_insert_instruction(append_to, new);
110 static void update_const_value(void * data, struct rc_instruction * inst,
111 rc_register_file file, unsigned int index, unsigned int mask)
113 struct const_value * value = data;
114 if(value->Src->File != file ||
115 value->Src->Index != index ||
116 !(1 << GET_SWZ(value->Src->Swizzle, 0) & mask)){
119 switch(inst->U.I.Opcode){
121 if(!src_reg_is_immediate(&inst->U.I.SrcReg[0], value->C)){
126 get_constant_value(value->C, &inst->U.I.SrcReg[0], 0);
131 static void get_incr_amount(void * data, struct rc_instruction * inst,
132 rc_register_file file, unsigned int index, unsigned int mask)
134 struct count_inst * count_inst = data;
136 const struct rc_opcode_info * opcode;
139 if(file != RC_FILE_TEMPORARY ||
140 count_inst->Index != index ||
141 (1 << GET_SWZ(count_inst->Swz,0) != mask)){
144 /* Find the index of the counter register. */
145 opcode = rc_get_opcode_info(inst->U.I.Opcode);
146 if(opcode->NumSrcRegs != 2){
147 count_inst->Unknown = 1;
150 if(inst->U.I.SrcReg[0].File == RC_FILE_TEMPORARY &&
151 inst->U.I.SrcReg[0].Index == count_inst->Index &&
152 inst->U.I.SrcReg[0].Swizzle == count_inst->Swz){
154 } else if( inst->U.I.SrcReg[1].File == RC_FILE_TEMPORARY &&
155 inst->U.I.SrcReg[1].Index == count_inst->Index &&
156 inst->U.I.SrcReg[1].Swizzle == count_inst->Swz){
160 count_inst->Unknown = 1;
163 if(src_reg_is_immediate(&inst->U.I.SrcReg[amnt_src_index],
165 amount = get_constant_value(count_inst->C,
166 &inst->U.I.SrcReg[amnt_src_index], 0);
169 count_inst->Unknown = 1 ;
172 switch(inst->U.I.Opcode){
174 count_inst->Amount += amount;
177 if(amnt_src_index == 0){
178 count_inst->Unknown = 0;
181 count_inst->Amount -= amount;
184 count_inst->Unknown = 1;
190 * If c->max_alu_inst is -1, then all eligible loops will be unrolled regardless
191 * of how many iterations they have.
193 static int try_unroll_loop(struct radeon_compiler * c, struct loop_info * loop)
197 struct count_inst count_inst;
199 struct rc_src_register * counter;
200 struct rc_src_register * limit;
201 struct const_value counter_value;
202 struct rc_instruction * inst;
204 /* Find the counter and the upper limit */
206 if(src_reg_is_immediate(&loop->Cond->U.I.SrcReg[0], c)){
207 limit = &loop->Cond->U.I.SrcReg[0];
208 counter = &loop->Cond->U.I.SrcReg[1];
210 else if(src_reg_is_immediate(&loop->Cond->U.I.SrcReg[1], c)){
211 limit = &loop->Cond->U.I.SrcReg[1];
212 counter = &loop->Cond->U.I.SrcReg[0];
215 DBG("No constant limit.\n");
219 /* Find the initial value of the counter */
220 counter_value.Src = counter;
221 counter_value.Value = 0.0f;
222 counter_value.HasValue = 0;
224 for(inst = c->Program.Instructions.Next; inst != loop->BeginLoop;
226 rc_for_all_writes_mask(inst, update_const_value, &counter_value);
228 if(!counter_value.HasValue){
229 DBG("Initial counter value cannot be determined.\n");
232 DBG("Initial counter value is %f\n", counter_value.Value);
233 /* Determine how the counter is modified each loop */
235 count_inst.Index = counter->Index;
236 count_inst.Swz = counter->Swizzle;
237 count_inst.Amount = 0.0f;
238 count_inst.Unknown = 0;
240 for(inst = loop->BeginLoop->Next; end_loops > 0; inst = inst->Next){
241 switch(inst->U.I.Opcode){
242 /* XXX In the future we might want to try to unroll nested
244 case RC_OPCODE_BGNLOOP:
247 case RC_OPCODE_ENDLOOP:
248 loop->EndLoop = inst;
252 /* Don't unroll loops if it has a BRK instruction
253 * other one used when testing the main conditional
256 /* Make sure we haven't entered a nested loops. */
257 if(inst != loop->Brk && end_loops == 1) {
261 /* XXX Check if the counter is modified within an if statement.
266 rc_for_all_writes_mask(inst, get_incr_amount, &count_inst);
267 if(count_inst.Unknown){
274 if(count_inst.Amount == 0.0f){
277 DBG("Counter is increased by %f each iteration.\n", count_inst.Amount);
278 /* Calculate the number of iterations of this loop. Keeping this
279 * simple, since we only support increment and decrement loops.
281 limit_value = get_constant_value(c, limit, 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){
289 iterations = (int) ceilf((limit_value - counter_value.Value) /
295 iterations = (int) floorf((limit_value - counter_value.Value) /
296 count_inst.Amount) + 1;
302 if (c->max_alu_insts > 0
303 && iterations > loop_max_possible_iterations(c, loop)) {
307 DBG("Loop will have %d iterations.\n", iterations);
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);
315 unroll_loop(c, loop, iterations);
316 loop->EndLoop = NULL;
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.
327 static int build_loop_info(struct radeon_compiler * c, struct loop_info * loop,
328 struct rc_instruction * inst)
330 struct rc_instruction * ptr;
332 if(inst->U.I.Opcode != RC_OPCODE_BGNLOOP){
333 rc_error(c, "%s: expected BGNLOOP", __FUNCTION__);
337 memset(loop, 0, sizeof(struct loop_info));
339 loop->BeginLoop = inst;
341 for(ptr = loop->BeginLoop->Next; !loop->EndLoop; ptr = ptr->Next) {
343 if (ptr == &c->Program.Instructions) {
344 rc_error(c, "%s: BGNLOOP without an ENDLOOOP.\n",
349 switch(ptr->U.I.Opcode){
350 case RC_OPCODE_BGNLOOP:
352 /* Nested loop, skip ahead to the end. */
353 unsigned int loop_depth = 1;
354 for(ptr = ptr->Next; ptr != &c->Program.Instructions;
356 if (ptr->U.I.Opcode == RC_OPCODE_BGNLOOP) {
358 } else if (ptr->U.I.Opcode == RC_OPCODE_ENDLOOP) {
364 if (ptr == &c->Program.Instructions) {
365 rc_error(c, "%s: BGNLOOP without an ENDLOOOP\n",
372 if(ptr->Next->U.I.Opcode != RC_OPCODE_ENDIF
373 || ptr->Prev->U.I.Opcode != RC_OPCODE_IF
378 loop->If = ptr->Prev;
379 loop->EndIf = ptr->Next;
380 switch(loop->If->Prev->U.I.Opcode){
391 loop->Cond = loop->If->Prev;
394 case RC_OPCODE_ENDLOOP:
400 if (loop->BeginLoop && loop->Brk && loop->If && loop->EndIf
401 && loop->Cond && loop->EndLoop) {
408 * This function prepares a loop to be unrolled by converting it into an if
409 * statement. Here is an outline of the conversion process:
410 * BGNLOOP; -> BGNLOOP;
411 * <Additional conditional code> -> <Additional conditional code>
412 * SGE/SLT temp[0], temp[1], temp[2]; -> SLT/SGE temp[0], temp[1], temp[2];
413 * IF temp[0]; -> IF temp[0];
415 * ENDIF; -> <Loop Body>
416 * <Loop Body> -> ENDIF;
417 * ENDLOOP; -> ENDLOOP
419 * @param inst A pointer to a BGNLOOP instruction.
420 * @return 1 for success, 0 for failure
422 static int transform_loop(struct emulate_loop_state * s,
423 struct rc_instruction * inst)
425 struct loop_info * loop;
427 memory_pool_array_reserve(&s->C->Pool, struct loop_info,
428 s->Loops, s->LoopCount, s->LoopReserved, 1);
430 loop = &s->Loops[s->LoopCount++];
432 if (!build_loop_info(s->C, loop, inst)) {
433 rc_error(s->C, "Failed to build loop info\n");
437 if(try_unroll_loop(s->C, loop)){
441 /* Reverse the conditional instruction */
442 switch(loop->Cond->U.I.Opcode){
444 loop->Cond->U.I.Opcode = RC_OPCODE_SLT;
447 loop->Cond->U.I.Opcode = RC_OPCODE_SGE;
450 loop->Cond->U.I.Opcode = RC_OPCODE_SGT;
453 loop->Cond->U.I.Opcode = RC_OPCODE_SLE;
456 loop->Cond->U.I.Opcode = RC_OPCODE_SNE;
459 loop->Cond->U.I.Opcode = RC_OPCODE_SEQ;
462 rc_error(s->C, "loop->Cond is not a conditional.\n");
466 /* Prepare the loop to be emulated */
467 rc_remove_instruction(loop->Brk);
468 rc_remove_instruction(loop->EndIf);
469 rc_insert_instruction(loop->EndLoop->Prev, loop->EndIf);
473 void rc_transform_loops(struct radeon_compiler *c, void *user)
475 struct emulate_loop_state * s = &c->loop_state;
476 struct rc_instruction * ptr;
478 memset(s, 0, sizeof(struct emulate_loop_state));
480 for(ptr = s->C->Program.Instructions.Next;
481 ptr != &s->C->Program.Instructions; ptr = ptr->Next) {
482 if(ptr->Type == RC_INSTRUCTION_NORMAL &&
483 ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
484 if (!transform_loop(s, ptr))
490 void rc_unroll_loops(struct radeon_compiler *c, void *user)
492 struct rc_instruction * inst;
493 struct loop_info loop;
495 for(inst = c->Program.Instructions.Next;
496 inst != &c->Program.Instructions; inst = inst->Next) {
498 if (inst->U.I.Opcode == RC_OPCODE_BGNLOOP) {
499 if (build_loop_info(c, &loop, inst)) {
500 try_unroll_loop(c, &loop);
506 void rc_emulate_loops(struct radeon_compiler *c, void *user)
508 struct emulate_loop_state * s = &c->loop_state;
510 /* Iterate backwards of the list of loops so that loops that nested
511 * loops are unrolled first.
513 for( i = s->LoopCount - 1; i >= 0; i-- ){
514 unsigned int iterations;
516 if(!s->Loops[i].EndLoop){
519 iterations = loop_max_possible_iterations(s->C, &s->Loops[i]);
520 unroll_loop(s->C, &s->Loops[i], iterations);