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