111
|
1 /* Conditional compare related functions
|
145
|
2 Copyright (C) 2014-2020 Free Software Foundation, Inc.
|
111
|
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 (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
|
|
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
|
145
|
105 tcode = gimple_assign_rhs_code (g);
|
111
|
106 if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
|
|
107 return false;
|
|
108
|
|
109 lhs = gimple_assign_lhs (g);
|
145
|
110 op0 = gimple_assign_rhs1 (g);
|
|
111 op1 = gimple_assign_rhs2 (g);
|
111
|
112 if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
|
|
113 || !has_single_use (lhs))
|
|
114 return false;
|
|
115
|
145
|
116 bb = gimple_bb (g);
|
111
|
117 gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
|
|
118 gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
|
|
119
|
|
120 if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
|
|
121 return true;
|
|
122 if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
|
|
123 return true;
|
|
124 if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (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 (t);
|
|
139 if (g)
|
|
140 {
|
|
141 *up = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
|
|
142 code = gimple_assign_rhs_code (g);
|
|
143 *rcode = get_rtx_code (code, *up);
|
|
144 *rhs1 = gimple_assign_rhs1 (g);
|
|
145 *rhs2 = gimple_assign_rhs2 (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(op, &unsignedp, &rcode, &rhs1, &rhs2);
|
|
172 return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
|
|
173 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 expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
|
|
189 {
|
145
|
190 tree_code code = gimple_assign_rhs_code (g);
|
111
|
191 basic_block bb = gimple_bb (g);
|
|
192
|
145
|
193 tree op0 = gimple_assign_rhs1 (g);
|
|
194 tree op1 = gimple_assign_rhs2 (g);
|
111
|
195 gimple *gs0 = get_gimple_for_ssa_name (op0);
|
|
196 gimple *gs1 = get_gimple_for_ssa_name (op1);
|
|
197 rtx tmp;
|
|
198
|
|
199 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
|
|
200
|
|
201 if (ccmp_tree_comparison_p (op0, bb))
|
|
202 {
|
|
203 if (ccmp_tree_comparison_p (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 (op0, &unsignedp0, &rcode0,
|
|
216 &logical_op0_rhs1, &logical_op0_rhs2);
|
|
217
|
|
218 get_compare_parts (op1, &unsignedp1, &rcode1,
|
|
219 &logical_op1_rhs1, &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 (op1, code, tmp, &prep_seq_1, &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 (op0, code, tmp2, &prep_seq_2,
|
|
244 &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 (gs1, prep_seq, gen_seq);
|
|
261 if (!tmp)
|
|
262 return NULL_RTX;
|
|
263 return expand_ccmp_next (op0, code, 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 (gs0, prep_seq, gen_seq);
|
|
272 if (!tmp)
|
|
273 return NULL_RTX;
|
|
274 return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
|
|
275 }
|
|
276
|
|
277 return NULL_RTX;
|
|
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 expand_ccmp_expr (gimple *g, machine_mode mode)
|
|
285 {
|
|
286 rtx_insn *last;
|
|
287 rtx tmp;
|
|
288
|
|
289 if (!ccmp_candidate_p (g))
|
|
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, &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 (cstore_optab, 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, cmp_code, cc_mode, cc_mode,
|
|
315 0, XEXP (tmp, 0), const0_rtx, 1, mode);
|
|
316 if (tmp)
|
|
317 return tmp;
|
|
318 }
|
|
319 }
|
|
320 /* Clean up. */
|
|
321 delete_insns_since (last);
|
|
322 return NULL_RTX;
|
|
323 }
|