X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fcompiler%2Fnir%2Fnir_control_flow.c;h=71a9806507218861f41de1e360ed9e98b872b9ba;hb=ce6f66242ad33be84c0a34519f18bdc15c195950;hp=a485e713fa4b37250acca9037a5f2e463b839525;hpb=8564916d01b31ca5665a27366e483738541ba5a3;p=mesa.git diff --git a/src/compiler/nir/nir_control_flow.c b/src/compiler/nir/nir_control_flow.c index a485e713fa4..71a98065072 100644 --- a/src/compiler/nir/nir_control_flow.c +++ b/src/compiler/nir/nir_control_flow.c @@ -39,21 +39,12 @@ * 3. Two basic blocks cannot be directly next to each other. * 4. If a basic block has a jump instruction, there must be only one and it * must be at the end of the block. - * 5. The CFG must always be connected - this means that we must insert a fake - * CFG edge for loops with no break statement. * * The purpose of the second one is so that we have places to insert code during * GCM, as well as eliminating the possibility of critical edges. */ /*@{*/ -static bool -block_ends_in_jump(nir_block *block) -{ - return !exec_list_is_empty(&block->instr_list) && - nir_block_last_instr(block)->type == nir_instr_type_jump; -} - static inline void block_add_pred(nir_block *block, nir_block *pred) { @@ -116,44 +107,20 @@ link_non_block_to_block(nir_cf_node *node, nir_block *block) nir_if *if_stmt = nir_cf_node_as_if(node); - nir_cf_node *last_then = nir_if_last_then_node(if_stmt); - assert(last_then->type == nir_cf_node_block); - nir_block *last_then_block = nir_cf_node_as_block(last_then); - - nir_cf_node *last_else = nir_if_last_else_node(if_stmt); - assert(last_else->type == nir_cf_node_block); - nir_block *last_else_block = nir_cf_node_as_block(last_else); + nir_block *last_then_block = nir_if_last_then_block(if_stmt); + nir_block *last_else_block = nir_if_last_else_block(if_stmt); - if (!block_ends_in_jump(last_then_block)) { + if (!nir_block_ends_in_jump(last_then_block)) { unlink_block_successors(last_then_block); link_blocks(last_then_block, block, NULL); } - if (!block_ends_in_jump(last_else_block)) { + if (!nir_block_ends_in_jump(last_else_block)) { unlink_block_successors(last_else_block); link_blocks(last_else_block, block, NULL); } } else { assert(node->type == nir_cf_node_loop); - - /* - * We can only get to this codepath if we're inserting a new loop, or - * at least a loop with no break statements; we can't insert break - * statements into a loop when we haven't inserted it into the CFG - * because we wouldn't know which block comes after the loop - * and therefore, which block should be the successor of the block with - * the break). Therefore, we need to insert a fake edge (see invariant - * #5). - */ - - nir_loop *loop = nir_cf_node_as_loop(node); - - nir_cf_node *last = nir_loop_last_cf_node(loop); - assert(last->type == nir_cf_node_block); - nir_block *last_block = nir_cf_node_as_block(last); - - last_block->successors[1] = block; - block_add_pred(block, last_block); } } @@ -168,30 +135,21 @@ link_block_to_non_block(nir_block *block, nir_cf_node *node) nir_if *if_stmt = nir_cf_node_as_if(node); - nir_cf_node *first_then = nir_if_first_then_node(if_stmt); - assert(first_then->type == nir_cf_node_block); - nir_block *first_then_block = nir_cf_node_as_block(first_then); - - nir_cf_node *first_else = nir_if_first_else_node(if_stmt); - assert(first_else->type == nir_cf_node_block); - nir_block *first_else_block = nir_cf_node_as_block(first_else); + nir_block *first_then_block = nir_if_first_then_block(if_stmt); + nir_block *first_else_block = nir_if_first_else_block(if_stmt); unlink_block_successors(block); link_blocks(block, first_then_block, first_else_block); - } else { + } else if (node->type == nir_cf_node_loop) { /* * For similar reasons as the corresponding case in * link_non_block_to_block(), don't worry about if the loop header has * any predecessors that need to be unlinked. */ - assert(node->type == nir_cf_node_loop); - nir_loop *loop = nir_cf_node_as_loop(node); - nir_cf_node *loop_header = nir_loop_first_cf_node(loop); - assert(loop_header->type == nir_cf_node_block); - nir_block *loop_header_block = nir_cf_node_as_block(loop_header); + nir_block *loop_header_block = nir_loop_first_block(loop); unlink_block_successors(block); link_blocks(block, loop_header_block, NULL); @@ -231,15 +189,13 @@ split_block_beginning(nir_block *block) new_block->cf_node.parent = block->cf_node.parent; exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node); - struct set_entry *entry; set_foreach(block->predecessors, entry) { nir_block *pred = (nir_block *) entry->key; replace_successor(pred, block, new_block); } /* Any phi nodes must stay part of the new block, or else their - * sourcse will be messed up. This will reverse the order of the phi's, but - * order shouldn't matter. + * sources will be messed up. */ nir_foreach_instr_safe(instr, block) { if (instr->type != nir_instr_type_phi) @@ -247,7 +203,7 @@ split_block_beginning(nir_block *block) exec_node_remove(&instr->node); instr->block = new_block; - exec_list_push_head(&new_block->instr_list, &instr->node); + exec_list_push_tail(&new_block->instr_list, &instr->node); } return new_block; @@ -333,21 +289,17 @@ block_add_normal_succs(nir_block *block) nir_cf_node *parent = block->cf_node.parent; if (parent->type == nir_cf_node_if) { nir_cf_node *next = nir_cf_node_next(parent); - assert(next->type == nir_cf_node_block); nir_block *next_block = nir_cf_node_as_block(next); link_blocks(block, next_block, NULL); } else if (parent->type == nir_cf_node_loop) { nir_loop *loop = nir_cf_node_as_loop(parent); - nir_cf_node *head = nir_loop_first_cf_node(loop); - assert(head->type == nir_cf_node_block); - nir_block *head_block = nir_cf_node_as_block(head); + nir_block *head_block = nir_loop_first_block(loop); link_blocks(block, head_block, NULL); insert_phi_undef(head_block, block); } else { - assert(parent->type == nir_cf_node_function); nir_function_impl *impl = nir_cf_node_as_function(parent); link_blocks(block, impl->end_block, NULL); } @@ -356,22 +308,14 @@ block_add_normal_succs(nir_block *block) if (next->type == nir_cf_node_if) { nir_if *next_if = nir_cf_node_as_if(next); - nir_cf_node *first_then = nir_if_first_then_node(next_if); - assert(first_then->type == nir_cf_node_block); - nir_block *first_then_block = nir_cf_node_as_block(first_then); - - nir_cf_node *first_else = nir_if_first_else_node(next_if); - assert(first_else->type == nir_cf_node_block); - nir_block *first_else_block = nir_cf_node_as_block(first_else); + nir_block *first_then_block = nir_if_first_then_block(next_if); + nir_block *first_else_block = nir_if_first_else_block(next_if); link_blocks(block, first_then_block, first_else_block); - } else { - assert(next->type == nir_cf_node_loop); + } else if (next->type == nir_cf_node_loop) { nir_loop *next_loop = nir_cf_node_as_loop(next); - nir_cf_node *first = nir_loop_first_cf_node(next_loop); - assert(first->type == nir_cf_node_block); - nir_block *first_block = nir_cf_node_as_block(first); + nir_block *first_block = nir_loop_first_block(next_loop); link_blocks(block, first_block, NULL); insert_phi_undef(first_block, block); @@ -386,7 +330,7 @@ split_block_end(nir_block *block) new_block->cf_node.parent = block->cf_node.parent; exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node); - if (block_ends_in_jump(block)) { + if (nir_block_ends_in_jump(block)) { /* Figure out what successor block would've had if it didn't have a jump * instruction, and make new_block have that successor. */ @@ -491,6 +435,23 @@ nearest_loop(nir_cf_node *node) return nir_cf_node_as_loop(node); } +static void +remove_phi_src(nir_block *block, nir_block *pred) +{ + nir_foreach_instr(instr, block) { + if (instr->type != nir_instr_type_phi) + break; + + nir_phi_instr *phi = nir_instr_as_phi(instr); + nir_foreach_phi_src_safe(src, phi) { + if (src->pred == pred) { + list_del(&src->src.use_link); + exec_node_remove(&src->node); + } + } + } +} + /* * update the CFG after a jump instruction has been added to the end of a block */ @@ -501,65 +462,55 @@ nir_handle_add_jump(nir_block *block) nir_instr *instr = nir_block_last_instr(block); nir_jump_instr *jump_instr = nir_instr_as_jump(instr); + if (block->successors[0]) + remove_phi_src(block->successors[0], block); + if (block->successors[1]) + remove_phi_src(block->successors[1], block); unlink_block_successors(block); nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); nir_metadata_preserve(impl, nir_metadata_none); - if (jump_instr->type == nir_jump_break || - jump_instr->type == nir_jump_continue) { + switch (jump_instr->type) { + case nir_jump_return: + link_blocks(block, impl->end_block, NULL); + break; + + case nir_jump_break: { nir_loop *loop = nearest_loop(&block->cf_node); + nir_cf_node *after = nir_cf_node_next(&loop->cf_node); + nir_block *after_block = nir_cf_node_as_block(after); + link_blocks(block, after_block, NULL); + break; + } - if (jump_instr->type == nir_jump_continue) { - nir_cf_node *first_node = nir_loop_first_cf_node(loop); - assert(first_node->type == nir_cf_node_block); - nir_block *first_block = nir_cf_node_as_block(first_node); - link_blocks(block, first_block, NULL); - } else { - nir_cf_node *after = nir_cf_node_next(&loop->cf_node); - assert(after->type == nir_cf_node_block); - nir_block *after_block = nir_cf_node_as_block(after); - link_blocks(block, after_block, NULL); - - /* If we inserted a fake link, remove it */ - nir_cf_node *last = nir_loop_last_cf_node(loop); - assert(last->type == nir_cf_node_block); - nir_block *last_block = nir_cf_node_as_block(last); - if (last_block->successors[1] != NULL) - unlink_blocks(last_block, after_block); - } - } else { - assert(jump_instr->type == nir_jump_return); - link_blocks(block, impl->end_block, NULL); + case nir_jump_continue: { + nir_loop *loop = nearest_loop(&block->cf_node); + nir_block *first_block = nir_loop_first_block(loop); + link_blocks(block, first_block, NULL); + break; } -} -static void -remove_phi_src(nir_block *block, nir_block *pred) -{ - nir_foreach_instr(instr, block) { - if (instr->type != nir_instr_type_phi) - break; + case nir_jump_goto: + link_blocks(block, jump_instr->target, NULL); + break; - nir_phi_instr *phi = nir_instr_as_phi(instr); - nir_foreach_phi_src_safe(src, phi) { - if (src->pred == pred) { - list_del(&src->src.use_link); - exec_node_remove(&src->node); - } - } + case nir_jump_goto_if: + link_blocks(block, jump_instr->else_target, jump_instr->target); + break; + + default: + unreachable("Invalid jump type"); } } -/* Removes the successor of a block with a jump, and inserts a fake edge for - * infinite loops. Note that the jump to be eliminated may be free-floating. +/* Removes the successor of a block with a jump. Note that the jump to be + * eliminated may be free-floating. */ static void unlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors) { - nir_block *next = block->successors[0]; - if (block->successors[0]) remove_phi_src(block->successors[0], block); if (block->successors[1]) @@ -568,33 +519,6 @@ unlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors) unlink_block_successors(block); if (add_normal_successors) block_add_normal_succs(block); - - /* If we've just removed a break, and the block we were jumping to (after - * the loop) now has zero predecessors, we've created a new infinite loop. - * - * NIR doesn't allow blocks (other than the start block) to have zero - * predecessors. In particular, dominance assumes all blocks are reachable. - * So, we insert a "fake link" by making successors[1] point after the loop. - * - * Note that we have to do this after unlinking/recreating the block's - * successors. If we removed a "break" at the end of the loop, then - * block == last_block, so block->successors[0] would already be "next", - * and adding a fake link would create two identical successors. Doing - * this afterward works, as we'll have changed block->successors[0] to - * be the top of the loop. - */ - if (type == nir_jump_break && next->predecessors->entries == 0) { - nir_loop *loop = - nir_cf_node_as_loop(nir_cf_node_prev(&next->cf_node)); - - /* insert fake link */ - nir_cf_node *last = nir_loop_last_cf_node(loop); - assert(last->type == nir_cf_node_block); - nir_block *last_block = nir_cf_node_as_block(last); - - last_block->successors[1] = next; - block_add_pred(next, last_block); - } } void @@ -639,7 +563,7 @@ stitch_blocks(nir_block *before, nir_block *after) * TODO: special case when before is empty and after isn't? */ - if (block_ends_in_jump(before)) { + if (nir_block_ends_in_jump(before)) { assert(exec_list_is_empty(&after->instr_list)); if (after->successors[0]) remove_phi_src(after->successors[0], after); @@ -674,7 +598,7 @@ nir_cf_node_insert(nir_cursor cursor, nir_cf_node *node) * already been setup with the correct successors, so we need to set * up jumps here as the block is being inserted. */ - if (block_ends_in_jump(block)) + if (nir_block_ends_in_jump(block)) nir_handle_add_jump(block); stitch_blocks(block, after); @@ -708,8 +632,10 @@ cleanup_cf_node(nir_cf_node *node, nir_function_impl *impl) /* We need to walk the instructions and clean up defs/uses */ nir_foreach_instr_safe(instr, block) { if (instr->type == nir_instr_type_jump) { - nir_jump_type jump_type = nir_instr_as_jump(instr)->type; - unlink_jump(block, jump_type, false); + nir_jump_instr *jump = nir_instr_as_jump(instr); + unlink_jump(block, jump->type, false); + if (jump->type == nir_jump_goto_if) + nir_instr_rewrite_src(instr, &jump->condition, NIR_SRC_INIT); } else { nir_foreach_ssa_def(instr, replace_ssa_def_uses, impl); nir_instr_remove(instr);