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