gcc/ccmp.cc

   1 /* Conditional compare related functions
   2    Copyright (C) 2014-2024 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; OUTER is true if
  94    G is the outer most AND/IOR.  */
  95 static bool
  96 ccmp_candidate_p (gimple *g, bool outer = false)
  97 {
  98   tree lhs, op0, op1;
  99   gimple *gs0, *gs1;
 100   tree_code tcode;
 101   basic_block bb;
 102
 103   if (!g)
 104     return false;
 105
 106   tcode = gimple_assign_rhs_code (g);
 107   if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
 108     return false;
 109
 110   lhs = gimple_assign_lhs (g);
 111   op0 = gimple_assign_rhs1 (g);
 112   op1 = gimple_assign_rhs2 (g);
 113   if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME))
 114     return false;
 115   if (!outer && !has_single_use (lhs))
 116     return false;
 117
 118   bb = gimple_bb (g);
 119   gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
 120   gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
 121
 122   if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
 123     return true;
 124   if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
 125     return true;
 126   if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
 127     return true;
 128   /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
 129      there is no way to set and maintain the CC flag on both sides of
 130      the logical operator at the same time.  */
 131   return false;
 132 }
 133
 134 /* Extract the comparison we want to do from the tree.  */
 135 void
 136 get_compare_parts (tree t, int *up, rtx_code *rcode,
 137                    tree *rhs1, tree *rhs2)
 138 {
 139   tree_code code;
 140   gimple *g = get_gimple_for_ssa_name (t);
 141   if (g)
 142     {
 143       *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
 144       code = gimple_assign_rhs_code (g);
 145       *rcode = get_rtx_code (code, *up);
 146       *rhs1 = gimple_assign_rhs1 (g);
 147       *rhs2 = gimple_assign_rhs2 (g);
 148     }
 149   else
 150     {
 151       /* If g is not a comparison operator create a compare to zero.  */
 152       *up = 1;
 153       *rcode = NE;
 154       *rhs1 = t;
 155       *rhs2 = build_zero_cst (TREE_TYPE (t));
 156     }
 157 }
 158
 159 /* PREV is a comparison with the CC register which represents the
 160    result of the previous CMP or CCMP.  The function expands the
 161    next compare based on G which is ANDed/ORed with the previous
 162    compare depending on CODE.
 163    PREP_SEQ returns all insns to prepare opearands for compare.
 164    GEN_SEQ returns all compare insns.  */
 165 static rtx
 166 expand_ccmp_next (tree op, tree_code code, rtx prev,
 167                   rtx_insn **prep_seq, rtx_insn **gen_seq)
 168 {
 169   rtx_code rcode;
 170   int unsignedp;
 171   tree rhs1, rhs2;
 172
 173   get_compare_parts(op, &unsignedp, &rcode, &rhs1, &rhs2);
 174   return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
 175                                 rhs1, rhs2, get_rtx_code (code, 0));
 176 }
 177
 178 /* Expand conditional compare gimple G.  A typical CCMP sequence is like:
 179
 180      CC0 = CMP (a, b);
 181      CC1 = CCMP (NE (CC0, 0), CMP (e, f));
 182      ...
 183      CCn = CCMP (NE (CCn-1, 0), CMP (...));
 184
 185    hook gen_ccmp_first is used to expand the first compare.
 186    hook gen_ccmp_next is used to expand the following CCMP.
 187    PREP_SEQ returns all insns to prepare opearand.
 188    GEN_SEQ returns all compare insns.  */
 189 static rtx
 190 expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
 191 {
 192   tree_code code = gimple_assign_rhs_code (g);
 193   basic_block bb = gimple_bb (g);
 194
 195   tree op0 = gimple_assign_rhs1 (g);
 196   tree op1 = gimple_assign_rhs2 (g);
 197   gimple *gs0 = get_gimple_for_ssa_name (op0);
 198   gimple *gs1 = get_gimple_for_ssa_name (op1);
 199   rtx tmp;
 200
 201   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 202
 203   if (ccmp_tree_comparison_p (op0, bb))
 204     {
 205       if (ccmp_tree_comparison_p (op1, bb))
 206         {
 207           int unsignedp0, unsignedp1;
 208           rtx_code rcode0, rcode1;
 209           tree logical_op0_rhs1, logical_op0_rhs2;
 210           tree logical_op1_rhs1, logical_op1_rhs2;
 211           int speed_p = optimize_insn_for_speed_p ();
 212
 213           rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
 214           unsigned cost1 = MAX_COST;
 215           unsigned cost2 = MAX_COST;
 216
 217           get_compare_parts (op0, &unsignedp0, &rcode0,
 218                              &logical_op0_rhs1, &logical_op0_rhs2);
 219
 220           get_compare_parts (op1, &unsignedp1, &rcode1,
 221                              &logical_op1_rhs1, &logical_op1_rhs2);
 222
 223           rtx_insn *prep_seq_1, *gen_seq_1;
 224           tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
 225                                         logical_op0_rhs1, logical_op0_rhs2);
 226           if (tmp != NULL)
 227             {
 228               ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
 229               cost1 = seq_cost (prep_seq_1, speed_p);
 230               cost1 += seq_cost (gen_seq_1, speed_p);
 231             }
 232
 233           /* FIXME: Temporary workaround for PR69619.
 234              Avoid exponential compile time due to expanding gs0 and gs1 twice.
 235              If gs0 and gs1 are complex, the cost will be high, so avoid
 236              reevaluation if above an arbitrary threshold.  */
 237           rtx_insn *prep_seq_2, *gen_seq_2;
 238           if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
 239             tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
 240                                            logical_op1_rhs1, logical_op1_rhs2);
 241           if (!tmp && !tmp2)
 242             return NULL_RTX;
 243           if (tmp2 != NULL)
 244             {
 245               ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
 246                                        &gen_seq_2);
 247               cost2 = seq_cost (prep_seq_2, speed_p);
 248               cost2 += seq_cost (gen_seq_2, speed_p);
 249             }
 250
 251           /* It's possible that one expansion succeeds and the other
 252              fails.
 253              For example, x86 has int ccmp but not fp ccmp, and so a
 254              combined fp and int comparison must be ordered such that
 255              the fp comparison happens first. The costs are not
 256              meaningful for failed expansions.  */
 257
 258           if (ret2 && (!ret || cost2 < cost1))
 259             {
 260               *prep_seq = prep_seq_2;
 261               *gen_seq = gen_seq_2;
 262               return ret2;
 263             }
 264           *prep_seq = prep_seq_1;
 265           *gen_seq = gen_seq_1;
 266           return ret;
 267         }
 268       else
 269         {
 270           tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
 271           if (!tmp)
 272             return NULL_RTX;
 273           return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
 274         }
 275     }
 276   else
 277     {
 278       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 279                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 280       gcc_assert (ccmp_tree_comparison_p (op1, bb));
 281       tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
 282       if (!tmp)
 283         return NULL_RTX;
 284       return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
 285     }
 286 }
 287
 288 /* Main entry to expand conditional compare statement G.
 289    Return NULL_RTX if G is not a legal candidate or expand fail.
 290    Otherwise return the target.  */
 291 rtx
 292 expand_ccmp_expr (gimple *g, machine_mode mode)
 293 {
 294   rtx_insn *last;
 295   rtx tmp;
 296
 297   if (!ccmp_candidate_p (g, true))
 298     return NULL_RTX;
 299
 300   last = get_last_insn ();
 301
 302   rtx_insn *prep_seq = NULL, *gen_seq = NULL;
 303   tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
 304
 305   if (tmp)
 306     {
 307       insn_code icode;
 308       machine_mode cc_mode = CCmode;
 309       rtx_code cmp_code = GET_CODE (tmp);
 310
 311 #ifdef SELECT_CC_MODE
 312       cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
 313 #endif
 314       icode = optab_handler (cstore_optab, cc_mode);
 315       if (icode != CODE_FOR_nothing)
 316         {
 317           rtx target = gen_reg_rtx (mode);
 318
 319           emit_insn (prep_seq);
 320           emit_insn (gen_seq);
 321
 322           tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
 323                              0, XEXP (tmp, 0), const0_rtx, 1, mode);
 324           if (tmp)
 325             return tmp;
 326         }
 327     }
 328   /* Clean up.  */
 329   delete_insns_since (last);
 330   return NULL_RTX;
 331 }