]>
Commit | Line | Data |
---|---|---|
f06cd23d | 1 | /* Conditional compare related functions |
a945c346 | 2 | Copyright (C) 2014-2024 Free Software Foundation, Inc. |
f06cd23d ZC |
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" | |
c7131fb2 | 23 | #include "backend.h" |
957060b5 AM |
24 | #include "target.h" |
25 | #include "rtl.h" | |
c7131fb2 AM |
26 | #include "tree.h" |
27 | #include "gimple.h" | |
4d0cdd0c | 28 | #include "memmodel.h" |
f06cd23d | 29 | #include "tm_p.h" |
957060b5 AM |
30 | #include "ssa.h" |
31 | #include "expmed.h" | |
32 | #include "optabs.h" | |
957060b5 | 33 | #include "emit-rtl.h" |
f06cd23d | 34 | #include "stor-layout.h" |
f06cd23d ZC |
35 | #include "tree-ssa-live.h" |
36 | #include "tree-outof-ssa.h" | |
37 | #include "cfgexpand.h" | |
f06cd23d | 38 | #include "ccmp.h" |
078fe40a | 39 | #include "predict.h" |
f06cd23d | 40 | |
f580a969 SE |
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 | 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 | ||
f06cd23d ZC |
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 | ||
c8012fbc WD |
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 | ||
4005b96a RH |
81 | * We use cstorecc4 pattern to convert the CCmode intermediate to |
82 | the integer mode result that expand_normal is expecting. | |
5f3bc026 ZC |
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. */ | |
f06cd23d | 92 | |
06ee648e AP |
93 | /* Check whether G is a potential conditional compare candidate; OUTER is true if |
94 | G is the outer most AND/IOR. */ | |
f06cd23d | 95 | static bool |
06ee648e | 96 | ccmp_candidate_p (gimple *g, bool outer = false) |
f06cd23d | 97 | { |
f06cd23d | 98 | tree lhs, op0, op1; |
355fe088 | 99 | gimple *gs0, *gs1; |
f580a969 SE |
100 | tree_code tcode; |
101 | basic_block bb; | |
102 | ||
103 | if (!g) | |
104 | return false; | |
f06cd23d | 105 | |
d6a73cc3 | 106 | tcode = gimple_assign_rhs_code (g); |
f06cd23d ZC |
107 | if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR) |
108 | return false; | |
109 | ||
110 | lhs = gimple_assign_lhs (g); | |
d6a73cc3 RB |
111 | op0 = gimple_assign_rhs1 (g); |
112 | op1 = gimple_assign_rhs2 (g); | |
06ee648e AP |
113 | if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)) |
114 | return false; | |
115 | if (!outer && !has_single_use (lhs)) | |
f06cd23d ZC |
116 | return false; |
117 | ||
d6a73cc3 | 118 | bb = gimple_bb (g); |
f580a969 SE |
119 | gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */ |
120 | gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */ | |
f06cd23d | 121 | |
f580a969 | 122 | if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb)) |
f06cd23d | 123 | return true; |
f580a969 | 124 | if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1)) |
f06cd23d | 125 | return true; |
f580a969 | 126 | if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0)) |
f06cd23d ZC |
127 | return true; |
128 | /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since | |
f580a969 SE |
129 | there is no way to set and maintain the CC flag on both sides of |
130 | the logical operator at the same time. */ | |
f06cd23d ZC |
131 | return false; |
132 | } | |
133 | ||
f580a969 SE |
134 | /* Extract the comparison we want to do from the tree. */ |
135 | void | |
136 | get_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 (t); | |
141 | if (g) | |
142 | { | |
143 | *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g))); | |
144 | code = gimple_assign_rhs_code (g); | |
145 | *rcode = get_rtx_code (code, *up); | |
146 | *rhs1 = gimple_assign_rhs1 (g); | |
147 | *rhs2 = gimple_assign_rhs2 (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 | ||
c8012fbc WD |
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. | |
5f3bc026 | 163 | PREP_SEQ returns all insns to prepare opearands for compare. |
c8012fbc | 164 | GEN_SEQ returns all compare insns. */ |
5f3bc026 | 165 | static rtx |
f580a969 | 166 | expand_ccmp_next (tree op, tree_code code, rtx prev, |
cb4347e8 | 167 | rtx_insn **prep_seq, rtx_insn **gen_seq) |
5f3bc026 | 168 | { |
078fe40a | 169 | rtx_code rcode; |
f580a969 SE |
170 | int unsignedp; |
171 | tree rhs1, rhs2; | |
5f3bc026 | 172 | |
f580a969 | 173 | get_compare_parts(op, &unsignedp, &rcode, &rhs1, &rhs2); |
5f3bc026 | 174 | return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode, |
f580a969 | 175 | rhs1, rhs2, get_rtx_code (code, 0)); |
5f3bc026 ZC |
176 | } |
177 | ||
f06cd23d ZC |
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. | |
5f3bc026 ZC |
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. */ | |
f06cd23d | 189 | static rtx |
cb4347e8 | 190 | expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq) |
f06cd23d | 191 | { |
8666d8bd | 192 | tree_code code = gimple_assign_rhs_code (g); |
f580a969 SE |
193 | basic_block bb = gimple_bb (g); |
194 | ||
8666d8bd RB |
195 | tree op0 = gimple_assign_rhs1 (g); |
196 | tree op1 = gimple_assign_rhs2 (g); | |
f580a969 SE |
197 | gimple *gs0 = get_gimple_for_ssa_name (op0); |
198 | gimple *gs1 = get_gimple_for_ssa_name (op1); | |
f06cd23d | 199 | rtx tmp; |
f06cd23d ZC |
200 | |
201 | gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); | |
f06cd23d | 202 | |
f580a969 | 203 | if (ccmp_tree_comparison_p (op0, bb)) |
f06cd23d | 204 | { |
f580a969 | 205 | if (ccmp_tree_comparison_p (op1, bb)) |
f06cd23d | 206 | { |
078fe40a WD |
207 | int unsignedp0, unsignedp1; |
208 | rtx_code rcode0, rcode1; | |
f580a969 SE |
209 | tree logical_op0_rhs1, logical_op0_rhs2; |
210 | tree logical_op1_rhs1, logical_op1_rhs2; | |
078fe40a | 211 | int speed_p = optimize_insn_for_speed_p (); |
f580a969 | 212 | |
e0b059b1 | 213 | rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX; |
078fe40a WD |
214 | unsigned cost1 = MAX_COST; |
215 | unsigned cost2 = MAX_COST; | |
f06cd23d | 216 | |
f580a969 SE |
217 | get_compare_parts (op0, &unsignedp0, &rcode0, |
218 | &logical_op0_rhs1, &logical_op0_rhs2); | |
219 | ||
220 | get_compare_parts (op1, &unsignedp1, &rcode1, | |
221 | &logical_op1_rhs1, &logical_op1_rhs2); | |
5f3bc026 | 222 | |
cb4347e8 | 223 | rtx_insn *prep_seq_1, *gen_seq_1; |
078fe40a | 224 | tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0, |
f580a969 | 225 | logical_op0_rhs1, logical_op0_rhs2); |
078fe40a WD |
226 | if (tmp != NULL) |
227 | { | |
f580a969 | 228 | ret = expand_ccmp_next (op1, code, tmp, &prep_seq_1, &gen_seq_1); |
cb4347e8 TS |
229 | cost1 = seq_cost (prep_seq_1, speed_p); |
230 | cost1 += seq_cost (gen_seq_1, speed_p); | |
078fe40a | 231 | } |
e0b059b1 WD |
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. */ | |
cb4347e8 | 237 | rtx_insn *prep_seq_2, *gen_seq_2; |
e0b059b1 WD |
238 | if (tmp == NULL || cost1 < COSTS_N_INSNS (25)) |
239 | tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1, | |
f580a969 | 240 | logical_op1_rhs1, logical_op1_rhs2); |
e0b059b1 WD |
241 | if (!tmp && !tmp2) |
242 | return NULL_RTX; | |
078fe40a WD |
243 | if (tmp2 != NULL) |
244 | { | |
f580a969 | 245 | ret2 = expand_ccmp_next (op0, code, tmp2, &prep_seq_2, |
078fe40a | 246 | &gen_seq_2); |
cb4347e8 TS |
247 | cost2 = seq_cost (prep_seq_2, speed_p); |
248 | cost2 += seq_cost (gen_seq_2, speed_p); | |
078fe40a | 249 | } |
078fe40a WD |
250 | if (cost2 < cost1) |
251 | { | |
252 | *prep_seq = prep_seq_2; | |
253 | *gen_seq = gen_seq_2; | |
254 | return ret2; | |
255 | } | |
078fe40a WD |
256 | *prep_seq = prep_seq_1; |
257 | *gen_seq = gen_seq_1; | |
258 | return ret; | |
f06cd23d ZC |
259 | } |
260 | else | |
261 | { | |
5f3bc026 ZC |
262 | tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq); |
263 | if (!tmp) | |
264 | return NULL_RTX; | |
f580a969 | 265 | return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq); |
f06cd23d ZC |
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); | |
f580a969 SE |
272 | gcc_assert (ccmp_tree_comparison_p (op1, bb)); |
273 | tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq); | |
274 | if (!tmp) | |
275 | return NULL_RTX; | |
276 | return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq); | |
f06cd23d | 277 | } |
f06cd23d ZC |
278 | } |
279 | ||
c8012fbc | 280 | /* Main entry to expand conditional compare statement G. |
f06cd23d ZC |
281 | Return NULL_RTX if G is not a legal candidate or expand fail. |
282 | Otherwise return the target. */ | |
283 | rtx | |
f580a969 | 284 | expand_ccmp_expr (gimple *g, machine_mode mode) |
f06cd23d ZC |
285 | { |
286 | rtx_insn *last; | |
287 | rtx tmp; | |
288 | ||
06ee648e | 289 | if (!ccmp_candidate_p (g, true)) |
f06cd23d ZC |
290 | return NULL_RTX; |
291 | ||
292 | last = get_last_insn (); | |
cb4347e8 TS |
293 | |
294 | rtx_insn *prep_seq = NULL, *gen_seq = NULL; | |
5f3bc026 | 295 | tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq); |
f06cd23d ZC |
296 | |
297 | if (tmp) | |
298 | { | |
078fe40a WD |
299 | insn_code icode; |
300 | machine_mode cc_mode = CCmode; | |
c8012fbc | 301 | rtx_code cmp_code = GET_CODE (tmp); |
5f3bc026 | 302 | |
f06cd23d | 303 | #ifdef SELECT_CC_MODE |
c8012fbc | 304 | cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx); |
f06cd23d | 305 | #endif |
f06cd23d ZC |
306 | icode = optab_handler (cstore_optab, cc_mode); |
307 | if (icode != CODE_FOR_nothing) | |
308 | { | |
f06cd23d | 309 | rtx target = gen_reg_rtx (mode); |
5f3bc026 ZC |
310 | |
311 | emit_insn (prep_seq); | |
312 | emit_insn (gen_seq); | |
313 | ||
c8012fbc WD |
314 | tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode, |
315 | 0, XEXP (tmp, 0), const0_rtx, 1, mode); | |
f06cd23d ZC |
316 | if (tmp) |
317 | return tmp; | |
318 | } | |
319 | } | |
320 | /* Clean up. */ | |
321 | delete_insns_since (last); | |
322 | return NULL_RTX; | |
323 | } |