1 /* Combining of if-expressions on trees.
2 Copyright (C) 2007-2013 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"
26 #include "basic-block.h"
27 #include "tree-pretty-print.h"
28 #include "tree-flow.h"
29 #include "tree-pass.h"
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.
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
41 1. two single bit tests X & (1 << Yn) (for logical and)
43 2. two bit tests X & Yn (for logical or)
45 3. two comparisons X OPn Y (for logical or)
47 To simplify this pass, removing basic blocks and dead code
48 is left to CFG cleanup and DCE. */
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. */
59 recognize_if_then_else (basic_block cond_bb
,
60 basic_block
*then_bb
, basic_block
*else_bb
)
64 if (EDGE_COUNT (cond_bb
->succs
) != 2)
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
))
76 if (!(t
->flags
& EDGE_TRUE_VALUE
)
77 || !(e
->flags
& EDGE_FALSE_VALUE
))
80 /* Check if the edge destinations point to the required block. */
82 && t
->dest
!= *then_bb
)
85 && e
->dest
!= *else_bb
)
96 /* Verify if the basic block BB does not have side-effects. Return
97 true in this case, else false. */
100 bb_no_side_effects_p (basic_block bb
)
102 gimple_stmt_iterator gsi
;
104 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
106 gimple stmt
= gsi_stmt (gsi
);
108 if (is_gimple_debug (stmt
))
111 if (gimple_has_side_effects (stmt
)
112 || gimple_could_trap_p (stmt
)
113 || gimple_vuse (stmt
))
120 /* Verify if all PHI node arguments in DEST for edges from BB1 or
121 BB2 to DEST are the same. This makes the CFG merge point
122 free from side-effects. Return true in this case, else false. */
125 same_phi_args_p (basic_block bb1
, basic_block bb2
, basic_block dest
)
127 edge e1
= find_edge (bb1
, dest
);
128 edge e2
= find_edge (bb2
, dest
);
129 gimple_stmt_iterator gsi
;
132 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
134 phi
= gsi_stmt (gsi
);
135 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi
, e1
),
136 PHI_ARG_DEF_FROM_EDGE (phi
, e2
), 0))
143 /* Return the best representative SSA name for CANDIDATE which is used
147 get_name_for_bit_test (tree candidate
)
149 /* Skip single-use names in favor of using the name from a
150 non-widening conversion definition. */
151 if (TREE_CODE (candidate
) == SSA_NAME
152 && has_single_use (candidate
))
154 gimple def_stmt
= SSA_NAME_DEF_STMT (candidate
);
155 if (is_gimple_assign (def_stmt
)
156 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
158 if (TYPE_PRECISION (TREE_TYPE (candidate
))
159 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
160 return gimple_assign_rhs1 (def_stmt
);
167 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
168 statements. Store the name being tested in *NAME and the bit
169 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
170 Returns true if the pattern matched, false otherwise. */
173 recognize_single_bit_test (gimple cond
, tree
*name
, tree
*bit
, bool inv
)
177 /* Get at the definition of the result of the bit test. */
178 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
179 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
180 || !integer_zerop (gimple_cond_rhs (cond
)))
182 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
183 if (!is_gimple_assign (stmt
))
186 /* Look at which bit is tested. One form to recognize is
187 D.1985_5 = state_3(D) >> control1_4(D);
188 D.1986_6 = (int) D.1985_5;
190 if (D.1987_7 != 0) */
191 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
192 && integer_onep (gimple_assign_rhs2 (stmt
))
193 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
195 tree orig_name
= gimple_assign_rhs1 (stmt
);
197 /* Look through copies and conversions to eventually
198 find the stmt that computes the shift. */
199 stmt
= SSA_NAME_DEF_STMT (orig_name
);
201 while (is_gimple_assign (stmt
)
202 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
203 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt
)))
204 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt
))))
205 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
206 || gimple_assign_ssa_name_copy_p (stmt
)))
207 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
209 /* If we found such, decompose it. */
210 if (is_gimple_assign (stmt
)
211 && gimple_assign_rhs_code (stmt
) == RSHIFT_EXPR
)
213 /* op0 & (1 << op1) */
214 *bit
= gimple_assign_rhs2 (stmt
);
215 *name
= gimple_assign_rhs1 (stmt
);
220 *bit
= integer_zero_node
;
221 *name
= get_name_for_bit_test (orig_name
);
228 D.1987_7 = op0 & (1 << CST)
229 if (D.1987_7 != 0) */
230 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
231 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
232 && integer_pow2p (gimple_assign_rhs2 (stmt
)))
234 *name
= gimple_assign_rhs1 (stmt
);
235 *bit
= build_int_cst (integer_type_node
,
236 tree_log2 (gimple_assign_rhs2 (stmt
)));
241 D.1986_6 = 1 << control1_4(D)
242 D.1987_7 = op0 & D.1986_6
243 if (D.1987_7 != 0) */
244 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
245 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
246 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
)
250 /* Both arguments of the BIT_AND_EXPR can be the single-bit
251 specifying expression. */
252 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
253 if (is_gimple_assign (tmp
)
254 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
255 && integer_onep (gimple_assign_rhs1 (tmp
)))
257 *name
= gimple_assign_rhs2 (stmt
);
258 *bit
= gimple_assign_rhs2 (tmp
);
262 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
263 if (is_gimple_assign (tmp
)
264 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
265 && integer_onep (gimple_assign_rhs1 (tmp
)))
267 *name
= gimple_assign_rhs1 (stmt
);
268 *bit
= gimple_assign_rhs2 (tmp
);
276 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
277 statements. Store the name being tested in *NAME and the bits
278 in *BITS. The COND_EXPR computes *NAME & *BITS.
279 Returns true if the pattern matched, false otherwise. */
282 recognize_bits_test (gimple cond
, tree
*name
, tree
*bits
, bool inv
)
286 /* Get at the definition of the result of the bit test. */
287 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
288 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
289 || !integer_zerop (gimple_cond_rhs (cond
)))
291 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
292 if (!is_gimple_assign (stmt
)
293 || gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
)
296 *name
= get_name_for_bit_test (gimple_assign_rhs1 (stmt
));
297 *bits
= gimple_assign_rhs2 (stmt
);
302 /* If-convert on a and pattern with a common else block. The inner
303 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
304 inner_inv, outer_inv and result_inv indicate whether the conditions
306 Returns true if the edges to the common else basic-block were merged. */
309 ifcombine_ifandif (basic_block inner_cond_bb
, bool inner_inv
,
310 basic_block outer_cond_bb
, bool outer_inv
, bool result_inv
)
312 gimple_stmt_iterator gsi
;
313 gimple inner_cond
, outer_cond
;
314 tree name1
, name2
, bit1
, bit2
, bits1
, bits2
;
316 inner_cond
= last_stmt (inner_cond_bb
);
318 || gimple_code (inner_cond
) != GIMPLE_COND
)
321 outer_cond
= last_stmt (outer_cond_bb
);
323 || gimple_code (outer_cond
) != GIMPLE_COND
)
326 /* See if we test a single bit of the same name in both tests. In
327 that case remove the outer test, merging both else edges,
328 and change the inner one to test for
329 name & (bit1 | bit2) == (bit1 | bit2). */
330 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
, inner_inv
)
331 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
, outer_inv
)
337 gsi
= gsi_for_stmt (inner_cond
);
338 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
339 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
340 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
341 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
342 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
343 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
344 true, GSI_SAME_STMT
);
345 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
346 t2
= force_gimple_operand_gsi (&gsi
, t2
, true, NULL_TREE
,
347 true, GSI_SAME_STMT
);
348 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
,
349 boolean_type_node
, t2
, t
);
350 t
= canonicalize_cond_expr_cond (t
);
353 gimple_cond_set_condition_from_tree (inner_cond
, t
);
354 update_stmt (inner_cond
);
356 /* Leave CFG optimization to cfg_cleanup. */
357 gimple_cond_set_condition_from_tree (outer_cond
,
358 outer_inv
? boolean_false_node
: boolean_true_node
);
359 update_stmt (outer_cond
);
363 fprintf (dump_file
, "optimizing double bit test to ");
364 print_generic_expr (dump_file
, name1
, 0);
365 fprintf (dump_file
, " & T == T\nwith temporary T = (1 << ");
366 print_generic_expr (dump_file
, bit1
, 0);
367 fprintf (dump_file
, ") | (1 << ");
368 print_generic_expr (dump_file
, bit2
, 0);
369 fprintf (dump_file
, ")\n");
375 /* See if we have two bit tests of the same name in both tests.
376 In that case remove the outer test and change the inner one to
377 test for name & (bits1 | bits2) != 0. */
378 else if (recognize_bits_test (inner_cond
, &name1
, &bits1
, !inner_inv
)
379 && recognize_bits_test (outer_cond
, &name2
, &bits2
, !outer_inv
))
381 gimple_stmt_iterator gsi
;
384 /* Find the common name which is bit-tested. */
387 else if (bits1
== bits2
)
396 else if (name1
== bits2
)
402 else if (bits1
== name2
)
411 /* As we strip non-widening conversions in finding a common
412 name that is tested make sure to end up with an integral
413 type for building the bit operations. */
414 if (TYPE_PRECISION (TREE_TYPE (bits1
))
415 >= TYPE_PRECISION (TREE_TYPE (bits2
)))
417 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
418 name1
= fold_convert (TREE_TYPE (bits1
), name1
);
419 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
420 bits2
= fold_convert (TREE_TYPE (bits1
), bits2
);
424 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
425 name1
= fold_convert (TREE_TYPE (bits2
), name1
);
426 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
427 bits1
= fold_convert (TREE_TYPE (bits2
), bits1
);
431 gsi
= gsi_for_stmt (inner_cond
);
432 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
433 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
434 true, GSI_SAME_STMT
);
435 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
436 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
437 true, GSI_SAME_STMT
);
438 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
, boolean_type_node
, t
,
439 build_int_cst (TREE_TYPE (t
), 0));
440 t
= canonicalize_cond_expr_cond (t
);
443 gimple_cond_set_condition_from_tree (inner_cond
, t
);
444 update_stmt (inner_cond
);
446 /* Leave CFG optimization to cfg_cleanup. */
447 gimple_cond_set_condition_from_tree (outer_cond
,
448 outer_inv
? boolean_false_node
: boolean_true_node
);
449 update_stmt (outer_cond
);
453 fprintf (dump_file
, "optimizing bits or bits test to ");
454 print_generic_expr (dump_file
, name1
, 0);
455 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
456 print_generic_expr (dump_file
, bits1
, 0);
457 fprintf (dump_file
, " | ");
458 print_generic_expr (dump_file
, bits2
, 0);
459 fprintf (dump_file
, "\n");
465 /* See if we have two comparisons that we can merge into one. */
466 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
467 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
)
470 enum tree_code inner_cond_code
= gimple_cond_code (inner_cond
);
471 enum tree_code outer_cond_code
= gimple_cond_code (outer_cond
);
473 /* Invert comparisons if necessary (and possible). */
475 inner_cond_code
= invert_tree_comparison (inner_cond_code
,
476 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond
)))));
477 if (inner_cond_code
== ERROR_MARK
)
480 outer_cond_code
= invert_tree_comparison (outer_cond_code
,
481 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond
)))));
482 if (outer_cond_code
== ERROR_MARK
)
484 /* Don't return false so fast, try maybe_fold_or_comparisons? */
486 if (!(t
= maybe_fold_and_comparisons (inner_cond_code
,
487 gimple_cond_lhs (inner_cond
),
488 gimple_cond_rhs (inner_cond
),
490 gimple_cond_lhs (outer_cond
),
491 gimple_cond_rhs (outer_cond
))))
494 t
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (t
), t
);
495 t
= canonicalize_cond_expr_cond (t
);
498 gimple_cond_set_condition_from_tree (inner_cond
, t
);
499 update_stmt (inner_cond
);
501 /* Leave CFG optimization to cfg_cleanup. */
502 gimple_cond_set_condition_from_tree (outer_cond
,
503 outer_inv
? boolean_false_node
: boolean_true_node
);
504 update_stmt (outer_cond
);
508 fprintf (dump_file
, "optimizing two comparisons to ");
509 print_generic_expr (dump_file
, t
, 0);
510 fprintf (dump_file
, "\n");
519 /* Recognize a CFG pattern and dispatch to the appropriate
520 if-conversion helper. We start with BB as the innermost
521 worker basic-block. Returns true if a transformation was done. */
524 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
526 basic_block then_bb
= NULL
, else_bb
= NULL
;
528 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
531 /* Recognize && and || of two conditions with a common
532 then/else block which entry edges we can merge. That is:
538 This requires a single predecessor of the inner cond_bb. */
539 if (single_pred_p (inner_cond_bb
))
541 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
543 /* The && form is characterized by a common else_bb with
544 the two edges leading to it mergable. The latter is
545 guaranteed by matching PHI arguments in the else_bb and
546 the inner cond_bb having no side-effects. */
547 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
548 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
549 && bb_no_side_effects_p (inner_cond_bb
))
553 if (q) goto inner_cond_bb; else goto else_bb;
555 if (p) goto ...; else goto else_bb;
560 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, false,
564 /* And a version where the outer condition is negated. */
565 if (recognize_if_then_else (outer_cond_bb
, &else_bb
, &inner_cond_bb
)
566 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
567 && bb_no_side_effects_p (inner_cond_bb
))
571 if (q) goto else_bb; else goto inner_cond_bb;
573 if (p) goto ...; else goto else_bb;
578 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, true,
582 /* The || form is characterized by a common then_bb with the
583 two edges leading to it mergable. The latter is guaranteed
584 by matching PHI arguments in the then_bb and the inner cond_bb
585 having no side-effects. */
586 if (recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
587 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
588 && bb_no_side_effects_p (inner_cond_bb
))
592 if (q) goto then_bb; else goto inner_cond_bb;
594 if (q) goto then_bb; else goto ...;
598 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, true,
602 /* And a version where the outer condition is negated. */
603 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &then_bb
)
604 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
605 && bb_no_side_effects_p (inner_cond_bb
))
609 if (q) goto inner_cond_bb; else goto then_bb;
611 if (q) goto then_bb; else goto ...;
615 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, false,
623 /* Main entry for the tree if-conversion pass. */
626 tree_ssa_ifcombine (void)
629 bool cfg_changed
= false;
632 bbs
= blocks_in_phiopt_order ();
633 calculate_dominance_info (CDI_DOMINATORS
);
635 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; ++i
)
637 basic_block bb
= bbs
[i
];
638 gimple stmt
= last_stmt (bb
);
641 && gimple_code (stmt
) == GIMPLE_COND
)
642 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
647 return cfg_changed
? TODO_cleanup_cfg
: 0;
651 gate_ifcombine (void)
656 struct gimple_opt_pass pass_tree_ifcombine
=
660 "ifcombine", /* name */
661 OPTGROUP_NONE
, /* optinfo_flags */
662 gate_ifcombine
, /* gate */
663 tree_ssa_ifcombine
, /* execute */
666 0, /* static_pass_number */
667 TV_TREE_IFCOMBINE
, /* tv_id */
668 PROP_cfg
| PROP_ssa
, /* properties_required */
669 0, /* properties_provided */
670 0, /* properties_destroyed */
671 0, /* todo_flags_start */
674 | TODO_verify_ssa
/* todo_flags_finish */