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 static void
1154 remove_defs_uses(nir_instr *instr);
1155
1156 static void
1157 cleanup_cf_node(nir_cf_node *node)
1158 {
1159    switch (node->type) {
1160    case nir_cf_node_block: {
1161       nir_block *block = nir_cf_node_as_block(node);
1162       /* We need to walk the instructions and clean up defs/uses */
1163       nir_foreach_instr(block, instr)
1164          remove_defs_uses(instr);
1165       break;
1166    }
1167
1168    case nir_cf_node_if: {
1169       nir_if *if_stmt = nir_cf_node_as_if(node);
1170       foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list)
1171          cleanup_cf_node(child);
1172       foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list)
1173          cleanup_cf_node(child);
1174
1175       struct set *if_uses;
1176       if (if_stmt->condition.is_ssa) {
1177          if_uses = if_stmt->condition.ssa->if_uses;
1178       } else {
1179          if_uses = if_stmt->condition.reg.reg->if_uses;
1180       }
1181
1182       struct set_entry *entry = _mesa_set_search(if_uses, if_stmt);
1183       assert(entry);
1184       _mesa_set_remove(if_uses, entry);
1185       break;
1186    }
1187
1188    case nir_cf_node_loop: {
1189       nir_loop *loop = nir_cf_node_as_loop(node);
1190       foreach_list_typed(nir_cf_node, child, node, &loop->body)
1191          cleanup_cf_node(child);
1192       break;
1193    }
1194    case nir_cf_node_function: {
1195       nir_function_impl *impl = nir_cf_node_as_function(node);
1196       foreach_list_typed(nir_cf_node, child, node, &impl->body)
1197          cleanup_cf_node(child);
1198       break;
1199    }
1200    default:
1201       unreachable("Invalid CF node type");
1202    }
1203 }
1204
1205 void
1206 nir_cf_node_remove(nir_cf_node *node)
1207 {
1208    nir_function_impl *impl = nir_cf_node_get_function(node);
1209    nir_metadata_preserve(impl, nir_metadata_none);
1210
1211    if (node->type == nir_cf_node_block) {
1212       /*
1213        * Basic blocks can't really be removed by themselves, since they act as
1214        * padding between the non-basic blocks. So all we do here is empty the
1215        * block of instructions.
1216        *
1217        * TODO: could we assert here?
1218        */
1219       exec_list_make_empty(&nir_cf_node_as_block(node)->instr_list);
1220    } else {
1221       nir_cf_node *before = nir_cf_node_prev(node);
1222       assert(before->type == nir_cf_node_block);
1223       nir_block *before_block = nir_cf_node_as_block(before);
1224
1225       nir_cf_node *after = nir_cf_node_next(node);
1226       assert(after->type == nir_cf_node_block);
1227       nir_block *after_block = nir_cf_node_as_block(after);
1228
1229       exec_node_remove(&node->node);
1230       stitch_blocks(before_block, after_block);
1231    }
1232
1233    cleanup_cf_node(node);
1234 }
1235
1236 static bool
1237 add_use_cb(nir_src *src, void *state)
1238 {
1239    nir_instr *instr = state;
1240
1241    struct set *uses_set = src->is_ssa ? src->ssa->uses : src->reg.reg->uses;
1242
1243    _mesa_set_add(uses_set, instr);
1244
1245    return true;
1246 }
1247
1248 static bool
1249 add_ssa_def_cb(nir_ssa_def *def, void *state)
1250 {
1251    nir_instr *instr = state;
1252
1253    if (instr->block && def->index == UINT_MAX) {
1254       nir_function_impl *impl =
1255          nir_cf_node_get_function(&instr->block->cf_node);
1256
1257       def->index = impl->ssa_alloc++;
1258    }
1259
1260    return true;
1261 }
1262
1263 static bool
1264 add_reg_def_cb(nir_dest *dest, void *state)
1265 {
1266    nir_instr *instr = state;
1267
1268    if (!dest->is_ssa)
1269       _mesa_set_add(dest->reg.reg->defs, instr);
1270
1271    return true;
1272 }
1273
1274 static void
1275 add_defs_uses(nir_instr *instr)
1276 {
1277    nir_foreach_src(instr, add_use_cb, instr);
1278    nir_foreach_dest(instr, add_reg_def_cb, instr);
1279    nir_foreach_ssa_def(instr, add_ssa_def_cb, instr);
1280 }
1281
1282 void
1283 nir_instr_insert_before(nir_instr *instr, nir_instr *before)
1284 {
1285    assert(before->type != nir_instr_type_jump);
1286    before->block = instr->block;
1287    add_defs_uses(before);
1288    exec_node_insert_node_before(&instr->node, &before->node);
1289 }
1290
1291 void
1292 nir_instr_insert_after(nir_instr *instr, nir_instr *after)
1293 {
1294    if (after->type == nir_instr_type_jump) {
1295       assert(instr == nir_block_last_instr(instr->block));
1296       assert(instr->type != nir_instr_type_jump);
1297    }
1298
1299    after->block = instr->block;
1300    add_defs_uses(after);
1301    exec_node_insert_after(&instr->node, &after->node);
1302
1303    if (after->type == nir_instr_type_jump)
1304       handle_jump(after->block);
1305 }
1306
1307 void
1308 nir_instr_insert_before_block(nir_block *block, nir_instr *before)
1309 {
1310    if (before->type == nir_instr_type_jump)
1311       assert(exec_list_is_empty(&block->instr_list));
1312
1313    before->block = block;
1314    add_defs_uses(before);
1315    exec_list_push_head(&block->instr_list, &before->node);
1316
1317    if (before->type == nir_instr_type_jump)
1318       handle_jump(block);
1319 }
1320
1321 void
1322 nir_instr_insert_after_block(nir_block *block, nir_instr *after)
1323 {
1324    if (after->type == nir_instr_type_jump) {
1325       assert(exec_list_is_empty(&block->instr_list) ||
1326              nir_block_last_instr(block)->type != nir_instr_type_jump);
1327    }
1328
1329    after->block = block;
1330    add_defs_uses(after);
1331    exec_list_push_tail(&block->instr_list, &after->node);
1332
1333    if (after->type == nir_instr_type_jump)
1334       handle_jump(block);
1335 }
1336
1337 void
1338 nir_instr_insert_before_cf(nir_cf_node *node, nir_instr *before)
1339 {
1340    if (node->type == nir_cf_node_block) {
1341       nir_instr_insert_before_block(nir_cf_node_as_block(node), before);
1342    } else {
1343       nir_cf_node *prev = nir_cf_node_prev(node);
1344       assert(prev->type == nir_cf_node_block);
1345       nir_block *prev_block = nir_cf_node_as_block(prev);
1346
1347       nir_instr_insert_before_block(prev_block, before);
1348    }
1349 }
1350
1351 void
1352 nir_instr_insert_after_cf(nir_cf_node *node, nir_instr *after)
1353 {
1354    if (node->type == nir_cf_node_block) {
1355       nir_instr_insert_after_block(nir_cf_node_as_block(node), after);
1356    } else {
1357       nir_cf_node *next = nir_cf_node_next(node);
1358       assert(next->type == nir_cf_node_block);
1359       nir_block *next_block = nir_cf_node_as_block(next);
1360
1361       nir_instr_insert_before_block(next_block, after);
1362    }
1363 }
1364
1365 void
1366 nir_instr_insert_before_cf_list(struct exec_list *list, nir_instr *before)
1367 {
1368    nir_cf_node *first_node = exec_node_data(nir_cf_node,
1369                                             exec_list_get_head(list), node);
1370    nir_instr_insert_before_cf(first_node, before);
1371 }
1372
1373 void
1374 nir_instr_insert_after_cf_list(struct exec_list *list, nir_instr *after)
1375 {
1376    nir_cf_node *last_node = exec_node_data(nir_cf_node,
1377                                            exec_list_get_tail(list), node);
1378    nir_instr_insert_after_cf(last_node, after);
1379 }
1380
1381 static bool
1382 remove_use_cb(nir_src *src, void *state)
1383 {
1384    nir_instr *instr = state;
1385
1386    struct set *uses_set = src->is_ssa ? src->ssa->uses : src->reg.reg->uses;
1387
1388    struct set_entry *entry = _mesa_set_search(uses_set, instr);
1389    if (entry)
1390       _mesa_set_remove(uses_set, entry);
1391
1392    return true;
1393 }
1394
1395 static bool
1396 remove_def_cb(nir_dest *dest, void *state)
1397 {
1398    nir_instr *instr = state;
1399
1400    if (dest->is_ssa)
1401       return true;
1402
1403    nir_register *reg = dest->reg.reg;
1404
1405    struct set_entry *entry = _mesa_set_search(reg->defs, instr);
1406    if (entry)
1407       _mesa_set_remove(reg->defs, entry);
1408
1409    return true;
1410 }
1411
1412 static void
1413 remove_defs_uses(nir_instr *instr)
1414 {
1415    nir_foreach_dest(instr, remove_def_cb, instr);
1416    nir_foreach_src(instr, remove_use_cb, instr);
1417 }
1418
1419 void nir_instr_remove(nir_instr *instr)
1420 {
1421    remove_defs_uses(instr);
1422    exec_node_remove(&instr->node);
1423
1424    if (instr->type == nir_instr_type_jump) {
1425       nir_jump_instr *jump_instr = nir_instr_as_jump(instr);
1426       handle_remove_jump(instr->block, jump_instr->type);
1427    }
1428 }
1429
1430 /*@}*/
1431
1432 void
1433 nir_index_local_regs(nir_function_impl *impl)
1434 {
1435    unsigned index = 0;
1436    foreach_list_typed(nir_register, reg, node, &impl->registers) {
1437       reg->index = index++;
1438    }
1439    impl->reg_alloc = index;
1440 }
1441
1442 void
1443 nir_index_global_regs(nir_shader *shader)
1444 {
1445    unsigned index = 0;
1446    foreach_list_typed(nir_register, reg, node, &shader->registers) {
1447       reg->index = index++;
1448    }
1449    shader->reg_alloc = index;
1450 }
1451
1452 static bool
1453 visit_alu_dest(nir_alu_instr *instr, nir_foreach_dest_cb cb, void *state)
1454 {
1455    return cb(&instr->dest.dest, state);
1456 }
1457
1458 static bool
1459 visit_intrinsic_dest(nir_intrinsic_instr *instr, nir_foreach_dest_cb cb,
1460                      void *state)
1461 {
1462    if (nir_intrinsic_infos[instr->intrinsic].has_dest)
1463       return cb(&instr->dest, state);
1464
1465    return true;
1466 }
1467
1468 static bool
1469 visit_texture_dest(nir_tex_instr *instr, nir_foreach_dest_cb cb,
1470                    void *state)
1471 {
1472    return cb(&instr->dest, state);
1473 }
1474
1475 static bool
1476 visit_phi_dest(nir_phi_instr *instr, nir_foreach_dest_cb cb, void *state)
1477 {
1478    return cb(&instr->dest, state);
1479 }
1480
1481 static bool
1482 visit_parallel_copy_dest(nir_parallel_copy_instr *instr,
1483                          nir_foreach_dest_cb cb, void *state)
1484 {
1485    nir_foreach_parallel_copy_entry(instr, entry) {
1486       if (!cb(&entry->dest, state))
1487          return false;
1488    }
1489
1490    return true;
1491 }
1492
1493 bool
1494 nir_foreach_dest(nir_instr *instr, nir_foreach_dest_cb cb, void *state)
1495 {
1496    switch (instr->type) {
1497    case nir_instr_type_alu:
1498       return visit_alu_dest(nir_instr_as_alu(instr), cb, state);
1499    case nir_instr_type_intrinsic:
1500       return visit_intrinsic_dest(nir_instr_as_intrinsic(instr), cb, state);
1501    case nir_instr_type_tex:
1502       return visit_texture_dest(nir_instr_as_tex(instr), cb, state);
1503    case nir_instr_type_phi:
1504       return visit_phi_dest(nir_instr_as_phi(instr), cb, state);
1505    case nir_instr_type_parallel_copy:
1506       return visit_parallel_copy_dest(nir_instr_as_parallel_copy(instr),
1507                                       cb, state);
1508
1509    case nir_instr_type_load_const:
1510    case nir_instr_type_ssa_undef:
1511    case nir_instr_type_call:
1512    case nir_instr_type_jump:
1513       break;
1514
1515    default:
1516       unreachable("Invalid instruction type");
1517       break;
1518    }
1519
1520    return true;
1521 }
1522
1523 struct foreach_ssa_def_state {
1524    nir_foreach_ssa_def_cb cb;
1525    void *client_state;
1526 };
1527
1528 static inline bool
1529 nir_ssa_def_visitor(nir_dest *dest, void *void_state)
1530 {
1531    struct foreach_ssa_def_state *state = void_state;
1532
1533    if (dest->is_ssa)
1534       return state->cb(&dest->ssa, state->client_state);
1535    else
1536       return true;
1537 }
1538
1539 bool
1540 nir_foreach_ssa_def(nir_instr *instr, nir_foreach_ssa_def_cb cb, void *state)
1541 {
1542    switch (instr->type) {
1543    case nir_instr_type_alu:
1544    case nir_instr_type_tex:
1545    case nir_instr_type_intrinsic:
1546    case nir_instr_type_phi:
1547    case nir_instr_type_parallel_copy: {
1548       struct foreach_ssa_def_state foreach_state = {cb, state};
1549       return nir_foreach_dest(instr, nir_ssa_def_visitor, &foreach_state);
1550    }
1551
1552    case nir_instr_type_load_const:
1553       return cb(&nir_instr_as_load_const(instr)->def, state);
1554    case nir_instr_type_ssa_undef:
1555       return cb(&nir_instr_as_ssa_undef(instr)->def, state);
1556    case nir_instr_type_call:
1557    case nir_instr_type_jump:
1558       return true;
1559    default:
1560       unreachable("Invalid instruction type");
1561    }
1562 }
1563
1564 static bool
1565 visit_src(nir_src *src, nir_foreach_src_cb cb, void *state)
1566 {
1567    if (!cb(src, state))
1568       return false;
1569    if (!src->is_ssa && src->reg.indirect)
1570       return cb(src->reg.indirect, state);
1571    return true;
1572 }
1573
1574 static bool
1575 visit_deref_array_src(nir_deref_array *deref, nir_foreach_src_cb cb,
1576                       void *state)
1577 {
1578    if (deref->deref_array_type == nir_deref_array_type_indirect)
1579       return visit_src(&deref->indirect, cb, state);
1580    return true;
1581 }
1582
1583 static bool
1584 visit_deref_src(nir_deref_var *deref, nir_foreach_src_cb cb, void *state)
1585 {
1586    nir_deref *cur = &deref->deref;
1587    while (cur != NULL) {
1588       if (cur->deref_type == nir_deref_type_array)
1589          if (!visit_deref_array_src(nir_deref_as_array(cur), cb, state))
1590             return false;
1591
1592       cur = cur->child;
1593    }
1594
1595    return true;
1596 }
1597
1598 static bool
1599 visit_alu_src(nir_alu_instr *instr, nir_foreach_src_cb cb, void *state)
1600 {
1601    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++)
1602       if (!visit_src(&instr->src[i].src, cb, state))
1603          return false;
1604
1605    return true;
1606 }
1607
1608 static bool
1609 visit_tex_src(nir_tex_instr *instr, nir_foreach_src_cb cb, void *state)
1610 {
1611    for (unsigned i = 0; i < instr->num_srcs; i++)
1612       if (!visit_src(&instr->src[i].src, cb, state))
1613          return false;
1614
1615    if (instr->sampler != NULL)
1616       if (!visit_deref_src(instr->sampler, cb, state))
1617          return false;
1618
1619    return true;
1620 }
1621
1622 static bool
1623 visit_intrinsic_src(nir_intrinsic_instr *instr, nir_foreach_src_cb cb,
1624                     void *state)
1625 {
1626    unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
1627    for (unsigned i = 0; i < num_srcs; i++)
1628       if (!visit_src(&instr->src[i], cb, state))
1629          return false;
1630
1631    unsigned num_vars =
1632       nir_intrinsic_infos[instr->intrinsic].num_variables;
1633    for (unsigned i = 0; i < num_vars; i++)
1634       if (!visit_deref_src(instr->variables[i], cb, state))
1635          return false;
1636
1637    return true;
1638 }
1639
1640 static bool
1641 visit_call_src(nir_call_instr *instr, nir_foreach_src_cb cb, void *state)
1642 {
1643    return true;
1644 }
1645
1646 static bool
1647 visit_load_const_src(nir_load_const_instr *instr, nir_foreach_src_cb cb,
1648                      void *state)
1649 {
1650    return true;
1651 }
1652
1653 static bool
1654 visit_phi_src(nir_phi_instr *instr, nir_foreach_src_cb cb, void *state)
1655 {
1656    nir_foreach_phi_src(instr, src) {
1657       if (!visit_src(&src->src, cb, state))
1658          return false;
1659    }
1660
1661    return true;
1662 }
1663
1664 static bool
1665 visit_parallel_copy_src(nir_parallel_copy_instr *instr,
1666                         nir_foreach_src_cb cb, void *state)
1667 {
1668    nir_foreach_parallel_copy_entry(instr, entry) {
1669       if (!visit_src(&entry->src, cb, state))
1670          return false;
1671    }
1672
1673    return true;
1674 }
1675
1676 typedef struct {
1677    void *state;
1678    nir_foreach_src_cb cb;
1679 } visit_dest_indirect_state;
1680
1681 static bool
1682 visit_dest_indirect(nir_dest *dest, void *_state)
1683 {
1684    visit_dest_indirect_state *state = (visit_dest_indirect_state *) _state;
1685
1686    if (!dest->is_ssa && dest->reg.indirect)
1687       return state->cb(dest->reg.indirect, state->state);
1688
1689    return true;
1690 }
1691
1692 bool
1693 nir_foreach_src(nir_instr *instr, nir_foreach_src_cb cb, void *state)
1694 {
1695    switch (instr->type) {
1696    case nir_instr_type_alu:
1697       if (!visit_alu_src(nir_instr_as_alu(instr), cb, state))
1698          return false;
1699       break;
1700    case nir_instr_type_intrinsic:
1701       if (!visit_intrinsic_src(nir_instr_as_intrinsic(instr), cb, state))
1702          return false;
1703       break;
1704    case nir_instr_type_tex:
1705       if (!visit_tex_src(nir_instr_as_tex(instr), cb, state))
1706          return false;
1707       break;
1708    case nir_instr_type_call:
1709       if (!visit_call_src(nir_instr_as_call(instr), cb, state))
1710          return false;
1711       break;
1712    case nir_instr_type_load_const:
1713       if (!visit_load_const_src(nir_instr_as_load_const(instr), cb, state))
1714          return false;
1715       break;
1716    case nir_instr_type_phi:
1717       if (!visit_phi_src(nir_instr_as_phi(instr), cb, state))
1718          return false;
1719       break;
1720    case nir_instr_type_parallel_copy:
1721       if (!visit_parallel_copy_src(nir_instr_as_parallel_copy(instr),
1722                                    cb, state))
1723          return false;
1724       break;
1725    case nir_instr_type_jump:
1726    case nir_instr_type_ssa_undef:
1727       return true;
1728
1729    default:
1730       unreachable("Invalid instruction type");
1731       break;
1732    }
1733
1734    visit_dest_indirect_state dest_state;
1735    dest_state.state = state;
1736    dest_state.cb = cb;
1737    return nir_foreach_dest(instr, visit_dest_indirect, &dest_state);
1738 }
1739
1740 nir_const_value *
1741 nir_src_as_const_value(nir_src src)
1742 {
1743    if (!src.is_ssa)
1744       return NULL;
1745
1746    if (src.ssa->parent_instr->type != nir_instr_type_load_const)
1747       return NULL;
1748
1749    nir_load_const_instr *load = nir_instr_as_load_const(src.ssa->parent_instr);
1750
1751    return &load->value;
1752 }
1753
1754 bool
1755 nir_srcs_equal(nir_src src1, nir_src src2)
1756 {
1757    if (src1.is_ssa) {
1758       if (src2.is_ssa) {
1759          return src1.ssa == src2.ssa;
1760       } else {
1761          return false;
1762       }
1763    } else {
1764       if (src2.is_ssa) {
1765          return false;
1766       } else {
1767          if ((src1.reg.indirect == NULL) != (src2.reg.indirect == NULL))
1768             return false;
1769
1770          if (src1.reg.indirect) {
1771             if (!nir_srcs_equal(*src1.reg.indirect, *src2.reg.indirect))
1772                return false;
1773          }
1774
1775          return src1.reg.reg == src2.reg.reg &&
1776                 src1.reg.base_offset == src2.reg.base_offset;
1777       }
1778    }
1779 }
1780
1781 static bool
1782 src_does_not_use_def(nir_src *src, void *void_def)
1783 {
1784    nir_ssa_def *def = void_def;
1785
1786    if (src->is_ssa) {
1787       return src->ssa != def;
1788    } else {
1789       return true;
1790    }
1791 }
1792
1793 static bool
1794 src_does_not_use_reg(nir_src *src, void *void_reg)
1795 {
1796    nir_register *reg = void_reg;
1797
1798    if (src->is_ssa) {
1799       return true;
1800    } else {
1801       return src->reg.reg != reg;
1802    }
1803 }
1804
1805 void
1806 nir_instr_rewrite_src(nir_instr *instr, nir_src *src, nir_src new_src)
1807 {
1808    if (src->is_ssa) {
1809       nir_ssa_def *old_ssa = src->ssa;
1810       *src = new_src;
1811       if (old_ssa && nir_foreach_src(instr, src_does_not_use_def, old_ssa)) {
1812          struct set_entry *entry = _mesa_set_search(old_ssa->uses, instr);
1813          assert(entry);
1814          _mesa_set_remove(old_ssa->uses, entry);
1815       }
1816    } else {
1817       if (src->reg.indirect)
1818          nir_instr_rewrite_src(instr, src->reg.indirect, new_src);
1819
1820       nir_register *old_reg = src->reg.reg;
1821       *src = new_src;
1822       if (old_reg && nir_foreach_src(instr, src_does_not_use_reg, old_reg)) {
1823          struct set_entry *entry = _mesa_set_search(old_reg->uses, instr);
1824          assert(entry);
1825          _mesa_set_remove(old_reg->uses, entry);
1826       }
1827    }
1828
1829    if (new_src.is_ssa) {
1830       if (new_src.ssa)
1831          _mesa_set_add(new_src.ssa->uses, instr);
1832    } else {
1833       if (new_src.reg.reg)
1834          _mesa_set_add(new_src.reg.reg->uses, instr);
1835    }
1836 }
1837
1838 void
1839 nir_ssa_def_init(nir_instr *instr, nir_ssa_def *def,
1840                  unsigned num_components, const char *name)
1841 {
1842    void *mem_ctx = ralloc_parent(instr);
1843
1844    def->name = name;
1845    def->parent_instr = instr;
1846    def->uses = _mesa_set_create(mem_ctx, _mesa_hash_pointer,
1847                                 _mesa_key_pointer_equal);
1848    def->if_uses = _mesa_set_create(mem_ctx, _mesa_hash_pointer,
1849                                    _mesa_key_pointer_equal);
1850    def->num_components = num_components;
1851
1852    if (instr->block) {
1853       nir_function_impl *impl =
1854          nir_cf_node_get_function(&instr->block->cf_node);
1855
1856       def->index = impl->ssa_alloc++;
1857    } else {
1858       def->index = UINT_MAX;
1859    }
1860 }
1861
1862 void
1863 nir_ssa_dest_init(nir_instr *instr, nir_dest *dest,
1864                  unsigned num_components, const char *name)
1865 {
1866    dest->is_ssa = true;
1867    nir_ssa_def_init(instr, &dest->ssa, num_components, name);
1868 }
1869
1870 struct ssa_def_rewrite_state {
1871    void *mem_ctx;
1872    nir_ssa_def *old;
1873    nir_src new_src;
1874 };
1875
1876 static bool
1877 ssa_def_rewrite_uses_src(nir_src *src, void *void_state)
1878 {
1879    struct ssa_def_rewrite_state *state = void_state;
1880
1881    if (src->is_ssa && src->ssa == state->old)
1882       nir_src_copy(src, &state->new_src, state->mem_ctx);
1883
1884    return true;
1885 }
1886
1887 void
1888 nir_ssa_def_rewrite_uses(nir_ssa_def *def, nir_src new_src, void *mem_ctx)
1889 {
1890    struct ssa_def_rewrite_state state;
1891    state.mem_ctx = mem_ctx;
1892    state.old = def;
1893    state.new_src = new_src;
1894
1895    assert(!new_src.is_ssa || def != new_src.ssa);
1896
1897    struct set *new_uses, *new_if_uses;
1898    if (new_src.is_ssa) {
1899       new_uses = new_src.ssa->uses;
1900       new_if_uses = new_src.ssa->if_uses;
1901    } else {
1902       new_uses = new_src.reg.reg->uses;
1903       new_if_uses = new_src.reg.reg->if_uses;
1904    }
1905
1906    struct set_entry *entry;
1907    set_foreach(def->uses, entry) {
1908       nir_instr *instr = (nir_instr *)entry->key;
1909
1910       _mesa_set_remove(def->uses, entry);
1911       nir_foreach_src(instr, ssa_def_rewrite_uses_src, &state);
1912       _mesa_set_add(new_uses, instr);
1913    }
1914
1915    set_foreach(def->if_uses, entry) {
1916       nir_if *if_use = (nir_if *)entry->key;
1917
1918       _mesa_set_remove(def->if_uses, entry);
1919       nir_src_copy(&if_use->condition, &new_src, mem_ctx);
1920       _mesa_set_add(new_if_uses, if_use);
1921    }
1922 }
1923
1924
1925 static bool foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1926                             bool reverse, void *state);
1927
1928 static inline bool
1929 foreach_if(nir_if *if_stmt, nir_foreach_block_cb cb, bool reverse, void *state)
1930 {
1931    if (reverse) {
1932       foreach_list_typed_safe_reverse(nir_cf_node, node, node,
1933                                       &if_stmt->else_list) {
1934          if (!foreach_cf_node(node, cb, reverse, state))
1935             return false;
1936       }
1937
1938       foreach_list_typed_safe_reverse(nir_cf_node, node, node,
1939                                       &if_stmt->then_list) {
1940          if (!foreach_cf_node(node, cb, reverse, state))
1941             return false;
1942       }
1943    } else {
1944       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->then_list) {
1945          if (!foreach_cf_node(node, cb, reverse, state))
1946             return false;
1947       }
1948
1949       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list) {
1950          if (!foreach_cf_node(node, cb, reverse, state))
1951             return false;
1952       }
1953    }
1954
1955    return true;
1956 }
1957
1958 static inline bool
1959 foreach_loop(nir_loop *loop, nir_foreach_block_cb cb, bool reverse, void *state)
1960 {
1961    if (reverse) {
1962       foreach_list_typed_safe_reverse(nir_cf_node, node, node, &loop->body) {
1963          if (!foreach_cf_node(node, cb, reverse, state))
1964             return false;
1965       }
1966    } else {
1967       foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {
1968          if (!foreach_cf_node(node, cb, reverse, state))
1969             return false;
1970       }
1971    }
1972
1973    return true;
1974 }
1975
1976 static bool
1977 foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1978                 bool reverse, void *state)
1979 {
1980    switch (node->type) {
1981    case nir_cf_node_block:
1982       return cb(nir_cf_node_as_block(node), state);
1983    case nir_cf_node_if:
1984       return foreach_if(nir_cf_node_as_if(node), cb, reverse, state);
1985    case nir_cf_node_loop:
1986       return foreach_loop(nir_cf_node_as_loop(node), cb, reverse, state);
1987       break;
1988
1989    default:
1990       unreachable("Invalid CFG node type");
1991       break;
1992    }
1993
1994    return false;
1995 }
1996
1997 bool
1998 nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb, void *state)
1999 {
2000    foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {
2001       if (!foreach_cf_node(node, cb, false, state))
2002          return false;
2003    }
2004
2005    return cb(impl->end_block, state);
2006 }
2007
2008 bool
2009 nir_foreach_block_reverse(nir_function_impl *impl, nir_foreach_block_cb cb,
2010                           void *state)
2011 {
2012    if (!cb(impl->end_block, state))
2013       return false;
2014
2015    foreach_list_typed_safe_reverse(nir_cf_node, node, node, &impl->body) {
2016       if (!foreach_cf_node(node, cb, true, state))
2017          return false;
2018    }
2019
2020    return true;
2021 }
2022
2023 nir_if *
2024 nir_block_get_following_if(nir_block *block)
2025 {
2026    if (exec_node_is_tail_sentinel(&block->cf_node.node))
2027       return NULL;
2028
2029    if (nir_cf_node_is_last(&block->cf_node))
2030       return NULL;
2031
2032    nir_cf_node *next_node = nir_cf_node_next(&block->cf_node);
2033
2034    if (next_node->type != nir_cf_node_if)
2035       return NULL;
2036
2037    return nir_cf_node_as_if(next_node);
2038 }
2039
2040 static bool
2041 index_block(nir_block *block, void *state)
2042 {
2043    unsigned *index = state;
2044    block->index = (*index)++;
2045    return true;
2046 }
2047
2048 void
2049 nir_index_blocks(nir_function_impl *impl)
2050 {
2051    unsigned index = 0;
2052
2053    if (impl->valid_metadata & nir_metadata_block_index)
2054       return;
2055
2056    nir_foreach_block(impl, index_block, &index);
2057
2058    impl->num_blocks = index;
2059 }
2060
2061 static bool
2062 index_ssa_def_cb(nir_ssa_def *def, void *state)
2063 {
2064    unsigned *index = (unsigned *) state;
2065    def->index = (*index)++;
2066
2067    return true;
2068 }
2069
2070 static bool
2071 index_ssa_block(nir_block *block, void *state)
2072 {
2073    nir_foreach_instr(block, instr)
2074       nir_foreach_ssa_def(instr, index_ssa_def_cb, state);
2075
2076    return true;
2077 }
2078
2079 void
2080 nir_index_ssa_defs(nir_function_impl *impl)
2081 {
2082    unsigned index = 0;
2083    nir_foreach_block(impl, index_ssa_block, &index);
2084    impl->ssa_alloc = index;
2085 }