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