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           && gimple_assign_cast_p (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 /* Helpers for recognize_single_bit_test defined mainly for source code
 166    formating.  */
 167
 168 static int
 169 operand_precision (tree t)
 170 {
 171   return TYPE_PRECISION (TREE_TYPE (t));
 172 }
 173
 174 static bool
 175 integral_operand_p (tree t)
 176 {
 177   return INTEGRAL_TYPE_P (TREE_TYPE (t));
 178 }
 179
 180 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
 181    statements.  Store the name being tested in *NAME and the bit
 182    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
 183    Returns true if the pattern matched, false otherwise.  */
 184
 185 static bool
 186 recognize_single_bit_test (gimple cond, tree *name, tree *bit)
 187 {
 188   gimple stmt;
 189
 190   /* Get at the definition of the result of the bit test.  */
 191   if (gimple_cond_code (cond) != NE_EXPR
 192       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
 193       || !integer_zerop (gimple_cond_rhs (cond)))
 194     return false;
 195   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
 196   if (!is_gimple_assign (stmt))
 197     return false;
 198
 199   /* Look at which bit is tested.  One form to recognize is
 200      D.1985_5 = state_3(D) >> control1_4(D);
 201      D.1986_6 = (int) D.1985_5;
 202      D.1987_7 = op0 & 1;
 203      if (D.1987_7 != 0)  */
 204   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 205       && integer_onep (gimple_assign_rhs2 (stmt))
 206       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
 207     {
 208       tree orig_name = gimple_assign_rhs1 (stmt);
 209
 210       /* Look through copies and conversions to eventually
 211          find the stmt that computes the shift.  */
 212       stmt = SSA_NAME_DEF_STMT (orig_name);
 213
 214       while (is_gimple_assign (stmt)
 215              && (gimple_assign_ssa_name_copy_p (stmt)
 216                  || (gimple_assign_cast_p (stmt)
 217                      && integral_operand_p (gimple_assign_lhs (stmt))
 218                      && integral_operand_p (gimple_assign_rhs1 (stmt))
 219                      && (operand_precision (gimple_assign_lhs (stmt))
 220                          <= operand_precision (gimple_assign_rhs1 (stmt))))))
 221         {
 222           stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
 223         }
 224
 225       /* If we found such, decompose it.  */
 226       if (is_gimple_assign (stmt)
 227           && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
 228         {
 229           /* op0 & (1 << op1) */
 230           *bit = gimple_assign_rhs2 (stmt);
 231           *name = gimple_assign_rhs1 (stmt);
 232         }
 233       else
 234         {
 235           /* t & 1 */
 236           *bit = integer_zero_node;
 237           *name = get_name_for_bit_test (orig_name);
 238         }
 239
 240       return true;
 241     }
 242
 243   /* Another form is
 244      D.1987_7 = op0 & (1 << CST)
 245      if (D.1987_7 != 0)  */
 246   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 247       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 248       && integer_pow2p (gimple_assign_rhs2 (stmt)))
 249     {
 250       *name = gimple_assign_rhs1 (stmt);
 251       *bit = build_int_cst (integer_type_node,
 252                             tree_log2 (gimple_assign_rhs2 (stmt)));
 253       return true;
 254     }
 255
 256   /* Another form is
 257      D.1986_6 = 1 << control1_4(D)
 258      D.1987_7 = op0 & D.1986_6
 259      if (D.1987_7 != 0)  */
 260   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 261       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 262       && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
 263     {
 264       gimple tmp;
 265
 266       /* Both arguments of the BIT_AND_EXPR can be the single-bit
 267          specifying expression.  */
 268       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
 269       if (is_gimple_assign (tmp)
 270           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
 271           && integer_onep (gimple_assign_rhs1 (tmp)))
 272         {
 273           *name = gimple_assign_rhs2 (stmt);
 274           *bit = gimple_assign_rhs2 (tmp);
 275           return true;
 276         }
 277
 278       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
 279       if (is_gimple_assign (tmp)
 280           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
 281           && integer_onep (gimple_assign_rhs1 (tmp)))
 282         {
 283           *name = gimple_assign_rhs1 (stmt);
 284           *bit = gimple_assign_rhs2 (tmp);
 285           return true;
 286         }
 287     }
 288
 289   return false;
 290 }
 291
 292 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
 293    statements.  Store the name being tested in *NAME and the bits
 294    in *BITS.  The COND_EXPR computes *NAME & *BITS.
 295    Returns true if the pattern matched, false otherwise.  */
 296
 297 static bool
 298 recognize_bits_test (gimple cond, tree *name, tree *bits)
 299 {
 300   gimple stmt;
 301
 302   /* Get at the definition of the result of the bit test.  */
 303   if (gimple_cond_code (cond) != NE_EXPR
 304       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
 305       || !integer_zerop (gimple_cond_rhs (cond)))
 306     return false;
 307   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
 308   if (!is_gimple_assign (stmt)
 309       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
 310     return false;
 311
 312   *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
 313   *bits = gimple_assign_rhs2 (stmt);
 314
 315   return true;
 316 }
 317
 318 /* If-convert on a and pattern with a common else block.  The inner
 319    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 320    Returns true if the edges to the common else basic-block were merged.  */
 321
 322 static bool
 323 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 324 {
 325   gimple_stmt_iterator gsi;
 326   gimple inner_cond, outer_cond;
 327   tree name1, name2, bit1, bit2;
 328
 329   inner_cond = last_stmt (inner_cond_bb);
 330   if (!inner_cond
 331       || gimple_code (inner_cond) != GIMPLE_COND)
 332     return false;
 333
 334   outer_cond = last_stmt (outer_cond_bb);
 335   if (!outer_cond
 336       || gimple_code (outer_cond) != GIMPLE_COND)
 337     return false;
 338
 339   /* See if we test a single bit of the same name in both tests.  In
 340      that case remove the outer test, merging both else edges,
 341      and change the inner one to test for
 342      name & (bit1 | bit2) == (bit1 | bit2).  */
 343   if (recognize_single_bit_test (inner_cond, &name1, &bit1)
 344       && recognize_single_bit_test (outer_cond, &name2, &bit2)
 345       && name1 == name2)
 346     {
 347       tree t, t2;
 348
 349       /* Do it.  */
 350       gsi = gsi_for_stmt (inner_cond);
 351       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 352                        build_int_cst (TREE_TYPE (name1), 1), bit1);
 353       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 354                         build_int_cst (TREE_TYPE (name1), 1), bit2);
 355       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
 356       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 357                                     true, GSI_SAME_STMT);
 358       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 359       t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
 360                                      true, GSI_SAME_STMT);
 361       t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
 362       gimple_cond_set_condition_from_tree (inner_cond, t);
 363       update_stmt (inner_cond);
 364
 365       /* Leave CFG optimization to cfg_cleanup.  */
 366       gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
 367       update_stmt (outer_cond);
 368
 369       if (dump_file)
 370         {
 371           fprintf (dump_file, "optimizing double bit test to ");
 372           print_generic_expr (dump_file, name1, 0);
 373           fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
 374           print_generic_expr (dump_file, bit1, 0);
 375           fprintf (dump_file, ") | (1 << ");
 376           print_generic_expr (dump_file, bit2, 0);
 377           fprintf (dump_file, ")\n");
 378         }
 379
 380       return true;
 381     }
 382
 383   /* See if we have two comparisons that we can merge into one.  */
 384   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 385            && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
 386            && operand_equal_p (gimple_cond_lhs (inner_cond),
 387                                gimple_cond_lhs (outer_cond), 0)
 388            && operand_equal_p (gimple_cond_rhs (inner_cond),
 389                                gimple_cond_rhs (outer_cond), 0))
 390     {
 391       enum tree_code code1 = gimple_cond_code (inner_cond);
 392       enum tree_code code2 = gimple_cond_code (outer_cond);
 393       tree t;
 394
 395       if (!(t = combine_comparisons (UNKNOWN_LOCATION,
 396                                      TRUTH_ANDIF_EXPR, code1, code2,
 397                                      boolean_type_node,
 398                                      gimple_cond_lhs (outer_cond),
 399                                      gimple_cond_rhs (outer_cond))))
 400         return false;
 401       t = canonicalize_cond_expr_cond (t);
 402       if (!t)
 403         return false;
 404       gimple_cond_set_condition_from_tree (inner_cond, t);
 405       update_stmt (inner_cond);
 406
 407       /* Leave CFG optimization to cfg_cleanup.  */
 408       gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
 409       update_stmt (outer_cond);
 410
 411       if (dump_file)
 412         {
 413           fprintf (dump_file, "optimizing two comparisons to ");
 414           print_generic_expr (dump_file, t, 0);
 415           fprintf (dump_file, "\n");
 416         }
 417
 418       return true;
 419     }
 420
 421   return false;
 422 }
 423
 424 /* If-convert on a or pattern with a common then block.  The inner
 425    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 426    Returns true, if the edges leading to the common then basic-block
 427    were merged.  */
 428
 429 static bool
 430 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 431 {
 432   gimple inner_cond, outer_cond;
 433   tree name1, name2, bits1, bits2;
 434
 435   inner_cond = last_stmt (inner_cond_bb);
 436   if (!inner_cond
 437       || gimple_code (inner_cond) != GIMPLE_COND)
 438     return false;
 439
 440   outer_cond = last_stmt (outer_cond_bb);
 441   if (!outer_cond
 442       || gimple_code (outer_cond) != GIMPLE_COND)
 443     return false;
 444
 445   /* See if we have two bit tests of the same name in both tests.
 446      In that case remove the outer test and change the inner one to
 447      test for name & (bits1 | bits2) != 0.  */
 448   if (recognize_bits_test (inner_cond, &name1, &bits1)
 449       && recognize_bits_test (outer_cond, &name2, &bits2))
 450     {
 451       gimple_stmt_iterator gsi;
 452       tree t;
 453
 454       /* Find the common name which is bit-tested.  */
 455       if (name1 == name2)
 456         ;
 457       else if (bits1 == bits2)
 458         {
 459           t = name2;
 460           name2 = bits2;
 461           bits2 = t;
 462           t = name1;
 463           name1 = bits1;
 464           bits1 = t;
 465         }
 466       else if (name1 == bits2)
 467         {
 468           t = name2;
 469           name2 = bits2;
 470           bits2 = t;
 471         }
 472       else if (bits1 == name2)
 473         {
 474           t = name1;
 475           name1 = bits1;
 476           bits1 = t;
 477         }
 478       else
 479         return false;
 480
 481       /* As we strip non-widening conversions in finding a common
 482          name that is tested make sure to end up with an integral
 483          type for building the bit operations.  */
 484       if (TYPE_PRECISION (TREE_TYPE (bits1))
 485           >= TYPE_PRECISION (TREE_TYPE (bits2)))
 486         {
 487           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
 488           name1 = fold_convert (TREE_TYPE (bits1), name1);
 489           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
 490           bits2 = fold_convert (TREE_TYPE (bits1), bits2);
 491         }
 492       else
 493         {
 494           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
 495           name1 = fold_convert (TREE_TYPE (bits2), name1);
 496           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
 497           bits1 = fold_convert (TREE_TYPE (bits2), bits1);
 498         }
 499
 500       /* Do it.  */
 501       gsi = gsi_for_stmt (inner_cond);
 502       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
 503       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 504                                     true, GSI_SAME_STMT);
 505       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 506       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 507                                     true, GSI_SAME_STMT);
 508       t = fold_build2 (NE_EXPR, boolean_type_node, t,
 509                        build_int_cst (TREE_TYPE (t), 0));
 510       gimple_cond_set_condition_from_tree (inner_cond, t);
 511       update_stmt (inner_cond);
 512
 513       /* Leave CFG optimization to cfg_cleanup.  */
 514       gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
 515       update_stmt (outer_cond);
 516
 517       if (dump_file)
 518         {
 519           fprintf (dump_file, "optimizing bits or bits test to ");
 520           print_generic_expr (dump_file, name1, 0);
 521           fprintf (dump_file, " & T != 0\nwith temporary T = ");
 522           print_generic_expr (dump_file, bits1, 0);
 523           fprintf (dump_file, " | ");
 524           print_generic_expr (dump_file, bits2, 0);
 525           fprintf (dump_file, "\n");
 526         }
 527
 528       return true;
 529     }
 530
 531   /* See if we have two comparisons that we can merge into one.
 532      This happens for C++ operator overloading where for example
 533      GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
 534   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 535            && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison
 536            && operand_equal_p (gimple_cond_lhs (inner_cond),
 537                                gimple_cond_lhs (outer_cond), 0)
 538            && operand_equal_p (gimple_cond_rhs (inner_cond),
 539                                gimple_cond_rhs (outer_cond), 0))
 540     {
 541       enum tree_code code1 = gimple_cond_code (inner_cond);
 542       enum tree_code code2 = gimple_cond_code (outer_cond);
 543       tree t;
 544
 545       if (!(t = combine_comparisons (UNKNOWN_LOCATION,
 546                                      TRUTH_ORIF_EXPR, code1, code2,
 547                                      boolean_type_node,
 548                                      gimple_cond_lhs (outer_cond),
 549                                      gimple_cond_rhs (outer_cond))))
 550         return false;
 551       t = canonicalize_cond_expr_cond (t);
 552       if (!t)
 553         return false;
 554       gimple_cond_set_condition_from_tree (inner_cond, t);
 555       update_stmt (inner_cond);
 556
 557       /* Leave CFG optimization to cfg_cleanup.  */
 558       gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
 559       update_stmt (outer_cond);
 560
 561       if (dump_file)
 562         {
 563           fprintf (dump_file, "optimizing two comparisons to ");
 564           print_generic_expr (dump_file, t, 0);
 565           fprintf (dump_file, "\n");
 566         }
 567
 568       return true;
 569     }
 570
 571   return false;
 572 }
 573
 574 /* Recognize a CFG pattern and dispatch to the appropriate
 575    if-conversion helper.  We start with BB as the innermost
 576    worker basic-block.  Returns true if a transformation was done.  */
 577
 578 static bool
 579 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 580 {
 581   basic_block then_bb = NULL, else_bb = NULL;
 582
 583   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
 584     return false;
 585
 586   /* Recognize && and || of two conditions with a common
 587      then/else block which entry edges we can merge.  That is:
 588        if (a || b)
 589          ;
 590      and
 591        if (a && b)
 592          ;
 593      This requires a single predecessor of the inner cond_bb.  */
 594   if (single_pred_p (inner_cond_bb))
 595     {
 596       basic_block outer_cond_bb = single_pred (inner_cond_bb);
 597
 598       /* The && form is characterized by a common else_bb with
 599          the two edges leading to it mergable.  The latter is
 600          guaranteed by matching PHI arguments in the else_bb and
 601          the inner cond_bb having no side-effects.  */
 602       if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
 603           && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
 604           && bb_no_side_effects_p (inner_cond_bb))
 605         {
 606           /* We have
 607                <outer_cond_bb>
 608                  if (q) goto inner_cond_bb; else goto else_bb;
 609                <inner_cond_bb>
 610                  if (p) goto ...; else goto else_bb;
 611                  ...
 612                <else_bb>
 613                  ...
 614            */
 615           return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
 616         }
 617
 618       /* The || form is characterized by a common then_bb with the
 619          two edges leading to it mergable.  The latter is guaranteed
 620          by matching PHI arguments in the then_bb and the inner cond_bb
 621          having no side-effects.  */
 622       if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
 623           && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
 624           && bb_no_side_effects_p (inner_cond_bb))
 625         {
 626           /* We have
 627                <outer_cond_bb>
 628                  if (q) goto then_bb; else goto inner_cond_bb;
 629                <inner_cond_bb>
 630                  if (q) goto then_bb; else goto ...;
 631                <then_bb>
 632                  ...
 633            */
 634           return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
 635         }
 636     }
 637
 638   return false;
 639 }
 640
 641 /* Main entry for the tree if-conversion pass.  */
 642
 643 static unsigned int
 644 tree_ssa_ifcombine (void)
 645 {
 646   basic_block *bbs;
 647   bool cfg_changed = false;
 648   int i;
 649
 650   bbs = blocks_in_phiopt_order ();
 651
 652   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
 653     {
 654       basic_block bb = bbs[i];
 655       gimple stmt = last_stmt (bb);
 656
 657       if (stmt
 658           && gimple_code (stmt) == GIMPLE_COND)
 659         cfg_changed |= tree_ssa_ifcombine_bb (bb);
 660     }
 661
 662   free (bbs);
 663
 664   return cfg_changed ? TODO_cleanup_cfg : 0;
 665 }
 666
 667 static bool
 668 gate_ifcombine (void)
 669 {
 670   return 1;
 671 }
 672
 673 struct gimple_opt_pass pass_tree_ifcombine =
 674 {
 675  {
 676   GIMPLE_PASS,
 677   "ifcombine",                  /* name */
 678   gate_ifcombine,               /* gate */
 679   tree_ssa_ifcombine,           /* execute */
 680   NULL,                         /* sub */
 681   NULL,                         /* next */
 682   0,                            /* static_pass_number */
 683   TV_TREE_IFCOMBINE,            /* tv_id */
 684   PROP_cfg | PROP_ssa,          /* properties_required */
 685   0,                            /* properties_provided */
 686   0,                            /* properties_destroyed */
 687   0,                            /* todo_flags_start */
 688   TODO_dump_func
 689   | TODO_ggc_collect
 690   | TODO_update_ssa
 691   | TODO_verify_ssa             /* todo_flags_finish */
 692  }
 693 };