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.h 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 "compiler/glsl_types.h" 33 #include "util/bitset.h" 34 35 /** 36 * Describes an access of an array element or an access of the whole array 37 */ 38 struct array_deref_range { 39 /** 40 * Index that was accessed. 41 * 42 * All valid array indices are less than the size of the array. If index 43 * is equal to the size of the array, this means the entire array has been 44 * accessed (e.g., due to use of a non-constant index). 45 */ 46 unsigned index; 47 48 /** Size of the array. Used for offset calculations. */ 49 unsigned size; 50 }; 51 52 class ir_array_refcount_entry 53 { 54 public: 55 ir_array_refcount_entry(ir_variable *var); 56 ~ir_array_refcount_entry(); 57 58 ir_variable *var; /* The key: the variable's pointer. */ 59 60 /** Has the variable been referenced? */ 61 bool is_referenced; 62 63 /** 64 * Mark a set of array elements as accessed. 65 * 66 * If every \c array_deref_range is for a single index, only a single 67 * element will be marked. If any \c array_deref_range is for an entire 68 * array-of-, then multiple elements will be marked. 69 * 70 * Items in the \c array_deref_range list appear in least- to 71 * most-significant order. This is the \b opposite order the indices 72 * appear in the GLSL shader text. An array access like 73 * 74 * x = y[1][i][3]; 75 * 76 * would appear as 77 * 78 * { { 3, n }, { m, m }, { 1, p } } 79 * 80 * where n, m, and p are the sizes of the arrays-of-arrays. 81 * 82 * The set of marked array elements can later be queried by 83 * \c ::is_linearized_index_referenced. 84 * 85 * \param dr List of array_deref_range elements to be processed. 86 * \param count Number of array_deref_range elements to be processed. 87 */ 88 void mark_array_elements_referenced(const array_deref_range *dr, 89 unsigned count); 90 91 /** Has a linearized array index been referenced? */ is_linearized_index_referenced(unsigned linearized_index)92 bool is_linearized_index_referenced(unsigned linearized_index) const 93 { 94 assert(bits != 0); 95 assert(linearized_index <= num_bits); 96 97 return BITSET_TEST(bits, linearized_index); 98 } 99 100 private: 101 /** Set of bit-flags to note which array elements have been accessed. */ 102 BITSET_WORD *bits; 103 104 /** 105 * Total number of bits referenced by \c bits. 106 * 107 * Also the total number of array(s-of-arrays) elements of \c var. 108 */ 109 unsigned num_bits; 110 111 /** Count of nested arrays in the type. */ 112 unsigned array_depth; 113 114 /** 115 * Recursive part of the public mark_array_elements_referenced method. 116 * 117 * The recursion occurs when an entire array-of- is accessed. See the 118 * implementation for more details. 119 * 120 * \param dr List of array_deref_range elements to be 121 * processed. 122 * \param count Number of array_deref_range elements to be 123 * processed. 124 * \param scale Current offset scale. 125 * \param linearized_index Current accumulated linearized array index. 126 */ 127 void mark_array_elements_referenced(const array_deref_range *dr, 128 unsigned count, 129 unsigned scale, 130 unsigned linearized_index); 131 132 friend class array_refcount_test; 133 }; 134 135 class ir_array_refcount_visitor : public ir_hierarchical_visitor { 136 public: 137 ir_array_refcount_visitor(void); 138 ~ir_array_refcount_visitor(void); 139 140 virtual ir_visitor_status visit(ir_dereference_variable *); 141 142 virtual ir_visitor_status visit_enter(ir_function_signature *); 143 virtual ir_visitor_status visit_enter(ir_dereference_array *); 144 145 /** 146 * Find variable in the hash table, and insert it if not present 147 */ 148 ir_array_refcount_entry *get_variable_entry(ir_variable *var); 149 150 /** 151 * Hash table mapping ir_variable to ir_array_refcount_entry. 152 */ 153 struct hash_table *ht; 154 155 void *mem_ctx; 156 157 private: 158 /** Get an array_deref_range element from private tracking. */ 159 array_deref_range *get_array_deref(); 160 161 /** 162 * Last ir_dereference_array that was visited 163 * 164 * Used to prevent some redundant calculations. 165 * 166 * \sa ::visit_enter(ir_dereference_array *) 167 */ 168 ir_dereference_array *last_array_deref; 169 170 /** 171 * \name array_deref_range tracking 172 */ 173 /*@{*/ 174 /** Currently allocated block of derefs. */ 175 array_deref_range *derefs; 176 177 /** Number of derefs used in current processing. */ 178 unsigned num_derefs; 179 180 /** Size of the derefs buffer in bytes. */ 181 unsigned derefs_size; 182 /*@}*/ 183 }; 184