gcc/ccmp.c

   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      * If the final result is not used in a COND_EXPR (checked by function
  94        used_in_cond_stmt_p), it calls cstorecc4 pattern to store the CC to a
  95        general register.
  96
  97    Since the operands of the later compares might clobber CC reg, we do not
  98    emit the insns during expand.  We keep the insn sequences in two seq
  99
 100      * prep_seq, which includes all the insns to prepare the operands.
 101      * gen_seq, which includes all the compare and conditional compares.
 102
 103    If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
 104    insns in gen_seq.  */
 105
 106 /* Check whether G is a potential conditional compare candidate.  */
 107 static bool
 108 ccmp_candidate_p (gimple g)
 109 {
 110   tree rhs = gimple_assign_rhs_to_tree (g);
 111   tree lhs, op0, op1;
 112   gimple gs0, gs1;
 113   enum tree_code tcode, tcode0, tcode1;
 114   tcode = TREE_CODE (rhs);
 115
 116   if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
 117     return false;
 118
 119   lhs = gimple_assign_lhs (g);
 120   op0 = TREE_OPERAND (rhs, 0);
 121   op1 = TREE_OPERAND (rhs, 1);
 122
 123   if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
 124       || !has_single_use (lhs))
 125     return false;
 126
 127   gs0 = get_gimple_for_ssa_name (op0);
 128   gs1 = get_gimple_for_ssa_name (op1);
 129   if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1)
 130       /* g, gs0 and gs1 must be in the same basic block, since current stage
 131          is out-of-ssa.  We can not guarantee the correctness when forwording
 132          the gs0 and gs1 into g whithout DATAFLOW analysis.  */
 133       || gimple_bb (gs0) != gimple_bb (gs1)
 134       || gimple_bb (gs0) != gimple_bb (g))
 135     return false;
 136
 137   if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))
 138        || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))))
 139       || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))
 140            || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))))
 141     return false;
 142
 143   tcode0 = gimple_assign_rhs_code (gs0);
 144   tcode1 = gimple_assign_rhs_code (gs1);
 145   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 146       && TREE_CODE_CLASS (tcode1) == tcc_comparison)
 147     return true;
 148   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 149       && ccmp_candidate_p (gs1))
 150     return true;
 151   else if (TREE_CODE_CLASS (tcode1) == tcc_comparison
 152            && ccmp_candidate_p (gs0))
 153     return true;
 154   /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
 155      there is no way to set the CC flag.  */
 156   return false;
 157 }
 158
 159 /* Check whether EXP is used in a GIMPLE_COND statement or not.  */
 160 static bool
 161 used_in_cond_stmt_p (tree exp)
 162 {
 163   bool expand_cond = false;
 164   imm_use_iterator ui;
 165   gimple use_stmt;
 166   FOR_EACH_IMM_USE_STMT (use_stmt, ui, exp)
 167     if (gimple_code (use_stmt) == GIMPLE_COND)
 168       {
 169         tree op1 = gimple_cond_rhs (use_stmt);
 170         if (integer_zerop (op1))
 171           expand_cond = true;
 172         BREAK_FROM_IMM_USE_STMT (ui);
 173       }
 174     else if (gimple_code (use_stmt) == GIMPLE_ASSIGN
 175              && gimple_expr_code (use_stmt) == COND_EXPR)
 176       {
 177         if (gimple_assign_rhs1 (use_stmt) == exp)
 178           expand_cond = true;
 179       }
 180
 181   return expand_cond;
 182 }
 183
 184 /* PREV is the CC flag from precvious compares.  The function expands the
 185    next compare based on G which ops previous compare with CODE.
 186    PREP_SEQ returns all insns to prepare opearands for compare.
 187    GEN_SEQ returnss all compare insns.  */
 188 static rtx
 189 expand_ccmp_next (gimple g, enum tree_code code, rtx prev,
 190                   rtx *prep_seq, rtx *gen_seq)
 191 {
 192   enum rtx_code rcode;
 193   int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
 194
 195   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 196
 197   rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp);
 198
 199   return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
 200                                 gimple_assign_rhs1 (g),
 201                                 gimple_assign_rhs2 (g),
 202                                 get_rtx_code (code, 0));
 203 }
 204
 205 /* Expand conditional compare gimple G.  A typical CCMP sequence is like:
 206
 207      CC0 = CMP (a, b);
 208      CC1 = CCMP (NE (CC0, 0), CMP (e, f));
 209      ...
 210      CCn = CCMP (NE (CCn-1, 0), CMP (...));
 211
 212    hook gen_ccmp_first is used to expand the first compare.
 213    hook gen_ccmp_next is used to expand the following CCMP.
 214    PREP_SEQ returns all insns to prepare opearand.
 215    GEN_SEQ returns all compare insns.  */
 216 static rtx
 217 expand_ccmp_expr_1 (gimple g, rtx *prep_seq, rtx *gen_seq)
 218 {
 219   tree exp = gimple_assign_rhs_to_tree (g);
 220   enum tree_code code = TREE_CODE (exp);
 221   gimple gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0));
 222   gimple gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1));
 223   rtx tmp;
 224   enum tree_code code0 = gimple_assign_rhs_code (gs0);
 225   enum tree_code code1 = gimple_assign_rhs_code (gs1);
 226
 227   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 228   gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1));
 229
 230   if (TREE_CODE_CLASS (code0) == tcc_comparison)
 231     {
 232       if (TREE_CODE_CLASS (code1) == tcc_comparison)
 233         {
 234           int unsignedp0;
 235           enum rtx_code rcode0;
 236
 237           unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
 238           rcode0 = get_rtx_code (code0, unsignedp0);
 239
 240           tmp = targetm.gen_ccmp_first (prep_seq, gen_seq, rcode0,
 241                                         gimple_assign_rhs1 (gs0),
 242                                         gimple_assign_rhs2 (gs0));
 243           if (!tmp)
 244             return NULL_RTX;
 245
 246           return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
 247         }
 248       else
 249         {
 250           tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
 251           if (!tmp)
 252             return NULL_RTX;
 253
 254           return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq);
 255         }
 256     }
 257   else
 258     {
 259       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 260                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 261
 262       if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison)
 263         {
 264           tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
 265           if (!tmp)
 266             return NULL_RTX;
 267
 268           return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
 269         }
 270       else
 271         {
 272           gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR
 273                       || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR);
 274         }
 275     }
 276
 277   return NULL_RTX;
 278 }
 279
 280 /* Main entry to expand conditional compare statement G.
 281    Return NULL_RTX if G is not a legal candidate or expand fail.
 282    Otherwise return the target.  */
 283 rtx
 284 expand_ccmp_expr (gimple g)
 285 {
 286   rtx_insn *last;
 287   rtx tmp;
 288   rtx prep_seq, gen_seq;
 289
 290   prep_seq = gen_seq = NULL_RTX;
 291
 292   if (!ccmp_candidate_p (g))
 293     return NULL_RTX;
 294
 295   last = get_last_insn ();
 296   tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
 297
 298   if (tmp)
 299     {
 300       enum insn_code icode;
 301       enum machine_mode cc_mode = CCmode;
 302       tree lhs = gimple_assign_lhs (g);
 303
 304       /* TMP should be CC.  If it is used in a GIMPLE_COND, just return it.
 305          Note: Target needs to define "cbranchcc4".  */
 306       if (used_in_cond_stmt_p (lhs))
 307         {
 308           emit_insn (prep_seq);
 309           emit_insn (gen_seq);
 310           return tmp;
 311         }
 312
 313 #ifdef SELECT_CC_MODE
 314       cc_mode = SELECT_CC_MODE (NE, tmp, const0_rtx);
 315 #endif
 316       /* If TMP is not used in a GIMPLE_COND, store it with a csctorecc4_optab.
 317          Note: Target needs to define "cstorecc4".  */
 318       icode = optab_handler (cstore_optab, cc_mode);
 319       if (icode != CODE_FOR_nothing)
 320         {
 321           enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
 322           rtx target = gen_reg_rtx (mode);
 323
 324           emit_insn (prep_seq);
 325           emit_insn (gen_seq);
 326
 327           tmp = emit_cstore (target, icode, NE, cc_mode, cc_mode,
 328                              0, tmp, const0_rtx, 1, mode);
 329           if (tmp)
 330             return tmp;
 331         }
 332     }
 333   /* Clean up.  */
 334   delete_insns_since (last);
 335   return NULL_RTX;
 336 }
 337