src/compiler/nir/nir_to_lcssa.c

   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    /* We don't want derefs ending up in phi sources */
 115    assert(def->parent_instr->type != nir_instr_type_deref);
 116
 117    /* Initialize a phi-instruction */
 118    nir_phi_instr *phi = nir_phi_instr_create(state->shader);
 119    nir_ssa_dest_init(&phi->instr, &phi->dest,
 120                      def->num_components, def->bit_size, "LCSSA-phi");
 121
 122    /* Create a phi node with as many sources pointing to the same ssa_def as
 123     * the block has predecessors.
 124     */
 125    set_foreach(block_after_loop->predecessors, entry) {
 126       nir_phi_src *phi_src = ralloc(phi, nir_phi_src);
 127       phi_src->src = nir_src_for_ssa(def);
 128       phi_src->pred = (nir_block *) entry->key;
 129
 130       exec_list_push_tail(&phi->srcs, &phi_src->node);
 131    }
 132
 133    nir_instr_insert_before_block(block_after_loop, &phi->instr);
 134
 135    /* Run through all uses and rewrite those outside the loop to point to
 136     * the phi instead of pointing to the ssa-def.
 137     */
 138    nir_foreach_use_safe(use, def) {
 139       if (use->parent_instr->type == nir_instr_type_phi &&
 140           block_after_loop == use->parent_instr->block) {
 141          continue;
 142       }
 143
 144       if (!is_use_inside_loop(use, state->loop)) {
 145          nir_instr_rewrite_src(use->parent_instr, use,
 146                                nir_src_for_ssa(&phi->dest.ssa));
 147       }
 148    }
 149
 150    nir_foreach_if_use_safe(use, def) {
 151       if (!is_if_use_inside_loop(use, state->loop)) {
 152          nir_if_rewrite_condition(use->parent_if,
 153                                   nir_src_for_ssa(&phi->dest.ssa));
 154       }
 155    }
 156
 157    return true;
 158 }
 159
 160 static void
 161 convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
 162 {
 163    switch (cf_node->type) {
 164    case nir_cf_node_block:
 165       nir_foreach_instr(instr, nir_cf_node_as_block(cf_node))
 166          nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state);
 167       return;
 168    case nir_cf_node_if: {
 169       nir_if *if_stmt = nir_cf_node_as_if(cf_node);
 170       foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
 171          convert_to_lcssa(nested_node, state);
 172       foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
 173          convert_to_lcssa(nested_node, state);
 174       return;
 175    }
 176    case nir_cf_node_loop: {
 177       nir_loop *parent_loop = state->loop;
 178       state->loop = nir_cf_node_as_loop(cf_node);
 179
 180       foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body)
 181          convert_to_lcssa(nested_node, state);
 182
 183       state->loop = parent_loop;
 184       return;
 185    }
 186    default:
 187       unreachable("unknown cf node type");
 188    }
 189 }
 190
 191 void
 192 nir_convert_loop_to_lcssa(nir_loop *loop) {
 193    nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
 194
 195    nir_metadata_require(impl, nir_metadata_block_index);
 196
 197    lcssa_state *state = rzalloc(NULL, lcssa_state);
 198    state->loop = loop;
 199    state->shader = impl->function->shader;
 200
 201    foreach_list_typed(nir_cf_node, node, node, &state->loop->body)
 202       convert_to_lcssa(node, state);
 203
 204    ralloc_free(state);
 205 }