src/compiler/glsl/ir_array_refcount.h

   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? */
  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 */