src/gallium/drivers/vc4/vc4_register_allocate.c

   1 /*
   2  * Copyright © 2014 Broadcom
   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
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #include "util/ralloc.h"
  25 #include "util/register_allocate.h"
  26 #include "vc4_context.h"
  27 #include "vc4_qir.h"
  28 #include "vc4_qpu.h"
  29
  30 #define QPU_R(file, index) { QPU_MUX_##file, index }
  31
  32 static const struct qpu_reg vc4_regs[] = {
  33         { QPU_MUX_R0, 0},
  34         { QPU_MUX_R1, 0},
  35         { QPU_MUX_R2, 0},
  36         { QPU_MUX_R3, 0},
  37         { QPU_MUX_R4, 0},
  38         QPU_R(A, 0),
  39         QPU_R(B, 0),
  40         QPU_R(A, 1),
  41         QPU_R(B, 1),
  42         QPU_R(A, 2),
  43         QPU_R(B, 2),
  44         QPU_R(A, 3),
  45         QPU_R(B, 3),
  46         QPU_R(A, 4),
  47         QPU_R(B, 4),
  48         QPU_R(A, 5),
  49         QPU_R(B, 5),
  50         QPU_R(A, 6),
  51         QPU_R(B, 6),
  52         QPU_R(A, 7),
  53         QPU_R(B, 7),
  54         QPU_R(A, 8),
  55         QPU_R(B, 8),
  56         QPU_R(A, 9),
  57         QPU_R(B, 9),
  58         QPU_R(A, 10),
  59         QPU_R(B, 10),
  60         QPU_R(A, 11),
  61         QPU_R(B, 11),
  62         QPU_R(A, 12),
  63         QPU_R(B, 12),
  64         QPU_R(A, 13),
  65         QPU_R(B, 13),
  66         QPU_R(A, 14),
  67         QPU_R(B, 14),
  68         QPU_R(A, 15),
  69         QPU_R(B, 15),
  70         QPU_R(A, 16),
  71         QPU_R(B, 16),
  72         QPU_R(A, 17),
  73         QPU_R(B, 17),
  74         QPU_R(A, 18),
  75         QPU_R(B, 18),
  76         QPU_R(A, 19),
  77         QPU_R(B, 19),
  78         QPU_R(A, 20),
  79         QPU_R(B, 20),
  80         QPU_R(A, 21),
  81         QPU_R(B, 21),
  82         QPU_R(A, 22),
  83         QPU_R(B, 22),
  84         QPU_R(A, 23),
  85         QPU_R(B, 23),
  86         QPU_R(A, 24),
  87         QPU_R(B, 24),
  88         QPU_R(A, 25),
  89         QPU_R(B, 25),
  90         QPU_R(A, 26),
  91         QPU_R(B, 26),
  92         QPU_R(A, 27),
  93         QPU_R(B, 27),
  94         QPU_R(A, 28),
  95         QPU_R(B, 28),
  96         QPU_R(A, 29),
  97         QPU_R(B, 29),
  98         QPU_R(A, 30),
  99         QPU_R(B, 30),
 100         QPU_R(A, 31),
 101         QPU_R(B, 31),
 102 };
 103 #define ACC_INDEX     0
 104 #define AB_INDEX      (ACC_INDEX + 5)
 105
 106 static void
 107 vc4_alloc_reg_set(struct vc4_context *vc4)
 108 {
 109         assert(vc4_regs[AB_INDEX].addr == 0);
 110         assert(vc4_regs[AB_INDEX + 1].addr == 0);
 111         STATIC_ASSERT(ARRAY_SIZE(vc4_regs) == AB_INDEX + 64);
 112
 113         if (vc4->regs)
 114                 return;
 115
 116         vc4->regs = ra_alloc_reg_set(vc4, ARRAY_SIZE(vc4_regs), true);
 117
 118         vc4->reg_class_any = ra_alloc_reg_class(vc4->regs);
 119         vc4->reg_class_a_or_b_or_acc = ra_alloc_reg_class(vc4->regs);
 120         vc4->reg_class_r4_or_a = ra_alloc_reg_class(vc4->regs);
 121         vc4->reg_class_a = ra_alloc_reg_class(vc4->regs);
 122         for (uint32_t i = 0; i < ARRAY_SIZE(vc4_regs); i++) {
 123                 /* Reserve ra31/rb31 for spilling fixup_raddr_conflict() in
 124                  * vc4_qpu_emit.c
 125                  */
 126                 if (vc4_regs[i].addr == 31)
 127                         continue;
 128
 129                 /* R4 can't be written as a general purpose register. (it's
 130                  * TMU_NOSWAP as a write address).
 131                  */
 132                 if (vc4_regs[i].mux == QPU_MUX_R4) {
 133                         ra_class_add_reg(vc4->regs, vc4->reg_class_r4_or_a, i);
 134                         ra_class_add_reg(vc4->regs, vc4->reg_class_any, i);
 135                         continue;
 136                 }
 137
 138                 ra_class_add_reg(vc4->regs, vc4->reg_class_any, i);
 139                 ra_class_add_reg(vc4->regs, vc4->reg_class_a_or_b_or_acc, i);
 140         }
 141
 142         for (uint32_t i = AB_INDEX; i < AB_INDEX + 64; i += 2) {
 143                 ra_class_add_reg(vc4->regs, vc4->reg_class_a, i);
 144                 ra_class_add_reg(vc4->regs, vc4->reg_class_r4_or_a, i);
 145         }
 146
 147         ra_set_finalize(vc4->regs, NULL);
 148 }
 149
 150 struct node_to_temp_map {
 151         uint32_t temp;
 152         uint32_t priority;
 153 };
 154
 155 static int
 156 node_to_temp_priority(const void *in_a, const void *in_b)
 157 {
 158         const struct node_to_temp_map *a = in_a;
 159         const struct node_to_temp_map *b = in_b;
 160
 161         return a->priority - b->priority;
 162 }
 163
 164 #define CLASS_BIT_A                     (1 << 0)
 165 #define CLASS_BIT_B_OR_ACC              (1 << 1)
 166 #define CLASS_BIT_R4                    (1 << 2)
 167
 168 /**
 169  * Returns a mapping from QFILE_TEMP indices to struct qpu_regs.
 170  *
 171  * The return value should be freed by the caller.
 172  */
 173 struct qpu_reg *
 174 vc4_register_allocate(struct vc4_context *vc4, struct vc4_compile *c)
 175 {
 176         struct node_to_temp_map map[c->num_temps];
 177         uint32_t temp_to_node[c->num_temps];
 178         uint32_t def[c->num_temps];
 179         uint32_t use[c->num_temps];
 180         uint8_t class_bits[c->num_temps];
 181         struct qpu_reg *temp_registers = calloc(c->num_temps,
 182                                                 sizeof(*temp_registers));
 183         for (int i = 0; i < ARRAY_SIZE(def); i++)
 184                 def[i] = ~0;
 185         memset(use, 0, sizeof(use));
 186
 187         /* If things aren't ever written (undefined values), just read from
 188          * r0.
 189          */
 190         for (uint32_t i = 0; i < c->num_temps; i++)
 191                 temp_registers[i] = qpu_rn(0);
 192
 193         vc4_alloc_reg_set(vc4);
 194
 195         struct ra_graph *g = ra_alloc_interference_graph(vc4->regs,
 196                                                          c->num_temps);
 197
 198         /* Compute the live ranges so we can figure out interference.
 199          */
 200         uint32_t ip = 0;
 201         list_for_each_entry(struct qinst, inst, &c->instructions, link) {
 202                 if (inst->dst.file == QFILE_TEMP) {
 203                         def[inst->dst.index] = MIN2(ip, def[inst->dst.index]);
 204                         use[inst->dst.index] = ip;
 205                 }
 206
 207                 for (int i = 0; i < qir_get_op_nsrc(inst->op); i++) {
 208                         if (inst->src[i].file == QFILE_TEMP)
 209                                 use[inst->src[i].index] = ip;
 210                 }
 211
 212                 switch (inst->op) {
 213                 case QOP_FRAG_Z:
 214                 case QOP_FRAG_W:
 215                         /* The payload registers have values implicitly loaded
 216                          * at the start of the program.
 217                          */
 218                         def[inst->dst.index] = 0;
 219                         break;
 220                 default:
 221                         break;
 222                 }
 223
 224                 ip++;
 225         }
 226
 227         for (uint32_t i = 0; i < c->num_temps; i++) {
 228                 map[i].temp = i;
 229                 map[i].priority = use[i] - def[i];
 230         }
 231         qsort(map, c->num_temps, sizeof(map[0]), node_to_temp_priority);
 232         for (uint32_t i = 0; i < c->num_temps; i++) {
 233                 temp_to_node[map[i].temp] = i;
 234         }
 235
 236         /* Figure out our register classes and preallocated registers.  We
 237          * start with any temp being able to be in any file, then instructions
 238          * incrementally remove bits that the temp definitely can't be in.
 239          */
 240         memset(class_bits,
 241                CLASS_BIT_A | CLASS_BIT_B_OR_ACC | CLASS_BIT_R4,
 242                sizeof(class_bits));
 243
 244         ip = 0;
 245         list_for_each_entry(struct qinst, inst, &c->instructions, link) {
 246                 if (qir_writes_r4(inst)) {
 247                         /* This instruction writes r4 (and optionally moves
 248                          * its result to a temp), so nothing else can be
 249                          * stored in r4 across it.
 250                          */
 251                         for (int i = 0; i < c->num_temps; i++) {
 252                                 if (def[i] < ip && use[i] > ip)
 253                                         class_bits[i] &= ~CLASS_BIT_R4;
 254                         }
 255                 } else {
 256                         /* R4 can't be written as a general purpose
 257                          * register. (it's TMU_NOSWAP as a write address).
 258                          */
 259                         if (inst->dst.file == QFILE_TEMP)
 260                                 class_bits[inst->dst.index] &= ~CLASS_BIT_R4;
 261                 }
 262
 263                 switch (inst->op) {
 264                 case QOP_FRAG_Z:
 265                         ra_set_node_reg(g, temp_to_node[inst->dst.index],
 266                                         AB_INDEX + QPU_R_FRAG_PAYLOAD_ZW * 2 + 1);
 267                         break;
 268
 269                 case QOP_FRAG_W:
 270                         ra_set_node_reg(g, temp_to_node[inst->dst.index],
 271                                         AB_INDEX + QPU_R_FRAG_PAYLOAD_ZW * 2);
 272                         break;
 273
 274                 default:
 275                         break;
 276                 }
 277
 278                 if (inst->dst.pack && !qir_is_mul(inst)) {
 279                         /* The non-MUL pack flags require an A-file dst
 280                          * register.
 281                          */
 282                         class_bits[inst->dst.index] &= CLASS_BIT_A;
 283                 }
 284
 285                 if (qir_src_needs_a_file(inst)) {
 286                         if (qir_is_float_input(inst)) {
 287                                 /* Special case: these can be done as R4
 288                                  * unpacks, as well.
 289                                  */
 290                                 class_bits[inst->src[0].index] &= (CLASS_BIT_A |
 291                                                                    CLASS_BIT_R4);
 292                         } else {
 293                                 class_bits[inst->src[0].index] &= CLASS_BIT_A;
 294                         }
 295                 }
 296                 ip++;
 297         }
 298
 299         for (uint32_t i = 0; i < c->num_temps; i++) {
 300                 int node = temp_to_node[i];
 301
 302                 switch (class_bits[i]) {
 303                 case CLASS_BIT_A | CLASS_BIT_B_OR_ACC | CLASS_BIT_R4:
 304                         ra_set_node_class(g, node, vc4->reg_class_any);
 305                         break;
 306                 case CLASS_BIT_A | CLASS_BIT_B_OR_ACC:
 307                         ra_set_node_class(g, node, vc4->reg_class_a_or_b_or_acc);
 308                         break;
 309                 case CLASS_BIT_A | CLASS_BIT_R4:
 310                         ra_set_node_class(g, node, vc4->reg_class_r4_or_a);
 311                         break;
 312                 case CLASS_BIT_A:
 313                         ra_set_node_class(g, node, vc4->reg_class_a);
 314                         break;
 315                 default:
 316                         fprintf(stderr, "temp %d: bad class bits: 0x%x\n",
 317                                 i, class_bits[i]);
 318                         abort();
 319                         break;
 320                 }
 321         }
 322
 323         for (uint32_t i = 0; i < c->num_temps; i++) {
 324                 for (uint32_t j = i + 1; j < c->num_temps; j++) {
 325                         if (!(def[i] >= use[j] || def[j] >= use[i])) {
 326                                 ra_add_node_interference(g,
 327                                                          temp_to_node[i],
 328                                                          temp_to_node[j]);
 329                         }
 330                 }
 331         }
 332
 333         bool ok = ra_allocate(g);
 334         if (!ok) {
 335                 fprintf(stderr, "Failed to register allocate:\n");
 336                 qir_dump(c);
 337                 abort();
 338         }
 339
 340         for (uint32_t i = 0; i < c->num_temps; i++) {
 341                 temp_registers[i] = vc4_regs[ra_get_node_reg(g, temp_to_node[i])];
 342
 343                 /* If the value's never used, just write to the NOP register
 344                  * for clarity in debug output.
 345                  */
 346                 if (def[i] == use[i])
 347                         temp_registers[i] = qpu_ra(QPU_W_NOP);
 348         }
 349
 350         ralloc_free(g);
 351
 352         return temp_registers;
 353 }