gcc/tree-ssa-ifcombine.c

   1 /* Combining of if-expressions on trees.
   2    Copyright (C) 2007-2015 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 "backend.h"
  25 #include "cfghooks.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "rtl.h"
  29 #include "ssa.h"
  30 /* rtl is needed only because arm back-end requires it for
  31    BRANCH_COST.  */
  32 #include "tm_p.h"
  33 #include "alias.h"
  34 #include "fold-const.h"
  35 #include "stor-layout.h"
  36 #include "cfganal.h"
  37 #include "tree-pretty-print.h"
  38 #include "internal-fn.h"
  39 #include "gimple-fold.h"
  40 #include "gimple-iterator.h"
  41 #include "gimplify-me.h"
  42 #include "tree-cfg.h"
  43 #include "tree-pass.h"
  44
  45 #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
  46 #define LOGICAL_OP_NON_SHORT_CIRCUIT \
  47   (BRANCH_COST (optimize_function_for_speed_p (cfun), \
  48                 false) >= 2)
  49 #endif
  50
  51 /* This pass combines COND_EXPRs to simplify control flow.  It
  52    currently recognizes bit tests and comparisons in chains that
  53    represent logical and or logical or of two COND_EXPRs.
  54
  55    It does so by walking basic blocks in a approximate reverse
  56    post-dominator order and trying to match CFG patterns that
  57    represent logical and or logical or of two COND_EXPRs.
  58    Transformations are done if the COND_EXPR conditions match
  59    either
  60
  61      1. two single bit tests X & (1 << Yn) (for logical and)
  62
  63      2. two bit tests X & Yn (for logical or)
  64
  65      3. two comparisons X OPn Y (for logical or)
  66
  67    To simplify this pass, removing basic blocks and dead code
  68    is left to CFG cleanup and DCE.  */
  69
  70
  71 /* Recognize a if-then-else CFG pattern starting to match with the
  72    COND_BB basic-block containing the COND_EXPR.  The recognized
  73    then end else blocks are stored to *THEN_BB and *ELSE_BB.  If
  74    *THEN_BB and/or *ELSE_BB are already set, they are required to
  75    match the then and else basic-blocks to make the pattern match.
  76    Returns true if the pattern matched, false otherwise.  */
  77
  78 static bool
  79 recognize_if_then_else (basic_block cond_bb,
  80                         basic_block *then_bb, basic_block *else_bb)
  81 {
  82   edge t, e;
  83
  84   if (EDGE_COUNT (cond_bb->succs) != 2)
  85     return false;
  86
  87   /* Find the then/else edges.  */
  88   t = EDGE_SUCC (cond_bb, 0);
  89   e = EDGE_SUCC (cond_bb, 1);
  90   if (!(t->flags & EDGE_TRUE_VALUE))
  91     std::swap (t, e);
  92   if (!(t->flags & EDGE_TRUE_VALUE)
  93       || !(e->flags & EDGE_FALSE_VALUE))
  94     return false;
  95
  96   /* Check if the edge destinations point to the required block.  */
  97   if (*then_bb
  98       && t->dest != *then_bb)
  99     return false;
 100   if (*else_bb
 101       && e->dest != *else_bb)
 102     return false;
 103
 104   if (!*then_bb)
 105     *then_bb = t->dest;
 106   if (!*else_bb)
 107     *else_bb = e->dest;
 108
 109   return true;
 110 }
 111
 112 /* Verify if the basic block BB does not have side-effects.  Return
 113    true in this case, else false.  */
 114
 115 static bool
 116 bb_no_side_effects_p (basic_block bb)
 117 {
 118   gimple_stmt_iterator gsi;
 119
 120   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 121     {
 122       gimple *stmt = gsi_stmt (gsi);
 123
 124       if (is_gimple_debug (stmt))
 125         continue;
 126
 127       if (gimple_has_side_effects (stmt)
 128           || gimple_could_trap_p (stmt)
 129           || gimple_vuse (stmt))
 130         return false;
 131     }
 132
 133   return true;
 134 }
 135
 136 /* Return true if BB is an empty forwarder block to TO_BB.  */
 137
 138 static bool
 139 forwarder_block_to (basic_block bb, basic_block to_bb)
 140 {
 141   return empty_block_p (bb)
 142          && single_succ_p (bb)
 143          && single_succ (bb) == to_bb;
 144 }
 145
 146 /* Verify if all PHI node arguments in DEST for edges from BB1 or
 147    BB2 to DEST are the same.  This makes the CFG merge point
 148    free from side-effects.  Return true in this case, else false.  */
 149
 150 static bool
 151 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
 152 {
 153   edge e1 = find_edge (bb1, dest);
 154   edge e2 = find_edge (bb2, dest);
 155   gphi_iterator gsi;
 156   gphi *phi;
 157
 158   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
 159     {
 160       phi = gsi.phi ();
 161       if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
 162                             PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
 163         return false;
 164     }
 165
 166   return true;
 167 }
 168
 169 /* Return the best representative SSA name for CANDIDATE which is used
 170    in a bit test.  */
 171
 172 static tree
 173 get_name_for_bit_test (tree candidate)
 174 {
 175   /* Skip single-use names in favor of using the name from a
 176      non-widening conversion definition.  */
 177   if (TREE_CODE (candidate) == SSA_NAME
 178       && has_single_use (candidate))
 179     {
 180       gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
 181       if (is_gimple_assign (def_stmt)
 182           && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
 183         {
 184           if (TYPE_PRECISION (TREE_TYPE (candidate))
 185               <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
 186             return gimple_assign_rhs1 (def_stmt);
 187         }
 188     }
 189
 190   return candidate;
 191 }
 192
 193 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
 194    statements.  Store the name being tested in *NAME and the bit
 195    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
 196    Returns true if the pattern matched, false otherwise.  */
 197
 198 static bool
 199 recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
 200 {
 201   gimple *stmt;
 202
 203   /* Get at the definition of the result of the bit test.  */
 204   if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
 205       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
 206       || !integer_zerop (gimple_cond_rhs (cond)))
 207     return false;
 208   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
 209   if (!is_gimple_assign (stmt))
 210     return false;
 211
 212   /* Look at which bit is tested.  One form to recognize is
 213      D.1985_5 = state_3(D) >> control1_4(D);
 214      D.1986_6 = (int) D.1985_5;
 215      D.1987_7 = op0 & 1;
 216      if (D.1987_7 != 0)  */
 217   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 218       && integer_onep (gimple_assign_rhs2 (stmt))
 219       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
 220     {
 221       tree orig_name = gimple_assign_rhs1 (stmt);
 222
 223       /* Look through copies and conversions to eventually
 224          find the stmt that computes the shift.  */
 225       stmt = SSA_NAME_DEF_STMT (orig_name);
 226
 227       while (is_gimple_assign (stmt)
 228              && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
 229                   && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
 230                       <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
 231                   && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
 232                  || gimple_assign_ssa_name_copy_p (stmt)))
 233         stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
 234
 235       /* If we found such, decompose it.  */
 236       if (is_gimple_assign (stmt)
 237           && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
 238         {
 239           /* op0 & (1 << op1) */
 240           *bit = gimple_assign_rhs2 (stmt);
 241           *name = gimple_assign_rhs1 (stmt);
 242         }
 243       else
 244         {
 245           /* t & 1 */
 246           *bit = integer_zero_node;
 247           *name = get_name_for_bit_test (orig_name);
 248         }
 249
 250       return true;
 251     }
 252
 253   /* Another form is
 254      D.1987_7 = op0 & (1 << CST)
 255      if (D.1987_7 != 0)  */
 256   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 257       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 258       && integer_pow2p (gimple_assign_rhs2 (stmt)))
 259     {
 260       *name = gimple_assign_rhs1 (stmt);
 261       *bit = build_int_cst (integer_type_node,
 262                             tree_log2 (gimple_assign_rhs2 (stmt)));
 263       return true;
 264     }
 265
 266   /* Another form is
 267      D.1986_6 = 1 << control1_4(D)
 268      D.1987_7 = op0 & D.1986_6
 269      if (D.1987_7 != 0)  */
 270   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
 271       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 272       && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
 273     {
 274       gimple *tmp;
 275
 276       /* Both arguments of the BIT_AND_EXPR can be the single-bit
 277          specifying expression.  */
 278       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (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_rhs2 (stmt);
 284           *bit = gimple_assign_rhs2 (tmp);
 285           return true;
 286         }
 287
 288       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
 289       if (is_gimple_assign (tmp)
 290           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
 291           && integer_onep (gimple_assign_rhs1 (tmp)))
 292         {
 293           *name = gimple_assign_rhs1 (stmt);
 294           *bit = gimple_assign_rhs2 (tmp);
 295           return true;
 296         }
 297     }
 298
 299   return false;
 300 }
 301
 302 /* Recognize a bit test pattern in a GIMPLE_COND and its defining
 303    statements.  Store the name being tested in *NAME and the bits
 304    in *BITS.  The COND_EXPR computes *NAME & *BITS.
 305    Returns true if the pattern matched, false otherwise.  */
 306
 307 static bool
 308 recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
 309 {
 310   gimple *stmt;
 311
 312   /* Get at the definition of the result of the bit test.  */
 313   if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
 314       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
 315       || !integer_zerop (gimple_cond_rhs (cond)))
 316     return false;
 317   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
 318   if (!is_gimple_assign (stmt)
 319       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
 320     return false;
 321
 322   *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
 323   *bits = gimple_assign_rhs2 (stmt);
 324
 325   return true;
 326 }
 327
 328 /* If-convert on a and pattern with a common else block.  The inner
 329    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
 330    inner_inv, outer_inv and result_inv indicate whether the conditions
 331    are inverted.
 332    Returns true if the edges to the common else basic-block were merged.  */
 333
 334 static bool
 335 ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
 336                    basic_block outer_cond_bb, bool outer_inv, bool result_inv)
 337 {
 338   gimple_stmt_iterator gsi;
 339   gimple *inner_stmt, *outer_stmt;
 340   gcond *inner_cond, *outer_cond;
 341   tree name1, name2, bit1, bit2, bits1, bits2;
 342
 343   inner_stmt = last_stmt (inner_cond_bb);
 344   if (!inner_stmt
 345       || gimple_code (inner_stmt) != GIMPLE_COND)
 346     return false;
 347   inner_cond = as_a <gcond *> (inner_stmt);
 348
 349   outer_stmt = last_stmt (outer_cond_bb);
 350   if (!outer_stmt
 351       || gimple_code (outer_stmt) != GIMPLE_COND)
 352     return false;
 353   outer_cond = as_a <gcond *> (outer_stmt);
 354
 355   /* See if we test a single bit of the same name in both tests.  In
 356      that case remove the outer test, merging both else edges,
 357      and change the inner one to test for
 358      name & (bit1 | bit2) == (bit1 | bit2).  */
 359   if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
 360       && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
 361       && name1 == name2)
 362     {
 363       tree t, t2;
 364
 365       /* Do it.  */
 366       gsi = gsi_for_stmt (inner_cond);
 367       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 368                        build_int_cst (TREE_TYPE (name1), 1), bit1);
 369       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 370                         build_int_cst (TREE_TYPE (name1), 1), bit2);
 371       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
 372       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 373                                     true, GSI_SAME_STMT);
 374       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 375       t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
 376                                      true, GSI_SAME_STMT);
 377       t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
 378                        boolean_type_node, t2, t);
 379       t = canonicalize_cond_expr_cond (t);
 380       if (!t)
 381         return false;
 382       gimple_cond_set_condition_from_tree (inner_cond, t);
 383       update_stmt (inner_cond);
 384
 385       /* Leave CFG optimization to cfg_cleanup.  */
 386       gimple_cond_set_condition_from_tree (outer_cond,
 387         outer_inv ? boolean_false_node : boolean_true_node);
 388       update_stmt (outer_cond);
 389
 390       if (dump_file)
 391         {
 392           fprintf (dump_file, "optimizing double bit test to ");
 393           print_generic_expr (dump_file, name1, 0);
 394           fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
 395           print_generic_expr (dump_file, bit1, 0);
 396           fprintf (dump_file, ") | (1 << ");
 397           print_generic_expr (dump_file, bit2, 0);
 398           fprintf (dump_file, ")\n");
 399         }
 400
 401       return true;
 402     }
 403
 404   /* See if we have two bit tests of the same name in both tests.
 405      In that case remove the outer test and change the inner one to
 406      test for name & (bits1 | bits2) != 0.  */
 407   else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
 408       && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
 409     {
 410       gimple_stmt_iterator gsi;
 411       tree t;
 412
 413       /* Find the common name which is bit-tested.  */
 414       if (name1 == name2)
 415         ;
 416       else if (bits1 == bits2)
 417         {
 418           std::swap (name2, bits2);
 419           std::swap (name1, bits1);
 420         }
 421       else if (name1 == bits2)
 422         std::swap (name2, bits2);
 423       else if (bits1 == name2)
 424         std::swap (name1, bits1);
 425       else
 426         return false;
 427
 428       /* As we strip non-widening conversions in finding a common
 429          name that is tested make sure to end up with an integral
 430          type for building the bit operations.  */
 431       if (TYPE_PRECISION (TREE_TYPE (bits1))
 432           >= TYPE_PRECISION (TREE_TYPE (bits2)))
 433         {
 434           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
 435           name1 = fold_convert (TREE_TYPE (bits1), name1);
 436           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
 437           bits2 = fold_convert (TREE_TYPE (bits1), bits2);
 438         }
 439       else
 440         {
 441           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
 442           name1 = fold_convert (TREE_TYPE (bits2), name1);
 443           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
 444           bits1 = fold_convert (TREE_TYPE (bits2), bits1);
 445         }
 446
 447       /* Do it.  */
 448       gsi = gsi_for_stmt (inner_cond);
 449       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
 450       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 451                                     true, GSI_SAME_STMT);
 452       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
 453       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 454                                     true, GSI_SAME_STMT);
 455       t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t,
 456                        build_int_cst (TREE_TYPE (t), 0));
 457       t = canonicalize_cond_expr_cond (t);
 458       if (!t)
 459         return false;
 460       gimple_cond_set_condition_from_tree (inner_cond, t);
 461       update_stmt (inner_cond);
 462
 463       /* Leave CFG optimization to cfg_cleanup.  */
 464       gimple_cond_set_condition_from_tree (outer_cond,
 465         outer_inv ? boolean_false_node : boolean_true_node);
 466       update_stmt (outer_cond);
 467
 468       if (dump_file)
 469         {
 470           fprintf (dump_file, "optimizing bits or bits test to ");
 471           print_generic_expr (dump_file, name1, 0);
 472           fprintf (dump_file, " & T != 0\nwith temporary T = ");
 473           print_generic_expr (dump_file, bits1, 0);
 474           fprintf (dump_file, " | ");
 475           print_generic_expr (dump_file, bits2, 0);
 476           fprintf (dump_file, "\n");
 477         }
 478
 479       return true;
 480     }
 481
 482   /* See if we have two comparisons that we can merge into one.  */
 483   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 484            && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
 485     {
 486       tree t;
 487       enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
 488       enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
 489
 490       /* Invert comparisons if necessary (and possible).  */
 491       if (inner_inv)
 492         inner_cond_code = invert_tree_comparison (inner_cond_code,
 493           HONOR_NANS (gimple_cond_lhs (inner_cond)));
 494       if (inner_cond_code == ERROR_MARK)
 495         return false;
 496       if (outer_inv)
 497         outer_cond_code = invert_tree_comparison (outer_cond_code,
 498           HONOR_NANS (gimple_cond_lhs (outer_cond)));
 499       if (outer_cond_code == ERROR_MARK)
 500         return false;
 501       /* Don't return false so fast, try maybe_fold_or_comparisons?  */
 502
 503       if (!(t = maybe_fold_and_comparisons (inner_cond_code,
 504                                             gimple_cond_lhs (inner_cond),
 505                                             gimple_cond_rhs (inner_cond),
 506                                             outer_cond_code,
 507                                             gimple_cond_lhs (outer_cond),
 508                                             gimple_cond_rhs (outer_cond))))
 509         {
 510           tree t1, t2;
 511           gimple_stmt_iterator gsi;
 512           if (!LOGICAL_OP_NON_SHORT_CIRCUIT)
 513             return false;
 514           /* Only do this optimization if the inner bb contains only the conditional. */
 515           if (!gsi_one_before_end_p (gsi_start_nondebug_after_labels_bb (inner_cond_bb)))
 516             return false;
 517           t1 = fold_build2_loc (gimple_location (inner_cond),
 518                                 inner_cond_code,
 519                                 boolean_type_node,
 520                                 gimple_cond_lhs (inner_cond),
 521                                 gimple_cond_rhs (inner_cond));
 522           t2 = fold_build2_loc (gimple_location (outer_cond),
 523                                 outer_cond_code,
 524                                 boolean_type_node,
 525                                 gimple_cond_lhs (outer_cond),
 526                                 gimple_cond_rhs (outer_cond));
 527           t = fold_build2_loc (gimple_location (inner_cond),
 528                                TRUTH_AND_EXPR, boolean_type_node, t1, t2);
 529           if (result_inv)
 530             {
 531               t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
 532               result_inv = false;
 533             }
 534           gsi = gsi_for_stmt (inner_cond);
 535           t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr, NULL, true,
 536                                           GSI_SAME_STMT);
 537         }
 538       if (result_inv)
 539         t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
 540       t = canonicalize_cond_expr_cond (t);
 541       if (!t)
 542         return false;
 543       gimple_cond_set_condition_from_tree (inner_cond, t);
 544       update_stmt (inner_cond);
 545
 546       /* Leave CFG optimization to cfg_cleanup.  */
 547       gimple_cond_set_condition_from_tree (outer_cond,
 548         outer_inv ? boolean_false_node : boolean_true_node);
 549       update_stmt (outer_cond);
 550
 551       if (dump_file)
 552         {
 553           fprintf (dump_file, "optimizing two comparisons to ");
 554           print_generic_expr (dump_file, t, 0);
 555           fprintf (dump_file, "\n");
 556         }
 557
 558       return true;
 559     }
 560
 561   return false;
 562 }
 563
 564 /* Helper function for tree_ssa_ifcombine_bb.  Recognize a CFG pattern and
 565    dispatch to the appropriate if-conversion helper for a particular
 566    set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
 567    PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.  */
 568
 569 static bool
 570 tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
 571                          basic_block then_bb, basic_block else_bb,
 572                          basic_block phi_pred_bb)
 573 {
 574   /* The && form is characterized by a common else_bb with
 575      the two edges leading to it mergable.  The latter is
 576      guaranteed by matching PHI arguments in the else_bb and
 577      the inner cond_bb having no side-effects.  */
 578   if (phi_pred_bb != else_bb
 579       && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
 580       && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb)
 581       && bb_no_side_effects_p (inner_cond_bb))
 582     {
 583       /* We have
 584            <outer_cond_bb>
 585              if (q) goto inner_cond_bb; else goto else_bb;
 586            <inner_cond_bb>
 587              if (p) goto ...; else goto else_bb;
 588              ...
 589            <else_bb>
 590              ...
 591        */
 592       return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false,
 593                                 false);
 594     }
 595
 596   /* And a version where the outer condition is negated.  */
 597   if (phi_pred_bb != else_bb
 598       && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
 599       && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb)
 600       && bb_no_side_effects_p (inner_cond_bb))
 601     {
 602       /* We have
 603            <outer_cond_bb>
 604              if (q) goto else_bb; else goto inner_cond_bb;
 605            <inner_cond_bb>
 606              if (p) goto ...; else goto else_bb;
 607              ...
 608            <else_bb>
 609              ...
 610        */
 611       return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true,
 612                                 false);
 613     }
 614
 615   /* The || form is characterized by a common then_bb with the
 616      two edges leading to it mergable.  The latter is guaranteed
 617      by matching PHI arguments in the then_bb and the inner cond_bb
 618      having no side-effects.  */
 619   if (phi_pred_bb != then_bb
 620       && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
 621       && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb)
 622       && bb_no_side_effects_p (inner_cond_bb))
 623     {
 624       /* We have
 625            <outer_cond_bb>
 626              if (q) goto then_bb; else goto inner_cond_bb;
 627            <inner_cond_bb>
 628              if (q) goto then_bb; else goto ...;
 629            <then_bb>
 630              ...
 631        */
 632       return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true,
 633                                 true);
 634     }
 635
 636   /* And a version where the outer condition is negated.  */
 637   if (phi_pred_bb != then_bb
 638       && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
 639       && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb)
 640       && bb_no_side_effects_p (inner_cond_bb))
 641     {
 642       /* We have
 643            <outer_cond_bb>
 644              if (q) goto inner_cond_bb; else goto then_bb;
 645            <inner_cond_bb>
 646              if (q) goto then_bb; else goto ...;
 647            <then_bb>
 648              ...
 649        */
 650       return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
 651                                 true);
 652     }
 653
 654   return false;
 655 }
 656
 657 /* Recognize a CFG pattern and dispatch to the appropriate
 658    if-conversion helper.  We start with BB as the innermost
 659    worker basic-block.  Returns true if a transformation was done.  */
 660
 661 static bool
 662 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 663 {
 664   basic_block then_bb = NULL, else_bb = NULL;
 665
 666   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
 667     return false;
 668
 669   /* Recognize && and || of two conditions with a common
 670      then/else block which entry edges we can merge.  That is:
 671        if (a || b)
 672          ;
 673      and
 674        if (a && b)
 675          ;
 676      This requires a single predecessor of the inner cond_bb.  */
 677   if (single_pred_p (inner_cond_bb))
 678     {
 679       basic_block outer_cond_bb = single_pred (inner_cond_bb);
 680
 681       if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
 682                                    then_bb, else_bb, inner_cond_bb))
 683         return true;
 684
 685       if (forwarder_block_to (else_bb, then_bb))
 686         {
 687           /* Other possibilities for the && form, if else_bb is
 688              empty forwarder block to then_bb.  Compared to the above simpler
 689              forms this can be treated as if then_bb and else_bb were swapped,
 690              and the corresponding inner_cond_bb not inverted because of that.
 691              For same_phi_args_p we look at equality of arguments between
 692              edge from outer_cond_bb and the forwarder block.  */
 693           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
 694                                        then_bb, else_bb))
 695             return true;
 696         }
 697       else if (forwarder_block_to (then_bb, else_bb))
 698         {
 699           /* Other possibilities for the || form, if then_bb is
 700              empty forwarder block to else_bb.  Compared to the above simpler
 701              forms this can be treated as if then_bb and else_bb were swapped,
 702              and the corresponding inner_cond_bb not inverted because of that.
 703              For same_phi_args_p we look at equality of arguments between
 704              edge from outer_cond_bb and the forwarder block.  */
 705           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
 706                                        then_bb, then_bb))
 707             return true;
 708         }
 709     }
 710
 711   return false;
 712 }
 713
 714 /* Main entry for the tree if-conversion pass.  */
 715
 716 namespace {
 717
 718 const pass_data pass_data_tree_ifcombine =
 719 {
 720   GIMPLE_PASS, /* type */
 721   "ifcombine", /* name */
 722   OPTGROUP_NONE, /* optinfo_flags */
 723   TV_TREE_IFCOMBINE, /* tv_id */
 724   ( PROP_cfg | PROP_ssa ), /* properties_required */
 725   0, /* properties_provided */
 726   0, /* properties_destroyed */
 727   0, /* todo_flags_start */
 728   TODO_update_ssa, /* todo_flags_finish */
 729 };
 730
 731 class pass_tree_ifcombine : public gimple_opt_pass
 732 {
 733 public:
 734   pass_tree_ifcombine (gcc::context *ctxt)
 735     : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
 736   {}
 737
 738   /* opt_pass methods: */
 739   virtual unsigned int execute (function *);
 740
 741 }; // class pass_tree_ifcombine
 742
 743 unsigned int
 744 pass_tree_ifcombine::execute (function *fun)
 745 {
 746   basic_block *bbs;
 747   bool cfg_changed = false;
 748   int i;
 749
 750   bbs = single_pred_before_succ_order ();
 751   calculate_dominance_info (CDI_DOMINATORS);
 752
 753   /* Search every basic block for COND_EXPR we may be able to optimize.
 754
 755      We walk the blocks in order that guarantees that a block with
 756      a single predecessor is processed after the predecessor.
 757      This ensures that we collapse outter ifs before visiting the
 758      inner ones, and also that we do not try to visit a removed
 759      block.  This is opposite of PHI-OPT, because we cascade the
 760      combining rather than cascading PHIs. */
 761   for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
 762     {
 763       basic_block bb = bbs[i];
 764       gimple *stmt = last_stmt (bb);
 765
 766       if (stmt
 767           && gimple_code (stmt) == GIMPLE_COND)
 768         if (tree_ssa_ifcombine_bb (bb))
 769           {
 770             /* Clear range info from all stmts in BB which is now executed
 771                conditional on a always true/false condition.  */
 772             reset_flow_sensitive_info_in_bb (bb);
 773             cfg_changed |= true;
 774           }
 775     }
 776
 777   free (bbs);
 778
 779   return cfg_changed ? TODO_cleanup_cfg : 0;
 780 }
 781
 782 } // anon namespace
 783
 784 gimple_opt_pass *
 785 make_pass_tree_ifcombine (gcc::context *ctxt)
 786 {
 787   return new pass_tree_ifcombine (ctxt);
 788 }