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