Home | History | Annotate | Download | only in nir 
      1 /*
      2  * Copyright  2015 Thomas Helland
      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 
     24 /*
     25  * This pass converts the ssa-graph into "Loop Closed SSA form". This is
     26  * done by placing phi nodes at the exits of the loop for all values
     27  * that are used outside the loop. The result is it transforms:
     28  *
     29  * loop {                    ->      loop {
     30  *    ssa2 = ....            ->          ssa2 = ...
     31  *    if (cond)              ->          if (cond)
     32  *       break;              ->             break;
     33  *    ssa3 = ssa2 * ssa4     ->          ssa3 = ssa2 * ssa4
     34  * }                         ->       }
     35  * ssa6 = ssa2 + 4           ->       ssa5 = phi(ssa2)
     36  *                                    ssa6 = ssa5 + 4
     37  */
     38 
     39 #include "nir.h"
     40 
     41 typedef struct {
     42    /* The nir_shader we are transforming */
     43    nir_shader *shader;
     44 
     45    /* The loop we store information for */
     46    nir_loop *loop;
     47 
     48 } lcssa_state;
     49 
     50 static bool
     51 is_if_use_inside_loop(nir_src *use, nir_loop* loop)
     52 {
     53    nir_block *block_before_loop =
     54       nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
     55    nir_block *block_after_loop =
     56       nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
     57 
     58    nir_block *prev_block =
     59       nir_cf_node_as_block(nir_cf_node_prev(&use->parent_if->cf_node));
     60    if (prev_block->index <= block_before_loop->index ||
     61        prev_block->index >= block_after_loop->index) {
     62       return false;
     63    }
     64 
     65    return true;
     66 }
     67 
     68 static bool
     69 is_use_inside_loop(nir_src *use, nir_loop* loop)
     70 {
     71    nir_block *block_before_loop =
     72       nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
     73    nir_block *block_after_loop =
     74       nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
     75 
     76    if (use->parent_instr->block->index <= block_before_loop->index ||
     77        use->parent_instr->block->index >= block_after_loop->index) {
     78       return false;
     79    }
     80 
     81    return true;
     82 }
     83 
     84 static bool
     85 convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
     86 {
     87    lcssa_state *state = void_state;
     88    bool all_uses_inside_loop = true;
     89 
     90    nir_block *block_after_loop =
     91       nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
     92 
     93    nir_foreach_use(use, def) {
     94       if (use->parent_instr->type == nir_instr_type_phi &&
     95           use->parent_instr->block == block_after_loop) {
     96          continue;
     97       }
     98 
     99       if (!is_use_inside_loop(use, state->loop)) {
    100          all_uses_inside_loop = false;
    101       }
    102    }
    103 
    104    nir_foreach_if_use(use, def) {
    105       if (!is_if_use_inside_loop(use, state->loop)) {
    106          all_uses_inside_loop = false;
    107       }
    108    }
    109 
    110    /* There where no sources that had defs outside the loop */
    111    if (all_uses_inside_loop)
    112       return true;
    113 
    114    /* Initialize a phi-instruction */
    115    nir_phi_instr *phi = nir_phi_instr_create(state->shader);
    116    nir_ssa_dest_init(&phi->instr, &phi->dest,
    117                      def->num_components, def->bit_size, "LCSSA-phi");
    118 
    119    /* Create a phi node with as many sources pointing to the same ssa_def as
    120     * the block has predecessors.
    121     */
    122    struct set_entry *entry;
    123    set_foreach(block_after_loop->predecessors, entry) {
    124       nir_phi_src *phi_src = ralloc(phi, nir_phi_src);
    125       phi_src->src = nir_src_for_ssa(def);
    126       phi_src->pred = (nir_block *) entry->key;
    127 
    128       exec_list_push_tail(&phi->srcs, &phi_src->node);
    129    }
    130 
    131    nir_instr_insert_before_block(block_after_loop, &phi->instr);
    132 
    133    /* Run through all uses and rewrite those outside the loop to point to
    134     * the phi instead of pointing to the ssa-def.
    135     */
    136    nir_foreach_use_safe(use, def) {
    137       if (use->parent_instr->type == nir_instr_type_phi &&
    138           block_after_loop == use->parent_instr->block) {
    139          continue;
    140       }
    141 
    142       if (!is_use_inside_loop(use, state->loop)) {
    143          nir_instr_rewrite_src(use->parent_instr, use,
    144                                nir_src_for_ssa(&phi->dest.ssa));
    145       }
    146    }
    147 
    148    nir_foreach_if_use_safe(use, def) {
    149       if (!is_if_use_inside_loop(use, state->loop)) {
    150          nir_if_rewrite_condition(use->parent_if,
    151                                   nir_src_for_ssa(&phi->dest.ssa));
    152       }
    153    }
    154 
    155    return true;
    156 }
    157 
    158 static void
    159 convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
    160 {
    161    switch (cf_node->type) {
    162    case nir_cf_node_block:
    163       nir_foreach_instr(instr, nir_cf_node_as_block(cf_node))
    164          nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state);
    165       return;
    166    case nir_cf_node_if: {
    167       nir_if *if_stmt = nir_cf_node_as_if(cf_node);
    168       foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
    169          convert_to_lcssa(nested_node, state);
    170       foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
    171          convert_to_lcssa(nested_node, state);
    172       return;
    173    }
    174    case nir_cf_node_loop: {
    175       nir_loop *parent_loop = state->loop;
    176       state->loop = nir_cf_node_as_loop(cf_node);
    177 
    178       foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body)
    179          convert_to_lcssa(nested_node, state);
    180 
    181       state->loop = parent_loop;
    182       return;
    183    }
    184    default:
    185       unreachable("unknown cf node type");
    186    }
    187 }
    188 
    189 void
    190 nir_convert_loop_to_lcssa(nir_loop *loop) {
    191    nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
    192 
    193    nir_metadata_require(impl, nir_metadata_block_index);
    194 
    195    lcssa_state *state = rzalloc(NULL, lcssa_state);
    196    state->loop = loop;
    197    state->shader = impl->function->shader;
    198 
    199    foreach_list_typed(nir_cf_node, node, node, &state->loop->body)
    200       convert_to_lcssa(node, state);
    201 
    202    ralloc_free(state);
    203 }
    204