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