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_insn **prep_seq, rtx_insn **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_insn **prep_seq, rtx_insn **gen_seq)
 153 {
 154   tree exp = gimple_assign_rhs_to_tree (g);
 155   tree_code code = TREE_CODE (exp);
 156   gimple *gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0));
 157   gimple *gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1));
 158   rtx tmp;
 159   tree_code code0 = gimple_assign_rhs_code (gs0);
 160   tree_code code1 = gimple_assign_rhs_code (gs1);
 161
 162   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 163   gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1));
 164
 165   if (TREE_CODE_CLASS (code0) == tcc_comparison)
 166     {
 167       if (TREE_CODE_CLASS (code1) == tcc_comparison)
 168         {
 169           int unsignedp0, unsignedp1;
 170           rtx_code rcode0, rcode1;
 171           int speed_p = optimize_insn_for_speed_p ();
 172           rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
 173           unsigned cost1 = MAX_COST;
 174           unsigned cost2 = MAX_COST;
 175
 176           unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
 177           unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1)));
 178           rcode0 = get_rtx_code (code0, unsignedp0);
 179           rcode1 = get_rtx_code (code1, unsignedp1);
 180
 181           rtx_insn *prep_seq_1, *gen_seq_1;
 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 (prep_seq_1, speed_p);
 190               cost1 += seq_cost (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           rtx_insn *prep_seq_2, *gen_seq_2;
 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 (prep_seq_2, speed_p);
 211               cost2 += seq_cost (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
 266   if (!ccmp_candidate_p (g))
 267     return NULL_RTX;
 268
 269   last = get_last_insn ();
 270
 271   rtx_insn *prep_seq = NULL, *gen_seq = NULL;
 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