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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
24 #include "coretypes.h"
27 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
34 /* This pass combines COND_EXPRs to simplify control flow. It
35 currently recognizes bit tests and comparisons in chains that
36 represent logical and or logical or of two COND_EXPRs.
38 It does so by walking basic blocks in a approximate reverse
39 post-dominator order and trying to match CFG patterns that
40 represent logical and or logical or of two COND_EXPRs.
41 Transformations are done if the COND_EXPR conditions match
44 1. two single bit tests X & (1 << Yn) (for logical and)
46 2. two bit tests X & Yn (for logical or)
48 3. two comparisons X OPn Y (for logical or)
50 To simplify this pass, removing basic blocks and dead code
51 is left to CFG cleanup and DCE. */
54 /* Recognize a if-then-else CFG pattern starting to match with the
55 COND_BB basic-block containing the COND_EXPR. The recognized
56 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
57 *THEN_BB and/or *ELSE_BB are already set, they are required to
58 match the then and else basic-blocks to make the pattern match.
59 Returns true if the pattern matched, false otherwise. */
62 recognize_if_then_else (basic_block cond_bb,
63 basic_block *then_bb, basic_block *else_bb)
67 if (EDGE_COUNT (cond_bb->succs) != 2)
70 /* Find the then/else edges. */
71 t = EDGE_SUCC (cond_bb, 0);
72 e = EDGE_SUCC (cond_bb, 1);
73 if (!(t->flags & EDGE_TRUE_VALUE))
79 if (!(t->flags & EDGE_TRUE_VALUE)
80 || !(e->flags & EDGE_FALSE_VALUE))
83 /* Check if the edge destinations point to the required block. */
85 && t->dest != *then_bb)
88 && e->dest != *else_bb)
99 /* Verify if the basic block BB does not have side-effects. Return
100 true in this case, else false. */
103 bb_no_side_effects_p (basic_block bb)
105 block_stmt_iterator bsi;
107 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
109 tree stmt = bsi_stmt (bsi);
110 stmt_ann_t ann = stmt_ann (stmt);
112 if (ann->has_volatile_ops
113 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
120 /* Verify if all PHI node arguments in DEST for edges from BB1 or
121 BB2 to DEST are the same. This makes the CFG merge point
122 free from side-effects. Return true in this case, else false. */
125 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
127 edge e1 = find_edge (bb1, dest);
128 edge e2 = find_edge (bb2, dest);
131 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
132 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
133 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
139 /* Recognize a single bit test pattern in COND_EXPR and its defining
140 statements. Store the name being tested in *NAME and the bit
141 in *BIT. The COND_EXPR computes *NAME & (1 << *BIT).
142 Returns true if the pattern matched, false otherwise. */
145 recognize_single_bit_test (tree cond_expr, tree *name, tree *bit)
149 /* Get at the definition of the result of the bit test. */
150 t = TREE_OPERAND (cond_expr, 0);
151 if (TREE_CODE (t) == NE_EXPR
152 && integer_zerop (TREE_OPERAND (t, 1)))
153 t = TREE_OPERAND (t, 0);
154 if (TREE_CODE (t) != SSA_NAME)
156 t = SSA_NAME_DEF_STMT (t);
157 if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
159 t = GIMPLE_STMT_OPERAND (t, 1);
161 /* Look at which bit is tested. One form to recognize is
162 D.1985_5 = state_3(D) >> control1_4(D);
163 D.1986_6 = (int) D.1985_5;
165 if (D.1987_7 != 0) */
166 if (TREE_CODE (t) == BIT_AND_EXPR
167 && integer_onep (TREE_OPERAND (t, 1))
168 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
170 tree orig_name = TREE_OPERAND (t, 0);
172 /* Look through copies and conversions to eventually
173 find the stmt that computes the shift. */
176 t = SSA_NAME_DEF_STMT (t);
177 if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
179 t = GIMPLE_STMT_OPERAND (t, 1);
180 if (TREE_CODE (t) == NOP_EXPR
181 || TREE_CODE (t) == CONVERT_EXPR)
182 t = TREE_OPERAND (t, 0);
183 } while (TREE_CODE (t) == SSA_NAME);
185 /* If we found such, decompose it. */
186 if (TREE_CODE (t) == RSHIFT_EXPR)
188 /* op0 & (1 << op1) */
189 *bit = TREE_OPERAND (t, 1);
190 *name = TREE_OPERAND (t, 0);
195 *bit = integer_zero_node;
203 D.1987_7 = op0 & (1 << CST)
204 if (D.1987_7 != 0) */
205 if (TREE_CODE (t) == BIT_AND_EXPR
206 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
207 && integer_pow2p (TREE_OPERAND (t, 1)))
209 *name = TREE_OPERAND (t, 0);
210 *bit = build_int_cst (integer_type_node,
211 tree_log2 (TREE_OPERAND (t, 1)));
216 D.1986_6 = 1 << control1_4(D)
217 D.1987_7 = op0 & D.1986_6
218 if (D.1987_7 != 0) */
219 if (TREE_CODE (t) == BIT_AND_EXPR
220 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
221 && TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
225 /* Both arguments of the BIT_AND_EXPR can be the single-bit
226 specifying expression. */
227 tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 0));
228 if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
229 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
230 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
232 *name = TREE_OPERAND (t, 1);
233 *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
237 tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 1));
238 if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
239 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
240 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
242 *name = TREE_OPERAND (t, 0);
243 *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
251 /* Recognize a bit test pattern in COND_EXPR and its defining
252 statements. Store the name being tested in *NAME and the bits
253 in *BITS. The COND_EXPR computes *NAME & *BITS.
254 Returns true if the pattern matched, false otherwise. */
257 recognize_bits_test (tree cond_expr, tree *name, tree *bits)
261 /* Get at the definition of the result of the bit test. */
262 t = TREE_OPERAND (cond_expr, 0);
263 if (TREE_CODE (t) == NE_EXPR
264 && integer_zerop (TREE_OPERAND (t, 1)))
265 t = TREE_OPERAND (t, 0);
266 if (TREE_CODE (t) != SSA_NAME)
268 t = SSA_NAME_DEF_STMT (t);
269 if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
271 t = GIMPLE_STMT_OPERAND (t, 1);
273 if (TREE_CODE (t) != BIT_AND_EXPR)
276 *name = TREE_OPERAND (t, 0);
277 *bits = TREE_OPERAND (t, 1);
282 /* If-convert on a and pattern with a common else block. The inner
283 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
284 Returns true if the edges to the common else basic-block were merged. */
287 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
289 block_stmt_iterator bsi;
290 tree inner_cond, outer_cond;
291 tree name1, name2, bit1, bit2;
293 inner_cond = last_stmt (inner_cond_bb);
295 || TREE_CODE (inner_cond) != COND_EXPR)
298 outer_cond = last_stmt (outer_cond_bb);
300 || TREE_CODE (outer_cond) != COND_EXPR)
303 /* See if we test a single bit of the same name in both tests. In
304 that case remove the outer test, merging both else edges,
305 and change the inner one to test for
306 name & (bit1 | bit2) == (bit1 | bit2). */
307 if (recognize_single_bit_test (inner_cond, &name1, &bit1)
308 && recognize_single_bit_test (outer_cond, &name2, &bit2)
314 bsi = bsi_for_stmt (inner_cond);
315 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
316 integer_one_node, bit1);
317 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
318 integer_one_node, bit2);
319 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
320 t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
321 true, BSI_SAME_STMT);
322 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
323 t2 = force_gimple_operand_bsi (&bsi, t2, true, NULL_TREE,
324 true, BSI_SAME_STMT);
325 COND_EXPR_COND (inner_cond) = fold_build2 (EQ_EXPR, boolean_type_node,
327 update_stmt (inner_cond);
329 /* Leave CFG optimization to cfg_cleanup. */
330 COND_EXPR_COND (outer_cond) = boolean_true_node;
331 update_stmt (outer_cond);
335 fprintf (dump_file, "optimizing double bit test to ");
336 print_generic_expr (dump_file, name1, 0);
337 fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
338 print_generic_expr (dump_file, bit1, 0);
339 fprintf (dump_file, ") | (1 << ");
340 print_generic_expr (dump_file, bit2, 0);
341 fprintf (dump_file, ")\n");
350 /* If-convert on a or pattern with a common then block. The inner
351 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
352 Returns true, if the edges leading to the common then basic-block
356 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
358 tree inner_cond, outer_cond;
359 tree name1, name2, bits1, bits2;
361 inner_cond = last_stmt (inner_cond_bb);
363 || TREE_CODE (inner_cond) != COND_EXPR)
366 outer_cond = last_stmt (outer_cond_bb);
368 || TREE_CODE (outer_cond) != COND_EXPR)
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 if (recognize_bits_test (inner_cond, &name1, &bits1)
375 && recognize_bits_test (outer_cond, &name2, &bits2))
377 block_stmt_iterator bsi;
380 /* Find the common name which is bit-tested. */
383 else if (bits1 == bits2)
392 else if (name1 == bits2)
398 else if (bits1 == name2)
408 bsi = bsi_for_stmt (inner_cond);
409 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
410 t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
411 true, BSI_SAME_STMT);
412 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
413 t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
414 true, BSI_SAME_STMT);
415 COND_EXPR_COND (inner_cond) = fold_build2 (NE_EXPR, boolean_type_node, t,
416 build_int_cst (TREE_TYPE (t), 0));
417 update_stmt (inner_cond);
419 /* Leave CFG optimization to cfg_cleanup. */
420 COND_EXPR_COND (outer_cond) = boolean_false_node;
421 update_stmt (outer_cond);
425 fprintf (dump_file, "optimizing bits or bits test to ");
426 print_generic_expr (dump_file, name1, 0);
427 fprintf (dump_file, " & T != 0\nwith temporary T = ");
428 print_generic_expr (dump_file, bits1, 0);
429 fprintf (dump_file, " | ");
430 print_generic_expr (dump_file, bits2, 0);
431 fprintf (dump_file, "\n");
437 /* See if we have two comparisons that we can merge into one.
438 This happens for C++ operator overloading where for example
439 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
440 else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond))
441 && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond))
442 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 0),
443 TREE_OPERAND (COND_EXPR_COND (outer_cond), 0), 0)
444 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 1),
445 TREE_OPERAND (COND_EXPR_COND (outer_cond), 1), 0))
447 tree ccond1 = COND_EXPR_COND (inner_cond);
448 tree ccond2 = COND_EXPR_COND (outer_cond);
449 enum tree_code code1 = TREE_CODE (ccond1);
450 enum tree_code code2 = TREE_CODE (ccond2);
454 #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
455 || (code2 == a ## _EXPR && code1 == b ## _EXPR))
456 /* Merge the two condition codes if possible. */
459 else if (CHK (EQ, LT))
461 else if (CHK (EQ, GT))
463 else if (CHK (LT, LE))
465 else if (CHK (GT, GE))
467 else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1, 0)))
468 || flag_unsafe_math_optimizations)
472 else if (CHK (LT, NE))
474 else if (CHK (GT, NE))
479 /* We could check for combinations leading to trivial true/false. */
485 t = fold_build2 (code, boolean_type_node,
486 TREE_OPERAND (ccond2, 0), TREE_OPERAND (ccond2, 1));
487 COND_EXPR_COND (inner_cond) = t;
488 update_stmt (inner_cond);
490 /* Leave CFG optimization to cfg_cleanup. */
491 COND_EXPR_COND (outer_cond) = boolean_false_node;
492 update_stmt (outer_cond);
496 fprintf (dump_file, "optimizing two comparisons to ");
497 print_generic_expr (dump_file, t, 0);
498 fprintf (dump_file, "\n");
507 /* Recognize a CFG pattern and dispatch to the appropriate
508 if-conversion helper. We start with BB as the innermost
509 worker basic-block. Returns true if a transformation was done. */
512 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
514 basic_block then_bb = NULL, else_bb = NULL;
516 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
519 /* Recognize && and || of two conditions with a common
520 then/else block which entry edges we can merge. That is:
526 This requires a single predecessor of the inner cond_bb. */
527 if (single_pred_p (inner_cond_bb))
529 basic_block outer_cond_bb = single_pred (inner_cond_bb);
531 /* The && form is characterized by a common else_bb with
532 the two edges leading to it mergable. The latter is
533 guaranteed by matching PHI arguments in the else_bb and
534 the inner cond_bb having no side-effects. */
535 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
536 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
537 && bb_no_side_effects_p (inner_cond_bb))
541 if (q) goto inner_cond_bb; else goto else_bb;
543 if (p) goto ...; else goto else_bb;
548 return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
551 /* The || form is characterized by a common then_bb with the
552 two edges leading to it mergable. The latter is guaranteed
553 by matching PHI arguments in the then_bb and the inner cond_bb
554 having no side-effects. */
555 if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
556 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
557 && bb_no_side_effects_p (inner_cond_bb))
561 if (q) goto then_bb; else goto inner_cond_bb;
563 if (q) goto then_bb; else goto ...;
567 return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
574 /* Main entry for the tree if-conversion pass. */
577 tree_ssa_ifcombine (void)
580 bool cfg_changed = false;
583 bbs = blocks_in_phiopt_order ();
585 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
587 basic_block bb = bbs[i];
588 tree stmt = last_stmt (bb);
591 && TREE_CODE (stmt) == COND_EXPR)
592 cfg_changed |= tree_ssa_ifcombine_bb (bb);
597 return cfg_changed ? TODO_cleanup_cfg : 0;
601 gate_ifcombine (void)
606 struct tree_opt_pass pass_tree_ifcombine = {
607 "ifcombine", /* name */
608 gate_ifcombine, /* gate */
609 tree_ssa_ifcombine, /* execute */
612 0, /* static_pass_number */
613 TV_TREE_IFCOMBINE, /* tv_id */
614 PROP_cfg | PROP_ssa, /* properties_required */
615 0, /* properties_provided */
616 0, /* properties_destroyed */
617 0, /* todo_flags_start */
621 | TODO_verify_ssa, /* todo_flags_finish */