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 (gimple_has_side_effects (stmt)
109 || gimple_vuse (stmt))
116 /* Verify if all PHI node arguments in DEST for edges from BB1 or
117 BB2 to DEST are the same. This makes the CFG merge point
118 free from side-effects. Return true in this case, else false. */
121 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
123 edge e1 = find_edge (bb1, dest);
124 edge e2 = find_edge (bb2, dest);
125 gimple_stmt_iterator gsi;
128 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
130 phi = gsi_stmt (gsi);
131 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
132 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
139 /* Return the best representative SSA name for CANDIDATE which is used
143 get_name_for_bit_test (tree candidate)
145 /* Skip single-use names in favor of using the name from a
146 non-widening conversion definition. */
147 if (TREE_CODE (candidate) == SSA_NAME
148 && has_single_use (candidate))
150 gimple def_stmt = SSA_NAME_DEF_STMT (candidate);
151 if (is_gimple_assign (def_stmt)
152 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
154 if (TYPE_PRECISION (TREE_TYPE (candidate))
155 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
156 return gimple_assign_rhs1 (def_stmt);
163 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
164 statements. Store the name being tested in *NAME and the bit
165 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
166 Returns true if the pattern matched, false otherwise. */
169 recognize_single_bit_test (gimple cond, tree *name, tree *bit, bool inv)
173 /* Get at the definition of the result of the bit test. */
174 if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
175 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
176 || !integer_zerop (gimple_cond_rhs (cond)))
178 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
179 if (!is_gimple_assign (stmt))
182 /* Look at which bit is tested. One form to recognize is
183 D.1985_5 = state_3(D) >> control1_4(D);
184 D.1986_6 = (int) D.1985_5;
186 if (D.1987_7 != 0) */
187 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
188 && integer_onep (gimple_assign_rhs2 (stmt))
189 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
191 tree orig_name = gimple_assign_rhs1 (stmt);
193 /* Look through copies and conversions to eventually
194 find the stmt that computes the shift. */
195 stmt = SSA_NAME_DEF_STMT (orig_name);
197 while (is_gimple_assign (stmt)
198 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
199 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
200 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
201 || gimple_assign_ssa_name_copy_p (stmt)))
202 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
204 /* If we found such, decompose it. */
205 if (is_gimple_assign (stmt)
206 && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
208 /* op0 & (1 << op1) */
209 *bit = gimple_assign_rhs2 (stmt);
210 *name = gimple_assign_rhs1 (stmt);
215 *bit = integer_zero_node;
216 *name = get_name_for_bit_test (orig_name);
223 D.1987_7 = op0 & (1 << CST)
224 if (D.1987_7 != 0) */
225 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
226 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
227 && integer_pow2p (gimple_assign_rhs2 (stmt)))
229 *name = gimple_assign_rhs1 (stmt);
230 *bit = build_int_cst (integer_type_node,
231 tree_log2 (gimple_assign_rhs2 (stmt)));
236 D.1986_6 = 1 << control1_4(D)
237 D.1987_7 = op0 & D.1986_6
238 if (D.1987_7 != 0) */
239 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
240 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
241 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
245 /* Both arguments of the BIT_AND_EXPR can be the single-bit
246 specifying expression. */
247 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
248 if (is_gimple_assign (tmp)
249 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
250 && integer_onep (gimple_assign_rhs1 (tmp)))
252 *name = gimple_assign_rhs2 (stmt);
253 *bit = gimple_assign_rhs2 (tmp);
257 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
258 if (is_gimple_assign (tmp)
259 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
260 && integer_onep (gimple_assign_rhs1 (tmp)))
262 *name = gimple_assign_rhs1 (stmt);
263 *bit = gimple_assign_rhs2 (tmp);
271 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
272 statements. Store the name being tested in *NAME and the bits
273 in *BITS. The COND_EXPR computes *NAME & *BITS.
274 Returns true if the pattern matched, false otherwise. */
277 recognize_bits_test (gimple cond, tree *name, tree *bits, bool inv)
281 /* Get at the definition of the result of the bit test. */
282 if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
283 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
284 || !integer_zerop (gimple_cond_rhs (cond)))
286 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
287 if (!is_gimple_assign (stmt)
288 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
291 *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
292 *bits = gimple_assign_rhs2 (stmt);
297 /* If-convert on a and pattern with a common else block. The inner
298 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
299 inner_inv, outer_inv and result_inv indicate whether the conditions
301 Returns true if the edges to the common else basic-block were merged. */
304 ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
305 basic_block outer_cond_bb, bool outer_inv, bool result_inv)
307 gimple_stmt_iterator gsi;
308 gimple inner_cond, outer_cond;
309 tree name1, name2, bit1, bit2, bits1, bits2;
311 inner_cond = last_stmt (inner_cond_bb);
313 || gimple_code (inner_cond) != GIMPLE_COND)
316 outer_cond = last_stmt (outer_cond_bb);
318 || gimple_code (outer_cond) != GIMPLE_COND)
321 /* See if we test a single bit of the same name in both tests. In
322 that case remove the outer test, merging both else edges,
323 and change the inner one to test for
324 name & (bit1 | bit2) == (bit1 | bit2). */
325 if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
326 && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
332 gsi = gsi_for_stmt (inner_cond);
333 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
334 build_int_cst (TREE_TYPE (name1), 1), bit1);
335 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
336 build_int_cst (TREE_TYPE (name1), 1), bit2);
337 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
338 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
339 true, GSI_SAME_STMT);
340 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
341 t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
342 true, GSI_SAME_STMT);
343 t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
344 boolean_type_node, t2, t);
345 t = canonicalize_cond_expr_cond (t);
348 gimple_cond_set_condition_from_tree (inner_cond, t);
349 update_stmt (inner_cond);
351 /* Leave CFG optimization to cfg_cleanup. */
352 gimple_cond_set_condition_from_tree (outer_cond,
353 outer_inv ? boolean_false_node : boolean_true_node);
354 update_stmt (outer_cond);
358 fprintf (dump_file, "optimizing double bit test to ");
359 print_generic_expr (dump_file, name1, 0);
360 fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
361 print_generic_expr (dump_file, bit1, 0);
362 fprintf (dump_file, ") | (1 << ");
363 print_generic_expr (dump_file, bit2, 0);
364 fprintf (dump_file, ")\n");
370 /* See if we have two bit tests of the same name in both tests.
371 In that case remove the outer test and change the inner one to
372 test for name & (bits1 | bits2) != 0. */
373 else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
374 && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
376 gimple_stmt_iterator gsi;
379 /* Find the common name which is bit-tested. */
382 else if (bits1 == bits2)
391 else if (name1 == bits2)
397 else if (bits1 == name2)
406 /* As we strip non-widening conversions in finding a common
407 name that is tested make sure to end up with an integral
408 type for building the bit operations. */
409 if (TYPE_PRECISION (TREE_TYPE (bits1))
410 >= TYPE_PRECISION (TREE_TYPE (bits2)))
412 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
413 name1 = fold_convert (TREE_TYPE (bits1), name1);
414 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
415 bits2 = fold_convert (TREE_TYPE (bits1), bits2);
419 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
420 name1 = fold_convert (TREE_TYPE (bits2), name1);
421 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
422 bits1 = fold_convert (TREE_TYPE (bits2), bits1);
426 gsi = gsi_for_stmt (inner_cond);
427 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
428 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
429 true, GSI_SAME_STMT);
430 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
431 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
432 true, GSI_SAME_STMT);
433 t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t,
434 build_int_cst (TREE_TYPE (t), 0));
435 t = canonicalize_cond_expr_cond (t);
438 gimple_cond_set_condition_from_tree (inner_cond, t);
439 update_stmt (inner_cond);
441 /* Leave CFG optimization to cfg_cleanup. */
442 gimple_cond_set_condition_from_tree (outer_cond,
443 outer_inv ? boolean_false_node : boolean_true_node);
444 update_stmt (outer_cond);
448 fprintf (dump_file, "optimizing bits or bits test to ");
449 print_generic_expr (dump_file, name1, 0);
450 fprintf (dump_file, " & T != 0\nwith temporary T = ");
451 print_generic_expr (dump_file, bits1, 0);
452 fprintf (dump_file, " | ");
453 print_generic_expr (dump_file, bits2, 0);
454 fprintf (dump_file, "\n");
460 /* See if we have two comparisons that we can merge into one. */
461 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
462 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
465 enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
466 enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
468 /* Invert comparisons if necessary (and possible). */
470 inner_cond_code = invert_tree_comparison (inner_cond_code,
471 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond)))));
472 if (inner_cond_code == ERROR_MARK)
475 outer_cond_code = invert_tree_comparison (outer_cond_code,
476 HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));
477 if (outer_cond_code == ERROR_MARK)
479 /* Don't return false so fast, try maybe_fold_or_comparisons? */
481 if (!(t = maybe_fold_and_comparisons (inner_cond_code,
482 gimple_cond_lhs (inner_cond),
483 gimple_cond_rhs (inner_cond),
485 gimple_cond_lhs (outer_cond),
486 gimple_cond_rhs (outer_cond))))
489 t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
490 t = canonicalize_cond_expr_cond (t);
493 gimple_cond_set_condition_from_tree (inner_cond, t);
494 update_stmt (inner_cond);
496 /* Leave CFG optimization to cfg_cleanup. */
497 gimple_cond_set_condition_from_tree (outer_cond,
498 outer_inv ? boolean_false_node : boolean_true_node);
499 update_stmt (outer_cond);
503 fprintf (dump_file, "optimizing two comparisons to ");
504 print_generic_expr (dump_file, t, 0);
505 fprintf (dump_file, "\n");
514 /* Recognize a CFG pattern and dispatch to the appropriate
515 if-conversion helper. We start with BB as the innermost
516 worker basic-block. Returns true if a transformation was done. */
519 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
521 basic_block then_bb = NULL, else_bb = NULL;
523 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
526 /* Recognize && and || of two conditions with a common
527 then/else block which entry edges we can merge. That is:
533 This requires a single predecessor of the inner cond_bb. */
534 if (single_pred_p (inner_cond_bb))
536 basic_block outer_cond_bb = single_pred (inner_cond_bb);
538 /* The && form is characterized by a common else_bb with
539 the two edges leading to it mergable. The latter is
540 guaranteed by matching PHI arguments in the else_bb and
541 the inner cond_bb having no side-effects. */
542 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
543 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
544 && bb_no_side_effects_p (inner_cond_bb))
548 if (q) goto inner_cond_bb; else goto else_bb;
550 if (p) goto ...; else goto else_bb;
555 return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false,
559 /* And a version where the outer condition is negated. */
560 if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
561 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
562 && bb_no_side_effects_p (inner_cond_bb))
566 if (q) goto else_bb; else goto inner_cond_bb;
568 if (p) goto ...; else goto else_bb;
573 return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true,
577 /* The || form is characterized by a common then_bb with the
578 two edges leading to it mergable. The latter is guaranteed
579 by matching PHI arguments in the then_bb and the inner cond_bb
580 having no side-effects. */
581 if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
582 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
583 && bb_no_side_effects_p (inner_cond_bb))
587 if (q) goto then_bb; else goto inner_cond_bb;
589 if (q) goto then_bb; else goto ...;
593 return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true,
597 /* And a version where the outer condition is negated. */
598 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
599 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
600 && bb_no_side_effects_p (inner_cond_bb))
604 if (q) goto inner_cond_bb; else goto then_bb;
606 if (q) goto then_bb; else goto ...;
610 return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
618 /* Main entry for the tree if-conversion pass. */
621 tree_ssa_ifcombine (void)
624 bool cfg_changed = false;
627 bbs = blocks_in_phiopt_order ();
628 calculate_dominance_info (CDI_DOMINATORS);
630 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
632 basic_block bb = bbs[i];
633 gimple stmt = last_stmt (bb);
636 && gimple_code (stmt) == GIMPLE_COND)
637 cfg_changed |= tree_ssa_ifcombine_bb (bb);
642 return cfg_changed ? TODO_cleanup_cfg : 0;
646 gate_ifcombine (void)
651 struct gimple_opt_pass pass_tree_ifcombine =
655 "ifcombine", /* name */
656 OPTGROUP_NONE, /* optinfo_flags */
657 gate_ifcombine, /* gate */
658 tree_ssa_ifcombine, /* execute */
661 0, /* static_pass_number */
662 TV_TREE_IFCOMBINE, /* tv_id */
663 PROP_cfg | PROP_ssa, /* properties_required */
664 0, /* properties_provided */
665 0, /* properties_destroyed */
666 0, /* todo_flags_start */
669 | TODO_verify_ssa /* todo_flags_finish */