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> ®ister_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