nir_control_flow.c revision 707e72f13bb78869ee95d3286980bf1709cba6cf
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 504f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunkestatic bool 514f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunkeblock_ends_in_jump(nir_block *block) 524f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke{ 534f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke return !exec_list_is_empty(&block->instr_list) && 544f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke nir_block_last_instr(block)->type == nir_instr_type_jump; 554f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke} 564f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke 57b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic inline void 58b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottblock_add_pred(nir_block *block, nir_block *pred) 59b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 60b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott _mesa_set_add(block->predecessors, pred); 61b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 62b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 63e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunkestatic inline void 64e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunkeblock_remove_pred(nir_block *block, nir_block *pred) 65e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke{ 66e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke struct set_entry *entry = _mesa_set_search(block->predecessors, pred); 67e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke 68e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke assert(entry); 69e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke 70e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke _mesa_set_remove(block->predecessors, entry); 71e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke} 72e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke 73b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 74b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_blocks(nir_block *pred, nir_block *succ1, nir_block *succ2) 75b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 76b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[0] = succ1; 776f5c81f86f9b1b08b57435562be657fb2d220408Connor Abbott if (succ1 != NULL) 786f5c81f86f9b1b08b57435562be657fb2d220408Connor Abbott block_add_pred(succ1, pred); 79b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 80b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = succ2; 81b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ2 != NULL) 82b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott block_add_pred(succ2, pred); 83b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 84b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 85b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 86b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottunlink_blocks(nir_block *pred, nir_block *succ) 87b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 88b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (pred->successors[0] == succ) { 89b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[0] = pred->successors[1]; 90b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = NULL; 91b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 92b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(pred->successors[1] == succ); 93b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = NULL; 94b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 95b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 96e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke block_remove_pred(succ, pred); 97b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 98b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 99b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 100b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottunlink_block_successors(nir_block *block) 101b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 102b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (block->successors[1] != NULL) 103b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(block, block->successors[1]); 1046560838703431f89c47d68822758bc76fd34c355Kenneth Graunke if (block->successors[0] != NULL) 1056560838703431f89c47d68822758bc76fd34c355Kenneth Graunke unlink_blocks(block, block->successors[0]); 106b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 107b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 108b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 109b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_non_block_to_block(nir_cf_node *node, nir_block *block) 110b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 111b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_if) { 112b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 113b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We're trying to link an if to a block after it; this just means linking 114b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the last block of the then and else branches. 115b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 116b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 117b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 118b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 119b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last_then = nir_if_last_then_node(if_stmt); 120b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last_then->type == nir_cf_node_block); 121b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_then_block = nir_cf_node_as_block(last_then); 122b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 123b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last_else = nir_if_last_else_node(if_stmt); 124b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last_else->type == nir_cf_node_block); 125b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_else_block = nir_cf_node_as_block(last_else); 126b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1274f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke if (!block_ends_in_jump(last_then_block)) { 128b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(last_then_block); 129b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(last_then_block, block, NULL); 130b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 131b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1324f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke if (!block_ends_in_jump(last_else_block)) { 133b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(last_else_block); 134b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(last_else_block, block, NULL); 135b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 136b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 137b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(node->type == nir_cf_node_loop); 138b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 139b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 140b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We can only get to this codepath if we're inserting a new loop, or 141b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * at least a loop with no break statements; we can't insert break 142b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * statements into a loop when we haven't inserted it into the CFG 143b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * because we wouldn't know which block comes after the loop 144b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * and therefore, which block should be the successor of the block with 145b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the break). Therefore, we need to insert a fake edge (see invariant 146b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * #5). 147b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 148b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 149b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 150b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 151b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last = nir_loop_last_cf_node(loop); 152b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last->type == nir_cf_node_block); 153b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_block = nir_cf_node_as_block(last); 154b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 155b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott last_block->successors[1] = block; 156b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott block_add_pred(block, last_block); 157b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 158b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 159b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 160b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 161b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_block_to_non_block(nir_block *block, nir_cf_node *node) 162b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 163b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_if) { 164b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 165b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We're trying to link a block to an if after it; this just means linking 166b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the block to the first block of the then and else branches. 167b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 168b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 169b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 170b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 171b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *first_then = nir_if_first_then_node(if_stmt); 172b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(first_then->type == nir_cf_node_block); 173b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *first_then_block = nir_cf_node_as_block(first_then); 174b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 175b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *first_else = nir_if_first_else_node(if_stmt); 176b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(first_else->type == nir_cf_node_block); 177b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *first_else_block = nir_cf_node_as_block(first_else); 178b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 179b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 180b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, first_then_block, first_else_block); 181b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 182b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 183b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * For similar reasons as the corresponding case in 184b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * link_non_block_to_block(), don't worry about if the loop header has 185b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * any predecessors that need to be unlinked. 186b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 187b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 188b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(node->type == nir_cf_node_loop); 189b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 190b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 191b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 192b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *loop_header = nir_loop_first_cf_node(loop); 193b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(loop_header->type == nir_cf_node_block); 194b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *loop_header_block = nir_cf_node_as_block(loop_header); 195b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 196b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 197b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, loop_header_block, NULL); 198b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 199b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 200b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 201b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 202b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 2039674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke * Replace a block's successor with a different one. 2049674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke */ 2059674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunkestatic void 2069674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunkereplace_successor(nir_block *block, nir_block *old_succ, nir_block *new_succ) 2079674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke{ 2089674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke if (block->successors[0] == old_succ) { 2099674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block->successors[0] = new_succ; 2109674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke } else { 2119674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke assert(block->successors[1] == old_succ); 2129674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block->successors[1] = new_succ; 2139674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke } 2149674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke 2159674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block_remove_pred(old_succ, block); 2169674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block_add_pred(new_succ, block); 2179674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke} 2189674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke 2199674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke/** 220b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Takes a basic block and inserts a new empty basic block before it, making its 221b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * predecessors point to the new block. This essentially splits the block into 222b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * an empty header and a body so that another non-block CF node can be inserted 223b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * between the two. Note that this does *not* link the two basic blocks, so 224b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * some kind of cleanup *must* be performed after this call. 225b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 226b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 227b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_block * 228b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottsplit_block_beginning(nir_block *block) 229b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 230b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *new_block = nir_block_create(ralloc_parent(block)); 231b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott new_block->cf_node.parent = block->cf_node.parent; 232b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node); 233b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 234b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott struct set_entry *entry; 235b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott set_foreach(block->predecessors, entry) { 236b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *pred = (nir_block *) entry->key; 2379674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke replace_successor(pred, block, new_block); 238b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 239b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 240788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott /* Any phi nodes must stay part of the new block, or else their 241788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott * sourcse will be messed up. This will reverse the order of the phi's, but 242788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott * order shouldn't matter. 243788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott */ 244707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 245788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott if (instr->type != nir_instr_type_phi) 246788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott break; 247788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott 248788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott exec_node_remove(&instr->node); 249788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott instr->block = new_block; 250788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott exec_list_push_head(&new_block->instr_list, &instr->node); 251788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott } 252788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott 253b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return new_block; 254b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 255b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 256b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 257b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottrewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred) 258b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 259707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 260b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (instr->type != nir_instr_type_phi) 261b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 262b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 263b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 264b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_foreach_phi_src(phi, src) { 265b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (src->pred == old_pred) { 266b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott src->pred = new_pred; 267b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 268b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 269b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 270b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 271b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 272b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 273762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbottstatic void 274762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbottinsert_phi_undef(nir_block *block, nir_block *pred) 275762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott{ 276762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 277707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr(instr, block) { 278762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott if (instr->type != nir_instr_type_phi) 279762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott break; 280762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 281762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 282762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_ssa_undef_instr *undef = 283762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_ssa_undef_instr_create(ralloc_parent(phi), 284e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez phi->dest.ssa.num_components, 285e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez phi->dest.ssa.bit_size); 286762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 287762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_phi_src *src = ralloc(phi, nir_phi_src); 288762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->pred = pred; 289762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.parent_instr = &phi->instr; 290762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.is_ssa = true; 291762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.ssa = &undef->def; 292762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 293762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott list_addtail(&src->src.use_link, &undef->def.uses); 294762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 295762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott exec_list_push_tail(&phi->srcs, &src->node); 296762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott } 297762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott} 298762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 299b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 300b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Moves the successors of source to the successors of dest, leaving both 301b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * successors of source NULL. 302b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 303b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 304b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 305b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottmove_successors(nir_block *source, nir_block *dest) 306b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 307b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *succ1 = source->successors[0]; 308b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *succ2 = source->successors[1]; 309b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 310b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ1) { 311b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(source, succ1); 312b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott rewrite_phi_preds(succ1, source, dest); 313b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 314b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 315b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ2) { 316b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(source, succ2); 317b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott rewrite_phi_preds(succ2, source, dest); 318b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 319b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 320b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(dest); 321b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(dest, succ1, succ2); 322b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 323b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 324747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott/* Given a basic block with no successors that has been inserted into the 325747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * control flow tree, gives it the successors it would normally have assuming 326747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * it doesn't end in a jump instruction. Also inserts phi sources with undefs 327747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * if necessary. 328747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott */ 329747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottstatic void 330747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottblock_add_normal_succs(nir_block *block) 331747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 332747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (exec_node_is_tail_sentinel(block->cf_node.node.next)) { 333747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *parent = block->cf_node.parent; 334747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (parent->type == nir_cf_node_if) { 335747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *next = nir_cf_node_next(parent); 336747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(next->type == nir_cf_node_block); 337747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *next_block = nir_cf_node_as_block(next); 338747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 339747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, next_block, NULL); 340124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand } else if (parent->type == nir_cf_node_loop) { 341747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(parent); 342747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 343747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *head = nir_loop_first_cf_node(loop); 344747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(head->type == nir_cf_node_block); 345747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *head_block = nir_cf_node_as_block(head); 346747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 347747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, head_block, NULL); 348747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott insert_phi_undef(head_block, block); 349124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand } else { 350124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand assert(parent->type == nir_cf_node_function); 351124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand nir_function_impl *impl = nir_cf_node_as_function(parent); 352124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand link_blocks(block, impl->end_block, NULL); 353747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 354747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 355747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *next = nir_cf_node_next(&block->cf_node); 356747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (next->type == nir_cf_node_if) { 357747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_if *next_if = nir_cf_node_as_if(next); 358747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 359747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *first_then = nir_if_first_then_node(next_if); 360747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(first_then->type == nir_cf_node_block); 361747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *first_then_block = nir_cf_node_as_block(first_then); 362747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 363747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *first_else = nir_if_first_else_node(next_if); 364747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(first_else->type == nir_cf_node_block); 365747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *first_else_block = nir_cf_node_as_block(first_else); 366747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 367747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, first_then_block, first_else_block); 368747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 369747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(next->type == nir_cf_node_loop); 370747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *next_loop = nir_cf_node_as_loop(next); 371747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 372747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *first = nir_loop_first_cf_node(next_loop); 373747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott assert(first->type == nir_cf_node_block); 374747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *first_block = nir_cf_node_as_block(first); 375747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 376747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, first_block, NULL); 377747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott insert_phi_undef(first_block, block); 378747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 379747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 380747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott} 381747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 382b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_block * 383b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottsplit_block_end(nir_block *block) 384b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 385b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *new_block = nir_block_create(ralloc_parent(block)); 386b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott new_block->cf_node.parent = block->cf_node.parent; 387b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node); 388b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 389940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott if (block_ends_in_jump(block)) { 390940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott /* Figure out what successor block would've had if it didn't have a jump 391940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott * instruction, and make new_block have that successor. 392940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott */ 393940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott block_add_normal_succs(new_block); 394940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott } else { 395940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott move_successors(block, new_block); 396940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott } 397b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 398b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return new_block; 399b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 400b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 40158a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbottstatic nir_block * 40258a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbottsplit_block_before_instr(nir_instr *instr) 40358a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott{ 40458a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott assert(instr->type != nir_instr_type_phi); 40558a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott nir_block *new_block = split_block_beginning(instr->block); 40658a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 407707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(cur_instr, instr->block) { 40858a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott if (cur_instr == instr) 40958a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott break; 41058a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 41158a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott exec_node_remove(&cur_instr->node); 41258a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott cur_instr->block = new_block; 41358a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott exec_list_push_tail(&new_block->instr_list, &cur_instr->node); 41458a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott } 41558a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 41658a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott return new_block; 41758a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott} 41858a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 419d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott/* Splits a basic block at the point specified by the cursor. The "before" and 420d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * "after" arguments are filled out with the blocks resulting from the split 421d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * if non-NULL. Note that the "beginning" of the block is actually interpreted 422d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * as before the first non-phi instruction, and it's illegal to split a block 423d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * before a phi instruction. 424d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott */ 425d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 426d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbottstatic void 427d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbottsplit_block_cursor(nir_cursor cursor, 428d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott nir_block **_before, nir_block **_after) 429d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott{ 430d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott nir_block *before, *after; 431d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott switch (cursor.option) { 432d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_before_block: 433d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.block; 434d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_beginning(cursor.block); 435d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 436d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 437d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_after_block: 438d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = cursor.block; 439d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = split_block_end(cursor.block); 440d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 441d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 442d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_before_instr: 443d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.instr->block; 444d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_before_instr(cursor.instr); 445d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 446d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 447d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_after_instr: 448d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott /* We lower this to split_block_before_instr() so that we can keep the 449d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * after-a-jump-instr case contained to split_block_end(). 450d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott */ 451d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (nir_instr_is_last(cursor.instr)) { 452d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = cursor.instr->block; 453d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = split_block_end(cursor.instr->block); 454d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } else { 455d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.instr->block; 456d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_before_instr(nir_instr_next(cursor.instr)); 457d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } 458d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 4593a0fef0005eca63c6f8067d55145b8e884221cfaVinson Lee 4603a0fef0005eca63c6f8067d55145b8e884221cfaVinson Lee default: 4613a0fef0005eca63c6f8067d55145b8e884221cfaVinson Lee unreachable("not reached"); 462d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } 463d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 464d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (_before) 465d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott *_before = before; 466d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (_after) 467d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott *_after = after; 468d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott} 469d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 470b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 471b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Inserts a non-basic block between two basic blocks and links them together. 472b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 473b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 474b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 475b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottinsert_non_block(nir_block *before, nir_cf_node *node, nir_block *after) 476b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 477b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott node->parent = before->cf_node.parent; 478b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_after(&before->cf_node.node, &node->node); 479b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_block_to_non_block(before, node); 480b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_non_block_to_block(node, after); 481b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 482b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 483b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* walk up the control flow tree to find the innermost enclosed loop */ 484b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_loop * 485b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnearest_loop(nir_cf_node *node) 486b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 487b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott while (node->type != nir_cf_node_loop) { 488b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott node = node->parent; 489b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 490b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 491b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return nir_cf_node_as_loop(node); 492b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 493b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 494b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* 495b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * update the CFG after a jump instruction has been added to the end of a block 496b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 497b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 498b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottvoid 499b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnir_handle_add_jump(nir_block *block) 500b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 501b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_instr *instr = nir_block_last_instr(block); 502b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_jump_instr *jump_instr = nir_instr_as_jump(instr); 503b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 504b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 505b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 506b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 507b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 508b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 509b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (jump_instr->type == nir_jump_break || 510b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott jump_instr->type == nir_jump_continue) { 511b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nearest_loop(&block->cf_node); 512b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 513b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (jump_instr->type == nir_jump_continue) { 514b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *first_node = nir_loop_first_cf_node(loop); 515b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(first_node->type == nir_cf_node_block); 516b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *first_block = nir_cf_node_as_block(first_node); 517b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, first_block, NULL); 518b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 519b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *after = nir_cf_node_next(&loop->cf_node); 520b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(after->type == nir_cf_node_block); 521b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *after_block = nir_cf_node_as_block(after); 522b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, after_block, NULL); 523b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 524b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* If we inserted a fake link, remove it */ 525b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *last = nir_loop_last_cf_node(loop); 526b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(last->type == nir_cf_node_block); 527b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *last_block = nir_cf_node_as_block(last); 528b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (last_block->successors[1] != NULL) 529b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(last_block, after_block); 530b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 531b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 532b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(jump_instr->type == nir_jump_return); 533b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, impl->end_block, NULL); 534b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 535b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 536b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 53713482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbottstatic void 53813482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbottremove_phi_src(nir_block *block, nir_block *pred) 53913482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott{ 540707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr(instr, block) { 54113482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott if (instr->type != nir_instr_type_phi) 54213482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott break; 54313482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott 54413482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 54513482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott nir_foreach_phi_src_safe(phi, src) { 54613482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott if (src->pred == pred) { 54713482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott list_del(&src->src.use_link); 54813482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott exec_node_remove(&src->node); 54913482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 55013482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 55113482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 55213482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott} 55313482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott 554747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott/* Removes the successor of a block with a jump, and inserts a fake edge for 555747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * infinite loops. Note that the jump to be eliminated may be free-floating. 556747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott */ 557b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 5580991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunkestatic void 5590991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunkeunlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors) 560747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 561024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke nir_block *next = block->successors[0]; 562024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke 563747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (block->successors[0]) 564747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott remove_phi_src(block->successors[0], block); 565747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (block->successors[1]) 566747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott remove_phi_src(block->successors[1], block); 567b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 568024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke unlink_block_successors(block); 569024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke if (add_normal_successors) 570024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke block_add_normal_succs(block); 571b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 572024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke /* If we've just removed a break, and the block we were jumping to (after 573024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * the loop) now has zero predecessors, we've created a new infinite loop. 574024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * 575024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * NIR doesn't allow blocks (other than the start block) to have zero 576024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * predecessors. In particular, dominance assumes all blocks are reachable. 577024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * So, we insert a "fake link" by making successors[1] point after the loop. 578024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * 579024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * Note that we have to do this after unlinking/recreating the block's 580024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * successors. If we removed a "break" at the end of the loop, then 581024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * block == last_block, so block->successors[0] would already be "next", 582024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * and adding a fake link would create two identical successors. Doing 583024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * this afterward works, as we'll have changed block->successors[0] to 584024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke * be the top of the loop. 585024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke */ 586024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke if (type == nir_jump_break && next->predecessors->entries == 0) { 587024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke nir_loop *loop = 588024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke nir_cf_node_as_loop(nir_cf_node_prev(&next->cf_node)); 589b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 590024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke /* insert fake link */ 591024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke nir_cf_node *last = nir_loop_last_cf_node(loop); 592024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke assert(last->type == nir_cf_node_block); 593024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke nir_block *last_block = nir_cf_node_as_block(last); 594b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 595024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke last_block->successors[1] = next; 596024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke block_add_pred(next, last_block); 597b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 598747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott} 599747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 600747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottvoid 601747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottnir_handle_remove_jump(nir_block *block, nir_jump_type type) 602747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 6030991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunke unlink_jump(block, type, true); 604747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 605b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 606b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 607b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 608b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 609b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 610b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottupdate_if_uses(nir_cf_node *node) 611b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 612b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type != nir_cf_node_if) 613b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return; 614b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 615b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 616b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 617b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if_stmt->condition.parent_if = if_stmt; 618b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (if_stmt->condition.is_ssa) { 619b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_addtail(&if_stmt->condition.use_link, 620b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott &if_stmt->condition.ssa->if_uses); 621b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 622b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_addtail(&if_stmt->condition.use_link, 623b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott &if_stmt->condition.reg.reg->if_uses); 624b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 625b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 626b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 627b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 628b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Stitch two basic blocks together into one. The aggregate must have the same 629b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * predecessors as the first and the same successors as the second. 630b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 631b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 632b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 633b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstitch_blocks(nir_block *before, nir_block *after) 634b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 635b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 636b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We move after into before, so we have to deal with up to 2 successors vs. 637b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * possibly a large number of predecessors. 638b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 639b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * TODO: special case when before is empty and after isn't? 640b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 641b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 642633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (block_ends_in_jump(before)) { 643633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott assert(exec_list_is_empty(&after->instr_list)); 644633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (after->successors[0]) 645633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott remove_phi_src(after->successors[0], after); 646633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (after->successors[1]) 647633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott remove_phi_src(after->successors[1], after); 648633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott unlink_block_successors(after); 649633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_node_remove(&after->cf_node.node); 650633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } else { 651633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott move_successors(after, before); 652b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 653633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott foreach_list_typed(nir_instr, instr, node, &after->instr_list) { 654633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott instr->block = before; 655633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } 656b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 657633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_list_append(&before->instr_list, &after->instr_list); 658633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_node_remove(&after->cf_node.node); 659633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } 660b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 661b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 662476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbottvoid 663476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbottnir_cf_node_insert(nir_cursor cursor, nir_cf_node *node) 664476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott{ 665476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_block *before, *after; 666476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 667476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott split_block_cursor(cursor, &before, &after); 668476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 669476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott if (node->type == nir_cf_node_block) { 670476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_block *block = nir_cf_node_as_block(node); 671476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott exec_node_insert_after(&before->cf_node.node, &block->cf_node.node); 672476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott block->cf_node.parent = before->cf_node.parent; 673476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott /* stitch_blocks() assumes that any block that ends with a jump has 674476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott * already been setup with the correct successors, so we need to set 675476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott * up jumps here as the block is being inserted. 676476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott */ 677476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott if (block_ends_in_jump(block)) 678476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_handle_add_jump(block); 679476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 680476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott stitch_blocks(block, after); 681476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott stitch_blocks(before, block); 682476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott } else { 683476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott update_if_uses(node); 684476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott insert_non_block(before, node, after); 685476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott } 686476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott} 687476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 688211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottstatic bool 689211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottreplace_ssa_def_uses(nir_ssa_def *def, void *void_impl) 690211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott{ 691211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_function_impl *impl = void_impl; 692211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott void *mem_ctx = ralloc_parent(impl); 693211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott 694211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_ssa_undef_instr *undef = 695e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez nir_ssa_undef_instr_create(mem_ctx, def->num_components, 696e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez def->bit_size); 697211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 698a4aa25be1e0a27b1a6a6b0bcf576beb9dfe1ea7aJason Ekstrand nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(&undef->def)); 699211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott return true; 700211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott} 701b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 702b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 703211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottcleanup_cf_node(nir_cf_node *node, nir_function_impl *impl) 704b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 705b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott switch (node->type) { 706b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_block: { 707b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *block = nir_cf_node_as_block(node); 708b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* We need to walk the instructions and clean up defs/uses */ 709707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 7106d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott if (instr->type == nir_instr_type_jump) { 7116d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott nir_jump_type jump_type = nir_instr_as_jump(instr)->type; 7120991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunke unlink_jump(block, jump_type, false); 7136d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott } else { 714211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_foreach_ssa_def(instr, replace_ssa_def_uses, impl); 715b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_instr_remove(instr); 716211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott } 717211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott } 718b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 719b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 720b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 721b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_if: { 722b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 723b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list) 724211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 725b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list) 726211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 727b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 728b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_del(&if_stmt->condition.use_link); 729b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 730b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 731b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 732b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_loop: { 733b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 734b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &loop->body) 735211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 736b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 737b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 738b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_function: { 739b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_as_function(node); 740b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &impl->body) 741211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 742b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 743b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 744b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott default: 745b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unreachable("Invalid CF node type"); 746b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 747b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 748b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 749b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottvoid 750fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_extract(nir_cf_list *extracted, nir_cursor begin, nir_cursor end) 751fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 752fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_block *block_begin, *block_end, *block_before, *block_after; 753fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 75497b663481c8c83fda06246860708530cff755a05Jason Ekstrand if (nir_cursors_equal(begin, end)) { 75597b663481c8c83fda06246860708530cff755a05Jason Ekstrand exec_list_make_empty(&extracted->list); 75697b663481c8c83fda06246860708530cff755a05Jason Ekstrand extracted->impl = NULL; /* we shouldn't need this */ 75797b663481c8c83fda06246860708530cff755a05Jason Ekstrand return; 75897b663481c8c83fda06246860708530cff755a05Jason Ekstrand } 75997b663481c8c83fda06246860708530cff755a05Jason Ekstrand 760fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott /* In the case where begin points to an instruction in some basic block and 761fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * end points to the end of the same basic block, we rely on the fact that 762fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * splitting on an instruction moves earlier instructions into a new basic 763fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * block. If the later instructions were moved instead, then the end cursor 764fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * would be pointing to the same place that begin used to point to, which 765fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * is obviously not what we want. 766fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott */ 767fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(begin, &block_before, &block_begin); 768fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(end, &block_end, &block_after); 769fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 770fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott extracted->impl = nir_cf_node_get_function(&block_begin->cf_node); 771fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_list_make_empty(&extracted->list); 772fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 773fbaa1b19d7accc5de95d6804525aad5b95abba72Kenneth Graunke /* Dominance and other block-related information is toast. */ 774fbaa1b19d7accc5de95d6804525aad5b95abba72Kenneth Graunke nir_metadata_preserve(extracted->impl, nir_metadata_none); 775fbaa1b19d7accc5de95d6804525aad5b95abba72Kenneth Graunke 776fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *cf_node = &block_begin->cf_node; 777fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *cf_node_end = &block_end->cf_node; 778fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott while (true) { 779fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *next = nir_cf_node_next(cf_node); 780fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 781fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_remove(&cf_node->node); 782fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cf_node->parent = NULL; 783fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_list_push_tail(&extracted->list, &cf_node->node); 784fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 785fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott if (cf_node == cf_node_end) 786fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott break; 787fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 788fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cf_node = next; 789fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 790fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 791fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(block_before, block_after); 792fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 793fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 794fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 795fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_reinsert(nir_cf_list *cf_list, nir_cursor cursor) 796fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 797fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_block *before, *after; 798fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 79997b663481c8c83fda06246860708530cff755a05Jason Ekstrand if (exec_list_is_empty(&cf_list->list)) 80097b663481c8c83fda06246860708530cff755a05Jason Ekstrand return; 80197b663481c8c83fda06246860708530cff755a05Jason Ekstrand 802fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(cursor, &before, &after); 803fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 804fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott foreach_list_typed_safe(nir_cf_node, node, node, &cf_list->list) { 805fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_remove(&node->node); 806fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott node->parent = before->cf_node.parent; 807fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_insert_node_before(&after->cf_node.node, &node->node); 808fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 809fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 810fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(before, 811fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node_as_block(nir_cf_node_next(&before->cf_node))); 812fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(nir_cf_node_as_block(nir_cf_node_prev(&after->cf_node)), 813fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott after); 814fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 815fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 816fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 817fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_delete(nir_cf_list *cf_list) 818fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 819fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott foreach_list_typed(nir_cf_node, node, node, &cf_list->list) { 820fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cleanup_cf_node(node, cf_list->impl); 821fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 822fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 823