2 * Copyright © 2014 Intel Corporation
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:
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
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
24 * Jason Ekstrand (jason@jlekstrand.net)
32 #include "nir_worklist.h"
33 #include "util/u_dynarray.h"
35 #define NIR_SEARCH_MAX_VARIABLES 16
40 nir_search_value_expression
,
41 nir_search_value_variable
,
42 nir_search_value_constant
,
43 } nir_search_value_type
;
46 nir_search_value_type type
;
49 * Bit size of the value. It is interpreted as follows:
51 * For a search expression:
52 * - If bit_size > 0, then the value only matches an SSA value with the
54 * - If bit_size <= 0, then the value matches any size SSA value.
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).
67 nir_search_value value
;
69 /** The variable index; Must be less than NIR_SEARCH_MAX_VARIABLES */
72 /** Indicates that the given variable must be a constant
74 * This is only allowed in search expressions and indicates that the
75 * given variable is only allowed to match constant values.
79 /** Indicates that the given variable must have a certain type
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.
86 * Note: A variable that is both constant and has a non-void type will
87 * never match anything.
91 /** Optional condition fxn ptr
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
98 bool (*cond
)(struct hash_table
*range_ht
, nir_alu_instr
*instr
, unsigned src
,
99 unsigned num_components
, const uint8_t *swizzle
);
101 /** Swizzle (for replace only) */
102 uint8_t swizzle
[NIR_MAX_VEC_COMPONENTS
];
103 } nir_search_variable
;
106 nir_search_value value
;
115 } nir_search_constant
;
118 nir_search_op_i2f
= nir_last_opcode
+ 1,
132 uint16_t nir_search_op_for_nir_op(nir_op op
);
135 nir_search_value value
;
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.
143 /** In a replacement, requests that the instruction be marked exact. */
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.
151 int8_t comm_expr_idx
;
153 /* Number of commutative expressions in this expression including this one
154 * (if it is commutative).
158 /* One of nir_op or nir_search_op */
160 const nir_search_value
*srcs
[4];
162 /** Optional condition fxn ptr
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.
168 bool (*cond
)(nir_alu_instr
*instr
);
169 } nir_search_expression
;
171 struct per_op_table
{
172 const uint16_t *filter
;
173 unsigned num_filtered_states
;
174 const uint16_t *table
;
178 const nir_search_expression
*search
;
179 const nir_search_value
*replace
;
180 unsigned condition_offset
;
183 /* Note: these must match the start states created in
184 * TreeAutomaton._build_table()
187 /* WILDCARD_STATE = 0 is set by zeroing the state array */
188 static const uint16_t CONST_STATE
= 1;
190 NIR_DEFINE_CAST(nir_search_value_as_variable
, nir_search_value
,
191 nir_search_variable
, value
,
192 type
, nir_search_value_variable
)
193 NIR_DEFINE_CAST(nir_search_value_as_constant
, nir_search_value
,
194 nir_search_constant
, value
,
195 type
, nir_search_value_constant
)
196 NIR_DEFINE_CAST(nir_search_value_as_expression
, nir_search_value
,
197 nir_search_expression
, value
,
198 type
, nir_search_value_expression
)
201 nir_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
);
209 nir_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
);
215 #endif /* _NIR_SEARCH_ */