Import Mesa 11.2.2

1 files changed, 51 insertions, 267 deletions

diff --git a/lib/mesa/src/compiler/glsl/loop_analysis.cpp b/lib/mesa/src/compiler/glsl/loop_analysis.cpp
index c8db6f63b..096a80abb 100644
--- a/lib/mesa/src/compiler/glsl/loop_analysis.cpp
+++ b/lib/mesa/src/compiler/glsl/loop_analysis.cpp
@@ -25,235 +25,13 @@
 #include "loop_analysis.h"
 #include "ir_hierarchical_visitor.h"
 
-static void try_add_loop_terminator(loop_variable_state *ls, ir_if *ir);
+static bool is_loop_terminator(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->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, bool inc_before_terminator)
-{
-   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);
-   }
-
-   int64_t iter_value = iter->get_int64_component(0);
-
-   /* Code after this block works under assumption that iterator will be
-    * incremented or decremented until it hits the limit,
-    * however the loop condition can be false on the first iteration.
-    * Handle such loops first.
-    */
-   {
-      ir_rvalue *first_value = from;
-      if (inc_before_terminator) {
-         first_value =
-            new(mem_ctx) ir_expression(ir_binop_add, from->type, from, increment);
-      }
-
-      ir_expression *cmp = swap_compare_operands
-            ? new(mem_ctx) ir_expression(op, glsl_type::bool_type, to, first_value)
-            : new(mem_ctx) ir_expression(op, glsl_type::bool_type, first_value, 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)) {
-         ralloc_free(mem_ctx);
-         return 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(int32_t(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_INT16:
-         iter = new(mem_ctx) ir_constant(int16_t(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_INT64:
-         iter = new(mem_ctx) ir_constant(int64_t(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_UINT:
-         iter = new(mem_ctx) ir_constant(unsigned(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_UINT16:
-         iter = new(mem_ctx) ir_constant(uint16_t(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_UINT64:
-         iter = new(mem_ctx) ir_constant(uint64_t(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_FLOAT:
-         iter = new(mem_ctx) ir_constant(float(iter_value + bias[i]));
-         break;
-      case GLSL_TYPE_FLOAT16:
-         iter = new(mem_ctx) ir_constant(float16_t(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);
-
-   if (inc_before_terminator) {
-      iter_value--;
-   }
-
-   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) {
-            return true;
-         }
-
-         break;
-      }
-
-      default:
-         break;
-      }
-   }
-
-   unreachable("Unable to find induction variable");
-}
 
 /**
  * Record the fact that the given loop variable was referenced inside the loop.
@@ -274,7 +52,8 @@ loop_variable::record_reference(bool in_assignee,
    if (in_assignee) {
       assert(current_assignment != NULL);
 
-      if (in_conditional_code_or_nested_loop) {
+      if (in_conditional_code_or_nested_loop ||
+          current_assignment->condition != NULL) {
          this->conditional_or_nested_assignment = true;
       }
 
@@ -296,7 +75,8 @@ loop_variable::record_reference(bool in_assignee,
 
 loop_state::loop_state()
 {
-   this->ht = _mesa_pointer_hash_table_create(NULL);
+   this->ht = hash_table_ctor(0, hash_table_pointer_hash,
+			      hash_table_pointer_compare);
    this->mem_ctx = ralloc_context(NULL);
    this->loop_found = false;
 }
@@ -304,7 +84,7 @@ loop_state::loop_state()
 
 loop_state::~loop_state()
 {
-   _mesa_hash_table_destroy(this->ht, NULL);
+   hash_table_dtor(this->ht);
    ralloc_free(this->mem_ctx);
 }
 
@@ -314,7 +94,7 @@ 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);
+   hash_table_insert(this->ht, ls, ir);
    this->loop_found = true;
 
    return ls;
@@ -324,19 +104,14 @@ loop_state::insert(ir_loop *ir)
 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;
+   return (loop_variable_state *) hash_table_find(this->ht, ir);
 }
 
 
 loop_variable *
 loop_variable_state::get(const ir_variable *ir)
 {
-   if (ir == NULL)
-      return NULL;
-
-   hash_entry *entry = _mesa_hash_table_search(this->var_hash, ir);
-   return entry ? (loop_variable *) entry->data : NULL;
+   return (loop_variable *) hash_table_find(this->var_hash, ir);
 }
 
 
@@ -348,7 +123,7 @@ loop_variable_state::insert(ir_variable *var)
 
    lv->var = var;
 
-   _mesa_hash_table_insert(this->var_hash, lv->var, lv);
+   hash_table_insert(this->var_hash, lv, lv->var);
    this->variables.push_tail(lv);
 
    return lv;
@@ -356,12 +131,12 @@ loop_variable_state::insert(ir_variable *var)
 
 
 loop_terminator *
-loop_variable_state::insert(ir_if *if_stmt, bool continue_from_then)
+loop_variable_state::insert(ir_if *if_stmt)
 {
    void *mem_ctx = ralloc_parent(this);
-   loop_terminator *t = new(mem_ctx) loop_terminator(if_stmt,
-                                                     continue_from_then);
+   loop_terminator *t = new(mem_ctx) loop_terminator();
 
+   t->ir = if_stmt;
    this->terminators.push_tail(t);
 
    return t;
@@ -518,8 +293,10 @@ loop_analysis::visit_leave(ir_loop *ir)
 
       ir_if *if_stmt = ((ir_instruction *) node)->as_if();
 
-      if (if_stmt != NULL)
-         try_add_loop_terminator(ls, if_stmt);
+      if ((if_stmt != NULL) && is_loop_terminator(if_stmt))
+	 ls->insert(if_stmt);
+      else
+	 break;
    }
 
 
@@ -628,6 +405,8 @@ loop_analysis::visit_leave(ir_loop *ir)
 
       switch (cond->operation) {
       case ir_binop_less:
+      case ir_binop_greater:
+      case ir_binop_lequal:
       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
@@ -636,12 +415,18 @@ loop_analysis::visit_leave(ir_loop *ir)
 	 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;
+
+	    switch (cmp) {
+	    case ir_binop_less:    cmp = ir_binop_greater; break;
+	    case ir_binop_greater: cmp = ir_binop_less;    break;
+	    case ir_binop_lequal:  cmp = ir_binop_gequal;  break;
+	    case ir_binop_gequal:  cmp = ir_binop_lequal;  break;
+	    default: assert(!"Should not get here.");
+	    }
 	 }
 
 	 if ((counter == NULL) || (limit == NULL))
@@ -653,13 +438,8 @@ loop_analysis::visit_leave(ir_loop *ir)
 
          loop_variable *lv = ls->get(var);
          if (lv != NULL && lv->is_induction_var()) {
-            bool inc_before_terminator =
-               incremented_before_terminator(ir, var, t->ir);
-
             t->iterations = calculate_iterations(init, limit, lv->increment,
-                                                 cmp, t->continue_from_then,
-                                                 swap_compare_operands,
-                                                 inc_before_terminator);
+                                                 cmp);
 
             if (t->iterations >= 0 &&
                 (ls->limiting_terminator == NULL ||
@@ -738,9 +518,8 @@ public:
 
    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;
+      loop_variable *lv =
+	 (loop_variable *) hash_table_find(this->loop_variables, ir->var);
 
       assert(lv != NULL);
 
@@ -797,8 +576,8 @@ get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
    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;
+	 loop_variable *lv =
+	    (loop_variable *) hash_table_find(var_hash, inc_var);
 
          if (lv == NULL || !lv->is_loop_constant()) {
             assert(lv != NULL);
@@ -822,26 +601,31 @@ get_basic_induction_increment(ir_assignment *ir, hash_table *var_hash)
 
 
 /**
- * Detect whether an if-statement is a loop terminating condition, if so
- * add it to the list of loop terminators.
+ * Detect whether an if-statement is a loop terminating condition
  *
  * Detects if-statements of the form
  *
- *  (if (expression bool ...) (...then_instrs...break))
- *
- *     or
- *
- *  (if (expression bool ...) ... (...else_instrs...break))
+ *  (if (expression bool ...) (break))
  */
-void
-try_add_loop_terminator(loop_variable_state *ls, ir_if *ir)
+bool
+is_loop_terminator(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 (!ir->else_instructions.is_empty())
+      return false;
+
+   ir_instruction *const inst =
+      (ir_instruction *) ir->then_instructions.get_head();
+   if (inst == NULL)
+      return false;
+
+   if (inst->ir_type != ir_type_loop_jump)
+      return false;
+
+   ir_loop_jump *const jump = (ir_loop_jump *) inst;
+   if (jump->mode != ir_loop_jump::jump_break)
+      return false;
 
-   if (is_break(inst) || is_break(else_inst))
-      ls->insert(ir, is_break(else_inst));
+   return true;
 }