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 37 struct nir_builder; 38 39 typedef enum PACKED { 40 nir_search_value_expression, 41 nir_search_value_variable, 42 nir_search_value_constant, 43 } nir_search_value_type; 44 45 typedef 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 int8_t bit_size; 64 } nir_search_value; 65 66 typedef struct { 67 nir_search_value value; 68 69 /** The variable index; Must be less than NIR_SEARCH_MAX_VARIABLES */ 70 uint8_t variable : 7; 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 : 1; 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 table->variable_cond[] fxn ptr index 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 int16_t cond_index; 99 100 /** Swizzle (for replace only) */ 101 uint8_t swizzle[NIR_MAX_VEC_COMPONENTS]; 102 } nir_search_variable; 103 104 typedef struct { 105 nir_search_value value; 106 107 nir_alu_type type; 108 109 union { 110 uint64_t u; 111 int64_t i; 112 double d; 113 } data; 114 } nir_search_constant; 115 116 enum nir_search_op { 117 nir_search_op_i2f = nir_last_opcode + 1, 118 nir_search_op_u2f, 119 nir_search_op_f2f, 120 nir_search_op_f2u, 121 nir_search_op_f2i, 122 nir_search_op_u2u, 123 nir_search_op_i2i, 124 nir_search_op_b2f, 125 nir_search_op_b2i, 126 nir_search_op_i2b, 127 nir_search_op_f2b, 128 nir_num_search_ops, 129 }; 130 131 uint16_t nir_search_op_for_nir_op(nir_op op); 132 133 typedef struct { 134 nir_search_value value; 135 136 /* When set on a search expression, the expression will only match an SSA 137 * value that does *not* have the exact bit set. If unset, the exact bit 138 * on the SSA value is ignored. 139 */ 140 bool inexact : 1; 141 142 /** In a replacement, requests that the instruction be marked exact. */ 143 bool exact : 1; 144 145 /** Don't make the replacement exact if the search expression is exact. */ 146 bool ignore_exact : 1; 147 148 /* One of nir_op or nir_search_op */ 149 uint16_t opcode : 13; 150 151 /* Commutative expression index. This is assigned by opt_algebraic.py when 152 * search structures are constructed and is a unique (to this structure) 153 * index within the commutative operation bitfield used for searching for 154 * all combinations of expressions containing commutative operations. 155 */ 156 int8_t comm_expr_idx; 157 158 /* Number of commutative expressions in this expression including this one 159 * (if it is commutative). 160 */ 161 uint8_t comm_exprs; 162 163 /* Index in table->values[] for the expression operands */ 164 uint16_t srcs[4]; 165 166 /** Optional table->expression_cond[] fxn ptr index 167 * 168 * This allows additional constraints on expression matching, it is 169 * typically used to match an expressions uses such as the number of times 170 * the expression is used, and whether its used by an if. 171 */ 172 int16_t cond_index; 173 } nir_search_expression; 174 175 struct per_op_table { 176 const uint16_t *filter; 177 unsigned num_filtered_states; 178 const uint16_t *table; 179 }; 180 181 struct transform { 182 uint16_t search; /* Index in table->values[] for the search expression. */ 183 uint16_t replace; /* Index in table->values[] for the replace value. */ 184 unsigned condition_offset; 185 }; 186 187 typedef union { 188 nir_search_value value; /* base type of the union, first element of each variant struct */ 189 190 nir_search_constant constant; 191 nir_search_variable variable; 192 nir_search_expression expression; 193 } nir_search_value_union; 194 195 typedef bool (*nir_search_expression_cond)(const nir_alu_instr *instr); 196 typedef bool (*nir_search_variable_cond)(struct hash_table *range_ht, 197 const nir_alu_instr *instr, 198 unsigned src, unsigned num_components, 199 const uint8_t *swizzle); 200 201 /* Generated data table for an algebraic optimization pass. */ 202 typedef struct { 203 /** Array of all transforms in the pass. */ 204 const struct transform *transforms; 205 /** Mapping from automaton state index to location in *transforms. */ 206 const uint16_t *transform_offsets; 207 const struct per_op_table *pass_op_table; 208 const nir_search_value_union *values; 209 210 /** 211 * Array of condition functions for expressions, referenced by 212 * nir_search_expression->cond. 213 */ 214 const nir_search_expression_cond *expression_cond; 215 216 /** 217 * Array of condition functions for variables, referenced by 218 * nir_search_variable->cond. 219 */ 220 const nir_search_variable_cond *variable_cond; 221 } nir_algebraic_table; 222 223 /* Note: these must match the start states created in 224 * TreeAutomaton._build_table() 225 */ 226 227 /* WILDCARD_STATE = 0 is set by zeroing the state array */ 228 static const uint16_t CONST_STATE = 1; 229 230 NIR_DEFINE_CAST(nir_search_value_as_variable, nir_search_value, 231 nir_search_variable, value, 232 type, nir_search_value_variable) 233 NIR_DEFINE_CAST(nir_search_value_as_constant, nir_search_value, 234 nir_search_constant, value, 235 type, nir_search_value_constant) 236 NIR_DEFINE_CAST(nir_search_value_as_expression, nir_search_value, 237 nir_search_expression, value, 238 type, nir_search_value_expression) 239 240 nir_ssa_def * 241 nir_replace_instr(struct nir_builder *b, nir_alu_instr *instr, 242 struct hash_table *range_ht, 243 struct util_dynarray *states, 244 const nir_algebraic_table *table, 245 const nir_search_expression *search, 246 const nir_search_value *replace, 247 nir_instr_worklist *algebraic_worklist); 248 bool 249 nir_algebraic_impl(nir_function_impl *impl, 250 const bool *condition_flags, 251 const nir_algebraic_table *table); 252 253 #endif /* _NIR_SEARCH_ */ 254