/*
* Copyright © 2016 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 "nir.h"
#include "nir_builder.h"
#include "nir_control_flow.h"
#include "nir_loop_analyze.h"
/* This limit is chosen fairly arbitrarily. GLSL IR max iteration is 32
* instructions. (Multiply counting nodes and magic number 5.) But there is
* no 1:1 mapping between GLSL IR and NIR so 25 was picked because it seemed
* to give about the same results. Around 5 instructions per node. But some
* loops that would unroll with GLSL IR fail to unroll if we set this to 25 so
* we set it to 26.
* This was bumped to 96 because it unrolled more loops with a positive
* effect (vulkan ssao demo).
*/
#define LOOP_UNROLL_LIMIT 96
/* Prepare this loop for unrolling by first converting to lcssa and then
* converting the phis from the top level of the loop body to regs.
* Partially converting out of SSA allows us to unroll the loop without having
* to keep track of and update phis along the way which gets tricky and
* doesn't add much value over converting to regs.
*
* The loop may have a continue instruction at the end of the loop which does
* nothing. Once we're out of SSA, we can safely delete it so we don't have
* to deal with it later.
*/
static void
loop_prepare_for_unroll(nir_loop *loop)
{
nir_convert_loop_to_lcssa(loop);
/* Lower phis at the top level of the loop body */
foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {
if (nir_cf_node_block == node->type) {
nir_lower_phis_to_regs_block(nir_cf_node_as_block(node));
}
}
/* Lower phis after the loop */
nir_block *block_after_loop =
nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node));
nir_lower_phis_to_regs_block(block_after_loop);
/* Remove continue if its the last instruction in the loop */
nir_instr *last_instr = nir_block_last_instr(nir_loop_last_block(loop));
if (last_instr && last_instr->type == nir_instr_type_jump) {
assert(nir_instr_as_jump(last_instr)->type == nir_jump_continue);
nir_instr_remove(last_instr);
}
}
static void
get_first_blocks_in_terminator(nir_loop_terminator *term,
nir_block **first_break_block,
nir_block **first_continue_block)
{
if (term->continue_from_then) {
*first_continue_block = nir_if_first_then_block(term->nif);
*first_break_block = nir_if_first_else_block(term->nif);
} else {
*first_continue_block = nir_if_first_else_block(term->nif);
*first_break_block = nir_if_first_then_block(term->nif);
}
}
/**
* Unroll a loop where we know exactly how many iterations there are and there
* is only a single exit point. Note here we can unroll loops with multiple
* theoretical exits that only have a single terminating exit that we always
* know is the "real" exit.
*
* loop {
* ...instrs...
* }
*
* And the iteration count is 3, the output will be:
*
* ...instrs... ...instrs... ...instrs...
*/
static void
simple_unroll(nir_loop *loop)
{
nir_loop_terminator *limiting_term = loop->info->limiting_terminator;
assert(nir_is_trivial_loop_if(limiting_term->nif,
limiting_term->break_block));
loop_prepare_for_unroll(loop);
/* Skip over loop terminator and get the loop body. */
list_for_each_entry(nir_loop_terminator, terminator,
&loop->info->loop_terminator_list,
loop_terminator_link) {
/* Remove all but the limiting terminator as we know the other exit
* conditions can never be met. Note we need to extract any instructions
* in the continue from branch and insert then into the loop body before
* removing it.
*/
if (terminator->nif != limiting_term->nif) {
nir_block *first_break_block;
nir_block *first_continue_block;
get_first_blocks_in_terminator(terminator, &first_break_block,
&first_continue_block);
assert(nir_is_trivial_loop_if(terminator->nif,
terminator->break_block));
nir_cf_list continue_from_lst;
nir_cf_extract(&continue_from_lst,
nir_before_block(first_continue_block),
nir_after_block(terminator->continue_from_block));
nir_cf_reinsert(&continue_from_lst,
nir_after_cf_node(&terminator->nif->cf_node));
nir_cf_node_remove(&terminator->nif->cf_node);
}
}
nir_block *first_break_block;
nir_block *first_continue_block;
get_first_blocks_in_terminator(limiting_term, &first_break_block,
&first_continue_block);
/* Pluck out the loop header */
nir_block *header_blk = nir_loop_first_block(loop);
nir_cf_list lp_header;
nir_cf_extract(&lp_header, nir_before_block(header_blk),
nir_before_cf_node(&limiting_term->nif->cf_node));
/* Add the continue from block of the limiting terminator to the loop body
*/
nir_cf_list continue_from_lst;
nir_cf_extract(&continue_from_lst, nir_before_block(first_continue_block),
nir_after_block(limiting_term->continue_from_block));
nir_cf_reinsert(&continue_from_lst,
nir_after_cf_node(&limiting_term->nif->cf_node));
/* Pluck out the loop body */
nir_cf_list loop_body;
nir_cf_extract(&loop_body, nir_after_cf_node(&limiting_term->nif->cf_node),
nir_after_block(nir_loop_last_block(loop)));
struct hash_table *remap_table =
_mesa_hash_table_create(NULL, _mesa_hash_pointer,
_mesa_key_pointer_equal);
/* Clone the loop header */
nir_cf_list cloned_header;
nir_cf_list_clone(&cloned_header, &lp_header, loop->cf_node.parent,
remap_table);
/* Insert cloned loop header before the loop */
nir_cf_reinsert(&cloned_header, nir_before_cf_node(&loop->cf_node));
/* Temp list to store the cloned loop body as we unroll */
nir_cf_list unrolled_lp_body;
/* Clone loop header and append to the loop body */
for (unsigned i = 0; i < loop->info->trip_count; i++) {
/* Clone loop body */
nir_cf_list_clone(&unrolled_lp_body, &loop_body, loop->cf_node.parent,
remap_table);
/* Insert unrolled loop body before the loop */
nir_cf_reinsert(&unrolled_lp_body, nir_before_cf_node(&loop->cf_node));
/* Clone loop header */
nir_cf_list_clone(&cloned_header, &lp_header, loop->cf_node.parent,
remap_table);
/* Insert loop header after loop body */
nir_cf_reinsert(&cloned_header, nir_before_cf_node(&loop->cf_node));
}
/* Remove the break from the loop terminator and add instructions from
* the break block after the unrolled loop.
*/
nir_instr *break_instr = nir_block_last_instr(limiting_term->break_block);
nir_instr_remove(break_instr);
nir_cf_list break_list;
nir_cf_extract(&break_list, nir_before_block(first_break_block),
nir_after_block(limiting_term->break_block));
/* Clone so things get properly remapped */
nir_cf_list cloned_break_list;
nir_cf_list_clone(&cloned_break_list, &break_list, loop->cf_node.parent,
remap_table);
nir_cf_reinsert(&cloned_break_list, nir_before_cf_node(&loop->cf_node));
/* Remove the loop */
nir_cf_node_remove(&loop->cf_node);
/* Delete the original loop body, break block & header */
nir_cf_delete(&lp_header);
nir_cf_delete(&loop_body);
nir_cf_delete(&break_list);
_mesa_hash_table_destroy(remap_table, NULL);
}
static void
move_cf_list_into_loop_term(nir_cf_list *lst, nir_loop_terminator *term)
{
/* Move the rest of the loop inside the continue-from-block */
nir_cf_reinsert(lst, nir_after_block(term->continue_from_block));
/* Remove the break */
nir_instr_remove(nir_block_last_instr(term->break_block));
}
static nir_cursor
get_complex_unroll_insert_location(nir_cf_node *node, bool continue_from_then)
{
if (node->type == nir_cf_node_loop) {
return nir_before_cf_node(node);
} else {
nir_if *if_stmt = nir_cf_node_as_if(node);
if (continue_from_then) {
return nir_after_block(nir_if_last_then_block(if_stmt));
} else {
return nir_after_block(nir_if_last_else_block(if_stmt));
}
}
}
/**
* Unroll a loop with two exists when the trip count of one of the exits is
* unknown. If continue_from_then is true, the loop is repeated only when the
* "then" branch of the if is taken; otherwise it is repeated only
* when the "else" branch of the if is taken.
*
* For example, if the input is:
*
* loop {
* ...phis/condition...
* if condition {
* ...then instructions...
* } else {
* ...continue instructions...
* break
* }
* ...body...
* }
*
* And the iteration count is 3, and unlimit_term->continue_from_then is true,
* then the output will be:
*
* ...condition...
* if condition {
* ...then instructions...
* ...body...
* if condition {
* ...then instructions...
* ...body...
* if condition {
* ...then instructions...
* ...body...
* } else {
* ...continue instructions...
* }
* } else {
* ...continue instructions...
* }
* } else {
* ...continue instructions...
* }
*/
static void
complex_unroll(nir_loop *loop, nir_loop_terminator *unlimit_term,
bool limiting_term_second)
{
assert(nir_is_trivial_loop_if(unlimit_term->nif,
unlimit_term->break_block));
nir_loop_terminator *limiting_term = loop->info->limiting_terminator;
assert(nir_is_trivial_loop_if(limiting_term->nif,
limiting_term->break_block));
loop_prepare_for_unroll(loop);
nir_block *header_blk = nir_loop_first_block(loop);
nir_cf_list lp_header;
nir_cf_list limit_break_list;
unsigned num_times_to_clone;
if (limiting_term_second) {
/* Pluck out the loop header */
nir_cf_extract(&lp_header, nir_before_block(header_blk),
nir_before_cf_node(&unlimit_term->nif->cf_node));
/* We need some special handling when its the second terminator causing
* us to exit the loop for example:
*
* for (int i = 0; i < uniform_lp_count; i++) {
* colour = vec4(0.0, 1.0, 0.0, 1.0);
*
* if (i == 1) {
* break;
* }
* ... any further code is unreachable after i == 1 ...
* }
*/
nir_cf_list after_lt;
nir_if *limit_if = limiting_term->nif;
nir_cf_extract(&after_lt, nir_after_cf_node(&limit_if->cf_node),
nir_after_block(nir_loop_last_block(loop)));
move_cf_list_into_loop_term(&after_lt, limiting_term);
/* Because the trip count is the number of times we pass over the entire
* loop before hitting a break when the second terminator is the
* limiting terminator we can actually execute code inside the loop when
* trip count == 0 e.g. the code above the break. So we need to bump
* the trip_count in order for the code below to clone anything. When
* trip count == 1 we execute the code above the break twice and the
* code below it once so we need clone things twice and so on.
*/
num_times_to_clone = loop->info->trip_count + 1;
} else {
/* Pluck out the loop header */
nir_cf_extract(&lp_header, nir_before_block(header_blk),
nir_before_cf_node(&limiting_term->nif->cf_node));
nir_block *first_break_block;
nir_block *first_continue_block;
get_first_blocks_in_terminator(limiting_term, &first_break_block,
&first_continue_block);
/* Remove the break then extract instructions from the break block so we
* can insert them in the innermost else of the unrolled loop.
*/
nir_instr *break_instr = nir_block_last_instr(limiting_term->break_block);
nir_instr_remove(break_instr);
nir_cf_extract(&limit_break_list, nir_before_block(first_break_block),
nir_after_block(limiting_term->break_block));
nir_cf_list continue_list;
nir_cf_extract(&continue_list, nir_before_block(first_continue_block),
nir_after_block(limiting_term->continue_from_block));
nir_cf_reinsert(&continue_list,
nir_after_cf_node(&limiting_term->nif->cf_node));
nir_cf_node_remove(&limiting_term->nif->cf_node);
num_times_to_clone = loop->info->trip_count;
}
/* In the terminator that we have no trip count for move everything after
* the terminator into the continue from branch.
*/
nir_cf_list loop_end;
nir_cf_extract(&loop_end, nir_after_cf_node(&unlimit_term->nif->cf_node),
nir_after_block(nir_loop_last_block(loop)));
move_cf_list_into_loop_term(&loop_end, unlimit_term);
/* Pluck out the loop body. */
nir_cf_list loop_body;
nir_cf_extract(&loop_body, nir_before_block(nir_loop_first_block(loop)),
nir_after_block(nir_loop_last_block(loop)));
struct hash_table *remap_table =
_mesa_hash_table_create(NULL, _mesa_hash_pointer,
_mesa_key_pointer_equal);
/* Set unroll_loc to the loop as we will insert the unrolled loop before it
*/
nir_cf_node *unroll_loc = &loop->cf_node;
/* Temp lists to store the cloned loop as we unroll */
nir_cf_list unrolled_lp_body;
nir_cf_list cloned_header;
for (unsigned i = 0; i < num_times_to_clone; i++) {
/* Clone loop header */
nir_cf_list_clone(&cloned_header, &lp_header, loop->cf_node.parent,
remap_table);
nir_cursor cursor =
get_complex_unroll_insert_location(unroll_loc,
unlimit_term->continue_from_then);
/* Insert cloned loop header */
nir_cf_reinsert(&cloned_header, cursor);
cursor =
get_complex_unroll_insert_location(unroll_loc,
unlimit_term->continue_from_then);
/* Clone loop body */
nir_cf_list_clone(&unrolled_lp_body, &loop_body, loop->cf_node.parent,
remap_table);
unroll_loc = exec_node_data(nir_cf_node,
exec_list_get_tail(&unrolled_lp_body.list),
node);
assert(unroll_loc->type == nir_cf_node_block &&
exec_list_is_empty(&nir_cf_node_as_block(unroll_loc)->instr_list));
/* Get the unrolled if node */
unroll_loc = nir_cf_node_prev(unroll_loc);
/* Insert unrolled loop body */
nir_cf_reinsert(&unrolled_lp_body, cursor);
}
if (!limiting_term_second) {
assert(unroll_loc->type == nir_cf_node_if);
nir_cf_list_clone(&cloned_header, &lp_header, loop->cf_node.parent,
remap_table);
nir_cursor cursor =
get_complex_unroll_insert_location(unroll_loc,
unlimit_term->continue_from_then);
/* Insert cloned loop header */
nir_cf_reinsert(&cloned_header, cursor);
/* Clone so things get properly remapped, and insert break block from
* the limiting terminator.
*/
nir_cf_list cloned_break_blk;
nir_cf_list_clone(&cloned_break_blk, &limit_break_list,
loop->cf_node.parent, remap_table);
cursor =
get_complex_unroll_insert_location(unroll_loc,
unlimit_term->continue_from_then);
nir_cf_reinsert(&cloned_break_blk, cursor);
nir_cf_delete(&limit_break_list);
}
/* The loop has been unrolled so remove it. */
nir_cf_node_remove(&loop->cf_node);
/* Delete the original loop header and body */
nir_cf_delete(&lp_header);
nir_cf_delete(&loop_body);
_mesa_hash_table_destroy(remap_table, NULL);
}
static bool
is_loop_small_enough_to_unroll(nir_shader *shader, nir_loop_info *li)
{
unsigned max_iter = shader->options->max_unroll_iterations;
if (li->trip_count > max_iter)
return false;
if (li->force_unroll)
return true;
bool loop_not_too_large =
li->num_instructions * li->trip_count <= max_iter * LOOP_UNROLL_LIMIT;
return loop_not_too_large;
}
static bool
process_loops(nir_shader *sh, nir_cf_node *cf_node, bool *innermost_loop)
{
bool progress = false;
nir_loop *loop;
switch (cf_node->type) {
case nir_cf_node_block:
return progress;
case nir_cf_node_if: {
nir_if *if_stmt = nir_cf_node_as_if(cf_node);
foreach_list_typed_safe(nir_cf_node, nested_node, node, &if_stmt->then_list)
progress |= process_loops(sh, nested_node, innermost_loop);
foreach_list_typed_safe(nir_cf_node, nested_node, node, &if_stmt->else_list)
progress |= process_loops(sh, nested_node, innermost_loop);
return progress;
}
case nir_cf_node_loop: {
loop = nir_cf_node_as_loop(cf_node);
foreach_list_typed_safe(nir_cf_node, nested_node, node, &loop->body)
progress |= process_loops(sh, nested_node, innermost_loop);
break;
}
default:
unreachable("unknown cf node type");
}
if (*innermost_loop) {
/* Don't attempt to unroll outer loops or a second inner loop in
* this pass wait until the next pass as we have altered the cf.
*/
*innermost_loop = false;
if (loop->info->limiting_terminator == NULL)
return progress;
if (!is_loop_small_enough_to_unroll(sh, loop->info))
return progress;
if (loop->info->is_trip_count_known) {
simple_unroll(loop);
progress = true;
} else {
/* Attempt to unroll loops with two terminators. */
unsigned num_lt = list_length(&loop->info->loop_terminator_list);
if (num_lt == 2) {
bool limiting_term_second = true;
nir_loop_terminator *terminator =
list_last_entry(&loop->info->loop_terminator_list,
nir_loop_terminator, loop_terminator_link);
if (terminator->nif == loop->info->limiting_terminator->nif) {
limiting_term_second = false;
terminator =
list_first_entry(&loop->info->loop_terminator_list,
nir_loop_terminator, loop_terminator_link);
}
/* If the first terminator has a trip count of zero and is the
* limiting terminator just do a simple unroll as the second
* terminator can never be reached.
*/
if (loop->info->trip_count == 0 && !limiting_term_second) {
simple_unroll(loop);
} else {
complex_unroll(loop, terminator, limiting_term_second);
}
progress = true;
}
}
}
return progress;
}
static bool
nir_opt_loop_unroll_impl(nir_function_impl *impl,
nir_variable_mode indirect_mask)
{
bool progress = false;
nir_metadata_require(impl, nir_metadata_loop_analysis, indirect_mask);
nir_metadata_require(impl, nir_metadata_block_index);
foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {
bool innermost_loop = true;
progress |= process_loops(impl->function->shader, node,
&innermost_loop);
}
if (progress)
nir_lower_regs_to_ssa_impl(impl);
return progress;
}
bool
nir_opt_loop_unroll(nir_shader *shader, nir_variable_mode indirect_mask)
{
bool progress = false;
nir_foreach_function(function, shader) {
if (function->impl) {
progress |= nir_opt_loop_unroll_impl(function->impl, indirect_mask);
}
}
return progress;
}