src/glsl/nir/nir.c

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