src/gallium/drivers/vc4/vc4_qir_schedule.c

   1 /*
   2  * Copyright © 2010 Intel Corporation
   3  * Copyright © 2014-2015 Broadcom
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the next
  13  * paragraph) shall be included in all copies or substantial portions of the
  14  * Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22  * IN THE SOFTWARE.
  23  */
  24
  25 /**
  26  * @file vc4_qir_schedule.c
  27  *
  28  * The basic model of the list scheduler is to take a basic block, compute a
  29  * DAG of the dependencies from the bottom up, and make a list of the DAG
  30  * heads.  Heuristically pick a DAG head and schedule (remove) it, then put
  31  * all the parents that are now DAG heads into the list of things to
  32  * schedule.
  33  *
  34  * The goal of scheduling here, before register allocation and conversion to
  35  * QPU instructions, is to reduce register pressure by reordering instructions
  36  * to consume values when possible.
  37  */
  38
  39 #include "vc4_qir.h"
  40
  41 static bool debug;
  42
  43 struct schedule_node {
  44         struct list_head link;
  45         struct qinst *inst;
  46
  47         struct schedule_node **children;
  48         uint32_t child_count;
  49         uint32_t child_array_size;
  50         uint32_t parent_count;
  51
  52         /* Length of the longest (latency) chain from a DAG head to the this
  53          * instruction.
  54          */
  55         uint32_t delay;
  56
  57         /* Longest time + latency_between(parent, this) of any parent of this
  58          * node.
  59          */
  60         uint32_t unblocked_time;
  61 };
  62
  63 struct schedule_state {
  64         /* List of struct schedule_node *.  This starts out with all
  65          * instructions, and after dependency updates it's trimmed to be just
  66          * the DAG heads.
  67          */
  68         struct list_head worklist;
  69
  70         uint32_t time;
  71
  72         uint32_t *temp_writes;
  73
  74         BITSET_WORD *temp_live;
  75 };
  76
  77 /* When walking the instructions in reverse, we need to swap before/after in
  78  * add_dep().
  79  */
  80 enum direction { F, R };
  81
  82 /**
  83  * Marks a dependency between two intructions, that @after must appear after
  84  * @before.
  85  *
  86  * Our dependencies are tracked as a DAG.  Since we're scheduling bottom-up,
  87  * the latest instructions with nothing left to schedule are the DAG heads,
  88  * and their inputs are their children.
  89  */
  90 static void
  91 add_dep(enum direction dir,
  92         struct schedule_node *before,
  93         struct schedule_node *after)
  94 {
  95         if (!before || !after)
  96                 return;
  97
  98         assert(before != after);
  99
 100         if (dir == R) {
 101                 struct schedule_node *t = before;
 102                 before = after;
 103                 after = t;
 104         }
 105
 106         for (int i = 0; i < after->child_count; i++) {
 107                 if (after->children[i] == after)
 108                         return;
 109         }
 110
 111         if (after->child_array_size <= after->child_count) {
 112                 after->child_array_size = MAX2(after->child_array_size * 2, 16);
 113                 after->children = reralloc(after, after->children,
 114                                            struct schedule_node *,
 115                                            after->child_array_size);
 116         }
 117
 118         after->children[after->child_count] = before;
 119         after->child_count++;
 120         before->parent_count++;
 121 }
 122
 123 static void
 124 add_write_dep(enum direction dir,
 125               struct schedule_node **before,
 126               struct schedule_node *after)
 127 {
 128         add_dep(dir, *before, after);
 129         *before = after;
 130 }
 131
 132 struct schedule_setup_state {
 133         struct schedule_node **last_temp_write;
 134         struct schedule_node *last_sf;
 135         struct schedule_node *last_vary_read;
 136         struct schedule_node *last_vpm_read;
 137         struct schedule_node *last_vpm_write;
 138         struct schedule_node *last_tex_coord;
 139         struct schedule_node *last_tex_result;
 140         struct schedule_node *last_tlb;
 141         enum direction dir;
 142
 143         /**
 144          * Texture FIFO tracking.  This is done top-to-bottom, and is used to
 145          * track the QOP_TEX_RESULTs and add dependencies on previous ones
 146          * when trying to submit texture coords with TFREQ full or new texture
 147          * fetches with TXRCV full.
 148          */
 149         struct {
 150                 struct schedule_node *node;
 151                 int coords;
 152         } tex_fifo[8];
 153         int tfreq_count; /**< Number of texture coords outstanding. */
 154         int tfrcv_count; /**< Number of texture results outstanding. */
 155         int tex_fifo_pos;
 156 };
 157
 158 static void
 159 block_until_tex_result(struct schedule_setup_state *state, struct schedule_node *n)
 160 {
 161         add_dep(state->dir, state->tex_fifo[0].node, n);
 162
 163         state->tfreq_count -= state->tex_fifo[0].coords;
 164         state->tfrcv_count--;
 165
 166         memmove(&state->tex_fifo[0],
 167                 &state->tex_fifo[1],
 168                 state->tex_fifo_pos * sizeof(state->tex_fifo[0]));
 169         state->tex_fifo_pos--;
 170 }
 171
 172 /**
 173  * Common code for dependencies that need to be tracked both forward and
 174  * backward.
 175  *
 176  * This is for things like "all VPM reads have to happen in order."
 177  */
 178 static void
 179 calculate_deps(struct schedule_setup_state *state, struct schedule_node *n)
 180 {
 181         struct qinst *inst = n->inst;
 182         enum direction dir = state->dir;
 183
 184
 185         /* Add deps for temp registers and varyings accesses.  Note that we
 186          * ignore uniforms accesses, because qir_reorder_uniforms() happens
 187          * after this.
 188          */
 189         for (int i = 0; i < qir_get_op_nsrc(inst->op); i++) {
 190                 switch (inst->src[i].file) {
 191                 case QFILE_TEMP:
 192                         add_dep(dir,
 193                                 state->last_temp_write[inst->src[i].index], n);
 194                         break;
 195
 196                 case QFILE_VARY:
 197                         add_write_dep(dir, &state->last_vary_read, n);
 198                         break;
 199
 200                 case QFILE_VPM:
 201                         add_write_dep(dir, &state->last_vpm_read, n);
 202                         break;
 203
 204                 default:
 205                         break;
 206                 }
 207         }
 208
 209         switch (inst->op) {
 210         case QOP_VARY_ADD_C:
 211                 add_dep(dir, state->last_vary_read, n);
 212                 break;
 213
 214         case QOP_TEX_S:
 215         case QOP_TEX_T:
 216         case QOP_TEX_R:
 217         case QOP_TEX_B:
 218         case QOP_TEX_DIRECT:
 219                 /* Texturing setup gets scheduled in order, because
 220                  * the uniforms referenced by them have to land in a
 221                  * specific order.
 222                  */
 223                 add_write_dep(dir, &state->last_tex_coord, n);
 224                 break;
 225
 226         case QOP_TEX_RESULT:
 227                 /* Results have to be fetched in order. */
 228                 add_write_dep(dir, &state->last_tex_result, n);
 229                 break;
 230
 231         case QOP_TLB_COLOR_WRITE:
 232         case QOP_TLB_COLOR_READ:
 233         case QOP_TLB_Z_WRITE:
 234         case QOP_TLB_STENCIL_SETUP:
 235         case QOP_MS_MASK:
 236                 add_write_dep(dir, &state->last_tlb, n);
 237                 break;
 238
 239         case QOP_TLB_DISCARD_SETUP:
 240                 add_write_dep(dir, &state->last_sf, n);
 241                 add_write_dep(dir, &state->last_tlb, n);
 242                 break;
 243
 244         default:
 245                 break;
 246         }
 247
 248         if (inst->dst.file == QFILE_VPM)
 249                 add_write_dep(dir, &state->last_vpm_write, n);
 250         else if (inst->dst.file == QFILE_TEMP)
 251                 add_write_dep(dir, &state->last_temp_write[inst->dst.index], n);
 252
 253         if (qir_depends_on_flags(inst))
 254                 add_dep(dir, state->last_sf, n);
 255
 256         if (inst->sf)
 257                 add_write_dep(dir, &state->last_sf, n);
 258 }
 259
 260 static void
 261 calculate_forward_deps(struct vc4_compile *c, void *mem_ctx,
 262                        struct list_head *schedule_list)
 263 {
 264         struct schedule_setup_state state;
 265
 266         memset(&state, 0, sizeof(state));
 267         state.last_temp_write = rzalloc_array(mem_ctx, struct schedule_node *,
 268                                               c->num_temps);
 269         state.dir = F;
 270
 271         list_for_each_entry(struct schedule_node, n, schedule_list, link) {
 272                 struct qinst *inst = n->inst;
 273
 274                 calculate_deps(&state, n);
 275
 276                 switch (inst->op) {
 277                 case QOP_TEX_S:
 278                 case QOP_TEX_T:
 279                 case QOP_TEX_R:
 280                 case QOP_TEX_B:
 281                 case QOP_TEX_DIRECT:
 282                         /* If the texture coordinate fifo is full,
 283                          * block this on the last QOP_TEX_RESULT.
 284                          */
 285                         if (state.tfreq_count == 8) {
 286                                 block_until_tex_result(&state, n);
 287                         }
 288
 289                         /* If the texture result fifo is full, block
 290                          * adding any more to it until the last
 291                          * QOP_TEX_RESULT.
 292                          */
 293                         if (inst->op == QOP_TEX_S ||
 294                             inst->op == QOP_TEX_DIRECT) {
 295                                 if (state.tfrcv_count == 4)
 296                                         block_until_tex_result(&state, n);
 297                                 state.tfrcv_count++;
 298                         }
 299
 300                         state.tex_fifo[state.tex_fifo_pos].coords++;
 301                         state.tfreq_count++;
 302                         break;
 303
 304                 case QOP_TEX_RESULT:
 305                         /* Results have to be fetched after the
 306                          * coordinate setup.  Note that we're assuming
 307                          * here that our input shader has the texture
 308                          * coord setup and result fetch in order,
 309                          * which is true initially but not of our
 310                          * instruction stream after this pass.
 311                          */
 312                         add_dep(state.dir, state.last_tex_coord, n);
 313
 314                         state.tex_fifo[state.tex_fifo_pos].node = n;
 315
 316                         state.tex_fifo_pos++;
 317                         memset(&state.tex_fifo[state.tex_fifo_pos], 0,
 318                                sizeof(state.tex_fifo[0]));
 319                         break;
 320                 default:
 321                         assert(!qir_is_tex(inst));
 322                         break;
 323                 }
 324         }
 325 }
 326
 327 static void
 328 calculate_reverse_deps(struct vc4_compile *c, void *mem_ctx,
 329                        struct list_head *schedule_list)
 330 {
 331         struct schedule_setup_state state;
 332
 333         memset(&state, 0, sizeof(state));
 334         state.dir = R;
 335         state.last_temp_write = rzalloc_array(mem_ctx, struct schedule_node *,
 336                                               c->num_temps);
 337
 338         list_for_each_entry_rev(struct schedule_node, n, schedule_list, link) {
 339                 calculate_deps(&state, n);
 340         }
 341 }
 342
 343 static int
 344 get_register_pressure_cost(struct schedule_state *state, struct qinst *inst)
 345 {
 346         int cost = 0;
 347
 348         if (inst->dst.file == QFILE_TEMP &&
 349             state->temp_writes[inst->dst.index] == 1)
 350                 cost--;
 351
 352         for (int i = 0; i < qir_get_op_nsrc(inst->op); i++) {
 353                 if (inst->src[i].file == QFILE_TEMP &&
 354                     !BITSET_TEST(state->temp_live, inst->src[i].index)) {
 355                         cost++;
 356                 }
 357         }
 358
 359         return cost;
 360 }
 361
 362 static bool
 363 locks_scoreboard(struct qinst *inst)
 364 {
 365         switch (inst->op) {
 366         case QOP_TLB_Z_WRITE:
 367         case QOP_TLB_COLOR_WRITE:
 368         case QOP_TLB_COLOR_WRITE_MS:
 369         case QOP_TLB_COLOR_READ:
 370                 return true;
 371         default:
 372                 return false;
 373         }
 374 }
 375
 376 static struct schedule_node *
 377 choose_instruction(struct schedule_state *state)
 378 {
 379         struct schedule_node *chosen = NULL;
 380
 381         list_for_each_entry(struct schedule_node, n, &state->worklist, link) {
 382                 if (!chosen) {
 383                         chosen = n;
 384                         continue;
 385                 }
 386
 387                 /* Prefer scheduling things that lock the scoreboard, so that
 388                  * they appear late in the program and we get more parallelism
 389                  * between shaders on multiple QPUs hitting the same fragment.
 390                  */
 391                 if (locks_scoreboard(n->inst) &&
 392                     !locks_scoreboard(chosen->inst)) {
 393                         chosen = n;
 394                         continue;
 395                 } else if (!locks_scoreboard(n->inst) &&
 396                            locks_scoreboard(chosen->inst)) {
 397                         continue;
 398                 }
 399
 400                 /* If we would block on the previously chosen node, but would
 401                  * block less on this one, then then prefer it.
 402                  */
 403                 if (chosen->unblocked_time > state->time &&
 404                     n->unblocked_time < chosen->unblocked_time) {
 405                         chosen = n;
 406                         continue;
 407                 } else if (n->unblocked_time > state->time &&
 408                            n->unblocked_time > chosen->unblocked_time) {
 409                         continue;
 410                 }
 411
 412                 /* If we can definitely reduce register pressure, do so
 413                  * immediately.
 414                  */
 415                 int register_pressure_cost =
 416                         get_register_pressure_cost(state, n->inst);
 417                 int chosen_register_pressure_cost =
 418                         get_register_pressure_cost(state, chosen->inst);
 419
 420                 if (register_pressure_cost < chosen_register_pressure_cost) {
 421                         chosen = n;
 422                         continue;
 423                 } else if (register_pressure_cost >
 424                            chosen_register_pressure_cost) {
 425                         continue;
 426                 }
 427
 428                 /* Otherwise, prefer instructions with the deepest chain to
 429                  * the end of the program.  This avoids the problem of
 430                  * "everything generates a temp, nothing finishes freeing one,
 431                  * guess I'll just keep emitting varying mul/adds".
 432                  */
 433                 if (n->delay > chosen->delay) {
 434                         chosen = n;
 435                         continue;
 436                 } else if (n->delay < chosen->delay) {
 437                         continue;
 438                 }
 439         }
 440
 441         return chosen;
 442 }
 443
 444 static void
 445 dump_state(struct vc4_compile *c, struct schedule_state *state)
 446 {
 447         uint32_t i = 0;
 448         list_for_each_entry(struct schedule_node, n, &state->worklist, link) {
 449                 fprintf(stderr, "%3d: ", i++);
 450                 qir_dump_inst(c, n->inst);
 451                 fprintf(stderr, " (%d cost)\n",
 452                         get_register_pressure_cost(state, n->inst));
 453
 454                 for (int i = 0; i < n->child_count; i++) {
 455                         struct schedule_node *child = n->children[i];
 456                         fprintf(stderr, "   - ");
 457                         qir_dump_inst(c, child->inst);
 458                         fprintf(stderr, " (%d parents)\n", child->parent_count);
 459                 }
 460         }
 461 }
 462
 463 /* Estimate of how many instructions we should schedule between operations.
 464  *
 465  * These aren't in real cycle counts, because we're just estimating cycle
 466  * times anyway.  QIR instructions will get paired up when turned into QPU
 467  * instructions, or extra NOP delays will have to be added due to register
 468  * allocation choices.
 469  */
 470 static uint32_t
 471 latency_between(struct schedule_node *before, struct schedule_node *after)
 472 {
 473         if ((before->inst->op == QOP_TEX_S ||
 474              before->inst->op == QOP_TEX_DIRECT) &&
 475             after->inst->op == QOP_TEX_RESULT)
 476                 return 100;
 477
 478         return 1;
 479 }
 480
 481 /** Recursive computation of the delay member of a node. */
 482 static void
 483 compute_delay(struct schedule_node *n)
 484 {
 485         if (!n->child_count) {
 486                 /* The color read needs to be scheduled late, to avoid locking
 487                  * the scoreboard early.  This is our best tool for
 488                  * encouraging that.  The other scoreboard locking ops will
 489                  * have this happen by default, since they are generally the
 490                  * DAG heads or close to them.
 491                  */
 492                 if (n->inst->op == QOP_TLB_COLOR_READ)
 493                         n->delay = 1000;
 494                 else
 495                         n->delay = 1;
 496         } else {
 497                 for (int i = 0; i < n->child_count; i++) {
 498                         if (!n->children[i]->delay)
 499                                 compute_delay(n->children[i]);
 500                         n->delay = MAX2(n->delay,
 501                                         n->children[i]->delay +
 502                                         latency_between(n, n->children[i]));
 503                 }
 504         }
 505 }
 506
 507 static void
 508 schedule_instructions(struct vc4_compile *c, struct schedule_state *state)
 509 {
 510         if (debug) {
 511                 fprintf(stderr, "initial deps:\n");
 512                 dump_state(c, state);
 513         }
 514
 515         /* Remove non-DAG heads from the list. */
 516         list_for_each_entry_safe(struct schedule_node, n,
 517                                  &state->worklist, link) {
 518                 if (n->parent_count != 0)
 519                         list_del(&n->link);
 520         }
 521
 522         state->time = 0;
 523         while (!list_empty(&state->worklist)) {
 524                 struct schedule_node *chosen = choose_instruction(state);
 525                 struct qinst *inst = chosen->inst;
 526
 527                 if (debug) {
 528                         fprintf(stderr, "current list:\n");
 529                         dump_state(c, state);
 530                         fprintf(stderr, "chose: ");
 531                         qir_dump_inst(c, inst);
 532                         fprintf(stderr, " (%d cost)\n",
 533                                 get_register_pressure_cost(state, inst));
 534                 }
 535
 536                 state->time = MAX2(state->time, chosen->unblocked_time);
 537
 538                 /* Schedule this instruction back onto the QIR list. */
 539                 list_del(&chosen->link);
 540                 list_add(&inst->link, &c->instructions);
 541
 542                 /* Now that we've scheduled a new instruction, some of its
 543                  * children can be promoted to the list of instructions ready to
 544                  * be scheduled.  Update the children's unblocked time for this
 545                  * DAG edge as we do so.
 546                  */
 547                 for (int i = chosen->child_count - 1; i >= 0; i--) {
 548                         struct schedule_node *child = chosen->children[i];
 549
 550                         child->unblocked_time = MAX2(child->unblocked_time,
 551                                                      state->time +
 552                                                      latency_between(chosen,
 553                                                                      child));
 554                         child->parent_count--;
 555                         if (child->parent_count == 0)
 556                                 list_add(&child->link, &state->worklist);
 557                 }
 558
 559                 /* Update our tracking of register pressure. */
 560                 for (int i = 0; i < qir_get_op_nsrc(inst->op); i++) {
 561                         if (inst->src[i].file == QFILE_TEMP)
 562                                 BITSET_SET(state->temp_live, inst->src[i].index);
 563                 }
 564                 if (inst->dst.file == QFILE_TEMP) {
 565                         state->temp_writes[inst->dst.index]--;
 566                         if (state->temp_writes[inst->dst.index] == 0)
 567                                 BITSET_CLEAR(state->temp_live, inst->dst.index);
 568                 }
 569
 570                 state->time++;
 571         }
 572 }
 573
 574 void
 575 qir_schedule_instructions(struct vc4_compile *c)
 576 {
 577         void *mem_ctx = ralloc_context(NULL);
 578         struct schedule_state state = { 0 };
 579
 580         if (debug) {
 581                 fprintf(stderr, "Pre-schedule instructions\n");
 582                 qir_dump(c);
 583         }
 584
 585         state.temp_writes = rzalloc_array(mem_ctx, uint32_t, c->num_temps);
 586         state.temp_live = rzalloc_array(mem_ctx, BITSET_WORD,
 587                                         BITSET_WORDS(c->num_temps));
 588         list_inithead(&state.worklist);
 589
 590         /* Wrap each instruction in a scheduler structure. */
 591         list_for_each_entry_safe(struct qinst, inst, &c->instructions, link) {
 592                 struct schedule_node *n = rzalloc(mem_ctx, struct schedule_node);
 593
 594                 n->inst = inst;
 595                 list_del(&inst->link);
 596                 list_addtail(&n->link, &state.worklist);
 597
 598                 if (inst->dst.file == QFILE_TEMP)
 599                         state.temp_writes[inst->dst.index]++;
 600         }
 601
 602         /* Dependencies tracked top-to-bottom. */
 603         calculate_forward_deps(c, mem_ctx, &state.worklist);
 604         /* Dependencies tracked bottom-to-top. */
 605         calculate_reverse_deps(c, mem_ctx, &state.worklist);
 606
 607         list_for_each_entry(struct schedule_node, n, &state.worklist, link)
 608                 compute_delay(n);
 609
 610         schedule_instructions(c, &state);
 611
 612         if (debug) {
 613                 fprintf(stderr, "Post-schedule instructions\n");
 614                 qir_dump(c);
 615         }
 616
 617         ralloc_free(mem_ctx);
 618 }