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