nir_to_lcssa.c revision 01e04c3f 
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
41typedef 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
50static bool
51is_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
68static bool
69is_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
84static bool
85convert_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
160static void
161convert_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
191void
192nir_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}
206