src/glsl/nir/nir.c

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