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, const nir_shader_compiler_options *options)
  34 {
  35    nir_shader *shader = ralloc(mem_ctx, nir_shader);
  36
  37    exec_list_make_empty(&shader->uniforms);
  38    exec_list_make_empty(&shader->inputs);
  39    exec_list_make_empty(&shader->outputs);
  40
  41    shader->options = options;
  42
  43    exec_list_make_empty(&shader->functions);
  44    exec_list_make_empty(&shader->registers);
  45    exec_list_make_empty(&shader->globals);
  46    exec_list_make_empty(&shader->system_values);
  47    shader->reg_alloc = 0;
  48
  49    shader->num_inputs = 0;
  50    shader->num_outputs = 0;
  51    shader->num_uniforms = 0;
  52
  53    return shader;
  54 }
  55
  56 static nir_register *
  57 reg_create(void *mem_ctx, struct exec_list *list)
  58 {
  59    nir_register *reg = ralloc(mem_ctx, nir_register);
  60
  61    list_inithead(&reg->uses);
  62    list_inithead(&reg->defs);
  63    list_inithead(&reg->if_uses);
  64
  65    reg->num_components = 0;
  66    reg->num_array_elems = 0;
  67    reg->is_packed = false;
  68    reg->name = NULL;
  69
  70    exec_list_push_tail(list, &reg->node);
  71
  72    return reg;
  73 }
  74
  75 nir_register *
  76 nir_global_reg_create(nir_shader *shader)
  77 {
  78    nir_register *reg = reg_create(shader, &shader->registers);
  79    reg->index = shader->reg_alloc++;
  80    reg->is_global = true;
  81
  82    return reg;
  83 }
  84
  85 nir_register *
  86 nir_local_reg_create(nir_function_impl *impl)
  87 {
  88    nir_register *reg = reg_create(ralloc_parent(impl), &impl->registers);
  89    reg->index = impl->reg_alloc++;
  90    reg->is_global = false;
  91
  92    return reg;
  93 }
  94
  95 void
  96 nir_reg_remove(nir_register *reg)
  97 {
  98    exec_node_remove(&reg->node);
  99 }
 100
 101 nir_function *
 102 nir_function_create(nir_shader *shader, const char *name)
 103 {
 104    nir_function *func = ralloc(shader, nir_function);
 105
 106    exec_list_push_tail(&shader->functions, &func->node);
 107    exec_list_make_empty(&func->overload_list);
 108    func->name = ralloc_strdup(func, name);
 109    func->shader = shader;
 110
 111    return func;
 112 }
 113
 114 nir_function_overload *
 115 nir_function_overload_create(nir_function *func)
 116 {
 117    void *mem_ctx = ralloc_parent(func);
 118
 119    nir_function_overload *overload = ralloc(mem_ctx, nir_function_overload);
 120
 121    overload->num_params = 0;
 122    overload->params = NULL;
 123    overload->return_type = glsl_void_type();
 124    overload->impl = NULL;
 125
 126    exec_list_push_tail(&func->overload_list, &overload->node);
 127    overload->function = func;
 128
 129    return overload;
 130 }
 131
 132 void nir_src_copy(nir_src *dest, const nir_src *src, void *mem_ctx)
 133 {
 134    dest->is_ssa = src->is_ssa;
 135    if (src->is_ssa) {
 136       dest->ssa = src->ssa;
 137    } else {
 138       dest->reg.base_offset = src->reg.base_offset;
 139       dest->reg.reg = src->reg.reg;
 140       if (src->reg.indirect) {
 141          dest->reg.indirect = ralloc(mem_ctx, nir_src);
 142          nir_src_copy(dest->reg.indirect, src->reg.indirect, mem_ctx);
 143       } else {
 144          dest->reg.indirect = NULL;
 145       }
 146    }
 147 }
 148
 149 void nir_dest_copy(nir_dest *dest, const nir_dest *src, void *mem_ctx)
 150 {
 151    /* Copying an SSA definition makes no sense whatsoever. */
 152    assert(!src->is_ssa);
 153
 154    dest->is_ssa = false;
 155
 156    dest->reg.base_offset = src->reg.base_offset;
 157    dest->reg.reg = src->reg.reg;
 158    if (src->reg.indirect) {
 159       dest->reg.indirect = ralloc(mem_ctx, nir_src);
 160       nir_src_copy(dest->reg.indirect, src->reg.indirect, mem_ctx);
 161    } else {
 162       dest->reg.indirect = NULL;
 163    }
 164 }
 165
 166 void
 167 nir_alu_src_copy(nir_alu_src *dest, const nir_alu_src *src, void *mem_ctx)
 168 {
 169    nir_src_copy(&dest->src, &src->src, mem_ctx);
 170    dest->abs = src->abs;
 171    dest->negate = src->negate;
 172    for (unsigned i = 0; i < 4; i++)
 173       dest->swizzle[i] = src->swizzle[i];
 174 }
 175
 176 void
 177 nir_alu_dest_copy(nir_alu_dest *dest, const nir_alu_dest *src, void *mem_ctx)
 178 {
 179    nir_dest_copy(&dest->dest, &src->dest, mem_ctx);
 180    dest->write_mask = src->write_mask;
 181    dest->saturate = src->saturate;
 182 }
 183
 184
 185 static void
 186 cf_init(nir_cf_node *node, nir_cf_node_type type)
 187 {
 188    exec_node_init(&node->node);
 189    node->parent = NULL;
 190    node->type = type;
 191 }
 192
 193 nir_function_impl *
 194 nir_function_impl_create(nir_function_overload *overload)
 195 {
 196    assert(overload->impl == NULL);
 197
 198    void *mem_ctx = ralloc_parent(overload);
 199
 200    nir_function_impl *impl = ralloc(mem_ctx, nir_function_impl);
 201
 202    overload->impl = impl;
 203    impl->overload = overload;
 204
 205    cf_init(&impl->cf_node, nir_cf_node_function);
 206
 207    exec_list_make_empty(&impl->body);
 208    exec_list_make_empty(&impl->registers);
 209    exec_list_make_empty(&impl->locals);
 210    impl->num_params = 0;
 211    impl->params = NULL;
 212    impl->return_var = NULL;
 213    impl->reg_alloc = 0;
 214    impl->ssa_alloc = 0;
 215    impl->valid_metadata = nir_metadata_none;
 216
 217    /* create start & end blocks */
 218    nir_block *start_block = nir_block_create(mem_ctx);
 219    nir_block *end_block = nir_block_create(mem_ctx);
 220    start_block->cf_node.parent = &impl->cf_node;
 221    end_block->cf_node.parent = &impl->cf_node;
 222    impl->end_block = end_block;
 223
 224    exec_list_push_tail(&impl->body, &start_block->cf_node.node);
 225
 226    start_block->successors[0] = end_block;
 227    _mesa_set_add(end_block->predecessors, start_block);
 228    return impl;
 229 }
 230
 231 nir_block *
 232 nir_block_create(void *mem_ctx)
 233 {
 234    nir_block *block = ralloc(mem_ctx, nir_block);
 235
 236    cf_init(&block->cf_node, nir_cf_node_block);
 237
 238    block->successors[0] = block->successors[1] = NULL;
 239    block->predecessors = _mesa_set_create(block, _mesa_hash_pointer,
 240                                           _mesa_key_pointer_equal);
 241    block->imm_dom = NULL;
 242    block->dom_frontier = _mesa_set_create(block, _mesa_hash_pointer,
 243                                           _mesa_key_pointer_equal);
 244
 245    exec_list_make_empty(&block->instr_list);
 246
 247    return block;
 248 }
 249
 250 static inline void
 251 src_init(nir_src *src)
 252 {
 253    src->is_ssa = false;
 254    src->reg.reg = NULL;
 255    src->reg.indirect = NULL;
 256    src->reg.base_offset = 0;
 257 }
 258
 259 nir_if *
 260 nir_if_create(void *mem_ctx)
 261 {
 262    nir_if *if_stmt = ralloc(mem_ctx, nir_if);
 263
 264    cf_init(&if_stmt->cf_node, nir_cf_node_if);
 265    src_init(&if_stmt->condition);
 266
 267    nir_block *then = nir_block_create(mem_ctx);
 268    exec_list_make_empty(&if_stmt->then_list);
 269    exec_list_push_tail(&if_stmt->then_list, &then->cf_node.node);
 270    then->cf_node.parent = &if_stmt->cf_node;
 271
 272    nir_block *else_stmt = nir_block_create(mem_ctx);
 273    exec_list_make_empty(&if_stmt->else_list);
 274    exec_list_push_tail(&if_stmt->else_list, &else_stmt->cf_node.node);
 275    else_stmt->cf_node.parent = &if_stmt->cf_node;
 276
 277    return if_stmt;
 278 }
 279
 280 nir_loop *
 281 nir_loop_create(void *mem_ctx)
 282 {
 283    nir_loop *loop = ralloc(mem_ctx, nir_loop);
 284
 285    cf_init(&loop->cf_node, nir_cf_node_loop);
 286
 287    nir_block *body = nir_block_create(mem_ctx);
 288    exec_list_make_empty(&loop->body);
 289    exec_list_push_tail(&loop->body, &body->cf_node.node);
 290    body->cf_node.parent = &loop->cf_node;
 291
 292    body->successors[0] = body;
 293    _mesa_set_add(body->predecessors, body);
 294
 295    return loop;
 296 }
 297
 298 static void
 299 instr_init(nir_instr *instr, nir_instr_type type)
 300 {
 301    instr->type = type;
 302    instr->block = NULL;
 303    exec_node_init(&instr->node);
 304 }
 305
 306 static void
 307 dest_init(nir_dest *dest)
 308 {
 309    dest->is_ssa = false;
 310    dest->reg.reg = NULL;
 311    dest->reg.indirect = NULL;
 312    dest->reg.base_offset = 0;
 313 }
 314
 315 static void
 316 alu_dest_init(nir_alu_dest *dest)
 317 {
 318    dest_init(&dest->dest);
 319    dest->saturate = false;
 320    dest->write_mask = 0xf;
 321 }
 322
 323 static void
 324 alu_src_init(nir_alu_src *src)
 325 {
 326    src_init(&src->src);
 327    src->abs = src->negate = false;
 328    src->swizzle[0] = 0;
 329    src->swizzle[1] = 1;
 330    src->swizzle[2] = 2;
 331    src->swizzle[3] = 3;
 332 }
 333
 334 nir_alu_instr *
 335 nir_alu_instr_create(nir_shader *shader, nir_op op)
 336 {
 337    unsigned num_srcs = nir_op_infos[op].num_inputs;
 338    nir_alu_instr *instr =
 339       ralloc_size(shader,
 340                   sizeof(nir_alu_instr) + num_srcs * sizeof(nir_alu_src));
 341
 342    instr_init(&instr->instr, nir_instr_type_alu);
 343    instr->op = op;
 344    alu_dest_init(&instr->dest);
 345    for (unsigned i = 0; i < num_srcs; i++)
 346       alu_src_init(&instr->src[i]);
 347
 348    return instr;
 349 }
 350
 351 nir_jump_instr *
 352 nir_jump_instr_create(nir_shader *shader, nir_jump_type type)
 353 {
 354    nir_jump_instr *instr = ralloc(shader, nir_jump_instr);
 355    instr_init(&instr->instr, nir_instr_type_jump);
 356    instr->type = type;
 357    return instr;
 358 }
 359
 360 nir_load_const_instr *
 361 nir_load_const_instr_create(nir_shader *shader, unsigned num_components)
 362 {
 363    nir_load_const_instr *instr = ralloc(shader, nir_load_const_instr);
 364    instr_init(&instr->instr, nir_instr_type_load_const);
 365
 366    nir_ssa_def_init(&instr->instr, &instr->def, num_components, NULL);
 367
 368    return instr;
 369 }
 370
 371 nir_intrinsic_instr *
 372 nir_intrinsic_instr_create(nir_shader *shader, nir_intrinsic_op op)
 373 {
 374    unsigned num_srcs = nir_intrinsic_infos[op].num_srcs;
 375    nir_intrinsic_instr *instr =
 376       ralloc_size(shader,
 377                   sizeof(nir_intrinsic_instr) + num_srcs * sizeof(nir_src));
 378
 379    instr_init(&instr->instr, nir_instr_type_intrinsic);
 380    instr->intrinsic = op;
 381
 382    if (nir_intrinsic_infos[op].has_dest)
 383       dest_init(&instr->dest);
 384
 385    for (unsigned i = 0; i < num_srcs; i++)
 386       src_init(&instr->src[i]);
 387
 388    return instr;
 389 }
 390
 391 nir_call_instr *
 392 nir_call_instr_create(nir_shader *shader, nir_function_overload *callee)
 393 {
 394    nir_call_instr *instr = ralloc(shader, nir_call_instr);
 395    instr_init(&instr->instr, nir_instr_type_call);
 396
 397    instr->callee = callee;
 398    instr->num_params = callee->num_params;
 399    instr->params = ralloc_array(instr, nir_deref_var *, instr->num_params);
 400    instr->return_deref = NULL;
 401
 402    return instr;
 403 }
 404
 405 nir_tex_instr *
 406 nir_tex_instr_create(nir_shader *shader, unsigned num_srcs)
 407 {
 408    nir_tex_instr *instr = rzalloc(shader, nir_tex_instr);
 409    instr_init(&instr->instr, nir_instr_type_tex);
 410
 411    dest_init(&instr->dest);
 412
 413    instr->num_srcs = num_srcs;
 414    instr->src = ralloc_array(instr, nir_tex_src, num_srcs);
 415    for (unsigned i = 0; i < num_srcs; i++)
 416       src_init(&instr->src[i].src);
 417
 418    instr->sampler_index = 0;
 419    instr->sampler_array_size = 0;
 420    instr->sampler = NULL;
 421
 422    return instr;
 423 }
 424
 425 nir_phi_instr *
 426 nir_phi_instr_create(nir_shader *shader)
 427 {
 428    nir_phi_instr *instr = ralloc(shader, nir_phi_instr);
 429    instr_init(&instr->instr, nir_instr_type_phi);
 430
 431    dest_init(&instr->dest);
 432    exec_list_make_empty(&instr->srcs);
 433    return instr;
 434 }
 435
 436 nir_parallel_copy_instr *
 437 nir_parallel_copy_instr_create(nir_shader *shader)
 438 {
 439    nir_parallel_copy_instr *instr = ralloc(shader, nir_parallel_copy_instr);
 440    instr_init(&instr->instr, nir_instr_type_parallel_copy);
 441
 442    exec_list_make_empty(&instr->entries);
 443
 444    return instr;
 445 }
 446
 447 nir_ssa_undef_instr *
 448 nir_ssa_undef_instr_create(nir_shader *shader, unsigned num_components)
 449 {
 450    nir_ssa_undef_instr *instr = ralloc(shader, nir_ssa_undef_instr);
 451    instr_init(&instr->instr, nir_instr_type_ssa_undef);
 452
 453    nir_ssa_def_init(&instr->instr, &instr->def, num_components, NULL);
 454
 455    return instr;
 456 }
 457
 458 nir_deref_var *
 459 nir_deref_var_create(void *mem_ctx, nir_variable *var)
 460 {
 461    nir_deref_var *deref = ralloc(mem_ctx, nir_deref_var);
 462    deref->deref.deref_type = nir_deref_type_var;
 463    deref->deref.child = NULL;
 464    deref->deref.type = var->type;
 465    deref->var = var;
 466    return deref;
 467 }
 468
 469 nir_deref_array *
 470 nir_deref_array_create(void *mem_ctx)
 471 {
 472    nir_deref_array *deref = ralloc(mem_ctx, nir_deref_array);
 473    deref->deref.deref_type = nir_deref_type_array;
 474    deref->deref.child = NULL;
 475    deref->deref_array_type = nir_deref_array_type_direct;
 476    src_init(&deref->indirect);
 477    deref->base_offset = 0;
 478    return deref;
 479 }
 480
 481 nir_deref_struct *
 482 nir_deref_struct_create(void *mem_ctx, unsigned field_index)
 483 {
 484    nir_deref_struct *deref = ralloc(mem_ctx, nir_deref_struct);
 485    deref->deref.deref_type = nir_deref_type_struct;
 486    deref->deref.child = NULL;
 487    deref->index = field_index;
 488    return deref;
 489 }
 490
 491 static nir_deref_var *
 492 copy_deref_var(void *mem_ctx, nir_deref_var *deref)
 493 {
 494    nir_deref_var *ret = nir_deref_var_create(mem_ctx, deref->var);
 495    ret->deref.type = deref->deref.type;
 496    if (deref->deref.child)
 497       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 498    return ret;
 499 }
 500
 501 static nir_deref_array *
 502 copy_deref_array(void *mem_ctx, nir_deref_array *deref)
 503 {
 504    nir_deref_array *ret = nir_deref_array_create(mem_ctx);
 505    ret->base_offset = deref->base_offset;
 506    ret->deref_array_type = deref->deref_array_type;
 507    if (deref->deref_array_type == nir_deref_array_type_indirect) {
 508       nir_src_copy(&ret->indirect, &deref->indirect, mem_ctx);
 509    }
 510    ret->deref.type = deref->deref.type;
 511    if (deref->deref.child)
 512       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 513    return ret;
 514 }
 515
 516 static nir_deref_struct *
 517 copy_deref_struct(void *mem_ctx, nir_deref_struct *deref)
 518 {
 519    nir_deref_struct *ret = nir_deref_struct_create(mem_ctx, deref->index);
 520    ret->deref.type = deref->deref.type;
 521    if (deref->deref.child)
 522       ret->deref.child = nir_copy_deref(ret, deref->deref.child);
 523    return ret;
 524 }
 525
 526 nir_deref *
 527 nir_copy_deref(void *mem_ctx, nir_deref *deref)
 528 {
 529    switch (deref->deref_type) {
 530    case nir_deref_type_var:
 531       return &copy_deref_var(mem_ctx, nir_deref_as_var(deref))->deref;
 532    case nir_deref_type_array:
 533       return &copy_deref_array(mem_ctx, nir_deref_as_array(deref))->deref;
 534    case nir_deref_type_struct:
 535       return &copy_deref_struct(mem_ctx, nir_deref_as_struct(deref))->deref;
 536    default:
 537       unreachable("Invalid dereference type");
 538    }
 539
 540    return NULL;
 541 }
 542
 543 /* Returns a load_const instruction that represents the constant
 544  * initializer for the given deref chain.  The caller is responsible for
 545  * ensuring that there actually is a constant initializer.
 546  */
 547 nir_load_const_instr *
 548 nir_deref_get_const_initializer_load(nir_shader *shader, nir_deref_var *deref)
 549 {
 550    nir_constant *constant = deref->var->constant_initializer;
 551    assert(constant);
 552
 553    const nir_deref *tail = &deref->deref;
 554    unsigned matrix_offset = 0;
 555    while (tail->child) {
 556       switch (tail->child->deref_type) {
 557       case nir_deref_type_array: {
 558          nir_deref_array *arr = nir_deref_as_array(tail->child);
 559          assert(arr->deref_array_type == nir_deref_array_type_direct);
 560          if (glsl_type_is_matrix(tail->type)) {
 561             assert(arr->deref.child == NULL);
 562             matrix_offset = arr->base_offset;
 563          } else {
 564             constant = constant->elements[arr->base_offset];
 565          }
 566          break;
 567       }
 568
 569       case nir_deref_type_struct: {
 570          constant = constant->elements[nir_deref_as_struct(tail->child)->index];
 571          break;
 572       }
 573
 574       default:
 575          unreachable("Invalid deref child type");
 576       }
 577
 578       tail = tail->child;
 579    }
 580
 581    nir_load_const_instr *load =
 582       nir_load_const_instr_create(shader, glsl_get_vector_elements(tail->type));
 583
 584    matrix_offset *= load->def.num_components;
 585    for (unsigned i = 0; i < load->def.num_components; i++) {
 586       switch (glsl_get_base_type(tail->type)) {
 587       case GLSL_TYPE_FLOAT:
 588       case GLSL_TYPE_INT:
 589       case GLSL_TYPE_UINT:
 590          load->value.u[i] = constant->value.u[matrix_offset + i];
 591          break;
 592       case GLSL_TYPE_BOOL:
 593          load->value.u[i] = constant->value.b[matrix_offset + i] ?
 594                              NIR_TRUE : NIR_FALSE;
 595          break;
 596       default:
 597          unreachable("Invalid immediate type");
 598       }
 599    }
 600
 601    return load;
 602 }
 603
 604 nir_function_impl *
 605 nir_cf_node_get_function(nir_cf_node *node)
 606 {
 607    while (node->type != nir_cf_node_function) {
 608       node = node->parent;
 609    }
 610
 611    return nir_cf_node_as_function(node);
 612 }
 613
 614 static bool
 615 add_use_cb(nir_src *src, void *state)
 616 {
 617    nir_instr *instr = state;
 618
 619    src->parent_instr = instr;
 620    list_addtail(&src->use_link,
 621                 src->is_ssa ? &src->ssa->uses : &src->reg.reg->uses);
 622
 623    return true;
 624 }
 625
 626 static bool
 627 add_ssa_def_cb(nir_ssa_def *def, void *state)
 628 {
 629    nir_instr *instr = state;
 630
 631    if (instr->block && def->index == UINT_MAX) {
 632       nir_function_impl *impl =
 633          nir_cf_node_get_function(&instr->block->cf_node);
 634
 635       def->index = impl->ssa_alloc++;
 636    }
 637
 638    return true;
 639 }
 640
 641 static bool
 642 add_reg_def_cb(nir_dest *dest, void *state)
 643 {
 644    nir_instr *instr = state;
 645
 646    if (!dest->is_ssa) {
 647       dest->reg.parent_instr = instr;
 648       list_addtail(&dest->reg.def_link, &dest->reg.reg->defs);
 649    }
 650
 651    return true;
 652 }
 653
 654 static void
 655 add_defs_uses(nir_instr *instr)
 656 {
 657    nir_foreach_src(instr, add_use_cb, instr);
 658    nir_foreach_dest(instr, add_reg_def_cb, instr);
 659    nir_foreach_ssa_def(instr, add_ssa_def_cb, instr);
 660 }
 661
 662 void
 663 nir_instr_insert_before(nir_instr *instr, nir_instr *before)
 664 {
 665    assert(before->type != nir_instr_type_jump);
 666    before->block = instr->block;
 667    add_defs_uses(before);
 668    exec_node_insert_node_before(&instr->node, &before->node);
 669 }
 670
 671 void
 672 nir_instr_insert_after(nir_instr *instr, nir_instr *after)
 673 {
 674    if (after->type == nir_instr_type_jump) {
 675       assert(instr == nir_block_last_instr(instr->block));
 676       assert(instr->type != nir_instr_type_jump);
 677    }
 678
 679    after->block = instr->block;
 680    add_defs_uses(after);
 681    exec_node_insert_after(&instr->node, &after->node);
 682
 683    if (after->type == nir_instr_type_jump)
 684       nir_handle_add_jump(after->block);
 685 }
 686
 687 void
 688 nir_instr_insert_before_block(nir_block *block, nir_instr *before)
 689 {
 690    if (before->type == nir_instr_type_jump)
 691       assert(exec_list_is_empty(&block->instr_list));
 692
 693    before->block = block;
 694    add_defs_uses(before);
 695    exec_list_push_head(&block->instr_list, &before->node);
 696
 697    if (before->type == nir_instr_type_jump)
 698       nir_handle_add_jump(block);
 699 }
 700
 701 void
 702 nir_instr_insert_after_block(nir_block *block, nir_instr *after)
 703 {
 704    if (after->type == nir_instr_type_jump) {
 705       assert(exec_list_is_empty(&block->instr_list) ||
 706              nir_block_last_instr(block)->type != nir_instr_type_jump);
 707    }
 708
 709    after->block = block;
 710    add_defs_uses(after);
 711    exec_list_push_tail(&block->instr_list, &after->node);
 712
 713    if (after->type == nir_instr_type_jump)
 714       nir_handle_add_jump(block);
 715 }
 716
 717 void
 718 nir_instr_insert_before_cf(nir_cf_node *node, nir_instr *before)
 719 {
 720    if (node->type == nir_cf_node_block) {
 721       nir_instr_insert_before_block(nir_cf_node_as_block(node), before);
 722    } else {
 723       nir_cf_node *prev = nir_cf_node_prev(node);
 724       assert(prev->type == nir_cf_node_block);
 725       nir_block *prev_block = nir_cf_node_as_block(prev);
 726
 727       nir_instr_insert_before_block(prev_block, before);
 728    }
 729 }
 730
 731 void
 732 nir_instr_insert_after_cf(nir_cf_node *node, nir_instr *after)
 733 {
 734    if (node->type == nir_cf_node_block) {
 735       nir_instr_insert_after_block(nir_cf_node_as_block(node), after);
 736    } else {
 737       nir_cf_node *next = nir_cf_node_next(node);
 738       assert(next->type == nir_cf_node_block);
 739       nir_block *next_block = nir_cf_node_as_block(next);
 740
 741       nir_instr_insert_before_block(next_block, after);
 742    }
 743 }
 744
 745 void
 746 nir_instr_insert_before_cf_list(struct exec_list *list, nir_instr *before)
 747 {
 748    nir_cf_node *first_node = exec_node_data(nir_cf_node,
 749                                             exec_list_get_head(list), node);
 750    nir_instr_insert_before_cf(first_node, before);
 751 }
 752
 753 void
 754 nir_instr_insert_after_cf_list(struct exec_list *list, nir_instr *after)
 755 {
 756    nir_cf_node *last_node = exec_node_data(nir_cf_node,
 757                                            exec_list_get_tail(list), node);
 758    nir_instr_insert_after_cf(last_node, after);
 759 }
 760
 761 static bool
 762 remove_use_cb(nir_src *src, void *state)
 763 {
 764    list_del(&src->use_link);
 765
 766    return true;
 767 }
 768
 769 static bool
 770 remove_def_cb(nir_dest *dest, void *state)
 771 {
 772    if (!dest->is_ssa)
 773       list_del(&dest->reg.def_link);
 774
 775    return true;
 776 }
 777
 778 static void
 779 remove_defs_uses(nir_instr *instr)
 780 {
 781    nir_foreach_dest(instr, remove_def_cb, instr);
 782    nir_foreach_src(instr, remove_use_cb, instr);
 783 }
 784
 785 void nir_instr_remove(nir_instr *instr)
 786 {
 787    remove_defs_uses(instr);
 788    exec_node_remove(&instr->node);
 789
 790    if (instr->type == nir_instr_type_jump) {
 791       nir_jump_instr *jump_instr = nir_instr_as_jump(instr);
 792       nir_handle_remove_jump(instr->block, jump_instr->type);
 793    }
 794 }
 795
 796 /*@}*/
 797
 798 void
 799 nir_index_local_regs(nir_function_impl *impl)
 800 {
 801    unsigned index = 0;
 802    foreach_list_typed(nir_register, reg, node, &impl->registers) {
 803       reg->index = index++;
 804    }
 805    impl->reg_alloc = index;
 806 }
 807
 808 void
 809 nir_index_global_regs(nir_shader *shader)
 810 {
 811    unsigned index = 0;
 812    foreach_list_typed(nir_register, reg, node, &shader->registers) {
 813       reg->index = index++;
 814    }
 815    shader->reg_alloc = index;
 816 }
 817
 818 static bool
 819 visit_alu_dest(nir_alu_instr *instr, nir_foreach_dest_cb cb, void *state)
 820 {
 821    return cb(&instr->dest.dest, state);
 822 }
 823
 824 static bool
 825 visit_intrinsic_dest(nir_intrinsic_instr *instr, nir_foreach_dest_cb cb,
 826                      void *state)
 827 {
 828    if (nir_intrinsic_infos[instr->intrinsic].has_dest)
 829       return cb(&instr->dest, state);
 830
 831    return true;
 832 }
 833
 834 static bool
 835 visit_texture_dest(nir_tex_instr *instr, nir_foreach_dest_cb cb,
 836                    void *state)
 837 {
 838    return cb(&instr->dest, state);
 839 }
 840
 841 static bool
 842 visit_phi_dest(nir_phi_instr *instr, nir_foreach_dest_cb cb, void *state)
 843 {
 844    return cb(&instr->dest, state);
 845 }
 846
 847 static bool
 848 visit_parallel_copy_dest(nir_parallel_copy_instr *instr,
 849                          nir_foreach_dest_cb cb, void *state)
 850 {
 851    nir_foreach_parallel_copy_entry(instr, entry) {
 852       if (!cb(&entry->dest, state))
 853          return false;
 854    }
 855
 856    return true;
 857 }
 858
 859 bool
 860 nir_foreach_dest(nir_instr *instr, nir_foreach_dest_cb cb, void *state)
 861 {
 862    switch (instr->type) {
 863    case nir_instr_type_alu:
 864       return visit_alu_dest(nir_instr_as_alu(instr), cb, state);
 865    case nir_instr_type_intrinsic:
 866       return visit_intrinsic_dest(nir_instr_as_intrinsic(instr), cb, state);
 867    case nir_instr_type_tex:
 868       return visit_texture_dest(nir_instr_as_tex(instr), cb, state);
 869    case nir_instr_type_phi:
 870       return visit_phi_dest(nir_instr_as_phi(instr), cb, state);
 871    case nir_instr_type_parallel_copy:
 872       return visit_parallel_copy_dest(nir_instr_as_parallel_copy(instr),
 873                                       cb, state);
 874
 875    case nir_instr_type_load_const:
 876    case nir_instr_type_ssa_undef:
 877    case nir_instr_type_call:
 878    case nir_instr_type_jump:
 879       break;
 880
 881    default:
 882       unreachable("Invalid instruction type");
 883       break;
 884    }
 885
 886    return true;
 887 }
 888
 889 struct foreach_ssa_def_state {
 890    nir_foreach_ssa_def_cb cb;
 891    void *client_state;
 892 };
 893
 894 static inline bool
 895 nir_ssa_def_visitor(nir_dest *dest, void *void_state)
 896 {
 897    struct foreach_ssa_def_state *state = void_state;
 898
 899    if (dest->is_ssa)
 900       return state->cb(&dest->ssa, state->client_state);
 901    else
 902       return true;
 903 }
 904
 905 bool
 906 nir_foreach_ssa_def(nir_instr *instr, nir_foreach_ssa_def_cb cb, void *state)
 907 {
 908    switch (instr->type) {
 909    case nir_instr_type_alu:
 910    case nir_instr_type_tex:
 911    case nir_instr_type_intrinsic:
 912    case nir_instr_type_phi:
 913    case nir_instr_type_parallel_copy: {
 914       struct foreach_ssa_def_state foreach_state = {cb, state};
 915       return nir_foreach_dest(instr, nir_ssa_def_visitor, &foreach_state);
 916    }
 917
 918    case nir_instr_type_load_const:
 919       return cb(&nir_instr_as_load_const(instr)->def, state);
 920    case nir_instr_type_ssa_undef:
 921       return cb(&nir_instr_as_ssa_undef(instr)->def, state);
 922    case nir_instr_type_call:
 923    case nir_instr_type_jump:
 924       return true;
 925    default:
 926       unreachable("Invalid instruction type");
 927    }
 928 }
 929
 930 static bool
 931 visit_src(nir_src *src, nir_foreach_src_cb cb, void *state)
 932 {
 933    if (!cb(src, state))
 934       return false;
 935    if (!src->is_ssa && src->reg.indirect)
 936       return cb(src->reg.indirect, state);
 937    return true;
 938 }
 939
 940 static bool
 941 visit_deref_array_src(nir_deref_array *deref, nir_foreach_src_cb cb,
 942                       void *state)
 943 {
 944    if (deref->deref_array_type == nir_deref_array_type_indirect)
 945       return visit_src(&deref->indirect, cb, state);
 946    return true;
 947 }
 948
 949 static bool
 950 visit_deref_src(nir_deref_var *deref, nir_foreach_src_cb cb, void *state)
 951 {
 952    nir_deref *cur = &deref->deref;
 953    while (cur != NULL) {
 954       if (cur->deref_type == nir_deref_type_array)
 955          if (!visit_deref_array_src(nir_deref_as_array(cur), cb, state))
 956             return false;
 957
 958       cur = cur->child;
 959    }
 960
 961    return true;
 962 }
 963
 964 static bool
 965 visit_alu_src(nir_alu_instr *instr, nir_foreach_src_cb cb, void *state)
 966 {
 967    for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++)
 968       if (!visit_src(&instr->src[i].src, cb, state))
 969          return false;
 970
 971    return true;
 972 }
 973
 974 static bool
 975 visit_tex_src(nir_tex_instr *instr, nir_foreach_src_cb cb, void *state)
 976 {
 977    for (unsigned i = 0; i < instr->num_srcs; i++)
 978       if (!visit_src(&instr->src[i].src, cb, state))
 979          return false;
 980
 981    if (instr->sampler != NULL)
 982       if (!visit_deref_src(instr->sampler, cb, state))
 983          return false;
 984
 985    return true;
 986 }
 987
 988 static bool
 989 visit_intrinsic_src(nir_intrinsic_instr *instr, nir_foreach_src_cb cb,
 990                     void *state)
 991 {
 992    unsigned num_srcs = nir_intrinsic_infos[instr->intrinsic].num_srcs;
 993    for (unsigned i = 0; i < num_srcs; i++)
 994       if (!visit_src(&instr->src[i], cb, state))
 995          return false;
 996
 997    unsigned num_vars =
 998       nir_intrinsic_infos[instr->intrinsic].num_variables;
 999    for (unsigned i = 0; i < num_vars; i++)
1000       if (!visit_deref_src(instr->variables[i], cb, state))
1001          return false;
1002
1003    return true;
1004 }
1005
1006 static bool
1007 visit_call_src(nir_call_instr *instr, nir_foreach_src_cb cb, void *state)
1008 {
1009    return true;
1010 }
1011
1012 static bool
1013 visit_load_const_src(nir_load_const_instr *instr, nir_foreach_src_cb cb,
1014                      void *state)
1015 {
1016    return true;
1017 }
1018
1019 static bool
1020 visit_phi_src(nir_phi_instr *instr, nir_foreach_src_cb cb, void *state)
1021 {
1022    nir_foreach_phi_src(instr, src) {
1023       if (!visit_src(&src->src, cb, state))
1024          return false;
1025    }
1026
1027    return true;
1028 }
1029
1030 static bool
1031 visit_parallel_copy_src(nir_parallel_copy_instr *instr,
1032                         nir_foreach_src_cb cb, void *state)
1033 {
1034    nir_foreach_parallel_copy_entry(instr, entry) {
1035       if (!visit_src(&entry->src, cb, state))
1036          return false;
1037    }
1038
1039    return true;
1040 }
1041
1042 typedef struct {
1043    void *state;
1044    nir_foreach_src_cb cb;
1045 } visit_dest_indirect_state;
1046
1047 static bool
1048 visit_dest_indirect(nir_dest *dest, void *_state)
1049 {
1050    visit_dest_indirect_state *state = (visit_dest_indirect_state *) _state;
1051
1052    if (!dest->is_ssa && dest->reg.indirect)
1053       return state->cb(dest->reg.indirect, state->state);
1054
1055    return true;
1056 }
1057
1058 bool
1059 nir_foreach_src(nir_instr *instr, nir_foreach_src_cb cb, void *state)
1060 {
1061    switch (instr->type) {
1062    case nir_instr_type_alu:
1063       if (!visit_alu_src(nir_instr_as_alu(instr), cb, state))
1064          return false;
1065       break;
1066    case nir_instr_type_intrinsic:
1067       if (!visit_intrinsic_src(nir_instr_as_intrinsic(instr), cb, state))
1068          return false;
1069       break;
1070    case nir_instr_type_tex:
1071       if (!visit_tex_src(nir_instr_as_tex(instr), cb, state))
1072          return false;
1073       break;
1074    case nir_instr_type_call:
1075       if (!visit_call_src(nir_instr_as_call(instr), cb, state))
1076          return false;
1077       break;
1078    case nir_instr_type_load_const:
1079       if (!visit_load_const_src(nir_instr_as_load_const(instr), cb, state))
1080          return false;
1081       break;
1082    case nir_instr_type_phi:
1083       if (!visit_phi_src(nir_instr_as_phi(instr), cb, state))
1084          return false;
1085       break;
1086    case nir_instr_type_parallel_copy:
1087       if (!visit_parallel_copy_src(nir_instr_as_parallel_copy(instr),
1088                                    cb, state))
1089          return false;
1090       break;
1091    case nir_instr_type_jump:
1092    case nir_instr_type_ssa_undef:
1093       return true;
1094
1095    default:
1096       unreachable("Invalid instruction type");
1097       break;
1098    }
1099
1100    visit_dest_indirect_state dest_state;
1101    dest_state.state = state;
1102    dest_state.cb = cb;
1103    return nir_foreach_dest(instr, visit_dest_indirect, &dest_state);
1104 }
1105
1106 nir_const_value *
1107 nir_src_as_const_value(nir_src src)
1108 {
1109    if (!src.is_ssa)
1110       return NULL;
1111
1112    if (src.ssa->parent_instr->type != nir_instr_type_load_const)
1113       return NULL;
1114
1115    nir_load_const_instr *load = nir_instr_as_load_const(src.ssa->parent_instr);
1116
1117    return &load->value;
1118 }
1119
1120 bool
1121 nir_srcs_equal(nir_src src1, nir_src src2)
1122 {
1123    if (src1.is_ssa) {
1124       if (src2.is_ssa) {
1125          return src1.ssa == src2.ssa;
1126       } else {
1127          return false;
1128       }
1129    } else {
1130       if (src2.is_ssa) {
1131          return false;
1132       } else {
1133          if ((src1.reg.indirect == NULL) != (src2.reg.indirect == NULL))
1134             return false;
1135
1136          if (src1.reg.indirect) {
1137             if (!nir_srcs_equal(*src1.reg.indirect, *src2.reg.indirect))
1138                return false;
1139          }
1140
1141          return src1.reg.reg == src2.reg.reg &&
1142                 src1.reg.base_offset == src2.reg.base_offset;
1143       }
1144    }
1145 }
1146
1147 static bool
1148 src_is_valid(const nir_src *src)
1149 {
1150    return src->is_ssa ? (src->ssa != NULL) : (src->reg.reg != NULL);
1151 }
1152
1153 static void
1154 src_remove_all_uses(nir_src *src)
1155 {
1156    for (; src; src = src->is_ssa ? NULL : src->reg.indirect) {
1157       if (!src_is_valid(src))
1158          continue;
1159
1160       list_del(&src->use_link);
1161    }
1162 }
1163
1164 static void
1165 src_add_all_uses(nir_src *src, nir_instr *parent_instr, nir_if *parent_if)
1166 {
1167    for (; src; src = src->is_ssa ? NULL : src->reg.indirect) {
1168       if (!src_is_valid(src))
1169          continue;
1170
1171       if (parent_instr) {
1172          src->parent_instr = parent_instr;
1173          if (src->is_ssa)
1174             list_addtail(&src->use_link, &src->ssa->uses);
1175          else
1176             list_addtail(&src->use_link, &src->reg.reg->uses);
1177       } else {
1178          assert(parent_if);
1179          src->parent_if = parent_if;
1180          if (src->is_ssa)
1181             list_addtail(&src->use_link, &src->ssa->if_uses);
1182          else
1183             list_addtail(&src->use_link, &src->reg.reg->if_uses);
1184       }
1185    }
1186 }
1187
1188 void
1189 nir_instr_rewrite_src(nir_instr *instr, nir_src *src, nir_src new_src)
1190 {
1191    assert(!src_is_valid(src) || src->parent_instr == instr);
1192
1193    src_remove_all_uses(src);
1194    *src = new_src;
1195    src_add_all_uses(src, instr, NULL);
1196 }
1197
1198 void
1199 nir_instr_move_src(nir_instr *dest_instr, nir_src *dest, nir_src *src)
1200 {
1201    assert(!src_is_valid(dest) || dest->parent_instr == dest_instr);
1202
1203    src_remove_all_uses(dest);
1204    src_remove_all_uses(src);
1205    *dest = *src;
1206    *src = NIR_SRC_INIT;
1207    src_add_all_uses(dest, dest_instr, NULL);
1208 }
1209
1210 void
1211 nir_if_rewrite_condition(nir_if *if_stmt, nir_src new_src)
1212 {
1213    nir_src *src = &if_stmt->condition;
1214    assert(!src_is_valid(src) || src->parent_if == if_stmt);
1215
1216    src_remove_all_uses(src);
1217    *src = new_src;
1218    src_add_all_uses(src, NULL, if_stmt);
1219 }
1220
1221 void
1222 nir_ssa_def_init(nir_instr *instr, nir_ssa_def *def,
1223                  unsigned num_components, const char *name)
1224 {
1225    def->name = name;
1226    def->parent_instr = instr;
1227    list_inithead(&def->uses);
1228    list_inithead(&def->if_uses);
1229    def->num_components = num_components;
1230
1231    if (instr->block) {
1232       nir_function_impl *impl =
1233          nir_cf_node_get_function(&instr->block->cf_node);
1234
1235       def->index = impl->ssa_alloc++;
1236    } else {
1237       def->index = UINT_MAX;
1238    }
1239 }
1240
1241 void
1242 nir_ssa_dest_init(nir_instr *instr, nir_dest *dest,
1243                  unsigned num_components, const char *name)
1244 {
1245    dest->is_ssa = true;
1246    nir_ssa_def_init(instr, &dest->ssa, num_components, name);
1247 }
1248
1249 void
1250 nir_ssa_def_rewrite_uses(nir_ssa_def *def, nir_src new_src, void *mem_ctx)
1251 {
1252    assert(!new_src.is_ssa || def != new_src.ssa);
1253
1254    nir_foreach_use_safe(def, use_src) {
1255       nir_instr *src_parent_instr = use_src->parent_instr;
1256       list_del(&use_src->use_link);
1257       nir_src_copy(use_src, &new_src, mem_ctx);
1258       src_add_all_uses(use_src, src_parent_instr, NULL);
1259    }
1260
1261    nir_foreach_if_use_safe(def, use_src) {
1262       nir_if *src_parent_if = use_src->parent_if;
1263       list_del(&use_src->use_link);
1264       nir_src_copy(use_src, &new_src, mem_ctx);
1265       src_add_all_uses(use_src, NULL, src_parent_if);
1266    }
1267 }
1268
1269
1270 static bool foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1271                             bool reverse, void *state);
1272
1273 static inline bool
1274 foreach_if(nir_if *if_stmt, nir_foreach_block_cb cb, bool reverse, void *state)
1275 {
1276    if (reverse) {
1277       foreach_list_typed_safe_reverse(nir_cf_node, node, node,
1278                                       &if_stmt->else_list) {
1279          if (!foreach_cf_node(node, cb, reverse, state))
1280             return false;
1281       }
1282
1283       foreach_list_typed_safe_reverse(nir_cf_node, node, node,
1284                                       &if_stmt->then_list) {
1285          if (!foreach_cf_node(node, cb, reverse, state))
1286             return false;
1287       }
1288    } else {
1289       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->then_list) {
1290          if (!foreach_cf_node(node, cb, reverse, state))
1291             return false;
1292       }
1293
1294       foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list) {
1295          if (!foreach_cf_node(node, cb, reverse, state))
1296             return false;
1297       }
1298    }
1299
1300    return true;
1301 }
1302
1303 static inline bool
1304 foreach_loop(nir_loop *loop, nir_foreach_block_cb cb, bool reverse, void *state)
1305 {
1306    if (reverse) {
1307       foreach_list_typed_safe_reverse(nir_cf_node, node, node, &loop->body) {
1308          if (!foreach_cf_node(node, cb, reverse, state))
1309             return false;
1310       }
1311    } else {
1312       foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {
1313          if (!foreach_cf_node(node, cb, reverse, state))
1314             return false;
1315       }
1316    }
1317
1318    return true;
1319 }
1320
1321 static bool
1322 foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
1323                 bool reverse, void *state)
1324 {
1325    switch (node->type) {
1326    case nir_cf_node_block:
1327       return cb(nir_cf_node_as_block(node), state);
1328    case nir_cf_node_if:
1329       return foreach_if(nir_cf_node_as_if(node), cb, reverse, state);
1330    case nir_cf_node_loop:
1331       return foreach_loop(nir_cf_node_as_loop(node), cb, reverse, state);
1332       break;
1333
1334    default:
1335       unreachable("Invalid CFG node type");
1336       break;
1337    }
1338
1339    return false;
1340 }
1341
1342 bool
1343 nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb, void *state)
1344 {
1345    foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {
1346       if (!foreach_cf_node(node, cb, false, state))
1347          return false;
1348    }
1349
1350    return cb(impl->end_block, state);
1351 }
1352
1353 bool
1354 nir_foreach_block_reverse(nir_function_impl *impl, nir_foreach_block_cb cb,
1355                           void *state)
1356 {
1357    if (!cb(impl->end_block, state))
1358       return false;
1359
1360    foreach_list_typed_safe_reverse(nir_cf_node, node, node, &impl->body) {
1361       if (!foreach_cf_node(node, cb, true, state))
1362          return false;
1363    }
1364
1365    return true;
1366 }
1367
1368 nir_if *
1369 nir_block_get_following_if(nir_block *block)
1370 {
1371    if (exec_node_is_tail_sentinel(&block->cf_node.node))
1372       return NULL;
1373
1374    if (nir_cf_node_is_last(&block->cf_node))
1375       return NULL;
1376
1377    nir_cf_node *next_node = nir_cf_node_next(&block->cf_node);
1378
1379    if (next_node->type != nir_cf_node_if)
1380       return NULL;
1381
1382    return nir_cf_node_as_if(next_node);
1383 }
1384
1385 static bool
1386 index_block(nir_block *block, void *state)
1387 {
1388    unsigned *index = state;
1389    block->index = (*index)++;
1390    return true;
1391 }
1392
1393 void
1394 nir_index_blocks(nir_function_impl *impl)
1395 {
1396    unsigned index = 0;
1397
1398    if (impl->valid_metadata & nir_metadata_block_index)
1399       return;
1400
1401    nir_foreach_block(impl, index_block, &index);
1402
1403    impl->num_blocks = index;
1404 }
1405
1406 static bool
1407 index_ssa_def_cb(nir_ssa_def *def, void *state)
1408 {
1409    unsigned *index = (unsigned *) state;
1410    def->index = (*index)++;
1411
1412    return true;
1413 }
1414
1415 static bool
1416 index_ssa_block(nir_block *block, void *state)
1417 {
1418    nir_foreach_instr(block, instr)
1419       nir_foreach_ssa_def(instr, index_ssa_def_cb, state);
1420
1421    return true;
1422 }
1423
1424 void
1425 nir_index_ssa_defs(nir_function_impl *impl)
1426 {
1427    unsigned index = 0;
1428    nir_foreach_block(impl, index_ssa_block, &index);
1429    impl->ssa_alloc = index;
1430 }