gcc/tree-ssa-ifcombine.c

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