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