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