1 /* Conditional compare related functions 2 Copyright (C) 2014-2017 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "backend.h" 24 #include "target.h" 25 #include "rtl.h" 26 #include "tree.h" 27 #include "gimple.h" 28 #include "memmodel.h" 29 #include "tm_p.h" 30 #include "ssa.h" 31 #include "expmed.h" 32 #include "optabs.h" 33 #include "emit-rtl.h" 34 #include "stor-layout.h" 35 #include "tree-ssa-live.h" 36 #include "tree-outof-ssa.h" 37 #include "cfgexpand.h" 38 #include "ccmp.h" 39 #include "predict.h" 40 41 /* The following functions expand conditional compare (CCMP) instructions. 42 Here is a short description about the over all algorithm: 43 * ccmp_candidate_p is used to identify the CCMP candidate 44 45 * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1 46 to expand CCMP. 47 48 * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP. 49 It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate 50 CCMP instructions. 51 - gen_ccmp_first expands the first compare in CCMP. 52 - gen_ccmp_next expands the following compares. 53 54 Both hooks return a comparison with the CC register that is equivalent 55 to the value of the gimple comparison. This is used by the next CCMP 56 and in the final conditional store. 57 58 * We use cstorecc4 pattern to convert the CCmode intermediate to 59 the integer mode result that expand_normal is expecting. 60 61 Since the operands of the later compares might clobber CC reg, we do not 62 emit the insns during expand. We keep the insn sequences in two seq 63 64 * prep_seq, which includes all the insns to prepare the operands. 65 * gen_seq, which includes all the compare and conditional compares. 66 67 If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then 68 insns in gen_seq. */ 69 70 /* Check whether G is a potential conditional compare candidate. */ 71 static bool 72 ccmp_candidate_p (gimple *g) 73 { 74 tree rhs = gimple_assign_rhs_to_tree (g); 75 tree lhs, op0, op1; 76 gimple *gs0, *gs1; 77 tree_code tcode, tcode0, tcode1; 78 tcode = TREE_CODE (rhs); 79 80 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR) 81 return false; 82 83 lhs = gimple_assign_lhs (g); 84 op0 = TREE_OPERAND (rhs, 0); 85 op1 = TREE_OPERAND (rhs, 1); 86 87 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME) 88 || !has_single_use (lhs)) 89 return false; 90 91 gs0 = get_gimple_for_ssa_name (op0); 92 gs1 = get_gimple_for_ssa_name (op1); 93 if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1) 94 /* g, gs0 and gs1 must be in the same basic block, since current stage 95 is out-of-ssa. We can not guarantee the correctness when forwording 96 the gs0 and gs1 into g whithout DATAFLOW analysis. */ 97 || gimple_bb (gs0) != gimple_bb (gs1) 98 || gimple_bb (gs0) != gimple_bb (g)) 99 return false; 100 101 tcode0 = gimple_assign_rhs_code (gs0); 102 tcode1 = gimple_assign_rhs_code (gs1); 103 if (TREE_CODE_CLASS (tcode0) == tcc_comparison 104 && TREE_CODE_CLASS (tcode1) == tcc_comparison) 105 return true; 106 if (TREE_CODE_CLASS (tcode0) == tcc_comparison 107 && ccmp_candidate_p (gs1)) 108 return true; 109 else if (TREE_CODE_CLASS (tcode1) == tcc_comparison 110 && ccmp_candidate_p (gs0)) 111 return true; 112 /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since 113 there is no way to set the CC flag. */ 114 return false; 115 } 116 117 /* PREV is a comparison with the CC register which represents the 118 result of the previous CMP or CCMP. The function expands the 119 next compare based on G which is ANDed/ORed with the previous 120 compare depending on CODE. 121 PREP_SEQ returns all insns to prepare opearands for compare. 122 GEN_SEQ returns all compare insns. */ 123 static rtx 124 expand_ccmp_next (gimple *g, tree_code code, rtx prev, 125 rtx_insn **prep_seq, rtx_insn **gen_seq) 126 { 127 rtx_code rcode; 128 int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g))); 129 130 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); 131 132 rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp); 133 134 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode, 135 gimple_assign_rhs1 (g), 136 gimple_assign_rhs2 (g), 137 get_rtx_code (code, 0)); 138 } 139 140 /* Expand conditional compare gimple G. A typical CCMP sequence is like: 141 142 CC0 = CMP (a, b); 143 CC1 = CCMP (NE (CC0, 0), CMP (e, f)); 144 ... 145 CCn = CCMP (NE (CCn-1, 0), CMP (...)); 146 147 hook gen_ccmp_first is used to expand the first compare. 148 hook gen_ccmp_next is used to expand the following CCMP. 149 PREP_SEQ returns all insns to prepare opearand. 150 GEN_SEQ returns all compare insns. */ 151 static rtx 152 expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq) 153 { 154 tree exp = gimple_assign_rhs_to_tree (g); 155 tree_code code = TREE_CODE (exp); 156 gimple *gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0)); 157 gimple *gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1)); 158 rtx tmp; 159 tree_code code0 = gimple_assign_rhs_code (gs0); 160 tree_code code1 = gimple_assign_rhs_code (gs1); 161 162 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); 163 gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1)); 164 165 if (TREE_CODE_CLASS (code0) == tcc_comparison) 166 { 167 if (TREE_CODE_CLASS (code1) == tcc_comparison) 168 { 169 int unsignedp0, unsignedp1; 170 rtx_code rcode0, rcode1; 171 int speed_p = optimize_insn_for_speed_p (); 172 rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX; 173 unsigned cost1 = MAX_COST; 174 unsigned cost2 = MAX_COST; 175 176 unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0))); 177 unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1))); 178 rcode0 = get_rtx_code (code0, unsignedp0); 179 rcode1 = get_rtx_code (code1, unsignedp1); 180 181 rtx_insn *prep_seq_1, *gen_seq_1; 182 tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0, 183 gimple_assign_rhs1 (gs0), 184 gimple_assign_rhs2 (gs0)); 185 186 if (tmp != NULL) 187 { 188 ret = expand_ccmp_next (gs1, code, tmp, &prep_seq_1, &gen_seq_1); 189 cost1 = seq_cost (prep_seq_1, speed_p); 190 cost1 += seq_cost (gen_seq_1, speed_p); 191 } 192 193 /* FIXME: Temporary workaround for PR69619. 194 Avoid exponential compile time due to expanding gs0 and gs1 twice. 195 If gs0 and gs1 are complex, the cost will be high, so avoid 196 reevaluation if above an arbitrary threshold. */ 197 rtx_insn *prep_seq_2, *gen_seq_2; 198 if (tmp == NULL || cost1 < COSTS_N_INSNS (25)) 199 tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1, 200 gimple_assign_rhs1 (gs1), 201 gimple_assign_rhs2 (gs1)); 202 203 if (!tmp && !tmp2) 204 return NULL_RTX; 205 206 if (tmp2 != NULL) 207 { 208 ret2 = expand_ccmp_next (gs0, code, tmp2, &prep_seq_2, 209 &gen_seq_2); 210 cost2 = seq_cost (prep_seq_2, speed_p); 211 cost2 += seq_cost (gen_seq_2, speed_p); 212 } 213 214 if (cost2 < cost1) 215 { 216 *prep_seq = prep_seq_2; 217 *gen_seq = gen_seq_2; 218 return ret2; 219 } 220 221 *prep_seq = prep_seq_1; 222 *gen_seq = gen_seq_1; 223 return ret; 224 } 225 else 226 { 227 tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq); 228 if (!tmp) 229 return NULL_RTX; 230 231 return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq); 232 } 233 } 234 else 235 { 236 gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR 237 || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR); 238 239 if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison) 240 { 241 tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq); 242 if (!tmp) 243 return NULL_RTX; 244 245 return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq); 246 } 247 else 248 { 249 gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR 250 || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR); 251 } 252 } 253 254 return NULL_RTX; 255 } 256 257 /* Main entry to expand conditional compare statement G. 258 Return NULL_RTX if G is not a legal candidate or expand fail. 259 Otherwise return the target. */ 260 rtx 261 expand_ccmp_expr (gimple *g) 262 { 263 rtx_insn *last; 264 rtx tmp; 265 266 if (!ccmp_candidate_p (g)) 267 return NULL_RTX; 268 269 last = get_last_insn (); 270 271 rtx_insn *prep_seq = NULL, *gen_seq = NULL; 272 tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq); 273 274 if (tmp) 275 { 276 insn_code icode; 277 machine_mode cc_mode = CCmode; 278 tree lhs = gimple_assign_lhs (g); 279 rtx_code cmp_code = GET_CODE (tmp); 280 281 #ifdef SELECT_CC_MODE 282 cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx); 283 #endif 284 icode = optab_handler (cstore_optab, cc_mode); 285 if (icode != CODE_FOR_nothing) 286 { 287 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); 288 rtx target = gen_reg_rtx (mode); 289 290 emit_insn (prep_seq); 291 emit_insn (gen_seq); 292 293 tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode, 294 0, XEXP (tmp, 0), const0_rtx, 1, mode); 295 if (tmp) 296 return tmp; 297 } 298 } 299 /* Clean up. */ 300 delete_insns_since (last); 301 return NULL_RTX; 302 } 303 304