src/glsl/nir/nir.c

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