Re: [Mesa-dev] [PATCH 3/3] glsl: make loop unrolling more like the nir unrolling path

[Timothy Arceri]

On 18/09/17 21:43, Timothy Arceri wrote:


On 18/09/17 20:50, Nicolai Hähnle wrote:
On 14.09.2017 06:47, Timothy Arceri wrote:
The old code incorrectly assumed that loop terminators will always
be at the start of the loop. It really seems to be just luck that
we haven't triggered any bugs here, for example if there is a loop
terminator at the start of the loop we might actually ignore any
other terminators that might be later in the loop because we break
before checking all the instructions. Ignoring the other
terminators might result in unrolling loops that we shouldn't be,
or the wrong number of iterations being calculated etc.

Incorrect analysis can also result in loops not being
unrolled at all. For example the current code would unroll:

   int j = 0;
   do {
      if (j > 5)
         break;

      ... do stuff ...

      j++;
   } while (j < 4);

But would fail to unroll the following as no iteration limit was
calculated because it failed to find the terminator:

   int j = 0;
   do {
      ... do stuff ...

      j++;
   } while (j < 4);

Also we would fail to unroll the following as we ended up
calculating the iteration limit as 6 rather than 4. The unroll
code then assumed we had 3 terminators rather the 2 as it
wasn't able to determine that "if (j > 5)" was redundant.

   int j = 0;
   do {
      if (j > 5)
         break;

      ... do stuff ...

      if (bool(i))
         break;

      j++;
   } while (j < 4);

This patch changes this pass to be more like the NIR unrolling pass.
With this change we handle loop terminators correctly and also
handle cases where the terminators have instructions in their
branches other than a break.

Some of that code is a bit tricky.

Could we perhaps normalize the loop terminators such that the break is 
always in the then-branch? I.e. flip then- and else-branches if 
required. This would simplify a lot of the case distinction.

Additionally, it's not clear to me what the value-add of the complex 
loop at the end of visit_leave is. Couldn't we just unconditionally do 
the splicing of terminators into a chain of if-statements, so that

   loop {
     ...
     if (cond) {
       ...
       break
     }
     ...
     if (cond) {
       ...
       break
     }
     ...
   }

becomes

   loop {
     ...
     if (cond) {
       ...
       break
     } else {
       ...
       if (cond) {
         ...
         break
       } else {
         ...
         // splice subsequent unrolled iterations here
       }
     }
   }

regardless of which condition is the limiting terminator?

Unrolling chains the if-statements even further, and constant 
propagation should take care of the rest. We already rely on constant 
propagation for cleanups anyway.

Ok I see where the confusion was now. I forgot to rename the bools from 
an earlier attempt at reworking this. Also because of the crazy way this 
code worked before I'd broken unrolling loops with breaks in the else
branch so we never tried to unroll them and the code I had in complex 
unrolling for these was just plain wrong. I've fixed everything up and 
I'm testing a V2 now. Should have it sent out shortly.


I'm not sure what exactly the point is you are trying to make. This is 
exactly what the code does. The difference between the simple unroll and 
complex unroll is 1. you need to splice one if inside the other 2. you 
need a placeholder so you can insert the subsequent iteration. These are 
the only differences between the simple unroll, but trying combine them 
would just make the code even harder to follow IMO.



Some other, more minor comments, below.



---
  src/compiler/glsl/loop_analysis.cpp |   7 +-
  src/compiler/glsl/loop_unroll.cpp   | 177 
++++++++++++++++++++++++++++--------
  2 files changed, 141 insertions(+), 43 deletions(-)

diff --git a/src/compiler/glsl/loop_analysis.cpp 
b/src/compiler/glsl/loop_analysis.cpp
index 8a0425d185..53372183dd 100644
--- a/src/compiler/glsl/loop_analysis.cpp
+++ b/src/compiler/glsl/loop_analysis.cpp
@@ -324,22 +324,20 @@ loop_analysis::visit_leave(ir_loop *ir)
     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) && is_loop_terminator(if_stmt))
       ls->insert(if_stmt);
