1 /* Combining of if-expressions on trees.
2 Copyright (C) 2007, 2008 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"
28 #include "diagnostic.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
31 #include "tree-dump.h"
33 /* This pass combines COND_EXPRs to simplify control flow. It
34 currently recognizes bit tests and comparisons in chains that
35 represent logical and or logical or of two COND_EXPRs.
37 It does so by walking basic blocks in a approximate reverse
38 post-dominator order and trying to match CFG patterns that
39 represent logical and or logical or of two COND_EXPRs.
40 Transformations are done if the COND_EXPR conditions match
43 1. two single bit tests X & (1 << Yn) (for logical and)
45 2. two bit tests X & Yn (for logical or)
47 3. two comparisons X OPn Y (for logical or)
49 To simplify this pass, removing basic blocks and dead code
50 is left to CFG cleanup and DCE. */
53 /* Recognize a if-then-else CFG pattern starting to match with the
54 COND_BB basic-block containing the COND_EXPR. The recognized
55 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
56 *THEN_BB and/or *ELSE_BB are already set, they are required to
57 match the then and else basic-blocks to make the pattern match.
58 Returns true if the pattern matched, false otherwise. */
61 recognize_if_then_else (basic_block cond_bb
,
62 basic_block
*then_bb
, basic_block
*else_bb
)
66 if (EDGE_COUNT (cond_bb
->succs
) != 2)
69 /* Find the then/else edges. */
70 t
= EDGE_SUCC (cond_bb
, 0);
71 e
= EDGE_SUCC (cond_bb
, 1);
72 if (!(t
->flags
& EDGE_TRUE_VALUE
))
78 if (!(t
->flags
& EDGE_TRUE_VALUE
)
79 || !(e
->flags
& EDGE_FALSE_VALUE
))
82 /* Check if the edge destinations point to the required block. */
84 && t
->dest
!= *then_bb
)
87 && e
->dest
!= *else_bb
)
98 /* Verify if the basic block BB does not have side-effects. Return
99 true in this case, else false. */
102 bb_no_side_effects_p (basic_block bb
)
104 gimple_stmt_iterator gsi
;
106 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
108 gimple stmt
= gsi_stmt (gsi
);
110 if (gimple_has_volatile_ops (stmt
)
111 || gimple_vuse (stmt
))
118 /* Verify if all PHI node arguments in DEST for edges from BB1 or
119 BB2 to DEST are the same. This makes the CFG merge point
120 free from side-effects. Return true in this case, else false. */
123 same_phi_args_p (basic_block bb1
, basic_block bb2
, basic_block dest
)
125 edge e1
= find_edge (bb1
, dest
);
126 edge e2
= find_edge (bb2
, dest
);
127 gimple_stmt_iterator gsi
;
130 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
132 phi
= gsi_stmt (gsi
);
133 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi
, e1
),
134 PHI_ARG_DEF_FROM_EDGE (phi
, e2
), 0))
141 /* Return the best representative SSA name for CANDIDATE which is used
145 get_name_for_bit_test (tree candidate
)
147 /* Skip single-use names in favor of using the name from a
148 non-widening conversion definition. */
149 if (TREE_CODE (candidate
) == SSA_NAME
150 && has_single_use (candidate
))
152 gimple def_stmt
= SSA_NAME_DEF_STMT (candidate
);
153 if (is_gimple_assign (def_stmt
)
154 && gimple_assign_cast_p (def_stmt
))
156 if (TYPE_PRECISION (TREE_TYPE (candidate
))
157 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
))))
158 return gimple_assign_rhs1 (def_stmt
);
165 /* Helpers for recognize_single_bit_test defined mainly for source code
169 operand_precision (tree t
)
171 return TYPE_PRECISION (TREE_TYPE (t
));
175 integral_operand_p (tree t
)
177 return INTEGRAL_TYPE_P (TREE_TYPE (t
));
180 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
181 statements. Store the name being tested in *NAME and the bit
182 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
183 Returns true if the pattern matched, false otherwise. */
186 recognize_single_bit_test (gimple cond
, tree
*name
, tree
*bit
)
190 /* Get at the definition of the result of the bit test. */
191 if (gimple_cond_code (cond
) != NE_EXPR
192 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
193 || !integer_zerop (gimple_cond_rhs (cond
)))
195 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
196 if (!is_gimple_assign (stmt
))
199 /* Look at which bit is tested. One form to recognize is
200 D.1985_5 = state_3(D) >> control1_4(D);
201 D.1986_6 = (int) D.1985_5;
203 if (D.1987_7 != 0) */
204 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
205 && integer_onep (gimple_assign_rhs2 (stmt
))
206 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
208 tree orig_name
= gimple_assign_rhs1 (stmt
);
210 /* Look through copies and conversions to eventually
211 find the stmt that computes the shift. */
212 stmt
= SSA_NAME_DEF_STMT (orig_name
);
214 while (is_gimple_assign (stmt
)
215 && (gimple_assign_ssa_name_copy_p (stmt
)
216 || (gimple_assign_cast_p (stmt
)
217 && integral_operand_p (gimple_assign_lhs (stmt
))
218 && integral_operand_p (gimple_assign_rhs1 (stmt
))
219 && (operand_precision (gimple_assign_lhs (stmt
))
220 <= operand_precision (gimple_assign_rhs1 (stmt
))))))
222 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
225 /* If we found such, decompose it. */
226 if (is_gimple_assign (stmt
)
227 && gimple_assign_rhs_code (stmt
) == RSHIFT_EXPR
)
229 /* op0 & (1 << op1) */
230 *bit
= gimple_assign_rhs2 (stmt
);
231 *name
= gimple_assign_rhs1 (stmt
);
236 *bit
= integer_zero_node
;
237 *name
= get_name_for_bit_test (orig_name
);
244 D.1987_7 = op0 & (1 << CST)
245 if (D.1987_7 != 0) */
246 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
247 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
248 && integer_pow2p (gimple_assign_rhs2 (stmt
)))
250 *name
= gimple_assign_rhs1 (stmt
);
251 *bit
= build_int_cst (integer_type_node
,
252 tree_log2 (gimple_assign_rhs2 (stmt
)));
257 D.1986_6 = 1 << control1_4(D)
258 D.1987_7 = op0 & D.1986_6
259 if (D.1987_7 != 0) */
260 if (gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
261 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
262 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
)
266 /* Both arguments of the BIT_AND_EXPR can be the single-bit
267 specifying expression. */
268 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
269 if (is_gimple_assign (tmp
)
270 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
271 && integer_onep (gimple_assign_rhs1 (tmp
)))
273 *name
= gimple_assign_rhs2 (stmt
);
274 *bit
= gimple_assign_rhs2 (tmp
);
278 tmp
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
279 if (is_gimple_assign (tmp
)
280 && gimple_assign_rhs_code (tmp
) == LSHIFT_EXPR
281 && integer_onep (gimple_assign_rhs1 (tmp
)))
283 *name
= gimple_assign_rhs1 (stmt
);
284 *bit
= gimple_assign_rhs2 (tmp
);
292 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
293 statements. Store the name being tested in *NAME and the bits
294 in *BITS. The COND_EXPR computes *NAME & *BITS.
295 Returns true if the pattern matched, false otherwise. */
298 recognize_bits_test (gimple cond
, tree
*name
, tree
*bits
)
302 /* Get at the definition of the result of the bit test. */
303 if (gimple_cond_code (cond
) != NE_EXPR
304 || TREE_CODE (gimple_cond_lhs (cond
)) != SSA_NAME
305 || !integer_zerop (gimple_cond_rhs (cond
)))
307 stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
308 if (!is_gimple_assign (stmt
)
309 || gimple_assign_rhs_code (stmt
) != BIT_AND_EXPR
)
312 *name
= get_name_for_bit_test (gimple_assign_rhs1 (stmt
));
313 *bits
= gimple_assign_rhs2 (stmt
);
318 /* If-convert on a and pattern with a common else block. The inner
319 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
320 Returns true if the edges to the common else basic-block were merged. */
323 ifcombine_ifandif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
325 gimple_stmt_iterator gsi
;
326 gimple inner_cond
, outer_cond
;
327 tree name1
, name2
, bit1
, bit2
;
329 inner_cond
= last_stmt (inner_cond_bb
);
331 || gimple_code (inner_cond
) != GIMPLE_COND
)
334 outer_cond
= last_stmt (outer_cond_bb
);
336 || gimple_code (outer_cond
) != GIMPLE_COND
)
339 /* See if we test a single bit of the same name in both tests. In
340 that case remove the outer test, merging both else edges,
341 and change the inner one to test for
342 name & (bit1 | bit2) == (bit1 | bit2). */
343 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
)
344 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
)
350 gsi
= gsi_for_stmt (inner_cond
);
351 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
352 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
353 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
354 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
355 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
356 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
357 true, GSI_SAME_STMT
);
358 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
359 t2
= force_gimple_operand_gsi (&gsi
, t2
, true, NULL_TREE
,
360 true, GSI_SAME_STMT
);
361 t
= fold_build2 (EQ_EXPR
, boolean_type_node
, t2
, t
);
362 gimple_cond_set_condition_from_tree (inner_cond
, t
);
363 update_stmt (inner_cond
);
365 /* Leave CFG optimization to cfg_cleanup. */
366 gimple_cond_set_condition_from_tree (outer_cond
, boolean_true_node
);
367 update_stmt (outer_cond
);
371 fprintf (dump_file
, "optimizing double bit test to ");
372 print_generic_expr (dump_file
, name1
, 0);
373 fprintf (dump_file
, " & T == T\nwith temporary T = (1 << ");
374 print_generic_expr (dump_file
, bit1
, 0);
375 fprintf (dump_file
, ") | (1 << ");
376 print_generic_expr (dump_file
, bit2
, 0);
377 fprintf (dump_file
, ")\n");
383 /* See if we have two comparisons that we can merge into one. */
384 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
385 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
386 && operand_equal_p (gimple_cond_lhs (inner_cond
),
387 gimple_cond_lhs (outer_cond
), 0)
388 && operand_equal_p (gimple_cond_rhs (inner_cond
),
389 gimple_cond_rhs (outer_cond
), 0))
391 enum tree_code code1
= gimple_cond_code (inner_cond
);
392 enum tree_code code2
= gimple_cond_code (outer_cond
);
395 if (!(t
= combine_comparisons (UNKNOWN_LOCATION
,
396 TRUTH_ANDIF_EXPR
, code1
, code2
,
398 gimple_cond_lhs (outer_cond
),
399 gimple_cond_rhs (outer_cond
))))
401 t
= canonicalize_cond_expr_cond (t
);
404 gimple_cond_set_condition_from_tree (inner_cond
, t
);
405 update_stmt (inner_cond
);
407 /* Leave CFG optimization to cfg_cleanup. */
408 gimple_cond_set_condition_from_tree (outer_cond
, boolean_true_node
);
409 update_stmt (outer_cond
);
413 fprintf (dump_file
, "optimizing two comparisons to ");
414 print_generic_expr (dump_file
, t
, 0);
415 fprintf (dump_file
, "\n");
424 /* If-convert on a or pattern with a common then block. The inner
425 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
426 Returns true, if the edges leading to the common then basic-block
430 ifcombine_iforif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
432 gimple inner_cond
, outer_cond
;
433 tree name1
, name2
, bits1
, bits2
;
435 inner_cond
= last_stmt (inner_cond_bb
);
437 || gimple_code (inner_cond
) != GIMPLE_COND
)
440 outer_cond
= last_stmt (outer_cond_bb
);
442 || gimple_code (outer_cond
) != GIMPLE_COND
)
445 /* See if we have two bit tests of the same name in both tests.
446 In that case remove the outer test and change the inner one to
447 test for name & (bits1 | bits2) != 0. */
448 if (recognize_bits_test (inner_cond
, &name1
, &bits1
)
449 && recognize_bits_test (outer_cond
, &name2
, &bits2
))
451 gimple_stmt_iterator gsi
;
454 /* Find the common name which is bit-tested. */
457 else if (bits1
== bits2
)
466 else if (name1
== bits2
)
472 else if (bits1
== name2
)
481 /* As we strip non-widening conversions in finding a common
482 name that is tested make sure to end up with an integral
483 type for building the bit operations. */
484 if (TYPE_PRECISION (TREE_TYPE (bits1
))
485 >= TYPE_PRECISION (TREE_TYPE (bits2
)))
487 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
488 name1
= fold_convert (TREE_TYPE (bits1
), name1
);
489 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
490 bits2
= fold_convert (TREE_TYPE (bits1
), bits2
);
494 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
495 name1
= fold_convert (TREE_TYPE (bits2
), name1
);
496 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
497 bits1
= fold_convert (TREE_TYPE (bits2
), bits1
);
501 gsi
= gsi_for_stmt (inner_cond
);
502 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
503 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
504 true, GSI_SAME_STMT
);
505 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
506 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
507 true, GSI_SAME_STMT
);
508 t
= fold_build2 (NE_EXPR
, boolean_type_node
, t
,
509 build_int_cst (TREE_TYPE (t
), 0));
510 gimple_cond_set_condition_from_tree (inner_cond
, t
);
511 update_stmt (inner_cond
);
513 /* Leave CFG optimization to cfg_cleanup. */
514 gimple_cond_set_condition_from_tree (outer_cond
, boolean_false_node
);
515 update_stmt (outer_cond
);
519 fprintf (dump_file
, "optimizing bits or bits test to ");
520 print_generic_expr (dump_file
, name1
, 0);
521 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
522 print_generic_expr (dump_file
, bits1
, 0);
523 fprintf (dump_file
, " | ");
524 print_generic_expr (dump_file
, bits2
, 0);
525 fprintf (dump_file
, "\n");
531 /* See if we have two comparisons that we can merge into one.
532 This happens for C++ operator overloading where for example
533 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
534 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
535 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
536 && operand_equal_p (gimple_cond_lhs (inner_cond
),
537 gimple_cond_lhs (outer_cond
), 0)
538 && operand_equal_p (gimple_cond_rhs (inner_cond
),
539 gimple_cond_rhs (outer_cond
), 0))
541 enum tree_code code1
= gimple_cond_code (inner_cond
);
542 enum tree_code code2
= gimple_cond_code (outer_cond
);
545 if (!(t
= combine_comparisons (UNKNOWN_LOCATION
,
546 TRUTH_ORIF_EXPR
, code1
, code2
,
548 gimple_cond_lhs (outer_cond
),
549 gimple_cond_rhs (outer_cond
))))
551 t
= canonicalize_cond_expr_cond (t
);
554 gimple_cond_set_condition_from_tree (inner_cond
, t
);
555 update_stmt (inner_cond
);
557 /* Leave CFG optimization to cfg_cleanup. */
558 gimple_cond_set_condition_from_tree (outer_cond
, boolean_false_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 /* Recognize a CFG pattern and dispatch to the appropriate
575 if-conversion helper. We start with BB as the innermost
576 worker basic-block. Returns true if a transformation was done. */
579 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
581 basic_block then_bb
= NULL
, else_bb
= NULL
;
583 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
586 /* Recognize && and || of two conditions with a common
587 then/else block which entry edges we can merge. That is:
593 This requires a single predecessor of the inner cond_bb. */
594 if (single_pred_p (inner_cond_bb
))
596 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
598 /* The && form is characterized by a common else_bb with
599 the two edges leading to it mergable. The latter is
600 guaranteed by matching PHI arguments in the else_bb and
601 the inner cond_bb having no side-effects. */
602 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
603 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
604 && bb_no_side_effects_p (inner_cond_bb
))
608 if (q) goto inner_cond_bb; else goto else_bb;
610 if (p) goto ...; else goto else_bb;
615 return ifcombine_ifandif (inner_cond_bb
, outer_cond_bb
);
618 /* The || form is characterized by a common then_bb with the
619 two edges leading to it mergable. The latter is guaranteed
620 by matching PHI arguments in the then_bb and the inner cond_bb
621 having no side-effects. */
622 if (recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
623 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
624 && bb_no_side_effects_p (inner_cond_bb
))
628 if (q) goto then_bb; else goto inner_cond_bb;
630 if (q) goto then_bb; else goto ...;
634 return ifcombine_iforif (inner_cond_bb
, outer_cond_bb
);
641 /* Main entry for the tree if-conversion pass. */
644 tree_ssa_ifcombine (void)
647 bool cfg_changed
= false;
650 bbs
= blocks_in_phiopt_order ();
652 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; ++i
)
654 basic_block bb
= bbs
[i
];
655 gimple stmt
= last_stmt (bb
);
658 && gimple_code (stmt
) == GIMPLE_COND
)
659 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
664 return cfg_changed
? TODO_cleanup_cfg
: 0;
668 gate_ifcombine (void)
673 struct gimple_opt_pass pass_tree_ifcombine
=
677 "ifcombine", /* name */
678 gate_ifcombine
, /* gate */
679 tree_ssa_ifcombine
, /* execute */
682 0, /* static_pass_number */
683 TV_TREE_IFCOMBINE
, /* tv_id */
684 PROP_cfg
| PROP_ssa
, /* properties_required */
685 0, /* properties_provided */
686 0, /* properties_destroyed */
687 0, /* todo_flags_start */
691 | TODO_verify_ssa
/* todo_flags_finish */