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