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);
set_begin(int _begin)225    void set_begin(int _begin){first_access = _begin;}
set_end(int _end)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 
array_id()232    int array_id() const {return id;}
target_array_id()233    int target_array_id() const {return target_array ? target_array->id : 0;}
final_target()234    const array_live_range *final_target() const {return target_array ?
235 	       target_array->final_target() : this;}
array_length()236    unsigned array_length() const { return length;}
begin()237    int begin() const { return first_access;}
end()238    int end() const { return last_access;}
access_mask()239    int access_mask() const { return component_access_mask;}
used_components()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 
is_mapped()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
315