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 "nir_control_flow_private.h"
  30 #include <assert.h>
  31
  32 nir_shader *
  33 nir_shader_create(void *mem_ctx,
  34                   gl_shader_stage stage,
  35                   const nir_shader_compiler_options *options)
  36 {
  37    nir_shader *shader = ralloc(mem_ctx, nir_shader);
  38
  39    exec_list_make_empty(&shader->uniforms);
  40    exec_list_make_empty(&shader->inputs);
  41    exec_list_make_empty(&shader->outputs);
  42
  43    shader->options = options;
  44    memset(&shader->info, 0, sizeof(shader->info));
  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    shader->stage = stage;
  57
  58    return shader;
  59 }
  60
  61 static nir_register *
  62 reg_create(void *mem_ctx, struct exec_list *list)
  63 {
  64    nir_register *reg = ralloc(mem_ctx, nir_register);
  65
  66    list_inithead(&reg->uses);
  67    list_inithead(&reg->defs);
  68    list_inithead(&reg->if_uses);
  69
  70    reg->num_components = 0;
  71    reg->num_array_elems = 0;
  72    reg->is_packed = false;
  73    reg->name = NULL;
  74
  75    exec_list_push_tail(list, &reg->node);
  76
  77    return reg;
  78 }
  79
  80 nir_register *
  81 nir_global_reg_create(nir_shader *shader)
  82 {
  83    nir_register *reg = reg_create(shader, &shader->registers);
  84    reg->index = shader->reg_alloc++;
  85    reg->is_global = true;
  86
  87    return reg;
  88 }
  89
  90 nir_register *
  91 nir_local_reg_create(nir_function_impl *impl)
  92 {
  93    nir_register *reg = reg_create(ralloc_parent(impl), &impl->registers);
  94    reg->index = impl->reg_alloc++;
  95    reg->is_global = false;
  96
  97    return reg;
  98 }
  99
 100 void
 101 nir_reg_remove(nir_register *reg)
 102 {
 103    exec_node_remove(&reg->node);
 104 }
 105
 106 void
 107 nir_shader_add_variable(nir_shader *shader, nir_variable *var)
 108 {
 109    switch (var->data.mode) {
 110    case nir_var_all:
 111       assert(!"invalid mode");
 112       break;
 113
 114    case nir_var_local:
 115       assert(!"nir_shader_add_variable cannot be used for local variables");
 116       break;
 117
 118    case nir_var_global:
 119       exec_list_push_tail(&shader->globals, &var->node);
 120       break;
 121
 122    case nir_var_shader_in:
 123       exec_list_push_tail(&shader->inputs, &var->node);
 124       break;
 125
 126    case nir_var_shader_out:
 127       exec_list_push_tail(&shader->outputs, &var->node);
 128       break;
 129
 130    case nir_var_uniform:
 131    case nir_var_shader_storage:
 132       exec_list_push_tail(&shader->uniforms, &var->node);
 133       break;
 134
 135    case nir_var_system_value:
 136       exec_list_push_tail(&shader->system_values, &var->node);
 137       break;
 138    }
 139 }
 140
 141 nir_variable *
 142 nir_variable_create(nir_shader *shader, nir_variable_mode mode,
 143                     const struct glsl_type *type, const char *name)
 144 {
 145    nir_variable *var = rzalloc(shader, nir_variable);
 146    var->name = ralloc_strdup(var, name);
 147    var->type = type;
 148    var->data.mode = mode;
 149
 150    if ((mode == nir_var_shader_in && shader->stage != MESA_SHADER_VERTEX) ||
 151        (mode == nir_var_shader_out && shader->stage != MESA_SHADER_FRAGMENT))
 152       var->data.interpolation = INTERP_QUALIFIER_SMOOTH;
 153
 154    if (mode == nir_var_shader_in || mode == nir_var_uniform)
 155       var->data.read_only = true;
 156
 157    nir_shader_add_variable(shader, var);
 158
 159    return var;
 160 }
 161
 162 nir_variable *
 163 nir_local_variable_create(nir_function_impl *impl,
 164                           const struct glsl_type *type, const char *name)
 165 {
 166    nir_variable *var = rzalloc(impl->overload->function->shader, nir_variable);
 167    var->name = ralloc_strdup(var, name);
 168    var->type = type;
 169    var->data.mode = nir_var_local;
 170
 171    nir_function_impl_add_variable(impl, var);
 172
 173    return var;
 174 }
 175
 176 nir_function *
 177 nir_function_create(nir_shader *shader, const char *name)
 178 {
 179    nir_function *func = ralloc(shader, nir_function);
 180
 181    exec_list_push_tail(&shader->functions, &func->node);
 182    exec_list_make_empty(&func->overload_list);
 183    func->name = ralloc_strdup(func, name);
 184    func->shader = shader;
 185
 186    return func;
 187 }
 188
 189 nir_function_overload *
 190 nir_function_overload_create(nir_function *func)
 191 {
 192    void *mem_ctx = ralloc_parent(func);
 193
 194    nir_function_overload *overload = ralloc(mem_ctx, nir_function_overload);
 195
 196    overload->num_params = 0;
 197    overload->params = NULL;
 198    overload->return_type = glsl_void_type();
 199    overload->impl = NULL;
 200
 201    exec_list_push_tail(&func->overload_list, &overload->node);
 202    overload->function = func;
 203
 204    return overload;
 205 }
 206
 207 void nir_src_copy(nir_src *dest, const nir_src *src, void *mem_ctx)
 208 {
 209    dest->is_ssa = src->is_ssa;
 210    if (src->is_ssa) {
 211       dest->ssa = src->ssa;
 212    } else {
 213       dest->reg.base_offset = src->reg.base_offset;
 214       dest->reg.reg = src->reg.reg;
 215       if (src->reg.indirect) {
 216          dest->reg.indirect = ralloc(mem_ctx, nir_src);
 217          nir_src_copy(dest->reg.indirect, src->reg.indirect, mem_ctx);
 218       } else {
 219          dest->reg.indirect = NULL;
 220       }
 221    }
 222 }
 223
 224 void nir_dest_copy(nir_dest *dest, const nir_dest *src, nir_instr *instr)
 225 {
 226    /* Copying an SSA definition makes no sense whatsoever. */
 227    assert(!src->is_ssa);
 228
 229    dest->is_ssa = false;
 230
 231    dest->reg.base_offset = src->reg.base_offset;
 232    dest->reg.reg = src->reg.reg;
 233    if (src->reg.indirect) {
 234       dest->reg.indirect = ralloc(instr, nir_src);
 235       nir_src_copy(dest->reg.indirect, src->reg.indirect, instr);
 236    } else {
 237       dest->reg.indirect = NULL;
 238    }
 239 }
 240
 241 void
 242 nir_alu_src_copy(nir_alu_src *dest, const nir_alu_src *src,
 243                  nir_alu_instr *instr)
 244 {
 245    nir_src_copy(&dest->src, &src->src, &instr->instr);
 246    dest->abs = src->abs;
 247    dest->negate = src->negate;
 248    for (unsigned i = 0; i < 4; i++)
 249       dest->swizzle[i] = src->swizzle[i];
 250 }
 251
 252 void
 253 nir_alu_dest_copy(nir_alu_dest *dest, const nir_alu_dest *src,
 254                   nir_alu_instr *instr)
 255 {
 256    nir_dest_copy(&dest->dest, &src->dest, &instr->instr);
 257    dest->write_mask = src->write_mask;
 258    dest->saturate = src->saturate;
 259 }
 260
 261
 262 static void
 263 cf_init(nir_cf_node *node, nir_cf_node_type type)
 264 {
 265    exec_node_init(&node->node);
 266    node->parent = NULL;
 267    node->type = type;
 268 }
 269
 270 nir_function_impl *
 271 nir_function_impl_create(nir_function_overload *overload)
 272 {
 273    assert(overload->impl == NULL);
 274
 275    void *mem_ctx = ralloc_parent(overload);
 276
 277    nir_function_impl *impl = ralloc(mem_ctx, nir_function_impl);
 278
 279    overload->impl = impl;
 280    impl->overload = overload;
 281
 282    cf_init(&impl->cf_node, nir_cf_node_function);
 283
 284    exec_list_make_empty(&impl->body);
 285    exec_list_make_empty(&impl->registers);
 286    exec_list_make_empty(&impl->locals);
 287    impl->num_params = 0;
 288    impl->params = NULL;
 289    impl->return_var = NULL;
 290    impl->reg_alloc = 0;
 291    impl->ssa_alloc = 0;
 292    impl->valid_metadata = nir_metadata_none;
 293
 294    /* create start & end blocks */
 295    nir_block *start_block = nir_block_create(mem_ctx);
 296    nir_block *end_block = nir_block_create(mem_ctx);
 297    start_block->cf_node.parent = &impl->cf_node;
 298    end_block->cf_node.parent = &impl->cf_node;
 299    impl->end_block = end_block;
 300
 301    exec_list_push_tail(&impl->body, &start_block->cf_node.node);
 302
 303    start_block->successors[0] = end_block;
 304    _mesa_set_add(end_block->predecessors, start_block);
 305    return impl;
 306 }
 307
 308 nir_block *
 309 nir_block_create(nir_shader *shader)
 310 {
 311    nir_block *block = ralloc(shader, nir_block);
 312
 313    cf_init(&block->cf_node, nir_cf_node_block);
 314
 315    block->successors[0] = block->successors[1] = NULL;
 316    block->predecessors = _mesa_set_create(block, _mesa_hash_pointer,
 317                                           _mesa_key_pointer_equal);
 318    block->imm_dom = NULL;
 319    /* XXX maybe it would be worth it to defer allocation?  This
 320     * way it doesn't get allocated for shader ref's that never run
 321     * nir_calc_dominance?  For example, state-tracker creates an
 322     * initial IR, clones that, runs appropriate lowering pass, passes
 323     * to driver which does common lowering/opt, and then stores ref
 324     * which is later used to do state specific lowering and futher
 325     * opt.  Do any of the references not need dominance metadata?
 326     */
 327    block->dom_frontier = _mesa_set_create(block, _mesa_hash_pointer,
 328                                           _mesa_key_pointer_equal);
 329
 330    exec_list_make_empty(&block->instr_list);
 331
 332    return block;
 333 }
 334
 335 static inline void
 336 src_init(nir_src *src)
 337 {
 338    src->is_ssa = false;
 339    src->reg.reg = NULL;
 340    src->reg.indirect = NULL;
 341    src->reg.base_offset = 0;
 342 }
 343
 344 nir_if *
 345 nir_if_create(nir_shader *shader)
 346 {
 347    nir_if *if_stmt = ralloc(shader, nir_if);
 348
 349    cf_init(&if_stmt->cf_node, nir_cf_node_if);
 350    src_init(&if_stmt->condition);
 351
 352    nir_block *then = nir_block_create(shader);
 353    exec_list_make_empty(&if_stmt->then_list);
 354    exec_list_push_tail(&if_stmt->then_list, &then->cf_node.node);
 355    then->cf_node.parent = &if_stmt->cf_node;
 356
 357    nir_block *else_stmt = nir_block_create(shader);
 358    exec_list_make_empty(&if_stmt->else_list);
 359    exec_list_push_tail(&if_stmt->else_list, &else_stmt->cf_node.node);
 360    else_stmt->cf_node.parent = &if_stmt->cf_node;
 361
 362    return if_stmt;
 363 }
 364
 365 nir_loop *
 366 nir_loop_create(nir_shader *shader)
 367 {
 368    nir_loop *loop = ralloc(shader, nir_loop);
 369
 370    cf_init(&loop->cf_node, nir_cf_node_loop);
 371
 372    nir_block *body = nir_block_create(shader);
 373    exec_list_make_empty(&loop->body);
 374    exec_list_push_tail(&loop->body, &body->cf_node.node);
 375    body->cf_node.parent = &loop->cf_node;
 376
 377    body->successors[0] = body;
 378    _mesa_set_add(body->predecessors, body);
 379
 380    return loop;
 381 }
 382
 383 static void
 384 instr_init(nir_instr *instr, nir_instr_type type)
 385 {
 386    instr->type = type;
 387    instr->block = NULL;
 388    exec_node_init(&instr->node);
 389 }
 390
 391 static void
 392 dest_init(nir_dest *dest)
 393 {
 394    dest->is_ssa = false;
 395    dest->reg.reg = NULL;
 396    dest->reg.indirect = NULL;
 397    dest->reg.base_offset = 0;
 398 }
 399
 400 static void
 401 alu_dest_init(nir_alu_dest *dest)
 402 {
 403    dest_init(&dest->dest);
 404    dest->saturate = false;
 405    dest->write_mask = 0xf;
 406 }
 407
 408 static void
 409 alu_src_init(nir_alu_src *src)
 410 {
 411    src_init(&src->src);
 412    src->abs = src->negate = false;
 413    src->swizzle[0] = 0;
 414    src->swizzle[1] = 1;
 415    src->swizzle[2] = 2;
 416    src->swizzle[3] = 3;
 417 }
 418
 419 nir_alu_instr *
 420 nir_alu_instr_create(nir_shader *shader, nir_op op)
 421 {
 422    unsigned num_srcs = nir_op_infos[op].num_inputs;
 423    nir_alu_instr *instr =
 424       ralloc_size(shader,
 425                   sizeof(nir_alu_instr) + num_srcs * sizeof(nir_alu_src));
 426
 427    instr_init(&instr->instr, nir_instr_type_alu);
 428    instr->op = op;
 429    alu_dest_init(&instr->dest);
 430    for (unsigned i = 0; i < num_srcs; i++)
 431       alu_src_init(&instr->src[i]);
 432
 433    return instr;
 434 }
 435
 436 nir_jump_instr *
 437 nir_jump_instr_create(nir_shader *shader, nir_jump_type type)
 438 {
 439    nir_jump_instr *instr = ralloc(shader, nir_jump_instr);
 440    instr_init(&instr->instr, nir_instr_type_jump);
 441    instr->type = type;
 442    return instr;
 443 }
 444
 445 nir_load_const_instr *
 446 nir_load_const_instr_create(nir_shader *shader, unsigned num_components)
 447 {
 448    nir_load_const_instr *instr = ralloc(shader, nir_load_const_instr);
 449    instr_init(&instr->instr, nir_instr_type_load_const);
 450
 451    nir_ssa_def_init(&instr->instr, &instr->def, num_components, NULL);
 452
 453    return instr;
 454 }
 455
 456 nir_intrinsic_instr *
 457 nir_intrinsic_instr_create(nir_shader *shader, nir_intrinsic_op op)
 458 {
 459    unsigned num_srcs = nir_intrinsic_infos[op].num_srcs;
 460    nir_intrinsic_instr *instr =
 461       ralloc_size(shader,
 462                   sizeof(nir_intrinsic_instr) + num_srcs * sizeof(nir_src));
 463
 464    instr_init(&instr->instr, nir_instr_type_intrinsic);
 465    instr->intrinsic = op;
 466
 467    if (nir_intrinsic_infos[op].has_dest)
 468       dest_init(&instr->dest);
 469
 470    for (unsigned i = 0; i < num_srcs; i++)
 471       src_init(&instr->src[i]);
 472
 473    return instr;
 474 }
 475
 476 nir_call_instr *
 477 nir_call_instr_create(nir_shader *shader, nir_function_overload *callee)
 478 {
 479    nir_call_instr *instr = ralloc(shader, nir_call_instr);
 480    instr_init(&instr->instr, nir_instr_type_call);
 481
 482    instr->callee = callee;
 483    instr->num_params = callee->num_params;
 484    instr->params = ralloc_array(instr, nir_deref_var *, instr->num_params);
 485    instr->return_deref = NULL;
 486
 487    return instr;
 488 }
 489
 490 nir_tex_instr *
 491 nir_tex_instr_create(nir_shader *shader, unsigned num_srcs)
 492 {
 493    nir_tex_instr *instr = rzalloc(shader, nir_tex_instr);
 494    instr_init(&instr->instr, nir_instr_type_tex);
 495
 496    dest_init(&instr->dest);
 497
 498    instr->num_srcs = num_srcs;
 499    instr->src = ralloc_array(instr, nir_tex_src, num_srcs);
 500    for (unsigned i = 0; i < num_srcs; i++)
 501       src_init(&instr->src[i].src);
 502
 503    instr->texture_index = 0;
 504    instr->texture_array_size = 0;
 505    instr->texture = NULL;
 506    instr->sampler_index = 0;
 507    instr->sampler = NULL;
 508
 509    return instr;
 510 }
 511
 512 nir_phi_instr *
 513 nir_phi_instr_create(nir_shader *shader)
 514 {
 515    nir_phi_instr *instr = ralloc(shader, nir_phi_instr);
 516    instr_init(&instr->instr, nir_instr_type_phi);
 517
 518    dest_init(&instr->dest);
 519    exec_list_make_empty(&instr->srcs);
 520    return instr;
 521 }
 522
 523 nir_parallel_copy_instr *
 524 nir_parallel_copy_instr_create(nir_shader *shader)
 525 {
 526    nir_parallel_copy_instr *instr = ralloc(shader, nir_parallel_copy_instr);
 527    instr_init(&instr->instr, nir_instr_type_parallel_copy);
 528
 529    exec_list_make_empty(&instr->entries);
 530
 531    return instr;
 532 }
 533
 534 nir_ssa_undef_instr *
 535 nir_ssa_undef_instr_create(nir_shader *shader, unsigned num_components)
 536 {
 537    nir_ssa_undef_instr *instr = ralloc(shader, nir_ssa_undef_instr);
 538    instr_init(&instr->instr, nir_instr_type_ssa_undef);
 539
 540    nir_ssa_def_init(&instr->instr, &instr->def, num_components, NULL);
 541
 542    return instr;
 543 }
 544
 545 nir_deref_var *
 546 nir_deref_var_create(void *mem_ctx, nir_variable *var)
 547 {
 548    nir_deref_var *deref = ralloc(mem_ctx, nir_deref_var);
 549    deref->deref.deref_type = nir_deref_type_var;
 550    deref->deref.child = NULL;
 551    deref->deref.type = var->type;
 552    deref->var = var;
 553    return deref;
 554 }
 555
 556 nir_deref_array *
 557 nir_deref_array_create(void *mem_ctx)
 558 {
 559    nir_deref_array *deref = ralloc(mem_ctx, nir_deref_array);
 560    deref->deref.deref_type = nir_deref_type_array;
 561    deref->deref.child = NULL;
 562    deref->deref_array_type = nir_deref_array_type_direct;
 563    src_init(&deref->indirect);
 564    deref->base_offset = 0;
 565    return deref;
 566 }
 567
 568 nir_deref_struct *
 569 nir_deref_struct_create(void *mem_ctx, unsigned field_index)
 570 {
 571    nir_deref_struct *deref = ralloc(mem_ctx, nir_deref_struct);
 572    deref->deref.deref_type = nir_deref_type_struct;
 573    deref->deref.child = NULL;
 574    deref->index = field_index;
 575    return deref;
 576 }
 577
 578 static nir_deref_var *
 579 copy_deref_var(void *mem_ctx, nir_deref_var *deref)
 580 {
 581    nir_deref_var *ret = nir_deref_var_create(mem_ctx, deref->var);
 582    ret->deref.type = deref->deref.type;
 583    if (deref->deref.child)
 584       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 585    return ret;
 586 }
 587
 588 static nir_deref_array *
 589 copy_deref_array(void *mem_ctx, nir_deref_array *deref)
 590 {
 591    nir_deref_array *ret = nir_deref_array_create(mem_ctx);
 592    ret->base_offset = deref->base_offset;
 593    ret->deref_array_type = deref->deref_array_type;
 594    if (deref->deref_array_type == nir_deref_array_type_indirect) {
 595       nir_src_copy(&ret->indirect, &deref->indirect, mem_ctx);
 596    }
 597    ret->deref.type = deref->deref.type;
 598    if (deref->deref.child)
 599       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 600    return ret;
 601 }
 602
 603 static nir_deref_struct *
 604 copy_deref_struct(void *mem_ctx, nir_deref_struct *deref)
 605 {
 606    nir_deref_struct *ret = nir_deref_struct_create(mem_ctx, deref->index);
 607    ret->deref.type = deref->deref.type;
 608    if (deref->deref.child)
 609       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 610    return ret;
 611 }
 612
 613 nir_deref *
 614 nir_copy_deref(void *mem_ctx, nir_deref *deref)
 615 {
 616    switch (deref->deref_type) {
 617    case nir_deref_type_var:
 618       return &copy_deref_var(mem_ctx, nir_deref_as_var(deref))->deref;
 619    case nir_deref_type_array:
 620       return &copy_deref_array(mem_ctx, nir_deref_as_array(deref))->deref;
 621    case nir_deref_type_struct:
 622       return &copy_deref_struct(mem_ctx, nir_deref_as_struct(deref))->deref;
 623    default:
 624       unreachable("Invalid dereference type");
 625    }
 626
 627    return NULL;
 628 }
 629
 630 /* Returns a load_const instruction that represents the constant
 631  * initializer for the given deref chain.  The caller is responsible for
 632  * ensuring that there actually is a constant initializer.
 633  */
 634 nir_load_const_instr *
 635 nir_deref_get_const_initializer_load(nir_shader *shader, nir_deref_var *deref)
 636 {
 637    nir_constant *constant = deref->var->constant_initializer;
 638    assert(constant);
 639
 640    const nir_deref *tail = &deref->deref;
 641    unsigned matrix_offset = 0;
 642    while (tail->child) {
 643       switch (tail->child->deref_type) {
 644       case nir_deref_type_array: {
 645          nir_deref_array *arr = nir_deref_as_array(tail->child);
 646          assert(arr->deref_array_type == nir_deref_array_type_direct);
 647          if (glsl_type_is_matrix(tail->type)) {
 648             assert(arr->deref.child == NULL);
 649             matrix_offset = arr->base_offset;
 650          } else {
 651             constant = constant->elements[arr->base_offset];
 652          }
 653          break;
 654       }
 655
 656       case nir_deref_type_struct: {
 657          constant = constant->elements[nir_deref_as_struct(tail->child)->index];
 658          break;
 659       }
 660
 661       default:
 662          unreachable("Invalid deref child type");
 663       }
 664
 665       tail = tail->child;
 666    }
 667
 668    nir_load_const_instr *load =
 669       nir_load_const_instr_create(shader, glsl_get_vector_elements(tail->type));
 670
 671    matrix_offset *= load->def.num_components;
 672    for (unsigned i = 0; i < load->def.num_components; i++) {
 673       switch (glsl_get_base_type(tail->type)) {
 674       case GLSL_TYPE_FLOAT:
 675       case GLSL_TYPE_INT:
 676       case GLSL_TYPE_UINT:
 677          load->value.u[i] = constant->value.u[matrix_offset + i];
 678          break;
 679       case GLSL_TYPE_BOOL:
 680          load->value.u[i] = constant->value.b[matrix_offset + i] ?
 681                              NIR_TRUE : NIR_FALSE;
 682          break;
 683       default:
 684          unreachable("Invalid immediate type");
 685       }
 686    }
 687
 688    return load;
 689 }
 690
 691 nir_function_impl *
 692 nir_cf_node_get_function(nir_cf_node *node)
 693 {
 694    while (node->type != nir_cf_node_function) {
 695       node = node->parent;
 696    }
 697
 698    return nir_cf_node_as_function(node);
 699 }
 700
 701 static bool
 702 add_use_cb(nir_src *src, void *state)
 703 {
 704    nir_instr *instr = state;
 705
 706    src->parent_instr = instr;
 707    list_addtail(&src->use_link,
 708                 src->is_ssa ? &src->ssa->uses : &src->reg.reg->uses);
 709
 710    return true;
 711 }
 712
 713 static bool
 714 add_ssa_def_cb(nir_ssa_def *def, void *state)
 715 {
 716    nir_instr *instr = state;
 717
 718    if (instr->block && def->index == UINT_MAX) {
 719       nir_function_impl *impl =
 720          nir_cf_node_get_function(&instr->block->cf_node);
 721
 722       def->index = impl->ssa_alloc++;
 723    }
 724
 725    return true;
 726 }
 727
 728 static bool
 729 add_reg_def_cb(nir_dest *dest, void *state)
 730 {
 731    nir_instr *instr = state;
 732
 733    if (!dest->is_ssa) {
 734       dest->reg.parent_instr = instr;
 735       list_addtail(&dest->reg.def_link, &dest->reg.reg->defs);
 736    }
 737
 738    return true;
 739 }
 740
 741 static void
 742 add_defs_uses(nir_instr *instr)
 743 {
 744    nir_foreach_src(instr, add_use_cb, instr);
 745    nir_foreach_dest(instr, add_reg_def_cb, instr);
 746    nir_foreach_ssa_def(instr, add_ssa_def_cb, instr);
 747 }
 748
 749 void
 750 nir_instr_insert(nir_cursor cursor, nir_instr *instr)
 751 {
 752    switch (cursor.option) {
 753    case nir_cursor_before_block:
 754       /* Only allow inserting jumps into empty blocks. */
 755       if (instr->type == nir_instr_type_jump)
 756          assert(exec_list_is_empty(&cursor.block->instr_list));
 757
 758       instr->block = cursor.block;
 759       add_defs_uses(instr);
 760       exec_list_push_head(&cursor.block->instr_list, &instr->node);
 761       break;
 762    case nir_cursor_after_block: {
 763       /* Inserting instructions after a jump is illegal. */
 764       nir_instr *last = nir_block_last_instr(cursor.block);
 765       assert(last == NULL || last->type != nir_instr_type_jump);
 766       (void) last;
 767
 768       instr->block = cursor.block;
 769       add_defs_uses(instr);
 770       exec_list_push_tail(&cursor.block->instr_list, &instr->node);
 771       break;
 772    }
 773    case nir_cursor_before_instr:
 774       assert(instr->type != nir_instr_type_jump);
 775       instr->block = cursor.instr->block;
 776       add_defs_uses(instr);
 777       exec_node_insert_node_before(&cursor.instr->node, &instr->node);
 778       break;
 779    case nir_cursor_after_instr:
 780       /* Inserting instructions after a jump is illegal. */
 781       assert(cursor.instr->type != nir_instr_type_jump);
 782
 783       /* Only allow inserting jumps at the end of the block. */
 784       if (instr->type == nir_instr_type_jump)
 785          assert(cursor.instr == nir_block_last_instr(cursor.instr->block));
 786
 787       instr->block = cursor.instr->block;
 788       add_defs_uses(instr);
 789       exec_node_insert_after(&cursor.instr->node, &instr->node);
 790       break;
 791    }
 792
 793    if (instr->type == nir_instr_type_jump)
 794       nir_handle_add_jump(instr->block);
 795 }
 796
 797 static bool
 798 src_is_valid(const nir_src *src)
 799 {
 800    return src->is_ssa ? (src->ssa != NULL) : (src->reg.reg != NULL);
 801 }
 802
 803 static bool
 804 remove_use_cb(nir_src *src, void *state)
 805 {
 806    if (src_is_valid(src))
 807       list_del(&src->use_link);
 808
 809    return true;
 810 }
 811
 812 static bool
 813 remove_def_cb(nir_dest *dest, void *state)
 814 {
 815    if (!dest->is_ssa)
 816       list_del(&dest->reg.def_link);
 817
 818    return true;
 819 }
 820
 821 static void
 822 remove_defs_uses(nir_instr *instr)
 823 {
 824    nir_foreach_dest(instr, remove_def_cb, instr);
 825    nir_foreach_src(instr, remove_use_cb, instr);
 826 }
 827
 828 void nir_instr_remove(nir_instr *instr)
 829 {
 830    remove_defs_uses(instr);
 831    exec_node_remove(&instr->node);
 832
 833    if (instr->type == nir_instr_type_jump) {
 834       nir_jump_instr *jump_instr = nir_instr_as_jump(instr);
 835       nir_handle_remove_jump(instr->block, jump_instr->type);
 836    }
 837 }
 838
 839 /*@}*/
 840
 841 void
 842 nir_index_local_regs(nir_function_impl *impl)
 843 {
 844    unsigned index = 0;
 845    foreach_list_typed(nir_register, reg, node, &impl->registers) {
 846       reg->index = index++;
 847    }
 848    impl->reg_alloc = index;
 849 }
 850
 851 void
 852 nir_index_global_regs(nir_shader *shader)
 853 {
 854    unsigned index = 0;
 855    foreach_list_typed(nir_register, reg, node, &shader->registers) {
 856       reg->index = index++;
 857    }
 858    shader->reg_alloc = index;
 859 }
 860
 861 static bool
 862 visit_alu_dest(nir_alu_instr *instr, nir_foreach_dest_cb cb, void *state)
 863 {
 864    return cb(&instr->dest.dest, state);
 865 }
 866
 867 static bool
 868 visit_intrinsic_dest(nir_intrinsic_instr *instr, nir_foreach_dest_cb cb,
 869                      void *state)
 870 {
 871    if (nir_intrinsic_infos[instr->intrinsic].has_dest)
 872       return cb(&instr->dest, state);
 873
 874    return true;
 875 }
 876
 877 static bool
 878 visit_texture_dest(nir_tex_instr *instr, nir_foreach_dest_cb cb,
 879                    void *state)
 880 {
 881    return cb(&instr->dest, state);
 882 }
 883
 884 static bool
 885 visit_phi_dest(nir_phi_instr *instr, nir_foreach_dest_cb cb, void *state)
 886 {
 887    return cb(&instr->dest, state);
 888 }
 889
 890 static bool
 891 visit_parallel_copy_dest(nir_parallel_copy_instr *instr,
 892                          nir_foreach_dest_cb cb, void *state)
 893 {
 894    nir_foreach_parallel_copy_entry(instr, entry) {
 895       if (!cb(&entry->dest, state))
 896          return false;
 897    }
 898
 899    return true;
 900 }
 901
 902 bool
 903 nir_foreach_dest(nir_instr *instr, nir_foreach_dest_cb cb, void *state)
 904 {
 905    switch (instr->type) {
 906    case nir_instr_type_alu:
 907       return visit_alu_dest(nir_instr_as_alu(instr), cb, state);
 908    case nir_instr_type_intrinsic:
 909       return visit_intrinsic_dest(nir_instr_as_intrinsic(instr), cb, state);
 910    case nir_instr_type_tex:
 911       return visit_texture_dest(nir_instr_as_tex(instr), cb, state);
 912    case nir_instr_type_phi:
 913       return visit_phi_dest(nir_instr_as_phi(instr), cb, state);
 914    case nir_instr_type_parallel_copy:
 915       return visit_parallel_copy_dest(nir_instr_as_parallel_copy(instr),
 916                                       cb, state);
 917
 918    case nir_instr_type_load_const:
 919    case nir_instr_type_ssa_undef:
 920    case nir_instr_type_call:
 921    case nir_instr_type_jump:
 922       break;
 923
 924    default:
 925       unreachable("Invalid instruction type");
 926       break;
 927    }
 928
 929    return true;
 930 }
 931
 932 struct foreach_ssa_def_state {
 933    nir_foreach_ssa_def_cb cb;
 934    void *client_state;
 935 };
 936
 937 static inline bool
 938 nir_ssa_def_visitor(nir_dest *dest, void *void_state)
 939 {
 940    struct foreach_ssa_def_state *state = void_state;
 941
 942    if (dest->is_ssa)
 943       return state->cb(&dest->ssa, state->client_state);
 944    else
 945       return true;
 946 }
 947
 948 bool
 949 nir_foreach_ssa_def(nir_instr *instr, nir_foreach_ssa_def_cb cb, void *state)
 950 {
 951    switch (instr->type) {
 952    case nir_instr_type_alu:
 953    case nir_instr_type_tex:
 954    case nir_instr_type_intrinsic:
 955    case nir_instr_type_phi:
 956    case nir_instr_type_parallel_copy: {
 957       struct foreach_ssa_def_state foreach_state = {cb, state};
 958       return nir_foreach_dest(instr, nir_ssa_def_visitor, &foreach_state);
 959    }
 960
 961    case nir_instr_type_load_const:
 962       return cb(&nir_instr_as_load_const(instr)->def, state);
 963    case nir_instr_type_ssa_undef:
 964       return cb(&nir_instr_as_ssa_undef(instr)->def, state);
 965    case nir_instr_type_call:
 966    case nir_instr_type_jump:
 967       return true;
 968    default:
 969       unreachable("Invalid instruction type");
 970    }
 971 }
 972
 973 static bool
 974 visit_src(nir_src *src, nir_foreach_src_cb cb, void *state)
 975 {
 976    if (!cb(src, state))
 977       return false;
 978    if (!src->is_ssa && src->reg.indirect)
 979       return cb(src->reg.indirect, state);
 980    return true;
 981 }
 982
 983 static bool
 984 visit_deref_array_src(nir_deref_array *deref, nir_foreach_src_cb cb,
 985                       void *state)
 986 {
 987    if (deref->deref_array_type == nir_deref_array_type_indirect)
 988       return visit_src(&deref->indirect, cb, state);
 989    return true;
 990 }
 991
 992 static bool
 993 visit_deref_src(nir_deref_var *deref, nir_foreach_src_cb cb, void *state)
 994 {
 995    nir_deref *cur = &deref->deref;
 996    while (cur != NULL) {
 997       if (cur->deref_type == nir_deref_type_array)
 998          if (!visit_deref_array_src(nir_deref_as_array(cur), cb, state))
 999             return false;
1000
1001       cur = cur->child;
1002    }
1003
1004    return true;
1005 }
1006
1007 static bool
1008 visit_alu_src(nir_alu_instr *instr, nir_foreach_src_cb cb, void *state)
1009 {
1010    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++)
1011       if (!visit_src(&instr->src[i].src, cb, state))
1012          return false;
1013
1014    return true;
1015 }
1016
1017 static bool
1018 visit_tex_src(nir_tex_instr *instr, nir_foreach_src_cb cb, void *state)
1019 {
1020    for (unsigned i = 0; i < instr->num_srcs; i++)
1021       if (!visit_src(&instr->src[i].src, cb, state))
1022          return false;
1023
1024    if (instr->texture != NULL)
1025       if (!visit_deref_src(instr->texture, cb, state))
1026          return false;
1027
1028    if (instr->sampler != NULL)
1029       if (!visit_deref_src(instr->sampler, cb, state))
1030          return false;
1031
1032    return true;
1033 }
1034
1035 static bool
1036 visit_intrinsic_src(nir_intrinsic_instr *instr, nir_foreach_src_cb cb,
1037                     void *state)
1038 {
1039    unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
1040    for (unsigned i = 0; i < num_srcs; i++)
1041       if (!visit_src(&instr->src[i], cb, state))
1042          return false;
1043
1044    unsigned num_vars =
1045       nir_intrinsic_infos[instr->intrinsic].num_variables;
1046    for (unsigned i = 0; i < num_vars; i++)
1047       if (!visit_deref_src(instr->variables[i], cb, state))
1048          return false;
1049
1050    return true;
1051 }
1052
1053 static bool
1054 visit_call_src(nir_call_instr *instr, nir_foreach_src_cb cb, void *state)
1055 {
1056    return true;
1057 }
1058
1059 static bool
1060 visit_load_const_src(nir_load_const_instr *instr, nir_foreach_src_cb cb,
1061                      void *state)
1062 {
1063    return true;
1064 }
1065
1066 static bool
1067 visit_phi_src(nir_phi_instr *instr, nir_foreach_src_cb cb, void *state)
1068 {
1069    nir_foreach_phi_src(instr, src) {
1070       if (!visit_src(&src->src, cb, state))
1071          return false;
1072    }
1073
1074    return true;
1075 }
1076
1077 static bool
1078 visit_parallel_copy_src(nir_parallel_copy_instr *instr,
1079                         nir_foreach_src_cb cb, void *state)
1080 {
1081    nir_foreach_parallel_copy_entry(instr, entry) {
1082       if (!visit_src(&entry->src, cb, state))
1083          return false;
1084    }
1085
1086    return true;
1087 }
1088
1089 typedef struct {
1090    void *state;
1091    nir_foreach_src_cb cb;
1092 } visit_dest_indirect_state;
1093
1094 static bool
1095 visit_dest_indirect(nir_dest *dest, void *_state)
1096 {
1097    visit_dest_indirect_state *state = (visit_dest_indirect_state *) _state;
1098
1099    if (!dest->is_ssa && dest->reg.indirect)
1100       return state->cb(dest->reg.indirect, state->state);
1101
1102    return true;
1103 }
1104
1105 bool
1106 nir_foreach_src(nir_instr *instr, nir_foreach_src_cb cb, void *state)
1107 {
1108    switch (instr->type) {
1109    case nir_instr_type_alu:
1110       if (!visit_alu_src(nir_instr_as_alu(instr), cb, state))
1111          return false;
1112       break;
1113    case nir_instr_type_intrinsic:
1114       if (!visit_intrinsic_src(nir_instr_as_intrinsic(instr), cb, state))
1115          return false;
1116       break;
1117    case nir_instr_type_tex:
1118       if (!visit_tex_src(nir_instr_as_tex(instr), cb, state))
1119          return false;
1120       break;
1121    case nir_instr_type_call:
1122       if (!visit_call_src(nir_instr_as_call(instr), cb, state))
1123          return false;
1124       break;
1125    case nir_instr_type_load_const:
1126       if (!visit_load_const_src(nir_instr_as_load_const(instr), cb, state))
1127          return false;
1128       break;
1129    case nir_instr_type_phi:
1130       if (!visit_phi_src(nir_instr_as_phi(instr), cb, state))
1131          return false;
1132       break;
1133    case nir_instr_type_parallel_copy:
1134       if (!visit_parallel_copy_src(nir_instr_as_parallel_copy(instr),
1135                                    cb, state))
1136          return false;
1137       break;
1138    case nir_instr_type_jump:
1139    case nir_instr_type_ssa_undef:
1140       return true;
1141
1142    default:
1143       unreachable("Invalid instruction type");
1144       break;
1145    }
1146
1147    visit_dest_indirect_state dest_state;
1148    dest_state.state = state;
1149    dest_state.cb = cb;
1150    return nir_foreach_dest(instr, visit_dest_indirect, &dest_state);
1151 }
1152
1153 nir_const_value *
1154 nir_src_as_const_value(nir_src src)
1155 {
1156    if (!src.is_ssa)
1157       return NULL;
1158
1159    if (src.ssa->parent_instr->type != nir_instr_type_load_const)
1160       return NULL;
1161
1162    nir_load_const_instr *load = nir_instr_as_load_const(src.ssa->parent_instr);
1163
1164    return &load->value;
1165 }
1166
1167 /**
1168  * Returns true if the source is known to be dynamically uniform. Otherwise it
1169  * returns false which means it may or may not be dynamically uniform but it
1170  * can't be determined.
1171  */
1172 bool
1173 nir_src_is_dynamically_uniform(nir_src src)
1174 {
1175    if (!src.is_ssa)
1176       return false;
1177
1178    /* Constants are trivially dynamically uniform */
1179    if (src.ssa->parent_instr->type == nir_instr_type_load_const)
1180       return true;
1181
1182    /* As are uniform variables */
1183    if (src.ssa->parent_instr->type == nir_instr_type_intrinsic) {
1184       nir_intrinsic_instr *intr = nir_instr_as_intrinsic(src.ssa->parent_instr);
1185
1186       if (intr->intrinsic == nir_intrinsic_load_uniform)
1187          return true;
1188    }
1189
1190    /* XXX: this could have many more tests, such as when a sampler function is
1191     * called with dynamically uniform arguments.
1192     */
1193    return false;
1194 }
1195
1196 static void
1197 src_remove_all_uses(nir_src *src)
1198 {
1199    for (; src; src = src->is_ssa ? NULL : src->reg.indirect) {
1200       if (!src_is_valid(src))
1201          continue;
1202
1203       list_del(&src->use_link);
1204    }
1205 }
1206
1207 static void
1208 src_add_all_uses(nir_src *src, nir_instr *parent_instr, nir_if *parent_if)
1209 {
1210    for (; src; src = src->is_ssa ? NULL : src->reg.indirect) {
1211       if (!src_is_valid(src))
1212          continue;
1213
1214       if (parent_instr) {
1215          src->parent_instr = parent_instr;
1216          if (src->is_ssa)
1217             list_addtail(&src->use_link, &src->ssa->uses);
1218          else
1219             list_addtail(&src->use_link, &src->reg.reg->uses);
1220       } else {
1221          assert(parent_if);
1222          src->parent_if = parent_if;
1223          if (src->is_ssa)
1224             list_addtail(&src->use_link, &src->ssa->if_uses);
1225          else
1226             list_addtail(&src->use_link, &src->reg.reg->if_uses);
1227       }
1228    }
1229 }
1230
1231 void
1232 nir_instr_rewrite_src(nir_instr *instr, nir_src *src, nir_src new_src)
1233 {
1234    assert(!src_is_valid(src) || src->parent_instr == instr);
1235
1236    src_remove_all_uses(src);
1237    *src = new_src;
1238    src_add_all_uses(src, instr, NULL);
1239 }
1240
1241 void
1242 nir_instr_move_src(nir_instr *dest_instr, nir_src *dest, nir_src *src)
1243 {
1244    assert(!src_is_valid(dest) || dest->parent_instr == dest_instr);
1245
1246    src_remove_all_uses(dest);
1247    src_remove_all_uses(src);
1248    *dest = *src;
1249    *src = NIR_SRC_INIT;
1250    src_add_all_uses(dest, dest_instr, NULL);
1251 }
1252
1253 void
1254 nir_if_rewrite_condition(nir_if *if_stmt, nir_src new_src)
1255 {
1256    nir_src *src = &if_stmt->condition;
1257    assert(!src_is_valid(src) || src->parent_if == if_stmt);
1258
1259    src_remove_all_uses(src);
1260    *src = new_src;
1261    src_add_all_uses(src, NULL, if_stmt);
1262 }
1263
1264 void
1265 nir_instr_rewrite_dest(nir_instr *instr, nir_dest *dest, nir_dest new_dest)
1266 {
1267    if (dest->is_ssa) {
1268       /* We can only overwrite an SSA destination if it has no uses. */
1269       assert(list_empty(&dest->ssa.uses) && list_empty(&dest->ssa.if_uses));
1270    } else {
1271       list_del(&dest->reg.def_link);
1272       if (dest->reg.indirect)
1273          src_remove_all_uses(dest->reg.indirect);
1274    }
1275
1276    /* We can't re-write with an SSA def */
1277    assert(!new_dest.is_ssa);
1278
1279    nir_dest_copy(dest, &new_dest, instr);
1280
1281    dest->reg.parent_instr = instr;
1282    list_addtail(&dest->reg.def_link, &new_dest.reg.reg->defs);
1283
1284    if (dest->reg.indirect)
1285       src_add_all_uses(dest->reg.indirect, instr, NULL);
1286 }
1287
1288 void
1289 nir_ssa_def_init(nir_instr *instr, nir_ssa_def *def,
1290                  unsigned num_components, const char *name)
1291 {
1292    def->name = name;
1293    def->parent_instr = instr;
1294    list_inithead(&def->uses);
1295    list_inithead(&def->if_uses);
1296    def->num_components = num_components;
1297
1298    if (instr->block) {
1299       nir_function_impl *impl =
1300          nir_cf_node_get_function(&instr->block->cf_node);
1301
1302       def->index = impl->ssa_alloc++;
1303    } else {
1304       def->index = UINT_MAX;
1305    }
1306 }
1307
1308 void
1309 nir_ssa_dest_init(nir_instr *instr, nir_dest *dest,
1310                  unsigned num_components, const char *name)
1311 {
1312    dest->is_ssa = true;
1313    nir_ssa_def_init(instr, &dest->ssa, num_components, name);
1314 }
1315
1316 void
1317 nir_ssa_def_rewrite_uses(nir_ssa_def *def, nir_src new_src)
1318 {
1319    assert(!new_src.is_ssa || def != new_src.ssa);
1320
1321    nir_foreach_use_safe(def, use_src)
1322       nir_instr_rewrite_src(use_src->parent_instr, use_src, new_src);
1323
1324    nir_foreach_if_use_safe(def, use_src)
1325       nir_if_rewrite_condition(use_src->parent_if, new_src);
1326 }
1327
1328 static bool
1329 is_instr_between(nir_instr *start, nir_instr *end, nir_instr *between)
1330 {
1331    assert(start->block == end->block);
1332
1333    if (between->block != start->block)
1334       return false;
1335
1336    /* Search backwards looking for "between" */
1337    while (start != end) {
1338       if (between == end)
1339          return true;
1340
1341       end = nir_instr_prev(end);
1342       assert(end);
1343    }
1344
1345    return false;
1346 }
1347
1348 /* Replaces all uses of the given SSA def with the given source but only if
1349  * the use comes after the after_me instruction.  This can be useful if you
1350  * are emitting code to fix up the result of some instruction: you can freely
1351  * use the result in that code and then call rewrite_uses_after and pass the
1352  * last fixup instruction as after_me and it will replace all of the uses you
1353  * want without touching the fixup code.
1354  *
1355  * This function assumes that after_me is in the same block as
1356  * def->parent_instr and that after_me comes after def->parent_instr.
1357  */
1358 void
1359 nir_ssa_def_rewrite_uses_after(nir_ssa_def *def, nir_src new_src,
1360                                nir_instr *after_me)
1361 {
1362    assert(!new_src.is_ssa || def != new_src.ssa);
1363
1364    nir_foreach_use_safe(def, use_src) {
1365       assert(use_src->parent_instr != def->parent_instr);
1366       /* Since def already dominates all of its uses, the only way a use can
1367        * not be dominated by after_me is if it is between def and after_me in
1368        * the instruction list.
1369        */
1370       if (!is_instr_between(def->parent_instr, after_me, use_src->parent_instr))
1371          nir_instr_rewrite_src(use_src->parent_instr, use_src, new_src);
1372    }
1373
1374    nir_foreach_if_use_safe(def, use_src)
1375       nir_if_rewrite_condition(use_src->parent_if, new_src);
1376 }
1377
1378 static bool foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1379                             bool reverse, void *state);
1380
1381 static inline bool
1382 foreach_if(nir_if *if_stmt, nir_foreach_block_cb cb, bool reverse, void *state)
1383 {
1384    if (reverse) {
1385       foreach_list_typed_reverse_safe(nir_cf_node, node, node,
1386                                       &if_stmt->else_list) {
1387          if (!foreach_cf_node(node, cb, reverse, state))
1388             return false;
1389       }
1390
1391       foreach_list_typed_reverse_safe(nir_cf_node, node, node,
1392                                       &if_stmt->then_list) {
1393          if (!foreach_cf_node(node, cb, reverse, state))
1394             return false;
1395       }
1396    } else {
1397       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->then_list) {
1398          if (!foreach_cf_node(node, cb, reverse, state))
1399             return false;
1400       }
1401
1402       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list) {
1403          if (!foreach_cf_node(node, cb, reverse, state))
1404             return false;
1405       }
1406    }
1407
1408    return true;
1409 }
1410
1411 static inline bool
1412 foreach_loop(nir_loop *loop, nir_foreach_block_cb cb, bool reverse, void *state)
1413 {
1414    if (reverse) {
1415       foreach_list_typed_reverse_safe(nir_cf_node, node, node, &loop->body) {
1416          if (!foreach_cf_node(node, cb, reverse, state))
1417             return false;
1418       }
1419    } else {
1420       foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {
1421          if (!foreach_cf_node(node, cb, reverse, state))
1422             return false;
1423       }
1424    }
1425
1426    return true;
1427 }
1428
1429 static bool
1430 foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1431                 bool reverse, void *state)
1432 {
1433    switch (node->type) {
1434    case nir_cf_node_block:
1435       return cb(nir_cf_node_as_block(node), state);
1436    case nir_cf_node_if:
1437       return foreach_if(nir_cf_node_as_if(node), cb, reverse, state);
1438    case nir_cf_node_loop:
1439       return foreach_loop(nir_cf_node_as_loop(node), cb, reverse, state);
1440       break;
1441
1442    default:
1443       unreachable("Invalid CFG node type");
1444       break;
1445    }
1446
1447    return false;
1448 }
1449
1450 bool
1451 nir_foreach_block_in_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1452                              void *state)
1453 {
1454    return foreach_cf_node(node, cb, false, state);
1455 }
1456
1457 bool
1458 nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb, void *state)
1459 {
1460    foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {
1461       if (!foreach_cf_node(node, cb, false, state))
1462          return false;
1463    }
1464
1465    return cb(impl->end_block, state);
1466 }
1467
1468 bool
1469 nir_foreach_block_reverse(nir_function_impl *impl, nir_foreach_block_cb cb,
1470                           void *state)
1471 {
1472    if (!cb(impl->end_block, state))
1473       return false;
1474
1475    foreach_list_typed_reverse_safe(nir_cf_node, node, node, &impl->body) {
1476       if (!foreach_cf_node(node, cb, true, state))
1477          return false;
1478    }
1479
1480    return true;
1481 }
1482
1483 nir_if *
1484 nir_block_get_following_if(nir_block *block)
1485 {
1486    if (exec_node_is_tail_sentinel(&block->cf_node.node))
1487       return NULL;
1488
1489    if (nir_cf_node_is_last(&block->cf_node))
1490       return NULL;
1491
1492    nir_cf_node *next_node = nir_cf_node_next(&block->cf_node);
1493
1494    if (next_node->type != nir_cf_node_if)
1495       return NULL;
1496
1497    return nir_cf_node_as_if(next_node);
1498 }
1499
1500 nir_loop *
1501 nir_block_get_following_loop(nir_block *block)
1502 {
1503    if (exec_node_is_tail_sentinel(&block->cf_node.node))
1504       return NULL;
1505
1506    if (nir_cf_node_is_last(&block->cf_node))
1507       return NULL;
1508
1509    nir_cf_node *next_node = nir_cf_node_next(&block->cf_node);
1510
1511    if (next_node->type != nir_cf_node_loop)
1512       return NULL;
1513
1514    return nir_cf_node_as_loop(next_node);
1515 }
1516 static bool
1517 index_block(nir_block *block, void *state)
1518 {
1519    unsigned *index = state;
1520    block->index = (*index)++;
1521    return true;
1522 }
1523
1524 void
1525 nir_index_blocks(nir_function_impl *impl)
1526 {
1527    unsigned index = 0;
1528
1529    if (impl->valid_metadata & nir_metadata_block_index)
1530       return;
1531
1532    nir_foreach_block(impl, index_block, &index);
1533
1534    impl->num_blocks = index;
1535 }
1536
1537 static bool
1538 index_ssa_def_cb(nir_ssa_def *def, void *state)
1539 {
1540    unsigned *index = (unsigned *) state;
1541    def->index = (*index)++;
1542
1543    return true;
1544 }
1545
1546 static bool
1547 index_ssa_block(nir_block *block, void *state)
1548 {
1549    nir_foreach_instr(block, instr)
1550       nir_foreach_ssa_def(instr, index_ssa_def_cb, state);
1551
1552    return true;
1553 }
1554
1555 /**
1556  * The indices are applied top-to-bottom which has the very nice property
1557  * that, if A dominates B, then A->index <= B->index.
1558  */
1559 void
1560 nir_index_ssa_defs(nir_function_impl *impl)
1561 {
1562    unsigned index = 0;
1563    nir_foreach_block(impl, index_ssa_block, &index);
1564    impl->ssa_alloc = index;
1565 }
1566
1567 static bool
1568 index_instrs_block(nir_block *block, void *state)
1569 {
1570    unsigned *index = state;
1571    nir_foreach_instr(block, instr)
1572       instr->index = (*index)++;
1573
1574    return true;
1575 }
1576
1577 /**
1578  * The indices are applied top-to-bottom which has the very nice property
1579  * that, if A dominates B, then A->index <= B->index.
1580  */
1581 unsigned
1582 nir_index_instrs(nir_function_impl *impl)
1583 {
1584    unsigned index = 0;
1585    nir_foreach_block(impl, index_instrs_block, &index);
1586    return index;
1587 }
1588
1589 nir_intrinsic_op
1590 nir_intrinsic_from_system_value(gl_system_value val)
1591 {
1592    switch (val) {
1593    case SYSTEM_VALUE_VERTEX_ID:
1594       return nir_intrinsic_load_vertex_id;
1595    case SYSTEM_VALUE_INSTANCE_ID:
1596       return nir_intrinsic_load_instance_id;
1597    case SYSTEM_VALUE_VERTEX_ID_ZERO_BASE:
1598       return nir_intrinsic_load_vertex_id_zero_base;
1599    case SYSTEM_VALUE_BASE_VERTEX:
1600       return nir_intrinsic_load_base_vertex;
1601    case SYSTEM_VALUE_INVOCATION_ID:
1602       return nir_intrinsic_load_invocation_id;
1603    case SYSTEM_VALUE_FRONT_FACE:
1604       return nir_intrinsic_load_front_face;
1605    case SYSTEM_VALUE_SAMPLE_ID:
1606       return nir_intrinsic_load_sample_id;
1607    case SYSTEM_VALUE_SAMPLE_POS:
1608       return nir_intrinsic_load_sample_pos;
1609    case SYSTEM_VALUE_SAMPLE_MASK_IN:
1610       return nir_intrinsic_load_sample_mask_in;
1611    case SYSTEM_VALUE_LOCAL_INVOCATION_ID:
1612       return nir_intrinsic_load_local_invocation_id;
1613    case SYSTEM_VALUE_WORK_GROUP_ID:
1614       return nir_intrinsic_load_work_group_id;
1615    case SYSTEM_VALUE_NUM_WORK_GROUPS:
1616       return nir_intrinsic_load_num_work_groups;
1617    case SYSTEM_VALUE_PRIMITIVE_ID:
1618       return nir_intrinsic_load_primitive_id;
1619    case SYSTEM_VALUE_TESS_COORD:
1620       return nir_intrinsic_load_tess_coord;
1621    case SYSTEM_VALUE_TESS_LEVEL_OUTER:
1622       return nir_intrinsic_load_tess_level_outer;
1623    case SYSTEM_VALUE_TESS_LEVEL_INNER:
1624       return nir_intrinsic_load_tess_level_inner;
1625    case SYSTEM_VALUE_VERTICES_IN:
1626       return nir_intrinsic_load_patch_vertices_in;
1627    case SYSTEM_VALUE_HELPER_INVOCATION:
1628       return nir_intrinsic_load_helper_invocation;
1629    default:
1630       unreachable("system value does not directly correspond to intrinsic");
1631    }
1632 }
1633
1634 gl_system_value
1635 nir_system_value_from_intrinsic(nir_intrinsic_op intrin)
1636 {
1637    switch (intrin) {
1638    case nir_intrinsic_load_vertex_id:
1639       return SYSTEM_VALUE_VERTEX_ID;
1640    case nir_intrinsic_load_instance_id:
1641       return SYSTEM_VALUE_INSTANCE_ID;
1642    case nir_intrinsic_load_vertex_id_zero_base:
1643       return SYSTEM_VALUE_VERTEX_ID_ZERO_BASE;
1644    case nir_intrinsic_load_base_vertex:
1645       return SYSTEM_VALUE_BASE_VERTEX;
1646    case nir_intrinsic_load_invocation_id:
1647       return SYSTEM_VALUE_INVOCATION_ID;
1648    case nir_intrinsic_load_front_face:
1649       return SYSTEM_VALUE_FRONT_FACE;
1650    case nir_intrinsic_load_sample_id:
1651       return SYSTEM_VALUE_SAMPLE_ID;
1652    case nir_intrinsic_load_sample_pos:
1653       return SYSTEM_VALUE_SAMPLE_POS;
1654    case nir_intrinsic_load_sample_mask_in:
1655       return SYSTEM_VALUE_SAMPLE_MASK_IN;
1656    case nir_intrinsic_load_local_invocation_id:
1657       return SYSTEM_VALUE_LOCAL_INVOCATION_ID;
1658    case nir_intrinsic_load_num_work_groups:
1659       return SYSTEM_VALUE_NUM_WORK_GROUPS;
1660    case nir_intrinsic_load_work_group_id:
1661       return SYSTEM_VALUE_WORK_GROUP_ID;
1662    case nir_intrinsic_load_primitive_id:
1663       return SYSTEM_VALUE_PRIMITIVE_ID;
1664    case nir_intrinsic_load_tess_coord:
1665       return SYSTEM_VALUE_TESS_COORD;
1666    case nir_intrinsic_load_tess_level_outer:
1667       return SYSTEM_VALUE_TESS_LEVEL_OUTER;
1668    case nir_intrinsic_load_tess_level_inner:
1669       return SYSTEM_VALUE_TESS_LEVEL_INNER;
1670    case nir_intrinsic_load_patch_vertices_in:
1671       return SYSTEM_VALUE_VERTICES_IN;
1672    case nir_intrinsic_load_helper_invocation:
1673       return SYSTEM_VALUE_HELPER_INVOCATION;
1674    default:
1675       unreachable("intrinsic doesn't produce a system value");
1676    }
1677 }