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