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 /* One of nir_op or nir_search_op */ 152 uint16_t opcode : 13; 153 154 /* Commutative expression index. This is assigned by opt_algebraic.py when 155 * search structures are constructed and is a unique (to this structure) 156 * index within the commutative operation bitfield used for searching for 157 * all combinations of expressions containing commutative operations. 158 */ 159 int8_t comm_expr_idx; 160 161 /* Number of commutative expressions in this expression including this one 162 * (if it is commutative). 163 */ 164 uint8_t comm_exprs; 165 166 /* Index in table->values[] for the expression operands */ 167 uint16_t srcs[4]; 168 169 /** Optional table->expression_cond[] fxn ptr index 170 * 171 * This allows additional constraints on expression matching, it is 172 * typically used to match an expressions uses such as the number of times 173 * the expression is used, and whether its used by an if. 174 */ 175 int16_t cond_index; 176 } nir_search_expression; 177 178 struct per_op_table { 179 const uint16_t *filter; 180 unsigned num_filtered_states; 181 const uint16_t *table; 182 }; 183 184 struct transform { 185 uint16_t search; /* Index in table->values[] for the search expression. */ 186 uint16_t replace; /* Index in table->values[] for the replace value. */ 187 unsigned condition_offset; 188 }; 189 190 typedef union { 191 nir_search_value value; /* base type of the union, first element of each variant struct */ 192 193 nir_search_constant constant; 194 nir_search_variable variable; 195 nir_search_expression expression; 196 } nir_search_value_union; 197 198 typedef bool (*nir_search_expression_cond)(const nir_alu_instr *instr); 199 typedef bool (*nir_search_variable_cond)(struct hash_table *range_ht, 200 const nir_alu_instr *instr, 201 unsigned src, unsigned num_components, 202 const uint8_t *swizzle); 203 204 /* Generated data table for an algebraic optimization pass. */ 205 typedef struct { 206 /** Array of all transforms in the pass. */ 207 const struct transform *transforms; 208 /** Mapping from automaton state index to location in *transforms. */ 209 const uint16_t *transform_offsets; 210 const struct per_op_table *pass_op_table; 211 const nir_search_value_union *values; 212 213 /** 214 * Array of condition functions for expressions, referenced by 215 * nir_search_expression->cond. 216 */ 217 const nir_search_expression_cond *expression_cond; 218 219 /** 220 * Array of condition functions for variables, referenced by 221 * nir_search_variable->cond. 222 */ 223 const nir_search_variable_cond *variable_cond; 224 } nir_algebraic_table; 225 226 /* Note: these must match the start states created in 227 * TreeAutomaton._build_table() 228 */ 229 230 /* WILDCARD_STATE = 0 is set by zeroing the state array */ 231 static const uint16_t CONST_STATE = 1; 232 233 NIR_DEFINE_CAST(nir_search_value_as_variable, nir_search_value, 234 nir_search_variable, value, 235 type, nir_search_value_variable) 236 NIR_DEFINE_CAST(nir_search_value_as_constant, nir_search_value, 237 nir_search_constant, value, 238 type, nir_search_value_constant) 239 NIR_DEFINE_CAST(nir_search_value_as_expression, nir_search_value, 240 nir_search_expression, value, 241 type, nir_search_value_expression) 242 243 bool 244 nir_algebraic_impl(nir_function_impl *impl, 245 const bool *condition_flags, 246 const nir_algebraic_table *table); 247 248 #endif /* _NIR_SEARCH_ */ 249