1/* Combining of if-expressions on trees.
2 Copyright (C) 2007-2017 Free Software Foundation, Inc.
3 Contributed by Richard Guenther <rguenther@suse.de>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "rtl.h"
26#include "tree.h"
27#include "gimple.h"
28#include "cfghooks.h"
29#include "tree-pass.h"
30#include "memmodel.h"
31#include "tm_p.h"
32#include "ssa.h"
33#include "tree-pretty-print.h"
34/* rtl is needed only because arm back-end requires it for
35 BRANCH_COST. */
36#include "fold-const.h"
37#include "cfganal.h"
38#include "gimple-fold.h"
39#include "gimple-iterator.h"
40#include "gimplify-me.h"
41#include "tree-cfg.h"
42#include "tree-ssa.h"
43
44#ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
45#define LOGICAL_OP_NON_SHORT_CIRCUIT \
46 (BRANCH_COST (optimize_function_for_speed_p (cfun), \
47 false) >= 2)
48#endif
49
50/* This pass combines COND_EXPRs to simplify control flow. It
51 currently recognizes bit tests and comparisons in chains that
52 represent logical and or logical or of two COND_EXPRs.
53
54 It does so by walking basic blocks in a approximate reverse
55 post-dominator order and trying to match CFG patterns that
56 represent logical and or logical or of two COND_EXPRs.
57 Transformations are done if the COND_EXPR conditions match
58 either
59
60 1. two single bit tests X & (1 << Yn) (for logical and)
61
62 2. two bit tests X & Yn (for logical or)
63
64 3. two comparisons X OPn Y (for logical or)
65
66 To simplify this pass, removing basic blocks and dead code
67 is left to CFG cleanup and DCE. */
68
69
70/* Recognize a if-then-else CFG pattern starting to match with the
71 COND_BB basic-block containing the COND_EXPR. The recognized
72 then end else blocks are stored to *THEN_BB and *ELSE_BB. If
73 *THEN_BB and/or *ELSE_BB are already set, they are required to
74 match the then and else basic-blocks to make the pattern match.
75 Returns true if the pattern matched, false otherwise. */
76
77static bool
78recognize_if_then_else (basic_block cond_bb,
79 basic_block *then_bb, basic_block *else_bb)
80{
81 edge t, e;
82
83 if (EDGE_COUNT (cond_bb->succs) != 2)
84 return false;
85
86 /* Find the then/else edges. */
87 t = EDGE_SUCC (cond_bb, 0);
88 e = EDGE_SUCC (cond_bb, 1);
89 if (!(t->flags & EDGE_TRUE_VALUE))
90 std::swap (t, e);
91 if (!(t->flags & EDGE_TRUE_VALUE)
92 || !(e->flags & EDGE_FALSE_VALUE))
93 return false;
94
95 /* Check if the edge destinations point to the required block. */
96 if (*then_bb
97 && t->dest != *then_bb)
98 return false;
99 if (*else_bb
100 && e->dest != *else_bb)
101 return false;
102
103 if (!*then_bb)
104 *then_bb = t->dest;
105 if (!*else_bb)
106 *else_bb = e->dest;
107
108 return true;
109}
110
111/* Verify if the basic block BB does not have side-effects. Return
112 true in this case, else false. */
113
114static bool
115bb_no_side_effects_p (basic_block bb)
116{
117 gimple_stmt_iterator gsi;
118
119 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
120 {
121 gimple *stmt = gsi_stmt (gsi);
122
123 if (is_gimple_debug (stmt))
124 continue;
125
126 if (gimple_has_side_effects (stmt)
127 || gimple_uses_undefined_value_p (stmt)
128 || gimple_could_trap_p (stmt)
129 || gimple_vuse (stmt)
130 /* const calls don't match any of the above, yet they could
131 still have some side-effects - they could contain
132 gimple_could_trap_p statements, like floating point
133 exceptions or integer division by zero. See PR70586.
134 FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
135 should handle this. */
136 || is_gimple_call (stmt))
137 return false;
138 }
139
140 return true;
141}
142
143/* Return true if BB is an empty forwarder block to TO_BB. */
144
145static bool
146forwarder_block_to (basic_block bb, basic_block to_bb)
147{
148 return empty_block_p (bb)
149 && single_succ_p (bb)
150 && single_succ (bb) == to_bb;
151}
152
153/* Verify if all PHI node arguments in DEST for edges from BB1 or
154 BB2 to DEST are the same. This makes the CFG merge point
155 free from side-effects. Return true in this case, else false. */
156
157static bool
158same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
159{
160 edge e1 = find_edge (bb1, dest);
161 edge e2 = find_edge (bb2, dest);
162 gphi_iterator gsi;
163 gphi *phi;
164
165 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
166 {
167 phi = gsi.phi ();
168 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
169 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
170 return false;
171 }
172
173 return true;
174}
175
176/* Return the best representative SSA name for CANDIDATE which is used
177 in a bit test. */
178
179static tree
180get_name_for_bit_test (tree candidate)
181{
182 /* Skip single-use names in favor of using the name from a
183 non-widening conversion definition. */
184 if (TREE_CODE (candidate) == SSA_NAME
185 && has_single_use (candidate))
186 {
187 gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
188 if (is_gimple_assign (def_stmt)
189 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
190 {
191 if (TYPE_PRECISION (TREE_TYPE (candidate))
192 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
193 return gimple_assign_rhs1 (def_stmt);
194 }
195 }
196
197 return candidate;
198}
199
200/* Recognize a single bit test pattern in GIMPLE_COND and its defining
201 statements. Store the name being tested in *NAME and the bit
202 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
203 Returns true if the pattern matched, false otherwise. */
204
205static bool
206recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
207{
208 gimple *stmt;
209
210 /* Get at the definition of the result of the bit test. */
211 if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
212 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
213 || !integer_zerop (gimple_cond_rhs (cond)))
214 return false;
215 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
216 if (!is_gimple_assign (stmt))
217 return false;
218
219 /* Look at which bit is tested. One form to recognize is
220 D.1985_5 = state_3(D) >> control1_4(D);
221 D.1986_6 = (int) D.1985_5;
222 D.1987_7 = op0 & 1;
223 if (D.1987_7 != 0) */
224 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
225 && integer_onep (gimple_assign_rhs2 (stmt))
226 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
227 {
228 tree orig_name = gimple_assign_rhs1 (stmt);
229
230 /* Look through copies and conversions to eventually
231 find the stmt that computes the shift. */
232 stmt = SSA_NAME_DEF_STMT (orig_name);
233
234 while (is_gimple_assign (stmt)
235 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
236 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
237 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
238 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
239 || gimple_assign_ssa_name_copy_p (stmt)))
240 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
241
242 /* If we found such, decompose it. */
243 if (is_gimple_assign (stmt)
244 && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
245 {
246 /* op0 & (1 << op1) */
247 *bit = gimple_assign_rhs2 (stmt);
248 *name = gimple_assign_rhs1 (stmt);
249 }
250 else
251 {
252 /* t & 1 */
253 *bit = integer_zero_node;
254 *name = get_name_for_bit_test (orig_name);
255 }
256
257 return true;
258 }
259
260 /* Another form is
261 D.1987_7 = op0 & (1 << CST)
262 if (D.1987_7 != 0) */
263 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
264 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
265 && integer_pow2p (gimple_assign_rhs2 (stmt)))
266 {
267 *name = gimple_assign_rhs1 (stmt);
268 *bit = build_int_cst (integer_type_node,
269 tree_log2 (gimple_assign_rhs2 (stmt)));
270 return true;
271 }
272
273 /* Another form is
274 D.1986_6 = 1 << control1_4(D)
275 D.1987_7 = op0 & D.1986_6
276 if (D.1987_7 != 0) */
277 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
278 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
279 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
280 {
281 gimple *tmp;
282
283 /* Both arguments of the BIT_AND_EXPR can be the single-bit
284 specifying expression. */
285 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
286 if (is_gimple_assign (tmp)
287 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
288 && integer_onep (gimple_assign_rhs1 (tmp)))
289 {
290 *name = gimple_assign_rhs2 (stmt);
291 *bit = gimple_assign_rhs2 (tmp);
292 return true;
293 }
294
295 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
296 if (is_gimple_assign (tmp)
297 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
298 && integer_onep (gimple_assign_rhs1 (tmp)))
299 {
300 *name = gimple_assign_rhs1 (stmt);
301 *bit = gimple_assign_rhs2 (tmp);
302 return true;
303 }
304 }
305
306 return false;
307}
308
309/* Recognize a bit test pattern in a GIMPLE_COND and its defining
310 statements. Store the name being tested in *NAME and the bits
311 in *BITS. The COND_EXPR computes *NAME & *BITS.
312 Returns true if the pattern matched, false otherwise. */
313
314static bool
315recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
316{
317 gimple *stmt;
318
319 /* Get at the definition of the result of the bit test. */
320 if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
321 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
322 || !integer_zerop (gimple_cond_rhs (cond)))
323 return false;
324 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
325 if (!is_gimple_assign (stmt)
326 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
327 return false;
328
329 *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
330 *bits = gimple_assign_rhs2 (stmt);
331
332 return true;
333}
334
335
336/* Update profile after code in outer_cond_bb was adjusted so
337 outer_cond_bb has no condition. */
338
339static void
340update_profile_after_ifcombine (basic_block inner_cond_bb,
341 basic_block outer_cond_bb)
342{
343 edge outer_to_inner = find_edge (outer_cond_bb, inner_cond_bb);
344 edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
345 ? EDGE_SUCC (outer_cond_bb, 1)
346 : EDGE_SUCC (outer_cond_bb, 0));
347 edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
348 edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
349
350 if (inner_taken->dest != outer2->dest)
351 std::swap (inner_taken, inner_not_taken);
352 gcc_assert (inner_taken->dest == outer2->dest);
353
354 /* In the following we assume that inner_cond_bb has single predecessor. */
355 gcc_assert (single_pred_p (inner_cond_bb));
356
357 /* Path outer_cond_bb->(outer2) needs to be merged into path
358 outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
359 and probability of inner_not_taken updated. */
360
361 inner_cond_bb->count = outer_cond_bb->count;
362
363 inner_taken->probability = outer2->probability + outer_to_inner->probability
364 * inner_taken->probability;
365 inner_not_taken->probability = profile_probability::always ()
366 - inner_taken->probability;
367
368 outer_to_inner->probability = profile_probability::always ();
369 outer2->probability = profile_probability::never ();
370}
371
372/* If-convert on a and pattern with a common else block. The inner
373 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
374 inner_inv, outer_inv and result_inv indicate whether the conditions
375 are inverted.
376 Returns true if the edges to the common else basic-block were merged. */
377
378static bool
379ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
380 basic_block outer_cond_bb, bool outer_inv, bool result_inv)
381{
382 gimple_stmt_iterator gsi;
383 gimple *inner_stmt, *outer_stmt;
384 gcond *inner_cond, *outer_cond;
385 tree name1, name2, bit1, bit2, bits1, bits2;
386
387 inner_stmt = last_stmt (inner_cond_bb);
388 if (!inner_stmt
389 || gimple_code (inner_stmt) != GIMPLE_COND)
390 return false;
391 inner_cond = as_a <gcond *> (inner_stmt);
392
393 outer_stmt = last_stmt (outer_cond_bb);
394 if (!outer_stmt
395 || gimple_code (outer_stmt) != GIMPLE_COND)
396 return false;
397 outer_cond = as_a <gcond *> (outer_stmt);
398
399 /* See if we test a single bit of the same name in both tests. In
400 that case remove the outer test, merging both else edges,
401 and change the inner one to test for
402 name & (bit1 | bit2) == (bit1 | bit2). */
403 if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
404 && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
405 && name1 == name2)
406 {
407 tree t, t2;
408
409 /* Do it. */
410 gsi = gsi_for_stmt (inner_cond);
411 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
412 build_int_cst (TREE_TYPE (name1), 1), bit1);
413 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
414 build_int_cst (TREE_TYPE (name1), 1), bit2);
415 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
416 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
417 true, GSI_SAME_STMT);
418 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
419 t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
420 true, GSI_SAME_STMT);
421 t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
422 boolean_type_node, t2, t);
423 t = canonicalize_cond_expr_cond (t);
424 if (!t)
425 return false;
426 gimple_cond_set_condition_from_tree (inner_cond, t);
427 update_stmt (inner_cond);
428
429 /* Leave CFG optimization to cfg_cleanup. */
430 gimple_cond_set_condition_from_tree (outer_cond,
431 outer_inv ? boolean_false_node : boolean_true_node);
432 update_stmt (outer_cond);
433
434 update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
435
436 if (dump_file)
437 {
438 fprintf (dump_file, "optimizing double bit test to ");
439 print_generic_expr (dump_file, name1);
440 fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
441 print_generic_expr (dump_file, bit1);
442 fprintf (dump_file, ") | (1 << ");
443 print_generic_expr (dump_file, bit2);
444 fprintf (dump_file, ")\n");
445 }
446
447 return true;
448 }
449
450 /* See if we have two bit tests of the same name in both tests.
451 In that case remove the outer test and change the inner one to
452 test for name & (bits1 | bits2) != 0. */
453 else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
454 && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
455 {
456 gimple_stmt_iterator gsi;
457 tree t;
458
459 /* Find the common name which is bit-tested. */
460 if (name1 == name2)
461 ;
462 else if (bits1 == bits2)
463 {
464 std::swap (name2, bits2);
465 std::swap (name1, bits1);
466 }
467 else if (name1 == bits2)
468 std::swap (name2, bits2);
469 else if (bits1 == name2)
470 std::swap (name1, bits1);
471 else
472 return false;
473
474 /* As we strip non-widening conversions in finding a common
475 name that is tested make sure to end up with an integral
476 type for building the bit operations. */
477 if (TYPE_PRECISION (TREE_TYPE (bits1))
478 >= TYPE_PRECISION (TREE_TYPE (bits2)))
479 {
480 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
481 name1 = fold_convert (TREE_TYPE (bits1), name1);
482 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
483 bits2 = fold_convert (TREE_TYPE (bits1), bits2);
484 }
485 else
486 {
487 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
488 name1 = fold_convert (TREE_TYPE (bits2), name1);
489 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
490 bits1 = fold_convert (TREE_TYPE (bits2), bits1);
491 }
492
493 /* Do it. */
494 gsi = gsi_for_stmt (inner_cond);
495 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
496 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
497 true, GSI_SAME_STMT);
498 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
499 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
500 true, GSI_SAME_STMT);
501 t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t,
502 build_int_cst (TREE_TYPE (t), 0));
503 t = canonicalize_cond_expr_cond (t);
504 if (!t)
505 return false;
506 gimple_cond_set_condition_from_tree (inner_cond, t);
507 update_stmt (inner_cond);
508
509 /* Leave CFG optimization to cfg_cleanup. */
510 gimple_cond_set_condition_from_tree (outer_cond,
511 outer_inv ? boolean_false_node : boolean_true_node);
512 update_stmt (outer_cond);
513 update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
514
515 if (dump_file)
516 {
517 fprintf (dump_file, "optimizing bits or bits test to ");
518 print_generic_expr (dump_file, name1);
519 fprintf (dump_file, " & T != 0\nwith temporary T = ");
520 print_generic_expr (dump_file, bits1);
521 fprintf (dump_file, " | ");
522 print_generic_expr (dump_file, bits2);
523 fprintf (dump_file, "\n");
524 }
525
526 return true;
527 }
528
529 /* See if we have two comparisons that we can merge into one. */
530 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
531 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
532 {
533 tree t;
534 enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
535 enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
536
537 /* Invert comparisons if necessary (and possible). */
538 if (inner_inv)
539 inner_cond_code = invert_tree_comparison (inner_cond_code,
540 HONOR_NANS (gimple_cond_lhs (inner_cond)));
541 if (inner_cond_code == ERROR_MARK)
542 return false;
543 if (outer_inv)
544 outer_cond_code = invert_tree_comparison (outer_cond_code,
545 HONOR_NANS (gimple_cond_lhs (outer_cond)));
546 if (outer_cond_code == ERROR_MARK)
547 return false;
548 /* Don't return false so fast, try maybe_fold_or_comparisons? */
549
550 if (!(t = maybe_fold_and_comparisons (inner_cond_code,
551 gimple_cond_lhs (inner_cond),
552 gimple_cond_rhs (inner_cond),
553 outer_cond_code,
554 gimple_cond_lhs (outer_cond),
555 gimple_cond_rhs (outer_cond))))
556 {
557 tree t1, t2;
558 gimple_stmt_iterator gsi;
559 if (!LOGICAL_OP_NON_SHORT_CIRCUIT || flag_sanitize_coverage)
560 return false;
561 /* Only do this optimization if the inner bb contains only the conditional. */
562 if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb)))
563 return false;
564 t1 = fold_build2_loc (gimple_location (inner_cond),
565 inner_cond_code,
566 boolean_type_node,
567 gimple_cond_lhs (inner_cond),
568 gimple_cond_rhs (inner_cond));
569 t2 = fold_build2_loc (gimple_location (outer_cond),
570 outer_cond_code,
571 boolean_type_node,
572 gimple_cond_lhs (outer_cond),
573 gimple_cond_rhs (outer_cond));
574 t = fold_build2_loc (gimple_location (inner_cond),
575 TRUTH_AND_EXPR, boolean_type_node, t1, t2);
576 if (result_inv)
577 {
578 t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
579 result_inv = false;
580 }
581 gsi = gsi_for_stmt (inner_cond);
582 t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr, NULL, true,
583 GSI_SAME_STMT);
584 }
585 if (result_inv)
586 t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
587 t = canonicalize_cond_expr_cond (t);
588 if (!t)
589 return false;
590 gimple_cond_set_condition_from_tree (inner_cond, t);
591 update_stmt (inner_cond);
592
593 /* Leave CFG optimization to cfg_cleanup. */
594 gimple_cond_set_condition_from_tree (outer_cond,
595 outer_inv ? boolean_false_node : boolean_true_node);
596 update_stmt (outer_cond);
597 update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
598
599 if (dump_file)
600 {
601 fprintf (dump_file, "optimizing two comparisons to ");
602 print_generic_expr (dump_file, t);
603 fprintf (dump_file, "\n");
604 }
605
606 return true;
607 }
608
609 return false;
610}
611
612/* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
613 dispatch to the appropriate if-conversion helper for a particular
614 set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
615 PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */
616
617static bool
618tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
619 basic_block then_bb, basic_block else_bb,
620 basic_block phi_pred_bb)
621{
622 /* The && form is characterized by a common else_bb with
623 the two edges leading to it mergable. The latter is
624 guaranteed by matching PHI arguments in the else_bb and
625 the inner cond_bb having no side-effects. */
626 if (phi_pred_bb != else_bb
627 && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
628 && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
629 {
630 /* We have
631 <outer_cond_bb>
632 if (q) goto inner_cond_bb; else goto else_bb;
633 <inner_cond_bb>
634 if (p) goto ...; else goto else_bb;
635 ...
636 <else_bb>
637 ...
638 */
639 return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false,
640 false);
641 }
642
643 /* And a version where the outer condition is negated. */
644 if (phi_pred_bb != else_bb
645 && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
646 && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
647 {
648 /* We have
649 <outer_cond_bb>
650 if (q) goto else_bb; else goto inner_cond_bb;
651 <inner_cond_bb>
652 if (p) goto ...; else goto else_bb;
653 ...
654 <else_bb>
655 ...
656 */
657 return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true,
658 false);
659 }
660
661 /* The || form is characterized by a common then_bb with the
662 two edges leading to it mergable. The latter is guaranteed
663 by matching PHI arguments in the then_bb and the inner cond_bb
664 having no side-effects. */
665 if (phi_pred_bb != then_bb
666 && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
667 && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
668 {
669 /* We have
670 <outer_cond_bb>
671 if (q) goto then_bb; else goto inner_cond_bb;
672 <inner_cond_bb>
673 if (q) goto then_bb; else goto ...;
674 <then_bb>
675 ...
676 */
677 return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true,
678 true);
679 }
680
681 /* And a version where the outer condition is negated. */
682 if (phi_pred_bb != then_bb
683 && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
684 && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
685 {
686 /* We have
687 <outer_cond_bb>
688 if (q) goto inner_cond_bb; else goto then_bb;
689 <inner_cond_bb>
690 if (q) goto then_bb; else goto ...;
691 <then_bb>
692 ...
693 */
694 return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
695 true);
696 }
697
698 return false;
699}
700
701/* Recognize a CFG pattern and dispatch to the appropriate
702 if-conversion helper. We start with BB as the innermost
703 worker basic-block. Returns true if a transformation was done. */
704
705static bool
706tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
707{
708 basic_block then_bb = NULL, else_bb = NULL;
709
710 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
711 return false;
712
713 /* Recognize && and || of two conditions with a common
714 then/else block which entry edges we can merge. That is:
715 if (a || b)
716 ;
717 and
718 if (a && b)
719 ;
720 This requires a single predecessor of the inner cond_bb. */
721 if (single_pred_p (inner_cond_bb)
722 && bb_no_side_effects_p (inner_cond_bb))
723 {
724 basic_block outer_cond_bb = single_pred (inner_cond_bb);
725
726 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
727 then_bb, else_bb, inner_cond_bb))
728 return true;
729
730 if (forwarder_block_to (else_bb, then_bb))
731 {
732 /* Other possibilities for the && form, if else_bb is
733 empty forwarder block to then_bb. Compared to the above simpler
734 forms this can be treated as if then_bb and else_bb were swapped,
735 and the corresponding inner_cond_bb not inverted because of that.
736 For same_phi_args_p we look at equality of arguments between
737 edge from outer_cond_bb and the forwarder block. */
738 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
739 then_bb, else_bb))
740 return true;
741 }
742 else if (forwarder_block_to (then_bb, else_bb))
743 {
744 /* Other possibilities for the || form, if then_bb is
745 empty forwarder block to else_bb. Compared to the above simpler
746 forms this can be treated as if then_bb and else_bb were swapped,
747 and the corresponding inner_cond_bb not inverted because of that.
748 For same_phi_args_p we look at equality of arguments between
749 edge from outer_cond_bb and the forwarder block. */
750 if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
751 then_bb, then_bb))
752 return true;
753 }
754 }
755
756 return false;
757}
758
759/* Main entry for the tree if-conversion pass. */
760
761namespace {
762
763const pass_data pass_data_tree_ifcombine =
764{
765 GIMPLE_PASS, /* type */
766 "ifcombine", /* name */
767 OPTGROUP_NONE, /* optinfo_flags */
768 TV_TREE_IFCOMBINE, /* tv_id */
769 ( PROP_cfg | PROP_ssa ), /* properties_required */
770 0, /* properties_provided */
771 0, /* properties_destroyed */
772 0, /* todo_flags_start */
773 TODO_update_ssa, /* todo_flags_finish */
774};
775
776class pass_tree_ifcombine : public gimple_opt_pass
777{
778public:
779 pass_tree_ifcombine (gcc::context *ctxt)
780 : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
781 {}
782
783 /* opt_pass methods: */
784 virtual unsigned int execute (function *);
785
786}; // class pass_tree_ifcombine
787
788unsigned int
789pass_tree_ifcombine::execute (function *fun)
790{
791 basic_block *bbs;
792 bool cfg_changed = false;
793 int i;
794
795 bbs = single_pred_before_succ_order ();
796 calculate_dominance_info (CDI_DOMINATORS);
797
798 /* Search every basic block for COND_EXPR we may be able to optimize.
799
800 We walk the blocks in order that guarantees that a block with
801 a single predecessor is processed after the predecessor.
802 This ensures that we collapse outter ifs before visiting the
803 inner ones, and also that we do not try to visit a removed
804 block. This is opposite of PHI-OPT, because we cascade the
805 combining rather than cascading PHIs. */
806 for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
807 {
808 basic_block bb = bbs[i];
809 gimple *stmt = last_stmt (bb);
810
811 if (stmt
812 && gimple_code (stmt) == GIMPLE_COND)
813 if (tree_ssa_ifcombine_bb (bb))
814 {
815 /* Clear range info from all stmts in BB which is now executed
816 conditional on a always true/false condition. */
817 reset_flow_sensitive_info_in_bb (bb);
818 cfg_changed |= true;
819 }
820 }
821
822 free (bbs);
823
824 return cfg_changed ? TODO_cleanup_cfg : 0;
825}
826
827} // anon namespace
828
829gimple_opt_pass *
830make_pass_tree_ifcombine (gcc::context *ctxt)
831{
832 return new pass_tree_ifcombine (ctxt);
833}
834