gcc/tree-ssa-ifcombine.c

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