LCOV - code coverage report
Current view: top level - gcc - tree-ssa-ifcombine.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.4 % 581 560
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 20 20
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Combining of if-expressions on trees.
       2              :    Copyright (C) 2007-2026 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 "memmodel.h"
      31              : #include "tm_p.h"
      32              : #include "ssa.h"
      33              : #include "tree-pretty-print.h"
      34              : /* rtl is needed only because arm back-end requires it for
      35              :    BRANCH_COST.  */
      36              : #include "fold-const.h"
      37              : #include "cfganal.h"
      38              : #include "gimple-iterator.h"
      39              : #include "gimple-fold.h"
      40              : #include "gimplify-me.h"
      41              : #include "tree-cfg.h"
      42              : #include "tree-ssa.h"
      43              : #include "tree-ssa-ifcombine.h"
      44              : #include "attribs.h"
      45              : #include "asan.h"
      46              : #include "bitmap.h"
      47              : #include "cfgloop.h"
      48              : 
      49              : #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
      50              : #define LOGICAL_OP_NON_SHORT_CIRCUIT \
      51              :   (BRANCH_COST (optimize_function_for_speed_p (cfun), \
      52              :                 false) >= 2)
      53              : #endif
      54              : 
      55              : /* Return FALSE iff the COND_BB ends with a conditional whose result is not a
      56              :    known constant.  */
      57              : 
      58              : static bool
      59     32626733 : known_succ_p (basic_block cond_bb)
      60              : {
      61     67240771 :   gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
      62              : 
      63     30933073 :   if (!cond)
      64              :     return true;
      65              : 
      66     30933073 :   return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
      67     30933073 :           && CONSTANT_CLASS_P (gimple_cond_rhs (cond)));
      68              : }
      69              : 
      70              : /* This pass combines COND_EXPRs to simplify control flow.  It
      71              :    currently recognizes bit tests and comparisons in chains that
      72              :    represent logical and or logical or of two COND_EXPRs.
      73              : 
      74              :    It does so by walking basic blocks in a approximate reverse
      75              :    post-dominator order and trying to match CFG patterns that
      76              :    represent logical and or logical or of two COND_EXPRs.
      77              :    Transformations are done if the COND_EXPR conditions match
      78              :    either
      79              : 
      80              :      1. two single bit tests X & (1 << Yn) (for logical and)
      81              : 
      82              :      2. two bit tests X & Yn (for logical or)
      83              : 
      84              :      3. two comparisons X OPn Y (for logical or)
      85              : 
      86              :    To simplify this pass, removing basic blocks and dead code
      87              :    is left to CFG cleanup and DCE.  */
      88              : 
      89              : 
      90              : /* Recognize a if-then-else CFG pattern starting to match with the COND_BB
      91              :    basic-block containing the COND_EXPR.  If !SUCCS_ANY, the condition must not
      92              :    resolve to a constant for a match.  Returns true if the pattern matched,
      93              :    false otherwise.  In case of a !SUCCS_ANY match, the recognized then end
      94              :    else blocks are stored to *THEN_BB and *ELSE_BB.  If *THEN_BB and/or
      95              :    *ELSE_BB are already set, they are required to match the then and else
      96              :    basic-blocks to make the pattern match.  If SUCCS_ANY, *THEN_BB and *ELSE_BB
      97              :    will not be filled in, and they will be found to match even if reversed.  */
      98              : 
      99              : bool
     100     36002834 : recognize_if_then_else (basic_block cond_bb,
     101              :                         basic_block *then_bb, basic_block *else_bb,
     102              :                         bool succs_any)
     103              : {
     104     36002834 :   edge t, e;
     105              : 
     106     36002834 :   if (EDGE_COUNT (cond_bb->succs) != 2
     107     36002834 :       || (!succs_any && known_succ_p (cond_bb)))
     108              :     return false;
     109              : 
     110              :   /* Find the then/else edges.  */
     111     31130825 :   t = EDGE_SUCC (cond_bb, 0);
     112     31130825 :   e = EDGE_SUCC (cond_bb, 1);
     113              : 
     114     31130825 :   if (succs_any)
     115       605046 :     return ((t->dest == *then_bb && e->dest == *else_bb)
     116      2494623 :             || (t->dest == *else_bb && e->dest == *then_bb));
     117              : 
     118     28965708 :   if (!(t->flags & EDGE_TRUE_VALUE))
     119      2672084 :     std::swap (t, e);
     120     28965708 :   if (!(t->flags & EDGE_TRUE_VALUE)
     121     28965708 :       || !(e->flags & EDGE_FALSE_VALUE))
     122              :     return false;
     123              : 
     124              :   /* Check if the edge destinations point to the required block.  */
     125     28965708 :   if (*then_bb
     126     22473927 :       && t->dest != *then_bb)
     127              :     return false;
     128     24043082 :   if (*else_bb
     129      2511982 :       && e->dest != *else_bb)
     130              :     return false;
     131              : 
     132     23090738 :   if (!*then_bb)
     133      6491781 :     *then_bb = t->dest;
     134     23090738 :   if (!*else_bb)
     135     21531100 :     *else_bb = e->dest;
     136              : 
     137              :   return true;
     138              : }
     139              : 
     140              : /* Verify if the basic block BB does not have side-effects.  Return
     141              :    true in this case, else false.  */
     142              : 
     143              : static bool
     144      4503634 : bb_no_side_effects_p (basic_block bb)
     145              : {
     146      4503634 :   gimple_stmt_iterator gsi;
     147              : 
     148     25626279 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     149              :     {
     150     19035746 :       gimple *stmt = gsi_stmt (gsi);
     151              : 
     152     19035746 :       if (is_gimple_debug (stmt))
     153     11238175 :         continue;
     154              : 
     155      7797571 :       gassign *ass;
     156      7797571 :       enum tree_code rhs_code;
     157      7797571 :       if (gimple_has_side_effects (stmt)
     158              :           /* Ignore GIMPLE_COND for trapping.  */
     159      6933756 :           || (!is_a<gcond*>(stmt)
     160      4846710 :               && gimple_could_trap_p (stmt))
     161      6054838 :           || gimple_vdef (stmt)
     162              :           /* We need to rewrite stmts with undefined overflow to use
     163              :              unsigned arithmetic but cannot do so for signed division.  */
     164      9007376 :           || ((ass = dyn_cast <gassign *> (stmt))
     165      3223556 :               && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
     166      4857006 :               && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
     167       839822 :               && ((rhs_code = gimple_assign_rhs_code (ass)), true)
     168       839822 :               && (rhs_code == TRUNC_DIV_EXPR
     169              :                   || rhs_code == CEIL_DIV_EXPR
     170              :                   || rhs_code == FLOOR_DIV_EXPR
     171       839822 :                   || rhs_code == ROUND_DIV_EXPR)
     172              :               /* We cannot use expr_not_equal_to since we'd have to restrict
     173              :                  flow-sensitive info to whats known at the outer if.  */
     174         1841 :               && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
     175         1841 :                   || !integer_minus_onep (gimple_assign_rhs2 (ass))))
     176              :           /* const calls don't match any of the above, yet they could
     177              :              still have some side-effects - they could contain
     178              :              gimple_could_trap_p statements, like floating point
     179              :              exceptions or integer division by zero.  See PR70586.
     180              :              FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
     181              :              should handle this.  */
     182     16009894 :           || is_gimple_call (stmt))
     183      2416735 :         return false;
     184              : 
     185      5385380 :       ssa_op_iter it;
     186      5385380 :       tree use;
     187     10732974 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
     188      5352138 :         if (ssa_name_maybe_undef_p (use))
     189              :           return false;
     190              :     }
     191              : 
     192              :   return true;
     193              : }
     194              : 
     195              : /* Return true if BB is an empty forwarder block to TO_BB.  */
     196              : 
     197              : static bool
     198      2522342 : forwarder_block_to (basic_block bb, basic_block to_bb)
     199              : {
     200      2522342 :   return empty_block_p (bb)
     201       359131 :          && single_succ_p (bb)
     202      2881473 :          && single_succ (bb) == to_bb;
     203              : }
     204              : 
     205              : /* Verify if all PHI node arguments in DEST for edges from BB1 or
     206              :    BB2 to DEST are the same.  This makes the CFG merge point
     207              :    free from side-effects.  Return true in this case, else false.  */
     208              : 
     209              : static bool
     210      1131600 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
     211              : {
     212      1131600 :   edge e1 = find_edge (bb1, dest);
     213      1131600 :   edge e2 = find_edge (bb2, dest);
     214      1131600 :   gphi_iterator gsi;
     215      1131600 :   gphi *phi;
     216              : 
     217      1392879 :   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
     218              :     {
     219       349282 :       phi = gsi.phi ();
     220       349282 :       if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
     221       349282 :                             PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
     222              :         return false;
     223              :     }
     224              : 
     225              :   return true;
     226              : }
     227              : 
     228              : /* Return the best representative SSA name for CANDIDATE which is used
     229              :    in a bit test.  */
     230              : 
     231              : static tree
     232         7716 : get_name_for_bit_test (tree candidate)
     233              : {
     234              :   /* Skip single-use names in favor of using the name from a
     235              :      non-widening conversion definition.  */
     236         7716 :   if (TREE_CODE (candidate) == SSA_NAME
     237         7716 :       && has_single_use (candidate))
     238              :     {
     239         7061 :       gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
     240         7061 :       if (is_gimple_assign (def_stmt)
     241         7061 :           && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
     242              :         {
     243           70 :           if (TYPE_PRECISION (TREE_TYPE (candidate))
     244           70 :               <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
     245              :             return gimple_assign_rhs1 (def_stmt);
     246              :         }
     247              :     }
     248              : 
     249              :   return candidate;
     250              : }
     251              : 
     252              : /* Recognize a single bit test pattern in GIMPLE_COND and its defining
     253              :    statements.  Store the name being tested in *NAME and the bit
     254              :    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
     255              :    Returns true if the pattern matched, false otherwise.  */
     256              : 
     257              : static bool
     258       453198 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
     259              : {
     260       453198 :   gimple *stmt;
     261              : 
     262              :   /* Get at the definition of the result of the bit test.  */
     263       453198 :   if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
     264       114882 :       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
     265       568065 :       || !integer_zerop (gimple_cond_rhs (cond)))
     266              :     return false;
     267        88605 :   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
     268        88605 :   if (!is_gimple_assign (stmt))
     269              :     return false;
     270              : 
     271              :   /* Look at which bit is tested.  One form to recognize is
     272              :      D.1985_5 = state_3(D) >> control1_4(D);
     273              :      D.1986_6 = (int) D.1985_5;
     274              :      D.1987_7 = op0 & 1;
     275              :      if (D.1987_7 != 0)  */
     276        84209 :   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     277        11090 :       && integer_onep (gimple_assign_rhs2 (stmt))
     278        84706 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
     279              :     {
     280          497 :       tree orig_name = gimple_assign_rhs1 (stmt);
     281              : 
     282              :       /* Look through copies and conversions to eventually
     283              :          find the stmt that computes the shift.  */
     284          497 :       stmt = SSA_NAME_DEF_STMT (orig_name);
     285              : 
     286          498 :       while (is_gimple_assign (stmt)
     287          498 :              && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
     288            1 :                   && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
     289            1 :                       <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
     290            1 :                   && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
     291          378 :                  || gimple_assign_ssa_name_copy_p (stmt)))
     292            1 :         stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
     293              : 
     294              :       /* If we found such, decompose it.  */
     295          497 :       if (is_gimple_assign (stmt)
     296          497 :           && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
     297              :         {
     298              :           /* op0 & (1 << op1) */
     299          119 :           *bit = gimple_assign_rhs2 (stmt);
     300          119 :           *name = gimple_assign_rhs1 (stmt);
     301              :         }
     302              :       else
     303              :         {
     304              :           /* t & 1 */
     305          378 :           *bit = integer_zero_node;
     306          378 :           *name = get_name_for_bit_test (orig_name);
     307              :         }
     308              : 
     309              :       return true;
     310              :     }
     311              : 
     312              :   /* Another form is
     313              :      D.1987_7 = op0 & (1 << CST)
     314              :      if (D.1987_7 != 0)  */
     315        83712 :   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     316        10593 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
     317        94305 :       && integer_pow2p (gimple_assign_rhs2 (stmt)))
     318              :     {
     319         5613 :       *name = gimple_assign_rhs1 (stmt);
     320         5613 :       *bit = build_int_cst (integer_type_node,
     321         5613 :                             tree_log2 (gimple_assign_rhs2 (stmt)));
     322         5613 :       return true;
     323              :     }
     324              : 
     325              :   /* Another form is
     326              :      D.1986_6 = 1 << control1_4(D)
     327              :      D.1987_7 = op0 & D.1986_6
     328              :      if (D.1987_7 != 0)  */
     329        78099 :   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     330         4980 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
     331        83079 :       && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
     332              :     {
     333         3863 :       gimple *tmp;
     334              : 
     335              :       /* Both arguments of the BIT_AND_EXPR can be the single-bit
     336              :          specifying expression.  */
     337         3863 :       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
     338         3863 :       if (is_gimple_assign (tmp)
     339         3716 :           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
     340         3882 :           && integer_onep (gimple_assign_rhs1 (tmp)))
     341              :         {
     342           19 :           *name = gimple_assign_rhs2 (stmt);
     343           19 :           *bit = gimple_assign_rhs2 (tmp);
     344           19 :           return true;
     345              :         }
     346              : 
     347         3844 :       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
     348         3844 :       if (is_gimple_assign (tmp)
     349         3747 :           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
     350         3892 :           && integer_onep (gimple_assign_rhs1 (tmp)))
     351              :         {
     352           48 :           *name = gimple_assign_rhs1 (stmt);
     353           48 :           *bit = gimple_assign_rhs2 (tmp);
     354           48 :           return true;
     355              :         }
     356              :     }
     357              : 
     358              :   return false;
     359              : }
     360              : 
     361              : /* Recognize a bit test pattern in a GIMPLE_COND and its defining
     362              :    statements.  Store the name being tested in *NAME and the bits
     363              :    in *BITS.  The COND_EXPR computes *NAME & *BITS.
     364              :    Returns true if the pattern matched, false otherwise.  */
     365              : 
     366              : static bool
     367       458678 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
     368              : {
     369       458678 :   gimple *stmt;
     370              : 
     371              :   /* Get at the definition of the result of the bit test.  */
     372       458678 :   if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
     373       279411 :       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
     374       738076 :       || !integer_zerop (gimple_cond_rhs (cond)))
     375              :     return false;
     376        56485 :   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
     377        56485 :   if (!is_gimple_assign (stmt)
     378        56485 :       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
     379              :     return false;
     380              : 
     381        15907 :   *name = gimple_assign_rhs1 (stmt);
     382        15907 :   *bits = gimple_assign_rhs2 (stmt);
     383              : 
     384        15907 :   return true;
     385              : }
     386              : 
     387              : 
     388              : /* Update profile after code in either outer_cond_bb or inner_cond_bb was
     389              :    adjusted so that it has no condition.  */
     390              : 
     391              : static void
     392        94088 : update_profile_after_ifcombine (basic_block inner_cond_bb,
     393              :                                 basic_block outer_cond_bb)
     394              : {
     395              :   /* In the following we assume that inner_cond_bb has single predecessor.  */
     396        94088 :   gcc_assert (single_pred_p (inner_cond_bb));
     397              : 
     398        94088 :   basic_block outer_to_inner_bb = inner_cond_bb;
     399        94088 :   profile_probability prob = profile_probability::always ();
     400        94351 :   for (;;)
     401              :     {
     402        94351 :       basic_block parent = single_pred (outer_to_inner_bb);
     403        94351 :       prob *= find_edge (parent, outer_to_inner_bb)->probability;
     404        94351 :       if (parent == outer_cond_bb)
     405              :         break;
     406              :       outer_to_inner_bb = parent;
     407              :     }
     408              : 
     409        94088 :   edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
     410        94088 :   edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
     411        42431 :                  ? EDGE_SUCC (outer_cond_bb, 1)
     412       136519 :                  : EDGE_SUCC (outer_cond_bb, 0));
     413        94088 :   edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
     414        94088 :   edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
     415              : 
     416        94088 :   if (inner_taken->dest != outer2->dest)
     417        35983 :     std::swap (inner_taken, inner_not_taken);
     418        94088 :   gcc_assert (inner_taken->dest == outer2->dest);
     419              : 
     420        94088 :   if (outer_to_inner_bb == inner_cond_bb
     421        94088 :       && known_succ_p (outer_cond_bb))
     422              :     {
     423              :       /* Path outer_cond_bb->(outer2) needs to be merged into path
     424              :          outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
     425              :          and probability of inner_not_taken updated.  */
     426              : 
     427        93755 :       inner_cond_bb->count = outer_cond_bb->count;
     428              : 
     429              :       /* Handle special case where inner_taken probability is always. In this
     430              :          case we know that the overall outcome will be always as well, but
     431              :          combining probabilities will be conservative because it does not know
     432              :          that outer2->probability is inverse of
     433              :          outer_to_inner->probability.  */
     434        93755 :       if (inner_taken->probability == profile_probability::always ())
     435              :         ;
     436              :       else
     437        90555 :         inner_taken->probability = outer2->probability
     438        90555 :           + outer_to_inner->probability * inner_taken->probability;
     439        93755 :       inner_not_taken->probability = profile_probability::always ()
     440        93755 :         - inner_taken->probability;
     441              : 
     442        93755 :       outer_to_inner->probability = profile_probability::always ();
     443        93755 :       outer2->probability = profile_probability::never ();
     444              :     }
     445          333 :   else if (known_succ_p (inner_cond_bb))
     446              :     {
     447              :       /* Path inner_cond_bb->(inner_taken) needs to be merged into path
     448              :          outer_cond_bb->(outer2).  We've accumulated the probabilities from
     449              :          outer_cond_bb->(outer)->...->inner_cond_bb in prob, so we have to
     450              :          adjust that by inner_taken, and make inner unconditional.  */
     451              : 
     452          212 :       prob *= inner_taken->probability;
     453          212 :       outer2->probability += prob;
     454          212 :       outer_to_inner->probability = profile_probability::always ()
     455          212 :         - outer2->probability;
     456              : 
     457          212 :       inner_taken->probability = profile_probability::never ();
     458          212 :       inner_not_taken->probability = profile_probability::always ();
     459              :     }
     460              :   else
     461              :     {
     462              :       /* We've moved part of the inner cond to outer, but we don't know the
     463              :          probabilities for each part, so estimate the effects by moving half of
     464              :          the odds of inner_taken to outer.  */
     465              : 
     466          121 :       inner_taken->probability *= profile_probability::even ();
     467          121 :       inner_not_taken->probability = profile_probability::always ()
     468          121 :         - inner_taken->probability;
     469              : 
     470          121 :       prob *= inner_taken->probability;
     471          121 :       outer2->probability += prob;
     472          121 :       outer_to_inner->probability = profile_probability::always ()
     473          121 :         - outer2->probability;
     474              :     }
     475        94088 : }
     476              : 
     477              : /* Set NAME's bit in USED if OUTER dominates it.  */
     478              : 
     479              : static void
     480         1416 : ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
     481              : {
     482         1416 :   if (!name || TREE_CODE (name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (name))
     483              :     return;
     484              : 
     485          670 :   gimple *def = SSA_NAME_DEF_STMT (name);
     486          670 :   basic_block bb = gimple_bb (def);
     487          670 :   if (!dominated_by_p (CDI_DOMINATORS, bb, outer))
     488              :     return;
     489              : 
     490          463 :   bitmap_set_bit (used, SSA_NAME_VERSION (name));
     491              : }
     492              : 
     493              : /* Data structure passed to ifcombine_mark_ssa_name.  */
     494              : struct ifcombine_mark_ssa_name_t
     495              : {
     496              :   /* SSA_NAMEs that have been referenced.  */
     497              :   bitmap used;
     498              :   /* Dominating block of DEFs that might need moving.  */
     499              :   basic_block outer;
     500              : };
     501              : 
     502              : /* Mark in DATA->used any SSA_NAMEs used in *t.  */
     503              : 
     504              : static tree
     505         1392 : ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
     506              : {
     507         1392 :   ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_;
     508              : 
     509         1392 :   ifcombine_mark_ssa_name (data->used, *t, data->outer);
     510              : 
     511         1392 :   return NULL;
     512              : }
     513              : 
     514              : /* Rewrite a stmt, that presumably used to be guarded by conditions that could
     515              :    avoid undefined overflow, into one that has well-defined overflow, so that
     516              :    it won't invoke undefined behavior once the guarding conditions change.  */
     517              : 
     518              : static inline void
     519       426333 : ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
     520              : {
     521       426333 :   if (!gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
     522              :     return;
     523           36 :   rewrite_to_defined_unconditional (&gsi);
     524              : }
     525              : 
     526              : 
     527              : /* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
     528              :    COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
     529              :    replaced with a constant, but if there are intervening blocks, it's best to
     530              :    adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND.  */
     531              : 
     532              : static bool
     533        94204 : ifcombine_replace_cond (gcond *inner_cond, bool inner_inv,
     534              :                         gcond *outer_cond, bool outer_inv,
     535              :                         tree cond, bool must_canon, tree cond2)
     536              : {
     537        94204 :   bool split_single_cond = false;
     538              :   /* Split cond into cond2 if they're contiguous.  ??? We might be able to
     539              :      handle ORIF as well, inverting both conditions, but it's not clear that
     540              :      this would be enough, and it never comes up.  */
     541        94204 :   if (!cond2
     542        94198 :       && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
     543        94340 :       && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
     544              :     {
     545          115 :       cond2 = TREE_OPERAND (cond, 1);
     546          115 :       cond = TREE_OPERAND (cond, 0);
     547          115 :       split_single_cond = true;
     548              :     }
     549              : 
     550        94204 :   bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
     551        94083 :                            != gimple_bb (outer_cond));
     552              :   bool result_inv = outer_p ? outer_inv : inner_inv;
     553        94204 :   bool strictening_outer_cond = !split_single_cond && outer_p;
     554              : 
     555        94204 :   if (result_inv)
     556        59501 :     cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
     557              : 
     558        94204 :   if (tree tcanon = canonicalize_cond_expr_cond (cond))
     559         6112 :     cond = tcanon;
     560        88092 :   else if (must_canon)
     561              :     return false;
     562              : 
     563        94089 :   if (outer_p)
     564              :     {
     565          334 :       {
     566          334 :         auto_bitmap used;
     567          334 :         basic_block outer_bb = gimple_bb (outer_cond);
     568              : 
     569          334 :         bitmap_tree_view (used);
     570              : 
     571              :         /* Mark SSA DEFs that are referenced by cond and may thus need to be
     572              :            moved to outer.  */
     573          334 :         {
     574          334 :           ifcombine_mark_ssa_name_t data = { used, outer_bb };
     575          334 :           walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
     576              :         }
     577              : 
     578          334 :         if (!bitmap_empty_p (used))
     579              :           {
     580          241 :             const int max_stmts = 6;
     581          241 :             auto_vec<gimple *, max_stmts> stmts;
     582              : 
     583              :             /* Iterate up from inner_cond, moving DEFs identified as used by
     584              :                cond, and marking USEs in the DEFs for moving as well.  */
     585          651 :             for (basic_block bb = gimple_bb (inner_cond);
     586          651 :                  bb != outer_bb; bb = single_pred (bb))
     587              :               {
     588          822 :                 for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
     589         2748 :                      !gsi_end_p (gsitr); gsi_prev (&gsitr))
     590              :                   {
     591         1926 :                     gimple *stmt = gsi_stmt (gsitr);
     592         1926 :                     bool move = false;
     593         1926 :                     tree t;
     594         1926 :                     ssa_op_iter it;
     595              : 
     596         2927 :                     FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
     597         1143 :                       if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
     598              :                         {
     599              :                           move = true;
     600              :                           break;
     601              :                         }
     602              : 
     603         1926 :                     if (!move)
     604         1784 :                       continue;
     605              : 
     606          142 :                     if (stmts.length () < max_stmts)
     607          142 :                       stmts.quick_push (stmt);
     608              :                     else
     609            0 :                       return false;
     610              : 
     611              :                     /* Mark uses in STMT before moving it.  */
     612          162 :                     FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE)
     613           20 :                       ifcombine_mark_ssa_name (used, t, outer_bb);
     614              :                   }
     615              : 
     616              :                 /* Surprisingly, there may be PHI nodes in single-predecessor
     617              :                    bocks, as in pr50682.C.  Fortunately, since they can't
     618              :                    involve back edges, there won't be references to parallel
     619              :                    nodes that we'd have to pay special attention to to keep
     620              :                    them parallel.  We can't move the PHI nodes, but we can turn
     621              :                    them into assignments.  */
     622          411 :                 for (gphi_iterator gsi = gsi_start_phis (bb);
     623          415 :                      !gsi_end_p (gsi);)
     624              :                   {
     625            5 :                     gphi *phi = gsi.phi ();
     626              : 
     627            5 :                     gcc_assert (gimple_phi_num_args (phi) == 1);
     628            5 :                     tree def = gimple_phi_result (phi);
     629              : 
     630            5 :                     if (!bitmap_bit_p (used, SSA_NAME_VERSION (def)))
     631              :                       {
     632            0 :                         gsi_next (&gsi);
     633            0 :                         continue;
     634              :                       }
     635              : 
     636            5 :                     if (stmts.length () < max_stmts)
     637            4 :                       stmts.quick_push (phi);
     638              :                     else
     639            1 :                       return false;
     640              : 
     641              :                     /* Mark uses in STMT before moving it.  */
     642            4 :                     use_operand_p use_p;
     643            4 :                     ssa_op_iter it;
     644            8 :                     FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
     645            4 :                       ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p),
     646              :                                                outer_bb);
     647              :                   }
     648              :               }
     649              : 
     650              :             /* ??? Test whether it makes sense to move STMTS.  */
     651              : 
     652              :             /* Move the STMTS that need moving.  From this point on, we're
     653              :                committing to the attempted ifcombine.  */
     654          240 :             gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
     655          240 :             unsigned i;
     656          240 :             gimple *stmt;
     657          620 :             FOR_EACH_VEC_ELT (stmts, i, stmt)
     658              :               {
     659          140 :                 if (gphi *phi = dyn_cast <gphi *> (stmt))
     660              :                   {
     661            0 :                     tree def = gimple_phi_result (phi);
     662            0 :                     tree use = gimple_phi_arg_def (phi, 0);
     663            0 :                     location_t loc = gimple_phi_arg_location (phi, 0);
     664              : 
     665            0 :                     gphi_iterator gsi = gsi_for_phi (phi);
     666            0 :                     remove_phi_node (&gsi, false);
     667              : 
     668            0 :                     gassign *a = gimple_build_assign (def, use);
     669            0 :                     gimple_set_location (a, loc);
     670            0 :                     gsi_insert_before (&gsins, a, GSI_NEW_STMT);
     671              :                   }
     672              :                 else
     673              :                   {
     674          140 :                     gimple_stmt_iterator gsitr = gsi_for_stmt (stmt);
     675          140 :                     gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT);
     676              :                   }
     677              :               }
     678              : 
     679          380 :             for (; gsi_stmt (gsins) != outer_cond; gsi_next (&gsins))
     680              :               {
     681              :                 /* Clear range info from all defs we've moved from under
     682              :                    conditions.  */
     683          140 :                 tree t;
     684          140 :                 ssa_op_iter it;
     685          280 :                 FOR_EACH_SSA_TREE_OPERAND (t, gsi_stmt (gsins), it, SSA_OP_DEF)
     686          140 :                   reset_flow_sensitive_info (t);
     687              :                 /* Avoid introducing undefined overflows while at that.  */
     688          140 :                 ifcombine_rewrite_to_defined_overflow (gsins);
     689              :               }
     690          241 :           }
     691            1 :       }
     692              : 
     693          333 :       if (!is_gimple_condexpr_for_cond (cond))
     694              :         {
     695           99 :           gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond);
     696           99 :           cond = force_gimple_operand_gsi_1 (&gsi, cond,
     697              :                                              is_gimple_condexpr_for_cond,
     698              :                                              NULL, true, GSI_SAME_STMT);
     699              :         }
     700              : 
     701              :       /* Leave CFG optimization to cfg_cleanup.  */
     702          333 :       gimple_cond_set_condition_from_tree (outer_cond, cond);
     703          333 :       update_stmt (outer_cond);
     704              : 
     705          333 :       if (cond2)
     706              :         {
     707          121 :           if (inner_inv)
     708          115 :             cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2);
     709              : 
     710          121 :           if (tree tcanon = canonicalize_cond_expr_cond (cond2))
     711           49 :             cond2 = tcanon;
     712          121 :           if (!is_gimple_condexpr_for_cond (cond2))
     713              :             {
     714           72 :               gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
     715           72 :               cond2 = force_gimple_operand_gsi_1 (&gsi, cond2,
     716              :                                                   is_gimple_condexpr_for_cond,
     717              :                                                   NULL, true, GSI_SAME_STMT);
     718              :             }
     719          121 :           gimple_cond_set_condition_from_tree (inner_cond, cond2);
     720              :         }
     721              :       else
     722          212 :         gimple_cond_set_condition_from_tree (inner_cond,
     723              :                                              inner_inv
     724              :                                              ? boolean_false_node
     725              :                                              : boolean_true_node);
     726          333 :       update_stmt (inner_cond);
     727              :     }
     728              :   else
     729              :     {
     730        93755 :       if (!is_gimple_condexpr_for_cond (cond))
     731              :         {
     732        87878 :           gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
     733        87878 :           cond = force_gimple_operand_gsi_1 (&gsi, cond,
     734              :                                              is_gimple_condexpr_for_cond,
     735              :                                              NULL, true, GSI_SAME_STMT);
     736              :         }
     737        93755 :       gimple_cond_set_condition_from_tree (inner_cond, cond);
     738        93755 :       update_stmt (inner_cond);
     739              : 
     740              :       /* Leave CFG optimization to cfg_cleanup.  */
     741        93755 :       gimple_cond_set_condition_from_tree (outer_cond,
     742              :                                            outer_inv
     743              :                                            ? boolean_false_node
     744              :                                            : boolean_true_node);
     745        93755 :       update_stmt (outer_cond);
     746              :     }
     747              : 
     748              :   /* We're changing conditions that guard inner blocks, so reset flow sensitive
     749              :      info and avoid introducing undefined behavior.  */
     750       188439 :   for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond);
     751       188439 :        bb != end; bb = single_pred (bb))
     752              :     {
     753              :       /* Clear range info from all stmts in BB which is now guarded by
     754              :          different conditionals.  */
     755        94351 :       reset_flow_sensitive_info_in_bb (gimple_bb (inner_cond));
     756              : 
     757              :       /* We only need to worry about introducing undefined behavior if we've
     758              :          relaxed the outer condition.  */
     759        94351 :       if (strictening_outer_cond)
     760          481 :         continue;
     761              : 
     762              :       /* Avoid introducing undefined behavior as we move stmts that used to be
     763              :          guarded by OUTER_COND.  */
     764       187740 :       for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond));
     765       520063 :            !gsi_end_p (gsi); gsi_next (&gsi))
     766       426193 :         ifcombine_rewrite_to_defined_overflow (gsi);
     767              :     }
     768              : 
     769        94088 :   update_profile_after_ifcombine (gimple_bb (inner_cond),
     770              :                                   gimple_bb (outer_cond));
     771              : 
     772        94088 :   return true;
     773              : }
     774              : 
     775              : /* Returns true if inner_cond_bb contains just the condition or 1/2 statements
     776              :    that define lhs or rhs with an integer conversion. */
     777              : 
     778              : static bool
     779       225706 : can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
     780              : {
     781       225706 :   gimple_stmt_iterator gsi;
     782       225706 :   gsi = gsi_start_nondebug_after_labels_bb (inner_cond_bb);
     783              :   /* If only the condition, this should be allowed. */
     784       225706 :   if (gsi_one_before_end_p (gsi))
     785              :     return true;
     786              :   /* Can have up to 2 statements defining each of lhs/rhs. */
     787       145847 :   for (int i = 0; i < 2; i++)
     788              :     {
     789       145847 :       gimple *stmt = gsi_stmt (gsi);
     790       145847 :       if (!is_gimple_assign (stmt)
     791       145847 :           || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
     792              :         return false;
     793              :       /* The defining statement needs to match either the lhs or rhs of
     794              :          the condition. */
     795        11644 :       if (lhs != gimple_assign_lhs (stmt)
     796        11644 :           && rhs != gimple_assign_lhs (stmt))
     797              :         return false;
     798         4701 :       gsi_next_nondebug (&gsi);
     799         5343 :       if (gsi_one_before_end_p (gsi))
     800              :         return true;
     801              :     }
     802              :   return false;
     803              : }
     804              : 
     805              : /* Return true if BB guards entry to a loop: a successor edge reaches a loop
     806              :    header BB does not belong to, directly or through a single-successor
     807              :    preheader.  Combining the scalar conditions guarding a loop into a single
     808              :    boolean leaves the number-of-iterations analysis unable to prove the loop
     809              :    runs at least once, pessimizing later loop passes such as ivopts.  */
     810              : 
     811              : static bool
     812       471737 : bb_guards_loop_p (basic_block bb)
     813              : {
     814       471737 :   edge e;
     815       471737 :   edge_iterator ei;
     816      1376302 :   FOR_EACH_EDGE (e, ei, bb->succs)
     817              :     {
     818       933063 :       basic_block h = e->dest;
     819       933063 :       if (single_succ_p (h) && !bb_loop_header_p (h))
     820       373628 :         h = single_succ (h);
     821       933063 :       if (bb_loop_header_p (h) && !dominated_by_p (CDI_DOMINATORS, bb, h))
     822              :         return true;
     823              :     }
     824              :   return false;
     825              : }
     826              : 
     827              : /* If-convert on a and pattern with a common else block.  The inner
     828              :    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
     829              :    inner_inv, outer_inv indicate whether the conditions are inverted.
     830              :    Returns true if the edges to the common else basic-block were merged.  */
     831              : 
     832              : static bool
     833       532703 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
     834              :                    basic_block outer_cond_bb, bool outer_inv)
     835              : {
     836       532703 :   gimple_stmt_iterator gsi;
     837       532703 :   tree name1, name2, bit1, bit2, bits1, bits2;
     838              : 
     839      1065406 :   gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
     840       532703 :   if (!inner_cond)
     841              :     return false;
     842              : 
     843      1065406 :   gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
     844       532703 :   if (!outer_cond)
     845              :     return false;
     846              : 
     847              :   /* If the inner condition can trap, there is no combining unless
     848              :      the operands are the same.  */
     849       532703 :   if (gimple_could_trap_p (inner_cond))
     850              :     {
     851         6398 :       if (!operand_equal_p (gimple_cond_lhs (inner_cond),
     852         6398 :                             gimple_cond_lhs (outer_cond))
     853         9249 :           || !operand_equal_p (gimple_cond_rhs (inner_cond),
     854         2851 :                                gimple_cond_rhs (outer_cond)))
     855              :         return false;
     856              :      // We don't check if the outer will cause a trap as combine_comparisons
     857              :      // will take care if the combining happens or not. Specifically in the
     858              :      // case of losing a trap or cause a trap that was not there before.
     859          679 :      tree res = NULL_TREE;
     860          679 :      tree_code outer_cond_code = gimple_cond_code (outer_cond);
     861          679 :      tree_code inner_cond_code = gimple_cond_code (inner_cond);
     862          679 :      tree larg = gimple_cond_lhs (inner_cond);
     863          679 :      tree rarg = gimple_cond_rhs (inner_cond);
     864              :      // Handle `(a && b)`, no inverse
     865          679 :      if (!inner_inv && !outer_inv)
     866          256 :         res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
     867              :                                    outer_cond_code, inner_cond_code,
     868              :                                    boolean_type_node, boolean_type_node,
     869              :                                    larg, rarg);
     870              :       // If both are inverse, `!a && !b`, then handle it as `!(a || b)`
     871              :       // As that !a or !b are most likely not producing a comparison code.
     872          423 :       else if (inner_inv && outer_inv)
     873              :         {
     874          132 :           res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ORIF_EXPR,
     875              :                                      outer_cond_code, inner_cond_code,
     876              :                                      boolean_type_node, boolean_type_node,
     877              :                                      larg, rarg);
     878          132 :           if (res)
     879          120 :             res = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (res), res);
     880              :         }
     881              :       else
     882              :         {
     883              :           // Handles the case where one is inverted and the other is not.
     884          291 :           tree_code inner_cond_code1 = inner_cond_code;
     885          291 :           tree_code outer_cond_code1 = outer_cond_code;
     886              :           // Try first `!a && b` and `a && !b`, those might be invertable.
     887          291 :           if (inner_inv)
     888          236 :             inner_cond_code1 = invert_tree_comparison (inner_cond_code1,
     889              :                                                        HONOR_NANS (larg));
     890           55 :           else if (outer_inv)
     891           55 :             outer_cond_code1 = invert_tree_comparison (outer_cond_code1,
     892              :                                                        HONOR_NANS (larg));
     893          291 :           if (inner_cond_code1 != ERROR_MARK && outer_cond_code1 != ERROR_MARK)
     894          224 :             res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
     895              :                                        outer_cond_code1, inner_cond_code1,
     896              :                                        boolean_type_node, boolean_type_node,
     897              :                                        larg, rarg);
     898              :           // Otherwise, we need to try `!(!a || b)
     899           67 :           else if (inner_cond_code1 == ERROR_MARK)
     900              :             {
     901              :               // a && !b -> !(!a || b)
     902           32 :               outer_cond_code1 = invert_tree_comparison (outer_cond_code,
     903              :                                                          HONOR_NANS (larg));
     904           32 :               if (outer_cond_code1 != ERROR_MARK)
     905           12 :                 res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ORIF_EXPR,
     906              :                                            outer_cond_code1, inner_cond_code,
     907              :                                            boolean_type_node, boolean_type_node,
     908              :                                            larg, rarg);
     909           12 :               if (res)
     910           12 :                 res = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (res), res);
     911              :             }
     912              :           // Or `!(a || !b)`
     913              :           else
     914              :             {
     915              :               // !a && b -> !(a || !b)
     916           35 :               inner_cond_code1 = invert_tree_comparison (inner_cond_code,
     917              :                                                          HONOR_NANS (larg));
     918           35 :               if (inner_cond_code1 != ERROR_MARK)
     919            0 :                 res = combine_comparisons (UNKNOWN_LOCATION, TRUTH_ORIF_EXPR,
     920              :                                            outer_cond_code, inner_cond_code1,
     921              :                                            boolean_type_node, boolean_type_node,
     922              :                                            larg, rarg);
     923            0 :               if (res)
     924            0 :                 res = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (res), res);
     925              :             }
     926              :         }
     927          612 :       if (res)
     928              :         {
     929          493 :           if (!ifcombine_replace_cond (inner_cond, inner_inv,
     930              :                                        outer_cond, outer_inv,
     931              :                                        res, true, NULL_TREE))
     932              :             return false;
     933              : 
     934          378 :           if (dump_file)
     935              :             {
     936            5 :               fprintf (dump_file, "optimizing trapping cond to ");
     937            5 :               print_generic_expr (dump_file, res);
     938            5 :               fprintf (dump_file, "\n");
     939              :             }
     940              :           return true;
     941              :         }
     942              :       return false;
     943              :     }
     944              : 
     945              :   /* niter analysis does not cope with boolean typed loop exit conditions, nor
     946              :      with boolean loop guards.  Avoid turning an analyzable loop exit or guard
     947              :      into an unanalyzable one.  */
     948       526305 :   if ((inner_cond_bb->loop_father == outer_cond_bb->loop_father
     949       526305 :        && loop_exits_from_bb_p (inner_cond_bb->loop_father, inner_cond_bb)
     950        60957 :        && loop_exits_from_bb_p (outer_cond_bb->loop_father, outer_cond_bb))
     951       998042 :       || bb_guards_loop_p (inner_cond_bb))
     952              :     {
     953        83066 :       tree outer_type = TREE_TYPE (gimple_cond_lhs (outer_cond));
     954        83066 :       tree inner_type = TREE_TYPE (gimple_cond_lhs (inner_cond));
     955        83066 :       if (TREE_CODE (outer_type) == INTEGER_TYPE
     956        20993 :           || POINTER_TYPE_P (outer_type)
     957        11424 :           || TREE_CODE (inner_type) == INTEGER_TYPE
     958         6784 :           || POINTER_TYPE_P (inner_type))
     959              :         return false;
     960              :     }
     961              : 
     962              :   /* See if we test a single bit of the same name in both tests.  In
     963              :      that case remove the outer test, merging both else edges,
     964              :      and change the inner one to test for
     965              :      name & (bit1 | bit2) == (bit1 | bit2).  */
     966       449100 :   if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
     967         4098 :       && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
     968       451179 :       && name1 == name2)
     969              :     {
     970         1018 :       tree t, t2;
     971              : 
     972         1018 :       if (TREE_CODE (name1) == SSA_NAME
     973         1018 :           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
     974              :         return false;
     975              : 
     976              :       /* Do it.  */
     977         1018 :       gsi = gsi_for_stmt (inner_cond);
     978         1018 :       location_t loc1 = gimple_location (inner_cond);
     979         1018 :       location_t loc2 = gimple_location (outer_cond);
     980         2036 :       t = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, LSHIFT_EXPR,
     981         1018 :                         TREE_TYPE (name1),
     982         1018 :                         build_int_cst (TREE_TYPE (name1), 1), bit1);
     983         2036 :       t2 = gimple_build (&gsi, true, GSI_SAME_STMT, loc2, LSHIFT_EXPR,
     984         1018 :                          TREE_TYPE (name1),
     985         1018 :                          build_int_cst (TREE_TYPE (name1), 1), bit2);
     986         1018 :       t = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, BIT_IOR_EXPR,
     987         1018 :                         TREE_TYPE (name1), t, t2);
     988         1018 :       t2 = gimple_build (&gsi, true, GSI_SAME_STMT, loc1, BIT_AND_EXPR,
     989         1018 :                          TREE_TYPE (name1), name1, t);
     990              : 
     991         1018 :       t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
     992              : 
     993         1018 :       if (!ifcombine_replace_cond (inner_cond, inner_inv,
     994              :                                    outer_cond, outer_inv,
     995              :                                    t, true, NULL_TREE))
     996              :         return false;
     997              : 
     998         1018 :       if (dump_file)
     999              :         {
    1000            1 :           fprintf (dump_file, "optimizing double bit test to ");
    1001            1 :           print_generic_expr (dump_file, name1);
    1002            1 :           fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
    1003            1 :           print_generic_expr (dump_file, bit1);
    1004            1 :           fprintf (dump_file, ") | (1 << ");
    1005            1 :           print_generic_expr (dump_file, bit2);
    1006            1 :           fprintf (dump_file, ")\n");
    1007              :         }
    1008              : 
    1009              :       return true;
    1010              :     }
    1011              : 
    1012              :   /* See if we have two bit tests of the same name in both tests.
    1013              :      In that case remove the outer test and change the inner one to
    1014              :      test for name & (bits1 | bits2) != 0.  */
    1015       448082 :   else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
    1016       448082 :            && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
    1017              :     {
    1018         5311 :       tree t;
    1019              : 
    1020         5311 :       if ((TREE_CODE (name1) == SSA_NAME
    1021         5311 :            && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
    1022         5311 :           || (TREE_CODE (name2) == SSA_NAME
    1023         5311 :               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2))
    1024         5311 :           || (TREE_CODE (bits1) == SSA_NAME
    1025         3285 :               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (bits1))
    1026        10622 :           || (TREE_CODE (bits2) == SSA_NAME
    1027         3305 :               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (bits2)))
    1028              :         return false;
    1029              : 
    1030              :       /* Find the common name which is bit-tested.  */
    1031         5311 :       if (name1 == name2)
    1032              :         ;
    1033         3761 :       else if (bits1 == bits2)
    1034              :         {
    1035           86 :           std::swap (name2, bits2);
    1036           86 :           std::swap (name1, bits1);
    1037              :         }
    1038         3675 :       else if (name1 == bits2)
    1039            6 :         std::swap (name2, bits2);
    1040         3669 :       else if (bits1 == name2)
    1041            0 :         std::swap (name1, bits1);
    1042              :       else
    1043              :         {
    1044              :           /* Look through non-widening conversions, but only on the names
    1045              :              so that a stripped operand never becomes part of the mask.  */
    1046         3669 :           tree t1 = get_name_for_bit_test (name1);
    1047         3669 :           tree t2 = get_name_for_bit_test (name2);
    1048         3669 :           if (t1 != t2)
    1049         3658 :             goto bits_test_failed;
    1050           11 :           name1 = name2 = t1;
    1051              :         }
    1052              : 
    1053         1653 :       if (TREE_CODE (name1) == SSA_NAME
    1054         1653 :           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
    1055              :         return false;
    1056              : 
    1057              :       /* As we strip non-widening conversions in finding a common
    1058              :          name that is tested make sure to end up with an integral
    1059              :          type for building the bit operations.  */
    1060         1653 :       if (TYPE_PRECISION (TREE_TYPE (bits1))
    1061         1653 :           >= TYPE_PRECISION (TREE_TYPE (bits2)))
    1062              :         {
    1063         1653 :           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
    1064         1653 :           name1 = fold_convert (TREE_TYPE (bits1), name1);
    1065         1653 :           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
    1066         1653 :           bits2 = fold_convert (TREE_TYPE (bits1), bits2);
    1067              :         }
    1068              :       else
    1069              :         {
    1070            0 :           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
    1071            0 :           name1 = fold_convert (TREE_TYPE (bits2), name1);
    1072            0 :           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
    1073            0 :           bits1 = fold_convert (TREE_TYPE (bits2), bits1);
    1074              :         }
    1075              : 
    1076         1653 :       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
    1077         1653 :       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
    1078         1653 :       t = fold_build2 (EQ_EXPR, boolean_type_node, t,
    1079              :                        build_int_cst (TREE_TYPE (t), 0));
    1080         1653 :       if (!ifcombine_replace_cond (inner_cond, inner_inv,
    1081              :                                    outer_cond, outer_inv,
    1082              :                                    t, false, NULL_TREE))
    1083              :         return false;
    1084              : 
    1085         1653 :       if (dump_file)
    1086              :         {
    1087            3 :           fprintf (dump_file, "optimizing bits or bits test to ");
    1088            3 :           print_generic_expr (dump_file, name1);
    1089            3 :           fprintf (dump_file, " & T != 0\nwith temporary T = ");
    1090            3 :           print_generic_expr (dump_file, bits1);
    1091            3 :           fprintf (dump_file, " | ");
    1092            3 :           print_generic_expr (dump_file, bits2);
    1093            3 :           fprintf (dump_file, "\n");
    1094              :         }
    1095              : 
    1096              :       return true;
    1097              :     }
    1098              : 
    1099              :   /* See if we have two comparisons that we can merge into one.  */
    1100              :   else
    1101              :     {
    1102       446429 :     bits_test_failed:
    1103       446429 :       tree t, ts = NULL_TREE;
    1104       446429 :       enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
    1105       446429 :       enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
    1106              : 
    1107              :       /* Invert comparisons if necessary (and possible).  */
    1108       446429 :       if (inner_inv)
    1109       284994 :         inner_cond_code = invert_tree_comparison (inner_cond_code,
    1110       284994 :           HONOR_NANS (gimple_cond_lhs (inner_cond)));
    1111       446429 :       if (inner_cond_code == ERROR_MARK)
    1112              :         return false;
    1113       444749 :       if (outer_inv)
    1114       277809 :         outer_cond_code = invert_tree_comparison (outer_cond_code,
    1115       277809 :           HONOR_NANS (gimple_cond_lhs (outer_cond)));
    1116       444749 :       if (outer_cond_code == ERROR_MARK)
    1117              :         return false;
    1118              :       /* Don't return false so fast, try maybe_fold_or_comparisons?  */
    1119              : 
    1120       444046 :       if (!(t = maybe_fold_and_comparisons (boolean_type_node,
    1121              :                                             TRUTH_ANDIF_EXPR, outer_cond_code,
    1122              :                                             gimple_cond_lhs (outer_cond),
    1123              :                                             gimple_cond_rhs (outer_cond),
    1124              :                                             inner_cond_code,
    1125              :                                             gimple_cond_lhs (inner_cond),
    1126              :                                             gimple_cond_rhs (inner_cond),
    1127              :                                             gimple_bb (outer_cond)))
    1128       444046 :           && !(t = (fold_truth_andor_for_ifcombine
    1129       440944 :                     (TRUTH_ANDIF_EXPR, boolean_type_node,
    1130              :                      gimple_location (outer_cond),
    1131              :                      outer_cond_code,
    1132              :                      gimple_cond_lhs (outer_cond),
    1133              :                      gimple_cond_rhs (outer_cond),
    1134              :                      gimple_location (inner_cond),
    1135              :                      inner_cond_code,
    1136              :                      gimple_cond_lhs (inner_cond),
    1137              :                      gimple_cond_rhs (inner_cond),
    1138       440944 :                      single_pred (inner_cond_bb) != outer_cond_bb
    1139              :                      ? &ts : 0))))
    1140              :         {
    1141              :           /* Only combine conditions in this fallback case if the blocks are
    1142              :              neighbors.  */
    1143       437566 :           if (single_pred (inner_cond_bb) != outer_cond_bb)
    1144              :             return false;
    1145       225854 :           tree t1, t2;
    1146       225854 :           bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
    1147       225854 :           if (param_logical_op_non_short_circuit != -1)
    1148          175 :             logical_op_non_short_circuit
    1149          175 :               = param_logical_op_non_short_circuit;
    1150       225854 :           if (!logical_op_non_short_circuit || sanitize_coverage_p ())
    1151              :             return false;
    1152              :           /* Only do this optimization if the inner bb contains only the conditional
    1153              :              or there is one or 2 statements which are nop conversion for the comparison. */
    1154       225706 :           if (!can_combine_bbs_with_short_circuit (inner_cond_bb,
    1155              :                                                    gimple_cond_lhs (inner_cond),
    1156              :                                                    gimple_cond_rhs (inner_cond)))
    1157              :             return false;
    1158        84560 :           t1 = fold_build2_loc (gimple_location (inner_cond),
    1159              :                                 inner_cond_code,
    1160              :                                 boolean_type_node,
    1161              :                                 gimple_cond_lhs (inner_cond),
    1162              :                                 gimple_cond_rhs (inner_cond));
    1163        84560 :           t2 = fold_build2_loc (gimple_location (outer_cond),
    1164              :                                 outer_cond_code,
    1165              :                                 boolean_type_node,
    1166              :                                 gimple_cond_lhs (outer_cond),
    1167              :                                 gimple_cond_rhs (outer_cond));
    1168        84560 :           t = fold_build2_loc (gimple_location (inner_cond),
    1169              :                                TRUTH_AND_EXPR, boolean_type_node, t1, t2);
    1170              :         }
    1171              : 
    1172        91040 :       if (!ifcombine_replace_cond (inner_cond, inner_inv,
    1173              :                                    outer_cond, outer_inv,
    1174              :                                    t, false, ts))
    1175              :         return false;
    1176              : 
    1177        91039 :       if (dump_file)
    1178              :         {
    1179           49 :           fprintf (dump_file, "optimizing two comparisons to ");
    1180           49 :           print_generic_expr (dump_file, t);
    1181           49 :           if (ts)
    1182              :             {
    1183            0 :               fprintf (dump_file, " and ");
    1184            0 :               print_generic_expr (dump_file, ts);
    1185              :             }
    1186           49 :           fprintf (dump_file, "\n");
    1187              :         }
    1188              : 
    1189              :       return true;
    1190              :     }
    1191              : 
    1192              :   return false;
    1193              : }
    1194              : 
    1195              : /* Helper function for tree_ssa_ifcombine_bb.  Recognize a CFG pattern and
    1196              :    dispatch to the appropriate if-conversion helper for a particular
    1197              :    set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
    1198              :    PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
    1199              :    OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
    1200              :    INNER_COND_BB.  */
    1201              : 
    1202              : static bool
    1203      1616965 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
    1204              :                          basic_block then_bb, basic_block else_bb,
    1205              :                          basic_block phi_pred_bb, basic_block outer_succ_bb)
    1206              : {
    1207              :   /* The && form is characterized by a common else_bb with
    1208              :      the two edges leading to it mergeable.  The latter is
    1209              :      guaranteed by matching PHI arguments in the else_bb and
    1210              :      the inner cond_bb having no side-effects.  */
    1211      1616965 :   if (phi_pred_bb != else_bb
    1212      1593644 :       && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
    1213      1821663 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
    1214              :     {
    1215              :       /* We have
    1216              :            <outer_cond_bb>
    1217              :              if (q) goto inner_cond_bb; else goto else_bb;
    1218              :            <inner_cond_bb>
    1219              :              if (p) goto ...; else goto else_bb;
    1220              :              ...
    1221              :            <else_bb>
    1222              :              ...
    1223              :        */
    1224       194786 :       return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false);
    1225              :     }
    1226              : 
    1227              :   /* And a version where the outer condition is negated.  */
    1228      1422179 :   if (phi_pred_bb != else_bb
    1229      1398858 :       && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
    1230      1441604 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
    1231              :     {
    1232              :       /* We have
    1233              :            <outer_cond_bb>
    1234              :              if (q) goto else_bb; else goto inner_cond_bb;
    1235              :            <inner_cond_bb>
    1236              :              if (p) goto ...; else goto else_bb;
    1237              :              ...
    1238              :            <else_bb>
    1239              :              ...
    1240              :        */
    1241        11028 :       return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true);
    1242              :     }
    1243              : 
    1244              :   /* The || form is characterized by a common then_bb with the
    1245              :      two edges leading to it mergeable.  The latter is guaranteed
    1246              :      by matching PHI arguments in the then_bb and the inner cond_bb
    1247              :      having no side-effects.  */
    1248      1411151 :   if (phi_pred_bb != then_bb
    1249      1397273 :       && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
    1250      1742155 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
    1251              :     {
    1252              :       /* We have
    1253              :            <outer_cond_bb>
    1254              :              if (q) goto then_bb; else goto inner_cond_bb;
    1255              :            <inner_cond_bb>
    1256              :              if (p) goto then_bb; else goto ...;
    1257              :            <then_bb>
    1258              :              ...
    1259              :        */
    1260       307110 :       return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true);
    1261              :     }
    1262              : 
    1263              :   /* And a version where the outer condition is negated.  */
    1264      1104041 :   if (phi_pred_bb != then_bb
    1265      1090163 :       && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
    1266      1131217 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
    1267              :     {
    1268              :       /* We have
    1269              :            <outer_cond_bb>
    1270              :              if (q) goto inner_cond_bb; else goto then_bb;
    1271              :            <inner_cond_bb>
    1272              :              if (p) goto then_bb; else goto ...;
    1273              :            <then_bb>
    1274              :              ...
    1275              :        */
    1276        19779 :       return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false);
    1277              :     }
    1278              : 
    1279              :   return false;
    1280              : }
    1281              : 
    1282              : /* Recognize a CFG pattern and dispatch to the appropriate
    1283              :    if-conversion helper.  We start with BB as the innermost
    1284              :    worker basic-block.  Returns true if a transformation was done.  */
    1285              : 
    1286              : bool
    1287      5514698 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
    1288              : {
    1289      5514698 :   bool ret = false;
    1290      5514698 :   basic_block then_bb = NULL, else_bb = NULL;
    1291              : 
    1292      5514698 :   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
    1293              :     return ret;
    1294              : 
    1295              :   /* Recognize && and || of two conditions with a common
    1296              :      then/else block which entry edges we can merge.  That is:
    1297              :        if (a || b)
    1298              :          ;
    1299              :      and
    1300              :        if (a && b)
    1301              :          ;
    1302              :      This requires a single predecessor of the inner cond_bb.
    1303              : 
    1304              :      Look for an OUTER_COND_BBs to combine with INNER_COND_BB.  They need not
    1305              :      be contiguous, as long as inner and intervening blocks have no side
    1306              :      effects, and are either single-entry-single-exit or conditionals choosing
    1307              :      between the same EXIT_BB with the same PHI args, possibly through an
    1308              :      EXIT_PRED, and the path leading to INNER_COND_BB.  EXIT_PRED will be set
    1309              :      just before (along with a successful combination) or just after setting
    1310              :      EXIT_BB, to either THEN_BB, ELSE_BB, or INNER_COND_BB.  ??? We could
    1311              :      potentially handle multi-block single-entry-single-exit regions, but the
    1312              :      loop below only deals with single-entry-single-exit individual intervening
    1313              :      blocks.  Larger regions without side effects are presumably rare, so it's
    1314              :      probably not worth the effort.  */
    1315      6292989 :   for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL,
    1316              :          /* This initialization shouldn't be needed, but in case the compiler
    1317              :             is not smart enough to tell, make it harmless.  */
    1318      5514446 :          exit_pred = NULL;
    1319      6292989 :        single_pred_p (bb) && bb_no_side_effects_p (bb);
    1320       778543 :        bb = outer_cond_bb)
    1321              :     {
    1322      2086899 :       bool changed = false;
    1323              : 
    1324      2086899 :       outer_cond_bb = single_pred (bb);
    1325              : 
    1326              :       /* Skip blocks without conditions.  */
    1327      2086899 :       if (single_succ_p (outer_cond_bb))
    1328       189679 :         continue;
    1329              : 
    1330              :       /* When considering noncontiguous conditions, make sure that all
    1331              :          non-final conditions lead to the same successor of the final
    1332              :          condition, when not taking the path to inner_bb, so that we can
    1333              :          combine C into A, both in A && (B && C), and in A || (B || C), but
    1334              :          neither in A && (B || C), nor A || (B && C).  Say, if C goes to
    1335              :          THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
    1336              :          C (whether C is then or else), and A must go to X and B (whether then
    1337              :          or else).
    1338              : 
    1339              :          We test for this, while allowing intervening nonconditional blocks, by
    1340              :          first taking note of which of the successors of the inner conditional
    1341              :          block is the exit path taken by the first considered outer conditional
    1342              :          block.
    1343              : 
    1344              :          Having identified and saved the exit block in EXIT_BB at the end of
    1345              :          the loop, here we test that subsequent conditional blocks under
    1346              :          consideration also use the exit block as a successor, besides the
    1347              :          block that leads to inner_cond_bb, and that the edges to exit share
    1348              :          the same phi values.  */
    1349      1897220 :       if (exit_bb
    1350      1897220 :           && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
    1351              :         break;
    1352              : 
    1353              :       /* After checking dests and phi args, we can also skip blocks whose
    1354              :          conditions have been optimized down to a constant, without trying to
    1355              :          combine them, but we must not skip the computation of EXIT_BB and the
    1356              :          checking of same phi args.  */
    1357      1831259 :       if (known_succ_p (outer_cond_bb))
    1358              :         changed = false;
    1359       232276 :       else if ((!exit_bb || exit_pred == inner_cond_bb)
    1360      1811730 :                && tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
    1361              :                                            then_bb, else_bb, inner_cond_bb, bb))
    1362              :         changed = true, exit_pred = inner_cond_bb;
    1363      1485806 :       else if (exit_bb
    1364      1485806 :                ? exit_pred == else_bb
    1365      1253664 :                : forwarder_block_to (else_bb, then_bb))
    1366              :         {
    1367              :           /* Other possibilities for the && form, if else_bb is
    1368              :              empty forwarder block to then_bb.  Compared to the above simpler
    1369              :              forms this can be treated as if then_bb and else_bb were swapped,
    1370              :              and the corresponding inner_cond_bb not inverted because of that.
    1371              :              For same_phi_args_p we look at equality of arguments between
    1372              :              edge from outer_cond_bb and the forwarder block.  */
    1373        14190 :           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
    1374              :                                        then_bb, else_bb, bb))
    1375          192 :             changed = true, exit_pred = else_bb;
    1376              :         }
    1377      1471616 :       else if (exit_bb
    1378      1471616 :                ? exit_pred == then_bb
    1379      1239494 :                : forwarder_block_to (then_bb, else_bb))
    1380              :         {
    1381              :           /* Other possibilities for the || form, if then_bb is
    1382              :              empty forwarder block to else_bb.  Compared to the above simpler
    1383              :              forms this can be treated as if then_bb and else_bb were swapped,
    1384              :              and the corresponding inner_cond_bb not inverted because of that.
    1385              :              For same_phi_args_p we look at equality of arguments between
    1386              :              edge from outer_cond_bb and the forwarder block.  */
    1387        23321 :           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
    1388              :                                        then_bb, then_bb, bb))
    1389          188 :             changed = true, exit_pred = then_bb;
    1390              :         }
    1391              : 
    1392          380 :       if (changed)
    1393        94088 :         ret = changed;
    1394              : 
    1395              :       /* If the inner condition is gone, there's no point in attempting to
    1396              :          combine it any further.  */
    1397        94088 :       if (changed && known_succ_p (inner_cond_bb))
    1398              :         break;
    1399              : 
    1400              :       /* Starting at this point in the loop, we start preparing to attempt
    1401              :          combinations in which OUTER_COND_BB will be an intervening block.
    1402              :          Checking that it has a single predecessor is a very cheap test, unlike
    1403              :          the PHI args tests below, so test it early and hopefully save the more
    1404              :          expensive tests in case we won't be able to try other blocks.  */
    1405      1831029 :       if (!single_pred_p (outer_cond_bb))
    1406              :         break;
    1407              : 
    1408              :       /* Record the exit path taken by the outer condition.  */
    1409      1365026 :       if (!exit_bb)
    1410              :         {
    1411              :           /* If we have removed the outer condition entirely, we need not
    1412              :              commit to an exit block yet, it's as if we'd merged the blocks and
    1413              :              were starting afresh.  This is sound as long as we never replace
    1414              :              the outer condition with a constant that leads away from the inner
    1415              :              block.  Here's why we never do: when combining contiguous
    1416              :              conditions, we replace the inner cond, and replace the outer cond
    1417              :              with a constant that leads to inner, so this case is good.  When
    1418              :              combining noncontiguous blocks, we normally modify outer, and
    1419              :              replace inner with a constant or remainders of the original
    1420              :              condition that couldn't be combined.  This test would normally not
    1421              :              hit with noncontiguous blocks, because we'd have computed EXIT_BB
    1422              :              before reaching the noncontiguous outer block.  However, if all
    1423              :              intervening blocks are unconditional, including those just made
    1424              :              unconditional, we may replace outer instead of inner with the
    1425              :              combined condition.  If the combined noncontiguous conditions are
    1426              :              mutually exclusive, we could end up with a constant outer
    1427              :              condition, but then, the inner condition would also be a constant,
    1428              :              and then we'd stop iterating because of the known_succ_p
    1429              :              (inner_cond_bb) test above.  */
    1430      1036735 :           if (changed && known_succ_p (outer_cond_bb))
    1431        77852 :             continue;
    1432              : 
    1433       958883 :           if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
    1434       127258 :             exit_bb = then_bb;
    1435       831625 :           else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
    1436        89999 :             exit_bb = else_bb;
    1437              :           else
    1438              :             break;
    1439              : 
    1440              :           /* Find out which path from INNER_COND_BB shares PHI args with the
    1441              :              edge (OUTER_COND_BB->EXIT_BB).  That path may involve a forwarder
    1442              :              block, whether THEN_BB or ELSE_BB, and we need to know which one
    1443              :              satisfies the condition to avoid combinations that could use
    1444              :              different forwarding arrangements, because they would be unsound.
    1445              :              E.g., given (a ? 0 : b ? 1 : c ? 1 : 0), after trying to merge b
    1446              :              and c, we test that both share the same exit block, with the same
    1447              :              value 1.  Whether or not that involves a forwarder block, if we
    1448              :              don't go through the same (possibly absent) forwarder block in
    1449              :              subsequent attempted combinations, e.g. a with c, we could find
    1450              :              that a and inverted c share the same exit block with a different
    1451              :              value, namely 0, which would enable an unsound merge.  We need all
    1452              :              of inner, intervening and outer blocks to reach the same exit with
    1453              :              the same value for the transformation to be sound.  So here we
    1454              :              determine how to get to EXIT_BB from outer and inner with the same
    1455              :              PHI values, record that in EXIT_PRED, and then subsequent
    1456              :              combination attempts that have OUTER_COND_BB as an intervening
    1457              :              block will ensure the same path to exit is taken, skipping unsound
    1458              :              transformations.  */
    1459       217257 :           if (changed)
    1460              :             /* EXIT_PRED was set along with CHANGED, and the successful
    1461              :                combination already checked for the same PHI args.  */;
    1462       217145 :           else if (same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
    1463              :             exit_pred = inner_cond_bb;
    1464        29184 :           else if (then_bb == exit_bb
    1465        20205 :                    && forwarder_block_to (else_bb, then_bb)
    1466        31822 :                    && same_phi_args_p (outer_cond_bb, else_bb, exit_bb))
    1467           76 :             exit_pred = else_bb;
    1468        29108 :           else if (else_bb == exit_bb
    1469         8979 :                    && forwarder_block_to (then_bb, else_bb)
    1470        30337 :                    && same_phi_args_p (outer_cond_bb, then_bb, exit_bb))
    1471          179 :             exit_pred = then_bb;
    1472              :           else
    1473              :             /* If none of the paths share the same PHI args, no combination is
    1474              :                viable.  */
    1475              :             break;
    1476              :           /* Skip the PHI args test below, it's redundant with the tests we've
    1477              :              just performed.  */
    1478       188328 :           continue;
    1479              :         }
    1480              : 
    1481              :       /* Before trying an earlier block, make sure INNER_COND_BB and the
    1482              :          current OUTER_COND_BB share the same PHI args at EXIT_BB.  We don't
    1483              :          need to check if the latest attempt at combining succeeded, because
    1484              :          that means we'll have already checked.  But we can't only check outer
    1485              :          and inner, we have to check that all intervening blocks also get to
    1486              :          exit with the same result, otherwise the transformation may change the
    1487              :          final result.  Consider (a ? 0 : b ? 1 : c ? 0 : -1).  If we combine
    1488              :          (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
    1489              :          rather than 1 when (!a&&b).  And if we were to replace inner instead
    1490              :          of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
    1491              :          yield 1 rather than 0 when (a).  */
    1492       328291 :       if (!changed
    1493       328291 :           && !same_phi_args_p (outer_cond_bb, exit_pred, exit_bb))
    1494              :         break;
    1495              :     }
    1496              : 
    1497      5514446 :   return ret;
    1498              : }
    1499              : 
    1500              : /* Main entry for the tree if-conversion pass.  */
    1501              : 
    1502              : namespace {
    1503              : 
    1504              : const pass_data pass_data_tree_ifcombine =
    1505              : {
    1506              :   GIMPLE_PASS, /* type */
    1507              :   "ifcombine", /* name */
    1508              :   OPTGROUP_NONE, /* optinfo_flags */
    1509              :   TV_TREE_IFCOMBINE, /* tv_id */
    1510              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    1511              :   0, /* properties_provided */
    1512              :   0, /* properties_destroyed */
    1513              :   0, /* todo_flags_start */
    1514              :   TODO_update_ssa, /* todo_flags_finish */
    1515              : };
    1516              : 
    1517              : class pass_tree_ifcombine : public gimple_opt_pass
    1518              : {
    1519              : public:
    1520       297180 :   pass_tree_ifcombine (gcc::context *ctxt)
    1521       594360 :     : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
    1522              :   {}
    1523              : 
    1524              :   /* opt_pass methods: */
    1525              :   unsigned int execute (function *) final override;
    1526              : 
    1527              : }; // class pass_tree_ifcombine
    1528              : 
    1529              : unsigned int
    1530      1062893 : pass_tree_ifcombine::execute (function *fun)
    1531              : {
    1532      1062893 :   basic_block *bbs;
    1533      1062893 :   bool cfg_changed = false;
    1534      1062893 :   int i;
    1535              : 
    1536      1062893 :   bbs = single_pred_before_succ_order ();
    1537      1062893 :   calculate_dominance_info (CDI_DOMINATORS);
    1538      1062893 :   mark_ssa_maybe_undefs ();
    1539              : 
    1540              :   /* Search every basic block for COND_EXPR we may be able to optimize.
    1541              : 
    1542              :      We walk the blocks in order that guarantees that a block with
    1543              :      a single predecessor is processed after the predecessor.
    1544              :      This ensures that we collapse outer ifs before visiting the
    1545              :      inner ones, and also that we do not try to visit a removed
    1546              :      block.  This is opposite of PHI-OPT, because we cascade the
    1547              :      combining rather than cascading PHIs. */
    1548     11675220 :   for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
    1549              :     {
    1550     10612327 :       basic_block bb = bbs[i];
    1551              : 
    1552     25575514 :       if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
    1553      4430234 :         if (tree_ssa_ifcombine_bb (bb))
    1554     10612327 :           cfg_changed |= true;
    1555              :     }
    1556              : 
    1557      1062893 :   free (bbs);
    1558              : 
    1559      1062893 :   return cfg_changed ? TODO_cleanup_cfg : 0;
    1560              : }
    1561              : 
    1562              : } // anon namespace
    1563              : 
    1564              : gimple_opt_pass *
    1565       297180 : make_pass_tree_ifcombine (gcc::context *ctxt)
    1566              : {
    1567       297180 :   return new pass_tree_ifcombine (ctxt);
    1568              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.