src/compiler/glsl/loop_analysis.cpp - third_party/mesa - Git at Google

 /*
  * Copyright © 2010 Intel Corporation
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
  * to deal in the Software without restriction, including without limitation
  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  * and/or sell copies of the Software, and to permit persons to whom the
  * Software is furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice (including the next
  * paragraph) shall be included in all copies or substantial portions of the
  * Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  * DEALINGS IN THE SOFTWARE.
  */

 #include "compiler/glsl_types.h"
 #include "loop_analysis.h"
 #include "ir_hierarchical_visitor.h"

 static void try_add_loop_terminator(loop_variable_state *ls, ir_if *ir);

 static bool all_expression_operands_are_loop_constant(ir_rvalue *,
 						      hash_table *);

 static ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *);

 /**
  * Find an initializer of a variable outside a loop
  *
  * Works backwards from the loop to find the pre-loop value of the variable.
  * This is used, for example, to find the initial value of loop induction
  * variables.
  *
  * \param loop  Loop where \c var is an induction variable
  * \param var   Variable whose initializer is to be found
  *
  * \return
  * The \c ir_rvalue assigned to the variable outside the loop.  May return
  * \c NULL if no initializer can be found.
  */
 static ir_rvalue *
 find_initial_value(ir_loop *loop, ir_variable *var)
 {
    for (exec_node *node = loop->prev; !node->is_head_sentinel();
         node = node->prev) {
       ir_instruction *ir = (ir_instruction *) node;

       switch (ir->ir_type) {
       case ir_type_call:
       case ir_type_loop:
       case ir_type_loop_jump:
       case ir_type_return:
       case ir_type_if:
          return NULL;

       case ir_type_function:
       case ir_type_function_signature:
          assert(!"Should not get here.");
          return NULL;

       case ir_type_assignment: {
          ir_assignment *assign = ir->as_assignment();
          ir_variable *assignee = assign->lhs->whole_variable_referenced();

          if (assignee == var)
             return (assign->condition != NULL) ? NULL : assign->rhs;

          break;
       }

       default:
          break;
       }
    }

    return NULL;
 }


 static int
 calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
                      enum ir_expression_operation op, bool continue_from_then,
                      bool swap_compare_operands)
 {
    if (from == NULL || to == NULL || increment == NULL)
       return -1;

    void *mem_ctx = ralloc_context(NULL);

    ir_expression *const sub =
       new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from);

    ir_expression *const div =
       new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment);

    ir_constant *iter = div->constant_expression_value(mem_ctx);
    if (iter == NULL) {
       ralloc_free(mem_ctx);
       return -1;
    }

    if (!iter->type->is_integer()) {
       const ir_expression_operation op = iter->type->is_double()
          ? ir_unop_d2i : ir_unop_f2i;
       ir_rvalue *cast =
          new(mem_ctx) ir_expression(op, glsl_type::int_type, iter, NULL);

       iter = cast->constant_expression_value(mem_ctx);
    }

    int iter_value = iter->get_int_component(0);

    /* Make sure that the calculated number of iterations satisfies the exit
     * condition.  This is needed to catch off-by-one errors and some types of
     * ill-formed loops.  For example, we need to detect that the following
     * loop does not have a maximum iteration count.
     *
     *    for (float x = 0.0; x != 0.9; x += 0.2)
     *        ;
     */
    const int bias[] = { -1, 0, 1 };
    bool valid_loop = false;

    for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) {
       /* Increment may be of type int, uint or float. */
       switch (increment->type->base_type) {
       case GLSL_TYPE_INT:
          iter = new(mem_ctx) ir_constant(iter_value + bias[i]);
          break;
       case GLSL_TYPE_UINT:
          iter = new(mem_ctx) ir_constant(unsigned(iter_value + bias[i]));
          break;
       case GLSL_TYPE_FLOAT:
          iter = new(mem_ctx) ir_constant(float(iter_value + bias[i]));
          break;
       case GLSL_TYPE_DOUBLE:
          iter = new(mem_ctx) ir_constant(double(iter_value + bias[i]));
          break;
       default:
           unreachable("Unsupported type for loop iterator.");
       }

       ir_expression *const mul =
          new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter,
                                     increment);

       ir_expression *const add =
          new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from);

       ir_expression *cmp = swap_compare_operands
          ? new(mem_ctx) ir_expression(op, glsl_type::bool_type, to, add)
          : new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to);
       if (continue_from_then)
          cmp = new(mem_ctx) ir_expression(ir_unop_logic_not, cmp);

       ir_constant *const cmp_result = cmp->constant_expression_value(mem_ctx);

       assert(cmp_result != NULL);
       if (cmp_result->get_bool_component(0)) {
          iter_value += bias[i];
          valid_loop = true;
          break;
       }
    }

    ralloc_free(mem_ctx);
    return (valid_loop) ? iter_value : -1;
 }

 static bool
 incremented_before_terminator(ir_loop *loop, ir_variable *var,
                               ir_if *terminator)
 {
    for (exec_node *node = loop->body_instructions.get_head();
         !node->is_tail_sentinel();
         node = node->get_next()) {
       ir_instruction *ir = (ir_instruction *) node;

       switch (ir->ir_type) {
       case ir_type_if:
          if (ir->as_if() == terminator)
             return false;
          break;

       case ir_type_assignment: {
          ir_assignment *assign = ir->as_assignment();
          ir_variable *assignee = assign->lhs->whole_variable_referenced();

          if (assignee == var) {
             assert(assign->condition == NULL);
             return true;
          }

          break;
       }

       default:
          break;
       }
    }

    unreachable("Unable to find induction variable");
 }

 /**
  * Record the fact that the given loop variable was referenced inside the loop.
  *
  * \arg in_assignee is true if the reference was on the LHS of an assignment.
  *
  * \arg in_conditional_code_or_nested_loop is true if the reference occurred
  * inside an if statement or a nested loop.
  *
  * \arg current_assignment is the ir_assignment node that the loop variable is
  * on the LHS of, if any (ignored if \c in_assignee is false).
  */
 void
 loop_variable::record_reference(bool in_assignee,
                                 bool in_conditional_code_or_nested_loop,
                                 ir_assignment *current_assignment)
 {
    if (in_assignee) {
       assert(current_assignment != NULL);

       if (in_conditional_code_or_nested_loop ||
           current_assignment->condition != NULL) {
          this->conditional_or_nested_assignment = true;
       }

       if (this->first_assignment == NULL) {
          assert(this->num_assignments == 0);

          this->first_assignment = current_assignment;
       }

       this->num_assignments++;
    } else if (this->first_assignment == current_assignment) {
       /* This catches the case where the variable is used in the RHS of an
        * assignment where it is also in the LHS.
        */
       this->read_before_write = true;
    }
 }


 loop_state::loop_state()
 {
    this->ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
                                       _mesa_key_pointer_equal);
    this->mem_ctx = ralloc_context(NULL);
    this->loop_found = false;
 }


 loop_state::~loop_state()
 {
    _mesa_hash_table_destroy(this->ht, NULL);
    ralloc_free(this->mem_ctx);
 }


 loop_variable_state *
 loop_state::insert(ir_loop *ir)
 {
    loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;

    _mesa_hash_table_insert(this->ht, ir, ls);
    this->loop_found = true;

    return ls;
 }


 loop_variable_state *
 loop_state::get(const ir_loop *ir)
 {
    hash_entry *entry = _mesa_hash_table_search(this->ht, ir);
    return entry ? (loop_variable_state *) entry->data : NULL;
 }


 loop_variable *
 loop_variable_state::get(const ir_variable *ir)
 {
    hash_entry *entry = _mesa_hash_table_search(this->var_hash, ir);
    return entry ? (loop_variable *) entry->data : NULL;
 }


 loop_variable *
 loop_variable_state::insert(ir_variable *var)
 {
    void *mem_ctx = ralloc_parent(this);
    loop_variable *lv = rzalloc(mem_ctx, loop_variable);

    lv->var = var;

    _mesa_hash_table_insert(this->var_hash, lv->var, lv);
    this->variables.push_tail(lv);

    return lv;
 }


 loop_terminator *
 loop_variable_state::insert(ir_if *if_stmt, bool continue_from_then)
 {
    void *mem_ctx = ralloc_parent(this);
    loop_terminator *t = new(mem_ctx) loop_terminator();

    t->ir = if_stmt;
    t->continue_from_then = continue_from_then;

    this->terminators.push_tail(t);

    return t;
 }


 /**
  * If the given variable already is recorded in the state for this loop,
  * return the corresponding loop_variable object that records information
  * about it.
  *
  * Otherwise, create a new loop_variable object to record information about
  * the variable, and set its \c read_before_write field appropriately based on
  * \c in_assignee.
  *
  * \arg in_assignee is true if this variable was encountered on the LHS of an
  * assignment.
  */
 loop_variable *
 loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee)
 {
    loop_variable *lv = this->get(var);

    if (lv == NULL) {
       lv = this->insert(var);
       lv->read_before_write = !in_assignee;
    }

    return lv;
 }


 namespace {

 class loop_analysis : public ir_hierarchical_visitor {
 public:
    loop_analysis(loop_state *loops);

    virtual ir_visitor_status visit(ir_loop_jump *);
    virtual ir_visitor_status visit(ir_dereference_variable *);

    virtual ir_visitor_status visit_enter(ir_call *);

    virtual ir_visitor_status visit_enter(ir_loop *);
    virtual ir_visitor_status visit_leave(ir_loop *);
    virtual ir_visitor_status visit_enter(ir_assignment *);
    virtual ir_visitor_status visit_leave(ir_assignment *);
    virtual ir_visitor_status visit_enter(ir_if *);
    virtual ir_visitor_status visit_leave(ir_if *);

    loop_state *loops;

    int if_statement_depth;

    ir_assignment *current_assignment;

    exec_list state;
 };

 } /* anonymous namespace */

 loop_analysis::loop_analysis(loop_state *loops)
    : loops(loops), if_statement_depth(0), current_assignment(NULL)
 {
    /* empty */
 }


 ir_visitor_status
 loop_analysis::visit(ir_loop_jump *ir)
 {
    (void) ir;

    assert(!this->state.is_empty());

    loop_variable_state *const ls =
       (loop_variable_state *) this->state.get_head();

    ls->num_loop_jumps++;

    return visit_continue;
 }


 ir_visitor_status
 loop_analysis::visit_enter(ir_call *)
 {
    /* Mark every loop that we're currently analyzing as containing an ir_call
     * (even those at outer nesting levels).
     */
    foreach_in_list(loop_variable_state, ls, &this->state) {
       ls->contains_calls = true;
    }

    return visit_continue_with_parent;
 }


 ir_visitor_status
 loop_analysis::visit(ir_dereference_variable *ir)
 {
    /* If we're not somewhere inside a loop, there's nothing to do.
     */
    if (this->state.is_empty())
       return visit_continue;

    bool nested = false;

    foreach_in_list(loop_variable_state, ls, &this->state) {
       ir_variable *var = ir->variable_referenced();
       loop_variable *lv = ls->get_or_insert(var, this->in_assignee);

       lv->record_reference(this->in_assignee,
                            nested || this->if_statement_depth > 0,
                            this->current_assignment);
       nested = true;
    }

    return visit_continue;
 }

 ir_visitor_status
 loop_analysis::visit_enter(ir_loop *ir)
 {
    loop_variable_state *ls = this->loops->insert(ir);
    this->state.push_head(ls);

    return visit_continue;
 }

 ir_visitor_status
 loop_analysis::visit_leave(ir_loop *ir)
 {
    loop_variable_state *const ls =
       (loop_variable_state *) this->state.pop_head();

    /* Function calls may contain side effects.  These could alter any of our
     * variables in ways that cannot be known, and may even terminate shader
     * execution (say, calling discard in the fragment shader).  So we can't
     * rely on any of our analysis about assignments to variables.
     *
     * We could perform some conservative analysis (prove there's no statically
     * possible assignment, etc.) but it isn't worth it for now; function
     * inlining will allow us to unroll loops anyway.
     */
    if (ls->contains_calls)
       return visit_continue;

    foreach_in_list(ir_instruction, node, &ir->body_instructions) {
       /* Skip over declarations at the start of a loop.
        */
       if (node->as_variable())
 	 continue;

       ir_if *if_stmt = ((ir_instruction *) node)->as_if();

       if (if_stmt != NULL)
          try_add_loop_terminator(ls, if_stmt);
    }


    foreach_in_list_safe(loop_variable, lv, &ls->variables) {
       /* Move variables that are already marked as being loop constant to
        * a separate list.  These trivially don't need to be tested.
        */
       if (lv->is_loop_constant()) {
 	 lv->remove();
 	 ls->constants.push_tail(lv);
       }
    }

    /* Each variable assigned in the loop that isn't already marked as being loop
     * constant might still be loop constant.  The requirements at this point
     * are:
     *
     *    - Variable is written before it is read.
     *
     *    - Only one assignment to the variable.
     *
     *    - All operands on the RHS of the assignment are also loop constants.
     *
     * The last requirement is the reason for the progress loop.  A variable
     * marked as a loop constant on one pass may allow other variables to be
     * marked as loop constant on following passes.
     */
    bool progress;
    do {
       progress = false;

       foreach_in_list_safe(loop_variable, lv, &ls->variables) {
 	 if (lv->conditional_or_nested_assignment || (lv->num_assignments > 1))
 	    continue;

 	 /* Process the RHS of the assignment.  If all of the variables
 	  * accessed there are loop constants, then add this
 	  */
 	 ir_rvalue *const rhs = lv->first_assignment->rhs;
 	 if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) {
 	    lv->rhs_clean = true;

 	    if (lv->is_loop_constant()) {
 	       progress = true;

 	       lv->remove();
 	       ls->constants.push_tail(lv);
 	    }
 	 }
       }
    } while (progress);

    /* The remaining variables that are not loop invariant might be loop
     * induction variables.
     */
    foreach_in_list_safe(loop_variable, lv, &ls->variables) {
       /* If there is more than one assignment to a variable, it cannot be a
        * loop induction variable.  This isn't strictly true, but this is a
        * very simple induction variable detector, and it can't handle more
        * complex cases.
        */
       if (lv->num_assignments > 1)
 	 continue;

       /* All of the variables with zero assignments in the loop are loop
        * invariant, and they should have already been filtered out.
        */
       assert(lv->num_assignments == 1);
       assert(lv->first_assignment != NULL);

       /* The assignment to the variable in the loop must be unconditional and
        * not inside a nested loop.
        */
       if (lv->conditional_or_nested_assignment)
 	 continue;

       /* Basic loop induction variables have a single assignment in the loop
        * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
        * loop invariant.
        */
       ir_rvalue *const inc =
 	 get_basic_induction_increment(lv->first_assignment, ls->var_hash);
       if (inc != NULL) {
 	 lv->increment = inc;

 	 lv->remove();
 	 ls->induction_variables.push_tail(lv);
       }
    }

    /* Search the loop terminating conditions for those of the form 'i < c'
     * where i is a loop induction variable, c is a constant, and < is any
     * relative operator.  From each of these we can infer an iteration count.
     * Also figure out which terminator (if any) produces the smallest
     * iteration count--this is the limiting terminator.
     */
    foreach_in_list(loop_terminator, t, &ls->terminators) {
       ir_if *if_stmt = t->ir;

       /* If-statements can be either 'if (expr)' or 'if (deref)'.  We only care
        * about the former here.
        */
       ir_expression *cond = if_stmt->condition->as_expression();
       if (cond == NULL)
 	 continue;

       switch (cond->operation) {
       case ir_binop_less:
       case ir_binop_gequal: {
 	 /* The expressions that we care about will either be of the form
 	  * 'counter < limit' or 'limit < counter'.  Figure out which is
 	  * which.
 	  */
 	 ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
 	 ir_constant *limit = cond->operands[1]->as_constant();
 	 enum ir_expression_operation cmp = cond->operation;
          bool swap_compare_operands = false;

 	 if (limit == NULL) {
 	    counter = cond->operands[1]->as_dereference_variable();
 	    limit = cond->operands[0]->as_constant();
             swap_compare_operands = true;
 	 }

 	 if ((counter == NULL) || (limit == NULL))
 	    break;

 	 ir_variable *var = counter->variable_referenced();

 	 ir_rvalue *init = find_initial_value(ir, var);

          loop_variable *lv = ls->get(var);
          if (lv != NULL && lv->is_induction_var()) {
             t->iterations = calculate_iterations(init, limit, lv->increment,
                                                  cmp, t->continue_from_then,
                                                  swap_compare_operands);

             if (incremented_before_terminator(ir, var, t->ir)) {
                t->iterations--;
             }

             if (t->iterations >= 0 &&
                 (ls->limiting_terminator == NULL ||
                  t->iterations < ls->limiting_terminator->iterations)) {
                ls->limiting_terminator = t;
             }
          }
          break;
       }

       default:
          break;
       }
    }

    return visit_continue;
 }

 ir_visitor_status
 loop_analysis::visit_enter(ir_if *ir)
 {
    (void) ir;

    if (!this->state.is_empty())
       this->if_statement_depth++;

    return visit_continue;
 }

 ir_visitor_status
 loop_analysis::visit_leave(ir_if *ir)
 {
    (void) ir;

    if (!this->state.is_empty())
       this->if_statement_depth--;

    return visit_continue;
 }

 ir_visitor_status
 loop_analysis::visit_enter(ir_assignment *ir)
 {
    /* If we're not somewhere inside a loop, there's nothing to do.
     */
    if (this->state.is_empty())
       return visit_continue_with_parent;

    this->current_assignment = ir;

    return visit_continue;
 }

 ir_visitor_status
 loop_analysis::visit_leave(ir_assignment *ir)
 {
    /* Since the visit_enter exits with visit_continue_with_parent for this
     * case, the loop state stack should never be empty here.
     */
    assert(!this->state.is_empty());

    assert(this->current_assignment == ir);
    this->current_assignment = NULL;

    return visit_continue;
 }


 class examine_rhs : public ir_hierarchical_visitor {
 public:
    examine_rhs(hash_table *loop_variables)
    {
       this->only_uses_loop_constants = true;
       this->loop_variables = loop_variables;
    }

    virtual ir_visitor_status visit(ir_dereference_variable *ir)
    {
       hash_entry *entry = _mesa_hash_table_search(this->loop_variables,
                                                   ir->var);
       loop_variable *lv = entry ? (loop_variable *) entry->data : NULL;

       assert(lv != NULL);

       if (lv->is_loop_constant()) {
 	 return visit_continue;
       } else {
 	 this->only_uses_loop_constants = false;
 	 return visit_stop;
       }
    }

    hash_table *loop_variables;
    bool only_uses_loop_constants;
 };


 bool
 all_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables)
 {
    examine_rhs v(variables);

    ir->accept(&v);

    return v.only_uses_loop_constants;
 }


 ir_rvalue *
 get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
 {
    /* The RHS must be a binary expression.
     */
    ir_expression *const rhs = ir->rhs->as_expression();
    if ((rhs == NULL)
        || ((rhs->operation != ir_binop_add)
 	   && (rhs->operation != ir_binop_sub)))
       return NULL;

    /* One of the of operands of the expression must be the variable assigned.
     * If the operation is subtraction, the variable in question must be the
     * "left" operand.
     */
    ir_variable *const var = ir->lhs->variable_referenced();

    ir_variable *const op0 = rhs->operands[0]->variable_referenced();
    ir_variable *const op1 = rhs->operands[1]->variable_referenced();

    if (((op0 != var) && (op1 != var))
        || ((op1 == var) && (rhs->operation == ir_binop_sub)))
       return NULL;

    ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];

    if (inc->as_constant() == NULL) {
       ir_variable *const inc_var = inc->variable_referenced();
       if (inc_var != NULL) {
          hash_entry *entry = _mesa_hash_table_search(var_hash, inc_var);
          loop_variable *lv = entry ? (loop_variable *) entry->data : NULL;

          if (lv == NULL || !lv->is_loop_constant()) {
             assert(lv != NULL);
             inc = NULL;
          }
       } else
 	 inc = NULL;
    }

    if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
       void *mem_ctx = ralloc_parent(ir);

       inc = new(mem_ctx) ir_expression(ir_unop_neg,
 				       inc->type,
 				       inc->clone(mem_ctx, NULL),
 				       NULL);
    }

    return inc;
 }


 /**
  * Detect whether an if-statement is a loop terminating condition, if so
  * add it to the list of loop terminators.
  *
  * Detects if-statements of the form
  *
  *  (if (expression bool ...) (...then_instrs...break))
  *
  *     or
  *
  *  (if (expression bool ...) ... (...else_instrs...break))
  */
 void
 try_add_loop_terminator(loop_variable_state *ls, ir_if *ir)
 {
    ir_instruction *inst = (ir_instruction *) ir->then_instructions.get_tail();
    ir_instruction *else_inst =
       (ir_instruction *) ir->else_instructions.get_tail();

    if (is_break(inst) || is_break(else_inst))
       ls->insert(ir, is_break(else_inst));
 }


 loop_state *
 analyze_loop_variables(exec_list *instructions)
 {
    loop_state *loops = new loop_state;
    loop_analysis v(loops);

    v.run(instructions);
    return v.loops;
 }
	/*
	* Copyright © 2010 Intel Corporation
	*
	* Permission is hereby granted, free of charge, to any person obtaining a
	* copy of this software and associated documentation files (the "Software"),
	* to deal in the Software without restriction, including without limitation
	* the rights to use, copy, modify, merge, publish, distribute, sublicense,
	* and/or sell copies of the Software, and to permit persons to whom the
	* Software is furnished to do so, subject to the following conditions:
	*
	* The above copyright notice and this permission notice (including the next
	* paragraph) shall be included in all copies or substantial portions of the
	* Software.
	*
	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
	* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
	* DEALINGS IN THE SOFTWARE.
	*/

	#include "compiler/glsl_types.h"
	#include "loop_analysis.h"
	#include "ir_hierarchical_visitor.h"

	static void try_add_loop_terminator(loop_variable_state ls, ir_if ir);

	static bool all_expression_operands_are_loop_constant(ir_rvalue *,
	hash_table *);

	static ir_rvalue get_basic_induction_increment(ir_assignment , hash_table *);

	/**
	* Find an initializer of a variable outside a loop
	*
	* Works backwards from the loop to find the pre-loop value of the variable.
	* This is used, for example, to find the initial value of loop induction
	* variables.
	*
	* \param loop Loop where \c var is an induction variable
	* \param var Variable whose initializer is to be found
	*
	* \return
	* The \c ir_rvalue assigned to the variable outside the loop. May return
	* \c NULL if no initializer can be found.
	*/
	static ir_rvalue *
	find_initial_value(ir_loop loop, ir_variable var)
	{
	for (exec_node *node = loop->prev; !node->is_head_sentinel();
	node = node->prev) {
	ir_instruction ir = (ir_instruction ) node;

	switch (ir->ir_type) {
	case ir_type_call:
	case ir_type_loop:
	case ir_type_loop_jump:
	case ir_type_return:
	case ir_type_if:
	return NULL;

	case ir_type_function:
	case ir_type_function_signature:
	assert(!"Should not get here.");
	return NULL;

	case ir_type_assignment: {
	ir_assignment *assign = ir->as_assignment();
	ir_variable *assignee = assign->lhs->whole_variable_referenced();

	if (assignee == var)
	return (assign->condition != NULL) ? NULL : assign->rhs;

	break;
	}

	default:
	break;
	}
	}

	return NULL;
	}


	static int
	calculate_iterations(ir_rvalue from, ir_rvalue to, ir_rvalue *increment,
	enum ir_expression_operation op, bool continue_from_then,
	bool swap_compare_operands)
	{
	if (from == NULL \|\| to == NULL \|\| increment == NULL)
	return -1;

	void *mem_ctx = ralloc_context(NULL);

	ir_expression *const sub =
	new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from);

	ir_expression *const div =
	new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment);

	ir_constant *iter = div->constant_expression_value(mem_ctx);
	if (iter == NULL) {
	ralloc_free(mem_ctx);
	return -1;
	}

	if (!iter->type->is_integer()) {
	const ir_expression_operation op = iter->type->is_double()
	? ir_unop_d2i : ir_unop_f2i;
	ir_rvalue *cast =
	new(mem_ctx) ir_expression(op, glsl_type::int_type, iter, NULL);

	iter = cast->constant_expression_value(mem_ctx);
	}

	int iter_value = iter->get_int_component(0);

	/* Make sure that the calculated number of iterations satisfies the exit
	* condition. This is needed to catch off-by-one errors and some types of
	* ill-formed loops. For example, we need to detect that the following
	* loop does not have a maximum iteration count.
	*
	* for (float x = 0.0; x != 0.9; x += 0.2)
	* ;
	*/
	const int bias[] = { -1, 0, 1 };
	bool valid_loop = false;

	for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) {
	/* Increment may be of type int, uint or float. */
	switch (increment->type->base_type) {
	case GLSL_TYPE_INT:
	iter = new(mem_ctx) ir_constant(iter_value + bias[i]);
	break;
	case GLSL_TYPE_UINT:
	iter = new(mem_ctx) ir_constant(unsigned(iter_value + bias[i]));
	break;
	case GLSL_TYPE_FLOAT:
	iter = new(mem_ctx) ir_constant(float(iter_value + bias[i]));
	break;
	case GLSL_TYPE_DOUBLE:
	iter = new(mem_ctx) ir_constant(double(iter_value + bias[i]));
	break;
	default:
	unreachable("Unsupported type for loop iterator.");
	}

	ir_expression *const mul =
	new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter,
	increment);

	ir_expression *const add =
	new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from);

	ir_expression *cmp = swap_compare_operands
	? new(mem_ctx) ir_expression(op, glsl_type::bool_type, to, add)
	: new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to);
	if (continue_from_then)
	cmp = new(mem_ctx) ir_expression(ir_unop_logic_not, cmp);

	ir_constant *const cmp_result = cmp->constant_expression_value(mem_ctx);

	assert(cmp_result != NULL);
	if (cmp_result->get_bool_component(0)) {
	iter_value += bias[i];
	valid_loop = true;
	break;
	}
	}

	ralloc_free(mem_ctx);
	return (valid_loop) ? iter_value : -1;
	}

	static bool
	incremented_before_terminator(ir_loop loop, ir_variable var,
	ir_if *terminator)
	{
	for (exec_node *node = loop->body_instructions.get_head();
	!node->is_tail_sentinel();
	node = node->get_next()) {
	ir_instruction ir = (ir_instruction ) node;

	switch (ir->ir_type) {
	case ir_type_if:
	if (ir->as_if() == terminator)
	return false;
	break;

	case ir_type_assignment: {
	ir_assignment *assign = ir->as_assignment();
	ir_variable *assignee = assign->lhs->whole_variable_referenced();

	if (assignee == var) {
	assert(assign->condition == NULL);
	return true;
	}

	break;
	}

	default:
	break;
	}
	}

	unreachable("Unable to find induction variable");
	}

	/**
	* Record the fact that the given loop variable was referenced inside the loop.
	*
	* \arg in_assignee is true if the reference was on the LHS of an assignment.
	*
	* \arg in_conditional_code_or_nested_loop is true if the reference occurred
	* inside an if statement or a nested loop.
	*
	* \arg current_assignment is the ir_assignment node that the loop variable is
	* on the LHS of, if any (ignored if \c in_assignee is false).
	*/
	void
	loop_variable::record_reference(bool in_assignee,
	bool in_conditional_code_or_nested_loop,
	ir_assignment *current_assignment)
	{
	if (in_assignee) {
	assert(current_assignment != NULL);

	if (in_conditional_code_or_nested_loop \|\|
	current_assignment->condition != NULL) {
	this->conditional_or_nested_assignment = true;
	}

	if (this->first_assignment == NULL) {
	assert(this->num_assignments == 0);

	this->first_assignment = current_assignment;
	}

	this->num_assignments++;
	} else if (this->first_assignment == current_assignment) {
	/* This catches the case where the variable is used in the RHS of an
	* assignment where it is also in the LHS.
	*/
	this->read_before_write = true;
	}
	}


	loop_state::loop_state()
	{
	this->ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
	_mesa_key_pointer_equal);
	this->mem_ctx = ralloc_context(NULL);
	this->loop_found = false;
	}


	loop_state::~loop_state()
	{
	_mesa_hash_table_destroy(this->ht, NULL);
	ralloc_free(this->mem_ctx);
	}


	loop_variable_state *
	loop_state::insert(ir_loop *ir)
	{
	loop_variable_state *ls = new(this->mem_ctx) loop_variable_state;

	_mesa_hash_table_insert(this->ht, ir, ls);
	this->loop_found = true;

	return ls;
	}


	loop_variable_state *
	loop_state::get(const ir_loop *ir)
	{
	hash_entry *entry = _mesa_hash_table_search(this->ht, ir);
	return entry ? (loop_variable_state *) entry->data : NULL;
	}


	loop_variable *
	loop_variable_state::get(const ir_variable *ir)
	{
	hash_entry *entry = _mesa_hash_table_search(this->var_hash, ir);
	return entry ? (loop_variable *) entry->data : NULL;
	}


	loop_variable *
	loop_variable_state::insert(ir_variable *var)
	{
	void *mem_ctx = ralloc_parent(this);
	loop_variable *lv = rzalloc(mem_ctx, loop_variable);

	lv->var = var;

	_mesa_hash_table_insert(this->var_hash, lv->var, lv);
	this->variables.push_tail(lv);

	return lv;
	}


	loop_terminator *
	loop_variable_state::insert(ir_if *if_stmt, bool continue_from_then)
	{
	void *mem_ctx = ralloc_parent(this);
	loop_terminator *t = new(mem_ctx) loop_terminator();

	t->ir = if_stmt;
	t->continue_from_then = continue_from_then;

	this->terminators.push_tail(t);

	return t;
	}


	/**
	* If the given variable already is recorded in the state for this loop,
	* return the corresponding loop_variable object that records information
	* about it.
	*
	* Otherwise, create a new loop_variable object to record information about
	* the variable, and set its \c read_before_write field appropriately based on
	* \c in_assignee.
	*
	* \arg in_assignee is true if this variable was encountered on the LHS of an
	* assignment.
	*/
	loop_variable *
	loop_variable_state::get_or_insert(ir_variable *var, bool in_assignee)
	{
	loop_variable *lv = this->get(var);

	if (lv == NULL) {
	lv = this->insert(var);
	lv->read_before_write = !in_assignee;
	}

	return lv;
	}


	namespace {

	class loop_analysis : public ir_hierarchical_visitor {
	public:
	loop_analysis(loop_state *loops);

	virtual ir_visitor_status visit(ir_loop_jump *);
	virtual ir_visitor_status visit(ir_dereference_variable *);

	virtual ir_visitor_status visit_enter(ir_call *);

	virtual ir_visitor_status visit_enter(ir_loop *);
	virtual ir_visitor_status visit_leave(ir_loop *);
	virtual ir_visitor_status visit_enter(ir_assignment *);
	virtual ir_visitor_status visit_leave(ir_assignment *);
	virtual ir_visitor_status visit_enter(ir_if *);
	virtual ir_visitor_status visit_leave(ir_if *);

	loop_state *loops;

	int if_statement_depth;

	ir_assignment *current_assignment;

	exec_list state;
	};

	} /* anonymous namespace */

	loop_analysis::loop_analysis(loop_state *loops)
	: loops(loops), if_statement_depth(0), current_assignment(NULL)
	{
	/* empty */
	}


	ir_visitor_status
	loop_analysis::visit(ir_loop_jump *ir)
	{
	(void) ir;

	assert(!this->state.is_empty());

	loop_variable_state *const ls =
	(loop_variable_state *) this->state.get_head();

	ls->num_loop_jumps++;

	return visit_continue;
	}


	ir_visitor_status
	loop_analysis::visit_enter(ir_call *)
	{
	/* Mark every loop that we're currently analyzing as containing an ir_call
	* (even those at outer nesting levels).
	*/
	foreach_in_list(loop_variable_state, ls, &this->state) {
	ls->contains_calls = true;
	}

	return visit_continue_with_parent;
	}


	ir_visitor_status
	loop_analysis::visit(ir_dereference_variable *ir)
	{
	/* If we're not somewhere inside a loop, there's nothing to do.
	*/
	if (this->state.is_empty())
	return visit_continue;

	bool nested = false;

	foreach_in_list(loop_variable_state, ls, &this->state) {
	ir_variable *var = ir->variable_referenced();
	loop_variable *lv = ls->get_or_insert(var, this->in_assignee);

	lv->record_reference(this->in_assignee,
	nested \|\| this->if_statement_depth > 0,
	this->current_assignment);
	nested = true;
	}

	return visit_continue;
	}

	ir_visitor_status
	loop_analysis::visit_enter(ir_loop *ir)
	{
	loop_variable_state *ls = this->loops->insert(ir);
	this->state.push_head(ls);

	return visit_continue;
	}

	ir_visitor_status
	loop_analysis::visit_leave(ir_loop *ir)
	{
	loop_variable_state *const ls =
	(loop_variable_state *) this->state.pop_head();

	/* Function calls may contain side effects. These could alter any of our
	* variables in ways that cannot be known, and may even terminate shader
	* execution (say, calling discard in the fragment shader). So we can't
	* rely on any of our analysis about assignments to variables.
	*
	* We could perform some conservative analysis (prove there's no statically
	* possible assignment, etc.) but it isn't worth it for now; function
	* inlining will allow us to unroll loops anyway.
	*/
	if (ls->contains_calls)
	return visit_continue;

	foreach_in_list(ir_instruction, node, &ir->body_instructions) {
	/* Skip over declarations at the start of a loop.
	*/
	if (node->as_variable())
	continue;

	ir_if if_stmt = ((ir_instruction ) node)->as_if();

	if (if_stmt != NULL)
	try_add_loop_terminator(ls, if_stmt);
	}


	foreach_in_list_safe(loop_variable, lv, &ls->variables) {
	/* Move variables that are already marked as being loop constant to
	* a separate list. These trivially don't need to be tested.
	*/
	if (lv->is_loop_constant()) {
	lv->remove();
	ls->constants.push_tail(lv);
	}
	}

	/* Each variable assigned in the loop that isn't already marked as being loop
	* constant might still be loop constant. The requirements at this point
	* are:
	*
	* - Variable is written before it is read.
	*
	* - Only one assignment to the variable.
	*
	* - All operands on the RHS of the assignment are also loop constants.
	*
	* The last requirement is the reason for the progress loop. A variable
	* marked as a loop constant on one pass may allow other variables to be
	* marked as loop constant on following passes.
	*/
	bool progress;
	do {
	progress = false;

	foreach_in_list_safe(loop_variable, lv, &ls->variables) {
	if (lv->conditional_or_nested_assignment \|\| (lv->num_assignments > 1))
	continue;

	/* Process the RHS of the assignment. If all of the variables
	* accessed there are loop constants, then add this
	*/
	ir_rvalue *const rhs = lv->first_assignment->rhs;
	if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) {
	lv->rhs_clean = true;

	if (lv->is_loop_constant()) {
	progress = true;

	lv->remove();
	ls->constants.push_tail(lv);
	}
	}
	}
	} while (progress);

	/* The remaining variables that are not loop invariant might be loop
	* induction variables.
	*/
	foreach_in_list_safe(loop_variable, lv, &ls->variables) {
	/* If there is more than one assignment to a variable, it cannot be a
	* loop induction variable. This isn't strictly true, but this is a
	* very simple induction variable detector, and it can't handle more
	* complex cases.
	*/
	if (lv->num_assignments > 1)
	continue;

	/* All of the variables with zero assignments in the loop are loop
	* invariant, and they should have already been filtered out.
	*/
	assert(lv->num_assignments == 1);
	assert(lv->first_assignment != NULL);

	/* The assignment to the variable in the loop must be unconditional and
	* not inside a nested loop.
	*/
	if (lv->conditional_or_nested_assignment)
	continue;

	/* Basic loop induction variables have a single assignment in the loop
	* that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a
	* loop invariant.
	*/
	ir_rvalue *const inc =
	get_basic_induction_increment(lv->first_assignment, ls->var_hash);
	if (inc != NULL) {
	lv->increment = inc;

	lv->remove();
	ls->induction_variables.push_tail(lv);
	}
	}

	/* Search the loop terminating conditions for those of the form 'i < c'
	* where i is a loop induction variable, c is a constant, and < is any
	* relative operator. From each of these we can infer an iteration count.
	* Also figure out which terminator (if any) produces the smallest
	* iteration count--this is the limiting terminator.
	*/
	foreach_in_list(loop_terminator, t, &ls->terminators) {
	ir_if *if_stmt = t->ir;

	/* If-statements can be either 'if (expr)' or 'if (deref)'. We only care
	* about the former here.
	*/
	ir_expression *cond = if_stmt->condition->as_expression();
	if (cond == NULL)
	continue;

	switch (cond->operation) {
	case ir_binop_less:
	case ir_binop_gequal: {
	/* The expressions that we care about will either be of the form
	* 'counter < limit' or 'limit < counter'. Figure out which is
	* which.
	*/
	ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
	ir_constant *limit = cond->operands[1]->as_constant();
	enum ir_expression_operation cmp = cond->operation;
	bool swap_compare_operands = false;

	if (limit == NULL) {
	counter = cond->operands[1]->as_dereference_variable();
	limit = cond->operands[0]->as_constant();
	swap_compare_operands = true;
	}

	if ((counter == NULL) \|\| (limit == NULL))
	break;

	ir_variable *var = counter->variable_referenced();

	ir_rvalue *init = find_initial_value(ir, var);

	loop_variable *lv = ls->get(var);
	if (lv != NULL && lv->is_induction_var()) {
	t->iterations = calculate_iterations(init, limit, lv->increment,
	cmp, t->continue_from_then,
	swap_compare_operands);

	if (incremented_before_terminator(ir, var, t->ir)) {
	t->iterations--;
	}

	if (t->iterations >= 0 &&
	(ls->limiting_terminator == NULL \|\|
	t->iterations < ls->limiting_terminator->iterations)) {
	ls->limiting_terminator = t;
	}
	}
	break;
	}

	default:
	break;
	}
	}

	return visit_continue;
	}

	ir_visitor_status
	loop_analysis::visit_enter(ir_if *ir)
	{
	(void) ir;

	if (!this->state.is_empty())
	this->if_statement_depth++;

	return visit_continue;
	}

	ir_visitor_status
	loop_analysis::visit_leave(ir_if *ir)
	{
	(void) ir;

	if (!this->state.is_empty())
	this->if_statement_depth--;

	return visit_continue;
	}

	ir_visitor_status
	loop_analysis::visit_enter(ir_assignment *ir)
	{
	/* If we're not somewhere inside a loop, there's nothing to do.
	*/
	if (this->state.is_empty())
	return visit_continue_with_parent;

	this->current_assignment = ir;

	return visit_continue;
	}

	ir_visitor_status
	loop_analysis::visit_leave(ir_assignment *ir)
	{
	/* Since the visit_enter exits with visit_continue_with_parent for this
	* case, the loop state stack should never be empty here.
	*/
	assert(!this->state.is_empty());

	assert(this->current_assignment == ir);
	this->current_assignment = NULL;

	return visit_continue;
	}


	class examine_rhs : public ir_hierarchical_visitor {
	public:
	examine_rhs(hash_table *loop_variables)
	{
	this->only_uses_loop_constants = true;
	this->loop_variables = loop_variables;
	}

	virtual ir_visitor_status visit(ir_dereference_variable *ir)
	{
	hash_entry *entry = _mesa_hash_table_search(this->loop_variables,
	ir->var);
	loop_variable lv = entry ? (loop_variable ) entry->data : NULL;

	assert(lv != NULL);

	if (lv->is_loop_constant()) {
	return visit_continue;
	} else {
	this->only_uses_loop_constants = false;
	return visit_stop;
	}
	}

	hash_table *loop_variables;
	bool only_uses_loop_constants;
	};


	bool
	all_expression_operands_are_loop_constant(ir_rvalue ir, hash_table variables)
	{
	examine_rhs v(variables);

	ir->accept(&v);

	return v.only_uses_loop_constants;
	}


	ir_rvalue *
	get_basic_induction_increment(ir_assignment ir, hash_table var_hash)
	{
	/* The RHS must be a binary expression.
	*/
	ir_expression *const rhs = ir->rhs->as_expression();
	if ((rhs == NULL)
	\|\| ((rhs->operation != ir_binop_add)
	&& (rhs->operation != ir_binop_sub)))
	return NULL;

	/* One of the of operands of the expression must be the variable assigned.
	* If the operation is subtraction, the variable in question must be the
	* "left" operand.
	*/
	ir_variable *const var = ir->lhs->variable_referenced();

	ir_variable *const op0 = rhs->operands[0]->variable_referenced();
	ir_variable *const op1 = rhs->operands[1]->variable_referenced();

	if (((op0 != var) && (op1 != var))
	\|\| ((op1 == var) && (rhs->operation == ir_binop_sub)))
	return NULL;

	ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0];

	if (inc->as_constant() == NULL) {
	ir_variable *const inc_var = inc->variable_referenced();
	if (inc_var != NULL) {
	hash_entry *entry = _mesa_hash_table_search(var_hash, inc_var);
	loop_variable lv = entry ? (loop_variable ) entry->data : NULL;

	if (lv == NULL \|\| !lv->is_loop_constant()) {
	assert(lv != NULL);
	inc = NULL;
	}
	} else
	inc = NULL;
	}

	if ((inc != NULL) && (rhs->operation == ir_binop_sub)) {
	void *mem_ctx = ralloc_parent(ir);

	inc = new(mem_ctx) ir_expression(ir_unop_neg,
	inc->type,
	inc->clone(mem_ctx, NULL),
	NULL);
	}

	return inc;
	}


	/**
	* Detect whether an if-statement is a loop terminating condition, if so
	* add it to the list of loop terminators.
	*
	* Detects if-statements of the form
	*
	* (if (expression bool ...) (...then_instrs...break))
	*
	* or
	*
	* (if (expression bool ...) ... (...else_instrs...break))
	*/
	void
	try_add_loop_terminator(loop_variable_state ls, ir_if ir)
	{
	ir_instruction inst = (ir_instruction ) ir->then_instructions.get_tail();
	ir_instruction *else_inst =
	(ir_instruction *) ir->else_instructions.get_tail();

	if (is_break(inst) \|\| is_break(else_inst))
	ls->insert(ir, is_break(else_inst));
	}


	loop_state *
	analyze_loop_variables(exec_list *instructions)
	{
	loop_state *loops = new loop_state;
	loop_analysis v(loops);

	v.run(instructions);
	return v.loops;
	}