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#ifndef NIR_PHI_BUILDER_H
25#define NIR_PHI_BUILDER_H
26
27#include "nir.h"
28
29/** A helper for placing phi nodes in a NIR shader
30 *
31 * Basic usage goes something like this:
32 *
33 *     each variable, var, has:
34 *         a bitset var.defs of blocks where the variable is defined
35 *         a struct nir_phi_builder_value *pb_val
36 *
37 *     // initialize bitsets
38 *     foreach block:
39 *         foreach def of variable var:
40 *             var.defs[def.block] = true;
41 *
42 *     // initialize phi builder
43 *     pb = nir_phi_builder_create()
44 *     foreach var:
45 *         var.pb_val = nir_phi_builder_add_value(pb, var.defs)
46 *
47 *     // Visit each block.  This needs to visit dominators first;
48 *     // nir_foreach_block() will be ok.
49 *
50 *     foreach block:
51 *         foreach instruction:
52 *             foreach use of variable var:
53 *                 replace use with nir_phi_builder_get_block_def(var.pb_val)
54 *             foreach def of variable var:
55 *                 create ssa def, register with
56 *     nir_phi_builder_set_block_def(var.pb_val)
57 *
58 *     nir_phi_builder_finish(pb)
59 */
60struct nir_phi_builder;
61
62struct nir_phi_builder_value;
63
64/* Create a new phi builder.
65 *
66 * While this is fairly cheap, it does allocate some memory and walk the list
67 * of blocks so it's recommended that you only call it once and use it to
68 * build phis for several values.
69 */
70struct nir_phi_builder *nir_phi_builder_create(nir_function_impl *impl);
71
72/* Register a value with the builder.
73 *
74 * The 'defs' parameter specifies a bitset of blocks in which the given value
75 * is defined.  This is used to determine where to place the phi nodes.
76 */
77struct nir_phi_builder_value *
78nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
79                          unsigned bit_size, const BITSET_WORD *defs);
80
81/* Register a definition for the given value and block.
82 *
83 * It is safe to call this function as many times as you wish for any given
84 * block/value pair.  However, it always replaces whatever was there
85 * previously even if that definition is from a phi node.  The phi builder
86 * always uses the latest information it has, so you must be careful about the
87 * order in which you register definitions.  The final value at the end of the
88 * block must be the last value registered.
89 */
90void
91nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
92                                    nir_block *block, nir_ssa_def *def);
93
94/* Get the definition for the given value in the given block.
95 *
96 * This definition will always be the latest definition known for the given
97 * block.  If no definition is immediately available, it will crawl up the
98 * dominance tree and insert phi nodes as needed until it finds one.  In the
99 * case that no suitable definition is found, it will return the result of a
100 * nir_ssa_undef_instr with the correct number of components.
101 *
102 * Because this function only uses the latest available information for any
103 * given block, you must have already finished registering definitions for any
104 * blocks that dominate the current block in order to get the correct result.
105 */
106nir_ssa_def *
107nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
108                                    nir_block *block);
109
110/* Finish building phi nodes and free the builder.
111 *
112 * This function does far more than just free memory.  Prior to calling
113 * nir_phi_builder_finish, no phi nodes have actually been inserted in the
114 * program.  This function is what finishes setting up phi node sources and
115 * adds the phi nodes to the program.
116 */
117void nir_phi_builder_finish(struct nir_phi_builder *pb);
118
119#endif /* NIR_PHI_BUILDER_H */
120