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