src/gallium/drivers/r600/sfn/sfn_liverange.h

   1 /* -*- mesa-c++  -*-
   2  *
   3  * Copyright (c) 2018-2019 Collabora LTD
   4  *
   5  * Author: Gert Wollny <gert.wollny@collabora.com>
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a
   8  * copy of this software and associated documentation files (the "Software"),
   9  * to deal in the Software without restriction, including without limitation
  10  * on the rights to use, copy, modify, merge, publish, distribute, sub
  11  * license, and/or sell copies of the Software, and to permit persons to whom
  12  * the Software is furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the next
  15  * paragraph) shall be included in all copies or substantial portions of the
  16  * Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
  21  * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
  22  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  23  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  24  * USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 #ifndef SFN_LIVERANGE_H
  28 #define SFN_LIVERANGE_H
  29
  30 #include <cstdint>
  31 #include <ostream>
  32 #include <vector>
  33 #include <limits>
  34
  35 #include "sfn_instruction_base.h"
  36 #include "sfn_nir.h"
  37
  38 namespace r600 {
  39
  40 /** Storage to record the required live range of a temporary register
  41  * begin == end == -1 indicates that the register can be reused without
  42  * limitations. Otherwise, "begin" indicates the first instruction in which
  43  * a write operation may target this temporary, and end indicates the
  44  * last instruction in which a value can be read from this temporary.
  45  * Hence, a register R2 can be merged with a register R1 if R1.end <= R2.begin.
  46  */
  47 struct register_live_range {
  48    int begin;
  49    int end;
  50    bool is_array_elm;
  51 };
  52
  53 enum prog_scope_type {
  54    outer_scope,           /* Outer program scope */
  55    loop_body,             /* Inside a loop */
  56    if_branch,             /* Inside if branch */
  57    else_branch,           /* Inside else branch */
  58    switch_body,           /* Inside switch statmenet */
  59    switch_case_branch,    /* Inside switch case statmenet */
  60    switch_default_branch, /* Inside switch default statmenet */
  61    undefined_scope
  62 };
  63
  64 class prog_scope {
  65 public:
  66    prog_scope();
  67    prog_scope(prog_scope *parent, prog_scope_type type, int id,
  68               int depth, int begin);
  69
  70    prog_scope_type type() const;
  71    prog_scope *parent() const;
  72    int nesting_depth() const;
  73    int id() const;
  74    int end() const;
  75    int begin() const;
  76    int loop_break_line() const;
  77
  78    const prog_scope *in_else_scope() const;
  79    const prog_scope *in_ifelse_scope() const;
  80    const prog_scope *in_parent_ifelse_scope() const;
  81    const prog_scope *innermost_loop() const;
  82    const prog_scope *outermost_loop() const;
  83    const prog_scope *enclosing_conditional() const;
  84
  85    bool is_loop() const;
  86    bool is_in_loop() const;
  87    bool is_switchcase_scope_in_loop() const;
  88    bool is_conditional() const;
  89    bool is_child_of(const prog_scope *scope) const;
  90    bool is_child_of_ifelse_id_sibling(const prog_scope *scope) const;
  91
  92    bool break_is_for_switchcase() const;
  93    bool contains_range_of(const prog_scope& other) const;
  94
  95    void set_end(int end);
  96    void set_loop_break_line(int line);
  97
  98 private:
  99    prog_scope_type scope_type;
 100    int scope_id;
 101    int scope_nesting_depth;
 102    int scope_begin;
 103    int scope_end;
 104    int break_loop_line;
 105    prog_scope *parent_scope;
 106 };
 107
 108 /* Some storage class to encapsulate the prog_scope (de-)allocations */
 109 class prog_scope_storage {
 110 public:
 111    prog_scope_storage(int n);
 112    ~prog_scope_storage();
 113    prog_scope * create(prog_scope *p, prog_scope_type type, int id,
 114                        int lvl, int s_begin);
 115 private:
 116    int current_slot;
 117    std::vector<prog_scope> storage;
 118 };
 119
 120 /* Class to track the access to a component of a temporary register. */
 121
 122 class temp_comp_access {
 123 public:
 124    temp_comp_access();
 125
 126    void record_read(int line, prog_scope *scope);
 127    void record_write(int line, prog_scope *scope);
 128    register_live_range get_required_live_range();
 129 private:
 130    void propagate_live_range_to_dominant_write_scope();
 131    bool conditional_ifelse_write_in_loop() const;
 132
 133    void record_ifelse_write(const prog_scope& scope);
 134    void record_if_write(const prog_scope& scope);
 135    void record_else_write(const prog_scope& scope);
 136
 137    prog_scope *last_read_scope;
 138    prog_scope *first_read_scope;
 139    prog_scope *first_write_scope;
 140
 141    int first_write;
 142    int last_read;
 143    int last_write;
 144    int first_read;
 145
 146    /* This member variable tracks the current resolution of conditional writing
 147     * to this temporary in IF/ELSE clauses.
 148     *
 149     * The initial value "conditionality_untouched" indicates that this
 150     * temporary has not yet been written to within an if clause.
 151     *
 152     * A positive (other than "conditionality_untouched") number refers to the
 153     * last loop id for which the write was resolved as unconditional. With each
 154     * new loop this value will be overwitten by "conditionality_unresolved"
 155     * on entering the first IF clause writing this temporary.
 156     *
 157     * The value "conditionality_unresolved" indicates that no resolution has
 158     * been achieved so far. If the variable is set to this value at the end of
 159     * the processing of the whole shader it also indicates a conditional write.
 160     *
 161     * The value "write_is_conditional" marks that the variable is written
 162     * conditionally (i.e. not in all relevant IF/ELSE code path pairs) in at
 163     * least one loop.
 164     */
 165    int conditionality_in_loop_id;
 166
 167    /* Helper constants to make the tracking code more readable. */
 168    static const int write_is_conditional = -1;
 169    static const int conditionality_unresolved = 0;
 170    static const int conditionality_untouched;
 171    static const int write_is_unconditional;
 172
 173    /* A bit field tracking the nexting levels of if-else clauses where the
 174     * temporary has (so far) been written to in the if branch, but not in the
 175     * else branch.
 176     */
 177    unsigned int if_scope_write_flags;
 178
 179    int next_ifelse_nesting_depth;
 180    static const int supported_ifelse_nesting_depth = 32;
 181
 182    /* Tracks the last if scope in which the temporary was written to
 183     * without a write in the correspondig else branch. Is also used
 184     * to track read-before-write in the according scope.
 185     */
 186    const prog_scope *current_unpaired_if_write_scope;
 187
 188    /* Flag to resolve read-before-write in the else scope. */
 189    bool was_written_in_current_else_scope;
 190 };
 191
 192 /* Class to track the access to all components of a temporary register. */
 193 class temp_access {
 194 public:
 195    temp_access();
 196    void record_read(int line, prog_scope *scope, int swizzle, bool is_array_elm);
 197    void record_write(int line, prog_scope *scope, int writemask, bool is_array_elm);
 198    register_live_range get_required_live_range();
 199 private:
 200    void update_access_mask(int mask);
 201
 202    temp_comp_access comp[4];
 203    int access_mask;
 204    bool needs_component_tracking;
 205    bool is_array_element;
 206 };
 207
 208 /* Helper class to merge the live ranges of an arrays.
 209  *
 210  * For arrays the array length, live range, and component access needs to
 211  * be kept, because when live ranges are merged or arrays are interleaved
 212  * one can only merge or interleave an array into another with equal or more
 213  * elements. For interleaving it is also required that the sum of used swizzles
 214  * is at most four.
 215  */
 216
 217 class array_live_range {
 218 public:
 219    array_live_range();
 220    array_live_range(unsigned aid, unsigned alength);
 221    array_live_range(unsigned aid, unsigned alength, int first_access,
 222                   int last_access, int mask);
 223
 224    void set_live_range(int first_access, int last_access);
 225    void set_begin(int _begin){first_access = _begin;}
 226    void set_end(int _end){last_access = _end;}
 227    void set_access_mask(int s);
 228
 229    static void merge(array_live_range *a, array_live_range *b);
 230    static void interleave(array_live_range *a, array_live_range *b);
 231
 232    int array_id() const {return id;}
 233    int target_array_id() const {return target_array ? target_array->id : 0;}
 234    const array_live_range *final_target() const {return target_array ?
 235                target_array->final_target() : this;}
 236    unsigned array_length() const { return length;}
 237    int begin() const { return first_access;}
 238    int end() const { return last_access;}
 239    int access_mask() const { return component_access_mask;}
 240    int used_components() const {return used_component_count;}
 241
 242    bool time_doesnt_overlap(const array_live_range& other) const;
 243
 244    void print(std::ostream& os) const;
 245
 246    bool is_mapped() const { return target_array != nullptr;}
 247
 248    int8_t remap_one_swizzle(int8_t idx) const;
 249
 250 private:
 251    void init_swizzles();
 252    void set_target(array_live_range  *target);
 253    void merge_live_range_from(array_live_range *other);
 254    void interleave_into(array_live_range *other);
 255
 256    unsigned id;
 257    unsigned length;
 258    int first_access;
 259    int last_access;
 260    uint8_t component_access_mask;
 261    uint8_t used_component_count;
 262    array_live_range *target_array;
 263    int8_t swizzle_map[4];
 264 };
 265
 266
 267
 268 class LiverangeEvaluator {
 269 public:
 270    LiverangeEvaluator();
 271
 272    void run(const Shader& shader,
 273             std::vector<register_live_range> &register_live_ranges);
 274
 275    void scope_if();
 276    void scope_else();
 277    void scope_endif();
 278    void scope_loop_begin();
 279    void scope_loop_end();
 280    void scope_loop_break();
 281
 282    void record_read(const Value& src, bool is_array_elm = false);
 283    void record_write(const Value& dst, bool is_array_elm = false);
 284
 285    void record_read(const GPRVector& src);
 286    void record_write(const GPRVector& dst);
 287
 288 private:
 289
 290    prog_scope *create_scope(prog_scope *parent, prog_scope_type type, int id,
 291                             int lvl, int s_begin);
 292
 293
 294    void get_required_live_ranges(std::vector<register_live_range>& register_live_ranges);
 295
 296    int line;
 297    int loop_id;
 298    int if_id;
 299    int switch_id;
 300    bool is_at_end;
 301    int n_scopes;
 302    std::unique_ptr<prog_scope_storage> scopes;
 303    prog_scope *cur_scope;
 304
 305    std::vector<temp_access> temp_acc;
 306
 307 };
 308
 309 std::vector<rename_reg_pair>
 310 get_temp_registers_remapping(const std::vector<register_live_range>& live_ranges);
 311
 312 } // end namespace r600
 313
 314 #endif