]>
Commit | Line | Data |
---|---|---|
f06cd23d | 1 | /* Conditional compare related functions |
5624e564 | 2 | Copyright (C) 2014-2015 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" | |
23 | #include "tm.h" | |
24 | #include "rtl.h" | |
25 | #include "tm_p.h" | |
40e23961 MC |
26 | #include "hash-set.h" |
27 | #include "machmode.h" | |
28 | #include "vec.h" | |
29 | #include "double-int.h" | |
30 | #include "input.h" | |
31 | #include "alias.h" | |
32 | #include "symtab.h" | |
33 | #include "wide-int.h" | |
34 | #include "inchash.h" | |
f06cd23d | 35 | #include "tree.h" |
40e23961 | 36 | #include "fold-const.h" |
f06cd23d ZC |
37 | #include "stringpool.h" |
38 | #include "stor-layout.h" | |
39 | #include "regs.h" | |
40 | #include "expr.h" | |
41 | #include "insn-codes.h" | |
42 | #include "optabs.h" | |
43 | #include "tree-iterator.h" | |
44 | #include "predict.h" | |
45 | #include "dominance.h" | |
46 | #include "cfg.h" | |
47 | #include "basic-block.h" | |
48 | #include "tree-ssa-alias.h" | |
49 | #include "internal-fn.h" | |
50 | #include "gimple-expr.h" | |
51 | #include "is-a.h" | |
52 | #include "gimple.h" | |
53 | #include "gimple-ssa.h" | |
54 | #include "tree-ssanames.h" | |
55 | #include "target.h" | |
56 | #include "common/common-target.h" | |
57 | #include "df.h" | |
58 | #include "tree-ssa-live.h" | |
59 | #include "tree-outof-ssa.h" | |
60 | #include "cfgexpand.h" | |
61 | #include "tree-phinodes.h" | |
62 | #include "ssa-iterators.h" | |
63 | #include "expmed.h" | |
64 | #include "ccmp.h" | |
65 | ||
66 | /* The following functions expand conditional compare (CCMP) instructions. | |
67 | Here is a short description about the over all algorithm: | |
68 | * ccmp_candidate_p is used to identify the CCMP candidate | |
69 | ||
70 | * expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1 | |
71 | to expand CCMP. | |
72 | ||
73 | * expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP. | |
74 | It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate | |
75 | CCMP instructions. | |
76 | - gen_ccmp_first expands the first compare in CCMP. | |
77 | - gen_ccmp_next expands the following compares. | |
78 | ||
79 | * If the final result is not used in a COND_EXPR (checked by function | |
80 | used_in_cond_stmt_p), it calls cstorecc4 pattern to store the CC to a | |
81 | general register. */ | |
82 | ||
83 | /* Check whether G is a potential conditional compare candidate. */ | |
84 | static bool | |
85 | ccmp_candidate_p (gimple g) | |
86 | { | |
87 | tree rhs = gimple_assign_rhs_to_tree (g); | |
88 | tree lhs, op0, op1; | |
89 | gimple gs0, gs1; | |
90 | enum tree_code tcode, tcode0, tcode1; | |
91 | tcode = TREE_CODE (rhs); | |
92 | ||
93 | if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR) | |
94 | return false; | |
95 | ||
96 | lhs = gimple_assign_lhs (g); | |
97 | op0 = TREE_OPERAND (rhs, 0); | |
98 | op1 = TREE_OPERAND (rhs, 1); | |
99 | ||
100 | if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME) | |
101 | || !has_single_use (lhs)) | |
102 | return false; | |
103 | ||
104 | gs0 = get_gimple_for_ssa_name (op0); | |
105 | gs1 = get_gimple_for_ssa_name (op1); | |
106 | if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1) | |
107 | /* g, gs0 and gs1 must be in the same basic block, since current stage | |
108 | is out-of-ssa. We can not guarantee the correctness when forwording | |
109 | the gs0 and gs1 into g whithout DATAFLOW analysis. */ | |
110 | || gimple_bb (gs0) != gimple_bb (gs1) | |
111 | || gimple_bb (gs0) != gimple_bb (g)) | |
112 | return false; | |
113 | ||
114 | if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))) | |
115 | || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))) | |
116 | || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1))) | |
117 | || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1))))) | |
118 | return false; | |
119 | ||
120 | tcode0 = gimple_assign_rhs_code (gs0); | |
121 | tcode1 = gimple_assign_rhs_code (gs1); | |
122 | if (TREE_CODE_CLASS (tcode0) == tcc_comparison | |
123 | && TREE_CODE_CLASS (tcode1) == tcc_comparison) | |
124 | return true; | |
125 | if (TREE_CODE_CLASS (tcode0) == tcc_comparison | |
126 | && ccmp_candidate_p (gs1)) | |
127 | return true; | |
128 | else if (TREE_CODE_CLASS (tcode1) == tcc_comparison | |
129 | && ccmp_candidate_p (gs0)) | |
130 | return true; | |
131 | /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since | |
132 | there is no way to set the CC flag. */ | |
133 | return false; | |
134 | } | |
135 | ||
136 | /* Check whether EXP is used in a GIMPLE_COND statement or not. */ | |
137 | static bool | |
138 | used_in_cond_stmt_p (tree exp) | |
139 | { | |
140 | bool expand_cond = false; | |
141 | imm_use_iterator ui; | |
142 | gimple use_stmt; | |
143 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, exp) | |
144 | if (gimple_code (use_stmt) == GIMPLE_COND) | |
145 | { | |
146 | tree op1 = gimple_cond_rhs (use_stmt); | |
147 | if (integer_zerop (op1)) | |
148 | expand_cond = true; | |
149 | BREAK_FROM_IMM_USE_STMT (ui); | |
150 | } | |
151 | else if (gimple_code (use_stmt) == GIMPLE_ASSIGN | |
152 | && gimple_expr_code (use_stmt) == COND_EXPR) | |
153 | { | |
154 | if (gimple_assign_rhs1 (use_stmt) == exp) | |
155 | expand_cond = true; | |
156 | } | |
157 | ||
158 | return expand_cond; | |
159 | } | |
160 | ||
161 | /* Expand conditional compare gimple G. A typical CCMP sequence is like: | |
162 | ||
163 | CC0 = CMP (a, b); | |
164 | CC1 = CCMP (NE (CC0, 0), CMP (e, f)); | |
165 | ... | |
166 | CCn = CCMP (NE (CCn-1, 0), CMP (...)); | |
167 | ||
168 | hook gen_ccmp_first is used to expand the first compare. | |
169 | hook gen_ccmp_next is used to expand the following CCMP. */ | |
170 | static rtx | |
171 | expand_ccmp_expr_1 (gimple g) | |
172 | { | |
173 | tree exp = gimple_assign_rhs_to_tree (g); | |
174 | enum tree_code code = TREE_CODE (exp); | |
175 | gimple gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0)); | |
176 | gimple gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1)); | |
177 | rtx tmp; | |
178 | enum tree_code code0 = gimple_assign_rhs_code (gs0); | |
179 | enum tree_code code1 = gimple_assign_rhs_code (gs1); | |
180 | ||
181 | gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR); | |
182 | gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1)); | |
183 | ||
184 | if (TREE_CODE_CLASS (code0) == tcc_comparison) | |
185 | { | |
186 | if (TREE_CODE_CLASS (code1) == tcc_comparison) | |
187 | { | |
188 | int unsignedp0, unsignedp1; | |
189 | enum rtx_code rcode0, rcode1; | |
190 | rtx op0, op1, op2, op3, tmp; | |
191 | ||
192 | unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0))); | |
193 | rcode0 = get_rtx_code (code0, unsignedp0); | |
194 | unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1))); | |
195 | rcode1 = get_rtx_code (code1, unsignedp1); | |
196 | ||
197 | expand_operands (gimple_assign_rhs1 (gs0), | |
198 | gimple_assign_rhs2 (gs0), | |
199 | NULL_RTX, &op0, &op1, EXPAND_NORMAL); | |
200 | ||
201 | /* Since the operands of GS1 might clobber CC reg, we expand the | |
202 | operands of GS1 before GEN_CCMP_FIRST. */ | |
203 | expand_operands (gimple_assign_rhs1 (gs1), | |
204 | gimple_assign_rhs2 (gs1), | |
205 | NULL_RTX, &op2, &op3, EXPAND_NORMAL); | |
206 | tmp = targetm.gen_ccmp_first (rcode0, op0, op1); | |
207 | if (!tmp) | |
208 | return NULL_RTX; | |
209 | ||
210 | return targetm.gen_ccmp_next (tmp, rcode1, op2, op3, | |
211 | get_rtx_code (code, 0)); | |
212 | } | |
213 | else | |
214 | { | |
215 | rtx op0, op1; | |
216 | enum rtx_code rcode; | |
217 | int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0))); | |
218 | ||
219 | rcode = get_rtx_code (gimple_assign_rhs_code (gs0), unsignedp); | |
220 | ||
221 | /* Hoist the preparation operations above the entire | |
222 | conditional compare sequence. */ | |
223 | expand_operands (gimple_assign_rhs1 (gs0), | |
224 | gimple_assign_rhs2 (gs0), | |
225 | NULL_RTX, &op0, &op1, EXPAND_NORMAL); | |
226 | ||
227 | gcc_assert (code1 == BIT_AND_EXPR || code1 == BIT_IOR_EXPR); | |
228 | ||
229 | /* Note: We swap the order to make the recursive function work. */ | |
230 | tmp = expand_ccmp_expr_1 (gs1); | |
231 | if (tmp) | |
232 | return targetm.gen_ccmp_next (tmp, rcode, op0, op1, | |
233 | get_rtx_code (code, 0)); | |
234 | } | |
235 | } | |
236 | else | |
237 | { | |
238 | gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR | |
239 | || gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR); | |
240 | ||
241 | if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison) | |
242 | { | |
243 | rtx op0, op1; | |
244 | enum rtx_code rcode; | |
245 | int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1))); | |
246 | ||
247 | rcode = get_rtx_code (gimple_assign_rhs_code (gs1), unsignedp); | |
248 | ||
249 | /* Hoist the preparation operations above the entire | |
250 | conditional compare sequence. */ | |
251 | expand_operands (gimple_assign_rhs1 (gs1), | |
252 | gimple_assign_rhs2 (gs1), | |
253 | NULL_RTX, &op0, &op1, EXPAND_NORMAL); | |
254 | tmp = expand_ccmp_expr_1 (gs0); | |
255 | if (tmp) | |
256 | return targetm.gen_ccmp_next (tmp, rcode, op0, op1, | |
257 | get_rtx_code (code, 0)); | |
258 | } | |
259 | else | |
260 | { | |
261 | gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR | |
262 | || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR); | |
263 | } | |
264 | } | |
265 | ||
266 | return NULL_RTX; | |
267 | } | |
268 | ||
269 | /* Main entry to expand conditional compare statement G. | |
270 | Return NULL_RTX if G is not a legal candidate or expand fail. | |
271 | Otherwise return the target. */ | |
272 | rtx | |
273 | expand_ccmp_expr (gimple g) | |
274 | { | |
275 | rtx_insn *last; | |
276 | rtx tmp; | |
277 | ||
278 | if (!ccmp_candidate_p (g)) | |
279 | return NULL_RTX; | |
280 | ||
281 | last = get_last_insn (); | |
282 | tmp = expand_ccmp_expr_1 (g); | |
283 | ||
284 | if (tmp) | |
285 | { | |
286 | enum insn_code icode; | |
287 | enum machine_mode cc_mode = CCmode; | |
288 | ||
289 | tree lhs = gimple_assign_lhs (g); | |
290 | /* TMP should be CC. If it is used in a GIMPLE_COND, just return it. | |
291 | Note: Target needs to define "cbranchcc4". */ | |
292 | if (used_in_cond_stmt_p (lhs)) | |
293 | return tmp; | |
294 | ||
295 | #ifdef SELECT_CC_MODE | |
296 | cc_mode = SELECT_CC_MODE (NE, tmp, const0_rtx); | |
297 | #endif | |
298 | /* If TMP is not used in a GIMPLE_COND, store it with a csctorecc4_optab. | |
299 | Note: Target needs to define "cstorecc4". */ | |
300 | icode = optab_handler (cstore_optab, cc_mode); | |
301 | if (icode != CODE_FOR_nothing) | |
302 | { | |
303 | tree lhs = gimple_assign_lhs (g); | |
304 | enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); | |
305 | rtx target = gen_reg_rtx (mode); | |
306 | tmp = emit_cstore (target, icode, NE, cc_mode, cc_mode, | |
307 | 0, tmp, const0_rtx, 1, mode); | |
308 | if (tmp) | |
309 | return tmp; | |
310 | } | |
311 | } | |
312 | /* Clean up. */ | |
313 | delete_insns_since (last); | |
314 | return NULL_RTX; | |
315 | } | |
316 |