1/*
2 * Copyright © 2016 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
24#include "nir_phi_builder.h"
25#include "nir/nir_vla.h"
26
27struct nir_phi_builder {
28   nir_shader *shader;
29   nir_function_impl *impl;
30
31   /* Copied from the impl for easy access */
32   unsigned num_blocks;
33
34   /* Array of all blocks indexed by block->index. */
35   nir_block **blocks;
36
37   /* Hold on to the values so we can easily iterate over them. */
38   struct exec_list values;
39
40   /* Worklist for phi adding */
41   unsigned iter_count;
42   unsigned *work;
43   nir_block **W;
44};
45
46#define NEEDS_PHI ((nir_ssa_def *)(intptr_t)-1)
47
48struct nir_phi_builder_value {
49   struct exec_node node;
50
51   struct nir_phi_builder *builder;
52
53   /* Needed so we can create phis and undefs */
54   unsigned num_components;
55   unsigned bit_size;
56
57   /* The list of phi nodes associated with this value.  Phi nodes are not
58    * added directly.  Instead, they are created, the instr->block pointer
59    * set, and then added to this list.  Later, in phi_builder_finish, we
60    * set up their sources and add them to the top of their respective
61    * blocks.
62    */
63   struct exec_list phis;
64
65   /* Array of SSA defs, indexed by block.  For each block, this array has has
66    * one of three types of values:
67    *
68    *  - NULL. Indicates that there is no known definition in this block.  If
69    *    you need to find one, look at the block's immediate dominator.
70    *
71    *  - NEEDS_PHI. Indicates that the block may need a phi node but none has
72    *    been created yet.  If a def is requested for a block, a phi will need
73    *    to be created.
74    *
75    *  - A regular SSA def.  This will be either the result of a phi node or
76    *    one of the defs provided by nir_phi_builder_value_set_blocK_def().
77    */
78   struct hash_table ht;
79};
80
81/**
82 * Convert a block index into a value that can be used as a key for a hash table
83 *
84 * The hash table functions want a pointer that is not \c NULL.
85 * _mesa_hash_pointer drops the two least significant bits, but that's where
86 * most of our data likely is.  Shift by 2 and add 1 to make everything happy.
87 */
88#define INDEX_TO_KEY(x) ((void *)(uintptr_t) ((x << 2) + 1))
89
90struct nir_phi_builder *
91nir_phi_builder_create(nir_function_impl *impl)
92{
93   struct nir_phi_builder *pb = rzalloc(NULL, struct nir_phi_builder);
94
95   pb->shader = impl->function->shader;
96   pb->impl = impl;
97
98   assert(impl->valid_metadata & (nir_metadata_block_index |
99                                  nir_metadata_dominance));
100
101   pb->num_blocks = impl->num_blocks;
102   pb->blocks = ralloc_array(pb, nir_block *, pb->num_blocks);
103   nir_foreach_block(block, impl) {
104      pb->blocks[block->index] = block;
105   }
106
107   exec_list_make_empty(&pb->values);
108
109   pb->iter_count = 0;
110   pb->work = rzalloc_array(pb, unsigned, pb->num_blocks);
111   pb->W = ralloc_array(pb, nir_block *, pb->num_blocks);
112
113   return pb;
114}
115
116struct nir_phi_builder_value *
117nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
118                          unsigned bit_size, const BITSET_WORD *defs)
119{
120   struct nir_phi_builder_value *val;
121   unsigned i, w_start = 0, w_end = 0;
122
123   val = rzalloc_size(pb, sizeof(*val));
124   val->builder = pb;
125   val->num_components = num_components;
126   val->bit_size = bit_size;
127   exec_list_make_empty(&val->phis);
128   exec_list_push_tail(&pb->values, &val->node);
129
130   _mesa_hash_table_init(&val->ht, pb, _mesa_hash_pointer,
131                         _mesa_key_pointer_equal);
132
133   pb->iter_count++;
134
135   BITSET_FOREACH_SET(i, defs, pb->num_blocks) {
136      if (pb->work[i] < pb->iter_count)
137         pb->W[w_end++] = pb->blocks[i];
138      pb->work[i] = pb->iter_count;
139   }
140
141   while (w_start != w_end) {
142      nir_block *cur = pb->W[w_start++];
143      set_foreach(cur->dom_frontier, dom_entry) {
144         nir_block *next = (nir_block *) dom_entry->key;
145
146         /* If there's more than one return statement, then the end block
147          * can be a join point for some definitions. However, there are
148          * no instructions in the end block, so nothing would use those
149          * phi nodes. Of course, we couldn't place those phi nodes
150          * anyways due to the restriction of having no instructions in the
151          * end block...
152          */
153         if (next == pb->impl->end_block)
154            continue;
155
156         if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(next->index)) == NULL) {
157            /* Instead of creating a phi node immediately, we simply set the
158             * value to the magic value NEEDS_PHI.  Later, we create phi nodes
159             * on demand in nir_phi_builder_value_get_block_def().
160             */
161            nir_phi_builder_value_set_block_def(val, next, NEEDS_PHI);
162
163            if (pb->work[next->index] < pb->iter_count) {
164               pb->work[next->index] = pb->iter_count;
165               pb->W[w_end++] = next;
166            }
167         }
168      }
169   }
170
171   return val;
172}
173
174void
175nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
176                                    nir_block *block, nir_ssa_def *def)
177{
178   _mesa_hash_table_insert(&val->ht, INDEX_TO_KEY(block->index), def);
179}
180
181nir_ssa_def *
182nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
183                                    nir_block *block)
184{
185   /* Crawl up the dominance tree and find the closest dominator for which we
186    * have a valid ssa_def, if any.
187    */
188   nir_block *dom = block;
189   struct hash_entry *he = NULL;
190
191   while (dom != NULL) {
192      he = _mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index));
193      if (he != NULL)
194         break;
195
196      dom = dom->imm_dom;
197   }
198
199   /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
200   assert((he != NULL) != (dom == NULL));
201
202   nir_ssa_def *def;
203   if (dom == NULL) {
204      /* No dominator means either that we crawled to the top without ever
205       * finding a definition or that this block is unreachable.  In either
206       * case, the value is undefined so we need an SSA undef.
207       */
208      nir_ssa_undef_instr *undef =
209         nir_ssa_undef_instr_create(val->builder->shader,
210                                    val->num_components,
211                                    val->bit_size);
212      nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
213                       &undef->instr);
214      def = &undef->def;
215   } else if (he->data == NEEDS_PHI) {
216      /* The magic value NEEDS_PHI indicates that the block needs a phi node
217       * but none has been created.  We need to create one now so we can
218       * return it to the caller.
219       *
220       * Because a phi node may use SSA defs that it does not dominate (this
221       * happens in loops), we do not yet have enough information to fully
222       * fill out the phi node.  Instead, the phi nodes we create here will be
223       * empty (have no sources) and won't actually be placed in the block's
224       * instruction list yet.  Later, in nir_phi_builder_finish(), we walk
225       * over all of the phi instructions, fill out the sources lists, and
226       * place them at the top of their respective block's instruction list.
227       *
228       * Creating phi nodes on-demand allows us to avoid creating dead phi
229       * nodes that will just get deleted later. While this probably isn't a
230       * big win for a full into-SSA pass, other users may use the phi builder
231       * to make small SSA form repairs where most of the phi nodes will never
232       * be used.
233       */
234      nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
235      nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components,
236                        val->bit_size, NULL);
237      phi->instr.block = dom;
238      exec_list_push_tail(&val->phis, &phi->instr.node);
239      def = &phi->dest.ssa;
240      he->data = def;
241   } else {
242      /* In this case, we have an actual SSA def.  It's either the result of a
243       * phi node created by the case above or one passed to us through
244       * nir_phi_builder_value_set_block_def().
245       */
246      def = (struct nir_ssa_def *) he->data;
247   }
248
249   /* Walk the chain and stash the def in all of the applicable blocks.  We do
250    * this for two reasons:
251    *
252    *  1) To speed up lookup next time even if the next time is called from a
253    *     block that is not dominated by this one.
254    *  2) To avoid unneeded recreation of phi nodes and undefs.
255    */
256   for (dom = block; dom != NULL; dom = dom->imm_dom) {
257      if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)) != NULL)
258         break;
259
260      nir_phi_builder_value_set_block_def(val, dom, def);
261   }
262
263   return def;
264}
265
266void
267nir_phi_builder_finish(struct nir_phi_builder *pb)
268{
269   foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) {
270      /* We treat the linked list of phi nodes like a worklist.  The list is
271       * pre-populated by calls to nir_phi_builder_value_get_block_def() that
272       * create phi nodes.  As we fill in the sources of phi nodes, more may
273       * be created and are added to the end of the list.
274       *
275       * Because we are adding and removing phi nodes from the list as we go,
276       * we can't iterate over it normally.  Instead, we just iterate until
277       * the list is empty.
278       */
279      while (!exec_list_is_empty(&val->phis)) {
280         struct exec_node *head = exec_list_get_head(&val->phis);
281         nir_phi_instr *phi = exec_node_data(nir_phi_instr, head, instr.node);
282         assert(phi->instr.type == nir_instr_type_phi);
283
284         exec_node_remove(&phi->instr.node);
285
286         /* XXX: Constructing the array this many times seems expensive. */
287         nir_block **preds = nir_block_get_predecessors_sorted(phi->instr.block, pb);
288
289         for (unsigned i = 0; i < phi->instr.block->predecessors->entries; i++) {
290            nir_phi_instr_add_src(phi, preds[i],
291                                  nir_src_for_ssa(nir_phi_builder_value_get_block_def(val, preds[i])));
292         }
293
294         ralloc_free(preds);
295
296         nir_instr_insert(nir_before_block(phi->instr.block), &phi->instr);
297      }
298   }
299
300   ralloc_free(pb);
301}
302