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