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_code code = gimple_assign_rhs_code (g);
 191   basic_block bb = gimple_bb (g);
 192
 193   tree op0 = gimple_assign_rhs1 (g);
 194   tree op1 = gimple_assign_rhs2 (g);
 195   gimple *gs0 = get_gimple_for_ssa_name (op0);
 196   gimple *gs1 = get_gimple_for_ssa_name (op1);
 197   rtx tmp;
 198
 199   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 200
 201   if (ccmp_tree_comparison_p (op0, bb))
 202     {
 203       if (ccmp_tree_comparison_p (op1, bb))
 204         {
 205           int unsignedp0, unsignedp1;
 206           rtx_code rcode0, rcode1;
 207           tree logical_op0_rhs1, logical_op0_rhs2;
 208           tree logical_op1_rhs1, logical_op1_rhs2;
 209           int speed_p = optimize_insn_for_speed_p ();
 210
 211           rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
 212           unsigned cost1 = MAX_COST;
 213           unsigned cost2 = MAX_COST;
 214
 215           get_compare_parts (op0, &unsignedp0, &rcode0,
 216                              &logical_op0_rhs1, &logical_op0_rhs2);
 217
 218           get_compare_parts (op1, &unsignedp1, &rcode1,
 219                              &logical_op1_rhs1, &logical_op1_rhs2);
 220
 221           rtx_insn *prep_seq_1, *gen_seq_1;
 222           tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
 223                                         logical_op0_rhs1, logical_op0_rhs2);
 224           if (tmp != NULL)
 225             {
 226               ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
 227               cost1 = seq_cost (prep_seq_1, speed_p);
 228               cost1 += seq_cost (gen_seq_1, speed_p);
 229             }
 230
 231           /* FIXME: Temporary workaround for PR69619.
 232              Avoid exponential compile time due to expanding gs0 and gs1 twice.
 233              If gs0 and gs1 are complex, the cost will be high, so avoid
 234              reevaluation if above an arbitrary threshold.  */
 235           rtx_insn *prep_seq_2, *gen_seq_2;
 236           if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
 237             tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
 238                                            logical_op1_rhs1, logical_op1_rhs2);
 239           if (!tmp && !tmp2)
 240             return NULL_RTX;
 241           if (tmp2 != NULL)
 242             {
 243               ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
 244                                        &gen_seq_2);
 245               cost2 = seq_cost (prep_seq_2, speed_p);
 246               cost2 += seq_cost (gen_seq_2, speed_p);
 247             }
 248           if (cost2 < cost1)
 249             {
 250               *prep_seq = prep_seq_2;
 251               *gen_seq = gen_seq_2;
 252               return ret2;
 253             }
 254           *prep_seq = prep_seq_1;
 255           *gen_seq = gen_seq_1;
 256           return ret;
 257         }
 258       else
 259         {
 260           tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
 261           if (!tmp)
 262             return NULL_RTX;
 263           return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
 264         }
 265     }
 266   else
 267     {
 268       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 269                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 270       gcc_assert (ccmp_tree_comparison_p (op1, bb));
 271       tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
 272       if (!tmp)
 273         return NULL_RTX;
 274       return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
 275     }
 276
 277   return NULL_RTX;
 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))
 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 }