src/mesa/drivers/dri/r300/compiler/radeon_emulate_loops.c

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