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 */
41struct 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
55class ir_array_refcount_entry
56{
57public:
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? */
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
103private:
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
138class ir_array_refcount_visitor : public ir_hierarchical_visitor {
139public:
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
160private:
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