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      * 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