1 /* Combining of if-expressions on trees.
2 Copyright (C) 2007-2017 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)
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/>. */
23 #include "coretypes.h"
29 #include "tree-pass.h"
33 #include "tree-pretty-print.h"
34 /* rtl is needed only because arm back-end requires it for
36 #include "fold-const.h"
38 #include "gimple-fold.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
44 #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
45 #define LOGICAL_OP_NON_SHORT_CIRCUIT \
46 (BRANCH_COST (optimize_function_for_speed_p (cfun), \
50 /* This pass combines COND_EXPRs to simplify control flow. It
51 currently recognizes bit tests and comparisons in chains that
52 represent logical and or logical or of two COND_EXPRs.
54 It does so by walking basic blocks in a approximate reverse
55 post-dominator order and trying to match CFG patterns that
56 represent logical and or logical or of two COND_EXPRs.
57 Transformations are done if the COND_EXPR conditions match
60 1. two single bit tests X & (1 << Yn) (for logical and)
62 2. two bit tests X & Yn (for logical or)
64 3. two comparisons X OPn Y (for logical or)
66 To simplify this pass, removing basic blocks and dead code
67 is left to CFG cleanup and DCE. */
70 /* Recognize a if-then-else CFG pattern starting to match with the
71 COND_BB basic-block containing the COND_EXPR. The recognized
72 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
73 *THEN_BB and/or *ELSE_BB are already set, they are required to
74 match the then and else basic-blocks to make the pattern match.
75 Returns true if the pattern matched, false otherwise. */
78 recognize_if_then_else (basic_block cond_bb
,
79 basic_block
*then_bb
, basic_block
*else_bb
)
83 if (EDGE_COUNT (cond_bb
->succs
) != 2)
86 /* Find the then/else edges. */
87 t
= EDGE_SUCC (cond_bb
, 0);
88 e
= EDGE_SUCC (cond_bb
, 1);
89 if (!(t
->flags
& EDGE_TRUE_VALUE
))
91 if (!(t
->flags
& EDGE_TRUE_VALUE
)
92 || !(e
->flags
& EDGE_FALSE_VALUE
))
95 /* Check if the edge destinations point to the required block. */
97 && t
->dest
!= *then_bb
)
100 && e
->dest
!= *else_bb
)
111 /* Verify if the basic block BB does not have side-effects. Return
112 true in this case, else false. */
115 bb_no_side_effects_p (basic_block bb
)
117 gimple_stmt_iterator gsi
;
119 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
121 gimple
*stmt
= gsi_stmt (gsi
);
123 if (is_gimple_debug (stmt
))
126 if (gimple_has_side_effects (stmt
)
127 || gimple_uses_undefined_value_p (stmt
)
128 || gimple_could_trap_p (stmt
)
129 || gimple_vuse (stmt
)
130 /* const calls don't match any of the above, yet they could
131 still have some side-effects - they could contain
132 gimple_could_trap_p statements, like floating point
133 exceptions or integer division by zero. See PR70586.
134 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
135 should handle this. */
136 || is_gimple_call (stmt
))
143 /* Return true if BB is an empty forwarder block to TO_BB. */
146 forwarder_block_to (basic_block bb
, basic_block to_bb
)
148 return empty_block_p (bb
)
149 && single_succ_p (bb
)
150 && single_succ (bb
) == to_bb
;
153 /* Verify if all PHI node arguments in DEST for edges from BB1 or
154 BB2 to DEST are the same. This makes the CFG merge point
155 free from side-effects. Return true in this case, else false. */
158 same_phi_args_p (basic_block bb1
, basic_block bb2
, basic_block dest
)
160 edge e1
= find_edge (bb1
, dest
);
161 edge e2
= find_edge (bb2
, dest
);
165 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
168 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi
, e1
),
169 PHI_ARG_DEF_FROM_EDGE (phi
, e2
), 0))
176 /* Return the best representative SSA name for CANDIDATE which is used
180 get_name_for_bit_test (tree candidate
)
182 /* Skip single-use names in favor of using the name from a
183 non-widening conversion definition. */
184 if (TREE_CODE (candidate
) == SSA_NAME
185 && has_single_use (candidate
))
187 gimple
*def_stmt
= SSA_NAME_DEF_STMT (candidate
);
188 if (is_gimple_assign (def_stmt
)
189 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
191 if (TYPE_PRECISION (TREE_TYPE (candidate
))
192 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
193 return gimple_assign_rhs1 (def_stmt
);
200 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
201 statements. Store the name being tested in *NAME and the bit
202 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
203 Returns true if the pattern matched, false otherwise. */
206 recognize_single_bit_test (gcond
*cond
, tree
*name
, tree
*bit
, bool inv
)
210 /* Get at the definition of the result of the bit test. */
211 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
212 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
213 || !integer_zerop (gimple_cond_rhs (cond
)))
215 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
216 if (!is_gimple_assign (stmt
))
219 /* Look at which bit is tested. One form to recognize is
220 D.1985_5 = state_3(D) >> control1_4(D);
221 D.1986_6 = (int) D.1985_5;
223 if (D.1987_7 != 0) */
224 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
225 && integer_onep (gimple_assign_rhs2 (stmt
))
226 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
228 tree orig_name
= gimple_assign_rhs1 (stmt
);
230 /* Look through copies and conversions to eventually
231 find the stmt that computes the shift. */
232 stmt
= SSA_NAME_DEF_STMT (orig_name
);
234 while (is_gimple_assign (stmt
)
235 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
236 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt
)))
237 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt
))))
238 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
239 || gimple_assign_ssa_name_copy_p (stmt
)))
240 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
242 /* If we found such, decompose it. */
243 if (is_gimple_assign (stmt
)
244 && gimple_assign_rhs_code (stmt
) == RSHIFT_EXPR
)
246 /* op0 & (1 << op1) */
247 *bit
= gimple_assign_rhs2 (stmt
);
248 *name
= gimple_assign_rhs1 (stmt
);
253 *bit
= integer_zero_node
;
254 *name
= get_name_for_bit_test (orig_name
);
261 D.1987_7 = op0 & (1 << CST)
262 if (D.1987_7 != 0) */
263 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
264 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
265 && integer_pow2p (gimple_assign_rhs2 (stmt
)))
267 *name
= gimple_assign_rhs1 (stmt
);
268 *bit
= build_int_cst (integer_type_node
,
269 tree_log2 (gimple_assign_rhs2 (stmt
)));
274 D.1986_6 = 1 << control1_4(D)
275 D.1987_7 = op0 & D.1986_6
276 if (D.1987_7 != 0) */
277 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
278 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
279 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
)
283 /* Both arguments of the BIT_AND_EXPR can be the single-bit
284 specifying expression. */
285 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
286 if (is_gimple_assign (tmp
)
287 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
288 && integer_onep (gimple_assign_rhs1 (tmp
)))
290 *name
= gimple_assign_rhs2 (stmt
);
291 *bit
= gimple_assign_rhs2 (tmp
);
295 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (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_rhs1 (stmt
);
301 *bit
= gimple_assign_rhs2 (tmp
);
309 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
310 statements. Store the name being tested in *NAME and the bits
311 in *BITS. The COND_EXPR computes *NAME & *BITS.
312 Returns true if the pattern matched, false otherwise. */
315 recognize_bits_test (gcond
*cond
, tree
*name
, tree
*bits
, bool inv
)
319 /* Get at the definition of the result of the bit test. */
320 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
321 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
322 || !integer_zerop (gimple_cond_rhs (cond
)))
324 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
325 if (!is_gimple_assign (stmt
)
326 || gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
)
329 *name
= get_name_for_bit_test (gimple_assign_rhs1 (stmt
));
330 *bits
= gimple_assign_rhs2 (stmt
);
336 /* Update profile after code in outer_cond_bb was adjusted so
337 outer_cond_bb has no condition. */
340 update_profile_after_ifcombine (basic_block inner_cond_bb
,
341 basic_block outer_cond_bb
)
343 edge outer_to_inner
= find_edge (outer_cond_bb
, inner_cond_bb
);
344 edge outer2
= (EDGE_SUCC (outer_cond_bb
, 0) == outer_to_inner
345 ? EDGE_SUCC (outer_cond_bb
, 1)
346 : EDGE_SUCC (outer_cond_bb
, 0));
347 edge inner_taken
= EDGE_SUCC (inner_cond_bb
, 0);
348 edge inner_not_taken
= EDGE_SUCC (inner_cond_bb
, 1);
350 if (inner_taken
->dest
!= outer2
->dest
)
351 std::swap (inner_taken
, inner_not_taken
);
352 gcc_assert (inner_taken
->dest
== outer2
->dest
);
354 /* In the following we assume that inner_cond_bb has single predecessor. */
355 gcc_assert (single_pred_p (inner_cond_bb
));
357 /* Path outer_cond_bb->(outer2) needs to be merged into path
358 outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
359 and probability of inner_not_taken updated. */
361 inner_cond_bb
->count
= outer_cond_bb
->count
;
363 inner_taken
->probability
= outer2
->probability
+ outer_to_inner
->probability
364 * inner_taken
->probability
;
365 inner_not_taken
->probability
= profile_probability::always ()
366 - inner_taken
->probability
;
368 outer_to_inner
->probability
= profile_probability::always ();
369 inner_cond_bb
->frequency
= outer_cond_bb
->frequency
;
370 outer2
->probability
= profile_probability::never ();
373 /* If-convert on a and pattern with a common else block. The inner
374 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
375 inner_inv, outer_inv and result_inv indicate whether the conditions
377 Returns true if the edges to the common else basic-block were merged. */
380 ifcombine_ifandif (basic_block inner_cond_bb
, bool inner_inv
,
381 basic_block outer_cond_bb
, bool outer_inv
, bool result_inv
)
383 gimple_stmt_iterator gsi
;
384 gimple
*inner_stmt
, *outer_stmt
;
385 gcond
*inner_cond
, *outer_cond
;
386 tree name1
, name2
, bit1
, bit2
, bits1
, bits2
;
388 inner_stmt
= last_stmt (inner_cond_bb
);
390 || gimple_code (inner_stmt
) != GIMPLE_COND
)
392 inner_cond
= as_a
<gcond
*> (inner_stmt
);
394 outer_stmt
= last_stmt (outer_cond_bb
);
396 || gimple_code (outer_stmt
) != GIMPLE_COND
)
398 outer_cond
= as_a
<gcond
*> (outer_stmt
);
400 /* See if we test a single bit of the same name in both tests. In
401 that case remove the outer test, merging both else edges,
402 and change the inner one to test for
403 name & (bit1 | bit2) == (bit1 | bit2). */
404 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
, inner_inv
)
405 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
, outer_inv
)
411 gsi
= gsi_for_stmt (inner_cond
);
412 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
413 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
414 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
415 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
416 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
417 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
418 true, GSI_SAME_STMT
);
419 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
420 t2
= force_gimple_operand_gsi (&gsi
, t2
, true, NULL_TREE
,
421 true, GSI_SAME_STMT
);
422 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
,
423 boolean_type_node
, t2
, t
);
424 t
= canonicalize_cond_expr_cond (t
);
427 gimple_cond_set_condition_from_tree (inner_cond
, t
);
428 update_stmt (inner_cond
);
430 /* Leave CFG optimization to cfg_cleanup. */
431 gimple_cond_set_condition_from_tree (outer_cond
,
432 outer_inv
? boolean_false_node
: boolean_true_node
);
433 update_stmt (outer_cond
);
435 update_profile_after_ifcombine (inner_cond_bb
, outer_cond_bb
);
439 fprintf (dump_file
, "optimizing double bit test to ");
440 print_generic_expr (dump_file
, name1
);
441 fprintf (dump_file
, " & T == T\nwith temporary T = (1 << ");
442 print_generic_expr (dump_file
, bit1
);
443 fprintf (dump_file
, ") | (1 << ");
444 print_generic_expr (dump_file
, bit2
);
445 fprintf (dump_file
, ")\n");
451 /* See if we have two bit tests of the same name in both tests.
452 In that case remove the outer test and change the inner one to
453 test for name & (bits1 | bits2) != 0. */
454 else if (recognize_bits_test (inner_cond
, &name1
, &bits1
, !inner_inv
)
455 && recognize_bits_test (outer_cond
, &name2
, &bits2
, !outer_inv
))
457 gimple_stmt_iterator gsi
;
460 /* Find the common name which is bit-tested. */
463 else if (bits1
== bits2
)
465 std::swap (name2
, bits2
);
466 std::swap (name1
, bits1
);
468 else if (name1
== bits2
)
469 std::swap (name2
, bits2
);
470 else if (bits1
== name2
)
471 std::swap (name1
, bits1
);
475 /* As we strip non-widening conversions in finding a common
476 name that is tested make sure to end up with an integral
477 type for building the bit operations. */
478 if (TYPE_PRECISION (TREE_TYPE (bits1
))
479 >= TYPE_PRECISION (TREE_TYPE (bits2
)))
481 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
482 name1
= fold_convert (TREE_TYPE (bits1
), name1
);
483 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
484 bits2
= fold_convert (TREE_TYPE (bits1
), bits2
);
488 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
489 name1
= fold_convert (TREE_TYPE (bits2
), name1
);
490 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
491 bits1
= fold_convert (TREE_TYPE (bits2
), bits1
);
495 gsi
= gsi_for_stmt (inner_cond
);
496 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
497 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
498 true, GSI_SAME_STMT
);
499 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
500 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
501 true, GSI_SAME_STMT
);
502 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
, boolean_type_node
, t
,
503 build_int_cst (TREE_TYPE (t
), 0));
504 t
= canonicalize_cond_expr_cond (t
);
507 gimple_cond_set_condition_from_tree (inner_cond
, t
);
508 update_stmt (inner_cond
);
510 /* Leave CFG optimization to cfg_cleanup. */
511 gimple_cond_set_condition_from_tree (outer_cond
,
512 outer_inv
? boolean_false_node
: boolean_true_node
);
513 update_stmt (outer_cond
);
514 update_profile_after_ifcombine (inner_cond_bb
, outer_cond_bb
);
518 fprintf (dump_file
, "optimizing bits or bits test to ");
519 print_generic_expr (dump_file
, name1
);
520 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
521 print_generic_expr (dump_file
, bits1
);
522 fprintf (dump_file
, " | ");
523 print_generic_expr (dump_file
, bits2
);
524 fprintf (dump_file
, "\n");
530 /* See if we have two comparisons that we can merge into one. */
531 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
532 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
)
535 enum tree_code inner_cond_code
= gimple_cond_code (inner_cond
);
536 enum tree_code outer_cond_code
= gimple_cond_code (outer_cond
);
538 /* Invert comparisons if necessary (and possible). */
540 inner_cond_code
= invert_tree_comparison (inner_cond_code
,
541 HONOR_NANS (gimple_cond_lhs (inner_cond
)));
542 if (inner_cond_code
== ERROR_MARK
)
545 outer_cond_code
= invert_tree_comparison (outer_cond_code
,
546 HONOR_NANS (gimple_cond_lhs (outer_cond
)));
547 if (outer_cond_code
== ERROR_MARK
)
549 /* Don't return false so fast, try maybe_fold_or_comparisons? */
551 if (!(t
= maybe_fold_and_comparisons (inner_cond_code
,
552 gimple_cond_lhs (inner_cond
),
553 gimple_cond_rhs (inner_cond
),
555 gimple_cond_lhs (outer_cond
),
556 gimple_cond_rhs (outer_cond
))))
559 gimple_stmt_iterator gsi
;
560 if (!LOGICAL_OP_NON_SHORT_CIRCUIT
|| flag_sanitize_coverage
)
562 /* Only do this optimization if the inner bb contains only the conditional. */
563 if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb
)))
565 t1
= fold_build2_loc (gimple_location (inner_cond
),
568 gimple_cond_lhs (inner_cond
),
569 gimple_cond_rhs (inner_cond
));
570 t2
= fold_build2_loc (gimple_location (outer_cond
),
573 gimple_cond_lhs (outer_cond
),
574 gimple_cond_rhs (outer_cond
));
575 t
= fold_build2_loc (gimple_location (inner_cond
),
576 TRUTH_AND_EXPR
, boolean_type_node
, t1
, t2
);
579 t
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (t
), t
);
582 gsi
= gsi_for_stmt (inner_cond
);
583 t
= force_gimple_operand_gsi_1 (&gsi
, t
, is_gimple_condexpr
, NULL
, true,
587 t
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (t
), t
);
588 t
= canonicalize_cond_expr_cond (t
);
591 gimple_cond_set_condition_from_tree (inner_cond
, t
);
592 update_stmt (inner_cond
);
594 /* Leave CFG optimization to cfg_cleanup. */
595 gimple_cond_set_condition_from_tree (outer_cond
,
596 outer_inv
? boolean_false_node
: boolean_true_node
);
597 update_stmt (outer_cond
);
598 update_profile_after_ifcombine (inner_cond_bb
, outer_cond_bb
);
602 fprintf (dump_file
, "optimizing two comparisons to ");
603 print_generic_expr (dump_file
, t
);
604 fprintf (dump_file
, "\n");
613 /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
614 dispatch to the appropriate if-conversion helper for a particular
615 set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
616 PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */
619 tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb
, basic_block outer_cond_bb
,
620 basic_block then_bb
, basic_block else_bb
,
621 basic_block phi_pred_bb
)
623 /* The && form is characterized by a common else_bb with
624 the two edges leading to it mergable. The latter is
625 guaranteed by matching PHI arguments in the else_bb and
626 the inner cond_bb having no side-effects. */
627 if (phi_pred_bb
!= else_bb
628 && recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
629 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, else_bb
))
633 if (q) goto inner_cond_bb; else goto else_bb;
635 if (p) goto ...; else goto else_bb;
640 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, false,
644 /* And a version where the outer condition is negated. */
645 if (phi_pred_bb
!= else_bb
646 && recognize_if_then_else (outer_cond_bb
, &else_bb
, &inner_cond_bb
)
647 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, else_bb
))
651 if (q) goto else_bb; else goto inner_cond_bb;
653 if (p) goto ...; else goto else_bb;
658 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, true,
662 /* The || form is characterized by a common then_bb with the
663 two edges leading to it mergable. The latter is guaranteed
664 by matching PHI arguments in the then_bb and the inner cond_bb
665 having no side-effects. */
666 if (phi_pred_bb
!= then_bb
667 && recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
668 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, then_bb
))
672 if (q) goto then_bb; else goto inner_cond_bb;
674 if (q) goto then_bb; else goto ...;
678 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, true,
682 /* And a version where the outer condition is negated. */
683 if (phi_pred_bb
!= then_bb
684 && recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &then_bb
)
685 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, then_bb
))
689 if (q) goto inner_cond_bb; else goto then_bb;
691 if (q) goto then_bb; else goto ...;
695 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, false,
702 /* Recognize a CFG pattern and dispatch to the appropriate
703 if-conversion helper. We start with BB as the innermost
704 worker basic-block. Returns true if a transformation was done. */
707 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
709 basic_block then_bb
= NULL
, else_bb
= NULL
;
711 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
714 /* Recognize && and || of two conditions with a common
715 then/else block which entry edges we can merge. That is:
721 This requires a single predecessor of the inner cond_bb. */
722 if (single_pred_p (inner_cond_bb
)
723 && bb_no_side_effects_p (inner_cond_bb
))
725 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
727 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb
, outer_cond_bb
,
728 then_bb
, else_bb
, inner_cond_bb
))
731 if (forwarder_block_to (else_bb
, then_bb
))
733 /* Other possibilities for the && form, if else_bb is
734 empty forwarder block to then_bb. Compared to the above simpler
735 forms this can be treated as if then_bb and else_bb were swapped,
736 and the corresponding inner_cond_bb not inverted because of that.
737 For same_phi_args_p we look at equality of arguments between
738 edge from outer_cond_bb and the forwarder block. */
739 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb
, outer_cond_bb
, else_bb
,
743 else if (forwarder_block_to (then_bb
, else_bb
))
745 /* Other possibilities for the || form, if then_bb is
746 empty forwarder block to else_bb. Compared to the above simpler
747 forms this can be treated as if then_bb and else_bb were swapped,
748 and the corresponding inner_cond_bb not inverted because of that.
749 For same_phi_args_p we look at equality of arguments between
750 edge from outer_cond_bb and the forwarder block. */
751 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb
, outer_cond_bb
, else_bb
,
760 /* Main entry for the tree if-conversion pass. */
764 const pass_data pass_data_tree_ifcombine
=
766 GIMPLE_PASS
, /* type */
767 "ifcombine", /* name */
768 OPTGROUP_NONE
, /* optinfo_flags */
769 TV_TREE_IFCOMBINE
, /* tv_id */
770 ( PROP_cfg
| PROP_ssa
), /* properties_required */
771 0, /* properties_provided */
772 0, /* properties_destroyed */
773 0, /* todo_flags_start */
774 TODO_update_ssa
, /* todo_flags_finish */
777 class pass_tree_ifcombine
: public gimple_opt_pass
780 pass_tree_ifcombine (gcc::context
*ctxt
)
781 : gimple_opt_pass (pass_data_tree_ifcombine
, ctxt
)
784 /* opt_pass methods: */
785 virtual unsigned int execute (function
*);
787 }; // class pass_tree_ifcombine
790 pass_tree_ifcombine::execute (function
*fun
)
793 bool cfg_changed
= false;
796 bbs
= single_pred_before_succ_order ();
797 calculate_dominance_info (CDI_DOMINATORS
);
799 /* Search every basic block for COND_EXPR we may be able to optimize.
801 We walk the blocks in order that guarantees that a block with
802 a single predecessor is processed after the predecessor.
803 This ensures that we collapse outter ifs before visiting the
804 inner ones, and also that we do not try to visit a removed
805 block. This is opposite of PHI-OPT, because we cascade the
806 combining rather than cascading PHIs. */
807 for (i
= n_basic_blocks_for_fn (fun
) - NUM_FIXED_BLOCKS
- 1; i
>= 0; i
--)
809 basic_block bb
= bbs
[i
];
810 gimple
*stmt
= last_stmt (bb
);
813 && gimple_code (stmt
) == GIMPLE_COND
)
814 if (tree_ssa_ifcombine_bb (bb
))
816 /* Clear range info from all stmts in BB which is now executed
817 conditional on a always true/false condition. */
818 reset_flow_sensitive_info_in_bb (bb
);
825 return cfg_changed
? TODO_cleanup_cfg
: 0;
831 make_pass_tree_ifcombine (gcc::context
*ctxt
)
833 return new pass_tree_ifcombine (ctxt
);