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 && CONVERT_EXPR_P (GIMPLE_STMT_OPERAND (def_stmt
, 1)))
153 tree rhs
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
154 if (TYPE_PRECISION (TREE_TYPE (rhs
))
155 <= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
156 return TREE_OPERAND (rhs
, 0);
163 /* Recognize a single bit test pattern in COND_EXPR and its defining
164 statements. Store the name being tested in *NAME and the bit
165 in *BIT. The COND_EXPR computes *NAME & (1 << *BIT).
166 Returns true if the pattern matched, false otherwise. */
169 recognize_single_bit_test (tree cond_expr
, tree
*name
, tree
*bit
)
173 /* Get at the definition of the result of the bit test. */
174 t
= TREE_OPERAND (cond_expr
, 0);
175 if (TREE_CODE (t
) == NE_EXPR
176 && integer_zerop (TREE_OPERAND (t
, 1)))
177 t
= TREE_OPERAND (t
, 0);
178 if (TREE_CODE (t
) != SSA_NAME
)
180 t
= SSA_NAME_DEF_STMT (t
);
181 if (TREE_CODE (t
) != GIMPLE_MODIFY_STMT
)
183 t
= GIMPLE_STMT_OPERAND (t
, 1);
185 /* Look at which bit is tested. One form to recognize is
186 D.1985_5 = state_3(D) >> control1_4(D);
187 D.1986_6 = (int) D.1985_5;
189 if (D.1987_7 != 0) */
190 if (TREE_CODE (t
) == BIT_AND_EXPR
191 && integer_onep (TREE_OPERAND (t
, 1))
192 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
194 tree orig_name
= TREE_OPERAND (t
, 0);
196 /* Look through copies and conversions to eventually
197 find the stmt that computes the shift. */
200 t
= SSA_NAME_DEF_STMT (t
);
201 if (TREE_CODE (t
) != GIMPLE_MODIFY_STMT
)
203 t
= GIMPLE_STMT_OPERAND (t
, 1);
204 if (CONVERT_EXPR_P (t
))
205 t
= TREE_OPERAND (t
, 0);
206 } while (TREE_CODE (t
) == SSA_NAME
);
208 /* If we found such, decompose it. */
209 if (TREE_CODE (t
) == RSHIFT_EXPR
)
211 /* op0 & (1 << op1) */
212 *bit
= TREE_OPERAND (t
, 1);
213 *name
= TREE_OPERAND (t
, 0);
218 *bit
= integer_zero_node
;
219 *name
= get_name_for_bit_test (orig_name
);
226 D.1987_7 = op0 & (1 << CST)
227 if (D.1987_7 != 0) */
228 if (TREE_CODE (t
) == BIT_AND_EXPR
229 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
230 && integer_pow2p (TREE_OPERAND (t
, 1)))
232 *name
= TREE_OPERAND (t
, 0);
233 *bit
= build_int_cst (integer_type_node
,
234 tree_log2 (TREE_OPERAND (t
, 1)));
239 D.1986_6 = 1 << control1_4(D)
240 D.1987_7 = op0 & D.1986_6
241 if (D.1987_7 != 0) */
242 if (TREE_CODE (t
) == BIT_AND_EXPR
243 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
244 && TREE_CODE (TREE_OPERAND (t
, 1)) == SSA_NAME
)
248 /* Both arguments of the BIT_AND_EXPR can be the single-bit
249 specifying expression. */
250 tmp
= SSA_NAME_DEF_STMT (TREE_OPERAND (t
, 0));
251 if (TREE_CODE (tmp
) == GIMPLE_MODIFY_STMT
252 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp
, 1)) == LSHIFT_EXPR
253 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 0)))
255 *name
= TREE_OPERAND (t
, 1);
256 *bit
= TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 1);
260 tmp
= SSA_NAME_DEF_STMT (TREE_OPERAND (t
, 1));
261 if (TREE_CODE (tmp
) == GIMPLE_MODIFY_STMT
262 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp
, 1)) == LSHIFT_EXPR
263 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 0)))
265 *name
= TREE_OPERAND (t
, 0);
266 *bit
= TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 1);
274 /* Recognize a bit test pattern in COND_EXPR and its defining
275 statements. Store the name being tested in *NAME and the bits
276 in *BITS. The COND_EXPR computes *NAME & *BITS.
277 Returns true if the pattern matched, false otherwise. */
280 recognize_bits_test (tree cond_expr
, tree
*name
, tree
*bits
)
284 /* Get at the definition of the result of the bit test. */
285 t
= TREE_OPERAND (cond_expr
, 0);
286 if (TREE_CODE (t
) == NE_EXPR
287 && integer_zerop (TREE_OPERAND (t
, 1)))
288 t
= TREE_OPERAND (t
, 0);
289 if (TREE_CODE (t
) != SSA_NAME
)
291 t
= SSA_NAME_DEF_STMT (t
);
292 if (TREE_CODE (t
) != GIMPLE_MODIFY_STMT
)
294 t
= GIMPLE_STMT_OPERAND (t
, 1);
296 if (TREE_CODE (t
) != BIT_AND_EXPR
)
299 *name
= get_name_for_bit_test (TREE_OPERAND (t
, 0));
300 *bits
= TREE_OPERAND (t
, 1);
305 /* If-convert on a and pattern with a common else block. The inner
306 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
307 Returns true if the edges to the common else basic-block were merged. */
310 ifcombine_ifandif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
312 block_stmt_iterator bsi
;
313 tree inner_cond
, outer_cond
;
314 tree name1
, name2
, bit1
, bit2
;
316 inner_cond
= last_stmt (inner_cond_bb
);
318 || TREE_CODE (inner_cond
) != COND_EXPR
)
321 outer_cond
= last_stmt (outer_cond_bb
);
323 || TREE_CODE (outer_cond
) != COND_EXPR
)
326 /* See if we test a single bit of the same name in both tests. In
327 that case remove the outer test, merging both else edges,
328 and change the inner one to test for
329 name & (bit1 | bit2) == (bit1 | bit2). */
330 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
)
331 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
)
337 bsi
= bsi_for_stmt (inner_cond
);
338 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
339 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
340 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
341 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
342 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
343 t
= force_gimple_operand_bsi (&bsi
, t
, true, NULL_TREE
,
344 true, BSI_SAME_STMT
);
345 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
346 t2
= force_gimple_operand_bsi (&bsi
, t2
, true, NULL_TREE
,
347 true, BSI_SAME_STMT
);
348 COND_EXPR_COND (inner_cond
) = fold_build2 (EQ_EXPR
, boolean_type_node
,
350 update_stmt (inner_cond
);
352 /* Leave CFG optimization to cfg_cleanup. */
353 COND_EXPR_COND (outer_cond
) = 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");
373 /* If-convert on a or pattern with a common then block. The inner
374 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
375 Returns true, if the edges leading to the common then basic-block
379 ifcombine_iforif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
381 tree inner_cond
, outer_cond
;
382 tree name1
, name2
, bits1
, bits2
;
384 inner_cond
= last_stmt (inner_cond_bb
);
386 || TREE_CODE (inner_cond
) != COND_EXPR
)
389 outer_cond
= last_stmt (outer_cond_bb
);
391 || TREE_CODE (outer_cond
) != COND_EXPR
)
394 /* See if we have two bit tests of the same name in both tests.
395 In that case remove the outer test and change the inner one to
396 test for name & (bits1 | bits2) != 0. */
397 if (recognize_bits_test (inner_cond
, &name1
, &bits1
)
398 && recognize_bits_test (outer_cond
, &name2
, &bits2
))
400 block_stmt_iterator bsi
;
403 /* Find the common name which is bit-tested. */
406 else if (bits1
== bits2
)
415 else if (name1
== bits2
)
421 else if (bits1
== name2
)
431 bsi
= bsi_for_stmt (inner_cond
);
432 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
433 t
= force_gimple_operand_bsi (&bsi
, t
, true, NULL_TREE
,
434 true, BSI_SAME_STMT
);
435 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
436 t
= force_gimple_operand_bsi (&bsi
, t
, true, NULL_TREE
,
437 true, BSI_SAME_STMT
);
438 COND_EXPR_COND (inner_cond
) = fold_build2 (NE_EXPR
, boolean_type_node
, t
,
439 build_int_cst (TREE_TYPE (t
), 0));
440 update_stmt (inner_cond
);
442 /* Leave CFG optimization to cfg_cleanup. */
443 COND_EXPR_COND (outer_cond
) = boolean_false_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 This happens for C++ operator overloading where for example
462 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
463 else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond
))
464 && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond
))
465 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond
), 0),
466 TREE_OPERAND (COND_EXPR_COND (outer_cond
), 0), 0)
467 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond
), 1),
468 TREE_OPERAND (COND_EXPR_COND (outer_cond
), 1), 0))
470 tree ccond1
= COND_EXPR_COND (inner_cond
);
471 tree ccond2
= COND_EXPR_COND (outer_cond
);
472 enum tree_code code1
= TREE_CODE (ccond1
);
473 enum tree_code code2
= TREE_CODE (ccond2
);
477 #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
478 || (code2 == a ## _EXPR && code1 == b ## _EXPR))
479 /* Merge the two condition codes if possible. */
482 else if (CHK (EQ
, LT
))
484 else if (CHK (EQ
, GT
))
486 else if (CHK (LT
, LE
))
488 else if (CHK (GT
, GE
))
490 else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1
, 0)))
491 || flag_unsafe_math_optimizations
)
495 else if (CHK (LT
, NE
))
497 else if (CHK (GT
, NE
))
502 /* We could check for combinations leading to trivial true/false. */
508 t
= fold_build2 (code
, boolean_type_node
,
509 TREE_OPERAND (ccond2
, 0), TREE_OPERAND (ccond2
, 1));
510 t
= canonicalize_cond_expr_cond (t
);
513 COND_EXPR_COND (inner_cond
) = t
;
514 update_stmt (inner_cond
);
516 /* Leave CFG optimization to cfg_cleanup. */
517 COND_EXPR_COND (outer_cond
) = boolean_false_node
;
518 update_stmt (outer_cond
);
522 fprintf (dump_file
, "optimizing two comparisons to ");
523 print_generic_expr (dump_file
, t
, 0);
524 fprintf (dump_file
, "\n");
533 /* Recognize a CFG pattern and dispatch to the appropriate
534 if-conversion helper. We start with BB as the innermost
535 worker basic-block. Returns true if a transformation was done. */
538 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
540 basic_block then_bb
= NULL
, else_bb
= NULL
;
542 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
545 /* Recognize && and || of two conditions with a common
546 then/else block which entry edges we can merge. That is:
552 This requires a single predecessor of the inner cond_bb. */
553 if (single_pred_p (inner_cond_bb
))
555 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
557 /* The && form is characterized by a common else_bb with
558 the two edges leading to it mergable. The latter is
559 guaranteed by matching PHI arguments in the else_bb and
560 the inner cond_bb having no side-effects. */
561 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
562 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
563 && bb_no_side_effects_p (inner_cond_bb
))
567 if (q) goto inner_cond_bb; else goto else_bb;
569 if (p) goto ...; else goto else_bb;
574 return ifcombine_ifandif (inner_cond_bb
, outer_cond_bb
);
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_iforif (inner_cond_bb
, outer_cond_bb
);
600 /* Main entry for the tree if-conversion pass. */
603 tree_ssa_ifcombine (void)
606 bool cfg_changed
= false;
609 bbs
= blocks_in_phiopt_order ();
611 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; ++i
)
613 basic_block bb
= bbs
[i
];
614 tree stmt
= last_stmt (bb
);
617 && TREE_CODE (stmt
) == COND_EXPR
)
618 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
623 return cfg_changed
? TODO_cleanup_cfg
: 0;
627 gate_ifcombine (void)
632 struct gimple_opt_pass pass_tree_ifcombine
=
636 "ifcombine", /* name */
637 gate_ifcombine
, /* gate */
638 tree_ssa_ifcombine
, /* execute */
641 0, /* static_pass_number */
642 TV_TREE_IFCOMBINE
, /* tv_id */
643 PROP_cfg
| PROP_ssa
, /* properties_required */
644 0, /* properties_provided */
645 0, /* properties_destroyed */
646 0, /* todo_flags_start */
650 | TODO_verify_ssa
/* todo_flags_finish */