1 /* 2 * Copyright 2016 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 */ 23 24 #include "nir.h" 25 26 /** 27 * \file nir_opt_move_comparisons.c 28 * 29 * This pass moves ALU comparison operations just before their first use. 30 * 31 * It only moves instructions within a single basic block; cross-block 32 * movement is left to global code motion. 33 * 34 * Many GPUs generate condition codes for comparisons, and use predication 35 * for conditional selects and control flow. In a sequence such as: 36 * 37 * vec1 32 ssa_1 = flt a b 38 * <some other operations> 39 * vec1 32 ssa_2 = bcsel ssa_1 c d 40 * 41 * the backend would likely do the comparison, producing condition codes, 42 * then save those to a boolean value. The intervening operations might 43 * trash the condition codes. Then, in order to do the bcsel, it would 44 * need to re-populate the condition code register based on the boolean. 45 * 46 * By moving the comparison just before the bcsel, the condition codes could 47 * be used directly. This eliminates the need to reload them from the boolean 48 * (generally eliminating an instruction). It may also eliminate the need to 49 * create a boolean value altogether (unless it's used elsewhere), which could 50 * lower register pressure. 51 */ 52 53 static bool 54 is_comparison(nir_op op) 55 { 56 switch (op) { 57 case nir_op_flt: 58 case nir_op_fge: 59 case nir_op_feq: 60 case nir_op_fne: 61 case nir_op_ilt: 62 case nir_op_ult: 63 case nir_op_ige: 64 case nir_op_uge: 65 case nir_op_ieq: 66 case nir_op_ine: 67 case nir_op_i2b: 68 case nir_op_f2b: 69 case nir_op_inot: 70 case nir_op_fnot: 71 return true; 72 default: 73 return false; 74 } 75 } 76 77 static bool 78 move_comparison_source(nir_src *src, nir_block *block, nir_instr *before) 79 { 80 if (!src->is_ssa) 81 return false; 82 83 nir_instr *src_instr = src->ssa->parent_instr; 84 85 if (src_instr->block == block && 86 src_instr->type == nir_instr_type_alu && 87 is_comparison(nir_instr_as_alu(src_instr)->op)) { 88 89 exec_node_remove(&src_instr->node); 90 91 if (before) 92 exec_node_insert_node_before(&before->node, &src_instr->node); 93 else 94 exec_list_push_tail(&block->instr_list, &src_instr->node); 95 96 return true; 97 } 98 99 return false; 100 } 101 102 static bool 103 move_comparison_source_cb(nir_src *src, void *data) 104 { 105 bool *progress = data; 106 107 nir_instr *instr = src->parent_instr; 108 if (move_comparison_source(src, instr->block, instr)) 109 *progress = true; 110 111 return true; /* nir_foreach_src should keep going */ 112 } 113 114 static bool 115 move_comparisons(nir_block *block) 116 { 117 bool progress = false; 118 119 /* We use a simple approach: walk instructions backwards. 120 * 121 * If the instruction's source is a comparison from the same block, 122 * simply move it here. This may break SSA if it's used earlier in 123 * the block as well. However, as we walk backwards, we'll find the 124 * earlier use and move it again, further up. It eventually ends up 125 * dominating all uses again, restoring SSA form. 126 * 127 * Before walking instructions, we consider the if-condition at the 128 * end of the block, if one exists. It's effectively a use at the 129 * bottom of the block. 130 */ 131 nir_if *iff = nir_block_get_following_if(block); 132 if (iff) { 133 progress |= move_comparison_source(&iff->condition, block, NULL); 134 } 135 136 nir_foreach_instr_reverse(instr, block) { 137 /* The sources of phi instructions happen after the predecessor block 138 * but before this block. (Yes, that's between blocks). This means 139 * that we don't need to move them in order for them to be correct. 140 * We could move them to encourage comparisons that are used in a phi to 141 * the end of the block, doing so correctly would make the pass 142 * substantially more complicated and wouldn't gain us anything since 143 * the phi can't use a flag value anyway. 144 */ 145 if (instr->type == nir_instr_type_phi) { 146 /* We're going backwards so everything else is a phi too */ 147 break; 148 } else if (instr->type == nir_instr_type_alu) { 149 /* Walk ALU instruction sources backwards so that bcsel's boolean 150 * condition is processed last. 151 */ 152 nir_alu_instr *alu = nir_instr_as_alu(instr); 153 for (int i = nir_op_infos[alu->op].num_inputs - 1; i >= 0; i--) { 154 progress |= move_comparison_source(&alu->src[i].src, 155 block, instr); 156 } 157 } else { 158 nir_foreach_src(instr, move_comparison_source_cb, &progress); 159 } 160 } 161 162 return progress; 163 } 164 165 bool 166 nir_opt_move_comparisons(nir_shader *shader) 167 { 168 bool progress = false; 169 170 nir_foreach_function(func, shader) { 171 if (!func->impl) 172 continue; 173 174 nir_foreach_block(block, func->impl) { 175 if (move_comparisons(block)) { 176 nir_metadata_preserve(func->impl, nir_metadata_block_index | 177 nir_metadata_dominance | 178 nir_metadata_live_ssa_defs); 179 progress = true; 180 } 181 } 182 } 183 184 return progress; 185 } 186