1 /* -*- c++ -*- */ 2 /* 3 * Copyright © 2010 Intel Corporation 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the next 13 * paragraph) shall be included in all copies or substantial portions of the 14 * Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 22 * DEALINGS IN THE SOFTWARE. 23 */ 24 25 #pragma once 26 #ifndef LOOP_ANALYSIS_H 27 #define LOOP_ANALYSIS_H 28 29 #include "ir.h" 30 #include "glsl_types.h" 31 #include "program/hash_table.h" 32 33 /** 34 * Analyze and classify all variables used in all loops in the instruction list 35 */ 36 extern class loop_state * 37 analyze_loop_variables(exec_list *instructions); 38 39 40 /** 41 * Fill in loop control fields 42 * 43 * Based on analysis of loop variables, this function tries to remove 44 * redundant sequences in the loop of the form 45 * 46 * (if (expression bool ...) (break)) 47 * 48 * For example, if it is provable that one loop exit condition will 49 * always be satisfied before another, the unnecessary exit condition will be 50 * removed. 51 */ 52 extern bool 53 set_loop_controls(exec_list *instructions, loop_state *ls); 54 55 56 extern bool 57 unroll_loops(exec_list *instructions, loop_state *ls, 58 const struct gl_shader_compiler_options *options); 59 60 ir_rvalue * 61 find_initial_value(ir_loop *loop, ir_variable *var, ir_instruction **out_containing_ir); 62 63 int 64 calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment, 65 enum ir_expression_operation op); 66 67 68 /** 69 * Tracking for all variables used in a loop 70 */ 71 class loop_variable_state : public exec_node { 72 public: 73 class loop_variable *get(const ir_variable *); 74 class loop_variable *insert(ir_variable *); 75 class loop_variable *get_or_insert(ir_variable *, bool in_assignee); 76 class loop_terminator *insert(ir_if *); 77 78 79 /** 80 * Variables that have not yet been classified 81 */ 82 exec_list variables; 83 84 /** 85 * Variables whose values are constant within the body of the loop 86 * 87 * This list contains \c loop_variable objects. 88 */ 89 exec_list constants; 90 91 /** 92 * Induction variables for this loop 93 * 94 * This list contains \c loop_variable objects. 95 */ 96 exec_list induction_variables; 97 int private_induction_variable_count; 98 99 /** 100 * Simple if-statements that lead to the termination of the loop 101 * 102 * This list contains \c loop_terminator objects. 103 * 104 * \sa is_loop_terminator 105 */ 106 exec_list terminators; 107 108 /** 109 * If any of the terminators in \c terminators leads to termination of the 110 * loop after a constant number of iterations, this is the terminator that 111 * leads to termination after the smallest number of iterations. Otherwise 112 * NULL. 113 */ 114 loop_terminator *limiting_terminator; 115 116 /** 117 * Hash table containing all variables accessed in this loop 118 */ 119 hash_table *var_hash; 120 121 /** 122 * Number of ir_loop_jump instructions that operate on this loop 123 */ 124 unsigned num_loop_jumps; 125 126 /** 127 * Whether this loop contains any function calls. 128 */ 129 bool contains_calls; 130 loop_variable_state()131 loop_variable_state() 132 { 133 this->num_loop_jumps = 0; 134 this->contains_calls = false; 135 this->var_hash = hash_table_ctor(0, hash_table_pointer_hash, 136 hash_table_pointer_compare); 137 this->limiting_terminator = NULL; 138 } 139 ~loop_variable_state()140 ~loop_variable_state() 141 { 142 hash_table_dtor(this->var_hash); 143 } 144 145 DECLARE_RALLOC_CXX_OPERATORS(loop_variable_state) 146 }; 147 148 149 class loop_variable : public exec_node { 150 public: 151 /** The variable in question. */ 152 ir_variable *var; 153 154 /** Is the variable read in the loop before it is written? */ 155 bool read_before_write; 156 157 /** Are all variables in the RHS of the assignment loop constants? */ 158 bool rhs_clean; 159 160 /** 161 * Is there an assignment to the variable that is conditional, or inside a 162 * nested loop? 163 */ 164 bool conditional_or_nested_assignment; 165 166 /** Reference to the first assignment to the variable in the loop body. */ 167 ir_assignment *first_assignment; 168 169 /** Reference to initial value outside of the loop. */ 170 ir_rvalue *initial_value; 171 /** IR that assigned the initial value. */ 172 ir_instruction *initial_value_ir; 173 174 /** Number of assignments to the variable in the loop body. */ 175 unsigned num_assignments; 176 177 /** 178 * Increment value for a loop induction variable 179 * 180 * If this is a loop induction variable, the amount by which the variable 181 * is incremented on each iteration through the loop. 182 * 183 * If this is not a loop induction variable, NULL. 184 */ 185 ir_rvalue *increment; 186 187 is_induction_var()188 inline bool is_induction_var() const 189 { 190 /* Induction variables always have a non-null increment, and vice 191 * versa. 192 */ 193 return this->increment != NULL; 194 } 195 196 is_loop_constant()197 inline bool is_loop_constant() const 198 { 199 const bool is_const = (this->num_assignments == 0) 200 || (((this->num_assignments == 1) 201 && !this->conditional_or_nested_assignment 202 && !this->read_before_write 203 && this->rhs_clean) || this->var->data.read_only); 204 205 /* If the RHS of *the* assignment is clean, then there must be exactly 206 * one assignment of the variable. 207 */ 208 assert((this->rhs_clean && (this->num_assignments == 1)) 209 || !this->rhs_clean); 210 211 return is_const; 212 } 213 214 void record_reference(bool in_assignee, 215 bool in_conditional_code_or_nested_loop, 216 ir_assignment *current_assignment); 217 }; 218 219 220 class loop_terminator : public exec_node { 221 public: loop_terminator()222 loop_terminator() 223 : ir(NULL), iterations(-1) 224 { 225 } 226 227 /** 228 * Statement which terminates the loop. 229 */ 230 ir_if *ir; 231 232 /** 233 * The number of iterations after which the terminator is known to 234 * terminate the loop (if that is a fixed value). Otherwise -1. 235 */ 236 int iterations; 237 }; 238 239 240 class loop_state { 241 public: 242 ~loop_state(); 243 244 /** 245 * Get the loop variable state data for a particular loop 246 */ 247 loop_variable_state *get(const ir_loop *); 248 249 loop_variable_state *insert(ir_loop *ir); 250 251 loop_variable_state* get_for_inductor (const ir_variable*); 252 bool insert_inductor(loop_variable* loopvar, loop_variable_state* state, ir_loop* loop); 253 void insert_non_inductor(ir_variable *var); 254 void insert_variable(ir_variable *var); 255 void reference_variable(ir_variable *var, bool assignment); 256 257 bool loop_found; 258 259 private: 260 loop_state(); 261 262 /** 263 * Hash table containing all loops that have been analyzed. 264 */ 265 hash_table *ht; 266 267 /** 268 * Hash table from ir_variables to loop state, for induction variables. 269 */ 270 hash_table *ht_inductors; 271 hash_table *ht_non_inductors; 272 hash_table *ht_variables; 273 274 275 void *mem_ctx; 276 277 friend loop_state *analyze_loop_variables(exec_list *instructions); 278 }; 279 280 #endif /* LOOP_ANALYSIS_H */ 281