Re: [Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
On 10/10/17 01:26, Nicolai Hähnle wrote:
On 21.09.2017 12:55, Timothy Arceri wrote:
The old code assumed that loop terminators will always be at
the start of the loop, resulting in otherwise unrollable
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.
V2:
- fixed regression where loops with a break in else were never
unrolled in v1.
- fixed confusing/wrong naming of bools in complex unrolling.
---
src/compiler/glsl/loop_analysis.cpp | 50 +--
src/compiler/glsl/loop_analysis.h | 5 +-
src/compiler/glsl/loop_unroll.cpp | 172
3 files changed, 161 insertions(+), 66 deletions(-)
diff --git a/src/compiler/glsl/loop_analysis.cpp
b/src/compiler/glsl/loop_analysis.cpp
index 78279844dc..5bf406e7ee 100644
--- a/src/compiler/glsl/loop_analysis.cpp
+++ b/src/compiler/glsl/loop_analysis.cpp
[snip]
@@ -778,41 +780,35 @@ get_basic_induction_increment(ir_assignment *ir,
hash_table *var_hash)
return inc;
}
/**
* Detect whether an if-statement is a loop terminating condition
Please update this part of the comment.
[snip]
diff --git a/src/compiler/glsl/loop_unroll.cpp
b/src/compiler/glsl/loop_unroll.cpp
index 358cbf10af..82931c9abf 100644
--- a/src/compiler/glsl/loop_unroll.cpp
+++ b/src/compiler/glsl/loop_unroll.cpp
[snip]
@@ -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 second_term_then_continue,
+ bool extra_interation_required,
s/interation/iteration/
I also wonder whether this parameter can't be folded into iterations?
It could but to avoid duplication of the comment below I think its best
to leave it in one place.
Thanks for the review! I know the unrolling code isn't the easiest to
follow :) I was worried I wouldn't find anyone to review these changes.
Thanks,
Tim
Cheers,
Nicolai
+ 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_interation_required)
+ iterations++;
+
for (int i = 0; i < iterations; i++) {
exec_list copy_list;
copy_list.make_empty();
clone_ir_list(mem_ctx, _list, >body_instructions);
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
+ ? _if->then_instructions : _if->else_instructions;
+ ir_if = ((ir_instruction *) first_list->get_tail())->as_if();
+
ir_to_replace->insert_before(_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 second_term_continue_list =
second_term_then_continue
? _if->then_instructions : _if->else_instructions;
- list->push_tail(ir_to_replace);
+ second_term_continue_list->push_tail(ir_to_replace);
}
ir_to_replace->remove();
this->progress = true;
}
/**
* Move all of the instructions
Re: [Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
On 21.09.2017 12:55, Timothy Arceri wrote:
The old code assumed that loop terminators will always be at
the start of the loop, resulting in otherwise unrollable
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.
V2:
- fixed regression where loops with a break in else were never
unrolled in v1.
- fixed confusing/wrong naming of bools in complex unrolling.
---
src/compiler/glsl/loop_analysis.cpp | 50 +--
src/compiler/glsl/loop_analysis.h | 5 +-
src/compiler/glsl/loop_unroll.cpp | 172
3 files changed, 161 insertions(+), 66 deletions(-)
diff --git a/src/compiler/glsl/loop_analysis.cpp
b/src/compiler/glsl/loop_analysis.cpp
index 78279844dc..5bf406e7ee 100644
--- a/src/compiler/glsl/loop_analysis.cpp
+++ b/src/compiler/glsl/loop_analysis.cpp
[snip]
@@ -778,41 +780,35 @@ get_basic_induction_increment(ir_assignment *ir,
hash_table *var_hash)
return inc;
}
/**
* Detect whether an if-statement is a loop terminating condition
Please update this part of the comment.
[snip]
diff --git a/src/compiler/glsl/loop_unroll.cpp
b/src/compiler/glsl/loop_unroll.cpp
index 358cbf10af..82931c9abf 100644
--- a/src/compiler/glsl/loop_unroll.cpp
+++ b/src/compiler/glsl/loop_unroll.cpp
[snip]
@@ -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 second_term_then_continue,
+bool extra_interation_required,
s/interation/iteration/
I also wonder whether this parameter can't be folded into iterations?
Cheers,
Nicolai
+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_interation_required)
+ iterations++;
+
for (int i = 0; i < iterations; i++) {
exec_list copy_list;
copy_list.make_empty();
clone_ir_list(mem_ctx, _list, >body_instructions);
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
+ ? _if->then_instructions : _if->else_instructions;
+ ir_if = ((ir_instruction *) first_list->get_tail())->as_if();
+
ir_to_replace->insert_before(_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 second_term_continue_list = second_term_then_continue
? _if->then_instructions : _if->else_instructions;
- list->push_tail(ir_to_replace);
+ second_term_continue_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()) {
Re: [Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
On 04/10/17 11:17, Timothy Arceri wrote:
Ping on patches 1 & 3
Ping again on these two.
Nicolai, I believe I've addressed all you feedback besides trying to add
a pass that flips the branches so that the break is always in the then
branch. I'd rather not spend to much more time on this code as it's
pretty much obsolete, if radeonsi switches to NIR it will only be used
by legacy drivers. I'm happy with the way it works now and I'm not
convinced handling the else branch is complex enough to mess around with
the additional lowering pass.
Tim
On 21/09/17 20:55, Timothy Arceri wrote:
The old code assumed that loop terminators will always be at
the start of the loop, resulting in otherwise unrollable
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.
V2:
- fixed regression where loops with a break in else were never
unrolled in v1.
- fixed confusing/wrong naming of bools in complex unrolling.
---
src/compiler/glsl/loop_analysis.cpp | 50 +--
src/compiler/glsl/loop_analysis.h | 5 +-
src/compiler/glsl/loop_unroll.cpp | 172
3 files changed, 161 insertions(+), 66 deletions(-)
diff --git a/src/compiler/glsl/loop_analysis.cpp
b/src/compiler/glsl/loop_analysis.cpp
index 78279844dc..5bf406e7ee 100644
--- a/src/compiler/glsl/loop_analysis.cpp
+++ b/src/compiler/glsl/loop_analysis.cpp
@@ -18,21 +18,21 @@
* 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 bool is_loop_terminator(ir_if *ir);
+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.
@@ -80,21 +80,21 @@ find_initial_value(ir_loop *loop, ir_variable *var)
break;
}
}
return NULL;
}
static int
calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue
*increment,
- enum ir_expression_operation op)
+ enum ir_expression_operation op, bool
continue_from_then)
{
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 =
@@ -147,22 +147,24 @@ calculate_iterations(ir_rvalue *from, ir_rvalue
*to, ir_rvalue *increment,
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 *const cmp =
+ ir_expression *cmp =
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;
}
}
@@ -299,26 +301,28 @@ loop_variable_state::insert(ir_variable *var)
lv->var = var;
_mesa_hash_table_insert(this->var_hash, lv->var, lv);
this->variables.push_tail(lv);
return lv;
}
loop_terminator *
Re: [Mesa-dev] [PATCH v2 3/3] glsl: make loop unrolling more like the nir unrolling path
Ping on patches 1 & 3
On 21/09/17 20:55, Timothy Arceri wrote:
The old code assumed that loop terminators will always be at
the start of the loop, resulting in otherwise unrollable
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.
V2:
- fixed regression where loops with a break in else were never
unrolled in v1.
- fixed confusing/wrong naming of bools in complex unrolling.
---
src/compiler/glsl/loop_analysis.cpp | 50 +--
src/compiler/glsl/loop_analysis.h | 5 +-
src/compiler/glsl/loop_unroll.cpp | 172
3 files changed, 161 insertions(+), 66 deletions(-)
diff --git a/src/compiler/glsl/loop_analysis.cpp
b/src/compiler/glsl/loop_analysis.cpp
index 78279844dc..5bf406e7ee 100644
--- a/src/compiler/glsl/loop_analysis.cpp
+++ b/src/compiler/glsl/loop_analysis.cpp
@@ -18,21 +18,21 @@
* 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 bool is_loop_terminator(ir_if *ir);
+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.
@@ -80,21 +80,21 @@ find_initial_value(ir_loop *loop, ir_variable *var)
break;
}
}
return NULL;
}
static int
calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
- enum ir_expression_operation op)
+ enum ir_expression_operation op, bool continue_from_then)
{
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 =
@@ -147,22 +147,24 @@ calculate_iterations(ir_rvalue *from, ir_rvalue *to,
ir_rvalue *increment,
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 *const cmp =
+ ir_expression *cmp =
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;
}
}
@@ -299,26 +301,28 @@ loop_variable_state::insert(ir_variable *var)
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)
+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
