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 { 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 int 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 unsigned variable; 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; 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 condition fxn ptr 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 bool (*cond)(struct hash_table *range_ht, const nir_alu_instr *instr, 99 unsigned src, unsigned num_components, const uint8_t *swizzle); 100 101 /** Swizzle (for replace only) */ 102 uint8_t swizzle[NIR_MAX_VEC_COMPONENTS]; 103 } nir_search_variable; 104 105 typedef struct { 106 nir_search_value value; 107 108 nir_alu_type type; 109 110 union { 111 uint64_t u; 112 int64_t i; 113 double d; 114 } data; 115 } nir_search_constant; 116 117 enum nir_search_op { 118 nir_search_op_i2f = nir_last_opcode + 1, 119 nir_search_op_u2f, 120 nir_search_op_f2f, 121 nir_search_op_f2u, 122 nir_search_op_f2i, 123 nir_search_op_u2u, 124 nir_search_op_i2i, 125 nir_search_op_b2f, 126 nir_search_op_b2i, 127 nir_search_op_i2b, 128 nir_search_op_f2b, 129 nir_num_search_ops, 130 }; 131 132 uint16_t nir_search_op_for_nir_op(nir_op op); 133 134 typedef struct { 135 nir_search_value value; 136 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. 140 */ 141 bool inexact; 142 143 /** In a replacement, requests that the instruction be marked exact. */ 144 bool exact; 145 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. 150 */ 151 int8_t comm_expr_idx; 152 153 /* Number of commutative expressions in this expression including this one 154 * (if it is commutative). 155 */ 156 uint8_t comm_exprs; 157 158 /* One of nir_op or nir_search_op */ 159 uint16_t opcode; 160 const nir_search_value *srcs[4]; 161 162 /** Optional condition fxn ptr 163 * 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. 167 */ 168 bool (*cond)(nir_alu_instr *instr); 169 } nir_search_expression; 170 171 struct per_op_table { 172 const uint16_t *filter; 173 unsigned num_filtered_states; 174 const uint16_t *table; 175 }; 176 177 struct transform { 178 const nir_search_expression *search; 179 const nir_search_value *replace; 180 unsigned condition_offset; 181 }; 182 183 /* Note: these must match the start states created in 184 * TreeAutomaton._build_table() 185 */ 186 187 /* WILDCARD_STATE = 0 is set by zeroing the state array */ 188 static const uint16_t CONST_STATE = 1; 189 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) 199 200 nir_ssa_def * 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); 208 bool 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); 214 215 #endif /* _NIR_SEARCH_ */ 216