/**
* Fill in loop control fields
*
- * Based on analysis of loop variables, this function tries to remove sequences
- * in the loop of the form
+ * Based on analysis of loop variables, this function tries to remove
+ * redundant sequences in the loop of the form
*
* (if (expression bool ...) (break))
*
- * and fill in the \c ir_loop::from, \c ir_loop::to, and \c ir_loop::counter
- * fields of the \c ir_loop.
- *
- * In this process, some conditional break-statements may be eliminated
- * altogether. For example, if it is provable that one loop exit condition will
+ * For example, if it is provable that one loop exit condition will
* always be satisfied before another, the unnecessary exit condition will be
* removed.
*/
extern bool
unroll_loops(exec_list *instructions, loop_state *ls, unsigned max_iterations);
+ir_rvalue *
+find_initial_value(ir_loop *loop, ir_variable *var);
+
+int
+calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
+ enum ir_expression_operation op);
+
/**
* Tracking for all variables used in a loop
public:
class loop_variable *get(const ir_variable *);
class loop_variable *insert(ir_variable *);
+ class loop_variable *get_or_insert(ir_variable *, bool in_assignee);
class loop_terminator *insert(ir_if *);
- /**
- * Loop whose variable state is being tracked by this structure
- */
- ir_loop *loop;
-
/**
* Variables that have not yet been classified
*/
exec_list terminators;
/**
- * Hash table containing all variables accessed in this loop
+ * If any of the terminators in \c terminators leads to termination of the
+ * loop after a constant number of iterations, this is the terminator that
+ * leads to termination after the smallest number of iterations. Otherwise
+ * NULL.
*/
- hash_table *var_hash;
+ loop_terminator *limiting_terminator;
/**
- * Maximum number of loop iterations.
- *
- * If this value is negative, then the loop may be infinite. This actually
- * means that analysis was unable to determine an upper bound on the number
- * of loop iterations.
+ * Hash table containing all variables accessed in this loop
*/
- int max_iterations;
+ hash_table *var_hash;
/**
* Number of ir_loop_jump instructions that operate on this loop
*/
unsigned num_loop_jumps;
+ /**
+ * Whether this loop contains any function calls.
+ */
+ bool contains_calls;
+
loop_variable_state()
{
- this->max_iterations = -1;
this->num_loop_jumps = 0;
+ this->contains_calls = false;
this->var_hash = hash_table_ctor(0, hash_table_pointer_hash,
hash_table_pointer_compare);
+ this->limiting_terminator = NULL;
}
~loop_variable_state()
{
hash_table_dtor(this->var_hash);
}
+
+ static void* operator new(size_t size, void *ctx)
+ {
+ void *lvs = ralloc_size(ctx, size);
+ assert(lvs != NULL);
+
+ ralloc_set_destructor(lvs, (void (*)(void*)) destructor);
+
+ return lvs;
+ }
+
+private:
+ static void
+ destructor(loop_variable_state *lvs)
+ {
+ lvs->~loop_variable_state();
+ }
};
/** Are all variables in the RHS of the assignment loop constants? */
bool rhs_clean;
- /** Is there an assignment to the variable that is conditional? */
- bool conditional_assignment;
+ /**
+ * Is there an assignment to the variable that is conditional, or inside a
+ * nested loop?
+ */
+ bool conditional_or_nested_assignment;
/** Reference to the first assignment to the variable in the loop body. */
ir_assignment *first_assignment;
unsigned num_assignments;
/**
- * Increment values for loop induction variables
+ * Increment value for a loop induction variable
*
- * Loop induction variables have a single increment of the form
- * \c b * \c biv + \c c, where \c b and \c c are loop constants and \c i
- * is a basic loop induction variable.
+ * If this is a loop induction variable, the amount by which the variable
+ * is incremented on each iteration through the loop.
*
- * If \c iv_scale is \c NULL, 1 is used. If \c biv is the same as \c var,
- * then \c var is a basic loop induction variable.
+ * If this is not a loop induction variable, NULL.
*/
- /*@{*/
- ir_rvalue *iv_scale;
- ir_variable *biv;
ir_rvalue *increment;
- /*@}*/
+
+
+ inline bool is_induction_var() const
+ {
+ /* Induction variables always have a non-null increment, and vice
+ * versa.
+ */
+ return this->increment != NULL;
+ }
inline bool is_loop_constant() const
{
const bool is_const = (this->num_assignments == 0)
|| ((this->num_assignments == 1)
- && !this->conditional_assignment
+ && !this->conditional_or_nested_assignment
&& !this->read_before_write
&& this->rhs_clean);
/* Variables that are marked read-only *MUST* be loop constant.
*/
- assert(!this->var->read_only || (this->var->read_only && is_const));
+ assert(!this->var->data.read_only
+ || (this->var->data.read_only && is_const));
return is_const;
}
+
+ void record_reference(bool in_assignee,
+ bool in_conditional_code_or_nested_loop,
+ ir_assignment *current_assignment);
};
class loop_terminator : public exec_node {
public:
+ loop_terminator()
+ : ir(NULL), iterations(-1)
+ {
+ }
+
+ /**
+ * Statement which terminates the loop.
+ */
ir_if *ir;
+
+ /**
+ * The number of iterations after which the terminator is known to
+ * terminate the loop (if that is a fixed value). Otherwise -1.
+ */
+ int iterations;
};
loop_variable_state *insert(ir_loop *ir);
+ bool loop_found;
+
private:
loop_state();
void *mem_ctx;
- friend class loop_analysis;
+ friend loop_state *analyze_loop_variables(exec_list *instructions);
};
#endif /* LOOP_ANALYSIS_H */
projects / mesa.git / blobdiff