1/* Conditional compare related functions
2 Copyright (C) 2014-2024 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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. */
43static bool
44ccmp_tree_comparison_p (tree t, basic_block bb)
45{
46 gimple *g = get_gimple_for_ssa_name (exp: 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 (gs: g))
57 return false;
58 if (bb != gimple_bb (g))
59 return false;
60 tcode = gimple_assign_rhs_code (gs: 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; OUTER is true if
94 G is the outer most AND/IOR. */
95static bool
96ccmp_candidate_p (gimple *g, bool outer = false)
97{
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 tcode = gimple_assign_rhs_code (gs: g);
107 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
108 return false;
109
110 lhs = gimple_assign_lhs (gs: g);
111 op0 = gimple_assign_rhs1 (gs: g);
112 op1 = gimple_assign_rhs2 (gs: g);
113 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME))
114 return false;
115 if (!outer && !has_single_use (var: lhs))
116 return false;
117
118 bb = gimple_bb (g);
119 gs0 = get_gimple_for_ssa_name (exp: op0); /* gs0 may be NULL */
120 gs1 = get_gimple_for_ssa_name (exp: op1); /* gs1 may be NULL */
121
122 if (ccmp_tree_comparison_p (t: op0, bb) && ccmp_tree_comparison_p (t: op1, bb))
123 return true;
124 if (ccmp_tree_comparison_p (t: op0, bb) && ccmp_candidate_p (g: gs1))
125 return true;
126 if (ccmp_tree_comparison_p (t: op1, bb) && ccmp_candidate_p (g: 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. */
135void
136get_compare_parts (tree t, int *up, rtx_code *rcode,
137 tree *rhs1, tree *rhs2)
138{
139 tree_code code;
140 gimple *g = get_gimple_for_ssa_name (exp: t);
141 if (g)
142 {
143 *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
144 code = gimple_assign_rhs_code (gs: g);
145 *rcode = get_rtx_code (tcode: code, unsignedp: *up);
146 *rhs1 = gimple_assign_rhs1 (gs: g);
147 *rhs2 = gimple_assign_rhs2 (gs: g);
148 }
149 else
150 {
151 /* If g is not a comparison operator create a compare to zero. */
152 *up = 1;
153 *rcode = NE;
154 *rhs1 = t;
155 *rhs2 = build_zero_cst (TREE_TYPE (t));
156 }
157}
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. */
165static rtx
166expand_ccmp_next (tree op, tree_code code, rtx prev,
167 rtx_insn **prep_seq, rtx_insn **gen_seq)
168{
169 rtx_code rcode;
170 int unsignedp;
171 tree rhs1, rhs2;
172
173 get_compare_parts(t: op, up: &unsignedp, rcode: &rcode, rhs1: &rhs1, rhs2: &rhs2);
174 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
175 rhs1, rhs2, get_rtx_code (tcode: code, unsignedp: 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. */
189static rtx
190expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
191{
192 tree_code code = gimple_assign_rhs_code (gs: g);
193 basic_block bb = gimple_bb (g);
194
195 tree op0 = gimple_assign_rhs1 (gs: g);
196 tree op1 = gimple_assign_rhs2 (gs: g);
197 gimple *gs0 = get_gimple_for_ssa_name (exp: op0);
198 gimple *gs1 = get_gimple_for_ssa_name (exp: op1);
199 rtx tmp;
200
201 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
202
203 if (ccmp_tree_comparison_p (t: op0, bb))
204 {
205 if (ccmp_tree_comparison_p (t: op1, bb))
206 {
207 int unsignedp0, unsignedp1;
208 rtx_code rcode0, rcode1;
209 tree logical_op0_rhs1, logical_op0_rhs2;
210 tree logical_op1_rhs1, logical_op1_rhs2;
211 int speed_p = optimize_insn_for_speed_p ();
212
213 rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX;
214 unsigned cost1 = MAX_COST;
215 unsigned cost2 = MAX_COST;
216
217 get_compare_parts (t: op0, up: &unsignedp0, rcode: &rcode0,
218 rhs1: &logical_op0_rhs1, rhs2: &logical_op0_rhs2);
219
220 get_compare_parts (t: op1, up: &unsignedp1, rcode: &rcode1,
221 rhs1: &logical_op1_rhs1, rhs2: &logical_op1_rhs2);
222
223 rtx_insn *prep_seq_1, *gen_seq_1;
224 tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
225 logical_op0_rhs1, logical_op0_rhs2);
226 if (tmp != NULL)
227 {
228 ret = expand_ccmp_next (op: op1, code, prev: tmp, prep_seq: &prep_seq_1, gen_seq: &gen_seq_1);
229 cost1 = seq_cost (prep_seq_1, speed_p);
230 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 rtx_insn *prep_seq_2, *gen_seq_2;
238 if (tmp == NULL || cost1 < COSTS_N_INSNS (25))
239 tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
240 logical_op1_rhs1, logical_op1_rhs2);
241 if (!tmp && !tmp2)
242 return NULL_RTX;
243 if (tmp2 != NULL)
244 {
245 ret2 = expand_ccmp_next (op: op0, code, prev: tmp2, prep_seq: &prep_seq_2,
246 gen_seq: &gen_seq_2);
247 cost2 = seq_cost (prep_seq_2, speed_p);
248 cost2 += seq_cost (gen_seq_2, speed_p);
249 }
250 if (cost2 < cost1)
251 {
252 *prep_seq = prep_seq_2;
253 *gen_seq = gen_seq_2;
254 return ret2;
255 }
256 *prep_seq = prep_seq_1;
257 *gen_seq = gen_seq_1;
258 return ret;
259 }
260 else
261 {
262 tmp = expand_ccmp_expr_1 (g: gs1, prep_seq, gen_seq);
263 if (!tmp)
264 return NULL_RTX;
265 return expand_ccmp_next (op: op0, code, prev: tmp, prep_seq, gen_seq);
266 }
267 }
268 else
269 {
270 gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
271 || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
272 gcc_assert (ccmp_tree_comparison_p (op1, bb));
273 tmp = expand_ccmp_expr_1 (g: gs0, prep_seq, gen_seq);
274 if (!tmp)
275 return NULL_RTX;
276 return expand_ccmp_next (op: op1, code, prev: 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. */
283rtx
284expand_ccmp_expr (gimple *g, machine_mode mode)
285{
286 rtx_insn *last;
287 rtx tmp;
288
289 if (!ccmp_candidate_p (g, outer: true))
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: &prep_seq, gen_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 (op: cstore_optab, mode: 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, code: cmp_code, mode: cc_mode, compare_mode: cc_mode,
315 unsignedp: 0, XEXP (tmp, 0), const0_rtx, normalizep: 1, target_mode: mode);
316 if (tmp)
317 return tmp;
318 }
319 }
320 /* Clean up. */
321 delete_insns_since (last);
322 return NULL_RTX;
323}
324

source code of gcc/ccmp.cc