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 53enum 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 71static 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 83static unsigned int * 84ppir_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 95struct 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 137static 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 149static 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(®->list, &comp->reg_list); 166 } 167 } 168 } 169 } 170} 171 172static 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_load_texture: 235 { 236 ppir_load_texture_node *load_tex = ppir_node_to_load_texture(node); 237 ppir_reg *reg = get_src_reg(&load_tex->src_coords); 238 if (reg && node->instr->seq > reg->live_out) 239 reg->live_out = node->instr->seq; 240 break; 241 } 242 default: 243 break; 244 } 245 } 246 } 247 248 return ret; 249} 250 251static int get_phy_reg_index(int reg) 252{ 253 int i; 254 255 for (i = 0; i < ppir_ra_reg_class_num; i++) { 256 if (reg < ppir_ra_reg_base[i + 1]) { 257 reg -= ppir_ra_reg_base[i]; 258 break; 259 } 260 } 261 262 if (i < ppir_ra_reg_class_head_vec1) 263 return reg / (4 - i) * 4 + reg % (4 - i); 264 else 265 return reg * 4; 266} 267 268static void ppir_regalloc_print_result(ppir_compiler *comp) 269{ 270 printf("======ppir regalloc result======\n"); 271 list_for_each_entry(ppir_block, block, &comp->block_list, list) { 272 list_for_each_entry(ppir_instr, instr, &block->instr_list, list) { 273 printf("%03d:", instr->index); 274 for (int i = 0; i < PPIR_INSTR_SLOT_NUM; i++) { 275 ppir_node *node = instr->slots[i]; 276 if (!node) 277 continue; 278 279 printf(" (%d|", node->index); 280 281 ppir_dest *dest = ppir_node_get_dest(node); 282 if (dest) 283 printf("%d", ppir_target_get_dest_reg_index(dest)); 284 285 printf("|"); 286 287 switch (node->type) { 288 case ppir_node_type_alu: 289 { 290 ppir_alu_node *alu = ppir_node_to_alu(node); 291 for (int j = 0; j < alu->num_src; j++) { 292 if (j) 293 printf(" "); 294 295 printf("%d", ppir_target_get_src_reg_index(alu->src + j)); 296 } 297 break; 298 } 299 case ppir_node_type_store: 300 { 301 ppir_store_node *store = ppir_node_to_store(node); 302 printf("%d", ppir_target_get_src_reg_index(&store->src)); 303 break; 304 } 305 case ppir_node_type_load: 306 { 307 ppir_load_node *load = ppir_node_to_load(node); 308 if (!load->num_components) 309 printf("%d", ppir_target_get_src_reg_index(&load->src)); 310 break; 311 } 312 case ppir_node_type_load_texture: 313 { 314 ppir_load_texture_node *load_tex = ppir_node_to_load_texture(node); 315 printf("%d", ppir_target_get_src_reg_index(&load_tex->src_coords)); 316 break; 317 } 318 default: 319 break; 320 } 321 322 printf(")"); 323 } 324 printf("\n"); 325 } 326 } 327 printf("--------------------------\n"); 328} 329 330static bool create_new_instr_after(ppir_block *block, ppir_instr *ref, 331 ppir_node *node) 332{ 333 ppir_instr *newinstr = ppir_instr_create(block); 334 if (unlikely(!newinstr)) 335 return false; 336 337 list_del(&newinstr->list); 338 list_add(&newinstr->list, &ref->list); 339 340 if (!ppir_instr_insert_node(newinstr, node)) 341 return false; 342 343 list_for_each_entry_from(ppir_instr, instr, ref, &block->instr_list, list) { 344 instr->seq++; 345 } 346 newinstr->seq = ref->seq+1; 347 newinstr->scheduled = true; 348 return true; 349} 350 351static bool create_new_instr_before(ppir_block *block, ppir_instr *ref, 352 ppir_node *node) 353{ 354 ppir_instr *newinstr = ppir_instr_create(block); 355 if (unlikely(!newinstr)) 356 return false; 357 358 list_del(&newinstr->list); 359 list_addtail(&newinstr->list, &ref->list); 360 361 if (!ppir_instr_insert_node(newinstr, node)) 362 return false; 363 364 list_for_each_entry_from(ppir_instr, instr, ref, &block->instr_list, list) { 365 instr->seq++; 366 } 367 newinstr->seq = ref->seq-1; 368 newinstr->scheduled = true; 369 return true; 370} 371 372static ppir_alu_node* ppir_update_spilled_src(ppir_compiler *comp, 373 ppir_block *block, 374 ppir_node *node, ppir_src *src, 375 ppir_alu_node *move_alu) 376{ 377 /* alu nodes may have multiple references to the same value. 378 * try to avoid unnecessary loads for the same alu node by 379 * saving the node resulting from the temporary load */ 380 if (move_alu) 381 goto update_src; 382 383 /* alloc new node to load value */ 384 ppir_node *load_node = ppir_node_create(block, ppir_op_load_temp, -1, 0); 385 if (!load_node) 386 return NULL; 387 list_addtail(&load_node->list, &node->list); 388 389 ppir_load_node *load = ppir_node_to_load(load_node); 390 391 load->index = -comp->prog->stack_size; /* index sizes are negative */ 392 load->num_components = src->reg->num_components; 393 394 ppir_dest *ld_dest = &load->dest; 395 ld_dest->type = ppir_target_pipeline; 396 ld_dest->pipeline = ppir_pipeline_reg_uniform; 397 ld_dest->write_mask = 0xf; 398 399 create_new_instr_before(block, node->instr, load_node); 400 401 /* Create move node */ 402 ppir_node *move_node = ppir_node_create(block, ppir_op_mov, -1 , 0); 403 if (unlikely(!move_node)) 404 return false; 405 list_addtail(&move_node->list, &node->list); 406 407 move_alu = ppir_node_to_alu(move_node); 408 409 move_alu->num_src = 1; 410 move_alu->src->type = ppir_target_pipeline; 411 move_alu->src->pipeline = ppir_pipeline_reg_uniform; 412 for (int i = 0; i < 4; i++) 413 move_alu->src->swizzle[i] = i; 414 415 ppir_dest *alu_dest = &move_alu->dest; 416 alu_dest->type = ppir_target_ssa; 417 alu_dest->ssa.num_components = 4; 418 alu_dest->ssa.live_in = INT_MAX; 419 alu_dest->ssa.live_out = 0; 420 alu_dest->write_mask = 0xf; 421 422 list_addtail(&alu_dest->ssa.list, &comp->reg_list); 423 424 if (!ppir_instr_insert_node(load_node->instr, move_node)) 425 return false; 426 427 /* insert the new node as predecessor */ 428 ppir_node_foreach_pred_safe(node, dep) { 429 ppir_node *pred = dep->pred; 430 ppir_node_remove_dep(dep); 431 ppir_node_add_dep(load_node, pred); 432 } 433 ppir_node_add_dep(node, move_node); 434 ppir_node_add_dep(move_node, load_node); 435 436update_src: 437 /* switch node src to use the new ssa instead */ 438 src->type = ppir_target_ssa; 439 src->ssa = &move_alu->dest.ssa; 440 441 return move_alu; 442} 443 444static ppir_reg *create_reg(ppir_compiler *comp, int num_components) 445{ 446 ppir_reg *r = rzalloc(comp, ppir_reg); 447 if (!r) 448 return NULL; 449 450 r->num_components = num_components; 451 r->live_in = INT_MAX; 452 r->live_out = 0; 453 r->is_head = false; 454 list_addtail(&r->list, &comp->reg_list); 455 456 return r; 457} 458 459static bool ppir_update_spilled_dest(ppir_compiler *comp, ppir_block *block, 460 ppir_node *node, ppir_dest *dest) 461{ 462 assert(dest != NULL); 463 ppir_reg *reg = NULL; 464 if (dest->type == ppir_target_register) { 465 reg = dest->reg; 466 reg->num_components = 4; 467 reg->spilled = true; 468 } 469 else { 470 reg = create_reg(comp, 4); 471 reg->spilled = true; 472 list_del(&dest->ssa.list); 473 } 474 475 /* alloc new node to load value */ 476 ppir_node *load_node = ppir_node_create(block, ppir_op_load_temp, -1, 0); 477 if (!load_node) 478 return NULL; 479 list_addtail(&load_node->list, &node->list); 480 481 ppir_load_node *load = ppir_node_to_load(load_node); 482 483 load->index = -comp->prog->stack_size; /* index sizes are negative */ 484 load->num_components = 4; 485 486 load->dest.type = ppir_target_pipeline; 487 load->dest.pipeline = ppir_pipeline_reg_uniform; 488 load->dest.write_mask = 0xf; 489 490 create_new_instr_before(block, node->instr, load_node); 491 492 /* Create move node */ 493 ppir_node *move_node = ppir_node_create(block, ppir_op_mov, -1 , 0); 494 if (unlikely(!move_node)) 495 return false; 496 list_addtail(&move_node->list, &node->list); 497 498 ppir_alu_node *move_alu = ppir_node_to_alu(move_node); 499 500 move_alu->num_src = 1; 501 move_alu->src->type = ppir_target_pipeline; 502 move_alu->src->pipeline = ppir_pipeline_reg_uniform; 503 for (int i = 0; i < 4; i++) 504 move_alu->src->swizzle[i] = i; 505 506 move_alu->dest.type = ppir_target_register; 507 move_alu->dest.reg = reg; 508 move_alu->dest.write_mask = 0x0f; 509 510 if (!ppir_instr_insert_node(load_node->instr, move_node)) 511 return false; 512 513 ppir_node_foreach_pred_safe(node, dep) { 514 ppir_node *pred = dep->pred; 515 ppir_node_remove_dep(dep); 516 ppir_node_add_dep(load_node, pred); 517 } 518 ppir_node_add_dep(node, move_node); 519 ppir_node_add_dep(move_node, load_node); 520 521 dest->type = ppir_target_register; 522 dest->reg = reg; 523 524 /* alloc new node to store value */ 525 ppir_node *store_node = ppir_node_create(block, ppir_op_store_temp, -1, 0); 526 if (!store_node) 527 return false; 528 list_addtail(&store_node->list, &node->list); 529 530 ppir_store_node *store = ppir_node_to_store(store_node); 531 532 store->index = -comp->prog->stack_size; /* index sizes are negative */ 533 store->num_components = 4; 534 535 store->src.type = ppir_target_register; 536 store->src.reg = dest->reg; 537 538 /* insert the new node as successor */ 539 ppir_node_foreach_succ_safe(node, dep) { 540 ppir_node *succ = dep->succ; 541 ppir_node_remove_dep(dep); 542 ppir_node_add_dep(succ, store_node); 543 } 544 ppir_node_add_dep(store_node, node); 545 546 create_new_instr_after(block, node->instr, store_node); 547 548 return true; 549} 550 551static bool ppir_regalloc_spill_reg(ppir_compiler *comp, ppir_reg *chosen) 552{ 553 list_for_each_entry(ppir_block, block, &comp->block_list, list) { 554 list_for_each_entry(ppir_node, node, &block->node_list, list) { 555 556 ppir_dest *dest = ppir_node_get_dest(node); 557 ppir_reg *reg = NULL; 558 if (dest) { 559 if (dest->type == ppir_target_ssa) 560 reg = &dest->ssa; 561 else if (dest->type == ppir_target_register) 562 reg = dest->reg; 563 564 if (reg == chosen) 565 ppir_update_spilled_dest(comp, block, node, dest); 566 } 567 568 switch (node->type) { 569 case ppir_node_type_alu: 570 { 571 /* alu nodes may have multiple references to the same value. 572 * try to avoid unnecessary loads for the same alu node by 573 * saving the node resulting from the temporary load */ 574 ppir_alu_node *move_alu = NULL; 575 ppir_alu_node *alu = ppir_node_to_alu(node); 576 for (int i = 0; i < alu->num_src; i++) { 577 reg = get_src_reg(alu->src + i); 578 if (reg == chosen) { 579 move_alu = ppir_update_spilled_src(comp, block, node, 580 alu->src + i, move_alu); 581 } 582 } 583 break; 584 } 585 case ppir_node_type_store: 586 { 587 ppir_store_node *store = ppir_node_to_store(node); 588 reg = get_src_reg(&store->src); 589 if (reg == chosen) { 590 ppir_update_spilled_src(comp, block, node, &store->src, NULL); 591 } 592 break; 593 } 594 case ppir_node_type_load: 595 { 596 ppir_load_node *load = ppir_node_to_load(node); 597 reg = get_src_reg(&load->src); 598 if (reg == chosen) { 599 ppir_update_spilled_src(comp, block, node, &load->src, NULL); 600 } 601 break; 602 } 603 case ppir_node_type_load_texture: 604 { 605 ppir_load_texture_node *load_tex = ppir_node_to_load_texture(node); 606 reg = get_src_reg(&load_tex->src_coords); 607 if (reg == chosen) { 608 ppir_update_spilled_src(comp, block, node, &load_tex->src_coords, 609 NULL); 610 } 611 break; 612 } 613 default: 614 break; 615 } 616 } 617 } 618 619 return true; 620} 621 622static ppir_reg *ppir_regalloc_choose_spill_node(ppir_compiler *comp, 623 struct ra_graph *g) 624{ 625 int max_range = -1; 626 ppir_reg *chosen = NULL; 627 628 list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { 629 int range = reg->live_out - reg->live_in; 630 631 if (!reg->spilled && reg->live_out != INT_MAX && range > max_range) { 632 chosen = reg; 633 max_range = range; 634 } 635 } 636 637 if (chosen) 638 chosen->spilled = true; 639 640 return chosen; 641} 642 643static void ppir_regalloc_reset_liveness_info(ppir_compiler *comp) 644{ 645 list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { 646 reg->live_in = INT_MAX; 647 reg->live_out = 0; 648 } 649} 650 651int lima_ppir_force_spilling = 0; 652 653static bool ppir_regalloc_prog_try(ppir_compiler *comp, bool *spilled) 654{ 655 ppir_reg *end_reg; 656 657 ppir_regalloc_reset_liveness_info(comp); 658 end_reg = ppir_regalloc_build_liveness_info(comp); 659 660 struct ra_graph *g = ra_alloc_interference_graph( 661 comp->ra, list_length(&comp->reg_list)); 662 663 int n = 0, end_reg_index = 0; 664 list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { 665 int c = ppir_ra_reg_class_vec1 + (reg->num_components - 1); 666 if (reg->is_head) 667 c += 4; 668 if (reg == end_reg) 669 end_reg_index = n; 670 ra_set_node_class(g, n++, c); 671 } 672 673 int n1 = 0; 674 list_for_each_entry(ppir_reg, reg1, &comp->reg_list, list) { 675 int n2 = n1 + 1; 676 list_for_each_entry_from(ppir_reg, reg2, reg1->list.next, 677 &comp->reg_list, list) { 678 bool interference = false; 679 if (reg1->live_in < reg2->live_in) { 680 if (reg1->live_out > reg2->live_in) 681 interference = true; 682 } 683 else if (reg1->live_in > reg2->live_in) { 684 if (reg2->live_out > reg1->live_in) 685 interference = true; 686 } 687 else 688 interference = true; 689 690 if (interference) 691 ra_add_node_interference(g, n1, n2); 692 693 n2++; 694 } 695 n1++; 696 } 697 698 ra_set_node_reg(g, end_reg_index, ppir_ra_reg_base[ppir_ra_reg_class_vec4]); 699 700 *spilled = false; 701 bool ok = ra_allocate(g); 702 if (!ok || (comp->force_spilling-- > 0)) { 703 ppir_reg *chosen = ppir_regalloc_choose_spill_node(comp, g); 704 if (chosen) { 705 /* stack_size will be used to assemble the frame reg in lima_draw. 706 * It is also be used in the spilling code, as negative indices 707 * starting from -1, to create stack addresses. */ 708 comp->prog->stack_size++; 709 ppir_regalloc_spill_reg(comp, chosen); 710 /* Ask the outer loop to call back in. */ 711 *spilled = true; 712 713 ppir_debug("ppir: spilled register\n"); 714 goto err_out; 715 } 716 717 ppir_error("ppir: regalloc fail\n"); 718 goto err_out; 719 } 720 721 n = 0; 722 list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) { 723 int reg_index = ra_get_node_reg(g, n++); 724 reg->index = get_phy_reg_index(reg_index); 725 } 726 727 ralloc_free(g); 728 729 if (lima_debug & LIMA_DEBUG_PP) 730 ppir_regalloc_print_result(comp); 731 732 return true; 733 734err_out: 735 ralloc_free(g); 736 return false; 737} 738 739bool ppir_regalloc_prog(ppir_compiler *comp) 740{ 741 bool spilled = false; 742 comp->prog->stack_size = 0; 743 744 /* Set from an environment variable to force spilling 745 * for debugging purposes, see lima_screen.c */ 746 comp->force_spilling = lima_ppir_force_spilling; 747 748 ppir_regalloc_update_reglist_ssa(comp); 749 750 /* this will most likely succeed in the first 751 * try, except for very complicated shaders */ 752 while (!ppir_regalloc_prog_try(comp, &spilled)) 753 if (!spilled) 754 return false; 755 756 return true; 757} 758