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