1 /* Conditional compare related functions
2 Copyright (C) 2014-2018 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 "memmodel.h"
29 #include "tm_p.h"
30 #include "ssa.h"
31 #include "expmed.h"
32 #include "optabs.h"
33 #include "emit-rtl.h"
34 #include "stor-layout.h"
35 #include "tree-ssa-live.h"
36 #include "tree-outof-ssa.h"
37 #include "cfgexpand.h"
38 #include "ccmp.h"
39 #include "predict.h"
40
41 /* Check whether T is a simple boolean variable or a SSA name
42 set by a comparison operator in the same basic block. */
43 static bool
ccmp_tree_comparison_p(tree t,basic_block bb)44 ccmp_tree_comparison_p (tree t, basic_block bb)
45 {
46 gimple *g = get_gimple_for_ssa_name (t);
47 tree_code tcode;
48
49 /* If we have a boolean variable allow it and generate a compare
50 to zero reg when expanding. */
51 if (!g)
52 return (TREE_CODE (TREE_TYPE (t)) == BOOLEAN_TYPE);
53
54 /* Check to see if SSA name is set by a comparison operator in
55 the same basic block. */
56 if (!is_gimple_assign (g))
57 return false;
58 if (bb != gimple_bb (g))
59 return false;
60 tcode = gimple_assign_rhs_code (g);
61 return TREE_CODE_CLASS (tcode) == tcc_comparison;
62 }
63
64 /* The following functions expand conditional compare (CCMP) instructions.
65 Here is a short description about the over all algorithm:
66 * ccmp_candidate_p is used to identify the CCMP candidate
67
68 * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
69 to expand CCMP.
70
71 * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
72 It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
73 CCMP instructions.
74 - gen_ccmp_first expands the first compare in CCMP.
75 - gen_ccmp_next expands the following compares.
76
77 Both hooks return a comparison with the CC register that is equivalent
78 to the value of the gimple comparison. This is used by the next CCMP
79 and in the final conditional store.
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
ccmp_candidate_p(gimple * g)95 ccmp_candidate_p (gimple *g)
96 {
97 tree rhs;
98 tree lhs, op0, op1;
99 gimple *gs0, *gs1;
100 tree_code tcode;
101 basic_block bb;
102
103 if (!g)
104 return false;
105
106 rhs = gimple_assign_rhs_to_tree (g);
107 tcode = TREE_CODE (rhs);
108 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
109 return false;
110
111 lhs = gimple_assign_lhs (g);
112 op0 = TREE_OPERAND (rhs, 0);
113 op1 = TREE_OPERAND (rhs, 1);
114 bb = gimple_bb (g);
115
116 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
117 || !has_single_use (lhs))
118 return false;
119
120 gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
121 gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
122
123 if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
124 return true;
125 if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
126 return true;
127 if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
128 return true;
129 /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
130 there is no way to set and maintain the CC flag on both sides of
131 the logical operator at the same time. */
132 return false;
133 }
134
135 /* Extract the comparison we want to do from the tree. */
136 void
get_compare_parts(tree t,int * up,rtx_code * rcode,tree * rhs1,tree * rhs2)137 get_compare_parts (tree t, int *up, rtx_code *rcode,
138 tree *rhs1, tree *rhs2)
139 {
140 tree_code code;
141 gimple *g = get_gimple_for_ssa_name (t);
142 if (g)
143 {
144 *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
145 code = gimple_assign_rhs_code (g);
146 *rcode = get_rtx_code (code, *up);
147 *rhs1 = gimple_assign_rhs1 (g);
148 *rhs2 = gimple_assign_rhs2 (g);
149 }
150 else
151 {
152 /* If g is not a comparison operator create a compare to zero. */
153 *up = 1;
154 *rcode = NE;
155 *rhs1 = t;
156 *rhs2 = build_zero_cst (TREE_TYPE (t));
157 }
158 }
159
160 /* PREV is a comparison with the CC register which represents the
161 result of the previous CMP or CCMP. The function expands the
162 next compare based on G which is ANDed/ORed with the previous
163 compare depending on CODE.
164 PREP_SEQ returns all insns to prepare opearands for compare.
165 GEN_SEQ returns all compare insns. */
166 static rtx
expand_ccmp_next(tree op,tree_code code,rtx prev,rtx_insn ** prep_seq,rtx_insn ** gen_seq)167 expand_ccmp_next (tree op, tree_code code, rtx prev,
168 rtx_insn **prep_seq, rtx_insn **gen_seq)
169 {
170 rtx_code rcode;
171 int unsignedp;
172 tree rhs1, rhs2;
173
174 get_compare_parts(op, &unsignedp, &rcode, &rhs1, &rhs2);
175 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
176 rhs1, rhs2, 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. */
190 static rtx
expand_ccmp_expr_1(gimple * g,rtx_insn ** prep_seq,rtx_insn ** gen_seq)191 expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
192 {
193 tree exp = gimple_assign_rhs_to_tree (g);
194 tree_code code = TREE_CODE (exp);
195 basic_block bb = gimple_bb (g);
196
197 tree op0 = TREE_OPERAND (exp, 0);
198 tree op1 = TREE_OPERAND (exp, 1);
199 gimple *gs0 = get_gimple_for_ssa_name (op0);
200 gimple *gs1 = get_gimple_for_ssa_name (op1);
201 rtx tmp;
202
203 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
204
205 if (ccmp_tree_comparison_p (op0, bb))
206 {
207 if (ccmp_tree_comparison_p (op1, bb))
208 {
209 int unsignedp0, unsignedp1;
210 rtx_code rcode0, rcode1;
211 tree logical_op0_rhs1, logical_op0_rhs2;
212 tree logical_op1_rhs1, logical_op1_rhs2;
213 int speed_p = optimize_insn_for_speed_p ();
214
215 rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
216 unsigned cost1 = MAX_COST;
217 unsigned cost2 = MAX_COST;
218
219 get_compare_parts (op0, &unsignedp0, &rcode0,
220 &logical_op0_rhs1, &logical_op0_rhs2);
221
222 get_compare_parts (op1, &unsignedp1, &rcode1,
223 &logical_op1_rhs1, &logical_op1_rhs2);
224
225 rtx_insn *prep_seq_1, *gen_seq_1;
226 tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
227 logical_op0_rhs1, logical_op0_rhs2);
228 if (tmp != NULL)
229 {
230 ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
231 cost1 = seq_cost (prep_seq_1, speed_p);
232 cost1 += seq_cost (gen_seq_1, speed_p);
233 }
234
235 /* FIXME: Temporary workaround for PR69619.
236 Avoid exponential compile time due to expanding gs0 and gs1 twice.
237 If gs0 and gs1 are complex, the cost will be high, so avoid
238 reevaluation if above an arbitrary threshold. */
239 rtx_insn *prep_seq_2, *gen_seq_2;
240 if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
241 tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
242 logical_op1_rhs1, logical_op1_rhs2);
243 if (!tmp && !tmp2)
244 return NULL_RTX;
245 if (tmp2 != NULL)
246 {
247 ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
248 &gen_seq_2);
249 cost2 = seq_cost (prep_seq_2, speed_p);
250 cost2 += seq_cost (gen_seq_2, speed_p);
251 }
252 if (cost2 < cost1)
253 {
254 *prep_seq = prep_seq_2;
255 *gen_seq = gen_seq_2;
256 return ret2;
257 }
258 *prep_seq = prep_seq_1;
259 *gen_seq = gen_seq_1;
260 return ret;
261 }
262 else
263 {
264 tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
265 if (!tmp)
266 return NULL_RTX;
267 return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
268 }
269 }
270 else
271 {
272 gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
273 || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
274 gcc_assert (ccmp_tree_comparison_p (op1, bb));
275 tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
276 if (!tmp)
277 return NULL_RTX;
278 return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
279 }
280
281 return NULL_RTX;
282 }
283
284 /* Main entry to expand conditional compare statement G.
285 Return NULL_RTX if G is not a legal candidate or expand fail.
286 Otherwise return the target. */
287 rtx
expand_ccmp_expr(gimple * g,machine_mode mode)288 expand_ccmp_expr (gimple *g, machine_mode mode)
289 {
290 rtx_insn *last;
291 rtx tmp;
292
293 if (!ccmp_candidate_p (g))
294 return NULL_RTX;
295
296 last = get_last_insn ();
297
298 rtx_insn *prep_seq = NULL, *gen_seq = NULL;
299 tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
300
301 if (tmp)
302 {
303 insn_code icode;
304 machine_mode cc_mode = CCmode;
305 rtx_code cmp_code = GET_CODE (tmp);
306
307 #ifdef SELECT_CC_MODE
308 cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
309 #endif
310 icode = optab_handler (cstore_optab, cc_mode);
311 if (icode != CODE_FOR_nothing)
312 {
313 rtx target = gen_reg_rtx (mode);
314
315 emit_insn (prep_seq);
316 emit_insn (gen_seq);
317
318 tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
319 0, XEXP (tmp, 0), const0_rtx, 1, mode);
320 if (tmp)
321 return tmp;
322 }
323 }
324 /* Clean up. */
325 delete_insns_since (last);
326 return NULL_RTX;
327 }
328