Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-ifcombine.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 24 May 2010 12:47:05 +0900 |
parents | 77e2b8dfacca |
children | f6334be47118 |
rev | line source |
---|---|
0 | 1 /* Combining of if-expressions on trees. |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
0 | 3 Contributed by Richard Guenther <rguenther@suse.de> |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify | |
8 it under the terms of the GNU General Public License as published by | |
9 the Free Software Foundation; either version 3, or (at your option) | |
10 any later version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, | |
13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 GNU General Public License for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 #include "config.h" | |
22 #include "system.h" | |
23 #include "coretypes.h" | |
24 #include "tm.h" | |
25 #include "tree.h" | |
26 #include "basic-block.h" | |
27 #include "timevar.h" | |
28 #include "diagnostic.h" | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
29 #include "tree-pretty-print.h" |
0 | 30 #include "tree-flow.h" |
31 #include "tree-pass.h" | |
32 #include "tree-dump.h" | |
33 | |
34 /* This pass combines COND_EXPRs to simplify control flow. It | |
35 currently recognizes bit tests and comparisons in chains that | |
36 represent logical and or logical or of two COND_EXPRs. | |
37 | |
38 It does so by walking basic blocks in a approximate reverse | |
39 post-dominator order and trying to match CFG patterns that | |
40 represent logical and or logical or of two COND_EXPRs. | |
41 Transformations are done if the COND_EXPR conditions match | |
42 either | |
43 | |
44 1. two single bit tests X & (1 << Yn) (for logical and) | |
45 | |
46 2. two bit tests X & Yn (for logical or) | |
47 | |
48 3. two comparisons X OPn Y (for logical or) | |
49 | |
50 To simplify this pass, removing basic blocks and dead code | |
51 is left to CFG cleanup and DCE. */ | |
52 | |
53 | |
54 /* Recognize a if-then-else CFG pattern starting to match with the | |
55 COND_BB basic-block containing the COND_EXPR. The recognized | |
56 then end else blocks are stored to *THEN_BB and *ELSE_BB. If | |
57 *THEN_BB and/or *ELSE_BB are already set, they are required to | |
58 match the then and else basic-blocks to make the pattern match. | |
59 Returns true if the pattern matched, false otherwise. */ | |
60 | |
61 static bool | |
62 recognize_if_then_else (basic_block cond_bb, | |
63 basic_block *then_bb, basic_block *else_bb) | |
64 { | |
65 edge t, e; | |
66 | |
67 if (EDGE_COUNT (cond_bb->succs) != 2) | |
68 return false; | |
69 | |
70 /* Find the then/else edges. */ | |
71 t = EDGE_SUCC (cond_bb, 0); | |
72 e = EDGE_SUCC (cond_bb, 1); | |
73 if (!(t->flags & EDGE_TRUE_VALUE)) | |
74 { | |
75 edge tmp = t; | |
76 t = e; | |
77 e = tmp; | |
78 } | |
79 if (!(t->flags & EDGE_TRUE_VALUE) | |
80 || !(e->flags & EDGE_FALSE_VALUE)) | |
81 return false; | |
82 | |
83 /* Check if the edge destinations point to the required block. */ | |
84 if (*then_bb | |
85 && t->dest != *then_bb) | |
86 return false; | |
87 if (*else_bb | |
88 && e->dest != *else_bb) | |
89 return false; | |
90 | |
91 if (!*then_bb) | |
92 *then_bb = t->dest; | |
93 if (!*else_bb) | |
94 *else_bb = e->dest; | |
95 | |
96 return true; | |
97 } | |
98 | |
99 /* Verify if the basic block BB does not have side-effects. Return | |
100 true in this case, else false. */ | |
101 | |
102 static bool | |
103 bb_no_side_effects_p (basic_block bb) | |
104 { | |
105 gimple_stmt_iterator gsi; | |
106 | |
107 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
108 { | |
109 gimple stmt = gsi_stmt (gsi); | |
110 | |
111 if (gimple_has_volatile_ops (stmt) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
112 || gimple_vuse (stmt)) |
0 | 113 return false; |
114 } | |
115 | |
116 return true; | |
117 } | |
118 | |
119 /* Verify if all PHI node arguments in DEST for edges from BB1 or | |
120 BB2 to DEST are the same. This makes the CFG merge point | |
121 free from side-effects. Return true in this case, else false. */ | |
122 | |
123 static bool | |
124 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest) | |
125 { | |
126 edge e1 = find_edge (bb1, dest); | |
127 edge e2 = find_edge (bb2, dest); | |
128 gimple_stmt_iterator gsi; | |
129 gimple phi; | |
130 | |
131 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) | |
132 { | |
133 phi = gsi_stmt (gsi); | |
134 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1), | |
135 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0)) | |
136 return false; | |
137 } | |
138 | |
139 return true; | |
140 } | |
141 | |
142 /* Return the best representative SSA name for CANDIDATE which is used | |
143 in a bit test. */ | |
144 | |
145 static tree | |
146 get_name_for_bit_test (tree candidate) | |
147 { | |
148 /* Skip single-use names in favor of using the name from a | |
149 non-widening conversion definition. */ | |
150 if (TREE_CODE (candidate) == SSA_NAME | |
151 && has_single_use (candidate)) | |
152 { | |
153 gimple def_stmt = SSA_NAME_DEF_STMT (candidate); | |
154 if (is_gimple_assign (def_stmt) | |
36 | 155 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) |
0 | 156 { |
157 if (TYPE_PRECISION (TREE_TYPE (candidate)) | |
158 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) | |
159 return gimple_assign_rhs1 (def_stmt); | |
160 } | |
161 } | |
162 | |
163 return candidate; | |
164 } | |
165 | |
166 /* Recognize a single bit test pattern in GIMPLE_COND and its defining | |
167 statements. Store the name being tested in *NAME and the bit | |
168 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT). | |
169 Returns true if the pattern matched, false otherwise. */ | |
170 | |
171 static bool | |
172 recognize_single_bit_test (gimple cond, tree *name, tree *bit) | |
173 { | |
174 gimple stmt; | |
175 | |
176 /* Get at the definition of the result of the bit test. */ | |
177 if (gimple_cond_code (cond) != NE_EXPR | |
178 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME | |
179 || !integer_zerop (gimple_cond_rhs (cond))) | |
180 return false; | |
181 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); | |
182 if (!is_gimple_assign (stmt)) | |
183 return false; | |
184 | |
185 /* Look at which bit is tested. One form to recognize is | |
186 D.1985_5 = state_3(D) >> control1_4(D); | |
187 D.1986_6 = (int) D.1985_5; | |
188 D.1987_7 = op0 & 1; | |
189 if (D.1987_7 != 0) */ | |
190 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR | |
191 && integer_onep (gimple_assign_rhs2 (stmt)) | |
192 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
193 { | |
194 tree orig_name = gimple_assign_rhs1 (stmt); | |
195 | |
196 /* Look through copies and conversions to eventually | |
197 find the stmt that computes the shift. */ | |
198 stmt = SSA_NAME_DEF_STMT (orig_name); | |
199 | |
200 while (is_gimple_assign (stmt) | |
36 | 201 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)) |
202 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt))) | |
203 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))) | |
204 || gimple_assign_ssa_name_copy_p (stmt))) | |
205 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); | |
0 | 206 |
207 /* If we found such, decompose it. */ | |
208 if (is_gimple_assign (stmt) | |
209 && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR) | |
210 { | |
211 /* op0 & (1 << op1) */ | |
212 *bit = gimple_assign_rhs2 (stmt); | |
213 *name = gimple_assign_rhs1 (stmt); | |
214 } | |
215 else | |
216 { | |
217 /* t & 1 */ | |
218 *bit = integer_zero_node; | |
219 *name = get_name_for_bit_test (orig_name); | |
220 } | |
221 | |
222 return true; | |
223 } | |
224 | |
225 /* Another form is | |
226 D.1987_7 = op0 & (1 << CST) | |
227 if (D.1987_7 != 0) */ | |
228 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR | |
229 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
230 && integer_pow2p (gimple_assign_rhs2 (stmt))) | |
231 { | |
232 *name = gimple_assign_rhs1 (stmt); | |
233 *bit = build_int_cst (integer_type_node, | |
234 tree_log2 (gimple_assign_rhs2 (stmt))); | |
235 return true; | |
236 } | |
237 | |
238 /* Another form is | |
239 D.1986_6 = 1 << control1_4(D) | |
240 D.1987_7 = op0 & D.1986_6 | |
241 if (D.1987_7 != 0) */ | |
242 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR | |
243 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
244 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME) | |
245 { | |
246 gimple tmp; | |
247 | |
248 /* Both arguments of the BIT_AND_EXPR can be the single-bit | |
249 specifying expression. */ | |
250 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); | |
251 if (is_gimple_assign (tmp) | |
252 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR | |
253 && integer_onep (gimple_assign_rhs1 (tmp))) | |
254 { | |
255 *name = gimple_assign_rhs2 (stmt); | |
256 *bit = gimple_assign_rhs2 (tmp); | |
257 return true; | |
258 } | |
259 | |
260 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); | |
261 if (is_gimple_assign (tmp) | |
262 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR | |
263 && integer_onep (gimple_assign_rhs1 (tmp))) | |
264 { | |
265 *name = gimple_assign_rhs1 (stmt); | |
266 *bit = gimple_assign_rhs2 (tmp); | |
267 return true; | |
268 } | |
269 } | |
270 | |
271 return false; | |
272 } | |
273 | |
274 /* Recognize a bit test pattern in a GIMPLE_COND and its defining | |
275 statements. Store the name being tested in *NAME and the bits | |
276 in *BITS. The COND_EXPR computes *NAME & *BITS. | |
277 Returns true if the pattern matched, false otherwise. */ | |
278 | |
279 static bool | |
280 recognize_bits_test (gimple cond, tree *name, tree *bits) | |
281 { | |
282 gimple stmt; | |
283 | |
284 /* Get at the definition of the result of the bit test. */ | |
285 if (gimple_cond_code (cond) != NE_EXPR | |
286 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME | |
287 || !integer_zerop (gimple_cond_rhs (cond))) | |
288 return false; | |
289 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); | |
290 if (!is_gimple_assign (stmt) | |
291 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR) | |
292 return false; | |
293 | |
294 *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt)); | |
295 *bits = gimple_assign_rhs2 (stmt); | |
296 | |
297 return true; | |
298 } | |
299 | |
300 /* If-convert on a and pattern with a common else block. The inner | |
301 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. | |
302 Returns true if the edges to the common else basic-block were merged. */ | |
303 | |
304 static bool | |
305 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb) | |
306 { | |
307 gimple_stmt_iterator gsi; | |
308 gimple inner_cond, outer_cond; | |
309 tree name1, name2, bit1, bit2; | |
310 | |
311 inner_cond = last_stmt (inner_cond_bb); | |
312 if (!inner_cond | |
313 || gimple_code (inner_cond) != GIMPLE_COND) | |
314 return false; | |
315 | |
316 outer_cond = last_stmt (outer_cond_bb); | |
317 if (!outer_cond | |
318 || gimple_code (outer_cond) != GIMPLE_COND) | |
319 return false; | |
320 | |
321 /* See if we test a single bit of the same name in both tests. In | |
322 that case remove the outer test, merging both else edges, | |
323 and change the inner one to test for | |
324 name & (bit1 | bit2) == (bit1 | bit2). */ | |
325 if (recognize_single_bit_test (inner_cond, &name1, &bit1) | |
326 && recognize_single_bit_test (outer_cond, &name2, &bit2) | |
327 && name1 == name2) | |
328 { | |
329 tree t, t2; | |
330 | |
331 /* Do it. */ | |
332 gsi = gsi_for_stmt (inner_cond); | |
333 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), | |
334 build_int_cst (TREE_TYPE (name1), 1), bit1); | |
335 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), | |
336 build_int_cst (TREE_TYPE (name1), 1), bit2); | |
337 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2); | |
338 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, | |
339 true, GSI_SAME_STMT); | |
340 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); | |
341 t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE, | |
342 true, GSI_SAME_STMT); | |
343 t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
344 t = canonicalize_cond_expr_cond (t); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
345 if (!t) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
346 return false; |
0 | 347 gimple_cond_set_condition_from_tree (inner_cond, t); |
348 update_stmt (inner_cond); | |
349 | |
350 /* Leave CFG optimization to cfg_cleanup. */ | |
351 gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); | |
352 update_stmt (outer_cond); | |
353 | |
354 if (dump_file) | |
355 { | |
356 fprintf (dump_file, "optimizing double bit test to "); | |
357 print_generic_expr (dump_file, name1, 0); | |
358 fprintf (dump_file, " & T == T\nwith temporary T = (1 << "); | |
359 print_generic_expr (dump_file, bit1, 0); | |
360 fprintf (dump_file, ") | (1 << "); | |
361 print_generic_expr (dump_file, bit2, 0); | |
362 fprintf (dump_file, ")\n"); | |
363 } | |
364 | |
365 return true; | |
366 } | |
367 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
368 /* See if we have two comparisons that we can merge into one. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
369 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
370 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
371 && operand_equal_p (gimple_cond_lhs (inner_cond), |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
372 gimple_cond_lhs (outer_cond), 0) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
373 && operand_equal_p (gimple_cond_rhs (inner_cond), |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
374 gimple_cond_rhs (outer_cond), 0)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
375 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
376 enum tree_code code1 = gimple_cond_code (inner_cond); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
377 enum tree_code code2 = gimple_cond_code (outer_cond); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
378 tree t; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
379 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
380 if (!(t = combine_comparisons (UNKNOWN_LOCATION, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
381 TRUTH_ANDIF_EXPR, code1, code2, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
382 boolean_type_node, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
383 gimple_cond_lhs (outer_cond), |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
384 gimple_cond_rhs (outer_cond)))) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
385 return false; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
386 t = canonicalize_cond_expr_cond (t); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
387 if (!t) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
388 return false; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
389 gimple_cond_set_condition_from_tree (inner_cond, t); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
390 update_stmt (inner_cond); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
391 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
392 /* Leave CFG optimization to cfg_cleanup. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
393 gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
394 update_stmt (outer_cond); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
395 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
396 if (dump_file) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
397 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
398 fprintf (dump_file, "optimizing two comparisons to "); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
399 print_generic_expr (dump_file, t, 0); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
400 fprintf (dump_file, "\n"); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
401 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
402 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
403 return true; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
404 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
405 |
0 | 406 return false; |
407 } | |
408 | |
409 /* If-convert on a or pattern with a common then block. The inner | |
410 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. | |
411 Returns true, if the edges leading to the common then basic-block | |
412 were merged. */ | |
413 | |
414 static bool | |
415 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb) | |
416 { | |
417 gimple inner_cond, outer_cond; | |
418 tree name1, name2, bits1, bits2; | |
419 | |
420 inner_cond = last_stmt (inner_cond_bb); | |
421 if (!inner_cond | |
422 || gimple_code (inner_cond) != GIMPLE_COND) | |
423 return false; | |
424 | |
425 outer_cond = last_stmt (outer_cond_bb); | |
426 if (!outer_cond | |
427 || gimple_code (outer_cond) != GIMPLE_COND) | |
428 return false; | |
429 | |
430 /* See if we have two bit tests of the same name in both tests. | |
431 In that case remove the outer test and change the inner one to | |
432 test for name & (bits1 | bits2) != 0. */ | |
433 if (recognize_bits_test (inner_cond, &name1, &bits1) | |
434 && recognize_bits_test (outer_cond, &name2, &bits2)) | |
435 { | |
436 gimple_stmt_iterator gsi; | |
437 tree t; | |
438 | |
439 /* Find the common name which is bit-tested. */ | |
440 if (name1 == name2) | |
441 ; | |
442 else if (bits1 == bits2) | |
443 { | |
444 t = name2; | |
445 name2 = bits2; | |
446 bits2 = t; | |
447 t = name1; | |
448 name1 = bits1; | |
449 bits1 = t; | |
450 } | |
451 else if (name1 == bits2) | |
452 { | |
453 t = name2; | |
454 name2 = bits2; | |
455 bits2 = t; | |
456 } | |
457 else if (bits1 == name2) | |
458 { | |
459 t = name1; | |
460 name1 = bits1; | |
461 bits1 = t; | |
462 } | |
463 else | |
464 return false; | |
465 | |
466 /* As we strip non-widening conversions in finding a common | |
467 name that is tested make sure to end up with an integral | |
468 type for building the bit operations. */ | |
469 if (TYPE_PRECISION (TREE_TYPE (bits1)) | |
470 >= TYPE_PRECISION (TREE_TYPE (bits2))) | |
471 { | |
472 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1); | |
473 name1 = fold_convert (TREE_TYPE (bits1), name1); | |
474 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2); | |
475 bits2 = fold_convert (TREE_TYPE (bits1), bits2); | |
476 } | |
477 else | |
478 { | |
479 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2); | |
480 name1 = fold_convert (TREE_TYPE (bits2), name1); | |
481 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1); | |
482 bits1 = fold_convert (TREE_TYPE (bits2), bits1); | |
483 } | |
484 | |
485 /* Do it. */ | |
486 gsi = gsi_for_stmt (inner_cond); | |
487 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2); | |
488 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, | |
489 true, GSI_SAME_STMT); | |
490 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); | |
491 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, | |
492 true, GSI_SAME_STMT); | |
493 t = fold_build2 (NE_EXPR, boolean_type_node, t, | |
494 build_int_cst (TREE_TYPE (t), 0)); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
495 t = canonicalize_cond_expr_cond (t); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
496 if (!t) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
497 return false; |
0 | 498 gimple_cond_set_condition_from_tree (inner_cond, t); |
499 update_stmt (inner_cond); | |
500 | |
501 /* Leave CFG optimization to cfg_cleanup. */ | |
502 gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); | |
503 update_stmt (outer_cond); | |
504 | |
505 if (dump_file) | |
506 { | |
507 fprintf (dump_file, "optimizing bits or bits test to "); | |
508 print_generic_expr (dump_file, name1, 0); | |
509 fprintf (dump_file, " & T != 0\nwith temporary T = "); | |
510 print_generic_expr (dump_file, bits1, 0); | |
511 fprintf (dump_file, " | "); | |
512 print_generic_expr (dump_file, bits2, 0); | |
513 fprintf (dump_file, "\n"); | |
514 } | |
515 | |
516 return true; | |
517 } | |
518 | |
519 /* See if we have two comparisons that we can merge into one. | |
520 This happens for C++ operator overloading where for example | |
521 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */ | |
522 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison | |
523 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison | |
524 && operand_equal_p (gimple_cond_lhs (inner_cond), | |
525 gimple_cond_lhs (outer_cond), 0) | |
526 && operand_equal_p (gimple_cond_rhs (inner_cond), | |
527 gimple_cond_rhs (outer_cond), 0)) | |
528 { | |
529 enum tree_code code1 = gimple_cond_code (inner_cond); | |
530 enum tree_code code2 = gimple_cond_code (outer_cond); | |
531 tree t; | |
532 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
533 if (!(t = combine_comparisons (UNKNOWN_LOCATION, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
534 TRUTH_ORIF_EXPR, code1, code2, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
535 boolean_type_node, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
536 gimple_cond_lhs (outer_cond), |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
537 gimple_cond_rhs (outer_cond)))) |
0 | 538 return false; |
539 t = canonicalize_cond_expr_cond (t); | |
540 if (!t) | |
541 return false; | |
542 gimple_cond_set_condition_from_tree (inner_cond, t); | |
543 update_stmt (inner_cond); | |
544 | |
545 /* Leave CFG optimization to cfg_cleanup. */ | |
546 gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); | |
547 update_stmt (outer_cond); | |
548 | |
549 if (dump_file) | |
550 { | |
551 fprintf (dump_file, "optimizing two comparisons to "); | |
552 print_generic_expr (dump_file, t, 0); | |
553 fprintf (dump_file, "\n"); | |
554 } | |
555 | |
556 return true; | |
557 } | |
558 | |
559 return false; | |
560 } | |
561 | |
562 /* Recognize a CFG pattern and dispatch to the appropriate | |
563 if-conversion helper. We start with BB as the innermost | |
564 worker basic-block. Returns true if a transformation was done. */ | |
565 | |
566 static bool | |
567 tree_ssa_ifcombine_bb (basic_block inner_cond_bb) | |
568 { | |
569 basic_block then_bb = NULL, else_bb = NULL; | |
570 | |
571 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb)) | |
572 return false; | |
573 | |
574 /* Recognize && and || of two conditions with a common | |
575 then/else block which entry edges we can merge. That is: | |
576 if (a || b) | |
577 ; | |
578 and | |
579 if (a && b) | |
580 ; | |
581 This requires a single predecessor of the inner cond_bb. */ | |
582 if (single_pred_p (inner_cond_bb)) | |
583 { | |
584 basic_block outer_cond_bb = single_pred (inner_cond_bb); | |
585 | |
586 /* The && form is characterized by a common else_bb with | |
587 the two edges leading to it mergable. The latter is | |
588 guaranteed by matching PHI arguments in the else_bb and | |
589 the inner cond_bb having no side-effects. */ | |
590 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) | |
591 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) | |
592 && bb_no_side_effects_p (inner_cond_bb)) | |
593 { | |
594 /* We have | |
595 <outer_cond_bb> | |
596 if (q) goto inner_cond_bb; else goto else_bb; | |
597 <inner_cond_bb> | |
598 if (p) goto ...; else goto else_bb; | |
599 ... | |
600 <else_bb> | |
601 ... | |
602 */ | |
603 return ifcombine_ifandif (inner_cond_bb, outer_cond_bb); | |
604 } | |
605 | |
606 /* The || form is characterized by a common then_bb with the | |
607 two edges leading to it mergable. The latter is guaranteed | |
608 by matching PHI arguments in the then_bb and the inner cond_bb | |
609 having no side-effects. */ | |
610 if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) | |
611 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) | |
612 && bb_no_side_effects_p (inner_cond_bb)) | |
613 { | |
614 /* We have | |
615 <outer_cond_bb> | |
616 if (q) goto then_bb; else goto inner_cond_bb; | |
617 <inner_cond_bb> | |
618 if (q) goto then_bb; else goto ...; | |
619 <then_bb> | |
620 ... | |
621 */ | |
622 return ifcombine_iforif (inner_cond_bb, outer_cond_bb); | |
623 } | |
624 } | |
625 | |
626 return false; | |
627 } | |
628 | |
629 /* Main entry for the tree if-conversion pass. */ | |
630 | |
631 static unsigned int | |
632 tree_ssa_ifcombine (void) | |
633 { | |
634 basic_block *bbs; | |
635 bool cfg_changed = false; | |
636 int i; | |
637 | |
638 bbs = blocks_in_phiopt_order (); | |
639 | |
640 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i) | |
641 { | |
642 basic_block bb = bbs[i]; | |
643 gimple stmt = last_stmt (bb); | |
644 | |
645 if (stmt | |
646 && gimple_code (stmt) == GIMPLE_COND) | |
647 cfg_changed |= tree_ssa_ifcombine_bb (bb); | |
648 } | |
649 | |
650 free (bbs); | |
651 | |
652 return cfg_changed ? TODO_cleanup_cfg : 0; | |
653 } | |
654 | |
655 static bool | |
656 gate_ifcombine (void) | |
657 { | |
658 return 1; | |
659 } | |
660 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
661 struct gimple_opt_pass pass_tree_ifcombine = |
0 | 662 { |
663 { | |
664 GIMPLE_PASS, | |
665 "ifcombine", /* name */ | |
666 gate_ifcombine, /* gate */ | |
667 tree_ssa_ifcombine, /* execute */ | |
668 NULL, /* sub */ | |
669 NULL, /* next */ | |
670 0, /* static_pass_number */ | |
671 TV_TREE_IFCOMBINE, /* tv_id */ | |
672 PROP_cfg | PROP_ssa, /* properties_required */ | |
673 0, /* properties_provided */ | |
674 0, /* properties_destroyed */ | |
675 0, /* todo_flags_start */ | |
676 TODO_dump_func | |
677 | TODO_ggc_collect | |
678 | TODO_update_ssa | |
679 | TODO_verify_ssa /* todo_flags_finish */ | |
680 } | |
681 }; |