1 /* Combining of if-expressions on trees.
2 Copyright (C) 2007 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 block_stmt_iterator bsi;
106 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
108 tree stmt = bsi_stmt (bsi);
109 stmt_ann_t ann = stmt_ann (stmt);
111 if (ann->has_volatile_ops
112 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
119 /* Verify if all PHI node arguments in DEST for edges from BB1 or
120 BB2 to DEST are the same. This makes the CFG merge point
121 free from side-effects. Return true in this case, else false. */
124 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
126 edge e1 = find_edge (bb1, dest);
127 edge e2 = find_edge (bb2, dest);
130 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
131 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
132 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
138 /* Return the best representative SSA name for CANDIDATE which is used
142 get_name_for_bit_test (tree candidate)
144 /* Skip single-use names in favor of using the name from a
145 non-widening conversion definition. */
146 if (TREE_CODE (candidate) == SSA_NAME
147 && has_single_use (candidate))
149 tree def_stmt = SSA_NAME_DEF_STMT (candidate);
150 if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
151 && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
152 || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == CONVERT_EXPR))
154 tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
155 if (TYPE_PRECISION (TREE_TYPE (rhs))
156 <= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs, 0))))
157 return TREE_OPERAND (rhs, 0);
164 /* Recognize a single bit test pattern in COND_EXPR and its defining
165 statements. Store the name being tested in *NAME and the bit
166 in *BIT. The COND_EXPR computes *NAME & (1 << *BIT).
167 Returns true if the pattern matched, false otherwise. */
170 recognize_single_bit_test (tree cond_expr, tree *name, tree *bit)
174 /* Get at the definition of the result of the bit test. */
175 t = TREE_OPERAND (cond_expr, 0);
176 if (TREE_CODE (t) == NE_EXPR
177 && integer_zerop (TREE_OPERAND (t, 1)))
178 t = TREE_OPERAND (t, 0);
179 if (TREE_CODE (t) != SSA_NAME)
181 t = SSA_NAME_DEF_STMT (t);
182 if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
184 t = GIMPLE_STMT_OPERAND (t, 1);
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 (TREE_CODE (t) == BIT_AND_EXPR
192 && integer_onep (TREE_OPERAND (t, 1))
193 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
195 tree orig_name = TREE_OPERAND (t, 0);
197 /* Look through copies and conversions to eventually
198 find the stmt that computes the shift. */
201 t = SSA_NAME_DEF_STMT (t);
202 if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
204 t = GIMPLE_STMT_OPERAND (t, 1);
205 if (TREE_CODE (t) == NOP_EXPR
206 || TREE_CODE (t) == CONVERT_EXPR)
207 t = TREE_OPERAND (t, 0);
208 } while (TREE_CODE (t) == SSA_NAME);
210 /* If we found such, decompose it. */
211 if (TREE_CODE (t) == RSHIFT_EXPR)
213 /* op0 & (1 << op1) */
214 *bit = TREE_OPERAND (t, 1);
215 *name = TREE_OPERAND (t, 0);
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 (TREE_CODE (t) == BIT_AND_EXPR
231 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
232 && integer_pow2p (TREE_OPERAND (t, 1)))
234 *name = TREE_OPERAND (t, 0);
235 *bit = build_int_cst (integer_type_node,
236 tree_log2 (TREE_OPERAND (t, 1)));
241 D.1986_6 = 1 << control1_4(D)
242 D.1987_7 = op0 & D.1986_6
243 if (D.1987_7 != 0) */
244 if (TREE_CODE (t) == BIT_AND_EXPR
245 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
246 && TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
250 /* Both arguments of the BIT_AND_EXPR can be the single-bit
251 specifying expression. */
252 tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 0));
253 if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
254 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
255 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
257 *name = TREE_OPERAND (t, 1);
258 *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
262 tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 1));
263 if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
264 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
265 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
267 *name = TREE_OPERAND (t, 0);
268 *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
276 /* Recognize a bit test pattern in COND_EXPR 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 (tree cond_expr, tree *name, tree *bits)
286 /* Get at the definition of the result of the bit test. */
287 t = TREE_OPERAND (cond_expr, 0);
288 if (TREE_CODE (t) == NE_EXPR
289 && integer_zerop (TREE_OPERAND (t, 1)))
290 t = TREE_OPERAND (t, 0);
291 if (TREE_CODE (t) != SSA_NAME)
293 t = SSA_NAME_DEF_STMT (t);
294 if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
296 t = GIMPLE_STMT_OPERAND (t, 1);
298 if (TREE_CODE (t) != BIT_AND_EXPR)
301 *name = get_name_for_bit_test (TREE_OPERAND (t, 0));
302 *bits = TREE_OPERAND (t, 1);
307 /* If-convert on a and pattern with a common else block. The inner
308 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
309 Returns true if the edges to the common else basic-block were merged. */
312 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
314 block_stmt_iterator bsi;
315 tree inner_cond, outer_cond;
316 tree name1, name2, bit1, bit2;
318 inner_cond = last_stmt (inner_cond_bb);
320 || TREE_CODE (inner_cond) != COND_EXPR)
323 outer_cond = last_stmt (outer_cond_bb);
325 || TREE_CODE (outer_cond) != COND_EXPR)
328 /* See if we test a single bit of the same name in both tests. In
329 that case remove the outer test, merging both else edges,
330 and change the inner one to test for
331 name & (bit1 | bit2) == (bit1 | bit2). */
332 if (recognize_single_bit_test (inner_cond, &name1, &bit1)
333 && recognize_single_bit_test (outer_cond, &name2, &bit2)
339 bsi = bsi_for_stmt (inner_cond);
340 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
341 build_int_cst (TREE_TYPE (name1), 1), bit1);
342 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
343 build_int_cst (TREE_TYPE (name1), 1), bit2);
344 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
345 t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
346 true, BSI_SAME_STMT);
347 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
348 t2 = force_gimple_operand_bsi (&bsi, t2, true, NULL_TREE,
349 true, BSI_SAME_STMT);
350 COND_EXPR_COND (inner_cond) = fold_build2 (EQ_EXPR, boolean_type_node,
352 update_stmt (inner_cond);
354 /* Leave CFG optimization to cfg_cleanup. */
355 COND_EXPR_COND (outer_cond) = boolean_true_node;
356 update_stmt (outer_cond);
360 fprintf (dump_file, "optimizing double bit test to ");
361 print_generic_expr (dump_file, name1, 0);
362 fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
363 print_generic_expr (dump_file, bit1, 0);
364 fprintf (dump_file, ") | (1 << ");
365 print_generic_expr (dump_file, bit2, 0);
366 fprintf (dump_file, ")\n");
375 /* If-convert on a or pattern with a common then block. The inner
376 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
377 Returns true, if the edges leading to the common then basic-block
381 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
383 tree inner_cond, outer_cond;
384 tree name1, name2, bits1, bits2;
386 inner_cond = last_stmt (inner_cond_bb);
388 || TREE_CODE (inner_cond) != COND_EXPR)
391 outer_cond = last_stmt (outer_cond_bb);
393 || TREE_CODE (outer_cond) != COND_EXPR)
396 /* See if we have two bit tests of the same name in both tests.
397 In that case remove the outer test and change the inner one to
398 test for name & (bits1 | bits2) != 0. */
399 if (recognize_bits_test (inner_cond, &name1, &bits1)
400 && recognize_bits_test (outer_cond, &name2, &bits2))
402 block_stmt_iterator bsi;
405 /* Find the common name which is bit-tested. */
408 else if (bits1 == bits2)
417 else if (name1 == bits2)
423 else if (bits1 == name2)
433 bsi = bsi_for_stmt (inner_cond);
434 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
435 t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
436 true, BSI_SAME_STMT);
437 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
438 t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
439 true, BSI_SAME_STMT);
440 COND_EXPR_COND (inner_cond) = fold_build2 (NE_EXPR, boolean_type_node, t,
441 build_int_cst (TREE_TYPE (t), 0));
442 update_stmt (inner_cond);
444 /* Leave CFG optimization to cfg_cleanup. */
445 COND_EXPR_COND (outer_cond) = boolean_false_node;
446 update_stmt (outer_cond);
450 fprintf (dump_file, "optimizing bits or bits test to ");
451 print_generic_expr (dump_file, name1, 0);
452 fprintf (dump_file, " & T != 0\nwith temporary T = ");
453 print_generic_expr (dump_file, bits1, 0);
454 fprintf (dump_file, " | ");
455 print_generic_expr (dump_file, bits2, 0);
456 fprintf (dump_file, "\n");
462 /* See if we have two comparisons that we can merge into one.
463 This happens for C++ operator overloading where for example
464 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
465 else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond))
466 && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond))
467 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 0),
468 TREE_OPERAND (COND_EXPR_COND (outer_cond), 0), 0)
469 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 1),
470 TREE_OPERAND (COND_EXPR_COND (outer_cond), 1), 0))
472 tree ccond1 = COND_EXPR_COND (inner_cond);
473 tree ccond2 = COND_EXPR_COND (outer_cond);
474 enum tree_code code1 = TREE_CODE (ccond1);
475 enum tree_code code2 = TREE_CODE (ccond2);
479 #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
480 || (code2 == a ## _EXPR && code1 == b ## _EXPR))
481 /* Merge the two condition codes if possible. */
484 else if (CHK (EQ, LT))
486 else if (CHK (EQ, GT))
488 else if (CHK (LT, LE))
490 else if (CHK (GT, GE))
492 else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1, 0)))
493 || flag_unsafe_math_optimizations)
497 else if (CHK (LT, NE))
499 else if (CHK (GT, NE))
504 /* We could check for combinations leading to trivial true/false. */
510 t = fold_build2 (code, boolean_type_node,
511 TREE_OPERAND (ccond2, 0), TREE_OPERAND (ccond2, 1));
512 t = canonicalize_cond_expr_cond (t);
515 COND_EXPR_COND (inner_cond) = t;
516 update_stmt (inner_cond);
518 /* Leave CFG optimization to cfg_cleanup. */
519 COND_EXPR_COND (outer_cond) = boolean_false_node;
520 update_stmt (outer_cond);
524 fprintf (dump_file, "optimizing two comparisons to ");
525 print_generic_expr (dump_file, t, 0);
526 fprintf (dump_file, "\n");
535 /* Recognize a CFG pattern and dispatch to the appropriate
536 if-conversion helper. We start with BB as the innermost
537 worker basic-block. Returns true if a transformation was done. */
540 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
542 basic_block then_bb = NULL, else_bb = NULL;
544 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
547 /* Recognize && and || of two conditions with a common
548 then/else block which entry edges we can merge. That is:
554 This requires a single predecessor of the inner cond_bb. */
555 if (single_pred_p (inner_cond_bb))
557 basic_block outer_cond_bb = single_pred (inner_cond_bb);
559 /* The && form is characterized by a common else_bb with
560 the two edges leading to it mergable. The latter is
561 guaranteed by matching PHI arguments in the else_bb and
562 the inner cond_bb having no side-effects. */
563 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
564 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
565 && bb_no_side_effects_p (inner_cond_bb))
569 if (q) goto inner_cond_bb; else goto else_bb;
571 if (p) goto ...; else goto else_bb;
576 return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
579 /* The || form is characterized by a common then_bb with the
580 two edges leading to it mergable. The latter is guaranteed
581 by matching PHI arguments in the then_bb and the inner cond_bb
582 having no side-effects. */
583 if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
584 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
585 && bb_no_side_effects_p (inner_cond_bb))
589 if (q) goto then_bb; else goto inner_cond_bb;
591 if (q) goto then_bb; else goto ...;
595 return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
602 /* Main entry for the tree if-conversion pass. */
605 tree_ssa_ifcombine (void)
608 bool cfg_changed = false;
611 bbs = blocks_in_phiopt_order ();
613 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
615 basic_block bb = bbs[i];
616 tree stmt = last_stmt (bb);
619 && TREE_CODE (stmt) == COND_EXPR)
620 cfg_changed |= tree_ssa_ifcombine_bb (bb);
625 return cfg_changed ? TODO_cleanup_cfg : 0;
629 gate_ifcombine (void)
634 struct gimple_opt_pass pass_tree_ifcombine =
638 "ifcombine", /* name */
639 gate_ifcombine, /* gate */
640 tree_ssa_ifcombine, /* execute */
643 0, /* static_pass_number */
644 TV_TREE_IFCOMBINE, /* tv_id */
645 PROP_cfg | PROP_ssa, /* properties_required */
646 0, /* properties_provided */
647 0, /* properties_destroyed */
648 0, /* todo_flags_start */
652 | TODO_verify_ssa /* todo_flags_finish */