nir_control_flow.c revision fc7f2d2364a98d4ec8fb8627b03c6f84b353998c
1b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* 2b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Copyright © 2014 Intel Corporation 3b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 4b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Permission is hereby granted, free of charge, to any person obtaining a 5b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * copy of this software and associated documentation files (the "Software"), 6b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * to deal in the Software without restriction, including without limitation 7b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * and/or sell copies of the Software, and to permit persons to whom the 9b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Software is furnished to do so, subject to the following conditions: 10b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 11b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * The above copyright notice and this permission notice (including the next 12b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * paragraph) shall be included in all copies or substantial portions of the 13b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Software. 14b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 15b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * IN THE SOFTWARE. 22b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 23b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Authors: 24b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Connor Abbott (cwabbott0@gmail.com) 25b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 26b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 27b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 28b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott#include "nir_control_flow_private.h" 29b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 30b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 31b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * \name Control flow modification 32b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 33b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * These functions modify the control flow tree while keeping the control flow 34b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * graph up-to-date. The invariants respected are: 35b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 1. Each then statement, else statement, or loop body must have at least one 36b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * control flow node. 37b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 2. Each if-statement and loop must have one basic block before it and one 38b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * after. 39b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 3. Two basic blocks cannot be directly next to each other. 40b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 4. If a basic block has a jump instruction, there must be only one and it 41b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * must be at the end of the block. 42b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 5. The CFG must always be connected - this means that we must insert a fake 43b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * CFG edge for loops with no break statement. 44b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 45b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * The purpose of the second one is so that we have places to insert code during 46b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * GCM, as well as eliminating the possibility of critical edges. 47b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 48b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/*@{*/ 49b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 50b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic inline void 51b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottblock_add_pred(nir_block *block, nir_block *pred) 52b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 53b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott _mesa_set_add(block->predecessors, pred); 54b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 55b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 56b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 57b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_blocks(nir_block *pred, nir_block *succ1, nir_block *succ2) 58b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 59b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[0] = succ1; 606f5c81f86f9b1b08b57435562be657fb2d220408Connor Abbott if (succ1 != NULL) 616f5c81f86f9b1b08b57435562be657fb2d220408Connor Abbott block_add_pred(succ1, pred); 62b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 63b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = succ2; 64b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ2 != NULL) 65b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott block_add_pred(succ2, pred); 66b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 67b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 68b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 69b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottunlink_blocks(nir_block *pred, nir_block *succ) 70b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 71b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (pred->successors[0] == succ) { 72b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[0] = pred->successors[1]; 73b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = NULL; 74b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 75b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(pred->successors[1] == succ); 76b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = NULL; 77b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 78b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 79b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott struct set_entry *entry = _mesa_set_search(succ->predecessors, pred); 80b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 81b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(entry); 82b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 83b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott _mesa_set_remove(succ->predecessors, entry); 84b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 85b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 86b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 87b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottunlink_block_successors(nir_block *block) 88b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 89b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (block->successors[0] != NULL) 90b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(block, block->successors[0]); 91b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (block->successors[1] != NULL) 92b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(block, block->successors[1]); 93b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 94b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 95b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 96b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_non_block_to_block(nir_cf_node *node, nir_block *block) 97b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 98b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_if) { 99b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 100b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We're trying to link an if to a block after it; this just means linking 101b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the last block of the then and else branches. 102b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 103b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 104b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 105b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 106b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last_then = nir_if_last_then_node(if_stmt); 107b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last_then->type == nir_cf_node_block); 108b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_then_block = nir_cf_node_as_block(last_then); 109b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 110b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last_else = nir_if_last_else_node(if_stmt); 111b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last_else->type == nir_cf_node_block); 112b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_else_block = nir_cf_node_as_block(last_else); 113b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 114b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (exec_list_is_empty(&last_then_block->instr_list) || 115b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block_last_instr(last_then_block)->type != nir_instr_type_jump) { 116b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(last_then_block); 117b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(last_then_block, block, NULL); 118b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 119b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 120b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (exec_list_is_empty(&last_else_block->instr_list) || 121b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block_last_instr(last_else_block)->type != nir_instr_type_jump) { 122b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(last_else_block); 123b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(last_else_block, block, NULL); 124b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 125b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 126b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(node->type == nir_cf_node_loop); 127b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 128b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 129b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We can only get to this codepath if we're inserting a new loop, or 130b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * at least a loop with no break statements; we can't insert break 131b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * statements into a loop when we haven't inserted it into the CFG 132b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * because we wouldn't know which block comes after the loop 133b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * and therefore, which block should be the successor of the block with 134b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the break). Therefore, we need to insert a fake edge (see invariant 135b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * #5). 136b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 137b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 138b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 139b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 140b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last = nir_loop_last_cf_node(loop); 141b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last->type == nir_cf_node_block); 142b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_block = nir_cf_node_as_block(last); 143b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 144b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott last_block->successors[1] = block; 145b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott block_add_pred(block, last_block); 146b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 147b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 148b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 149b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 150b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_block_to_non_block(nir_block *block, nir_cf_node *node) 151b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 152b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_if) { 153b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 154b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We're trying to link a block to an if after it; this just means linking 155b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the block to the first block of the then and else branches. 156b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 157b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 158b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 159b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 160b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *first_then = nir_if_first_then_node(if_stmt); 161b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(first_then->type == nir_cf_node_block); 162b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *first_then_block = nir_cf_node_as_block(first_then); 163b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 164b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *first_else = nir_if_first_else_node(if_stmt); 165b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(first_else->type == nir_cf_node_block); 166b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *first_else_block = nir_cf_node_as_block(first_else); 167b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 168b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 169b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, first_then_block, first_else_block); 170b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 171b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 172b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * For similar reasons as the corresponding case in 173b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * link_non_block_to_block(), don't worry about if the loop header has 174b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * any predecessors that need to be unlinked. 175b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 176b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 177b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(node->type == nir_cf_node_loop); 178b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 179b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 180b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 181b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *loop_header = nir_loop_first_cf_node(loop); 182b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(loop_header->type == nir_cf_node_block); 183b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *loop_header_block = nir_cf_node_as_block(loop_header); 184b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 185b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 186b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, loop_header_block, NULL); 187b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 188b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 189b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 190b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 191b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 192b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Takes a basic block and inserts a new empty basic block before it, making its 193b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * predecessors point to the new block. This essentially splits the block into 194b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * an empty header and a body so that another non-block CF node can be inserted 195b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * between the two. Note that this does *not* link the two basic blocks, so 196b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * some kind of cleanup *must* be performed after this call. 197b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 198b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 199b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_block * 200b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottsplit_block_beginning(nir_block *block) 201b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 202b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *new_block = nir_block_create(ralloc_parent(block)); 203b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott new_block->cf_node.parent = block->cf_node.parent; 204b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node); 205b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 206b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott struct set_entry *entry; 207b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott set_foreach(block->predecessors, entry) { 208b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *pred = (nir_block *) entry->key; 209b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 210b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(pred, block); 211b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(pred, new_block, NULL); 212b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 213b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 214788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott /* Any phi nodes must stay part of the new block, or else their 215788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott * sourcse will be messed up. This will reverse the order of the phi's, but 216788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott * order shouldn't matter. 217788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott */ 218788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott nir_foreach_instr_safe(block, instr) { 219788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott if (instr->type != nir_instr_type_phi) 220788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott break; 221788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott 222788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott exec_node_remove(&instr->node); 223788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott instr->block = new_block; 224788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott exec_list_push_head(&new_block->instr_list, &instr->node); 225788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott } 226788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott 227b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return new_block; 228b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 229b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 230b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 231b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottrewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred) 232b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 233b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_foreach_instr_safe(block, instr) { 234b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (instr->type != nir_instr_type_phi) 235b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 236b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 237b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 238b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_foreach_phi_src(phi, src) { 239b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (src->pred == old_pred) { 240b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott src->pred = new_pred; 241b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 242b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 243b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 244b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 245b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 246b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 247762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbottstatic void 248762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbottinsert_phi_undef(nir_block *block, nir_block *pred) 249762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott{ 250762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 251762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_foreach_instr(block, instr) { 252762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott if (instr->type != nir_instr_type_phi) 253762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott break; 254762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 255762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 256762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_ssa_undef_instr *undef = 257762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_ssa_undef_instr_create(ralloc_parent(phi), 258762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott phi->dest.ssa.num_components); 259762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 260762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_phi_src *src = ralloc(phi, nir_phi_src); 261762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->pred = pred; 262762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.parent_instr = &phi->instr; 263762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.is_ssa = true; 264762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.ssa = &undef->def; 265762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 266762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott list_addtail(&src->src.use_link, &undef->def.uses); 267762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 268762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott exec_list_push_tail(&phi->srcs, &src->node); 269762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott } 270762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott} 271762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 272b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 273b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Moves the successors of source to the successors of dest, leaving both 274b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * successors of source NULL. 275b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 276b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 277b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 278b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottmove_successors(nir_block *source, nir_block *dest) 279b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 280b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *succ1 = source->successors[0]; 281b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *succ2 = source->successors[1]; 282b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 283b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ1) { 284b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(source, succ1); 285b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott rewrite_phi_preds(succ1, source, dest); 286b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 287b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 288b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ2) { 289b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(source, succ2); 290b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott rewrite_phi_preds(succ2, source, dest); 291b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 292b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 293b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(dest); 294b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(dest, succ1, succ2); 295b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 296b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 297f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbottstatic bool 298f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbottblock_ends_in_jump(nir_block *block) 299f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbott{ 300f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbott return !exec_list_is_empty(&block->instr_list) && 301f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbott nir_block_last_instr(block)->type == nir_instr_type_jump; 302f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbott} 303f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbott 304f596e4021c4c1b2ce95ff32606e2f217955504bdConnor Abbott 305747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott/* Given a basic block with no successors that has been inserted into the 306747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * control flow tree, gives it the successors it would normally have assuming 307747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * it doesn't end in a jump instruction. Also inserts phi sources with undefs 308747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * if necessary. 309747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott */ 310747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottstatic void 311747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottblock_add_normal_succs(nir_block *block) 312747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 313747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (exec_node_is_tail_sentinel(block->cf_node.node.next)) { 314747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *parent = block->cf_node.parent; 315747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (parent->type == nir_cf_node_if) { 316747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *next = nir_cf_node_next(parent); 317747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(next->type == nir_cf_node_block); 318747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *next_block = nir_cf_node_as_block(next); 319747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 320747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, next_block, NULL); 321747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 322747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(parent->type == nir_cf_node_loop); 323747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(parent); 324747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 325747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *head = nir_loop_first_cf_node(loop); 326747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(head->type == nir_cf_node_block); 327747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *head_block = nir_cf_node_as_block(head); 328747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 329747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, head_block, NULL); 330747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott insert_phi_undef(head_block, block); 331747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 332747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 333747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *next = nir_cf_node_next(&block->cf_node); 334747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (next->type == nir_cf_node_if) { 335747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_if *next_if = nir_cf_node_as_if(next); 336747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 337747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *first_then = nir_if_first_then_node(next_if); 338747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(first_then->type == nir_cf_node_block); 339747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *first_then_block = nir_cf_node_as_block(first_then); 340747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 341747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *first_else = nir_if_first_else_node(next_if); 342747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(first_else->type == nir_cf_node_block); 343747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *first_else_block = nir_cf_node_as_block(first_else); 344747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 345747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, first_then_block, first_else_block); 346747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 347747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(next->type == nir_cf_node_loop); 348747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *next_loop = nir_cf_node_as_loop(next); 349747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 350747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *first = nir_loop_first_cf_node(next_loop); 351747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(first->type == nir_cf_node_block); 352747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *first_block = nir_cf_node_as_block(first); 353747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 354747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, first_block, NULL); 355747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott insert_phi_undef(first_block, block); 356747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 357747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 358747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott} 359747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 360b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_block * 361b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottsplit_block_end(nir_block *block) 362b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 363b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *new_block = nir_block_create(ralloc_parent(block)); 364b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott new_block->cf_node.parent = block->cf_node.parent; 365b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node); 366b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 367940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott if (block_ends_in_jump(block)) { 368940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott /* Figure out what successor block would've had if it didn't have a jump 369940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott * instruction, and make new_block have that successor. 370940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott */ 371940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott block_add_normal_succs(new_block); 372940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott } else { 373940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott move_successors(block, new_block); 374940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott } 375b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 376b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return new_block; 377b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 378b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 37958a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbottstatic nir_block * 38058a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbottsplit_block_before_instr(nir_instr *instr) 38158a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott{ 38258a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott assert(instr->type != nir_instr_type_phi); 38358a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott nir_block *new_block = split_block_beginning(instr->block); 38458a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 38558a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott nir_foreach_instr_safe(instr->block, cur_instr) { 38658a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott if (cur_instr == instr) 38758a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott break; 38858a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 38958a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott exec_node_remove(&cur_instr->node); 39058a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott cur_instr->block = new_block; 39158a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott exec_list_push_tail(&new_block->instr_list, &cur_instr->node); 39258a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott } 39358a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 39458a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott return new_block; 39558a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott} 39658a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 397d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott/* Splits a basic block at the point specified by the cursor. The "before" and 398d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * "after" arguments are filled out with the blocks resulting from the split 399d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * if non-NULL. Note that the "beginning" of the block is actually interpreted 400d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * as before the first non-phi instruction, and it's illegal to split a block 401d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * before a phi instruction. 402d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott */ 403d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 404d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbottstatic void 405d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbottsplit_block_cursor(nir_cursor cursor, 406d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott nir_block **_before, nir_block **_after) 407d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott{ 408d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott nir_block *before, *after; 409d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott switch (cursor.option) { 410d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_before_block: 411d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.block; 412d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_beginning(cursor.block); 413d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 414d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 415d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_after_block: 416d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = cursor.block; 417d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = split_block_end(cursor.block); 418d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 419d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 420d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_before_instr: 421d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.instr->block; 422d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_before_instr(cursor.instr); 423d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 424d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 425d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_after_instr: 426d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott /* We lower this to split_block_before_instr() so that we can keep the 427d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * after-a-jump-instr case contained to split_block_end(). 428d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott */ 429d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (nir_instr_is_last(cursor.instr)) { 430d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = cursor.instr->block; 431d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = split_block_end(cursor.instr->block); 432d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } else { 433d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.instr->block; 434d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_before_instr(nir_instr_next(cursor.instr)); 435d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } 436d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 437d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } 438d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 439d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (_before) 440d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott *_before = before; 441d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (_after) 442d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott *_after = after; 443d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott} 444d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 445b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 446b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Inserts a non-basic block between two basic blocks and links them together. 447b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 448b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 449b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 450b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottinsert_non_block(nir_block *before, nir_cf_node *node, nir_block *after) 451b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 452b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott node->parent = before->cf_node.parent; 453b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_after(&before->cf_node.node, &node->node); 454b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_block_to_non_block(before, node); 455b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_non_block_to_block(node, after); 456b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 457b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 458b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* walk up the control flow tree to find the innermost enclosed loop */ 459b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_loop * 460b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnearest_loop(nir_cf_node *node) 461b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 462b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott while (node->type != nir_cf_node_loop) { 463b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott node = node->parent; 464b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 465b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 466b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return nir_cf_node_as_loop(node); 467b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 468b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 469b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* 470b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * update the CFG after a jump instruction has been added to the end of a block 471b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 472b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 473b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottvoid 474b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnir_handle_add_jump(nir_block *block) 475b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 476b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_instr *instr = nir_block_last_instr(block); 477b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_jump_instr *jump_instr = nir_instr_as_jump(instr); 478b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 479b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 480b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 481b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 482b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 483b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 484b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (jump_instr->type == nir_jump_break || 485b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott jump_instr->type == nir_jump_continue) { 486b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nearest_loop(&block->cf_node); 487b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 488b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (jump_instr->type == nir_jump_continue) { 489b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *first_node = nir_loop_first_cf_node(loop); 490b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(first_node->type == nir_cf_node_block); 491b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *first_block = nir_cf_node_as_block(first_node); 492b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, first_block, NULL); 493b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 494b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *after = nir_cf_node_next(&loop->cf_node); 495b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(after->type == nir_cf_node_block); 496b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *after_block = nir_cf_node_as_block(after); 497b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, after_block, NULL); 498b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 499b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* If we inserted a fake link, remove it */ 500b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last = nir_loop_last_cf_node(loop); 501b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last->type == nir_cf_node_block); 502b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_block = nir_cf_node_as_block(last); 503b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (last_block->successors[1] != NULL) 504b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(last_block, after_block); 505b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 506b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 507b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(jump_instr->type == nir_jump_return); 508b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, impl->end_block, NULL); 509b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 510b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 511b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 51213482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbottstatic void 51313482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbottremove_phi_src(nir_block *block, nir_block *pred) 51413482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott{ 51513482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott nir_foreach_instr(block, instr) { 51613482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott if (instr->type != nir_instr_type_phi) 51713482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott break; 51813482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott 51913482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 52013482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott nir_foreach_phi_src_safe(phi, src) { 52113482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott if (src->pred == pred) { 52213482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott list_del(&src->src.use_link); 52313482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott exec_node_remove(&src->node); 52413482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 52513482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 52613482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 52713482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott} 52813482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott 529747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott/* Removes the successor of a block with a jump, and inserts a fake edge for 530747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * infinite loops. Note that the jump to be eliminated may be free-floating. 531747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott */ 532b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 533747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottstatic 534747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottvoid unlink_jump(nir_block *block, nir_jump_type type) 535747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 536747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (block->successors[0]) 537747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott remove_phi_src(block->successors[0], block); 538747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (block->successors[1]) 539747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott remove_phi_src(block->successors[1], block); 540b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 541b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (type == nir_jump_break) { 542747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *next = block->successors[0]; 543b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 544747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (next->predecessors->entries == 1) { 545747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *loop = 546747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node_as_loop(nir_cf_node_prev(&next->cf_node)); 547b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 548b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* insert fake link */ 549b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last = nir_loop_last_cf_node(loop); 550b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last->type == nir_cf_node_block); 551b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_block = nir_cf_node_as_block(last); 552b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 553747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott last_block->successors[1] = next; 554747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott block_add_pred(next, last_block); 555b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 556b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 557b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 558747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott unlink_block_successors(block); 559747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott} 560747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 561747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottvoid 562747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottnir_handle_remove_jump(nir_block *block, nir_jump_type type) 563747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 564747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott unlink_jump(block, type); 565747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 566747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott block_add_normal_succs(block); 567747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 568b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 569b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 570b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 571b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 572b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 573b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottupdate_if_uses(nir_cf_node *node) 574b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 575b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type != nir_cf_node_if) 576b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return; 577b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 578b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 579b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 580b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if_stmt->condition.parent_if = if_stmt; 581b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (if_stmt->condition.is_ssa) { 582b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_addtail(&if_stmt->condition.use_link, 583b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott &if_stmt->condition.ssa->if_uses); 584b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 585b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_addtail(&if_stmt->condition.use_link, 586b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott &if_stmt->condition.reg.reg->if_uses); 587b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 588b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 589b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 590b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 591b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Stitch two basic blocks together into one. The aggregate must have the same 592b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * predecessors as the first and the same successors as the second. 593b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 594b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 595b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 596b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstitch_blocks(nir_block *before, nir_block *after) 597b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 598b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 599b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We move after into before, so we have to deal with up to 2 successors vs. 600b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * possibly a large number of predecessors. 601b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 602b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * TODO: special case when before is empty and after isn't? 603b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 604b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 605633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (block_ends_in_jump(before)) { 606633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott assert(exec_list_is_empty(&after->instr_list)); 607633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (after->successors[0]) 608633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott remove_phi_src(after->successors[0], after); 609633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (after->successors[1]) 610633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott remove_phi_src(after->successors[1], after); 611633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott unlink_block_successors(after); 612633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_node_remove(&after->cf_node.node); 613633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } else { 614633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott move_successors(after, before); 615b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 616633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott foreach_list_typed(nir_instr, instr, node, &after->instr_list) { 617633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott instr->block = before; 618633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } 619b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 620633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_list_append(&before->instr_list, &after->instr_list); 621633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_node_remove(&after->cf_node.node); 622633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } 623b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 624b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 625476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbottvoid 626476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbottnir_cf_node_insert(nir_cursor cursor, nir_cf_node *node) 627476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott{ 628476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_block *before, *after; 629476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 630476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott split_block_cursor(cursor, &before, &after); 631476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 632476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott if (node->type == nir_cf_node_block) { 633476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_block *block = nir_cf_node_as_block(node); 634476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott exec_node_insert_after(&before->cf_node.node, &block->cf_node.node); 635476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott block->cf_node.parent = before->cf_node.parent; 636476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott /* stitch_blocks() assumes that any block that ends with a jump has 637476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott * already been setup with the correct successors, so we need to set 638476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott * up jumps here as the block is being inserted. 639476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott */ 640476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott if (block_ends_in_jump(block)) 641476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_handle_add_jump(block); 642476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 643476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott stitch_blocks(block, after); 644476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott stitch_blocks(before, block); 645476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott } else { 646476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott update_if_uses(node); 647476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott insert_non_block(before, node, after); 648476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott } 649476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott} 650476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 651211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottstatic bool 652211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottreplace_ssa_def_uses(nir_ssa_def *def, void *void_impl) 653211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott{ 654211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_function_impl *impl = void_impl; 655211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott void *mem_ctx = ralloc_parent(impl); 656211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott 657211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_ssa_undef_instr *undef = 658211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_ssa_undef_instr_create(mem_ctx, def->num_components); 659211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 660211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(&undef->def), mem_ctx); 661211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott return true; 662211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott} 663b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 664b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 665211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottcleanup_cf_node(nir_cf_node *node, nir_function_impl *impl) 666b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 667b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott switch (node->type) { 668b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_block: { 669b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *block = nir_cf_node_as_block(node); 670b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* We need to walk the instructions and clean up defs/uses */ 671211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_foreach_instr_safe(block, instr) { 6726d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott if (instr->type == nir_instr_type_jump) { 6736d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott nir_jump_type jump_type = nir_instr_as_jump(instr)->type; 6746d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott unlink_jump(block, jump_type); 6756d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott } else { 676211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_foreach_ssa_def(instr, replace_ssa_def_uses, impl); 677b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_instr_remove(instr); 678211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott } 679211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott } 680b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 681b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 682b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 683b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_if: { 684b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 685b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list) 686211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 687b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list) 688211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 689b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 690b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_del(&if_stmt->condition.use_link); 691b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 692b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 693b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 694b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_loop: { 695b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 696b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &loop->body) 697211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 698b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 699b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 700b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_function: { 701b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_as_function(node); 702b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &impl->body) 703211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 704b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 705b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 706b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott default: 707b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unreachable("Invalid CF node type"); 708b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 709b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 710b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 711b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottvoid 712b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnir_cf_node_remove(nir_cf_node *node) 713b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 714b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(node); 715b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 716b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 717b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_block) { 718b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 719b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Basic blocks can't really be removed by themselves, since they act as 720b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * padding between the non-basic blocks. So all we do here is empty the 721b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * block of instructions. 722b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 723b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * TODO: could we assert here? 724b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 725b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_list_make_empty(&nir_cf_node_as_block(node)->instr_list); 726b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 727b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *before = nir_cf_node_prev(node); 728b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(before->type == nir_cf_node_block); 729b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *before_block = nir_cf_node_as_block(before); 730b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 731b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *after = nir_cf_node_next(node); 732b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(after->type == nir_cf_node_block); 733b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *after_block = nir_cf_node_as_block(after); 734b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 735b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_remove(&node->node); 736b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott stitch_blocks(before_block, after_block); 737b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 738b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 739211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(node, impl); 740b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 741211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott 742fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 743fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_extract(nir_cf_list *extracted, nir_cursor begin, nir_cursor end) 744fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 745fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_block *block_begin, *block_end, *block_before, *block_after; 746fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 747fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott /* In the case where begin points to an instruction in some basic block and 748fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * end points to the end of the same basic block, we rely on the fact that 749fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * splitting on an instruction moves earlier instructions into a new basic 750fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * block. If the later instructions were moved instead, then the end cursor 751fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * would be pointing to the same place that begin used to point to, which 752fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * is obviously not what we want. 753fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott */ 754fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(begin, &block_before, &block_begin); 755fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(end, &block_end, &block_after); 756fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 757fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott extracted->impl = nir_cf_node_get_function(&block_begin->cf_node); 758fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_list_make_empty(&extracted->list); 759fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 760fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *cf_node = &block_begin->cf_node; 761fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *cf_node_end = &block_end->cf_node; 762fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott while (true) { 763fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *next = nir_cf_node_next(cf_node); 764fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 765fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_remove(&cf_node->node); 766fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cf_node->parent = NULL; 767fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_list_push_tail(&extracted->list, &cf_node->node); 768fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 769fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott if (cf_node == cf_node_end) 770fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott break; 771fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 772fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cf_node = next; 773fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 774fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 775fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(block_before, block_after); 776fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 777fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 778fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 779fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_reinsert(nir_cf_list *cf_list, nir_cursor cursor) 780fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 781fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_block *before, *after; 782fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 783fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(cursor, &before, &after); 784fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 785fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott foreach_list_typed_safe(nir_cf_node, node, node, &cf_list->list) { 786fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_remove(&node->node); 787fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott node->parent = before->cf_node.parent; 788fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_insert_node_before(&after->cf_node.node, &node->node); 789fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 790fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 791fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(before, 792fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node_as_block(nir_cf_node_next(&before->cf_node))); 793fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(nir_cf_node_as_block(nir_cf_node_prev(&after->cf_node)), 794fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott after); 795fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 796fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 797fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 798fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_delete(nir_cf_list *cf_list) 799fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 800fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott foreach_list_typed(nir_cf_node, node, node, &cf_list->list) { 801fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cleanup_cf_node(node, cf_list->impl); 802fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 803fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 804