gcc/tree-ssa-ifcombine.c

   1 /* Combining of if-expressions on trees.
   2    Copyright (C) 2007, 2008 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 #include "tree.h"
  26 #include "basic-block.h"
  27 #include "timevar.h"
  28 #include "diagnostic.h"
  29 #include "tree-flow.h"
  30 #include "tree-pass.h"
  31 #include "tree-dump.h"
  32
  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.
  36
  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
  41    either
  42
  43      1. two single bit tests X & (1 << Yn) (for logical and)
  44
  45      2. two bit tests X & Yn (for logical or)
  46
  47      3. two comparisons X OPn Y (for logical or)
  48
  49    To simplify this pass, removing basic blocks and dead code
  50    is left to CFG cleanup and DCE.  */
  51
  52
  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.  */
  59
  60 static bool
  61 recognize_if_then_else (basic_block cond_bb,
  62                         basic_block *then_bb, basic_block *else_bb)
  63 {
  64   edge t, e;
  65
  66   if (EDGE_COUNT (cond_bb->succs) != 2)
  67     return false;
  68
  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))
  73     {
  74       edge tmp = t;
  75       t = e;
  76       e = tmp;
  77     }
  78   if (!(t->flags & EDGE_TRUE_VALUE)
  79       || !(e->flags & EDGE_FALSE_VALUE))
  80     return false;
  81
  82   /* Check if the edge destinations point to the required block.  */
  83   if (*then_bb
  84       && t->dest != *then_bb)
  85     return false;
  86   if (*else_bb
  87       && e->dest != *else_bb)
  88     return false;
  89
  90   if (!*then_bb)
  91     *then_bb = t->dest;
  92   if (!*else_bb)
  93     *else_bb = e->dest;
  94
  95   return true;
  96 }
  97
  98 /* Verify if the basic block BB does not have side-effects.  Return
  99    true in this case, else false.  */
 100
 101 static bool
 102 bb_no_side_effects_p (basic_block bb)
 103 {
 104   gimple_stmt_iterator gsi;
 105
 106   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 107     {
 108       gimple stmt = gsi_stmt (gsi);
 109
 110       if (gimple_has_volatile_ops (stmt)
 111           || gimple_vuse (stmt))
 112         return false;
 113     }
 114
 115   return true;
 116 }
 117
 118 /* Verify if all PHI node arguments in DEST for edges from BB1 or
 119    BB2 to DEST are the same.  This makes the CFG merge point
 120    free from side-effects.  Return true in this case, else false.  */
 121
 122 static bool
 123 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
 124 {
 125   edge e1 = find_edge (bb1, dest);
 126   edge e2 = find_edge (bb2, dest);
 127   gimple_stmt_iterator gsi;
 128   gimple phi;
 129
 130   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
 131     {
 132       phi = gsi_stmt (gsi);
 133       if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
 134                             PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
 135         return false;
 136     }
 137
 138   return true;
 139 }
 140
 141 /* Return the best representative SSA name for CANDIDATE which is used
 142    in a bit test.  */
 143
 144 static tree
 145 get_name_for_bit_test (tree candidate)
 146 {
 147   /* Skip single-use names in favor of using the name from a
 148      non-widening conversion definition.  */
 149   if (TREE_CODE (candidate) == SSA_NAME
 150       && has_single_use (candidate))
 151     {
 152       gimple def_stmt = SSA_NAME_DEF_STMT (candidate);
 153       if (is_gimple_assign (def_stmt)
 154           && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
 155         {
 156           if (TYPE_PRECISION (TREE_TYPE (candidate))
 157               <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 158             return gimple_assign_rhs1 (def_stmt);
 159         }
 160     }
 161
 162   return candidate;
 163 }
 164
 165 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
 166    statements.  Store the name being tested in *NAME and the bit
 167    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
 168    Returns true if the pattern matched, false otherwise.  */
 169
 170 static bool
 171 recognize_single_bit_test (gimple cond, tree *name, tree *bit)
 172 {
 173   gimple stmt;
 174
 175   /* Get at the definition of the result of the bit test.  */
 176   if (gimple_cond_code (cond) != NE_EXPR
 177       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
 178       || !integer_zerop (gimple_cond_rhs (cond)))
 179     return false;
 180   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
 181   if (!is_gimple_assign (stmt))
 182     return false;
 183
 184   /* Look at which bit is tested.  One form to recognize is
 185      D.1985_5 = state_3(D) >> control1_4(D);
 186      D.1986_6 = (int) D.1985_5;
 187      D.1987_7 = op0 & 1;
 188      if (D.1987_7 != 0)  */
 189   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 190       && integer_onep (gimple_assign_rhs2 (stmt))
 191       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
 192     {
 193       tree orig_name = gimple_assign_rhs1 (stmt);
 194
 195       /* Look through copies and conversions to eventually
 196          find the stmt that computes the shift.  */
 197       stmt = SSA_NAME_DEF_STMT (orig_name);
 198
 199       while (is_gimple_assign (stmt)
 200              && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
 201                   && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
 202                       <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
 203                  || gimple_assign_ssa_name_copy_p (stmt)))
 204         stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
 205
 206       /* If we found such, decompose it.  */
 207       if (is_gimple_assign (stmt)
 208           && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
 209         {
 210           /* op0 & (1 << op1) */
 211           *bit = gimple_assign_rhs2 (stmt);
 212           *name = gimple_assign_rhs1 (stmt);
 213         }
 214       else
 215         {
 216           /* t & 1 */
 217           *bit = integer_zero_node;
 218           *name = get_name_for_bit_test (orig_name);
 219         }
 220
 221       return true;
 222     }
 223
 224   /* Another form is
 225      D.1987_7 = op0 & (1 << CST)
 226      if (D.1987_7 != 0)  */
 227   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 228       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 229       && integer_pow2p (gimple_assign_rhs2 (stmt)))
 230     {
 231       *name = gimple_assign_rhs1 (stmt);
 232       *bit = build_int_cst (integer_type_node,
 233                             tree_log2 (gimple_assign_rhs2 (stmt)));
 234       return true;
 235     }
 236
 237   /* Another form is
 238      D.1986_6 = 1 << control1_4(D)
 239      D.1987_7 = op0 & D.1986_6
 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       && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
 244     {
 245       gimple tmp;
 246
 247       /* Both arguments of the BIT_AND_EXPR can be the single-bit
 248          specifying expression.  */
 249       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
 250       if (is_gimple_assign (tmp)
 251           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
 252           && integer_onep (gimple_assign_rhs1 (tmp)))
 253         {
 254           *name = gimple_assign_rhs2 (stmt);
 255           *bit = gimple_assign_rhs2 (tmp);
 256           return true;
 257         }
 258
 259       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
 260       if (is_gimple_assign (tmp)
 261           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
 262           && integer_onep (gimple_assign_rhs1 (tmp)))
 263         {
 264           *name = gimple_assign_rhs1 (stmt);
 265           *bit = gimple_assign_rhs2 (tmp);
 266           return true;
 267         }
 268     }
 269
 270   return false;
 271 }
 272
 273 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
 274    statements.  Store the name being tested in *NAME and the bits
 275    in *BITS.  The COND_EXPR computes *NAME & *BITS.
 276    Returns true if the pattern matched, false otherwise.  */
 277
 278 static bool
 279 recognize_bits_test (gimple cond, tree *name, tree *bits)
 280 {
 281   gimple stmt;
 282
 283   /* Get at the definition of the result of the bit test.  */
 284   if (gimple_cond_code (cond) != NE_EXPR
 285       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
 286       || !integer_zerop (gimple_cond_rhs (cond)))
 287     return false;
 288   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
 289   if (!is_gimple_assign (stmt)
 290       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
 291     return false;
 292
 293   *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
 294   *bits = gimple_assign_rhs2 (stmt);
 295
 296   return true;
 297 }
 298
 299 /* If-convert on a and pattern with a common else block.  The inner
 300    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 301    Returns true if the edges to the common else basic-block were merged.  */
 302
 303 static bool
 304 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 305 {
 306   gimple_stmt_iterator gsi;
 307   gimple inner_cond, outer_cond;
 308   tree name1, name2, bit1, bit2;
 309
 310   inner_cond = last_stmt (inner_cond_bb);
 311   if (!inner_cond
 312       || gimple_code (inner_cond) != GIMPLE_COND)
 313     return false;
 314
 315   outer_cond = last_stmt (outer_cond_bb);
 316   if (!outer_cond
 317       || gimple_code (outer_cond) != GIMPLE_COND)
 318     return false;
 319
 320   /* See if we test a single bit of the same name in both tests.  In
 321      that case remove the outer test, merging both else edges,
 322      and change the inner one to test for
 323      name & (bit1 | bit2) == (bit1 | bit2).  */
 324   if (recognize_single_bit_test (inner_cond, &name1, &bit1)
 325       && recognize_single_bit_test (outer_cond, &name2, &bit2)
 326       && name1 == name2)
 327     {
 328       tree t, t2;
 329
 330       /* Do it.  */
 331       gsi = gsi_for_stmt (inner_cond);
 332       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 333                        build_int_cst (TREE_TYPE (name1), 1), bit1);
 334       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 335                         build_int_cst (TREE_TYPE (name1), 1), bit2);
 336       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
 337       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 338                                     true, GSI_SAME_STMT);
 339       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 340       t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
 341                                      true, GSI_SAME_STMT);
 342       t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
 343       t = canonicalize_cond_expr_cond (t);
 344       if (!t)
 345         return false;
 346       gimple_cond_set_condition_from_tree (inner_cond, t);
 347       update_stmt (inner_cond);
 348
 349       /* Leave CFG optimization to cfg_cleanup.  */
 350       gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
 351       update_stmt (outer_cond);
 352
 353       if (dump_file)
 354         {
 355           fprintf (dump_file, "optimizing double bit test to ");
 356           print_generic_expr (dump_file, name1, 0);
 357           fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
 358           print_generic_expr (dump_file, bit1, 0);
 359           fprintf (dump_file, ") | (1 << ");
 360           print_generic_expr (dump_file, bit2, 0);
 361           fprintf (dump_file, ")\n");
 362         }
 363
 364       return true;
 365     }
 366
 367   /* See if we have two comparisons that we can merge into one.  */
 368   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 369            && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
 370            && operand_equal_p (gimple_cond_lhs (inner_cond),
 371                                gimple_cond_lhs (outer_cond), 0)
 372            && operand_equal_p (gimple_cond_rhs (inner_cond),
 373                                gimple_cond_rhs (outer_cond), 0))
 374     {
 375       enum tree_code code1 = gimple_cond_code (inner_cond);
 376       enum tree_code code2 = gimple_cond_code (outer_cond);
 377       tree t;
 378
 379       if (!(t = combine_comparisons (UNKNOWN_LOCATION,
 380                                      TRUTH_ANDIF_EXPR, code1, code2,
 381                                      boolean_type_node,
 382                                      gimple_cond_lhs (outer_cond),
 383                                      gimple_cond_rhs (outer_cond))))
 384         return false;
 385       t = canonicalize_cond_expr_cond (t);
 386       if (!t)
 387         return false;
 388       gimple_cond_set_condition_from_tree (inner_cond, t);
 389       update_stmt (inner_cond);
 390
 391       /* Leave CFG optimization to cfg_cleanup.  */
 392       gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
 393       update_stmt (outer_cond);
 394
 395       if (dump_file)
 396         {
 397           fprintf (dump_file, "optimizing two comparisons to ");
 398           print_generic_expr (dump_file, t, 0);
 399           fprintf (dump_file, "\n");
 400         }
 401
 402       return true;
 403     }
 404
 405   return false;
 406 }
 407
 408 /* If-convert on a or pattern with a common then block.  The inner
 409    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 410    Returns true, if the edges leading to the common then basic-block
 411    were merged.  */
 412
 413 static bool
 414 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 415 {
 416   gimple inner_cond, outer_cond;
 417   tree name1, name2, bits1, bits2;
 418
 419   inner_cond = last_stmt (inner_cond_bb);
 420   if (!inner_cond
 421       || gimple_code (inner_cond) != GIMPLE_COND)
 422     return false;
 423
 424   outer_cond = last_stmt (outer_cond_bb);
 425   if (!outer_cond
 426       || gimple_code (outer_cond) != GIMPLE_COND)
 427     return false;
 428
 429   /* See if we have two bit tests of the same name in both tests.
 430      In that case remove the outer test and change the inner one to
 431      test for name & (bits1 | bits2) != 0.  */
 432   if (recognize_bits_test (inner_cond, &name1, &bits1)
 433       && recognize_bits_test (outer_cond, &name2, &bits2))
 434     {
 435       gimple_stmt_iterator gsi;
 436       tree t;
 437
 438       /* Find the common name which is bit-tested.  */
 439       if (name1 == name2)
 440         ;
 441       else if (bits1 == bits2)
 442         {
 443           t = name2;
 444           name2 = bits2;
 445           bits2 = t;
 446           t = name1;
 447           name1 = bits1;
 448           bits1 = t;
 449         }
 450       else if (name1 == bits2)
 451         {
 452           t = name2;
 453           name2 = bits2;
 454           bits2 = t;
 455         }
 456       else if (bits1 == name2)
 457         {
 458           t = name1;
 459           name1 = bits1;
 460           bits1 = t;
 461         }
 462       else
 463         return false;
 464
 465       /* As we strip non-widening conversions in finding a common
 466          name that is tested make sure to end up with an integral
 467          type for building the bit operations.  */
 468       if (TYPE_PRECISION (TREE_TYPE (bits1))
 469           >= TYPE_PRECISION (TREE_TYPE (bits2)))
 470         {
 471           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
 472           name1 = fold_convert (TREE_TYPE (bits1), name1);
 473           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
 474           bits2 = fold_convert (TREE_TYPE (bits1), bits2);
 475         }
 476       else
 477         {
 478           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
 479           name1 = fold_convert (TREE_TYPE (bits2), name1);
 480           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
 481           bits1 = fold_convert (TREE_TYPE (bits2), bits1);
 482         }
 483
 484       /* Do it.  */
 485       gsi = gsi_for_stmt (inner_cond);
 486       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
 487       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 488                                     true, GSI_SAME_STMT);
 489       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 490       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 491                                     true, GSI_SAME_STMT);
 492       t = fold_build2 (NE_EXPR, boolean_type_node, t,
 493                        build_int_cst (TREE_TYPE (t), 0));
 494       t = canonicalize_cond_expr_cond (t);
 495       if (!t)
 496         return false;
 497       gimple_cond_set_condition_from_tree (inner_cond, t);
 498       update_stmt (inner_cond);
 499
 500       /* Leave CFG optimization to cfg_cleanup.  */
 501       gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
 502       update_stmt (outer_cond);
 503
 504       if (dump_file)
 505         {
 506           fprintf (dump_file, "optimizing bits or bits test to ");
 507           print_generic_expr (dump_file, name1, 0);
 508           fprintf (dump_file, " & T != 0\nwith temporary T = ");
 509           print_generic_expr (dump_file, bits1, 0);
 510           fprintf (dump_file, " | ");
 511           print_generic_expr (dump_file, bits2, 0);
 512           fprintf (dump_file, "\n");
 513         }
 514
 515       return true;
 516     }
 517
 518   /* See if we have two comparisons that we can merge into one.
 519      This happens for C++ operator overloading where for example
 520      GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
 521   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 522            && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
 523            && operand_equal_p (gimple_cond_lhs (inner_cond),
 524                                gimple_cond_lhs (outer_cond), 0)
 525            && operand_equal_p (gimple_cond_rhs (inner_cond),
 526                                gimple_cond_rhs (outer_cond), 0))
 527     {
 528       enum tree_code code1 = gimple_cond_code (inner_cond);
 529       enum tree_code code2 = gimple_cond_code (outer_cond);
 530       tree t;
 531
 532       if (!(t = combine_comparisons (UNKNOWN_LOCATION,
 533                                      TRUTH_ORIF_EXPR, code1, code2,
 534                                      boolean_type_node,
 535                                      gimple_cond_lhs (outer_cond),
 536                                      gimple_cond_rhs (outer_cond))))
 537         return false;
 538       t = canonicalize_cond_expr_cond (t);
 539       if (!t)
 540         return false;
 541       gimple_cond_set_condition_from_tree (inner_cond, t);
 542       update_stmt (inner_cond);
 543
 544       /* Leave CFG optimization to cfg_cleanup.  */
 545       gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
 546       update_stmt (outer_cond);
 547
 548       if (dump_file)
 549         {
 550           fprintf (dump_file, "optimizing two comparisons to ");
 551           print_generic_expr (dump_file, t, 0);
 552           fprintf (dump_file, "\n");
 553         }
 554
 555       return true;
 556     }
 557
 558   return false;
 559 }
 560
 561 /* Recognize a CFG pattern and dispatch to the appropriate
 562    if-conversion helper.  We start with BB as the innermost
 563    worker basic-block.  Returns true if a transformation was done.  */
 564
 565 static bool
 566 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 567 {
 568   basic_block then_bb = NULL, else_bb = NULL;
 569
 570   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
 571     return false;
 572
 573   /* Recognize && and || of two conditions with a common
 574      then/else block which entry edges we can merge.  That is:
 575        if (a || b)
 576          ;
 577      and
 578        if (a && b)
 579          ;
 580      This requires a single predecessor of the inner cond_bb.  */
 581   if (single_pred_p (inner_cond_bb))
 582     {
 583       basic_block outer_cond_bb = single_pred (inner_cond_bb);
 584
 585       /* The && form is characterized by a common else_bb with
 586          the two edges leading to it mergable.  The latter is
 587          guaranteed by matching PHI arguments in the else_bb and
 588          the inner cond_bb having no side-effects.  */
 589       if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
 590           && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
 591           && bb_no_side_effects_p (inner_cond_bb))
 592         {
 593           /* We have
 594                <outer_cond_bb>
 595                  if (q) goto inner_cond_bb; else goto else_bb;
 596                <inner_cond_bb>
 597                  if (p) goto ...; else goto else_bb;
 598                  ...
 599                <else_bb>
 600                  ...
 601            */
 602           return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
 603         }
 604
 605       /* The || form is characterized by a common then_bb with the
 606          two edges leading to it mergable.  The latter is guaranteed
 607          by matching PHI arguments in the then_bb and the inner cond_bb
 608          having no side-effects.  */
 609       if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
 610           && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
 611           && bb_no_side_effects_p (inner_cond_bb))
 612         {
 613           /* We have
 614                <outer_cond_bb>
 615                  if (q) goto then_bb; else goto inner_cond_bb;
 616                <inner_cond_bb>
 617                  if (q) goto then_bb; else goto ...;
 618                <then_bb>
 619                  ...
 620            */
 621           return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
 622         }
 623     }
 624
 625   return false;
 626 }
 627
 628 /* Main entry for the tree if-conversion pass.  */
 629
 630 static unsigned int
 631 tree_ssa_ifcombine (void)
 632 {
 633   basic_block *bbs;
 634   bool cfg_changed = false;
 635   int i;
 636
 637   bbs = blocks_in_phiopt_order ();
 638
 639   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
 640     {
 641       basic_block bb = bbs[i];
 642       gimple stmt = last_stmt (bb);
 643
 644       if (stmt
 645           && gimple_code (stmt) == GIMPLE_COND)
 646         cfg_changed |= tree_ssa_ifcombine_bb (bb);
 647     }
 648
 649   free (bbs);
 650
 651   return cfg_changed ? TODO_cleanup_cfg : 0;
 652 }
 653
 654 static bool
 655 gate_ifcombine (void)
 656 {
 657   return 1;
 658 }
 659
 660 struct gimple_opt_pass pass_tree_ifcombine =
 661 {
 662  {
 663   GIMPLE_PASS,
 664   "ifcombine",                  /* name */
 665   gate_ifcombine,               /* gate */
 666   tree_ssa_ifcombine,           /* execute */
 667   NULL,                         /* sub */
 668   NULL,                         /* next */
 669   0,                            /* static_pass_number */
 670   TV_TREE_IFCOMBINE,            /* tv_id */
 671   PROP_cfg | PROP_ssa,          /* properties_required */
 672   0,                            /* properties_provided */
 673   0,                            /* properties_destroyed */
 674   0,                            /* todo_flags_start */
 675   TODO_dump_func
 676   | TODO_ggc_collect
 677   | TODO_update_ssa
 678   | TODO_verify_ssa             /* todo_flags_finish */
 679  }
 680 };