gcc/ccmp.c

   1 /* Conditional compare related functions
   2    Copyright (C) 2014-2015 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 "tm.h"
  24 #include "rtl.h"
  25 #include "tm_p.h"
  26 #include "hash-set.h"
  27 #include "machmode.h"
  28 #include "vec.h"
  29 #include "double-int.h"
  30 #include "input.h"
  31 #include "alias.h"
  32 #include "symtab.h"
  33 #include "wide-int.h"
  34 #include "inchash.h"
  35 #include "tree.h"
  36 #include "fold-const.h"
  37 #include "stringpool.h"
  38 #include "stor-layout.h"
  39 #include "regs.h"
  40 #include "expr.h"
  41 #include "insn-codes.h"
  42 #include "optabs.h"
  43 #include "tree-iterator.h"
  44 #include "predict.h"
  45 #include "dominance.h"
  46 #include "cfg.h"
  47 #include "basic-block.h"
  48 #include "tree-ssa-alias.h"
  49 #include "internal-fn.h"
  50 #include "gimple-expr.h"
  51 #include "is-a.h"
  52 #include "gimple.h"
  53 #include "gimple-ssa.h"
  54 #include "tree-ssanames.h"
  55 #include "target.h"
  56 #include "common/common-target.h"
  57 #include "df.h"
  58 #include "tree-ssa-live.h"
  59 #include "tree-outof-ssa.h"
  60 #include "cfgexpand.h"
  61 #include "tree-phinodes.h"
  62 #include "ssa-iterators.h"
  63 #include "expmed.h"
  64 #include "ccmp.h"
  65
  66 /* The following functions expand conditional compare (CCMP) instructions.
  67    Here is a short description about the over all algorithm:
  68      * ccmp_candidate_p is used to identify the CCMP candidate
  69
  70      * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
  71        to expand CCMP.
  72
  73      * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
  74        It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
  75        CCMP instructions.
  76          - gen_ccmp_first expands the first compare in CCMP.
  77          - gen_ccmp_next expands the following compares.
  78
  79      * If the final result is not used in a COND_EXPR (checked by function
  80        used_in_cond_stmt_p), it calls cstorecc4 pattern to store the CC to a
  81        general register.  */
  82
  83 /* Check whether G is a potential conditional compare candidate.  */
  84 static bool
  85 ccmp_candidate_p (gimple g)
  86 {
  87   tree rhs = gimple_assign_rhs_to_tree (g);
  88   tree lhs, op0, op1;
  89   gimple gs0, gs1;
  90   enum tree_code tcode, tcode0, tcode1;
  91   tcode = TREE_CODE (rhs);
  92
  93   if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
  94     return false;
  95
  96   lhs = gimple_assign_lhs (g);
  97   op0 = TREE_OPERAND (rhs, 0);
  98   op1 = TREE_OPERAND (rhs, 1);
  99
 100   if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
 101       || !has_single_use (lhs))
 102     return false;
 103
 104   gs0 = get_gimple_for_ssa_name (op0);
 105   gs1 = get_gimple_for_ssa_name (op1);
 106   if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1)
 107       /* g, gs0 and gs1 must be in the same basic block, since current stage
 108          is out-of-ssa.  We can not guarantee the correctness when forwording
 109          the gs0 and gs1 into g whithout DATAFLOW analysis.  */
 110       || gimple_bb (gs0) != gimple_bb (gs1)
 111       || gimple_bb (gs0) != gimple_bb (g))
 112     return false;
 113
 114   if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))
 115        || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))))
 116       || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))
 117            || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))))
 118     return false;
 119
 120   tcode0 = gimple_assign_rhs_code (gs0);
 121   tcode1 = gimple_assign_rhs_code (gs1);
 122   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 123       && TREE_CODE_CLASS (tcode1) == tcc_comparison)
 124     return true;
 125   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 126       && ccmp_candidate_p (gs1))
 127     return true;
 128   else if (TREE_CODE_CLASS (tcode1) == tcc_comparison
 129            && ccmp_candidate_p (gs0))
 130     return true;
 131   /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
 132      there is no way to set the CC flag.  */
 133   return false;
 134 }
 135
 136 /* Check whether EXP is used in a GIMPLE_COND statement or not.  */
 137 static bool
 138 used_in_cond_stmt_p (tree exp)
 139 {
 140   bool expand_cond = false;
 141   imm_use_iterator ui;
 142   gimple use_stmt;
 143   FOR_EACH_IMM_USE_STMT (use_stmt, ui, exp)
 144     if (gimple_code (use_stmt) == GIMPLE_COND)
 145       {
 146         tree op1 = gimple_cond_rhs (use_stmt);
 147         if (integer_zerop (op1))
 148           expand_cond = true;
 149         BREAK_FROM_IMM_USE_STMT (ui);
 150       }
 151     else if (gimple_code (use_stmt) == GIMPLE_ASSIGN
 152              && gimple_expr_code (use_stmt) == COND_EXPR)
 153       {
 154         if (gimple_assign_rhs1 (use_stmt) == exp)
 155           expand_cond = true;
 156       }
 157
 158   return expand_cond;
 159 }
 160
 161 /* Expand conditional compare gimple G.  A typical CCMP sequence is like:
 162
 163      CC0 = CMP (a, b);
 164      CC1 = CCMP (NE (CC0, 0), CMP (e, f));
 165      ...
 166      CCn = CCMP (NE (CCn-1, 0), CMP (...));
 167
 168    hook gen_ccmp_first is used to expand the first compare.
 169    hook gen_ccmp_next is used to expand the following CCMP.  */
 170 static rtx
 171 expand_ccmp_expr_1 (gimple g)
 172 {
 173   tree exp = gimple_assign_rhs_to_tree (g);
 174   enum tree_code code = TREE_CODE (exp);
 175   gimple gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0));
 176   gimple gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1));
 177   rtx tmp;
 178   enum tree_code code0 = gimple_assign_rhs_code (gs0);
 179   enum tree_code code1 = gimple_assign_rhs_code (gs1);
 180
 181   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 182   gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1));
 183
 184   if (TREE_CODE_CLASS (code0) == tcc_comparison)
 185     {
 186       if (TREE_CODE_CLASS (code1) == tcc_comparison)
 187         {
 188           int unsignedp0, unsignedp1;
 189           enum rtx_code rcode0, rcode1;
 190           rtx op0, op1, op2, op3, tmp;
 191
 192           unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
 193           rcode0 = get_rtx_code (code0, unsignedp0);
 194           unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1)));
 195           rcode1 = get_rtx_code (code1, unsignedp1);
 196
 197           expand_operands (gimple_assign_rhs1 (gs0),
 198                            gimple_assign_rhs2 (gs0),
 199                            NULL_RTX, &op0, &op1, EXPAND_NORMAL);
 200
 201           /* Since the operands of GS1 might clobber CC reg, we expand the
 202              operands of GS1 before GEN_CCMP_FIRST.  */
 203           expand_operands (gimple_assign_rhs1 (gs1),
 204                            gimple_assign_rhs2 (gs1),
 205                            NULL_RTX, &op2, &op3, EXPAND_NORMAL);
 206           tmp = targetm.gen_ccmp_first (rcode0, op0, op1);
 207           if (!tmp)
 208             return NULL_RTX;
 209
 210           return targetm.gen_ccmp_next (tmp, rcode1, op2, op3,
 211                                         get_rtx_code (code, 0));
 212         }
 213       else
 214         {
 215           rtx op0, op1;
 216           enum rtx_code rcode;
 217           int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
 218
 219           rcode = get_rtx_code (gimple_assign_rhs_code (gs0), unsignedp);
 220
 221           /* Hoist the preparation operations above the entire
 222              conditional compare sequence.  */
 223           expand_operands (gimple_assign_rhs1 (gs0),
 224                            gimple_assign_rhs2 (gs0),
 225                            NULL_RTX, &op0, &op1, EXPAND_NORMAL);
 226
 227           gcc_assert (code1 == BIT_AND_EXPR || code1 == BIT_IOR_EXPR);
 228
 229           /* Note: We swap the order to make the recursive function work.  */
 230           tmp = expand_ccmp_expr_1 (gs1);
 231           if (tmp)
 232             return targetm.gen_ccmp_next (tmp, rcode, op0, op1,
 233                                           get_rtx_code (code, 0));
 234         }
 235     }
 236   else
 237     {
 238       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 239                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 240
 241       if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison)
 242         {
 243           rtx op0, op1;
 244           enum rtx_code rcode;
 245           int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1)));
 246
 247           rcode = get_rtx_code (gimple_assign_rhs_code (gs1), unsignedp);
 248
 249           /* Hoist the preparation operations above the entire
 250              conditional compare sequence.  */
 251           expand_operands (gimple_assign_rhs1 (gs1),
 252                            gimple_assign_rhs2 (gs1),
 253                            NULL_RTX, &op0, &op1, EXPAND_NORMAL);
 254           tmp = expand_ccmp_expr_1 (gs0);
 255           if (tmp)
 256             return targetm.gen_ccmp_next (tmp, rcode, op0, op1,
 257                                           get_rtx_code (code, 0));
 258         }
 259       else
 260         {
 261           gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR
 262                       || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR);
 263         }
 264     }
 265
 266   return NULL_RTX;
 267 }
 268
 269 /* Main entry to expand conditional compare statement G.
 270    Return NULL_RTX if G is not a legal candidate or expand fail.
 271    Otherwise return the target.  */
 272 rtx
 273 expand_ccmp_expr (gimple g)
 274 {
 275   rtx_insn *last;
 276   rtx tmp;
 277
 278   if (!ccmp_candidate_p (g))
 279     return NULL_RTX;
 280
 281   last = get_last_insn ();
 282   tmp = expand_ccmp_expr_1 (g);
 283
 284   if (tmp)
 285     {
 286       enum insn_code icode;
 287       enum machine_mode cc_mode = CCmode;
 288
 289       tree lhs = gimple_assign_lhs (g);
 290       /* TMP should be CC.  If it is used in a GIMPLE_COND, just return it.
 291          Note: Target needs to define "cbranchcc4".  */
 292       if (used_in_cond_stmt_p (lhs))
 293         return tmp;
 294
 295 #ifdef SELECT_CC_MODE
 296       cc_mode = SELECT_CC_MODE (NE, tmp, const0_rtx);
 297 #endif
 298       /* If TMP is not used in a GIMPLE_COND, store it with a csctorecc4_optab.
 299          Note: Target needs to define "cstorecc4".  */
 300       icode = optab_handler (cstore_optab, cc_mode);
 301       if (icode != CODE_FOR_nothing)
 302         {
 303           tree lhs = gimple_assign_lhs (g);
 304           enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
 305           rtx target = gen_reg_rtx (mode);
 306           tmp = emit_cstore (target, icode, NE, cc_mode, cc_mode,
 307                              0, tmp, const0_rtx, 1, mode);
 308           if (tmp)
 309             return tmp;
 310         }
 311     }
 312   /* Clean up.  */
 313   delete_insns_since (last);
 314   return NULL_RTX;
 315 }
 316