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 "input.h"
  27 #include "alias.h"
  28 #include "symtab.h"
  29 #include "tree.h"
  30 #include "fold-const.h"
  31 #include "stringpool.h"
  32 #include "stor-layout.h"
  33 #include "regs.h"
  34 #include "hard-reg-set.h"
  35 #include "function.h"
  36 #include "flags.h"
  37 #include "insn-config.h"
  38 #include "expmed.h"
  39 #include "dojump.h"
  40 #include "explow.h"
  41 #include "calls.h"
  42 #include "emit-rtl.h"
  43 #include "varasm.h"
  44 #include "stmt.h"
  45 #include "expr.h"
  46 #include "insn-codes.h"
  47 #include "optabs.h"
  48 #include "tree-iterator.h"
  49 #include "predict.h"
  50 #include "dominance.h"
  51 #include "cfg.h"
  52 #include "basic-block.h"
  53 #include "tree-ssa-alias.h"
  54 #include "internal-fn.h"
  55 #include "gimple-expr.h"
  56 #include "is-a.h"
  57 #include "gimple.h"
  58 #include "gimple-ssa.h"
  59 #include "tree-ssanames.h"
  60 #include "target.h"
  61 #include "common/common-target.h"
  62 #include "df.h"
  63 #include "tree-ssa-live.h"
  64 #include "tree-outof-ssa.h"
  65 #include "cfgexpand.h"
  66 #include "tree-phinodes.h"
  67 #include "ssa-iterators.h"
  68 #include "ccmp.h"
  69
  70 /* The following functions expand conditional compare (CCMP) instructions.
  71    Here is a short description about the over all algorithm:
  72      * ccmp_candidate_p is used to identify the CCMP candidate
  73
  74      * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
  75        to expand CCMP.
  76
  77      * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
  78        It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
  79        CCMP instructions.
  80          - gen_ccmp_first expands the first compare in CCMP.
  81          - gen_ccmp_next expands the following compares.
  82
  83      * We use cstorecc4 pattern to convert the CCmode intermediate to
  84        the integer mode result that expand_normal is expecting.
  85
  86    Since the operands of the later compares might clobber CC reg, we do not
  87    emit the insns during expand.  We keep the insn sequences in two seq
  88
  89      * prep_seq, which includes all the insns to prepare the operands.
  90      * gen_seq, which includes all the compare and conditional compares.
  91
  92    If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
  93    insns in gen_seq.  */
  94
  95 /* Check whether G is a potential conditional compare candidate.  */
  96 static bool
  97 ccmp_candidate_p (gimple g)
  98 {
  99   tree rhs = gimple_assign_rhs_to_tree (g);
 100   tree lhs, op0, op1;
 101   gimple gs0, gs1;
 102   enum tree_code tcode, tcode0, tcode1;
 103   tcode = TREE_CODE (rhs);
 104
 105   if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
 106     return false;
 107
 108   lhs = gimple_assign_lhs (g);
 109   op0 = TREE_OPERAND (rhs, 0);
 110   op1 = TREE_OPERAND (rhs, 1);
 111
 112   if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
 113       || !has_single_use (lhs))
 114     return false;
 115
 116   gs0 = get_gimple_for_ssa_name (op0);
 117   gs1 = get_gimple_for_ssa_name (op1);
 118   if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1)
 119       /* g, gs0 and gs1 must be in the same basic block, since current stage
 120          is out-of-ssa.  We can not guarantee the correctness when forwording
 121          the gs0 and gs1 into g whithout DATAFLOW analysis.  */
 122       || gimple_bb (gs0) != gimple_bb (gs1)
 123       || gimple_bb (gs0) != gimple_bb (g))
 124     return false;
 125
 126   if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))
 127        || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))))
 128       || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))
 129            || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))))
 130     return false;
 131
 132   tcode0 = gimple_assign_rhs_code (gs0);
 133   tcode1 = gimple_assign_rhs_code (gs1);
 134   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 135       && TREE_CODE_CLASS (tcode1) == tcc_comparison)
 136     return true;
 137   if (TREE_CODE_CLASS (tcode0) == tcc_comparison
 138       && ccmp_candidate_p (gs1))
 139     return true;
 140   else if (TREE_CODE_CLASS (tcode1) == tcc_comparison
 141            && ccmp_candidate_p (gs0))
 142     return true;
 143   /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
 144      there is no way to set the CC flag.  */
 145   return false;
 146 }
 147
 148 /* PREV is the CC flag from precvious compares.  The function expands the
 149    next compare based on G which ops previous compare with CODE.
 150    PREP_SEQ returns all insns to prepare opearands for compare.
 151    GEN_SEQ returnss all compare insns.  */
 152 static rtx
 153 expand_ccmp_next (gimple g, enum tree_code code, rtx prev,
 154                   rtx *prep_seq, rtx *gen_seq)
 155 {
 156   enum rtx_code rcode;
 157   int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
 158
 159   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 160
 161   rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp);
 162
 163   return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
 164                                 gimple_assign_rhs1 (g),
 165                                 gimple_assign_rhs2 (g),
 166                                 get_rtx_code (code, 0));
 167 }
 168
 169 /* Expand conditional compare gimple G.  A typical CCMP sequence is like:
 170
 171      CC0 = CMP (a, b);
 172      CC1 = CCMP (NE (CC0, 0), CMP (e, f));
 173      ...
 174      CCn = CCMP (NE (CCn-1, 0), CMP (...));
 175
 176    hook gen_ccmp_first is used to expand the first compare.
 177    hook gen_ccmp_next is used to expand the following CCMP.
 178    PREP_SEQ returns all insns to prepare opearand.
 179    GEN_SEQ returns all compare insns.  */
 180 static rtx
 181 expand_ccmp_expr_1 (gimple g, rtx *prep_seq, rtx *gen_seq)
 182 {
 183   tree exp = gimple_assign_rhs_to_tree (g);
 184   enum tree_code code = TREE_CODE (exp);
 185   gimple gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0));
 186   gimple gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1));
 187   rtx tmp;
 188   enum tree_code code0 = gimple_assign_rhs_code (gs0);
 189   enum tree_code code1 = gimple_assign_rhs_code (gs1);
 190
 191   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 192   gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1));
 193
 194   if (TREE_CODE_CLASS (code0) == tcc_comparison)
 195     {
 196       if (TREE_CODE_CLASS (code1) == tcc_comparison)
 197         {
 198           int unsignedp0;
 199           enum rtx_code rcode0;
 200
 201           unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
 202           rcode0 = get_rtx_code (code0, unsignedp0);
 203
 204           tmp = targetm.gen_ccmp_first (prep_seq, gen_seq, rcode0,
 205                                         gimple_assign_rhs1 (gs0),
 206                                         gimple_assign_rhs2 (gs0));
 207           if (!tmp)
 208             return NULL_RTX;
 209
 210           return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
 211         }
 212       else
 213         {
 214           tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
 215           if (!tmp)
 216             return NULL_RTX;
 217
 218           return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq);
 219         }
 220     }
 221   else
 222     {
 223       gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
 224                   || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
 225
 226       if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison)
 227         {
 228           tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
 229           if (!tmp)
 230             return NULL_RTX;
 231
 232           return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
 233         }
 234       else
 235         {
 236           gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR
 237                       || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR);
 238         }
 239     }
 240
 241   return NULL_RTX;
 242 }
 243
 244 /* Main entry to expand conditional compare statement G.
 245    Return NULL_RTX if G is not a legal candidate or expand fail.
 246    Otherwise return the target.  */
 247 rtx
 248 expand_ccmp_expr (gimple g)
 249 {
 250   rtx_insn *last;
 251   rtx tmp;
 252   rtx prep_seq, gen_seq;
 253
 254   prep_seq = gen_seq = NULL_RTX;
 255
 256   if (!ccmp_candidate_p (g))
 257     return NULL_RTX;
 258
 259   last = get_last_insn ();
 260   tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
 261
 262   if (tmp)
 263     {
 264       enum insn_code icode;
 265       enum machine_mode cc_mode = CCmode;
 266       tree lhs = gimple_assign_lhs (g);
 267
 268 #ifdef SELECT_CC_MODE
 269       cc_mode = SELECT_CC_MODE (NE, tmp, const0_rtx);
 270 #endif
 271       icode = optab_handler (cstore_optab, cc_mode);
 272       if (icode != CODE_FOR_nothing)
 273         {
 274           enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
 275           rtx target = gen_reg_rtx (mode);
 276
 277           emit_insn (prep_seq);
 278           emit_insn (gen_seq);
 279
 280           tmp = emit_cstore (target, icode, NE, cc_mode, cc_mode,
 281                              0, tmp, const0_rtx, 1, mode);
 282           if (tmp)
 283             return tmp;
 284         }
 285     }
 286   /* Clean up.  */
 287   delete_insns_since (last);
 288   return NULL_RTX;
 289 }
 290