Line data Source code
1 : /* Conditional compare related functions
2 : Copyright (C) 2014-2026 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 an SSA name set by a
42 : comparison operator in BB. Set *HAS_COMPARISON if T is the latter. */
43 : static bool
44 131412 : ccmp_tree_comparison_p (tree t, basic_block bb,
45 : bool *has_comparison = nullptr)
46 : {
47 131412 : gimple *g = get_gimple_for_ssa_name (t);
48 131412 : tree_code tcode;
49 :
50 131412 : if (has_comparison)
51 65824 : *has_comparison = false;
52 :
53 : /* If we have a boolean variable allow it and generate a compare
54 : to zero reg when expanding. */
55 131412 : if (!g)
56 128 : return (TREE_CODE (TREE_TYPE (t)) == BOOLEAN_TYPE);
57 :
58 : /* Check to see if SSA name is set by a comparison operator in
59 : the same basic block. */
60 131284 : if (!is_gimple_assign (g))
61 : return false;
62 131284 : if (bb != gimple_bb (g))
63 : return false;
64 131284 : tcode = gimple_assign_rhs_code (g);
65 131284 : if (TREE_CODE_CLASS (tcode) != tcc_comparison)
66 : return false;
67 :
68 131170 : if (has_comparison)
69 65585 : *has_comparison = true;
70 : return true;
71 : }
72 :
73 : /* The following functions expand conditional compare (CCMP) instructions.
74 : Here is a short description about the over all algorithm:
75 : * ccmp_candidate_p is used to identify the CCMP candidate
76 :
77 : * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
78 : to expand CCMP.
79 :
80 : * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
81 : It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
82 : CCMP instructions.
83 : - gen_ccmp_first expands the first compare in CCMP.
84 : - gen_ccmp_next expands the following compares.
85 :
86 : Both hooks return a comparison with the CC register that is equivalent
87 : to the value of the gimple comparison. This is used by the next CCMP
88 : and in the final conditional store.
89 :
90 : * We use cstorecc4 pattern to convert the CCmode intermediate to
91 : the integer mode result that expand_normal is expecting.
92 :
93 : Since the operands of the later compares might clobber CC reg, we do not
94 : emit the insns during expand. We keep the insn sequences in two seq
95 :
96 : * prep_seq, which includes all the insns to prepare the operands.
97 : * gen_seq, which includes all the compare and conditional compares.
98 :
99 : If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
100 : insns in gen_seq. */
101 :
102 : /* Return true if G is a potential conditional compare candidate. Set
103 : *HAS_COMPARISON if it contains a comparison that will be folded into the
104 : flags. OUTER is true if G is the outermost AND/IOR. */
105 : static bool
106 164997 : ccmp_candidate_p (gimple *g, bool *has_comparison, bool outer = false)
107 : {
108 164997 : tree lhs, op0, op1;
109 164997 : gimple *gs0, *gs1;
110 164997 : tree_code tcode;
111 164997 : basic_block bb;
112 :
113 164997 : *has_comparison = false;
114 :
115 164997 : if (!g || !is_gimple_assign (g))
116 : return false;
117 :
118 164997 : tcode = gimple_assign_rhs_code (g);
119 164997 : if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
120 : return false;
121 :
122 32993 : lhs = gimple_assign_lhs (g);
123 32993 : op0 = gimple_assign_rhs1 (g);
124 32993 : op1 = gimple_assign_rhs2 (g);
125 32993 : if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME))
126 : return false;
127 32912 : if (!outer && !has_single_use (lhs))
128 : return false;
129 :
130 32912 : if (SA.ccmp_no_comparison
131 32912 : && bitmap_bit_p (SA.ccmp_no_comparison, SSA_NAME_VERSION (lhs)))
132 : {
133 0 : *has_comparison = false;
134 0 : return true;
135 : }
136 :
137 32912 : bb = gimple_bb (g);
138 32912 : gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
139 32912 : gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
140 :
141 32912 : bool comparison0, comparison1;
142 32912 : bool leaf0 = ccmp_tree_comparison_p (op0, bb, &comparison0);
143 32912 : bool leaf1 = ccmp_tree_comparison_p (op1, bb, &comparison1);
144 :
145 32912 : if (leaf0 && leaf1)
146 32791 : *has_comparison = comparison0 || comparison1;
147 121 : else if (leaf0 || leaf1)
148 : {
149 3 : bool inner_has_comparison;
150 6 : if (!ccmp_candidate_p (leaf0 ? gs1 : gs0, &inner_has_comparison))
151 0 : return false;
152 3 : *has_comparison = inner_has_comparison
153 3 : || (leaf0 ? comparison0 : comparison1);
154 : }
155 : else
156 : return false;
157 :
158 : /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
159 : there is no way to set and maintain the CC flag on both sides of
160 : the logical operator at the same time. */
161 :
162 32794 : if (!*has_comparison)
163 : {
164 0 : if (!SA.ccmp_no_comparison)
165 0 : SA.ccmp_no_comparison = BITMAP_ALLOC (NULL);
166 0 : bitmap_set_bit (SA.ccmp_no_comparison, SSA_NAME_VERSION (lhs));
167 : }
168 :
169 : return true;
170 0 : }
171 :
172 : /* Extract the comparison we want to do from the tree. */
173 : void
174 98396 : get_compare_parts (tree t, rtx_code *rcode,
175 : tree *rhs1, tree *rhs2)
176 : {
177 98396 : tree_code code;
178 98396 : gimple *g = get_gimple_for_ssa_name (t);
179 98396 : if (g && is_gimple_assign (g))
180 : {
181 98396 : int up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
182 98396 : code = gimple_assign_rhs_code (g);
183 98396 : *rcode = get_rtx_code (code, up);
184 98396 : *rhs1 = gimple_assign_rhs1 (g);
185 98396 : *rhs2 = gimple_assign_rhs2 (g);
186 : }
187 : else
188 : {
189 : /* If g is not a comparison operator create a compare to zero. */
190 0 : *rcode = NE;
191 0 : *rhs1 = t;
192 0 : *rhs2 = build_zero_cst (TREE_TYPE (t));
193 : }
194 98396 : }
195 :
196 : /* PREV is a comparison with the CC register which represents the
197 : result of the previous CMP or CCMP. The function expands the
198 : next compare based on G which is ANDed/ORed with the previous
199 : compare depending on CODE.
200 : PREP_SEQ returns all insns to prepare operands for compare.
201 : GEN_SEQ returns all compare insns. */
202 : static rtx
203 32814 : expand_ccmp_next (tree op, tree_code code, rtx prev,
204 : rtx_insn **prep_seq, rtx_insn **gen_seq)
205 : {
206 32814 : rtx_code rcode;
207 32814 : tree rhs1, rhs2;
208 :
209 32814 : get_compare_parts (op, &rcode, &rhs1, &rhs2);
210 32814 : return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
211 32814 : rhs1, rhs2, get_rtx_code (code, 0));
212 : }
213 :
214 : /* Expand conditional compare gimple G. A typical CCMP sequence is like:
215 :
216 : CC0 = CMP (a, b);
217 : CC1 = CCMP (NE (CC0, 0), CMP (e, f));
218 : ...
219 : CCn = CCMP (NE (CCn-1, 0), CMP (...));
220 :
221 : hook gen_ccmp_first is used to expand the first compare.
222 : hook gen_ccmp_next is used to expand the following CCMP.
223 : PREP_SEQ returns all insns to prepare operand.
224 : GEN_SEQ returns all compare insns. */
225 : static rtx
226 32794 : expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
227 : {
228 32794 : tree_code code = gimple_assign_rhs_code (g);
229 32794 : basic_block bb = gimple_bb (g);
230 :
231 32794 : tree op0 = gimple_assign_rhs1 (g);
232 32794 : tree op1 = gimple_assign_rhs2 (g);
233 32794 : gimple *gs0 = get_gimple_for_ssa_name (op0);
234 32794 : gimple *gs1 = get_gimple_for_ssa_name (op1);
235 32794 : rtx tmp;
236 :
237 32794 : gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
238 :
239 32794 : if (ccmp_tree_comparison_p (op0, bb))
240 : {
241 32791 : if (ccmp_tree_comparison_p (op1, bb))
242 : {
243 32791 : rtx_code rcode0, rcode1;
244 32791 : tree logical_op0_rhs1, logical_op0_rhs2;
245 32791 : tree logical_op1_rhs1, logical_op1_rhs2;
246 32791 : int speed_p = optimize_insn_for_speed_p ();
247 :
248 32791 : rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
249 32791 : unsigned cost1 = MAX_COST;
250 32791 : unsigned cost2 = MAX_COST;
251 :
252 32791 : get_compare_parts (op0, &rcode0,
253 : &logical_op0_rhs1, &logical_op0_rhs2);
254 :
255 32791 : get_compare_parts (op1, &rcode1,
256 : &logical_op1_rhs1, &logical_op1_rhs2);
257 :
258 32791 : rtx_insn *prep_seq_1, *gen_seq_1;
259 32791 : tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
260 : logical_op0_rhs1, logical_op0_rhs2);
261 32791 : if (tmp != NULL)
262 : {
263 25 : ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
264 25 : cost1 = seq_cost (prep_seq_1, speed_p);
265 25 : cost1 += seq_cost (gen_seq_1, speed_p);
266 : }
267 :
268 : /* FIXME: Temporary workaround for PR69619.
269 : Avoid exponential compile time due to expanding gs0 and gs1 twice.
270 : If gs0 and gs1 are complex, the cost will be high, so avoid
271 : reevaluation if above an arbitrary threshold. */
272 32791 : rtx_insn *prep_seq_2, *gen_seq_2;
273 32791 : if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
274 32791 : tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
275 : logical_op1_rhs1, logical_op1_rhs2);
276 32791 : if (!tmp && !tmp2)
277 : return NULL_RTX;
278 32791 : if (tmp2 != NULL)
279 : {
280 32786 : ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
281 : &gen_seq_2);
282 32786 : cost2 = seq_cost (prep_seq_2, speed_p);
283 32786 : cost2 += seq_cost (gen_seq_2, speed_p);
284 : }
285 :
286 : /* It's possible that one expansion succeeds and the other
287 : fails.
288 : For example, x86 has int ccmp but not fp ccmp, and so a
289 : combined fp and int comparison must be ordered such that
290 : the fp comparison happens first. The costs are not
291 : meaningful for failed expansions. */
292 :
293 32786 : if (ret2 && (!ret || cost2 < cost1))
294 : {
295 5 : *prep_seq = prep_seq_2;
296 5 : *gen_seq = gen_seq_2;
297 5 : return ret2;
298 : }
299 32786 : *prep_seq = prep_seq_1;
300 32786 : *gen_seq = gen_seq_1;
301 32786 : return ret;
302 : }
303 : else
304 : {
305 0 : tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
306 0 : if (!tmp)
307 : return NULL_RTX;
308 0 : return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
309 : }
310 : }
311 : else
312 : {
313 3 : gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
314 : || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
315 3 : gcc_assert (ccmp_tree_comparison_p (op1, bb));
316 3 : tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
317 3 : if (!tmp)
318 : return NULL_RTX;
319 3 : return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
320 : }
321 : }
322 :
323 : /* Main entry to expand conditional compare statement G.
324 : Return NULL_RTX if G is not a legal candidate or expand fail.
325 : Otherwise return the target. */
326 : rtx
327 164994 : expand_ccmp_expr (gimple *g, machine_mode mode)
328 : {
329 164994 : rtx_insn *last;
330 164994 : rtx tmp;
331 :
332 164994 : bool has_comparison;
333 164994 : if (!ccmp_candidate_p (g, &has_comparison, true) || !has_comparison)
334 : return NULL_RTX;
335 :
336 32791 : last = get_last_insn ();
337 :
338 32791 : rtx_insn *prep_seq = NULL, *gen_seq = NULL;
339 32791 : tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
340 :
341 32791 : if (tmp)
342 : {
343 20 : insn_code icode;
344 20 : machine_mode cc_mode = CCmode;
345 20 : rtx_code cmp_code = GET_CODE (tmp);
346 :
347 : #ifdef SELECT_CC_MODE
348 20 : cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
349 : #endif
350 20 : icode = optab_handler (cstore_optab, cc_mode);
351 20 : if (icode != CODE_FOR_nothing)
352 : {
353 20 : rtx target = gen_reg_rtx (mode);
354 :
355 20 : emit_insn (prep_seq);
356 20 : emit_insn (gen_seq);
357 :
358 20 : tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
359 : 0, XEXP (tmp, 0), const0_rtx, 1, mode);
360 20 : if (tmp)
361 : return tmp;
362 : }
363 : }
364 : /* Clean up. */
365 32771 : delete_insns_since (last);
366 32771 : return NULL_RTX;
367 : }
|
