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