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         default:
 240                 break;
 241         }
 242
 243         if (inst->dst.file == QFILE_VPM)
 244                 add_write_dep(dir, &state->last_vpm_write, n);
 245         else if (inst->dst.file == QFILE_TEMP)
 246                 add_write_dep(dir, &state->last_temp_write[inst->dst.index], n);
 247
 248         if (qir_depends_on_flags(inst))
 249                 add_dep(dir, state->last_sf, n);
 250
 251         if (inst->sf)
 252                 add_write_dep(dir, &state->last_sf, n);
 253 }
 254
 255 static void
 256 calculate_forward_deps(struct vc4_compile *c, void *mem_ctx,
 257                        struct list_head *schedule_list)
 258 {
 259         struct schedule_setup_state state;
 260
 261         memset(&state, 0, sizeof(state));
 262         state.last_temp_write = rzalloc_array(mem_ctx, struct schedule_node *,
 263                                               c->num_temps);
 264         state.dir = F;
 265
 266         list_for_each_entry(struct schedule_node, n, schedule_list, link) {
 267                 struct qinst *inst = n->inst;
 268
 269                 calculate_deps(&state, n);
 270
 271                 switch (inst->op) {
 272                 case QOP_TEX_S:
 273                 case QOP_TEX_T:
 274                 case QOP_TEX_R:
 275                 case QOP_TEX_B:
 276                 case QOP_TEX_DIRECT:
 277                         /* If the texture coordinate fifo is full,
 278                          * block this on the last QOP_TEX_RESULT.
 279                          */
 280                         if (state.tfreq_count == 8) {
 281                                 block_until_tex_result(&state, n);
 282                         }
 283
 284                         /* If the texture result fifo is full, block
 285                          * adding any more to it until the last
 286                          * QOP_TEX_RESULT.
 287                          */
 288                         if (inst->op == QOP_TEX_S ||
 289                             inst->op == QOP_TEX_DIRECT) {
 290                                 if (state.tfrcv_count == 4)
 291                                         block_until_tex_result(&state, n);
 292                                 state.tfrcv_count++;
 293                         }
 294
 295                         state.tex_fifo[state.tex_fifo_pos].coords++;
 296                         state.tfreq_count++;
 297                         break;
 298
 299                 case QOP_TEX_RESULT:
 300                         /* Results have to be fetched after the
 301                          * coordinate setup.  Note that we're assuming
 302                          * here that our input shader has the texture
 303                          * coord setup and result fetch in order,
 304                          * which is true initially but not of our
 305                          * instruction stream after this pass.
 306                          */
 307                         add_dep(state.dir, state.last_tex_coord, n);
 308
 309                         state.tex_fifo[state.tex_fifo_pos].node = n;
 310
 311                         state.tex_fifo_pos++;
 312                         memset(&state.tex_fifo[state.tex_fifo_pos], 0,
 313                                sizeof(state.tex_fifo[0]));
 314                         break;
 315                 default:
 316                         assert(!qir_is_tex(inst));
 317                         break;
 318                 }
 319         }
 320 }
 321
 322 static void
 323 calculate_reverse_deps(struct vc4_compile *c, void *mem_ctx,
 324                        struct list_head *schedule_list)
 325 {
 326         struct schedule_setup_state state;
 327
 328         memset(&state, 0, sizeof(state));
 329         state.dir = R;
 330         state.last_temp_write = rzalloc_array(mem_ctx, struct schedule_node *,
 331                                               c->num_temps);
 332
 333         list_for_each_entry_rev(struct schedule_node, n, schedule_list, link) {
 334                 calculate_deps(&state, n);
 335         }
 336 }
 337
 338 static int
 339 get_register_pressure_cost(struct schedule_state *state, struct qinst *inst)
 340 {
 341         int cost = 0;
 342
 343         if (inst->dst.file == QFILE_TEMP &&
 344             state->temp_writes[inst->dst.index] == 1)
 345                 cost--;
 346
 347         for (int i = 0; i < qir_get_op_nsrc(inst->op); i++) {
 348                 if (inst->src[i].file == QFILE_TEMP &&
 349                     !BITSET_TEST(state->temp_live, inst->src[i].index)) {
 350                         cost++;
 351                 }
 352         }
 353
 354         return cost;
 355 }
 356
 357 static bool
 358 locks_scoreboard(struct qinst *inst)
 359 {
 360         switch (inst->op) {
 361         case QOP_TLB_Z_WRITE:
 362         case QOP_TLB_COLOR_WRITE:
 363         case QOP_TLB_COLOR_WRITE_MS:
 364         case QOP_TLB_COLOR_READ:
 365                 return true;
 366         default:
 367                 return false;
 368         }
 369 }
 370
 371 static struct schedule_node *
 372 choose_instruction(struct schedule_state *state)
 373 {
 374         struct schedule_node *chosen = NULL;
 375
 376         list_for_each_entry(struct schedule_node, n, &state->worklist, link) {
 377                 if (!chosen) {
 378                         chosen = n;
 379                         continue;
 380                 }
 381
 382                 /* Prefer scheduling things that lock the scoreboard, so that
 383                  * they appear late in the program and we get more parallelism
 384                  * between shaders on multiple QPUs hitting the same fragment.
 385                  */
 386                 if (locks_scoreboard(n->inst) &&
 387                     !locks_scoreboard(chosen->inst)) {
 388                         chosen = n;
 389                         continue;
 390                 } else if (!locks_scoreboard(n->inst) &&
 391                            locks_scoreboard(chosen->inst)) {
 392                         continue;
 393                 }
 394
 395                 /* If we would block on the previously chosen node, but would
 396                  * block less on this one, then then prefer it.
 397                  */
 398                 if (chosen->unblocked_time > state->time &&
 399                     n->unblocked_time < chosen->unblocked_time) {
 400                         chosen = n;
 401                         continue;
 402                 } else if (n->unblocked_time > state->time &&
 403                            n->unblocked_time > chosen->unblocked_time) {
 404                         continue;
 405                 }
 406
 407                 /* If we can definitely reduce register pressure, do so
 408                  * immediately.
 409                  */
 410                 int register_pressure_cost =
 411                         get_register_pressure_cost(state, n->inst);
 412                 int chosen_register_pressure_cost =
 413                         get_register_pressure_cost(state, chosen->inst);
 414
 415                 if (register_pressure_cost < chosen_register_pressure_cost) {
 416                         chosen = n;
 417                         continue;
 418                 } else if (register_pressure_cost >
 419                            chosen_register_pressure_cost) {
 420                         continue;
 421                 }
 422
 423                 /* Otherwise, prefer instructions with the deepest chain to
 424                  * the end of the program.  This avoids the problem of
 425                  * "everything generates a temp, nothing finishes freeing one,
 426                  * guess I'll just keep emitting varying mul/adds".
 427                  */
 428                 if (n->delay > chosen->delay) {
 429                         chosen = n;
 430                         continue;
 431                 } else if (n->delay < chosen->delay) {
 432                         continue;
 433                 }
 434         }
 435
 436         return chosen;
 437 }
 438
 439 static void
 440 dump_state(struct vc4_compile *c, struct schedule_state *state)
 441 {
 442         uint32_t i = 0;
 443         list_for_each_entry(struct schedule_node, n, &state->worklist, link) {
 444                 fprintf(stderr, "%3d: ", i++);
 445                 qir_dump_inst(c, n->inst);
 446                 fprintf(stderr, " (%d cost)\n",
 447                         get_register_pressure_cost(state, n->inst));
 448
 449                 for (int i = 0; i < n->child_count; i++) {
 450                         struct schedule_node *child = n->children[i];
 451                         fprintf(stderr, "   - ");
 452                         qir_dump_inst(c, child->inst);
 453                         fprintf(stderr, " (%d parents)\n", child->parent_count);
 454                 }
 455         }
 456 }
 457
 458 /* Estimate of how many instructions we should schedule between operations.
 459  *
 460  * These aren't in real cycle counts, because we're just estimating cycle
 461  * times anyway.  QIR instructions will get paired up when turned into QPU
 462  * instructions, or extra NOP delays will have to be added due to register
 463  * allocation choices.
 464  */
 465 static uint32_t
 466 latency_between(struct schedule_node *before, struct schedule_node *after)
 467 {
 468         if ((before->inst->op == QOP_TEX_S ||
 469              before->inst->op == QOP_TEX_DIRECT) &&
 470             after->inst->op == QOP_TEX_RESULT)
 471                 return 100;
 472
 473         return 1;
 474 }
 475
 476 /** Recursive computation of the delay member of a node. */
 477 static void
 478 compute_delay(struct schedule_node *n)
 479 {
 480         if (!n->child_count) {
 481                 /* The color read needs to be scheduled late, to avoid locking
 482                  * the scoreboard early.  This is our best tool for
 483                  * encouraging that.  The other scoreboard locking ops will
 484                  * have this happen by default, since they are generally the
 485                  * DAG heads or close to them.
 486                  */
 487                 if (n->inst->op == QOP_TLB_COLOR_READ)
 488                         n->delay = 1000;
 489                 else
 490                         n->delay = 1;
 491         } else {
 492                 for (int i = 0; i < n->child_count; i++) {
 493                         if (!n->children[i]->delay)
 494                                 compute_delay(n->children[i]);
 495                         n->delay = MAX2(n->delay,
 496                                         n->children[i]->delay +
 497                                         latency_between(n, n->children[i]));
 498                 }
 499         }
 500 }
 501
 502 static void
 503 schedule_instructions(struct vc4_compile *c, struct schedule_state *state)
 504 {
 505         if (debug) {
 506                 fprintf(stderr, "initial deps:\n");
 507                 dump_state(c, state);
 508         }
 509
 510         /* Remove non-DAG heads from the list. */
 511         list_for_each_entry_safe(struct schedule_node, n,
 512                                  &state->worklist, link) {
 513                 if (n->parent_count != 0)
 514                         list_del(&n->link);
 515         }
 516
 517         state->time = 0;
 518         while (!list_empty(&state->worklist)) {
 519                 struct schedule_node *chosen = choose_instruction(state);
 520                 struct qinst *inst = chosen->inst;
 521
 522                 if (debug) {
 523                         fprintf(stderr, "current list:\n");
 524                         dump_state(c, state);
 525                         fprintf(stderr, "chose: ");
 526                         qir_dump_inst(c, inst);
 527                         fprintf(stderr, " (%d cost)\n",
 528                                 get_register_pressure_cost(state, inst));
 529                 }
 530
 531                 state->time = MAX2(state->time, chosen->unblocked_time);
 532
 533                 /* Schedule this instruction back onto the QIR list. */
 534                 list_del(&chosen->link);
 535                 list_add(&inst->link, &c->instructions);
 536
 537                 /* Now that we've scheduled a new instruction, some of its
 538                  * children can be promoted to the list of instructions ready to
 539                  * be scheduled.  Update the children's unblocked time for this
 540                  * DAG edge as we do so.
 541                  */
 542                 for (int i = chosen->child_count - 1; i >= 0; i--) {
 543                         struct schedule_node *child = chosen->children[i];
 544
 545                         child->unblocked_time = MAX2(child->unblocked_time,
 546                                                      state->time +
 547                                                      latency_between(chosen,
 548                                                                      child));
 549                         child->parent_count--;
 550                         if (child->parent_count == 0)
 551                                 list_add(&child->link, &state->worklist);
 552                 }
 553
 554                 /* Update our tracking of register pressure. */
 555                 for (int i = 0; i < qir_get_op_nsrc(inst->op); i++) {
 556                         if (inst->src[i].file == QFILE_TEMP)
 557                                 BITSET_SET(state->temp_live, inst->src[i].index);
 558                 }
 559                 if (inst->dst.file == QFILE_TEMP) {
 560                         state->temp_writes[inst->dst.index]--;
 561                         if (state->temp_writes[inst->dst.index] == 0)
 562                                 BITSET_CLEAR(state->temp_live, inst->dst.index);
 563                 }
 564
 565                 state->time++;
 566         }
 567 }
 568
 569 void
 570 qir_schedule_instructions(struct vc4_compile *c)
 571 {
 572         void *mem_ctx = ralloc_context(NULL);
 573         struct schedule_state state = { { 0 } };
 574
 575         if (debug) {
 576                 fprintf(stderr, "Pre-schedule instructions\n");
 577                 qir_dump(c);
 578         }
 579
 580         state.temp_writes = rzalloc_array(mem_ctx, uint32_t, c->num_temps);
 581         state.temp_live = rzalloc_array(mem_ctx, BITSET_WORD,
 582                                         BITSET_WORDS(c->num_temps));
 583         list_inithead(&state.worklist);
 584
 585         /* Wrap each instruction in a scheduler structure. */
 586         list_for_each_entry_safe(struct qinst, inst, &c->instructions, link) {
 587                 struct schedule_node *n = rzalloc(mem_ctx, struct schedule_node);
 588
 589                 n->inst = inst;
 590                 list_del(&inst->link);
 591                 list_addtail(&n->link, &state.worklist);
 592
 593                 if (inst->dst.file == QFILE_TEMP)
 594                         state.temp_writes[inst->dst.index]++;
 595         }
 596
 597         /* Dependencies tracked top-to-bottom. */
 598         calculate_forward_deps(c, mem_ctx, &state.worklist);
 599         /* Dependencies tracked bottom-to-top. */
 600         calculate_reverse_deps(c, mem_ctx, &state.worklist);
 601
 602         list_for_each_entry(struct schedule_node, n, &state.worklist, link)
 603                 compute_delay(n);
 604
 605         schedule_instructions(c, &state);
 606
 607         if (debug) {
 608                 fprintf(stderr, "Post-schedule instructions\n");
 609                 qir_dump(c);
 610         }
 611
 612         ralloc_free(mem_ctx);
 613 }