gcc/ccmp.c

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