-      else
-     break;
     }
     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);
@@ -644,25 +642,22 @@ get_basic_induction_increment(ir_assignment 
*ir, hash_table *var_hash)
  /**
   * Detect whether an if-statement is a loop terminating condition
   *
   * Detects if-statements of the form
   *
   *  (if (expression bool ...) (break))

Please update this comment to account for possibly having more 
instruction and an else-branch.


   */
  bool
  is_loop_terminator(ir_if *ir)
  {
-   if (!ir->else_instructions.is_empty())
-      return false;
-
     ir_instruction *const inst =
-      (ir_instruction *) ir->then_instructions.get_head();
+      (ir_instruction *) ir->then_instructions.get_tail();
     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;
diff --git a/src/compiler/glsl/loop_unroll.cpp 
b/src/compiler/glsl/loop_unroll.cpp
index 7f601295a1..9aa2b975f7 100644
--- a/src/compiler/glsl/loop_unroll.cpp
+++ b/src/compiler/glsl/loop_unroll.cpp
@@ -35,21 +35,23 @@ public:
                         const struct gl_shader_compiler_options 
*options)
     {
        this->state = state;
        this->progress = false;
        this->options = options;
     }
     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;
     bool progress;
     const struct gl_shader_compiler_options *options;
  };
  } /* anonymous namespace */
@@ -169,20 +171,65 @@ private:
   *     (loop (...) ...instrs...)
   *
   * And the iteration count is 3, the output will be:
   *
   *     ...instrs... ...instrs... ...instrs...
   */
  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);
+
+   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 (limit_if != first_ir->as_if() || exit_branch_has_instructions)
+      iterations++;
     for (int i = 0; i < iterations; i++) {
        exec_list copy_list;
        copy_list.make_empty();
        clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
        ir->insert_before(&copy_list);
     }
@@ -220,45 +267,60 @@ loop_unroll_visitor::simple_unroll(ir_loop *ir, 
int iterations)
   *              (...then_instrs...
   *               ...body...
   *               (if (cond)
   *                   (...then_instrs...)
   *                 (...else_instrs...)))
   *            (...else_instrs...)))
   *       (...else_instrs))
   */
  void
  loop_unroll_visitor::complex_unroll(ir_loop *ir, int iterations,
-                                    bool continue_from_then_branch)
+                                    bool continue_from_then_branch,
+                                    bool extra_interation_required,

*iteration


+                                    bool lt_continue_from_then_branch)
  {
     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_interation_required)
+      iterations++;
+
     for (int i = 0; i < iterations; i++) {
        exec_list copy_list;
        copy_list.make_empty();
        clone_ir_list(mem_ctx, &copy_list, &ir->body_instructions);
        ir_if *ir_if = ((ir_instruction *) 
copy_list.get_tail())->as_if();
        assert(ir_if != NULL);
+      exec_list *const lt_list = lt_continue_from_then_branch
+         ? &ir_if->then_instructions : &ir_if->else_instructions;
+      ir_if = ((ir_instruction *) lt_list->get_tail())->as_if();
+
        ir_to_replace->insert_before(&copy_list);
        ir_to_replace->remove();
        /* placeholder that will be removed in the next iteration */
        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 unknown_term_limit_list = 
(continue_from_then_branch)
           ? &ir_if->then_instructions : &ir_if->else_instructions;
-      list->push_tail(ir_to_replace);
+      unknown_term_limit_list->push_tail(ir_to_replace);
     }
     ir_to_replace->remove();
     this->progress = true;
  }
  /**
   * Move all of the instructions which follow \c ir_if to the end of
@@ -286,20 +348,35 @@ 
loop_unroll_visitor::splice_post_if_instructions(ir_if *ir_if,
                                                   exec_list 
*splice_dest)
  {
     while (!ir_if->get_next()->is_tail_sentinel()) {
        ir_instruction *move_ir = (ir_instruction *) ir_if->get_next();
        move_ir->remove();
        splice_dest->push_tail(move_ir);
     }
  }
+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;
+   }

Use exec_list::is_empty().

That is not what we are checking. We are checking if the exit branch 
contains 1 instruction (the break) or more instructions.



+
+   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.
      */
