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   /* 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   set_foreach(block_after_loop->predecessors, entry) {
123      nir_phi_src *phi_src = ralloc(phi, nir_phi_src);
124      phi_src->src = nir_src_for_ssa(def);
125      phi_src->pred = (nir_block *) entry->key;
126
127      exec_list_push_tail(&phi->srcs, &phi_src->node);
128   }
129
130   nir_instr_insert_before_block(block_after_loop, &phi->instr);
131   nir_ssa_def *dest = &phi->dest.ssa;
132
133   /* deref instructions need a cast after the phi */
134   if (def->parent_instr->type == nir_instr_type_deref) {
135      nir_deref_instr *cast =
136         nir_deref_instr_create(state->shader, nir_deref_type_cast);
137
138      nir_deref_instr *instr = nir_instr_as_deref(def->parent_instr);
139      cast->mode = instr->mode;
140      cast->type = instr->type;
141      cast->parent = nir_src_for_ssa(&phi->dest.ssa);
142      cast->cast.ptr_stride = nir_deref_instr_ptr_as_array_stride(instr);
143
144      nir_ssa_dest_init(&cast->instr, &cast->dest,
145                        phi->dest.ssa.num_components,
146                        phi->dest.ssa.bit_size, NULL);
147      nir_instr_insert(nir_after_phis(block_after_loop), &cast->instr);
148      dest = &cast->dest.ssa;
149   }
150
151   /* Run through all uses and rewrite those outside the loop to point to
152    * the phi instead of pointing to the ssa-def.
153    */
154   nir_foreach_use_safe(use, def) {
155      if (use->parent_instr->type == nir_instr_type_phi &&
156          block_after_loop == use->parent_instr->block) {
157         continue;
158      }
159
160      if (!is_use_inside_loop(use, state->loop)) {
161         nir_instr_rewrite_src(use->parent_instr, use, nir_src_for_ssa(dest));
162      }
163   }
164
165   nir_foreach_if_use_safe(use, def) {
166      if (!is_if_use_inside_loop(use, state->loop)) {
167         nir_if_rewrite_condition(use->parent_if, nir_src_for_ssa(dest));
168      }
169   }
170
171   return true;
172}
173
174static void
175convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state)
176{
177   switch (cf_node->type) {
178   case nir_cf_node_block:
179      nir_foreach_instr(instr, nir_cf_node_as_block(cf_node))
180         nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state);
181      return;
182   case nir_cf_node_if: {
183      nir_if *if_stmt = nir_cf_node_as_if(cf_node);
184      foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
185         convert_to_lcssa(nested_node, state);
186      foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
187         convert_to_lcssa(nested_node, state);
188      return;
189   }
190   case nir_cf_node_loop: {
191      nir_loop *parent_loop = state->loop;
192      state->loop = nir_cf_node_as_loop(cf_node);
193
194      foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body)
195         convert_to_lcssa(nested_node, state);
196
197      state->loop = parent_loop;
198      return;
199   }
200   default:
201      unreachable("unknown cf node type");
202   }
203}
204
205void
206nir_convert_loop_to_lcssa(nir_loop *loop) {
207   nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node);
208
209   nir_metadata_require(impl, nir_metadata_block_index);
210
211   lcssa_state *state = rzalloc(NULL, lcssa_state);
212   state->loop = loop;
213   state->shader = impl->function->shader;
214
215   foreach_list_typed(nir_cf_node, node, node, &state->loop->body)
216      convert_to_lcssa(node, state);
217
218   ralloc_free(state);
219}
220