1/*
2 * Copyright © 2014 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 * Authors:
24 *    Jason Ekstrand (jason@jlekstrand.net)
25 *
26 */
27
28#ifndef _NIR_SEARCH_
29#define _NIR_SEARCH_
30
31#include "nir.h"
32#include "nir_worklist.h"
33#include "util/u_dynarray.h"
34
35#define NIR_SEARCH_MAX_VARIABLES 16
36
37struct nir_builder;
38
39typedef enum {
40   nir_search_value_expression,
41   nir_search_value_variable,
42   nir_search_value_constant,
43} nir_search_value_type;
44
45typedef struct {
46   nir_search_value_type type;
47
48   /**
49    * Bit size of the value. It is interpreted as follows:
50    *
51    * For a search expression:
52    * - If bit_size > 0, then the value only matches an SSA value with the
53    *   given bit size.
54    * - If bit_size <= 0, then the value matches any size SSA value.
55    *
56    * For a replace expression:
57    * - If bit_size > 0, then the value is constructed with the given bit size.
58    * - If bit_size == 0, then the value is constructed with the same bit size
59    *   as the search value.
60    * - If bit_size < 0, then the value is constructed with the same bit size
61    *   as variable (-bit_size - 1).
62    */
63   int bit_size;
64} nir_search_value;
65
66typedef struct {
67   nir_search_value value;
68
69   /** The variable index;  Must be less than NIR_SEARCH_MAX_VARIABLES */
70   unsigned variable;
71
72   /** Indicates that the given variable must be a constant
73    *
74    * This is only allowed in search expressions and indicates that the
75    * given variable is only allowed to match constant values.
76    */
77   bool is_constant;
78
79   /** Indicates that the given variable must have a certain type
80    *
81    * This is only allowed in search expressions and indicates that the
82    * given variable is only allowed to match values that come from an ALU
83    * instruction with the given output type.  A type of nir_type_void
84    * means it can match any type.
85    *
86    * Note: A variable that is both constant and has a non-void type will
87    * never match anything.
88    */
89   nir_alu_type type;
90
91   /** Optional condition fxn ptr
92    *
93    * This is only allowed in search expressions, and allows additional
94    * constraints to be placed on the match.  Typically used for 'is_constant'
95    * variables to require, for example, power-of-two in order for the search
96    * to match.
97    */
98   bool (*cond)(struct hash_table *range_ht, const nir_alu_instr *instr,
99                unsigned src, unsigned num_components, const uint8_t *swizzle);
100
101   /** Swizzle (for replace only) */
102   uint8_t swizzle[NIR_MAX_VEC_COMPONENTS];
103} nir_search_variable;
104
105typedef struct {
106   nir_search_value value;
107
108   nir_alu_type type;
109
110   union {
111      uint64_t u;
112      int64_t i;
113      double d;
114   } data;
115} nir_search_constant;
116
117enum nir_search_op {
118   nir_search_op_i2f = nir_last_opcode + 1,
119   nir_search_op_u2f,
120   nir_search_op_f2f,
121   nir_search_op_f2u,
122   nir_search_op_f2i,
123   nir_search_op_u2u,
124   nir_search_op_i2i,
125   nir_search_op_b2f,
126   nir_search_op_b2i,
127   nir_search_op_i2b,
128   nir_search_op_f2b,
129   nir_num_search_ops,
130};
131
132uint16_t nir_search_op_for_nir_op(nir_op op);
133
134typedef struct {
135   nir_search_value value;
136
137   /* When set on a search expression, the expression will only match an SSA
138    * value that does *not* have the exact bit set.  If unset, the exact bit
139    * on the SSA value is ignored.
140    */
141   bool inexact;
142
143   /** In a replacement, requests that the instruction be marked exact. */
144   bool exact;
145
146   /* Commutative expression index.  This is assigned by opt_algebraic.py when
147    * search structures are constructed and is a unique (to this structure)
148    * index within the commutative operation bitfield used for searching for
149    * all combinations of expressions containing commutative operations.
150    */
151   int8_t comm_expr_idx;
152
153   /* Number of commutative expressions in this expression including this one
154    * (if it is commutative).
155    */
156   uint8_t comm_exprs;
157
158   /* One of nir_op or nir_search_op */
159   uint16_t opcode;
160   const nir_search_value *srcs[4];
161
162   /** Optional condition fxn ptr
163    *
164    * This allows additional constraints on expression matching, it is
165    * typically used to match an expressions uses such as the number of times
166    * the expression is used, and whether its used by an if.
167    */
168   bool (*cond)(nir_alu_instr *instr);
169} nir_search_expression;
170
171struct per_op_table {
172   const uint16_t *filter;
173   unsigned num_filtered_states;
174   const uint16_t *table;
175};
176
177struct transform {
178   const nir_search_expression *search;
179   const nir_search_value *replace;
180   unsigned condition_offset;
181};
182
183/* Note: these must match the start states created in
184 * TreeAutomaton._build_table()
185 */
186
187/* WILDCARD_STATE = 0 is set by zeroing the state array */
188static const uint16_t CONST_STATE = 1;
189
190NIR_DEFINE_CAST(nir_search_value_as_variable, nir_search_value,
191                nir_search_variable, value,
192                type, nir_search_value_variable)
193NIR_DEFINE_CAST(nir_search_value_as_constant, nir_search_value,
194                nir_search_constant, value,
195                type, nir_search_value_constant)
196NIR_DEFINE_CAST(nir_search_value_as_expression, nir_search_value,
197                nir_search_expression, value,
198                type, nir_search_value_expression)
199
200nir_ssa_def *
201nir_replace_instr(struct nir_builder *b, nir_alu_instr *instr,
202                  struct hash_table *range_ht,
203                  struct util_dynarray *states,
204                  const struct per_op_table *pass_op_table,
205                  const nir_search_expression *search,
206                  const nir_search_value *replace,
207                  nir_instr_worklist *algebraic_worklist);
208bool
209nir_algebraic_impl(nir_function_impl *impl,
210                   const bool *condition_flags,
211                   const struct transform **transforms,
212                   const uint16_t *transform_counts,
213                   const struct per_op_table *pass_op_table);
214
215#endif /* _NIR_SEARCH_ */
216