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 * 43b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * The purpose of the second one is so that we have places to insert code during 44b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * GCM, as well as eliminating the possibility of critical edges. 45b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 46b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/*@{*/ 47b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 484f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunkestatic bool 494f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunkeblock_ends_in_jump(nir_block *block) 504f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke{ 514f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke return !exec_list_is_empty(&block->instr_list) && 524f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke nir_block_last_instr(block)->type == nir_instr_type_jump; 534f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke} 544f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke 55b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic inline void 56b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottblock_add_pred(nir_block *block, nir_block *pred) 57b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 58b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott _mesa_set_add(block->predecessors, pred); 59b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 60b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 61e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunkestatic inline void 62e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunkeblock_remove_pred(nir_block *block, nir_block *pred) 63e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke{ 64e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke struct set_entry *entry = _mesa_set_search(block->predecessors, pred); 65e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke 66e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke assert(entry); 67e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke 68e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke _mesa_set_remove(block->predecessors, entry); 69e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke} 70e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke 71b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 72b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_blocks(nir_block *pred, nir_block *succ1, nir_block *succ2) 73b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 74b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[0] = succ1; 756f5c81f86f9b1b08b57435562be657fb2d220408Connor Abbott if (succ1 != NULL) 766f5c81f86f9b1b08b57435562be657fb2d220408Connor Abbott block_add_pred(succ1, pred); 77b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 78b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = succ2; 79b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ2 != NULL) 80b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott block_add_pred(succ2, pred); 81b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 82b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 83b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 84b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottunlink_blocks(nir_block *pred, nir_block *succ) 85b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 86b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (pred->successors[0] == succ) { 87b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[0] = pred->successors[1]; 88b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = NULL; 89b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 90b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(pred->successors[1] == succ); 91b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott pred->successors[1] = NULL; 92b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 93b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 94e2637db618b868682e1c996b3c6394c2e82963f1Kenneth Graunke block_remove_pred(succ, pred); 95b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 96b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 97b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 98b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottunlink_block_successors(nir_block *block) 99b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 100b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (block->successors[1] != NULL) 101b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(block, block->successors[1]); 1026560838703431f89c47d68822758bc76fd34c355Kenneth Graunke if (block->successors[0] != NULL) 1036560838703431f89c47d68822758bc76fd34c355Kenneth Graunke unlink_blocks(block, block->successors[0]); 104b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 105b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 106b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 107b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_non_block_to_block(nir_cf_node *node, nir_block *block) 108b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 109b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_if) { 110b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 111b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We're trying to link an if to a block after it; this just means linking 112b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the last block of the then and else branches. 113b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 114b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 115b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 116b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1172ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *last_then_block = nir_if_last_then_block(if_stmt); 1182ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *last_else_block = nir_if_last_else_block(if_stmt); 119b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1204f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke if (!block_ends_in_jump(last_then_block)) { 121b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(last_then_block); 122b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(last_then_block, block, NULL); 123b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 124b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1254f2cdd849738019ce9552ee1d5f8dafce8af3f10Kenneth Graunke if (!block_ends_in_jump(last_else_block)) { 126b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(last_else_block); 127b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(last_else_block, block, NULL); 128b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 129b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 130b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(node->type == nir_cf_node_loop); 131b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 132b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 133b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 134b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 135b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottlink_block_to_non_block(nir_block *block, nir_cf_node *node) 136b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 137b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type == nir_cf_node_if) { 138b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 139b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We're trying to link a block to an if after it; this just means linking 140b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * the block to the first block of the then and else branches. 141b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 142b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 143b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 144b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1452ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *first_then_block = nir_if_first_then_block(if_stmt); 1462ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *first_else_block = nir_if_first_else_block(if_stmt); 147b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 148b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 149b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, first_then_block, first_else_block); 150b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 151b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 152b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * For similar reasons as the corresponding case in 153b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * link_non_block_to_block(), don't worry about if the loop header has 154b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * any predecessors that need to be unlinked. 155b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 156b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 157b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 158b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 1592ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *loop_header_block = nir_loop_first_block(loop); 160b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 161b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 162b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, loop_header_block, NULL); 163b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 164b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 165b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 166b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 167b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 1689674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke * Replace a block's successor with a different one. 1699674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke */ 1709674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunkestatic void 1719674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunkereplace_successor(nir_block *block, nir_block *old_succ, nir_block *new_succ) 1729674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke{ 1739674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke if (block->successors[0] == old_succ) { 1749674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block->successors[0] = new_succ; 1759674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke } else { 1769674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke assert(block->successors[1] == old_succ); 1779674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block->successors[1] = new_succ; 1789674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke } 1799674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke 1809674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block_remove_pred(old_succ, block); 1819674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke block_add_pred(new_succ, block); 1829674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke} 1839674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke 1849674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke/** 185b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Takes a basic block and inserts a new empty basic block before it, making its 186b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * predecessors point to the new block. This essentially splits the block into 187b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * an empty header and a body so that another non-block CF node can be inserted 188b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * between the two. Note that this does *not* link the two basic blocks, so 189b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * some kind of cleanup *must* be performed after this call. 190b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 191b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 192b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_block * 193b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottsplit_block_beginning(nir_block *block) 194b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 195b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *new_block = nir_block_create(ralloc_parent(block)); 196b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott new_block->cf_node.parent = block->cf_node.parent; 197b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_node_before(&block->cf_node.node, &new_block->cf_node.node); 198b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 199b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott struct set_entry *entry; 200b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott set_foreach(block->predecessors, entry) { 201b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *pred = (nir_block *) entry->key; 2029674c76c0e473a3edbc45f935ea88afd64024325Kenneth Graunke replace_successor(pred, block, new_block); 203b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 204b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 205788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott /* Any phi nodes must stay part of the new block, or else their 206788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott * sourcse will be messed up. This will reverse the order of the phi's, but 207788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott * order shouldn't matter. 208788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott */ 209707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 210788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott if (instr->type != nir_instr_type_phi) 211788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott break; 212788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott 213788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott exec_node_remove(&instr->node); 214788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott instr->block = new_block; 215788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott exec_list_push_head(&new_block->instr_list, &instr->node); 216788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott } 217788d45cb478d6285fe6811c87b4f1db1daded6d9Connor Abbott 218b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return new_block; 219b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 220b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 221b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 222b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottrewrite_phi_preds(nir_block *block, nir_block *old_pred, nir_block *new_pred) 223b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 224707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 225b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (instr->type != nir_instr_type_phi) 226b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 227b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 228b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 2298564916d01b31ca5665a27366e483738541ba5a3Jason Ekstrand nir_foreach_phi_src(src, phi) { 230b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (src->pred == old_pred) { 231b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott src->pred = new_pred; 232b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 233b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 234b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 235b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 236b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 237b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 238762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbottstatic void 239762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbottinsert_phi_undef(nir_block *block, nir_block *pred) 240762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott{ 241762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 242707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr(instr, block) { 243762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott if (instr->type != nir_instr_type_phi) 244762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott break; 245762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 246762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 247762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_ssa_undef_instr *undef = 248762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_ssa_undef_instr_create(ralloc_parent(phi), 249e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez phi->dest.ssa.num_components, 250e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez phi->dest.ssa.bit_size); 251762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 252762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott nir_phi_src *src = ralloc(phi, nir_phi_src); 253762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->pred = pred; 254762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.parent_instr = &phi->instr; 255762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.is_ssa = true; 256762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott src->src.ssa = &undef->def; 257762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 258762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott list_addtail(&src->src.use_link, &undef->def.uses); 259762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 260762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott exec_list_push_tail(&phi->srcs, &src->node); 261762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott } 262762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott} 263762ae436ea578651c9f8a50620196b5d744b8eeeConnor Abbott 264b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 265b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Moves the successors of source to the successors of dest, leaving both 266b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * successors of source NULL. 267b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 268b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 269b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 270b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottmove_successors(nir_block *source, nir_block *dest) 271b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 272b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *succ1 = source->successors[0]; 273b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *succ2 = source->successors[1]; 274b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 275b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ1) { 276b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(source, succ1); 277b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott rewrite_phi_preds(succ1, source, dest); 278b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 279b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 280b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (succ2) { 281b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_blocks(source, succ2); 282b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott rewrite_phi_preds(succ2, source, dest); 283b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 284b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 285b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(dest); 286b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(dest, succ1, succ2); 287b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 288b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 289747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott/* Given a basic block with no successors that has been inserted into the 290747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * control flow tree, gives it the successors it would normally have assuming 291747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * it doesn't end in a jump instruction. Also inserts phi sources with undefs 292747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott * if necessary. 293747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott */ 294747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottstatic void 295747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottblock_add_normal_succs(nir_block *block) 296747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 297747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (exec_node_is_tail_sentinel(block->cf_node.node.next)) { 298747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *parent = block->cf_node.parent; 299747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (parent->type == nir_cf_node_if) { 300747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *next = nir_cf_node_next(parent); 301747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_block *next_block = nir_cf_node_as_block(next); 302747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 303747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, next_block, NULL); 304124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand } else if (parent->type == nir_cf_node_loop) { 305747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(parent); 306747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 3072ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *head_block = nir_loop_first_block(loop); 308747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 309747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, head_block, NULL); 310747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott insert_phi_undef(head_block, block); 311124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand } else { 312124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand nir_function_impl *impl = nir_cf_node_as_function(parent); 313124f229ece8ffa7d1f8d530771f183f7803d6cdcJason Ekstrand link_blocks(block, impl->end_block, NULL); 314747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 315747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 316747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_cf_node *next = nir_cf_node_next(&block->cf_node); 317747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (next->type == nir_cf_node_if) { 318747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_if *next_if = nir_cf_node_as_if(next); 319747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 3202ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *first_then_block = nir_if_first_then_block(next_if); 3212ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *first_else_block = nir_if_first_else_block(next_if); 322747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 323747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, first_then_block, first_else_block); 324747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } else { 325747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott nir_loop *next_loop = nir_cf_node_as_loop(next); 326747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 3272ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *first_block = nir_loop_first_block(next_loop); 328747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 329747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott link_blocks(block, first_block, NULL); 330747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott insert_phi_undef(first_block, block); 331747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 332747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott } 333747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott} 334747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 335b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_block * 336b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottsplit_block_end(nir_block *block) 337b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 338b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *new_block = nir_block_create(ralloc_parent(block)); 339b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott new_block->cf_node.parent = block->cf_node.parent; 340b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_after(&block->cf_node.node, &new_block->cf_node.node); 341b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 342940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott if (block_ends_in_jump(block)) { 343940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott /* Figure out what successor block would've had if it didn't have a jump 344940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott * instruction, and make new_block have that successor. 345940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott */ 346940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott block_add_normal_succs(new_block); 347940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott } else { 348940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott move_successors(block, new_block); 349940873bf22c90db79d065f14ff44dab12415feb0Connor Abbott } 350b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 351b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return new_block; 352b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 353b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 35458a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbottstatic nir_block * 35558a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbottsplit_block_before_instr(nir_instr *instr) 35658a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott{ 35758a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott assert(instr->type != nir_instr_type_phi); 35858a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott nir_block *new_block = split_block_beginning(instr->block); 35958a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 360707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(cur_instr, instr->block) { 36158a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott if (cur_instr == instr) 36258a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott break; 36358a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 36458a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott exec_node_remove(&cur_instr->node); 36558a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott cur_instr->block = new_block; 36658a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott exec_list_push_tail(&new_block->instr_list, &cur_instr->node); 36758a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott } 36858a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 36958a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott return new_block; 37058a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott} 37158a360c6b8aead1fec34aea298654ab544e7c8e8Connor Abbott 372d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott/* Splits a basic block at the point specified by the cursor. The "before" and 373d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * "after" arguments are filled out with the blocks resulting from the split 374d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * if non-NULL. Note that the "beginning" of the block is actually interpreted 375d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * as before the first non-phi instruction, and it's illegal to split a block 376d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * before a phi instruction. 377d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott */ 378d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 379d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbottstatic void 380d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbottsplit_block_cursor(nir_cursor cursor, 381d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott nir_block **_before, nir_block **_after) 382d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott{ 383d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott nir_block *before, *after; 384d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott switch (cursor.option) { 385d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_before_block: 386d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.block; 387d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_beginning(cursor.block); 388d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 389d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 390d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_after_block: 391d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = cursor.block; 392d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = split_block_end(cursor.block); 393d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 394d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 395d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_before_instr: 396d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.instr->block; 397d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_before_instr(cursor.instr); 398d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 399d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 400d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott case nir_cursor_after_instr: 401d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott /* We lower this to split_block_before_instr() so that we can keep the 402d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott * after-a-jump-instr case contained to split_block_end(). 403d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott */ 404d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (nir_instr_is_last(cursor.instr)) { 405d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = cursor.instr->block; 406d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = split_block_end(cursor.instr->block); 407d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } else { 408d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott after = cursor.instr->block; 409d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott before = split_block_before_instr(nir_instr_next(cursor.instr)); 410d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } 411d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott break; 4123a0fef0005eca63c6f8067d55145b8e884221cfaVinson Lee 4133a0fef0005eca63c6f8067d55145b8e884221cfaVinson Lee default: 4143a0fef0005eca63c6f8067d55145b8e884221cfaVinson Lee unreachable("not reached"); 415d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott } 416d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 417d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (_before) 418d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott *_before = before; 419d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott if (_after) 420d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott *_after = after; 421d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott} 422d356f84d4ceb9fb63e4b254ab8b26ce891c2f2b9Connor Abbott 423b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 424b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Inserts a non-basic block between two basic blocks and links them together. 425b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 426b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 427b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 428b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottinsert_non_block(nir_block *before, nir_cf_node *node, nir_block *after) 429b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 430b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott node->parent = before->cf_node.parent; 431b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott exec_node_insert_after(&before->cf_node.node, &node->node); 432b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_block_to_non_block(before, node); 433b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_non_block_to_block(node, after); 434b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 435b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 436b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* walk up the control flow tree to find the innermost enclosed loop */ 437b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic nir_loop * 438b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnearest_loop(nir_cf_node *node) 439b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 440b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott while (node->type != nir_cf_node_loop) { 441b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott node = node->parent; 442b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 443b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 444b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return nir_cf_node_as_loop(node); 445b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 446b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 447b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/* 448b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * update the CFG after a jump instruction has been added to the end of a block 449b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 450b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 451b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottvoid 452b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottnir_handle_add_jump(nir_block *block) 453b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 454b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_instr *instr = nir_block_last_instr(block); 455b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_jump_instr *jump_instr = nir_instr_as_jump(instr); 456b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 457b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unlink_block_successors(block); 458b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 459b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 460b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 461b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 462b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (jump_instr->type == nir_jump_break || 463b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott jump_instr->type == nir_jump_continue) { 464b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nearest_loop(&block->cf_node); 465b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 466b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (jump_instr->type == nir_jump_continue) { 4672ed17d46de045404042f13c6591895a1cf31b167Jason Ekstrand nir_block *first_block = nir_loop_first_block(loop); 468b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, first_block, NULL); 469b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 470b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_cf_node *after = nir_cf_node_next(&loop->cf_node); 471b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *after_block = nir_cf_node_as_block(after); 472b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, after_block, NULL); 473b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 474b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 475b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott assert(jump_instr->type == nir_jump_return); 476b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott link_blocks(block, impl->end_block, NULL); 477b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 478b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 479b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 48013482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbottstatic void 48113482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbottremove_phi_src(nir_block *block, nir_block *pred) 48213482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott{ 483707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr(instr, block) { 48413482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott if (instr->type != nir_instr_type_phi) 48513482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott break; 48613482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott 48713482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott nir_phi_instr *phi = nir_instr_as_phi(instr); 4888564916d01b31ca5665a27366e483738541ba5a3Jason Ekstrand nir_foreach_phi_src_safe(src, phi) { 48913482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott if (src->pred == pred) { 49013482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott list_del(&src->src.use_link); 49113482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott exec_node_remove(&src->node); 49213482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 49313482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 49413482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott } 49513482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott} 49613482111d0dd9649d4b14ed05df344d5a2cea3deConnor Abbott 497aad4f15506c2b5ff9f3304a467b51b45dd77554dJason Ekstrand/* Removes the successor of a block with a jump. Note that the jump to be 498aad4f15506c2b5ff9f3304a467b51b45dd77554dJason Ekstrand * eliminated may be free-floating. 499747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott */ 500b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 5010991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunkestatic void 5020991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunkeunlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors) 503747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 504747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (block->successors[0]) 505747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott remove_phi_src(block->successors[0], block); 506747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott if (block->successors[1]) 507747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott remove_phi_src(block->successors[1], block); 508b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 509024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke unlink_block_successors(block); 510024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke if (add_normal_successors) 511024e5ec9777c38f8c05be6678a9f51b145a00236Kenneth Graunke block_add_normal_succs(block); 512747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott} 513747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 514747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottvoid 515747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbottnir_handle_remove_jump(nir_block *block, nir_jump_type type) 516747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott{ 5170991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunke unlink_jump(block, type, true); 518747ddc3cdd51cc3786894e2ba56d86334a7051a5Connor Abbott 519b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node); 520b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_metadata_preserve(impl, nir_metadata_none); 521b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 522b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 523b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 524b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottupdate_if_uses(nir_cf_node *node) 525b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 526b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (node->type != nir_cf_node_if) 527b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott return; 528b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 529b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 530b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 531b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if_stmt->condition.parent_if = if_stmt; 532b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott if (if_stmt->condition.is_ssa) { 533b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_addtail(&if_stmt->condition.use_link, 534b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott &if_stmt->condition.ssa->if_uses); 535b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } else { 536b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_addtail(&if_stmt->condition.use_link, 537b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott &if_stmt->condition.reg.reg->if_uses); 538b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 539b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 540b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 541b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott/** 542b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * Stitch two basic blocks together into one. The aggregate must have the same 543b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * predecessors as the first and the same successors as the second. 544b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 545b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 546b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 547b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstitch_blocks(nir_block *before, nir_block *after) 548b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 549b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* 550b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * We move after into before, so we have to deal with up to 2 successors vs. 551b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * possibly a large number of predecessors. 552b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * 553b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott * TODO: special case when before is empty and after isn't? 554b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott */ 555b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 556633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (block_ends_in_jump(before)) { 557633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott assert(exec_list_is_empty(&after->instr_list)); 558633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (after->successors[0]) 559633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott remove_phi_src(after->successors[0], after); 560633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott if (after->successors[1]) 561633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott remove_phi_src(after->successors[1], after); 562633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott unlink_block_successors(after); 563633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_node_remove(&after->cf_node.node); 564633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } else { 565633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott move_successors(after, before); 566b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 567633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott foreach_list_typed(nir_instr, instr, node, &after->instr_list) { 568633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott instr->block = before; 569633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } 570b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 571633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_list_append(&before->instr_list, &after->instr_list); 572633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott exec_node_remove(&after->cf_node.node); 573633cbbc0682b1cec3107398a21a057697e8572aaConnor Abbott } 574b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 575b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 576476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbottvoid 577476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbottnir_cf_node_insert(nir_cursor cursor, nir_cf_node *node) 578476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott{ 579476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_block *before, *after; 580476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 581476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott split_block_cursor(cursor, &before, &after); 582476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 583476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott if (node->type == nir_cf_node_block) { 584476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_block *block = nir_cf_node_as_block(node); 585476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott exec_node_insert_after(&before->cf_node.node, &block->cf_node.node); 586476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott block->cf_node.parent = before->cf_node.parent; 587476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott /* stitch_blocks() assumes that any block that ends with a jump has 588476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott * already been setup with the correct successors, so we need to set 589476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott * up jumps here as the block is being inserted. 590476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott */ 591476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott if (block_ends_in_jump(block)) 592476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott nir_handle_add_jump(block); 593476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 594476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott stitch_blocks(block, after); 595476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott stitch_blocks(before, block); 596476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott } else { 597476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott update_if_uses(node); 598476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott insert_non_block(before, node, after); 599476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott } 600476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott} 601476eb5e4a16efdbc54c4418e44b1f38989026addConnor Abbott 602211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottstatic bool 603211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottreplace_ssa_def_uses(nir_ssa_def *def, void *void_impl) 604211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott{ 605211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_function_impl *impl = void_impl; 606211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott void *mem_ctx = ralloc_parent(impl); 607211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott 608211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_ssa_undef_instr *undef = 609e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez nir_ssa_undef_instr_create(mem_ctx, def->num_components, 610e3edaec739a72a36d54b60ddf5c952d377324f00Samuel Iglesias Gonsálvez def->bit_size); 611211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_instr_insert_before_cf_list(&impl->body, &undef->instr); 612a4aa25be1e0a27b1a6a6b0bcf576beb9dfe1ea7aJason Ekstrand nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(&undef->def)); 613211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott return true; 614211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott} 615b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 616b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottstatic void 617211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbottcleanup_cf_node(nir_cf_node *node, nir_function_impl *impl) 618b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott{ 619b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott switch (node->type) { 620b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_block: { 621b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_block *block = nir_cf_node_as_block(node); 622b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott /* We need to walk the instructions and clean up defs/uses */ 623707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 6246d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott if (instr->type == nir_instr_type_jump) { 6256d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott nir_jump_type jump_type = nir_instr_as_jump(instr)->type; 6260991b2eb3535f9af289149c9e63c38b56cb4b549Kenneth Graunke unlink_jump(block, jump_type, false); 6276d028749ac593b6c724ab86a42bf969da47cc569Connor Abbott } else { 628211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott nir_foreach_ssa_def(instr, replace_ssa_def_uses, impl); 629b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_instr_remove(instr); 630211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott } 631211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott } 632b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 633b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 634b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 635b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_if: { 636b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_if *if_stmt = nir_cf_node_as_if(node); 637b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &if_stmt->then_list) 638211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 639b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &if_stmt->else_list) 640211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 641b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 642b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott list_del(&if_stmt->condition.use_link); 643b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 644b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 645b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 646b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_loop: { 647b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_loop *loop = nir_cf_node_as_loop(node); 648b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &loop->body) 649211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 650b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 651b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 652b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott case nir_cf_node_function: { 653b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott nir_function_impl *impl = nir_cf_node_as_function(node); 654b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott foreach_list_typed(nir_cf_node, child, node, &impl->body) 655211c79515d2d4cde12cc6a19bb064692b2de3f26Connor Abbott cleanup_cf_node(child, impl); 656b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott break; 657b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 658b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott default: 659b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott unreachable("Invalid CF node type"); 660b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott } 661b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott} 662b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbott 663b49371b8ede380f10ea3ab333246a3b01ac6aca5Connor Abbottvoid 664fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_extract(nir_cf_list *extracted, nir_cursor begin, nir_cursor end) 665fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 666fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_block *block_begin, *block_end, *block_before, *block_after; 667fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 66897b663481c8c83fda06246860708530cff755a05Jason Ekstrand if (nir_cursors_equal(begin, end)) { 66997b663481c8c83fda06246860708530cff755a05Jason Ekstrand exec_list_make_empty(&extracted->list); 67097b663481c8c83fda06246860708530cff755a05Jason Ekstrand extracted->impl = NULL; /* we shouldn't need this */ 67197b663481c8c83fda06246860708530cff755a05Jason Ekstrand return; 67297b663481c8c83fda06246860708530cff755a05Jason Ekstrand } 67397b663481c8c83fda06246860708530cff755a05Jason Ekstrand 674fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott /* In the case where begin points to an instruction in some basic block and 675fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * end points to the end of the same basic block, we rely on the fact that 676fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * splitting on an instruction moves earlier instructions into a new basic 677fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * block. If the later instructions were moved instead, then the end cursor 678fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * would be pointing to the same place that begin used to point to, which 679fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott * is obviously not what we want. 680fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott */ 681fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(begin, &block_before, &block_begin); 682fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(end, &block_end, &block_after); 683fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 684fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott extracted->impl = nir_cf_node_get_function(&block_begin->cf_node); 685fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_list_make_empty(&extracted->list); 686fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 687fbaa1b19d7accc5de95d6804525aad5b95abba72Kenneth Graunke /* Dominance and other block-related information is toast. */ 688fbaa1b19d7accc5de95d6804525aad5b95abba72Kenneth Graunke nir_metadata_preserve(extracted->impl, nir_metadata_none); 689fbaa1b19d7accc5de95d6804525aad5b95abba72Kenneth Graunke 690fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *cf_node = &block_begin->cf_node; 691fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *cf_node_end = &block_end->cf_node; 692fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott while (true) { 693fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node *next = nir_cf_node_next(cf_node); 694fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 695fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_remove(&cf_node->node); 696fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cf_node->parent = NULL; 697fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_list_push_tail(&extracted->list, &cf_node->node); 698fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 699fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott if (cf_node == cf_node_end) 700fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott break; 701fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 702fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cf_node = next; 703fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 704fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 705fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(block_before, block_after); 706fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 707fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 708fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 709fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_reinsert(nir_cf_list *cf_list, nir_cursor cursor) 710fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 711fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_block *before, *after; 712fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 71397b663481c8c83fda06246860708530cff755a05Jason Ekstrand if (exec_list_is_empty(&cf_list->list)) 71497b663481c8c83fda06246860708530cff755a05Jason Ekstrand return; 71597b663481c8c83fda06246860708530cff755a05Jason Ekstrand 716fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott split_block_cursor(cursor, &before, &after); 717fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 718fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott foreach_list_typed_safe(nir_cf_node, node, node, &cf_list->list) { 719fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_remove(&node->node); 720fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott node->parent = before->cf_node.parent; 721fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott exec_node_insert_node_before(&after->cf_node.node, &node->node); 722fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 723fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 724fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(before, 725fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott nir_cf_node_as_block(nir_cf_node_next(&before->cf_node))); 726fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott stitch_blocks(nir_cf_node_as_block(nir_cf_node_prev(&after->cf_node)), 727fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott after); 728fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 729fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott 730fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottvoid 731fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbottnir_cf_delete(nir_cf_list *cf_list) 732fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott{ 733fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott foreach_list_typed(nir_cf_node, node, node, &cf_list->list) { 734fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott cleanup_cf_node(node, cf_list->impl); 735fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott } 736fc7f2d2364a98d4ec8fb8627b03c6f84b353998cConnor Abbott} 737