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