1 /* Combining of if-expressions on trees.
2 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Richard Guenther <rguenther@suse.de>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
32 /* This pass combines COND_EXPRs to simplify control flow. It
33 currently recognizes bit tests and comparisons in chains that
34 represent logical and or logical or of two COND_EXPRs.
36 It does so by walking basic blocks in a approximate reverse
37 post-dominator order and trying to match CFG patterns that
38 represent logical and or logical or of two COND_EXPRs.
39 Transformations are done if the COND_EXPR conditions match
42 1. two single bit tests X & (1 << Yn) (for logical and)
44 2. two bit tests X & Yn (for logical or)
46 3. two comparisons X OPn Y (for logical or)
48 To simplify this pass, removing basic blocks and dead code
49 is left to CFG cleanup and DCE. */
52 /* Recognize a if-then-else CFG pattern starting to match with the
53 COND_BB basic-block containing the COND_EXPR. The recognized
54 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
55 *THEN_BB and/or *ELSE_BB are already set, they are required to
56 match the then and else basic-blocks to make the pattern match.
57 Returns true if the pattern matched, false otherwise. */
60 recognize_if_then_else (basic_block cond_bb
,
61 basic_block
*then_bb
, basic_block
*else_bb
)
65 if (EDGE_COUNT (cond_bb
->succs
) != 2)
68 /* Find the then/else edges. */
69 t
= EDGE_SUCC (cond_bb
, 0);
70 e
= EDGE_SUCC (cond_bb
, 1);
71 if (!(t
->flags
& EDGE_TRUE_VALUE
))
77 if (!(t
->flags
& EDGE_TRUE_VALUE
)
78 || !(e
->flags
& EDGE_FALSE_VALUE
))
81 /* Check if the edge destinations point to the required block. */
83 && t
->dest
!= *then_bb
)
86 && e
->dest
!= *else_bb
)
97 /* Verify if the basic block BB does not have side-effects. Return
98 true in this case, else false. */
101 bb_no_side_effects_p (basic_block bb
)
103 gimple_stmt_iterator gsi
;
105 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
107 gimple stmt
= gsi_stmt (gsi
);
109 if (gimple_has_side_effects (stmt
)
110 || gimple_vuse (stmt
))
117 /* Verify if all PHI node arguments in DEST for edges from BB1 or
118 BB2 to DEST are the same. This makes the CFG merge point
119 free from side-effects. Return true in this case, else false. */
122 same_phi_args_p (basic_block bb1
, basic_block bb2
, basic_block dest
)
124 edge e1
= find_edge (bb1
, dest
);
125 edge e2
= find_edge (bb2
, dest
);
126 gimple_stmt_iterator gsi
;
129 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
131 phi
= gsi_stmt (gsi
);
132 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi
, e1
),
133 PHI_ARG_DEF_FROM_EDGE (phi
, e2
), 0))
140 /* Return the best representative SSA name for CANDIDATE which is used
144 get_name_for_bit_test (tree candidate
)
146 /* Skip single-use names in favor of using the name from a
147 non-widening conversion definition. */
148 if (TREE_CODE (candidate
) == SSA_NAME
149 && has_single_use (candidate
))
151 gimple def_stmt
= SSA_NAME_DEF_STMT (candidate
);
152 if (is_gimple_assign (def_stmt
)
153 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
155 if (TYPE_PRECISION (TREE_TYPE (candidate
))
156 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
157 return gimple_assign_rhs1 (def_stmt
);
164 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
165 statements. Store the name being tested in *NAME and the bit
166 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
167 Returns true if the pattern matched, false otherwise. */
170 recognize_single_bit_test (gimple cond
, tree
*name
, tree
*bit
, bool inv
)
174 /* Get at the definition of the result of the bit test. */
175 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
176 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
177 || !integer_zerop (gimple_cond_rhs (cond
)))
179 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
180 if (!is_gimple_assign (stmt
))
183 /* Look at which bit is tested. One form to recognize is
184 D.1985_5 = state_3(D) >> control1_4(D);
185 D.1986_6 = (int) D.1985_5;
187 if (D.1987_7 != 0) */
188 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
189 && integer_onep (gimple_assign_rhs2 (stmt
))
190 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
192 tree orig_name
= gimple_assign_rhs1 (stmt
);
194 /* Look through copies and conversions to eventually
195 find the stmt that computes the shift. */
196 stmt
= SSA_NAME_DEF_STMT (orig_name
);
198 while (is_gimple_assign (stmt
)
199 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
200 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt
)))
201 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
202 || gimple_assign_ssa_name_copy_p (stmt
)))
203 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
205 /* If we found such, decompose it. */
206 if (is_gimple_assign (stmt
)
207 && gimple_assign_rhs_code (stmt
) == RSHIFT_EXPR
)
209 /* op0 & (1 << op1) */
210 *bit
= gimple_assign_rhs2 (stmt
);
211 *name
= gimple_assign_rhs1 (stmt
);
216 *bit
= integer_zero_node
;
217 *name
= get_name_for_bit_test (orig_name
);
224 D.1987_7 = op0 & (1 << CST)
225 if (D.1987_7 != 0) */
226 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
227 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
228 && integer_pow2p (gimple_assign_rhs2 (stmt
)))
230 *name
= gimple_assign_rhs1 (stmt
);
231 *bit
= build_int_cst (integer_type_node
,
232 tree_log2 (gimple_assign_rhs2 (stmt
)));
237 D.1986_6 = 1 << control1_4(D)
238 D.1987_7 = op0 & D.1986_6
239 if (D.1987_7 != 0) */
240 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
241 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
242 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
)
246 /* Both arguments of the BIT_AND_EXPR can be the single-bit
247 specifying expression. */
248 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
249 if (is_gimple_assign (tmp
)
250 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
251 && integer_onep (gimple_assign_rhs1 (tmp
)))
253 *name
= gimple_assign_rhs2 (stmt
);
254 *bit
= gimple_assign_rhs2 (tmp
);
258 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
259 if (is_gimple_assign (tmp
)
260 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
261 && integer_onep (gimple_assign_rhs1 (tmp
)))
263 *name
= gimple_assign_rhs1 (stmt
);
264 *bit
= gimple_assign_rhs2 (tmp
);
272 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
273 statements. Store the name being tested in *NAME and the bits
274 in *BITS. The COND_EXPR computes *NAME & *BITS.
275 Returns true if the pattern matched, false otherwise. */
278 recognize_bits_test (gimple cond
, tree
*name
, tree
*bits
, bool inv
)
282 /* Get at the definition of the result of the bit test. */
283 if (gimple_cond_code (cond
) != (inv
? EQ_EXPR
: NE_EXPR
)
284 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
285 || !integer_zerop (gimple_cond_rhs (cond
)))
287 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
288 if (!is_gimple_assign (stmt
)
289 || gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
)
292 *name
= get_name_for_bit_test (gimple_assign_rhs1 (stmt
));
293 *bits
= gimple_assign_rhs2 (stmt
);
298 /* If-convert on a and pattern with a common else block. The inner
299 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
300 inner_inv, outer_inv and result_inv indicate whether the conditions
302 Returns true if the edges to the common else basic-block were merged. */
305 ifcombine_ifandif (basic_block inner_cond_bb
, bool inner_inv
,
306 basic_block outer_cond_bb
, bool outer_inv
, bool result_inv
)
308 gimple_stmt_iterator gsi
;
309 gimple inner_cond
, outer_cond
;
310 tree name1
, name2
, bit1
, bit2
, bits1
, bits2
;
312 inner_cond
= last_stmt (inner_cond_bb
);
314 || gimple_code (inner_cond
) != GIMPLE_COND
)
317 outer_cond
= last_stmt (outer_cond_bb
);
319 || gimple_code (outer_cond
) != GIMPLE_COND
)
322 /* See if we test a single bit of the same name in both tests. In
323 that case remove the outer test, merging both else edges,
324 and change the inner one to test for
325 name & (bit1 | bit2) == (bit1 | bit2). */
326 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
, inner_inv
)
327 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
, outer_inv
)
333 gsi
= gsi_for_stmt (inner_cond
);
334 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
335 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
336 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
337 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
338 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
339 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
340 true, GSI_SAME_STMT
);
341 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
342 t2
= force_gimple_operand_gsi (&gsi
, t2
, true, NULL_TREE
,
343 true, GSI_SAME_STMT
);
344 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
,
345 boolean_type_node
, t2
, t
);
346 t
= canonicalize_cond_expr_cond (t
);
349 gimple_cond_set_condition_from_tree (inner_cond
, t
);
350 update_stmt (inner_cond
);
352 /* Leave CFG optimization to cfg_cleanup. */
353 gimple_cond_set_condition_from_tree (outer_cond
,
354 outer_inv
? boolean_false_node
: boolean_true_node
);
355 update_stmt (outer_cond
);
359 fprintf (dump_file
, "optimizing double bit test to ");
360 print_generic_expr (dump_file
, name1
, 0);
361 fprintf (dump_file
, " & T == T\nwith temporary T = (1 << ");
362 print_generic_expr (dump_file
, bit1
, 0);
363 fprintf (dump_file
, ") | (1 << ");
364 print_generic_expr (dump_file
, bit2
, 0);
365 fprintf (dump_file
, ")\n");
371 /* See if we have two bit tests of the same name in both tests.
372 In that case remove the outer test and change the inner one to
373 test for name & (bits1 | bits2) != 0. */
374 else if (recognize_bits_test (inner_cond
, &name1
, &bits1
, !inner_inv
)
375 && recognize_bits_test (outer_cond
, &name2
, &bits2
, !outer_inv
))
377 gimple_stmt_iterator gsi
;
380 /* Find the common name which is bit-tested. */
383 else if (bits1
== bits2
)
392 else if (name1
== bits2
)
398 else if (bits1
== name2
)
407 /* As we strip non-widening conversions in finding a common
408 name that is tested make sure to end up with an integral
409 type for building the bit operations. */
410 if (TYPE_PRECISION (TREE_TYPE (bits1
))
411 >= TYPE_PRECISION (TREE_TYPE (bits2
)))
413 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
414 name1
= fold_convert (TREE_TYPE (bits1
), name1
);
415 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
416 bits2
= fold_convert (TREE_TYPE (bits1
), bits2
);
420 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
421 name1
= fold_convert (TREE_TYPE (bits2
), name1
);
422 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
423 bits1
= fold_convert (TREE_TYPE (bits2
), bits1
);
427 gsi
= gsi_for_stmt (inner_cond
);
428 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
429 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
430 true, GSI_SAME_STMT
);
431 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
432 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
433 true, GSI_SAME_STMT
);
434 t
= fold_build2 (result_inv
? NE_EXPR
: EQ_EXPR
, boolean_type_node
, t
,
435 build_int_cst (TREE_TYPE (t
), 0));
436 t
= canonicalize_cond_expr_cond (t
);
439 gimple_cond_set_condition_from_tree (inner_cond
, t
);
440 update_stmt (inner_cond
);
442 /* Leave CFG optimization to cfg_cleanup. */
443 gimple_cond_set_condition_from_tree (outer_cond
,
444 outer_inv
? boolean_false_node
: boolean_true_node
);
445 update_stmt (outer_cond
);
449 fprintf (dump_file
, "optimizing bits or bits test to ");
450 print_generic_expr (dump_file
, name1
, 0);
451 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
452 print_generic_expr (dump_file
, bits1
, 0);
453 fprintf (dump_file
, " | ");
454 print_generic_expr (dump_file
, bits2
, 0);
455 fprintf (dump_file
, "\n");
461 /* See if we have two comparisons that we can merge into one. */
462 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
463 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
)
466 enum tree_code inner_cond_code
= gimple_cond_code (inner_cond
);
467 enum tree_code outer_cond_code
= gimple_cond_code (outer_cond
);
469 /* Invert comparisons if necessary (and possible). */
471 inner_cond_code
= invert_tree_comparison (inner_cond_code
,
472 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond
)))));
473 if (inner_cond_code
== ERROR_MARK
)
476 outer_cond_code
= invert_tree_comparison (outer_cond_code
,
477 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond
)))));
478 if (outer_cond_code
== ERROR_MARK
)
480 /* Don't return false so fast, try maybe_fold_or_comparisons? */
482 if (!(t
= maybe_fold_and_comparisons (inner_cond_code
,
483 gimple_cond_lhs (inner_cond
),
484 gimple_cond_rhs (inner_cond
),
486 gimple_cond_lhs (outer_cond
),
487 gimple_cond_rhs (outer_cond
))))
490 t
= fold_build1 (TRUTH_NOT_EXPR
, TREE_TYPE (t
), t
);
491 t
= canonicalize_cond_expr_cond (t
);
494 gimple_cond_set_condition_from_tree (inner_cond
, t
);
495 update_stmt (inner_cond
);
497 /* Leave CFG optimization to cfg_cleanup. */
498 gimple_cond_set_condition_from_tree (outer_cond
,
499 outer_inv
? boolean_false_node
: boolean_true_node
);
500 update_stmt (outer_cond
);
504 fprintf (dump_file
, "optimizing two comparisons to ");
505 print_generic_expr (dump_file
, t
, 0);
506 fprintf (dump_file
, "\n");
515 /* Recognize a CFG pattern and dispatch to the appropriate
516 if-conversion helper. We start with BB as the innermost
517 worker basic-block. Returns true if a transformation was done. */
520 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
522 basic_block then_bb
= NULL
, else_bb
= NULL
;
524 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
527 /* Recognize && and || of two conditions with a common
528 then/else block which entry edges we can merge. That is:
534 This requires a single predecessor of the inner cond_bb. */
535 if (single_pred_p (inner_cond_bb
))
537 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
539 /* The && form is characterized by a common else_bb with
540 the two edges leading to it mergable. The latter is
541 guaranteed by matching PHI arguments in the else_bb and
542 the inner cond_bb having no side-effects. */
543 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
544 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
545 && bb_no_side_effects_p (inner_cond_bb
))
549 if (q) goto inner_cond_bb; else goto else_bb;
551 if (p) goto ...; else goto else_bb;
556 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, false,
560 /* And a version where the outer condition is negated. */
561 if (recognize_if_then_else (outer_cond_bb
, &else_bb
, &inner_cond_bb
)
562 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
563 && bb_no_side_effects_p (inner_cond_bb
))
567 if (q) goto else_bb; else goto inner_cond_bb;
569 if (p) goto ...; else goto else_bb;
574 return ifcombine_ifandif (inner_cond_bb
, false, outer_cond_bb
, true,
578 /* The || form is characterized by a common then_bb with the
579 two edges leading to it mergable. The latter is guaranteed
580 by matching PHI arguments in the then_bb and the inner cond_bb
581 having no side-effects. */
582 if (recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
583 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
584 && bb_no_side_effects_p (inner_cond_bb
))
588 if (q) goto then_bb; else goto inner_cond_bb;
590 if (q) goto then_bb; else goto ...;
594 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, true,
598 /* And a version where the outer condition is negated. */
599 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &then_bb
)
600 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
601 && bb_no_side_effects_p (inner_cond_bb
))
605 if (q) goto inner_cond_bb; else goto then_bb;
607 if (q) goto then_bb; else goto ...;
611 return ifcombine_ifandif (inner_cond_bb
, true, outer_cond_bb
, false,
619 /* Main entry for the tree if-conversion pass. */
622 tree_ssa_ifcombine (void)
625 bool cfg_changed
= false;
628 bbs
= blocks_in_phiopt_order ();
629 calculate_dominance_info (CDI_DOMINATORS
);
631 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; ++i
)
633 basic_block bb
= bbs
[i
];
634 gimple stmt
= last_stmt (bb
);
637 && gimple_code (stmt
) == GIMPLE_COND
)
638 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
643 return cfg_changed
? TODO_cleanup_cfg
: 0;
647 gate_ifcombine (void)
652 struct gimple_opt_pass pass_tree_ifcombine
=
656 "ifcombine", /* name */
657 OPTGROUP_NONE
, /* optinfo_flags */
658 gate_ifcombine
, /* gate */
659 tree_ssa_ifcombine
, /* execute */
662 0, /* static_pass_number */
663 TV_TREE_IFCOMBINE
, /* tv_id */
664 PROP_cfg
| PROP_ssa
, /* properties_required */
665 0, /* properties_provided */
666 0, /* properties_destroyed */
667 0, /* todo_flags_start */
670 | TODO_verify_ssa
/* todo_flags_finish */