1 /* Conditional compare related functions 2 Copyright (C) 2014-2018 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 /* Check whether T is a simple boolean variable or a SSA name 42 set by a comparison operator in the same basic block. */ 43 static bool 44 ccmp_tree_comparison_p (tree t, basic_block bb) 45 { 46 gimple *g = get_gimple_for_ssa_name (t); 47 tree_code tcode; 48 49 /* If we have a boolean variable allow it and generate a compare 50 to zero reg when expanding. */ 51 if (!g) 52 return (TREE_CODE (TREE_TYPE (t)) == BOOLEAN_TYPE); 53 54 /* Check to see if SSA name is set by a comparison operator in 55 the same basic block. */ 56 if (!is_gimple_assign (g)) 57 return false; 58 if (bb != gimple_bb (g)) 59 return false; 60 tcode = gimple_assign_rhs_code (g); 61 return TREE_CODE_CLASS (tcode) == tcc_comparison; 62 } 63 64 /* The following functions expand conditional compare (CCMP) instructions. 65 Here is a short description about the over all algorithm: 66 * ccmp_candidate_p is used to identify the CCMP candidate 67 68 * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1 69 to expand CCMP. 70 71 * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP. 72 It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate 73 CCMP instructions. 74 - gen_ccmp_first expands the first compare in CCMP. 75 - gen_ccmp_next expands the following compares. 76 77 Both hooks return a comparison with the CC register that is equivalent 78 to the value of the gimple comparison. This is used by the next CCMP 79 and in the final conditional store. 80 81 * We use cstorecc4 pattern to convert the CCmode intermediate to 82 the integer mode result that expand_normal is expecting. 83 84 Since the operands of the later compares might clobber CC reg, we do not 85 emit the insns during expand. We keep the insn sequences in two seq 86 87 * prep_seq, which includes all the insns to prepare the operands. 88 * gen_seq, which includes all the compare and conditional compares. 89 90 If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then 91 insns in gen_seq. */ 92 93 /* Check whether G is a potential conditional compare candidate. */ 94 static bool 95 ccmp_candidate_p (gimple *g) 96 { 97 tree rhs; 98 tree lhs, op0, op1; 99 gimple *gs0, *gs1; 100 tree_code tcode; 101 basic_block bb; 102 103 if (!g) 104 return false; 105 106 rhs = gimple_assign_rhs_to_tree (g); 107 tcode = TREE_CODE (rhs); 108 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR) 109 return false; 110 111 lhs = gimple_assign_lhs (g); 112 op0 = TREE_OPERAND (rhs, 0); 113 op1 = TREE_OPERAND (rhs, 1); 114 bb = gimple_bb (g); 115 116 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME) 117 || !has_single_use (lhs)) 118 return false; 119 120 gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */ 121 gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */ 122 123 if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb)) 124 return true; 125 if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1)) 126 return true; 127 if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0)) 128 return true; 129 /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since 130 there is no way to set and maintain the CC flag on both sides of 131 the logical operator at the same time. */ 132 return false; 133 } 134 135 /* Extract the comparison we want to do from the tree. */ 136 void 137 get_compare_parts (tree t, int *up, rtx_code *rcode, 138 tree *rhs1, tree *rhs2) 139 { 140 tree_code code; 141 gimple *g = get_gimple_for_ssa_name (t); 142 if (g) 143 { 144 *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g))); 145 code = gimple_assign_rhs_code (g); 146 *rcode = get_rtx_code (code, *up); 147 *rhs1 = gimple_assign_rhs1 (g); 148 *rhs2 = gimple_assign_rhs2 (g); 149 } 150 else 151 { 152 /* If g is not a comparison operator create a compare to zero. */ 153 *up = 1; 154 *rcode = NE; 155 *rhs1 = t; 156 *rhs2 = build_zero_cst (TREE_TYPE (t)); 157 } 158 } 159 160 /* PREV is a comparison with the CC register which represents the 161 result of the previous CMP or CCMP. The function expands the 162 next compare based on G which is ANDed/ORed with the previous 163 compare depending on CODE. 164 PREP_SEQ returns all insns to prepare opearands for compare. 165 GEN_SEQ returns all compare insns. */ 166 static rtx 167 expand_ccmp_next (tree op, tree_code code, rtx prev, 168 rtx_insn **prep_seq, rtx_insn **gen_seq) 169 { 170 rtx_code rcode; 171 int unsignedp; 172 tree rhs1, rhs2; 173 174 get_compare_parts(op, &unsignedp, &rcode, &rhs1, &rhs2); 175 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode, 176 rhs1, rhs2, get_rtx_code (code, 0)); 177 } 178 179 /* Expand conditional compare gimple G. A typical CCMP sequence is like: 180 181 CC0 = CMP (a, b); 182 CC1 = CCMP (NE (CC0, 0), CMP (e, f)); 183 ... 184 CCn = CCMP (NE (CCn-1, 0), CMP (...)); 185 186 hook gen_ccmp_first is used to expand the first compare. 187 hook gen_ccmp_next is used to expand the following CCMP. 188 PREP_SEQ returns all insns to prepare opearand. 189 GEN_SEQ returns all compare insns. */ 190 static rtx 191 expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq) 192 { 193 tree exp = gimple_assign_rhs_to_tree (g); 194 tree_code code = TREE_CODE (exp); 195 basic_block bb = gimple_bb (g); 196 197 tree op0 = TREE_OPERAND (exp, 0); 198 tree op1 = TREE_OPERAND (exp, 1); 199 gimple *gs0 = get_gimple_for_ssa_name (op0); 200 gimple *gs1 = get_gimple_for_ssa_name (op1); 201 rtx tmp; 202 203 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); 204 205 if (ccmp_tree_comparison_p (op0, bb)) 206 { 207 if (ccmp_tree_comparison_p (op1, bb)) 208 { 209 int unsignedp0, unsignedp1; 210 rtx_code rcode0, rcode1; 211 tree logical_op0_rhs1, logical_op0_rhs2; 212 tree logical_op1_rhs1, logical_op1_rhs2; 213 int speed_p = optimize_insn_for_speed_p (); 214 215 rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX; 216 unsigned cost1 = MAX_COST; 217 unsigned cost2 = MAX_COST; 218 219 get_compare_parts (op0, &unsignedp0, &rcode0, 220 &logical_op0_rhs1, &logical_op0_rhs2); 221 222 get_compare_parts (op1, &unsignedp1, &rcode1, 223 &logical_op1_rhs1, &logical_op1_rhs2); 224 225 rtx_insn *prep_seq_1, *gen_seq_1; 226 tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0, 227 logical_op0_rhs1, logical_op0_rhs2); 228 if (tmp != NULL) 229 { 230 ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1); 231 cost1 = seq_cost (prep_seq_1, speed_p); 232 cost1 += seq_cost (gen_seq_1, speed_p); 233 } 234 235 /* FIXME: Temporary workaround for PR69619. 236 Avoid exponential compile time due to expanding gs0 and gs1 twice. 237 If gs0 and gs1 are complex, the cost will be high, so avoid 238 reevaluation if above an arbitrary threshold. */ 239 rtx_insn *prep_seq_2, *gen_seq_2; 240 if (tmp == NULL || cost1 < COSTS_N_INSNS (25)) 241 tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1, 242 logical_op1_rhs1, logical_op1_rhs2); 243 if (!tmp && !tmp2) 244 return NULL_RTX; 245 if (tmp2 != NULL) 246 { 247 ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2, 248 &gen_seq_2); 249 cost2 = seq_cost (prep_seq_2, speed_p); 250 cost2 += seq_cost (gen_seq_2, speed_p); 251 } 252 if (cost2 < cost1) 253 { 254 *prep_seq = prep_seq_2; 255 *gen_seq = gen_seq_2; 256 return ret2; 257 } 258 *prep_seq = prep_seq_1; 259 *gen_seq = gen_seq_1; 260 return ret; 261 } 262 else 263 { 264 tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq); 265 if (!tmp) 266 return NULL_RTX; 267 return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq); 268 } 269 } 270 else 271 { 272 gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR 273 || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR); 274 gcc_assert (ccmp_tree_comparison_p (op1, bb)); 275 tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq); 276 if (!tmp) 277 return NULL_RTX; 278 return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq); 279 } 280 281 return NULL_RTX; 282 } 283 284 /* Main entry to expand conditional compare statement G. 285 Return NULL_RTX if G is not a legal candidate or expand fail. 286 Otherwise return the target. */ 287 rtx 288 expand_ccmp_expr (gimple *g, machine_mode mode) 289 { 290 rtx_insn *last; 291 rtx tmp; 292 293 if (!ccmp_candidate_p (g)) 294 return NULL_RTX; 295 296 last = get_last_insn (); 297 298 rtx_insn *prep_seq = NULL, *gen_seq = NULL; 299 tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq); 300 301 if (tmp) 302 { 303 insn_code icode; 304 machine_mode cc_mode = CCmode; 305 rtx_code cmp_code = GET_CODE (tmp); 306 307 #ifdef SELECT_CC_MODE 308 cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx); 309 #endif 310 icode = optab_handler (cstore_optab, cc_mode); 311 if (icode != CODE_FOR_nothing) 312 { 313 rtx target = gen_reg_rtx (mode); 314 315 emit_insn (prep_seq); 316 emit_insn (gen_seq); 317 318 tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode, 319 0, XEXP (tmp, 0), const0_rtx, 1, mode); 320 if (tmp) 321 return tmp; 322 } 323 } 324 /* Clean up. */ 325 delete_insns_since (last); 326 return NULL_RTX; 327 } 328