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_compiler_util.h"
36 #include "radeon_dataflow.h"
40 #define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)
43 struct radeon_compiler * C;
44 struct rc_src_register * Src;
50 struct radeon_compiler * C;
58 static unsigned int loop_max_possible_iterations(struct radeon_compiler *c,
59 struct loop_info * loop)
61 unsigned int total_i = rc_recompute_ips(c);
62 unsigned int loop_i = (loop->EndLoop->IP - loop->BeginLoop->IP) - 1;
63 /* +1 because the program already has one iteration of the loop. */
64 return 1 + ((c->max_alu_insts - total_i) / loop_i);
67 static void unroll_loop(struct radeon_compiler * c, struct loop_info * loop,
68 unsigned int iterations)
71 struct rc_instruction * ptr;
72 struct rc_instruction * first = loop->BeginLoop->Next;
73 struct rc_instruction * last = loop->EndLoop->Prev;
74 struct rc_instruction * append_to = last;
75 rc_remove_instruction(loop->BeginLoop);
76 rc_remove_instruction(loop->EndLoop);
77 for( i = 1; i < iterations; i++){
78 for(ptr = first; ptr != last->Next; ptr = ptr->Next){
79 struct rc_instruction *new = rc_alloc_instruction(c);
80 memcpy(new, ptr, sizeof(struct rc_instruction));
81 rc_insert_instruction(append_to, new);
88 static void update_const_value(void * data, struct rc_instruction * inst,
89 rc_register_file file, unsigned int index, unsigned int mask)
91 struct const_value * value = data;
92 if(value->Src->File != file ||
93 value->Src->Index != index ||
94 !(1 << GET_SWZ(value->Src->Swizzle, 0) & mask)){
97 switch(inst->U.I.Opcode){
99 if(!rc_src_reg_is_immediate(value->C, inst->U.I.SrcReg[0].File,
100 inst->U.I.SrcReg[0].Index)){
105 rc_get_constant_value(value->C,
106 inst->U.I.SrcReg[0].Index,
107 inst->U.I.SrcReg[0].Swizzle,
108 inst->U.I.SrcReg[0].Negate, 0);
113 static void get_incr_amount(void * data, struct rc_instruction * inst,
114 rc_register_file file, unsigned int index, unsigned int mask)
116 struct count_inst * count_inst = data;
118 const struct rc_opcode_info * opcode;
121 if(file != RC_FILE_TEMPORARY ||
122 count_inst->Index != index ||
123 (1 << GET_SWZ(count_inst->Swz,0) != mask)){
127 /* XXX: Give up if the counter is modified within an IF block. We
128 * could handle this case with better analysis. */
129 if (count_inst->BranchDepth > 0) {
130 count_inst->Unknown = 1;
134 /* Find the index of the counter register. */
135 opcode = rc_get_opcode_info(inst->U.I.Opcode);
136 if(opcode->NumSrcRegs != 2){
137 count_inst->Unknown = 1;
140 if(inst->U.I.SrcReg[0].File == RC_FILE_TEMPORARY &&
141 inst->U.I.SrcReg[0].Index == count_inst->Index &&
142 inst->U.I.SrcReg[0].Swizzle == count_inst->Swz){
144 } else if( inst->U.I.SrcReg[1].File == RC_FILE_TEMPORARY &&
145 inst->U.I.SrcReg[1].Index == count_inst->Index &&
146 inst->U.I.SrcReg[1].Swizzle == count_inst->Swz){
150 count_inst->Unknown = 1;
153 if(rc_src_reg_is_immediate(count_inst->C,
154 inst->U.I.SrcReg[amnt_src_index].File,
155 inst->U.I.SrcReg[amnt_src_index].Index)){
156 amount = rc_get_constant_value(count_inst->C,
157 inst->U.I.SrcReg[amnt_src_index].Index,
158 inst->U.I.SrcReg[amnt_src_index].Swizzle,
159 inst->U.I.SrcReg[amnt_src_index].Negate, 0);
162 count_inst->Unknown = 1 ;
165 switch(inst->U.I.Opcode){
167 count_inst->Amount += amount;
170 if(amnt_src_index == 0){
171 count_inst->Unknown = 0;
174 count_inst->Amount -= amount;
177 count_inst->Unknown = 1;
183 * If c->max_alu_inst is -1, then all eligible loops will be unrolled regardless
184 * of how many iterations they have.
186 static int try_unroll_loop(struct radeon_compiler * c, struct loop_info * loop)
190 struct count_inst count_inst;
192 struct rc_src_register * counter;
193 struct rc_src_register * limit;
194 struct const_value counter_value;
195 struct rc_instruction * inst;
197 /* Find the counter and the upper limit */
199 if(rc_src_reg_is_immediate(c, loop->Cond->U.I.SrcReg[0].File,
200 loop->Cond->U.I.SrcReg[0].Index)){
201 limit = &loop->Cond->U.I.SrcReg[0];
202 counter = &loop->Cond->U.I.SrcReg[1];
204 else if(rc_src_reg_is_immediate(c, loop->Cond->U.I.SrcReg[1].File,
205 loop->Cond->U.I.SrcReg[1].Index)){
206 limit = &loop->Cond->U.I.SrcReg[1];
207 counter = &loop->Cond->U.I.SrcReg[0];
210 DBG("No constant limit.\n");
214 /* Find the initial value of the counter */
215 counter_value.Src = counter;
216 counter_value.Value = 0.0f;
217 counter_value.HasValue = 0;
219 for(inst = c->Program.Instructions.Next; inst != loop->BeginLoop;
221 rc_for_all_writes_mask(inst, update_const_value, &counter_value);
223 if(!counter_value.HasValue){
224 DBG("Initial counter value cannot be determined.\n");
227 DBG("Initial counter value is %f\n", counter_value.Value);
228 /* Determine how the counter is modified each loop */
230 count_inst.Index = counter->Index;
231 count_inst.Swz = counter->Swizzle;
232 count_inst.Amount = 0.0f;
233 count_inst.Unknown = 0;
234 count_inst.BranchDepth = 0;
236 for(inst = loop->BeginLoop->Next; end_loops > 0; inst = inst->Next){
237 switch(inst->U.I.Opcode){
238 /* XXX In the future we might want to try to unroll nested
240 case RC_OPCODE_BGNLOOP:
243 case RC_OPCODE_ENDLOOP:
244 loop->EndLoop = inst;
248 /* Don't unroll loops if it has a BRK instruction
249 * other one used when testing the main conditional
252 /* Make sure we haven't entered a nested loops. */
253 if(inst != loop->Brk && end_loops == 1) {
258 count_inst.BranchDepth++;
260 case RC_OPCODE_ENDIF:
261 count_inst.BranchDepth--;
264 rc_for_all_writes_mask(inst, get_incr_amount, &count_inst);
265 if(count_inst.Unknown){
272 if(count_inst.Amount == 0.0f){
275 DBG("Counter is increased by %f each iteration.\n", count_inst.Amount);
276 /* Calculate the number of iterations of this loop. Keeping this
277 * simple, since we only support increment and decrement loops.
279 limit_value = rc_get_constant_value(c, limit->Index, limit->Swizzle,
281 DBG("Limit is %f.\n", limit_value);
282 /* The iteration calculations are opposite of what you would expect.
283 * In a normal loop, if the condition is met, then loop continues, but
284 * with our loops, if the condition is met, the is exited. */
285 switch(loop->Cond->U.I.Opcode){
288 iterations = (int) ceilf((limit_value - counter_value.Value) /
294 iterations = (int) floorf((limit_value - counter_value.Value) /
295 count_inst.Amount) + 1;
301 if (c->max_alu_insts > 0
302 && iterations > loop_max_possible_iterations(c, loop)) {
306 DBG("Loop will have %d iterations.\n", iterations);
308 /* Prepare loop for unrolling */
309 rc_remove_instruction(loop->Cond);
310 rc_remove_instruction(loop->If);
311 rc_remove_instruction(loop->Brk);
312 rc_remove_instruction(loop->EndIf);
314 unroll_loop(c, loop, iterations);
315 loop->EndLoop = NULL;
322 * @param inst A pointer to a BGNLOOP instruction.
323 * @return 1 if all of the members of loop where set.
324 * @return 0 if there was an error and some members of loop are still NULL.
326 static int build_loop_info(struct radeon_compiler * c, struct loop_info * loop,
327 struct rc_instruction * inst)
329 struct rc_instruction * ptr;
331 if(inst->U.I.Opcode != RC_OPCODE_BGNLOOP){
332 rc_error(c, "%s: expected BGNLOOP", __FUNCTION__);
336 memset(loop, 0, sizeof(struct loop_info));
338 loop->BeginLoop = inst;
340 for(ptr = loop->BeginLoop->Next; !loop->EndLoop; ptr = ptr->Next) {
342 if (ptr == &c->Program.Instructions) {
343 rc_error(c, "%s: BGNLOOP without an ENDLOOOP.\n",
348 switch(ptr->U.I.Opcode){
349 case RC_OPCODE_BGNLOOP:
351 /* Nested loop, skip ahead to the end. */
352 unsigned int loop_depth = 1;
353 for(ptr = ptr->Next; ptr != &c->Program.Instructions;
355 if (ptr->U.I.Opcode == RC_OPCODE_BGNLOOP) {
357 } else if (ptr->U.I.Opcode == RC_OPCODE_ENDLOOP) {
363 if (ptr == &c->Program.Instructions) {
364 rc_error(c, "%s: BGNLOOP without an ENDLOOOP\n",
371 if(ptr->Next->U.I.Opcode != RC_OPCODE_ENDIF
372 || ptr->Prev->U.I.Opcode != RC_OPCODE_IF
377 loop->If = ptr->Prev;
378 loop->EndIf = ptr->Next;
379 switch(loop->If->Prev->U.I.Opcode){
390 loop->Cond = loop->If->Prev;
393 case RC_OPCODE_ENDLOOP:
399 if (loop->BeginLoop && loop->Brk && loop->If && loop->EndIf
400 && loop->Cond && loop->EndLoop) {
407 * This function prepares a loop to be unrolled by converting it into an if
408 * statement. Here is an outline of the conversion process:
409 * BGNLOOP; -> BGNLOOP;
410 * <Additional conditional code> -> <Additional conditional code>
411 * SGE/SLT temp[0], temp[1], temp[2]; -> SLT/SGE temp[0], temp[1], temp[2];
412 * IF temp[0]; -> IF temp[0];
414 * ENDIF; -> <Loop Body>
415 * <Loop Body> -> ENDIF;
416 * ENDLOOP; -> ENDLOOP
418 * @param inst A pointer to a BGNLOOP instruction.
419 * @return 1 for success, 0 for failure
421 static int transform_loop(struct emulate_loop_state * s,
422 struct rc_instruction * inst)
424 struct loop_info * loop;
426 memory_pool_array_reserve(&s->C->Pool, struct loop_info,
427 s->Loops, s->LoopCount, s->LoopReserved, 1);
429 loop = &s->Loops[s->LoopCount++];
431 if (!build_loop_info(s->C, loop, inst)) {
432 rc_error(s->C, "Failed to build loop info\n");
436 if(try_unroll_loop(s->C, loop)){
440 /* Reverse the conditional instruction */
441 switch(loop->Cond->U.I.Opcode){
443 loop->Cond->U.I.Opcode = RC_OPCODE_SLT;
446 loop->Cond->U.I.Opcode = RC_OPCODE_SGE;
449 loop->Cond->U.I.Opcode = RC_OPCODE_SGT;
452 loop->Cond->U.I.Opcode = RC_OPCODE_SLE;
455 loop->Cond->U.I.Opcode = RC_OPCODE_SNE;
458 loop->Cond->U.I.Opcode = RC_OPCODE_SEQ;
461 rc_error(s->C, "loop->Cond is not a conditional.\n");
465 /* Prepare the loop to be emulated */
466 rc_remove_instruction(loop->Brk);
467 rc_remove_instruction(loop->EndIf);
468 rc_insert_instruction(loop->EndLoop->Prev, loop->EndIf);
472 void rc_transform_loops(struct radeon_compiler *c, void *user)
474 struct emulate_loop_state * s = &c->loop_state;
475 struct rc_instruction * ptr;
477 memset(s, 0, sizeof(struct emulate_loop_state));
479 for(ptr = s->C->Program.Instructions.Next;
480 ptr != &s->C->Program.Instructions; ptr = ptr->Next) {
481 if(ptr->Type == RC_INSTRUCTION_NORMAL &&
482 ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
483 if (!transform_loop(s, ptr))
489 void rc_unroll_loops(struct radeon_compiler *c, void *user)
491 struct rc_instruction * inst;
492 struct loop_info loop;
494 for(inst = c->Program.Instructions.Next;
495 inst != &c->Program.Instructions; inst = inst->Next) {
497 if (inst->U.I.Opcode == RC_OPCODE_BGNLOOP) {
498 if (build_loop_info(c, &loop, inst)) {
499 try_unroll_loop(c, &loop);
505 void rc_emulate_loops(struct radeon_compiler *c, void *user)
507 struct emulate_loop_state * s = &c->loop_state;
509 /* Iterate backwards of the list of loops so that loops that nested
510 * loops are unrolled first.
512 for( i = s->LoopCount - 1; i >= 0; i-- ){
513 unsigned int iterations;
515 if(!s->Loops[i].EndLoop){
518 iterations = loop_max_possible_iterations(s->C, &s->Loops[i]);
519 unroll_loop(s->C, &s->Loops[i], iterations);