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