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