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