src/gallium/drivers/panfrost/midgard/midgard_ra.c

   1 /*
   2  * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
   3  * Copyright (C) 2019 Collabora
   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/register_allocate.h"
  28 #include "util/u_math.h"
  29
  30 /* For work registers, we can subdivide in various ways. So we create
  31  * classes for the various sizes and conflict accordingly, keeping in
  32  * mind that physical registers are divided along 128-bit boundaries.
  33  * The important part is that 128-bit boundaries are not crossed.
  34  *
  35  * For each 128-bit register, we can subdivide to 32-bits 10 ways
  36  *
  37  * vec4: xyzw
  38  * vec3: xyz, yzw
  39  * vec2: xy, yz, zw,
  40  * vec1: x, y, z, w
  41  *
  42  * For each 64-bit register, we can subdivide similarly to 16-bit
  43  * (TODO: half-float RA, not that we support fp16 yet)
  44  */
  45
  46 #define WORK_STRIDE 10
  47
  48 /* Prepacked masks/swizzles for virtual register types */
  49 static unsigned reg_type_to_mask[WORK_STRIDE] = {
  50         0xF,                                    /* xyzw */
  51         0x7, 0x7 << 1,                          /* xyz */
  52         0x3, 0x3 << 1, 0x3 << 2,                /* xy */
  53         0x1, 0x1 << 1, 0x1 << 2, 0x1 << 3       /* x */
  54 };
  55
  56 static unsigned reg_type_to_swizzle[WORK_STRIDE] = {
  57         SWIZZLE(COMPONENT_X, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  58
  59         SWIZZLE(COMPONENT_X, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  60         SWIZZLE(COMPONENT_Y, COMPONENT_Z, COMPONENT_W, COMPONENT_W),
  61
  62         SWIZZLE(COMPONENT_X, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  63         SWIZZLE(COMPONENT_Y, COMPONENT_Z, COMPONENT_Z, COMPONENT_W),
  64         SWIZZLE(COMPONENT_Z, COMPONENT_W, COMPONENT_Z, COMPONENT_W),
  65
  66         SWIZZLE(COMPONENT_X, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  67         SWIZZLE(COMPONENT_Y, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  68         SWIZZLE(COMPONENT_Z, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  69         SWIZZLE(COMPONENT_W, COMPONENT_Y, COMPONENT_Z, COMPONENT_W),
  70 };
  71
  72 struct phys_reg {
  73         unsigned reg;
  74         unsigned mask;
  75         unsigned swizzle;
  76 };
  77
  78 /* Given the mask/swizzle of both the register and the original source,
  79  * compose to find the actual mask/swizzle to give the hardware */
  80
  81 static unsigned
  82 compose_writemask(unsigned mask, struct phys_reg reg)
  83 {
  84         /* Note: the reg mask is guaranteed to be contiguous. So we shift
  85          * into the X place, compose via a simple AND, and shift back */
  86
  87         unsigned shift = __builtin_ctz(reg.mask);
  88         return ((reg.mask >> shift) & mask) << shift;
  89 }
  90
  91 static unsigned
  92 compose_swizzle(unsigned swizzle, unsigned mask,
  93                 struct phys_reg reg, struct phys_reg dst)
  94 {
  95         unsigned out = 0;
  96
  97         for (unsigned c = 0; c < 4; ++c) {
  98                 unsigned s = (swizzle >> (2*c)) & 0x3;
  99                 unsigned q = (reg.swizzle >> (2*s)) & 0x3;
 100
 101                 out |= (q << (2*c));
 102         }
 103
 104         /* Based on the register mask, we need to adjust over. E.g if we're
 105          * writing to yz, a base swizzle of xy__ becomes _xy_. Save the
 106          * original first component (x). But to prevent duplicate shifting
 107          * (only applies to ALU -- mask param is set to xyzw out on L/S to
 108          * prevent changes), we have to account for the shift inherent to the
 109          * original writemask */
 110
 111         unsigned rep = out & 0x3;
 112         unsigned shift = __builtin_ctz(dst.mask) - __builtin_ctz(mask);
 113         unsigned shifted = out << (2*shift);
 114
 115         /* ..but we fill in the gaps so it appears to replicate */
 116
 117         for (unsigned s = 0; s < shift; ++s)
 118                 shifted |= rep << (2*s);
 119
 120         return shifted;
 121 }
 122
 123 /* When we're 'squeezing down' the values in the IR, we maintain a hash
 124  * as such */
 125
 126 static unsigned
 127 find_or_allocate_temp(compiler_context *ctx, unsigned hash)
 128 {
 129         if ((hash < 0) || (hash >= SSA_FIXED_MINIMUM))
 130                 return hash;
 131
 132         unsigned temp = (uintptr_t) _mesa_hash_table_u64_search(
 133                         ctx->hash_to_temp, hash + 1);
 134
 135         if (temp)
 136                 return temp - 1;
 137
 138         /* If no temp is find, allocate one */
 139         temp = ctx->temp_count++;
 140         ctx->max_hash = MAX2(ctx->max_hash, hash);
 141
 142         _mesa_hash_table_u64_insert(ctx->hash_to_temp,
 143                         hash + 1, (void *) ((uintptr_t) temp + 1));
 144
 145         return temp;
 146 }
 147
 148 /* Callback for register allocation selection, trivial default for now */
 149
 150 static unsigned int
 151 midgard_ra_select_callback(struct ra_graph *g, BITSET_WORD *regs, void *data)
 152 {
 153         /* Choose the first available register to minimise register pressure */
 154
 155         for (int i = 0; i < (16 * WORK_STRIDE); ++i) {
 156                 if (BITSET_TEST(regs, i)) {
 157                         return i;
 158                 }
 159         }
 160
 161         assert(0);
 162         return 0;
 163 }
 164
 165 /* Helper to return the default phys_reg for a given register */
 166
 167 static struct phys_reg
 168 default_phys_reg(int reg)
 169 {
 170         struct phys_reg r = {
 171                 .reg = reg,
 172                 .mask = 0xF, /* xyzw */
 173                 .swizzle = 0xE4 /* xyzw */
 174         };
 175
 176         return r;
 177 }
 178
 179 /* Determine which physical register, swizzle, and mask a virtual
 180  * register corresponds to */
 181
 182 static struct phys_reg
 183 index_to_reg(compiler_context *ctx, struct ra_graph *g, int reg)
 184 {
 185         /* Check for special cases */
 186         if (reg >= SSA_FIXED_MINIMUM)
 187                 return default_phys_reg(SSA_REG_FROM_FIXED(reg));
 188         else if ((reg < 0) || !g)
 189                 return default_phys_reg(REGISTER_UNUSED);
 190
 191         /* Special cases aside, we pick the underlying register */
 192         int virt = ra_get_node_reg(g, reg);
 193
 194         /* Divide out the register and classification */
 195         int phys = virt / WORK_STRIDE;
 196         int type = virt % WORK_STRIDE;
 197
 198         struct phys_reg r = {
 199                 .reg = phys,
 200                 .mask = reg_type_to_mask[type],
 201                 .swizzle = reg_type_to_swizzle[type]
 202         };
 203
 204         /* Report that we actually use this register, and return it */
 205         ctx->work_registers = MAX2(ctx->work_registers, phys);
 206         return r;
 207 }
 208
 209 /* This routine performs the actual register allocation. It should be succeeded
 210  * by install_registers */
 211
 212 struct ra_graph *
 213 allocate_registers(compiler_context *ctx)
 214 {
 215         /* The number of vec4 work registers available depends on when the
 216          * uniforms start, so compute that first */
 217
 218         int work_count = 16 - MAX2((ctx->uniform_cutoff - 8), 0);
 219
 220         int virtual_count = work_count * WORK_STRIDE;
 221
 222         /* First, initialize the RA */
 223         struct ra_regs *regs = ra_alloc_reg_set(NULL, virtual_count, true);
 224
 225         int work_vec4 = ra_alloc_reg_class(regs);
 226         int work_vec3 = ra_alloc_reg_class(regs);
 227         int work_vec2 = ra_alloc_reg_class(regs);
 228         int work_vec1 = ra_alloc_reg_class(regs);
 229
 230         unsigned classes[4] = {
 231                 work_vec1,
 232                 work_vec2,
 233                 work_vec3,
 234                 work_vec4
 235         };
 236
 237         /* Add the full set of work registers */
 238         for (unsigned i = 0; i < work_count; ++i) {
 239                 int base = WORK_STRIDE * i;
 240
 241                 /* Build a full set of subdivisions */
 242                 ra_class_add_reg(regs, work_vec4, base);
 243                 ra_class_add_reg(regs, work_vec3, base + 1);
 244                 ra_class_add_reg(regs, work_vec3, base + 2);
 245                 ra_class_add_reg(regs, work_vec2, base + 3);
 246                 ra_class_add_reg(regs, work_vec2, base + 4);
 247                 ra_class_add_reg(regs, work_vec2, base + 5);
 248                 ra_class_add_reg(regs, work_vec1, base + 6);
 249                 ra_class_add_reg(regs, work_vec1, base + 7);
 250                 ra_class_add_reg(regs, work_vec1, base + 8);
 251                 ra_class_add_reg(regs, work_vec1, base + 9);
 252
 253                 for (unsigned a = 0; a < 10; ++a) {
 254                         unsigned mask1 = reg_type_to_mask[a];
 255
 256                         for (unsigned b = 0; b < 10; ++b) {
 257                                 unsigned mask2 = reg_type_to_mask[b];
 258
 259                                 if (mask1 & mask2)
 260                                         ra_add_reg_conflict(regs,
 261                                                         base + a, base + b);
 262                         }
 263                 }
 264         }
 265
 266         /* We're done setting up */
 267         ra_set_finalize(regs, NULL);
 268
 269         /* Transform the MIR into squeezed index form */
 270         mir_foreach_block(ctx, block) {
 271                 mir_foreach_instr_in_block(block, ins) {
 272                         if (ins->compact_branch) continue;
 273
 274                         ins->ssa_args.dest = find_or_allocate_temp(ctx, ins->ssa_args.dest);
 275                         ins->ssa_args.src0 = find_or_allocate_temp(ctx, ins->ssa_args.src0);
 276
 277                         if (!ins->ssa_args.inline_constant)
 278                                 ins->ssa_args.src1 = find_or_allocate_temp(ctx, ins->ssa_args.src1);
 279
 280                 }
 281         }
 282
 283         /* No register allocation to do with no SSA */
 284
 285         if (!ctx->temp_count)
 286                 return NULL;
 287
 288         /* Let's actually do register allocation */
 289         int nodes = ctx->temp_count;
 290         struct ra_graph *g = ra_alloc_interference_graph(regs, nodes);
 291
 292         /* Determine minimum size needed to hold values, to indirectly
 293          * determine class */
 294
 295         unsigned *found_class = calloc(sizeof(unsigned), ctx->temp_count);
 296
 297         mir_foreach_block(ctx, block) {
 298                 mir_foreach_instr_in_block(block, ins) {
 299                         if (ins->compact_branch) continue;
 300                         if (ins->ssa_args.dest < 0) continue;
 301                         if (ins->ssa_args.dest >= SSA_FIXED_MINIMUM) continue;
 302
 303                         /* Default to vec4 if we're not sure */
 304
 305                         int mask = 0xF;
 306
 307                         if (ins->type == TAG_ALU_4)
 308                                 mask = squeeze_writemask(ins->alu.mask);
 309                         else if (ins->type == TAG_LOAD_STORE_4)
 310                                 mask = ins->load_store.mask;
 311
 312                         int class = util_logbase2(mask) + 1;
 313
 314                         /* Use the largest class if there's ambiguity, this
 315                          * handles partial writes */
 316
 317                         int dest = ins->ssa_args.dest;
 318                         found_class[dest] = MAX2(found_class[dest], class);
 319                 }
 320         }
 321
 322         for (unsigned i = 0; i < ctx->temp_count; ++i) {
 323                 unsigned class = found_class[i];
 324                 if (!class) continue;
 325                 ra_set_node_class(g, i, classes[class - 1]);
 326         }
 327
 328         /* Determine liveness */
 329
 330         int *live_start = malloc(nodes * sizeof(int));
 331         int *live_end = malloc(nodes * sizeof(int));
 332
 333         /* Initialize as non-existent */
 334
 335         for (int i = 0; i < nodes; ++i) {
 336                 live_start[i] = live_end[i] = -1;
 337         }
 338
 339         int d = 0;
 340
 341         mir_foreach_block(ctx, block) {
 342                 mir_foreach_instr_in_block(block, ins) {
 343                         if (ins->compact_branch) continue;
 344
 345                         /* Dest is < 0 for st_vary instructions, which break
 346                          * the usual SSA conventions. Liveness analysis doesn't
 347                          * make sense on these instructions, so skip them to
 348                          * avoid memory corruption */
 349
 350                         if (ins->ssa_args.dest < 0) continue;
 351
 352                         if (ins->ssa_args.dest < SSA_FIXED_MINIMUM) {
 353                                 /* If this destination is not yet live, it is
 354                                  * now since we just wrote it */
 355
 356                                 int dest = ins->ssa_args.dest;
 357
 358                                 if (live_start[dest] == -1)
 359                                         live_start[dest] = d;
 360                         }
 361
 362                         /* Since we just used a source, the source might be
 363                          * dead now. Scan the rest of the block for
 364                          * invocations, and if there are none, the source dies
 365                          * */
 366
 367                         int sources[2] = {
 368                                 ins->ssa_args.src0, ins->ssa_args.src1
 369                         };
 370
 371                         for (int src = 0; src < 2; ++src) {
 372                                 int s = sources[src];
 373
 374                                 if (s < 0) continue;
 375
 376                                 if (s >= SSA_FIXED_MINIMUM) continue;
 377
 378                                 if (!mir_is_live_after(ctx, block, ins, s)) {
 379                                         live_end[s] = d;
 380                                 }
 381                         }
 382
 383                         ++d;
 384                 }
 385         }
 386
 387         /* If a node still hasn't been killed, kill it now */
 388
 389         for (int i = 0; i < nodes; ++i) {
 390                 /* live_start == -1 most likely indicates a pinned output */
 391
 392                 if (live_end[i] == -1)
 393                         live_end[i] = d;
 394         }
 395
 396         /* Setup interference between nodes that are live at the same time */
 397
 398         for (int i = 0; i < nodes; ++i) {
 399                 for (int j = i + 1; j < nodes; ++j) {
 400                         bool j_overlaps_i = live_start[j] < live_end[i];
 401                         bool i_overlaps_j = live_end[j] < live_start[i];
 402
 403                         if (i_overlaps_j || j_overlaps_i)
 404                                 ra_add_node_interference(g, i, j);
 405                 }
 406         }
 407
 408         ra_set_select_reg_callback(g, midgard_ra_select_callback, NULL);
 409
 410         if (!ra_allocate(g)) {
 411                 unreachable("Error allocating registers\n");
 412         }
 413
 414         /* Cleanup */
 415         free(live_start);
 416         free(live_end);
 417
 418         return g;
 419 }
 420
 421 /* Once registers have been decided via register allocation
 422  * (allocate_registers), we need to rewrite the MIR to use registers instead of
 423  * indices */
 424
 425 static void
 426 install_registers_instr(
 427                 compiler_context *ctx,
 428                 struct ra_graph *g,
 429                 midgard_instruction *ins)
 430 {
 431         ssa_args args = ins->ssa_args;
 432
 433         switch (ins->type) {
 434         case TAG_ALU_4: {
 435                 int adjusted_src = args.inline_constant ? -1 : args.src1;
 436                 struct phys_reg src1 = index_to_reg(ctx, g, args.src0);
 437                 struct phys_reg src2 = index_to_reg(ctx, g, adjusted_src);
 438                 struct phys_reg dest = index_to_reg(ctx, g, args.dest);
 439
 440                 unsigned mask = squeeze_writemask(ins->alu.mask);
 441                 ins->alu.mask = expand_writemask(compose_writemask(mask, dest));
 442
 443                 /* Adjust the dest mask if necessary. Mostly this is a no-op
 444                  * but it matters for dot products */
 445                 dest.mask = effective_writemask(&ins->alu);
 446
 447                 midgard_vector_alu_src mod1 =
 448                         vector_alu_from_unsigned(ins->alu.src1);
 449                 mod1.swizzle = compose_swizzle(mod1.swizzle, mask, src1, dest);
 450                 ins->alu.src1 = vector_alu_srco_unsigned(mod1);
 451
 452                 ins->registers.src1_reg = src1.reg;
 453
 454                 ins->registers.src2_imm = args.inline_constant;
 455
 456                 if (args.inline_constant) {
 457                         /* Encode inline 16-bit constant. See disassembler for
 458                          * where the algorithm is from */
 459
 460                         ins->registers.src2_reg = ins->inline_constant >> 11;
 461
 462                         int lower_11 = ins->inline_constant & ((1 << 12) - 1);
 463                         uint16_t imm = ((lower_11 >> 8) & 0x7) |
 464                                 ((lower_11 & 0xFF) << 3);
 465
 466                         ins->alu.src2 = imm << 2;
 467                 } else {
 468                         midgard_vector_alu_src mod2 =
 469                                 vector_alu_from_unsigned(ins->alu.src2);
 470                         mod2.swizzle = compose_swizzle(
 471                                         mod2.swizzle, mask, src2, dest);
 472                         ins->alu.src2 = vector_alu_srco_unsigned(mod2);
 473
 474                         ins->registers.src2_reg = src2.reg;
 475                 }
 476
 477                 ins->registers.out_reg = dest.reg;
 478                 break;
 479         }
 480
 481         case TAG_LOAD_STORE_4: {
 482                 if (OP_IS_STORE_VARY(ins->load_store.op)) {
 483                         /* TODO: use ssa_args for st_vary */
 484                         ins->load_store.reg = 0;
 485                 } else {
 486                         /* Which physical register we read off depends on
 487                          * whether we are loading or storing -- think about the
 488                          * logical dataflow */
 489
 490                         unsigned r = OP_IS_STORE(ins->load_store.op) ?
 491                                 args.src0 : args.dest;
 492                         struct phys_reg src = index_to_reg(ctx, g, r);
 493
 494                         ins->load_store.reg = src.reg;
 495
 496                         ins->load_store.swizzle = compose_swizzle(
 497                                         ins->load_store.swizzle, 0xF,
 498                                         default_phys_reg(0), src);
 499
 500                         ins->load_store.mask = compose_writemask(
 501                                         ins->load_store.mask, src);
 502                 }
 503
 504                 break;
 505         }
 506
 507         default:
 508                 break;
 509         }
 510 }
 511
 512 void
 513 install_registers(compiler_context *ctx, struct ra_graph *g)
 514 {
 515         mir_foreach_block(ctx, block) {
 516                 mir_foreach_instr_in_block(block, ins) {
 517                         if (ins->compact_branch) continue;
 518                         install_registers_instr(ctx, g, ins);
 519                 }
 520         }
 521
 522 }