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