@@ -359,80 +436,106 @@ loop_unroll_visitor::visit_leave(ir_loop *ir)
     /* Note: the limiting terminator contributes 1 to 
ls->num_loop_jumps.
      * We'll be removing the limiting terminator before we unroll.
      */
     assert(ls->num_loop_jumps > 0);
     unsigned predicted_num_loop_jumps = ls->num_loop_jumps - 1;
     if (predicted_num_loop_jumps > 1)
        return visit_continue;
     if (predicted_num_loop_jumps == 0) {
-      ls->limiting_terminator->ir->remove();
        simple_unroll(ir, iterations);
        return visit_continue;
     }
     ir_instruction *last_ir = (ir_instruction *) 
ir->body_instructions.get_tail();
     assert(last_ir != NULL);
     if (is_break(last_ir)) {
        /* If the only loop-jump is a break at the end of the loop, 
the loop
         * will execute exactly once.  Remove the break and use the 
simple
         * unroller with an iteration count of 1.
         */
        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)
+   /* Remove unreachable terminators from the list */
+   unsigned term_count = 0;
+   foreach_in_list_safe(loop_terminator, t, &ls->terminators) {
+      if (t->iterations >= ls->limiting_terminator->iterations &&
+          t != ls->limiting_terminator) {
+         t->remove();
           continue;
+      }
+      term_count++;
+   }

Shouldn't that happen during loop analysis?

Yeah. It should be done in loop_control.cpp (where its updated in pacth 
1) as this is where the terminator is deleted. TBH I'm not sure why that 
extra control visitor needs to exist at all but I'd rather leave it as 
is for now as I don't really have much time to work on GLSL IR at the 
moment. Our focus is shifting to RADV for the immediate future.

I'd like to get this series in as it should be quite helpful but I don't 
really see it happening if I need to spend a large amount of time 
re-factoring the code.

One thing I seem to have overlooked is making sure that if branches 
don't contain nested jumps and abort if they do. I'll need to update the 
analysis pass to do this and retest with CTS. I meant to do a full CTS 
test but seem to have forgotten this before sending.


Cheers,
Nicolai


+   assert(term_count == 2);
+
+   if (term_count != 2 || ls->num_loop_jumps != 2)
+      return visit_continue;
+
+   ir_instruction *first_ir =
+      (ir_instruction *) ir->body_instructions.get_head();
-      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();
+   term_count = 0;
+   bool lt_then_continue = false;
+   foreach_in_list(loop_terminator, t, &ls->terminators) {
+      assert(term_count < 2);
+      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,
+                                            lt_then_continue);
+            complex_unroll(ir, iterations, false,
+                           first_ir->as_if() != 
ls->limiting_terminator->ir ||
+                           ebi,
+                           lt_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) {
+               lt_then_continue = t == ls->limiting_terminator ?
+                  true : lt_then_continue;
+               bool ebi =
+ exit_branch_has_instructions(ls->limiting_terminator->ir,
+                                               lt_then_continue);
+               complex_unroll(ir, iterations, true,
+                              first_ir->as_if() != 
ls->limiting_terminator->ir ||
+                              ebi,
+                              lt_then_continue);
                 return visit_continue;
+            } else {
+               lt_then_continue = true;
              }
           }
        }
+
+      term_count++;
     }
     /* Did not find the break statement.  It must be in a complex 
if-nesting,
      * so don't try to unroll.
      */
     return visit_continue;
  }
  bool



_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev