glsl: fix the type of ir_constant_data::u16
[mesa.git] / src / compiler / glsl / loop_unroll.cpp
index aea2743cdb18f69a2f4268861bdf4825490a23fa..1a9229acc345c4263f1cca8a35eba6c4f45db06b 100644 (file)
@@ -42,7 +42,9 @@ public:
    virtual ir_visitor_status visit_leave(ir_loop *ir);
    void simple_unroll(ir_loop *ir, int iterations);
    void complex_unroll(ir_loop *ir, int iterations,
-                       bool continue_from_then_branch);
+                       bool continue_from_then_branch,
+                       bool limiting_term_first,
+                       bool lt_continue_from_then_branch);
    void splice_post_if_instructions(ir_if *ir_if, exec_list *splice_dest);
 
    loop_state *state;
@@ -53,13 +55,6 @@ public:
 
 } /* anonymous namespace */
 
-static bool
-is_break(ir_instruction *ir)
-{
-   return ir != NULL && ir->ir_type == ir_type_loop_jump
-                    && ((ir_loop_jump *) ir)->is_break();
-}
-
 class loop_unroll_count : public ir_hierarchical_visitor {
 public:
    int nodes;
@@ -106,7 +101,7 @@ public:
       if (options->EmitNoIndirectSampler) {
          if ((ir->array->type->is_array() &&
               ir->array->type->contains_sampler()) &&
-             !ir->array_index->constant_expression_value()) {
+             !ir->array_index->constant_expression_value(ralloc_parent(ir))) {
             unsupported_variable_indexing = true;
             return visit_continue;
          }
@@ -183,6 +178,57 @@ void
 loop_unroll_visitor::simple_unroll(ir_loop *ir, int iterations)
 {
    void *const mem_ctx = ralloc_parent(ir);
+   loop_variable_state *const ls = this->state->get(ir);
+
+   /* If there are no terminators, then the loop iteration count must be 1.
+    * This is the 'do { } while (false);' case.
+    */
+   assert(!ls->terminators.is_empty() || iterations == 1);
+
+   ir_instruction *first_ir =
+      (ir_instruction *) ir->body_instructions.get_head();
+
+   if (!first_ir) {
+      /* The loop is empty remove it and return */
+      ir->remove();
+      return;
+   }
+
+   ir_if *limit_if = NULL;
+   bool exit_branch_has_instructions = false;
+   if (ls->limiting_terminator) {
+      limit_if = ls->limiting_terminator->ir;
+      ir_instruction *ir_if_last = (ir_instruction *)
+         limit_if->then_instructions.get_tail();
+
+      if (is_break(ir_if_last)) {
+         if (ir_if_last != limit_if->then_instructions.get_head())
+            exit_branch_has_instructions = true;
+
+         splice_post_if_instructions(limit_if, &limit_if->else_instructions);
+         ir_if_last->remove();
+      } else {
+         ir_if_last = (ir_instruction *)
+            limit_if->else_instructions.get_tail();
+         assert(is_break(ir_if_last));
+
+         if (ir_if_last != limit_if->else_instructions.get_head())
+            exit_branch_has_instructions = true;
+
+         splice_post_if_instructions(limit_if, &limit_if->then_instructions);
+         ir_if_last->remove();
+      }
+   }
+
+   /* Because 'iterations' is the number of times we pass over the *entire*
+    * loop body before hitting the first break, we need to bump the number of
+    * iterations if the limiting terminator is not the first instruction in
+    * the loop, or it the exit branch contains instructions. This ensures we
+    * execute any instructions before the terminator or in its exit branch.
+    */
+   if (!ls->terminators.is_empty() &&
+       (limit_if != first_ir->as_if() || exit_branch_has_instructions))
+      iterations++;
 
    for (int i = 0; i < iterations; i++) {
       exec_list copy_list;
@@ -234,11 +280,22 @@ loop_unroll_visitor::simple_unroll(ir_loop *ir, int iterations)
  */
 void
 loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
-                                    bool continue_from_then_branch)
+                                    bool second_term_then_continue,
+                                    bool extra_iteration_required,
+                                    bool first_term_then_continue)
 {
    void *const mem_ctx = ralloc_parent(ir);
    ir_instruction *ir_to_replace = ir;
 
+   /* Because 'iterations' is the number of times we pass over the *entire*
+    * loop body before hitting the first break, we need to bump the number of
+    * iterations if the limiting terminator is not the first instruction in
+    * the loop, or it the exit branch contains instructions. This ensures we
+    * execute any instructions before the terminator or in its exit branch.
+    */
+   if (extra_iteration_required)
+      iterations++;
+
    for (int i = 0; i < iterations; i++) {
       exec_list copy_list;
 
@@ -248,6 +305,10 @@ loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
       ir_if *ir_if = ((ir_instruction *) copy_list.get_tail())->as_if();
       assert(ir_if != NULL);
 
+      exec_list *const first_list = first_term_then_continue
+         ? &ir_if->then_instructions : &ir_if->else_instructions;
+      ir_if = ((ir_instruction *) first_list->get_tail())->as_if();
+
       ir_to_replace->insert_before(&copy_list);
       ir_to_replace->remove();
 
@@ -255,10 +316,10 @@ loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
       ir_to_replace =
          new(mem_ctx) ir_loop_jump(ir_loop_jump::jump_continue);
 
-      exec_list *const list = (continue_from_then_branch)
+      exec_list *const second_term_continue_list = second_term_then_continue
          ? &ir_if->then_instructions : &ir_if->else_instructions;
 
-      list->push_tail(ir_to_replace);
+      second_term_continue_list->push_tail(ir_to_replace);
    }
 
    ir_to_replace->remove();
@@ -300,12 +361,26 @@ loop_unroll_visitor::splice_post_if_instructions(ir_if *ir_if,
    }
 }
 
+static bool
+exit_branch_has_instructions(ir_if *term_if, bool lt_then_continue)
+{
+   if (lt_then_continue) {
+      if (term_if->else_instructions.get_head() ==
+          term_if->else_instructions.get_tail())
+         return false;
+   } else {
+      if (term_if->then_instructions.get_head() ==
+          term_if->then_instructions.get_tail())
+         return false;
+   }
+
+   return true;
+}
 
 ir_visitor_status
 loop_unroll_visitor::visit_leave(ir_loop *ir)
 {
    loop_variable_state *const ls = this->state->get(ir);
-   int iterations;
 
    /* If we've entered a loop that hasn't been analyzed, something really,
     * really bad has happened.
@@ -315,13 +390,80 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
       return visit_continue;
    }
 
-   /* Don't try to unroll loops where the number of iterations is not known
-    * at compile-time.
+   /* Limiting terminator may have iteration count of zero,
+    * this is a valid case because the loop may break during
+    * the first iteration.
     */
-   if (ls->limiting_terminator == NULL)
+
+   /* Remove the conditional break statements associated with all terminators
+    * that are associated with a fixed iteration count, except for the one
+    * associated with the limiting terminator--that one needs to stay, since
+    * it terminates the loop.  Exception: if the loop still has a normative
+    * bound, then that terminates the loop, so we don't even need the limiting
+    * terminator.
+    */
+   foreach_in_list_safe(loop_terminator, t, &ls->terminators) {
+      if (t->iterations < 0)
+         continue;
+
+      exec_list *branch_instructions;
+      if (t != ls->limiting_terminator) {
+         ir_instruction *ir_if_last = (ir_instruction *)
+            t->ir->then_instructions.get_tail();
+         if (is_break(ir_if_last)) {
+            branch_instructions = &t->ir->else_instructions;
+         } else {
+            branch_instructions = &t->ir->then_instructions;
+            assert(is_break((ir_instruction *)
+                            t->ir->else_instructions.get_tail()));
+         }
+
+         exec_list copy_list;
+         copy_list.make_empty();
+         clone_ir_list(ir, &copy_list, branch_instructions);
+
+         t->ir->insert_before(&copy_list);
+         t->ir->remove();
+
+         assert(ls->num_loop_jumps > 0);
+         ls->num_loop_jumps--;
+
+         /* Also remove it from the terminator list */
+         t->remove();
+
+         this->progress = true;
+      }
+   }
+
+   if (ls->limiting_terminator == NULL) {
+      ir_instruction *last_ir =
+         (ir_instruction *) ir->body_instructions.get_tail();
+
+      /* If a loop has no induction variable and the last instruction is
+       * a break, unroll the loop with a count of 1.  This is the classic
+       *
+       *    do {
+       *        // ...
+       *    } while (false)
+       *
+       * that is used to wrap multi-line macros.
+       *
+       * If num_loop_jumps is not zero, last_ir cannot be NULL... there has to
+       * be at least num_loop_jumps instructions in the loop.
+       */
+      if (ls->num_loop_jumps == 1 && is_break(last_ir)) {
+         last_ir->remove();
+
+         simple_unroll(ir, 1);
+      }
+
+      /* Don't try to unroll loops where the number of iterations is not known
+       * at compile-time.
+       */
       return visit_continue;
+   }
 
-   iterations = ls->limiting_terminator->iterations;
+   int iterations = ls->limiting_terminator->iterations;
 
    const int max_iterations = options->MaxUnrollIterations;
 
@@ -351,7 +493,6 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
       return visit_continue;
 
    if (predicted_num_loop_jumps == 0) {
-      ls->limiting_terminator->ir->remove();
       simple_unroll(ir, iterations);
       return visit_continue;
    }
@@ -366,51 +507,69 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
        */
       last_ir->remove();
 
-      ls->limiting_terminator->ir->remove();
       simple_unroll(ir, 1);
       return visit_continue;
    }
 
-   /* recognize loops in the form produced by ir_lower_jumps */
-   foreach_in_list(ir_instruction, cur_ir, &ir->body_instructions) {
-      /* Skip the limiting terminator, since it will go away when we
-       * unroll.
-       */
-      if (cur_ir == ls->limiting_terminator->ir)
-         continue;
+   /* Complex unrolling can only handle two terminators. One with an unknown
+    * iteration count and one with a known iteration count. We have already
+    * made sure we have a known iteration count above and removed any
+    * unreachable terminators with a known count. Here we make sure there
+    * isn't any additional unknown terminators, or any other jumps nested
+    * inside futher ifs.
+    */
+   if (ls->num_loop_jumps != 2 || ls->terminators.length() != 2)
+      return visit_continue;
 
-      ir_if *ir_if = cur_ir->as_if();
-      if (ir_if != NULL) {
-         /* Determine which if-statement branch, if any, ends with a
-          * break.  The branch that did *not* have the break will get a
-          * temporary continue inserted in each iteration of the loop
-          * unroll.
-          *
-          * Note that since ls->num_loop_jumps is <= 1, it is impossible
-          * for both branches to end with a break.
-          */
-         ir_instruction *ir_if_last =
-            (ir_instruction *) ir_if->then_instructions.get_tail();
+   ir_instruction *first_ir =
+      (ir_instruction *) ir->body_instructions.get_head();
 
+   unsigned term_count = 0;
+   bool first_term_then_continue = false;
+   foreach_in_list(loop_terminator, t, &ls->terminators) {
+      ir_if *ir_if = t->ir->as_if();
+      assert(ir_if != NULL);
+
+      ir_instruction *ir_if_last =
+         (ir_instruction *) ir_if->then_instructions.get_tail();
+
+      if (is_break(ir_if_last)) {
+         splice_post_if_instructions(ir_if, &ir_if->else_instructions);
+         ir_if_last->remove();
+         if (term_count == 1) {
+            bool ebi =
+               exit_branch_has_instructions(ls->limiting_terminator->ir,
+                                            first_term_then_continue);
+            complex_unroll(ir, iterations, false,
+                           first_ir->as_if() != ls->limiting_terminator->ir ||
+                           ebi,
+                           first_term_then_continue);
+            return visit_continue;
+         }
+      } else {
+         ir_if_last =
+            (ir_instruction *) ir_if->else_instructions.get_tail();
+
+         assert(is_break(ir_if_last));
          if (is_break(ir_if_last)) {
-            ls->limiting_terminator->ir->remove();
-            splice_post_if_instructions(ir_if, &ir_if->else_instructions);
+            splice_post_if_instructions(ir_if, &ir_if->then_instructions);
             ir_if_last->remove();
-            complex_unroll(ir, iterations, false);
-            return visit_continue;
-         } else {
-            ir_if_last =
-               (ir_instruction *) ir_if->else_instructions.get_tail();
-
-            if (is_break(ir_if_last)) {
-               ls->limiting_terminator->ir->remove();
-               splice_post_if_instructions(ir_if, &ir_if->then_instructions);
-               ir_if_last->remove();
-               complex_unroll(ir, iterations, true);
+            if (term_count == 1) {
+               bool ebi =
+                  exit_branch_has_instructions(ls->limiting_terminator->ir,
+                                               first_term_then_continue);
+               complex_unroll(ir, iterations, true,
+                              first_ir->as_if() != ls->limiting_terminator->ir ||
+                              ebi,
+                              first_term_then_continue);
                return visit_continue;
+            } else {
+               first_term_then_continue = true;
             }
          }
       }
+
+      term_count++;
    }
 
    /* Did not find the break statement.  It must be in a complex if-nesting,