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

   1 /*
   2  * Copyright 2011 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 #include "radeon_variable.h"
  29
  30 #include "memory_pool.h"
  31 #include "radeon_compiler_util.h"
  32 #include "radeon_dataflow.h"
  33 #include "radeon_list.h"
  34 #include "radeon_opcodes.h"
  35 #include "radeon_program.h"
  36
  37 /**
  38  * Rewrite the index and writemask for the destination register of var
  39  * and its friends to new_index and new_writemask.  This function also takes
  40  * care of rewriting the swizzles for the sources of var.
  41  */
  42 void rc_variable_change_dst(
  43         struct rc_variable * var,
  44         unsigned int new_index,
  45         unsigned int new_writemask)
  46 {
  47         struct rc_variable * var_ptr;
  48         struct rc_list * readers;
  49         unsigned int old_mask = rc_variable_writemask_sum(var);
  50         unsigned int conversion_swizzle =
  51                         rc_make_conversion_swizzle(old_mask, new_writemask);
  52
  53         for (var_ptr = var; var_ptr; var_ptr = var_ptr->Friend) {
  54                 if (var_ptr->Inst->Type == RC_INSTRUCTION_NORMAL) {
  55                         rc_normal_rewrite_writemask(var_ptr->Inst,
  56                                                         conversion_swizzle);
  57                         var_ptr->Inst->U.I.DstReg.Index = new_index;
  58                 } else {
  59                         struct rc_pair_sub_instruction * sub;
  60                         if (var_ptr->Dst.WriteMask == RC_MASK_W) {
  61                                 assert(new_writemask & RC_MASK_W);
  62                                 sub = &var_ptr->Inst->U.P.Alpha;
  63                         } else {
  64                                 sub = &var_ptr->Inst->U.P.RGB;
  65                                 rc_pair_rewrite_writemask(sub,
  66                                                         conversion_swizzle);
  67                         }
  68                         sub->DestIndex = new_index;
  69                 }
  70         }
  71
  72         readers = rc_variable_readers_union(var);
  73
  74         for ( ; readers; readers = readers->Next) {
  75                 struct rc_reader * reader = readers->Item;
  76                 if (reader->Inst->Type == RC_INSTRUCTION_NORMAL) {
  77                         reader->U.I.Src->Index = new_index;
  78                         reader->U.I.Src->Swizzle = rc_rewrite_swizzle(
  79                                 reader->U.I.Src->Swizzle, conversion_swizzle);
  80                 } else {
  81                         struct rc_pair_instruction * pair_inst =
  82                                                         &reader->Inst->U.P;
  83                         unsigned int src_type = rc_source_type_swz(
  84                                                         reader->U.P.Arg->Swizzle);
  85
  86                         int src_index = reader->U.P.Arg->Source;
  87                         if (src_index == RC_PAIR_PRESUB_SRC) {
  88                                 src_index = rc_pair_get_src_index(
  89                                                 pair_inst, reader->U.P.Src);
  90                         }
  91                         /* Try to delete the old src, it is OK if this fails,
  92                          * because rc_pair_alloc_source might be able to
  93                          * find a source the ca be reused.
  94                          */
  95                         if (rc_pair_remove_src(reader->Inst, src_type,
  96                                                         src_index, old_mask)) {
  97                                 /* Reuse the source index of the source that
  98                                  * was just deleted and set its register
  99                                  * index.  We can't use rc_pair_alloc_source
 100                                  * for this becuase it might return a source
 101                                  * index that is already being used. */
 102                                 if (src_type & RC_SOURCE_RGB) {
 103                                         pair_inst->RGB.Src[src_index]
 104                                                 .Used = 1;
 105                                         pair_inst->RGB.Src[src_index]
 106                                                 .Index = new_index;
 107                                         pair_inst->RGB.Src[src_index]
 108                                                 .File = RC_FILE_TEMPORARY;
 109                                 }
 110                                 if (src_type & RC_SOURCE_ALPHA) {
 111                                         pair_inst->Alpha.Src[src_index]
 112                                                 .Used = 1;
 113                                         pair_inst->Alpha.Src[src_index]
 114                                                 .Index = new_index;
 115                                         pair_inst->Alpha.Src[src_index]
 116                                                 .File = RC_FILE_TEMPORARY;
 117                                 }
 118                         } else {
 119                                 src_index = rc_pair_alloc_source(
 120                                                 &reader->Inst->U.P,
 121                                                 src_type & RC_SOURCE_RGB,
 122                                                 src_type & RC_SOURCE_ALPHA,
 123                                                 RC_FILE_TEMPORARY,
 124                                                 new_index);
 125                                 if (src_index < 0) {
 126                                         rc_error(var->C, "Rewrite of inst %u failed "
 127                                                 "Can't allocate source for "
 128                                                 "Inst %u src_type=%x "
 129                                                 "new_index=%u new_mask=%u\n",
 130                                                 var->Inst->IP, reader->Inst->IP, src_type, new_index, new_writemask);
 131                                                 continue;
 132                                 }
 133                         }
 134                         reader->U.P.Arg->Swizzle = rc_rewrite_swizzle(
 135                                 reader->U.P.Arg->Swizzle, conversion_swizzle);
 136                         if (reader->U.P.Arg->Source != RC_PAIR_PRESUB_SRC) {
 137                                 reader->U.P.Arg->Source = src_index;
 138                         }
 139                 }
 140         }
 141 }
 142
 143 /**
 144  * Compute the live intervals for var and its friends.
 145  */
 146 void rc_variable_compute_live_intervals(struct rc_variable * var)
 147 {
 148         while(var) {
 149                 unsigned int i;
 150                 unsigned int start = var->Inst->IP;
 151
 152                 for (i = 0; i < var->ReaderCount; i++) {
 153                         unsigned int chan;
 154                         unsigned int chan_start = start;
 155                         unsigned int chan_end = var->Readers[i].Inst->IP;
 156                         unsigned int mask = var->Readers[i].WriteMask;
 157                         struct rc_instruction * inst;
 158
 159                         /* Extend the live interval of T0 to the start of the
 160                          * loop for sequences like:
 161                          * BGNLOOP
 162                          * read T0
 163                          * ...
 164                          * write T0
 165                          * ENDLOOP
 166                          */
 167                         if (var->Readers[i].Inst->IP < start) {
 168                                 struct rc_instruction * bgnloop =
 169                                         rc_match_endloop(var->Readers[i].Inst);
 170                                 chan_start = bgnloop->IP;
 171                         }
 172
 173                         /* Extend the live interval of T0 to the start of the
 174                          * loop in case there is a BRK instruction in the loop
 175                          * (we don't actually check for a BRK instruction we
 176                          * assume there is one somewhere in the loop, which
 177                          * there usually is) for sequences like:
 178                          * BGNLOOP
 179                          * ...
 180                          * conditional BRK
 181                          * ...
 182                          * write T0
 183                          * ENDLOOP
 184                          * read T0
 185                          ***************************************************
 186                          * Extend the live interval of T0 to the end of the
 187                          * loop for sequences like:
 188                          * write T0
 189                          * BGNLOOP
 190                          * ...
 191                          * read T0
 192                          * ENDLOOP
 193                          */
 194                         for (inst = var->Inst; inst != var->Readers[i].Inst;
 195                                                         inst = inst->Next) {
 196                                 rc_opcode op = rc_get_flow_control_inst(inst);
 197                                 if (op == RC_OPCODE_ENDLOOP) {
 198                                         struct rc_instruction * bgnloop =
 199                                                 rc_match_endloop(inst);
 200                                         if (bgnloop->IP < chan_start) {
 201                                                 chan_start = bgnloop->IP;
 202                                         }
 203                                 } else if (op == RC_OPCODE_BGNLOOP) {
 204                                         struct rc_instruction * endloop =
 205                                                 rc_match_bgnloop(inst);
 206                                         if (endloop->IP > chan_end) {
 207                                                 chan_end = endloop->IP;
 208                                         }
 209                                 }
 210                         }
 211
 212                         for (chan = 0; chan < 4; chan++) {
 213                                 if ((mask >> chan) & 0x1) {
 214                                         if (!var->Live[chan].Used
 215                                         || chan_start < var->Live[chan].Start) {
 216                                                 var->Live[chan].Start =
 217                                                                 chan_start;
 218                                         }
 219                                         if (!var->Live[chan].Used
 220                                         || chan_end > var->Live[chan].End) {
 221                                                 var->Live[chan].End = chan_end;
 222                                         }
 223                                         var->Live[chan].Used = 1;
 224                                 }
 225                         }
 226                 }
 227                 var = var->Friend;
 228         }
 229 }
 230
 231 /**
 232  * @return 1 if a and b share a reader
 233  * @return 0 if they do not
 234  */
 235 static unsigned int readers_intersect(
 236         struct rc_variable * a,
 237         struct rc_variable * b)
 238 {
 239         unsigned int a_index, b_index;
 240         for (a_index = 0; a_index < a->ReaderCount; a_index++) {
 241                 struct rc_reader reader_a = a->Readers[a_index];
 242                 for (b_index = 0; b_index < b->ReaderCount; b_index++) {
 243                         struct rc_reader reader_b = b->Readers[b_index];
 244                         if (reader_a.Inst->Type == RC_INSTRUCTION_NORMAL
 245                                 && reader_b.Inst->Type == RC_INSTRUCTION_NORMAL
 246                                 && reader_a.U.I.Src == reader_b.U.I.Src) {
 247
 248                                 return 1;
 249                         }
 250                         if (reader_a.Inst->Type == RC_INSTRUCTION_PAIR
 251                                 && reader_b.Inst->Type == RC_INSTRUCTION_PAIR
 252                                 && reader_a.U.P.Src == reader_b.U.P.Src) {
 253
 254                                 return 1;
 255                         }
 256                 }
 257         }
 258         return 0;
 259 }
 260
 261 void rc_variable_add_friend(
 262         struct rc_variable * var,
 263         struct rc_variable * friend)
 264 {
 265         assert(var->Dst.Index == friend->Dst.Index);
 266         while(var->Friend) {
 267                 var = var->Friend;
 268         }
 269         var->Friend = friend;
 270 }
 271
 272 struct rc_variable * rc_variable(
 273         struct radeon_compiler * c,
 274         unsigned int DstFile,
 275         unsigned int DstIndex,
 276         unsigned int DstWriteMask,
 277         struct rc_reader_data * reader_data)
 278 {
 279         struct rc_variable * new =
 280                         memory_pool_malloc(&c->Pool, sizeof(struct rc_variable));
 281         memset(new, 0, sizeof(struct rc_variable));
 282         new->C = c;
 283         new->Dst.File = DstFile;
 284         new->Dst.Index = DstIndex;
 285         new->Dst.WriteMask = DstWriteMask;
 286         if (reader_data) {
 287                 new->Inst = reader_data->Writer;
 288                 new->ReaderCount = reader_data->ReaderCount;
 289                 new->Readers = reader_data->Readers;
 290         }
 291         return new;
 292 }
 293
 294 static void get_variable_helper(
 295         struct rc_list ** variable_list,
 296         struct rc_variable * variable)
 297 {
 298         struct rc_list * list_ptr;
 299         for (list_ptr = *variable_list; list_ptr; list_ptr = list_ptr->Next) {
 300                 struct rc_variable * var;
 301                 for (var = list_ptr->Item; var; var = var->Friend) {
 302                         if (readers_intersect(var, variable)) {
 303                                 rc_variable_add_friend(var, variable);
 304                                 return;
 305                         }
 306                 }
 307         }
 308         rc_list_add(variable_list, rc_list(&variable->C->Pool, variable));
 309 }
 310
 311 static void get_variable_pair_helper(
 312         struct rc_list ** variable_list,
 313         struct radeon_compiler * c,
 314         struct rc_instruction * inst,
 315         struct rc_pair_sub_instruction * sub_inst)
 316 {
 317         struct rc_reader_data reader_data;
 318         struct rc_variable * new_var;
 319         rc_register_file file;
 320         unsigned int writemask;
 321
 322         if (sub_inst->Opcode == RC_OPCODE_NOP) {
 323                 return;
 324         }
 325         memset(&reader_data, 0, sizeof(struct rc_reader_data));
 326         rc_get_readers_sub(c, inst, sub_inst, &reader_data, NULL, NULL, NULL);
 327
 328         if (reader_data.ReaderCount == 0) {
 329                 return;
 330         }
 331
 332         if (sub_inst->WriteMask) {
 333                 file = RC_FILE_TEMPORARY;
 334                 writemask = sub_inst->WriteMask;
 335         } else if (sub_inst->OutputWriteMask) {
 336                 file = RC_FILE_OUTPUT;
 337                 writemask = sub_inst->OutputWriteMask;
 338         } else {
 339                 writemask = 0;
 340                 file = RC_FILE_NONE;
 341         }
 342         new_var = rc_variable(c, file, sub_inst->DestIndex, writemask,
 343                                                                 &reader_data);
 344         get_variable_helper(variable_list, new_var);
 345 }
 346
 347 /**
 348  * Generate a list of variables used by the shader program.  Each instruction
 349  * that writes to a register is considered a variable.  The struct rc_variable
 350  * data structure includes a list of readers and is essentially a
 351  * definition-use chain.  Any two variables that share a reader are considered
 352  * "friends" and they are linked together via the Friend attribute.
 353  */
 354 struct rc_list * rc_get_variables(struct radeon_compiler * c)
 355 {
 356         struct rc_instruction * inst;
 357         struct rc_list * variable_list = NULL;
 358
 359         for (inst = c->Program.Instructions.Next;
 360                                         inst != &c->Program.Instructions;
 361                                         inst = inst->Next) {
 362                 struct rc_reader_data reader_data;
 363                 struct rc_variable * new_var;
 364                 memset(&reader_data, 0, sizeof(reader_data));
 365
 366                 if (inst->Type == RC_INSTRUCTION_NORMAL) {
 367                         rc_get_readers(c, inst, &reader_data, NULL, NULL, NULL);
 368                         if (reader_data.ReaderCount == 0) {
 369                                 continue;
 370                         }
 371                         new_var = rc_variable(c, inst->U.I.DstReg.File,
 372                                 inst->U.I.DstReg.Index,
 373                                 inst->U.I.DstReg.WriteMask, &reader_data);
 374                         get_variable_helper(&variable_list, new_var);
 375                 } else {
 376                         get_variable_pair_helper(&variable_list, c, inst,
 377                                                         &inst->U.P.RGB);
 378                         get_variable_pair_helper(&variable_list, c, inst,
 379                                                         &inst->U.P.Alpha);
 380                 }
 381         }
 382
 383         return variable_list;
 384 }
 385
 386 /**
 387  * @return The bitwise or of the writemasks of a variable and all of its
 388  * friends.
 389  */
 390 unsigned int rc_variable_writemask_sum(struct rc_variable * var)
 391 {
 392         unsigned int writemask = 0;
 393         while(var) {
 394                 writemask |= var->Dst.WriteMask;
 395                 var = var->Friend;
 396         }
 397         return writemask;
 398 }
 399
 400 /*
 401  * @return A list of readers for a variable and its friends.  Readers
 402  * that read from two different variable friends are only included once in
 403  * this list.
 404  */
 405 struct rc_list * rc_variable_readers_union(struct rc_variable * var)
 406 {
 407         struct rc_list * list = NULL;
 408         while (var) {
 409                 unsigned int i;
 410                 for (i = 0; i < var->ReaderCount; i++) {
 411                         struct rc_list * temp;
 412                         struct rc_reader * a = &var->Readers[i];
 413                         unsigned int match = 0;
 414                         for (temp = list; temp; temp = temp->Next) {
 415                                 struct rc_reader * b = temp->Item;
 416                                 if (a->Inst->Type != b->Inst->Type) {
 417                                         continue;
 418                                 }
 419                                 if (a->Inst->Type == RC_INSTRUCTION_NORMAL) {
 420                                         if (a->U.I.Src == b->U.I.Src) {
 421                                                 match = 1;
 422                                                 break;
 423                                         }
 424                                 }
 425                                 if (a->Inst->Type == RC_INSTRUCTION_PAIR) {
 426                                         if (a->U.P.Arg == b->U.P.Arg
 427                                             && a->U.P.Src == b->U.P.Src) {
 428                                                 match = 1;
 429                                                 break;
 430                                         }
 431                                 }
 432                         }
 433                         if (match) {
 434                                 continue;
 435                         }
 436                         rc_list_add(&list, rc_list(&var->C->Pool, a));
 437                 }
 438                 var = var->Friend;
 439         }
 440         return list;
 441 }
 442
 443 static unsigned int reader_equals_src(
 444         struct rc_reader reader,
 445         unsigned int src_type,
 446         void * src)
 447 {
 448         if (reader.Inst->Type != src_type) {
 449                 return 0;
 450         }
 451         if (src_type == RC_INSTRUCTION_NORMAL) {
 452                 return reader.U.I.Src == src;
 453         } else {
 454                 return reader.U.P.Src == src;
 455         }
 456 }
 457
 458 static unsigned int variable_writes_src(
 459         struct rc_variable * var,
 460         unsigned int src_type,
 461         void * src)
 462 {
 463         unsigned int i;
 464         for (i = 0; i < var->ReaderCount; i++) {
 465                 if (reader_equals_src(var->Readers[i], src_type, src)) {
 466                         return 1;
 467                 }
 468         }
 469         return 0;
 470 }
 471
 472
 473 struct rc_list * rc_variable_list_get_writers(
 474         struct rc_list * var_list,
 475         unsigned int src_type,
 476         void * src)
 477 {
 478         struct rc_list * list_ptr;
 479         struct rc_list * writer_list = NULL;
 480         for (list_ptr = var_list; list_ptr; list_ptr = list_ptr->Next) {
 481                 struct rc_variable * var = list_ptr->Item;
 482                 if (variable_writes_src(var, src_type, src)) {
 483                         struct rc_variable * friend;
 484                         rc_list_add(&writer_list, rc_list(&var->C->Pool, var));
 485                         for (friend = var->Friend; friend;
 486                                                 friend = friend->Friend) {
 487                                 if (variable_writes_src(friend, src_type, src)) {
 488                                         rc_list_add(&writer_list,
 489                                                 rc_list(&var->C->Pool, friend));
 490                                 }
 491                         }
 492                         /* Once we have indentifed the variable and its
 493                          * friends that write this source, we can stop
 494                          * stop searching, because we know none of the
 495                          * other variables in the list will write this source.
 496                          * If they did they would be friends of var.
 497                          */
 498                         break;
 499                 }
 500         }
 501         return writer_list;
 502 }
 503
 504 struct rc_list * rc_variable_list_get_writers_one_reader(
 505         struct rc_list * var_list,
 506         unsigned int src_type,
 507         void * src)
 508 {
 509         struct rc_list * writer_list =
 510                 rc_variable_list_get_writers(var_list, src_type, src);
 511         struct rc_list * reader_list =
 512                 rc_variable_readers_union(writer_list->Item);
 513         if (rc_list_count(reader_list) > 1) {
 514                 return NULL;
 515         } else {
 516                 return writer_list;
 517         }
 518 }
 519
 520 void rc_variable_print(struct rc_variable * var)
 521 {
 522         unsigned int i;
 523         while (var) {
 524                 fprintf(stderr, "%u: TEMP[%u].%u: ",
 525                         var->Inst->IP, var->Dst.Index, var->Dst.WriteMask);
 526                 for (i = 0; i < 4; i++) {
 527                         fprintf(stderr, "chan %u: start=%u end=%u ", i,
 528                                         var->Live[i].Start, var->Live[i].End);
 529                 }
 530                 fprintf(stderr, "%u readers\n", var->ReaderCount);
 531                 if (var->Friend) {
 532                         fprintf(stderr, "Friend: \n\t");
 533                 }
 534                 var = var->Friend;
 535         }
 536 }