1 /* Conditional compare related functions 2 Copyright (C) 2014-2015 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 "tm.h" 24 #include "rtl.h" 25 #include "tm_p.h" 26 #include "hash-set.h" 27 #include "machmode.h" 28 #include "vec.h" 29 #include "double-int.h" 30 #include "input.h" 31 #include "alias.h" 32 #include "symtab.h" 33 #include "wide-int.h" 34 #include "inchash.h" 35 #include "tree.h" 36 #include "fold-const.h" 37 #include "stringpool.h" 38 #include "stor-layout.h" 39 #include "regs.h" 40 #include "hashtab.h" 41 #include "hard-reg-set.h" 42 #include "function.h" 43 #include "flags.h" 44 #include "statistics.h" 45 #include "real.h" 46 #include "fixed-value.h" 47 #include "insn-config.h" 48 #include "expmed.h" 49 #include "dojump.h" 50 #include "explow.h" 51 #include "calls.h" 52 #include "emit-rtl.h" 53 #include "varasm.h" 54 #include "stmt.h" 55 #include "expr.h" 56 #include "insn-codes.h" 57 #include "optabs.h" 58 #include "tree-iterator.h" 59 #include "predict.h" 60 #include "dominance.h" 61 #include "cfg.h" 62 #include "basic-block.h" 63 #include "tree-ssa-alias.h" 64 #include "internal-fn.h" 65 #include "gimple-expr.h" 66 #include "is-a.h" 67 #include "gimple.h" 68 #include "gimple-ssa.h" 69 #include "tree-ssanames.h" 70 #include "target.h" 71 #include "common/common-target.h" 72 #include "df.h" 73 #include "tree-ssa-live.h" 74 #include "tree-outof-ssa.h" 75 #include "cfgexpand.h" 76 #include "tree-phinodes.h" 77 #include "ssa-iterators.h" 78 #include "ccmp.h" 79 80 /* The following functions expand conditional compare (CCMP) instructions. 81 Here is a short description about the over all algorithm: 82 * ccmp_candidate_p is used to identify the CCMP candidate 83 84 * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1 85 to expand CCMP. 86 87 * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP. 88 It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate 89 CCMP instructions. 90 - gen_ccmp_first expands the first compare in CCMP. 91 - gen_ccmp_next expands the following compares. 92 93 * We use cstorecc4 pattern to convert the CCmode intermediate to 94 the integer mode result that expand_normal is expecting. 95 96 Since the operands of the later compares might clobber CC reg, we do not 97 emit the insns during expand. We keep the insn sequences in two seq 98 99 * prep_seq, which includes all the insns to prepare the operands. 100 * gen_seq, which includes all the compare and conditional compares. 101 102 If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then 103 insns in gen_seq. */ 104 105 /* Check whether G is a potential conditional compare candidate. */ 106 static bool 107 ccmp_candidate_p (gimple g) 108 { 109 tree rhs = gimple_assign_rhs_to_tree (g); 110 tree lhs, op0, op1; 111 gimple gs0, gs1; 112 enum tree_code tcode, tcode0, tcode1; 113 tcode = TREE_CODE (rhs); 114 115 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR) 116 return false; 117 118 lhs = gimple_assign_lhs (g); 119 op0 = TREE_OPERAND (rhs, 0); 120 op1 = TREE_OPERAND (rhs, 1); 121 122 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME) 123 || !has_single_use (lhs)) 124 return false; 125 126 gs0 = get_gimple_for_ssa_name (op0); 127 gs1 = get_gimple_for_ssa_name (op1); 128 if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1) 129 /* g, gs0 and gs1 must be in the same basic block, since current stage 130 is out-of-ssa. We can not guarantee the correctness when forwording 131 the gs0 and gs1 into g whithout DATAFLOW analysis. */ 132 || gimple_bb (gs0) != gimple_bb (gs1) 133 || gimple_bb (gs0) != gimple_bb (g)) 134 return false; 135 136 if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))) 137 || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))) 138 || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1))) 139 || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1))))) 140 return false; 141 142 tcode0 = gimple_assign_rhs_code (gs0); 143 tcode1 = gimple_assign_rhs_code (gs1); 144 if (TREE_CODE_CLASS (tcode0) == tcc_comparison 145 && TREE_CODE_CLASS (tcode1) == tcc_comparison) 146 return true; 147 if (TREE_CODE_CLASS (tcode0) == tcc_comparison 148 && ccmp_candidate_p (gs1)) 149 return true; 150 else if (TREE_CODE_CLASS (tcode1) == tcc_comparison 151 && ccmp_candidate_p (gs0)) 152 return true; 153 /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since 154 there is no way to set the CC flag. */ 155 return false; 156 } 157 158 /* PREV is the CC flag from precvious compares. The function expands the 159 next compare based on G which ops previous compare with CODE. 160 PREP_SEQ returns all insns to prepare opearands for compare. 161 GEN_SEQ returnss all compare insns. */ 162 static rtx 163 expand_ccmp_next (gimple g, enum tree_code code, rtx prev, 164 rtx *prep_seq, rtx *gen_seq) 165 { 166 enum rtx_code rcode; 167 int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g))); 168 169 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); 170 171 rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp); 172 173 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode, 174 gimple_assign_rhs1 (g), 175 gimple_assign_rhs2 (g), 176 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 *prep_seq, rtx *gen_seq) 192 { 193 tree exp = gimple_assign_rhs_to_tree (g); 194 enum tree_code code = TREE_CODE (exp); 195 gimple gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0)); 196 gimple gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1)); 197 rtx tmp; 198 enum tree_code code0 = gimple_assign_rhs_code (gs0); 199 enum tree_code code1 = gimple_assign_rhs_code (gs1); 200 201 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); 202 gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1)); 203 204 if (TREE_CODE_CLASS (code0) == tcc_comparison) 205 { 206 if (TREE_CODE_CLASS (code1) == tcc_comparison) 207 { 208 int unsignedp0; 209 enum rtx_code rcode0; 210 211 unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0))); 212 rcode0 = get_rtx_code (code0, unsignedp0); 213 214 tmp = targetm.gen_ccmp_first (prep_seq, gen_seq, rcode0, 215 gimple_assign_rhs1 (gs0), 216 gimple_assign_rhs2 (gs0)); 217 if (!tmp) 218 return NULL_RTX; 219 220 return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq); 221 } 222 else 223 { 224 tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq); 225 if (!tmp) 226 return NULL_RTX; 227 228 return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq); 229 } 230 } 231 else 232 { 233 gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR 234 || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR); 235 236 if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison) 237 { 238 tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq); 239 if (!tmp) 240 return NULL_RTX; 241 242 return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq); 243 } 244 else 245 { 246 gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR 247 || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR); 248 } 249 } 250 251 return NULL_RTX; 252 } 253 254 /* Main entry to expand conditional compare statement G. 255 Return NULL_RTX if G is not a legal candidate or expand fail. 256 Otherwise return the target. */ 257 rtx 258 expand_ccmp_expr (gimple g) 259 { 260 rtx_insn *last; 261 rtx tmp; 262 rtx prep_seq, gen_seq; 263 264 prep_seq = gen_seq = NULL_RTX; 265 266 if (!ccmp_candidate_p (g)) 267 return NULL_RTX; 268 269 last = get_last_insn (); 270 tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq); 271 272 if (tmp) 273 { 274 enum insn_code icode; 275 enum machine_mode cc_mode = CCmode; 276 tree lhs = gimple_assign_lhs (g); 277 278 #ifdef SELECT_CC_MODE 279 cc_mode = SELECT_CC_MODE (NE, tmp, const0_rtx); 280 #endif 281 icode = optab_handler (cstore_optab, cc_mode); 282 if (icode != CODE_FOR_nothing) 283 { 284 enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); 285 rtx target = gen_reg_rtx (mode); 286 287 emit_insn (prep_seq); 288 emit_insn (gen_seq); 289 290 tmp = emit_cstore (target, icode, NE, cc_mode, cc_mode, 291 0, tmp, const0_rtx, 1, mode); 292 if (tmp) 293 return tmp; 294 } 295 } 296 /* Clean up. */ 297 delete_insns_since (last); 298 return NULL_RTX; 299 } 300 301