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 (CONVERT_EXPR_P (t
))
206 t
= TREE_OPERAND (t
, 0);
207 } while (TREE_CODE (t
) == SSA_NAME
);
209 /* If we found such, decompose it. */
210 if (TREE_CODE (t
) == RSHIFT_EXPR
)
212 /* op0 & (1 << op1) */
213 *bit
= TREE_OPERAND (t
, 1);
214 *name
= TREE_OPERAND (t
, 0);
219 *bit
= integer_zero_node
;
220 *name
= get_name_for_bit_test (orig_name
);
227 D.1987_7 = op0 & (1 << CST)
228 if (D.1987_7 != 0) */
229 if (TREE_CODE (t
) == BIT_AND_EXPR
230 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
231 && integer_pow2p (TREE_OPERAND (t
, 1)))
233 *name
= TREE_OPERAND (t
, 0);
234 *bit
= build_int_cst (integer_type_node
,
235 tree_log2 (TREE_OPERAND (t
, 1)));
240 D.1986_6 = 1 << control1_4(D)
241 D.1987_7 = op0 & D.1986_6
242 if (D.1987_7 != 0) */
243 if (TREE_CODE (t
) == BIT_AND_EXPR
244 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
245 && TREE_CODE (TREE_OPERAND (t
, 1)) == SSA_NAME
)
249 /* Both arguments of the BIT_AND_EXPR can be the single-bit
250 specifying expression. */
251 tmp
= SSA_NAME_DEF_STMT (TREE_OPERAND (t
, 0));
252 if (TREE_CODE (tmp
) == GIMPLE_MODIFY_STMT
253 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp
, 1)) == LSHIFT_EXPR
254 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 0)))
256 *name
= TREE_OPERAND (t
, 1);
257 *bit
= TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 1);
261 tmp
= SSA_NAME_DEF_STMT (TREE_OPERAND (t
, 1));
262 if (TREE_CODE (tmp
) == GIMPLE_MODIFY_STMT
263 && TREE_CODE (GIMPLE_STMT_OPERAND (tmp
, 1)) == LSHIFT_EXPR
264 && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 0)))
266 *name
= TREE_OPERAND (t
, 0);
267 *bit
= TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp
, 1), 1);
275 /* Recognize a bit test pattern in COND_EXPR and its defining
276 statements. Store the name being tested in *NAME and the bits
277 in *BITS. The COND_EXPR computes *NAME & *BITS.
278 Returns true if the pattern matched, false otherwise. */
281 recognize_bits_test (tree cond_expr
, tree
*name
, tree
*bits
)
285 /* Get at the definition of the result of the bit test. */
286 t
= TREE_OPERAND (cond_expr
, 0);
287 if (TREE_CODE (t
) == NE_EXPR
288 && integer_zerop (TREE_OPERAND (t
, 1)))
289 t
= TREE_OPERAND (t
, 0);
290 if (TREE_CODE (t
) != SSA_NAME
)
292 t
= SSA_NAME_DEF_STMT (t
);
293 if (TREE_CODE (t
) != GIMPLE_MODIFY_STMT
)
295 t
= GIMPLE_STMT_OPERAND (t
, 1);
297 if (TREE_CODE (t
) != BIT_AND_EXPR
)
300 *name
= get_name_for_bit_test (TREE_OPERAND (t
, 0));
301 *bits
= TREE_OPERAND (t
, 1);
306 /* If-convert on a and pattern with a common else block. The inner
307 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
308 Returns true if the edges to the common else basic-block were merged. */
311 ifcombine_ifandif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
313 block_stmt_iterator bsi
;
314 tree inner_cond
, outer_cond
;
315 tree name1
, name2
, bit1
, bit2
;
317 inner_cond
= last_stmt (inner_cond_bb
);
319 || TREE_CODE (inner_cond
) != COND_EXPR
)
322 outer_cond
= last_stmt (outer_cond_bb
);
324 || TREE_CODE (outer_cond
) != COND_EXPR
)
327 /* See if we test a single bit of the same name in both tests. In
328 that case remove the outer test, merging both else edges,
329 and change the inner one to test for
330 name & (bit1 | bit2) == (bit1 | bit2). */
331 if (recognize_single_bit_test (inner_cond
, &name1
, &bit1
)
332 && recognize_single_bit_test (outer_cond
, &name2
, &bit2
)
338 bsi
= bsi_for_stmt (inner_cond
);
339 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
340 build_int_cst (TREE_TYPE (name1
), 1), bit1
);
341 t2
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (name1
),
342 build_int_cst (TREE_TYPE (name1
), 1), bit2
);
343 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), t
, t2
);
344 t
= force_gimple_operand_bsi (&bsi
, t
, true, NULL_TREE
,
345 true, BSI_SAME_STMT
);
346 t2
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
347 t2
= force_gimple_operand_bsi (&bsi
, t2
, true, NULL_TREE
,
348 true, BSI_SAME_STMT
);
349 COND_EXPR_COND (inner_cond
) = fold_build2 (EQ_EXPR
, boolean_type_node
,
351 update_stmt (inner_cond
);
353 /* Leave CFG optimization to cfg_cleanup. */
354 COND_EXPR_COND (outer_cond
) = boolean_true_node
;
355 update_stmt (outer_cond
);
359 fprintf (dump_file
, "optimizing double bit test to ");
360 print_generic_expr (dump_file
, name1
, 0);
361 fprintf (dump_file
, " & T == T\nwith temporary T = (1 << ");
362 print_generic_expr (dump_file
, bit1
, 0);
363 fprintf (dump_file
, ") | (1 << ");
364 print_generic_expr (dump_file
, bit2
, 0);
365 fprintf (dump_file
, ")\n");
374 /* If-convert on a or pattern with a common then block. The inner
375 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
376 Returns true, if the edges leading to the common then basic-block
380 ifcombine_iforif (basic_block inner_cond_bb
, basic_block outer_cond_bb
)
382 tree inner_cond
, outer_cond
;
383 tree name1
, name2
, bits1
, bits2
;
385 inner_cond
= last_stmt (inner_cond_bb
);
387 || TREE_CODE (inner_cond
) != COND_EXPR
)
390 outer_cond
= last_stmt (outer_cond_bb
);
392 || TREE_CODE (outer_cond
) != COND_EXPR
)
395 /* See if we have two bit tests of the same name in both tests.
396 In that case remove the outer test and change the inner one to
397 test for name & (bits1 | bits2) != 0. */
398 if (recognize_bits_test (inner_cond
, &name1
, &bits1
)
399 && recognize_bits_test (outer_cond
, &name2
, &bits2
))
401 block_stmt_iterator bsi
;
404 /* Find the common name which is bit-tested. */
407 else if (bits1
== bits2
)
416 else if (name1
== bits2
)
422 else if (bits1
== name2
)
432 bsi
= bsi_for_stmt (inner_cond
);
433 t
= fold_build2 (BIT_IOR_EXPR
, TREE_TYPE (name1
), bits1
, bits2
);
434 t
= force_gimple_operand_bsi (&bsi
, t
, true, NULL_TREE
,
435 true, BSI_SAME_STMT
);
436 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (name1
), name1
, t
);
437 t
= force_gimple_operand_bsi (&bsi
, t
, true, NULL_TREE
,
438 true, BSI_SAME_STMT
);
439 COND_EXPR_COND (inner_cond
) = fold_build2 (NE_EXPR
, boolean_type_node
, t
,
440 build_int_cst (TREE_TYPE (t
), 0));
441 update_stmt (inner_cond
);
443 /* Leave CFG optimization to cfg_cleanup. */
444 COND_EXPR_COND (outer_cond
) = boolean_false_node
;
445 update_stmt (outer_cond
);
449 fprintf (dump_file
, "optimizing bits or bits test to ");
450 print_generic_expr (dump_file
, name1
, 0);
451 fprintf (dump_file
, " & T != 0\nwith temporary T = ");
452 print_generic_expr (dump_file
, bits1
, 0);
453 fprintf (dump_file
, " | ");
454 print_generic_expr (dump_file
, bits2
, 0);
455 fprintf (dump_file
, "\n");
461 /* See if we have two comparisons that we can merge into one.
462 This happens for C++ operator overloading where for example
463 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
464 else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond
))
465 && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond
))
466 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond
), 0),
467 TREE_OPERAND (COND_EXPR_COND (outer_cond
), 0), 0)
468 && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond
), 1),
469 TREE_OPERAND (COND_EXPR_COND (outer_cond
), 1), 0))
471 tree ccond1
= COND_EXPR_COND (inner_cond
);
472 tree ccond2
= COND_EXPR_COND (outer_cond
);
473 enum tree_code code1
= TREE_CODE (ccond1
);
474 enum tree_code code2
= TREE_CODE (ccond2
);
478 #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
479 || (code2 == a ## _EXPR && code1 == b ## _EXPR))
480 /* Merge the two condition codes if possible. */
483 else if (CHK (EQ
, LT
))
485 else if (CHK (EQ
, GT
))
487 else if (CHK (LT
, LE
))
489 else if (CHK (GT
, GE
))
491 else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1
, 0)))
492 || flag_unsafe_math_optimizations
)
496 else if (CHK (LT
, NE
))
498 else if (CHK (GT
, NE
))
503 /* We could check for combinations leading to trivial true/false. */
509 t
= fold_build2 (code
, boolean_type_node
,
510 TREE_OPERAND (ccond2
, 0), TREE_OPERAND (ccond2
, 1));
511 t
= canonicalize_cond_expr_cond (t
);
514 COND_EXPR_COND (inner_cond
) = t
;
515 update_stmt (inner_cond
);
517 /* Leave CFG optimization to cfg_cleanup. */
518 COND_EXPR_COND (outer_cond
) = boolean_false_node
;
519 update_stmt (outer_cond
);
523 fprintf (dump_file
, "optimizing two comparisons to ");
524 print_generic_expr (dump_file
, t
, 0);
525 fprintf (dump_file
, "\n");
534 /* Recognize a CFG pattern and dispatch to the appropriate
535 if-conversion helper. We start with BB as the innermost
536 worker basic-block. Returns true if a transformation was done. */
539 tree_ssa_ifcombine_bb (basic_block inner_cond_bb
)
541 basic_block then_bb
= NULL
, else_bb
= NULL
;
543 if (!recognize_if_then_else (inner_cond_bb
, &then_bb
, &else_bb
))
546 /* Recognize && and || of two conditions with a common
547 then/else block which entry edges we can merge. That is:
553 This requires a single predecessor of the inner cond_bb. */
554 if (single_pred_p (inner_cond_bb
))
556 basic_block outer_cond_bb
= single_pred (inner_cond_bb
);
558 /* The && form is characterized by a common else_bb with
559 the two edges leading to it mergable. The latter is
560 guaranteed by matching PHI arguments in the else_bb and
561 the inner cond_bb having no side-effects. */
562 if (recognize_if_then_else (outer_cond_bb
, &inner_cond_bb
, &else_bb
)
563 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, else_bb
)
564 && bb_no_side_effects_p (inner_cond_bb
))
568 if (q) goto inner_cond_bb; else goto else_bb;
570 if (p) goto ...; else goto else_bb;
575 return ifcombine_ifandif (inner_cond_bb
, outer_cond_bb
);
578 /* The || form is characterized by a common then_bb with the
579 two edges leading to it mergable. The latter is guaranteed
580 by matching PHI arguments in the then_bb and the inner cond_bb
581 having no side-effects. */
582 if (recognize_if_then_else (outer_cond_bb
, &then_bb
, &inner_cond_bb
)
583 && same_phi_args_p (outer_cond_bb
, inner_cond_bb
, then_bb
)
584 && bb_no_side_effects_p (inner_cond_bb
))
588 if (q) goto then_bb; else goto inner_cond_bb;
590 if (q) goto then_bb; else goto ...;
594 return ifcombine_iforif (inner_cond_bb
, outer_cond_bb
);
601 /* Main entry for the tree if-conversion pass. */
604 tree_ssa_ifcombine (void)
607 bool cfg_changed
= false;
610 bbs
= blocks_in_phiopt_order ();
612 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; ++i
)
614 basic_block bb
= bbs
[i
];
615 tree stmt
= last_stmt (bb
);
618 && TREE_CODE (stmt
) == COND_EXPR
)
619 cfg_changed
|= tree_ssa_ifcombine_bb (bb
);
624 return cfg_changed
? TODO_cleanup_cfg
: 0;
628 gate_ifcombine (void)
633 struct gimple_opt_pass pass_tree_ifcombine
=
637 "ifcombine", /* name */
638 gate_ifcombine
, /* gate */
639 tree_ssa_ifcombine
, /* execute */
642 0, /* static_pass_number */
643 TV_TREE_IFCOMBINE
, /* tv_id */
644 PROP_cfg
| PROP_ssa
, /* properties_required */
645 0, /* properties_provided */
646 0, /* properties_destroyed */
647 0, /* todo_flags_start */
651 | TODO_verify_ssa
/* todo_flags_finish */