Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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