gcc/ccmp.c

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