src/gallium/drivers/lima/ir/pp/regalloc.c

   1 /*
   2  * Copyright (c) 2017 Lima Project
   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, sub license,
   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
  12  * next paragraph) shall be included in all copies or substantial portions
  13  * of the 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 NON-INFRINGEMENT. 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
  21  * DEALINGS IN THE SOFTWARE.
  22  *
  23  */
  24
  25 #include "util/ralloc.h"
  26 #include "util/register_allocate.h"
  27 #include "util/u_debug.h"
  28
  29 #include "ppir.h"
  30 #include "lima_context.h"
  31
  32 #define PPIR_FULL_REG_NUM  6
  33
  34 #define PPIR_VEC1_REG_NUM       (PPIR_FULL_REG_NUM * 4) /* x, y, z, w */
  35 #define PPIR_VEC2_REG_NUM       (PPIR_FULL_REG_NUM * 3) /* xy, yz, zw */
  36 #define PPIR_VEC3_REG_NUM       (PPIR_FULL_REG_NUM * 2) /* xyz, yzw */
  37 #define PPIR_VEC4_REG_NUM       PPIR_FULL_REG_NUM       /* xyzw */
  38 #define PPIR_HEAD_VEC1_REG_NUM  PPIR_FULL_REG_NUM       /* x */
  39 #define PPIR_HEAD_VEC2_REG_NUM  PPIR_FULL_REG_NUM       /* xy */
  40 #define PPIR_HEAD_VEC3_REG_NUM  PPIR_FULL_REG_NUM       /* xyz */
  41 #define PPIR_HEAD_VEC4_REG_NUM  PPIR_FULL_REG_NUM       /* xyzw */
  42
  43 #define PPIR_VEC1_REG_BASE       0
  44 #define PPIR_VEC2_REG_BASE       (PPIR_VEC1_REG_BASE + PPIR_VEC1_REG_NUM)
  45 #define PPIR_VEC3_REG_BASE       (PPIR_VEC2_REG_BASE + PPIR_VEC2_REG_NUM)
  46 #define PPIR_VEC4_REG_BASE       (PPIR_VEC3_REG_BASE + PPIR_VEC3_REG_NUM)
  47 #define PPIR_HEAD_VEC1_REG_BASE  (PPIR_VEC4_REG_BASE + PPIR_VEC4_REG_NUM)
  48 #define PPIR_HEAD_VEC2_REG_BASE  (PPIR_HEAD_VEC1_REG_BASE + PPIR_HEAD_VEC1_REG_NUM)
  49 #define PPIR_HEAD_VEC3_REG_BASE  (PPIR_HEAD_VEC2_REG_BASE + PPIR_HEAD_VEC2_REG_NUM)
  50 #define PPIR_HEAD_VEC4_REG_BASE  (PPIR_HEAD_VEC3_REG_BASE + PPIR_HEAD_VEC3_REG_NUM)
  51 #define PPIR_REG_COUNT           (PPIR_HEAD_VEC4_REG_BASE + PPIR_HEAD_VEC4_REG_NUM)
  52
  53 enum ppir_ra_reg_class {
  54    ppir_ra_reg_class_vec1,
  55    ppir_ra_reg_class_vec2,
  56    ppir_ra_reg_class_vec3,
  57    ppir_ra_reg_class_vec4,
  58
  59    /* 4 reg class for load/store instr regs:
  60     * load/store instr has no swizzle field, so the (virtual) register
  61     * must be allocated at the beginning of a (physical) register,
  62     */
  63    ppir_ra_reg_class_head_vec1,
  64    ppir_ra_reg_class_head_vec2,
  65    ppir_ra_reg_class_head_vec3,
  66    ppir_ra_reg_class_head_vec4,
  67
  68    ppir_ra_reg_class_num,
  69 };
  70
  71 static const int ppir_ra_reg_base[ppir_ra_reg_class_num + 1] = {
  72    [ppir_ra_reg_class_vec1]       = PPIR_VEC1_REG_BASE,
  73    [ppir_ra_reg_class_vec2]       = PPIR_VEC2_REG_BASE,
  74    [ppir_ra_reg_class_vec3]       = PPIR_VEC3_REG_BASE,
  75    [ppir_ra_reg_class_vec4]       = PPIR_VEC4_REG_BASE,
  76    [ppir_ra_reg_class_head_vec1]  = PPIR_HEAD_VEC1_REG_BASE,
  77    [ppir_ra_reg_class_head_vec2]  = PPIR_HEAD_VEC2_REG_BASE,
  78    [ppir_ra_reg_class_head_vec3]  = PPIR_HEAD_VEC3_REG_BASE,
  79    [ppir_ra_reg_class_head_vec4]  = PPIR_HEAD_VEC4_REG_BASE,
  80    [ppir_ra_reg_class_num]        = PPIR_REG_COUNT,
  81 };
  82
  83 static unsigned int *
  84 ppir_ra_reg_q_values[ppir_ra_reg_class_num] = {
  85    (unsigned int []) {1, 2, 3, 4, 1, 2, 3, 4},
  86    (unsigned int []) {2, 3, 3, 3, 1, 2, 3, 3},
  87    (unsigned int []) {2, 2, 2, 2, 1, 2, 2, 2},
  88    (unsigned int []) {1, 1, 1, 1, 1, 1, 1, 1},
  89    (unsigned int []) {1, 1, 1, 1, 1, 1, 1, 1},
  90    (unsigned int []) {1, 1, 1, 1, 1, 1, 1, 1},
  91    (unsigned int []) {1, 1, 1, 1, 1, 1, 1, 1},
  92    (unsigned int []) {1, 1, 1, 1, 1, 1, 1, 1},
  93 };
  94
  95 struct ra_regs *ppir_regalloc_init(void *mem_ctx)
  96 {
  97    struct ra_regs *ret = ra_alloc_reg_set(mem_ctx, PPIR_REG_COUNT, false);
  98    if (!ret)
  99       return NULL;
 100
 101    /* (x, y, z, w) (xy, yz, zw) (xyz, yzw) (xyzw) (x) (xy) (xyz) (xyzw) */
 102    static const int class_reg_num[ppir_ra_reg_class_num] = {
 103       4, 3, 2, 1, 1, 1, 1, 1,
 104    };
 105    /* base reg (x, y, z, w) confliction with other regs */
 106    for (int h = 0; h < 4; h++) {
 107       int base_reg_mask = 1 << h;
 108       for (int i = 1; i < ppir_ra_reg_class_num; i++) {
 109          int class_reg_base_mask = (1 << ((i % 4) + 1)) - 1;
 110          for (int j = 0; j < class_reg_num[i]; j++) {
 111             if (base_reg_mask & (class_reg_base_mask << j)) {
 112                for (int k = 0; k < PPIR_FULL_REG_NUM; k++) {
 113                   ra_add_reg_conflict(ret, k * 4 + h,
 114                      ppir_ra_reg_base[i] + k * class_reg_num[i] + j);
 115                }
 116             }
 117          }
 118       }
 119    }
 120    /* build all other confliction by the base reg confliction */
 121    for (int i = 0; i < PPIR_VEC1_REG_NUM; i++)
 122       ra_make_reg_conflicts_transitive(ret, i);
 123
 124    for (int i = 0; i < ppir_ra_reg_class_num; i++)
 125       ra_alloc_reg_class(ret);
 126
 127    int reg_index = 0;
 128    for (int i = 0; i < ppir_ra_reg_class_num; i++) {
 129       while (reg_index < ppir_ra_reg_base[i + 1])
 130          ra_class_add_reg(ret, i, reg_index++);
 131    }
 132
 133    ra_set_finalize(ret, ppir_ra_reg_q_values);
 134    return ret;
 135 }
 136
 137 static ppir_reg *get_src_reg(ppir_src *src)
 138 {
 139    switch (src->type) {
 140    case ppir_target_ssa:
 141       return src->ssa;
 142    case ppir_target_register:
 143       return src->reg;
 144    default:
 145       return NULL;
 146    }
 147 }
 148
 149 static void ppir_regalloc_update_reglist_ssa(ppir_compiler *comp)
 150 {
 151    list_for_each_entry(ppir_block, block, &comp->block_list, list) {
 152       list_for_each_entry(ppir_node, node, &block->node_list, list) {
 153          if (node->op == ppir_op_store_color)
 154             continue;
 155
 156          if (!node->instr || node->op == ppir_op_const)
 157             continue;
 158
 159          ppir_dest *dest = ppir_node_get_dest(node);
 160          if (dest) {
 161             ppir_reg *reg = NULL;
 162
 163             if (dest->type == ppir_target_ssa) {
 164                reg = &dest->ssa;
 165                list_addtail(&reg->list, &comp->reg_list);
 166             }
 167          }
 168       }
 169    }
 170 }
 171
 172 static ppir_reg *ppir_regalloc_build_liveness_info(ppir_compiler *comp)
 173 {
 174    ppir_reg *ret = NULL;
 175
 176    list_for_each_entry(ppir_block, block, &comp->block_list, list) {
 177       list_for_each_entry(ppir_node, node, &block->node_list, list) {
 178          if (node->op == ppir_op_store_color) {
 179             ppir_store_node *store = ppir_node_to_store(node);
 180             if (store->src.type == ppir_target_ssa)
 181                ret = store->src.ssa;
 182             else
 183                ret = store->src.reg;
 184             ret->live_out = INT_MAX;
 185             continue;
 186          }
 187
 188          if (!node->instr || node->op == ppir_op_const)
 189             continue;
 190
 191          /* update reg live_in from node dest (write) */
 192          ppir_dest *dest = ppir_node_get_dest(node);
 193          if (dest) {
 194             ppir_reg *reg = NULL;
 195
 196             if (dest->type == ppir_target_ssa) {
 197                reg = &dest->ssa;
 198             }
 199             else if (dest->type == ppir_target_register)
 200                reg = dest->reg;
 201
 202             if (reg && node->instr->seq < reg->live_in)
 203                reg->live_in = node->instr->seq;
 204          }
 205
 206          /* update reg live_out from node src (read) */
 207          switch (node->type) {
 208          case ppir_node_type_alu:
 209          {
 210             ppir_alu_node *alu = ppir_node_to_alu(node);
 211             for (int i = 0; i < alu->num_src; i++) {
 212                ppir_reg *reg = get_src_reg(alu->src + i);
 213                if (reg && node->instr->seq > reg->live_out)
 214                   reg->live_out = node->instr->seq;
 215             }
 216             break;
 217          }
 218          case ppir_node_type_store:
 219          {
 220             ppir_store_node *store = ppir_node_to_store(node);
 221             ppir_reg *reg = get_src_reg(&store->src);
 222             if (reg && node->instr->seq > reg->live_out)
 223                reg->live_out = node->instr->seq;
 224             break;
 225          }
 226          case ppir_node_type_load:
 227          {
 228             ppir_load_node *load = ppir_node_to_load(node);
 229             ppir_reg *reg = get_src_reg(&load->src);
 230             if (reg && node->instr->seq > reg->live_out)
 231                reg->live_out = node->instr->seq;
 232             break;
 233          }
 234          case ppir_node_type_branch:
 235          {
 236             ppir_branch_node *branch = ppir_node_to_branch(node);
 237             for (int i = 0; i < 2; i++) {
 238                ppir_reg *reg = get_src_reg(branch->src + i);
 239                if (reg && node->instr->seq > reg->live_out)
 240                   reg->live_out = node->instr->seq;
 241             }
 242             break;
 243          }
 244          default:
 245             break;
 246          }
 247       }
 248    }
 249
 250    return ret;
 251 }
 252
 253 static int get_phy_reg_index(int reg)
 254 {
 255    int i;
 256
 257    for (i = 0; i < ppir_ra_reg_class_num; i++) {
 258       if (reg < ppir_ra_reg_base[i + 1]) {
 259          reg -= ppir_ra_reg_base[i];
 260          break;
 261       }
 262    }
 263
 264    if (i < ppir_ra_reg_class_head_vec1)
 265       return reg / (4 - i) * 4 + reg % (4 - i);
 266    else
 267       return reg * 4;
 268 }
 269
 270 static void ppir_regalloc_print_result(ppir_compiler *comp)
 271 {
 272    printf("======ppir regalloc result======\n");
 273    list_for_each_entry(ppir_block, block, &comp->block_list, list) {
 274       list_for_each_entry(ppir_instr, instr, &block->instr_list, list) {
 275          printf("%03d:", instr->index);
 276          for (int i = 0; i < PPIR_INSTR_SLOT_NUM; i++) {
 277             ppir_node *node = instr->slots[i];
 278             if (!node)
 279                continue;
 280
 281             printf(" (%d|", node->index);
 282
 283             ppir_dest *dest = ppir_node_get_dest(node);
 284             if (dest)
 285                printf("%d", ppir_target_get_dest_reg_index(dest));
 286
 287             printf("|");
 288
 289             switch (node->type) {
 290             case ppir_node_type_alu:
 291             {
 292                ppir_alu_node *alu = ppir_node_to_alu(node);
 293                for (int j = 0; j < alu->num_src; j++) {
 294                   if (j)
 295                      printf(" ");
 296
 297                   printf("%d", ppir_target_get_src_reg_index(alu->src + j));
 298                }
 299                break;
 300             }
 301             case ppir_node_type_store:
 302             {
 303                ppir_store_node *store = ppir_node_to_store(node);
 304                printf("%d", ppir_target_get_src_reg_index(&store->src));
 305                break;
 306             }
 307             case ppir_node_type_load:
 308             {
 309                ppir_load_node *load = ppir_node_to_load(node);
 310                if (!load->num_components)
 311                   printf("%d", ppir_target_get_src_reg_index(&load->src));
 312                break;
 313             }
 314             case ppir_node_type_branch:
 315             {
 316                ppir_branch_node *branch = ppir_node_to_branch(node);
 317                for (int j = 0; j < 2; j++) {
 318                   if (j)
 319                      printf(" ");
 320
 321                   printf("%d", ppir_target_get_src_reg_index(branch->src + j));
 322                }
 323                break;
 324             }
 325             default:
 326                break;
 327             }
 328
 329             printf(")");
 330          }
 331          printf("\n");
 332       }
 333    }
 334    printf("--------------------------\n");
 335 }
 336
 337 static bool create_new_instr_after(ppir_block *block, ppir_instr *ref,
 338                                    ppir_node *node)
 339 {
 340    ppir_instr *newinstr = ppir_instr_create(block);
 341    if (unlikely(!newinstr))
 342       return false;
 343
 344    list_del(&newinstr->list);
 345    list_add(&newinstr->list, &ref->list);
 346
 347    if (!ppir_instr_insert_node(newinstr, node))
 348       return false;
 349
 350    list_for_each_entry_from(ppir_instr, instr, ref, &block->instr_list, list) {
 351       instr->seq++;
 352    }
 353    newinstr->seq = ref->seq+1;
 354    newinstr->scheduled = true;
 355    return true;
 356 }
 357
 358 static bool create_new_instr_before(ppir_block *block, ppir_instr *ref,
 359                                     ppir_node *node)
 360 {
 361    ppir_instr *newinstr = ppir_instr_create(block);
 362    if (unlikely(!newinstr))
 363       return false;
 364
 365    list_del(&newinstr->list);
 366    list_addtail(&newinstr->list, &ref->list);
 367
 368    if (!ppir_instr_insert_node(newinstr, node))
 369       return false;
 370
 371    list_for_each_entry_from(ppir_instr, instr, ref, &block->instr_list, list) {
 372       instr->seq++;
 373    }
 374    newinstr->seq = ref->seq-1;
 375    newinstr->scheduled = true;
 376    return true;
 377 }
 378
 379 static ppir_alu_node* ppir_update_spilled_src(ppir_compiler *comp,
 380                                               ppir_block *block,
 381                                               ppir_node *node, ppir_src *src,
 382                                               ppir_alu_node *move_alu)
 383 {
 384    /* alu nodes may have multiple references to the same value.
 385     * try to avoid unnecessary loads for the same alu node by
 386     * saving the node resulting from the temporary load */
 387    if (move_alu)
 388       goto update_src;
 389
 390    /* alloc new node to load value */
 391    ppir_node *load_node = ppir_node_create(block, ppir_op_load_temp, -1, 0);
 392    if (!load_node)
 393       return NULL;
 394    list_addtail(&load_node->list, &node->list);
 395
 396    ppir_load_node *load = ppir_node_to_load(load_node);
 397
 398    load->index = -comp->prog->stack_size; /* index sizes are negative */
 399    load->num_components = 4;
 400
 401    ppir_dest *ld_dest = &load->dest;
 402    ld_dest->type = ppir_target_pipeline;
 403    ld_dest->pipeline = ppir_pipeline_reg_uniform;
 404    ld_dest->write_mask = 0xf;
 405
 406    create_new_instr_before(block, node->instr, load_node);
 407
 408    /* Create move node */
 409    ppir_node *move_node = ppir_node_create(block, ppir_op_mov, -1 , 0);
 410    if (unlikely(!move_node))
 411       return false;
 412    list_addtail(&move_node->list, &node->list);
 413
 414    move_alu = ppir_node_to_alu(move_node);
 415
 416    move_alu->num_src = 1;
 417    move_alu->src->type = ppir_target_pipeline;
 418    move_alu->src->pipeline = ppir_pipeline_reg_uniform;
 419    for (int i = 0; i < 4; i++)
 420       move_alu->src->swizzle[i] = i;
 421
 422    ppir_dest *alu_dest = &move_alu->dest;
 423    alu_dest->type = ppir_target_ssa;
 424    alu_dest->ssa.num_components = 4;
 425    alu_dest->ssa.live_in = INT_MAX;
 426    alu_dest->ssa.live_out = 0;
 427    alu_dest->write_mask = 0xf;
 428
 429    list_addtail(&alu_dest->ssa.list, &comp->reg_list);
 430
 431    if (!ppir_instr_insert_node(load_node->instr, move_node))
 432       return false;
 433
 434    /* insert the new node as predecessor */
 435    ppir_node_foreach_pred_safe(node, dep) {
 436       ppir_node *pred = dep->pred;
 437       ppir_node_remove_dep(dep);
 438       ppir_node_add_dep(load_node, pred);
 439    }
 440    ppir_node_add_dep(node, move_node);
 441    ppir_node_add_dep(move_node, load_node);
 442
 443 update_src:
 444    /* switch node src to use the new ssa instead */
 445    src->type = ppir_target_ssa;
 446    src->ssa = &move_alu->dest.ssa;
 447
 448    return move_alu;
 449 }
 450
 451 static ppir_reg *create_reg(ppir_compiler *comp, int num_components)
 452 {
 453    ppir_reg *r = rzalloc(comp, ppir_reg);
 454    if (!r)
 455       return NULL;
 456
 457    r->num_components = num_components;
 458    r->live_in = INT_MAX;
 459    r->live_out = 0;
 460    r->is_head = false;
 461    list_addtail(&r->list, &comp->reg_list);
 462
 463    return r;
 464 }
 465
 466 static bool ppir_update_spilled_dest(ppir_compiler *comp, ppir_block *block,
 467                                      ppir_node *node, ppir_dest *dest)
 468 {
 469    assert(dest != NULL);
 470    ppir_reg *reg = NULL;
 471    if (dest->type == ppir_target_register) {
 472       reg = dest->reg;
 473       reg->num_components = 4;
 474       reg->spilled = true;
 475    }
 476    else {
 477       reg = create_reg(comp, 4);
 478       reg->spilled = true;
 479       list_del(&dest->ssa.list);
 480    }
 481
 482    /* alloc new node to load value */
 483    ppir_node *load_node = ppir_node_create(block, ppir_op_load_temp, -1, 0);
 484    if (!load_node)
 485       return NULL;
 486    list_addtail(&load_node->list, &node->list);
 487
 488    ppir_load_node *load = ppir_node_to_load(load_node);
 489
 490    load->index = -comp->prog->stack_size; /* index sizes are negative */
 491    load->num_components = 4;
 492
 493    load->dest.type = ppir_target_pipeline;
 494    load->dest.pipeline = ppir_pipeline_reg_uniform;
 495    load->dest.write_mask = 0xf;
 496
 497    create_new_instr_before(block, node->instr, load_node);
 498
 499    /* Create move node */
 500    ppir_node *move_node = ppir_node_create(block, ppir_op_mov, -1 , 0);
 501    if (unlikely(!move_node))
 502       return false;
 503    list_addtail(&move_node->list, &node->list);
 504
 505    ppir_alu_node *move_alu = ppir_node_to_alu(move_node);
 506
 507    move_alu->num_src = 1;
 508    move_alu->src->type = ppir_target_pipeline;
 509    move_alu->src->pipeline = ppir_pipeline_reg_uniform;
 510    for (int i = 0; i < 4; i++)
 511       move_alu->src->swizzle[i] = i;
 512
 513    move_alu->dest.type = ppir_target_register;
 514    move_alu->dest.reg = reg;
 515    move_alu->dest.write_mask = 0x0f;
 516
 517    if (!ppir_instr_insert_node(load_node->instr, move_node))
 518       return false;
 519
 520    ppir_node_foreach_pred_safe(node, dep) {
 521       ppir_node *pred = dep->pred;
 522       ppir_node_remove_dep(dep);
 523       ppir_node_add_dep(load_node, pred);
 524    }
 525    ppir_node_add_dep(node, move_node);
 526    ppir_node_add_dep(move_node, load_node);
 527
 528    dest->type = ppir_target_register;
 529    dest->reg = reg;
 530
 531    /* alloc new node to store value */
 532    ppir_node *store_node = ppir_node_create(block, ppir_op_store_temp, -1, 0);
 533    if (!store_node)
 534       return false;
 535    list_addtail(&store_node->list, &node->list);
 536
 537    ppir_store_node *store = ppir_node_to_store(store_node);
 538
 539    store->index = -comp->prog->stack_size; /* index sizes are negative */
 540    store->num_components = 4;
 541
 542    store->src.type = ppir_target_register;
 543    store->src.reg = dest->reg;
 544
 545    /* insert the new node as successor */
 546    ppir_node_foreach_succ_safe(node, dep) {
 547       ppir_node *succ = dep->succ;
 548       ppir_node_remove_dep(dep);
 549       ppir_node_add_dep(succ, store_node);
 550    }
 551    ppir_node_add_dep(store_node, node);
 552
 553    create_new_instr_after(block, node->instr, store_node);
 554
 555    return true;
 556 }
 557
 558 static bool ppir_regalloc_spill_reg(ppir_compiler *comp, ppir_reg *chosen)
 559 {
 560    list_for_each_entry(ppir_block, block, &comp->block_list, list) {
 561       list_for_each_entry(ppir_node, node, &block->node_list, list) {
 562
 563          ppir_dest *dest = ppir_node_get_dest(node);
 564          ppir_reg *reg = NULL;
 565          if (dest) {
 566             if (dest->type == ppir_target_ssa)
 567                reg = &dest->ssa;
 568             else if (dest->type == ppir_target_register)
 569                reg = dest->reg;
 570
 571             if (reg == chosen)
 572                ppir_update_spilled_dest(comp, block, node, dest);
 573          }
 574
 575          switch (node->type) {
 576          case ppir_node_type_alu:
 577          {
 578             /* alu nodes may have multiple references to the same value.
 579              * try to avoid unnecessary loads for the same alu node by
 580              * saving the node resulting from the temporary load */
 581             ppir_alu_node *move_alu = NULL;
 582             ppir_alu_node *alu = ppir_node_to_alu(node);
 583             for (int i = 0; i < alu->num_src; i++) {
 584                reg = get_src_reg(alu->src + i);
 585                if (reg == chosen) {
 586                   move_alu = ppir_update_spilled_src(comp, block, node,
 587                                                      alu->src + i, move_alu);
 588                }
 589             }
 590             break;
 591          }
 592          case ppir_node_type_store:
 593          {
 594             ppir_store_node *store = ppir_node_to_store(node);
 595             reg = get_src_reg(&store->src);
 596             if (reg == chosen) {
 597                ppir_update_spilled_src(comp, block, node, &store->src, NULL);
 598             }
 599             break;
 600          }
 601          case ppir_node_type_load:
 602          {
 603             ppir_load_node *load = ppir_node_to_load(node);
 604             reg = get_src_reg(&load->src);
 605             if (reg == chosen) {
 606                ppir_update_spilled_src(comp, block, node, &load->src, NULL);
 607             }
 608             break;
 609          }
 610          case ppir_node_type_branch:
 611          {
 612             ppir_branch_node *branch = ppir_node_to_branch(node);
 613             for (int i = 0; i < 2; i++) {
 614                reg = get_src_reg(branch->src + i);
 615                if (reg == chosen) {
 616                   ppir_update_spilled_src(comp, block, node,
 617                                           branch->src + i, NULL);
 618                }
 619             }
 620             break;
 621          }
 622          default:
 623             break;
 624          }
 625       }
 626    }
 627
 628    return true;
 629 }
 630
 631 static ppir_reg *ppir_regalloc_choose_spill_node(ppir_compiler *comp,
 632                                                  struct ra_graph *g)
 633 {
 634    int max_range = -1;
 635    ppir_reg *chosen = NULL;
 636
 637    list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) {
 638       int range = reg->live_out - reg->live_in;
 639
 640       if (!reg->spilled && reg->live_out != INT_MAX && range > max_range) {
 641          chosen = reg;
 642          max_range = range;
 643       }
 644    }
 645
 646    if (chosen)
 647       chosen->spilled = true;
 648
 649    return chosen;
 650 }
 651
 652 static void ppir_regalloc_reset_liveness_info(ppir_compiler *comp)
 653 {
 654    list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) {
 655       reg->live_in = INT_MAX;
 656       reg->live_out = 0;
 657    }
 658 }
 659
 660 int lima_ppir_force_spilling = 0;
 661
 662 static bool ppir_regalloc_prog_try(ppir_compiler *comp, bool *spilled)
 663 {
 664    ppir_reg *end_reg;
 665
 666    ppir_regalloc_reset_liveness_info(comp);
 667    end_reg = ppir_regalloc_build_liveness_info(comp);
 668
 669    struct ra_graph *g = ra_alloc_interference_graph(
 670       comp->ra, list_length(&comp->reg_list));
 671
 672    int n = 0, end_reg_index = 0;
 673    list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) {
 674       int c = ppir_ra_reg_class_vec1 + (reg->num_components - 1);
 675       if (reg->is_head)
 676          c += 4;
 677       if (reg == end_reg)
 678          end_reg_index = n;
 679       ra_set_node_class(g, n++, c);
 680    }
 681
 682    int n1 = 0;
 683    list_for_each_entry(ppir_reg, reg1, &comp->reg_list, list) {
 684       int n2 = n1 + 1;
 685       list_for_each_entry_from(ppir_reg, reg2, reg1->list.next,
 686                                &comp->reg_list, list) {
 687          bool interference = false;
 688          if (reg1->live_in < reg2->live_in) {
 689             if (reg1->live_out > reg2->live_in)
 690                interference = true;
 691          }
 692          else if (reg1->live_in > reg2->live_in) {
 693             if (reg2->live_out > reg1->live_in)
 694                interference = true;
 695          }
 696          else
 697             interference = true;
 698
 699          if (interference)
 700             ra_add_node_interference(g, n1, n2);
 701
 702          n2++;
 703       }
 704       n1++;
 705    }
 706
 707    ra_set_node_reg(g, end_reg_index, ppir_ra_reg_base[ppir_ra_reg_class_vec4]);
 708
 709    *spilled = false;
 710    bool ok = ra_allocate(g);
 711    if (!ok || (comp->force_spilling-- > 0)) {
 712       ppir_reg *chosen = ppir_regalloc_choose_spill_node(comp, g);
 713       if (chosen) {
 714          /* stack_size will be used to assemble the frame reg in lima_draw.
 715           * It is also be used in the spilling code, as negative indices
 716           * starting from -1, to create stack addresses. */
 717          comp->prog->stack_size++;
 718          ppir_regalloc_spill_reg(comp, chosen);
 719          /* Ask the outer loop to call back in. */
 720          *spilled = true;
 721
 722          ppir_debug("spilled register\n");
 723          goto err_out;
 724       }
 725
 726       ppir_error("regalloc fail\n");
 727       goto err_out;
 728    }
 729
 730    n = 0;
 731    list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) {
 732       int reg_index = ra_get_node_reg(g, n++);
 733       reg->index = get_phy_reg_index(reg_index);
 734    }
 735
 736    ralloc_free(g);
 737
 738    if (lima_debug & LIMA_DEBUG_PP)
 739       ppir_regalloc_print_result(comp);
 740
 741    return true;
 742
 743 err_out:
 744    ralloc_free(g);
 745    return false;
 746 }
 747
 748 bool ppir_regalloc_prog(ppir_compiler *comp)
 749 {
 750    bool spilled = false;
 751    comp->prog->stack_size = 0;
 752
 753    /* Set from an environment variable to force spilling
 754     * for debugging purposes, see lima_screen.c */
 755    comp->force_spilling = lima_ppir_force_spilling;
 756
 757    ppir_regalloc_update_reglist_ssa(comp);
 758
 759    /* No registers? Probably shader consists of discard instruction */
 760    if (list_empty(&comp->reg_list))
 761       return true;
 762
 763    /* this will most likely succeed in the first
 764     * try, except for very complicated shaders */
 765    while (!ppir_regalloc_prog_try(comp, &spilled))
 766       if (!spilled)
 767          return false;
 768
 769    return true;
 770 }