LCOV - code coverage report
Current view: top level - gcc - tree-ssa-ifcombine.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.5 % 517 499
Test Date: 2025-02-01 13:18:56 Functions: 100.0 % 19 19
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Combining of if-expressions on trees.
       2                 :             :    Copyright (C) 2007-2025 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 "attribs.h"
      44                 :             : #include "asan.h"
      45                 :             : #include "bitmap.h"
      46                 :             : 
      47                 :             : #ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
      48                 :             : #define LOGICAL_OP_NON_SHORT_CIRCUIT \
      49                 :             :   (BRANCH_COST (optimize_function_for_speed_p (cfun), \
      50                 :             :                 false) >= 2)
      51                 :             : #endif
      52                 :             : 
      53                 :             : /* Return FALSE iff the COND_BB ends with a conditional whose result is not a
      54                 :             :    known constant.  */
      55                 :             : 
      56                 :             : static bool
      57                 :     8843871 : known_succ_p (basic_block cond_bb)
      58                 :             : {
      59                 :    17687742 :   gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
      60                 :             : 
      61                 :     8843871 :   if (!cond)
      62                 :      118927 :     return true;
      63                 :             : 
      64                 :     8724944 :   return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
      65                 :     8724944 :           && CONSTANT_CLASS_P (gimple_cond_rhs (cond)));
      66                 :             : }
      67                 :             : 
      68                 :             : /* This pass combines COND_EXPRs to simplify control flow.  It
      69                 :             :    currently recognizes bit tests and comparisons in chains that
      70                 :             :    represent logical and or logical or of two COND_EXPRs.
      71                 :             : 
      72                 :             :    It does so by walking basic blocks in a approximate reverse
      73                 :             :    post-dominator order and trying to match CFG patterns that
      74                 :             :    represent logical and or logical or of two COND_EXPRs.
      75                 :             :    Transformations are done if the COND_EXPR conditions match
      76                 :             :    either
      77                 :             : 
      78                 :             :      1. two single bit tests X & (1 << Yn) (for logical and)
      79                 :             : 
      80                 :             :      2. two bit tests X & Yn (for logical or)
      81                 :             : 
      82                 :             :      3. two comparisons X OPn Y (for logical or)
      83                 :             : 
      84                 :             :    To simplify this pass, removing basic blocks and dead code
      85                 :             :    is left to CFG cleanup and DCE.  */
      86                 :             : 
      87                 :             : 
      88                 :             : /* Recognize a if-then-else CFG pattern starting to match with the COND_BB
      89                 :             :    basic-block containing the COND_EXPR.  If !SUCCS_ANY, the condition must not
      90                 :             :    resolve to a constant for a match.  Returns true if the pattern matched,
      91                 :             :    false otherwise.  In case of a !SUCCS_ANY match, the recognized then end
      92                 :             :    else blocks are stored to *THEN_BB and *ELSE_BB.  If *THEN_BB and/or
      93                 :             :    *ELSE_BB are already set, they are required to match the then and else
      94                 :             :    basic-blocks to make the pattern match.  If SUCCS_ANY, *THEN_BB and *ELSE_BB
      95                 :             :    will not be filled in, and they will be found to match even if reversed.  */
      96                 :             : 
      97                 :             : static bool
      98                 :     8764540 : recognize_if_then_else (basic_block cond_bb,
      99                 :             :                         basic_block *then_bb, basic_block *else_bb,
     100                 :             :                         bool succs_any = false)
     101                 :             : {
     102                 :     8764540 :   edge t, e;
     103                 :             : 
     104                 :     8764540 :   if (EDGE_COUNT (cond_bb->succs) != 2
     105                 :     8764540 :       || (!succs_any && known_succ_p (cond_bb)))
     106                 :             :     return false;
     107                 :             : 
     108                 :             :   /* Find the then/else edges.  */
     109                 :     8742918 :   t = EDGE_SUCC (cond_bb, 0);
     110                 :     8742918 :   e = EDGE_SUCC (cond_bb, 1);
     111                 :             : 
     112                 :     8742918 :   if (succs_any)
     113                 :      318542 :     return ((t->dest == *then_bb && e->dest == *else_bb)
     114                 :     2041353 :             || (t->dest == *else_bb && e->dest == *then_bb));
     115                 :             : 
     116                 :     7340739 :   if (!(t->flags & EDGE_TRUE_VALUE))
     117                 :      247265 :     std::swap (t, e);
     118                 :     7340739 :   if (!(t->flags & EDGE_TRUE_VALUE)
     119                 :     7340739 :       || !(e->flags & EDGE_FALSE_VALUE))
     120                 :             :     return false;
     121                 :             : 
     122                 :             :   /* Check if the edge destinations point to the required block.  */
     123                 :     7340739 :   if (*then_bb
     124                 :     3359954 :       && t->dest != *then_bb)
     125                 :             :     return false;
     126                 :     4901882 :   if (*else_bb
     127                 :      921097 :       && e->dest != *else_bb)
     128                 :             :     return false;
     129                 :             : 
     130                 :     4311155 :   if (!*then_bb)
     131                 :     3980785 :     *then_bb = t->dest;
     132                 :     4311155 :   if (!*else_bb)
     133                 :     3980785 :     *else_bb = e->dest;
     134                 :             : 
     135                 :             :   return true;
     136                 :             : }
     137                 :             : 
     138                 :             : /* Verify if the basic block BB does not have side-effects.  Return
     139                 :             :    true in this case, else false.  */
     140                 :             : 
     141                 :             : static bool
     142                 :     3186963 : bb_no_side_effects_p (basic_block bb)
     143                 :             : {
     144                 :     3186963 :   gimple_stmt_iterator gsi;
     145                 :             : 
     146                 :    15986179 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     147                 :             :     {
     148                 :    11400425 :       gimple *stmt = gsi_stmt (gsi);
     149                 :             : 
     150                 :    11400425 :       if (is_gimple_debug (stmt))
     151                 :     5957574 :         continue;
     152                 :             : 
     153                 :     5442851 :       gassign *ass;
     154                 :     5442851 :       enum tree_code rhs_code;
     155                 :     5442851 :       if (gimple_has_side_effects (stmt)
     156                 :     4886027 :           || gimple_could_trap_p (stmt)
     157                 :     4152249 :           || gimple_vdef (stmt)
     158                 :             :           /* We need to rewrite stmts with undefined overflow to use
     159                 :             :              unsigned arithmetic but cannot do so for signed division.  */
     160                 :     6137350 :           || ((ass = dyn_cast <gassign *> (stmt))
     161                 :     2204423 :               && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (ass)))
     162                 :     3428696 :               && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (ass)))
     163                 :      417106 :               && ((rhs_code = gimple_assign_rhs_code (ass)), true)
     164                 :      417106 :               && (rhs_code == TRUNC_DIV_EXPR
     165                 :             :                   || rhs_code == CEIL_DIV_EXPR
     166                 :             :                   || rhs_code == FLOOR_DIV_EXPR
     167                 :      417106 :                   || rhs_code == ROUND_DIV_EXPR)
     168                 :             :               /* We cannot use expr_not_equal_to since we'd have to restrict
     169                 :             :                  flow-sensitive info to whats known at the outer if.  */
     170                 :        1153 :               && (TREE_CODE (gimple_assign_rhs2 (ass)) != INTEGER_CST
     171                 :        1153 :                   || !integer_minus_onep (gimple_assign_rhs2 (ass))))
     172                 :             :           /* const calls don't match any of the above, yet they could
     173                 :             :              still have some side-effects - they could contain
     174                 :             :              gimple_could_trap_p statements, like floating point
     175                 :             :              exceptions or integer division by zero.  See PR70586.
     176                 :             :              FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
     177                 :             :              should handle this.  */
     178                 :    11090126 :           || is_gimple_call (stmt))
     179                 :     1788172 :         return false;
     180                 :             : 
     181                 :     3658055 :       ssa_op_iter it;
     182                 :     3658055 :       tree use;
     183                 :     7279833 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, it, SSA_OP_USE)
     184                 :     3625154 :         if (ssa_name_maybe_undef_p (use))
     185                 :             :           return false;
     186                 :             :     }
     187                 :             : 
     188                 :             :   return true;
     189                 :             : }
     190                 :             : 
     191                 :             : /* Return true if BB is an empty forwarder block to TO_BB.  */
     192                 :             : 
     193                 :             : static bool
     194                 :     1443872 : forwarder_block_to (basic_block bb, basic_block to_bb)
     195                 :             : {
     196                 :     1443872 :   return empty_block_p (bb)
     197                 :       50126 :          && single_succ_p (bb)
     198                 :     1493998 :          && single_succ (bb) == to_bb;
     199                 :             : }
     200                 :             : 
     201                 :             : /* Verify if all PHI node arguments in DEST for edges from BB1 or
     202                 :             :    BB2 to DEST are the same.  This makes the CFG merge point
     203                 :             :    free from side-effects.  Return true in this case, else false.  */
     204                 :             : 
     205                 :             : static bool
     206                 :      766057 : same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
     207                 :             : {
     208                 :      766057 :   edge e1 = find_edge (bb1, dest);
     209                 :      766057 :   edge e2 = find_edge (bb2, dest);
     210                 :      766057 :   gphi_iterator gsi;
     211                 :      766057 :   gphi *phi;
     212                 :             : 
     213                 :     1118206 :   for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
     214                 :             :     {
     215                 :      454863 :       phi = gsi.phi ();
     216                 :      454863 :       if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
     217                 :      454863 :                             PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
     218                 :             :         return false;
     219                 :             :     }
     220                 :             : 
     221                 :             :   return true;
     222                 :             : }
     223                 :             : 
     224                 :             : /* Return the best representative SSA name for CANDIDATE which is used
     225                 :             :    in a bit test.  */
     226                 :             : 
     227                 :             : static tree
     228                 :        8621 : get_name_for_bit_test (tree candidate)
     229                 :             : {
     230                 :             :   /* Skip single-use names in favor of using the name from a
     231                 :             :      non-widening conversion definition.  */
     232                 :        8621 :   if (TREE_CODE (candidate) == SSA_NAME
     233                 :        8621 :       && has_single_use (candidate))
     234                 :             :     {
     235                 :        4019 :       gimple *def_stmt = SSA_NAME_DEF_STMT (candidate);
     236                 :        4019 :       if (is_gimple_assign (def_stmt)
     237                 :        4019 :           && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
     238                 :             :         {
     239                 :         169 :           if (TYPE_PRECISION (TREE_TYPE (candidate))
     240                 :         169 :               <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
     241                 :             :             return gimple_assign_rhs1 (def_stmt);
     242                 :             :         }
     243                 :             :     }
     244                 :             : 
     245                 :             :   return candidate;
     246                 :             : }
     247                 :             : 
     248                 :             : /* Recognize a single bit test pattern in GIMPLE_COND and its defining
     249                 :             :    statements.  Store the name being tested in *NAME and the bit
     250                 :             :    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
     251                 :             :    Returns true if the pattern matched, false otherwise.  */
     252                 :             : 
     253                 :             : static bool
     254                 :      277157 : recognize_single_bit_test (gcond *cond, tree *name, tree *bit, bool inv)
     255                 :             : {
     256                 :      277157 :   gimple *stmt;
     257                 :             : 
     258                 :             :   /* Get at the definition of the result of the bit test.  */
     259                 :      277157 :   if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
     260                 :       42360 :       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
     261                 :      318683 :       || !integer_zerop (gimple_cond_rhs (cond)))
     262                 :      252980 :     return false;
     263                 :       24177 :   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
     264                 :       24177 :   if (!is_gimple_assign (stmt))
     265                 :             :     return false;
     266                 :             : 
     267                 :             :   /* Look at which bit is tested.  One form to recognize is
     268                 :             :      D.1985_5 = state_3(D) >> control1_4(D);
     269                 :             :      D.1986_6 = (int) D.1985_5;
     270                 :             :      D.1987_7 = op0 & 1;
     271                 :             :      if (D.1987_7 != 0)  */
     272                 :       20266 :   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     273                 :        6293 :       && integer_onep (gimple_assign_rhs2 (stmt))
     274                 :       20854 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
     275                 :             :     {
     276                 :         588 :       tree orig_name = gimple_assign_rhs1 (stmt);
     277                 :             : 
     278                 :             :       /* Look through copies and conversions to eventually
     279                 :             :          find the stmt that computes the shift.  */
     280                 :         588 :       stmt = SSA_NAME_DEF_STMT (orig_name);
     281                 :             : 
     282                 :         589 :       while (is_gimple_assign (stmt)
     283                 :         589 :              && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
     284                 :           1 :                   && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)))
     285                 :           1 :                       <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))
     286                 :           1 :                   && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
     287                 :         507 :                  || gimple_assign_ssa_name_copy_p (stmt)))
     288                 :           1 :         stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
     289                 :             : 
     290                 :             :       /* If we found such, decompose it.  */
     291                 :         588 :       if (is_gimple_assign (stmt)
     292                 :         588 :           && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR)
     293                 :             :         {
     294                 :             :           /* op0 & (1 << op1) */
     295                 :          77 :           *bit = gimple_assign_rhs2 (stmt);
     296                 :          77 :           *name = gimple_assign_rhs1 (stmt);
     297                 :             :         }
     298                 :             :       else
     299                 :             :         {
     300                 :             :           /* t & 1 */
     301                 :         511 :           *bit = integer_zero_node;
     302                 :         511 :           *name = get_name_for_bit_test (orig_name);
     303                 :             :         }
     304                 :             : 
     305                 :         588 :       return true;
     306                 :             :     }
     307                 :             : 
     308                 :             :   /* Another form is
     309                 :             :      D.1987_7 = op0 & (1 << CST)
     310                 :             :      if (D.1987_7 != 0)  */
     311                 :       19678 :   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     312                 :        5705 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
     313                 :       25383 :       && integer_pow2p (gimple_assign_rhs2 (stmt)))
     314                 :             :     {
     315                 :        3288 :       *name = gimple_assign_rhs1 (stmt);
     316                 :        3288 :       *bit = build_int_cst (integer_type_node,
     317                 :        3288 :                             tree_log2 (gimple_assign_rhs2 (stmt)));
     318                 :        3288 :       return true;
     319                 :             :     }
     320                 :             : 
     321                 :             :   /* Another form is
     322                 :             :      D.1986_6 = 1 << control1_4(D)
     323                 :             :      D.1987_7 = op0 & D.1986_6
     324                 :             :      if (D.1987_7 != 0)  */
     325                 :       16390 :   if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     326                 :        2417 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
     327                 :       18807 :       && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
     328                 :             :     {
     329                 :        2061 :       gimple *tmp;
     330                 :             : 
     331                 :             :       /* Both arguments of the BIT_AND_EXPR can be the single-bit
     332                 :             :          specifying expression.  */
     333                 :        2061 :       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
     334                 :        2061 :       if (is_gimple_assign (tmp)
     335                 :        2025 :           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
     336                 :        2071 :           && integer_onep (gimple_assign_rhs1 (tmp)))
     337                 :             :         {
     338                 :          10 :           *name = gimple_assign_rhs2 (stmt);
     339                 :          10 :           *bit = gimple_assign_rhs2 (tmp);
     340                 :          10 :           return true;
     341                 :             :         }
     342                 :             : 
     343                 :        2051 :       tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
     344                 :        2051 :       if (is_gimple_assign (tmp)
     345                 :        1922 :           && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR
     346                 :        2081 :           && integer_onep (gimple_assign_rhs1 (tmp)))
     347                 :             :         {
     348                 :          30 :           *name = gimple_assign_rhs1 (stmt);
     349                 :          30 :           *bit = gimple_assign_rhs2 (tmp);
     350                 :          30 :           return true;
     351                 :             :         }
     352                 :             :     }
     353                 :             : 
     354                 :             :   return false;
     355                 :             : }
     356                 :             : 
     357                 :             : /* Recognize a bit test pattern in a GIMPLE_COND and its defining
     358                 :             :    statements.  Store the name being tested in *NAME and the bits
     359                 :             :    in *BITS.  The COND_EXPR computes *NAME & *BITS.
     360                 :             :    Returns true if the pattern matched, false otherwise.  */
     361                 :             : 
     362                 :             : static bool
     363                 :      279268 : recognize_bits_test (gcond *cond, tree *name, tree *bits, bool inv)
     364                 :             : {
     365                 :      279268 :   gimple *stmt;
     366                 :             : 
     367                 :             :   /* Get at the definition of the result of the bit test.  */
     368                 :      279268 :   if (gimple_cond_code (cond) != (inv ? EQ_EXPR : NE_EXPR)
     369                 :      186093 :       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
     370                 :      464674 :       || !integer_zerop (gimple_cond_rhs (cond)))
     371                 :      216138 :     return false;
     372                 :       63130 :   stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
     373                 :       63130 :   if (!is_gimple_assign (stmt)
     374                 :       63130 :       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
     375                 :             :     return false;
     376                 :             : 
     377                 :        8110 :   *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
     378                 :        8110 :   *bits = gimple_assign_rhs2 (stmt);
     379                 :             : 
     380                 :        8110 :   return true;
     381                 :             : }
     382                 :             : 
     383                 :             : 
     384                 :             : /* Update profile after code in either outer_cond_bb or inner_cond_bb was
     385                 :             :    adjusted so that it has no condition.  */
     386                 :             : 
     387                 :             : static void
     388                 :       85284 : update_profile_after_ifcombine (basic_block inner_cond_bb,
     389                 :             :                                 basic_block outer_cond_bb)
     390                 :             : {
     391                 :             :   /* In the following we assume that inner_cond_bb has single predecessor.  */
     392                 :       85284 :   gcc_assert (single_pred_p (inner_cond_bb));
     393                 :             : 
     394                 :       85284 :   basic_block outer_to_inner_bb = inner_cond_bb;
     395                 :       85284 :   profile_probability prob = profile_probability::always ();
     396                 :       85444 :   for (;;)
     397                 :             :     {
     398                 :       85444 :       basic_block parent = single_pred (outer_to_inner_bb);
     399                 :       85444 :       prob *= find_edge (parent, outer_to_inner_bb)->probability;
     400                 :       85444 :       if (parent == outer_cond_bb)
     401                 :             :         break;
     402                 :             :       outer_to_inner_bb = parent;
     403                 :             :     }
     404                 :             : 
     405                 :       85284 :   edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
     406                 :       85284 :   edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
     407                 :       85284 :                  ? EDGE_SUCC (outer_cond_bb, 1)
     408                 :       85284 :                  : EDGE_SUCC (outer_cond_bb, 0));
     409                 :       85284 :   edge inner_taken = EDGE_SUCC (inner_cond_bb, 0);
     410                 :       85284 :   edge inner_not_taken = EDGE_SUCC (inner_cond_bb, 1);
     411                 :             : 
     412                 :       85284 :   if (inner_taken->dest != outer2->dest)
     413                 :       30611 :     std::swap (inner_taken, inner_not_taken);
     414                 :       85284 :   gcc_assert (inner_taken->dest == outer2->dest);
     415                 :             : 
     416                 :       85284 :   if (outer_to_inner_bb == inner_cond_bb
     417                 :       85284 :       && known_succ_p (outer_cond_bb))
     418                 :             :     {
     419                 :             :       /* Path outer_cond_bb->(outer2) needs to be merged into path
     420                 :             :          outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
     421                 :             :          and probability of inner_not_taken updated.  */
     422                 :             : 
     423                 :       85060 :       inner_cond_bb->count = outer_cond_bb->count;
     424                 :             : 
     425                 :             :       /* Handle special case where inner_taken probability is always. In this
     426                 :             :          case we know that the overall outcome will be always as well, but
     427                 :             :          combining probabilities will be conservative because it does not know
     428                 :             :          that outer2->probability is inverse of
     429                 :             :          outer_to_inner->probability.  */
     430                 :       85060 :       if (inner_taken->probability == profile_probability::always ())
     431                 :             :         ;
     432                 :             :       else
     433                 :       83529 :         inner_taken->probability = outer2->probability
     434                 :       83529 :           + outer_to_inner->probability * inner_taken->probability;
     435                 :       85060 :       inner_not_taken->probability = profile_probability::always ()
     436                 :       85060 :         - inner_taken->probability;
     437                 :             : 
     438                 :       85060 :       outer_to_inner->probability = profile_probability::always ();
     439                 :       85060 :       outer2->probability = profile_probability::never ();
     440                 :             :     }
     441                 :         224 :   else if (known_succ_p (inner_cond_bb))
     442                 :             :     {
     443                 :             :       /* Path inner_cond_bb->(inner_taken) needs to be merged into path
     444                 :             :          outer_cond_bb->(outer2).  We've accumulated the probabilities from
     445                 :             :          outer_cond_bb->(outer)->...->inner_cond_bb in prob, so we have to
     446                 :             :          adjust that by inner_taken, and make inner unconditional.  */
     447                 :             : 
     448                 :         109 :       prob *= inner_taken->probability;
     449                 :         109 :       outer2->probability += prob;
     450                 :         109 :       outer_to_inner->probability = profile_probability::always ()
     451                 :         109 :         - outer2->probability;
     452                 :             : 
     453                 :         109 :       inner_taken->probability = profile_probability::never ();
     454                 :         109 :       inner_not_taken->probability = profile_probability::always ();
     455                 :             :     }
     456                 :             :   else
     457                 :             :     {
     458                 :             :       /* We've moved part of the inner cond to outer, but we don't know the
     459                 :             :          probabilities for each part, so estimate the effects by moving half of
     460                 :             :          the odds of inner_taken to outer.  */
     461                 :             : 
     462                 :         115 :       inner_taken->probability *= profile_probability::even ();
     463                 :         115 :       inner_not_taken->probability = profile_probability::always ()
     464                 :         115 :         - inner_taken->probability;
     465                 :             : 
     466                 :         115 :       prob *= inner_taken->probability;
     467                 :         115 :       outer2->probability += prob;
     468                 :         115 :       outer_to_inner->probability = profile_probability::always ()
     469                 :         115 :         - outer2->probability;
     470                 :             :     }
     471                 :       85284 : }
     472                 :             : 
     473                 :             : /* Set NAME's bit in USED if OUTER dominates it.  */
     474                 :             : 
     475                 :             : static void
     476                 :        1093 : ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
     477                 :             : {
     478                 :        1093 :   if (!name || TREE_CODE (name) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (name))
     479                 :             :     return;
     480                 :             : 
     481                 :         457 :   gimple *def = SSA_NAME_DEF_STMT (name);
     482                 :         457 :   basic_block bb = gimple_bb (def);
     483                 :         457 :   if (!dominated_by_p (CDI_DOMINATORS, bb, outer))
     484                 :             :     return;
     485                 :             : 
     486                 :         413 :   bitmap_set_bit (used, SSA_NAME_VERSION (name));
     487                 :             : }
     488                 :             : 
     489                 :             : /* Data structure passed to ifcombine_mark_ssa_name.  */
     490                 :             : struct ifcombine_mark_ssa_name_t
     491                 :             : {
     492                 :             :   /* SSA_NAMEs that have been referenced.  */
     493                 :             :   bitmap used;
     494                 :             :   /* Dominating block of DEFs that might need moving.  */
     495                 :             :   basic_block outer;
     496                 :             : };
     497                 :             : 
     498                 :             : /* Mark in DATA->used any SSA_NAMEs used in *t.  */
     499                 :             : 
     500                 :             : static tree
     501                 :        1069 : ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
     502                 :             : {
     503                 :        1069 :   ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_;
     504                 :             : 
     505                 :        1069 :   ifcombine_mark_ssa_name (data->used, *t, data->outer);
     506                 :             : 
     507                 :        1069 :   return NULL;
     508                 :             : }
     509                 :             : 
     510                 :             : /* Rewrite a stmt, that presumably used to be guarded by conditions that could
     511                 :             :    avoid undefined overflow, into one that has well-defined overflow, so that
     512                 :             :    it won't invoke undefined behavior once the guarding conditions change.  */
     513                 :             : 
     514                 :             : static inline void
     515                 :      337594 : ifcombine_rewrite_to_defined_overflow (gimple_stmt_iterator gsi)
     516                 :             : {
     517                 :      337594 :   gassign *ass = dyn_cast <gassign *> (gsi_stmt (gsi));
     518                 :      214952 :   if (!ass)
     519                 :             :     return;
     520                 :      214952 :   tree lhs = gimple_assign_lhs (ass);
     521                 :      429351 :   if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
     522                 :           8 :        || POINTER_TYPE_P (TREE_TYPE (lhs)))
     523                 :      429904 :       && arith_code_with_undefined_signed_overflow
     524                 :      214952 :       (gimple_assign_rhs_code (ass)))
     525                 :        6982 :     rewrite_to_defined_overflow (&gsi);
     526                 :             : }
     527                 :             : 
     528                 :             : 
     529                 :             : /* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
     530                 :             :    COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
     531                 :             :    replaced with a constant, but if there are intervening blocks, it's best to
     532                 :             :    adjust COND for insertion at OUTER_COND, placing COND2 at INNER_COND.  */
     533                 :             : 
     534                 :             : static bool
     535                 :       85285 : ifcombine_replace_cond (gcond *inner_cond, bool inner_inv,
     536                 :             :                         gcond *outer_cond, bool outer_inv,
     537                 :             :                         tree cond, bool must_canon, tree cond2)
     538                 :             : {
     539                 :       85285 :   bool split_single_cond = false;
     540                 :             :   /* Split cond into cond2 if they're contiguous.  ??? We might be able to
     541                 :             :      handle ORIF as well, inverting both conditions, but it's not clear that
     542                 :             :      this would be enough, and it never comes up.  */
     543                 :       85285 :   if (!cond2
     544                 :       85279 :       && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
     545                 :       85415 :       && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
     546                 :             :     {
     547                 :         109 :       cond2 = TREE_OPERAND (cond, 1);
     548                 :         109 :       cond = TREE_OPERAND (cond, 0);
     549                 :         109 :       split_single_cond = true;
     550                 :             :     }
     551                 :             : 
     552                 :       85285 :   bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
     553                 :       85170 :                            != gimple_bb (outer_cond));
     554                 :       85285 :   bool result_inv = outer_p ? outer_inv : inner_inv;
     555                 :       85285 :   bool strictening_outer_cond = !split_single_cond && outer_p;
     556                 :             : 
     557                 :       85285 :   if (result_inv)
     558                 :       53627 :     cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
     559                 :             : 
     560                 :       85285 :   if (tree tcanon = canonicalize_cond_expr_cond (cond))
     561                 :        4424 :     cond = tcanon;
     562                 :       80861 :   else if (must_canon)
     563                 :             :     return false;
     564                 :             : 
     565                 :       85285 :   if (outer_p)
     566                 :             :     {
     567                 :         225 :       {
     568                 :         225 :         auto_bitmap used;
     569                 :         225 :         basic_block outer_bb = gimple_bb (outer_cond);
     570                 :             : 
     571                 :         225 :         bitmap_tree_view (used);
     572                 :             : 
     573                 :             :         /* Mark SSA DEFs that are referenced by cond and may thus need to be
     574                 :             :            moved to outer.  */
     575                 :         225 :         {
     576                 :         225 :           ifcombine_mark_ssa_name_t data = { used, outer_bb };
     577                 :         225 :           walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
     578                 :             :         }
     579                 :             : 
     580                 :         225 :         if (!bitmap_empty_p (used))
     581                 :             :           {
     582                 :         208 :             const int max_stmts = 6;
     583                 :         208 :             auto_vec<gimple *, max_stmts> stmts;
     584                 :             : 
     585                 :             :             /* Iterate up from inner_cond, moving DEFs identified as used by
     586                 :             :                cond, and marking USEs in the DEFs for moving as well.  */
     587                 :         555 :             for (basic_block bb = gimple_bb (inner_cond);
     588                 :         555 :                  bb != outer_bb; bb = single_pred (bb))
     589                 :             :               {
     590                 :         348 :                 for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
     591                 :        4110 :                      !gsi_end_p (gsitr); gsi_prev (&gsitr))
     592                 :             :                   {
     593                 :        1881 :                     gimple *stmt = gsi_stmt (gsitr);
     594                 :        1881 :                     bool move = false;
     595                 :        1881 :                     tree t;
     596                 :        1881 :                     ssa_op_iter it;
     597                 :             : 
     598                 :        2864 :                     FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
     599                 :        1125 :                       if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
     600                 :             :                         {
     601                 :             :                           move = true;
     602                 :             :                           break;
     603                 :             :                         }
     604                 :             : 
     605                 :        1881 :                     if (!move)
     606                 :        1739 :                       continue;
     607                 :             : 
     608                 :         142 :                     if (stmts.length () < max_stmts)
     609                 :         142 :                       stmts.quick_push (stmt);
     610                 :             :                     else
     611                 :           0 :                       return false;
     612                 :             : 
     613                 :             :                     /* Mark uses in STMT before moving it.  */
     614                 :         162 :                     FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE)
     615                 :          20 :                       ifcombine_mark_ssa_name (used, t, outer_bb);
     616                 :             :                   }
     617                 :             : 
     618                 :             :                 /* Surprisingly, there may be PHI nodes in single-predecessor
     619                 :             :                    bocks, as in pr50682.C.  Fortunately, since they can't
     620                 :             :                    involve back edges, there won't be references to parallel
     621                 :             :                    nodes that we'd have to pay special attention to to keep
     622                 :             :                    them parallel.  We can't move the PHI nodes, but we can turn
     623                 :             :                    them into assignments.  */
     624                 :         348 :                 for (gphi_iterator gsi = gsi_start_phis (bb);
     625                 :         352 :                      !gsi_end_p (gsi);)
     626                 :             :                   {
     627                 :           5 :                     gphi *phi = gsi.phi ();
     628                 :             : 
     629                 :           5 :                     gcc_assert (gimple_phi_num_args (phi) == 1);
     630                 :           5 :                     tree def = gimple_phi_result (phi);
     631                 :             : 
     632                 :           5 :                     if (!bitmap_bit_p (used, SSA_NAME_VERSION (def)))
     633                 :             :                       {
     634                 :           0 :                         gsi_next (&gsi);
     635                 :           0 :                         continue;
     636                 :             :                       }
     637                 :             : 
     638                 :           5 :                     if (stmts.length () < max_stmts)
     639                 :           4 :                       stmts.quick_push (phi);
     640                 :             :                     else
     641                 :           1 :                       return false;
     642                 :             : 
     643                 :             :                     /* Mark uses in STMT before moving it.  */
     644                 :           4 :                     use_operand_p use_p;
     645                 :           4 :                     ssa_op_iter it;
     646                 :           8 :                     FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
     647                 :           4 :                       ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p),
     648                 :             :                                                outer_bb);
     649                 :             :                   }
     650                 :             :               }
     651                 :             : 
     652                 :             :             /* ??? Test whether it makes sense to move STMTS.  */
     653                 :             : 
     654                 :             :             /* Move the STMTS that need moving.  From this point on, we're
     655                 :             :                committing to the attempted ifcombine.  */
     656                 :         207 :             gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
     657                 :         207 :             unsigned i;
     658                 :         207 :             gimple *stmt;
     659                 :         347 :             FOR_EACH_VEC_ELT (stmts, i, stmt)
     660                 :             :               {
     661                 :         140 :                 if (gphi *phi = dyn_cast <gphi *> (stmt))
     662                 :             :                   {
     663                 :           0 :                     tree def = gimple_phi_result (phi);
     664                 :           0 :                     tree use = gimple_phi_arg_def (phi, 0);
     665                 :           0 :                     location_t loc = gimple_phi_arg_location (phi, 0);
     666                 :             : 
     667                 :           0 :                     gphi_iterator gsi = gsi_for_phi (phi);
     668                 :           0 :                     remove_phi_node (&gsi, false);
     669                 :             : 
     670                 :           0 :                     gassign *a = gimple_build_assign (def, use);
     671                 :           0 :                     gimple_set_location (a, loc);
     672                 :           0 :                     gsi_insert_before (&gsins, a, GSI_NEW_STMT);
     673                 :             :                   }
     674                 :             :                 else
     675                 :             :                   {
     676                 :         140 :                     gimple_stmt_iterator gsitr = gsi_for_stmt (stmt);
     677                 :         140 :                     gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT);
     678                 :             :                   }
     679                 :             :               }
     680                 :             : 
     681                 :         347 :             for (; gsi_stmt (gsins) != outer_cond; gsi_next (&gsins))
     682                 :             :               {
     683                 :             :                 /* Clear range info from all defs we've moved from under
     684                 :             :                    conditions.  */
     685                 :         140 :                 tree t;
     686                 :         140 :                 ssa_op_iter it;
     687                 :         280 :                 FOR_EACH_SSA_TREE_OPERAND (t, gsi_stmt (gsins), it, SSA_OP_DEF)
     688                 :         140 :                   reset_flow_sensitive_info (t);
     689                 :             :                 /* Avoid introducing undefined overflows while at that.  */
     690                 :         140 :                 ifcombine_rewrite_to_defined_overflow (gsins);
     691                 :             :               }
     692                 :         208 :           }
     693                 :           1 :       }
     694                 :             : 
     695                 :         224 :       if (!is_gimple_condexpr_for_cond (cond))
     696                 :             :         {
     697                 :         101 :           gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond);
     698                 :         101 :           cond = force_gimple_operand_gsi_1 (&gsi, cond,
     699                 :             :                                              is_gimple_condexpr_for_cond,
     700                 :             :                                              NULL, true, GSI_SAME_STMT);
     701                 :             :         }
     702                 :             : 
     703                 :             :       /* Leave CFG optimization to cfg_cleanup.  */
     704                 :         224 :       gimple_cond_set_condition_from_tree (outer_cond, cond);
     705                 :         224 :       update_stmt (outer_cond);
     706                 :             : 
     707                 :         224 :       if (cond2)
     708                 :             :         {
     709                 :         115 :           if (inner_inv)
     710                 :         115 :             cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2);
     711                 :             : 
     712                 :         115 :           if (tree tcanon = canonicalize_cond_expr_cond (cond2))
     713                 :          43 :             cond2 = tcanon;
     714                 :         115 :           if (!is_gimple_condexpr_for_cond (cond2))
     715                 :             :             {
     716                 :          72 :               gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
     717                 :          72 :               cond2 = force_gimple_operand_gsi_1 (&gsi, cond2,
     718                 :             :                                                   is_gimple_condexpr_for_cond,
     719                 :             :                                                   NULL, true, GSI_SAME_STMT);
     720                 :             :             }
     721                 :         115 :           gimple_cond_set_condition_from_tree (inner_cond, cond2);
     722                 :             :         }
     723                 :             :       else
     724                 :         109 :         gimple_cond_set_condition_from_tree (inner_cond,
     725                 :             :                                              inner_inv
     726                 :             :                                              ? boolean_false_node
     727                 :             :                                              : boolean_true_node);
     728                 :         224 :       update_stmt (inner_cond);
     729                 :             :     }
     730                 :             :   else
     731                 :             :     {
     732                 :       85060 :       if (!is_gimple_condexpr_for_cond (cond))
     733                 :             :         {
     734                 :       80760 :           gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
     735                 :       80760 :           cond = force_gimple_operand_gsi_1 (&gsi, cond,
     736                 :             :                                              is_gimple_condexpr_for_cond,
     737                 :             :                                              NULL, true, GSI_SAME_STMT);
     738                 :             :         }
     739                 :       85060 :       gimple_cond_set_condition_from_tree (inner_cond, cond);
     740                 :       85060 :       update_stmt (inner_cond);
     741                 :             : 
     742                 :             :       /* Leave CFG optimization to cfg_cleanup.  */
     743                 :       85060 :       gimple_cond_set_condition_from_tree (outer_cond,
     744                 :             :                                            outer_inv
     745                 :             :                                            ? boolean_false_node
     746                 :             :                                            : boolean_true_node);
     747                 :       85060 :       update_stmt (outer_cond);
     748                 :             :     }
     749                 :             : 
     750                 :             :   /* We're changing conditions that guard inner blocks, so reset flow sensitive
     751                 :             :      info and avoid introducing undefined behavior.  */
     752                 :      170728 :   for (basic_block bb = gimple_bb (inner_cond), end = gimple_bb (outer_cond);
     753                 :      170728 :        bb != end; bb = single_pred (bb))
     754                 :             :     {
     755                 :             :       /* Clear range info from all stmts in BB which is now guarded by
     756                 :             :          different conditionals.  */
     757                 :       85444 :       reset_flow_sensitive_info_in_bb (gimple_bb (inner_cond));
     758                 :             : 
     759                 :             :       /* We only need to worry about introducing undefined behavior if we've
     760                 :             :          relaxed the outer condition.  */
     761                 :       85444 :       if (strictening_outer_cond)
     762                 :         275 :         continue;
     763                 :             : 
     764                 :             :       /* Avoid introducing undefined behavior as we move stmts that used to be
     765                 :             :          guarded by OUTER_COND.  */
     766                 :      170338 :       for (gimple_stmt_iterator gsi = gsi_start_bb (gimple_bb (inner_cond));
     767                 :      422623 :            !gsi_end_p (gsi); gsi_next (&gsi))
     768                 :      337454 :         ifcombine_rewrite_to_defined_overflow (gsi);
     769                 :             :     }
     770                 :             : 
     771                 :       85284 :   update_profile_after_ifcombine (gimple_bb (inner_cond),
     772                 :             :                                   gimple_bb (outer_cond));
     773                 :             : 
     774                 :       85284 :   return true;
     775                 :             : }
     776                 :             : 
     777                 :             : /* Returns true if inner_cond_bb contains just the condition or 1/2 statements
     778                 :             :    that define lhs or rhs with an integer conversion. */
     779                 :             : 
     780                 :             : static bool
     781                 :      145310 : can_combine_bbs_with_short_circuit (basic_block inner_cond_bb, tree lhs, tree rhs)
     782                 :             : {
     783                 :      145310 :   gimple_stmt_iterator gsi;
     784                 :      145310 :   gsi = gsi_start_nondebug_after_labels_bb (inner_cond_bb);
     785                 :             :   /* If only the condition, this should be allowed. */
     786                 :      145310 :   if (gsi_one_before_end_p (gsi))
     787                 :             :     return true;
     788                 :             :   /* Can have up to 2 statements defining each of lhs/rhs. */
     789                 :       72541 :   for (int i = 0; i < 2; i++)
     790                 :             :     {
     791                 :       72541 :       gimple *stmt = gsi_stmt (gsi);
     792                 :       72541 :       if (!is_gimple_assign (stmt)
     793                 :       72541 :           || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
     794                 :             :         return false;
     795                 :             :       /* The defining statement needs to match either the lhs or rhs of
     796                 :             :          the condition. */
     797                 :        9985 :       if (lhs != gimple_assign_lhs (stmt)
     798                 :        9985 :           && rhs != gimple_assign_lhs (stmt))
     799                 :             :         return false;
     800                 :        4980 :       gsi_next_nondebug (&gsi);
     801                 :       83130 :       if (gsi_one_before_end_p (gsi))
     802                 :             :         return true;
     803                 :             :     }
     804                 :             :   return false;
     805                 :             : }
     806                 :             : 
     807                 :             : /* If-convert on a and pattern with a common else block.  The inner
     808                 :             :    if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
     809                 :             :    inner_inv, outer_inv indicate whether the conditions are inverted.
     810                 :             :    Returns true if the edges to the common else basic-block were merged.  */
     811                 :             : 
     812                 :             : static bool
     813                 :      274498 : ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
     814                 :             :                    basic_block outer_cond_bb, bool outer_inv)
     815                 :             : {
     816                 :      274498 :   gimple_stmt_iterator gsi;
     817                 :      274498 :   tree name1, name2, bit1, bit2, bits1, bits2;
     818                 :             : 
     819                 :      548996 :   gcond *inner_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (inner_cond_bb));
     820                 :      274498 :   if (!inner_cond)
     821                 :             :     return false;
     822                 :             : 
     823                 :      548996 :   gcond *outer_cond = safe_dyn_cast <gcond *> (*gsi_last_bb (outer_cond_bb));
     824                 :      274498 :   if (!outer_cond)
     825                 :             :     return false;
     826                 :             : 
     827                 :             :   /* See if we test a single bit of the same name in both tests.  In
     828                 :             :      that case remove the outer test, merging both else edges,
     829                 :             :      and change the inner one to test for
     830                 :             :      name & (bit1 | bit2) == (bit1 | bit2).  */
     831                 :      274498 :   if (recognize_single_bit_test (inner_cond, &name1, &bit1, inner_inv)
     832                 :        2659 :       && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
     833                 :      275755 :       && name1 == name2)
     834                 :             :     {
     835                 :         952 :       tree t, t2;
     836                 :             : 
     837                 :         952 :       if (TREE_CODE (name1) == SSA_NAME
     838                 :         952 :           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
     839                 :             :         return false;
     840                 :             : 
     841                 :             :       /* Do it.  */
     842                 :         952 :       gsi = gsi_for_stmt (inner_cond);
     843                 :         952 :       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
     844                 :             :                        build_int_cst (TREE_TYPE (name1), 1), bit1);
     845                 :         952 :       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
     846                 :             :                         build_int_cst (TREE_TYPE (name1), 1), bit2);
     847                 :         952 :       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
     848                 :         952 :       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
     849                 :             :                                     true, GSI_SAME_STMT);
     850                 :         952 :       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
     851                 :         952 :       t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
     852                 :             :                                      true, GSI_SAME_STMT);
     853                 :             : 
     854                 :         952 :       t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
     855                 :             : 
     856                 :         952 :       if (!ifcombine_replace_cond (inner_cond, inner_inv,
     857                 :             :                                    outer_cond, outer_inv,
     858                 :             :                                    t, true, NULL_TREE))
     859                 :             :         return false;
     860                 :             : 
     861                 :         952 :       if (dump_file)
     862                 :             :         {
     863                 :           1 :           fprintf (dump_file, "optimizing double bit test to ");
     864                 :           1 :           print_generic_expr (dump_file, name1);
     865                 :           1 :           fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
     866                 :           1 :           print_generic_expr (dump_file, bit1);
     867                 :           1 :           fprintf (dump_file, ") | (1 << ");
     868                 :           1 :           print_generic_expr (dump_file, bit2);
     869                 :           1 :           fprintf (dump_file, ")\n");
     870                 :             :         }
     871                 :             : 
     872                 :         952 :       return true;
     873                 :             :     }
     874                 :             : 
     875                 :             :   /* See if we have two bit tests of the same name in both tests.
     876                 :             :      In that case remove the outer test and change the inner one to
     877                 :             :      test for name & (bits1 | bits2) != 0.  */
     878                 :      273546 :   else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
     879                 :      273546 :            && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
     880                 :             :     {
     881                 :        2388 :       tree t;
     882                 :             : 
     883                 :        2388 :       if ((TREE_CODE (name1) == SSA_NAME
     884                 :        2387 :            && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name1))
     885                 :        4775 :           || (TREE_CODE (name2) == SSA_NAME
     886                 :        2387 :               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name2)))
     887                 :             :         return false;
     888                 :             : 
     889                 :             :       /* Find the common name which is bit-tested.  */
     890                 :        2388 :       if (name1 == name2)
     891                 :             :         ;
     892                 :        1048 :       else if (bits1 == bits2)
     893                 :             :         {
     894                 :          88 :           std::swap (name2, bits2);
     895                 :          88 :           std::swap (name1, bits1);
     896                 :             :         }
     897                 :         960 :       else if (name1 == bits2)
     898                 :           5 :         std::swap (name2, bits2);
     899                 :         955 :       else if (bits1 == name2)
     900                 :           0 :         std::swap (name1, bits1);
     901                 :             :       else
     902                 :         955 :         goto bits_test_failed;
     903                 :             : 
     904                 :             :       /* As we strip non-widening conversions in finding a common
     905                 :             :          name that is tested make sure to end up with an integral
     906                 :             :          type for building the bit operations.  */
     907                 :        1433 :       if (TYPE_PRECISION (TREE_TYPE (bits1))
     908                 :        1433 :           >= TYPE_PRECISION (TREE_TYPE (bits2)))
     909                 :             :         {
     910                 :        1433 :           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
     911                 :        1433 :           name1 = fold_convert (TREE_TYPE (bits1), name1);
     912                 :        1433 :           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
     913                 :        1433 :           bits2 = fold_convert (TREE_TYPE (bits1), bits2);
     914                 :             :         }
     915                 :             :       else
     916                 :             :         {
     917                 :           0 :           bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2);
     918                 :           0 :           name1 = fold_convert (TREE_TYPE (bits2), name1);
     919                 :           0 :           bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1);
     920                 :           0 :           bits1 = fold_convert (TREE_TYPE (bits2), bits1);
     921                 :             :         }
     922                 :             : 
     923                 :        1433 :       t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
     924                 :        1433 :       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
     925                 :        1433 :       t = fold_build2 (EQ_EXPR, boolean_type_node, t,
     926                 :             :                        build_int_cst (TREE_TYPE (t), 0));
     927                 :        1433 :       if (!ifcombine_replace_cond (inner_cond, inner_inv,
     928                 :             :                                    outer_cond, outer_inv,
     929                 :             :                                    t, false, NULL_TREE))
     930                 :             :         return false;
     931                 :             : 
     932                 :        1433 :       if (dump_file)
     933                 :             :         {
     934                 :           1 :           fprintf (dump_file, "optimizing bits or bits test to ");
     935                 :           1 :           print_generic_expr (dump_file, name1);
     936                 :           1 :           fprintf (dump_file, " & T != 0\nwith temporary T = ");
     937                 :           1 :           print_generic_expr (dump_file, bits1);
     938                 :           1 :           fprintf (dump_file, " | ");
     939                 :           1 :           print_generic_expr (dump_file, bits2);
     940                 :           1 :           fprintf (dump_file, "\n");
     941                 :             :         }
     942                 :             : 
     943                 :        1433 :       return true;
     944                 :             :     }
     945                 :             : 
     946                 :             :   /* See if we have two comparisons that we can merge into one.  */
     947                 :      272113 :   else bits_test_failed:
     948                 :      272113 :     if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
     949                 :      272113 :            && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
     950                 :             :     {
     951                 :      272113 :       tree t, ts = NULL_TREE;
     952                 :      272113 :       enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
     953                 :      272113 :       enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
     954                 :             : 
     955                 :             :       /* Invert comparisons if necessary (and possible).  */
     956                 :      272113 :       if (inner_inv)
     957                 :      199309 :         inner_cond_code = invert_tree_comparison (inner_cond_code,
     958                 :      199309 :           HONOR_NANS (gimple_cond_lhs (inner_cond)));
     959                 :      272113 :       if (inner_cond_code == ERROR_MARK)
     960                 :             :         return false;
     961                 :      270375 :       if (outer_inv)
     962                 :      191421 :         outer_cond_code = invert_tree_comparison (outer_cond_code,
     963                 :      191421 :           HONOR_NANS (gimple_cond_lhs (outer_cond)));
     964                 :      270375 :       if (outer_cond_code == ERROR_MARK)
     965                 :             :         return false;
     966                 :             :       /* Don't return false so fast, try maybe_fold_or_comparisons?  */
     967                 :             : 
     968                 :      270097 :       if (!(t = maybe_fold_and_comparisons (boolean_type_node, inner_cond_code,
     969                 :             :                                             gimple_cond_lhs (inner_cond),
     970                 :             :                                             gimple_cond_rhs (inner_cond),
     971                 :             :                                             outer_cond_code,
     972                 :             :                                             gimple_cond_lhs (outer_cond),
     973                 :             :                                             gimple_cond_rhs (outer_cond),
     974                 :             :                                             gimple_bb (outer_cond)))
     975                 :      270097 :           && !(t = (fold_truth_andor_for_ifcombine
     976                 :      268061 :                     (TRUTH_ANDIF_EXPR, boolean_type_node,
     977                 :             :                      gimple_location (outer_cond),
     978                 :             :                      outer_cond_code,
     979                 :             :                      gimple_cond_lhs (outer_cond),
     980                 :             :                      gimple_cond_rhs (outer_cond),
     981                 :             :                      gimple_location (inner_cond),
     982                 :             :                      inner_cond_code,
     983                 :             :                      gimple_cond_lhs (inner_cond),
     984                 :             :                      gimple_cond_rhs (inner_cond),
     985                 :      268061 :                      single_pred (inner_cond_bb) != outer_cond_bb
     986                 :             :                      ? &ts : 0))))
     987                 :             :         {
     988                 :             :           /* Only combine conditions in this fallback case if the blocks are
     989                 :             :              neighbors.  */
     990                 :      264946 :           if (single_pred (inner_cond_bb) != outer_cond_bb)
     991                 :             :             return false;
     992                 :      145440 :           tree t1, t2;
     993                 :      145440 :           bool logical_op_non_short_circuit = LOGICAL_OP_NON_SHORT_CIRCUIT;
     994                 :      145440 :           if (param_logical_op_non_short_circuit != -1)
     995                 :         167 :             logical_op_non_short_circuit
     996                 :         167 :               = param_logical_op_non_short_circuit;
     997                 :      145440 :           if (!logical_op_non_short_circuit || sanitize_coverage_p ())
     998                 :         130 :             return false;
     999                 :             :           /* Only do this optimization if the inner bb contains only the conditional
    1000                 :             :              or there is one or 2 statements which are nop conversion for the comparison. */
    1001                 :      145310 :           if (!can_combine_bbs_with_short_circuit (inner_cond_bb,
    1002                 :             :                                                    gimple_cond_lhs (inner_cond),
    1003                 :             :                                                    gimple_cond_rhs (inner_cond)))
    1004                 :             :             return false;
    1005                 :       77749 :           t1 = fold_build2_loc (gimple_location (inner_cond),
    1006                 :             :                                 inner_cond_code,
    1007                 :             :                                 boolean_type_node,
    1008                 :             :                                 gimple_cond_lhs (inner_cond),
    1009                 :             :                                 gimple_cond_rhs (inner_cond));
    1010                 :       77749 :           t2 = fold_build2_loc (gimple_location (outer_cond),
    1011                 :             :                                 outer_cond_code,
    1012                 :             :                                 boolean_type_node,
    1013                 :             :                                 gimple_cond_lhs (outer_cond),
    1014                 :             :                                 gimple_cond_rhs (outer_cond));
    1015                 :       77749 :           t = fold_build2_loc (gimple_location (inner_cond),
    1016                 :             :                                TRUTH_AND_EXPR, boolean_type_node, t1, t2);
    1017                 :             :         }
    1018                 :             : 
    1019                 :       82900 :       if (!ifcombine_replace_cond (inner_cond, inner_inv,
    1020                 :             :                                    outer_cond, outer_inv,
    1021                 :             :                                    t, false, ts))
    1022                 :             :         return false;
    1023                 :             : 
    1024                 :       82899 :       if (dump_file)
    1025                 :             :         {
    1026                 :          30 :           fprintf (dump_file, "optimizing two comparisons to ");
    1027                 :          30 :           print_generic_expr (dump_file, t);
    1028                 :          30 :           if (ts)
    1029                 :             :             {
    1030                 :           0 :               fprintf (dump_file, " and ");
    1031                 :           0 :               print_generic_expr (dump_file, ts);
    1032                 :             :             }
    1033                 :          30 :           fprintf (dump_file, "\n");
    1034                 :             :         }
    1035                 :             : 
    1036                 :       82899 :       return true;
    1037                 :             :     }
    1038                 :             : 
    1039                 :             :   return false;
    1040                 :             : }
    1041                 :             : 
    1042                 :             : /* Helper function for tree_ssa_ifcombine_bb.  Recognize a CFG pattern and
    1043                 :             :    dispatch to the appropriate if-conversion helper for a particular
    1044                 :             :    set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
    1045                 :             :    PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
    1046                 :             :    OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
    1047                 :             :    INNER_COND_BB.  */
    1048                 :             : 
    1049                 :             : static bool
    1050                 :      956742 : tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
    1051                 :             :                          basic_block then_bb, basic_block else_bb,
    1052                 :             :                          basic_block phi_pred_bb, basic_block outer_succ_bb)
    1053                 :             : {
    1054                 :             :   /* The && form is characterized by a common else_bb with
    1055                 :             :      the two edges leading to it mergable.  The latter is
    1056                 :             :      guaranteed by matching PHI arguments in the else_bb and
    1057                 :             :      the inner cond_bb having no side-effects.  */
    1058                 :      956742 :   if (phi_pred_bb != else_bb
    1059                 :      937751 :       && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
    1060                 :     1034793 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
    1061                 :             :     {
    1062                 :             :       /* We have
    1063                 :             :            <outer_cond_bb>
    1064                 :             :              if (q) goto inner_cond_bb; else goto else_bb;
    1065                 :             :            <inner_cond_bb>
    1066                 :             :              if (p) goto ...; else goto else_bb;
    1067                 :             :              ...
    1068                 :             :            <else_bb>
    1069                 :             :              ...
    1070                 :             :        */
    1071                 :       69504 :       return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false);
    1072                 :             :     }
    1073                 :             : 
    1074                 :             :   /* And a version where the outer condition is negated.  */
    1075                 :      887238 :   if (phi_pred_bb != else_bb
    1076                 :      868247 :       && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
    1077                 :      897823 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
    1078                 :             :     {
    1079                 :             :       /* We have
    1080                 :             :            <outer_cond_bb>
    1081                 :             :              if (q) goto else_bb; else goto inner_cond_bb;
    1082                 :             :            <inner_cond_bb>
    1083                 :             :              if (p) goto ...; else goto else_bb;
    1084                 :             :              ...
    1085                 :             :            <else_bb>
    1086                 :             :              ...
    1087                 :             :        */
    1088                 :        4285 :       return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true);
    1089                 :             :     }
    1090                 :             : 
    1091                 :             :   /* The || form is characterized by a common then_bb with the
    1092                 :             :      two edges leading to it mergeable.  The latter is guaranteed
    1093                 :             :      by matching PHI arguments in the then_bb and the inner cond_bb
    1094                 :             :      having no side-effects.  */
    1095                 :      882953 :   if (phi_pred_bb != then_bb
    1096                 :      871258 :       && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
    1097                 :     1107063 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
    1098                 :             :     {
    1099                 :             :       /* We have
    1100                 :             :            <outer_cond_bb>
    1101                 :             :              if (q) goto then_bb; else goto inner_cond_bb;
    1102                 :             :            <inner_cond_bb>
    1103                 :             :              if (p) goto then_bb; else goto ...;
    1104                 :             :            <then_bb>
    1105                 :             :              ...
    1106                 :             :        */
    1107                 :      188560 :       return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true);
    1108                 :             :     }
    1109                 :             : 
    1110                 :             :   /* And a version where the outer condition is negated.  */
    1111                 :      694393 :   if (phi_pred_bb != then_bb
    1112                 :      682698 :       && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
    1113                 :      712017 :       && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
    1114                 :             :     {
    1115                 :             :       /* We have
    1116                 :             :            <outer_cond_bb>
    1117                 :             :              if (q) goto inner_cond_bb; else goto then_bb;
    1118                 :             :            <inner_cond_bb>
    1119                 :             :              if (p) goto then_bb; else goto ...;
    1120                 :             :            <then_bb>
    1121                 :             :              ...
    1122                 :             :        */
    1123                 :       12149 :       return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false);
    1124                 :             :     }
    1125                 :             : 
    1126                 :             :   return false;
    1127                 :             : }
    1128                 :             : 
    1129                 :             : /* Recognize a CFG pattern and dispatch to the appropriate
    1130                 :             :    if-conversion helper.  We start with BB as the innermost
    1131                 :             :    worker basic-block.  Returns true if a transformation was done.  */
    1132                 :             : 
    1133                 :             : static bool
    1134                 :     3980845 : tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
    1135                 :             : {
    1136                 :     3980845 :   bool ret = false;
    1137                 :     3980845 :   basic_block then_bb = NULL, else_bb = NULL;
    1138                 :             : 
    1139                 :     3980845 :   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
    1140                 :             :     return ret;
    1141                 :             : 
    1142                 :             :   /* Recognize && and || of two conditions with a common
    1143                 :             :      then/else block which entry edges we can merge.  That is:
    1144                 :             :        if (a || b)
    1145                 :             :          ;
    1146                 :             :      and
    1147                 :             :        if (a && b)
    1148                 :             :          ;
    1149                 :             :      This requires a single predecessor of the inner cond_bb.
    1150                 :             : 
    1151                 :             :      Look for an OUTER_COND_BBs to combine with INNER_COND_BB.  They need not
    1152                 :             :      be contiguous, as long as inner and intervening blocks have no side
    1153                 :             :      effects, and are either single-entry-single-exit or conditionals choosing
    1154                 :             :      between the same EXIT_BB with the same PHI args, possibly through an
    1155                 :             :      EXIT_PRED, and the path leading to INNER_COND_BB.  EXIT_PRED will be set
    1156                 :             :      just before (along with a successful combination) or just after setting
    1157                 :             :      EXIT_BB, to either THEN_BB, ELSE_BB, or INNER_COND_BB.  ??? We could
    1158                 :             :      potentially handle multi-block single-entry-single-exit regions, but the
    1159                 :             :      loop below only deals with single-entry-single-exit individual intervening
    1160                 :             :      blocks.  Larger regions without side effects are presumably rare, so it's
    1161                 :             :      probably not worth the effort.  */
    1162                 :     4548366 :   for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL,
    1163                 :             :          /* This initialization shouldn't be needed, but in case the compiler
    1164                 :             :             is not smart enough to tell, make it harmless.  */
    1165                 :     3980785 :          exit_pred = NULL;
    1166                 :     4548366 :        single_pred_p (bb) && bb_no_side_effects_p (bb);
    1167                 :      567581 :        bb = outer_cond_bb)
    1168                 :             :     {
    1169                 :     1398791 :       bool changed = false;
    1170                 :             : 
    1171                 :     1398791 :       outer_cond_bb = single_pred (bb);
    1172                 :             : 
    1173                 :             :       /* Skip blocks without conditions.  */
    1174                 :     1398791 :       if (single_succ_p (outer_cond_bb))
    1175                 :      112687 :         continue;
    1176                 :             : 
    1177                 :             :       /* When considering noncontiguous conditions, make sure that all
    1178                 :             :          non-final conditions lead to the same successor of the final
    1179                 :             :          condition, when not taking the path to inner_bb, so that we can
    1180                 :             :          combine C into A, both in A && (B && C), and in A || (B || C), but
    1181                 :             :          neither in A && (B || C), nor A || (B && C).  Say, if C goes to
    1182                 :             :          THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
    1183                 :             :          C (whether C is then or else), and A must go to X and B (whether then
    1184                 :             :          or else).
    1185                 :             : 
    1186                 :             :          We test for this, while allowing intervening nonconditional blocks, by
    1187                 :             :          first taking note of which of the successors of the inner conditional
    1188                 :             :          block is the exit path taken by the first considered outer conditional
    1189                 :             :          block.
    1190                 :             : 
    1191                 :             :          Having identified and saved the exit block in EXIT_BB at the end of
    1192                 :             :          the loop, here we test that subsequent conditional blocks under
    1193                 :             :          consideration also use the exit block as a successor, besides the
    1194                 :             :          block that leads to inner_cond_bb, and that the edges to exit share
    1195                 :             :          the same phi values.  */
    1196                 :     1286104 :       if (exit_bb
    1197                 :     1286104 :           && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
    1198                 :             :         break;
    1199                 :             : 
    1200                 :             :       /* After checking dests and phi args, we can also skip blocks whose
    1201                 :             :          conditions have been optimized down to a constant, without trying to
    1202                 :             :          combine them, but we must not skip the computation of EXIT_BB and the
    1203                 :             :          checking of same phi args.  */
    1204                 :     1266352 :       if (known_succ_p (outer_cond_bb))
    1205                 :             :         changed = false;
    1206                 :      128481 :       else if ((!exit_bb || exit_pred == inner_cond_bb)
    1207                 :     1054377 :                && tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
    1208                 :             :                                            then_bb, else_bb, inner_cond_bb, bb))
    1209                 :             :         changed = true, exit_pred = inner_cond_bb;
    1210                 :      840826 :       else if (exit_bb
    1211                 :      840826 :                ? exit_pred == else_bb
    1212                 :      712460 :                : forwarder_block_to (else_bb, then_bb))
    1213                 :             :         {
    1214                 :             :           /* Other possibilities for the && form, if else_bb is
    1215                 :             :              empty forwarder block to then_bb.  Compared to the above simpler
    1216                 :             :              forms this can be treated as if then_bb and else_bb were swapped,
    1217                 :             :              and the corresponding inner_cond_bb not inverted because of that.
    1218                 :             :              For same_phi_args_p we look at equality of arguments between
    1219                 :             :              edge from outer_cond_bb and the forwarder block.  */
    1220                 :       11855 :           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
    1221                 :             :                                        then_bb, else_bb, bb))
    1222                 :             :             changed = true, exit_pred = else_bb;
    1223                 :             :         }
    1224                 :      828971 :       else if (exit_bb
    1225                 :      828971 :                ? exit_pred == then_bb
    1226                 :      700632 :                : forwarder_block_to (then_bb, else_bb))
    1227                 :             :         {
    1228                 :             :           /* Other possibilities for the || form, if then_bb is
    1229                 :             :              empty forwarder block to else_bb.  Compared to the above simpler
    1230                 :             :              forms this can be treated as if then_bb and else_bb were swapped,
    1231                 :             :              and the corresponding inner_cond_bb not inverted because of that.
    1232                 :             :              For same_phi_args_p we look at equality of arguments between
    1233                 :             :              edge from outer_cond_bb and the forwarder block.  */
    1234                 :       18991 :           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
    1235                 :             :                                        then_bb, then_bb, bb))
    1236                 :             :             changed = true, exit_pred = then_bb;
    1237                 :             :         }
    1238                 :             : 
    1239                 :             :       if (changed)
    1240                 :       85284 :         ret = changed;
    1241                 :             : 
    1242                 :             :       /* If the inner condition is gone, there's no point in attempting to
    1243                 :             :          combine it any further.  */
    1244                 :       85284 :       if (changed && known_succ_p (inner_cond_bb))
    1245                 :             :         break;
    1246                 :             : 
    1247                 :             :       /* Starting at this point in the loop, we start preparing to attempt
    1248                 :             :          combinations in which OUTER_COND_BB will be an intervening block.
    1249                 :             :          Checking that it has a single predecessor is a very cheap test, unlike
    1250                 :             :          the PHI args tests below, so test it early and hopefully save the more
    1251                 :             :          expensive tests in case we won't be able to try other blocks.  */
    1252                 :     1266241 :       if (!single_pred_p (outer_cond_bb))
    1253                 :             :         break;
    1254                 :             : 
    1255                 :             :       /* Record the exit path taken by the outer condition.  */
    1256                 :      966520 :       if (!exit_bb)
    1257                 :             :         {
    1258                 :             :           /* If we have removed the outer condition entirely, we need not
    1259                 :             :              commit to an exit block yet, it's as if we'd merged the blocks and
    1260                 :             :              were starting afresh.  This is sound as long as we never replace
    1261                 :             :              the outer condition with a constant that leads away from the inner
    1262                 :             :              block.  Here's why we never do: when combining contiguous
    1263                 :             :              conditions, we replace the inner cond, and replace the outer cond
    1264                 :             :              with a constant that leads to inner, so this case is good.  When
    1265                 :             :              combining noncontiguous blocks, we normally modify outer, and
    1266                 :             :              replace inner with a constant or remainders of the original
    1267                 :             :              condition that couldn't be combined.  This test would normally not
    1268                 :             :              hit with noncontiguous blocks, because we'd have computed EXIT_BB
    1269                 :             :              before reaching the noncontiguous outer block.  However, if all
    1270                 :             :              intervening blocks are unconditional, including those just made
    1271                 :             :              unconditional, we may replace outer instead of inner with the
    1272                 :             :              combined condition.  If the combined noncontiguous conditions are
    1273                 :             :              mutually exclusive, we could end up with a constant outer
    1274                 :             :              condition, but then, the inner condition would also be a constant,
    1275                 :             :              and then we'd stop iterating because of the known_succ_p
    1276                 :             :              (inner_cond_bb) test above.  */
    1277                 :      642517 :           if (changed && known_succ_p (outer_cond_bb))
    1278                 :       65937 :             continue;
    1279                 :             : 
    1280                 :      576580 :           if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
    1281                 :       78196 :             exit_bb = then_bb;
    1282                 :      498384 :           else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
    1283                 :       30275 :             exit_bb = else_bb;
    1284                 :             :           else
    1285                 :             :             break;
    1286                 :             : 
    1287                 :             :           /* Find out which path from INNER_COND_BB shares PHI args with the
    1288                 :             :              edge (OUTER_COND_BB->EXIT_BB).  That path may involve a forwarder
    1289                 :             :              block, whether THEN_BB or ELSE_BB, and we need to know which one
    1290                 :             :              satisfies the condition to avoid combinations that could use
    1291                 :             :              different forwarding arrangements, because they would be unsound.
    1292                 :             :              E.g., given (a ? 0 : b ? 1 : c ? 1 : 0), after trying to merge b
    1293                 :             :              and c, we test that both share the same exit block, with the same
    1294                 :             :              value 1.  Whether or not that involves a forwarder block, if we
    1295                 :             :              don't go through the same (possibly absent) forwarder block in
    1296                 :             :              subsequent attempted combinations, e.g. a with c, we could find
    1297                 :             :              that a and inverted c share the same exit block with a different
    1298                 :             :              value, namely 0, which would enable an unsound merge.  We need all
    1299                 :             :              of inner, intervening and outer blocks to reach the same exit with
    1300                 :             :              the same value for the transformation to be sound.  So here we
    1301                 :             :              determine how to get to EXIT_BB from outer and inner with the same
    1302                 :             :              PHI values, record that in EXIT_PRED, and then subsequent
    1303                 :             :              combination attempts that have OUTER_COND_BB as an intervening
    1304                 :             :              block will ensure the same path to exit is taken, skipping unsound
    1305                 :             :              transformations.  */
    1306                 :      108471 :           if (changed)
    1307                 :             :             /* EXIT_PRED was set along with CHANGED, and the successful
    1308                 :             :                combination already checked for the same PHI args.  */;
    1309                 :      108365 :           else if (same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
    1310                 :             :             exit_pred = inner_cond_bb;
    1311                 :       30780 :           else if (then_bb == exit_bb
    1312                 :       22936 :                    && forwarder_block_to (else_bb, then_bb)
    1313                 :       33068 :                    && same_phi_args_p (outer_cond_bb, else_bb, exit_bb))
    1314                 :             :             exit_pred = else_bb;
    1315                 :       30722 :           else if (else_bb == exit_bb
    1316                 :        7844 :                    && forwarder_block_to (then_bb, else_bb)
    1317                 :       31759 :                    && same_phi_args_p (outer_cond_bb, then_bb, exit_bb))
    1318                 :             :             exit_pred = then_bb;
    1319                 :             :           else
    1320                 :             :             /* If none of the paths share the same PHI args, no combination is
    1321                 :             :                viable.  */
    1322                 :             :             break;
    1323                 :             :           /* Skip the PHI args test below, it's redundant with the tests we've
    1324                 :             :              just performed.  */
    1325                 :       77870 :           continue;
    1326                 :             :         }
    1327                 :             : 
    1328                 :             :       /* Before trying an earlier block, make sure INNER_COND_BB and the
    1329                 :             :          current OUTER_COND_BB share the same PHI args at EXIT_BB.  We don't
    1330                 :             :          need to check if the latest attempt at combining succeeded, because
    1331                 :             :          that means we'll have already checked.  But we can't only check outer
    1332                 :             :          and inner, we have to check that all intervening blocks also get to
    1333                 :             :          exit with the same result, otherwise the transformation may change the
    1334                 :             :          final result.  Consider (a ? 0 : b ? 1 : c ? 0 : -1).  If we combine
    1335                 :             :          (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
    1336                 :             :          rather than 1 when (!a&&b).  And if we were to replace inner instead
    1337                 :             :          of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
    1338                 :             :          yield 1 rather than 0 when (a).  */
    1339                 :      324003 :       if (!changed
    1340                 :      324003 :           && !same_phi_args_p (outer_cond_bb, exit_pred, exit_bb))
    1341                 :             :         break;
    1342                 :             :     }
    1343                 :             : 
    1344                 :     3980785 :   return ret;
    1345                 :             : }
    1346                 :             : 
    1347                 :             : /* Main entry for the tree if-conversion pass.  */
    1348                 :             : 
    1349                 :             : namespace {
    1350                 :             : 
    1351                 :             : const pass_data pass_data_tree_ifcombine =
    1352                 :             : {
    1353                 :             :   GIMPLE_PASS, /* type */
    1354                 :             :   "ifcombine", /* name */
    1355                 :             :   OPTGROUP_NONE, /* optinfo_flags */
    1356                 :             :   TV_TREE_IFCOMBINE, /* tv_id */
    1357                 :             :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    1358                 :             :   0, /* properties_provided */
    1359                 :             :   0, /* properties_destroyed */
    1360                 :             :   0, /* todo_flags_start */
    1361                 :             :   TODO_update_ssa, /* todo_flags_finish */
    1362                 :             : };
    1363                 :             : 
    1364                 :             : class pass_tree_ifcombine : public gimple_opt_pass
    1365                 :             : {
    1366                 :             : public:
    1367                 :      280831 :   pass_tree_ifcombine (gcc::context *ctxt)
    1368                 :      561662 :     : gimple_opt_pass (pass_data_tree_ifcombine, ctxt)
    1369                 :             :   {}
    1370                 :             : 
    1371                 :             :   /* opt_pass methods: */
    1372                 :             :   unsigned int execute (function *) final override;
    1373                 :             : 
    1374                 :             : }; // class pass_tree_ifcombine
    1375                 :             : 
    1376                 :             : unsigned int
    1377                 :     1000722 : pass_tree_ifcombine::execute (function *fun)
    1378                 :             : {
    1379                 :     1000722 :   basic_block *bbs;
    1380                 :     1000722 :   bool cfg_changed = false;
    1381                 :     1000722 :   int i;
    1382                 :             : 
    1383                 :     1000722 :   bbs = single_pred_before_succ_order ();
    1384                 :     1000722 :   calculate_dominance_info (CDI_DOMINATORS);
    1385                 :     1000722 :   mark_ssa_maybe_undefs ();
    1386                 :             : 
    1387                 :             :   /* Search every basic block for COND_EXPR we may be able to optimize.
    1388                 :             : 
    1389                 :             :      We walk the blocks in order that guarantees that a block with
    1390                 :             :      a single predecessor is processed after the predecessor.
    1391                 :             :      This ensures that we collapse outter ifs before visiting the
    1392                 :             :      inner ones, and also that we do not try to visit a removed
    1393                 :             :      block.  This is opposite of PHI-OPT, because we cascade the
    1394                 :             :      combining rather than cascading PHIs. */
    1395                 :    10637074 :   for (i = n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
    1396                 :             :     {
    1397                 :     9636352 :       basic_block bb = bbs[i];
    1398                 :             : 
    1399                 :    19272704 :       if (safe_is_a <gcond *> (*gsi_last_bb (bb)))
    1400                 :     3980845 :         if (tree_ssa_ifcombine_bb (bb))
    1401                 :     9636352 :           cfg_changed |= true;
    1402                 :             :     }
    1403                 :             : 
    1404                 :     1000722 :   free (bbs);
    1405                 :             : 
    1406                 :     1000722 :   return cfg_changed ? TODO_cleanup_cfg : 0;
    1407                 :             : }
    1408                 :             : 
    1409                 :             : } // anon namespace
    1410                 :             : 
    1411                 :             : gimple_opt_pass *
    1412                 :      280831 : make_pass_tree_ifcombine (gcc::context *ctxt)
    1413                 :             : {
    1414                 :      280831 :   return new pass_tree_ifcombine (ctxt);
    1415                 :             : }
        

Generated by: LCOV version 2.1-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.