1 /* 2 * Copyright 2016 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 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24 /** 25 * \file ir_array_refcount.cpp 26 * 27 * Provides a visitor which produces a list of variables referenced. 28 */ 29 30 #include "ir.h" 31 #include "ir_visitor.h" 32 #include "ir_array_refcount.h" 33 #include "compiler/glsl_types.h" 34 #include "util/hash_table.h" 35 36 ir_array_refcount_visitor::ir_array_refcount_visitor() 37 : last_array_deref(0), derefs(0), num_derefs(0), derefs_size(0) 38 { 39 this->mem_ctx = ralloc_context(NULL); 40 this->ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer, 41 _mesa_key_pointer_equal); 42 } 43 44 static void 45 free_entry(struct hash_entry *entry) 46 { 47 ir_array_refcount_entry *ivre = (ir_array_refcount_entry *) entry->data; 48 delete ivre; 49 } 50 51 ir_array_refcount_visitor::~ir_array_refcount_visitor() 52 { 53 ralloc_free(this->mem_ctx); 54 _mesa_hash_table_destroy(this->ht, free_entry); 55 } 56 57 ir_array_refcount_entry::ir_array_refcount_entry(ir_variable *var) 58 : var(var), is_referenced(false) 59 { 60 num_bits = MAX2(1, var->type->arrays_of_arrays_size()); 61 bits = new BITSET_WORD[BITSET_WORDS(num_bits)]; 62 memset(bits, 0, BITSET_WORDS(num_bits) * sizeof(bits[0])); 63 64 /* Count the "depth" of the arrays-of-arrays. */ 65 array_depth = 0; 66 for (const glsl_type *type = var->type; 67 type->is_array(); 68 type = type->fields.array) { 69 array_depth++; 70 } 71 } 72 73 74 ir_array_refcount_entry::~ir_array_refcount_entry() 75 { 76 delete [] bits; 77 } 78 79 80 void 81 ir_array_refcount_entry::mark_array_elements_referenced(const array_deref_range *dr, 82 unsigned count) 83 { 84 if (count != array_depth) 85 return; 86 87 mark_array_elements_referenced(dr, count, 1, 0); 88 } 89 90 void 91 ir_array_refcount_entry::mark_array_elements_referenced(const array_deref_range *dr, 92 unsigned count, 93 unsigned scale, 94 unsigned linearized_index) 95 { 96 /* Walk through the list of array dereferences in least- to 97 * most-significant order. Along the way, accumulate the current 98 * linearized offset and the scale factor for each array-of-. 99 */ 100 for (unsigned i = 0; i < count; i++) { 101 if (dr[i].index < dr[i].size) { 102 linearized_index += dr[i].index * scale; 103 scale *= dr[i].size; 104 } else { 105 /* For each element in the current array, update the count and 106 * offset, then recurse to process the remaining arrays. 107 * 108 * There is some inefficency here if the last element in the 109 * array_deref_range list specifies the entire array. In that case, 110 * the loop will make recursive calls with count == 0. In the call, 111 * all that will happen is the bit will be set. 112 */ 113 for (unsigned j = 0; j < dr[i].size; j++) { 114 mark_array_elements_referenced(&dr[i + 1], 115 count - (i + 1), 116 scale * dr[i].size, 117 linearized_index + (j * scale)); 118 } 119 120 return; 121 } 122 } 123 124 BITSET_SET(bits, linearized_index); 125 } 126 127 ir_array_refcount_entry * 128 ir_array_refcount_visitor::get_variable_entry(ir_variable *var) 129 { 130 assert(var); 131 132 struct hash_entry *e = _mesa_hash_table_search(this->ht, var); 133 if (e) 134 return (ir_array_refcount_entry *)e->data; 135 136 ir_array_refcount_entry *entry = new ir_array_refcount_entry(var); 137 _mesa_hash_table_insert(this->ht, var, entry); 138 139 return entry; 140 } 141 142 143 array_deref_range * 144 ir_array_refcount_visitor::get_array_deref() 145 { 146 if ((num_derefs + 1) * sizeof(array_deref_range) > derefs_size) { 147 void *ptr = reralloc_size(mem_ctx, derefs, derefs_size + 4096); 148 149 if (ptr == NULL) 150 return NULL; 151 152 derefs_size += 4096; 153 derefs = (array_deref_range *)ptr; 154 } 155 156 array_deref_range *d = &derefs[num_derefs]; 157 num_derefs++; 158 159 return d; 160 } 161 162 ir_visitor_status 163 ir_array_refcount_visitor::visit_enter(ir_dereference_array *ir) 164 { 165 /* It could also be a vector or a matrix. Individual elements of vectors 166 * are natrices are not tracked, so bail. 167 */ 168 if (!ir->array->type->is_array()) 169 return visit_continue; 170 171 /* If this array dereference is a child of an array dereference that was 172 * already visited, just continue on. Otherwise, for an arrays-of-arrays 173 * dereference like x[1][2][3][4], we'd process the [1][2][3][4] sequence, 174 * the [1][2][3] sequence, the [1][2] sequence, and the [1] sequence. This 175 * ensures that we only process the full sequence. 176 */ 177 if (last_array_deref && last_array_deref->array == ir) { 178 last_array_deref = ir; 179 return visit_continue; 180 } 181 182 last_array_deref = ir; 183 184 num_derefs = 0; 185 186 ir_rvalue *rv = ir; 187 while (rv->ir_type == ir_type_dereference_array) { 188 ir_dereference_array *const deref = rv->as_dereference_array(); 189 190 assert(deref != NULL); 191 assert(deref->array->type->is_array()); 192 193 ir_rvalue *const array = deref->array; 194 const ir_constant *const idx = deref->array_index->as_constant(); 195 array_deref_range *const dr = get_array_deref(); 196 197 dr->size = array->type->array_size(); 198 199 if (idx != NULL) { 200 dr->index = idx->get_int_component(0); 201 } else { 202 /* An unsized array can occur at the end of an SSBO. We can't track 203 * accesses to such an array, so bail. 204 */ 205 if (array->type->array_size() == 0) 206 return visit_continue; 207 208 dr->index = dr->size; 209 } 210 211 rv = array; 212 } 213 214 ir_dereference_variable *const var_deref = rv->as_dereference_variable(); 215 216 /* If the array being dereferenced is not a variable, bail. At the very 217 * least, ir_constant and ir_dereference_record are possible. 218 */ 219 if (var_deref == NULL) 220 return visit_continue; 221 222 ir_array_refcount_entry *const entry = 223 this->get_variable_entry(var_deref->var); 224 225 if (entry == NULL) 226 return visit_stop; 227 228 entry->mark_array_elements_referenced(derefs, num_derefs); 229 230 return visit_continue; 231 } 232 233 234 ir_visitor_status 235 ir_array_refcount_visitor::visit(ir_dereference_variable *ir) 236 { 237 ir_variable *const var = ir->variable_referenced(); 238 ir_array_refcount_entry *entry = this->get_variable_entry(var); 239 240 entry->is_referenced = true; 241 242 return visit_continue; 243 } 244 245 246 ir_visitor_status 247 ir_array_refcount_visitor::visit_enter(ir_function_signature *ir) 248 { 249 /* We don't want to descend into the function parameters and 250 * dead-code eliminate them, so just accept the body here. 251 */ 252 visit_list_elements(this, &ir->body); 253 return visit_continue_with_parent; 254 } 255
