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 a SSA name
42 : set by a comparison operator in the same basic block. */
43 : static bool
44 131530 : ccmp_tree_comparison_p (tree t, basic_block bb)
45 : {
46 131530 : gimple *g = get_gimple_for_ssa_name (t);
47 131530 : tree_code tcode;
48 :
49 : /* If we have a boolean variable allow it and generate a compare
50 : to zero reg when expanding. */
51 131530 : if (!g)
52 172 : 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 131358 : if (!is_gimple_assign (g))
57 : return false;
58 131358 : if (bb != gimple_bb (g))
59 : return false;
60 131358 : tcode = gimple_assign_rhs_code (g);
61 131358 : 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; OUTER is true if
94 : G is the outer most AND/IOR. */
95 : static bool
96 164955 : ccmp_candidate_p (gimple *g, bool outer = false)
97 : {
98 164955 : tree lhs, op0, op1;
99 164955 : gimple *gs0, *gs1;
100 164955 : tree_code tcode;
101 164955 : basic_block bb;
102 :
103 164955 : if (!g || !is_gimple_assign (g))
104 : return false;
105 :
106 164955 : tcode = gimple_assign_rhs_code (g);
107 164955 : if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
108 : return false;
109 :
110 32993 : lhs = gimple_assign_lhs (g);
111 32993 : op0 = gimple_assign_rhs1 (g);
112 32993 : op1 = gimple_assign_rhs2 (g);
113 32993 : if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME))
114 : return false;
115 32912 : if (!outer && !has_single_use (lhs))
116 : return false;
117 :
118 32912 : bb = gimple_bb (g);
119 32912 : gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
120 32912 : gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
121 :
122 32912 : if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
123 : return true;
124 124 : if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
125 : return true;
126 124 : if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
127 : return true;
128 : /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
129 : there is no way to set and maintain the CC flag on both sides of
130 : the logical operator at the same time. */
131 : return false;
132 : }
133 :
134 : /* Extract the comparison we want to do from the tree. */
135 : void
136 98385 : get_compare_parts (tree t, rtx_code *rcode,
137 : tree *rhs1, tree *rhs2)
138 : {
139 98385 : tree_code code;
140 98385 : gimple *g = get_gimple_for_ssa_name (t);
141 98385 : if (g && is_gimple_assign (g))
142 : {
143 98385 : int up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
144 98385 : code = gimple_assign_rhs_code (g);
145 98385 : *rcode = get_rtx_code (code, up);
146 98385 : *rhs1 = gimple_assign_rhs1 (g);
147 98385 : *rhs2 = gimple_assign_rhs2 (g);
148 : }
149 : else
150 : {
151 : /* If g is not a comparison operator create a compare to zero. */
152 0 : *rcode = NE;
153 0 : *rhs1 = t;
154 0 : *rhs2 = build_zero_cst (TREE_TYPE (t));
155 : }
156 98385 : }
157 :
158 : /* PREV is a comparison with the CC register which represents the
159 : result of the previous CMP or CCMP. The function expands the
160 : next compare based on G which is ANDed/ORed with the previous
161 : compare depending on CODE.
162 : PREP_SEQ returns all insns to prepare opearands for compare.
163 : GEN_SEQ returns all compare insns. */
164 : static rtx
165 32809 : expand_ccmp_next (tree op, tree_code code, rtx prev,
166 : rtx_insn **prep_seq, rtx_insn **gen_seq)
167 : {
168 32809 : rtx_code rcode;
169 32809 : tree rhs1, rhs2;
170 :
171 32809 : get_compare_parts (op, &rcode, &rhs1, &rhs2);
172 32809 : return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
173 32809 : 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
188 32791 : expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
189 : {
190 32791 : tree_code code = gimple_assign_rhs_code (g);
191 32791 : basic_block bb = gimple_bb (g);
192 :
193 32791 : tree op0 = gimple_assign_rhs1 (g);
194 32791 : tree op1 = gimple_assign_rhs2 (g);
195 32791 : gimple *gs0 = get_gimple_for_ssa_name (op0);
196 32791 : gimple *gs1 = get_gimple_for_ssa_name (op1);
197 32791 : rtx tmp;
198 :
199 32791 : gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
200 :
201 32791 : if (ccmp_tree_comparison_p (op0, bb))
202 : {
203 32788 : if (ccmp_tree_comparison_p (op1, bb))
204 : {
205 32788 : rtx_code rcode0, rcode1;
206 32788 : tree logical_op0_rhs1, logical_op0_rhs2;
207 32788 : tree logical_op1_rhs1, logical_op1_rhs2;
208 32788 : int speed_p = optimize_insn_for_speed_p ();
209 :
210 32788 : rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
211 32788 : unsigned cost1 = MAX_COST;
212 32788 : unsigned cost2 = MAX_COST;
213 :
214 32788 : get_compare_parts (op0, &rcode0,
215 : &logical_op0_rhs1, &logical_op0_rhs2);
216 :
217 32788 : get_compare_parts (op1, &rcode1,
218 : &logical_op1_rhs1, &logical_op1_rhs2);
219 :
220 32788 : rtx_insn *prep_seq_1, *gen_seq_1;
221 32788 : tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
222 : logical_op0_rhs1, logical_op0_rhs2);
223 32788 : if (tmp != NULL)
224 : {
225 22 : ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1);
226 22 : cost1 = seq_cost (prep_seq_1, speed_p);
227 22 : cost1 += seq_cost (gen_seq_1, speed_p);
228 : }
229 :
230 : /* FIXME: Temporary workaround for PR69619.
231 : Avoid exponential compile time due to expanding gs0 and gs1 twice.
232 : If gs0 and gs1 are complex, the cost will be high, so avoid
233 : reevaluation if above an arbitrary threshold. */
234 32788 : rtx_insn *prep_seq_2, *gen_seq_2;
235 32788 : if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
236 32788 : tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
237 : logical_op1_rhs1, logical_op1_rhs2);
238 32788 : if (!tmp && !tmp2)
239 : return NULL_RTX;
240 32788 : if (tmp2 != NULL)
241 : {
242 32784 : ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2,
243 : &gen_seq_2);
244 32784 : cost2 = seq_cost (prep_seq_2, speed_p);
245 32784 : cost2 += seq_cost (gen_seq_2, speed_p);
246 : }
247 :
248 : /* It's possible that one expansion succeeds and the other
249 : fails.
250 : For example, x86 has int ccmp but not fp ccmp, and so a
251 : combined fp and int comparison must be ordered such that
252 : the fp comparison happens first. The costs are not
253 : meaningful for failed expansions. */
254 :
255 32784 : if (ret2 && (!ret || cost2 < cost1))
256 : {
257 3 : *prep_seq = prep_seq_2;
258 3 : *gen_seq = gen_seq_2;
259 3 : return ret2;
260 : }
261 32785 : *prep_seq = prep_seq_1;
262 32785 : *gen_seq = gen_seq_1;
263 32785 : return ret;
264 : }
265 : else
266 : {
267 0 : tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
268 0 : if (!tmp)
269 : return NULL_RTX;
270 0 : return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
271 : }
272 : }
273 : else
274 : {
275 3 : gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
276 : || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
277 3 : gcc_assert (ccmp_tree_comparison_p (op1, bb));
278 3 : tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
279 3 : if (!tmp)
280 : return NULL_RTX;
281 3 : return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
282 : }
283 : }
284 :
285 : /* Main entry to expand conditional compare statement G.
286 : Return NULL_RTX if G is not a legal candidate or expand fail.
287 : Otherwise return the target. */
288 : rtx
289 164952 : expand_ccmp_expr (gimple *g, machine_mode mode)
290 : {
291 164952 : rtx_insn *last;
292 164952 : rtx tmp;
293 :
294 164952 : if (!ccmp_candidate_p (g, true))
295 : return NULL_RTX;
296 :
297 32788 : last = get_last_insn ();
298 :
299 32788 : rtx_insn *prep_seq = NULL, *gen_seq = NULL;
300 32788 : tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
301 :
302 32788 : if (tmp)
303 : {
304 18 : insn_code icode;
305 18 : machine_mode cc_mode = CCmode;
306 18 : rtx_code cmp_code = GET_CODE (tmp);
307 :
308 : #ifdef SELECT_CC_MODE
309 18 : cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
310 : #endif
311 18 : icode = optab_handler (cstore_optab, cc_mode);
312 18 : if (icode != CODE_FOR_nothing)
313 : {
314 18 : rtx target = gen_reg_rtx (mode);
315 :
316 18 : emit_insn (prep_seq);
317 18 : emit_insn (gen_seq);
318 :
319 18 : tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
320 : 0, XEXP (tmp, 0), const0_rtx, 1, mode);
321 18 : if (tmp)
322 : return tmp;
323 : }
324 : }
325 : /* Clean up. */
326 32770 : delete_insns_since (last);
327 32770 : return NULL_RTX;
328 : }
|
