gcc/tree-ssa-ifcombine.c

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