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