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           if (cost2 < cost1)
 251             {
 252               *prep_seq = prep_seq_2;
 253               *gen_seq = gen_seq_2;
 254               return ret2;
 255             }
 256           *prep_seq = prep_seq_1;
 257           *gen_seq = gen_seq_1;
 258           return ret;
 259         }
 260       else
 261         {
 262           tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
 263           if (!tmp)
 264             return NULL_RTX;
 265           return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
 266         }
 267     }
 268   else
 269     {
 270       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 271                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 272       gcc_assert (ccmp_tree_comparison_p (op1, bb));
 273       tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
 274       if (!tmp)
 275         return NULL_RTX;
 276       return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
 277     }
 278 }
 279
 280 /* Main entry to expand conditional compare statement G.
 281    Return NULL_RTX if G is not a legal candidate or expand fail.
 282    Otherwise return the target.  */
 283 rtx
 284 expand_ccmp_expr (gimple *g, machine_mode mode)
 285 {
 286   rtx_insn *last;
 287   rtx tmp;
 288
 289   if (!ccmp_candidate_p (g, true))
 290     return NULL_RTX;
 291
 292   last = get_last_insn ();
 293
 294   rtx_insn *prep_seq = NULL, *gen_seq = NULL;
 295   tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
 296
 297   if (tmp)
 298     {
 299       insn_code icode;
 300       machine_mode cc_mode = CCmode;
 301       rtx_code cmp_code = GET_CODE (tmp);
 302
 303 #ifdef SELECT_CC_MODE
 304       cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
 305 #endif
 306       icode = optab_handler (cstore_optab, cc_mode);
 307       if (icode != CODE_FOR_nothing)
 308         {
 309           rtx target = gen_reg_rtx (mode);
 310
 311           emit_insn (prep_seq);
 312           emit_insn (gen_seq);
 313
 314           tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
 315                              0, XEXP (tmp, 0), const0_rtx, 1, mode);
 316           if (tmp)
 317             return tmp;
 318         }
 319     }
 320   /* Clean up.  */
 321   delete_insns_since (last);
 322   return NULL_RTX;
 323 }