1 /* Conditional compare related functions
2 Copyright (C) 2014-2020 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 lhs, op0, op1;
98 gimple *gs0, *gs1;
99 tree_code tcode;
100 basic_block bb;
101
102 if (!g)
103 return false;
104
105 tcode = gimple_assign_rhs_code (g);
106 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
107 return false;
108
109 lhs = gimple_assign_lhs (g);
110 op0 = gimple_assign_rhs1 (g);
111 op1 = gimple_assign_rhs2 (g);
112 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
113 || !has_single_use (lhs))
114 return false;
115
116 bb = gimple_bb (g);
117 gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
118 gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
119
120 if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
121 return true;
122 if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
123 return true;
124 if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
125 return true;
126 /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
127 there is no way to set and maintain the CC flag on both sides of
128 the logical operator at the same time. */
129 return false;
130 }
131
132 /* Extract the comparison we want to do from the tree. */
133 void
get_compare_parts(tree t,int * up,rtx_code * rcode,tree * rhs1,tree * rhs2)134 get_compare_parts (tree t, int *up, rtx_code *rcode,
135 tree *rhs1, tree *rhs2)
136 {
137 tree_code code;
138 gimple *g = get_gimple_for_ssa_name (t);
139 if (g)
140 {
141 *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
142 code = gimple_assign_rhs_code (g);
143 *rcode = get_rtx_code (code, *up);
144 *rhs1 = gimple_assign_rhs1 (g);
145 *rhs2 = gimple_assign_rhs2 (g);
146 }
147 else
148 {
149 /* If g is not a comparison operator create a compare to zero. */
150 *up = 1;
151 *rcode = NE;
152 *rhs1 = t;
153 *rhs2 = build_zero_cst (TREE_TYPE (t));
154 }
155 }
156
157 /* PREV is a comparison with the CC register which represents the
158 result of the previous CMP or CCMP. The function expands the
159 next compare based on G which is ANDed/ORed with the previous
160 compare depending on CODE.
161 PREP_SEQ returns all insns to prepare opearands for compare.
162 GEN_SEQ returns all compare insns. */
163 static rtx
expand_ccmp_next(tree op,tree_code code,rtx prev,rtx_insn ** prep_seq,rtx_insn ** gen_seq)164 expand_ccmp_next (tree op, tree_code code, rtx prev,
165 rtx_insn **prep_seq, rtx_insn **gen_seq)
166 {
167 rtx_code rcode;
168 int unsignedp;
169 tree rhs1, rhs2;
170
171 get_compare_parts(op, &unsignedp, &rcode, &rhs1, &rhs2);
172 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
173 rhs1, rhs2, get_rtx_code (code, 0));
174 }
175
176 /* Expand conditional compare gimple G. A typical CCMP sequence is like:
177
178 CC0 = CMP (a, b);
179 CC1 = CCMP (NE (CC0, 0), CMP (e, f));
180 ...
181 CCn = CCMP (NE (CCn-1, 0), CMP (...));
182
183 hook gen_ccmp_first is used to expand the first compare.
184 hook gen_ccmp_next is used to expand the following CCMP.
185 PREP_SEQ returns all insns to prepare opearand.
186 GEN_SEQ returns all compare insns. */
187 static rtx
expand_ccmp_expr_1(gimple * g,rtx_insn ** prep_seq,rtx_insn ** gen_seq)188 expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
189 {
190 tree_code code = gimple_assign_rhs_code (g);
191 basic_block bb = gimple_bb (g);
192
193 tree op0 = gimple_assign_rhs1 (g);
194 tree op1 = gimple_assign_rhs2 (g);
195 gimple *gs0 = get_gimple_for_ssa_name (op0);
196 gimple *gs1 = get_gimple_for_ssa_name (op1);
197 rtx tmp;
198
199 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
200
201 if (ccmp_tree_comparison_p (op0, bb))
202 {
203 if (ccmp_tree_comparison_p (op1, bb))
204 {
205 int unsignedp0, unsignedp1;
206 rtx_code rcode0, rcode1;
207 tree logical_op0_rhs1, logical_op0_rhs2;
208 tree logical_op1_rhs1, logical_op1_rhs2;
209 int speed_p = optimize_insn_for_speed_p ();
210
211 rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
212 unsigned cost1 = MAX_COST;
213 unsigned cost2 = MAX_COST;
214
215 get_compare_parts (op0, &unsignedp0, &rcode0,
216 &logical_op0_rhs1, &logical_op0_rhs2);
217
218 get_compare_parts (op1, &unsignedp1, &rcode1,
219 &logical_op1_rhs1, &logical_op1_rhs2);
220
221 rtx_insn *prep_seq_1, *gen_seq_1;
222 tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
223 logical_op0_rhs1, logical_op0_rhs2);
224 if (tmp != NULL)
225 {
226 ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
227 cost1 = seq_cost (prep_seq_1, speed_p);
228 cost1 += seq_cost (gen_seq_1, speed_p);
229 }
230
231 /* FIXME: Temporary workaround for PR69619.
232 Avoid exponential compile time due to expanding gs0 and gs1 twice.
233 If gs0 and gs1 are complex, the cost will be high, so avoid
234 reevaluation if above an arbitrary threshold. */
235 rtx_insn *prep_seq_2, *gen_seq_2;
236 if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
237 tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
238 logical_op1_rhs1, logical_op1_rhs2);
239 if (!tmp && !tmp2)
240 return NULL_RTX;
241 if (tmp2 != NULL)
242 {
243 ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
244 &gen_seq_2);
245 cost2 = seq_cost (prep_seq_2, speed_p);
246 cost2 += seq_cost (gen_seq_2, speed_p);
247 }
248 if (cost2 < cost1)
249 {
250 *prep_seq = prep_seq_2;
251 *gen_seq = gen_seq_2;
252 return ret2;
253 }
254 *prep_seq = prep_seq_1;
255 *gen_seq = gen_seq_1;
256 return ret;
257 }
258 else
259 {
260 tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
261 if (!tmp)
262 return NULL_RTX;
263 return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
264 }
265 }
266 else
267 {
268 gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
269 || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
270 gcc_assert (ccmp_tree_comparison_p (op1, bb));
271 tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
272 if (!tmp)
273 return NULL_RTX;
274 return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
275 }
276
277 return NULL_RTX;
278 }
279
280 /* Main entry to expand conditional compare statement G.
281 Return NULL_RTX if G is not a legal candidate or expand fail.
282 Otherwise return the target. */
283 rtx
expand_ccmp_expr(gimple * g,machine_mode mode)284 expand_ccmp_expr (gimple *g, machine_mode mode)
285 {
286 rtx_insn *last;
287 rtx tmp;
288
289 if (!ccmp_candidate_p (g))
290 return NULL_RTX;
291
292 last = get_last_insn ();
293
294 rtx_insn *prep_seq = NULL, *gen_seq = NULL;
295 tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
296
297 if (tmp)
298 {
299 insn_code icode;
300 machine_mode cc_mode = CCmode;
301 rtx_code cmp_code = GET_CODE (tmp);
302
303 #ifdef SELECT_CC_MODE
304 cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
305 #endif
306 icode = optab_handler (cstore_optab, cc_mode);
307 if (icode != CODE_FOR_nothing)
308 {
309 rtx target = gen_reg_rtx (mode);
310
311 emit_insn (prep_seq);
312 emit_insn (gen_seq);
313
314 tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
315 0, XEXP (tmp, 0), const0_rtx, 1, mode);
316 if (tmp)
317 return tmp;
318 }
319 }
320 /* Clean up. */
321 delete_insns_since (last);
322 return NULL_RTX;
323 }
324