* combine.c (try_combine): Prefer to delete dead SETs inside
[official-gcc.git] / gcc / tree-ssa-ifcombine.c
blob9fd71130db165eaa9f5e54ddf0283d7c24ade682
1 /* Combining of if-expressions on trees.
2 Copyright (C) 2007-2014 Free Software Foundation, Inc.
3 Contributed by Richard Guenther <rguenther@suse.de>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 /* rtl is needed only because arm back-end requires it for
26 BRANCH_COST. */
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "tree.h"
30 #include "stor-layout.h"
31 #include "predict.h"
32 #include "vec.h"
33 #include "hashtab.h"
34 #include "hash-set.h"
35 #include "machmode.h"
36 #include "hard-reg-set.h"
37 #include "input.h"
38 #include "function.h"
39 #include "dominance.h"
40 #include "cfg.h"
41 #include "cfganal.h"
42 #include "basic-block.h"
43 #include "tree-pretty-print.h"
44 #include "tree-ssa-alias.h"
45 #include "internal-fn.h"
46 #include "gimple-fold.h"
47 #include "gimple-expr.h"
48 #include "is-a.h"
49 #include "gimple.h"
50 #include "gimple-iterator.h"
51 #include "gimplify-me.h"
52 #include "gimple-ssa.h"
53 #include "tree-cfg.h"
54 #include "tree-phinodes.h"
55 #include "ssa-iterators.h"
56 #include "tree-pass.h"
58 #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
59 #define LOGICAL_OP_NON_SHORT_CIRCUIT \
60 (BRANCH_COST (optimize_function_for_speed_p (cfun), \
61 false) >= 2)
62 #endif
64 /* This pass combines COND_EXPRs to simplify control flow. It
65 currently recognizes bit tests and comparisons in chains that
66 represent logical and or logical or of two COND_EXPRs.
68 It does so by walking basic blocks in a approximate reverse
69 post-dominator order and trying to match CFG patterns that
70 represent logical and or logical or of two COND_EXPRs.
71 Transformations are done if the COND_EXPR conditions match
72 either
74 1. two single bit tests X & (1 << Yn) (for logical and)
76 2. two bit tests X & Yn (for logical or)
78 3. two comparisons X OPn Y (for logical or)
80 To simplify this pass, removing basic blocks and dead code
81 is left to CFG cleanup and DCE. */
84 /* Recognize a if-then-else CFG pattern starting to match with the
85 COND_BB basic-block containing the COND_EXPR. The recognized
86 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
87 *THEN_BB and/or *ELSE_BB are already set, they are required to
88 match the then and else basic-blocks to make the pattern match.
89 Returns true if the pattern matched, false otherwise. */
91 static bool
92 recognize_if_then_else (basic_block cond_bb,
93 basic_block *then_bb, basic_block *else_bb)
95 edge t, e;
97 if (EDGE_COUNT (cond_bb->succs) != 2)
98 return false;
100 /* Find the then/else edges. */
101 t = EDGE_SUCC (cond_bb, 0);
102 e = EDGE_SUCC (cond_bb, 1);
103 if (!(t->flags & EDGE_TRUE_VALUE))
105 edge tmp = t;
106 t = e;
107 e = tmp;
109 if (!(t->flags & EDGE_TRUE_VALUE)
110 || !(e->flags & EDGE_FALSE_VALUE))
111 return false;
113 /* Check if the edge destinations point to the required block. */
114 if (*then_bb
115 && t->dest != *then_bb)
116 return false;
117 if (*else_bb
118 && e->dest != *else_bb)
119 return false;
121 if (!*then_bb)
122 *then_bb = t->dest;
123 if (!*else_bb)
124 *else_bb = e->dest;
126 return true;
129 /* Verify if the basic block BB does not have side-effects. Return
130 true in this case, else false. */
132 static bool
133 bb_no_side_effects_p (basic_block bb)
135 gimple_stmt_iterator gsi;
137 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
139 gimple stmt = gsi_stmt (gsi);
141 if (is_gimple_debug (stmt))
142 continue;
144 if (gimple_has_side_effects (stmt)
145 || gimple_could_trap_p (stmt)
146 || gimple_vuse (stmt))
147 return false;
150 return true;
153 /* Return true if BB is an empty forwarder block to TO_BB. */
155 static bool
156 forwarder_block_to (basic_block bb, basic_block to_bb)
158 return empty_block_p (bb)
159 && single_succ_p (bb)
160 && single_succ (bb) == to_bb;
163 /* Verify if all PHI node arguments in DEST for edges from BB1 or
164 BB2 to DEST are the same. This makes the CFG merge point
165 free from side-effects. Return true in this case, else false. */
167 static bool
168 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
170 edge e1 = find_edge (bb1, dest);
171 edge e2 = find_edge (bb2, dest);
172 gphi_iterator gsi;
173 gphi *phi;
175 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
177 phi = gsi.phi ();
178 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
179 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
180 return false;
183 return true;
186 /* Return the best representative SSA name for CANDIDATE which is used
187 in a bit test. */
189 static tree
190 get_name_for_bit_test (tree candidate)
192 /* Skip single-use names in favor of using the name from a
193 non-widening conversion definition. */
194 if (TREE_CODE (candidate) == SSA_NAME
195 && has_single_use (candidate))
197 gimple def_stmt = SSA_NAME_DEF_STMT (candidate);
198 if (is_gimple_assign (def_stmt)
199 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
201 if (TYPE_PRECISION (TREE_TYPE (candidate))
202 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
203 return gimple_assign_rhs1 (def_stmt);
207 return candidate;
210 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
211 statements. Store the name being tested in *NAME and the bit
212 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
213 Returns true if the pattern matched, false otherwise. */
215 static bool
216 recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
218 gimple stmt;
220 /* Get at the definition of the result of the bit test. */
221 if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
222 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
223 || !integer_zerop (gimple_cond_rhs (cond)))
224 return false;
225 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
226 if (!is_gimple_assign (stmt))
227 return false;
229 /* Look at which bit is tested. One form to recognize is
230 D.1985_5 = state_3(D) >> control1_4(D);
231 D.1986_6 = (int) D.1985_5;
232 D.1987_7 = op0 & 1;
233 if (D.1987_7 != 0) */
234 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
235 && integer_onep (gimple_assign_rhs2 (stmt))
236 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
238 tree orig_name = gimple_assign_rhs1 (stmt);
240 /* Look through copies and conversions to eventually
241 find the stmt that computes the shift. */
242 stmt = SSA_NAME_DEF_STMT (orig_name);
244 while (is_gimple_assign (stmt)
245 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
246 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
247 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
248 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
249 || gimple_assign_ssa_name_copy_p (stmt)))
250 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
252 /* If we found such, decompose it. */
253 if (is_gimple_assign (stmt)
254 && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
256 /* op0 & (1 << op1) */
257 *bit = gimple_assign_rhs2 (stmt);
258 *name = gimple_assign_rhs1 (stmt);
260 else
262 /* t & 1 */
263 *bit = integer_zero_node;
264 *name = get_name_for_bit_test (orig_name);
267 return true;
270 /* Another form is
271 D.1987_7 = op0 & (1 << CST)
272 if (D.1987_7 != 0) */
273 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
274 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
275 && integer_pow2p (gimple_assign_rhs2 (stmt)))
277 *name = gimple_assign_rhs1 (stmt);
278 *bit = build_int_cst (integer_type_node,
279 tree_log2 (gimple_assign_rhs2 (stmt)));
280 return true;
283 /* Another form is
284 D.1986_6 = 1 << control1_4(D)
285 D.1987_7 = op0 & D.1986_6
286 if (D.1987_7 != 0) */
287 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
288 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
289 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
291 gimple tmp;
293 /* Both arguments of the BIT_AND_EXPR can be the single-bit
294 specifying expression. */
295 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
296 if (is_gimple_assign (tmp)
297 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
298 && integer_onep (gimple_assign_rhs1 (tmp)))
300 *name = gimple_assign_rhs2 (stmt);
301 *bit = gimple_assign_rhs2 (tmp);
302 return true;
305 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
306 if (is_gimple_assign (tmp)
307 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
308 && integer_onep (gimple_assign_rhs1 (tmp)))
310 *name = gimple_assign_rhs1 (stmt);
311 *bit = gimple_assign_rhs2 (tmp);
312 return true;
316 return false;
319 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
320 statements. Store the name being tested in *NAME and the bits
321 in *BITS. The COND_EXPR computes *NAME & *BITS.
322 Returns true if the pattern matched, false otherwise. */
324 static bool
325 recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
327 gimple stmt;
329 /* Get at the definition of the result of the bit test. */
330 if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
331 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
332 || !integer_zerop (gimple_cond_rhs (cond)))
333 return false;
334 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
335 if (!is_gimple_assign (stmt)
336 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
337 return false;
339 *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
340 *bits = gimple_assign_rhs2 (stmt);
342 return true;
345 /* If-convert on a and pattern with a common else block. The inner
346 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
347 inner_inv, outer_inv and result_inv indicate whether the conditions
348 are inverted.
349 Returns true if the edges to the common else basic-block were merged. */
351 static bool
352 ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
353 basic_block outer_cond_bb, bool outer_inv, bool result_inv)
355 gimple_stmt_iterator gsi;
356 gimple inner_stmt, outer_stmt;
357 gcond *inner_cond, *outer_cond;
358 tree name1, name2, bit1, bit2, bits1, bits2;
360 inner_stmt = last_stmt (inner_cond_bb);
361 if (!inner_stmt
362 || gimple_code (inner_stmt) != GIMPLE_COND)
363 return false;
364 inner_cond = as_a <gcond *> (inner_stmt);
366 outer_stmt = last_stmt (outer_cond_bb);
367 if (!outer_stmt
368 || gimple_code (outer_stmt) != GIMPLE_COND)
369 return false;
370 outer_cond = as_a <gcond *> (outer_stmt);
372 /* See if we test a single bit of the same name in both tests. In
373 that case remove the outer test, merging both else edges,
374 and change the inner one to test for
375 name & (bit1 | bit2) == (bit1 | bit2). */
376 if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
377 && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
378 && name1 == name2)
380 tree t, t2;
382 /* Do it. */
383 gsi = gsi_for_stmt (inner_cond);
384 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
385 build_int_cst (TREE_TYPE (name1), 1), bit1);
386 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
387 build_int_cst (TREE_TYPE (name1), 1), bit2);
388 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
389 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
390 true, GSI_SAME_STMT);
391 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
392 t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
393 true, GSI_SAME_STMT);
394 t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
395 boolean_type_node, t2, t);
396 t = canonicalize_cond_expr_cond (t);
397 if (!t)
398 return false;
399 gimple_cond_set_condition_from_tree (inner_cond, t);
400 update_stmt (inner_cond);
402 /* Leave CFG optimization to cfg_cleanup. */
403 gimple_cond_set_condition_from_tree (outer_cond,
404 outer_inv ? boolean_false_node : boolean_true_node);
405 update_stmt (outer_cond);
407 if (dump_file)
409 fprintf (dump_file, "optimizing double bit test to ");
410 print_generic_expr (dump_file, name1, 0);
411 fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
412 print_generic_expr (dump_file, bit1, 0);
413 fprintf (dump_file, ") | (1 << ");
414 print_generic_expr (dump_file, bit2, 0);
415 fprintf (dump_file, ")\n");
418 return true;
421 /* See if we have two bit tests of the same name in both tests.
422 In that case remove the outer test and change the inner one to
423 test for name & (bits1 | bits2) != 0. */
424 else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
425 && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
427 gimple_stmt_iterator gsi;
428 tree t;
430 /* Find the common name which is bit-tested. */
431 if (name1 == name2)
433 else if (bits1 == bits2)
435 t = name2;
436 name2 = bits2;
437 bits2 = t;
438 t = name1;
439 name1 = bits1;
440 bits1 = t;
442 else if (name1 == bits2)
444 t = name2;
445 name2 = bits2;
446 bits2 = t;
448 else if (bits1 == name2)
450 t = name1;
451 name1 = bits1;
452 bits1 = t;
454 else
455 return false;
457 /* As we strip non-widening conversions in finding a common
458 name that is tested make sure to end up with an integral
459 type for building the bit operations. */
460 if (TYPE_PRECISION (TREE_TYPE (bits1))
461 >= TYPE_PRECISION (TREE_TYPE (bits2)))
463 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
464 name1 = fold_convert (TREE_TYPE (bits1), name1);
465 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
466 bits2 = fold_convert (TREE_TYPE (bits1), bits2);
468 else
470 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
471 name1 = fold_convert (TREE_TYPE (bits2), name1);
472 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
473 bits1 = fold_convert (TREE_TYPE (bits2), bits1);
476 /* Do it. */
477 gsi = gsi_for_stmt (inner_cond);
478 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
479 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
480 true, GSI_SAME_STMT);
481 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
482 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
483 true, GSI_SAME_STMT);
484 t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t,
485 build_int_cst (TREE_TYPE (t), 0));
486 t = canonicalize_cond_expr_cond (t);
487 if (!t)
488 return false;
489 gimple_cond_set_condition_from_tree (inner_cond, t);
490 update_stmt (inner_cond);
492 /* Leave CFG optimization to cfg_cleanup. */
493 gimple_cond_set_condition_from_tree (outer_cond,
494 outer_inv ? boolean_false_node : boolean_true_node);
495 update_stmt (outer_cond);
497 if (dump_file)
499 fprintf (dump_file, "optimizing bits or bits test to ");
500 print_generic_expr (dump_file, name1, 0);
501 fprintf (dump_file, " & T != 0\nwith temporary T = ");
502 print_generic_expr (dump_file, bits1, 0);
503 fprintf (dump_file, " | ");
504 print_generic_expr (dump_file, bits2, 0);
505 fprintf (dump_file, "\n");
508 return true;
511 /* See if we have two comparisons that we can merge into one. */
512 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
513 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
515 tree t;
516 enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
517 enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
519 /* Invert comparisons if necessary (and possible). */
520 if (inner_inv)
521 inner_cond_code = invert_tree_comparison (inner_cond_code,
522 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond)))));
523 if (inner_cond_code == ERROR_MARK)
524 return false;
525 if (outer_inv)
526 outer_cond_code = invert_tree_comparison (outer_cond_code,
527 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));
528 if (outer_cond_code == ERROR_MARK)
529 return false;
530 /* Don't return false so fast, try maybe_fold_or_comparisons? */
532 if (!(t = maybe_fold_and_comparisons (inner_cond_code,
533 gimple_cond_lhs (inner_cond),
534 gimple_cond_rhs (inner_cond),
535 outer_cond_code,
536 gimple_cond_lhs (outer_cond),
537 gimple_cond_rhs (outer_cond))))
539 tree t1, t2;
540 gimple_stmt_iterator gsi;
541 if (!LOGICAL_OP_NON_SHORT_CIRCUIT)
542 return false;
543 /* Only do this optimization if the inner bb contains only the conditional. */
544 if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb)))
545 return false;
546 t1 = fold_build2_loc (gimple_location (inner_cond),
547 inner_cond_code,
548 boolean_type_node,
549 gimple_cond_lhs (inner_cond),
550 gimple_cond_rhs (inner_cond));
551 t2 = fold_build2_loc (gimple_location (outer_cond),
552 outer_cond_code,
553 boolean_type_node,
554 gimple_cond_lhs (outer_cond),
555 gimple_cond_rhs (outer_cond));
556 t = fold_build2_loc (gimple_location (inner_cond),
557 TRUTH_AND_EXPR, boolean_type_node, t1, t2);
558 if (result_inv)
560 t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
561 result_inv = false;
563 gsi = gsi_for_stmt (inner_cond);
564 t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr, NULL, true,
565 GSI_SAME_STMT);
567 if (result_inv)
568 t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
569 t = canonicalize_cond_expr_cond (t);
570 if (!t)
571 return false;
572 gimple_cond_set_condition_from_tree (inner_cond, t);
573 update_stmt (inner_cond);
575 /* Leave CFG optimization to cfg_cleanup. */
576 gimple_cond_set_condition_from_tree (outer_cond,
577 outer_inv ? boolean_false_node : boolean_true_node);
578 update_stmt (outer_cond);
580 if (dump_file)
582 fprintf (dump_file, "optimizing two comparisons to ");
583 print_generic_expr (dump_file, t, 0);
584 fprintf (dump_file, "\n");
587 return true;
590 return false;
593 /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
594 dispatch to the appropriate if-conversion helper for a particular
595 set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
596 PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */
598 static bool
599 tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
600 basic_block then_bb, basic_block else_bb,
601 basic_block phi_pred_bb)
603 /* The && form is characterized by a common else_bb with
604 the two edges leading to it mergable. The latter is
605 guaranteed by matching PHI arguments in the else_bb and
606 the inner cond_bb having no side-effects. */
607 if (phi_pred_bb != else_bb
608 && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
609 && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb)
610 && bb_no_side_effects_p (inner_cond_bb))
612 /* We have
613 <outer_cond_bb>
614 if (q) goto inner_cond_bb; else goto else_bb;
615 <inner_cond_bb>
616 if (p) goto ...; else goto else_bb;
618 <else_bb>
621 return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false,
622 false);
625 /* And a version where the outer condition is negated. */
626 if (phi_pred_bb != else_bb
627 && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
628 && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb)
629 && bb_no_side_effects_p (inner_cond_bb))
631 /* We have
632 <outer_cond_bb>
633 if (q) goto else_bb; else goto inner_cond_bb;
634 <inner_cond_bb>
635 if (p) goto ...; else goto else_bb;
637 <else_bb>
640 return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true,
641 false);
644 /* The || form is characterized by a common then_bb with the
645 two edges leading to it mergable. The latter is guaranteed
646 by matching PHI arguments in the then_bb and the inner cond_bb
647 having no side-effects. */
648 if (phi_pred_bb != then_bb
649 && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
650 && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb)
651 && bb_no_side_effects_p (inner_cond_bb))
653 /* We have
654 <outer_cond_bb>
655 if (q) goto then_bb; else goto inner_cond_bb;
656 <inner_cond_bb>
657 if (q) goto then_bb; else goto ...;
658 <then_bb>
661 return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true,
662 true);
665 /* And a version where the outer condition is negated. */
666 if (phi_pred_bb != then_bb
667 && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
668 && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb)
669 && bb_no_side_effects_p (inner_cond_bb))
671 /* We have
672 <outer_cond_bb>
673 if (q) goto inner_cond_bb; else goto then_bb;
674 <inner_cond_bb>
675 if (q) goto then_bb; else goto ...;
676 <then_bb>
679 return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
680 true);
683 return false;
686 /* Recognize a CFG pattern and dispatch to the appropriate
687 if-conversion helper. We start with BB as the innermost
688 worker basic-block. Returns true if a transformation was done. */
690 static bool
691 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
693 basic_block then_bb = NULL, else_bb = NULL;
695 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
696 return false;
698 /* Recognize && and || of two conditions with a common
699 then/else block which entry edges we can merge. That is:
700 if (a || b)
703 if (a && b)
705 This requires a single predecessor of the inner cond_bb. */
706 if (single_pred_p (inner_cond_bb))
708 basic_block outer_cond_bb = single_pred (inner_cond_bb);
710 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
711 then_bb, else_bb, inner_cond_bb))
712 return true;
714 if (forwarder_block_to (else_bb, then_bb))
716 /* Other possibilities for the && form, if else_bb is
717 empty forwarder block to then_bb. Compared to the above simpler
718 forms this can be treated as if then_bb and else_bb were swapped,
719 and the corresponding inner_cond_bb not inverted because of that.
720 For same_phi_args_p we look at equality of arguments between
721 edge from outer_cond_bb and the forwarder block. */
722 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
723 then_bb, else_bb))
724 return true;
726 else if (forwarder_block_to (then_bb, else_bb))
728 /* Other possibilities for the || form, if then_bb is
729 empty forwarder block to else_bb. Compared to the above simpler
730 forms this can be treated as if then_bb and else_bb were swapped,
731 and the corresponding inner_cond_bb not inverted because of that.
732 For same_phi_args_p we look at equality of arguments between
733 edge from outer_cond_bb and the forwarder block. */
734 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
735 then_bb, then_bb))
736 return true;
740 return false;
743 /* Main entry for the tree if-conversion pass. */
745 namespace {
747 const pass_data pass_data_tree_ifcombine =
749 GIMPLE_PASS, /* type */
750 "ifcombine", /* name */
751 OPTGROUP_NONE, /* optinfo_flags */
752 TV_TREE_IFCOMBINE, /* tv_id */
753 ( PROP_cfg | PROP_ssa ), /* properties_required */
754 0, /* properties_provided */
755 0, /* properties_destroyed */
756 0, /* todo_flags_start */
757 TODO_update_ssa, /* todo_flags_finish */
760 class pass_tree_ifcombine : public gimple_opt_pass
762 public:
763 pass_tree_ifcombine (gcc::context *ctxt)
764 : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
767 /* opt_pass methods: */
768 virtual unsigned int execute (function *);
770 }; // class pass_tree_ifcombine
772 unsigned int
773 pass_tree_ifcombine::execute (function *fun)
775 basic_block *bbs;
776 bool cfg_changed = false;
777 int i;
779 bbs = single_pred_before_succ_order ();
780 calculate_dominance_info (CDI_DOMINATORS);
782 /* Search every basic block for COND_EXPR we may be able to optimize.
784 We walk the blocks in order that guarantees that a block with
785 a single predecessor is processed after the predecessor.
786 This ensures that we collapse outter ifs before visiting the
787 inner ones, and also that we do not try to visit a removed
788 block. This is opposite of PHI-OPT, because we cascade the
789 combining rather than cascading PHIs. */
790 for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
792 basic_block bb = bbs[i];
793 gimple stmt = last_stmt (bb);
795 if (stmt
796 && gimple_code (stmt) == GIMPLE_COND)
797 cfg_changed |= tree_ssa_ifcombine_bb (bb);
800 free (bbs);
802 return cfg_changed ? TODO_cleanup_cfg : 0;
805 } // anon namespace
807 gimple_opt_pass *
808 make_pass_tree_ifcombine (gcc::context *ctxt)
810 return new pass_tree_ifcombine (ctxt);