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->end_block = end_block;
 266
 267    exec_list_push_tail(&impl->body, &start_block->cf_node.node);
 268
 269    start_block->successors[0] = end_block;
 270    _mesa_set_add(end_block->predecessors, start_block);
 271    return impl;
 272 }
 273
 274 nir_block *
 275 nir_block_create(void *mem_ctx)
 276 {
 277    nir_block *block = ralloc(mem_ctx, nir_block);
 278
 279    cf_init(&block->cf_node, nir_cf_node_block);
 280
 281    block->successors[0] = block->successors[1] = NULL;
 282    block->predecessors = _mesa_set_create(block, _mesa_hash_pointer,
 283                                           _mesa_key_pointer_equal);
 284    block->imm_dom = NULL;
 285    block->dom_frontier = _mesa_set_create(block, _mesa_hash_pointer,
 286                                           _mesa_key_pointer_equal);
 287
 288    exec_list_make_empty(&block->instr_list);
 289
 290    return block;
 291 }
 292
 293 static inline void
 294 src_init(nir_src *src)
 295 {
 296    src->is_ssa = false;
 297    src->reg.reg = NULL;
 298    src->reg.indirect = NULL;
 299    src->reg.base_offset = 0;
 300 }
 301
 302 nir_if *
 303 nir_if_create(void *mem_ctx)
 304 {
 305    nir_if *if_stmt = ralloc(mem_ctx, nir_if);
 306
 307    cf_init(&if_stmt->cf_node, nir_cf_node_if);
 308    src_init(&if_stmt->condition);
 309
 310    nir_block *then = nir_block_create(mem_ctx);
 311    exec_list_make_empty(&if_stmt->then_list);
 312    exec_list_push_tail(&if_stmt->then_list, &then->cf_node.node);
 313    then->cf_node.parent = &if_stmt->cf_node;
 314
 315    nir_block *else_stmt = nir_block_create(mem_ctx);
 316    exec_list_make_empty(&if_stmt->else_list);
 317    exec_list_push_tail(&if_stmt->else_list, &else_stmt->cf_node.node);
 318    else_stmt->cf_node.parent = &if_stmt->cf_node;
 319
 320    return if_stmt;
 321 }
 322
 323 nir_loop *
 324 nir_loop_create(void *mem_ctx)
 325 {
 326    nir_loop *loop = ralloc(mem_ctx, nir_loop);
 327
 328    cf_init(&loop->cf_node, nir_cf_node_loop);
 329
 330    nir_block *body = nir_block_create(mem_ctx);
 331    exec_list_make_empty(&loop->body);
 332    exec_list_push_tail(&loop->body, &body->cf_node.node);
 333    body->cf_node.parent = &loop->cf_node;
 334
 335    body->successors[0] = body;
 336    _mesa_set_add(body->predecessors, body);
 337
 338    return loop;
 339 }
 340
 341 static void
 342 instr_init(nir_instr *instr, nir_instr_type type)
 343 {
 344    instr->type = type;
 345    instr->block = NULL;
 346    exec_node_init(&instr->node);
 347 }
 348
 349 static void
 350 dest_init(nir_dest *dest)
 351 {
 352    dest->is_ssa = false;
 353    dest->reg.reg = NULL;
 354    dest->reg.indirect = NULL;
 355    dest->reg.base_offset = 0;
 356 }
 357
 358 static void
 359 alu_dest_init(nir_alu_dest *dest)
 360 {
 361    dest_init(&dest->dest);
 362    dest->saturate = false;
 363    dest->write_mask = 0xf;
 364 }
 365
 366 static void
 367 alu_src_init(nir_alu_src *src)
 368 {
 369    src_init(&src->src);
 370    src->abs = src->negate = false;
 371    src->swizzle[0] = 0;
 372    src->swizzle[1] = 1;
 373    src->swizzle[2] = 2;
 374    src->swizzle[3] = 3;
 375 }
 376
 377 nir_alu_instr *
 378 nir_alu_instr_create(nir_shader *shader, nir_op op)
 379 {
 380    unsigned num_srcs = nir_op_infos[op].num_inputs;
 381    nir_alu_instr *instr =
 382       ralloc_size(shader,
 383                   sizeof(nir_alu_instr) + num_srcs * sizeof(nir_alu_src));
 384
 385    instr_init(&instr->instr, nir_instr_type_alu);
 386    instr->op = op;
 387    alu_dest_init(&instr->dest);
 388    for (unsigned i = 0; i < num_srcs; i++)
 389       alu_src_init(&instr->src[i]);
 390
 391    return instr;
 392 }
 393
 394 nir_jump_instr *
 395 nir_jump_instr_create(nir_shader *shader, nir_jump_type type)
 396 {
 397    nir_jump_instr *instr = ralloc(shader, nir_jump_instr);
 398    instr_init(&instr->instr, nir_instr_type_jump);
 399    instr->type = type;
 400    return instr;
 401 }
 402
 403 nir_load_const_instr *
 404 nir_load_const_instr_create(nir_shader *shader, unsigned num_components)
 405 {
 406    nir_load_const_instr *instr = ralloc(shader, nir_load_const_instr);
 407    instr_init(&instr->instr, nir_instr_type_load_const);
 408
 409    nir_ssa_def_init(&instr->instr, &instr->def, num_components, NULL);
 410
 411    return instr;
 412 }
 413
 414 nir_intrinsic_instr *
 415 nir_intrinsic_instr_create(nir_shader *shader, nir_intrinsic_op op)
 416 {
 417    unsigned num_srcs = nir_intrinsic_infos[op].num_srcs;
 418    nir_intrinsic_instr *instr =
 419       ralloc_size(shader,
 420                   sizeof(nir_intrinsic_instr) + num_srcs * sizeof(nir_src));
 421
 422    instr_init(&instr->instr, nir_instr_type_intrinsic);
 423    instr->intrinsic = op;
 424
 425    if (nir_intrinsic_infos[op].has_dest)
 426       dest_init(&instr->dest);
 427
 428    for (unsigned i = 0; i < num_srcs; i++)
 429       src_init(&instr->src[i]);
 430
 431    return instr;
 432 }
 433
 434 nir_call_instr *
 435 nir_call_instr_create(nir_shader *shader, nir_function_overload *callee)
 436 {
 437    nir_call_instr *instr = ralloc(shader, nir_call_instr);
 438    instr_init(&instr->instr, nir_instr_type_call);
 439
 440    instr->callee = callee;
 441    instr->num_params = callee->num_params;
 442    instr->params = ralloc_array(instr, nir_deref_var *, instr->num_params);
 443    instr->return_deref = NULL;
 444
 445    return instr;
 446 }
 447
 448 nir_tex_instr *
 449 nir_tex_instr_create(nir_shader *shader, unsigned num_srcs)
 450 {
 451    nir_tex_instr *instr = rzalloc(shader, nir_tex_instr);
 452    instr_init(&instr->instr, nir_instr_type_tex);
 453
 454    dest_init(&instr->dest);
 455
 456    instr->num_srcs = num_srcs;
 457    instr->src = ralloc_array(instr, nir_tex_src, num_srcs);
 458    for (unsigned i = 0; i < num_srcs; i++)
 459       src_init(&instr->src[i].src);
 460
 461    instr->sampler_index = 0;
 462    instr->sampler_array_size = 0;
 463    instr->sampler = NULL;
 464
 465    return instr;
 466 }
 467
 468 nir_phi_instr *
 469 nir_phi_instr_create(nir_shader *shader)
 470 {
 471    nir_phi_instr *instr = ralloc(shader, nir_phi_instr);
 472    instr_init(&instr->instr, nir_instr_type_phi);
 473
 474    dest_init(&instr->dest);
 475    exec_list_make_empty(&instr->srcs);
 476    return instr;
 477 }
 478
 479 nir_parallel_copy_instr *
 480 nir_parallel_copy_instr_create(nir_shader *shader)
 481 {
 482    nir_parallel_copy_instr *instr = ralloc(shader, nir_parallel_copy_instr);
 483    instr_init(&instr->instr, nir_instr_type_parallel_copy);
 484
 485    exec_list_make_empty(&instr->entries);
 486
 487    return instr;
 488 }
 489
 490 nir_ssa_undef_instr *
 491 nir_ssa_undef_instr_create(nir_shader *shader, unsigned num_components)
 492 {
 493    nir_ssa_undef_instr *instr = ralloc(shader, nir_ssa_undef_instr);
 494    instr_init(&instr->instr, nir_instr_type_ssa_undef);
 495
 496    nir_ssa_def_init(&instr->instr, &instr->def, num_components, NULL);
 497
 498    return instr;
 499 }
 500
 501 nir_deref_var *
 502 nir_deref_var_create(void *mem_ctx, nir_variable *var)
 503 {
 504    nir_deref_var *deref = ralloc(mem_ctx, nir_deref_var);
 505    deref->deref.deref_type = nir_deref_type_var;
 506    deref->deref.child = NULL;
 507    deref->deref.type = var->type;
 508    deref->var = var;
 509    return deref;
 510 }
 511
 512 nir_deref_array *
 513 nir_deref_array_create(void *mem_ctx)
 514 {
 515    nir_deref_array *deref = ralloc(mem_ctx, nir_deref_array);
 516    deref->deref.deref_type = nir_deref_type_array;
 517    deref->deref.child = NULL;
 518    deref->deref_array_type = nir_deref_array_type_direct;
 519    src_init(&deref->indirect);
 520    deref->base_offset = 0;
 521    return deref;
 522 }
 523
 524 nir_deref_struct *
 525 nir_deref_struct_create(void *mem_ctx, unsigned field_index)
 526 {
 527    nir_deref_struct *deref = ralloc(mem_ctx, nir_deref_struct);
 528    deref->deref.deref_type = nir_deref_type_struct;
 529    deref->deref.child = NULL;
 530    deref->index = field_index;
 531    return deref;
 532 }
 533
 534 static nir_deref_var *
 535 copy_deref_var(void *mem_ctx, nir_deref_var *deref)
 536 {
 537    nir_deref_var *ret = nir_deref_var_create(mem_ctx, deref->var);
 538    ret->deref.type = deref->deref.type;
 539    if (deref->deref.child)
 540       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 541    return ret;
 542 }
 543
 544 static nir_deref_array *
 545 copy_deref_array(void *mem_ctx, nir_deref_array *deref)
 546 {
 547    nir_deref_array *ret = nir_deref_array_create(mem_ctx);
 548    ret->base_offset = deref->base_offset;
 549    ret->deref_array_type = deref->deref_array_type;
 550    if (deref->deref_array_type == nir_deref_array_type_indirect) {
 551       nir_src_copy(&ret->indirect, &deref->indirect, mem_ctx);
 552    }
 553    ret->deref.type = deref->deref.type;
 554    if (deref->deref.child)
 555       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 556    return ret;
 557 }
 558
 559 static nir_deref_struct *
 560 copy_deref_struct(void *mem_ctx, nir_deref_struct *deref)
 561 {
 562    nir_deref_struct *ret = nir_deref_struct_create(mem_ctx, deref->index);
 563    ret->deref.type = deref->deref.type;
 564    if (deref->deref.child)
 565       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 566    return ret;
 567 }
 568
 569 nir_deref *
 570 nir_copy_deref(void *mem_ctx, nir_deref *deref)
 571 {
 572    switch (deref->deref_type) {
 573    case nir_deref_type_var:
 574       return &copy_deref_var(mem_ctx, nir_deref_as_var(deref))->deref;
 575    case nir_deref_type_array:
 576       return &copy_deref_array(mem_ctx, nir_deref_as_array(deref))->deref;
 577    case nir_deref_type_struct:
 578       return &copy_deref_struct(mem_ctx, nir_deref_as_struct(deref))->deref;
 579    default:
 580       unreachable("Invalid dereference type");
 581    }
 582
 583    return NULL;
 584 }
 585
 586 /* Returns a load_const instruction that represents the constant
 587  * initializer for the given deref chain.  The caller is responsible for
 588  * ensuring that there actually is a constant initializer.
 589  */
 590 nir_load_const_instr *
 591 nir_deref_get_const_initializer_load(nir_shader *shader, nir_deref_var *deref)
 592 {
 593    nir_constant *constant = deref->var->constant_initializer;
 594    assert(constant);
 595
 596    const nir_deref *tail = &deref->deref;
 597    unsigned matrix_offset = 0;
 598    while (tail->child) {
 599       switch (tail->child->deref_type) {
 600       case nir_deref_type_array: {
 601          nir_deref_array *arr = nir_deref_as_array(tail->child);
 602          assert(arr->deref_array_type == nir_deref_array_type_direct);
 603          if (glsl_type_is_matrix(tail->type)) {
 604             assert(arr->deref.child == NULL);
 605             matrix_offset = arr->base_offset;
 606          } else {
 607             constant = constant->elements[arr->base_offset];
 608          }
 609          break;
 610       }
 611
 612       case nir_deref_type_struct: {
 613          constant = constant->elements[nir_deref_as_struct(tail->child)->index];
 614          break;
 615       }
 616
 617       default:
 618          unreachable("Invalid deref child type");
 619       }
 620
 621       tail = tail->child;
 622    }
 623
 624    nir_load_const_instr *load =
 625       nir_load_const_instr_create(shader, glsl_get_vector_elements(tail->type));
 626
 627    matrix_offset *= load->def.num_components;
 628    for (unsigned i = 0; i < load->def.num_components; i++) {
 629       switch (glsl_get_base_type(tail->type)) {
 630       case GLSL_TYPE_FLOAT:
 631       case GLSL_TYPE_INT:
 632       case GLSL_TYPE_UINT:
 633          load->value.u[i] = constant->value.u[matrix_offset + i];
 634          break;
 635       case GLSL_TYPE_BOOL:
 636          load->value.u[i] = constant->value.b[matrix_offset + i] ?
 637                              NIR_TRUE : NIR_FALSE;
 638          break;
 639       default:
 640          unreachable("Invalid immediate type");
 641       }
 642    }
 643
 644    return load;
 645 }
 646
 647 /**
 648  * \name Control flow modification
 649  *
 650  * These functions modify the control flow tree while keeping the control flow
 651  * graph up-to-date. The invariants respected are:
 652  * 1. Each then statement, else statement, or loop body must have at least one
 653  *    control flow node.
 654  * 2. Each if-statement and loop must have one basic block before it and one
 655  *    after.
 656  * 3. Two basic blocks cannot be directly next to each other.
 657  * 4. If a basic block has a jump instruction, there must be only one and it
 658  *    must be at the end of the block.
 659  * 5. The CFG must always be connected - this means that we must insert a fake
 660  *    CFG edge for loops with no break statement.
 661  *
 662  * The purpose of the second one is so that we have places to insert code during
 663  * GCM, as well as eliminating the possibility of critical edges.
 664  */
 665 /*@{*/
 666
 667 static void
 668 link_non_block_to_block(nir_cf_node *node, nir_block *block)
 669 {
 670    if (node->type == nir_cf_node_if) {
 671       /*
 672        * We're trying to link an if to a block after it; this just means linking
 673        * the last 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 *last_then = nir_if_last_then_node(if_stmt);
 679       assert(last_then->type == nir_cf_node_block);
 680       nir_block *last_then_block = nir_cf_node_as_block(last_then);
 681
 682       nir_cf_node *last_else = nir_if_last_else_node(if_stmt);
 683       assert(last_else->type == nir_cf_node_block);
 684       nir_block *last_else_block = nir_cf_node_as_block(last_else);
 685
 686       if (exec_list_is_empty(&last_then_block->instr_list) ||
 687           nir_block_last_instr(last_then_block)->type != nir_instr_type_jump) {
 688          unlink_block_successors(last_then_block);
 689          link_blocks(last_then_block, block, NULL);
 690       }
 691
 692       if (exec_list_is_empty(&last_else_block->instr_list) ||
 693           nir_block_last_instr(last_else_block)->type != nir_instr_type_jump) {
 694          unlink_block_successors(last_else_block);
 695          link_blocks(last_else_block, block, NULL);
 696       }
 697    } else {
 698       assert(node->type == nir_cf_node_loop);
 699
 700       /*
 701        * We can only get to this codepath if we're inserting a new loop, or
 702        * at least a loop with no break statements; we can't insert break
 703        * statements into a loop when we haven't inserted it into the CFG
 704        * because we wouldn't know which block comes after the loop
 705        * and therefore, which block should be the successor of the block with
 706        * the break). Therefore, we need to insert a fake edge (see invariant
 707        * #5).
 708        */
 709
 710       nir_loop *loop = nir_cf_node_as_loop(node);
 711
 712       nir_cf_node *last = nir_loop_last_cf_node(loop);
 713       assert(last->type == nir_cf_node_block);
 714       nir_block *last_block =  nir_cf_node_as_block(last);
 715
 716       last_block->successors[1] = block;
 717       block_add_pred(block, last_block);
 718    }
 719 }
 720
 721 static void
 722 link_block_to_non_block(nir_block *block, nir_cf_node *node)
 723 {
 724    if (node->type == nir_cf_node_if) {
 725       /*
 726        * We're trying to link a block to an if after it; this just means linking
 727        * the block to the first block of the then and else branches.
 728        */
 729
 730       nir_if *if_stmt = nir_cf_node_as_if(node);
 731
 732       nir_cf_node *first_then = nir_if_first_then_node(if_stmt);
 733       assert(first_then->type == nir_cf_node_block);
 734       nir_block *first_then_block = nir_cf_node_as_block(first_then);
 735
 736       nir_cf_node *first_else = nir_if_first_else_node(if_stmt);
 737       assert(first_else->type == nir_cf_node_block);
 738       nir_block *first_else_block = nir_cf_node_as_block(first_else);
 739
 740       unlink_block_successors(block);
 741       link_blocks(block, first_then_block, first_else_block);
 742    } else {
 743       /*
 744        * For similar reasons as the corresponding case in
 745        * link_non_block_to_block(), don't worry about if the loop header has
 746        * any predecessors that need to be unlinked.
 747        */
 748
 749       assert(node->type == nir_cf_node_loop);
 750
 751       nir_loop *loop = nir_cf_node_as_loop(node);
 752
 753       nir_cf_node *loop_header = nir_loop_first_cf_node(loop);
 754       assert(loop_header->type == nir_cf_node_block);
 755       nir_block *loop_header_block = nir_cf_node_as_block(loop_header);
 756
 757       unlink_block_successors(block);
 758       link_blocks(block, loop_header_block, NULL);
 759    }
 760
 761 }
 762
 763 /**
 764  * Takes a basic block and inserts a new empty basic block before it, making its
 765  * predecessors point to the new block. This essentially splits the block into
 766  * an empty header and a body so that another non-block CF node can be inserted
 767  * between the two. Note that this does *not* link the two basic blocks, so
 768  * some kind of cleanup *must* be performed after this call.
 769  */
 770
 771 static nir_block *
 772 split_block_beginning(nir_block *block)
 773 {
 774    nir_block *new_block = nir_block_create(ralloc_parent(block));
 775    new_block->cf_node.parent = block->cf_node.parent;
 776    exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node);
 777
 778    struct set_entry *entry;
 779    set_foreach(block->predecessors, entry) {
 780       nir_block *pred = (nir_block *) entry->key;
 781
 782       unlink_blocks(pred, block);
 783       link_blocks(pred, new_block, NULL);
 784    }
 785
 786    return new_block;
 787 }
 788
 789 static void
 790 rewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred)
 791 {
 792    nir_foreach_instr_safe(block, instr) {
 793       if (instr->type != nir_instr_type_phi)
 794          break;
 795
 796       nir_phi_instr *phi = nir_instr_as_phi(instr);
 797       nir_foreach_phi_src(phi, src) {
 798          if (src->pred == old_pred) {
 799             src->pred = new_pred;
 800             break;
 801          }
 802       }
 803    }
 804 }
 805
 806 /**
 807  * Moves the successors of source to the successors of dest, leaving both
 808  * successors of source NULL.
 809  */
 810
 811 static void
 812 move_successors(nir_block *source, nir_block *dest)
 813 {
 814    nir_block *succ1 = source->successors[0];
 815    nir_block *succ2 = source->successors[1];
 816
 817    if (succ1) {
 818       unlink_blocks(source, succ1);
 819       rewrite_phi_preds(succ1, source, dest);
 820    }
 821
 822    if (succ2) {
 823       unlink_blocks(source, succ2);
 824       rewrite_phi_preds(succ2, source, dest);
 825    }
 826
 827    unlink_block_successors(dest);
 828    link_blocks(dest, succ1, succ2);
 829 }
 830
 831 static nir_block *
 832 split_block_end(nir_block *block)
 833 {
 834    nir_block *new_block = nir_block_create(ralloc_parent(block));
 835    new_block->cf_node.parent = block->cf_node.parent;
 836    exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node);
 837
 838    move_successors(block, new_block);
 839
 840    return new_block;
 841 }
 842
 843 /**
 844  * Inserts a non-basic block between two basic blocks and links them together.
 845  */
 846
 847 static void
 848 insert_non_block(nir_block *before, nir_cf_node *node, nir_block *after)
 849 {
 850    node->parent = before->cf_node.parent;
 851    exec_node_insert_after(&before->cf_node.node, &node->node);
 852    link_block_to_non_block(before, node);
 853    link_non_block_to_block(node, after);
 854 }
 855
 856 /**
 857  * Inserts a non-basic block before a basic block.
 858  */
 859
 860 static void
 861 insert_non_block_before_block(nir_cf_node *node, nir_block *block)
 862 {
 863    /* split off the beginning of block into new_block */
 864    nir_block *new_block = split_block_beginning(block);
 865
 866    /* insert our node in between new_block and block */
 867    insert_non_block(new_block, node, block);
 868 }
 869
 870 static void
 871 insert_non_block_after_block(nir_block *block, nir_cf_node *node)
 872 {
 873    /* split off the end of block into new_block */
 874    nir_block *new_block = split_block_end(block);
 875
 876    /* insert our node in between block and new_block */
 877    insert_non_block(block, node, new_block);
 878 }
 879
 880 /* walk up the control flow tree to find the innermost enclosed loop */
 881 static nir_loop *
 882 nearest_loop(nir_cf_node *node)
 883 {
 884    while (node->type != nir_cf_node_loop) {
 885       node = node->parent;
 886    }
 887
 888    return nir_cf_node_as_loop(node);
 889 }
 890
 891 nir_function_impl *
 892 nir_cf_node_get_function(nir_cf_node *node)
 893 {
 894    while (node->type != nir_cf_node_function) {
 895       node = node->parent;
 896    }
 897
 898    return nir_cf_node_as_function(node);
 899 }
 900
 901 /*
 902  * update the CFG after a jump instruction has been added to the end of a block
 903  */
 904
 905 static void
 906 handle_jump(nir_block *block)
 907 {
 908    nir_instr *instr = nir_block_last_instr(block);
 909    nir_jump_instr *jump_instr = nir_instr_as_jump(instr);
 910
 911    unlink_block_successors(block);
 912
 913    nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
 914    nir_metadata_preserve(impl, nir_metadata_none);
 915
 916    if (jump_instr->type == nir_jump_break ||
 917        jump_instr->type == nir_jump_continue) {
 918       nir_loop *loop = nearest_loop(&block->cf_node);
 919
 920       if (jump_instr->type == nir_jump_continue) {
 921          nir_cf_node *first_node = nir_loop_first_cf_node(loop);
 922          assert(first_node->type == nir_cf_node_block);
 923          nir_block *first_block = nir_cf_node_as_block(first_node);
 924          link_blocks(block, first_block, NULL);
 925       } else {
 926          nir_cf_node *after = nir_cf_node_next(&loop->cf_node);
 927          assert(after->type == nir_cf_node_block);
 928          nir_block *after_block = nir_cf_node_as_block(after);
 929          link_blocks(block, after_block, NULL);
 930
 931          /* If we inserted a fake link, remove it */
 932          nir_cf_node *last = nir_loop_last_cf_node(loop);
 933          assert(last->type == nir_cf_node_block);
 934          nir_block *last_block =  nir_cf_node_as_block(last);
 935          if (last_block->successors[1] != NULL)
 936             unlink_blocks(last_block, after_block);
 937       }
 938    } else {
 939       assert(jump_instr->type == nir_jump_return);
 940       link_blocks(block, impl->end_block, NULL);
 941    }
 942 }
 943
 944 static void
 945 handle_remove_jump(nir_block *block, nir_jump_type type)
 946 {
 947    unlink_block_successors(block);
 948
 949    if (exec_node_is_tail_sentinel(block->cf_node.node.next)) {
 950       nir_cf_node *parent = block->cf_node.parent;
 951       if (parent->type == nir_cf_node_if) {
 952          nir_cf_node *next = nir_cf_node_next(parent);
 953          assert(next->type == nir_cf_node_block);
 954          nir_block *next_block = nir_cf_node_as_block(next);
 955
 956          link_blocks(block, next_block, NULL);
 957       } else {
 958          assert(parent->type == nir_cf_node_loop);
 959          nir_loop *loop = nir_cf_node_as_loop(parent);
 960
 961          nir_cf_node *head = nir_loop_first_cf_node(loop);
 962          assert(head->type == nir_cf_node_block);
 963          nir_block *head_block = nir_cf_node_as_block(head);
 964
 965          link_blocks(block, head_block, NULL);
 966       }
 967    } else {
 968       nir_cf_node *next = nir_cf_node_next(&block->cf_node);
 969       if (next->type == nir_cf_node_if) {
 970          nir_if *next_if = nir_cf_node_as_if(next);
 971
 972          nir_cf_node *first_then = nir_if_first_then_node(next_if);
 973          assert(first_then->type == nir_cf_node_block);
 974          nir_block *first_then_block = nir_cf_node_as_block(first_then);
 975
 976          nir_cf_node *first_else = nir_if_first_else_node(next_if);
 977          assert(first_else->type == nir_cf_node_block);
 978          nir_block *first_else_block = nir_cf_node_as_block(first_else);
 979
 980          link_blocks(block, first_then_block, first_else_block);
 981       } else {
 982          assert(next->type == nir_cf_node_loop);
 983          nir_loop *next_loop = nir_cf_node_as_loop(next);
 984
 985          nir_cf_node *first = nir_loop_first_cf_node(next_loop);
 986          assert(first->type == nir_cf_node_block);
 987          nir_block *first_block = nir_cf_node_as_block(first);
 988
 989          link_blocks(block, first_block, NULL);
 990       }
 991    }
 992
 993    if (type == nir_jump_break) {
 994       nir_loop *loop = nearest_loop(&block->cf_node);
 995
 996       nir_cf_node *next = nir_cf_node_next(&loop->cf_node);
 997       assert(next->type == nir_cf_node_block);
 998       nir_block *next_block = nir_cf_node_as_block(next);
 999
1000       if (next_block->predecessors->entries == 0) {
1001          /* insert fake link */
1002          nir_cf_node *last = nir_loop_last_cf_node(loop);
1003          assert(last->type == nir_cf_node_block);
1004          nir_block *last_block = nir_cf_node_as_block(last);
1005
1006          last_block->successors[1] = next_block;
1007          block_add_pred(next_block, last_block);
1008       }
1009    }
1010
1011    nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
1012    nir_metadata_preserve(impl, nir_metadata_none);
1013 }
1014
1015 /**
1016  * Inserts a basic block before another by merging the instructions.
1017  *
1018  * @param block the target of the insertion
1019  * @param before the block to be inserted - must not have been inserted before
1020  * @param has_jump whether \before has a jump instruction at the end
1021  */
1022
1023 static void
1024 insert_block_before_block(nir_block *block, nir_block *before, bool has_jump)
1025 {
1026    assert(!has_jump || exec_list_is_empty(&block->instr_list));
1027
1028    foreach_list_typed(nir_instr, instr, node, &before->instr_list) {
1029       instr->block = block;
1030    }
1031
1032    exec_list_prepend(&block->instr_list, &before->instr_list);
1033
1034    if (has_jump)
1035       handle_jump(block);
1036 }
1037
1038 /**
1039  * Inserts a basic block after another by merging the instructions.
1040  *
1041  * @param block the target of the insertion
1042  * @param after the block to be inserted - must not have been inserted before
1043  * @param has_jump whether \after has a jump instruction at the end
1044  */
1045
1046 static void
1047 insert_block_after_block(nir_block *block, nir_block *after, bool has_jump)
1048 {
1049    foreach_list_typed(nir_instr, instr, node, &after->instr_list) {
1050       instr->block = block;
1051    }
1052
1053    exec_list_append(&block->instr_list, &after->instr_list);
1054
1055    if (has_jump)
1056       handle_jump(block);
1057 }
1058
1059 static void
1060 update_if_uses(nir_cf_node *node)
1061 {
1062    if (node->type != nir_cf_node_if)
1063       return;
1064
1065    nir_if *if_stmt = nir_cf_node_as_if(node);
1066
1067    if_stmt->condition.parent_if = if_stmt;
1068    if (if_stmt->condition.is_ssa) {
1069       list_addtail(&if_stmt->condition.use_link,
1070                    &if_stmt->condition.ssa->if_uses);
1071    } else {
1072       list_addtail(&if_stmt->condition.use_link,
1073                    &if_stmt->condition.reg.reg->if_uses);
1074    }
1075 }
1076
1077 void
1078 nir_cf_node_insert_after(nir_cf_node *node, nir_cf_node *after)
1079 {
1080    update_if_uses(after);
1081
1082    if (after->type == nir_cf_node_block) {
1083       /*
1084        * either node or the one after it must be a basic block, by invariant #2;
1085        * in either case, just merge the blocks together.
1086        */
1087       nir_block *after_block = nir_cf_node_as_block(after);
1088
1089       bool has_jump = !exec_list_is_empty(&after_block->instr_list) &&
1090          nir_block_last_instr(after_block)->type == nir_instr_type_jump;
1091
1092       if (node->type == nir_cf_node_block) {
1093          insert_block_after_block(nir_cf_node_as_block(node), after_block,
1094                                   has_jump);
1095       } else {
1096          nir_cf_node *next = nir_cf_node_next(node);
1097          assert(next->type == nir_cf_node_block);
1098          nir_block *next_block = nir_cf_node_as_block(next);
1099
1100          insert_block_before_block(next_block, after_block, has_jump);
1101       }
1102    } else {
1103       if (node->type == nir_cf_node_block) {
1104          insert_non_block_after_block(nir_cf_node_as_block(node), after);
1105       } else {
1106          /*
1107           * We have to insert a non-basic block after a non-basic block. Since
1108           * every non-basic block has a basic block after it, this is equivalent
1109           * to inserting a non-basic block before a basic block.
1110           */
1111
1112          nir_cf_node *next = nir_cf_node_next(node);
1113          assert(next->type == nir_cf_node_block);
1114          nir_block *next_block = nir_cf_node_as_block(next);
1115
1116          insert_non_block_before_block(after, next_block);
1117       }
1118    }
1119
1120    nir_function_impl *impl = nir_cf_node_get_function(node);
1121    nir_metadata_preserve(impl, nir_metadata_none);
1122 }
1123
1124 void
1125 nir_cf_node_insert_before(nir_cf_node *node, nir_cf_node *before)
1126 {
1127    update_if_uses(before);
1128
1129    if (before->type == nir_cf_node_block) {
1130       nir_block *before_block = nir_cf_node_as_block(before);
1131
1132       bool has_jump = !exec_list_is_empty(&before_block->instr_list) &&
1133          nir_block_last_instr(before_block)->type == nir_instr_type_jump;
1134
1135       if (node->type == nir_cf_node_block) {
1136          insert_block_before_block(nir_cf_node_as_block(node), before_block,
1137                                    has_jump);
1138       } else {
1139          nir_cf_node *prev = nir_cf_node_prev(node);
1140          assert(prev->type == nir_cf_node_block);
1141          nir_block *prev_block = nir_cf_node_as_block(prev);
1142
1143          insert_block_after_block(prev_block, before_block, has_jump);
1144       }
1145    } else {
1146       if (node->type == nir_cf_node_block) {
1147          insert_non_block_before_block(before, nir_cf_node_as_block(node));
1148       } else {
1149          /*
1150           * We have to insert a non-basic block before a non-basic block. This
1151           * is equivalent to inserting a non-basic block after a basic block.
1152           */
1153
1154          nir_cf_node *prev_node = nir_cf_node_prev(node);
1155          assert(prev_node->type == nir_cf_node_block);
1156          nir_block *prev_block = nir_cf_node_as_block(prev_node);
1157
1158          insert_non_block_after_block(prev_block, before);
1159       }
1160    }
1161
1162    nir_function_impl *impl = nir_cf_node_get_function(node);
1163    nir_metadata_preserve(impl, nir_metadata_none);
1164 }
1165
1166 void
1167 nir_cf_node_insert_begin(struct exec_list *list, nir_cf_node *node)
1168 {
1169    nir_cf_node *begin = exec_node_data(nir_cf_node, list->head, node);
1170    nir_cf_node_insert_before(begin, node);
1171 }
1172
1173 void
1174 nir_cf_node_insert_end(struct exec_list *list, nir_cf_node *node)
1175 {
1176    nir_cf_node *end = exec_node_data(nir_cf_node, list->tail_pred, node);
1177    nir_cf_node_insert_after(end, node);
1178 }
1179
1180 /**
1181  * Stitch two basic blocks together into one. The aggregate must have the same
1182  * predecessors as the first and the same successors as the second.
1183  */
1184
1185 static void
1186 stitch_blocks(nir_block *before, nir_block *after)
1187 {
1188    /*
1189     * We move after into before, so we have to deal with up to 2 successors vs.
1190     * possibly a large number of predecessors.
1191     *
1192     * TODO: special case when before is empty and after isn't?
1193     */
1194
1195    move_successors(after, before);
1196
1197    foreach_list_typed(nir_instr, instr, node, &after->instr_list) {
1198       instr->block = before;
1199    }
1200
1201    exec_list_append(&before->instr_list, &after->instr_list);
1202    exec_node_remove(&after->cf_node.node);
1203 }
1204
1205 static void
1206 remove_defs_uses(nir_instr *instr);
1207
1208 static void
1209 cleanup_cf_node(nir_cf_node *node)
1210 {
1211    switch (node->type) {
1212    case nir_cf_node_block: {
1213       nir_block *block = nir_cf_node_as_block(node);
1214       /* We need to walk the instructions and clean up defs/uses */
1215       nir_foreach_instr(block, instr) {
1216          if (instr->type != nir_instr_type_jump)
1217             nir_instr_remove(instr);
1218       }
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 }