gcc/ccmp.c

   1 /* Conditional compare related functions
   2    Copyright (C) 2014-2016 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 "tm_p.h"
  29 #include "ssa.h"
  30 #include "expmed.h"
  31 #include "optabs.h"
  32 #include "emit-rtl.h"
  33 #include "stor-layout.h"
  34 #include "tree-ssa-live.h"
  35 #include "tree-outof-ssa.h"
  36 #include "cfgexpand.h"
  37 #include "ccmp.h"
  38
  39 /* The following functions expand conditional compare (CCMP) instructions.
  40    Here is a short description about the over all algorithm:
  41      * ccmp_candidate_p is used to identify the CCMP candidate
  42
  43      * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
  44        to expand CCMP.
  45
  46      * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
  47        It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
  48        CCMP instructions.
  49          - gen_ccmp_first expands the first compare in CCMP.
  50          - gen_ccmp_next expands the following compares.
  51
  52        Both hooks return a comparison with the CC register that is equivalent
  53        to the value of the gimple comparison.  This is used by the next CCMP
  54        and in the final conditional store.
  55
  56      * We use cstorecc4 pattern to convert the CCmode intermediate to
  57        the integer mode result that expand_normal is expecting.
  58
  59    Since the operands of the later compares might clobber CC reg, we do not
  60    emit the insns during expand.  We keep the insn sequences in two seq
  61
  62      * prep_seq, which includes all the insns to prepare the operands.
  63      * gen_seq, which includes all the compare and conditional compares.
  64
  65    If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
  66    insns in gen_seq.  */
  67
  68 /* Check whether G is a potential conditional compare candidate.  */
  69 static bool
  70 ccmp_candidate_p (gimple *g)
  71 {
  72   tree rhs = gimple_assign_rhs_to_tree (g);
  73   tree lhs, op0, op1;
  74   gimple *gs0, *gs1;
  75   enum tree_code tcode, tcode0, tcode1;
  76   tcode = TREE_CODE (rhs);
  77
  78   if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
  79     return false;
  80
  81   lhs = gimple_assign_lhs (g);
  82   op0 = TREE_OPERAND (rhs, 0);
  83   op1 = TREE_OPERAND (rhs, 1);
  84
  85   if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
  86       || !has_single_use (lhs))
  87     return false;
  88
  89   gs0 = get_gimple_for_ssa_name (op0);
  90   gs1 = get_gimple_for_ssa_name (op1);
  91   if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1)
  92       /* g, gs0 and gs1 must be in the same basic block, since current stage
  93          is out-of-ssa.  We can not guarantee the correctness when forwording
  94          the gs0 and gs1 into g whithout DATAFLOW analysis.  */
  95       || gimple_bb (gs0) != gimple_bb (gs1)
  96       || gimple_bb (gs0) != gimple_bb (g))
  97     return false;
  98
  99   if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))
 100        || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))))
 101       || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))
 102            || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))))
 103     return false;
 104
 105   tcode0 = gimple_assign_rhs_code (gs0);
 106   tcode1 = gimple_assign_rhs_code (gs1);
 107   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 108       && TREE_CODE_CLASS (tcode1) == tcc_comparison)
 109     return true;
 110   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 111       && ccmp_candidate_p (gs1))
 112     return true;
 113   else if (TREE_CODE_CLASS (tcode1) == tcc_comparison
 114            && ccmp_candidate_p (gs0))
 115     return true;
 116   /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
 117      there is no way to set the CC flag.  */
 118   return false;
 119 }
 120
 121 /* PREV is a comparison with the CC register which represents the
 122    result of the previous CMP or CCMP.  The function expands the
 123    next compare based on G which is ANDed/ORed with the previous
 124    compare depending on CODE.
 125    PREP_SEQ returns all insns to prepare opearands for compare.
 126    GEN_SEQ returns all compare insns.  */
 127 static rtx
 128 expand_ccmp_next (gimple *g, enum tree_code code, rtx prev,
 129                   rtx *prep_seq, rtx *gen_seq)
 130 {
 131   enum rtx_code rcode;
 132   int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
 133
 134   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 135
 136   rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp);
 137
 138   return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
 139                                 gimple_assign_rhs1 (g),
 140                                 gimple_assign_rhs2 (g),
 141                                 get_rtx_code (code, 0));
 142 }
 143
 144 /* Expand conditional compare gimple G.  A typical CCMP sequence is like:
 145
 146      CC0 = CMP (a, b);
 147      CC1 = CCMP (NE (CC0, 0), CMP (e, f));
 148      ...
 149      CCn = CCMP (NE (CCn-1, 0), CMP (...));
 150
 151    hook gen_ccmp_first is used to expand the first compare.
 152    hook gen_ccmp_next is used to expand the following CCMP.
 153    PREP_SEQ returns all insns to prepare opearand.
 154    GEN_SEQ returns all compare insns.  */
 155 static rtx
 156 expand_ccmp_expr_1 (gimple *g, rtx *prep_seq, rtx *gen_seq)
 157 {
 158   tree exp = gimple_assign_rhs_to_tree (g);
 159   enum tree_code code = TREE_CODE (exp);
 160   gimple *gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0));
 161   gimple *gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1));
 162   rtx tmp;
 163   enum tree_code code0 = gimple_assign_rhs_code (gs0);
 164   enum tree_code code1 = gimple_assign_rhs_code (gs1);
 165
 166   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 167   gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1));
 168
 169   if (TREE_CODE_CLASS (code0) == tcc_comparison)
 170     {
 171       if (TREE_CODE_CLASS (code1) == tcc_comparison)
 172         {
 173           int unsignedp0;
 174           enum rtx_code rcode0;
 175
 176           unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
 177           rcode0 = get_rtx_code (code0, unsignedp0);
 178
 179           tmp = targetm.gen_ccmp_first (prep_seq, gen_seq, rcode0,
 180                                         gimple_assign_rhs1 (gs0),
 181                                         gimple_assign_rhs2 (gs0));
 182           if (!tmp)
 183             return NULL_RTX;
 184
 185           return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
 186         }
 187       else
 188         {
 189           tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
 190           if (!tmp)
 191             return NULL_RTX;
 192
 193           return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq);
 194         }
 195     }
 196   else
 197     {
 198       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 199                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 200
 201       if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison)
 202         {
 203           tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
 204           if (!tmp)
 205             return NULL_RTX;
 206
 207           return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
 208         }
 209       else
 210         {
 211           gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR
 212                       || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR);
 213         }
 214     }
 215
 216   return NULL_RTX;
 217 }
 218
 219 /* Main entry to expand conditional compare statement G.
 220    Return NULL_RTX if G is not a legal candidate or expand fail.
 221    Otherwise return the target.  */
 222 rtx
 223 expand_ccmp_expr (gimple *g)
 224 {
 225   rtx_insn *last;
 226   rtx tmp;
 227   rtx prep_seq, gen_seq;
 228
 229   prep_seq = gen_seq = NULL_RTX;
 230
 231   if (!ccmp_candidate_p (g))
 232     return NULL_RTX;
 233
 234   last = get_last_insn ();
 235   tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
 236
 237   if (tmp)
 238     {
 239       enum insn_code icode;
 240       enum machine_mode cc_mode = CCmode;
 241       tree lhs = gimple_assign_lhs (g);
 242       rtx_code cmp_code = GET_CODE (tmp);
 243
 244 #ifdef SELECT_CC_MODE
 245       cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
 246 #endif
 247       icode = optab_handler (cstore_optab, cc_mode);
 248       if (icode != CODE_FOR_nothing)
 249         {
 250           enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
 251           rtx target = gen_reg_rtx (mode);
 252
 253           emit_insn (prep_seq);
 254           emit_insn (gen_seq);
 255
 256           tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
 257                              0, XEXP (tmp, 0), const0_rtx, 1, mode);
 258           if (tmp)
 259             return tmp;
 260         }
 261     }
 262   /* Clean up.  */
 263   delete_insns_since (last);
 264   return NULL_RTX;
 265 }
 266