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/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 = pan_compose_swizzle(swizzle, reg.swizzle);
  96
  97         /* Based on the register mask, we need to adjust over. E.g if we're
  98          * writing to yz, a base swizzle of xy__ becomes _xy_. Save the
  99          * original first component (x). But to prevent duplicate shifting
 100          * (only applies to ALU -- mask param is set to xyzw out on L/S to
 101          * prevent changes), we have to account for the shift inherent to the
 102          * original writemask */
 103
 104         unsigned rep = out & 0x3;
 105         unsigned shift = __builtin_ctz(dst.mask) - __builtin_ctz(mask);
 106         unsigned shifted = out << (2*shift);
 107
 108         /* ..but we fill in the gaps so it appears to replicate */
 109
 110         for (unsigned s = 0; s < shift; ++s)
 111                 shifted |= rep << (2*s);
 112
 113         return shifted;
 114 }
 115
 116 /* When we're 'squeezing down' the values in the IR, we maintain a hash
 117  * as such */
 118
 119 static unsigned
 120 find_or_allocate_temp(compiler_context *ctx, unsigned hash)
 121 {
 122         if ((hash < 0) || (hash >= SSA_FIXED_MINIMUM))
 123                 return hash;
 124
 125         unsigned temp = (uintptr_t) _mesa_hash_table_u64_search(
 126                                 ctx->hash_to_temp, hash + 1);
 127
 128         if (temp)
 129                 return temp - 1;
 130
 131         /* If no temp is find, allocate one */
 132         temp = ctx->temp_count++;
 133         ctx->max_hash = MAX2(ctx->max_hash, hash);
 134
 135         _mesa_hash_table_u64_insert(ctx->hash_to_temp,
 136                                     hash + 1, (void *) ((uintptr_t) temp + 1));
 137
 138         return temp;
 139 }
 140
 141 /* Helper to return the default phys_reg for a given register */
 142
 143 static struct phys_reg
 144 default_phys_reg(int reg)
 145 {
 146         struct phys_reg r = {
 147                 .reg = reg,
 148                 .mask = 0xF, /* xyzw */
 149                 .swizzle = 0xE4 /* xyzw */
 150         };
 151
 152         return r;
 153 }
 154
 155 /* Determine which physical register, swizzle, and mask a virtual
 156  * register corresponds to */
 157
 158 static struct phys_reg
 159 index_to_reg(compiler_context *ctx, struct ra_graph *g, int reg)
 160 {
 161         /* Check for special cases */
 162         if (reg >= SSA_FIXED_MINIMUM)
 163                 return default_phys_reg(SSA_REG_FROM_FIXED(reg));
 164         else if ((reg < 0) || !g)
 165                 return default_phys_reg(REGISTER_UNUSED);
 166
 167         /* Special cases aside, we pick the underlying register */
 168         int virt = ra_get_node_reg(g, reg);
 169
 170         /* Divide out the register and classification */
 171         int phys = virt / WORK_STRIDE;
 172         int type = virt % WORK_STRIDE;
 173
 174         struct phys_reg r = {
 175                 .reg = phys,
 176                 .mask = reg_type_to_mask[type],
 177                 .swizzle = reg_type_to_swizzle[type]
 178         };
 179
 180         /* Report that we actually use this register, and return it */
 181         ctx->work_registers = MAX2(ctx->work_registers, phys);
 182         return r;
 183 }
 184
 185 /* This routine performs the actual register allocation. It should be succeeded
 186  * by install_registers */
 187
 188 struct ra_graph *
 189 allocate_registers(compiler_context *ctx, bool *spilled)
 190 {
 191         /* The number of vec4 work registers available depends on when the
 192          * uniforms start, so compute that first */
 193
 194         int work_count = 16 - MAX2((ctx->uniform_cutoff - 8), 0);
 195
 196         int virtual_count = work_count * WORK_STRIDE;
 197
 198         /* First, initialize the RA */
 199         struct ra_regs *regs = ra_alloc_reg_set(NULL, virtual_count, true);
 200
 201         int work_vec4 = ra_alloc_reg_class(regs);
 202         int work_vec3 = ra_alloc_reg_class(regs);
 203         int work_vec2 = ra_alloc_reg_class(regs);
 204         int work_vec1 = ra_alloc_reg_class(regs);
 205
 206         unsigned classes[4] = {
 207                 work_vec1,
 208                 work_vec2,
 209                 work_vec3,
 210                 work_vec4
 211         };
 212
 213         /* Add the full set of work registers */
 214         for (unsigned i = 0; i < work_count; ++i) {
 215                 int base = WORK_STRIDE * i;
 216
 217                 /* Build a full set of subdivisions */
 218                 ra_class_add_reg(regs, work_vec4, base);
 219                 ra_class_add_reg(regs, work_vec3, base + 1);
 220                 ra_class_add_reg(regs, work_vec3, base + 2);
 221                 ra_class_add_reg(regs, work_vec2, base + 3);
 222                 ra_class_add_reg(regs, work_vec2, base + 4);
 223                 ra_class_add_reg(regs, work_vec2, base + 5);
 224                 ra_class_add_reg(regs, work_vec1, base + 6);
 225                 ra_class_add_reg(regs, work_vec1, base + 7);
 226                 ra_class_add_reg(regs, work_vec1, base + 8);
 227                 ra_class_add_reg(regs, work_vec1, base + 9);
 228
 229                 for (unsigned a = 0; a < 10; ++a) {
 230                         unsigned mask1 = reg_type_to_mask[a];
 231
 232                         for (unsigned b = 0; b < 10; ++b) {
 233                                 unsigned mask2 = reg_type_to_mask[b];
 234
 235                                 if (mask1 & mask2)
 236                                         ra_add_reg_conflict(regs,
 237                                                             base + a, base + b);
 238                         }
 239                 }
 240         }
 241
 242         /* We're done setting up */
 243         ra_set_finalize(regs, NULL);
 244
 245         /* Transform the MIR into squeezed index form */
 246         mir_foreach_block(ctx, block) {
 247                 mir_foreach_instr_in_block(block, ins) {
 248                         if (ins->compact_branch) continue;
 249
 250                         ins->ssa_args.dest = find_or_allocate_temp(ctx, ins->ssa_args.dest);
 251                         ins->ssa_args.src0 = find_or_allocate_temp(ctx, ins->ssa_args.src0);
 252
 253                         if (!ins->ssa_args.inline_constant)
 254                                 ins->ssa_args.src1 = find_or_allocate_temp(ctx, ins->ssa_args.src1);
 255
 256                 }
 257         }
 258
 259         /* No register allocation to do with no SSA */
 260
 261         if (!ctx->temp_count)
 262                 return NULL;
 263
 264         /* Let's actually do register allocation */
 265         int nodes = ctx->temp_count;
 266         struct ra_graph *g = ra_alloc_interference_graph(regs, nodes);
 267
 268         /* Determine minimum size needed to hold values, to indirectly
 269          * determine class */
 270
 271         unsigned *found_class = calloc(sizeof(unsigned), ctx->temp_count);
 272
 273         mir_foreach_block(ctx, block) {
 274                 mir_foreach_instr_in_block(block, ins) {
 275                         if (ins->compact_branch) continue;
 276                         if (ins->ssa_args.dest < 0) continue;
 277                         if (ins->ssa_args.dest >= SSA_FIXED_MINIMUM) continue;
 278
 279                         int class = util_logbase2(ins->mask) + 1;
 280
 281                         /* Use the largest class if there's ambiguity, this
 282                          * handles partial writes */
 283
 284                         int dest = ins->ssa_args.dest;
 285                         found_class[dest] = MAX2(found_class[dest], class);
 286                 }
 287         }
 288
 289         for (unsigned i = 0; i < ctx->temp_count; ++i) {
 290                 unsigned class = found_class[i];
 291                 if (!class) continue;
 292                 ra_set_node_class(g, i, classes[class - 1]);
 293         }
 294
 295         /* Determine liveness */
 296
 297         int *live_start = malloc(nodes * sizeof(int));
 298         int *live_end = malloc(nodes * sizeof(int));
 299
 300         /* Initialize as non-existent */
 301
 302         for (int i = 0; i < nodes; ++i) {
 303                 live_start[i] = live_end[i] = -1;
 304         }
 305
 306         int d = 0;
 307
 308         mir_foreach_block(ctx, block) {
 309                 mir_foreach_instr_in_block(block, ins) {
 310                         if (ins->compact_branch) continue;
 311
 312                         /* Dest is < 0 for st_vary instructions, which break
 313                          * the usual SSA conventions. Liveness analysis doesn't
 314                          * make sense on these instructions, so skip them to
 315                          * avoid memory corruption */
 316
 317                         if (ins->ssa_args.dest < 0) continue;
 318
 319                         if (ins->ssa_args.dest < SSA_FIXED_MINIMUM) {
 320                                 /* If this destination is not yet live, it is
 321                                  * now since we just wrote it */
 322
 323                                 int dest = ins->ssa_args.dest;
 324
 325                                 if (live_start[dest] == -1)
 326                                         live_start[dest] = d;
 327                         }
 328
 329                         /* Since we just used a source, the source might be
 330                          * dead now. Scan the rest of the block for
 331                          * invocations, and if there are none, the source dies
 332                          * */
 333
 334                         int sources[2] = {
 335                                 ins->ssa_args.src0, ins->ssa_args.src1
 336                         };
 337
 338                         for (int src = 0; src < 2; ++src) {
 339                                 int s = sources[src];
 340
 341                                 if (s < 0) continue;
 342
 343                                 if (s >= SSA_FIXED_MINIMUM) continue;
 344
 345                                 if (!mir_is_live_after(ctx, block, ins, s)) {
 346                                         live_end[s] = d;
 347                                 }
 348                         }
 349
 350                         ++d;
 351                 }
 352         }
 353
 354         /* If a node still hasn't been killed, kill it now */
 355
 356         for (int i = 0; i < nodes; ++i) {
 357                 /* live_start == -1 most likely indicates a pinned output */
 358
 359                 if (live_end[i] == -1)
 360                         live_end[i] = d;
 361         }
 362
 363         /* Setup interference between nodes that are live at the same time */
 364
 365         for (int i = 0; i < nodes; ++i) {
 366                 for (int j = i + 1; j < nodes; ++j) {
 367                         bool j_overlaps_i = live_start[j] < live_end[i];
 368                         bool i_overlaps_j = live_end[j] < live_start[i];
 369
 370                         if (i_overlaps_j || j_overlaps_i)
 371                                 ra_add_node_interference(g, i, j);
 372                 }
 373         }
 374
 375         /* Cleanup */
 376         free(live_start);
 377         free(live_end);
 378
 379         if (!ra_allocate(g)) {
 380                 *spilled = true;
 381                 return NULL;
 382         }
 383
 384         return g;
 385 }
 386
 387 /* Once registers have been decided via register allocation
 388  * (allocate_registers), we need to rewrite the MIR to use registers instead of
 389  * indices */
 390
 391 static void
 392 install_registers_instr(
 393         compiler_context *ctx,
 394         struct ra_graph *g,
 395         midgard_instruction *ins)
 396 {
 397         ssa_args args = ins->ssa_args;
 398
 399         switch (ins->type) {
 400         case TAG_ALU_4: {
 401                 int adjusted_src = args.inline_constant ? -1 : args.src1;
 402                 struct phys_reg src1 = index_to_reg(ctx, g, args.src0);
 403                 struct phys_reg src2 = index_to_reg(ctx, g, adjusted_src);
 404                 struct phys_reg dest = index_to_reg(ctx, g, args.dest);
 405
 406                 unsigned uncomposed_mask = ins->mask;
 407                 ins->mask = compose_writemask(uncomposed_mask, dest);
 408
 409                 /* Adjust the dest mask if necessary. Mostly this is a no-op
 410                  * but it matters for dot products */
 411                 dest.mask = effective_writemask(&ins->alu, ins->mask);
 412
 413                 midgard_vector_alu_src mod1 =
 414                         vector_alu_from_unsigned(ins->alu.src1);
 415                 mod1.swizzle = compose_swizzle(mod1.swizzle, uncomposed_mask, src1, dest);
 416                 ins->alu.src1 = vector_alu_srco_unsigned(mod1);
 417
 418                 ins->registers.src1_reg = src1.reg;
 419
 420                 ins->registers.src2_imm = args.inline_constant;
 421
 422                 if (args.inline_constant) {
 423                         /* Encode inline 16-bit constant. See disassembler for
 424                          * where the algorithm is from */
 425
 426                         ins->registers.src2_reg = ins->inline_constant >> 11;
 427
 428                         int lower_11 = ins->inline_constant & ((1 << 12) - 1);
 429                         uint16_t imm = ((lower_11 >> 8) & 0x7) |
 430                                        ((lower_11 & 0xFF) << 3);
 431
 432                         ins->alu.src2 = imm << 2;
 433                 } else {
 434                         midgard_vector_alu_src mod2 =
 435                                 vector_alu_from_unsigned(ins->alu.src2);
 436                         mod2.swizzle = compose_swizzle(
 437                                                mod2.swizzle, uncomposed_mask, src2, dest);
 438                         ins->alu.src2 = vector_alu_srco_unsigned(mod2);
 439
 440                         ins->registers.src2_reg = src2.reg;
 441                 }
 442
 443                 ins->registers.out_reg = dest.reg;
 444                 break;
 445         }
 446
 447         case TAG_LOAD_STORE_4: {
 448                 if (OP_IS_STORE_R26(ins->load_store.op)) {
 449                         /* TODO: use ssa_args for st_vary */
 450                         ins->load_store.reg = 0;
 451                 } else {
 452                         /* Which physical register we read off depends on
 453                          * whether we are loading or storing -- think about the
 454                          * logical dataflow */
 455
 456                         unsigned r = OP_IS_STORE(ins->load_store.op) ?
 457                                      args.src0 : args.dest;
 458                         struct phys_reg src = index_to_reg(ctx, g, r);
 459
 460                         ins->load_store.reg = src.reg;
 461
 462                         ins->load_store.swizzle = compose_swizzle(
 463                                                           ins->load_store.swizzle, 0xF,
 464                                                           default_phys_reg(0), src);
 465
 466                         ins->mask = compose_writemask(
 467                                             ins->mask, src);
 468                 }
 469
 470                 break;
 471         }
 472
 473         default:
 474                 break;
 475         }
 476 }
 477
 478 void
 479 install_registers(compiler_context *ctx, struct ra_graph *g)
 480 {
 481         mir_foreach_block(ctx, block) {
 482                 mir_foreach_instr_in_block(block, ins) {
 483                         if (ins->compact_branch) continue;
 484                         install_registers_instr(ctx, g, ins);
 485                 }
 486         }
 487
 488 }