src/panfrost/midgard/midgard_schedule.c

   1 /*
   2  * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23
  24 #include "compiler.h"
  25 #include "midgard_ops.h"
  26 #include "util/u_memory.h"
  27 #include "util/register_allocate.h"
  28
  29 /* Create a mask of accessed components from a swizzle to figure out vector
  30  * dependencies */
  31
  32 static unsigned
  33 swizzle_to_access_mask(unsigned swizzle)
  34 {
  35         unsigned component_mask = 0;
  36
  37         for (int i = 0; i < 4; ++i) {
  38                 unsigned c = (swizzle >> (2 * i)) & 3;
  39                 component_mask |= (1 << c);
  40         }
  41
  42         return component_mask;
  43 }
  44
  45 /* Does the mask cover more than a scalar? */
  46
  47 static bool
  48 is_single_component_mask(unsigned mask)
  49 {
  50         int components = 0;
  51
  52         for (int c = 0; c < 8; ++c) {
  53                 if (mask & (1 << c))
  54                         components++;
  55         }
  56
  57         return components == 1;
  58 }
  59
  60 /* Checks for an SSA data hazard between two adjacent instructions, keeping in
  61  * mind that we are a vector architecture and we can write to different
  62  * components simultaneously */
  63
  64 static bool
  65 can_run_concurrent_ssa(midgard_instruction *first, midgard_instruction *second)
  66 {
  67         /* Each instruction reads some registers and writes to a register. See
  68          * where the first writes */
  69
  70         /* Figure out where exactly we wrote to */
  71         int source = first->ssa_args.dest;
  72         int source_mask = first->mask;
  73
  74         /* As long as the second doesn't read from the first, we're okay */
  75         if (second->ssa_args.src0 == source) {
  76                 if (first->type == TAG_ALU_4) {
  77                         /* Figure out which components we just read from */
  78
  79                         int q = second->alu.src1;
  80                         midgard_vector_alu_src *m = (midgard_vector_alu_src *) &q;
  81
  82                         /* Check if there are components in common, and fail if so */
  83                         if (swizzle_to_access_mask(m->swizzle) & source_mask)
  84                                 return false;
  85                 } else
  86                         return false;
  87
  88         }
  89
  90         if (second->ssa_args.src1 == source)
  91                 return false;
  92
  93         /* Otherwise, it's safe in that regard. Another data hazard is both
  94          * writing to the same place, of course */
  95
  96         if (second->ssa_args.dest == source) {
  97                 /* ...but only if the components overlap */
  98
  99                 if (second->mask & source_mask)
 100                         return false;
 101         }
 102
 103         /* ...That's it */
 104         return true;
 105 }
 106
 107 static bool
 108 midgard_has_hazard(
 109         midgard_instruction **segment, unsigned segment_size,
 110         midgard_instruction *ains)
 111 {
 112         for (int s = 0; s < segment_size; ++s)
 113                 if (!can_run_concurrent_ssa(segment[s], ains))
 114                         return true;
 115
 116         return false;
 117
 118
 119 }
 120
 121 /* Fragment writeout (of r0) is allowed when:
 122  *
 123  *  - All components of r0 are written in the bundle
 124  *  - No components of r0 are written in VLUT
 125  *  - Non-pipelined dependencies of r0 are not written in the bundle
 126  *
 127  * This function checks if these requirements are satisfied given the content
 128  * of a scheduled bundle.
 129  */
 130
 131 static bool
 132 can_writeout_fragment(compiler_context *ctx, midgard_instruction **bundle, unsigned count, unsigned node_count)
 133 {
 134         /* First scan for which components of r0 are written out. Initially
 135          * none are written */
 136
 137         uint8_t r0_written_mask = 0x0;
 138
 139         /* Simultaneously we scan for the set of dependencies */
 140         BITSET_WORD *dependencies = calloc(sizeof(BITSET_WORD), BITSET_WORDS(node_count));
 141
 142         for (unsigned i = 0; i < count; ++i) {
 143                 midgard_instruction *ins = bundle[i];
 144
 145                 if (ins->ssa_args.dest != SSA_FIXED_REGISTER(0))
 146                         continue;
 147
 148                 /* Record written out mask */
 149                 r0_written_mask |= ins->mask;
 150
 151                 /* Record dependencies, but only if they won't become pipeline
 152                  * registers. We know we can't be live after this, because
 153                  * we're writeout at the very end of the shader. So check if
 154                  * they were written before us. */
 155
 156                 unsigned src0 = ins->ssa_args.src0;
 157                 unsigned src1 = ins->ssa_args.src1;
 158
 159                 if (!mir_is_written_before(ctx, bundle[0], src0))
 160                         src0 = -1;
 161
 162                 if (!mir_is_written_before(ctx, bundle[0], src1))
 163                         src1 = -1;
 164
 165                 if ((src0 > 0) && (src0 < node_count))
 166                         BITSET_SET(dependencies, src0);
 167
 168                 if ((src1 > 0) && (src1 < node_count))
 169                         BITSET_SET(dependencies, src1);
 170
 171                 /* Requirement 2 */
 172                 if (ins->unit == UNIT_VLUT)
 173                         return false;
 174         }
 175
 176         /* Requirement 1 */
 177         if ((r0_written_mask & 0xF) != 0xF)
 178                 return false;
 179
 180         /* Requirement 3 */
 181
 182         for (unsigned i = 0; i < count; ++i) {
 183                 unsigned dest = bundle[i]->ssa_args.dest;
 184
 185                 if (dest < node_count && BITSET_TEST(dependencies, dest))
 186                         return false;
 187         }
 188
 189         /* Otherwise, we're good to go */
 190         return true;
 191 }
 192
 193 /* Schedules, but does not emit, a single basic block. After scheduling, the
 194  * final tag and size of the block are known, which are necessary for branching
 195  * */
 196
 197 static midgard_bundle
 198 schedule_bundle(compiler_context *ctx, midgard_block *block, midgard_instruction *ins, int *skip)
 199 {
 200         int instructions_emitted = 0, packed_idx = 0;
 201         midgard_bundle bundle = { 0 };
 202
 203         midgard_instruction *scheduled[5] = { NULL };
 204
 205         uint8_t tag = ins->type;
 206
 207         /* Default to the instruction's tag */
 208         bundle.tag = tag;
 209
 210         switch (ins->type) {
 211         case TAG_ALU_4: {
 212                 uint32_t control = 0;
 213                 size_t bytes_emitted = sizeof(control);
 214
 215                 /* TODO: Constant combining */
 216                 int index = 0, last_unit = 0;
 217
 218                 /* Previous instructions, for the purpose of parallelism */
 219                 midgard_instruction *segment[4] = {0};
 220                 int segment_size = 0;
 221
 222                 instructions_emitted = -1;
 223                 midgard_instruction *pins = ins;
 224
 225                 unsigned constant_count = 0;
 226
 227                 for (;;) {
 228                         midgard_instruction *ains = pins;
 229
 230                         /* Advance instruction pointer */
 231                         if (index) {
 232                                 ains = mir_next_op(pins);
 233                                 pins = ains;
 234                         }
 235
 236                         /* Out-of-work condition */
 237                         if ((struct list_head *) ains == &block->instructions)
 238                                 break;
 239
 240                         /* Ensure that the chain can continue */
 241                         if (ains->type != TAG_ALU_4) break;
 242
 243                         /* If there's already something in the bundle and we
 244                          * have weird scheduler constraints, break now */
 245                         if (ains->precede_break && index) break;
 246
 247                         /* According to the presentation "The ARM
 248                          * Mali-T880 Mobile GPU" from HotChips 27,
 249                          * there are two pipeline stages. Branching
 250                          * position determined experimentally. Lines
 251                          * are executed in parallel:
 252                          *
 253                          * [ VMUL ] [ SADD ]
 254                          * [ VADD ] [ SMUL ] [ LUT ] [ BRANCH ]
 255                          *
 256                          * Verify that there are no ordering dependencies here.
 257                          *
 258                          * TODO: Allow for parallelism!!!
 259                          */
 260
 261                         /* Pick a unit for it if it doesn't force a particular unit */
 262
 263                         int unit = ains->unit;
 264
 265                         if (!unit) {
 266                                 int op = ains->alu.op;
 267                                 int units = alu_opcode_props[op].props;
 268
 269                                 bool scalarable = units & UNITS_SCALAR;
 270                                 bool could_scalar = is_single_component_mask(ains->mask);
 271
 272                                 /* Only 16/32-bit can run on a scalar unit */
 273                                 could_scalar &= ains->alu.reg_mode != midgard_reg_mode_8;
 274                                 could_scalar &= ains->alu.reg_mode != midgard_reg_mode_64;
 275                                 could_scalar &= ains->alu.dest_override == midgard_dest_override_none;
 276
 277                                 if (ains->alu.reg_mode == midgard_reg_mode_16) {
 278                                         /* If we're running in 16-bit mode, we
 279                                          * can't have any 8-bit sources on the
 280                                          * scalar unit (since the scalar unit
 281                                          * doesn't understand 8-bit) */
 282
 283                                         midgard_vector_alu_src s1 =
 284                                                 vector_alu_from_unsigned(ains->alu.src1);
 285
 286                                         could_scalar &= !s1.half;
 287
 288                                         midgard_vector_alu_src s2 =
 289                                                 vector_alu_from_unsigned(ains->alu.src2);
 290
 291                                         could_scalar &= !s2.half;
 292                                 }
 293
 294                                 bool scalar = could_scalar && scalarable;
 295
 296                                 /* TODO: Check ahead-of-time for other scalar
 297                                  * hazards that otherwise get aborted out */
 298
 299                                 if (scalar)
 300                                         assert(units & UNITS_SCALAR);
 301
 302                                 if (!scalar) {
 303                                         if (last_unit >= UNIT_VADD) {
 304                                                 if (units & UNIT_VLUT)
 305                                                         unit = UNIT_VLUT;
 306                                                 else
 307                                                         break;
 308                                         } else {
 309                                                 if ((units & UNIT_VMUL) && last_unit < UNIT_VMUL)
 310                                                         unit = UNIT_VMUL;
 311                                                 else if ((units & UNIT_VADD) && !(control & UNIT_VADD))
 312                                                         unit = UNIT_VADD;
 313                                                 else if (units & UNIT_VLUT)
 314                                                         unit = UNIT_VLUT;
 315                                                 else
 316                                                         break;
 317                                         }
 318                                 } else {
 319                                         if (last_unit >= UNIT_VADD) {
 320                                                 if ((units & UNIT_SMUL) && !(control & UNIT_SMUL))
 321                                                         unit = UNIT_SMUL;
 322                                                 else if (units & UNIT_VLUT)
 323                                                         unit = UNIT_VLUT;
 324                                                 else
 325                                                         break;
 326                                         } else {
 327                                                 if ((units & UNIT_VMUL) && (last_unit < UNIT_VMUL))
 328                                                         unit = UNIT_VMUL;
 329                                                 else if ((units & UNIT_SADD) && !(control & UNIT_SADD) && !midgard_has_hazard(segment, segment_size, ains))
 330                                                         unit = UNIT_SADD;
 331                                                 else if (units & UNIT_VADD)
 332                                                         unit = UNIT_VADD;
 333                                                 else if (units & UNIT_SMUL)
 334                                                         unit = UNIT_SMUL;
 335                                                 else if (units & UNIT_VLUT)
 336                                                         unit = UNIT_VLUT;
 337                                                 else
 338                                                         break;
 339                                         }
 340                                 }
 341
 342                                 assert(unit & units);
 343                         }
 344
 345                         /* Late unit check, this time for encoding (not parallelism) */
 346                         if (unit <= last_unit) break;
 347
 348                         /* Clear the segment */
 349                         if (last_unit < UNIT_VADD && unit >= UNIT_VADD)
 350                                 segment_size = 0;
 351
 352                         if (midgard_has_hazard(segment, segment_size, ains))
 353                                 break;
 354
 355                         /* We're good to go -- emit the instruction */
 356                         ains->unit = unit;
 357
 358                         segment[segment_size++] = ains;
 359
 360                         /* We try to reuse constants if possible, by adjusting
 361                          * the swizzle */
 362
 363                         if (ains->has_blend_constant) {
 364                                 /* Everything conflicts with the blend constant */
 365                                 if (bundle.has_embedded_constants)
 366                                         break;
 367
 368                                 bundle.has_blend_constant = 1;
 369                                 bundle.has_embedded_constants = 1;
 370                         } else if (ains->has_constants && ains->alu.reg_mode == midgard_reg_mode_16) {
 371                                 /* TODO: DRY with the analysis pass */
 372
 373                                 if (bundle.has_blend_constant)
 374                                         break;
 375
 376                                 if (constant_count)
 377                                         break;
 378
 379                                 /* TODO: Fix packing XXX */
 380                                 uint16_t *bundles = (uint16_t *) bundle.constants;
 381                                 uint32_t *constants = (uint32_t *) ains->constants;
 382
 383                                 /* Copy them wholesale */
 384                                 for (unsigned i = 0; i < 4; ++i)
 385                                         bundles[i] = constants[i];
 386
 387                                 bundle.has_embedded_constants = true;
 388                                 constant_count = 4;
 389                         } else if (ains->has_constants) {
 390                                 /* By definition, blend constants conflict with
 391                                  * everything, so if there are already
 392                                  * constants we break the bundle *now* */
 393
 394                                 if (bundle.has_blend_constant)
 395                                         break;
 396
 397                                 /* For anything but blend constants, we can do
 398                                  * proper analysis, however */
 399
 400                                 /* TODO: Mask by which are used */
 401                                 uint32_t *constants = (uint32_t *) ains->constants;
 402                                 uint32_t *bundles = (uint32_t *) bundle.constants;
 403
 404                                 uint32_t indices[4] = { 0 };
 405                                 bool break_bundle = false;
 406
 407                                 for (unsigned i = 0; i < 4; ++i) {
 408                                         uint32_t cons = constants[i];
 409                                         bool constant_found = false;
 410
 411                                         /* Search for the constant */
 412                                         for (unsigned j = 0; j < constant_count; ++j) {
 413                                                 if (bundles[j] != cons)
 414                                                         continue;
 415
 416                                                 /* We found it, reuse */
 417                                                 indices[i] = j;
 418                                                 constant_found = true;
 419                                                 break;
 420                                         }
 421
 422                                         if (constant_found)
 423                                                 continue;
 424
 425                                         /* We didn't find it, so allocate it */
 426                                         unsigned idx = constant_count++;
 427
 428                                         if (idx >= 4) {
 429                                                 /* Uh-oh, out of space */
 430                                                 break_bundle = true;
 431                                                 break;
 432                                         }
 433
 434                                         /* We have space, copy it in! */
 435                                         bundles[idx] = cons;
 436                                         indices[i] = idx;
 437                                 }
 438
 439                                 if (break_bundle)
 440                                         break;
 441
 442                                 /* Cool, we have it in. So use indices as a
 443                                  * swizzle */
 444
 445                                 unsigned swizzle = SWIZZLE_FROM_ARRAY(indices);
 446                                 unsigned r_constant = SSA_FIXED_REGISTER(REGISTER_CONSTANT);
 447
 448                                 if (ains->ssa_args.src0 == r_constant)
 449                                         ains->alu.src1 = vector_alu_apply_swizzle(ains->alu.src1, swizzle);
 450
 451                                 if (ains->ssa_args.src1 == r_constant)
 452                                         ains->alu.src2 = vector_alu_apply_swizzle(ains->alu.src2, swizzle);
 453
 454                                 bundle.has_embedded_constants = true;
 455                         }
 456
 457                         if (ains->unit & UNITS_ANY_VECTOR) {
 458                                 bytes_emitted += sizeof(midgard_reg_info);
 459                                 bytes_emitted += sizeof(midgard_vector_alu);
 460                         } else if (ains->compact_branch) {
 461                                 /* All of r0 has to be written out along with
 462                                  * the branch writeout */
 463
 464                                 if (ains->writeout && !can_writeout_fragment(ctx, scheduled, index, ctx->temp_count)) {
 465                                         /* We only work on full moves
 466                                          * at the beginning. We could
 467                                          * probably do better */
 468                                         if (index != 0)
 469                                                 break;
 470
 471                                         /* Inject a move */
 472                                         midgard_instruction ins = v_mov(0, blank_alu_src, SSA_FIXED_REGISTER(0));
 473                                         ins.unit = UNIT_VMUL;
 474                                         control |= ins.unit;
 475
 476                                         /* TODO don't leak */
 477                                         midgard_instruction *move =
 478                                                 mem_dup(&ins, sizeof(midgard_instruction));
 479                                         bytes_emitted += sizeof(midgard_reg_info);
 480                                         bytes_emitted += sizeof(midgard_vector_alu);
 481                                         bundle.instructions[packed_idx++] = move;
 482                                 }
 483
 484                                 if (ains->unit == ALU_ENAB_BRANCH) {
 485                                         bytes_emitted += sizeof(midgard_branch_extended);
 486                                 } else {
 487                                         bytes_emitted += sizeof(ains->br_compact);
 488                                 }
 489                         } else {
 490                                 bytes_emitted += sizeof(midgard_reg_info);
 491                                 bytes_emitted += sizeof(midgard_scalar_alu);
 492                         }
 493
 494                         /* Defer marking until after writing to allow for break */
 495                         scheduled[index] = ains;
 496                         control |= ains->unit;
 497                         last_unit = ains->unit;
 498                         ++instructions_emitted;
 499                         ++index;
 500                 }
 501
 502                 int padding = 0;
 503
 504                 /* Pad ALU op to nearest word */
 505
 506                 if (bytes_emitted & 15) {
 507                         padding = 16 - (bytes_emitted & 15);
 508                         bytes_emitted += padding;
 509                 }
 510
 511                 /* Constants must always be quadwords */
 512                 if (bundle.has_embedded_constants)
 513                         bytes_emitted += 16;
 514
 515                 /* Size ALU instruction for tag */
 516                 bundle.tag = (TAG_ALU_4) + (bytes_emitted / 16) - 1;
 517                 bundle.padding = padding;
 518                 bundle.control = bundle.tag | control;
 519
 520                 break;
 521         }
 522
 523         case TAG_LOAD_STORE_4: {
 524                 /* Load store instructions have two words at once. If
 525                  * we only have one queued up, we need to NOP pad.
 526                  * Otherwise, we store both in succession to save space
 527                  * and cycles -- letting them go in parallel -- skip
 528                  * the next. The usefulness of this optimisation is
 529                  * greatly dependent on the quality of the instruction
 530                  * scheduler.
 531                  */
 532
 533                 midgard_instruction *next_op = mir_next_op(ins);
 534
 535                 if ((struct list_head *) next_op != &block->instructions && next_op->type == TAG_LOAD_STORE_4) {
 536                         /* TODO: Concurrency check */
 537                         instructions_emitted++;
 538                 }
 539
 540                 break;
 541         }
 542
 543         case TAG_TEXTURE_4: {
 544                 /* Which tag we use depends on the shader stage */
 545                 bool in_frag = ctx->stage == MESA_SHADER_FRAGMENT;
 546                 bundle.tag = in_frag ? TAG_TEXTURE_4 : TAG_TEXTURE_4_VTX;
 547                 break;
 548         }
 549
 550         default:
 551                 unreachable("Unknown tag");
 552                 break;
 553         }
 554
 555         /* Copy the instructions into the bundle */
 556         bundle.instruction_count = instructions_emitted + 1 + packed_idx;
 557
 558         midgard_instruction *uins = ins;
 559         for (; packed_idx < bundle.instruction_count; ++packed_idx) {
 560                 bundle.instructions[packed_idx] = uins;
 561                 uins = mir_next_op(uins);
 562         }
 563
 564         *skip = instructions_emitted;
 565
 566         return bundle;
 567 }
 568
 569 /* Schedule a single block by iterating its instruction to create bundles.
 570  * While we go, tally about the bundle sizes to compute the block size. */
 571
 572 static void
 573 schedule_block(compiler_context *ctx, midgard_block *block)
 574 {
 575         util_dynarray_init(&block->bundles, NULL);
 576
 577         block->quadword_count = 0;
 578
 579         mir_foreach_instr_in_block(block, ins) {
 580                 int skip;
 581                 midgard_bundle bundle = schedule_bundle(ctx, block, ins, &skip);
 582                 util_dynarray_append(&block->bundles, midgard_bundle, bundle);
 583
 584                 if (bundle.has_blend_constant) {
 585                         /* TODO: Multiblock? */
 586                         int quadwords_within_block = block->quadword_count + quadword_size(bundle.tag) - 1;
 587                         ctx->blend_constant_offset = quadwords_within_block * 0x10;
 588                 }
 589
 590                 while(skip--)
 591                         ins = mir_next_op(ins);
 592
 593                 block->quadword_count += quadword_size(bundle.tag);
 594         }
 595
 596         block->is_scheduled = true;
 597 }
 598
 599 /* The following passes reorder MIR instructions to enable better scheduling */
 600
 601 static void
 602 midgard_pair_load_store(compiler_context *ctx, midgard_block *block)
 603 {
 604         mir_foreach_instr_in_block_safe(block, ins) {
 605                 if (ins->type != TAG_LOAD_STORE_4) continue;
 606
 607                 /* We've found a load/store op. Check if next is also load/store. */
 608                 midgard_instruction *next_op = mir_next_op(ins);
 609                 if (&next_op->link != &block->instructions) {
 610                         if (next_op->type == TAG_LOAD_STORE_4) {
 611                                 /* If so, we're done since we're a pair */
 612                                 ins = mir_next_op(ins);
 613                                 continue;
 614                         }
 615
 616                         /* Maximum search distance to pair, to avoid register pressure disasters */
 617                         int search_distance = 8;
 618
 619                         /* Otherwise, we have an orphaned load/store -- search for another load */
 620                         mir_foreach_instr_in_block_from(block, c, mir_next_op(ins)) {
 621                                 /* Terminate search if necessary */
 622                                 if (!(search_distance--)) break;
 623
 624                                 if (c->type != TAG_LOAD_STORE_4) continue;
 625
 626                                 /* Stores cannot be reordered, since they have
 627                                  * dependencies. For the same reason, indirect
 628                                  * loads cannot be reordered as their index is
 629                                  * loaded in r27.w */
 630
 631                                 if (OP_IS_STORE(c->load_store.op)) continue;
 632
 633                                 /* It appears the 0x8 bit is set whenever a
 634                                  * load is direct, unset when it is indirect.
 635                                  * Skip indirect loads. */
 636
 637                                 if (!(c->load_store.arg_2 & 0x8)) continue;
 638
 639                                 /* We found one! Move it up to pair and remove it from the old location */
 640
 641                                 mir_insert_instruction_before(ins, *c);
 642                                 mir_remove_instruction(c);
 643
 644                                 break;
 645                         }
 646                 }
 647         }
 648 }
 649
 650 /* When we're 'squeezing down' the values in the IR, we maintain a hash
 651  * as such */
 652
 653 static unsigned
 654 find_or_allocate_temp(compiler_context *ctx, unsigned hash)
 655 {
 656         if ((hash < 0) || (hash >= SSA_FIXED_MINIMUM))
 657                 return hash;
 658
 659         unsigned temp = (uintptr_t) _mesa_hash_table_u64_search(
 660                                 ctx->hash_to_temp, hash + 1);
 661
 662         if (temp)
 663                 return temp - 1;
 664
 665         /* If no temp is find, allocate one */
 666         temp = ctx->temp_count++;
 667         ctx->max_hash = MAX2(ctx->max_hash, hash);
 668
 669         _mesa_hash_table_u64_insert(ctx->hash_to_temp,
 670                                     hash + 1, (void *) ((uintptr_t) temp + 1));
 671
 672         return temp;
 673 }
 674
 675 /* Reassigns numbering to get rid of gaps in the indices */
 676
 677 static void
 678 mir_squeeze_index(compiler_context *ctx)
 679 {
 680         /* Reset */
 681         ctx->temp_count = 0;
 682         /* TODO don't leak old hash_to_temp */
 683         ctx->hash_to_temp = _mesa_hash_table_u64_create(NULL);
 684
 685         mir_foreach_instr_global(ctx, ins) {
 686                 ins->ssa_args.dest = find_or_allocate_temp(ctx, ins->ssa_args.dest);
 687                 ins->ssa_args.src0 = find_or_allocate_temp(ctx, ins->ssa_args.src0);
 688                 ins->ssa_args.src1 = find_or_allocate_temp(ctx, ins->ssa_args.src1);
 689         }
 690 }
 691
 692 static midgard_instruction
 693 v_load_store_scratch(
 694                 unsigned srcdest,
 695                 unsigned index,
 696                 bool is_store,
 697                 unsigned mask)
 698 {
 699         /* We index by 32-bit vec4s */
 700         unsigned byte = (index * 4 * 4);
 701
 702         midgard_instruction ins = {
 703                 .type = TAG_LOAD_STORE_4,
 704                 .mask = mask,
 705                 .ssa_args = {
 706                         .dest = -1,
 707                         .src0 = -1,
 708                         .src1 = -1
 709                 },
 710                 .load_store = {
 711                         .op = is_store ? midgard_op_st_int4 : midgard_op_ld_int4,
 712                         .swizzle = SWIZZLE_XYZW,
 713
 714                         /* For register spilling - to thread local storage */
 715                         .arg_1 = 0xEA,
 716                         .arg_2 = 0x1E,
 717
 718                         /* Splattered across, TODO combine logically */
 719                         .varying_parameters = (byte & 0x1FF) << 1,
 720                         .address = (byte >> 9)
 721                 }
 722         };
 723
 724        if (is_store) {
 725                 /* r0 = r26, r1 = r27 */
 726                 assert(srcdest == SSA_FIXED_REGISTER(26) || srcdest == SSA_FIXED_REGISTER(27));
 727                 ins.ssa_args.src0 = (srcdest == SSA_FIXED_REGISTER(27)) ? SSA_FIXED_REGISTER(1) : SSA_FIXED_REGISTER(0);
 728         } else {
 729                 ins.ssa_args.dest = srcdest;
 730         }
 731
 732         return ins;
 733 }
 734
 735 void
 736 schedule_program(compiler_context *ctx)
 737 {
 738         struct ra_graph *g = NULL;
 739         bool spilled = false;
 740         int iter_count = 1000; /* max iterations */
 741
 742         /* Number of 128-bit slots in memory we've spilled into */
 743         unsigned spill_count = 0;
 744
 745         midgard_promote_uniforms(ctx, 8);
 746
 747         mir_foreach_block(ctx, block) {
 748                 midgard_pair_load_store(ctx, block);
 749         }
 750
 751         /* Must be lowered right before RA */
 752         mir_squeeze_index(ctx);
 753         mir_lower_special_reads(ctx);
 754
 755         /* Lowering can introduce some dead moves */
 756
 757         mir_foreach_block(ctx, block) {
 758                 midgard_opt_dead_move_eliminate(ctx, block);
 759         }
 760
 761         do {
 762                 /* If we spill, find the best spill node and spill it */
 763
 764                 unsigned spill_index = ctx->temp_count;
 765                 if (g && spilled) {
 766                         /* All nodes are equal in spill cost, but we can't
 767                          * spill nodes written to from an unspill */
 768
 769                         for (unsigned i = 0; i < ctx->temp_count; ++i) {
 770                                 ra_set_node_spill_cost(g, i, 1.0);
 771                         }
 772
 773                         mir_foreach_instr_global(ctx, ins) {
 774                                 if (ins->type != TAG_LOAD_STORE_4)  continue;
 775                                 if (ins->load_store.op != midgard_op_ld_int4) continue;
 776                                 if (ins->load_store.arg_1 != 0xEA) continue;
 777                                 if (ins->load_store.arg_2 != 0x1E) continue;
 778                                 ra_set_node_spill_cost(g, ins->ssa_args.dest, -1.0);
 779                         }
 780
 781                         int spill_node = ra_get_best_spill_node(g);
 782
 783                         if (spill_node < 0) {
 784                                 mir_print_shader(ctx);
 785                                 assert(0);
 786                         }
 787
 788                         /* Check the class. Work registers legitimately spill
 789                          * to TLS, but special registers just spill to work
 790                          * registers */
 791                         unsigned class = ra_get_node_class(g, spill_node);
 792                         bool is_special = (class >> 2) != REG_CLASS_WORK;
 793                         bool is_special_w = (class >> 2) == REG_CLASS_TEXW;
 794
 795                         /* Allocate TLS slot (maybe) */
 796                         unsigned spill_slot = !is_special ? spill_count++ : 0;
 797                         midgard_instruction *spill_move = NULL;
 798
 799                         /* For TLS, replace all stores to the spilled node. For
 800                          * special reads, just keep as-is; the class will be demoted
 801                          * implicitly. For special writes, spill to a work register */
 802
 803                         if (!is_special || is_special_w) {
 804                                 mir_foreach_instr_global_safe(ctx, ins) {
 805                                         if (ins->ssa_args.dest != spill_node) continue;
 806
 807                                         midgard_instruction st;
 808
 809                                         if (is_special_w) {
 810                                                 spill_slot = spill_index++;
 811                                                 st = v_mov(spill_node, blank_alu_src, spill_slot);
 812                                         } else {
 813                                                 ins->ssa_args.dest = SSA_FIXED_REGISTER(26);
 814                                                 st = v_load_store_scratch(ins->ssa_args.dest, spill_slot, true, ins->mask);
 815                                         }
 816
 817                                         spill_move = mir_insert_instruction_before(mir_next_op(ins), st);
 818
 819                                         if (!is_special)
 820                                                 ctx->spills++;
 821                                 }
 822                         }
 823
 824                         /* Insert a load from TLS before the first consecutive
 825                          * use of the node, rewriting to use spilled indices to
 826                          * break up the live range. Or, for special, insert a
 827                          * move. Ironically the latter *increases* register
 828                          * pressure, but the two uses of the spilling mechanism
 829                          * are somewhat orthogonal. (special spilling is to use
 830                          * work registers to back special registers; TLS
 831                          * spilling is to use memory to back work registers) */
 832
 833                         mir_foreach_block(ctx, block) {
 834
 835                         bool consecutive_skip = false;
 836                         unsigned consecutive_index = 0;
 837
 838                         mir_foreach_instr_in_block(block, ins) {
 839                                 /* We can't rewrite the move used to spill in the first place */
 840                                 if (ins == spill_move) continue;
 841
 842                                 if (!mir_has_arg(ins, spill_node)) {
 843                                         consecutive_skip = false;
 844                                         continue;
 845                                 }
 846
 847                                 if (consecutive_skip) {
 848                                         /* Rewrite */
 849                                         mir_rewrite_index_src_single(ins, spill_node, consecutive_index);
 850                                         continue;
 851                                 }
 852
 853                                 if (!is_special_w) {
 854                                         consecutive_index = ++spill_index;
 855
 856                                         midgard_instruction *before = ins;
 857
 858                                         /* For a csel, go back one more not to break up the bundle */
 859                                         if (ins->type == TAG_ALU_4 && OP_IS_CSEL(ins->alu.op))
 860                                                 before = mir_prev_op(before);
 861
 862                                         midgard_instruction st;
 863
 864                                         if (is_special) {
 865                                                 /* Move */
 866                                                 st = v_mov(spill_node, blank_alu_src, consecutive_index);
 867                                         } else {
 868                                                 /* TLS load */
 869                                                 st = v_load_store_scratch(consecutive_index, spill_slot, false, 0xF);
 870                                         }
 871
 872                                         mir_insert_instruction_before(before, st);
 873                                        // consecutive_skip = true;
 874                                 } else {
 875                                         /* Special writes already have their move spilled in */
 876                                         consecutive_index = spill_slot;
 877                                 }
 878
 879
 880                                 /* Rewrite to use */
 881                                 mir_rewrite_index_src_single(ins, spill_node, consecutive_index);
 882
 883                                 if (!is_special)
 884                                         ctx->fills++;
 885                         }
 886                         }
 887                 }
 888
 889                 mir_squeeze_index(ctx);
 890
 891                 g = NULL;
 892                 g = allocate_registers(ctx, &spilled);
 893         } while(spilled && ((iter_count--) > 0));
 894
 895         /* We can simplify a bit after RA */
 896
 897         mir_foreach_block(ctx, block) {
 898                 midgard_opt_post_move_eliminate(ctx, block, g);
 899         }
 900
 901         /* After RA finishes, we schedule all at once */
 902
 903         mir_foreach_block(ctx, block) {
 904                 schedule_block(ctx, block);
 905         }
 906
 907         /* Finally, we create pipeline registers as a peephole pass after
 908          * scheduling. This isn't totally optimal, since there are cases where
 909          * the usage of pipeline registers can eliminate spills, but it does
 910          * save some power */
 911
 912         mir_create_pipeline_registers(ctx);
 913
 914         if (iter_count <= 0) {
 915                 fprintf(stderr, "panfrost: Gave up allocating registers, rendering will be incomplete\n");
 916                 assert(0);
 917         }
 918
 919         /* Report spilling information. spill_count is in 128-bit slots (vec4 x
 920          * fp32), but tls_size is in bytes, so multiply by 16 */
 921
 922         ctx->tls_size = spill_count * 16;
 923
 924         install_registers(ctx, g);
 925 }