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)
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"
25 /* rtl is needed only because arm back-end requires it for
30 #include "stor-layout.h"
31 #include "basic-block.h"
32 #include "tree-pretty-print.h"
33 #include "tree-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-fold.h"
36 #include "gimple-expr.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "gimple-ssa.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
45 #include "tree-pass.h"
47 #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
48 #define LOGICAL_OP_NON_SHORT_CIRCUIT \
49 (BRANCH_COST (optimize_function_for_speed_p (cfun), \
53 /* This pass combines COND_EXPRs to simplify control flow. It
54 currently recognizes bit tests and comparisons in chains that
55 represent logical and or logical or of two COND_EXPRs.
57 It does so by walking basic blocks in a approximate reverse
58 post-dominator order and trying to match CFG patterns that
59 represent logical and or logical or of two COND_EXPRs.
60 Transformations are done if the COND_EXPR conditions match
63 1. two single bit tests X & (1 << Yn) (for logical and)
65 2. two bit tests X & Yn (for logical or)
67 3. two comparisons X OPn Y (for logical or)
69 To simplify this pass, removing basic blocks and dead code
70 is left to CFG cleanup and DCE. */
73 /* Recognize a if-then-else CFG pattern starting to match with the
74 COND_BB basic-block containing the COND_EXPR. The recognized
75 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
76 *THEN_BB and/or *ELSE_BB are already set, they are required to
77 match the then and else basic-blocks to make the pattern match.
78 Returns true if the pattern matched, false otherwise. */
81 recognize_if_then_else (basic_block cond_bb
,
82 basic_block
*then_bb
, basic_block
*else_bb
)
86 if (EDGE_COUNT (cond_bb
->succs
) != 2)
89 /* Find the then/else edges. */
90 t
= EDGE_SUCC (cond_bb
, 0);
91 e
= EDGE_SUCC (cond_bb
, 1);
92 if (!(t
->flags
& EDGE_TRUE_VALUE
))
98 if (!(t
->flags
& EDGE_TRUE_VALUE
)
99 || !(e
->flags
& EDGE_FALSE_VALUE
))
102 /* Check if the edge destinations point to the required block. */
104 && t
->dest
!= *then_bb
)
107 && e
->dest
!= *else_bb
)
118 /* Verify if the basic block BB does not have side-effects. Return
119 true in this case, else false. */
122 bb_no_side_effects_p (basic_block bb
)
124 gimple_stmt_iterator gsi
;
126 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
128 gimple stmt
= gsi_stmt (gsi
);
130 if (gimple_has_side_effects (stmt
)
131 || gimple_vuse (stmt
))
138 /* Return true if BB is an empty forwarder block to TO_BB. */
141 forwarder_block_to (basic_block bb
, basic_block to_bb
)
143 return empty_block_p (bb
)
144 && single_succ_p (bb
)
145 && single_succ (bb
) == to_bb
;
148 /* Verify if all PHI node arguments in DEST for edges from BB1 or
149 BB2 to DEST are the same. This makes the CFG merge point
150 free from side-effects. Return true in this case, else false. */
153 same_phi_args_p (basic_block bb1
, basic_block bb2
, basic_block dest
)
155 edge e1
= find_edge (bb1
, dest
);
156 edge e2
= find_edge (bb2
, dest
);
157 gimple_stmt_iterator gsi
;
160 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
162 phi
= gsi_stmt (gsi
);
163 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi
, e1
),
164 PHI_ARG_DEF_FROM_EDGE (phi
, e2
), 0))
171 /* Return the best representative SSA name for CANDIDATE which is used
175 get_name_for_bit_test (tree candidate
)
177 /* Skip single-use names in favor of using the name from a
178 non-widening conversion definition. */
179 if (TREE_CODE (candidate
) == SSA_NAME
180 && has_single_use (candidate
))
182 gimple def_stmt
= SSA_NAME_DEF_STMT (candidate
);
183 if (is_gimple_assign (def_stmt
)
184 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
186 if (TYPE_PRECISION (TREE_TYPE (candidate
))
187 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
188 return gimple_assign_rhs1 (def_stmt
);
195 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
196 statements. Store the name being tested in *NAME and the bit
197 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
198 Returns true if the pattern matched, false otherwise. */
201 recognize_single_bit_test (gimple cond
, tree
*name
, tree
*bit
, bool inv
)
205 /* Get at the definition of the result of the bit test. */
206 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
207 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
208 || !integer_zerop (gimple_cond_rhs (cond
)))
210 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
211 if (!is_gimple_assign (stmt
))
214 /* Look at which bit is tested. One form to recognize is
215 D.1985_5 = state_3(D) >> control1_4(D);
216 D.1986_6 = (int) D.1985_5;
218 if (D.1987_7 != 0) */
219 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
220 && integer_onep (gimple_assign_rhs2 (stmt
))
221 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
223 tree orig_name
= gimple_assign_rhs1 (stmt
);
225 /* Look through copies and conversions to eventually
226 find the stmt that computes the shift. */
227 stmt
= SSA_NAME_DEF_STMT (orig_name
);
229 while (is_gimple_assign (stmt
)
230 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
231 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt
)))
232 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
233 || gimple_assign_ssa_name_copy_p (stmt
)))
234 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
236 /* If we found such, decompose it. */
237 if (is_gimple_assign (stmt
)
238 && gimple_assign_rhs_code (stmt
) == RSHIFT_EXPR
)
240 /* op0 & (1 << op1) */
241 *bit
= gimple_assign_rhs2 (stmt
);
242 *name
= gimple_assign_rhs1 (stmt
);
247 *bit
= integer_zero_node
;
248 *name
= get_name_for_bit_test (orig_name
);
255 D.1987_7 = op0 & (1 << CST)
256 if (D.1987_7 != 0) */
257 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
258 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
259 && integer_pow2p (gimple_assign_rhs2 (stmt
)))
261 *name
= gimple_assign_rhs1 (stmt
);
262 *bit
= build_int_cst (integer_type_node
,
263 tree_log2 (gimple_assign_rhs2 (stmt
)));
268 D.1986_6 = 1 << control1_4(D)
269 D.1987_7 = op0 & D.1986_6
270 if (D.1987_7 != 0) */
271 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
272 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
273 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
)
277 /* Both arguments of the BIT_AND_EXPR can be the single-bit
278 specifying expression. */
279 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
280 if (is_gimple_assign (tmp
)
281 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
282 && integer_onep (gimple_assign_rhs1 (tmp
)))
284 *name
= gimple_assign_rhs2 (stmt
);
285 *bit
= gimple_assign_rhs2 (tmp
);
289 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
290 if (is_gimple_assign (tmp
)
291 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
292 && integer_onep (gimple_assign_rhs1 (tmp
)))
294 *name
= gimple_assign_rhs1 (stmt
);
295 *bit
= gimple_assign_rhs2 (tmp
);
303 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
304 statements. Store the name being tested in *NAME and the bits
305 in *BITS. The COND_EXPR computes *NAME & *BITS.
306 Returns true if the pattern matched, false otherwise. */
309 recognize_bits_test (gimple cond
, tree
*name
, tree
*bits
, bool inv
)
313 /* Get at the definition of the result of the bit test. */
314 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
315 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
316 || !integer_zerop (gimple_cond_rhs (cond
)))
318 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
319 if (!is_gimple_assign (stmt
)
320 || gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
)
323 *name
= get_name_for_bit_test (gimple_assign_rhs1 (stmt
));
324 *bits
= gimple_assign_rhs2 (stmt
);
329 /* If-convert on a and pattern with a common else block. The inner
330 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
331 inner_inv, outer_inv and result_inv indicate whether the conditions
333 Returns true if the edges to the common else basic-block were merged. */
336 ifcombine_ifandif (basic_block inner_cond_bb
, bool inner_inv
,
337 basic_block outer_cond_bb
, bool outer_inv
, bool result_inv
)
339 gimple_stmt_iterator gsi
;
340 gimple inner_cond
, outer_cond
;
341 tree name1
, name2
, bit1
, bit2
, bits1
, bits2
;
343 inner_cond
= last_stmt (inner_cond_bb
);
345 || gimple_code (inner_cond
) != GIMPLE_COND
)
348 outer_cond
= last_stmt (outer_cond_bb
);
350 || gimple_code (outer_cond
) != GIMPLE_COND
)
353 /* See if we test a single bit of the same name in both tests. In
354 that case remove the outer test, merging both else edges,
355 and change the inner one to test for
356 name & (bit1 | bit2) == (bit1 | bit2). */
357 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
, inner_inv
)
358 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
, outer_inv
)
364 gsi
= gsi_for_stmt (inner_cond
);
365 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
366 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
367 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
368 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
369 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
370 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
371 true, GSI_SAME_STMT
);
372 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
373 t2
= force_gimple_operand_gsi (&gsi
, t2
, true, NULL_TREE
,
374 true, GSI_SAME_STMT
);
375 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
,
376 boolean_type_node
, t2
, t
);
377 t
= canonicalize_cond_expr_cond (t
);
380 gimple_cond_set_condition_from_tree (inner_cond
, t
);
381 update_stmt (inner_cond
);
383 /* Leave CFG optimization to cfg_cleanup. */
384 gimple_cond_set_condition_from_tree (outer_cond
,
385 outer_inv
? boolean_false_node
: boolean_true_node
);
386 update_stmt (outer_cond
);
390 fprintf (dump_file
, "optimizing double bit test to ");
391 print_generic_expr (dump_file
, name1
, 0);
392 fprintf (dump_file
, " & T == T\nwith temporary T = (1 << ");
393 print_generic_expr (dump_file
, bit1
, 0);
394 fprintf (dump_file
, ") | (1 << ");
395 print_generic_expr (dump_file
, bit2
, 0);
396 fprintf (dump_file
, ")\n");
402 /* See if we have two bit tests of the same name in both tests.
403 In that case remove the outer test and change the inner one to
404 test for name & (bits1 | bits2) != 0. */
405 else if (recognize_bits_test (inner_cond
, &name1
, &bits1
, !inner_inv
)
406 && recognize_bits_test (outer_cond
, &name2
, &bits2
, !outer_inv
))
408 gimple_stmt_iterator gsi
;
411 /* Find the common name which is bit-tested. */
414 else if (bits1
== bits2
)
423 else if (name1
== bits2
)
429 else if (bits1
== name2
)
438 /* As we strip non-widening conversions in finding a common
439 name that is tested make sure to end up with an integral
440 type for building the bit operations. */
441 if (TYPE_PRECISION (TREE_TYPE (bits1
))
442 >= TYPE_PRECISION (TREE_TYPE (bits2
)))
444 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
445 name1
= fold_convert (TREE_TYPE (bits1
), name1
);
446 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
447 bits2
= fold_convert (TREE_TYPE (bits1
), bits2
);
451 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
452 name1
= fold_convert (TREE_TYPE (bits2
), name1
);
453 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
454 bits1
= fold_convert (TREE_TYPE (bits2
), bits1
);
458 gsi
= gsi_for_stmt (inner_cond
);
459 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
460 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
461 true, GSI_SAME_STMT
);
462 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
463 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
464 true, GSI_SAME_STMT
);
465 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
, boolean_type_node
, t
,
466 build_int_cst (TREE_TYPE (t
), 0));
467 t
= canonicalize_cond_expr_cond (t
);
470 gimple_cond_set_condition_from_tree (inner_cond
, t
);
471 update_stmt (inner_cond
);
473 /* Leave CFG optimization to cfg_cleanup. */
474 gimple_cond_set_condition_from_tree (outer_cond
,
475 outer_inv
? boolean_false_node
: boolean_true_node
);
476 update_stmt (outer_cond
);
480 fprintf (dump_file
, "optimizing bits or bits test to ");
481 print_generic_expr (dump_file
, name1
, 0);
482 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
483 print_generic_expr (dump_file
, bits1
, 0);
484 fprintf (dump_file
, " | ");
485 print_generic_expr (dump_file
, bits2
, 0);
486 fprintf (dump_file
, "\n");
492 /* See if we have two comparisons that we can merge into one. */
493 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
494 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
)
497 enum tree_code inner_cond_code
= gimple_cond_code (inner_cond
);
498 enum tree_code outer_cond_code
= gimple_cond_code (outer_cond
);
500 /* Invert comparisons if necessary (and possible). */
502 inner_cond_code
= invert_tree_comparison (inner_cond_code
,
503 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond
)))));
504 if (inner_cond_code
== ERROR_MARK
)
507 outer_cond_code
= invert_tree_comparison (outer_cond_code
,
508 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond
)))));
509 if (outer_cond_code
== ERROR_MARK
)
511 /* Don't return false so fast, try maybe_fold_or_comparisons? */
513 if (!(t
= maybe_fold_and_comparisons (inner_cond_code
,
514 gimple_cond_lhs (inner_cond
),
515 gimple_cond_rhs (inner_cond
),
517 gimple_cond_lhs (outer_cond
),
518 gimple_cond_rhs (outer_cond
))))
521 gimple_stmt_iterator gsi
;
522 if (!LOGICAL_OP_NON_SHORT_CIRCUIT
)
524 /* Only do this optimization if the inner bb contains only the conditional. */
525 if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb
)))
527 t1
= fold_build2_loc (gimple_location (inner_cond
),
530 gimple_cond_lhs (inner_cond
),
531 gimple_cond_rhs (inner_cond
));
532 t2
= fold_build2_loc (gimple_location (outer_cond
),
535 gimple_cond_lhs (outer_cond
),
536 gimple_cond_rhs (outer_cond
));
537 t
= fold_build2_loc (gimple_location (inner_cond
),
538 TRUTH_AND_EXPR
, boolean_type_node
, t1
, t2
);
541 t
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (t
), t
);
544 gsi
= gsi_for_stmt (inner_cond
);
545 t
= force_gimple_operand_gsi_1 (&gsi
, t
, is_gimple_condexpr
, NULL
, true,
549 t
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (t
), t
);
550 t
= canonicalize_cond_expr_cond (t
);
553 gimple_cond_set_condition_from_tree (inner_cond
, t
);
554 update_stmt (inner_cond
);
556 /* Leave CFG optimization to cfg_cleanup. */
557 gimple_cond_set_condition_from_tree (outer_cond
,
558 outer_inv
? boolean_false_node
: boolean_true_node
);
559 update_stmt (outer_cond
);
563 fprintf (dump_file
, "optimizing two comparisons to ");
564 print_generic_expr (dump_file
, t
, 0);
565 fprintf (dump_file
, "\n");
574 /* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
575 dispatch to the appropriate if-conversion helper for a particular
576 set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
577 PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */
580 tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb
, basic_block outer_cond_bb
,
581 basic_block then_bb
, basic_block else_bb
,
582 basic_block phi_pred_bb
)
584 /* The && form is characterized by a common else_bb with
585 the two edges leading to it mergable. The latter is
586 guaranteed by matching PHI arguments in the else_bb and
587 the inner cond_bb having no side-effects. */
588 if (phi_pred_bb
!= else_bb
589 && recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
590 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, else_bb
)
591 && bb_no_side_effects_p (inner_cond_bb
))
595 if (q) goto inner_cond_bb; else goto else_bb;
597 if (p) goto ...; else goto else_bb;
602 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, false,
606 /* And a version where the outer condition is negated. */
607 if (phi_pred_bb
!= else_bb
608 && recognize_if_then_else (outer_cond_bb
, &else_bb
, &inner_cond_bb
)
609 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, else_bb
)
610 && bb_no_side_effects_p (inner_cond_bb
))
614 if (q) goto else_bb; else goto inner_cond_bb;
616 if (p) goto ...; else goto else_bb;
621 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, true,
625 /* The || form is characterized by a common then_bb with the
626 two edges leading to it mergable. The latter is guaranteed
627 by matching PHI arguments in the then_bb and the inner cond_bb
628 having no side-effects. */
629 if (phi_pred_bb
!= then_bb
630 && recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
631 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, then_bb
)
632 && bb_no_side_effects_p (inner_cond_bb
))
636 if (q) goto then_bb; else goto inner_cond_bb;
638 if (q) goto then_bb; else goto ...;
642 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, true,
646 /* And a version where the outer condition is negated. */
647 if (phi_pred_bb
!= then_bb
648 && recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &then_bb
)
649 && same_phi_args_p (outer_cond_bb
, phi_pred_bb
, then_bb
)
650 && bb_no_side_effects_p (inner_cond_bb
))
654 if (q) goto inner_cond_bb; else goto then_bb;
656 if (q) goto then_bb; else goto ...;
660 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, false,
667 /* Recognize a CFG pattern and dispatch to the appropriate
668 if-conversion helper. We start with BB as the innermost
669 worker basic-block. Returns true if a transformation was done. */
672 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
674 basic_block then_bb
= NULL
, else_bb
= NULL
;
676 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
679 /* Recognize && and || of two conditions with a common
680 then/else block which entry edges we can merge. That is:
686 This requires a single predecessor of the inner cond_bb. */
687 if (single_pred_p (inner_cond_bb
))
689 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
691 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb
, outer_cond_bb
,
692 then_bb
, else_bb
, inner_cond_bb
))
695 if (forwarder_block_to (else_bb
, then_bb
))
697 /* Other possibilities for the && form, if else_bb is
698 empty forwarder block to then_bb. Compared to the above simpler
699 forms this can be treated as if then_bb and else_bb were swapped,
700 and the corresponding inner_cond_bb not inverted because of that.
701 For same_phi_args_p we look at equality of arguments between
702 edge from outer_cond_bb and the forwarder block. */
703 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb
, outer_cond_bb
, else_bb
,
707 else if (forwarder_block_to (then_bb
, else_bb
))
709 /* Other possibilities for the || form, if then_bb is
710 empty forwarder block to else_bb. Compared to the above simpler
711 forms this can be treated as if then_bb and else_bb were swapped,
712 and the corresponding inner_cond_bb not inverted because of that.
713 For same_phi_args_p we look at equality of arguments between
714 edge from outer_cond_bb and the forwarder block. */
715 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb
, outer_cond_bb
, else_bb
,
724 /* Main entry for the tree if-conversion pass. */
727 tree_ssa_ifcombine (void)
730 bool cfg_changed
= false;
733 bbs
= single_pred_before_succ_order ();
734 calculate_dominance_info (CDI_DOMINATORS
);
736 /* Search every basic block for COND_EXPR we may be able to optimize.
738 We walk the blocks in order that guarantees that a block with
739 a single predecessor is processed after the predecessor.
740 This ensures that we collapse outter ifs before visiting the
741 inner ones, and also that we do not try to visit a removed
742 block. This is opposite of PHI-OPT, because we cascade the
743 combining rather than cascading PHIs. */
744 for (i
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
- 1; i
>= 0; i
--)
746 basic_block bb
= bbs
[i
];
747 gimple stmt
= last_stmt (bb
);
750 && gimple_code (stmt
) == GIMPLE_COND
)
751 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
756 return cfg_changed
? TODO_cleanup_cfg
: 0;
760 gate_ifcombine (void)
767 const pass_data pass_data_tree_ifcombine
=
769 GIMPLE_PASS
, /* type */
770 "ifcombine", /* name */
771 OPTGROUP_NONE
, /* optinfo_flags */
773 true, /* has_execute */
774 TV_TREE_IFCOMBINE
, /* tv_id */
775 ( PROP_cfg
| PROP_ssa
), /* properties_required */
776 0, /* properties_provided */
777 0, /* properties_destroyed */
778 0, /* todo_flags_start */
779 ( TODO_update_ssa
| TODO_verify_ssa
), /* todo_flags_finish */
782 class pass_tree_ifcombine
: public gimple_opt_pass
785 pass_tree_ifcombine (gcc::context
*ctxt
)
786 : gimple_opt_pass (pass_data_tree_ifcombine
, ctxt
)
789 /* opt_pass methods: */
790 bool gate () { return gate_ifcombine (); }
791 unsigned int execute () { return tree_ssa_ifcombine (); }
793 }; // class pass_tree_ifcombine
798 make_pass_tree_ifcombine (gcc::context
*ctxt
)
800 return new pass_tree_ifcombine (ctxt
);