src/glsl/nir/nir.c

   1 /*
   2  * Copyright © 2014 Intel Corporation
   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  * Authors:
  24  *    Connor Abbott (cwabbott0@gmail.com)
  25  *
  26  */
  27
  28 #include "nir.h"
  29 #include <assert.h>
  30
  31 nir_shader *
  32 nir_shader_create(void *mem_ctx)
  33 {
  34    nir_shader *shader = ralloc(mem_ctx, nir_shader);
  35
  36    shader->uniforms = _mesa_hash_table_create(shader, _mesa_key_hash_string,
  37                                               _mesa_key_string_equal);
  38    shader->inputs = _mesa_hash_table_create(shader, _mesa_key_hash_string,
  39                                             _mesa_key_string_equal);
  40    shader->outputs = _mesa_hash_table_create(shader, _mesa_key_hash_string,
  41                                              _mesa_key_string_equal);
  42
  43    shader->num_user_structures = 0;
  44    shader->user_structures = NULL;
  45
  46    exec_list_make_empty(&shader->functions);
  47    exec_list_make_empty(&shader->registers);
  48    exec_list_make_empty(&shader->globals);
  49    exec_list_make_empty(&shader->system_values);
  50    shader->reg_alloc = 0;
  51
  52    shader->num_inputs = 0;
  53    shader->num_outputs = 0;
  54    shader->num_uniforms = 0;
  55
  56    return shader;
  57 }
  58
  59 static nir_register *
  60 reg_create(void *mem_ctx, struct exec_list *list)
  61 {
  62    nir_register *reg = ralloc(mem_ctx, nir_register);
  63
  64    reg->uses = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
  65    reg->defs = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
  66    reg->if_uses = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
  67
  68    reg->num_components = 0;
  69    reg->num_array_elems = 0;
  70    reg->is_packed = false;
  71    reg->name = NULL;
  72
  73    exec_list_push_tail(list, &reg->node);
  74
  75    return reg;
  76 }
  77
  78 nir_register *
  79 nir_global_reg_create(nir_shader *shader)
  80 {
  81    nir_register *reg = reg_create(shader, &shader->registers);
  82    reg->index = shader->reg_alloc++;
  83    reg->is_global = true;
  84
  85    return reg;
  86 }
  87
  88 nir_register *
  89 nir_local_reg_create(nir_function_impl *impl)
  90 {
  91    nir_register *reg = reg_create(ralloc_parent(impl), &impl->registers);
  92    reg->index = impl->reg_alloc++;
  93    reg->is_global = false;
  94
  95    return reg;
  96 }
  97
  98 void
  99 nir_reg_remove(nir_register *reg)
 100 {
 101    exec_node_remove(&reg->node);
 102 }
 103
 104 nir_function *
 105 nir_function_create(nir_shader *shader, const char *name)
 106 {
 107    nir_function *func = ralloc(shader, nir_function);
 108
 109    exec_list_push_tail(&shader->functions, &func->node);
 110    exec_list_make_empty(&func->overload_list);
 111    func->name = name;
 112    func->shader = shader;
 113
 114    return func;
 115 }
 116
 117 nir_function_overload *
 118 nir_function_overload_create(nir_function *func)
 119 {
 120    void *mem_ctx = ralloc_parent(func);
 121
 122    nir_function_overload *overload = ralloc(mem_ctx, nir_function_overload);
 123
 124    overload->num_params = 0;
 125    overload->params = NULL;
 126    overload->return_type = glsl_void_type();
 127    overload->impl = NULL;
 128
 129    exec_list_push_tail(&func->overload_list, &overload->node);
 130    overload->function = func;
 131
 132    return overload;
 133 }
 134
 135 nir_src nir_src_copy(nir_src src, void *mem_ctx)
 136 {
 137    nir_src ret;
 138    ret.is_ssa = src.is_ssa;
 139    if (ret.is_ssa) {
 140       ret.ssa = src.ssa;
 141    } else {
 142       ret.reg.base_offset = src.reg.base_offset;
 143       ret.reg.reg = src.reg.reg;
 144       if (src.reg.indirect) {
 145          ret.reg.indirect = ralloc(mem_ctx, nir_src);
 146          *ret.reg.indirect = *src.reg.indirect;
 147       } else {
 148          ret.reg.indirect = NULL;
 149       }
 150    }
 151
 152    return ret;
 153 }
 154
 155 nir_dest nir_dest_copy(nir_dest dest, void *mem_ctx)
 156 {
 157    nir_dest ret;
 158    ret.is_ssa = dest.is_ssa;
 159    if (ret.is_ssa) {
 160       ret.ssa = dest.ssa;
 161    } else {
 162       ret.reg.base_offset = dest.reg.base_offset;
 163       ret.reg.reg = dest.reg.reg;
 164       if (dest.reg.indirect) {
 165          ret.reg.indirect = ralloc(mem_ctx, nir_src);
 166          *ret.reg.indirect = *dest.reg.indirect;
 167       } else {
 168          ret.reg.indirect = NULL;
 169       }
 170    }
 171
 172    return ret;
 173 }
 174
 175 static inline void
 176 block_add_pred(nir_block *block, nir_block *pred)
 177 {
 178    _mesa_set_add(block->predecessors, _mesa_hash_pointer(pred), pred);
 179 }
 180
 181 static void
 182 cf_init(nir_cf_node *node, nir_cf_node_type type)
 183 {
 184    exec_node_init(&node->node);
 185    node->parent = NULL;
 186    node->type = type;
 187 }
 188
 189 static void
 190 link_blocks(nir_block *pred, nir_block *succ1, nir_block *succ2)
 191 {
 192    pred->successors[0] = succ1;
 193    block_add_pred(succ1, pred);
 194
 195    pred->successors[1] = succ2;
 196    if (succ2 != NULL)
 197       block_add_pred(succ2, pred);
 198 }
 199
 200 static void
 201 unlink_blocks(nir_block *pred, nir_block *succ)
 202 {
 203    if (pred->successors[0] == succ) {
 204       pred->successors[0] = pred->successors[1];
 205       pred->successors[1] = NULL;
 206    } else {
 207       assert(pred->successors[1] == succ);
 208       pred->successors[1] = NULL;
 209    }
 210
 211    struct set_entry *entry = _mesa_set_search(succ->predecessors,
 212                                               _mesa_hash_pointer(pred), pred);
 213
 214    assert(entry);
 215
 216    _mesa_set_remove(succ->predecessors, entry);
 217 }
 218
 219 static void
 220 unlink_block_successors(nir_block *block)
 221 {
 222    if (block->successors[0] != NULL)
 223       unlink_blocks(block, block->successors[0]);
 224    if (block->successors[1] != NULL)
 225       unlink_blocks(block, block->successors[1]);
 226 }
 227
 228
 229 nir_function_impl *
 230 nir_function_impl_create(nir_function_overload *overload)
 231 {
 232    assert(overload->impl == NULL);
 233
 234    void *mem_ctx = ralloc_parent(overload);
 235
 236    nir_function_impl *impl = ralloc(mem_ctx, nir_function_impl);
 237
 238    overload->impl = impl;
 239    impl->overload = overload;
 240
 241    cf_init(&impl->cf_node, nir_cf_node_function);
 242
 243    exec_list_make_empty(&impl->body);
 244    exec_list_make_empty(&impl->registers);
 245    exec_list_make_empty(&impl->locals);
 246    impl->num_params = 0;
 247    impl->params = NULL;
 248    impl->return_var = NULL;
 249    impl->reg_alloc = 0;
 250    impl->ssa_alloc = 0;
 251    impl->valid_metadata = nir_metadata_none;
 252
 253    /* create start & end blocks */
 254    nir_block *start_block = nir_block_create(mem_ctx);
 255    nir_block *end_block = nir_block_create(mem_ctx);
 256    start_block->cf_node.parent = &impl->cf_node;
 257    end_block->cf_node.parent = &impl->cf_node;
 258    impl->start_block = start_block;
 259    impl->end_block = end_block;
 260
 261    exec_list_push_tail(&impl->body, &start_block->cf_node.node);
 262
 263    start_block->successors[0] = end_block;
 264    block_add_pred(end_block, start_block);
 265
 266    return impl;
 267 }
 268
 269 nir_block *
 270 nir_block_create(void *mem_ctx)
 271 {
 272    nir_block *block = ralloc(mem_ctx, nir_block);
 273
 274    cf_init(&block->cf_node, nir_cf_node_block);
 275
 276    block->successors[0] = block->successors[1] = NULL;
 277    block->predecessors = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
 278    block->imm_dom = NULL;
 279    block->dom_frontier = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
 280
 281    exec_list_make_empty(&block->instr_list);
 282
 283    return block;
 284 }
 285
 286 static inline void
 287 src_init(nir_src *src)
 288 {
 289    src->is_ssa = false;
 290    src->reg.reg = NULL;
 291    src->reg.indirect = NULL;
 292    src->reg.base_offset = 0;
 293 }
 294
 295 nir_if *
 296 nir_if_create(void *mem_ctx)
 297 {
 298    nir_if *if_stmt = ralloc(mem_ctx, nir_if);
 299
 300    cf_init(&if_stmt->cf_node, nir_cf_node_if);
 301    src_init(&if_stmt->condition);
 302
 303    nir_block *then = nir_block_create(mem_ctx);
 304    exec_list_make_empty(&if_stmt->then_list);
 305    exec_list_push_tail(&if_stmt->then_list, &then->cf_node.node);
 306    then->cf_node.parent = &if_stmt->cf_node;
 307
 308    nir_block *else_stmt = nir_block_create(mem_ctx);
 309    exec_list_make_empty(&if_stmt->else_list);
 310    exec_list_push_tail(&if_stmt->else_list, &else_stmt->cf_node.node);
 311    else_stmt->cf_node.parent = &if_stmt->cf_node;
 312
 313    return if_stmt;
 314 }
 315
 316 nir_loop *
 317 nir_loop_create(void *mem_ctx)
 318 {
 319    nir_loop *loop = ralloc(mem_ctx, nir_loop);
 320
 321    cf_init(&loop->cf_node, nir_cf_node_loop);
 322
 323    nir_block *body = nir_block_create(mem_ctx);
 324    exec_list_make_empty(&loop->body);
 325    exec_list_push_tail(&loop->body, &body->cf_node.node);
 326    body->cf_node.parent = &loop->cf_node;
 327
 328    body->successors[0] = body;
 329    block_add_pred(body, body);
 330
 331    return loop;
 332 }
 333
 334 static void
 335 instr_init(nir_instr *instr, nir_instr_type type)
 336 {
 337    instr->type = type;
 338    instr->block = NULL;
 339    exec_node_init(&instr->node);
 340 }
 341
 342 static void
 343 dest_init(nir_dest *dest)
 344 {
 345    dest->is_ssa = false;
 346    dest->reg.reg = NULL;
 347    dest->reg.indirect = NULL;
 348    dest->reg.base_offset = 0;
 349 }
 350
 351 static void
 352 alu_dest_init(nir_alu_dest *dest)
 353 {
 354    dest_init(&dest->dest);
 355    dest->saturate = false;
 356    dest->write_mask = 0xf;
 357 }
 358
 359 static void
 360 alu_src_init(nir_alu_src *src)
 361 {
 362    src_init(&src->src);
 363    src->abs = src->negate = false;
 364    src->swizzle[0] = 0;
 365    src->swizzle[1] = 1;
 366    src->swizzle[2] = 2;
 367    src->swizzle[3] = 3;
 368 }
 369
 370 nir_alu_instr *
 371 nir_alu_instr_create(void *mem_ctx, nir_op op)
 372 {
 373    unsigned num_srcs = nir_op_infos[op].num_inputs;
 374    nir_alu_instr *instr =
 375       ralloc_size(mem_ctx,
 376                   sizeof(nir_alu_instr) + num_srcs * sizeof(nir_alu_src));
 377
 378    instr_init(&instr->instr, nir_instr_type_alu);
 379    instr->op = op;
 380    alu_dest_init(&instr->dest);
 381    for (unsigned i = 0; i < num_srcs; i++)
 382       alu_src_init(&instr->src[i]);
 383
 384    return instr;
 385 }
 386
 387 nir_jump_instr *
 388 nir_jump_instr_create(void *mem_ctx, nir_jump_type type)
 389 {
 390    nir_jump_instr *instr = ralloc(mem_ctx, nir_jump_instr);
 391    instr_init(&instr->instr, nir_instr_type_jump);
 392    instr->type = type;
 393    return instr;
 394 }
 395
 396 nir_load_const_instr *
 397 nir_load_const_instr_create(void *mem_ctx)
 398 {
 399    nir_load_const_instr *instr = ralloc(mem_ctx, nir_load_const_instr);
 400    instr_init(&instr->instr, nir_instr_type_load_const);
 401
 402    dest_init(&instr->dest);
 403    instr->num_components = 0;
 404    instr->array_elems = 0;
 405
 406    return instr;
 407 }
 408
 409 nir_intrinsic_instr *
 410 nir_intrinsic_instr_create(void *mem_ctx, nir_intrinsic_op op)
 411 {
 412    unsigned num_srcs = nir_intrinsic_infos[op].num_srcs;
 413    nir_intrinsic_instr *instr =
 414       ralloc_size(mem_ctx,
 415                   sizeof(nir_intrinsic_instr) + num_srcs * sizeof(nir_src));
 416
 417    instr_init(&instr->instr, nir_instr_type_intrinsic);
 418    instr->intrinsic = op;
 419
 420    if (nir_intrinsic_infos[op].has_dest)
 421       dest_init(&instr->dest);
 422
 423    for (unsigned i = 0; i < num_srcs; i++)
 424       src_init(&instr->src[i]);
 425
 426    return instr;
 427 }
 428
 429 nir_call_instr *
 430 nir_call_instr_create(void *mem_ctx, nir_function_overload *callee)
 431 {
 432    nir_call_instr *instr = ralloc(mem_ctx, nir_call_instr);
 433    instr_init(&instr->instr, nir_instr_type_call);
 434
 435    instr->callee = callee;
 436    instr->num_params = callee->num_params;
 437    instr->params = ralloc_array(mem_ctx, nir_deref_var *, instr->num_params);
 438    instr->return_deref = NULL;
 439
 440    return instr;
 441 }
 442
 443 nir_tex_instr *
 444 nir_tex_instr_create(void *mem_ctx, unsigned num_srcs)
 445 {
 446    nir_tex_instr *instr = ralloc(mem_ctx, nir_tex_instr);
 447    instr_init(&instr->instr, nir_instr_type_tex);
 448
 449    dest_init(&instr->dest);
 450
 451    instr->num_srcs = num_srcs;
 452    for (unsigned i = 0; i < 4; i++)
 453       src_init(&instr->src[i]);
 454
 455    instr->sampler_index = 0;
 456    instr->sampler_array_size = 0;
 457    instr->sampler = NULL;
 458
 459    return instr;
 460 }
 461
 462 nir_phi_instr *
 463 nir_phi_instr_create(void *mem_ctx)
 464 {
 465    nir_phi_instr *instr = ralloc(mem_ctx, nir_phi_instr);
 466    instr_init(&instr->instr, nir_instr_type_phi);
 467
 468    dest_init(&instr->dest);
 469    exec_list_make_empty(&instr->srcs);
 470    return instr;
 471 }
 472
 473 nir_parallel_copy_instr *
 474 nir_parallel_copy_instr_create(void *mem_ctx)
 475 {
 476    nir_parallel_copy_instr *instr = ralloc(mem_ctx, nir_parallel_copy_instr);
 477    instr_init(&instr->instr, nir_instr_type_parallel_copy);
 478
 479    instr->at_end = false;
 480    exec_list_make_empty(&instr->copies);
 481
 482    return instr;
 483 }
 484
 485 nir_ssa_undef_instr *
 486 nir_ssa_undef_instr_create(void *mem_ctx)
 487 {
 488    nir_ssa_undef_instr *instr = ralloc(mem_ctx, nir_ssa_undef_instr);
 489    instr_init(&instr->instr, nir_instr_type_ssa_undef);
 490
 491    instr->def.name = NULL;
 492    instr->def.parent_instr = &instr->instr;
 493
 494    return instr;
 495 }
 496
 497 nir_deref_var *
 498 nir_deref_var_create(void *mem_ctx, nir_variable *var)
 499 {
 500    nir_deref_var *deref = ralloc(mem_ctx, nir_deref_var);
 501    deref->deref.deref_type = nir_deref_type_var;
 502    deref->deref.child = NULL;
 503    deref->deref.type = var->type;
 504    deref->var = var;
 505    return deref;
 506 }
 507
 508 nir_deref_array *
 509 nir_deref_array_create(void *mem_ctx)
 510 {
 511    nir_deref_array *deref = ralloc(mem_ctx, nir_deref_array);
 512    deref->deref.deref_type = nir_deref_type_array;
 513    deref->deref.child = NULL;
 514    deref->deref_array_type = nir_deref_array_type_direct;
 515    src_init(&deref->indirect);
 516    deref->base_offset = 0;
 517    return deref;
 518 }
 519
 520 nir_deref_struct *
 521 nir_deref_struct_create(void *mem_ctx, unsigned field_index)
 522 {
 523    nir_deref_struct *deref = ralloc(mem_ctx, nir_deref_struct);
 524    deref->deref.deref_type = nir_deref_type_struct;
 525    deref->deref.child = NULL;
 526    deref->index = field_index;
 527    return deref;
 528 }
 529
 530 static nir_deref_var *
 531 copy_deref_var(void *mem_ctx, nir_deref_var *deref)
 532 {
 533    nir_deref_var *ret = nir_deref_var_create(mem_ctx, deref->var);
 534    ret->deref.type = deref->deref.type;
 535    if (deref->deref.child)
 536       ret->deref.child = nir_copy_deref(mem_ctx, deref->deref.child);
 537    return ret;
 538 }
 539
 540 static nir_deref_array *
 541 copy_deref_array(void *mem_ctx, nir_deref_array *deref)
 542 {
 543    nir_deref_array *ret = nir_deref_array_create(mem_ctx);
 544    ret->base_offset = deref->base_offset;
 545    ret->deref_array_type = deref->deref_array_type;
 546    if (deref->deref_array_type == nir_deref_array_type_indirect) {
 547       ret->indirect = nir_src_copy(deref->indirect, mem_ctx);
 548    }
 549    ret->deref.type = deref->deref.type;
 550    if (deref->deref.child)
 551       ret->deref.child = nir_copy_deref(mem_ctx, deref->deref.child);
 552    return ret;
 553 }
 554
 555 static nir_deref_struct *
 556 copy_deref_struct(void *mem_ctx, nir_deref_struct *deref)
 557 {
 558    nir_deref_struct *ret = nir_deref_struct_create(mem_ctx, deref->index);
 559    ret->deref.type = deref->deref.type;
 560    if (deref->deref.child)
 561       ret->deref.child = nir_copy_deref(mem_ctx, deref->deref.child);
 562    return ret;
 563 }
 564
 565 nir_deref *
 566 nir_copy_deref(void *mem_ctx, nir_deref *deref)
 567 {
 568    switch (deref->deref_type) {
 569    case nir_deref_type_var:
 570       return &copy_deref_var(mem_ctx, nir_deref_as_var(deref))->deref;
 571    case nir_deref_type_array:
 572       return &copy_deref_array(mem_ctx, nir_deref_as_array(deref))->deref;
 573    case nir_deref_type_struct:
 574       return &copy_deref_struct(mem_ctx, nir_deref_as_struct(deref))->deref;
 575    default:
 576       unreachable("Invalid dereference type");
 577    }
 578
 579    return NULL;
 580 }
 581
 582
 583 /**
 584  * \name Control flow modification
 585  *
 586  * These functions modify the control flow tree while keeping the control flow
 587  * graph up-to-date. The invariants respected are:
 588  * 1. Each then statement, else statement, or loop body must have at least one
 589  *    control flow node.
 590  * 2. Each if-statement and loop must have one basic block before it and one
 591  *    after.
 592  * 3. Two basic blocks cannot be directly next to each other.
 593  * 4. If a basic block has a jump instruction, there must be only one and it
 594  *    must be at the end of the block.
 595  * 5. The CFG must always be connected - this means that we must insert a fake
 596  *    CFG edge for loops with no break statement.
 597  *
 598  * The purpose of the second one is so that we have places to insert code during
 599  * GCM, as well as eliminating the possibility of critical edges.
 600  */
 601 /*@{*/
 602
 603 static void
 604 link_non_block_to_block(nir_cf_node *node, nir_block *block)
 605 {
 606    if (node->type == nir_cf_node_if) {
 607       /*
 608        * We're trying to link an if to a block after it; this just means linking
 609        * the last block of the then and else branches.
 610        */
 611
 612       nir_if *if_stmt = nir_cf_node_as_if(node);
 613
 614       nir_cf_node *last_then = nir_if_last_then_node(if_stmt);
 615       assert(last_then->type == nir_cf_node_block);
 616       nir_block *last_then_block = nir_cf_node_as_block(last_then);
 617
 618       nir_cf_node *last_else = nir_if_last_else_node(if_stmt);
 619       assert(last_else->type == nir_cf_node_block);
 620       nir_block *last_else_block = nir_cf_node_as_block(last_else);
 621
 622       if (exec_list_is_empty(&last_then_block->instr_list) ||
 623           nir_block_last_instr(last_then_block)->type != nir_instr_type_jump) {
 624          unlink_block_successors(last_then_block);
 625          link_blocks(last_then_block, block, NULL);
 626       }
 627
 628       if (exec_list_is_empty(&last_else_block->instr_list) ||
 629           nir_block_last_instr(last_else_block)->type != nir_instr_type_jump) {
 630          unlink_block_successors(last_else_block);
 631          link_blocks(last_else_block, block, NULL);
 632       }
 633    } else {
 634       assert(node->type == nir_cf_node_loop);
 635
 636       /*
 637        * We can only get to this codepath if we're inserting a new loop, or
 638        * at least a loop with no break statements; we can't insert break
 639        * statements into a loop when we haven't inserted it into the CFG
 640        * because we wouldn't know which block comes after the loop
 641        * and therefore, which block should be the successor of the block with
 642        * the break). Therefore, we need to insert a fake edge (see invariant
 643        * #5).
 644        */
 645
 646       nir_loop *loop = nir_cf_node_as_loop(node);
 647
 648       nir_cf_node *last = nir_loop_last_cf_node(loop);
 649       assert(last->type == nir_cf_node_block);
 650       nir_block *last_block =  nir_cf_node_as_block(last);
 651
 652       last_block->successors[1] = block;
 653       block_add_pred(block, last_block);
 654    }
 655 }
 656
 657 static void
 658 link_block_to_non_block(nir_block *block, nir_cf_node *node)
 659 {
 660    if (node->type == nir_cf_node_if) {
 661       /*
 662        * We're trying to link a block to an if after it; this just means linking
 663        * the block to the first block of the then and else branches.
 664        */
 665
 666       nir_if *if_stmt = nir_cf_node_as_if(node);
 667
 668       nir_cf_node *first_then = nir_if_first_then_node(if_stmt);
 669       assert(first_then->type == nir_cf_node_block);
 670       nir_block *first_then_block = nir_cf_node_as_block(first_then);
 671
 672       nir_cf_node *first_else = nir_if_first_else_node(if_stmt);
 673       assert(first_else->type == nir_cf_node_block);
 674       nir_block *first_else_block = nir_cf_node_as_block(first_else);
 675
 676       unlink_block_successors(block);
 677       link_blocks(block, first_then_block, first_else_block);
 678    } else {
 679       /*
 680        * For similar reasons as the corresponding case in
 681        * link_non_block_to_block(), don't worry about if the loop header has
 682        * any predecessors that need to be unlinked.
 683        */
 684
 685       assert(node->type == nir_cf_node_loop);
 686
 687       nir_loop *loop = nir_cf_node_as_loop(node);
 688
 689       nir_cf_node *loop_header = nir_loop_first_cf_node(loop);
 690       assert(loop_header->type == nir_cf_node_block);
 691       nir_block *loop_header_block = nir_cf_node_as_block(loop_header);
 692
 693       unlink_block_successors(block);
 694       link_blocks(block, loop_header_block, NULL);
 695    }
 696
 697 }
 698
 699 /**
 700  * Takes a basic block and inserts a new empty basic block before it, making its
 701  * predecessors point to the new block. This essentially splits the block into
 702  * an empty header and a body so that another non-block CF node can be inserted
 703  * between the two. Note that this does *not* link the two basic blocks, so
 704  * some kind of cleanup *must* be performed after this call.
 705  */
 706
 707 static nir_block *
 708 split_block_beginning(nir_block *block)
 709 {
 710    nir_block *new_block = nir_block_create(ralloc_parent(block));
 711    new_block->cf_node.parent = block->cf_node.parent;
 712    exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node);
 713
 714    struct set_entry *entry;
 715    set_foreach(block->predecessors, entry) {
 716       nir_block *pred = (nir_block *) entry->key;
 717
 718       unlink_blocks(pred, block);
 719       link_blocks(pred, new_block, NULL);
 720    }
 721
 722    return new_block;
 723 }
 724
 725 static void
 726 rewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred)
 727 {
 728    nir_foreach_instr_safe(block, instr) {
 729       if (instr->type != nir_instr_type_phi)
 730          break;
 731
 732       nir_phi_instr *phi = nir_instr_as_phi(instr);
 733       foreach_list_typed_safe(nir_phi_src, src, node, &phi->srcs) {
 734          if (src->pred == old_pred) {
 735             src->pred = new_pred;
 736             break;
 737          }
 738       }
 739    }
 740 }
 741
 742 /**
 743  * Moves the successors of source to the successors of dest, leaving both
 744  * successors of source NULL.
 745  */
 746
 747 static void
 748 move_successors(nir_block *source, nir_block *dest)
 749 {
 750    nir_block *succ1 = source->successors[0];
 751    nir_block *succ2 = source->successors[1];
 752
 753    if (succ1) {
 754       unlink_blocks(source, succ1);
 755       rewrite_phi_preds(succ1, source, dest);
 756    }
 757
 758    if (succ2) {
 759       unlink_blocks(source, succ2);
 760       rewrite_phi_preds(succ2, source, dest);
 761    }
 762
 763    unlink_block_successors(dest);
 764    link_blocks(dest, succ1, succ2);
 765 }
 766
 767 static nir_block *
 768 split_block_end(nir_block *block)
 769 {
 770    nir_block *new_block = nir_block_create(ralloc_parent(block));
 771    new_block->cf_node.parent = block->cf_node.parent;
 772    exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node);
 773
 774    move_successors(block, new_block);
 775
 776    return new_block;
 777 }
 778
 779 /**
 780  * Inserts a non-basic block between two basic blocks and links them together.
 781  */
 782
 783 static void
 784 insert_non_block(nir_block *before, nir_cf_node *node, nir_block *after)
 785 {
 786    node->parent = before->cf_node.parent;
 787    exec_node_insert_after(&before->cf_node.node, &node->node);
 788    link_block_to_non_block(before, node);
 789    link_non_block_to_block(node, after);
 790 }
 791
 792 /**
 793  * Inserts a non-basic block before a basic block.
 794  */
 795
 796 static void
 797 insert_non_block_before_block(nir_cf_node *node, nir_block *block)
 798 {
 799    /* split off the beginning of block into new_block */
 800    nir_block *new_block = split_block_beginning(block);
 801
 802    /* insert our node in between new_block and block */
 803    insert_non_block(new_block, node, block);
 804 }
 805
 806 static void
 807 insert_non_block_after_block(nir_block *block, nir_cf_node *node)
 808 {
 809    /* split off the end of block into new_block */
 810    nir_block *new_block = split_block_end(block);
 811
 812    /* insert our node in between block and new_block */
 813    insert_non_block(block, node, new_block);
 814 }
 815
 816 /* walk up the control flow tree to find the innermost enclosed loop */
 817 static nir_loop *
 818 nearest_loop(nir_cf_node *node)
 819 {
 820    while (node->type != nir_cf_node_loop) {
 821       node = node->parent;
 822    }
 823
 824    return nir_cf_node_as_loop(node);
 825 }
 826
 827 nir_function_impl *
 828 nir_cf_node_get_function(nir_cf_node *node)
 829 {
 830    while (node->type != nir_cf_node_function) {
 831       node = node->parent;
 832    }
 833
 834    return nir_cf_node_as_function(node);
 835 }
 836
 837 /*
 838  * update the CFG after a jump instruction has been added to the end of a block
 839  */
 840
 841 static void
 842 handle_jump(nir_block *block)
 843 {
 844    nir_instr *instr = nir_block_last_instr(block);
 845    nir_jump_instr *jump_instr = nir_instr_as_jump(instr);
 846
 847    unlink_block_successors(block);
 848
 849    nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
 850    nir_metadata_preserve(impl, nir_metadata_none);
 851
 852    if (jump_instr->type == nir_jump_break ||
 853        jump_instr->type == nir_jump_continue) {
 854       nir_loop *loop = nearest_loop(&block->cf_node);
 855
 856       if (jump_instr->type == nir_jump_continue) {
 857          nir_cf_node *first_node = nir_loop_first_cf_node(loop);
 858          assert(first_node->type == nir_cf_node_block);
 859          nir_block *first_block = nir_cf_node_as_block(first_node);
 860          link_blocks(block, first_block, NULL);
 861       } else {
 862          nir_cf_node *after = nir_cf_node_next(&loop->cf_node);
 863          assert(after->type == nir_cf_node_block);
 864          nir_block *after_block = nir_cf_node_as_block(after);
 865          link_blocks(block, after_block, NULL);
 866
 867          /* If we inserted a fake link, remove it */
 868          nir_cf_node *last = nir_loop_last_cf_node(loop);
 869          assert(last->type == nir_cf_node_block);
 870          nir_block *last_block =  nir_cf_node_as_block(last);
 871          if (last_block->successors[1] != NULL)
 872             unlink_blocks(last_block, after_block);
 873       }
 874    } else {
 875       assert(jump_instr->type == nir_jump_return);
 876       link_blocks(block, impl->end_block, NULL);
 877    }
 878 }
 879
 880 static void
 881 handle_remove_jump(nir_block *block, nir_jump_type type)
 882 {
 883    unlink_block_successors(block);
 884
 885    if (exec_node_is_tail_sentinel(block->cf_node.node.next)) {
 886       nir_cf_node *parent = block->cf_node.parent;
 887       if (parent->type == nir_cf_node_if) {
 888          nir_cf_node *next = nir_cf_node_next(parent);
 889          assert(next->type == nir_cf_node_block);
 890          nir_block *next_block = nir_cf_node_as_block(next);
 891
 892          link_blocks(block, next_block, NULL);
 893       } else {
 894          assert(parent->type == nir_cf_node_loop);
 895          nir_loop *loop = nir_cf_node_as_loop(parent);
 896
 897          nir_cf_node *head = nir_loop_first_cf_node(loop);
 898          assert(head->type == nir_cf_node_block);
 899          nir_block *head_block = nir_cf_node_as_block(head);
 900
 901          link_blocks(block, head_block, NULL);
 902       }
 903    } else {
 904       nir_cf_node *next = nir_cf_node_next(&block->cf_node);
 905       if (next->type == nir_cf_node_if) {
 906          nir_if *next_if = nir_cf_node_as_if(next);
 907
 908          nir_cf_node *first_then = nir_if_first_then_node(next_if);
 909          assert(first_then->type == nir_cf_node_block);
 910          nir_block *first_then_block = nir_cf_node_as_block(first_then);
 911
 912          nir_cf_node *first_else = nir_if_first_else_node(next_if);
 913          assert(first_else->type == nir_cf_node_block);
 914          nir_block *first_else_block = nir_cf_node_as_block(first_else);
 915
 916          link_blocks(block, first_then_block, first_else_block);
 917       } else {
 918          assert(next->type == nir_cf_node_loop);
 919          nir_loop *next_loop = nir_cf_node_as_loop(next);
 920
 921          nir_cf_node *first = nir_loop_first_cf_node(next_loop);
 922          assert(first->type == nir_cf_node_block);
 923          nir_block *first_block = nir_cf_node_as_block(first);
 924
 925          link_blocks(block, first_block, NULL);
 926       }
 927    }
 928
 929    if (type == nir_jump_break) {
 930       nir_loop *loop = nearest_loop(&block->cf_node);
 931
 932       nir_cf_node *next = nir_cf_node_next(&loop->cf_node);
 933       assert(next->type == nir_cf_node_block);
 934       nir_block *next_block = nir_cf_node_as_block(next);
 935
 936       if (next_block->predecessors->entries == 0) {
 937          /* insert fake link */
 938          nir_cf_node *last = nir_loop_last_cf_node(loop);
 939          assert(last->type == nir_cf_node_block);
 940          nir_block *last_block = nir_cf_node_as_block(last);
 941
 942          last_block->successors[1] = next_block;
 943          block_add_pred(next_block, last_block);
 944       }
 945    }
 946
 947    nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
 948    nir_metadata_preserve(impl, nir_metadata_none);
 949 }
 950
 951 /**
 952  * Inserts a basic block before another by merging the instructions.
 953  *
 954  * @param block the target of the insertion
 955  * @param before the block to be inserted - must not have been inserted before
 956  * @param has_jump whether \before has a jump instruction at the end
 957  */
 958
 959 static void
 960 insert_block_before_block(nir_block *block, nir_block *before, bool has_jump)
 961 {
 962    assert(!has_jump || exec_list_is_empty(&block->instr_list));
 963
 964    foreach_list_typed(nir_instr, instr, node, &before->instr_list) {
 965       instr->block = block;
 966    }
 967
 968    exec_list_prepend(&block->instr_list, &before->instr_list);
 969
 970    if (has_jump)
 971       handle_jump(block);
 972 }
 973
 974 /**
 975  * Inserts a basic block after another by merging the instructions.
 976  *
 977  * @param block the target of the insertion
 978  * @param after the block to be inserted - must not have been inserted before
 979  * @param has_jump whether \after has a jump instruction at the end
 980  */
 981
 982 static void
 983 insert_block_after_block(nir_block *block, nir_block *after, bool has_jump)
 984 {
 985    foreach_list_typed(nir_instr, instr, node, &after->instr_list) {
 986       instr->block = block;
 987    }
 988
 989    exec_list_append(&block->instr_list, &after->instr_list);
 990
 991    if (has_jump)
 992       handle_jump(block);
 993 }
 994
 995 static void
 996 update_if_uses(nir_cf_node *node)
 997 {
 998    if (node->type != nir_cf_node_if)
 999       return;
1000
1001    nir_if *if_stmt = nir_cf_node_as_if(node);
1002
1003    struct set *if_uses_set = if_stmt->condition.is_ssa ?
1004                              if_stmt->condition.ssa->if_uses :
1005                              if_stmt->condition.reg.reg->uses;
1006
1007    _mesa_set_add(if_uses_set, _mesa_hash_pointer(if_stmt), if_stmt);
1008 }
1009
1010 void
1011 nir_cf_node_insert_after(nir_cf_node *node, nir_cf_node *after)
1012 {
1013    update_if_uses(after);
1014
1015    if (after->type == nir_cf_node_block) {
1016       /*
1017        * either node or the one after it must be a basic block, by invariant #2;
1018        * in either case, just merge the blocks together.
1019        */
1020       nir_block *after_block = nir_cf_node_as_block(after);
1021
1022       bool has_jump = !exec_list_is_empty(&after_block->instr_list) &&
1023          nir_block_last_instr(after_block)->type == nir_instr_type_jump;
1024
1025       if (node->type == nir_cf_node_block) {
1026          insert_block_after_block(nir_cf_node_as_block(node), after_block,
1027                                   has_jump);
1028       } else {
1029          nir_cf_node *next = nir_cf_node_next(node);
1030          assert(next->type == nir_cf_node_block);
1031          nir_block *next_block = nir_cf_node_as_block(next);
1032
1033          insert_block_before_block(next_block, after_block, has_jump);
1034       }
1035    } else {
1036       if (node->type == nir_cf_node_block) {
1037          insert_non_block_after_block(nir_cf_node_as_block(node), after);
1038       } else {
1039          /*
1040           * We have to insert a non-basic block after a non-basic block. Since
1041           * every non-basic block has a basic block after it, this is equivalent
1042           * to inserting a non-basic block before a basic block.
1043           */
1044
1045          nir_cf_node *next = nir_cf_node_next(node);
1046          assert(next->type == nir_cf_node_block);
1047          nir_block *next_block = nir_cf_node_as_block(next);
1048
1049          insert_non_block_before_block(after, next_block);
1050       }
1051    }
1052
1053    nir_function_impl *impl = nir_cf_node_get_function(node);
1054    nir_metadata_preserve(impl, nir_metadata_none);
1055 }
1056
1057 void
1058 nir_cf_node_insert_before(nir_cf_node *node, nir_cf_node *before)
1059 {
1060    update_if_uses(before);
1061
1062    if (before->type == nir_cf_node_block) {
1063       nir_block *before_block = nir_cf_node_as_block(before);
1064
1065       bool has_jump = !exec_list_is_empty(&before_block->instr_list) &&
1066          nir_block_last_instr(before_block)->type == nir_instr_type_jump;
1067
1068       if (node->type == nir_cf_node_block) {
1069          insert_block_before_block(nir_cf_node_as_block(node), before_block,
1070                                    has_jump);
1071       } else {
1072          nir_cf_node *prev = nir_cf_node_prev(node);
1073          assert(prev->type == nir_cf_node_block);
1074          nir_block *prev_block = nir_cf_node_as_block(prev);
1075
1076          insert_block_after_block(prev_block, before_block, has_jump);
1077       }
1078    } else {
1079       if (node->type == nir_cf_node_block) {
1080          insert_non_block_before_block(before, nir_cf_node_as_block(node));
1081       } else {
1082          /*
1083           * We have to insert a non-basic block before a non-basic block. This
1084           * is equivalent to inserting a non-basic block after a basic block.
1085           */
1086
1087          nir_cf_node *prev_node = nir_cf_node_prev(node);
1088          assert(prev_node->type == nir_cf_node_block);
1089          nir_block *prev_block = nir_cf_node_as_block(prev_node);
1090
1091          insert_non_block_after_block(prev_block, before);
1092       }
1093    }
1094
1095    nir_function_impl *impl = nir_cf_node_get_function(node);
1096    nir_metadata_preserve(impl, nir_metadata_none);
1097 }
1098
1099 void
1100 nir_cf_node_insert_begin(struct exec_list *list, nir_cf_node *node)
1101 {
1102    nir_cf_node *begin = exec_node_data(nir_cf_node, list->head, node);
1103    nir_cf_node_insert_before(begin, node);
1104 }
1105
1106 void
1107 nir_cf_node_insert_end(struct exec_list *list, nir_cf_node *node)
1108 {
1109    nir_cf_node *end = exec_node_data(nir_cf_node, list->tail_pred, node);
1110    nir_cf_node_insert_after(end, node);
1111 }
1112
1113 /**
1114  * Stitch two basic blocks together into one. The aggregate must have the same
1115  * predecessors as the first and the same successors as the second.
1116  */
1117
1118 static void
1119 stitch_blocks(nir_block *before, nir_block *after)
1120 {
1121    /*
1122     * We move after into before, so we have to deal with up to 2 successors vs.
1123     * possibly a large number of predecessors.
1124     *
1125     * TODO: special case when before is empty and after isn't?
1126     */
1127
1128    move_successors(after, before);
1129
1130    foreach_list_typed(nir_instr, instr, node, &after->instr_list) {
1131       instr->block = before;
1132    }
1133
1134    exec_list_append(&before->instr_list, &after->instr_list);
1135    exec_node_remove(&after->cf_node.node);
1136 }
1137
1138 void
1139 nir_cf_node_remove(nir_cf_node *node)
1140 {
1141    nir_function_impl *impl = nir_cf_node_get_function(node);
1142    nir_metadata_preserve(impl, nir_metadata_none);
1143
1144    if (node->type == nir_cf_node_block) {
1145       /*
1146        * Basic blocks can't really be removed by themselves, since they act as
1147        * padding between the non-basic blocks. So all we do here is empty the
1148        * block of instructions.
1149        *
1150        * TODO: could we assert here?
1151        */
1152       exec_list_make_empty(&nir_cf_node_as_block(node)->instr_list);
1153    } else {
1154       nir_cf_node *before = nir_cf_node_prev(node);
1155       assert(before->type == nir_cf_node_block);
1156       nir_block *before_block = nir_cf_node_as_block(before);
1157
1158       nir_cf_node *after = nir_cf_node_next(node);
1159       assert(after->type == nir_cf_node_block);
1160       nir_block *after_block = nir_cf_node_as_block(after);
1161
1162       exec_node_remove(&node->node);
1163       stitch_blocks(before_block, after_block);
1164    }
1165 }
1166
1167 static bool
1168 add_use_cb(nir_src *src, void *state)
1169 {
1170    nir_instr *instr = (nir_instr *) state;
1171
1172    struct set *uses_set = src->is_ssa ? src->ssa->uses : src->reg.reg->uses;
1173
1174    _mesa_set_add(uses_set, _mesa_hash_pointer(instr), instr);
1175
1176    return true;
1177 }
1178
1179 static void
1180 add_ssa_def(nir_instr *instr, nir_ssa_def *def)
1181 {
1182    if (instr->block && def->index == UINT_MAX) {
1183       nir_function_impl *impl =
1184          nir_cf_node_get_function(&instr->block->cf_node);
1185
1186       def->index = impl->ssa_alloc++;
1187    }
1188 }
1189
1190 static bool
1191 add_def_cb(nir_dest *dest, void *state)
1192 {
1193    nir_instr *instr = (nir_instr *) state;
1194
1195    if (dest->is_ssa) {
1196       add_ssa_def(instr, &dest->ssa);
1197    } else {
1198       _mesa_set_add(dest->reg.reg->defs, _mesa_hash_pointer(instr), instr);
1199    }
1200
1201    return true;
1202 }
1203
1204 static void
1205 add_defs_uses(nir_instr *instr)
1206 {
1207    if (instr->type == nir_instr_type_ssa_undef) {
1208       add_ssa_def(instr, &nir_instr_as_ssa_undef(instr)->def);
1209    } else {
1210       nir_foreach_src(instr, add_use_cb, instr);
1211       nir_foreach_dest(instr, add_def_cb, instr);
1212    }
1213 }
1214
1215 void
1216 nir_instr_insert_before(nir_instr *instr, nir_instr *before)
1217 {
1218    assert(before->type != nir_instr_type_jump);
1219    before->block = instr->block;
1220    add_defs_uses(before);
1221    exec_node_insert_node_before(&instr->node, &before->node);
1222 }
1223
1224 void
1225 nir_instr_insert_after(nir_instr *instr, nir_instr *after)
1226 {
1227    if (after->type == nir_instr_type_jump) {
1228       assert(instr == nir_block_last_instr(instr->block));
1229       assert(instr->type != nir_instr_type_jump);
1230    }
1231
1232    after->block = instr->block;
1233    add_defs_uses(after);
1234    exec_node_insert_after(&instr->node, &after->node);
1235
1236    if (after->type == nir_instr_type_jump)
1237       handle_jump(after->block);
1238 }
1239
1240 void
1241 nir_instr_insert_before_block(nir_block *block, nir_instr *before)
1242 {
1243    if (before->type == nir_instr_type_jump)
1244       assert(exec_list_is_empty(&block->instr_list));
1245
1246    before->block = block;
1247    add_defs_uses(before);
1248    exec_list_push_head(&block->instr_list, &before->node);
1249
1250    if (before->type == nir_instr_type_jump)
1251       handle_jump(block);
1252 }
1253
1254 void
1255 nir_instr_insert_after_block(nir_block *block, nir_instr *after)
1256 {
1257    if (after->type == nir_instr_type_jump) {
1258       assert(exec_list_is_empty(&block->instr_list) ||
1259              nir_block_last_instr(block)->type != nir_instr_type_jump);
1260    }
1261
1262    after->block = block;
1263    add_defs_uses(after);
1264    exec_list_push_tail(&block->instr_list, &after->node);
1265
1266    if (after->type == nir_instr_type_jump)
1267       handle_jump(block);
1268 }
1269
1270 void
1271 nir_instr_insert_before_cf(nir_cf_node *node, nir_instr *before)
1272 {
1273    if (node->type == nir_cf_node_block) {
1274       nir_instr_insert_before_block(nir_cf_node_as_block(node), before);
1275    } else {
1276       nir_cf_node *prev = nir_cf_node_prev(node);
1277       assert(prev->type == nir_cf_node_block);
1278       nir_block *prev_block = nir_cf_node_as_block(prev);
1279
1280       nir_instr_insert_before_block(prev_block, before);
1281    }
1282 }
1283
1284 void
1285 nir_instr_insert_after_cf(nir_cf_node *node, nir_instr *after)
1286 {
1287       if (node->type == nir_cf_node_block) {
1288       nir_instr_insert_after_block(nir_cf_node_as_block(node), after);
1289    } else {
1290       nir_cf_node *next = nir_cf_node_next(node);
1291       assert(next->type == nir_cf_node_block);
1292       nir_block *next_block = nir_cf_node_as_block(next);
1293
1294       nir_instr_insert_before_block(next_block, after);
1295    }
1296 }
1297
1298 void
1299 nir_instr_insert_before_cf_list(struct exec_list *list, nir_instr *before)
1300 {
1301    nir_cf_node *first_node = exec_node_data(nir_cf_node,
1302                                             exec_list_get_head(list), node);
1303    nir_instr_insert_before_cf(first_node, before);
1304 }
1305
1306 void
1307 nir_instr_insert_after_cf_list(struct exec_list *list, nir_instr *after)
1308 {
1309    nir_cf_node *last_node = exec_node_data(nir_cf_node,
1310                                            exec_list_get_tail(list), node);
1311    nir_instr_insert_after_cf(last_node, after);
1312 }
1313
1314 static bool
1315 remove_use_cb(nir_src *src, void *state)
1316 {
1317    nir_instr *instr = (nir_instr *) state;
1318
1319    struct set *uses_set = src->is_ssa ? src->ssa->uses : src->reg.reg->uses;
1320
1321    struct set_entry *entry = _mesa_set_search(uses_set,
1322                                               _mesa_hash_pointer(instr),
1323                                               instr);
1324    if (entry)
1325       _mesa_set_remove(uses_set, entry);
1326
1327    return true;
1328 }
1329
1330 static bool
1331 remove_def_cb(nir_dest *dest, void *state)
1332 {
1333    nir_instr *instr = (nir_instr *) state;
1334
1335    if (dest->is_ssa)
1336       return true;
1337
1338    nir_register *reg = dest->reg.reg;
1339
1340    struct set_entry *entry = _mesa_set_search(reg->defs,
1341                                               _mesa_hash_pointer(instr),
1342                                               instr);
1343    if (entry)
1344       _mesa_set_remove(reg->defs, entry);
1345
1346    return true;
1347 }
1348
1349 static void
1350 remove_defs_uses(nir_instr *instr)
1351 {
1352    nir_foreach_dest(instr, remove_def_cb, instr);
1353    nir_foreach_src(instr, remove_use_cb, instr);
1354 }
1355
1356 void nir_instr_remove(nir_instr *instr)
1357 {
1358    remove_defs_uses(instr);
1359    exec_node_remove(&instr->node);
1360
1361    if (instr->type == nir_instr_type_jump) {
1362       nir_jump_instr *jump_instr = nir_instr_as_jump(instr);
1363       handle_remove_jump(instr->block, jump_instr->type);
1364    }
1365 }
1366
1367 /*@}*/
1368
1369 void
1370 nir_index_local_regs(nir_function_impl *impl)
1371 {
1372    unsigned index = 0;
1373    foreach_list_typed(nir_register, reg, node, &impl->registers) {
1374       reg->index = index++;
1375    }
1376    impl->reg_alloc = index;
1377 }
1378
1379 void
1380 nir_index_global_regs(nir_shader *shader)
1381 {
1382    unsigned index = 0;
1383    foreach_list_typed(nir_register, reg, node, &shader->registers) {
1384       reg->index = index++;
1385    }
1386    shader->reg_alloc = index;
1387 }
1388
1389 static bool
1390 visit_alu_dest(nir_alu_instr *instr, nir_foreach_dest_cb cb, void *state)
1391 {
1392    return cb(&instr->dest.dest, state);
1393 }
1394
1395 static bool
1396 visit_intrinsic_dest(nir_intrinsic_instr *instr, nir_foreach_dest_cb cb,
1397                      void *state)
1398 {
1399    if (nir_intrinsic_infos[instr->intrinsic].has_dest)
1400       return cb(&instr->dest, state);
1401
1402    return true;
1403 }
1404
1405 static bool
1406 visit_texture_dest(nir_tex_instr *instr, nir_foreach_dest_cb cb,
1407                    void *state)
1408 {
1409    return cb(&instr->dest, state);
1410 }
1411
1412 static bool
1413 visit_load_const_dest(nir_load_const_instr *instr, nir_foreach_dest_cb cb,
1414                       void *state)
1415 {
1416    return cb(&instr->dest, state);
1417 }
1418
1419 static bool
1420 visit_phi_dest(nir_phi_instr *instr, nir_foreach_dest_cb cb, void *state)
1421 {
1422    return cb(&instr->dest, state);
1423 }
1424
1425 static bool
1426 visit_parallel_copy_dest(nir_parallel_copy_instr *instr,
1427                          nir_foreach_dest_cb cb, void *state)
1428 {
1429    foreach_list_typed(nir_parallel_copy_copy, copy, node, &instr->copies) {
1430       if (!cb(&copy->dest, state))
1431          return false;
1432    }
1433
1434    return true;
1435 }
1436
1437 bool
1438 nir_foreach_dest(nir_instr *instr, nir_foreach_dest_cb cb, void *state)
1439 {
1440    switch (instr->type) {
1441    case nir_instr_type_alu:
1442       return visit_alu_dest(nir_instr_as_alu(instr), cb, state);
1443    case nir_instr_type_intrinsic:
1444       return visit_intrinsic_dest(nir_instr_as_intrinsic(instr), cb, state);
1445    case nir_instr_type_tex:
1446       return visit_texture_dest(nir_instr_as_tex(instr), cb, state);
1447    case nir_instr_type_load_const:
1448       return visit_load_const_dest(nir_instr_as_load_const(instr), cb, state);
1449    case nir_instr_type_phi:
1450       return visit_phi_dest(nir_instr_as_phi(instr), cb, state);
1451    case nir_instr_type_parallel_copy:
1452       return visit_parallel_copy_dest(nir_instr_as_parallel_copy(instr),
1453                                       cb, state);
1454
1455    case nir_instr_type_ssa_undef:
1456    case nir_instr_type_call:
1457    case nir_instr_type_jump:
1458       break;
1459
1460    default:
1461       unreachable("Invalid instruction type");
1462       break;
1463    }
1464
1465    return true;
1466 }
1467
1468 struct foreach_ssa_def_state {
1469    nir_foreach_ssa_def_cb cb;
1470    void *client_state;
1471 };
1472
1473 static inline bool
1474 nir_ssa_def_visitor(nir_dest *dest, void *void_state)
1475 {
1476    struct foreach_ssa_def_state *state = void_state;
1477
1478    if (dest->is_ssa)
1479       return state->cb(&dest->ssa, state->client_state);
1480    else
1481       return true;
1482 }
1483
1484 bool
1485 nir_foreach_ssa_def(nir_instr *instr, nir_foreach_ssa_def_cb cb, void *state)
1486 {
1487    switch (instr->type) {
1488    case nir_instr_type_alu:
1489    case nir_instr_type_tex:
1490    case nir_instr_type_intrinsic:
1491    case nir_instr_type_load_const:
1492    case nir_instr_type_phi:
1493    case nir_instr_type_parallel_copy: {
1494       struct foreach_ssa_def_state foreach_state = {cb, state};
1495       return nir_foreach_dest(instr, nir_ssa_def_visitor, &foreach_state);
1496    }
1497
1498    case nir_instr_type_ssa_undef:
1499       return cb(&nir_instr_as_ssa_undef(instr)->def, state);
1500    case nir_instr_type_call:
1501    case nir_instr_type_jump:
1502       return true;
1503    default:
1504       unreachable("Invalid instruction type");
1505    }
1506 }
1507
1508 static bool
1509 visit_src(nir_src *src, nir_foreach_src_cb cb, void *state)
1510 {
1511    if (!cb(src, state))
1512       return false;
1513    if (!src->is_ssa && src->reg.indirect)
1514       return cb(src->reg.indirect, state);
1515    return true;
1516 }
1517
1518 static bool
1519 visit_deref_array_src(nir_deref_array *deref, nir_foreach_src_cb cb,
1520                       void *state)
1521 {
1522    if (deref->deref_array_type == nir_deref_array_type_indirect)
1523       return visit_src(&deref->indirect, cb, state);
1524    return true;
1525 }
1526
1527 static bool
1528 visit_deref_src(nir_deref_var *deref, nir_foreach_src_cb cb, void *state)
1529 {
1530    nir_deref *cur = &deref->deref;
1531    while (cur != NULL) {
1532       if (cur->deref_type == nir_deref_type_array)
1533          if (!visit_deref_array_src(nir_deref_as_array(cur), cb, state))
1534             return false;
1535
1536       cur = cur->child;
1537    }
1538
1539    return true;
1540 }
1541
1542 static bool
1543 visit_alu_src(nir_alu_instr *instr, nir_foreach_src_cb cb, void *state)
1544 {
1545    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++)
1546       if (!visit_src(&instr->src[i].src, cb, state))
1547          return false;
1548
1549    return true;
1550 }
1551
1552 static bool
1553 visit_tex_src(nir_tex_instr *instr, nir_foreach_src_cb cb, void *state)
1554 {
1555    for (unsigned i = 0; i < instr->num_srcs; i++)
1556       if (!visit_src(&instr->src[i], cb, state))
1557          return false;
1558
1559    if (instr->sampler != NULL)
1560       if (!visit_deref_src(instr->sampler, cb, state))
1561          return false;
1562
1563    return true;
1564 }
1565
1566 static bool
1567 visit_intrinsic_src(nir_intrinsic_instr *instr, nir_foreach_src_cb cb,
1568                     void *state)
1569 {
1570    unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
1571    for (unsigned i = 0; i < num_srcs; i++)
1572       if (!visit_src(&instr->src[i], cb, state))
1573          return false;
1574
1575    unsigned num_vars =
1576       nir_intrinsic_infos[instr->intrinsic].num_variables;
1577    for (unsigned i = 0; i < num_vars; i++)
1578       if (!visit_deref_src(instr->variables[i], cb, state))
1579          return false;
1580
1581    return true;
1582 }
1583
1584 static bool
1585 visit_call_src(nir_call_instr *instr, nir_foreach_src_cb cb, void *state)
1586 {
1587    return true;
1588 }
1589
1590 static bool
1591 visit_load_const_src(nir_load_const_instr *instr, nir_foreach_src_cb cb,
1592                      void *state)
1593 {
1594    return true;
1595 }
1596
1597 static bool
1598 visit_phi_src(nir_phi_instr *instr, nir_foreach_src_cb cb, void *state)
1599 {
1600    foreach_list_typed(nir_phi_src, src, node, &instr->srcs) {
1601       if (!visit_src(&src->src, cb, state))
1602          return false;
1603    }
1604
1605    return true;
1606 }
1607
1608 static bool
1609 visit_parallel_copy_src(nir_parallel_copy_instr *instr,
1610                         nir_foreach_src_cb cb, void *state)
1611 {
1612    foreach_list_typed(nir_parallel_copy_copy, copy, node, &instr->copies) {
1613       if (!visit_src(&copy->src, cb, state))
1614          return false;
1615    }
1616
1617    return true;
1618 }
1619
1620 typedef struct {
1621    void *state;
1622    nir_foreach_src_cb cb;
1623 } visit_dest_indirect_state;
1624
1625 static bool
1626 visit_dest_indirect(nir_dest *dest, void *_state)
1627 {
1628    visit_dest_indirect_state *state = (visit_dest_indirect_state *) _state;
1629
1630    if (!dest->is_ssa && dest->reg.indirect)
1631       return state->cb(dest->reg.indirect, state->state);
1632
1633    return true;
1634 }
1635
1636 bool
1637 nir_foreach_src(nir_instr *instr, nir_foreach_src_cb cb, void *state)
1638 {
1639    switch (instr->type) {
1640    case nir_instr_type_alu:
1641       if (!visit_alu_src(nir_instr_as_alu(instr), cb, state))
1642          return false;
1643       break;
1644    case nir_instr_type_intrinsic:
1645       if (!visit_intrinsic_src(nir_instr_as_intrinsic(instr), cb, state))
1646          return false;
1647       break;
1648    case nir_instr_type_tex:
1649       if (!visit_tex_src(nir_instr_as_tex(instr), cb, state))
1650          return false;
1651       break;
1652    case nir_instr_type_call:
1653       if (!visit_call_src(nir_instr_as_call(instr), cb, state))
1654          return false;
1655       break;
1656    case nir_instr_type_load_const:
1657       if (!visit_load_const_src(nir_instr_as_load_const(instr), cb, state))
1658          return false;
1659       break;
1660    case nir_instr_type_phi:
1661       if (!visit_phi_src(nir_instr_as_phi(instr), cb, state))
1662          return false;
1663       break;
1664    case nir_instr_type_parallel_copy:
1665       if (!visit_parallel_copy_src(nir_instr_as_parallel_copy(instr),
1666                                    cb, state))
1667          return false;
1668       break;
1669    case nir_instr_type_jump:
1670    case nir_instr_type_ssa_undef:
1671       return true;
1672
1673    default:
1674       unreachable("Invalid instruction type");
1675       break;
1676    }
1677
1678    visit_dest_indirect_state dest_state;
1679    dest_state.state = state;
1680    dest_state.cb = cb;
1681    return nir_foreach_dest(instr, visit_dest_indirect, &dest_state);
1682 }
1683
1684 nir_const_value *
1685 nir_src_as_const_value(nir_src src)
1686 {
1687    if (!src.is_ssa)
1688       return NULL;
1689
1690    if (src.ssa->parent_instr->type != nir_instr_type_load_const)
1691       return NULL;
1692
1693    nir_load_const_instr *load = nir_instr_as_load_const(src.ssa->parent_instr);
1694
1695    if (load->array_elems == 0)
1696       return &load->value;
1697    if (load->array_elems == 1)
1698       return load->array;
1699    else
1700       return NULL;
1701 }
1702
1703 bool
1704 nir_srcs_equal(nir_src src1, nir_src src2)
1705 {
1706    if (src1.is_ssa) {
1707       if (src2.is_ssa) {
1708          return src1.ssa == src2.ssa;
1709       } else {
1710          return false;
1711       }
1712    } else {
1713       if (src2.is_ssa) {
1714          return false;
1715       } else {
1716          if ((src1.reg.indirect == NULL) != (src2.reg.indirect == NULL))
1717             return false;
1718
1719          if (src1.reg.indirect) {
1720             if (!nir_srcs_equal(*src1.reg.indirect, *src2.reg.indirect))
1721                return false;
1722          }
1723
1724          return src1.reg.reg == src2.reg.reg &&
1725                 src1.reg.base_offset == src2.reg.base_offset;
1726       }
1727    }
1728 }
1729
1730 static bool
1731 src_does_not_use_def(nir_src *src, void *void_def)
1732 {
1733    nir_ssa_def *def = void_def;
1734
1735    if (src->is_ssa) {
1736       return src->ssa != def;
1737    } else {
1738       return true;
1739    }
1740 }
1741
1742 static bool
1743 src_does_not_use_reg(nir_src *src, void *void_reg)
1744 {
1745    nir_register *reg = void_reg;
1746
1747    if (src->is_ssa) {
1748       return true;
1749    } else {
1750       return src->reg.reg != reg;
1751    }
1752 }
1753
1754 void
1755 nir_instr_rewrite_src(nir_instr *instr, nir_src *src, nir_src new_src)
1756 {
1757    if (src->is_ssa) {
1758       nir_ssa_def *old_ssa = src->ssa;
1759       *src = new_src;
1760       if (old_ssa && nir_foreach_src(instr, src_does_not_use_def, old_ssa)) {
1761          struct set_entry *entry = _mesa_set_search(old_ssa->uses,
1762                                                     _mesa_hash_pointer(instr),
1763                                                     instr);
1764          assert(entry);
1765          _mesa_set_remove(old_ssa->uses, entry);
1766       }
1767    } else {
1768       if (src->reg.indirect)
1769          nir_instr_rewrite_src(instr, src->reg.indirect, new_src);
1770
1771       nir_register *old_reg = src->reg.reg;
1772       *src = new_src;
1773       if (old_reg && nir_foreach_src(instr, src_does_not_use_reg, old_reg)) {
1774          struct set_entry *entry = _mesa_set_search(old_reg->uses,
1775                                                     _mesa_hash_pointer(instr),
1776                                                     instr);
1777          assert(entry);
1778          _mesa_set_remove(old_reg->uses, entry);
1779       }
1780    }
1781
1782    if (new_src.is_ssa) {
1783       if (new_src.ssa)
1784          _mesa_set_add(new_src.ssa->uses, _mesa_hash_pointer(instr), instr);
1785    } else {
1786       if (new_src.reg.reg)
1787          _mesa_set_add(new_src.reg.reg->uses, _mesa_hash_pointer(instr), instr);
1788    }
1789 }
1790
1791 void
1792 nir_ssa_def_init(nir_instr *instr, nir_ssa_def *def,
1793                  unsigned num_components, const char *name)
1794 {
1795    void *mem_ctx = ralloc_parent(instr);
1796
1797    def->name = name;
1798    def->parent_instr = instr;
1799    def->uses = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
1800    def->if_uses = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
1801    def->num_components = num_components;
1802
1803    if (instr->block) {
1804       nir_function_impl *impl =
1805          nir_cf_node_get_function(&instr->block->cf_node);
1806
1807       def->index = impl->ssa_alloc++;
1808    } else {
1809       def->index = UINT_MAX;
1810    }
1811 }
1812
1813 struct ssa_def_rewrite_state {
1814    void *mem_ctx;
1815    nir_ssa_def *old;
1816    nir_src new_src;
1817 };
1818
1819 static bool
1820 ssa_def_rewrite_uses_src(nir_src *src, void *void_state)
1821 {
1822    struct ssa_def_rewrite_state *state = void_state;
1823
1824    if (src->is_ssa && src->ssa == state->old)
1825       *src = nir_src_copy(state->new_src, state->mem_ctx);
1826
1827    return true;
1828 }
1829
1830 void
1831 nir_ssa_def_rewrite_uses(nir_ssa_def *def, nir_src new_src, void *mem_ctx)
1832 {
1833    struct ssa_def_rewrite_state state;
1834    state.mem_ctx = mem_ctx;
1835    state.old = def;
1836    state.new_src = new_src;
1837
1838    assert(!new_src.is_ssa || def != new_src.ssa);
1839
1840    struct set *new_uses, *new_if_uses;
1841    if (new_src.is_ssa) {
1842       new_uses = new_src.ssa->uses;
1843       new_if_uses = new_src.ssa->if_uses;
1844    } else {
1845       new_uses = new_src.reg.reg->uses;
1846       new_if_uses = new_src.reg.reg->if_uses;
1847    }
1848
1849    struct set_entry *entry;
1850    set_foreach(def->uses, entry) {
1851       nir_instr *instr = (nir_instr *)entry->key;
1852
1853       _mesa_set_remove(def->uses, entry);
1854       nir_foreach_src(instr, ssa_def_rewrite_uses_src, &state);
1855       _mesa_set_add(new_uses, _mesa_hash_pointer(instr), instr);
1856    }
1857
1858    set_foreach(def->if_uses, entry) {
1859       nir_if *if_use = (nir_if *)entry->key;
1860
1861       _mesa_set_remove(def->if_uses, entry);
1862       if_use->condition = nir_src_copy(new_src, mem_ctx);
1863       _mesa_set_add(new_if_uses, _mesa_hash_pointer(if_use), if_use);
1864    }
1865 }
1866
1867
1868 static bool foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1869                             bool reverse, void *state);
1870
1871 static inline bool
1872 foreach_if(nir_if *if_stmt, nir_foreach_block_cb cb, bool reverse, void *state)
1873 {
1874    if (reverse) {
1875       foreach_list_typed_safe_reverse(nir_cf_node, node, node,
1876                                       &if_stmt->else_list) {
1877          if (!foreach_cf_node(node, cb, reverse, state))
1878             return false;
1879       }
1880
1881       foreach_list_typed_safe_reverse(nir_cf_node, node, node,
1882                                       &if_stmt->then_list) {
1883          if (!foreach_cf_node(node, cb, reverse, state))
1884             return false;
1885       }
1886    } else {
1887       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->then_list) {
1888          if (!foreach_cf_node(node, cb, reverse, state))
1889             return false;
1890       }
1891
1892       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list) {
1893          if (!foreach_cf_node(node, cb, reverse, state))
1894             return false;
1895       }
1896    }
1897
1898    return true;
1899 }
1900
1901 static inline bool
1902 foreach_loop(nir_loop *loop, nir_foreach_block_cb cb, bool reverse, void *state)
1903 {
1904    if (reverse) {
1905       foreach_list_typed_safe_reverse(nir_cf_node, node, node, &loop->body) {
1906          if (!foreach_cf_node(node, cb, reverse, state))
1907             return false;
1908       }
1909    } else {
1910       foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {
1911          if (!foreach_cf_node(node, cb, reverse, state))
1912             return false;
1913       }
1914    }
1915
1916    return true;
1917 }
1918
1919 static bool
1920 foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1921                 bool reverse, void *state)
1922 {
1923    switch (node->type) {
1924    case nir_cf_node_block:
1925       return cb(nir_cf_node_as_block(node), state);
1926    case nir_cf_node_if:
1927       return foreach_if(nir_cf_node_as_if(node), cb, reverse, state);
1928    case nir_cf_node_loop:
1929       return foreach_loop(nir_cf_node_as_loop(node), cb, reverse, state);
1930       break;
1931
1932    default:
1933       unreachable("Invalid CFG node type");
1934       break;
1935    }
1936
1937    return false;
1938 }
1939
1940 bool
1941 nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb, void *state)
1942 {
1943    foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {
1944       if (!foreach_cf_node(node, cb, false, state))
1945          return false;
1946    }
1947
1948    return cb(impl->end_block, state);
1949 }
1950
1951 bool
1952 nir_foreach_block_reverse(nir_function_impl *impl, nir_foreach_block_cb cb,
1953                           void *state)
1954 {
1955    if (!cb(impl->end_block, state))
1956       return false;
1957
1958    foreach_list_typed_safe_reverse(nir_cf_node, node, node, &impl->body) {
1959       if (!foreach_cf_node(node, cb, true, state))
1960          return false;
1961    }
1962
1963    return true;
1964 }
1965
1966 nir_if *
1967 nir_block_following_if(nir_block *block)
1968 {
1969    if (exec_node_is_tail_sentinel(&block->cf_node.node))
1970       return NULL;
1971
1972    if (nir_cf_node_is_last(&block->cf_node))
1973       return NULL;
1974
1975    nir_cf_node *next_node = nir_cf_node_next(&block->cf_node);
1976
1977    if (next_node->type != nir_cf_node_if)
1978       return NULL;
1979
1980    return nir_cf_node_as_if(next_node);
1981 }
1982
1983 static bool
1984 index_block(nir_block *block, void *state)
1985 {
1986    unsigned *index = (unsigned *) state;
1987    block->index = (*index)++;
1988    return true;
1989 }
1990
1991 void
1992 nir_index_blocks(nir_function_impl *impl)
1993 {
1994    unsigned index = 0;
1995
1996    if (impl->valid_metadata & nir_metadata_block_index)
1997       return;
1998
1999    nir_foreach_block(impl, index_block, &index);
2000
2001    impl->num_blocks = index;
2002 }
2003
2004 static void
2005 index_ssa_def(nir_ssa_def *def, unsigned *index)
2006 {
2007    def->index = (*index)++;
2008 }
2009
2010 static bool
2011 index_ssa_def_cb(nir_dest *dest, void *state)
2012 {
2013    unsigned *index = (unsigned *) state;
2014    if (dest->is_ssa)
2015       index_ssa_def(&dest->ssa, index);
2016    return true;
2017 }
2018
2019 static void
2020 index_ssa_undef(nir_ssa_undef_instr *instr, unsigned *index)
2021 {
2022    index_ssa_def(&instr->def, index);
2023 }
2024
2025 static bool
2026 index_ssa_block(nir_block *block, void *state)
2027 {
2028    unsigned *index = (unsigned *) state;
2029
2030    nir_foreach_instr(block, instr) {
2031       if (instr->type == nir_instr_type_ssa_undef)
2032          index_ssa_undef(nir_instr_as_ssa_undef(instr), index);
2033       else
2034          nir_foreach_dest(instr, index_ssa_def_cb, state);
2035    }
2036
2037    return true;
2038 }
2039
2040 void
2041 nir_index_ssa_defs(nir_function_impl *impl)
2042 {
2043    unsigned index = 0;
2044    nir_foreach_block(impl, index_ssa_block, &index);
2045    impl->ssa_alloc = index;
2046 }