15085b640313f806150729a197c438a0cfea35f49Ian Romanick/* 25085b640313f806150729a197c438a0cfea35f49Ian Romanick * Copyright © 2016 Intel Corporation 35085b640313f806150729a197c438a0cfea35f49Ian Romanick * 45085b640313f806150729a197c438a0cfea35f49Ian Romanick * Permission is hereby granted, free of charge, to any person obtaining a 55085b640313f806150729a197c438a0cfea35f49Ian Romanick * copy of this software and associated documentation files (the "Software"), 65085b640313f806150729a197c438a0cfea35f49Ian Romanick * to deal in the Software without restriction, including without limitation 75085b640313f806150729a197c438a0cfea35f49Ian Romanick * the rights to use, copy, modify, merge, publish, distribute, sublicense, 85085b640313f806150729a197c438a0cfea35f49Ian Romanick * and/or sell copies of the Software, and to permit persons to whom the 95085b640313f806150729a197c438a0cfea35f49Ian Romanick * Software is furnished to do so, subject to the following conditions: 105085b640313f806150729a197c438a0cfea35f49Ian Romanick * 115085b640313f806150729a197c438a0cfea35f49Ian Romanick * The above copyright notice and this permission notice (including the next 125085b640313f806150729a197c438a0cfea35f49Ian Romanick * paragraph) shall be included in all copies or substantial portions of the 135085b640313f806150729a197c438a0cfea35f49Ian Romanick * Software. 145085b640313f806150729a197c438a0cfea35f49Ian Romanick * 155085b640313f806150729a197c438a0cfea35f49Ian Romanick * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 165085b640313f806150729a197c438a0cfea35f49Ian Romanick * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 175085b640313f806150729a197c438a0cfea35f49Ian Romanick * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 185085b640313f806150729a197c438a0cfea35f49Ian Romanick * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 195085b640313f806150729a197c438a0cfea35f49Ian Romanick * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 205085b640313f806150729a197c438a0cfea35f49Ian Romanick * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 215085b640313f806150729a197c438a0cfea35f49Ian Romanick * DEALINGS IN THE SOFTWARE. 225085b640313f806150729a197c438a0cfea35f49Ian Romanick */ 235085b640313f806150729a197c438a0cfea35f49Ian Romanick 245085b640313f806150729a197c438a0cfea35f49Ian Romanick/** 255085b640313f806150729a197c438a0cfea35f49Ian Romanick * \file ir_array_refcount.h 265085b640313f806150729a197c438a0cfea35f49Ian Romanick * 275085b640313f806150729a197c438a0cfea35f49Ian Romanick * Provides a visitor which produces a list of variables referenced. 285085b640313f806150729a197c438a0cfea35f49Ian Romanick */ 295085b640313f806150729a197c438a0cfea35f49Ian Romanick 305085b640313f806150729a197c438a0cfea35f49Ian Romanick#include "ir.h" 315085b640313f806150729a197c438a0cfea35f49Ian Romanick#include "ir_visitor.h" 325085b640313f806150729a197c438a0cfea35f49Ian Romanick#include "compiler/glsl_types.h" 33b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick#include "util/bitset.h" 345085b640313f806150729a197c438a0cfea35f49Ian Romanick 358d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick/** 368d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * Describes an access of an array element or an access of the whole array 378d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick */ 388d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanickstruct array_deref_range { 398d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** 408d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * Index that was accessed. 418d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * 428d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * All valid array indices are less than the size of the array. If index 438d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * is equal to the size of the array, this means the entire array has been 448d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * accessed (e.g., due to use of a non-constant index). 458d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick */ 468d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick unsigned index; 478d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick 488d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** Size of the array. Used for offset calculations. */ 498d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick unsigned size; 508d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick}; 518d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick 525085b640313f806150729a197c438a0cfea35f49Ian Romanickclass ir_array_refcount_entry 535085b640313f806150729a197c438a0cfea35f49Ian Romanick{ 545085b640313f806150729a197c438a0cfea35f49Ian Romanickpublic: 555085b640313f806150729a197c438a0cfea35f49Ian Romanick ir_array_refcount_entry(ir_variable *var); 56b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick ~ir_array_refcount_entry(); 575085b640313f806150729a197c438a0cfea35f49Ian Romanick 585085b640313f806150729a197c438a0cfea35f49Ian Romanick ir_variable *var; /* The key: the variable's pointer. */ 595085b640313f806150729a197c438a0cfea35f49Ian Romanick 605085b640313f806150729a197c438a0cfea35f49Ian Romanick /** Has the variable been referenced? */ 615085b640313f806150729a197c438a0cfea35f49Ian Romanick bool is_referenced; 62b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick 63e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick /** 64e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * Mark a set of array elements as accessed. 65e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 66e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * If every \c array_deref_range is for a single index, only a single 67e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * element will be marked. If any \c array_deref_range is for an entire 68e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * array-of-, then multiple elements will be marked. 69e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 70e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * Items in the \c array_deref_range list appear in least- to 71e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * most-significant order. This is the \b opposite order the indices 72e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * appear in the GLSL shader text. An array access like 73e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 74e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * x = y[1][i][3]; 75e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 76e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * would appear as 77e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 78e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * { { 3, n }, { m, m }, { 1, p } } 79e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 80e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * where n, m, and p are the sizes of the arrays-of-arrays. 81e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 82e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * The set of marked array elements can later be queried by 83e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \c ::is_linearized_index_referenced. 84e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 85e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \param dr List of array_deref_range elements to be processed. 86e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \param count Number of array_deref_range elements to be processed. 87e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick */ 88e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick void mark_array_elements_referenced(const array_deref_range *dr, 89e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick unsigned count); 90e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick 91b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick /** Has a linearized array index been referenced? */ 92b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick bool is_linearized_index_referenced(unsigned linearized_index) const 93b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick { 94b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick assert(bits != 0); 95b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick assert(linearized_index <= num_bits); 96b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick 97b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick return BITSET_TEST(bits, linearized_index); 98b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick } 99b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick 100b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanickprivate: 101b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick /** Set of bit-flags to note which array elements have been accessed. */ 102b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick BITSET_WORD *bits; 103b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick 104b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick /** 105b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick * Total number of bits referenced by \c bits. 106b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick * 107b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick * Also the total number of array(s-of-arrays) elements of \c var. 108b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick */ 109b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick unsigned num_bits; 110b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick 111e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick /** Count of nested arrays in the type. */ 112e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick unsigned array_depth; 113e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick 114e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick /** 115e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * Recursive part of the public mark_array_elements_referenced method. 116e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 117e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * The recursion occurs when an entire array-of- is accessed. See the 118e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * implementation for more details. 119e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * 120e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \param dr List of array_deref_range elements to be 121e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * processed. 122e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \param count Number of array_deref_range elements to be 123e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * processed. 124e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \param scale Current offset scale. 125e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick * \param linearized_index Current accumulated linearized array index. 126e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick */ 127e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick void mark_array_elements_referenced(const array_deref_range *dr, 128e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick unsigned count, 129e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick unsigned scale, 130e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick unsigned linearized_index); 131e92935089bd9a987027d1f0791e7298bb3a57113Ian Romanick 132b7053b80f27091acc8ccc954db99197e3073bff4Ian Romanick friend class array_refcount_test; 1335085b640313f806150729a197c438a0cfea35f49Ian Romanick}; 1345085b640313f806150729a197c438a0cfea35f49Ian Romanick 1355085b640313f806150729a197c438a0cfea35f49Ian Romanickclass ir_array_refcount_visitor : public ir_hierarchical_visitor { 1365085b640313f806150729a197c438a0cfea35f49Ian Romanickpublic: 1375085b640313f806150729a197c438a0cfea35f49Ian Romanick ir_array_refcount_visitor(void); 1385085b640313f806150729a197c438a0cfea35f49Ian Romanick ~ir_array_refcount_visitor(void); 1395085b640313f806150729a197c438a0cfea35f49Ian Romanick 1405085b640313f806150729a197c438a0cfea35f49Ian Romanick virtual ir_visitor_status visit(ir_dereference_variable *); 1415085b640313f806150729a197c438a0cfea35f49Ian Romanick 1425085b640313f806150729a197c438a0cfea35f49Ian Romanick virtual ir_visitor_status visit_enter(ir_function_signature *); 143d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick virtual ir_visitor_status visit_enter(ir_dereference_array *); 1445085b640313f806150729a197c438a0cfea35f49Ian Romanick 1455085b640313f806150729a197c438a0cfea35f49Ian Romanick /** 1465085b640313f806150729a197c438a0cfea35f49Ian Romanick * Find variable in the hash table, and insert it if not present 1475085b640313f806150729a197c438a0cfea35f49Ian Romanick */ 1485085b640313f806150729a197c438a0cfea35f49Ian Romanick ir_array_refcount_entry *get_variable_entry(ir_variable *var); 1495085b640313f806150729a197c438a0cfea35f49Ian Romanick 1505085b640313f806150729a197c438a0cfea35f49Ian Romanick /** 1515085b640313f806150729a197c438a0cfea35f49Ian Romanick * Hash table mapping ir_variable to ir_array_refcount_entry. 1525085b640313f806150729a197c438a0cfea35f49Ian Romanick */ 1535085b640313f806150729a197c438a0cfea35f49Ian Romanick struct hash_table *ht; 1545085b640313f806150729a197c438a0cfea35f49Ian Romanick 1555085b640313f806150729a197c438a0cfea35f49Ian Romanick void *mem_ctx; 1568d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick 1578d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanickprivate: 1588d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** Get an array_deref_range element from private tracking. */ 1598d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick array_deref_range *get_array_deref(); 1608d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick 1618d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** 162d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick * Last ir_dereference_array that was visited 163d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick * 164d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick * Used to prevent some redundant calculations. 165d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick * 166d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick * \sa ::visit_enter(ir_dereference_array *) 167d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick */ 168d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick ir_dereference_array *last_array_deref; 169d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick 170d32956935edf06c8ae6872c707bc65187b4a1d15Ian Romanick /** 1718d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick * \name array_deref_range tracking 1728d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick */ 1738d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /*@{*/ 1748d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** Currently allocated block of derefs. */ 1758d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick array_deref_range *derefs; 1768d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick 1778d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** Number of derefs used in current processing. */ 1788d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick unsigned num_derefs; 1798d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick 1808d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /** Size of the derefs buffer in bytes. */ 1818d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick unsigned derefs_size; 1828d499f60c88b70a39f53d0fbe96a6ada6fd36b8bIan Romanick /*@}*/ 1835085b640313f806150729a197c438a0cfea35f49Ian Romanick}; 184