src/panfrost/midgard/midgard_ra.c

   1 /*
   2  * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
   3  * Copyright (C) 2019 Collabora, Ltd.
   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 FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "compiler.h"
  26 #include "midgard_ops.h"
  27 #include "util/u_math.h"
  28 #include "util/u_memory.h"
  29 #include "midgard_quirks.h"
  30
  31 struct phys_reg {
  32         /* Physical register: 0-31 */
  33         unsigned reg;
  34
  35         /* Byte offset into the physical register: 0-15 */
  36         unsigned offset;
  37
  38         /* Number of bytes in a component of this register */
  39         unsigned size;
  40 };
  41
  42 /* Shift up by reg_offset and horizontally by dst_offset. */
  43
  44 static void
  45 offset_swizzle(unsigned *swizzle, unsigned reg_offset, unsigned srcsize, unsigned dstsize, unsigned dst_offset)
  46 {
  47         unsigned out[MIR_VEC_COMPONENTS];
  48
  49         signed reg_comp = reg_offset / srcsize;
  50         signed dst_comp = dst_offset / dstsize;
  51
  52         unsigned max_component = (16 / srcsize) - 1;
  53
  54         assert(reg_comp * srcsize == reg_offset);
  55         assert(dst_comp * dstsize == dst_offset);
  56
  57         for (signed c = 0; c < MIR_VEC_COMPONENTS; ++c) {
  58                 signed comp = MAX2(c - dst_comp, 0);
  59                 out[c] = MIN2(swizzle[comp] + reg_comp, max_component);
  60         }
  61
  62         memcpy(swizzle, out, sizeof(out));
  63 }
  64
  65 /* Helper to return the default phys_reg for a given register */
  66
  67 static struct phys_reg
  68 default_phys_reg(int reg, unsigned size)
  69 {
  70         struct phys_reg r = {
  71                 .reg = reg,
  72                 .offset = 0,
  73                 .size = size
  74         };
  75
  76         return r;
  77 }
  78
  79 /* Determine which physical register, swizzle, and mask a virtual
  80  * register corresponds to */
  81
  82 static struct phys_reg
  83 index_to_reg(compiler_context *ctx, struct lcra_state *l, unsigned reg, unsigned size)
  84 {
  85         /* Check for special cases */
  86         if (reg == ~0)
  87                 return default_phys_reg(REGISTER_UNUSED, size);
  88         else if (reg >= SSA_FIXED_MINIMUM)
  89                 return default_phys_reg(SSA_REG_FROM_FIXED(reg), size);
  90         else if (!l)
  91                 return default_phys_reg(REGISTER_UNUSED, size);
  92
  93         struct phys_reg r = {
  94                 .reg = l->solutions[reg] / 16,
  95                 .offset = l->solutions[reg] & 0xF,
  96                 .size = size
  97         };
  98
  99         /* Report that we actually use this register, and return it */
 100
 101         if (r.reg < 16)
 102                 ctx->work_registers = MAX2(ctx->work_registers, r.reg);
 103
 104         return r;
 105 }
 106
 107 static void
 108 set_class(unsigned *classes, unsigned node, unsigned class)
 109 {
 110         if (node < SSA_FIXED_MINIMUM && class != classes[node]) {
 111                 assert(classes[node] == REG_CLASS_WORK);
 112                 classes[node] = class;
 113         }
 114 }
 115
 116 /* Special register classes impose special constraints on who can read their
 117  * values, so check that */
 118
 119 static bool
 120 check_read_class(unsigned *classes, unsigned tag, unsigned node)
 121 {
 122         /* Non-nodes are implicitly ok */
 123         if (node >= SSA_FIXED_MINIMUM)
 124                 return true;
 125
 126         switch (classes[node]) {
 127         case REG_CLASS_LDST:
 128                 return (tag == TAG_LOAD_STORE_4);
 129         case REG_CLASS_TEXR:
 130                 return (tag == TAG_TEXTURE_4);
 131         case REG_CLASS_TEXW:
 132                 return (tag != TAG_LOAD_STORE_4);
 133         case REG_CLASS_WORK:
 134                 return IS_ALU(tag);
 135         default:
 136                 unreachable("Invalid class");
 137         }
 138 }
 139
 140 static bool
 141 check_write_class(unsigned *classes, unsigned tag, unsigned node)
 142 {
 143         /* Non-nodes are implicitly ok */
 144         if (node >= SSA_FIXED_MINIMUM)
 145                 return true;
 146
 147         switch (classes[node]) {
 148         case REG_CLASS_TEXR:
 149                 return true;
 150         case REG_CLASS_TEXW:
 151                 return (tag == TAG_TEXTURE_4);
 152         case REG_CLASS_LDST:
 153         case REG_CLASS_WORK:
 154                 return IS_ALU(tag) || (tag == TAG_LOAD_STORE_4);
 155         default:
 156                 unreachable("Invalid class");
 157         }
 158 }
 159
 160 /* Prepass before RA to ensure special class restrictions are met. The idea is
 161  * to create a bit field of types of instructions that read a particular index.
 162  * Later, we'll add moves as appropriate and rewrite to specialize by type. */
 163
 164 static void
 165 mark_node_class (unsigned *bitfield, unsigned node)
 166 {
 167         if (node < SSA_FIXED_MINIMUM)
 168                 BITSET_SET(bitfield, node);
 169 }
 170
 171 void
 172 mir_lower_special_reads(compiler_context *ctx)
 173 {
 174         size_t sz = BITSET_WORDS(ctx->temp_count) * sizeof(BITSET_WORD);
 175
 176         /* Bitfields for the various types of registers we could have. aluw can
 177          * be written by either ALU or load/store */
 178
 179         unsigned *alur = calloc(sz, 1);
 180         unsigned *aluw = calloc(sz, 1);
 181         unsigned *brar = calloc(sz, 1);
 182         unsigned *ldst = calloc(sz, 1);
 183         unsigned *texr = calloc(sz, 1);
 184         unsigned *texw = calloc(sz, 1);
 185
 186         /* Pass #1 is analysis, a linear scan to fill out the bitfields */
 187
 188         mir_foreach_instr_global(ctx, ins) {
 189                 switch (ins->type) {
 190                 case TAG_ALU_4:
 191                         mark_node_class(aluw, ins->dest);
 192                         mark_node_class(alur, ins->src[0]);
 193                         mark_node_class(alur, ins->src[1]);
 194                         mark_node_class(alur, ins->src[2]);
 195
 196                         if (ins->compact_branch && ins->writeout)
 197                                 mark_node_class(brar, ins->src[0]);
 198
 199                         break;
 200
 201                 case TAG_LOAD_STORE_4:
 202                         mark_node_class(aluw, ins->dest);
 203                         mark_node_class(ldst, ins->src[0]);
 204                         mark_node_class(ldst, ins->src[1]);
 205                         mark_node_class(ldst, ins->src[2]);
 206                         break;
 207
 208                 case TAG_TEXTURE_4:
 209                         mark_node_class(texr, ins->src[0]);
 210                         mark_node_class(texr, ins->src[1]);
 211                         mark_node_class(texr, ins->src[2]);
 212                         mark_node_class(texw, ins->dest);
 213                         break;
 214                 }
 215         }
 216
 217         /* Pass #2 is lowering now that we've analyzed all the classes.
 218          * Conceptually, if an index is only marked for a single type of use,
 219          * there is nothing to lower. If it is marked for different uses, we
 220          * split up based on the number of types of uses. To do so, we divide
 221          * into N distinct classes of use (where N>1 by definition), emit N-1
 222          * moves from the index to copies of the index, and finally rewrite N-1
 223          * of the types of uses to use the corresponding move */
 224
 225         unsigned spill_idx = ctx->temp_count;
 226
 227         for (unsigned i = 0; i < ctx->temp_count; ++i) {
 228                 bool is_alur = BITSET_TEST(alur, i);
 229                 bool is_aluw = BITSET_TEST(aluw, i);
 230                 bool is_brar = BITSET_TEST(brar, i);
 231                 bool is_ldst = BITSET_TEST(ldst, i);
 232                 bool is_texr = BITSET_TEST(texr, i);
 233                 bool is_texw = BITSET_TEST(texw, i);
 234
 235                 /* Analyse to check how many distinct uses there are. ALU ops
 236                  * (alur) can read the results of the texture pipeline (texw)
 237                  * but not ldst or texr. Load/store ops (ldst) cannot read
 238                  * anything but load/store inputs. Texture pipeline cannot read
 239                  * anything but texture inputs. TODO: Simplify.  */
 240
 241                 bool collision =
 242                         (is_alur && (is_ldst || is_texr)) ||
 243                         (is_ldst && (is_alur || is_texr || is_texw)) ||
 244                         (is_texr && (is_alur || is_ldst || is_texw)) ||
 245                         (is_texw && (is_aluw || is_ldst || is_texr)) ||
 246                         (is_brar && is_texw);
 247
 248                 if (!collision)
 249                         continue;
 250
 251                 /* Use the index as-is as the work copy. Emit copies for
 252                  * special uses */
 253
 254                 unsigned classes[] = { TAG_LOAD_STORE_4, TAG_TEXTURE_4, TAG_TEXTURE_4, TAG_ALU_4};
 255                 bool collisions[] = { is_ldst, is_texr, is_texw && is_aluw, is_brar };
 256
 257                 for (unsigned j = 0; j < ARRAY_SIZE(collisions); ++j) {
 258                         if (!collisions[j]) continue;
 259
 260                         /* When the hazard is from reading, we move and rewrite
 261                          * sources (typical case). When it's from writing, we
 262                          * flip the move and rewrite destinations (obscure,
 263                          * only from control flow -- impossible in SSA) */
 264
 265                         bool hazard_write = (j == 2);
 266
 267                         unsigned idx = spill_idx++;
 268
 269                         midgard_instruction m = hazard_write ?
 270                                 v_mov(idx, i) : v_mov(i, idx);
 271
 272                         /* Insert move before each read/write, depending on the
 273                          * hazard we're trying to account for */
 274
 275                         mir_foreach_instr_global_safe(ctx, pre_use) {
 276                                 if (pre_use->type != classes[j])
 277                                         continue;
 278
 279                                 if (hazard_write) {
 280                                         if (pre_use->dest != i)
 281                                                 continue;
 282                                 } else {
 283                                         if (!mir_has_arg(pre_use, i))
 284                                                 continue;
 285                                 }
 286
 287                                 if (hazard_write) {
 288                                         midgard_instruction *use = mir_next_op(pre_use);
 289                                         assert(use);
 290                                         mir_insert_instruction_before(ctx, use, m);
 291                                         mir_rewrite_index_dst_single(pre_use, i, idx);
 292                                 } else {
 293                                         idx = spill_idx++;
 294                                         m = v_mov(i, idx);
 295                                         m.mask = mir_from_bytemask(mir_bytemask_of_read_components(pre_use, i), 32);
 296                                         mir_insert_instruction_before(ctx, pre_use, m);
 297                                         mir_rewrite_index_src_single(pre_use, i, idx);
 298                                 }
 299                         }
 300                 }
 301         }
 302
 303         free(alur);
 304         free(aluw);
 305         free(brar);
 306         free(ldst);
 307         free(texr);
 308         free(texw);
 309 }
 310
 311 /* We register allocate after scheduling, so we need to ensure instructions
 312  * executing in parallel within a segment of a bundle don't clobber each
 313  * other's registers. This is mostly a non-issue thanks to scheduling, but
 314  * there are edge cases. In particular, after a register is written in a
 315  * segment, it interferes with anything reading. */
 316
 317 static void
 318 mir_compute_segment_interference(
 319                 compiler_context *ctx,
 320                 struct lcra_state *l,
 321                 midgard_bundle *bun,
 322                 unsigned pivot,
 323                 unsigned i)
 324 {
 325         for (unsigned j = pivot; j < i; ++j) {
 326                 mir_foreach_src(bun->instructions[j], s) {
 327                         if (bun->instructions[j]->src[s] >= ctx->temp_count)
 328                                 continue;
 329
 330                         for (unsigned q = pivot; q < i; ++q) {
 331                                 if (bun->instructions[q]->dest >= ctx->temp_count)
 332                                         continue;
 333
 334                                 /* See dEQP-GLES2.functional.shaders.return.output_write_in_func_dynamic_fragment */
 335
 336                                 if (q >= j) {
 337                                         if (!(bun->instructions[j]->unit == UNIT_SMUL && bun->instructions[q]->unit == UNIT_VLUT))
 338                                                 continue;
 339                                 }
 340
 341                                 unsigned mask = mir_bytemask(bun->instructions[q]);
 342                                 unsigned rmask = mir_bytemask_of_read_components(bun->instructions[j], bun->instructions[j]->src[s]);
 343                                 lcra_add_node_interference(l, bun->instructions[q]->dest, mask, bun->instructions[j]->src[s], rmask);
 344                         }
 345                 }
 346         }
 347 }
 348
 349 static void
 350 mir_compute_bundle_interference(
 351                 compiler_context *ctx,
 352                 struct lcra_state *l,
 353                 midgard_bundle *bun)
 354 {
 355         if (!IS_ALU(bun->tag))
 356                 return;
 357
 358         bool old = bun->instructions[0]->unit >= UNIT_VADD;
 359         unsigned pivot = 0;
 360
 361         for (unsigned i = 1; i < bun->instruction_count; ++i) {
 362                 bool new = bun->instructions[i]->unit >= UNIT_VADD;
 363
 364                 if (old != new) {
 365                         mir_compute_segment_interference(ctx, l, bun, 0, i);
 366                         pivot = i;
 367                         break;
 368                 }
 369         }
 370
 371         mir_compute_segment_interference(ctx, l, bun, pivot, bun->instruction_count);
 372 }
 373
 374 static void
 375 mir_compute_interference(
 376                 compiler_context *ctx,
 377                 struct lcra_state *l)
 378 {
 379         /* First, we need liveness information to be computed per block */
 380         mir_compute_liveness(ctx);
 381
 382         /* We need to force r1.w live throughout a blend shader */
 383
 384         if (ctx->is_blend) {
 385                 unsigned r1w = ~0;
 386
 387                 mir_foreach_block(ctx, _block) {
 388                         midgard_block *block = (midgard_block *) _block;
 389                         mir_foreach_instr_in_block_rev(block, ins) {
 390                                 if (ins->writeout)
 391                                         r1w = ins->src[2];
 392                         }
 393
 394                         if (r1w != ~0)
 395                                 break;
 396                 }
 397
 398                 mir_foreach_instr_global(ctx, ins) {
 399                         if (ins->dest < ctx->temp_count)
 400                                 lcra_add_node_interference(l, ins->dest, mir_bytemask(ins), r1w, 0xF);
 401                 }
 402         }
 403
 404         /* Now that every block has live_in/live_out computed, we can determine
 405          * interference by walking each block linearly. Take live_out at the
 406          * end of each block and walk the block backwards. */
 407
 408         mir_foreach_block(ctx, _blk) {
 409                 midgard_block *blk = (midgard_block *) _blk;
 410                 uint16_t *live = mem_dup(_blk->live_out, ctx->temp_count * sizeof(uint16_t));
 411
 412                 mir_foreach_instr_in_block_rev(blk, ins) {
 413                         /* Mark all registers live after the instruction as
 414                          * interfering with the destination */
 415
 416                         unsigned dest = ins->dest;
 417
 418                         if (dest < ctx->temp_count) {
 419                                 for (unsigned i = 0; i < ctx->temp_count; ++i)
 420                                         if (live[i]) {
 421                                                 unsigned mask = mir_bytemask(ins);
 422                                                 lcra_add_node_interference(l, dest, mask, i, live[i]);
 423                                         }
 424                         }
 425
 426                         /* Update live_in */
 427                         mir_liveness_ins_update(live, ins, ctx->temp_count);
 428                 }
 429
 430                 mir_foreach_bundle_in_block(blk, bun)
 431                         mir_compute_bundle_interference(ctx, l, bun);
 432
 433                 free(live);
 434         }
 435 }
 436
 437 /* This routine performs the actual register allocation. It should be succeeded
 438  * by install_registers */
 439
 440 static struct lcra_state *
 441 allocate_registers(compiler_context *ctx, bool *spilled)
 442 {
 443         /* The number of vec4 work registers available depends on when the
 444          * uniforms start, so compute that first */
 445         int work_count = 16 - MAX2((ctx->uniform_cutoff - 8), 0);
 446
 447        /* No register allocation to do with no SSA */
 448
 449         if (!ctx->temp_count)
 450                 return NULL;
 451
 452         struct lcra_state *l = lcra_alloc_equations(ctx->temp_count, 5);
 453
 454         /* Starts of classes, in bytes */
 455         l->class_start[REG_CLASS_WORK]  = 16 * 0;
 456         l->class_start[REG_CLASS_LDST]  = 16 * 26;
 457         l->class_start[REG_CLASS_TEXR]  = 16 * 28;
 458         l->class_start[REG_CLASS_TEXW]  = 16 * 28;
 459
 460         l->class_size[REG_CLASS_WORK] = 16 * work_count;
 461         l->class_size[REG_CLASS_LDST]  = 16 * 2;
 462         l->class_size[REG_CLASS_TEXR]  = 16 * 2;
 463         l->class_size[REG_CLASS_TEXW]  = 16 * 2;
 464
 465         lcra_set_disjoint_class(l, REG_CLASS_TEXR, REG_CLASS_TEXW);
 466
 467         /* To save space on T*20, we don't have real texture registers.
 468          * Instead, tex inputs reuse the load/store pipeline registers, and
 469          * tex outputs use work r0/r1. Note we still use TEXR/TEXW classes,
 470          * noting that this handles interferences and sizes correctly. */
 471
 472         if (ctx->quirks & MIDGARD_INTERPIPE_REG_ALIASING) {
 473                 l->class_start[REG_CLASS_TEXR] = l->class_start[REG_CLASS_LDST];
 474                 l->class_start[REG_CLASS_TEXW] = l->class_start[REG_CLASS_WORK];
 475         }
 476
 477         unsigned *found_class = calloc(sizeof(unsigned), ctx->temp_count);
 478         unsigned *min_alignment = calloc(sizeof(unsigned), ctx->temp_count);
 479         unsigned *min_bound = calloc(sizeof(unsigned), ctx->temp_count);
 480
 481         mir_foreach_instr_global(ctx, ins) {
 482                 /* Swizzles of 32-bit sources on 64-bit instructions need to be
 483                  * aligned to either bottom (xy) or top (zw). More general
 484                  * swizzle lowering should happen prior to scheduling (TODO),
 485                  * but once we get RA we shouldn't disrupt this further. Align
 486                  * sources of 64-bit instructions. */
 487
 488                 if (ins->type == TAG_ALU_4 && ins->alu.reg_mode == midgard_reg_mode_64) {
 489                         mir_foreach_src(ins, v) {
 490                                 unsigned s = ins->src[v];
 491
 492                                 if (s < ctx->temp_count)
 493                                         min_alignment[s] = 3;
 494                         }
 495                 }
 496
 497                 if (ins->type == TAG_LOAD_STORE_4 && OP_HAS_ADDRESS(ins->load_store.op)) {
 498                         mir_foreach_src(ins, v) {
 499                                 unsigned s = ins->src[v];
 500                                 unsigned size = nir_alu_type_get_type_size(ins->src_types[v]);
 501
 502                                 if (s < ctx->temp_count)
 503                                         min_alignment[s] = (size == 64) ? 3 : 2;
 504                         }
 505                 }
 506
 507                 if (ins->dest >= SSA_FIXED_MINIMUM) continue;
 508
 509                 unsigned size = nir_alu_type_get_type_size(ins->dest_type);
 510
 511                 /* 0 for x, 1 for xy, 2 for xyz, 3 for xyzw */
 512                 int comps1 = util_logbase2(ins->mask);
 513
 514                 int bytes = (comps1 + 1) * (size / 8);
 515
 516                 /* Use the largest class if there's ambiguity, this
 517                  * handles partial writes */
 518
 519                 int dest = ins->dest;
 520                 found_class[dest] = MAX2(found_class[dest], bytes);
 521
 522                 /* XXX: Ensure swizzles align the right way with more LCRA constraints? */
 523                 if (ins->type == TAG_ALU_4 && size != 32)
 524                         min_alignment[dest] = 3; /* (1 << 3) = 8 */
 525
 526                 if (ins->type == TAG_LOAD_STORE_4 && ins->load_64)
 527                         min_alignment[dest] = 3;
 528
 529                 /* We don't have a swizzle for the conditional and we don't
 530                  * want to muck with the conditional itself, so just force
 531                  * alignment for now */
 532
 533                 if (ins->type == TAG_ALU_4 && OP_IS_CSEL_V(ins->alu.op))
 534                         min_alignment[dest] = 4; /* 1 << 4= 16-byte = vec4 */
 535
 536         }
 537
 538         for (unsigned i = 0; i < ctx->temp_count; ++i) {
 539                 lcra_set_alignment(l, i, min_alignment[i] ? min_alignment[i] : 2,
 540                                 min_bound[i] ? min_bound[i] : 16);
 541                 lcra_restrict_range(l, i, found_class[i]);
 542         }
 543
 544         free(found_class);
 545         free(min_alignment);
 546         free(min_bound);
 547
 548         /* Next, we'll determine semantic class. We default to zero (work).
 549          * But, if we're used with a special operation, that will force us to a
 550          * particular class. Each node must be assigned to exactly one class; a
 551          * prepass before RA should have lowered what-would-have-been
 552          * multiclass nodes into a series of moves to break it up into multiple
 553          * nodes (TODO) */
 554
 555         mir_foreach_instr_global(ctx, ins) {
 556                 /* Check if this operation imposes any classes */
 557
 558                 if (ins->type == TAG_LOAD_STORE_4) {
 559                         set_class(l->class, ins->src[0], REG_CLASS_LDST);
 560                         set_class(l->class, ins->src[1], REG_CLASS_LDST);
 561                         set_class(l->class, ins->src[2], REG_CLASS_LDST);
 562
 563                         if (OP_IS_VEC4_ONLY(ins->load_store.op)) {
 564                                 lcra_restrict_range(l, ins->dest, 16);
 565                                 lcra_restrict_range(l, ins->src[0], 16);
 566                                 lcra_restrict_range(l, ins->src[1], 16);
 567                                 lcra_restrict_range(l, ins->src[2], 16);
 568                         }
 569                 } else if (ins->type == TAG_TEXTURE_4) {
 570                         set_class(l->class, ins->dest, REG_CLASS_TEXW);
 571                         set_class(l->class, ins->src[0], REG_CLASS_TEXR);
 572                         set_class(l->class, ins->src[1], REG_CLASS_TEXR);
 573                         set_class(l->class, ins->src[2], REG_CLASS_TEXR);
 574                         set_class(l->class, ins->src[3], REG_CLASS_TEXR);
 575                 }
 576         }
 577
 578         /* Check that the semantics of the class are respected */
 579         mir_foreach_instr_global(ctx, ins) {
 580                 assert(check_write_class(l->class, ins->type, ins->dest));
 581                 assert(check_read_class(l->class, ins->type, ins->src[0]));
 582                 assert(check_read_class(l->class, ins->type, ins->src[1]));
 583                 assert(check_read_class(l->class, ins->type, ins->src[2]));
 584         }
 585
 586         /* Mark writeout to r0, render target to r1.z, unknown to r1.w */
 587         mir_foreach_instr_global(ctx, ins) {
 588                 if (!(ins->compact_branch && ins->writeout)) continue;
 589
 590                 if (ins->src[0] < ctx->temp_count) {
 591                         if (ins->writeout_depth)
 592                                 l->solutions[ins->src[0]] = (16 * 1) + COMPONENT_X * 4;
 593                         else if (ins->writeout_stencil)
 594                                 l->solutions[ins->src[0]] = (16 * 1) + COMPONENT_Y * 4;
 595                         else
 596                                 l->solutions[ins->src[0]] = 0;
 597                 }
 598
 599                 if (ins->src[1] < ctx->temp_count)
 600                         l->solutions[ins->src[1]] = (16 * 1) + COMPONENT_Z * 4;
 601
 602                 if (ins->src[2] < ctx->temp_count)
 603                         l->solutions[ins->src[2]] = (16 * 1) + COMPONENT_W * 4;
 604         }
 605
 606         mir_compute_interference(ctx, l);
 607
 608         *spilled = !lcra_solve(l);
 609         return l;
 610 }
 611
 612
 613 /* Once registers have been decided via register allocation
 614  * (allocate_registers), we need to rewrite the MIR to use registers instead of
 615  * indices */
 616
 617 static void
 618 install_registers_instr(
 619         compiler_context *ctx,
 620         struct lcra_state *l,
 621         midgard_instruction *ins)
 622 {
 623         unsigned src_size[MIR_SRC_COUNT];
 624
 625         for (unsigned i = 0; i < MIR_SRC_COUNT; ++i)
 626                 src_size[i] = MAX2(nir_alu_type_get_type_size(ins->src_types[i]) / 8, 1);
 627
 628         unsigned dest_size = MAX2(nir_alu_type_get_type_size(ins->dest_type) / 8, 1);
 629
 630         switch (ins->type) {
 631         case TAG_ALU_4:
 632         case TAG_ALU_8:
 633         case TAG_ALU_12:
 634         case TAG_ALU_16: {
 635                  if (ins->compact_branch)
 636                          return;
 637
 638                 struct phys_reg src1 = index_to_reg(ctx, l, ins->src[0], src_size[0]);
 639                 struct phys_reg src2 = index_to_reg(ctx, l, ins->src[1], src_size[1]);
 640                 struct phys_reg dest = index_to_reg(ctx, l, ins->dest, dest_size);
 641
 642                 mir_set_bytemask(ins, mir_bytemask(ins) << dest.offset);
 643
 644                 unsigned dest_offset =
 645                         GET_CHANNEL_COUNT(alu_opcode_props[ins->alu.op].props) ? 0 :
 646                         dest.offset;
 647
 648                 offset_swizzle(ins->swizzle[0], src1.offset, src1.size, dest.size, dest_offset);
 649
 650                 ins->registers.src1_reg = src1.reg;
 651
 652                 ins->registers.src2_imm = ins->has_inline_constant;
 653
 654                 if (ins->has_inline_constant) {
 655                         /* Encode inline 16-bit constant. See disassembler for
 656                          * where the algorithm is from */
 657
 658                         ins->registers.src2_reg = ins->inline_constant >> 11;
 659
 660                         int lower_11 = ins->inline_constant & ((1 << 12) - 1);
 661                         uint16_t imm = ((lower_11 >> 8) & 0x7) |
 662                                        ((lower_11 & 0xFF) << 3);
 663
 664                         ins->alu.src2 = imm << 2;
 665                 } else {
 666                         offset_swizzle(ins->swizzle[1], src2.offset, src2.size, dest.size, dest_offset);
 667
 668                         ins->registers.src2_reg = src2.reg;
 669                 }
 670
 671                 ins->registers.out_reg = dest.reg;
 672                 break;
 673         }
 674
 675         case TAG_LOAD_STORE_4: {
 676                 /* Which physical register we read off depends on
 677                  * whether we are loading or storing -- think about the
 678                  * logical dataflow */
 679
 680                 bool encodes_src = OP_IS_STORE(ins->load_store.op);
 681
 682                 if (encodes_src) {
 683                         struct phys_reg src = index_to_reg(ctx, l, ins->src[0], src_size[0]);
 684                         assert(src.reg == 26 || src.reg == 27);
 685
 686                         ins->load_store.reg = src.reg - 26;
 687                         offset_swizzle(ins->swizzle[0], src.offset, src.size, 1, 0);
 688                } else {
 689                         struct phys_reg dst = index_to_reg(ctx, l, ins->dest, dest_size);
 690
 691                         ins->load_store.reg = dst.reg;
 692                         offset_swizzle(ins->swizzle[0], 0, 4, 4, dst.offset);
 693                         mir_set_bytemask(ins, mir_bytemask(ins) << dst.offset);
 694                 }
 695
 696                 /* We also follow up by actual arguments */
 697
 698                 unsigned src2 = ins->src[1];
 699                 unsigned src3 = ins->src[2];
 700
 701                 if (src2 != ~0) {
 702                         struct phys_reg src = index_to_reg(ctx, l, src2, 4);
 703                         unsigned component = src.offset / src.size;
 704                         assert(component * src.size == src.offset);
 705                         ins->load_store.arg_1 |= midgard_ldst_reg(src.reg, component);
 706                 }
 707
 708                 if (src3 != ~0) {
 709                         struct phys_reg src = index_to_reg(ctx, l, src3, 4);
 710                         unsigned component = src.offset / src.size;
 711                         assert(component * src.size == src.offset);
 712                         ins->load_store.arg_2 |= midgard_ldst_reg(src.reg, component);
 713                 }
 714
 715                 break;
 716         }
 717
 718         case TAG_TEXTURE_4: {
 719                 if (ins->texture.op == TEXTURE_OP_BARRIER)
 720                         break;
 721
 722                 /* Grab RA results */
 723                 struct phys_reg dest = index_to_reg(ctx, l, ins->dest, dest_size);
 724                 struct phys_reg coord = index_to_reg(ctx, l, ins->src[1], src_size[1]);
 725                 struct phys_reg lod = index_to_reg(ctx, l, ins->src[2], src_size[2]);
 726                 struct phys_reg offset = index_to_reg(ctx, l, ins->src[3], src_size[3]);
 727
 728                 /* First, install the texture coordinate */
 729                 ins->texture.in_reg_select = coord.reg & 1;
 730                 offset_swizzle(ins->swizzle[1], coord.offset, coord.size, dest.size, 0);
 731
 732                 /* Next, install the destination */
 733                 ins->texture.out_reg_select = dest.reg & 1;
 734                 offset_swizzle(ins->swizzle[0], 0, 4, dest.size,
 735                                 dest_size == 2 ? dest.offset % 8 :
 736                                 dest.offset);
 737                 mir_set_bytemask(ins, mir_bytemask(ins) << dest.offset);
 738
 739                 /* If there is a register LOD/bias, use it */
 740                 if (ins->src[2] != ~0) {
 741                         assert(!(lod.offset & 3));
 742                         midgard_tex_register_select sel = {
 743                                 .select = lod.reg & 1,
 744                                 .full = 1,
 745                                 .component = lod.offset / 4
 746                         };
 747
 748                         uint8_t packed;
 749                         memcpy(&packed, &sel, sizeof(packed));
 750                         ins->texture.bias = packed;
 751                 }
 752
 753                 /* If there is an offset register, install it */
 754                 if (ins->src[3] != ~0) {
 755                         unsigned x = offset.offset / 4;
 756                         unsigned y = x + 1;
 757                         unsigned z = x + 2;
 758
 759                         /* Check range, TODO: half-registers */
 760                         assert(z < 4);
 761
 762                         ins->texture.offset =
 763                                 (1)                   | /* full */
 764                                 (offset.reg & 1) << 1 | /* select */
 765                                 (0 << 2)              | /* upper */
 766                                 (x << 3)              | /* swizzle */
 767                                 (y << 5)              | /* swizzle */
 768                                 (z << 7);               /* swizzle */
 769                 }
 770
 771                 break;
 772         }
 773
 774         default:
 775                 break;
 776         }
 777 }
 778
 779 static void
 780 install_registers(compiler_context *ctx, struct lcra_state *l)
 781 {
 782         mir_foreach_instr_global(ctx, ins)
 783                 install_registers_instr(ctx, l, ins);
 784 }
 785
 786
 787 /* If register allocation fails, find the best spill node */
 788
 789 static signed
 790 mir_choose_spill_node(
 791                 compiler_context *ctx,
 792                 struct lcra_state *l)
 793 {
 794         /* We can't spill a previously spilled value or an unspill */
 795
 796         mir_foreach_instr_global(ctx, ins) {
 797                 if (ins->no_spill & (1 << l->spill_class)) {
 798                         lcra_set_node_spill_cost(l, ins->dest, -1);
 799
 800                         if (l->spill_class != REG_CLASS_WORK) {
 801                                 mir_foreach_src(ins, s)
 802                                         lcra_set_node_spill_cost(l, ins->src[s], -1);
 803                         }
 804                 }
 805         }
 806
 807         return lcra_get_best_spill_node(l);
 808 }
 809
 810 /* Once we've chosen a spill node, spill it */
 811
 812 static void
 813 mir_spill_register(
 814                 compiler_context *ctx,
 815                 unsigned spill_node,
 816                 unsigned spill_class,
 817                 unsigned *spill_count)
 818 {
 819         unsigned spill_index = ctx->temp_count;
 820
 821         /* We have a spill node, so check the class. Work registers
 822          * legitimately spill to TLS, but special registers just spill to work
 823          * registers */
 824
 825         bool is_special = spill_class != REG_CLASS_WORK;
 826         bool is_special_w = spill_class == REG_CLASS_TEXW;
 827
 828         /* Allocate TLS slot (maybe) */
 829         unsigned spill_slot = !is_special ? (*spill_count)++ : 0;
 830
 831         /* For TLS, replace all stores to the spilled node. For
 832          * special reads, just keep as-is; the class will be demoted
 833          * implicitly. For special writes, spill to a work register */
 834
 835         if (!is_special || is_special_w) {
 836                 if (is_special_w)
 837                         spill_slot = spill_index++;
 838
 839                 mir_foreach_block(ctx, _block) {
 840                 midgard_block *block = (midgard_block *) _block;
 841                 mir_foreach_instr_in_block_safe(block, ins) {
 842                         if (ins->dest != spill_node) continue;
 843
 844                         midgard_instruction st;
 845
 846                         if (is_special_w) {
 847                                 st = v_mov(spill_node, spill_slot);
 848                                 st.no_spill |= (1 << spill_class);
 849                         } else {
 850                                 ins->dest = spill_index++;
 851                                 ins->no_spill |= (1 << spill_class);
 852                                 st = v_load_store_scratch(ins->dest, spill_slot, true, ins->mask);
 853                         }
 854
 855                         /* Hint: don't rewrite this node */
 856                         st.hint = true;
 857
 858                         mir_insert_instruction_after_scheduled(ctx, block, ins, st);
 859
 860                         if (!is_special)
 861                                 ctx->spills++;
 862                 }
 863                 }
 864         }
 865
 866         /* For special reads, figure out how many bytes we need */
 867         unsigned read_bytemask = 0;
 868
 869         mir_foreach_instr_global_safe(ctx, ins) {
 870                 read_bytemask |= mir_bytemask_of_read_components(ins, spill_node);
 871         }
 872
 873         /* Insert a load from TLS before the first consecutive
 874          * use of the node, rewriting to use spilled indices to
 875          * break up the live range. Or, for special, insert a
 876          * move. Ironically the latter *increases* register
 877          * pressure, but the two uses of the spilling mechanism
 878          * are somewhat orthogonal. (special spilling is to use
 879          * work registers to back special registers; TLS
 880          * spilling is to use memory to back work registers) */
 881
 882         mir_foreach_block(ctx, _block) {
 883                 midgard_block *block = (midgard_block *) _block;
 884                 mir_foreach_instr_in_block(block, ins) {
 885                         /* We can't rewrite the moves used to spill in the
 886                          * first place. These moves are hinted. */
 887                         if (ins->hint) continue;
 888
 889                         /* If we don't use the spilled value, nothing to do */
 890                         if (!mir_has_arg(ins, spill_node)) continue;
 891
 892                         unsigned index = 0;
 893
 894                         if (!is_special_w) {
 895                                 index = ++spill_index;
 896
 897                                 midgard_instruction *before = ins;
 898                                 midgard_instruction st;
 899
 900                                 if (is_special) {
 901                                         /* Move */
 902                                         st = v_mov(spill_node, index);
 903                                         st.no_spill |= (1 << spill_class);
 904                                 } else {
 905                                         /* TLS load */
 906                                         st = v_load_store_scratch(index, spill_slot, false, 0xF);
 907                                 }
 908
 909                                 /* Mask the load based on the component count
 910                                  * actually needed to prevent RA loops */
 911
 912                                 st.mask = mir_from_bytemask(read_bytemask, 32);
 913
 914                                 mir_insert_instruction_before_scheduled(ctx, block, before, st);
 915                         } else {
 916                                 /* Special writes already have their move spilled in */
 917                                 index = spill_slot;
 918                         }
 919
 920
 921                         /* Rewrite to use */
 922                         mir_rewrite_index_src_single(ins, spill_node, index);
 923
 924                         if (!is_special)
 925                                 ctx->fills++;
 926                 }
 927         }
 928
 929         /* Reset hints */
 930
 931         mir_foreach_instr_global(ctx, ins) {
 932                 ins->hint = false;
 933         }
 934 }
 935
 936 /* Run register allocation in a loop, spilling until we succeed */
 937
 938 void
 939 mir_ra(compiler_context *ctx)
 940 {
 941         struct lcra_state *l = NULL;
 942         bool spilled = false;
 943         int iter_count = 1000; /* max iterations */
 944
 945         /* Number of 128-bit slots in memory we've spilled into */
 946         unsigned spill_count = 0;
 947
 948
 949         mir_create_pipeline_registers(ctx);
 950
 951         do {
 952                 if (spilled) {
 953                         signed spill_node = mir_choose_spill_node(ctx, l);
 954
 955                         if (spill_node == -1) {
 956                                 fprintf(stderr, "ERROR: Failed to choose spill node\n");
 957                                 return;
 958                         }
 959
 960                         mir_spill_register(ctx, spill_node, l->spill_class, &spill_count);
 961                 }
 962
 963                 mir_squeeze_index(ctx);
 964                 mir_invalidate_liveness(ctx);
 965
 966                 if (l) {
 967                         lcra_free(l);
 968                         l = NULL;
 969                 }
 970
 971                 l = allocate_registers(ctx, &spilled);
 972         } while(spilled && ((iter_count--) > 0));
 973
 974         if (iter_count <= 0) {
 975                 fprintf(stderr, "panfrost: Gave up allocating registers, rendering will be incomplete\n");
 976                 assert(0);
 977         }
 978
 979         /* Report spilling information. spill_count is in 128-bit slots (vec4 x
 980          * fp32), but tls_size is in bytes, so multiply by 16 */
 981
 982         ctx->tls_size = spill_count * 16;
 983
 984         install_registers(ctx, l);
 985
 986         lcra_free(l);
 987 }