gcc/tree-ssa-ifcombine.c

   1 /* Combining of if-expressions on trees.
   2    Copyright (C) 2007 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   block_stmt_iterator bsi;
 105
 106   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 107     {
 108       tree stmt = bsi_stmt (bsi);
 109       stmt_ann_t ann = stmt_ann (stmt);
 110
 111       if (ann->has_volatile_ops
 112           || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
 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   tree phi;
 129
 130   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 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   return true;
 136 }
 137
 138 /* Return the best representative SSA name for CANDIDATE which is used
 139    in a bit test.  */
 140
 141 static tree
 142 get_name_for_bit_test (tree candidate)
 143 {
 144   /* Skip single-use names in favor of using the name from a
 145      non-widening conversion definition.  */
 146   if (TREE_CODE (candidate) == SSA_NAME
 147       && has_single_use (candidate))
 148     {
 149       tree def_stmt = SSA_NAME_DEF_STMT (candidate);
 150       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
 151           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
 152               || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == CONVERT_EXPR))
 153         {
 154           tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
 155           if (TYPE_PRECISION (TREE_TYPE (rhs))
 156               <= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs, 0))))
 157             return TREE_OPERAND (rhs, 0);
 158         }
 159     }
 160
 161   return candidate;
 162 }
 163
 164 /* Recognize a single bit test pattern in COND_EXPR and its defining
 165    statements.  Store the name being tested in *NAME and the bit
 166    in *BIT.  The COND_EXPR computes *NAME & (1 << *BIT).
 167    Returns true if the pattern matched, false otherwise.  */
 168
 169 static bool
 170 recognize_single_bit_test (tree cond_expr, tree *name, tree *bit)
 171 {
 172   tree t;
 173
 174   /* Get at the definition of the result of the bit test.  */
 175   t = TREE_OPERAND (cond_expr, 0);
 176   if (TREE_CODE (t) == NE_EXPR
 177       && integer_zerop (TREE_OPERAND (t, 1)))
 178     t = TREE_OPERAND (t, 0);
 179   if (TREE_CODE (t) != SSA_NAME)
 180     return false;
 181   t = SSA_NAME_DEF_STMT (t);
 182   if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
 183     return false;
 184   t = GIMPLE_STMT_OPERAND (t, 1);
 185
 186   /* Look at which bit is tested.  One form to recognize is
 187      D.1985_5 = state_3(D) >> control1_4(D);
 188      D.1986_6 = (int) D.1985_5;
 189      D.1987_7 = op0 & 1;
 190      if (D.1987_7 != 0)  */
 191   if (TREE_CODE (t) == BIT_AND_EXPR
 192       && integer_onep (TREE_OPERAND (t, 1))
 193       && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
 194     {
 195       tree orig_name = TREE_OPERAND (t, 0);
 196
 197       /* Look through copies and conversions to eventually
 198          find the stmt that computes the shift.  */
 199       t = orig_name;
 200       do {
 201         t = SSA_NAME_DEF_STMT (t);
 202         if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
 203           break;
 204         t = GIMPLE_STMT_OPERAND (t, 1);
 205         if (TREE_CODE (t) == NOP_EXPR
 206             || TREE_CODE (t) == CONVERT_EXPR)
 207           t = TREE_OPERAND (t, 0);
 208       } while (TREE_CODE (t) == SSA_NAME);
 209
 210       /* If we found such, decompose it.  */
 211       if (TREE_CODE (t) == RSHIFT_EXPR)
 212         {
 213           /* op0 & (1 << op1) */
 214           *bit = TREE_OPERAND (t, 1);
 215           *name = TREE_OPERAND (t, 0);
 216         }
 217       else
 218         {
 219           /* t & 1 */
 220           *bit = integer_zero_node;
 221           *name = get_name_for_bit_test (orig_name);
 222         }
 223
 224       return true;
 225     }
 226
 227   /* Another form is
 228      D.1987_7 = op0 & (1 << CST)
 229      if (D.1987_7 != 0)  */
 230   if (TREE_CODE (t) == BIT_AND_EXPR
 231       && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 232       && integer_pow2p (TREE_OPERAND (t, 1)))
 233     {
 234       *name = TREE_OPERAND (t, 0);
 235       *bit = build_int_cst (integer_type_node,
 236                             tree_log2 (TREE_OPERAND (t, 1)));
 237       return true;
 238     }
 239
 240   /* Another form is
 241      D.1986_6 = 1 << control1_4(D)
 242      D.1987_7 = op0 & D.1986_6
 243      if (D.1987_7 != 0)  */
 244   if (TREE_CODE (t) == BIT_AND_EXPR
 245       && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 246       && TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
 247     {
 248       tree tmp;
 249
 250       /* Both arguments of the BIT_AND_EXPR can be the single-bit
 251          specifying expression.  */
 252       tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 0));
 253       if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
 254           && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
 255           && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
 256         {
 257           *name = TREE_OPERAND (t, 1);
 258           *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
 259           return true;
 260         }
 261
 262       tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 1));
 263       if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
 264           && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
 265           && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
 266         {
 267           *name = TREE_OPERAND (t, 0);
 268           *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
 269           return true;
 270         }
 271     }
 272
 273   return false;
 274 }
 275
 276 /* Recognize a bit test pattern in COND_EXPR and its defining
 277    statements.  Store the name being tested in *NAME and the bits
 278    in *BITS.  The COND_EXPR computes *NAME & *BITS.
 279    Returns true if the pattern matched, false otherwise.  */
 280
 281 static bool
 282 recognize_bits_test (tree cond_expr, tree *name, tree *bits)
 283 {
 284   tree t;
 285
 286   /* Get at the definition of the result of the bit test.  */
 287   t = TREE_OPERAND (cond_expr, 0);
 288   if (TREE_CODE (t) == NE_EXPR
 289       && integer_zerop (TREE_OPERAND (t, 1)))
 290     t = TREE_OPERAND (t, 0);
 291   if (TREE_CODE (t) != SSA_NAME)
 292     return false;
 293   t = SSA_NAME_DEF_STMT (t);
 294   if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
 295     return false;
 296   t = GIMPLE_STMT_OPERAND (t, 1);
 297
 298   if (TREE_CODE (t) != BIT_AND_EXPR)
 299     return false;
 300
 301   *name = get_name_for_bit_test (TREE_OPERAND (t, 0));
 302   *bits = TREE_OPERAND (t, 1);
 303
 304   return true;
 305 }
 306
 307 /* If-convert on a and pattern with a common else block.  The inner
 308    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 309    Returns true if the edges to the common else basic-block were merged.  */
 310
 311 static bool
 312 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 313 {
 314   block_stmt_iterator bsi;
 315   tree inner_cond, outer_cond;
 316   tree name1, name2, bit1, bit2;
 317
 318   inner_cond = last_stmt (inner_cond_bb);
 319   if (!inner_cond
 320       || TREE_CODE (inner_cond) != COND_EXPR)
 321     return false;
 322
 323   outer_cond = last_stmt (outer_cond_bb);
 324   if (!outer_cond
 325       || TREE_CODE (outer_cond) != COND_EXPR)
 326     return false;
 327
 328   /* See if we test a single bit of the same name in both tests.  In
 329      that case remove the outer test, merging both else edges,
 330      and change the inner one to test for
 331      name & (bit1 | bit2) == (bit1 | bit2).  */
 332   if (recognize_single_bit_test (inner_cond, &name1, &bit1)
 333       && recognize_single_bit_test (outer_cond, &name2, &bit2)
 334       && name1 == name2)
 335     {
 336       tree t, t2;
 337
 338       /* Do it.  */
 339       bsi = bsi_for_stmt (inner_cond);
 340       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 341                        build_int_cst (TREE_TYPE (name1), 1), bit1);
 342       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 343                         build_int_cst (TREE_TYPE (name1), 1), bit2);
 344       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
 345       t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
 346                                     true, BSI_SAME_STMT);
 347       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 348       t2 = force_gimple_operand_bsi (&bsi, t2, true, NULL_TREE,
 349                                      true, BSI_SAME_STMT);
 350       COND_EXPR_COND (inner_cond) = fold_build2 (EQ_EXPR, boolean_type_node,
 351                                                  t2, t);
 352       update_stmt (inner_cond);
 353
 354       /* Leave CFG optimization to cfg_cleanup.  */
 355       COND_EXPR_COND (outer_cond) = boolean_true_node;
 356       update_stmt (outer_cond);
 357
 358       if (dump_file)
 359         {
 360           fprintf (dump_file, "optimizing double bit test to ");
 361           print_generic_expr (dump_file, name1, 0);
 362           fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
 363           print_generic_expr (dump_file, bit1, 0);
 364           fprintf (dump_file, ") | (1 << ");
 365           print_generic_expr (dump_file, bit2, 0);
 366           fprintf (dump_file, ")\n");
 367         }
 368
 369       return true;
 370     }
 371
 372   return false;
 373 }
 374
 375 /* If-convert on a or pattern with a common then block.  The inner
 376    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 377    Returns true, if the edges leading to the common then basic-block
 378    were merged.  */
 379
 380 static bool
 381 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 382 {
 383   tree inner_cond, outer_cond;
 384   tree name1, name2, bits1, bits2;
 385
 386   inner_cond = last_stmt (inner_cond_bb);
 387   if (!inner_cond
 388       || TREE_CODE (inner_cond) != COND_EXPR)
 389     return false;
 390
 391   outer_cond = last_stmt (outer_cond_bb);
 392   if (!outer_cond
 393       || TREE_CODE (outer_cond) != COND_EXPR)
 394     return false;
 395
 396   /* See if we have two bit tests of the same name in both tests.
 397      In that case remove the outer test and change the inner one to
 398      test for name & (bits1 | bits2) != 0.  */
 399   if (recognize_bits_test (inner_cond, &name1, &bits1)
 400       && recognize_bits_test (outer_cond, &name2, &bits2))
 401     {
 402       block_stmt_iterator bsi;
 403       tree t;
 404
 405       /* Find the common name which is bit-tested.  */
 406       if (name1 == name2)
 407         ;
 408       else if (bits1 == bits2)
 409         {
 410           t = name2;
 411           name2 = bits2;
 412           bits2 = t;
 413           t = name1;
 414           name1 = bits1;
 415           bits1 = t;
 416         }
 417       else if (name1 == bits2)
 418         {
 419           t = name2;
 420           name2 = bits2;
 421           bits2 = t;
 422         }
 423       else if (bits1 == name2)
 424         {
 425           t = name1;
 426           name1 = bits1;
 427           bits1 = t;
 428         }
 429       else
 430         return false;
 431
 432       /* Do it.  */
 433       bsi = bsi_for_stmt (inner_cond);
 434       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
 435       t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
 436                                     true, BSI_SAME_STMT);
 437       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 438       t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE,
 439                                     true, BSI_SAME_STMT);
 440       COND_EXPR_COND (inner_cond) = fold_build2 (NE_EXPR, boolean_type_node, t,
 441                                                  build_int_cst (TREE_TYPE (t), 0));
 442       update_stmt (inner_cond);
 443
 444       /* Leave CFG optimization to cfg_cleanup.  */
 445       COND_EXPR_COND (outer_cond) = boolean_false_node;
 446       update_stmt (outer_cond);
 447
 448       if (dump_file)
 449         {
 450           fprintf (dump_file, "optimizing bits or bits test to ");
 451           print_generic_expr (dump_file, name1, 0);
 452           fprintf (dump_file, " & T != 0\nwith temporary T = ");
 453           print_generic_expr (dump_file, bits1, 0);
 454           fprintf (dump_file, " | ");
 455           print_generic_expr (dump_file, bits2, 0);
 456           fprintf (dump_file, "\n");
 457         }
 458
 459       return true;
 460     }
 461
 462   /* See if we have two comparisons that we can merge into one.
 463      This happens for C++ operator overloading where for example
 464      GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
 465   else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond))
 466            && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond))
 467            && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 0),
 468                                TREE_OPERAND (COND_EXPR_COND (outer_cond), 0), 0)
 469            && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 1),
 470                                TREE_OPERAND (COND_EXPR_COND (outer_cond), 1), 0))
 471     {
 472       tree ccond1 = COND_EXPR_COND (inner_cond);
 473       tree ccond2 = COND_EXPR_COND (outer_cond);
 474       enum tree_code code1 = TREE_CODE (ccond1);
 475       enum tree_code code2 = TREE_CODE (ccond2);
 476       enum tree_code code;
 477       tree t;
 478
 479 #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
 480                   || (code2 == a ## _EXPR && code1 == b ## _EXPR))
 481       /* Merge the two condition codes if possible.  */
 482       if (code1 == code2)
 483         code = code1;
 484       else if (CHK (EQ, LT))
 485         code = LE_EXPR;
 486       else if (CHK (EQ, GT))
 487         code = GE_EXPR;
 488       else if (CHK (LT, LE))
 489         code = LE_EXPR;
 490       else if (CHK (GT, GE))
 491         code = GE_EXPR;
 492       else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1, 0)))
 493                || flag_unsafe_math_optimizations)
 494         {
 495           if (CHK (LT, GT))
 496             code = NE_EXPR;
 497           else if (CHK (LT, NE))
 498             code = NE_EXPR;
 499           else if (CHK (GT, NE))
 500             code = NE_EXPR;
 501           else
 502             return false;
 503         }
 504       /* We could check for combinations leading to trivial true/false.  */
 505       else
 506         return false;
 507 #undef CHK
 508
 509       /* Do it.  */
 510       t = fold_build2 (code, boolean_type_node,
 511                        TREE_OPERAND (ccond2, 0), TREE_OPERAND (ccond2, 1));
 512       t = canonicalize_cond_expr_cond (t);
 513       if (!t)
 514         return false;
 515       COND_EXPR_COND (inner_cond) = t;
 516       update_stmt (inner_cond);
 517
 518       /* Leave CFG optimization to cfg_cleanup.  */
 519       COND_EXPR_COND (outer_cond) = boolean_false_node;
 520       update_stmt (outer_cond);
 521
 522       if (dump_file)
 523         {
 524           fprintf (dump_file, "optimizing two comparisons to ");
 525           print_generic_expr (dump_file, t, 0);
 526           fprintf (dump_file, "\n");
 527         }
 528
 529       return true;
 530     }
 531
 532   return false;
 533 }
 534
 535 /* Recognize a CFG pattern and dispatch to the appropriate
 536    if-conversion helper.  We start with BB as the innermost
 537    worker basic-block.  Returns true if a transformation was done.  */
 538
 539 static bool
 540 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 541 {
 542   basic_block then_bb = NULL, else_bb = NULL;
 543
 544   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
 545     return false;
 546
 547   /* Recognize && and || of two conditions with a common
 548      then/else block which entry edges we can merge.  That is:
 549        if (a || b)
 550          ;
 551      and
 552        if (a && b)
 553          ;
 554      This requires a single predecessor of the inner cond_bb.  */
 555   if (single_pred_p (inner_cond_bb))
 556     {
 557       basic_block outer_cond_bb = single_pred (inner_cond_bb);
 558
 559       /* The && form is characterized by a common else_bb with
 560          the two edges leading to it mergable.  The latter is
 561          guaranteed by matching PHI arguments in the else_bb and
 562          the inner cond_bb having no side-effects.  */
 563       if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
 564           && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
 565           && bb_no_side_effects_p (inner_cond_bb))
 566         {
 567           /* We have
 568                <outer_cond_bb>
 569                  if (q) goto inner_cond_bb; else goto else_bb;
 570                <inner_cond_bb>
 571                  if (p) goto ...; else goto else_bb;
 572                  ...
 573                <else_bb>
 574                  ...
 575            */
 576           return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
 577         }
 578
 579       /* The || form is characterized by a common then_bb with the
 580          two edges leading to it mergable.  The latter is guaranteed
 581          by matching PHI arguments in the then_bb and the inner cond_bb
 582          having no side-effects.  */
 583       if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
 584           && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
 585           && bb_no_side_effects_p (inner_cond_bb))
 586         {
 587           /* We have
 588                <outer_cond_bb>
 589                  if (q) goto then_bb; else goto inner_cond_bb;
 590                <inner_cond_bb>
 591                  if (q) goto then_bb; else goto ...;
 592                <then_bb>
 593                  ...
 594            */
 595           return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
 596         }
 597     }
 598
 599   return false;
 600 }
 601
 602 /* Main entry for the tree if-conversion pass.  */
 603
 604 static unsigned int
 605 tree_ssa_ifcombine (void)
 606 {
 607   basic_block *bbs;
 608   bool cfg_changed = false;
 609   int i;
 610
 611   bbs = blocks_in_phiopt_order ();
 612
 613   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
 614     {
 615       basic_block bb = bbs[i];
 616       tree stmt = last_stmt (bb);
 617
 618       if (stmt
 619           && TREE_CODE (stmt) == COND_EXPR)
 620         cfg_changed |= tree_ssa_ifcombine_bb (bb);
 621     }
 622
 623   free (bbs);
 624
 625   return cfg_changed ? TODO_cleanup_cfg : 0;
 626 }
 627
 628 static bool
 629 gate_ifcombine (void)
 630 {
 631   return 1;
 632 }
 633
 634 struct gimple_opt_pass pass_tree_ifcombine =
 635 {
 636  {
 637   GIMPLE_PASS,
 638   "ifcombine",                  /* name */
 639   gate_ifcombine,               /* gate */
 640   tree_ssa_ifcombine,           /* execute */
 641   NULL,                         /* sub */
 642   NULL,                         /* next */
 643   0,                            /* static_pass_number */
 644   TV_TREE_IFCOMBINE,            /* tv_id */
 645   PROP_cfg | PROP_ssa,          /* properties_required */
 646   0,                            /* properties_provided */
 647   0,                            /* properties_destroyed */
 648   0,                            /* todo_flags_start */
 649   TODO_dump_func
 650   | TODO_ggc_collect
 651   | TODO_update_ssa
 652   | TODO_verify_ssa             /* todo_flags_finish */
 653  }
 654 };