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