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