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