src/glsl/nir/nir.c

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