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