]>
Commit | Line | Data |
---|---|---|
f06cd23d | 1 | /* Conditional compare related functions |
818ab71a | 2 | Copyright (C) 2014-2016 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 ZC |
40 | |
41 | /* The following functions expand conditional compare (CCMP) instructions. | |
42 | Here is a short description about the over all algorithm: | |
43 | * ccmp_candidate_p is used to identify the CCMP candidate | |
44 | ||
45 | * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1 | |
46 | to expand CCMP. | |
47 | ||
48 | * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP. | |
49 | It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate | |
50 | CCMP instructions. | |
51 | - gen_ccmp_first expands the first compare in CCMP. | |
52 | - gen_ccmp_next expands the following compares. | |
53 | ||
c8012fbc WD |
54 | Both hooks return a comparison with the CC register that is equivalent |
55 | to the value of the gimple comparison. This is used by the next CCMP | |
56 | and in the final conditional store. | |
57 | ||
4005b96a RH |
58 | * We use cstorecc4 pattern to convert the CCmode intermediate to |
59 | the integer mode result that expand_normal is expecting. | |
5f3bc026 ZC |
60 | |
61 | Since the operands of the later compares might clobber CC reg, we do not | |
62 | emit the insns during expand. We keep the insn sequences in two seq | |
63 | ||
64 | * prep_seq, which includes all the insns to prepare the operands. | |
65 | * gen_seq, which includes all the compare and conditional compares. | |
66 | ||
67 | If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then | |
68 | insns in gen_seq. */ | |
f06cd23d ZC |
69 | |
70 | /* Check whether G is a potential conditional compare candidate. */ | |
71 | static bool | |
355fe088 | 72 | ccmp_candidate_p (gimple *g) |
f06cd23d ZC |
73 | { |
74 | tree rhs = gimple_assign_rhs_to_tree (g); | |
75 | tree lhs, op0, op1; | |
355fe088 | 76 | gimple *gs0, *gs1; |
078fe40a | 77 | tree_code tcode, tcode0, tcode1; |
f06cd23d ZC |
78 | tcode = TREE_CODE (rhs); |
79 | ||
80 | if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR) | |
81 | return false; | |
82 | ||
83 | lhs = gimple_assign_lhs (g); | |
84 | op0 = TREE_OPERAND (rhs, 0); | |
85 | op1 = TREE_OPERAND (rhs, 1); | |
86 | ||
87 | if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME) | |
88 | || !has_single_use (lhs)) | |
89 | return false; | |
90 | ||
91 | gs0 = get_gimple_for_ssa_name (op0); | |
92 | gs1 = get_gimple_for_ssa_name (op1); | |
93 | if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1) | |
94 | /* g, gs0 and gs1 must be in the same basic block, since current stage | |
95 | is out-of-ssa. We can not guarantee the correctness when forwording | |
96 | the gs0 and gs1 into g whithout DATAFLOW analysis. */ | |
97 | || gimple_bb (gs0) != gimple_bb (gs1) | |
98 | || gimple_bb (gs0) != gimple_bb (g)) | |
99 | return false; | |
100 | ||
f06cd23d ZC |
101 | tcode0 = gimple_assign_rhs_code (gs0); |
102 | tcode1 = gimple_assign_rhs_code (gs1); | |
103 | if (TREE_CODE_CLASS (tcode0) == tcc_comparison | |
104 | && TREE_CODE_CLASS (tcode1) == tcc_comparison) | |
105 | return true; | |
106 | if (TREE_CODE_CLASS (tcode0) == tcc_comparison | |
107 | && ccmp_candidate_p (gs1)) | |
108 | return true; | |
109 | else if (TREE_CODE_CLASS (tcode1) == tcc_comparison | |
110 | && ccmp_candidate_p (gs0)) | |
111 | return true; | |
112 | /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since | |
113 | there is no way to set the CC flag. */ | |
114 | return false; | |
115 | } | |
116 | ||
c8012fbc WD |
117 | /* PREV is a comparison with the CC register which represents the |
118 | result of the previous CMP or CCMP. The function expands the | |
119 | next compare based on G which is ANDed/ORed with the previous | |
120 | compare depending on CODE. | |
5f3bc026 | 121 | PREP_SEQ returns all insns to prepare opearands for compare. |
c8012fbc | 122 | GEN_SEQ returns all compare insns. */ |
5f3bc026 | 123 | static rtx |
078fe40a | 124 | expand_ccmp_next (gimple *g, tree_code code, rtx prev, |
5f3bc026 ZC |
125 | rtx *prep_seq, rtx *gen_seq) |
126 | { | |
078fe40a | 127 | rtx_code rcode; |
5f3bc026 ZC |
128 | int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g))); |
129 | ||
130 | gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); | |
131 | ||
132 | rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp); | |
133 | ||
134 | return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode, | |
135 | gimple_assign_rhs1 (g), | |
136 | gimple_assign_rhs2 (g), | |
137 | get_rtx_code (code, 0)); | |
138 | } | |
139 | ||
f06cd23d ZC |
140 | /* Expand conditional compare gimple G. A typical CCMP sequence is like: |
141 | ||
142 | CC0 = CMP (a, b); | |
143 | CC1 = CCMP (NE (CC0, 0), CMP (e, f)); | |
144 | ... | |
145 | CCn = CCMP (NE (CCn-1, 0), CMP (...)); | |
146 | ||
147 | hook gen_ccmp_first is used to expand the first compare. | |
5f3bc026 ZC |
148 | hook gen_ccmp_next is used to expand the following CCMP. |
149 | PREP_SEQ returns all insns to prepare opearand. | |
150 | GEN_SEQ returns all compare insns. */ | |
f06cd23d | 151 | static rtx |
355fe088 | 152 | expand_ccmp_expr_1 (gimple *g, rtx *prep_seq, rtx *gen_seq) |
f06cd23d | 153 | { |
078fe40a WD |
154 | rtx prep_seq_1, gen_seq_1; |
155 | rtx prep_seq_2, gen_seq_2; | |
f06cd23d | 156 | tree exp = gimple_assign_rhs_to_tree (g); |
078fe40a | 157 | tree_code code = TREE_CODE (exp); |
355fe088 TS |
158 | gimple *gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0)); |
159 | gimple *gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1)); | |
f06cd23d | 160 | rtx tmp; |
078fe40a WD |
161 | tree_code code0 = gimple_assign_rhs_code (gs0); |
162 | tree_code code1 = gimple_assign_rhs_code (gs1); | |
f06cd23d ZC |
163 | |
164 | gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); | |
165 | gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1)); | |
166 | ||
167 | if (TREE_CODE_CLASS (code0) == tcc_comparison) | |
168 | { | |
169 | if (TREE_CODE_CLASS (code1) == tcc_comparison) | |
170 | { | |
078fe40a WD |
171 | int unsignedp0, unsignedp1; |
172 | rtx_code rcode0, rcode1; | |
173 | int speed_p = optimize_insn_for_speed_p (); | |
e0b059b1 | 174 | rtx tmp2 = NULL_RTX, ret = NULL_RTX, ret2 = NULL_RTX; |
078fe40a WD |
175 | unsigned cost1 = MAX_COST; |
176 | unsigned cost2 = MAX_COST; | |
f06cd23d ZC |
177 | |
178 | unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0))); | |
078fe40a | 179 | unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1))); |
f06cd23d | 180 | rcode0 = get_rtx_code (code0, unsignedp0); |
078fe40a | 181 | rcode1 = get_rtx_code (code1, unsignedp1); |
5f3bc026 | 182 | |
078fe40a | 183 | tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0, |
5f3bc026 ZC |
184 | gimple_assign_rhs1 (gs0), |
185 | gimple_assign_rhs2 (gs0)); | |
078fe40a | 186 | |
078fe40a WD |
187 | if (tmp != NULL) |
188 | { | |
189 | ret = expand_ccmp_next (gs1, code, tmp, &prep_seq_1, &gen_seq_1); | |
190 | cost1 = seq_cost (safe_as_a <rtx_insn *> (prep_seq_1), speed_p); | |
191 | cost1 += seq_cost (safe_as_a <rtx_insn *> (gen_seq_1), speed_p); | |
192 | } | |
e0b059b1 WD |
193 | |
194 | /* FIXME: Temporary workaround for PR69619. | |
195 | Avoid exponential compile time due to expanding gs0 and gs1 twice. | |
196 | If gs0 and gs1 are complex, the cost will be high, so avoid | |
197 | reevaluation if above an arbitrary threshold. */ | |
198 | if (tmp == NULL || cost1 < COSTS_N_INSNS (25)) | |
199 | tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1, | |
200 | gimple_assign_rhs1 (gs1), | |
201 | gimple_assign_rhs2 (gs1)); | |
202 | ||
203 | if (!tmp && !tmp2) | |
204 | return NULL_RTX; | |
205 | ||
078fe40a WD |
206 | if (tmp2 != NULL) |
207 | { | |
208 | ret2 = expand_ccmp_next (gs0, code, tmp2, &prep_seq_2, | |
209 | &gen_seq_2); | |
210 | cost2 = seq_cost (safe_as_a <rtx_insn *> (prep_seq_2), speed_p); | |
211 | cost2 += seq_cost (safe_as_a <rtx_insn *> (gen_seq_2), speed_p); | |
212 | } | |
213 | ||
214 | if (cost2 < cost1) | |
215 | { | |
216 | *prep_seq = prep_seq_2; | |
217 | *gen_seq = gen_seq_2; | |
218 | return ret2; | |
219 | } | |
220 | ||
221 | *prep_seq = prep_seq_1; | |
222 | *gen_seq = gen_seq_1; | |
223 | return ret; | |
f06cd23d ZC |
224 | } |
225 | else | |
226 | { | |
5f3bc026 ZC |
227 | tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq); |
228 | if (!tmp) | |
229 | return NULL_RTX; | |
f06cd23d | 230 | |
5f3bc026 | 231 | return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq); |
f06cd23d ZC |
232 | } |
233 | } | |
234 | else | |
235 | { | |
236 | gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR | |
237 | || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR); | |
238 | ||
239 | if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison) | |
240 | { | |
5f3bc026 ZC |
241 | tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq); |
242 | if (!tmp) | |
243 | return NULL_RTX; | |
244 | ||
245 | return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq); | |
f06cd23d ZC |
246 | } |
247 | else | |
248 | { | |
249 | gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR | |
250 | || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR); | |
251 | } | |
252 | } | |
253 | ||
254 | return NULL_RTX; | |
255 | } | |
256 | ||
c8012fbc | 257 | /* Main entry to expand conditional compare statement G. |
f06cd23d ZC |
258 | Return NULL_RTX if G is not a legal candidate or expand fail. |
259 | Otherwise return the target. */ | |
260 | rtx | |
355fe088 | 261 | expand_ccmp_expr (gimple *g) |
f06cd23d ZC |
262 | { |
263 | rtx_insn *last; | |
264 | rtx tmp; | |
5f3bc026 ZC |
265 | rtx prep_seq, gen_seq; |
266 | ||
267 | prep_seq = gen_seq = NULL_RTX; | |
f06cd23d ZC |
268 | |
269 | if (!ccmp_candidate_p (g)) | |
270 | return NULL_RTX; | |
271 | ||
272 | last = get_last_insn (); | |
5f3bc026 | 273 | tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq); |
f06cd23d ZC |
274 | |
275 | if (tmp) | |
276 | { | |
078fe40a WD |
277 | insn_code icode; |
278 | machine_mode cc_mode = CCmode; | |
f06cd23d | 279 | tree lhs = gimple_assign_lhs (g); |
c8012fbc | 280 | rtx_code cmp_code = GET_CODE (tmp); |
5f3bc026 | 281 | |
f06cd23d | 282 | #ifdef SELECT_CC_MODE |
c8012fbc | 283 | cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx); |
f06cd23d | 284 | #endif |
f06cd23d ZC |
285 | icode = optab_handler (cstore_optab, cc_mode); |
286 | if (icode != CODE_FOR_nothing) | |
287 | { | |
078fe40a | 288 | machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); |
f06cd23d | 289 | rtx target = gen_reg_rtx (mode); |
5f3bc026 ZC |
290 | |
291 | emit_insn (prep_seq); | |
292 | emit_insn (gen_seq); | |
293 | ||
c8012fbc WD |
294 | tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode, |
295 | 0, XEXP (tmp, 0), const0_rtx, 1, mode); | |
f06cd23d ZC |
296 | if (tmp) |
297 | return tmp; | |
298 | } | |
299 | } | |
300 | /* Clean up. */ | |
301 | delete_insns_since (last); | |
302 | return NULL_RTX; | |
303 | } | |
304 |