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
38namespace 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 */
47struct register_live_range {
48   int begin;
49   int end;
50   bool is_array_elm;
51};
52
53enum 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 statement */
59   switch_case_branch,    /* Inside switch case statement */
60   switch_default_branch, /* Inside switch default statement */
61   undefined_scope
62};
63
64class prog_scope {
65public:
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
98private:
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 */
109class prog_scope_storage {
110public:
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);
115private:
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
122class temp_comp_access {
123public:
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();
129private:
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 corresponding 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. */
193class temp_access {
194public:
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();
199private:
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
217class array_live_range {
218public:
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
250private:
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
268class LiverangeEvaluator {
269public:
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
288private:
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
309std::vector<rename_reg_pair>
310get_temp_registers_remapping(const std::vector<register_live_range>& live_ranges);
311
312} // end namespace r600
313
314#endif
315