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