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 (TRUTH_ANDIF_EXPR
, code1
, code2
,
397 gimple_cond_lhs (outer_cond
),
398 gimple_cond_rhs (outer_cond
))))
400 t
= canonicalize_cond_expr_cond (t
);
403 gimple_cond_set_condition_from_tree (inner_cond
, t
);
404 update_stmt (inner_cond
);
406 /* Leave CFG optimization to cfg_cleanup. */
407 gimple_cond_set_condition_from_tree (outer_cond
, boolean_true_node
);
408 update_stmt (outer_cond
);
412 fprintf (dump_file
, "optimizing two comparisons to ");
413 print_generic_expr (dump_file
, t
, 0);
414 fprintf (dump_file
, "\n");
423 /* If-convert on a or pattern with a common then block. The inner
424 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
425 Returns true, if the edges leading to the common then basic-block
429 ifcombine_iforif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
431 gimple inner_cond
, outer_cond
;
432 tree name1
, name2
, bits1
, bits2
;
434 inner_cond
= last_stmt (inner_cond_bb
);
436 || gimple_code (inner_cond
) != GIMPLE_COND
)
439 outer_cond
= last_stmt (outer_cond_bb
);
441 || gimple_code (outer_cond
) != GIMPLE_COND
)
444 /* See if we have two bit tests of the same name in both tests.
445 In that case remove the outer test and change the inner one to
446 test for name & (bits1 | bits2) != 0. */
447 if (recognize_bits_test (inner_cond
, &name1
, &bits1
)
448 && recognize_bits_test (outer_cond
, &name2
, &bits2
))
450 gimple_stmt_iterator gsi
;
453 /* Find the common name which is bit-tested. */
456 else if (bits1
== bits2
)
465 else if (name1
== bits2
)
471 else if (bits1
== name2
)
480 /* As we strip non-widening conversions in finding a common
481 name that is tested make sure to end up with an integral
482 type for building the bit operations. */
483 if (TYPE_PRECISION (TREE_TYPE (bits1
))
484 >= TYPE_PRECISION (TREE_TYPE (bits2
)))
486 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
487 name1
= fold_convert (TREE_TYPE (bits1
), name1
);
488 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
489 bits2
= fold_convert (TREE_TYPE (bits1
), bits2
);
493 bits2
= fold_convert (unsigned_type_for (TREE_TYPE (bits2
)), bits2
);
494 name1
= fold_convert (TREE_TYPE (bits2
), name1
);
495 bits1
= fold_convert (unsigned_type_for (TREE_TYPE (bits1
)), bits1
);
496 bits1
= fold_convert (TREE_TYPE (bits2
), bits1
);
500 gsi
= gsi_for_stmt (inner_cond
);
501 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
502 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
503 true, GSI_SAME_STMT
);
504 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
505 t
= force_gimple_operand_gsi (&gsi
, t
, true, NULL_TREE
,
506 true, GSI_SAME_STMT
);
507 t
= fold_build2 (NE_EXPR
, boolean_type_node
, t
,
508 build_int_cst (TREE_TYPE (t
), 0));
509 gimple_cond_set_condition_from_tree (inner_cond
, t
);
510 update_stmt (inner_cond
);
512 /* Leave CFG optimization to cfg_cleanup. */
513 gimple_cond_set_condition_from_tree (outer_cond
, boolean_false_node
);
514 update_stmt (outer_cond
);
518 fprintf (dump_file
, "optimizing bits or bits test to ");
519 print_generic_expr (dump_file
, name1
, 0);
520 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
521 print_generic_expr (dump_file
, bits1
, 0);
522 fprintf (dump_file
, " | ");
523 print_generic_expr (dump_file
, bits2
, 0);
524 fprintf (dump_file
, "\n");
530 /* See if we have two comparisons that we can merge into one.
531 This happens for C++ operator overloading where for example
532 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
533 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond
)) == tcc_comparison
534 && TREE_CODE_CLASS (gimple_cond_code (outer_cond
)) == tcc_comparison
535 && operand_equal_p (gimple_cond_lhs (inner_cond
),
536 gimple_cond_lhs (outer_cond
), 0)
537 && operand_equal_p (gimple_cond_rhs (inner_cond
),
538 gimple_cond_rhs (outer_cond
), 0))
540 enum tree_code code1
= gimple_cond_code (inner_cond
);
541 enum tree_code code2
= gimple_cond_code (outer_cond
);
544 if (!(t
= combine_comparisons (TRUTH_ORIF_EXPR
, code1
, code2
,
546 gimple_cond_lhs (outer_cond
),
547 gimple_cond_rhs (outer_cond
))))
549 t
= canonicalize_cond_expr_cond (t
);
552 gimple_cond_set_condition_from_tree (inner_cond
, t
);
553 update_stmt (inner_cond
);
555 /* Leave CFG optimization to cfg_cleanup. */
556 gimple_cond_set_condition_from_tree (outer_cond
, boolean_false_node
);
557 update_stmt (outer_cond
);
561 fprintf (dump_file
, "optimizing two comparisons to ");
562 print_generic_expr (dump_file
, t
, 0);
563 fprintf (dump_file
, "\n");
572 /* Recognize a CFG pattern and dispatch to the appropriate
573 if-conversion helper. We start with BB as the innermost
574 worker basic-block. Returns true if a transformation was done. */
577 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
579 basic_block then_bb
= NULL
, else_bb
= NULL
;
581 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
584 /* Recognize && and || of two conditions with a common
585 then/else block which entry edges we can merge. That is:
591 This requires a single predecessor of the inner cond_bb. */
592 if (single_pred_p (inner_cond_bb
))
594 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
596 /* The && form is characterized by a common else_bb with
597 the two edges leading to it mergable. The latter is
598 guaranteed by matching PHI arguments in the else_bb and
599 the inner cond_bb having no side-effects. */
600 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
601 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
602 && bb_no_side_effects_p (inner_cond_bb
))
606 if (q) goto inner_cond_bb; else goto else_bb;
608 if (p) goto ...; else goto else_bb;
613 return ifcombine_ifandif (inner_cond_bb
, outer_cond_bb
);
616 /* The || form is characterized by a common then_bb with the
617 two edges leading to it mergable. The latter is guaranteed
618 by matching PHI arguments in the then_bb and the inner cond_bb
619 having no side-effects. */
620 if (recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
621 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
622 && bb_no_side_effects_p (inner_cond_bb
))
626 if (q) goto then_bb; else goto inner_cond_bb;
628 if (q) goto then_bb; else goto ...;
632 return ifcombine_iforif (inner_cond_bb
, outer_cond_bb
);
639 /* Main entry for the tree if-conversion pass. */
642 tree_ssa_ifcombine (void)
645 bool cfg_changed
= false;
648 bbs
= blocks_in_phiopt_order ();
650 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; ++i
)
652 basic_block bb
= bbs
[i
];
653 gimple stmt
= last_stmt (bb
);
656 && gimple_code (stmt
) == GIMPLE_COND
)
657 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
662 return cfg_changed
? TODO_cleanup_cfg
: 0;
666 gate_ifcombine (void)
671 struct gimple_opt_pass pass_tree_ifcombine
=
675 "ifcombine", /* name */
676 gate_ifcombine
, /* gate */
677 tree_ssa_ifcombine
, /* execute */
680 0, /* static_pass_number */
681 TV_TREE_IFCOMBINE
, /* tv_id */
682 PROP_cfg
| PROP_ssa
, /* properties_required */
683 0, /* properties_provided */
684 0, /* properties_destroyed */
685 0, /* todo_flags_start */
689 | TODO_verify_ssa
/* todo_flags_finish */