LCOV - code coverage report
Current view: top level - gcc - tree-ssa-phiopt.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.7 % 2336 2235
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 57 57
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Optimization of PHI nodes by converting them into straightline code.
       2              :    Copyright (C) 2004-2026 Free Software Foundation, Inc.
       3              : 
       4              : This file is part of GCC.
       5              : 
       6              : GCC is free software; you can redistribute it and/or modify it
       7              : under the terms of the GNU General Public License as published by the
       8              : Free Software Foundation; either version 3, or (at your option) any
       9              : later version.
      10              : 
      11              : GCC is distributed in the hope that it will be useful, but WITHOUT
      12              : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14              : for more details.
      15              : 
      16              : You should have received a copy of the GNU General Public License
      17              : along with GCC; see the file COPYING3.  If not see
      18              : <http://www.gnu.org/licenses/>.  */
      19              : 
      20              : #include "config.h"
      21              : #include "system.h"
      22              : #include "coretypes.h"
      23              : #include "backend.h"
      24              : #include "insn-codes.h"
      25              : #include "rtl.h"
      26              : #include "tree.h"
      27              : #include "gimple.h"
      28              : #include "cfghooks.h"
      29              : #include "tree-pass.h"
      30              : #include "ssa.h"
      31              : #include "tree-ssa.h"
      32              : #include "optabs-tree.h"
      33              : #include "insn-config.h"
      34              : #include "gimple-pretty-print.h"
      35              : #include "fold-const.h"
      36              : #include "stor-layout.h"
      37              : #include "cfganal.h"
      38              : #include "gimple-iterator.h"
      39              : #include "tree-cfg.h"
      40              : #include "tree-dfa.h"
      41              : #include "domwalk.h"
      42              : #include "cfgloop.h"
      43              : #include "tree-data-ref.h"
      44              : #include "tree-scalar-evolution.h"
      45              : #include "tree-inline.h"
      46              : #include "case-cfn-macros.h"
      47              : #include "tree-eh.h"
      48              : #include "gimple-fold.h"
      49              : #include "internal-fn.h"
      50              : #include "gimple-range.h"
      51              : #include "gimple-match.h"
      52              : #include "dbgcnt.h"
      53              : #include "tree-ssa-propagate.h"
      54              : #include "tree-ssa-dce.h"
      55              : #include "tree-ssa-loop-niter.h"
      56              : #include "gimple-predict.h"
      57              : #include "alias.h"
      58              : #include "tree-ssa-threadedge.h"
      59              : 
      60              : /* Return the singleton PHI in the SEQ of PHIs for edges E0 and E1. */
      61              : 
      62              : static gphi *
      63      3526154 : single_non_singleton_phi_for_edges (gimple_seq seq, edge e0, edge e1)
      64              : {
      65      3526154 :   gimple_stmt_iterator i;
      66      3526154 :   gphi *phi = NULL;
      67      5247178 :   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
      68              :     {
      69      4278157 :       gphi *p = as_a <gphi *> (gsi_stmt (i));
      70              :       /* If the PHI arguments are equal then we can skip this PHI. */
      71      4278157 :       if (operand_equal_for_phi_arg_p (gimple_phi_arg_def (p, e0->dest_idx),
      72      4278157 :                                        gimple_phi_arg_def (p, e1->dest_idx)))
      73       254495 :         continue;
      74              : 
      75              :       /* Punt on virtual phis with different arguments from the edges.  */
      76      8047324 :       if (virtual_operand_p (gimple_phi_result (p)))
      77              :         return NULL;
      78              : 
      79              :       /* If we already have a PHI that has the two edge arguments are
      80              :          different, then return it is not a singleton for these PHIs. */
      81      1729409 :       if (phi)
      82              :         return NULL;
      83              : 
      84              :       phi = p;
      85              :     }
      86              :   return phi;
      87              : }
      88              : 
      89              : /* Replace PHI node element whose edge is E in block BB with variable NEW.
      90              :    Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
      91              :    is known to have two edges, one of which must reach BB).  */
      92              : 
      93              : static void
      94        97804 : replace_phi_edge_with_variable (basic_block cond_block,
      95              :                                 edge e, gphi *phi, tree new_tree,
      96              :                                 bitmap dce_ssa_names = nullptr)
      97              : {
      98        97804 :   basic_block bb = gimple_bb (phi);
      99        97804 :   gimple_stmt_iterator gsi;
     100        97804 :   tree phi_result = gimple_phi_result (phi);
     101        97804 :   bool deleteboth = false;
     102              : 
     103              :   /* Duplicate range info if they are the only things setting the target PHI.
     104              :      This is needed as later on, the new_tree will be replacing
     105              :      The assignment of the PHI.
     106              :      For an example:
     107              :      bb1:
     108              :      _4 = min<a_1, 255>
     109              :      goto bb2
     110              : 
     111              :      # RANGE [-INF, 255]
     112              :      a_3 = PHI<_4(1)>
     113              :      bb3:
     114              : 
     115              :      use(a_3)
     116              :      And _4 gets propagated into the use of a_3 and losing the range info.
     117              :      This can't be done for more than 2 incoming edges as the propagation
     118              :      won't happen.
     119              :      The new_tree needs to be defined in the same basic block as the conditional.  */
     120        97804 :   if (TREE_CODE (new_tree) == SSA_NAME
     121        97783 :       && EDGE_COUNT (gimple_bb (phi)->preds) == 2
     122        63541 :       && INTEGRAL_TYPE_P (TREE_TYPE (phi_result))
     123        58268 :       && !SSA_NAME_RANGE_INFO (new_tree)
     124        57860 :       && SSA_NAME_RANGE_INFO (phi_result)
     125        31515 :       && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) == cond_block
     126       129318 :       && dbg_cnt (phiopt_edge_range))
     127        31514 :     duplicate_ssa_name_range_info (new_tree, phi_result);
     128              : 
     129              :   /* Change the PHI argument to new.  */
     130        97804 :   SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);
     131              : 
     132              :   /* Remove the empty basic block.  */
     133        97804 :   edge edge_to_remove = NULL, keep_edge = NULL;
     134        97804 :   if (EDGE_SUCC (cond_block, 0)->dest == bb)
     135              :     {
     136        29930 :       edge_to_remove = EDGE_SUCC (cond_block, 1);
     137        29930 :       keep_edge = EDGE_SUCC (cond_block, 0);
     138              :     }
     139        67874 :   else if (EDGE_SUCC (cond_block, 1)->dest == bb)
     140              :     {
     141              :       edge_to_remove = EDGE_SUCC (cond_block, 0);
     142              :       keep_edge = EDGE_SUCC (cond_block, 1);
     143              :     }
     144         1386 :   else if ((keep_edge = find_edge (cond_block, e->src)))
     145              :     {
     146         1386 :       basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
     147         1386 :       basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
     148              :       // If the new phi entry does not refer to either of
     149              :       // the middle bb, then either middle bbs can be deleted
     150              :       // as long as the middle bbs only reach the phi bb and only
     151              :       // reachable from the conditional bb.
     152       100576 :       if (single_pred_p (bb1) && single_pred_p (bb2)
     153         2772 :           && single_succ_p (bb1) && single_succ_p (bb2)
     154         2772 :           && (TREE_CODE (new_tree) != SSA_NAME
     155         1386 :               || (gimple_bb (SSA_NAME_DEF_STMT (new_tree)) != bb1
     156         1386 :                   && gimple_bb (SSA_NAME_DEF_STMT (new_tree)) != bb2)))
     157              :         deleteboth = true;
     158              :     }
     159              :   else
     160            0 :     gcc_unreachable ();
     161              : 
     162              :   /* If we are removing the cond on a loop exit,
     163              :      reset number of iteration information of the loop. */
     164        97804 :   if (loop_exits_from_bb_p (cond_block->loop_father, cond_block))
     165              :     {
     166            0 :       auto loop = cond_block->loop_father;
     167            0 :       free_numbers_of_iterations_estimates (loop);
     168            0 :       loop->any_upper_bound = false;
     169            0 :       loop->any_likely_upper_bound = false;
     170              :     }
     171              : 
     172        97804 :   if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
     173              :     {
     174        85133 :       e->flags |= EDGE_FALLTHRU;
     175        85133 :       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
     176        85133 :       e->probability = profile_probability::always ();
     177        85133 :       delete_basic_block (edge_to_remove->dest);
     178              : 
     179              :       /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
     180        85133 :       gsi = gsi_last_bb (cond_block);
     181        85133 :       gsi_remove (&gsi, true);
     182              :     }
     183        12671 :   else if (deleteboth)
     184              :     {
     185         1386 :       basic_block bb1 = EDGE_SUCC (cond_block, 0)->dest;
     186         1386 :       basic_block bb2 = EDGE_SUCC (cond_block, 1)->dest;
     187              : 
     188         1386 :       edge newedge = redirect_edge_and_branch (keep_edge, bb);
     189              : 
     190              :       /* The new edge should be the same. */
     191         1386 :       gcc_assert (newedge == keep_edge);
     192              : 
     193         1386 :       keep_edge->flags |= EDGE_FALLTHRU;
     194         1386 :       keep_edge->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
     195         1386 :       keep_edge->probability = profile_probability::always ();
     196              : 
     197              :       /* Copy the edge's phi entry from the old one. */
     198         1386 :       copy_phi_arg_into_existing_phi (e, keep_edge);
     199              : 
     200              :       /* Delete the old 2 empty basic blocks */
     201         1386 :       delete_basic_block (bb1);
     202         1386 :       delete_basic_block (bb2);
     203              : 
     204              :       /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
     205         1386 :       gsi = gsi_last_bb (cond_block);
     206         1386 :       gsi_remove (&gsi, true);
     207              :     }
     208              :   else
     209              :     {
     210              :       /* If there are other edges into the middle block make
     211              :          CFG cleanup deal with the edge removal to avoid
     212              :          updating dominators here in a non-trivial way.  */
     213        22570 :       gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_block));
     214        11285 :       if (keep_edge->flags & EDGE_FALSE_VALUE)
     215         7392 :         gimple_cond_make_false (cond);
     216         3893 :       else if (keep_edge->flags & EDGE_TRUE_VALUE)
     217         3893 :         gimple_cond_make_true (cond);
     218              :     }
     219              : 
     220        97804 :   if (dce_ssa_names)
     221        95764 :     simple_dce_from_worklist (dce_ssa_names);
     222              : 
     223        97804 :   statistics_counter_event (cfun, "Replace PHI with variable", 1);
     224              : 
     225        97804 :   if (dump_file && (dump_flags & TDF_DETAILS))
     226           30 :     fprintf (dump_file,
     227              :               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
     228              :               cond_block->index,
     229              :               bb->index);
     230        97804 : }
     231              : 
     232              : /* Returns true if the OPERANDS (OPCOUNTED) defined from DEF_STMT is profitable to move
     233              :    to the usage into the basic block MERGE where the new statement
     234              :    will be located.  */
     235              : static bool
     236        73249 : is_factor_profitable (gimple *def_stmt, basic_block merge, tree *operands, unsigned opcount)
     237              : {
     238              :   /* The defining statement should be conditional.  */
     239        73249 :   if (dominated_by_p (CDI_DOMINATORS, merge,
     240        73249 :                       gimple_bb (def_stmt)))
     241              :     return false;
     242              : 
     243              :   /* We should not increase the live range of arg
     244              :      across too many statements or calls.  */
     245        68989 :   gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
     246        68989 :   gsi_next_nondebug (&gsi);
     247              : 
     248              :   /* Skip past nops and predicates. */
     249       138631 :   while (!gsi_end_p (gsi)
     250        69642 :          && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
     251         9936 :              || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT))
     252          653 :     gsi_next_nondebug (&gsi);
     253              : 
     254              :   /* If the defining statement is at the end of the bb, then it is
     255              :      always profitable to be to move.  */
     256        68989 :   if (gsi_end_p (gsi))
     257              :     return true;
     258              : 
     259              :   /* If there are a few (non-call/asm) statements between
     260              :      the old defining statement and end of the bb, then
     261              :      the live range of operands will increase enough.  */
     262         9283 :   int max_statements = param_phiopt_factor_max_stmts_live;
     263         9283 :   bool stmts_extending_ok = true;
     264              : 
     265        27219 :   while (!gsi_end_p (gsi))
     266              :     {
     267        19106 :       gimple *stmt = gsi_stmt (gsi);
     268        19106 :       auto gcode = gimple_code (stmt);
     269              :       /* Skip over NOPs and predicts. */
     270        19151 :       if (gcode == GIMPLE_NOP
     271        19106 :           || gcode == GIMPLE_PREDICT)
     272              :         {
     273           45 :           gsi_next_nondebug (&gsi);
     274           45 :           continue;
     275              :         }
     276              :       /* Non-assigns will extend the live range too much.  */
     277        19061 :       if (gcode != GIMPLE_ASSIGN)
     278              :         {
     279              :           stmts_extending_ok = false;
     280              :           break;
     281              :         }
     282        18779 :       max_statements --;
     283        18779 :       if (max_statements == 0)
     284              :         {
     285              :           stmts_extending_ok = false;
     286              :           break;
     287              :         }
     288        17891 :       gsi_next_nondebug (&gsi);
     289              :   }
     290         9283 :   if (stmts_extending_ok)
     291              :     return true;
     292              : 
     293              :   /* Loop over all of the operands to see if all are used after anyways.  */
     294         1703 :   for (unsigned i = 0; i < opcount; i++)
     295              :     {
     296         1200 :       tree arg = operands[i];
     297              :       /* If the arg is invariant, then there is
     298              :          no extending of the live range. */
     299         1200 :       if (is_gimple_min_invariant (arg))
     300          460 :         continue;
     301              : 
     302              :       /* Otherwise, the arg needs to be a ssa name. */
     303          740 :       if (TREE_CODE (arg) != SSA_NAME)
     304          667 :         return false;
     305              : 
     306              :       /* Check if the uses of arg is dominated by merge block, this is a quick and
     307              :          rough estimate if arg is still alive at the merge bb.  */
     308              :       /* FIXME: extend to a more complete live range detection.  */
     309          740 :       use_operand_p use_p;
     310          740 :       imm_use_iterator iter;
     311          740 :       bool usedafter = false;
     312         2362 :       FOR_EACH_IMM_USE_FAST (use_p, iter, arg)
     313              :         {
     314         1695 :           gimple *use_stmt = USE_STMT (use_p);
     315         1695 :           if (is_gimple_debug (use_stmt))
     316          312 :             continue;
     317         1383 :           basic_block use_bb = gimple_bb (use_stmt);
     318         1383 :           if (dominated_by_p (CDI_DOMINATORS, merge, use_bb))
     319              :             {
     320              :               usedafter = true;
     321              :               break;
     322              :             }
     323          740 :         }
     324          740 :       if (!usedafter)
     325              :         return false;
     326              :     }
     327              :   return true;
     328              : }
     329              : 
     330              : /* PR66726: Factor operations out of COND_EXPR.  If the arguments of the PHI
     331              :    stmt are Unary operator, factor out the operation and perform the operation
     332              :    to the result of PHI stmt.  COND_STMT is the controlling predicate.
     333              :    Return true if the operation was factored out; false otherwise.  */
     334              : 
     335              : static bool
     336      3068009 : factor_out_conditional_operation (edge e0, edge e1, basic_block merge,
     337              :                                   gphi *phi, gimple *cond_stmt,
     338              :                                   bool early_p)
     339              : {
     340      3068009 :   gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL;
     341      3068009 :   tree temp, result;
     342      3068009 :   gphi *newphi;
     343      3068009 :   gimple_stmt_iterator gsi, gsi_for_def;
     344      3068009 :   location_t locus = gimple_location (phi);
     345      3068009 :   gimple_match_op arg0_op, arg1_op;
     346              : 
     347              :   /* We should only get here if the phi had two arguments.  */
     348      3068009 :   gcc_assert (gimple_phi_num_args (phi) == 2);
     349              : 
     350              :   /* Virtual operands are never handled. */
     351      6136018 :   if (virtual_operand_p (gimple_phi_result (phi)))
     352              :     return false;
     353              : 
     354      1346614 :   tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
     355      1346614 :   tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
     356      1346614 :   location_t narg0_loc = gimple_location (phi);
     357      1346614 :   location_t narg1_loc = gimple_location (phi);
     358      1346614 :   if (gimple_phi_arg_location (phi, e0->dest_idx) != UNKNOWN_LOCATION)
     359      1127859 :     narg0_loc = gimple_phi_arg_location (phi, e0->dest_idx);
     360      1346614 :   if (gimple_phi_arg_location (phi, e1->dest_idx) != UNKNOWN_LOCATION)
     361       950004 :     narg1_loc = gimple_phi_arg_location (phi, e1->dest_idx);
     362              : 
     363      1346614 :   gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
     364              : 
     365              :   /* Arguments that are the same don't have anything to be
     366              :      done to them. */
     367      1346614 :   if (operand_equal_for_phi_arg_p (arg0, arg1))
     368              :     return false;
     369              : 
     370              :   /* First canonicalize to simplify tests.  */
     371      1346424 :   if (TREE_CODE (arg0) != SSA_NAME)
     372              :     {
     373       261796 :       std::swap (arg0, arg1);
     374       261796 :       std::swap (e0, e1);
     375              :     }
     376              : 
     377      1346424 :   if (TREE_CODE (arg0) != SSA_NAME
     378      1225391 :       || (TREE_CODE (arg1) != SSA_NAME
     379       496390 :           && TREE_CODE (arg1) != INTEGER_CST))
     380              :     return false;
     381              : 
     382              :   /* Check if arg0 is an SSA_NAME and the stmt which defines arg0 is
     383              :      an unary operation.  */
     384      1189424 :   arg0_def_stmt = SSA_NAME_DEF_STMT (arg0);
     385      1189424 :   if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
     386              :     return false;
     387              : 
     388              :   /* Check to make sure none of the operands are in abnormal phis.  */
     389       617616 :   if (arg0_op.operands_occurs_in_abnormal_phi ())
     390              :    return false;
     391              : 
     392       617616 :   tree new_arg0;
     393       617616 :   tree new_arg1;
     394       617616 :   int opnum = -1;
     395              : 
     396              :   /* If arg0 have > 1 use, then this transformation actually increases
     397              :      the number of expressions evaluated at runtime.  */
     398       617616 :   if (!has_single_use (arg0))
     399              :     return false;
     400       504120 :   if (gimple_has_location (arg0_def_stmt))
     401       464715 :     narg0_loc = gimple_location (arg0_def_stmt);
     402              : 
     403       504120 :   if (TREE_CODE (arg1) == SSA_NAME)
     404              :     {
     405              :       /* Check if arg1 is an SSA_NAME.  */
     406       325256 :       arg1_def_stmt = SSA_NAME_DEF_STMT (arg1);
     407       325256 :       if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
     408       316639 :         return false;
     409       168028 :       if (arg1_op.code != arg0_op.code)
     410              :         return false;
     411        48671 :       if (arg1_op.num_ops != arg0_op.num_ops)
     412              :         return false;
     413        48655 :       if (arg1_op.operands_occurs_in_abnormal_phi ())
     414              :         return false;
     415              : 
     416              :       /* For the complex expression, don't factor
     417              :          out, that will confuse the uninitializing
     418              :          warnings.  */
     419        48655 :       if (arg1_op.code == COMPLEX_EXPR)
     420              :         return false;
     421              : 
     422              :       /* If arg1 have > 1 use, then this transformation actually increases
     423              :          the number of expressions evaluated at runtime.  */
     424        48540 :       if (!has_single_use (arg1))
     425              :         return false;
     426              : 
     427        36383 :       opnum = find_different_opnum (arg0_op, arg1_op, &new_arg0, &new_arg1);
     428        36383 :       if (opnum == -1)
     429              :         return false;
     430              : 
     431              :       /* Check to make sure extending the lifetimes of all operands is ok.  */
     432        14235 :       if (!is_factor_profitable (arg0_def_stmt, merge,
     433              :                                  arg0_op.ops, arg0_op.num_ops))
     434              :         return false;
     435        13172 :       if (!is_factor_profitable (arg1_def_stmt, merge,
     436              :                                  arg1_op.ops, arg1_op.num_ops))
     437              :         return false;
     438              : 
     439        10206 :       tree args[2] = { new_arg0, new_arg1 };
     440        10206 :       location_t locs[2];
     441        10206 :       locs[0] = gimple_location (arg0_def_stmt);
     442        10206 :       locs[1] = gimple_location (arg1_def_stmt);
     443        10206 :       if (!factor_operation_ok (arg1_op.code, opnum, args, locs, 2, false, !early_p))
     444              :         return false;
     445              : 
     446         8617 :       if (gimple_has_location (arg1_def_stmt))
     447         8365 :         narg1_loc = gimple_location (arg1_def_stmt);
     448              : 
     449              :       /* Chose the location for the new statement if the phi location is unknown.  */
     450         8617 :       if (locus == UNKNOWN_LOCATION)
     451              :         {
     452         8617 :           if (narg0_loc == UNKNOWN_LOCATION
     453         8617 :               && narg1_loc != UNKNOWN_LOCATION)
     454              :             locus = narg1_loc;
     455         8617 :           else if (narg0_loc != UNKNOWN_LOCATION
     456         8617 :                    && narg1_loc == UNKNOWN_LOCATION)
     457           49 :             locus = narg0_loc;
     458              :         }
     459              :     }
     460       178864 :   else if (arg0_op.num_ops != 1)
     461              :     return false;
     462              :   else
     463              :     {
     464        52344 :       new_arg0 = arg0_op.ops[0];
     465        52344 :       opnum = 0;
     466              :       /* For constants only handle if the phi was the only one. */
     467        52344 :       if (single_non_singleton_phi_for_edges (phi_nodes (merge), e0, e1) == NULL)
     468              :         return false;
     469              :       /* TODO: handle more than just casts and ~/- here. */
     470        39023 :       if (!gimple_assign_cast_p (arg0_def_stmt)
     471         6688 :           && arg0_op.code != NEGATE_EXPR
     472        45222 :           && arg0_op.code != BIT_NOT_EXPR)
     473              :         return false;
     474        34064 :       if (!is_factor_profitable (arg0_def_stmt, merge, arg0_op.ops, arg0_op.num_ops))
     475              :         return false;
     476              : 
     477              :       // Heuristics for ~/-, is about being able to being able to handle
     478              :       // `if (a) t = -1; else t = -(CMP);`
     479              :       // and the like.  - is usually used for a mask to emulate a
     480              :       // vector.
     481        33184 :       if (arg0_op.code == NEGATE_EXPR
     482        33184 :           || arg0_op.code == BIT_NOT_EXPR)
     483              :         {
     484         1696 :           if (TREE_CODE (arg1) != INTEGER_CST
     485         1696 :               || TREE_CODE (new_arg0) != SSA_NAME)
     486              :             return false;
     487              : 
     488              :           // For neg, only allow -1, 0 as those
     489              :           //  the only ones which will reduce.
     490         1696 :           if (arg0_op.code == NEGATE_EXPR
     491          477 :               && !integer_zerop (arg1)
     492         1983 :               && !integer_minus_onep (arg1))
     493              :             return false;
     494              :           // For ~, only allow -2 (~1), -1 (~0) as those
     495              :           //  the only ones which will reduce.
     496         2872 :           if (arg0_op.code == BIT_NOT_EXPR
     497         1219 :               && !integer_minus_onep (arg1)
     498         3438 :               && ~wi::to_wide (arg1) != 1)
     499              :             return false;
     500              : 
     501              :           // Look to see if the -/~ comes from a cast from a boolean.
     502          654 :           gimple *arg0_def_def_stmt = SSA_NAME_DEF_STMT (new_arg0);
     503          654 :           if (gimple_bb (arg0_def_def_stmt) != gimple_bb (arg0_def_stmt))
     504              :             return false;
     505          434 :           if (!gimple_assign_cast_p (arg0_def_def_stmt))
     506              :             return false;
     507          140 :           tree_code ass_code = gimple_assign_rhs_code (arg0_def_def_stmt);
     508          140 :           if (!CONVERT_EXPR_CODE_P (ass_code))
     509              :             return false;
     510          136 :           tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (arg0_def_def_stmt));
     511          136 :           if (!INTEGRAL_TYPE_P (rhs_type)
     512          136 :               || !TYPE_UNSIGNED (rhs_type)
     513          228 :               || TYPE_PRECISION (rhs_type) != 1)
     514              :             return false;
     515              :         }
     516              : 
     517              :       /* If arg1 is an INTEGER_CST, fold it to new type if it fits, or else
     518              :          if the bits will not be modified during the conversion, except for
     519              :          boolean types whose precision is not 1 (see int_fits_type_p).  */
     520        62963 :       else if (!INTEGRAL_TYPE_P (TREE_TYPE (new_arg0))
     521        62699 :                || !(int_fits_type_p (arg1, TREE_TYPE (new_arg0))
     522         1627 :                     || (TYPE_PRECISION (TREE_TYPE (new_arg0))
     523         1627 :                          == TYPE_PRECISION (TREE_TYPE (arg1))
     524          708 :                         && (TREE_CODE (TREE_TYPE (new_arg0)) != BOOLEAN_TYPE
     525            0 :                             || TYPE_PRECISION (TREE_TYPE (new_arg0)) == 1))))
     526              :         return false;
     527              : 
     528              :       /* For the INTEGER_CST case, we are just moving the
     529              :          conversion from one place to another, which can often
     530              :          hurt as the conversion moves further away from the
     531              :          statement that computes the value.  So, perform this
     532              :          only if new_arg0 is an operand of COND_STMT, or
     533              :          if arg0_def_stmt is the only non-debug stmt in
     534              :          its basic block, because then it is possible this
     535              :          could enable further optimizations (minmax replacement
     536              :          etc.).  See PR71016.
     537              :          Note no-op conversions don't have this issue as
     538              :          it will not generate any zero/sign extend in that case.  */
     539        30305 :       else if ((TYPE_PRECISION (TREE_TYPE (new_arg0))
     540        30305 :                 != TYPE_PRECISION (TREE_TYPE (arg1)))
     541        14530 :                && new_arg0 != gimple_cond_lhs (cond_stmt)
     542        13829 :                && new_arg0 != gimple_cond_rhs (cond_stmt)
     543        44128 :                && gimple_bb (arg0_def_stmt) == e0->src)
     544              :         {
     545        13823 :           gsi = gsi_for_stmt (arg0_def_stmt);
     546        13823 :           gsi_prev_nondebug (&gsi);
     547              :           /* Ignore nops, predicates and labels. */
     548        27658 :           while (!gsi_end_p (gsi)
     549        13835 :                   && (gimple_code (gsi_stmt (gsi)) == GIMPLE_NOP
     550              :                       || gimple_code (gsi_stmt (gsi)) == GIMPLE_PREDICT
     551              :                       || gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL))
     552           12 :             gsi_prev_nondebug (&gsi);
     553              : 
     554        13823 :           if (!gsi_end_p (gsi))
     555              :             {
     556        10391 :               gimple *stmt = gsi_stmt (gsi);
     557        10391 :               if (gassign *assign = dyn_cast <gassign *> (stmt))
     558              :                 {
     559         9758 :                   tree lhs = gimple_assign_lhs (assign);
     560         9758 :                   tree lhst = TREE_TYPE (lhs);
     561         9758 :                   enum tree_code ass_code
     562         9758 :                     = gimple_assign_rhs_code (assign);
     563         9758 :                   if (ass_code != MAX_EXPR && ass_code != MIN_EXPR
     564              :                       /* Conversions from boolean like types is ok
     565              :                          as `a?1:b` and `a?0:b` will always simplify
     566              :                          to `a & b` or `a | b`.
     567              :                          See PR 116890.  */
     568         9758 :                       && !(INTEGRAL_TYPE_P (lhst)
     569         9279 :                            && TYPE_UNSIGNED (lhst)
     570         6917 :                            && TYPE_PRECISION (lhst) == 1))
     571              :                     return false;
     572         4663 :                   if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
     573              :                     return false;
     574         4621 :                   gsi_prev_nondebug (&gsi);
     575         4621 :                   if (!gsi_end_p (gsi))
     576              :                     return false;
     577              :                 }
     578              :               else
     579              :                 return false;
     580              :             }
     581              :         }
     582              : 
     583              :       // - is still the opposite of -, likewise for ~.
     584        20349 :       if (arg0_op.code == NEGATE_EXPR
     585        20349 :           || arg0_op.code == BIT_NOT_EXPR)
     586           91 :         new_arg1 = fold_build1 ((tree_code)arg0_op.code,
     587              :                                 TREE_TYPE (new_arg0), arg1);
     588              :       else
     589        20258 :         new_arg1 = fold_convert (TREE_TYPE (new_arg0), arg1);
     590              : 
     591              :       /* Drop the overflow that fold_convert might add. */
     592        20349 :       if (TREE_OVERFLOW (new_arg1))
     593            0 :         new_arg1 = drop_tree_overflow (new_arg1);
     594              : 
     595              :       /* The locus of the new statement is arg0 defining statement. */
     596        20349 :       if (gimple_has_location (arg0_def_stmt))
     597        19861 :         locus = gimple_location (arg0_def_stmt);
     598              :     }
     599              : 
     600              :   /* Create a new PHI stmt.  */
     601        28966 :   result = gimple_phi_result (phi);
     602        28966 :   temp = make_ssa_name (TREE_TYPE (new_arg0), NULL);
     603              : 
     604        28966 :   gimple_match_op new_op = arg0_op;
     605              : 
     606              :   /* Create the operation stmt if possible and insert it.  */
     607        28966 :   new_op.ops[opnum] = temp;
     608        28966 :   gimple_seq seq = NULL;
     609        28966 :   result = maybe_push_res_to_seq (&new_op, &seq, result);
     610              : 
     611              :   /* If we can't create the new statement, release the temp name
     612              :      and return back.  */
     613        28966 :   if (!result)
     614              :     {
     615          259 :       release_ssa_name (temp);
     616          259 :       return false;
     617              :     }
     618              : 
     619        28707 :   if (locus != UNKNOWN_LOCATION)
     620        19910 :     annotate_all_with_location (seq, locus);
     621        28707 :   gsi = gsi_after_labels (gimple_bb (phi));
     622        28707 :   gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
     623              : 
     624        28707 :   newphi = create_phi_node (temp, gimple_bb (phi));
     625              : 
     626        28707 :   if (dump_file && (dump_flags & TDF_DETAILS))
     627              :     {
     628           38 :       fprintf (dump_file, "PHI ");
     629           38 :       print_generic_expr (dump_file, gimple_phi_result (phi));
     630           38 :       fprintf (dump_file,
     631              :                " changed to factor operation out from COND_EXPR.\n");
     632           38 :       fprintf (dump_file, "New stmt with OPERATION that defines ");
     633           38 :       print_generic_expr (dump_file, result);
     634           38 :       fprintf (dump_file, ".\n");
     635              :     }
     636              : 
     637              :   /* Remove the old operation(s) that has single use.  */
     638        28707 :   gsi_for_def = gsi_for_stmt (arg0_def_stmt);
     639        28707 :   gsi_remove (&gsi_for_def, true);
     640        28707 :   release_defs (arg0_def_stmt);
     641              : 
     642        28707 :   if (arg1_def_stmt)
     643              :     {
     644         8358 :       gsi_for_def = gsi_for_stmt (arg1_def_stmt);
     645         8358 :       gsi_remove (&gsi_for_def, true);
     646         8358 :       release_defs (arg1_def_stmt);
     647              :     }
     648              : 
     649        28707 :   add_phi_arg (newphi, new_arg0, e0, narg0_loc);
     650        28707 :   add_phi_arg (newphi, new_arg1, e1, narg1_loc);
     651              : 
     652              :   /* Remove the original PHI stmt.  */
     653        28707 :   gsi = gsi_for_stmt (phi);
     654        28707 :   remove_phi_node (&gsi, false);
     655              : 
     656        28707 :   statistics_counter_event (cfun, "factored out operation", 1);
     657              : 
     658        28707 :   return true;
     659              : }
     660              : 
     661              : 
     662              : /* Return TRUE if SEQ/OP pair should be allowed during early phiopt.
     663              :    Currently this is to allow MIN/MAX and ABS/NEGATE and constants.  */
     664              : static bool
     665       182551 : phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
     666              : {
     667              :   /* Don't allow functions. */
     668       182551 :   if (!op.code.is_tree_code ())
     669              :     return false;
     670       182472 :   tree_code code = (tree_code)op.code;
     671              : 
     672              :   /* For non-empty sequence, only allow one statement
     673              :      a MIN/MAX and an original MIN/MAX.  */
     674       182472 :   if (!gimple_seq_empty_p (seq))
     675              :     {
     676       148155 :       if (code == MIN_EXPR || code == MAX_EXPR)
     677              :         {
     678       150157 :           if (!gimple_seq_singleton_p (seq))
     679              :             return false;
     680              : 
     681            3 :           gimple *stmt = gimple_seq_first_stmt (seq);
     682              :           /* Only allow assignments.  */
     683            3 :           if (!is_gimple_assign (stmt))
     684              :             return false;
     685            3 :           code = gimple_assign_rhs_code (stmt);
     686            3 :           return code == MIN_EXPR || code == MAX_EXPR;
     687              :         }
     688              :       return false;
     689              :     }
     690              : 
     691        34317 :   switch (code)
     692              :     {
     693              :       case MIN_EXPR:
     694              :       case MAX_EXPR:
     695              :       case ABS_EXPR:
     696              :       case ABSU_EXPR:
     697              :       case NEGATE_EXPR:
     698              :       case SSA_NAME:
     699              :         return true;
     700              :       case INTEGER_CST:
     701              :       case REAL_CST:
     702              :       case VECTOR_CST:
     703              :       case FIXED_CST:
     704              :         return true;
     705              :       default:
     706              :         return false;
     707              :     }
     708              : }
     709              : 
     710              : /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
     711              :    Return NULL if nothing can be simplified or the resulting simplified value
     712              :    with parts pushed if EARLY_P was true. Also rejects non allowed tree code
     713              :    if EARLY_P is set.
     714              :    Takes the comparison from COMP_STMT and two args, ARG0 and ARG1 and tries
     715              :    to simplify CMP ? ARG0 : ARG1.
     716              :    Also try to simplify (!CMP) ? ARG1 : ARG0 if the non-inverse failed.  */
     717              : static tree
     718       545081 : gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
     719              :                         tree arg0, tree arg1,
     720              :                         gimple_seq *seq)
     721              : {
     722       545081 :   gimple_seq seq1 = NULL;
     723       545081 :   enum tree_code comp_code = gimple_cond_code (comp_stmt);
     724       545081 :   location_t loc = gimple_location (comp_stmt);
     725       545081 :   tree cmp0 = gimple_cond_lhs (comp_stmt);
     726       545081 :   tree cmp1 = gimple_cond_rhs (comp_stmt);
     727              :   /* To handle special cases like floating point comparison, it is easier and
     728              :      less error-prone to build a tree and gimplify it on the fly though it is
     729              :      less efficient.
     730              :      Don't use fold_build2 here as that might create (bool)a instead of just
     731              :      "a != 0".  */
     732       545081 :   tree cond = build2_loc (loc, comp_code, boolean_type_node,
     733              :                           cmp0, cmp1);
     734              : 
     735       545081 :   if (dump_file && (dump_flags & TDF_FOLDING))
     736              :     {
     737            1 :       fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
     738            1 :       print_generic_expr (dump_file, cond);
     739            1 :       fprintf (dump_file, " ? ");
     740            1 :       print_generic_expr (dump_file, arg0);
     741            1 :       fprintf (dump_file, " : ");
     742            1 :       print_generic_expr (dump_file, arg1);
     743            1 :       fprintf (dump_file, "\n");
     744              :     }
     745              : 
     746       545081 :   gimple_match_op op (gimple_match_cond::UNCOND,
     747       545081 :                       COND_EXPR, type, cond, arg0, arg1);
     748              : 
     749       545081 :   if (op.resimplify (&seq1, follow_all_ssa_edges))
     750              :     {
     751       163112 :       bool allowed = !early_p || phiopt_early_allow (seq1, op);
     752       163112 :       tree result = maybe_push_res_to_seq (&op, &seq1);
     753       163112 :       if (dump_file && (dump_flags & TDF_FOLDING))
     754              :         {
     755            1 :           fprintf (dump_file, "\nphiopt match-simplify back:\n");
     756            1 :           if (seq1)
     757            0 :             print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
     758            1 :           fprintf (dump_file, "result: ");
     759            1 :           if (result)
     760            1 :             print_generic_expr (dump_file, result);
     761              :           else
     762            0 :             fprintf (dump_file, " (none)");
     763            1 :           fprintf (dump_file, "\n");
     764            1 :           if (!allowed)
     765            0 :             fprintf (dump_file, "rejected because early\n");
     766              :         }
     767              :       /* Early we want only to allow some generated tree codes. */
     768       163112 :       if (allowed && result)
     769              :         {
     770        86909 :           if (loc != UNKNOWN_LOCATION)
     771        86421 :             annotate_all_with_location (seq1, loc);
     772        86909 :           gimple_seq_add_seq_without_update (seq, seq1);
     773        86909 :           return result;
     774              :         }
     775              :     }
     776       458172 :   gimple_seq_discard (seq1);
     777       458172 :   seq1 = NULL;
     778              : 
     779              :   /* Try the inverted comparison, that is !COMP ? ARG1 : ARG0. */
     780       458172 :   comp_code = invert_tree_comparison (comp_code, HONOR_NANS (cmp0));
     781              : 
     782       458172 :   if (comp_code == ERROR_MARK)
     783              :     return NULL;
     784              : 
     785       440859 :   cond = build2_loc (loc,
     786              :                      comp_code, boolean_type_node,
     787              :                      cmp0, cmp1);
     788              : 
     789       440859 :   if (dump_file && (dump_flags & TDF_FOLDING))
     790              :     {
     791            0 :       fprintf (dump_file, "\nphiopt match-simplify trying:\n\t");
     792            0 :       print_generic_expr (dump_file, cond);
     793            0 :       fprintf (dump_file, " ? ");
     794            0 :       print_generic_expr (dump_file, arg1);
     795            0 :       fprintf (dump_file, " : ");
     796            0 :       print_generic_expr (dump_file, arg0);
     797            0 :       fprintf (dump_file, "\n");
     798              :     }
     799              : 
     800       440859 :   gimple_match_op op1 (gimple_match_cond::UNCOND,
     801       440859 :                        COND_EXPR, type, cond, arg1, arg0);
     802              : 
     803       440859 :   if (op1.resimplify (&seq1, follow_all_ssa_edges))
     804              :     {
     805        78808 :       bool allowed = !early_p || phiopt_early_allow (seq1, op1);
     806        78808 :       tree result = maybe_push_res_to_seq (&op1, &seq1);
     807        78808 :       if (dump_file && (dump_flags & TDF_FOLDING))
     808              :         {
     809            0 :           fprintf (dump_file, "\nphiopt match-simplify back:\n");
     810            0 :           if (seq1)
     811            0 :             print_gimple_seq (dump_file, seq1, 0, TDF_VOPS|TDF_MEMSYMS);
     812            0 :           fprintf (dump_file, "result: ");
     813            0 :           if (result)
     814            0 :             print_generic_expr (dump_file, result);
     815              :           else
     816            0 :             fprintf (dump_file, " (none)");
     817            0 :           fprintf (dump_file, "\n");
     818            0 :           if (!allowed)
     819            0 :             fprintf (dump_file, "rejected because early\n");
     820              :         }
     821              :       /* Early we want only to allow some generated tree codes. */
     822        78808 :       if (allowed && result)
     823              :         {
     824         4825 :           if (loc != UNKNOWN_LOCATION)
     825         4825 :             annotate_all_with_location (seq1, loc);
     826         4825 :           gimple_seq_add_seq_without_update (seq, seq1);
     827         4825 :           return result;
     828              :         }
     829              :     }
     830       436034 :   gimple_seq_discard (seq1);
     831              : 
     832       436034 :   return NULL;
     833              : }
     834              : 
     835              : /* one_feeding_comparison_into_p returns true if BB has one comparison
     836              :    statement and it sets STMT to that statement.  Note the comparison can
     837              :    be trapping too.  */
     838              : static bool
     839         1283 : one_feeding_comparison_into_p (basic_block bb,
     840              :                                gimple *phi,
     841              :                                gassign *&assign)
     842              : {
     843         1283 :   assign = nullptr;
     844         1283 :   gimple *stmt = nullptr;
     845              : 
     846         1283 :   if (empty_block_p (bb))
     847              :     return false;
     848              : 
     849         1265 :   if (!single_pred_p (bb))
     850              :     return false;
     851              : 
     852         1247 :   if (!gimple_seq_empty_p (phi_nodes (bb)))
     853              :     return false;
     854              : 
     855         1247 :   gimple_stmt_iterator gsi;
     856         1247 :   gsi = gsi_start_nondebug_after_labels_bb (bb);
     857         2496 :   while (!gsi_end_p (gsi))
     858              :     {
     859         2022 :       gimple *s = gsi_stmt (gsi);
     860         2022 :       gsi_next_nondebug (&gsi);
     861              :       /* Skip over Predict and nop statements. */
     862         2022 :       if (gimple_code (s) == GIMPLE_PREDICT
     863         2022 :           || gimple_code (s) == GIMPLE_NOP)
     864            2 :         continue;
     865              :       /* If there is more one statement return false. */
     866         2020 :       if (stmt)
     867              :         return false;
     868              :       stmt = s;
     869              :     }
     870              : 
     871          474 :   if (!stmt)
     872              :     return false;
     873              : 
     874          948 :   if (gimple_vuse (stmt))
     875              :     return false;
     876              : 
     877          468 :   gassign *a = dyn_cast<gassign*>(stmt);
     878          468 :   if (!a || TREE_CODE_CLASS (gimple_assign_rhs_code (a)) != tcc_comparison)
     879              :     return false;
     880              : 
     881          468 :   tree lhs = gimple_assign_lhs (a);
     882              : 
     883          468 :   gimple *use_stmt;
     884          468 :   use_operand_p use_p;
     885              :   /* Allow only a statement which feeds into the other stmt.  */
     886          468 :   if (!lhs || TREE_CODE (lhs) != SSA_NAME
     887          468 :       || !single_imm_use (lhs, &use_p, &use_stmt)
     888          936 :       || use_stmt != phi)
     889              :     return false;
     890              : 
     891              :   // Don't handle non-call exceptions
     892          468 :   if (stmt_could_throw_p (cfun, a))
     893              :     return false;
     894              : 
     895          462 :   assign = a;
     896          462 :   return true;
     897              : }
     898              : 
     899              : /* empty_bb_or_one_feeding_into_p returns true if bb was empty basic block
     900              :    or it has one cheap preparation statement that feeds into the PHI
     901              :    statement and it sets STMT to that statement. */
     902              : static bool
     903       888987 : empty_bb_or_one_feeding_into_p (basic_block bb,
     904              :                                 gimple *phi,
     905              :                                 gimple *&stmt)
     906              : {
     907       888987 :   stmt = nullptr;
     908       888987 :   gimple *stmt_to_move = nullptr;
     909       888987 :   tree lhs;
     910              : 
     911       888987 :   if (empty_block_p (bb))
     912              :     return true;
     913              : 
     914       467860 :   if (!single_pred_p (bb))
     915              :     return false;
     916              : 
     917              :   /* The middle bb cannot have phi nodes as we don't
     918              :      move those assignments yet. */
     919       454237 :   if (!gimple_seq_empty_p (phi_nodes (bb)))
     920              :     return false;
     921              : 
     922       454217 :   gimple_stmt_iterator gsi;
     923              : 
     924       454217 :   gsi = gsi_start_nondebug_after_labels_bb (bb);
     925       911706 :   while (!gsi_end_p (gsi))
     926              :     {
     927       673242 :       gimple *s = gsi_stmt (gsi);
     928       673242 :       gsi_next_nondebug (&gsi);
     929              :       /* Skip over Predict and nop statements. */
     930       673242 :       if (gimple_code (s) == GIMPLE_PREDICT
     931       673242 :           || gimple_code (s) == GIMPLE_NOP)
     932         3272 :         continue;
     933              :       /* If there is more one statement return false. */
     934       669970 :       if (stmt_to_move)
     935              :         return false;
     936              :       stmt_to_move = s;
     937              :     }
     938              : 
     939              :   /* The only statement here was a Predict or a nop statement
     940              :      so return true. */
     941       238464 :   if (!stmt_to_move)
     942              :     return true;
     943              : 
     944       476928 :   if (gimple_vuse (stmt_to_move))
     945              :     return false;
     946              : 
     947       166841 :   if (gimple_could_trap_p (stmt_to_move)
     948       166841 :       || gimple_has_side_effects (stmt_to_move))
     949              :     return false;
     950              : 
     951       161276 :   ssa_op_iter it;
     952       161276 :   tree use;
     953       353076 :   FOR_EACH_SSA_TREE_OPERAND (use, stmt_to_move, it, SSA_OP_USE)
     954       192467 :     if (ssa_name_maybe_undef_p (use))
     955              :       return false;
     956              : 
     957              :   /* Allow assignments but allow some builtin/internal calls.
     958              :      As const calls don't match any of the above, yet they could
     959              :      still have some side-effects - they could contain
     960              :      gimple_could_trap_p statements, like floating point
     961              :      exceptions or integer division by zero.  See PR70586.
     962              :      FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
     963              :      should handle this.
     964              :      Allow some known builtin/internal calls that are known not to
     965              :      trap: logical functions (e.g. bswap and bit counting). */
     966       160609 :   if (!is_gimple_assign (stmt_to_move))
     967              :     {
     968         6082 :       if (!is_gimple_call (stmt_to_move))
     969              :         return false;
     970         5835 :       combined_fn cfn = gimple_call_combined_fn (stmt_to_move);
     971         5835 :       switch (cfn)
     972              :         {
     973              :         default:
     974              :           return false;
     975         4866 :         CASE_CFN_BSWAP:
     976         4866 :         CASE_CFN_BITREVERSE:
     977         4866 :         CASE_CFN_FFS:
     978         4866 :         CASE_CFN_PARITY:
     979         4866 :         CASE_CFN_POPCOUNT:
     980         4866 :         CASE_CFN_CLZ:
     981         4866 :         CASE_CFN_CTZ:
     982         4866 :         case CFN_BUILT_IN_CLRSB:
     983         4866 :         case CFN_BUILT_IN_CLRSBL:
     984         4866 :         case CFN_BUILT_IN_CLRSBLL:
     985         4866 :           lhs = gimple_call_lhs (stmt_to_move);
     986         4866 :           break;
     987              :         }
     988              :     }
     989              :   else
     990       154527 :     lhs = gimple_assign_lhs (stmt_to_move);
     991              : 
     992       159393 :   gimple *use_stmt;
     993       159393 :   use_operand_p use_p;
     994              : 
     995              :   /* Allow only a statement which feeds into the other stmt.  */
     996       159393 :   if (!lhs || TREE_CODE (lhs) != SSA_NAME
     997       159393 :       || !single_imm_use (lhs, &use_p, &use_stmt)
     998       318781 :       || use_stmt != phi)
     999              :     return false;
    1000              : 
    1001       159388 :   stmt = stmt_to_move;
    1002       159388 :   return true;
    1003              : }
    1004              : 
    1005              : /* Move STMT to before GSI and insert its defining
    1006              :    name into INSERTED_EXPRS bitmap.
    1007              :    Also rewrite its if it might be undefined when unconditionalized.  */
    1008              : static void
    1009       191528 : move_stmt (gimple *stmt, gimple_stmt_iterator *gsi, auto_bitmap &inserted_exprs)
    1010              : {
    1011       191528 :   if (!stmt)
    1012       185447 :     return;
    1013         6081 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1014              :     {
    1015            9 :       fprintf (dump_file, "statement un-sinked:\n");
    1016            9 :       print_gimple_stmt (dump_file, stmt, 0,
    1017              :                          TDF_VOPS|TDF_MEMSYMS);
    1018              :     }
    1019              : 
    1020         6081 :   tree name = gimple_get_lhs (stmt);
    1021              :   // Mark the name to be renamed if there is one.
    1022         6081 :   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
    1023         6081 :   gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt);
    1024         6081 :   gsi_move_before (&gsi1, gsi, GSI_NEW_STMT);
    1025         6081 :   reset_flow_sensitive_info (name);
    1026              : 
    1027              :   /* Rewrite some code which might be undefined when
    1028              :      unconditionalized. */
    1029         6081 :   if (gimple_needing_rewrite_undefined (stmt))
    1030         1164 :     rewrite_to_defined_unconditional (gsi);
    1031              : }
    1032              : 
    1033              : /* RAII style class to temporarily remove flow sensitive
    1034              :    from ssa names defined by a gimple statement.  */
    1035              : class auto_flow_sensitive
    1036              : {
    1037              : public:
    1038              :   auto_flow_sensitive (gimple *s);
    1039              :   ~auto_flow_sensitive ();
    1040              : private:
    1041              :   auto_vec<std::pair<tree, flow_sensitive_info_storage>, 2> stack;
    1042              : };
    1043              : 
    1044              : /* Constructor for auto_flow_sensitive. Saves
    1045              :    off the ssa names' flow sensitive information
    1046              :    that was defined by gimple statement S and
    1047              :    resets it to be non-flow based ones. */
    1048              : 
    1049      1090162 : auto_flow_sensitive::auto_flow_sensitive (gimple *s)
    1050              : {
    1051      1090162 :   if (!s)
    1052       939520 :     return;
    1053       150642 :   ssa_op_iter it;
    1054       150642 :   tree def;
    1055       301284 :   FOR_EACH_SSA_TREE_OPERAND (def, s, it, SSA_OP_DEF)
    1056              :     {
    1057       150642 :       flow_sensitive_info_storage storage;
    1058       150642 :       storage.save_and_clear (def);
    1059       150642 :       stack.safe_push (std::make_pair (def, storage));
    1060              :     }
    1061              : }
    1062              : 
    1063              : /* Deconstructor, restores the flow sensitive information
    1064              :    for the SSA names that had been saved off.  */
    1065              : 
    1066      1090162 : auto_flow_sensitive::~auto_flow_sensitive ()
    1067              : {
    1068      3421128 :   for (auto p : stack)
    1069       150642 :     p.second.restore (p.first);
    1070      1090162 : }
    1071              : 
    1072              : /* Returns true if BB contains an user provided predictor
    1073              :    (PRED_HOT_LABEL/PRED_COLD_LABEL).  */
    1074              : 
    1075              : static bool
    1076         6705 : contains_hot_cold_predict (basic_block bb)
    1077              : {
    1078         6705 :   gimple_stmt_iterator gsi;
    1079         6705 :   gsi = gsi_start_nondebug_after_labels_bb (bb);
    1080         9277 :   for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
    1081              :     {
    1082         2573 :       gimple *s = gsi_stmt (gsi);
    1083         2573 :       if (gimple_code (s) != GIMPLE_PREDICT)
    1084            1 :         continue;
    1085         2572 :       auto predict = gimple_predict_predictor (s);
    1086         2572 :       if (predict == PRED_HOT_LABEL
    1087         2572 :           || predict == PRED_COLD_LABEL)
    1088              :         return true;
    1089              :     }
    1090              :   return false;
    1091              : }
    1092              : 
    1093              : /*  The function match_simplify_replacement does the main work of doing the
    1094              :     replacement using match and simplify.  Return true if the replacement is done.
    1095              :     Otherwise return false.
    1096              :     BB is the basic block where the replacement is going to be done on.  ARG0
    1097              :     is argument 0 from PHI.  Likewise for ARG1.  */
    1098              : 
    1099              : static bool
    1100       858172 : match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
    1101              :                             basic_block middle_bb_alt,
    1102              :                             edge e0, edge e1, gphi *phi,
    1103              :                             tree arg0, tree arg1, bool early_p,
    1104              :                             bool threeway_p)
    1105              : {
    1106       858172 :   gimple *stmt;
    1107       858172 :   gimple_stmt_iterator gsi;
    1108       858172 :   edge true_edge, false_edge;
    1109       858172 :   gimple_seq seq = NULL;
    1110       858172 :   tree result;
    1111       858172 :   gimple *stmt_to_move = NULL;
    1112       858172 :   gimple *stmt_to_move_alt = NULL;
    1113       858172 :   tree arg_true, arg_false;
    1114              : 
    1115              :   /* Special case A ? B : B as this will always simplify to B. */
    1116       858172 :   if (operand_equal_for_phi_arg_p (arg0, arg1))
    1117              :     return false;
    1118              : 
    1119              :   /* If the basic block only has a cheap preparation statement,
    1120              :      allow it and move it once the transformation is done. */
    1121       858172 :   if (!empty_bb_or_one_feeding_into_p (middle_bb, phi, stmt_to_move))
    1122              :     return false;
    1123              : 
    1124       563372 :   if (threeway_p
    1125       563372 :       && middle_bb != middle_bb_alt
    1126       563372 :       && !empty_bb_or_one_feeding_into_p (middle_bb_alt, phi,
    1127              :                                           stmt_to_move_alt))
    1128              :     return false;
    1129              : 
    1130              :   /* Do not make conditional undefs unconditional.  */
    1131       549700 :   if ((TREE_CODE (arg0) == SSA_NAME
    1132       280296 :        && ssa_name_maybe_undef_p (arg0))
    1133       829673 :       || (TREE_CODE (arg1) == SSA_NAME
    1134       243163 :           && ssa_name_maybe_undef_p (arg1)))
    1135              :     return false;
    1136              : 
    1137              :     /* At this point we know we have a GIMPLE_COND with two successors.
    1138              :      One successor is BB, the other successor is an empty block which
    1139              :      falls through into BB.
    1140              : 
    1141              :      There is a single PHI node at the join point (BB).
    1142              : 
    1143              :      So, given the condition COND, and the two PHI arguments, match and simplify
    1144              :      can happen on (COND) ? arg0 : arg1. */
    1145              : 
    1146       545081 :   stmt = last_nondebug_stmt (cond_bb);
    1147              : 
    1148              :   /* We need to know which is the true edge and which is the false
    1149              :      edge so that we know when to invert the condition below.  */
    1150       545081 :   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
    1151              : 
    1152              :   /* Forward the edges over the middle basic block.  */
    1153       545081 :   if (true_edge->dest == middle_bb)
    1154       354138 :     true_edge = EDGE_SUCC (true_edge->dest, 0);
    1155       545081 :   if (false_edge->dest == middle_bb)
    1156       190943 :     false_edge = EDGE_SUCC (false_edge->dest, 0);
    1157              : 
    1158              :   /* When THREEWAY_P then e1 will point to the edge of the final transition
    1159              :      from middle-bb to end.  */
    1160       545081 :   if (true_edge == e0)
    1161              :     {
    1162       354138 :       if (!threeway_p)
    1163       337591 :         gcc_assert (false_edge == e1);
    1164              :       arg_true = arg0;
    1165              :       arg_false = arg1;
    1166              :     }
    1167              :   else
    1168              :     {
    1169       190943 :       gcc_assert (false_edge == e0);
    1170       190943 :       if (!threeway_p)
    1171       190469 :         gcc_assert (true_edge == e1);
    1172              :       arg_true = arg1;
    1173              :       arg_false = arg0;
    1174              :     }
    1175              : 
    1176       545081 :   tree type = TREE_TYPE (gimple_phi_result (phi));
    1177       545081 :   {
    1178       545081 :     auto_flow_sensitive s1(stmt_to_move);
    1179       545081 :     auto_flow_sensitive s_alt(stmt_to_move_alt);
    1180              : 
    1181       545081 :     result = gimple_simplify_phiopt (early_p, type, stmt,
    1182              :                                      arg_true, arg_false,
    1183              :                                     &seq);
    1184       545081 :   }
    1185              : 
    1186              :   /* For early phiopt, we don't want to lose user generated predictors
    1187              :      if the phiopt is converting `if (a)` into `a` as that might
    1188              :      be jump threaded later on so we want to keep around the
    1189              :      predictors.  */
    1190       545081 :   if (early_p && result && TREE_CODE (result) == SSA_NAME)
    1191              :     {
    1192        32382 :       bool check_it = false;
    1193        32382 :       tree cmp0 = gimple_cond_lhs (stmt);
    1194        32382 :       tree cmp1 = gimple_cond_rhs (stmt);
    1195        32382 :       if (result == cmp0 || result == cmp1)
    1196              :         check_it = true;
    1197        26065 :       else if (gimple_seq_singleton_p (seq))
    1198              :         {
    1199        25900 :           gimple *stmt = gimple_seq_first_stmt (seq);
    1200        25900 :           if (is_gimple_assign (stmt)
    1201        25900 :               && result == gimple_assign_lhs (stmt)
    1202        51800 :               && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
    1203              :                    == tcc_comparison)
    1204              :             check_it = true;
    1205              :         }
    1206              :       if (!check_it)
    1207              :         ;
    1208         6317 :       else if (contains_hot_cold_predict (middle_bb))
    1209              :         return false;
    1210         6316 :       else if (threeway_p
    1211              :                && middle_bb != middle_bb_alt
    1212         6316 :                && contains_hot_cold_predict (middle_bb_alt))
    1213              :         return false;
    1214              :     }
    1215              : 
    1216       545065 :   if (!result)
    1217              :     {
    1218              :       /* If we don't get back a MIN/MAX_EXPR still make sure the expression
    1219              :          stays in a form to be recognized by ISA that map to IEEE x > y ? x : y
    1220              :          semantics (that's not IEEE max semantics).  */
    1221       453347 :       if (!HONOR_NANS (type) && !HONOR_SIGNED_ZEROS (type))
    1222              :         return false;
    1223        17376 :       if (stmt_to_move || stmt_to_move_alt)
    1224              :         return false;
    1225        14399 :       tree_code cmp = gimple_cond_code (stmt);
    1226        14399 :       if (cmp != LT_EXPR && cmp != LE_EXPR
    1227        14399 :           && cmp != GT_EXPR && cmp != GE_EXPR)
    1228              :         return false;
    1229         6986 :       tree lhs = gimple_cond_lhs (stmt);
    1230         6986 :       tree rhs = gimple_cond_rhs (stmt);
    1231              :       /* `lhs CMP rhs ? lhs : rhs` or `lhs CMP rhs ? rhs : lhs`
    1232              :          are only acceptable case here.  */
    1233         6986 :       if ((!operand_equal_for_phi_arg_p (lhs, arg_false)
    1234         2691 :            || !operand_equal_for_phi_arg_p (rhs, arg_true))
    1235         7065 :           && (!operand_equal_for_phi_arg_p (rhs, arg_false)
    1236         1581 :                || !operand_equal_for_phi_arg_p (lhs, arg_true)))
    1237              :         return false;
    1238         4031 :       seq = nullptr;
    1239         4031 :       result = gimple_build (&seq, cmp, boolean_type_node, lhs, rhs);
    1240         4031 :       result = gimple_build (&seq, COND_EXPR, type, result,
    1241              :                              arg_true, arg_false);
    1242         4031 :       statistics_counter_event (cfun, "Non-IEEE FP MIN/MAX PHI replacement",
    1243              :                                 1);
    1244              :     }
    1245        95764 :   if (dump_file && (dump_flags & TDF_FOLDING))
    1246            1 :     fprintf (dump_file, "accepted the phiopt match-simplify.\n");
    1247              : 
    1248        95764 :   auto_bitmap exprs_maybe_dce;
    1249              : 
    1250              :   /* Mark the cond statements' lhs/rhs as maybe dce.  */
    1251        95764 :   if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
    1252        95764 :       && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_lhs (stmt)))
    1253        90154 :     bitmap_set_bit (exprs_maybe_dce,
    1254        90154 :                     SSA_NAME_VERSION (gimple_cond_lhs (stmt)));
    1255        95764 :   if (TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME
    1256        95764 :       && !SSA_NAME_IS_DEFAULT_DEF (gimple_cond_rhs (stmt)))
    1257        28171 :     bitmap_set_bit (exprs_maybe_dce,
    1258        28171 :                     SSA_NAME_VERSION (gimple_cond_rhs (stmt)));
    1259        95764 :   if (TREE_CODE (arg_true) == SSA_NAME
    1260        95764 :       && !SSA_NAME_IS_DEFAULT_DEF (arg_true))
    1261        22279 :     bitmap_set_bit (exprs_maybe_dce, SSA_NAME_VERSION (arg_true));
    1262        95764 :   if (TREE_CODE (arg_false) == SSA_NAME
    1263        95764 :       && !SSA_NAME_IS_DEFAULT_DEF (arg_false))
    1264        35184 :     bitmap_set_bit (exprs_maybe_dce, SSA_NAME_VERSION (arg_false));
    1265              : 
    1266        95764 :   gsi = gsi_last_bb (cond_bb);
    1267              :   /* Insert the sequence generated from gimple_simplify_phiopt.  */
    1268        95764 :   if (seq)
    1269              :     {
    1270              :       // Mark the lhs of the new statements maybe for dce
    1271        86983 :       mark_lhs_in_seq_for_dce (exprs_maybe_dce, seq);
    1272        86983 :       gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
    1273              :     }
    1274              : 
    1275              :   /* If there was a statement to move, move it to right before
    1276              :      the original conditional.  */
    1277        95764 :   move_stmt (stmt_to_move, &gsi, exprs_maybe_dce);
    1278        95764 :   move_stmt (stmt_to_move_alt, &gsi, exprs_maybe_dce);
    1279              : 
    1280        95764 :   replace_phi_edge_with_variable (cond_bb, e1, phi, result, exprs_maybe_dce);
    1281              : 
    1282              :   /* Add Statistic here even though replace_phi_edge_with_variable already
    1283              :      does it as we want to be able to count when match-simplify happens vs
    1284              :      the others.  */
    1285        95764 :   statistics_counter_event (cfun, "match-simplify PHI replacement", 1);
    1286              : 
    1287              :   /* Note that we optimized this PHI.  */
    1288        95764 :   return true;
    1289        95764 : }
    1290              : 
    1291              : /*  The function comparison_combine tries to handle cases like:
    1292              :     if (a CMP0 b)
    1293              :       d = a CMP1 b;
    1294              :     PHI<d, [0,1]>
    1295              :     This has to be seperately as `a CMP1 b` might be trapping and
    1296              :     match_simplify_replacement does not handle trapping statements.
    1297              :     Returns true if a replacement happens.  */
    1298              : 
    1299              : static bool
    1300       762408 : comparison_combine (basic_block cond_bb, basic_block middle_bb,
    1301              :                     basic_block middle_bb_alt,
    1302              :                     edge e0, edge e1, gphi *phi,
    1303              :                     tree arg0, tree arg1, bool threeway_p)
    1304              : {
    1305       762408 :   gcond *stmt;
    1306       762408 :   gimple_stmt_iterator gsi;
    1307       762408 :   edge true_edge, false_edge;
    1308       762408 :   tree arg_true, arg_false;
    1309              : 
    1310       762408 :   if (!types_compatible_p (boolean_type_node, TREE_TYPE (arg0)))
    1311              :     return false;
    1312              : 
    1313              :   /* Do not make conditional undefs unconditional.  */
    1314       111601 :   if ((TREE_CODE (arg0) == SSA_NAME
    1315        79305 :        && ssa_name_maybe_undef_p (arg0))
    1316       190906 :       || (TREE_CODE (arg1) == SSA_NAME
    1317        12184 :           && ssa_name_maybe_undef_p (arg1)))
    1318              :     return false;
    1319              : 
    1320       111582 :   stmt = as_a<gcond*>(last_nondebug_stmt (cond_bb));
    1321              : 
    1322              :   // Handle only floating point types as they only trap.
    1323              :   // The match and simplify will handle the non-trapping case.
    1324       111582 :   if (!FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))
    1325              :     return false;
    1326              : 
    1327              :   /* Needs to be PHI<[1,0],arg1> PHI<arg0,[1,0]>.  */
    1328         5100 :   if (((!integer_onep (arg0) && !integer_zerop (arg0))
    1329         1234 :         || TREE_CODE (arg1) != SSA_NAME)
    1330         5240 :       && ((!integer_onep (arg1) && !integer_zerop (arg1))
    1331         2469 :            || TREE_CODE (arg0) != SSA_NAME))
    1332              :     return false;
    1333              : 
    1334         1271 :   gassign *other_cmp = nullptr;
    1335         1271 :   if (!one_feeding_comparison_into_p (middle_bb, phi, other_cmp))
    1336              :     {
    1337          811 :       if (!threeway_p || middle_bb == middle_bb_alt)
    1338              :         return false;
    1339           12 :       if (!empty_block_p (middle_bb))
    1340              :         return false;
    1341           12 :       if (!one_feeding_comparison_into_p (middle_bb_alt, phi, other_cmp))
    1342              :         return false;
    1343              :     }
    1344          460 :   else if (threeway_p
    1345          460 :            && middle_bb != middle_bb_alt
    1346          460 :            && !empty_block_p (middle_bb_alt))
    1347              :     return false;
    1348              :  
    1349              :   /* We need to know which is the true edge and which is the false
    1350              :      edge so that we know when to invert the condition below.  */
    1351          462 :   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
    1352              : 
    1353              :   /* Forward the edges over the middle basic block.  */
    1354          462 :   if (true_edge->dest == middle_bb)
    1355          340 :     true_edge = EDGE_SUCC (true_edge->dest, 0);
    1356          462 :   if (false_edge->dest == middle_bb)
    1357          122 :     false_edge = EDGE_SUCC (false_edge->dest, 0);
    1358              :   /* When THREEWAY_P then e1 will point to the edge of the final transition
    1359              :      from middle-bb to end.  */
    1360          462 :   if (true_edge == e0)
    1361              :     {
    1362          340 :       if (!threeway_p)
    1363          338 :         gcc_assert (false_edge == e1);
    1364              :       arg_true = arg0;
    1365              :       arg_false = arg1;
    1366              :     }
    1367              :   else
    1368              :     {
    1369          122 :       gcc_assert (false_edge == e0);
    1370          122 :       if (!threeway_p)
    1371          122 :         gcc_assert (true_edge == e1);
    1372              :       arg_true = arg1;
    1373              :       arg_false = arg0;
    1374              :     }
    1375          462 :   if (TREE_CODE (arg_true) == SSA_NAME
    1376          462 :       && arg_true != gimple_assign_lhs (other_cmp))
    1377              :     return false;
    1378          462 :   if (TREE_CODE (arg_false) == SSA_NAME
    1379          462 :       && arg_false != gimple_assign_lhs (other_cmp))
    1380              :     return false;
    1381              : 
    1382          462 :   tree larg = gimple_cond_lhs (stmt);
    1383          462 :   tree rarg = gimple_cond_rhs (stmt);
    1384          462 :   if (!operand_equal_p (larg, gimple_assign_rhs1 (other_cmp))
    1385          785 :       || !operand_equal_p (rarg, gimple_assign_rhs2 (other_cmp)))
    1386              :     return false;
    1387              : 
    1388          171 :   tree_code logical;
    1389              :   // a CMP0 b ? 1 : a CMP1 b -> `a CMP0 b || a CMP1 b`
    1390              :   // a CMP0 b ? a CMP1 b : 1 -> `!(a CMP0 b) || a CMP1 b`
    1391              :   
    1392              :   // a CMP0 b ? a CMP1 b : 0 -> `a CMP0 b && a CMP1 b`
    1393              :   // a CMP0 b ? 0 : a CMP1 b -> `!(a CMP0 b) && a CMP1 b`
    1394          171 :   if (integer_onep (arg_true) || integer_onep (arg_false))
    1395              :     logical = TRUTH_ORIF_EXPR;
    1396              :   else
    1397              :     logical = TRUTH_ANDIF_EXPR;
    1398          171 :   tree_code outer_code = gimple_cond_code (stmt);
    1399          171 :   tree_code inner_code = gimple_assign_rhs_code (other_cmp);
    1400              :   // Invert the outter if needed.
    1401          171 :   if (integer_onep (arg_false) || integer_zerop (arg_true))
    1402              :     {
    1403            0 :       outer_code = invert_tree_comparison (outer_code,
    1404              :                                            HONOR_NANS (larg));
    1405              :       // In theory could handle it as !((a CMP0 b) LOGICAL' !(a CMP1 b))
    1406              :       // Most likely the outer comparison will be EQ/NE which is invertable.
    1407            0 :       if (outer_code == ERROR_MARK)
    1408              :         return false;
    1409              :     }
    1410          171 :   tree result;
    1411          171 :   tree_code newcmp_code;
    1412          171 :   newcmp_code = combine_comparisons (logical, outer_code, inner_code,
    1413              :                                      boolean_type_node, boolean_type_node,
    1414              :                                      HONOR_NANS (larg), &result);
    1415          171 :   if (newcmp_code == ERROR_MARK)
    1416              :     return false;
    1417           16 :   gimple_seq seq = nullptr;
    1418           16 :   if (newcmp_code != INTEGER_CST)
    1419           16 :    result = gimple_build (&seq, newcmp_code, boolean_type_node,
    1420              :                           larg, rarg);
    1421           16 :   gsi = gsi_last_bb (cond_bb);
    1422           16 :   gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
    1423           16 :   replace_phi_edge_with_variable (cond_bb, e1, phi, result);
    1424           16 :   return true;
    1425              : }
    1426              : 
    1427              : /* Update *ARG which is defined in STMT so that it contains the
    1428              :    computed value if that seems profitable.  Return true if the
    1429              :    statement is made dead by that rewriting.  */
    1430              : 
    1431              : static bool
    1432       337375 : jump_function_from_stmt (tree *arg, gimple *stmt)
    1433              : {
    1434       337375 :   enum tree_code code = gimple_assign_rhs_code (stmt);
    1435       337375 :   if (code == ADDR_EXPR)
    1436              :     {
    1437              :       /* For arg = &p->i transform it to p, if possible.  */
    1438         4973 :       tree rhs1 = gimple_assign_rhs1 (stmt);
    1439         4973 :       poly_int64 offset;
    1440         4973 :       tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs1, 0),
    1441              :                                                 &offset);
    1442         4973 :       if (tem
    1443         4887 :           && TREE_CODE (tem) == MEM_REF
    1444         9860 :           && known_eq (mem_ref_offset (tem) + offset, 0))
    1445              :         {
    1446         2105 :           *arg = TREE_OPERAND (tem, 0);
    1447         2105 :           return true;
    1448              :         }
    1449              :     }
    1450              :   /* TODO: Much like IPA-CP jump-functions we want to handle constant
    1451              :      additions symbolically here, and we'd need to update the comparison
    1452              :      code that compares the arg + cst tuples in our caller.  For now the
    1453              :      code above exactly handles the VEC_BASE pattern from vec.h.  */
    1454              :   return false;
    1455              : }
    1456              : 
    1457              : /* RHS is a source argument in a BIT_AND_EXPR or BIT_IOR_EXPR which feeds
    1458              :    a conditional of the form SSA_NAME NE 0.
    1459              : 
    1460              :    If RHS is fed by a simple EQ_EXPR or NE_EXPR comparison of two values,
    1461              :    see if the two input values of the comparison match arg0 and arg1.
    1462              : 
    1463              :    If so update *code and return TRUE.  Otherwise return FALSE.  */
    1464              : 
    1465              : static bool
    1466       166114 : rhs_is_fed_for_value_replacement (const_tree arg0, const_tree arg1,
    1467              :                                   enum tree_code *code, const_tree rhs,
    1468              :                                   enum tree_code bit_expression_code)
    1469              : {
    1470              :   /* Obviously if RHS is not an SSA_NAME, we can't look at the defining
    1471              :      statement.  */
    1472       166114 :   if (TREE_CODE (rhs) == SSA_NAME)
    1473              :     {
    1474       130077 :       gimple *def1 = SSA_NAME_DEF_STMT (rhs);
    1475              : 
    1476              :       /* Verify the defining statement has an EQ_EXPR or NE_EXPR on the RHS.  */
    1477       130077 :       if (is_gimple_assign (def1)
    1478       130077 :           && ((bit_expression_code == BIT_AND_EXPR
    1479        80651 :                && gimple_assign_rhs_code (def1) == EQ_EXPR)
    1480        96497 :               || (bit_expression_code == BIT_IOR_EXPR
    1481        39247 :                   && gimple_assign_rhs_code (def1) == NE_EXPR)))
    1482              :         {
    1483              :           /* Finally verify the source operands of the EQ_EXPR or NE_EXPR
    1484              :              are equal to arg0 and arg1.  */
    1485        28777 :           tree op0 = gimple_assign_rhs1 (def1);
    1486        28777 :           tree op1 = gimple_assign_rhs2 (def1);
    1487        28777 :           if ((operand_equal_for_phi_arg_p (arg0, op0)
    1488          718 :                && operand_equal_for_phi_arg_p (arg1, op1))
    1489        29392 :               || (operand_equal_for_phi_arg_p (arg0, op1)
    1490          661 :                && operand_equal_for_phi_arg_p (arg1, op0)))
    1491              :             {
    1492              :               /* We will perform the optimization.  */
    1493          533 :               *code = gimple_assign_rhs_code (def1);
    1494          533 :               return true;
    1495              :             }
    1496              :         }
    1497              :     }
    1498              :   return false;
    1499              : }
    1500              : 
    1501              : /* Return TRUE if arg0/arg1 are equal to the rhs/lhs or lhs/rhs of COND.
    1502              : 
    1503              :    Also return TRUE if arg0/arg1 are equal to the source arguments of an
    1504              :    EQ comparison feeding a BIT_AND_EXPR, or NE comparison feeding a
    1505              :    BIT_IOR_EXPR which feeds COND.
    1506              : 
    1507              :    Return FALSE otherwise.  */
    1508              : 
    1509              : static bool
    1510       681700 : operand_equal_for_value_replacement (const_tree arg0, const_tree arg1,
    1511              :                                      enum tree_code *code, gimple *cond)
    1512              : {
    1513       681700 :   gimple *def;
    1514       681700 :   tree lhs = gimple_cond_lhs (cond);
    1515       681700 :   tree rhs = gimple_cond_rhs (cond);
    1516              : 
    1517       681700 :   if ((operand_equal_for_phi_arg_p (arg0, lhs)
    1518        27934 :        && operand_equal_for_phi_arg_p (arg1, rhs))
    1519       700232 :       || (operand_equal_for_phi_arg_p (arg1, lhs)
    1520        48769 :           && operand_equal_for_phi_arg_p (arg0, rhs)))
    1521              :     return true;
    1522              : 
    1523              :   /* Now handle more complex case where we have an EQ comparison
    1524              :      feeding a BIT_AND_EXPR, or a NE comparison feeding a BIT_IOR_EXPR,
    1525              :      which then feeds into COND.
    1526              : 
    1527              :      First verify that COND is of the form SSA_NAME NE 0.  */
    1528       391798 :   if (*code != NE_EXPR || !integer_zerop (rhs)
    1529       953776 :       || TREE_CODE (lhs) != SSA_NAME)
    1530              :     return false;
    1531              : 
    1532              :   /* Now ensure that SSA_NAME is set by a BIT_AND_EXPR or BIT_OR_EXPR.  */
    1533       285066 :   def = SSA_NAME_DEF_STMT (lhs);
    1534       285066 :   if (!is_gimple_assign (def)
    1535       285066 :       || (gimple_assign_rhs_code (def) != BIT_AND_EXPR
    1536       139300 :           && gimple_assign_rhs_code (def) != BIT_IOR_EXPR))
    1537              :     return false;
    1538              : 
    1539              :   /* Now verify arg0/arg1 correspond to the source arguments of an EQ
    1540              :      comparison feeding the BIT_AND_EXPR or a NE comparison feeding the
    1541              :      BIT_IOR_EXPR.  */
    1542              : 
    1543        83249 :   tree tmp = gimple_assign_rhs1 (def);
    1544        83249 :   if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
    1545              :                                         gimple_assign_rhs_code (def)))
    1546              :     return true;
    1547              : 
    1548        82865 :   tmp = gimple_assign_rhs2 (def);
    1549        82865 :   if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp,
    1550              :                                         gimple_assign_rhs_code (def)))
    1551              :     return true;
    1552              : 
    1553              :   return false;
    1554              : }
    1555              : 
    1556              : /* Returns true if ARG is a neutral element for operation CODE
    1557              :    on the RIGHT side.  */
    1558              : 
    1559              : static bool
    1560         1097 : neutral_element_p (tree_code code, tree arg, bool right)
    1561              : {
    1562         1097 :   switch (code)
    1563              :     {
    1564           33 :     case PLUS_EXPR:
    1565           33 :     case BIT_IOR_EXPR:
    1566           33 :     case BIT_XOR_EXPR:
    1567           33 :       return integer_zerop (arg);
    1568              : 
    1569          198 :     case LROTATE_EXPR:
    1570          198 :     case RROTATE_EXPR:
    1571          198 :     case LSHIFT_EXPR:
    1572          198 :     case RSHIFT_EXPR:
    1573          198 :     case MINUS_EXPR:
    1574          198 :     case POINTER_PLUS_EXPR:
    1575          198 :       return right && integer_zerop (arg);
    1576              : 
    1577          691 :     case MULT_EXPR:
    1578          691 :       return integer_onep (arg);
    1579              : 
    1580           31 :     case TRUNC_DIV_EXPR:
    1581           31 :     case CEIL_DIV_EXPR:
    1582           31 :     case FLOOR_DIV_EXPR:
    1583           31 :     case ROUND_DIV_EXPR:
    1584           31 :     case EXACT_DIV_EXPR:
    1585           31 :       return right && integer_onep (arg);
    1586              : 
    1587            0 :     case BIT_AND_EXPR:
    1588            0 :       return integer_all_onesp (arg);
    1589              : 
    1590              :     default:
    1591              :       return false;
    1592              :     }
    1593              : }
    1594              : 
    1595              : /* Returns true if ARG is an absorbing element for operation CODE.  */
    1596              : 
    1597              : static bool
    1598          869 : absorbing_element_p (tree_code code, tree arg, bool right, tree rval)
    1599              : {
    1600          869 :   switch (code)
    1601              :     {
    1602           18 :     case BIT_IOR_EXPR:
    1603           18 :       return integer_all_onesp (arg);
    1604              : 
    1605           47 :     case MULT_EXPR:
    1606           47 :     case BIT_AND_EXPR:
    1607           47 :       return integer_zerop (arg);
    1608              : 
    1609            3 :     case LSHIFT_EXPR:
    1610            3 :     case RSHIFT_EXPR:
    1611            3 :     case LROTATE_EXPR:
    1612            3 :     case RROTATE_EXPR:
    1613            3 :       return !right && integer_zerop (arg);
    1614              : 
    1615          166 :     case TRUNC_DIV_EXPR:
    1616          166 :     case CEIL_DIV_EXPR:
    1617          166 :     case FLOOR_DIV_EXPR:
    1618          166 :     case ROUND_DIV_EXPR:
    1619          166 :     case EXACT_DIV_EXPR:
    1620          166 :     case TRUNC_MOD_EXPR:
    1621          166 :     case CEIL_MOD_EXPR:
    1622          166 :     case FLOOR_MOD_EXPR:
    1623          166 :     case ROUND_MOD_EXPR:
    1624          166 :       return (!right
    1625            8 :               && integer_zerop (arg)
    1626          174 :               && tree_single_nonzero_p (rval));
    1627              : 
    1628              :     default:
    1629              :       return false;
    1630              :     }
    1631              : }
    1632              : 
    1633              : /*  The function value_replacement does the main work of doing the value
    1634              :     replacement.  Return non-zero if the replacement is done.  Otherwise return
    1635              :     0.  If we remove the middle basic block, return 2.
    1636              :     BB is the basic block where the replacement is going to be done on.  ARG0
    1637              :     is argument 0 from the PHI.  Likewise for ARG1.  */
    1638              : 
    1639              : static int
    1640      2475691 : value_replacement (basic_block cond_bb, basic_block middle_bb,
    1641              :                    edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
    1642              : {
    1643      2475691 :   gimple_stmt_iterator gsi;
    1644      2475691 :   edge true_edge, false_edge;
    1645      2475691 :   enum tree_code code;
    1646      2475691 :   bool empty_or_with_defined_p = true;
    1647              : 
    1648              :   /* Virtual operands don't need to be handled. */
    1649      4409041 :   if (virtual_operand_p (arg1))
    1650              :     return 0;
    1651              : 
    1652              :   /* Special case A ? B : B as this will always simplify to B. */
    1653      1317083 :   if (operand_equal_for_phi_arg_p (arg0, arg1))
    1654              :     return 0;
    1655              : 
    1656      2338472 :   gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
    1657      1169236 :   code = gimple_cond_code (cond);
    1658              : 
    1659              :   /* This transformation is only valid for equality comparisons.  */
    1660      1169236 :   if (code != NE_EXPR && code != EQ_EXPR)
    1661              :     return 0;
    1662              : 
    1663              :   /* Do not make conditional undefs unconditional.  */
    1664       711302 :   if ((TREE_CODE (arg0) == SSA_NAME
    1665       546431 :        && ssa_name_maybe_undef_p (arg0))
    1666      1255971 :       || (TREE_CODE (arg1) == SSA_NAME
    1667       306170 :           && ssa_name_maybe_undef_p (arg1)))
    1668              :     return false;
    1669              : 
    1670              :   /* If the type says honor signed zeros we cannot do this
    1671              :      optimization.  */
    1672       695056 :   if (HONOR_SIGNED_ZEROS (arg1))
    1673              :     return 0;
    1674              : 
    1675              :   /* If there is a statement in MIDDLE_BB that defines one of the PHI
    1676              :      arguments, then adjust arg0 or arg1.  */
    1677       681700 :   gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
    1678      2197574 :   while (!gsi_end_p (gsi))
    1679              :     {
    1680      1515874 :       gimple *stmt = gsi_stmt (gsi);
    1681      1515874 :       tree lhs;
    1682      1515874 :       gsi_next_nondebug (&gsi);
    1683      1515874 :       if (!is_gimple_assign (stmt))
    1684              :         {
    1685       207770 :           if (gimple_code (stmt) != GIMPLE_PREDICT
    1686       207770 :               && gimple_code (stmt) != GIMPLE_NOP)
    1687              :             empty_or_with_defined_p = false;
    1688       207770 :           continue;
    1689              :         }
    1690              :       /* Now try to adjust arg0 or arg1 according to the computation
    1691              :          in the statement.  */
    1692      1308104 :       lhs = gimple_assign_lhs (stmt);
    1693       337375 :       if (!(lhs == arg0
    1694       337375 :              && jump_function_from_stmt (&arg0, stmt))
    1695      1310209 :             || (lhs == arg1
    1696            0 :                 && jump_function_from_stmt (&arg1, stmt)))
    1697      1515874 :         empty_or_with_defined_p = false;
    1698              :     }
    1699              : 
    1700              :   /* The middle bb is not empty if there are any phi nodes. */
    1701       681700 :   if (phi_nodes (middle_bb))
    1702        79133 :     empty_or_with_defined_p = false;
    1703              : 
    1704              :   /* We need to know which is the true edge and which is the false
    1705              :       edge so that we know if have abs or negative abs.  */
    1706       681700 :   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
    1707              : 
    1708              :   /* At this point we know we have a COND_EXPR with two successors.
    1709              :      One successor is BB, the other successor is an empty block which
    1710              :      falls through into BB.
    1711              : 
    1712              :      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
    1713              : 
    1714              :      There is a single PHI node at the join point (BB) with two arguments.
    1715              : 
    1716              :      We now need to verify that the two arguments in the PHI node match
    1717              :      the two arguments to the equality comparison.  */
    1718              : 
    1719       681700 :   bool equal_p = operand_equal_for_value_replacement (arg0, arg1, &code, cond);
    1720       681700 :   bool maybe_equal_p = false;
    1721       681700 :   if (!equal_p
    1722       681700 :       && empty_or_with_defined_p
    1723       190596 :       && TREE_CODE (gimple_cond_rhs (cond)) == INTEGER_CST
    1724       831442 :       && (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg0)
    1725       149742 :           ? TREE_CODE (arg1) == INTEGER_CST
    1726       141935 :           : (operand_equal_for_phi_arg_p (gimple_cond_lhs (cond), arg1)
    1727        23574 :              && TREE_CODE (arg0) == INTEGER_CST)))
    1728              :     maybe_equal_p = true;
    1729       661570 :   if (equal_p || maybe_equal_p)
    1730              :     {
    1731        34054 :       edge e;
    1732        34054 :       tree arg;
    1733              : 
    1734              :       /* For NE_EXPR, we want to build an assignment result = arg where
    1735              :          arg is the PHI argument associated with the true edge.  For
    1736              :          EQ_EXPR we want the PHI argument associated with the false edge.  */
    1737        34054 :       e = (code == NE_EXPR ? true_edge : false_edge);
    1738              : 
    1739              :       /* Unfortunately, E may not reach BB (it may instead have gone to
    1740              :          OTHER_BLOCK).  If that is the case, then we want the single outgoing
    1741              :          edge from OTHER_BLOCK which reaches BB and represents the desired
    1742              :          path from COND_BLOCK.  */
    1743        34054 :       if (e->dest == middle_bb)
    1744        13676 :         e = single_succ_edge (e->dest);
    1745              : 
    1746              :       /* Now we know the incoming edge to BB that has the argument for the
    1747              :          RHS of our new assignment statement.  */
    1748        34054 :       if (e0 == e)
    1749              :         arg = arg0;
    1750              :       else
    1751        20378 :         arg = arg1;
    1752              : 
    1753              :       /* If the middle basic block was empty or is defining the
    1754              :          PHI arguments and this is a single phi where the args are different
    1755              :          for the edges e0 and e1 then we can remove the middle basic block. */
    1756        34054 :       if (empty_or_with_defined_p
    1757        34054 :           && single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)),
    1758              :                                                  e0, e1) == phi)
    1759              :         {
    1760        20378 :           use_operand_p use_p;
    1761        20378 :           gimple *use_stmt;
    1762              : 
    1763              :           /* Even if arg0/arg1 isn't equal to second operand of cond, we
    1764              :              can optimize away the bb if we can prove it doesn't care whether
    1765              :              phi result is arg0/arg1 or second operand of cond.  Consider:
    1766              :              <bb 2> [local count: 118111600]:
    1767              :              if (i_2(D) == 4)
    1768              :                goto <bb 4>; [97.00%]
    1769              :              else
    1770              :                goto <bb 3>; [3.00%]
    1771              : 
    1772              :              <bb 3> [local count: 3540129]:
    1773              : 
    1774              :              <bb 4> [local count: 118111600]:
    1775              :              # i_6 = PHI <i_2(D)(3), 6(2)>
    1776              :              _3 = i_6 != 0;
    1777              :              Here, carg is 4, oarg is 6, crhs is 0, and because
    1778              :              (4 != 0) == (6 != 0), we don't care if i_6 is 4 or 6, both
    1779              :              have the same outcome.  So, we can optimize this to:
    1780              :              _3 = i_2(D) != 0;
    1781              :              If the single imm use of phi result >, >=, < or <=, similarly
    1782              :              we can check if both carg and oarg compare the same against
    1783              :              crhs using ccode.  */
    1784        20378 :           if (maybe_equal_p
    1785        18495 :               && TREE_CODE (arg) != INTEGER_CST
    1786        38857 :               && single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt))
    1787              :             {
    1788        10272 :               enum tree_code ccode = ERROR_MARK;
    1789        10272 :               tree clhs = NULL_TREE, crhs = NULL_TREE;
    1790        10272 :               tree carg = gimple_cond_rhs (cond);
    1791        10272 :               tree oarg = e0 == e ? arg1 : arg0;
    1792        10272 :               if (is_gimple_assign (use_stmt)
    1793        10272 :                   && (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt))
    1794              :                       == tcc_comparison))
    1795              :                 {
    1796           57 :                   ccode = gimple_assign_rhs_code (use_stmt);
    1797           57 :                   clhs = gimple_assign_rhs1 (use_stmt);
    1798           57 :                   crhs = gimple_assign_rhs2 (use_stmt);
    1799              :                 }
    1800        10215 :               else if (gimple_code (use_stmt) == GIMPLE_COND)
    1801              :                 {
    1802           61 :                   ccode = gimple_cond_code (use_stmt);
    1803           61 :                   clhs = gimple_cond_lhs (use_stmt);
    1804           61 :                   crhs = gimple_cond_rhs (use_stmt);
    1805              :                 }
    1806          118 :               if (ccode != ERROR_MARK
    1807          118 :                   && clhs == gimple_phi_result (phi)
    1808          207 :                   && TREE_CODE (crhs) == INTEGER_CST)
    1809           45 :                 switch (ccode)
    1810              :                   {
    1811           26 :                   case EQ_EXPR:
    1812           26 :                   case NE_EXPR:
    1813           26 :                     if (!tree_int_cst_equal (crhs, carg)
    1814           26 :                         && !tree_int_cst_equal (crhs, oarg))
    1815              :                       equal_p = true;
    1816              :                     break;
    1817            2 :                   case GT_EXPR:
    1818            4 :                     if (tree_int_cst_lt (crhs, carg)
    1819            2 :                         == tree_int_cst_lt (crhs, oarg))
    1820              :                       equal_p = true;
    1821              :                     break;
    1822            0 :                   case GE_EXPR:
    1823            0 :                     if (tree_int_cst_le (crhs, carg)
    1824            0 :                         == tree_int_cst_le (crhs, oarg))
    1825              :                       equal_p = true;
    1826              :                     break;
    1827           13 :                   case LT_EXPR:
    1828           26 :                     if (tree_int_cst_lt (carg, crhs)
    1829           13 :                         == tree_int_cst_lt (oarg, crhs))
    1830              :                       equal_p = true;
    1831              :                     break;
    1832            4 :                   case LE_EXPR:
    1833            8 :                     if (tree_int_cst_le (carg, crhs)
    1834            4 :                         == tree_int_cst_le (oarg, crhs))
    1835              :                       equal_p = true;
    1836              :                     break;
    1837              :                   default:
    1838              :                     break;
    1839              :                   }
    1840        10256 :               if (equal_p)
    1841              :                 {
    1842           16 :                   tree phires = gimple_phi_result (phi);
    1843           16 :                   if (SSA_NAME_RANGE_INFO (phires))
    1844              :                     {
    1845              :                       /* After the optimization PHI result can have value
    1846              :                          which it couldn't have previously.  */
    1847           15 :                       value_range r (TREE_TYPE (phires));
    1848           15 :                       if (get_global_range_query ()->range_of_expr (r, phires,
    1849              :                                                                     phi))
    1850              :                         {
    1851           15 :                           value_range tmp (carg, carg);
    1852           15 :                           r.union_ (tmp);
    1853           15 :                           reset_flow_sensitive_info (phires);
    1854           15 :                           set_range_info (phires, r);
    1855           15 :                         }
    1856              :                       else
    1857            0 :                         reset_flow_sensitive_info (phires);
    1858           15 :                     }
    1859              :                 }
    1860           16 :               if (equal_p && MAY_HAVE_DEBUG_BIND_STMTS)
    1861              :                 {
    1862           13 :                   imm_use_iterator imm_iter;
    1863           13 :                   tree phires = gimple_phi_result (phi);
    1864           13 :                   tree temp = NULL_TREE;
    1865           13 :                   bool reset_p = false;
    1866              : 
    1867              :                   /* Add # DEBUG D#1 => arg != carg ? arg : oarg.  */
    1868           42 :                   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, phires)
    1869              :                     {
    1870           30 :                       if (!is_gimple_debug (use_stmt))
    1871           13 :                         continue;
    1872           17 :                       if (temp == NULL_TREE)
    1873              :                         {
    1874           12 :                           if (!single_pred_p (middle_bb)
    1875           12 :                               || EDGE_COUNT (gimple_bb (phi)->preds) != 2)
    1876              :                             {
    1877              :                               /* But only if middle_bb has a single
    1878              :                                  predecessor and phi bb has two, otherwise
    1879              :                                  we could use a SSA_NAME not usable in that
    1880              :                                  place or wrong-debug.  */
    1881            1 :                               reset_p = true;
    1882            1 :                               break;
    1883              :                             }
    1884           11 :                           gimple_stmt_iterator gsi
    1885           11 :                             = gsi_after_labels (gimple_bb (phi));
    1886           11 :                           tree type = TREE_TYPE (phires);
    1887           11 :                           temp = build_debug_expr_decl (type);
    1888           11 :                           tree t = build2 (NE_EXPR, boolean_type_node,
    1889              :                                            arg, carg);
    1890           11 :                           t = build3 (COND_EXPR, type, t, arg, oarg);
    1891           11 :                           gimple *g = gimple_build_debug_bind (temp, t, phi);
    1892           11 :                           gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    1893              :                         }
    1894           32 :                       FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
    1895           16 :                         replace_exp (use_p, temp);
    1896           16 :                       update_stmt (use_stmt);
    1897           13 :                     }
    1898           13 :                   if (reset_p)
    1899            1 :                     reset_debug_uses (phi);
    1900              :                 }
    1901              :             }
    1902        10122 :           if (equal_p)
    1903              :             {
    1904         1899 :               replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
    1905              :               /* Note that we optimized this PHI.  */
    1906         1899 :               return 2;
    1907              :             }
    1908              :         }
    1909        13676 :       else if (equal_p)
    1910              :         {
    1911        12041 :           if (!single_pred_p (middle_bb))
    1912              :             return 0;
    1913        11204 :           statistics_counter_event (cfun, "Replace PHI with "
    1914              :                                     "variable/value_replacement", 1);
    1915              : 
    1916              :           /* Replace the PHI arguments with arg. */
    1917        11204 :           SET_PHI_ARG_DEF (phi, e0->dest_idx, arg);
    1918        11204 :           SET_PHI_ARG_DEF (phi, e1->dest_idx, arg);
    1919        11204 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1920              :             {
    1921            0 :               fprintf (dump_file, "PHI ");
    1922            0 :               print_generic_expr (dump_file, gimple_phi_result (phi));
    1923            0 :               fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
    1924              :                        cond_bb->index);
    1925            0 :               print_generic_expr (dump_file, arg);
    1926            0 :               fprintf (dump_file, ".\n");
    1927              :             }
    1928              :           return 1;
    1929              :         }
    1930              :     }
    1931              : 
    1932       667760 :   if (!single_pred_p (middle_bb))
    1933              :     return 0;
    1934              : 
    1935              :   /* Now optimize (x != 0) ? x + y : y to just x + y.  */
    1936       563005 :   gsi = gsi_last_nondebug_bb (middle_bb);
    1937       563005 :   if (gsi_end_p (gsi))
    1938              :     return 0;
    1939              : 
    1940       389980 :   gimple *assign = gsi_stmt (gsi);
    1941       389980 :   if (!is_gimple_assign (assign)
    1942       389980 :       || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
    1943       106739 :           && !POINTER_TYPE_P (TREE_TYPE (arg0))))
    1944              :     return 0;
    1945              : 
    1946       331341 :   if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
    1947              :     {
    1948              :       /* If last stmt of the middle_bb is a conversion, handle it like
    1949              :          a preparation statement through constant evaluation with
    1950              :          checking for UB.  */
    1951       142252 :       enum tree_code sc = gimple_assign_rhs_code (assign);
    1952       142252 :       if (CONVERT_EXPR_CODE_P (sc))
    1953              :         assign = NULL;
    1954              :       else
    1955              :         return 0;
    1956              :     }
    1957              : 
    1958              :   /* Punt if there are (degenerate) PHIs in middle_bb, there should not be.  */
    1959       212376 :   if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
    1960              :     return 0;
    1961              : 
    1962              :   /* Allow up to 2 cheap preparation statements that prepare argument
    1963              :      for assign, e.g.:
    1964              :       if (y_4 != 0)
    1965              :         goto <bb 3>;
    1966              :       else
    1967              :         goto <bb 4>;
    1968              :      <bb 3>:
    1969              :       _1 = (int) y_4;
    1970              :       iftmp.0_6 = x_5(D) r<< _1;
    1971              :      <bb 4>:
    1972              :       # iftmp.0_2 = PHI <iftmp.0_6(3), x_5(D)(2)>
    1973              :      or:
    1974              :       if (y_3(D) == 0)
    1975              :         goto <bb 4>;
    1976              :       else
    1977              :         goto <bb 3>;
    1978              :      <bb 3>:
    1979              :       y_4 = y_3(D) & 31;
    1980              :       _1 = (int) y_4;
    1981              :       _6 = x_5(D) r<< _1;
    1982              :      <bb 4>:
    1983              :       # _2 = PHI <x_5(D)(2), _6(3)>  */
    1984       212376 :   gimple *prep_stmt[2] = { NULL, NULL };
    1985       212376 :   int prep_cnt;
    1986       212376 :   for (prep_cnt = 0; ; prep_cnt++)
    1987              :     {
    1988       274329 :       if (prep_cnt || assign)
    1989       251042 :         gsi_prev_nondebug (&gsi);
    1990       274329 :       if (gsi_end_p (gsi))
    1991              :         break;
    1992              : 
    1993       208993 :       gimple *g = gsi_stmt (gsi);
    1994       208993 :       if (gimple_code (g) == GIMPLE_LABEL)
    1995              :         break;
    1996              : 
    1997       208623 :       if (prep_cnt == 2 || !is_gimple_assign (g))
    1998       146670 :         return 0;
    1999              : 
    2000       183910 :       tree lhs = gimple_assign_lhs (g);
    2001       183910 :       tree rhs1 = gimple_assign_rhs1 (g);
    2002       183910 :       use_operand_p use_p;
    2003       183910 :       gimple *use_stmt;
    2004       183910 :       if (TREE_CODE (lhs) != SSA_NAME
    2005       176798 :           || TREE_CODE (rhs1) != SSA_NAME
    2006       112900 :           || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
    2007       109394 :           || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
    2008       105486 :           || !single_imm_use (lhs, &use_p, &use_stmt)
    2009       288244 :           || ((prep_cnt || assign)
    2010        82556 :               && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
    2011              :         return 0;
    2012        96914 :       switch (gimple_assign_rhs_code (g))
    2013              :         {
    2014              :         CASE_CONVERT:
    2015              :           break;
    2016        21161 :         case PLUS_EXPR:
    2017        21161 :         case BIT_AND_EXPR:
    2018        21161 :         case BIT_IOR_EXPR:
    2019        21161 :         case BIT_XOR_EXPR:
    2020        21161 :           if (TREE_CODE (gimple_assign_rhs2 (g)) != INTEGER_CST)
    2021              :             return 0;
    2022              :           break;
    2023              :         default:
    2024              :           return 0;
    2025              :         }
    2026        61953 :       prep_stmt[prep_cnt] = g;
    2027        61953 :     }
    2028              : 
    2029              :   /* Only transform if it removes the condition.  */
    2030        65706 :   if (!single_non_singleton_phi_for_edges (phi_nodes (gimple_bb (phi)), e0, e1))
    2031              :     return 0;
    2032              : 
    2033              :   /* Size-wise, this is always profitable.  */
    2034        49290 :   if (optimize_bb_for_speed_p (cond_bb)
    2035              :       /* The special case is useless if it has a low probability.  */
    2036        46467 :       && profile_status_for_fn (cfun) != PROFILE_ABSENT
    2037        55206 :       && EDGE_PRED (middle_bb, 0)->probability < profile_probability::even ()
    2038              :       /* If assign is cheap, there is no point avoiding it.  */
    2039        58048 :       && estimate_num_insns_seq (bb_seq (middle_bb), &eni_time_weights)
    2040         8758 :          >= 3 * estimate_num_insns (cond, &eni_time_weights))
    2041           91 :     return 0;
    2042              : 
    2043        49199 :   tree cond_lhs = gimple_cond_lhs (cond);
    2044        49199 :   tree cond_rhs = gimple_cond_rhs (cond);
    2045              : 
    2046              :   /* Propagate the cond_rhs constant through preparation stmts,
    2047              :      make sure UB isn't invoked while doing that.  */
    2048        50818 :   for (int i = prep_cnt - 1; i >= 0; --i)
    2049              :     {
    2050        13408 :       gimple *g = prep_stmt[i];
    2051        13408 :       tree grhs1 = gimple_assign_rhs1 (g);
    2052        13408 :       if (!operand_equal_for_phi_arg_p (cond_lhs, grhs1))
    2053              :         return 0;
    2054         7101 :       cond_lhs = gimple_assign_lhs (g);
    2055         7101 :       cond_rhs = fold_convert (TREE_TYPE (grhs1), cond_rhs);
    2056         7101 :       if (TREE_CODE (cond_rhs) != INTEGER_CST
    2057         7101 :           || TREE_OVERFLOW (cond_rhs))
    2058              :         return 0;
    2059         1619 :       if (gimple_assign_rhs_class (g) == GIMPLE_BINARY_RHS)
    2060              :         {
    2061          566 :           cond_rhs = int_const_binop (gimple_assign_rhs_code (g), cond_rhs,
    2062          566 :                                       gimple_assign_rhs2 (g));
    2063          566 :           if (TREE_OVERFLOW (cond_rhs))
    2064              :             return 0;
    2065              :         }
    2066         1619 :       cond_rhs = fold_convert (TREE_TYPE (cond_lhs), cond_rhs);
    2067         1619 :       if (TREE_CODE (cond_rhs) != INTEGER_CST
    2068         1619 :           || TREE_OVERFLOW (cond_rhs))
    2069              :         return 0;
    2070              :     }
    2071              : 
    2072        37410 :   tree lhs, rhs1, rhs2;
    2073        37410 :   enum tree_code code_def;
    2074        37410 :   if (assign)
    2075              :     {
    2076        37142 :       lhs = gimple_assign_lhs (assign);
    2077        37142 :       rhs1 = gimple_assign_rhs1 (assign);
    2078        37142 :       rhs2 = gimple_assign_rhs2 (assign);
    2079        37142 :       code_def = gimple_assign_rhs_code (assign);
    2080              :     }
    2081              :   else
    2082              :     {
    2083          268 :       gcc_assert (prep_cnt > 0);
    2084              :       lhs = cond_lhs;
    2085              :       rhs1 = NULL_TREE;
    2086              :       rhs2 = NULL_TREE;
    2087              :       code_def = ERROR_MARK;
    2088              :     }
    2089              : 
    2090        23511 :   if (((code == NE_EXPR && e1 == false_edge)
    2091        16926 :         || (code == EQ_EXPR && e1 == true_edge))
    2092        23282 :       && arg0 == lhs
    2093        60692 :       && ((assign == NULL
    2094          267 :            && operand_equal_for_phi_arg_p (arg1, cond_rhs))
    2095              :           || (assign
    2096        23015 :               && arg1 == rhs1
    2097        15073 :               && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
    2098          401 :               && neutral_element_p (code_def, cond_rhs, true))
    2099        22944 :           || (assign
    2100        22944 :               && arg1 == rhs2
    2101         1464 :               && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
    2102          696 :               && neutral_element_p (code_def, cond_rhs, false))
    2103              :           || (assign
    2104        22944 :               && operand_equal_for_phi_arg_p (arg1, cond_rhs)
    2105         2829 :               && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
    2106          193 :                    && absorbing_element_p (code_def, cond_rhs, true, rhs2))
    2107         2828 :                   || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
    2108          676 :                       && absorbing_element_p (code_def,
    2109              :                                               cond_rhs, false, rhs2))))))
    2110              :     {
    2111          112 :       gsi = gsi_for_stmt (cond);
    2112              :       /* Moving ASSIGN might change VR of lhs, e.g. when moving u_6
    2113              :          def-stmt in:
    2114              :            if (n_5 != 0)
    2115              :              goto <bb 3>;
    2116              :            else
    2117              :              goto <bb 4>;
    2118              : 
    2119              :            <bb 3>:
    2120              :            # RANGE [0, 4294967294]
    2121              :            u_6 = n_5 + 4294967295;
    2122              : 
    2123              :            <bb 4>:
    2124              :            # u_3 = PHI <u_6(3), 4294967295(2)>  */
    2125          112 :       reset_flow_sensitive_info (lhs);
    2126          112 :       gimple_stmt_iterator gsi_from;
    2127          309 :       for (int i = prep_cnt - 1; i >= 0; --i)
    2128              :         {
    2129           85 :           tree plhs = gimple_assign_lhs (prep_stmt[i]);
    2130           85 :           reset_flow_sensitive_info (plhs);
    2131           85 :           gsi_from = gsi_for_stmt (prep_stmt[i]);
    2132           85 :           gsi_move_before (&gsi_from, &gsi);
    2133              :         }
    2134          112 :       if (assign)
    2135              :         {
    2136          110 :           gsi_from = gsi_for_stmt (assign);
    2137          110 :           gsi_move_before (&gsi_from, &gsi);
    2138              :         }
    2139          112 :       replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
    2140          112 :       return 2;
    2141              :     }
    2142              : 
    2143              :   return 0;
    2144              : }
    2145              : 
    2146              : /* Attempt to optimize (x <=> y) cmp 0 and similar comparisons.
    2147              :    For strong ordering <=> try to match something like:
    2148              :     <bb 2> :  // cond3_bb (== cond2_bb)
    2149              :     if (x_4(D) != y_5(D))
    2150              :       goto <bb 3>; [INV]
    2151              :     else
    2152              :       goto <bb 6>; [INV]
    2153              : 
    2154              :     <bb 3> :  // cond_bb
    2155              :     if (x_4(D) < y_5(D))
    2156              :       goto <bb 6>; [INV]
    2157              :     else
    2158              :       goto <bb 4>; [INV]
    2159              : 
    2160              :     <bb 4> :  // middle_bb
    2161              : 
    2162              :     <bb 6> :  // phi_bb
    2163              :     # iftmp.0_2 = PHI <1(4), 0(2), -1(3)>
    2164              :     _1 = iftmp.0_2 == 0;
    2165              : 
    2166              :    and for partial ordering <=> something like:
    2167              : 
    2168              :     <bb 2> :  // cond3_bb
    2169              :     if (a_3(D) == b_5(D))
    2170              :       goto <bb 6>; [50.00%]
    2171              :     else
    2172              :       goto <bb 3>; [50.00%]
    2173              : 
    2174              :     <bb 3> [local count: 536870913]:  // cond2_bb
    2175              :     if (a_3(D) < b_5(D))
    2176              :       goto <bb 6>; [50.00%]
    2177              :     else
    2178              :       goto <bb 4>; [50.00%]
    2179              : 
    2180              :     <bb 4> [local count: 268435456]:  // cond_bb
    2181              :     if (a_3(D) > b_5(D))
    2182              :       goto <bb 6>; [50.00%]
    2183              :     else
    2184              :       goto <bb 5>; [50.00%]
    2185              : 
    2186              :     <bb 5> [local count: 134217728]:  // middle_bb
    2187              : 
    2188              :     <bb 6> [local count: 1073741824]:  // phi_bb
    2189              :     # SR.27_4 = PHI <0(2), -1(3), 1(4), -128(5)>
    2190              :     _2 = SR.27_4 > 0;  */
    2191              : 
    2192              : static bool
    2193       648213 : spaceship_replacement (basic_block cond_bb, basic_block middle_bb,
    2194              :                        edge e0, edge e1, gphi *phi,
    2195              :                        tree arg0, tree arg1)
    2196              : {
    2197       648213 :   tree phires = gimple_phi_result (phi);
    2198      1289469 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (phires))
    2199       514629 :       || TYPE_UNSIGNED (TREE_TYPE (phires))
    2200       259596 :       || !tree_fits_shwi_p (arg0)
    2201        75283 :       || !tree_fits_shwi_p (arg1)
    2202        41466 :       || (!IN_RANGE (tree_to_shwi (arg0), -1, 1)
    2203        19139 :           && tree_to_shwi (arg0) != -128)
    2204       671033 :       || (!IN_RANGE (tree_to_shwi (arg1), -1, 1)
    2205         2836 :           && tree_to_shwi (arg1) != -128))
    2206              :     return false;
    2207              : 
    2208        20042 :   basic_block phi_bb = gimple_bb (phi);
    2209        20042 :   gcc_assert (phi_bb == e0->dest && phi_bb == e1->dest);
    2210        20042 :   if (!IN_RANGE (EDGE_COUNT (phi_bb->preds), 3, 4))
    2211              :     return false;
    2212              : 
    2213         7798 :   use_operand_p use_p;
    2214         7798 :   gimple *use_stmt;
    2215         7798 :   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phires))
    2216              :     return false;
    2217         7793 :   if (!single_imm_use (phires, &use_p, &use_stmt))
    2218              :     return false;
    2219         7118 :   enum tree_code cmp;
    2220         7118 :   tree lhs, rhs;
    2221         7118 :   gimple *orig_use_stmt = use_stmt;
    2222         7118 :   tree orig_use_lhs = NULL_TREE;
    2223         7118 :   tree temps[2] = { NULL_TREE, NULL_TREE };
    2224              : 
    2225              :   /* Handle std::partial_ordering::_M_reverse(), i.e.
    2226              :      _1 = (unsigned char) phires;
    2227              :      _2 = -_1;
    2228              :      _3 = (signed char) _2;
    2229              :      and uses of _3 in comparison instead of phires.  */
    2230         7118 :   if (gimple_assign_cast_p (use_stmt))
    2231              :     {
    2232          236 :       orig_use_lhs = gimple_assign_lhs (use_stmt);
    2233          236 :       temps[0] = orig_use_lhs;
    2234          236 :       tree ty1 = TREE_TYPE (gimple_assign_rhs1 (use_stmt));
    2235          236 :       tree ty2 = TREE_TYPE (orig_use_lhs);
    2236              : 
    2237          236 :       if (!TYPE_UNSIGNED (ty2) || !INTEGRAL_TYPE_P (ty2))
    2238              :         return false;
    2239          197 :       if (TYPE_PRECISION (ty2) != 8 || TYPE_PRECISION (ty1) < 8)
    2240              :         return false;
    2241           94 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
    2242              :         return false;
    2243           94 :       if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
    2244              :         return false;
    2245              : 
    2246           93 :       if (!is_gimple_assign (use_stmt)
    2247           93 :           || gimple_assign_rhs_code (use_stmt) != NEGATE_EXPR)
    2248              :         return false;
    2249              : 
    2250           78 :       orig_use_lhs = gimple_assign_lhs (use_stmt);
    2251           78 :       temps[1] = orig_use_lhs;
    2252           78 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
    2253              :         return false;
    2254           78 :       if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
    2255              :         return false;
    2256              : 
    2257           78 :       if (!gimple_assign_cast_p (use_stmt))
    2258              :         return false;
    2259              : 
    2260           78 :       orig_use_lhs = gimple_assign_lhs (use_stmt);
    2261           78 :       tree ty3 = TREE_TYPE (orig_use_lhs);
    2262              : 
    2263           78 :       if (!useless_type_conversion_p (ty3, ty1))
    2264              :         return false;
    2265           78 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig_use_lhs))
    2266              :         return false;
    2267           78 :       if (!single_imm_use (orig_use_lhs, &use_p, &use_stmt))
    2268              :         return false;
    2269              :     }
    2270         6960 :   if (gimple_code (use_stmt) == GIMPLE_COND)
    2271              :     {
    2272         2518 :       cmp = gimple_cond_code (use_stmt);
    2273         2518 :       lhs = gimple_cond_lhs (use_stmt);
    2274         2518 :       rhs = gimple_cond_rhs (use_stmt);
    2275              :     }
    2276         4442 :   else if (is_gimple_assign (use_stmt))
    2277              :     {
    2278         2527 :       if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
    2279              :         {
    2280         1364 :           cmp = gimple_assign_rhs_code (use_stmt);
    2281         1364 :           lhs = gimple_assign_rhs1 (use_stmt);
    2282         1364 :           rhs = gimple_assign_rhs2 (use_stmt);
    2283              :         }
    2284         1163 :       else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
    2285              :         {
    2286            0 :           tree cond = gimple_assign_rhs1 (use_stmt);
    2287            0 :           if (!COMPARISON_CLASS_P (cond))
    2288              :             return false;
    2289            0 :           cmp = TREE_CODE (cond);
    2290            0 :           lhs = TREE_OPERAND (cond, 0);
    2291            0 :           rhs = TREE_OPERAND (cond, 1);
    2292              :         }
    2293              :       else
    2294              :         return false;
    2295              :     }
    2296              :   else
    2297              :     return false;
    2298         3882 :   switch (cmp)
    2299              :     {
    2300         3391 :     case EQ_EXPR:
    2301         3391 :     case NE_EXPR:
    2302         3391 :     case LT_EXPR:
    2303         3391 :     case GT_EXPR:
    2304         3391 :     case LE_EXPR:
    2305         3391 :     case GE_EXPR:
    2306         3391 :       break;
    2307              :     default:
    2308              :       return false;
    2309              :     }
    2310         6704 :   if (lhs != (orig_use_lhs ? orig_use_lhs : phires)
    2311         3028 :       || !tree_fits_shwi_p (rhs)
    2312         2760 :       || !IN_RANGE (tree_to_shwi (rhs), -1, 1))
    2313              :     return false;
    2314              : 
    2315         2748 :   if (!empty_block_p (middle_bb))
    2316              :     return false;
    2317              : 
    2318         5496 :   gcond *cond1 = as_a <gcond *> (*gsi_last_bb (cond_bb));
    2319         2748 :   enum tree_code cmp1 = gimple_cond_code (cond1);
    2320         2748 :   switch (cmp1)
    2321              :     {
    2322         2611 :     case LT_EXPR:
    2323         2611 :     case LE_EXPR:
    2324         2611 :     case GT_EXPR:
    2325         2611 :     case GE_EXPR:
    2326         2611 :       break;
    2327              :     default:
    2328              :       return false;
    2329              :     }
    2330         2611 :   tree lhs1 = gimple_cond_lhs (cond1);
    2331         2611 :   tree rhs1 = gimple_cond_rhs (cond1);
    2332         2611 :   if (TREE_CODE (lhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs1))
    2333              :     return false;
    2334         2611 :   if (TREE_CODE (rhs1) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs1))
    2335              :     return false;
    2336              : 
    2337         2611 :   if (!single_pred_p (cond_bb) || !cond_only_block_p (cond_bb))
    2338              :     return false;
    2339              : 
    2340         2587 :   basic_block cond2_bb = single_pred (cond_bb);
    2341         2587 :   if (EDGE_COUNT (cond2_bb->succs) != 2)
    2342              :     return false;
    2343         2587 :   edge cond2_phi_edge;
    2344         2587 :   if (EDGE_SUCC (cond2_bb, 0)->dest == cond_bb)
    2345              :     {
    2346         2116 :       if (EDGE_SUCC (cond2_bb, 1)->dest != phi_bb)
    2347              :         return false;
    2348              :       cond2_phi_edge = EDGE_SUCC (cond2_bb, 1);
    2349              :     }
    2350          471 :   else if (EDGE_SUCC (cond2_bb, 0)->dest != phi_bb)
    2351              :     return false;
    2352              :   else
    2353              :     cond2_phi_edge = EDGE_SUCC (cond2_bb, 0);
    2354         2587 :   tree arg2 = gimple_phi_arg_def (phi, cond2_phi_edge->dest_idx);
    2355         2587 :   if (!tree_fits_shwi_p (arg2))
    2356              :     return false;
    2357         5174 :   gcond *cond2 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond2_bb));
    2358         2587 :   if (!cond2)
    2359              :     return false;
    2360         2587 :   enum tree_code cmp2 = gimple_cond_code (cond2);
    2361         2587 :   tree lhs2 = gimple_cond_lhs (cond2);
    2362         2587 :   tree rhs2 = gimple_cond_rhs (cond2);
    2363         2587 :   if (lhs2 == lhs1)
    2364              :     {
    2365         2585 :       if (!operand_equal_p (rhs2, rhs1, 0))
    2366              :         {
    2367          341 :           if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
    2368          341 :               && TREE_CODE (rhs1) == INTEGER_CST
    2369          341 :               && TREE_CODE (rhs2) == INTEGER_CST)
    2370              :             {
    2371              :               /* For integers, we can have cond2 x == 5
    2372              :                  and cond1 x < 5, x <= 4, x <= 5, x < 6,
    2373              :                  x > 5, x >= 6, x >= 5 or x > 4.  */
    2374          341 :               if (tree_int_cst_lt (rhs1, rhs2))
    2375              :                 {
    2376          341 :                   if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
    2377              :                     return false;
    2378          341 :                   if (cmp1 == LE_EXPR)
    2379              :                     cmp1 = LT_EXPR;
    2380            0 :                   else if (cmp1 == GT_EXPR)
    2381              :                     cmp1 = GE_EXPR;
    2382              :                   else
    2383              :                     return false;
    2384              :                 }
    2385              :               else
    2386              :                 {
    2387            0 :                   gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
    2388            0 :                   if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
    2389              :                     return false;
    2390            0 :                   if (cmp1 == LT_EXPR)
    2391              :                     cmp1 = LE_EXPR;
    2392            0 :                   else if (cmp1 == GE_EXPR)
    2393              :                     cmp1 = GT_EXPR;
    2394              :                   else
    2395              :                     return false;
    2396              :                 }
    2397              :               rhs1 = rhs2;
    2398              :             }
    2399              :           else
    2400              :             return false;
    2401              :         }
    2402              :     }
    2403            2 :   else if (lhs2 == rhs1)
    2404              :     {
    2405            0 :       if (rhs2 != lhs1)
    2406              :         return false;
    2407              :     }
    2408              :   else
    2409              :     return false;
    2410              : 
    2411         2585 :   tree arg3 = arg2;
    2412         2585 :   basic_block cond3_bb = cond2_bb;
    2413         2585 :   edge cond3_phi_edge = cond2_phi_edge;
    2414         2585 :   gcond *cond3 = cond2;
    2415         2585 :   enum tree_code cmp3 = cmp2;
    2416         2585 :   tree lhs3 = lhs2;
    2417         2585 :   tree rhs3 = rhs2;
    2418         2585 :   if (EDGE_COUNT (phi_bb->preds) == 4)
    2419              :     {
    2420          446 :       if (absu_hwi (tree_to_shwi (arg2)) != 1)
    2421              :         return false;
    2422          438 :       if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
    2423          438 :           && HONOR_NANS (TREE_TYPE (lhs1)))
    2424              :         return false;
    2425          342 :       if (e1->flags & EDGE_TRUE_VALUE)
    2426              :         {
    2427          340 :           if (tree_to_shwi (arg0) != -128
    2428          340 :               || absu_hwi (tree_to_shwi (arg1)) != 1
    2429          680 :               || wi::to_widest (arg1) == wi::to_widest (arg2))
    2430              :             return false;
    2431              :         }
    2432            2 :       else if (tree_to_shwi (arg1) != -128
    2433            2 :                || absu_hwi (tree_to_shwi (arg0)) != 1
    2434            4 :                || wi::to_widest (arg0) == wi::to_widest (arg2))
    2435              :         return false;
    2436          342 :       switch (cmp2)
    2437              :         {
    2438          342 :         case LT_EXPR:
    2439          342 :         case LE_EXPR:
    2440          342 :         case GT_EXPR:
    2441          342 :         case GE_EXPR:
    2442          342 :           break;
    2443              :         default:
    2444              :           return false;
    2445              :         }
    2446              :       /* if (x < y) goto phi_bb; else fallthru;
    2447              :          if (x > y) goto phi_bb; else fallthru;
    2448              :          bbx:;
    2449              :          phi_bb:;
    2450              :          is ok, but if x and y are swapped in one of the comparisons,
    2451              :          or the comparisons are the same and operands not swapped,
    2452              :          or the true and false edges are swapped, it is not.
    2453              :          For HONOR_NANS, the edge flags are irrelevant and the comparisons
    2454              :          must be different for non-swapped operands and same for swapped
    2455              :          operands.  */
    2456          342 :       if ((lhs2 == lhs1)
    2457          342 :           ^ ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
    2458          342 :              != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
    2459          342 :           ^ ((cond2_phi_edge->flags & EDGE_FALSE_VALUE) != 0))
    2460              :         return false;
    2461          340 :       if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
    2462              :         return false;
    2463          340 :       cond3_bb = single_pred (cond2_bb);
    2464          340 :       if (EDGE_COUNT (cond3_bb->succs) != 2)
    2465              :         return false;
    2466          320 :       if (EDGE_SUCC (cond3_bb, 0)->dest == cond2_bb)
    2467              :         {
    2468          150 :           if (EDGE_SUCC (cond3_bb, 1)->dest != phi_bb)
    2469              :             return false;
    2470              :           cond3_phi_edge = EDGE_SUCC (cond3_bb, 1);
    2471              :         }
    2472          170 :       else if (EDGE_SUCC (cond3_bb, 0)->dest != phi_bb)
    2473              :         return false;
    2474              :       else
    2475              :         cond3_phi_edge = EDGE_SUCC (cond3_bb, 0);
    2476          320 :       arg3 = gimple_phi_arg_def (phi, cond3_phi_edge->dest_idx);
    2477          640 :       cond3 = safe_dyn_cast <gcond *> (*gsi_last_bb (cond3_bb));
    2478          320 :       if (!cond3)
    2479              :         return false;
    2480          320 :       cmp3 = gimple_cond_code (cond3);
    2481          320 :       lhs3 = gimple_cond_lhs (cond3);
    2482          320 :       rhs3 = gimple_cond_rhs (cond3);
    2483          320 :       if (lhs3 == lhs1)
    2484              :         {
    2485          318 :           if (!operand_equal_p (rhs3, rhs1, 0))
    2486              :             return false;
    2487              :         }
    2488            2 :       else if (lhs3 == rhs1)
    2489              :         {
    2490            0 :           if (rhs3 != lhs1)
    2491              :             return false;
    2492              :         }
    2493              :       else
    2494              :         return false;
    2495              :     }
    2496         2139 :   else if (absu_hwi (tree_to_shwi (arg0)) != 1
    2497         2118 :            || absu_hwi (tree_to_shwi (arg1)) != 1
    2498         4257 :            || wi::to_widest (arg0) == wi::to_widest (arg1)
    2499         4257 :            || HONOR_NANS (TREE_TYPE (lhs1)))
    2500              :     return false;
    2501              : 
    2502         2436 :   if (!integer_zerop (arg3) || (cmp3 != EQ_EXPR && cmp3 != NE_EXPR))
    2503              :     return false;
    2504         2436 :   if ((cond3_phi_edge->flags & (cmp3 == EQ_EXPR
    2505         2436 :                                 ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) == 0)
    2506              :     return false;
    2507              : 
    2508              :   /* lhs1 one_cmp rhs1 results in phires of 1.  */
    2509         2436 :   enum tree_code one_cmp;
    2510         4872 :   if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
    2511         2580 :       ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
    2512              :     one_cmp = LT_EXPR;
    2513              :   else
    2514         1793 :     one_cmp = GT_EXPR;
    2515              : 
    2516         2436 :   enum tree_code res_cmp;
    2517         2436 :   bool negate_p = false;
    2518         2436 :   switch (cmp)
    2519              :     {
    2520         1332 :     case EQ_EXPR:
    2521         1332 :       if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
    2522              :         res_cmp = EQ_EXPR;
    2523         1248 :       else if (integer_minus_onep (rhs))
    2524          781 :         res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
    2525          467 :       else if (integer_onep (rhs))
    2526              :         res_cmp = one_cmp;
    2527              :       else
    2528              :         return false;
    2529              :       break;
    2530         1014 :     case NE_EXPR:
    2531         1014 :       if (integer_zerop (rhs) && !HONOR_NANS (TREE_TYPE (lhs1)))
    2532              :         res_cmp = NE_EXPR;
    2533          976 :       else if (integer_minus_onep (rhs))
    2534          492 :         res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
    2535          484 :       else if (integer_onep (rhs))
    2536          699 :         res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
    2537              :       else
    2538              :         return false;
    2539          984 :       if (HONOR_NANS (TREE_TYPE (lhs1)))
    2540              :         negate_p = true;
    2541              :       break;
    2542           28 :     case LT_EXPR:
    2543           28 :       if (integer_onep (rhs))
    2544            0 :         res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
    2545           28 :       else if (integer_zerop (rhs))
    2546           28 :         res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
    2547              :       else
    2548              :         return false;
    2549           28 :       if (HONOR_NANS (TREE_TYPE (lhs1)))
    2550              :         negate_p = true;
    2551              :       break;
    2552            5 :     case LE_EXPR:
    2553            5 :       if (integer_zerop (rhs))
    2554            5 :         res_cmp = one_cmp == LT_EXPR ? GE_EXPR : LE_EXPR;
    2555            0 :       else if (integer_minus_onep (rhs))
    2556            0 :         res_cmp = one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR;
    2557              :       else
    2558              :         return false;
    2559            5 :       if (HONOR_NANS (TREE_TYPE (lhs1)))
    2560              :         negate_p = true;
    2561              :       break;
    2562            0 :     case GT_EXPR:
    2563            0 :       if (integer_minus_onep (rhs))
    2564            0 :         res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
    2565            0 :       else if (integer_zerop (rhs))
    2566              :         res_cmp = one_cmp;
    2567              :       else
    2568              :         return false;
    2569              :       break;
    2570           57 :     case GE_EXPR:
    2571           57 :       if (integer_zerop (rhs))
    2572           57 :         res_cmp = one_cmp == LT_EXPR ? LE_EXPR : GE_EXPR;
    2573            0 :       else if (integer_onep (rhs))
    2574              :         res_cmp = one_cmp;
    2575              :       else
    2576              :         return false;
    2577              :       break;
    2578              :     default:
    2579              :       gcc_unreachable ();
    2580              :     }
    2581         2364 :   if (orig_use_lhs)
    2582           60 :     res_cmp = swap_tree_comparison (res_cmp);
    2583              : 
    2584         2364 :   tree clhs1 = lhs1, crhs1 = rhs1;
    2585         2364 :   if (negate_p)
    2586              :     {
    2587           72 :       if (cfun->can_throw_non_call_exceptions)
    2588            0 :         return false;
    2589           72 :       res_cmp = invert_tree_comparison (res_cmp, false);
    2590           72 :       clhs1 = make_ssa_name (boolean_type_node);
    2591           72 :       gimple *g = gimple_build_assign (clhs1, res_cmp, lhs1, rhs1);
    2592           72 :       gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
    2593           72 :       gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2594           72 :       crhs1 = boolean_false_node;
    2595           72 :       res_cmp = EQ_EXPR;
    2596              :     }  
    2597              : 
    2598         2364 :   if (gimple_code (use_stmt) == GIMPLE_COND)
    2599              :     {
    2600         1705 :       gcond *use_cond = as_a <gcond *> (use_stmt);
    2601         1705 :       gimple_cond_set_code (use_cond, res_cmp);
    2602         1705 :       gimple_cond_set_lhs (use_cond, clhs1);
    2603         1705 :       gimple_cond_set_rhs (use_cond, crhs1);
    2604              :     }
    2605          659 :   else if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
    2606              :     {
    2607          659 :       gimple_assign_set_rhs_code (use_stmt, res_cmp);
    2608          659 :       gimple_assign_set_rhs1 (use_stmt, clhs1);
    2609          659 :       gimple_assign_set_rhs2 (use_stmt, crhs1);
    2610              :     }
    2611              :   else
    2612              :     {
    2613            0 :       tree cond = build2 (res_cmp, TREE_TYPE (gimple_assign_rhs1 (use_stmt)),
    2614              :                           clhs1, crhs1);
    2615            0 :       gimple_assign_set_rhs1 (use_stmt, cond);
    2616              :     }
    2617         2364 :   update_stmt (use_stmt);
    2618              : 
    2619         2364 :   if (MAY_HAVE_DEBUG_BIND_STMTS)
    2620              :     {
    2621         1966 :       use_operand_p use_p;
    2622         1966 :       imm_use_iterator iter;
    2623         1966 :       bool has_debug_uses = false;
    2624         1966 :       bool has_cast1_debug_uses = false;
    2625         1966 :       bool has_neg_debug_uses = false;
    2626         1966 :       bool has_cast2_debug_uses = false;
    2627         1988 :       FOR_EACH_IMM_USE_FAST (use_p, iter, phires)
    2628              :         {
    2629         1988 :           gimple *use_stmt = USE_STMT (use_p);
    2630         1988 :           if (is_gimple_debug (use_stmt))
    2631              :             {
    2632              :               has_debug_uses = true;
    2633              :               break;
    2634              :             }
    2635         1966 :         }
    2636         1966 :       if (orig_use_lhs)
    2637              :         {
    2638           44 :           FOR_EACH_IMM_USE_FAST (use_p, iter, temps[0])
    2639              :             {
    2640           38 :               gimple *use_stmt = USE_STMT (use_p);
    2641           38 :               if (is_gimple_debug (use_stmt))
    2642              :                 {
    2643              :                   has_debug_uses = true;
    2644              :                   has_cast1_debug_uses = true;
    2645              :                   break;
    2646              :                 }
    2647           22 :             }
    2648           44 :           FOR_EACH_IMM_USE_FAST (use_p, iter, temps[1])
    2649              :             {
    2650           38 :               gimple *use_stmt = USE_STMT (use_p);
    2651           38 :               if (is_gimple_debug (use_stmt))
    2652              :                 {
    2653              :                   has_debug_uses = true;
    2654              :                   has_cast1_debug_uses = true;
    2655              :                   has_neg_debug_uses = true;
    2656              :                   break;
    2657              :                 }
    2658           22 :             }
    2659           22 :           FOR_EACH_IMM_USE_FAST (use_p, iter, orig_use_lhs)
    2660              :             {
    2661           16 :               gimple *use_stmt = USE_STMT (use_p);
    2662           16 :               if (is_gimple_debug (use_stmt))
    2663              :                 {
    2664              :                   has_debug_uses = true;
    2665              :                   has_cast1_debug_uses = true;
    2666              :                   has_neg_debug_uses = true;
    2667              :                   has_cast2_debug_uses = true;
    2668              :                   break;
    2669              :                 }
    2670           22 :             }
    2671           22 :           if (has_debug_uses)
    2672              :             {
    2673           22 :               gimple_stmt_iterator gsi = gsi_for_stmt (orig_use_stmt);
    2674           22 :               tree zero = build_zero_cst (TREE_TYPE (temps[0]));
    2675           22 :               gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
    2676           22 :               update_stmt (orig_use_stmt);
    2677           22 :               gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
    2678           22 :               zero = build_zero_cst (TREE_TYPE (temps[1]));
    2679           22 :               gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
    2680           22 :               update_stmt (SSA_NAME_DEF_STMT (temps[1]));
    2681           22 :               gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
    2682           22 :               zero = build_zero_cst (TREE_TYPE (orig_use_lhs));
    2683           22 :               gimple_assign_set_rhs_with_ops (&gsi, INTEGER_CST, zero);
    2684           22 :               update_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
    2685              :             }
    2686              :         }
    2687              : 
    2688         1966 :       if (has_debug_uses)
    2689              :         {
    2690              :           /* If there are debug uses, emit something like:
    2691              :              # DEBUG D#1 => i_2(D) > j_3(D) ? 1 : -1
    2692              :              # DEBUG D#2 => i_2(D) == j_3(D) ? 0 : D#1
    2693              :              where > stands for the comparison that yielded 1
    2694              :              and replace debug uses of phi result with that D#2.
    2695              :              Ignore the value of -128 if !HONOR_NANS, because if NaNs
    2696              :              aren't expected, all floating point numbers should be
    2697              :              comparable.  If HONOR_NANS, emit something like:
    2698              :              # DEBUG D#1 => i_2(D) < j_3(D) ? -1 : -128
    2699              :              # DEBUG D#2 => i_2(D) > j_3(D) ? 1 : D#1
    2700              :              # DEBUG D#3 => i_2(D) == j_3(D) ? 0 : D#2
    2701              :              instead.  */
    2702         1966 :           gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
    2703         1966 :           tree type = TREE_TYPE (phires);
    2704         1966 :           tree minus_one = build_int_cst (type, -1);
    2705         1966 :           if (HONOR_NANS (TREE_TYPE (lhs1)))
    2706              :             {
    2707          102 :               tree temp3 = build_debug_expr_decl (type);
    2708          204 :               tree t = build2 (one_cmp == LT_EXPR ? GT_EXPR : LT_EXPR,
    2709              :                                boolean_type_node, lhs1, rhs2);
    2710          102 :               t = build3 (COND_EXPR, type, t, minus_one,
    2711              :                           build_int_cst (type, -128));
    2712          102 :               gimple *g = gimple_build_debug_bind (temp3, t, phi);
    2713          102 :               gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2714          102 :               minus_one = temp3;
    2715              :             }
    2716         1966 :           tree temp1 = build_debug_expr_decl (type);
    2717         1966 :           tree t = build2 (one_cmp, boolean_type_node, lhs1, rhs2);
    2718         1966 :           t = build3 (COND_EXPR, type, t, build_one_cst (type),
    2719              :                       minus_one);
    2720         1966 :           gimple *g = gimple_build_debug_bind (temp1, t, phi);
    2721         1966 :           gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2722         1966 :           tree temp2 = build_debug_expr_decl (type);
    2723         1966 :           t = build2 (EQ_EXPR, boolean_type_node, lhs1, rhs2);
    2724         1966 :           t = build3 (COND_EXPR, type, t, build_zero_cst (type), temp1);
    2725         1966 :           g = gimple_build_debug_bind (temp2, t, phi);
    2726         1966 :           gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2727         1966 :           replace_uses_by (phires, temp2);
    2728         1966 :           if (has_cast1_debug_uses)
    2729              :             {
    2730           16 :               tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[0]));
    2731           16 :               t = fold_convert (TREE_TYPE (temps[0]), temp2);
    2732           16 :               g = gimple_build_debug_bind (temp3, t, phi);
    2733           16 :               gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2734           16 :               replace_uses_by (temps[0], temp3);
    2735           16 :               temp2 = temp3;
    2736              :             }
    2737         1966 :           if (has_neg_debug_uses)
    2738              :             {
    2739           16 :               tree temp3 = build_debug_expr_decl (TREE_TYPE (temps[1]));
    2740           16 :               t = fold_build1 (NEGATE_EXPR, TREE_TYPE (temps[1]), temp2);
    2741           16 :               g = gimple_build_debug_bind (temp3, t, phi);
    2742           16 :               gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2743           16 :               replace_uses_by (temps[1], temp3);
    2744           16 :               temp2 = temp3;
    2745              :             }
    2746         1966 :           if (has_cast2_debug_uses)
    2747              :             {
    2748           16 :               tree temp3 = build_debug_expr_decl (TREE_TYPE (orig_use_lhs));
    2749           16 :               t = fold_convert (TREE_TYPE (orig_use_lhs), temp2);
    2750           16 :               g = gimple_build_debug_bind (temp3, t, phi);
    2751           16 :               gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2752           16 :               replace_uses_by (orig_use_lhs, temp3);
    2753              :             }
    2754              :         }
    2755              :     }
    2756              : 
    2757         2364 :   if (orig_use_lhs)
    2758              :     {
    2759           60 :       gimple_stmt_iterator gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (orig_use_lhs));
    2760           60 :       gsi_remove (&gsi, true);
    2761           60 :       gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (temps[1]));
    2762           60 :       gsi_remove (&gsi, true);
    2763           60 :       gsi = gsi_for_stmt (orig_use_stmt);
    2764           60 :       gsi_remove (&gsi, true);
    2765           60 :       release_ssa_name (orig_use_lhs);
    2766           60 :       release_ssa_name (temps[1]);
    2767           60 :       release_ssa_name (temps[0]);
    2768              :     }
    2769              : 
    2770         2364 :   gimple_stmt_iterator psi = gsi_for_stmt (phi);
    2771         2364 :   remove_phi_node (&psi, true);
    2772         2364 :   statistics_counter_event (cfun, "spaceship replacement", 1);
    2773              : 
    2774         2364 :   return true;
    2775              : }
    2776              : 
    2777              : /* Optimize x ? __builtin_fun (x) : C, where C is __builtin_fun (0).
    2778              :    Convert
    2779              : 
    2780              :    <bb 2>
    2781              :    if (b_4(D) != 0)
    2782              :    goto <bb 3>
    2783              :    else
    2784              :    goto <bb 4>
    2785              : 
    2786              :    <bb 3>
    2787              :    _2 = (unsigned long) b_4(D);
    2788              :    _9 = __builtin_popcountl (_2);
    2789              :    OR
    2790              :    _9 = __builtin_popcountl (b_4(D));
    2791              : 
    2792              :    <bb 4>
    2793              :    c_12 = PHI <0(2), _9(3)>
    2794              : 
    2795              :    Into
    2796              :    <bb 2>
    2797              :    _2 = (unsigned long) b_4(D);
    2798              :    _9 = __builtin_popcountl (_2);
    2799              :    OR
    2800              :    _9 = __builtin_popcountl (b_4(D));
    2801              : 
    2802              :    <bb 4>
    2803              :    c_12 = PHI <_9(2)>
    2804              : 
    2805              :    Similarly for __builtin_clz or __builtin_ctz if
    2806              :    C?Z_DEFINED_VALUE_AT_ZERO is 2, optab is present and
    2807              :    instead of 0 above it uses the value from that macro.  */
    2808              : 
    2809              : static bool
    2810       445993 : cond_removal_in_builtin_zero_pattern (basic_block cond_bb,
    2811              :                                       basic_block middle_bb,
    2812              :                                       edge e1, edge e2, gphi *phi,
    2813              :                                       tree arg0, tree arg1)
    2814              : {
    2815       445993 :   gimple_stmt_iterator gsi, gsi_from;
    2816       445993 :   gimple *call;
    2817       445993 :   gimple *cast = NULL;
    2818       445993 :   tree lhs, arg;
    2819              : 
    2820              :   /* Check that
    2821              :    _2 = (unsigned long) b_4(D);
    2822              :    _9 = __builtin_popcountl (_2);
    2823              :    OR
    2824              :    _9 = __builtin_popcountl (b_4(D));
    2825              :    are the only stmts in the middle_bb.  */
    2826              : 
    2827       445993 :   gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
    2828       445993 :   if (gsi_end_p (gsi))
    2829              :     return false;
    2830       279164 :   cast = gsi_stmt (gsi);
    2831       279164 :   gsi_next_nondebug (&gsi);
    2832       279164 :   if (!gsi_end_p (gsi))
    2833              :     {
    2834       141339 :       call = gsi_stmt (gsi);
    2835       141339 :       gsi_next_nondebug (&gsi);
    2836       141339 :       if (!gsi_end_p (gsi))
    2837              :         return false;
    2838              :     }
    2839              :   else
    2840              :     {
    2841              :       call = cast;
    2842              :       cast = NULL;
    2843              :     }
    2844              : 
    2845              :   /* Check that we have a popcount/clz/ctz builtin.  */
    2846       186118 :   if (!is_gimple_call (call))
    2847              :     return false;
    2848              : 
    2849         5306 :   lhs = gimple_get_lhs (call);
    2850              : 
    2851         5306 :   if (lhs == NULL_TREE)
    2852              :     return false;
    2853              : 
    2854         5280 :   combined_fn cfn = gimple_call_combined_fn (call);
    2855         5280 :   if (gimple_call_num_args (call) != 1
    2856         5280 :       && (gimple_call_num_args (call) != 2
    2857              :           || cfn == CFN_CLZ
    2858          592 :           || cfn == CFN_CTZ))
    2859              :     return false;
    2860              : 
    2861         3772 :   arg = gimple_call_arg (call, 0);
    2862              : 
    2863         3772 :   internal_fn ifn = IFN_LAST;
    2864         3772 :   int val = 0;
    2865         3772 :   bool any_val = false;
    2866         3772 :   switch (cfn)
    2867              :     {
    2868              :     CASE_CFN_BSWAP:
    2869              :     CASE_CFN_BITREVERSE:
    2870              :     CASE_CFN_FFS:
    2871              :     CASE_CFN_PARITY:
    2872              :     CASE_CFN_POPCOUNT:
    2873              :       break;
    2874          857 :     CASE_CFN_CLZ:
    2875          857 :       if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
    2876              :         {
    2877          857 :           tree type = TREE_TYPE (arg);
    2878          857 :           if (BITINT_TYPE_P (type))
    2879              :             {
    2880            4 :               if (gimple_call_num_args (call) == 1)
    2881              :                 {
    2882              :                   any_val = true;
    2883              :                   ifn = IFN_CLZ;
    2884              :                   break;
    2885              :                 }
    2886            0 :               if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
    2887              :                 return false;
    2888            0 :               HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
    2889            0 :               if ((int) at_zero != at_zero)
    2890              :                 return false;
    2891            0 :               ifn = IFN_CLZ;
    2892            0 :               val = at_zero;
    2893            0 :               break;
    2894              :             }
    2895          853 :           if (direct_internal_fn_supported_p (IFN_CLZ, type, OPTIMIZE_FOR_BOTH)
    2896         1681 :               && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
    2897              :                                             val) == 2)
    2898              :             {
    2899              :               ifn = IFN_CLZ;
    2900              :               break;
    2901              :             }
    2902              :         }
    2903              :       return false;
    2904          342 :     CASE_CFN_CTZ:
    2905          342 :       if (INTEGRAL_TYPE_P (TREE_TYPE (arg)))
    2906              :         {
    2907          342 :           tree type = TREE_TYPE (arg);
    2908          342 :           if (BITINT_TYPE_P (type))
    2909              :             {
    2910            4 :               if (gimple_call_num_args (call) == 1)
    2911              :                 {
    2912              :                   any_val = true;
    2913              :                   ifn = IFN_CTZ;
    2914              :                   break;
    2915              :                 }
    2916            0 :               if (!tree_fits_shwi_p (gimple_call_arg (call, 1)))
    2917              :                 return false;
    2918            0 :               HOST_WIDE_INT at_zero = tree_to_shwi (gimple_call_arg (call, 1));
    2919            0 :               if ((int) at_zero != at_zero)
    2920              :                 return false;
    2921            0 :               ifn = IFN_CTZ;
    2922            0 :               val = at_zero;
    2923            0 :               break;
    2924              :             }
    2925          338 :           if (direct_internal_fn_supported_p (IFN_CTZ, type, OPTIMIZE_FOR_BOTH)
    2926          655 :               && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type),
    2927              :                                             val) == 2)
    2928              :             {
    2929              :               ifn = IFN_CTZ;
    2930              :               break;
    2931              :             }
    2932              :         }
    2933              :       return false;
    2934            3 :     case CFN_BUILT_IN_CLRSB:
    2935            3 :       val = TYPE_PRECISION (integer_type_node) - 1;
    2936            3 :       break;
    2937            3 :     case CFN_BUILT_IN_CLRSBL:
    2938            3 :       val = TYPE_PRECISION (long_integer_type_node) - 1;
    2939            3 :       break;
    2940            3 :     case CFN_BUILT_IN_CLRSBLL:
    2941            3 :       val = TYPE_PRECISION (long_long_integer_type_node) - 1;
    2942            3 :       break;
    2943              :     default:
    2944              :       return false;
    2945              :     }
    2946              : 
    2947          152 :   if (cast)
    2948              :     {
    2949              :       /* We have a cast stmt feeding popcount/clz/ctz builtin.  */
    2950              :       /* Check that we have a cast prior to that.  */
    2951           55 :       if (gimple_code (cast) != GIMPLE_ASSIGN
    2952           55 :           || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (cast)))
    2953              :         return false;
    2954              :       /* Result of the cast stmt is the argument to the builtin.  */
    2955           25 :       if (arg != gimple_assign_lhs (cast))
    2956              :         return false;
    2957           25 :       arg = gimple_assign_rhs1 (cast);
    2958              :     }
    2959              : 
    2960          244 :   gcond *cond = dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
    2961              : 
    2962              :   /* Cond_bb has a check for b_4 [!=|==] 0 before calling the popcount/clz/ctz
    2963              :      builtin.  */
    2964          122 :   if (!cond
    2965          122 :       || (gimple_cond_code (cond) != NE_EXPR
    2966           23 :           && gimple_cond_code (cond) != EQ_EXPR)
    2967          122 :       || !integer_zerop (gimple_cond_rhs (cond))
    2968          119 :       || arg != gimple_cond_lhs (cond))
    2969              :     return false;
    2970              : 
    2971           41 :   edge true_edge, false_edge;
    2972              :   /* We need to know which is the true edge and which is the false
    2973              :      edge so that we know when to invert the condition below.  */
    2974           41 :   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
    2975              : 
    2976              :   /* Forward the edges over the middle basic block.  */
    2977           41 :   if (true_edge->dest == middle_bb)
    2978           41 :     true_edge = EDGE_SUCC (true_edge->dest, 0);
    2979           41 :   if (false_edge->dest == middle_bb)
    2980            0 :     false_edge = EDGE_SUCC (false_edge->dest, 0);
    2981              : 
    2982              :   /* Canonicalize the args with respect to the edges,
    2983              :      arg0 is from the true edge and arg1 is from the
    2984              :      false edge.
    2985              :      That is `cond ? arg0 : arg1`.*/
    2986           41 :   if (true_edge == e1)
    2987           41 :     gcc_assert (false_edge == e2);
    2988              :   else
    2989              :     {
    2990            0 :       gcc_assert (false_edge == e1);
    2991            0 :       gcc_assert (true_edge == e2);
    2992              :       std::swap (arg0, arg1);
    2993              :     }
    2994              : 
    2995              :   /* Canonicalize the args such that we get:
    2996              :      `arg != 0 ? arg0 : arg1`. So swap arg0/arg1
    2997              :      around if cond was an equals.  */
    2998           41 :   if (gimple_cond_code (cond) == EQ_EXPR)
    2999            2 :     std::swap (arg0, arg1);
    3000              : 
    3001              :   /* Check PHI arguments.  */
    3002           41 :   if (lhs != arg0
    3003           39 :       || TREE_CODE (arg1) != INTEGER_CST)
    3004              :     return false;
    3005           31 :   if (any_val)
    3006              :     {
    3007            0 :       if (!tree_fits_shwi_p (arg1))
    3008              :         return false;
    3009            0 :       HOST_WIDE_INT at_zero = tree_to_shwi (arg1);
    3010            0 :       if ((int) at_zero != at_zero)
    3011              :         return false;
    3012            0 :       val = at_zero;
    3013              :     }
    3014           31 :   else if (wi::to_wide (arg1) != val)
    3015              :     return false;
    3016              : 
    3017              :   /* And insert the popcount/clz/ctz builtin and cast stmt before the
    3018              :      cond_bb.  */
    3019           13 :   gsi = gsi_last_bb (cond_bb);
    3020           13 :   if (cast)
    3021              :     {
    3022           13 :       gsi_from = gsi_for_stmt (cast);
    3023           13 :       gsi_move_before (&gsi_from, &gsi);
    3024           13 :       reset_flow_sensitive_info (gimple_get_lhs (cast));
    3025              :     }
    3026           13 :   gsi_from = gsi_for_stmt (call);
    3027           13 :   if (ifn == IFN_LAST
    3028           13 :       || (gimple_call_internal_p (call) && gimple_call_num_args (call) == 2))
    3029            8 :     gsi_move_before (&gsi_from, &gsi);
    3030              :   else
    3031              :     {
    3032              :       /* For __builtin_c[lt]z* force .C[LT]Z ifn, because only
    3033              :          the latter is well defined at zero.  */
    3034            5 :       call = gimple_build_call_internal (ifn, 2, gimple_call_arg (call, 0),
    3035            5 :                                          build_int_cst (integer_type_node, val));
    3036            5 :       gimple_call_set_lhs (call, lhs);
    3037            5 :       gsi_insert_before (&gsi, call, GSI_SAME_STMT);
    3038            5 :       gsi_remove (&gsi_from, true);
    3039              :     }
    3040           13 :   reset_flow_sensitive_info (lhs);
    3041              : 
    3042              :   /* Now update the PHI and remove unneeded bbs.  */
    3043           13 :   replace_phi_edge_with_variable (cond_bb, e2, phi, lhs);
    3044           13 :   return true;
    3045              : }
    3046              : 
    3047              : /* Auxiliary functions to determine the set of memory accesses which
    3048              :    can't trap because they are preceded by accesses to the same memory
    3049              :    portion.  We do that for MEM_REFs, so we only need to track
    3050              :    the SSA_NAME of the pointer indirectly referenced.  The algorithm
    3051              :    simply is a walk over all instructions in dominator order.  When
    3052              :    we see an MEM_REF we determine if we've already seen a same
    3053              :    ref anywhere up to the root of the dominator tree.  If we do the
    3054              :    current access can't trap.  If we don't see any dominating access
    3055              :    the current access might trap, but might also make later accesses
    3056              :    non-trapping, so we remember it.  We need to be careful with loads
    3057              :    or stores, for instance a load might not trap, while a store would,
    3058              :    so if we see a dominating read access this doesn't mean that a later
    3059              :    write access would not trap.  Hence we also need to differentiate the
    3060              :    type of access(es) seen.
    3061              : 
    3062              :    ??? We currently are very conservative and assume that a load might
    3063              :    trap even if a store doesn't (write-only memory).  This probably is
    3064              :    overly conservative.
    3065              : 
    3066              :    We currently support a special case that for !TREE_ADDRESSABLE automatic
    3067              :    variables, it could ignore whether something is a load or store because the
    3068              :    local stack should be always writable.  */
    3069              : 
    3070              : /* A hash-table of references (MEM_REF/ARRAY_REF/COMPONENT_REF), and in which
    3071              :    basic block an *_REF through it was seen, which would constitute a
    3072              :    no-trap region for same accesses.
    3073              : 
    3074              :    Size is needed to support 2 MEM_REFs of different types, like
    3075              :    MEM<double>(s_1) and MEM<long>(s_1), which would compare equal with
    3076              :    OEP_ADDRESS_OF.  */
    3077              : struct ref_to_bb
    3078              : {
    3079              :   tree exp;
    3080              :   HOST_WIDE_INT size;
    3081              :   unsigned int phase;
    3082              :   basic_block bb;
    3083              : };
    3084              : 
    3085              : /* Hashtable helpers.  */
    3086              : 
    3087              : struct refs_hasher : free_ptr_hash<ref_to_bb>
    3088              : {
    3089              :   static inline hashval_t hash (const ref_to_bb *);
    3090              :   static inline bool equal (const ref_to_bb *, const ref_to_bb *);
    3091              : };
    3092              : 
    3093              : /* Used for quick clearing of the hash-table when we see calls.
    3094              :    Hash entries with phase < nt_call_phase are invalid.  */
    3095              : static unsigned int nt_call_phase;
    3096              : 
    3097              : /* The hash function.  */
    3098              : 
    3099              : inline hashval_t
    3100     20096019 : refs_hasher::hash (const ref_to_bb *n)
    3101              : {
    3102     20096019 :   inchash::hash hstate;
    3103     20096019 :   inchash::add_expr (n->exp, hstate, OEP_ADDRESS_OF);
    3104     20096019 :   hstate.add_hwi (n->size);
    3105     20096019 :   return hstate.end ();
    3106              : }
    3107              : 
    3108              : /* The equality function of *P1 and *P2.  */
    3109              : 
    3110              : inline bool
    3111     14675737 : refs_hasher::equal (const ref_to_bb *n1, const ref_to_bb *n2)
    3112              : {
    3113     14675737 :   return operand_equal_p (n1->exp, n2->exp, OEP_ADDRESS_OF)
    3114     14675737 :          && n1->size == n2->size;
    3115              : }
    3116              : 
    3117              : class nontrapping_dom_walker : public dom_walker
    3118              : {
    3119              : public:
    3120      1062856 :   nontrapping_dom_walker (cdi_direction direction, hash_set<tree> *ps)
    3121      1062856 :     : dom_walker (direction), m_nontrapping (ps), m_seen_refs (128)
    3122      1062856 :   {}
    3123              : 
    3124              :   edge before_dom_children (basic_block) final override;
    3125              :   void after_dom_children (basic_block) final override;
    3126              : 
    3127              : private:
    3128              : 
    3129              :   /* We see the expression EXP in basic block BB.  If it's an interesting
    3130              :      expression (an MEM_REF through an SSA_NAME) possibly insert the
    3131              :      expression into the set NONTRAP or the hash table of seen expressions.
    3132              :      STORE is true if this expression is on the LHS, otherwise it's on
    3133              :      the RHS.  */
    3134              :   void add_or_mark_expr (basic_block, tree, bool);
    3135              : 
    3136              :   hash_set<tree> *m_nontrapping;
    3137              : 
    3138              :   /* The hash table for remembering what we've seen.  */
    3139              :   hash_table<refs_hasher> m_seen_refs;
    3140              : };
    3141              : 
    3142              : /* Called by walk_dominator_tree, when entering the block BB.  */
    3143              : edge
    3144     11881281 : nontrapping_dom_walker::before_dom_children (basic_block bb)
    3145              : {
    3146     11881281 :   edge e;
    3147     11881281 :   edge_iterator ei;
    3148     11881281 :   gimple_stmt_iterator gsi;
    3149              : 
    3150              :   /* If we haven't seen all our predecessors, clear the hash-table.  */
    3151     26110155 :   FOR_EACH_EDGE (e, ei, bb->preds)
    3152     14934248 :     if ((((size_t)e->src->aux) & 2) == 0)
    3153              :       {
    3154       705374 :         nt_call_phase++;
    3155       705374 :         break;
    3156              :       }
    3157              : 
    3158              :   /* Mark this BB as being on the path to dominator root and as visited.  */
    3159     11881281 :   bb->aux = (void*)(1 | 2);
    3160              : 
    3161              :   /* And walk the statements in order.  */
    3162    107396869 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3163              :     {
    3164     83634307 :       gimple *stmt = gsi_stmt (gsi);
    3165              : 
    3166     83634307 :       if ((gimple_code (stmt) == GIMPLE_ASM && gimple_vdef (stmt))
    3167     83670298 :           || (is_gimple_call (stmt)
    3168      5711225 :               && (!nonfreeing_call_p (stmt) || !nonbarrier_call_p (stmt))))
    3169      5123730 :         nt_call_phase++;
    3170     93966297 :       else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt))
    3171              :         {
    3172     13440202 :           add_or_mark_expr (bb, gimple_assign_lhs (stmt), true);
    3173     13440202 :           add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), false);
    3174              :         }
    3175              :     }
    3176     11881281 :   return NULL;
    3177              : }
    3178              : 
    3179              : /* Called by walk_dominator_tree, when basic block BB is exited.  */
    3180              : void
    3181     11881281 : nontrapping_dom_walker::after_dom_children (basic_block bb)
    3182              : {
    3183              :   /* This BB isn't on the path to dominator root anymore.  */
    3184     11881281 :   bb->aux = (void*)2;
    3185     11881281 : }
    3186              : 
    3187              : /* We see the expression EXP in basic block BB.  If it's an interesting
    3188              :    expression of:
    3189              :      1) MEM_REF
    3190              :      2) ARRAY_REF
    3191              :      3) COMPONENT_REF
    3192              :    possibly insert the expression into the set NONTRAP or the hash table
    3193              :    of seen expressions.  STORE is true if this expression is on the LHS,
    3194              :    otherwise it's on the RHS.  */
    3195              : void
    3196     26880404 : nontrapping_dom_walker::add_or_mark_expr (basic_block bb, tree exp, bool store)
    3197              : {
    3198     26880404 :   HOST_WIDE_INT size;
    3199              : 
    3200     26880404 :   if ((TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == ARRAY_REF
    3201     22506224 :        || TREE_CODE (exp) == COMPONENT_REF)
    3202     34117398 :       && (size = int_size_in_bytes (TREE_TYPE (exp))) > 0)
    3203              :     {
    3204     11611169 :       struct ref_to_bb map;
    3205     11611169 :       ref_to_bb **slot;
    3206     11611169 :       struct ref_to_bb *r2bb;
    3207     11611169 :       basic_block found_bb = 0;
    3208              : 
    3209     11611169 :       if (!store)
    3210              :         {
    3211      5324830 :           tree base = get_base_address (exp);
    3212              :           /* Only record a LOAD of a local variable without address-taken, as
    3213              :              the local stack is always writable.  This allows cselim on a STORE
    3214              :              with a dominating LOAD.  */
    3215      5324830 :           if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
    3216      4357649 :             return;
    3217              :         }
    3218              : 
    3219              :       /* Try to find the last seen *_REF, which can trap.  */
    3220      7253520 :       map.exp = exp;
    3221      7253520 :       map.size = size;
    3222      7253520 :       slot = m_seen_refs.find_slot (&map, INSERT);
    3223      7253520 :       r2bb = *slot;
    3224      7253520 :       if (r2bb && r2bb->phase >= nt_call_phase)
    3225       290610 :         found_bb = r2bb->bb;
    3226              : 
    3227              :       /* If we've found a trapping *_REF, _and_ it dominates EXP
    3228              :          (it's in a basic block on the path from us to the dominator root)
    3229              :          then we can't trap.  */
    3230       290610 :       if (found_bb && (((size_t)found_bb->aux) & 1) == 1)
    3231              :         {
    3232        75290 :           m_nontrapping->add (exp);
    3233              :         }
    3234              :       else
    3235              :         {
    3236              :           /* EXP might trap, so insert it into the hash table.  */
    3237      7178230 :           if (r2bb)
    3238              :             {
    3239       992829 :               r2bb->phase = nt_call_phase;
    3240       992829 :               r2bb->bb = bb;
    3241              :             }
    3242              :           else
    3243              :             {
    3244      6185401 :               r2bb = XNEW (struct ref_to_bb);
    3245      6185401 :               r2bb->phase = nt_call_phase;
    3246      6185401 :               r2bb->bb = bb;
    3247      6185401 :               r2bb->exp = exp;
    3248      6185401 :               r2bb->size = size;
    3249      6185401 :               *slot = r2bb;
    3250              :             }
    3251              :         }
    3252              :     }
    3253              : }
    3254              : 
    3255              : /* This is the entry point of gathering non trapping memory accesses.
    3256              :    It will do a dominator walk over the whole function, and it will
    3257              :    make use of the bb->aux pointers.  It returns a set of trees
    3258              :    (the MEM_REFs itself) which can't trap.  */
    3259              : static hash_set<tree> *
    3260      1062856 : get_non_trapping (void)
    3261              : {
    3262      1062856 :   nt_call_phase = 0;
    3263      1062856 :   hash_set<tree> *nontrap = new hash_set<tree>;
    3264              : 
    3265      2125712 :   nontrapping_dom_walker (CDI_DOMINATORS, nontrap)
    3266      1062856 :     .walk (cfun->cfg->x_entry_block_ptr);
    3267              : 
    3268      1062856 :   clear_aux_for_blocks ();
    3269      1062856 :   return nontrap;
    3270              : }
    3271              : 
    3272              : /* Do the main work of conditional store replacement.  We already know
    3273              :    that the recognized pattern looks like so:
    3274              : 
    3275              :    split:
    3276              :      if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
    3277              :    MIDDLE_BB:
    3278              :      something
    3279              :      fallthrough (edge E0)
    3280              :    JOIN_BB:
    3281              :      some more
    3282              : 
    3283              :    ASSIGN is a store in MIDDLE_BB which is the candidate for cselim.  We check
    3284              :    that MIDDLE_BB contains only one store (i.e., ASSIGN), that that store
    3285              :    doesn't trap (not via NOTRAP, but via checking if an access to the same
    3286              :    memory location dominates us, or the store is to a local addressable object)
    3287              :    and that the store has a "simple" RHS.  */
    3288              : 
    3289              : static bool
    3290       430682 : cond_store_replacement (basic_block middle_bb, basic_block join_bb, edge e0,
    3291              :                         edge e1, gimple *assign, hash_set<tree> *nontrap)
    3292              : {
    3293       430682 :   tree lhs, rhs, name, name2;
    3294       430682 :   gphi *newphi;
    3295       430682 :   gassign *new_stmt;
    3296       430682 :   gimple_stmt_iterator gsi;
    3297       430682 :   location_t locus;
    3298              : 
    3299              :   /* Check if middle_bb contains of only one store.  */
    3300       430682 :   if (!assign
    3301        26796 :       || !gimple_assign_single_p (assign)
    3302       457478 :       || gimple_has_volatile_ops (assign))
    3303              :     return false;
    3304              : 
    3305        26580 :   locus = gimple_location (assign);
    3306        26580 :   lhs = gimple_assign_lhs (assign);
    3307        26580 :   rhs = gimple_assign_rhs1 (assign);
    3308        26580 :   if ((!REFERENCE_CLASS_P (lhs)
    3309        26580 :        && !DECL_P (lhs))
    3310        26580 :       || !is_gimple_reg_type (TREE_TYPE (lhs)))
    3311              :     return false;
    3312              : 
    3313              :   /* Make sure all uses (except the rhs) in the single stmt are also available
    3314              :      where we insert to.  */
    3315        26117 :   ssa_op_iter iter;
    3316        26117 :   tree use;
    3317        50283 :   FOR_EACH_SSA_TREE_OPERAND (use, assign, iter, SSA_OP_USE)
    3318              :     {
    3319        28566 :       if (use == rhs)
    3320        12793 :         continue;
    3321              : 
    3322        15773 :       gimple *stmt = SSA_NAME_DEF_STMT (use);
    3323        15773 :       if (stmt && gimple_bb (stmt) == middle_bb)
    3324              :         return false;
    3325              :     }
    3326              : 
    3327              :   /* Prove that we can move the store down.  We could also check
    3328              :      TREE_THIS_NOTRAP here, but in that case we also could move stores,
    3329              :      whose value is not available readily, which we want to avoid.  */
    3330        21717 :   if (nontrap->contains (lhs))
    3331              :     {
    3332              :       /* For local non-addressable variables, a load in the same bb
    3333              :          (though before) will cause the lhs to be in the nontrap hashset.
    3334              :          So need to check if there are no other loads in the middle bb.
    3335              :          FIXME: this is over conserative, this check could be made to
    3336              :          allow loads unrelated to lhs.  */
    3337          379 :       tree vuse = gimple_vuse (assign);
    3338          379 :       imm_use_iterator iter;
    3339          379 :       gimple *use_stmt;
    3340         1133 :       FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
    3341              :         {
    3342          955 :           if (use_stmt == assign)
    3343          378 :             continue;
    3344          577 :           if (gimple_bb (use_stmt) == middle_bb)
    3345          201 :             return false;
    3346          379 :         }
    3347              :     }
    3348              :   else
    3349              :     {
    3350              :       /* If LHS is an access to a local variable without address-taken
    3351              :          (or when we allow data races) and known not to trap, we could
    3352              :          always safely move down the store.  */
    3353        21338 :       if (ref_can_have_store_data_races (lhs)
    3354        21338 :           || lhs_could_trap_p (lhs))
    3355              :         return false;
    3356              :     }
    3357              : 
    3358              :   /* Now we've checked the constraints, so do the transformation:
    3359              :      1) Remove the single store.  */
    3360          178 :   gsi = gsi_for_stmt (assign);
    3361          178 :   unlink_stmt_vdef (assign);
    3362          178 :   gsi_remove (&gsi, true);
    3363          178 :   release_defs (assign);
    3364              : 
    3365              :   /* Make both store and load use alias-set zero as we have to
    3366              :      deal with the case of the store being a conditional change
    3367              :      of the dynamic type.  */
    3368          178 :   lhs = unshare_expr (lhs);
    3369          178 :   tree *basep = &lhs;
    3370          363 :   while (handled_component_p (*basep))
    3371          185 :     basep = &TREE_OPERAND (*basep, 0);
    3372          178 :   if (TREE_CODE (*basep) == MEM_REF
    3373          178 :       || TREE_CODE (*basep) == TARGET_MEM_REF)
    3374           94 :     TREE_OPERAND (*basep, 1)
    3375          188 :       = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
    3376              :   else
    3377           84 :     *basep = build2 (MEM_REF, TREE_TYPE (*basep),
    3378              :                      build_fold_addr_expr (*basep),
    3379              :                      build_zero_cst (ptr_type_node));
    3380              : 
    3381              :   /* 2) Insert a load from the memory of the store to the temporary
    3382              :         on the edge which did not contain the store.  */
    3383          178 :   gphi *vphi = get_virtual_phi (join_bb);
    3384          178 :   name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
    3385          178 :   new_stmt = gimple_build_assign (name, lhs);
    3386          178 :   gimple_set_location (new_stmt, locus);
    3387              :   /* Set the vuse for the new load.  */
    3388          178 :   gimple_set_vuse (new_stmt, gimple_phi_arg_def (vphi, e1->dest_idx));
    3389          178 :   lhs = unshare_expr (lhs);
    3390          178 :   {
    3391              :     /* Set the no-warning bit on the rhs of the load to avoid uninit
    3392              :        warnings.  */
    3393          178 :     tree rhs1 = gimple_assign_rhs1 (new_stmt);
    3394          178 :     suppress_warning (rhs1, OPT_Wuninitialized);
    3395              :   }
    3396          178 :   gsi_insert_on_edge (e1, new_stmt);
    3397              : 
    3398              :   /* 3) Create a PHI node at the join block, with one argument
    3399              :         holding the old RHS, and the other holding the temporary
    3400              :         where we stored the old memory contents.  */
    3401          178 :   name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
    3402          178 :   newphi = create_phi_node (name2, join_bb);
    3403          178 :   add_phi_arg (newphi, rhs, e0, locus);
    3404          178 :   add_phi_arg (newphi, name, e1, locus);
    3405              : 
    3406          178 :   new_stmt = gimple_build_assign (lhs, gimple_phi_result (newphi));
    3407              : 
    3408              :   /* Update the vdef for the new store statement. */
    3409          178 :   tree newvphilhs = make_ssa_name (gimple_vop (cfun));
    3410          178 :   tree vdef = gimple_phi_result (vphi);
    3411          178 :   gimple_set_vuse (new_stmt, newvphilhs);
    3412          178 :   gimple_set_vdef (new_stmt, vdef);
    3413          178 :   gimple_phi_set_result (vphi, newvphilhs);
    3414          178 :   SSA_NAME_DEF_STMT (vdef) = new_stmt;
    3415          178 :   update_stmt (vphi);
    3416              : 
    3417              :   /* 4) Insert that PHI node.  */
    3418          178 :   gsi = gsi_after_labels (join_bb);
    3419          178 :   gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
    3420              : 
    3421          178 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3422              :     {
    3423            1 :       fprintf (dump_file, "\nConditional store replacement happened!");
    3424            1 :       fprintf (dump_file, "\nReplaced the store with a load.");
    3425            1 :       fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
    3426            1 :       print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
    3427              :     }
    3428          178 :   statistics_counter_event (cfun, "conditional store replacement", 1);
    3429              : 
    3430          178 :   return true;
    3431              : }
    3432              : 
    3433              : /* Do the main work of conditional store replacement.  */
    3434              : 
    3435              : static bool
    3436       110997 : cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
    3437              :                                   basic_block join_bb, gimple *then_assign,
    3438              :                                   gimple *else_assign,
    3439              :                                   gphi *vphi)
    3440              : {
    3441       110997 :   tree lhs_base, lhs, then_rhs, else_rhs, name;
    3442       110997 :   location_t then_locus, else_locus;
    3443       110997 :   gimple_stmt_iterator gsi;
    3444       110997 :   gphi *newphi = nullptr;
    3445       110997 :   gassign *new_stmt;
    3446              : 
    3447       110997 :   if (then_assign == NULL
    3448       110997 :       || !gimple_assign_single_p (then_assign)
    3449       110997 :       || else_assign == NULL
    3450       110997 :       || !gimple_assign_single_p (else_assign)
    3451       110997 :       || stmt_references_abnormal_ssa_name (then_assign)
    3452       221980 :       || stmt_references_abnormal_ssa_name (else_assign))
    3453              :     return false;
    3454              : 
    3455              :   /* Allow both being clobbers but no other volatile operations. */
    3456       110983 :   if (gimple_clobber_p (then_assign)
    3457       110983 :       && gimple_clobber_p (else_assign))
    3458              :     ;
    3459       204064 :   else if (gimple_has_volatile_ops (then_assign)
    3460       204064 :            || gimple_has_volatile_ops (else_assign))
    3461              :    return false;
    3462              : 
    3463        93559 :   lhs = gimple_assign_lhs (then_assign);
    3464        93559 :   if (!operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
    3465              :     return false;
    3466              : 
    3467        33621 :   lhs_base = get_base_address (lhs);
    3468        33621 :   if (lhs_base == NULL_TREE
    3469        33621 :       || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
    3470              :     return false;
    3471              : 
    3472        33576 :   then_rhs = gimple_assign_rhs1 (then_assign);
    3473        33576 :   else_rhs = gimple_assign_rhs1 (else_assign);
    3474        33576 :   then_locus = gimple_location (then_assign);
    3475        33576 :   else_locus = gimple_location (else_assign);
    3476              : 
    3477        33576 :   if (!is_gimple_reg_type (TREE_TYPE (lhs)))
    3478              :     {
    3479              :       /* Handle clobbers separately as operand_equal_p does not check
    3480              :          the kind of the clobbers being the same. */
    3481         6993 :       if (TREE_CLOBBER_P (then_rhs) && TREE_CLOBBER_P (else_rhs))
    3482              :         {
    3483         2817 :           if (CLOBBER_KIND (then_rhs) != CLOBBER_KIND  (else_rhs))
    3484              :             return false;
    3485              :         }
    3486         4176 :       else if (!operand_equal_p (then_rhs, else_rhs))
    3487              :         return false;
    3488              :       /* Currently only handle commoning of `= {}`.   */
    3489         3377 :       if (TREE_CODE (then_rhs) != CONSTRUCTOR)
    3490              :         return false;
    3491              :     }
    3492              : 
    3493        29536 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3494              :     {
    3495           11 :       if (TREE_CLOBBER_P (then_rhs))
    3496            3 :         fprintf(dump_file, "factoring out clobber:\n\tthen:\n");
    3497              :       else
    3498            8 :         fprintf(dump_file, "factoring out stores:\n\tthen:\n");
    3499           11 :       print_gimple_stmt (dump_file, then_assign, 0,
    3500              :                          TDF_VOPS|TDF_MEMSYMS);
    3501           11 :       fprintf(dump_file, "\telse:\n");
    3502           11 :       print_gimple_stmt (dump_file, else_assign, 0,
    3503              :                          TDF_VOPS|TDF_MEMSYMS);
    3504           11 :       fprintf (dump_file, "\n");
    3505              :     }
    3506              : 
    3507              :   /* Now we've checked the constraints, so do the transformation:
    3508              :      1) Remove the stores.  */
    3509        29536 :   gsi = gsi_for_stmt (then_assign);
    3510        29536 :   unlink_stmt_vdef (then_assign);
    3511        29536 :   gsi_remove (&gsi, true);
    3512        29536 :   release_defs (then_assign);
    3513              : 
    3514        29536 :   gsi = gsi_for_stmt (else_assign);
    3515        29536 :   unlink_stmt_vdef (else_assign);
    3516        29536 :   gsi_remove (&gsi, true);
    3517        29536 :   release_defs (else_assign);
    3518              : 
    3519              :   /* 2) Create a PHI node at the join block, with one argument
    3520              :         holding the old RHS, and the other holding the temporary
    3521              :         where we stored the old memory contents.  */
    3522        29536 :   if (operand_equal_p (then_rhs, else_rhs))
    3523              :     name = then_rhs;
    3524              :   else
    3525              :     {
    3526        24219 :       name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
    3527        24219 :       newphi = create_phi_node (name, join_bb);
    3528        24219 :       add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
    3529        24219 :       add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
    3530              :     }
    3531              : 
    3532        29536 :   new_stmt = gimple_build_assign (lhs, name);
    3533              :   /* Update the vdef for the new store statement. */
    3534        29536 :   tree newvphilhs = make_ssa_name (gimple_vop (cfun));
    3535        29536 :   tree vdef = gimple_phi_result (vphi);
    3536        29536 :   gimple_set_vuse (new_stmt, newvphilhs);
    3537        29536 :   gimple_set_vdef (new_stmt, vdef);
    3538        29536 :   gimple_phi_set_result (vphi, newvphilhs);
    3539        29536 :   SSA_NAME_DEF_STMT (vdef) = new_stmt;
    3540        29536 :   update_stmt (vphi);
    3541        29536 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3542              :     {
    3543           11 :       if (newphi)
    3544              :         {
    3545            4 :          fprintf(dump_file, "to use phi:\n");
    3546            4 :           print_gimple_stmt (dump_file, newphi, 0,
    3547              :                              TDF_VOPS|TDF_MEMSYMS);
    3548            4 :           fprintf(dump_file, "\n");
    3549              :         }
    3550              :       else
    3551            7 :         fprintf(dump_file, "to:\n");
    3552           11 :       print_gimple_stmt (dump_file, new_stmt, 0,
    3553              :                          TDF_VOPS|TDF_MEMSYMS);
    3554           11 :       fprintf(dump_file, "\n\n");
    3555              :     }
    3556              : 
    3557              :   /* 3) Insert that new store.  */
    3558        29536 :   gsi = gsi_after_labels (join_bb);
    3559        29536 :   gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
    3560              : 
    3561        29536 :   statistics_counter_event (cfun, "if-then-else store replacement", 1);
    3562              : 
    3563        29536 :   return true;
    3564              : }
    3565              : 
    3566              : /* Return the last store in BB with VDEF or NULL if there are
    3567              :    loads following the store. VUSE_ONLY is where the only use of the
    3568              :    vdef should be.  If ONLYONESTORE is true, then the store is
    3569              :    the only store in the BB.  */
    3570              : 
    3571              : static gimple *
    3572      3426605 : trailing_store_in_bb (basic_block bb, tree vdef, gimple *vuse_only, bool onlyonestore)
    3573              : {
    3574      3426605 :   if (SSA_NAME_IS_DEFAULT_DEF (vdef))
    3575              :     return NULL;
    3576      3396757 :   gimple *store = SSA_NAME_DEF_STMT (vdef);
    3577      3396757 :   if (gimple_bb (store) != bb
    3578      3396757 :       || gimple_code (store) == GIMPLE_PHI)
    3579              :     return NULL;
    3580              : 
    3581              :   /* Verify there is no other store in this BB if requested.  */
    3582      3295191 :   if (onlyonestore
    3583      1638496 :       && !SSA_NAME_IS_DEFAULT_DEF (gimple_vuse (store))
    3584      1241337 :       && gimple_bb (SSA_NAME_DEF_STMT (gimple_vuse (store))) == bb
    3585      3771862 :       && gimple_code (SSA_NAME_DEF_STMT (gimple_vuse (store))) != GIMPLE_PHI)
    3586              :     return NULL;
    3587              : 
    3588              :   // Needs to be an simple store and not a call.
    3589      2818750 :   if (!gimple_assign_single_p (store))
    3590              :     return NULL;
    3591              : 
    3592              :   /* Verify there is no load or store after the store, the vdef of the store
    3593              :      should only be used by the vuse_only.  */
    3594      1078783 :   use_operand_p use_p;
    3595      1078783 :   gimple *use_stmt;
    3596      2157566 :   if (!single_imm_use (gimple_vdef (store), &use_p, &use_stmt))
    3597              :     return NULL;
    3598      1053838 :   if (use_stmt != vuse_only)
    3599            0 :     return NULL;
    3600              : 
    3601              :   return store;
    3602              : }
    3603              : 
    3604              : /* Takes a MEM and changes the aliasing set to be zero on it.
    3605              :    This handles all variants include decls. */
    3606              : static tree
    3607         1541 : copy_mem_with_alias_set_zero (tree mem)
    3608              : {
    3609         1541 :   mem = unshare_expr (mem);
    3610         1541 :   tree *basep = &mem;
    3611         3180 :   while (handled_component_p (*basep))
    3612         1639 :     basep = &TREE_OPERAND (*basep, 0);
    3613         1541 :   if (TREE_CODE (*basep) == MEM_REF
    3614         1541 :       || TREE_CODE (*basep) == TARGET_MEM_REF)
    3615          178 :     TREE_OPERAND (*basep, 1)
    3616          356 :       = fold_convert (ptr_type_node, TREE_OPERAND (*basep, 1));
    3617              :   else
    3618         1363 :     *basep = build2 (MEM_REF, TREE_TYPE (*basep),
    3619              :                      build_fold_addr_expr (*basep),
    3620              :                      build_zero_cst (ptr_type_node));
    3621         1541 :   return mem;
    3622              : }
    3623              : 
    3624              : /* Do the main work of a limited conditional store replacement.
    3625              :    This recognized pattern like so:
    3626              : 
    3627              :    COND_BB:
    3628              :      store = a_1;
    3629              :      // no loads
    3630              :      if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
    3631              :    MIDDLE_BB:
    3632              :      something // no loads
    3633              :      store = a_2;
    3634              :      something // no loads
    3635              :      fallthrough (edge E0)
    3636              :    JOIN_BB:
    3637              :      some more
    3638              : 
    3639              :   This is a limited form of the full cond_store_replacement
    3640              :   to be allowed from use from phiopt and can be done
    3641              :   without calculating the non-trapping cases.  */
    3642              : static bool
    3643      1457342 : cond_store_replacement_limited (basic_block middle_bb, basic_block join_bb,
    3644              :                                 basic_block cond_bb,
    3645              :                                 edge e0, edge e1,
    3646              :                                 bool caninsert_edge)
    3647              : {
    3648      1457342 :   tree lhs, rhs;
    3649      1457342 :   location_t locus;
    3650              :   /* Currently don't handle more than 2 incoming edges
    3651              :      into the merge bb. */
    3652      1457342 :   if (EDGE_COUNT (join_bb->preds) > 2)
    3653              :     return false;
    3654              :   /* The middle bb needs to have a single predecessor of the cond_bb.  */
    3655      1457342 :   if (!single_pred_p (middle_bb))
    3656              :     return false;
    3657      1457342 :   gphi *vphi = get_virtual_phi (join_bb);
    3658      1457342 :   if (!vphi)
    3659              :     return false;
    3660      1289864 :   tree middle_vdef = gimple_phi_arg_def_from_edge (vphi, e0);
    3661              :   /* Check if middle_bb contains of only one store.  */
    3662      1289864 :   gimple *store_middle;
    3663      1289864 :   store_middle = trailing_store_in_bb (middle_bb, middle_vdef,
    3664              :                                        vphi, true);
    3665              : 
    3666      1289864 :   if (!store_middle
    3667       139519 :       || !gimple_assign_single_p (store_middle)
    3668       139519 :       || gimple_has_volatile_ops (store_middle)
    3669              :       // Rejects clobbers too.
    3670      1428521 :       || gimple_clobber_p (store_middle))
    3671              :     return false;
    3672              : 
    3673       138657 :   locus = gimple_location (store_middle);
    3674       138657 :   lhs = gimple_assign_lhs (store_middle);
    3675       138657 :   rhs = gimple_assign_rhs1 (store_middle);
    3676       138657 :   if ((!REFERENCE_CLASS_P (lhs)
    3677       138657 :        && !DECL_P (lhs))
    3678       138657 :       || !is_gimple_reg_type (TREE_TYPE (lhs)))
    3679              :     return false;
    3680              : 
    3681              :   /* Three cases that can be handled:
    3682              :      1) the lhs is stored to right before the condition.
    3683              :        Will remove the store before the condition.
    3684              :      2) Or the lhs is loaded from right before the condition.
    3685              :      3) Neither of these. (this will insert a load in the other edge)
    3686              :      For case 2 and 3, check for data races.
    3687              :      For case 2, the load can either be based on a local variable
    3688              :      or a known non-trapping decl.
    3689              :      For case 3, the store needs to known to be non-trapping.  */
    3690       136422 :   tree vuse = gimple_vuse (store_middle);
    3691       136422 :   gimple *beforestore = nullptr;
    3692       136422 :   gimple *vdef_before = SSA_NAME_DEF_STMT (vuse);
    3693       136422 :   tree other_rhs = nullptr;
    3694              : 
    3695              :   /* See if there is a store before the condition case.  */
    3696       136422 :   if (gimple_assign_single_p (vdef_before))
    3697              :     {
    3698        34609 :       tree beforelhs = gimple_assign_lhs (vdef_before);
    3699              :       /* Only allow the store to be right before the condition.  */
    3700        34609 :       if (gimple_bb (vdef_before) == cond_bb
    3701              :           /* This can't be a clobber */
    3702        29305 :           && !gimple_clobber_p (vdef_before)
    3703              :           /* An exact match is only supported.
    3704              :              FIXME: Allow for clique/base mismatch?  */
    3705        59720 :           && operand_equal_p (lhs, beforelhs))
    3706              :         {
    3707              :           /* The vuse of the of store in the middle should be also
    3708              :              the entry in the phi for the other edge.  */
    3709         5419 :           gcc_assert (vuse == gimple_phi_arg_def_from_edge (vphi, e1));
    3710         5419 :           tree vuse = gimple_vuse (store_middle);
    3711         5419 :           imm_use_iterator iter;
    3712         5419 :           gimple *use_stmt;
    3713         5419 :           bool has_load = false;
    3714              :           /* If there is a load, then just reuse the value and not
    3715              :              remove the old store as that might be used by the load.  */
    3716        15692 :           FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
    3717              :             {
    3718        10876 :               if (use_stmt != store_middle
    3719        10876 :                   && use_stmt != vphi)
    3720              :                 {
    3721              :                   has_load = true;
    3722              :                   break;
    3723              :                 }
    3724         5419 :             }
    3725         5419 :           other_rhs = gimple_assign_rhs1 (vdef_before);
    3726              :           /* If there is no load, then keep the reference to the store stmt.  */
    3727         5419 :           if (!has_load)
    3728         4816 :             beforestore = vdef_before;
    3729              :         }
    3730              :     }
    3731              :   /*
    3732              :     case 2:
    3733              :     a = local_var[n];
    3734              :     if (b)
    3735              :       local_var[n] = c;
    3736              : 
    3737              :     case 3:
    3738              :     if (b)
    3739              :       nontrapping = c;
    3740              : 
    3741              :     For case 3, nontrapping needs to satisfy tree_could_trap_p.
    3742              :     In both cases ref_can_have_store_data_races needs to be satisfy.
    3743              :   */
    3744              : 
    3745              :   /* Maybe the load/local non-escaped variable case.  */
    3746         5419 :   if (!other_rhs)
    3747              :     {
    3748       131003 :       tree lhsbase = get_base_address (lhs);
    3749              :       /* If this store ref can't have data races, a store
    3750              :          that was conditional can't become unconditional.  */
    3751       131003 :       if (ref_can_have_store_data_races (lhs))
    3752       129462 :         return false;
    3753         8055 :       tree vuse = gimple_vuse (store_middle);
    3754         8055 :       imm_use_iterator iter;
    3755         8055 :       gimple *use_stmt;
    3756              :       /* Try to find the load before the store that matches
    3757              :          if we have a local variable or a non trapping store.  */
    3758        15397 :       if ((auto_var_p (lhsbase) && !TREE_ADDRESSABLE (lhsbase))
    3759         8091 :           || !lhs_could_trap_p (lhs))
    3760              :         {
    3761        35704 :           FOR_EACH_IMM_USE_STMT (use_stmt, iter, vuse)
    3762              :             {
    3763        29212 :               if (gimple_bb (use_stmt) != cond_bb)
    3764        20691 :                 continue;
    3765              :               /* Looking for a load only.  */
    3766         8521 :               if (!gimple_assign_load_p (use_stmt))
    3767            0 :                 continue;
    3768         8521 :               tree rhs = gimple_assign_rhs1 (use_stmt);
    3769         8521 :               if (!operand_equal_p (rhs, lhs))
    3770         7640 :                 continue;
    3771          881 :               other_rhs = gimple_assign_lhs (use_stmt);
    3772          881 :               lhs = copy_mem_with_alias_set_zero (lhs);
    3773          881 :               break;
    3774         7373 :             }
    3775              :         }
    3776         8055 :       if (!other_rhs)
    3777              :         {
    3778         7174 :           gassign *new_stmt;
    3779              :           /* If not allowing inserting on the edge, then don't.  */
    3780         7174 :           if (!caninsert_edge)
    3781              :             return false;
    3782              :           /* If LHS is an access to a local variable without address-taken
    3783              :              (or when we allow data races) and known not to trap, we could
    3784              :              always safely move down the store.  */
    3785         2145 :           if (lhs_could_trap_p (lhs))
    3786              :             return false;
    3787          660 :           lhs = copy_mem_with_alias_set_zero (lhs);
    3788              :           /* Insert a load from the memory of the store to the temporary
    3789              :              on the edge which did not contain the store.  */
    3790          660 :           other_rhs = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
    3791          660 :           new_stmt = gimple_build_assign (other_rhs, lhs);
    3792          660 :           gimple_set_location (new_stmt, locus);
    3793              :           /* Set the vuse for the new load.  */
    3794          660 :           gimple_set_vuse (new_stmt,
    3795          660 :                            gimple_phi_arg_def (vphi, e1->dest_idx));
    3796          660 :           lhs = unshare_expr (lhs);
    3797          660 :           {
    3798              :             /* Set the no-warning bit on the rhs of the load to avoid
    3799              :                uninit warnings.  */
    3800          660 :             tree rhs1 = gimple_assign_rhs1 (new_stmt);
    3801          660 :             suppress_warning (rhs1, OPT_Wuninitialized);
    3802              :           }
    3803          660 :           gsi_insert_on_edge (e1, new_stmt);
    3804              :         }
    3805              :     }
    3806              : 
    3807         6960 :   gphi *newphi;
    3808         6960 :   gassign *new_stmt;
    3809         6960 :   gimple_stmt_iterator gsi;
    3810              :   /* Now we've checked the constraints, so do the transformation:
    3811              :      1) Remove the store(s).  */
    3812         6960 :   gsi = gsi_for_stmt (store_middle);
    3813         6960 :   unlink_stmt_vdef (store_middle);
    3814         6960 :   gsi_remove (&gsi, true);
    3815         6960 :   release_defs (store_middle);
    3816              : 
    3817              :   /* Remove the store before the conditional if possible.  */
    3818         6960 :   if (beforestore)
    3819              :     {
    3820         4816 :       gsi = gsi_for_stmt (beforestore);
    3821         4816 :       unlink_stmt_vdef (beforestore);
    3822         4816 :       gsi_remove (&gsi, true);
    3823         4816 :       release_defs (beforestore);
    3824              :     }
    3825              : 
    3826              : 
    3827              :   /* 2) Create a PHI node at the join block, with one argument
    3828              :         holding the old RHS, and the other holding the temporary
    3829              :         where we stored the old memory contents.  */
    3830         6960 :   tree phiname = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
    3831         6960 :   newphi = create_phi_node (phiname, join_bb);
    3832         6960 :   add_phi_arg (newphi, rhs, e0, locus);
    3833         6960 :   add_phi_arg (newphi, other_rhs, e1, locus);
    3834              : 
    3835              :   /* 3. Create the new store.  */
    3836         6960 :   new_stmt = gimple_build_assign (lhs, phiname);
    3837              : 
    3838              :   /* Update the vdef for the new store statement. */
    3839         6960 :   tree newvphilhs = make_ssa_name (gimple_vop (cfun));
    3840         6960 :   tree vdef = gimple_phi_result (vphi);
    3841         6960 :   gimple_set_vuse (new_stmt, newvphilhs);
    3842         6960 :   gimple_set_vdef (new_stmt, vdef);
    3843         6960 :   gimple_phi_set_result (vphi, newvphilhs);
    3844         6960 :   SSA_NAME_DEF_STMT (vdef) = new_stmt;
    3845         6960 :   update_stmt (vphi);
    3846              : 
    3847         6960 :   gsi = gsi_after_labels (join_bb);
    3848         6960 :   gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
    3849              : 
    3850         6960 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3851              :     {
    3852           14 :       fprintf (dump_file, "\nConditional store replacement happened!");
    3853           14 :       if (beforestore)
    3854            5 :         fprintf (dump_file, "\nRemoved the store before the condition.");
    3855           14 :       fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
    3856           14 :       print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
    3857              :     }
    3858         6960 :   statistics_counter_event (cfun, "conditional store replacement", 1);
    3859         6960 :   return true;
    3860              : }
    3861              : 
    3862              : 
    3863              : /* Return the only store in MIDDLE_BB as the candidate store for cselim.  Return
    3864              :    NULL if no candidate can be found.  */
    3865              : 
    3866              : static gimple *
    3867       430682 : cselim_candidate (basic_block middle_bb, basic_block join_bb, edge e0)
    3868              : {
    3869       430682 :   gphi *vphi = get_virtual_phi (join_bb);
    3870       430682 :   if (!vphi)
    3871              :     return NULL;
    3872              : 
    3873       263204 :   tree middle_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, e0);
    3874       263204 :   return trailing_store_in_bb (middle_bb, middle_vdef, vphi, true);
    3875              : }
    3876              : 
    3877              : /* Limited Conditional store replacement.  We already know
    3878              :    that the recognized pattern looks like so:
    3879              : 
    3880              :    split:
    3881              :      if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
    3882              :    THEN_BB:
    3883              :      ...
    3884              :      STORE = Y;
    3885              :      ...
    3886              :      goto JOIN_BB;
    3887              :    ELSE_BB:
    3888              :      ...
    3889              :      STORE = Z;
    3890              :      ...
    3891              :      fallthrough (edge E0)
    3892              :    JOIN_BB:
    3893              :      some more
    3894              : 
    3895              :    Handles only the case with store in THEN_BB and ELSE_BB.  That is
    3896              :    cheap enough due to in phiopt and not worry about heurstics.  Moving the store
    3897              :    out might provide an opportunity for a phiopt to happen.
    3898              :    At -O1 (!flag_expensive_optimizations), this only handles the only store in
    3899              :    the BBs.  */
    3900              : 
    3901              : static bool
    3902       957342 : cond_if_else_store_replacement_limited (basic_block then_bb, basic_block else_bb,
    3903              :                                         basic_block join_bb)
    3904              : {
    3905       957342 :   gphi *vphi = get_virtual_phi (join_bb);
    3906       957342 :   if (!vphi)
    3907              :     return false;
    3908              : 
    3909       957342 :   tree then_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (then_bb));
    3910      1914684 :   gimple *then_assign = trailing_store_in_bb (then_bb, then_vdef, vphi,
    3911       957342 :                                               !flag_expensive_optimizations);
    3912       957342 :   if (!then_assign)
    3913              :     return false;
    3914              : 
    3915       776943 :   tree else_vdef = PHI_ARG_DEF_FROM_EDGE (vphi, single_succ_edge (else_bb));
    3916      1553886 :   gimple *else_assign = trailing_store_in_bb (else_bb, else_vdef, vphi,
    3917       776943 :                                               !flag_expensive_optimizations);
    3918       776943 :   if (!else_assign)
    3919              :     return false;
    3920              : 
    3921        99149 :   if (!cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
    3922              :                                          then_assign, else_assign, vphi))
    3923              :     {
    3924        71213 :       gimple *then_n, *else_n;
    3925              : 
    3926              :       // Try to see if one "store" can be skipped on either side.
    3927        71213 :       if (!flag_expensive_optimizations)
    3928              :         return false;
    3929       139252 :       then_n = trailing_store_in_bb (then_bb, gimple_vuse (then_assign),
    3930              :                                      then_assign, true);
    3931        69626 :       if (then_n)
    3932              :         {
    3933         7435 :           ao_ref then_ref_n;
    3934         7435 :           ao_ref_init (&then_ref_n, gimple_assign_lhs (then_n));
    3935         7435 :           if (stmt_may_clobber_ref_p_1 (then_assign, &then_ref_n, false)
    3936         7435 :               || ref_maybe_used_by_stmt_p (then_assign, &then_ref_n, false))
    3937              :             then_n = nullptr;
    3938              :         }
    3939       139252 :       else_n = trailing_store_in_bb (else_bb, gimple_vuse (else_assign),
    3940              :                                      else_assign, true);
    3941        69626 :       if (else_n)
    3942              :         {
    3943         3996 :           ao_ref else_ref_n;
    3944         3996 :           ao_ref_init (&else_ref_n, gimple_assign_lhs (else_n));
    3945         3996 :           if (stmt_may_clobber_ref_p_1 (else_assign, &else_ref_n, false)
    3946         3996 :               || ref_maybe_used_by_stmt_p (else_assign, &else_ref_n, false))
    3947              :             else_n = nullptr;
    3948              :         }
    3949        69626 :       if (then_n
    3950        69626 :           && cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
    3951              :                                                then_n, else_assign, vphi))
    3952              :         return true;
    3953        69295 :       if (else_n
    3954        69295 :           && cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
    3955              :                                                then_assign, else_n, vphi))
    3956              :         return true;
    3957        69236 :       if (else_n && then_n
    3958        69236 :           && cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
    3959              :                                                then_n, else_n, vphi))
    3960           99 :         return true;
    3961              :       return false;
    3962              :   }
    3963              :   return true;
    3964              : }
    3965              : 
    3966              : /* Conditional store replacement.  We already know
    3967              :    that the recognized pattern looks like so:
    3968              : 
    3969              :    split:
    3970              :      if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
    3971              :    THEN_BB:
    3972              :      ...
    3973              :      X = Y;
    3974              :      ...
    3975              :      goto JOIN_BB;
    3976              :    ELSE_BB:
    3977              :      ...
    3978              :      X = Z;
    3979              :      ...
    3980              :      fallthrough (edge E0)
    3981              :    JOIN_BB:
    3982              :      some more
    3983              : 
    3984              :    We check that it is safe to sink the store to JOIN_BB by verifying that
    3985              :    there are no read-after-write or write-after-write dependencies in
    3986              :    THEN_BB and ELSE_BB.  */
    3987              : 
    3988              : static bool
    3989       241252 : cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
    3990              :                                 basic_block join_bb)
    3991              : {
    3992       241252 :   vec<data_reference_p> then_datarefs, else_datarefs;
    3993       241252 :   vec<ddr_p> then_ddrs, else_ddrs;
    3994       241252 :   gimple *then_store, *else_store;
    3995       241252 :   bool found, ok = false, res;
    3996       241252 :   tree then_lhs, else_lhs;
    3997       241252 :   basic_block blocks[3];
    3998       241252 :   gphi *vphi = get_virtual_phi (join_bb);
    3999       241252 :   if (!vphi)
    4000              :     return false;
    4001              : 
    4002              :   /* Handle the case with trailing stores in THEN_BB and ELSE_BB.  That is
    4003              :      cheap enough to always handle as it allows us to elide dependence
    4004              :      checking.  */
    4005       240033 :   while (cond_if_else_store_replacement_limited (then_bb, else_bb, join_bb))
    4006              :     ;
    4007              : 
    4008              :   /* If vectorization is disabled then do not sink any stores.  */
    4009       225253 :   if (param_max_stores_to_sink == 0
    4010       225252 :       || (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize))
    4011              :     return false;
    4012              : 
    4013              :   /* Find data references.  */
    4014       219486 :   then_datarefs.create (1);
    4015       219486 :   else_datarefs.create (1);
    4016       219486 :   if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
    4017       219486 :         == chrec_dont_know)
    4018       194166 :       || !then_datarefs.length ()
    4019       187863 :       || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
    4020       187863 :           == chrec_dont_know)
    4021       235355 :       || !else_datarefs.length ())
    4022              :     {
    4023       204788 :       free_data_refs (then_datarefs);
    4024       204788 :       free_data_refs (else_datarefs);
    4025       204788 :       return false;
    4026              :     }
    4027              : 
    4028              :   /* Clear visited on else stores, we want to make sure to pick each store
    4029              :      at most once to avoid quadratic behavior.  */
    4030        67067 :   for (auto else_dr : else_datarefs)
    4031              :     {
    4032        37671 :       if (DR_IS_READ (else_dr))
    4033        19533 :         continue;
    4034        18138 :       gimple_set_visited (DR_STMT (else_dr), false);
    4035              :     }
    4036              : 
    4037              :   /* Find pairs of stores with equal LHS.  Work from the end to avoid
    4038              :      re-ordering stores unnecessarily.  */
    4039        14698 :   auto_vec<std::pair<gimple *, gimple *>, 1> stores_pairs;
    4040        14698 :   unsigned i;
    4041        14698 :   data_reference_p then_dr;
    4042        62013 :   FOR_EACH_VEC_ELT_REVERSE (then_datarefs, i, then_dr)
    4043              :     {
    4044        32617 :       if (DR_IS_READ (then_dr))
    4045        32617 :         continue;
    4046              : 
    4047        19386 :       then_store = DR_STMT (then_dr);
    4048        19386 :       then_lhs = gimple_get_lhs (then_store);
    4049        19386 :       if (then_lhs == NULL_TREE)
    4050            0 :         continue;
    4051        19386 :       found = false;
    4052              : 
    4053        19386 :       unsigned j;
    4054        19386 :       data_reference_p else_dr;
    4055        92011 :       FOR_EACH_VEC_ELT_REVERSE (else_datarefs, j, else_dr)
    4056              :         {
    4057        56737 :           if (DR_IS_READ (else_dr))
    4058        20350 :             continue;
    4059              : 
    4060        36387 :           else_store = DR_STMT (else_dr);
    4061        36387 :           if (gimple_visited_p (else_store))
    4062         3333 :             continue;
    4063        33054 :           else_lhs = gimple_get_lhs (else_store);
    4064        33054 :           if (else_lhs == NULL_TREE)
    4065            0 :             continue;
    4066              : 
    4067        33054 :           if (operand_equal_p (then_lhs, else_lhs, 0))
    4068              :             {
    4069              :               found = true;
    4070              :               break;
    4071              :             }
    4072              :         }
    4073              : 
    4074        19386 :       if (!found)
    4075        15888 :         continue;
    4076              : 
    4077         3498 :       gimple_set_visited (else_store, true);
    4078         3498 :       stores_pairs.safe_push (std::make_pair (then_store, else_store));
    4079              :     }
    4080              : 
    4081              :   /* No pairs of stores found.  */
    4082        14698 :   if (!stores_pairs.length ()
    4083        14698 :       || stores_pairs.length () > (unsigned) param_max_stores_to_sink)
    4084              :     {
    4085        12707 :       free_data_refs (then_datarefs);
    4086        12707 :       free_data_refs (else_datarefs);
    4087        12707 :       return false;
    4088              :     }
    4089              : 
    4090              :   /* Compute and check data dependencies in both basic blocks.  */
    4091         1991 :   then_ddrs.create (1);
    4092         1991 :   else_ddrs.create (1);
    4093         1991 :   if (!compute_all_dependences (then_datarefs, &then_ddrs,
    4094         1991 :                                 vNULL, false)
    4095         3982 :       || !compute_all_dependences (else_datarefs, &else_ddrs,
    4096         1991 :                                    vNULL, false))
    4097              :     {
    4098            0 :       free_dependence_relations (then_ddrs);
    4099            0 :       free_dependence_relations (else_ddrs);
    4100            0 :       free_data_refs (then_datarefs);
    4101            0 :       free_data_refs (else_datarefs);
    4102            0 :       return false;
    4103              :     }
    4104         1991 :   blocks[0] = then_bb;
    4105         1991 :   blocks[1] = else_bb;
    4106         1991 :   blocks[2] = join_bb;
    4107         1991 :   renumber_gimple_stmt_uids_in_blocks (blocks, 3);
    4108              : 
    4109              :   /* Check that there are no read-after-write or write-after-write dependencies
    4110              :      in THEN_BB.  */
    4111        12322 :   for (auto ddr : then_ddrs)
    4112              :     {
    4113         7109 :       struct data_reference *dra = DDR_A (ddr);
    4114         7109 :       struct data_reference *drb = DDR_B (ddr);
    4115              : 
    4116         7109 :       if (DDR_ARE_DEPENDENT (ddr) != chrec_known
    4117         7109 :           && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
    4118          771 :                && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
    4119         1531 :               || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
    4120          495 :                   && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
    4121         1036 :               || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
    4122              :         {
    4123          760 :           free_dependence_relations (then_ddrs);
    4124          760 :           free_dependence_relations (else_ddrs);
    4125          760 :           free_data_refs (then_datarefs);
    4126          760 :           free_data_refs (else_datarefs);
    4127          760 :           return false;
    4128              :         }
    4129              :     }
    4130              : 
    4131              :   /* Check that there are no read-after-write or write-after-write dependencies
    4132              :      in ELSE_BB.  */
    4133         8053 :   for (auto ddr : else_ddrs)
    4134              :     {
    4135         4524 :       struct data_reference *dra = DDR_A (ddr);
    4136         4524 :       struct data_reference *drb = DDR_B (ddr);
    4137              : 
    4138         4524 :       if (DDR_ARE_DEPENDENT (ddr) != chrec_known
    4139         4524 :           && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
    4140          395 :                && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
    4141          559 :               || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
    4142          140 :                   && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
    4143          419 :               || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
    4144              :         {
    4145          164 :           free_dependence_relations (then_ddrs);
    4146          164 :           free_dependence_relations (else_ddrs);
    4147          164 :           free_data_refs (then_datarefs);
    4148          164 :           free_data_refs (else_datarefs);
    4149          164 :           return false;
    4150              :         }
    4151              :     }
    4152              : 
    4153              :   /* Sink stores with same LHS.  */
    4154         4592 :   for (auto &store_pair : stores_pairs)
    4155              :     {
    4156         1391 :       then_store = store_pair.first;
    4157         1391 :       else_store = store_pair.second;
    4158         1391 :       res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
    4159              :                                               then_store, else_store, vphi);
    4160         1391 :       ok = ok || res;
    4161              :     }
    4162              : 
    4163         1067 :   free_dependence_relations (then_ddrs);
    4164         1067 :   free_dependence_relations (else_ddrs);
    4165         1067 :   free_data_refs (then_datarefs);
    4166         1067 :   free_data_refs (else_datarefs);
    4167              : 
    4168         1067 :   return ok;
    4169        14698 : }
    4170              : 
    4171              : /* Returns true when P is based on an induction variable
    4172              :    inside MERGE's inner most loop.  */
    4173              : static bool
    4174         1300 : induction_based (tree p, basic_block merge)
    4175              : {
    4176         1300 :   if (TREE_CODE (p) != SSA_NAME)
    4177              :     return false;
    4178          594 :   tree ev = analyze_scalar_evolution (merge->loop_father, p);
    4179          594 :   if (chrec_contains_undetermined (ev)
    4180          594 :       || chrec_contains_symbols_defined_in_loop (ev, merge->loop_father->num))
    4181              :     return false;
    4182          140 :   if (tree_does_not_contain_chrecs (ev))
    4183              :     return false;
    4184              :   return true;
    4185              : }
    4186              : 
    4187              : /* If PHI at MERGE is a "load PHI", PHI <*P, *Q> whose two arguments are
    4188              :    single-use, non-volatile scalar MEM_REF loads reading the same memory state
    4189              :    (same VUSE), factor the load out: introduce P' = PHI <P, Q> and a single
    4190              :    load *P' replacing the PHI.  No speculative load is introduced (the load uses
    4191              :    whichever pointer the taken edge selected).
    4192              :    E0/E1 are the middle bbs to MERGE edges.
    4193              :    EARLY_P is set when the first phiopt is run.
    4194              :    BEFORE_VECT is true if this is before vectorization, where some extra checks
    4195              :    are needed for profitability.
    4196              :    Returns true if a load was factored out.  */
    4197              : 
    4198              : static bool
    4199       998229 : factor_out_conditional_load (edge e0, edge e1, basic_block merge, gphi *phi,
    4200              :                              bool early_p, bool before_vect)
    4201              : {
    4202              :   /* Not a virtual operand. */
    4203      1294763 :   if (virtual_operand_p (gimple_phi_result (phi))
    4204              :       /* can only handle the merge bb having 2 predecessors.  */
    4205      1294763 :       || gimple_phi_num_args (phi) != 2)
    4206              :     return false;
    4207              : 
    4208       296534 :   tree arg0 = gimple_phi_arg_def (phi, e0->dest_idx);
    4209       296534 :   tree arg1 = gimple_phi_arg_def (phi, e1->dest_idx);
    4210              :   /* The load needs to be only used in the phi.  */
    4211       252483 :   if (TREE_CODE (arg0) != SSA_NAME || TREE_CODE (arg1) != SSA_NAME
    4212       531584 :       || !has_single_use (arg0) || !has_single_use (arg1))
    4213              :     return false;
    4214              : 
    4215              :   /* Re-derive the loads and pointers validated by the predicate above.  */
    4216       125722 :   gimple *load0 = SSA_NAME_DEF_STMT (arg0);
    4217       125722 :   gimple *load1 = SSA_NAME_DEF_STMT (arg1);
    4218              : 
    4219              :   /* Load have to need to be in the middle bbs.  */
    4220       125722 :   if (gimple_bb (load0) != e0->src
    4221       125722 :       || gimple_bb (load1) != e1->src)
    4222              :     return false;
    4223              : 
    4224              :   /* The load needs to be a load with NO volatile ops.  */
    4225       150076 :   if (!gimple_assign_load_p (load0) || !gimple_assign_load_p (load1)
    4226       169490 :       || gimple_has_volatile_ops (load0) || gimple_has_volatile_ops (load1))
    4227              :     return false;
    4228              : 
    4229              :   /* Allow for stores/calls before the load.  */
    4230        25720 :   if (gphi *vphi = get_virtual_phi (merge))
    4231              :     {
    4232        29414 :       if (gimple_vuse (load0) != gimple_phi_arg_def (vphi, e0->dest_idx)
    4233        25595 :           || gimple_vuse (load1) != gimple_phi_arg_def (vphi, e1->dest_idx))
    4234              :         return false;
    4235              :     }
    4236              :   /* Sometimes due to not removing dead statements,
    4237              :      a virtual phi does not show up going into an infinite loop
    4238              :      so just reject that case.  */
    4239        33039 :   else if (gimple_vuse (load0) != gimple_vuse (load1))
    4240              :     return false;
    4241              : 
    4242        21822 :   tree ref0 = gimple_assign_rhs1 (load0);
    4243        21822 :   tree ref1 = gimple_assign_rhs1 (load1);
    4244        21822 :   tree index = nullptr;
    4245        21822 :   tree step = nullptr;
    4246        21822 :   tree index2 = nullptr;
    4247        21822 :   bool rev_order = false;
    4248              : 
    4249              :   /* Both must be *P loads of a compatible value type.  The
    4250              :      TBAA alias-ptr type carried by MEM_REF operand 1 need not match; it is
    4251              :      merged the way get_alias_type_for_stmts does when the load is built.  */
    4252        21822 :   if (TREE_CODE (ref0) == MEM_REF)
    4253         6045 :     rev_order = REF_REVERSE_STORAGE_ORDER (ref0);
    4254              :   else
    4255              :     {
    4256        15777 :       if (TREE_CODE (ref0) != TARGET_MEM_REF)
    4257              :         return false;
    4258          372 :       index = TMR_INDEX (ref0);
    4259          372 :       step = TMR_STEP (ref0);
    4260          372 :       index2 = TMR_INDEX2 (ref0);
    4261              :     }
    4262         6417 :   if (TREE_CODE (ref1) == MEM_REF)
    4263              :     {
    4264         5805 :       if (index || step || index2)
    4265              :         return false;
    4266         5805 :       if (rev_order != REF_REVERSE_STORAGE_ORDER (ref1))
    4267              :         return false;
    4268              :     }
    4269              :   else
    4270              :     {
    4271          612 :       if (TREE_CODE (ref1) != TARGET_MEM_REF)
    4272              :         return false;
    4273          382 :       if (rev_order)
    4274              :         return false;
    4275          382 :       if (!safe_operand_equal_p (index, TMR_INDEX (ref1)))
    4276              :         return false;
    4277          369 :       if (!safe_operand_equal_p (step, TMR_STEP (ref1)))
    4278              :         return false;
    4279          369 :       if (!safe_operand_equal_p (index2, TMR_INDEX2 (ref1)))
    4280              :         return false;
    4281              :     }
    4282              : 
    4283         6159 :   if (!types_compatible_p (TREE_TYPE (ref0), TREE_TYPE (ref1)))
    4284              :     return false;
    4285              : 
    4286              :   /* The alignment of the two accesses need to be the same.  */
    4287         6159 :   if (TYPE_ALIGN (TREE_TYPE (ref0)) != TYPE_ALIGN (TREE_TYPE (ref1)))
    4288              :     return false;
    4289              : 
    4290         5898 :   tree p0 = TREE_OPERAND (ref0, 0);
    4291         5898 :   tree p1 = TREE_OPERAND (ref1, 0);
    4292         5898 :   if (!is_factor_profitable (load0, merge, &p0, 1))
    4293              :     return false;
    4294         5880 :   if (!is_factor_profitable (load1, merge, &p1, 1))
    4295              :     return false;
    4296              : 
    4297              :   /* Merge the two arms' TBAA info as get_alias_type_for_stmts does: keep the
    4298              :      common alias-ptr type and dependence clique/base when the arms agree,
    4299              :      otherwise fall back to ptr_type_node (alias-everything) and drop the
    4300              :      clique/base, so the combined load conservatively conflicts with any store
    4301              :      either original arm could.  */
    4302         5880 :   unsigned short clique = MR_DEPENDENCE_CLIQUE (ref0);
    4303         5880 :   unsigned short base = MR_DEPENDENCE_BASE (ref0);
    4304         5880 :   if (clique != MR_DEPENDENCE_CLIQUE (ref1) || base != MR_DEPENDENCE_BASE (ref1))
    4305              :     clique = base = 0;
    4306         5880 :   tree atype = TREE_TYPE (TREE_OPERAND (ref0, 1));
    4307         5880 :   if (!alias_ptr_types_compatible_p (atype, TREE_TYPE (TREE_OPERAND (ref1, 1))))
    4308              :     {
    4309          640 :       atype = ptr_type_node;
    4310          640 :       clique = base = 0;
    4311              :     }
    4312              : 
    4313         5880 :   tree index0 = TREE_OPERAND (ref0, 1);
    4314         5880 :   tree index1 = TREE_OPERAND (ref1, 1);
    4315         5880 :   tree newindex;
    4316         5880 :   gimple_stmt_iterator gsi;
    4317         5880 :   gsi = gsi_after_labels (merge);
    4318              : 
    4319              :   // factoring of the same pointer should be allowed
    4320              :   // irrespect to loops.
    4321         5880 :   if (p0 == p1 && operand_equal_p (index0, index1))
    4322              :     ;
    4323              :   // Before inlining, we can't tell if different
    4324              :   // pointers are going to be induction variable based
    4325              :   // or not.
    4326         4692 :   else if (early_p)
    4327              :     return false;
    4328              :   // Before vectorization, don't factor out
    4329              :   // pointers which are based on induction variables.
    4330         4147 :   else if (before_vect
    4331         2403 :            && bb_loop_depth (merge) != 0
    4332         4849 :            && (induction_based (p0, merge)
    4333          598 :                || induction_based (p1, merge)))
    4334              :     return false;
    4335              : 
    4336              :   /* Try to handle different indices.  */
    4337         5231 :   if (operand_equal_p (index0, index1))
    4338         4678 :     newindex = fold_convert (atype, index0);
    4339              :   /* FIXME: right now non ssa names with different indices are not handled.  */
    4340          553 :   else if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
    4341              :     return false;
    4342              :   /* If we have the same base already, just create a phi for the index
    4343              :      and the pointer plus will be done in the merge.  */
    4344           87 :   else if (p0 == p1)
    4345              :     {
    4346           60 :       index0 = fold_convert (sizetype, index0);
    4347           60 :       index1 = fold_convert (sizetype, index1);
    4348           60 :       tree index = make_ssa_name (sizetype);
    4349           60 :       gphi *pphi = create_phi_node (index, merge);
    4350           60 :       add_phi_arg (pphi, index0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
    4351           60 :       add_phi_arg (pphi, index1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
    4352           60 :       p0 = gimple_build (&gsi, true, GSI_SAME_STMT,
    4353              :                          UNKNOWN_LOCATION,
    4354              :                          POINTER_PLUS_EXPR, atype, p0, index);
    4355              :       /* Since we already have the same pointer for both, just set that way.
    4356              :          Also the index offset is already 0 because we just did the add.  */
    4357           60 :       p1 = p0;
    4358           60 :       newindex = build_zero_cst (atype);
    4359           60 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4360              :         {
    4361            2 :           fprintf (dump_file, "new PHI ");
    4362            2 :           print_generic_expr (dump_file, index);
    4363            2 :           fprintf (dump_file,
    4364              :                    " was created for the index.\n");
    4365              :         }
    4366              :     }
    4367              :   else
    4368              :     {
    4369           27 :       gimple_stmt_iterator gsi_index;
    4370              :       /* When the indices are different create 2 new pointers on each
    4371              :          of the middle bb right after the original load.
    4372              :          Note in the case of 0 index, gimple_build just returns
    4373              :          the original pointer.  */
    4374           27 :       gsi_index = gsi_for_stmt (load0);
    4375           27 :       index0 = fold_convert (sizetype, index0);
    4376           27 :       p0 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
    4377              :                          gimple_location (load0),
    4378              :                          POINTER_PLUS_EXPR, atype, p0, index0);
    4379              : 
    4380           27 :       gsi_index = gsi_for_stmt (load1);
    4381           27 :       index1 = fold_convert (sizetype, index1);
    4382           27 :       p1 = gimple_build (&gsi_index, false, GSI_SAME_STMT,
    4383              :                          gimple_location (load1),
    4384              :                          POINTER_PLUS_EXPR, atype, p1, index1);
    4385           27 :       newindex = build_zero_cst (atype);
    4386           27 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4387              :         {
    4388            1 :           fprintf (dump_file, "new ptrs ");
    4389            1 :           print_generic_expr (dump_file, p0);
    4390            1 :           fprintf (dump_file, " and ");
    4391            1 :           print_generic_expr (dump_file, p1);
    4392            1 :           fprintf (dump_file,
    4393              :                    " was created due to different offsets.\n");
    4394              :         }
    4395              :     }
    4396              : 
    4397         4765 :   tree newptr;
    4398         4765 :   if (p0 != p1)
    4399              :     {
    4400              :       /* We can't factor out a non-ssa named based load
    4401              :          as it might cause a variable not taken an
    4402              :          address to become needing the address taken.
    4403              :          An example is in go.
    4404              :          Were we produce:
    4405              :          _24 = PHI <&crypto/tls.cipherSuitesPreferenceOrder(36), &crypto/tls.cipherSuitesPreferenceOrderNoAES(37)>
    4406              :          And &crypto/tls.cipherSuitesPreferenceOrder address bit was not set.
    4407              :          FIXME: Refine to check ADDRESSABLE bit.  */
    4408         3517 :       if (TREE_CODE (p0) != SSA_NAME || TREE_CODE (p1) != SSA_NAME)
    4409              :         return false;
    4410              :       // Incompatible address spaces or differnt function pointers could show up here.
    4411          444 :       if (!types_compatible_p (TREE_TYPE (p0), TREE_TYPE (p1)))
    4412              :         return false;
    4413              :       /* Build P' = PHI <P, Q> and the single load result = *P'.  */
    4414          426 :       newptr = make_ssa_name (TREE_TYPE (p0));
    4415          426 :       gphi *pphi = create_phi_node (newptr, merge);
    4416          426 :       add_phi_arg (pphi, p0, e0, gimple_phi_arg_location (phi, e0->dest_idx));
    4417          426 :       add_phi_arg (pphi, p1, e1, gimple_phi_arg_location (phi, e1->dest_idx));
    4418              :     }
    4419              :    else
    4420              :      newptr = p0;
    4421              : 
    4422              :   /* Build the combined load RES = *PTR, reusing the PHI result so any range
    4423              :      info on it is preserved (as factor_out_conditional_operation does).  */
    4424         1674 :   tree nref;
    4425         1674 :   if (index || step || index2)
    4426           28 :     nref = build5 (TARGET_MEM_REF, TREE_TYPE (ref0), newptr,
    4427              :                    newindex, index, step, index2);
    4428              :   else
    4429              :     {
    4430         1646 :       nref = build2 (MEM_REF, TREE_TYPE (ref0), newptr, newindex);
    4431         1646 :       REF_REVERSE_STORAGE_ORDER (nref) = rev_order;
    4432              :     }
    4433         1674 :   MR_DEPENDENCE_CLIQUE (nref) = clique;
    4434         1674 :   MR_DEPENDENCE_BASE (nref) = base;
    4435         1674 :   tree res = gimple_phi_result (phi);
    4436         1674 :   gassign *load = gimple_build_assign (res, nref);
    4437         1674 :   if (gphi *vphi = get_virtual_phi (merge))
    4438         1253 :     gimple_set_vuse (load, gimple_phi_result (vphi));
    4439              :   else
    4440          842 :     gimple_set_vuse (load, gimple_vuse (load0));
    4441         1674 :   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
    4442              : 
    4443              :   /* RES is now defined by the load; drop the original PHI.  */
    4444         1674 :   gsi = gsi_for_stmt (phi);
    4445         1674 :   remove_phi_node (&gsi, false);
    4446              : 
    4447              :   /* The two arm loads are now dead.  */
    4448         1674 :   gsi = gsi_for_stmt (load0);
    4449         1674 :   gsi_remove (&gsi, true);
    4450         1674 :   release_defs (load0);
    4451         1674 :   gsi = gsi_for_stmt (load1);
    4452         1674 :   gsi_remove (&gsi, true);
    4453         1674 :   release_defs (load1);
    4454              : 
    4455         1674 :   if (dump_file && (dump_flags & TDF_DETAILS))
    4456              :     {
    4457           15 :       fprintf (dump_file, "PHI ");
    4458           15 :       print_generic_expr (dump_file, res);
    4459           15 :       fprintf (dump_file,
    4460              :                " changed to factor out load from COND_EXPR.\n");
    4461           15 :       if (p0 != p1)
    4462              :         {
    4463           13 :           fprintf (dump_file, "new PHI ");
    4464           13 :           print_generic_expr (dump_file, newptr);
    4465           13 :           fprintf (dump_file,
    4466              :                    " was created for the pointers.\n");
    4467              :         }
    4468              :     }
    4469              : 
    4470         1674 :   statistics_counter_event (cfun, "factored load out of COND_EXPR", 1);
    4471         1674 :   return true;
    4472              : }
    4473              : 
    4474              : /* Factor out operations and stores from the phi of the MERGE block coming
    4475              :    in from the edges E1 and E2 if possible. COND_STMT is the conditional
    4476              :    statement of the origin block. DIAMOND_P says that both E1 and E2 src
    4477              :    are not the origin block but rather 2 middle BBs. EARLY_P is true if
    4478              :    this was the early phi-opt.
    4479              :    Returns true if a factoring happened. */
    4480              : static bool
    4481      2533586 : factor_out_all (edge e1, edge e2, basic_block merge,
    4482              :                 gcond *cond_stmt, bool diamond_p, bool early_p)
    4483              : {
    4484      2533586 :   bool changed = false;
    4485      2533586 :   bool do_over;
    4486      2533586 :   bool before_vect = !fold_before_rtl_expansion_p ();
    4487              :   // If vectorization is disable, then we are never before the vectorizer.
    4488      2533586 :   if (!flag_tree_loop_vectorize
    4489       191505 :       && !merge->loop_father->force_vectorize)
    4490      2533586 :     before_vect = false;
    4491      2533586 :   basic_block bb1 = e1->src;
    4492      2533586 :   basic_block bb2 = e2->src;
    4493      2511486 :   do
    4494              :     {
    4495      2583609 :       do_over = false;
    4496      2583609 :       if (diamond_p && get_virtual_phi (merge))
    4497              :         {
    4498       717309 :           if (cond_if_else_store_replacement_limited (bb1, bb2, merge))
    4499              :             {
    4500        13645 :               changed = true;
    4501        13645 :               do_over = true;
    4502        19642 :               continue;
    4503              :             }
    4504              :         }
    4505      2569964 :       if (!single_pred_p (bb1))
    4506              :         break;
    4507      1716444 :       if (!diamond_p && get_virtual_phi (merge)
    4508      3523538 :           && cond_store_replacement_limited (bb1, merge, bb2,
    4509              :                                              e1, e2, false))
    4510              :         {
    4511         5997 :           changed = true;
    4512         5997 :           do_over = true;
    4513         5997 :           continue;
    4514              :         }
    4515      2491844 :       gphi_iterator gsi;
    4516      5531146 :       for (gsi = gsi_start_phis (merge); !gsi_end_p (gsi); gsi_next (&gsi))
    4517              :         {
    4518      3069683 :           gphi *phi = *gsi;
    4519              :           /* Conditional load elimination can only be on a diamond.  */
    4520      3069683 :           if ((diamond_p
    4521       998229 :                && factor_out_conditional_load (e1, e2, merge, phi, early_p,
    4522              :                                                before_vect))
    4523      4066238 :               || factor_out_conditional_operation (e1, e2, merge, phi,
    4524              :                                                    cond_stmt, early_p))
    4525              :             {
    4526              :               changed = true;
    4527              :               do_over = true;
    4528              :               break;
    4529              :             }
    4530              :         }
    4531              :     } while (do_over);
    4532      2533586 :   return changed;
    4533              : }
    4534              : 
    4535              : /* Return TRUE if STMT has a VUSE whose corresponding VDEF is in BB.  */
    4536              : 
    4537              : static bool
    4538        12592 : local_mem_dependence (gimple *stmt, basic_block bb)
    4539              : {
    4540        25184 :   tree vuse = gimple_vuse (stmt);
    4541        12592 :   gimple *def;
    4542              : 
    4543        12592 :   if (!vuse)
    4544              :     return false;
    4545              : 
    4546        12592 :   def = SSA_NAME_DEF_STMT (vuse);
    4547        12592 :   return (def && gimple_bb (def) == bb);
    4548              : }
    4549              : 
    4550              : /* Given a "diamond" control-flow pattern where BB0 tests a condition,
    4551              :    BB1 and BB2 are "then" and "else" blocks dependent on this test,
    4552              :    and BB3 rejoins control flow following BB1 and BB2, look for
    4553              :    opportunities to hoist loads as follows.  If BB3 contains a PHI of
    4554              :    two loads, one each occurring in BB1 and BB2, and the loads are
    4555              :    provably of adjacent fields in the same structure, then move both
    4556              :    loads into BB0.  Of course this can only be done if there are no
    4557              :    dependencies preventing such motion.
    4558              : 
    4559              :    One of the hoisted loads will always be speculative, so the
    4560              :    transformation is currently conservative:
    4561              : 
    4562              :     - The fields must be strictly adjacent.
    4563              :     - The two fields must occupy a single memory block that is
    4564              :       guaranteed to not cross a page boundary.
    4565              : 
    4566              :     The last is difficult to prove, as such memory blocks should be
    4567              :     aligned on the minimum of the stack alignment boundary and the
    4568              :     alignment guaranteed by heap allocation interfaces.  Thus we rely
    4569              :     on a parameter for the alignment value.
    4570              : 
    4571              :     Provided a good value is used for the last case, the first
    4572              :     restriction could possibly be relaxed.  */
    4573              : 
    4574              : static void
    4575       601921 : hoist_adjacent_loads (basic_block bb0, basic_block bb1,
    4576              :                       basic_block bb2, basic_block bb3)
    4577              : {
    4578       601921 :   unsigned HOST_WIDE_INT param_align = param_l1_cache_line_size;
    4579       601921 :   unsigned HOST_WIDE_INT param_align_bits = param_align * BITS_PER_UNIT;
    4580       601921 :   gphi_iterator gsi;
    4581              : 
    4582              :   /* Walk the phis in bb3 looking for an opportunity.  We are looking
    4583              :      for phis of two SSA names, one each of which is defined in bb1 and
    4584              :      bb2.  */
    4585      1353188 :   for (gsi = gsi_start_phis (bb3); !gsi_end_p (gsi); gsi_next (&gsi))
    4586              :     {
    4587       751267 :       gphi *phi_stmt = gsi.phi ();
    4588       751267 :       gimple *def1, *def2;
    4589       751267 :       tree arg1, arg2, ref1, ref2, field1, field2;
    4590       751267 :       tree tree_offset1, tree_offset2, tree_size2, next;
    4591       751267 :       unsigned HOST_WIDE_INT offset1, offset2, size2, align1;
    4592       751267 :       gimple_stmt_iterator gsi2;
    4593       751267 :       basic_block bb_for_def1, bb_for_def2;
    4594              : 
    4595       751267 :       if (gimple_phi_num_args (phi_stmt) != 2
    4596      1502534 :           || virtual_operand_p (gimple_phi_result (phi_stmt)))
    4597       744971 :         continue;
    4598              : 
    4599       191789 :       arg1 = gimple_phi_arg_def (phi_stmt, 0);
    4600       191789 :       arg2 = gimple_phi_arg_def (phi_stmt, 1);
    4601              : 
    4602       224271 :       if (TREE_CODE (arg1) != SSA_NAME
    4603       174177 :           || TREE_CODE (arg2) != SSA_NAME
    4604       160558 :           || SSA_NAME_IS_DEFAULT_DEF (arg1)
    4605       352016 :           || SSA_NAME_IS_DEFAULT_DEF (arg2))
    4606        32482 :         continue;
    4607              : 
    4608       159307 :       def1 = SSA_NAME_DEF_STMT (arg1);
    4609       159307 :       def2 = SSA_NAME_DEF_STMT (arg2);
    4610              : 
    4611       159307 :       if ((gimple_bb (def1) != bb1 || gimple_bb (def2) != bb2)
    4612       173097 :           && (gimple_bb (def2) != bb1 || gimple_bb (def1) != bb2))
    4613        41241 :         continue;
    4614              : 
    4615              :       /* Check the mode of the arguments to be sure a conditional move
    4616              :          can be generated for it.  */
    4617       236132 :       if (optab_handler (movcc_optab, TYPE_MODE (TREE_TYPE (arg1)))
    4618              :           == CODE_FOR_nothing)
    4619         5009 :         continue;
    4620              : 
    4621              :       /* Both statements must be assignments whose RHS is a COMPONENT_REF.  */
    4622       113057 :       if (!gimple_assign_single_p (def1)
    4623        52863 :           || !gimple_assign_single_p (def2)
    4624        70520 :           || gimple_has_volatile_ops (def1)
    4625       183531 :           || gimple_has_volatile_ops (def2))
    4626        77820 :         continue;
    4627              : 
    4628        35237 :       ref1 = gimple_assign_rhs1 (def1);
    4629        35237 :       ref2 = gimple_assign_rhs1 (def2);
    4630              : 
    4631        35237 :       if (TREE_CODE (ref1) != COMPONENT_REF
    4632        24467 :           || TREE_CODE (ref2) != COMPONENT_REF)
    4633        10940 :         continue;
    4634              : 
    4635              :       /* The zeroth operand of the two component references must be
    4636              :          identical.  It is not sufficient to compare get_base_address of
    4637              :          the two references, because this could allow for different
    4638              :          elements of the same array in the two trees.  It is not safe to
    4639              :          assume that the existence of one array element implies the
    4640              :          existence of a different one.  */
    4641        24297 :       if (!operand_equal_p (TREE_OPERAND (ref1, 0), TREE_OPERAND (ref2, 0), 0))
    4642         4647 :         continue;
    4643              : 
    4644        19650 :       field1 = TREE_OPERAND (ref1, 1);
    4645        19650 :       field2 = TREE_OPERAND (ref2, 1);
    4646              : 
    4647              :       /* Check for field adjacency, and ensure field1 comes first.  */
    4648        19650 :       for (next = DECL_CHAIN (field1);
    4649        34323 :            next && TREE_CODE (next) != FIELD_DECL;
    4650        14673 :            next = DECL_CHAIN (next))
    4651              :         ;
    4652              : 
    4653        19650 :       if (next != field2)
    4654              :         {
    4655        15926 :           for (next = DECL_CHAIN (field2);
    4656        17965 :                next && TREE_CODE (next) != FIELD_DECL;
    4657         2039 :                next = DECL_CHAIN (next))
    4658              :             ;
    4659              : 
    4660        15926 :           if (next != field1)
    4661        13354 :             continue;
    4662              : 
    4663              :           std::swap (field1, field2);
    4664              :           std::swap (def1, def2);
    4665              :         }
    4666              : 
    4667         6296 :       bb_for_def1 = gimple_bb (def1);
    4668         6296 :       bb_for_def2 = gimple_bb (def2);
    4669              : 
    4670              :       /* Check for proper alignment of the first field.  */
    4671         6296 :       tree_offset1 = bit_position (field1);
    4672         6296 :       tree_offset2 = bit_position (field2);
    4673         6296 :       tree_size2 = DECL_SIZE (field2);
    4674              : 
    4675         6296 :       if (!tree_fits_uhwi_p (tree_offset1)
    4676         6296 :           || !tree_fits_uhwi_p (tree_offset2)
    4677         6296 :           || !tree_fits_uhwi_p (tree_size2))
    4678            0 :         continue;
    4679              : 
    4680         6296 :       offset1 = tree_to_uhwi (tree_offset1);
    4681         6296 :       offset2 = tree_to_uhwi (tree_offset2);
    4682         6296 :       size2 = tree_to_uhwi (tree_size2);
    4683         6296 :       align1 = DECL_ALIGN (field1) % param_align_bits;
    4684              : 
    4685         6296 :       if (offset1 % BITS_PER_UNIT != 0)
    4686            0 :         continue;
    4687              : 
    4688              :       /* For profitability, the two field references should fit within
    4689              :          a single cache line.  */
    4690         6296 :       if (align1 + offset2 - offset1 + size2 > param_align_bits)
    4691            0 :         continue;
    4692              : 
    4693              :       /* The two expressions cannot be dependent upon vdefs defined
    4694              :          in bb1/bb2.  */
    4695         6296 :       if (local_mem_dependence (def1, bb_for_def1)
    4696         6296 :           || local_mem_dependence (def2, bb_for_def2))
    4697            0 :         continue;
    4698              : 
    4699              :       /* The conditions are satisfied; hoist the loads from bb1 and bb2 into
    4700              :          bb0.  We hoist the first one first so that a cache miss is handled
    4701              :          efficiently regardless of hardware cache-fill policy.  */
    4702         6296 :       gsi2 = gsi_for_stmt (def1);
    4703         6296 :       gsi_move_to_bb_end (&gsi2, bb0);
    4704         6296 :       gsi2 = gsi_for_stmt (def2);
    4705         6296 :       gsi_move_to_bb_end (&gsi2, bb0);
    4706              :       /* Clear range info from the defs we've moved from under the
    4707              :          condition.  */
    4708         6296 :       reset_flow_sensitive_info (gimple_assign_lhs (def1));
    4709         6296 :       reset_flow_sensitive_info (gimple_assign_lhs (def2));
    4710         6296 :       statistics_counter_event (cfun, "hoisted loads", 1);
    4711              : 
    4712         6296 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4713              :         {
    4714            0 :           fprintf (dump_file,
    4715              :                    "\nHoisting adjacent loads from %d and %d into %d: \n",
    4716              :                    bb_for_def1->index, bb_for_def2->index, bb0->index);
    4717            0 :           print_gimple_stmt (dump_file, def1, 0, TDF_VOPS|TDF_MEMSYMS);
    4718            0 :           print_gimple_stmt (dump_file, def2, 0, TDF_VOPS|TDF_MEMSYMS);
    4719              :         }
    4720              :     }
    4721       601921 : }
    4722              : 
    4723              : /* Determine whether we should attempt to hoist adjacent loads out of
    4724              :    diamond patterns in pass_phiopt.  Always hoist loads if
    4725              :    -fhoist-adjacent-loads is specified and the target machine has
    4726              :    both a conditional move instruction and a defined cache line size.  */
    4727              : 
    4728              : static bool
    4729      3188527 : gate_hoist_loads (void)
    4730              : {
    4731      3188527 :   return (flag_hoist_adjacent_loads == 1
    4732      3188527 :           && param_l1_cache_line_size
    4733            0 :           && HAVE_conditional_move);
    4734              : }
    4735              : 
    4736              : template <class func_type>
    4737              : static void
    4738      6773174 : execute_over_cond_phis (func_type func)
    4739              : {
    4740              :   unsigned n, i;
    4741              :   basic_block *bb_order;
    4742              :   basic_block bb;
    4743              :   /* Search every basic block for COND_EXPR we may be able to optimize.
    4744              : 
    4745              :      We walk the blocks in order that guarantees that a block with
    4746              :      a single predecessor is processed before the predecessor.
    4747              :      This ensures that we collapse inner ifs before visiting the
    4748              :      outer ones, and also that we do not try to visit a removed
    4749              :      block.  */
    4750      6773174 :   bb_order = single_pred_before_succ_order ();
    4751      6773174 :   n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
    4752              : 
    4753     61885037 :   for (i = 0; i < n; i++)
    4754              :     {
    4755              :       basic_block bb1, bb2;
    4756              :       edge e1, e2;
    4757     55111863 :       bool diamond_p = false;
    4758              : 
    4759     55111863 :       bb = bb_order[i];
    4760              : 
    4761              :       /* Check to see if the last statement is a GIMPLE_COND.  */
    4762     55111863 :       gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
    4763     33398820 :       if (!cond_stmt)
    4764     55111863 :         continue;
    4765              : 
    4766     21713043 :       e1 = EDGE_SUCC (bb, 0);
    4767     21713043 :       bb1 = e1->dest;
    4768     21713043 :       e2 = EDGE_SUCC (bb, 1);
    4769     21713043 :       bb2 = e2->dest;
    4770              : 
    4771              :       /* We cannot do the optimization on abnormal edges.  */
    4772     21713043 :       if ((e1->flags & EDGE_ABNORMAL) != 0
    4773     21713043 :           || (e2->flags & EDGE_ABNORMAL) != 0)
    4774            0 :         continue;
    4775              : 
    4776              :       /* If either bb1's succ or bb2 or bb2's succ is non NULL.  */
    4777     21713043 :       if (EDGE_COUNT (bb1->succs) == 0
    4778     20359519 :           || EDGE_COUNT (bb2->succs) == 0)
    4779      4974829 :         continue;
    4780              : 
    4781              :       /* Find the bb which is the fall through to the other.  */
    4782     16738214 :       if (EDGE_SUCC (bb1, 0)->dest == bb2)
    4783              :         ;
    4784     14232185 :       else if (EDGE_SUCC (bb2, 0)->dest == bb1)
    4785              :         {
    4786              :           std::swap (bb1, bb2);
    4787              :           std::swap (e1, e2);
    4788              :         }
    4789     10956747 :       else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
    4790     12530173 :                && single_succ_p (bb2))
    4791              :         {
    4792      1573426 :           diamond_p = true;
    4793      1573426 :           e2 = EDGE_SUCC (bb2, 0);
    4794              :           /* Make sure bb2 is just a fall through. */
    4795      1573426 :           if ((e2->flags & EDGE_FALLTHRU) == 0)
    4796        52001 :             continue;
    4797              :         }
    4798              :       else
    4799     10956747 :         continue;
    4800              : 
    4801      5729466 :       e1 = EDGE_SUCC (bb1, 0);
    4802              : 
    4803              :       /* Make sure that bb1 is just a fall through.  */
    4804      5729466 :       if (!single_succ_p (bb1)
    4805      5729466 :           || (e1->flags & EDGE_FALLTHRU) == 0)
    4806      1276701 :         continue;
    4807              : 
    4808      4452765 :       func (bb, bb1, bb2, e1, e2, diamond_p, cond_stmt);
    4809              :     }
    4810      6773174 :   free (bb_order);
    4811      6773174 : }
    4812              : 
    4813              : /* This pass tries to replaces an if-then-else block with an
    4814              :    assignment.  We have different kinds of transformations.
    4815              :    Some of these transformations are also performed by the ifcvt
    4816              :    RTL optimizer.
    4817              : 
    4818              :    PHI-OPT using Match-and-simplify infrastructure
    4819              :    -----------------------
    4820              : 
    4821              :    The PHI-OPT pass will try to use match-and-simplify infrastructure
    4822              :    (gimple_simplify) to do transformations. This is implemented in
    4823              :    match_simplify_replacement.
    4824              : 
    4825              :    The way it works is it replaces:
    4826              :      bb0:
    4827              :       if (cond) goto bb2; else goto bb1;
    4828              :      bb1:
    4829              :      bb2:
    4830              :       x = PHI <a (bb1), b (bb0), ...>;
    4831              : 
    4832              :    with a statement if it gets simplified from `cond ? b : a`.
    4833              : 
    4834              :      bb0:
    4835              :       x1 = cond ? b : a;
    4836              :      bb2:
    4837              :       x = PHI <a (bb1), x1 (bb0), ...>;
    4838              :    Bb1 might be removed as it becomes unreachable when doing the replacement.
    4839              :    Though bb1 does not have to be considered a forwarding basic block from bb0.
    4840              : 
    4841              :    Will try to see if `(!cond) ? a : b` gets simplified (iff !cond simplifies);
    4842              :    this is done not to have an explosion of patterns in match.pd.
    4843              :    Note bb1 does not need to be completely empty, it can contain
    4844              :    one statement which is known not to trap.
    4845              : 
    4846              :    It also can handle the case where we have two forwarding bbs (diamond):
    4847              :      bb0:
    4848              :       if (cond) goto bb2; else goto bb1;
    4849              :      bb1: goto bb3;
    4850              :      bb2: goto bb3;
    4851              :      bb3:
    4852              :       x = PHI <a (bb1), b (bb2), ...>;
    4853              :    And that is replaced with a statement if it is simplified
    4854              :    from `cond ? b : a`.
    4855              :    Again bb1 and bb2 does not have to be completely empty but
    4856              :    each can contain one statement which is known not to trap.
    4857              :    But in this case bb1/bb2 can only be forwarding basic blocks.
    4858              : 
    4859              :    This fully replaces the old "Conditional Replacement",
    4860              :    "ABS Replacement" and "MIN/MAX Replacement" transformations as they are now
    4861              :    implemented in match.pd.
    4862              : 
    4863              :    Value Replacement
    4864              :    -----------------
    4865              : 
    4866              :    This transformation, implemented in value_replacement, replaces
    4867              : 
    4868              :      bb0:
    4869              :        if (a != b) goto bb2; else goto bb1;
    4870              :      bb1:
    4871              :      bb2:
    4872              :        x = PHI <a (bb1), b (bb0), ...>;
    4873              : 
    4874              :    with
    4875              : 
    4876              :      bb0:
    4877              :      bb2:
    4878              :        x = PHI <b (bb0), ...>;
    4879              : 
    4880              :    This opportunity can sometimes occur as a result of other
    4881              :    optimizations.
    4882              : 
    4883              : 
    4884              :    Another case caught by value replacement looks like this:
    4885              : 
    4886              :      bb0:
    4887              :        t1 = a == CONST;
    4888              :        t2 = b > c;
    4889              :        t3 = t1 & t2;
    4890              :        if (t3 != 0) goto bb1; else goto bb2;
    4891              :      bb1:
    4892              :      bb2:
    4893              :        x = PHI (CONST, a)
    4894              : 
    4895              :    Gets replaced with:
    4896              :      bb0:
    4897              :      bb2:
    4898              :        t1 = a == CONST;
    4899              :        t2 = b > c;
    4900              :        t3 = t1 & t2;
    4901              :        x = a;
    4902              : 
    4903              : 
    4904              :    This pass also performs a fifth transformation of a slightly different
    4905              :    flavor.
    4906              : 
    4907              :    Factor operations in COND_EXPR
    4908              :    ------------------------------
    4909              : 
    4910              :    This transformation factors the unary operations out of COND_EXPR with
    4911              :    factor_out_conditional_operation.
    4912              : 
    4913              :    For example:
    4914              :    if (a <= CST) goto <bb 3>; else goto <bb 4>;
    4915              :    <bb 3>:
    4916              :    tmp = (int) a;
    4917              :    <bb 4>:
    4918              :    tmp = PHI <tmp, CST>
    4919              : 
    4920              :    Into:
    4921              :    if (a <= CST) goto <bb 3>; else goto <bb 4>;
    4922              :    <bb 3>:
    4923              :    <bb 4>:
    4924              :    a = PHI <a, CST>
    4925              :    tmp = (int) a;
    4926              : 
    4927              :    Adjacent Load Hoisting
    4928              :    ----------------------
    4929              : 
    4930              :    This transformation replaces
    4931              : 
    4932              :      bb0:
    4933              :        if (...) goto bb2; else goto bb1;
    4934              :      bb1:
    4935              :        x1 = (<expr>).field1;
    4936              :        goto bb3;
    4937              :      bb2:
    4938              :        x2 = (<expr>).field2;
    4939              :      bb3:
    4940              :        # x = PHI <x1, x2>;
    4941              : 
    4942              :    with
    4943              : 
    4944              :      bb0:
    4945              :        x1 = (<expr>).field1;
    4946              :        x2 = (<expr>).field2;
    4947              :        if (...) goto bb2; else goto bb1;
    4948              :      bb1:
    4949              :        goto bb3;
    4950              :      bb2:
    4951              :      bb3:
    4952              :        # x = PHI <x1, x2>;
    4953              : 
    4954              :    The purpose of this transformation is to enable generation of conditional
    4955              :    move instructions such as Intel CMOVE or PowerPC ISEL.  Because one of
    4956              :    the loads is speculative, the transformation is restricted to very
    4957              :    specific cases to avoid introducing a page fault.  We are looking for
    4958              :    the common idiom:
    4959              : 
    4960              :      if (...)
    4961              :        x = y->left;
    4962              :      else
    4963              :        x = y->right;
    4964              : 
    4965              :    where left and right are typically adjacent pointers in a tree structure.  */
    4966              : 
    4967              : /* Replicate the join block at E's destination into E's source.  The copy's
    4968              :    PHIs degenerate to their argument on E, so the copied conditional tests the
    4969              :    predecessor's own value.  The net effect after cleanups, for edge (3, 5)
    4970              :    would be:
    4971              : 
    4972              :      <bb 3>:                              <bb 3>:
    4973              :      t_9 = a < b;                    t_9 = a < b;
    4974              :      goto <bb 5>;                 if (t_9 != 0)
    4975              : 
    4976              :      <bb 4>:                      ->   <bb 4>:
    4977              :      t_6 = c < d;                    t_6 = c < d;
    4978              :      goto <bb 5>;                 goto <bb 5>;
    4979              : 
    4980              :      <bb 5>:                              <bb 5>:
    4981              :      # t_1 = PHI <t_9(3), t_6(4)> # t_1 = PHI <t_6(4)>
    4982              :      if (t_1 != 0)                      if (t_1 != 0)
    4983              : 
    4984              :    Return TRUE if the replication was performed.  */
    4985              : 
    4986              : static bool
    4987        51004 : replicate_cond_into_pred (edge e)
    4988              : {
    4989        51004 :   basic_block bb = e->dest;
    4990              : 
    4991        51004 :   if (!can_duplicate_block_on_edge_p (e))
    4992              :     return false;
    4993              : 
    4994        51004 :   if (dump_file && (dump_flags & TDF_DETAILS))
    4995            2 :     fprintf (dump_file,
    4996              :              "replicating conditional in bb%d into predecessor bb%d\n",
    4997            2 :              bb->index, e->src->index);
    4998              : 
    4999        51004 :   basic_block copy = duplicate_block (bb, e, e->src);
    5000        51004 :   flush_pending_stmts (e);
    5001        51004 :   add_phi_args_after_copy (&copy, 1, NULL);
    5002        51004 :   return true;
    5003              : }
    5004              : 
    5005              : /* Replicate conditionals over a PHI of comparisons into the
    5006              :    qualifying predecessors of every join block in the function, so
    5007              :    each arm branches directly on its own comparison instead of merging
    5008              :    into a boolean that is tested again:
    5009              : 
    5010              :      <bb 3>:                      <bb 3>:
    5011              :      t_9 = a < b;            t_9 = a < b;
    5012              :      goto <bb 5>;         if (t_9 != 0)
    5013              : 
    5014              :      <bb 4>:              ->   <bb 4>:
    5015              :      t_6 = c < d;            t_6 = c < d;
    5016              :      goto <bb 5>;         if (t_6 != 0)
    5017              : 
    5018              :      <bb 5>:
    5019              :      # t_1 = PHI <t_9(3), t_6(4)>
    5020              :      if (t_1 != 0)
    5021              : */
    5022              : 
    5023              : static bool
    5024      5710318 : replicate_conds_over_phis (void)
    5025              : {
    5026      5710318 :   bool cfgchanged = false;
    5027      5710318 :   basic_block bb;
    5028              : 
    5029      5710318 :   initialize_original_copy_tables ();
    5030     49915997 :   FOR_EACH_BB_FN (bb, cfun)
    5031              :     {
    5032     44205679 :       gcond *cond;
    5033     44205679 :       gphi *phi;
    5034              :       /* Never duplicate loop headers.  */
    5035     88176426 :       if (bb->loop_father->header == bb
    5036     41472839 :           || EDGE_COUNT (bb->preds) < 2
    5037     51906829 :           || !cond_on_phi_p (bb, &cond, &phi))
    5038     43970747 :         continue;
    5039              : 
    5040       234932 :       edge e;
    5041       234932 :       edge_iterator ei = ei_start (bb->preds);
    5042       763598 :       while ((e = ei_safe_edge (ei)))
    5043              :         {
    5044       528666 :           if (phi_arg_from_cmp_p (phi, e)
    5045       528666 :               && replicate_cond_into_pred (e))
    5046              :             cfgchanged = true;
    5047              :           else
    5048       477662 :             ei_next (&ei);
    5049              :         }
    5050              :     }
    5051      5710318 :   free_original_copy_tables ();
    5052              : 
    5053              :   /* Removing an entry of an irreducible region can make it reducible, creating
    5054              :      a new loop.  */
    5055      5710318 :   if (cfgchanged)
    5056        25457 :     loops_state_set (LOOPS_NEED_FIXUP);
    5057              : 
    5058      5710318 :   return cfgchanged;
    5059              : }
    5060              : 
    5061              : namespace {
    5062              : 
    5063              : const pass_data pass_data_phiopt =
    5064              : {
    5065              :   GIMPLE_PASS, /* type */
    5066              :   "phiopt", /* name */
    5067              :   OPTGROUP_NONE, /* optinfo_flags */
    5068              :   TV_TREE_PHIOPT, /* tv_id */
    5069              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    5070              :   0, /* properties_provided */
    5071              :   0, /* properties_destroyed */
    5072              :   0, /* todo_flags_start */
    5073              :   0, /* todo_flags_finish */
    5074              : };
    5075              : 
    5076              : class pass_phiopt : public gimple_opt_pass
    5077              : {
    5078              : public:
    5079      1188720 :   pass_phiopt (gcc::context *ctxt)
    5080      2377440 :     : gimple_opt_pass (pass_data_phiopt, ctxt), early_p (false)
    5081              :   {}
    5082              : 
    5083              :   /* opt_pass methods: */
    5084       891540 :   opt_pass * clone () final override { return new pass_phiopt (m_ctxt); }
    5085      1188720 :   void set_pass_param (unsigned n, bool param) final override
    5086              :     {
    5087      1188720 :       gcc_assert (n == 0);
    5088      1188720 :       early_p = param;
    5089      1188720 :     }
    5090      5713771 :   bool gate (function *) final override { return flag_ssa_phiopt; }
    5091              :   unsigned int execute (function *) final override;
    5092              : 
    5093              : private:
    5094              :   bool early_p;
    5095              : }; // class pass_phiopt
    5096              : 
    5097              : } // anon namespace
    5098              : 
    5099              : gimple_opt_pass *
    5100       297180 : make_pass_phiopt (gcc::context *ctxt)
    5101              : {
    5102       297180 :   return new pass_phiopt (ctxt);
    5103              : }
    5104              : 
    5105              : unsigned int
    5106      5710318 : pass_phiopt::execute (function *)
    5107              : {
    5108      5710318 :   bool do_hoist_loads = !early_p ? gate_hoist_loads () : false;
    5109      5710318 :   bool cfgchanged = false;
    5110      5710318 :   bool need_loop_finalize = false;
    5111              : 
    5112      5710318 :   if (!early_p
    5113      3188527 :       && !fold_before_rtl_expansion_p ()
    5114      2126125 :       && (flag_tree_loop_vectorize
    5115       274802 :           || cfun->has_force_vectorize_loops)
    5116      9420972 :       && number_of_loops (cfun) > 1)
    5117              :   {
    5118       426753 :     loop_optimizer_init (LOOPS_NORMAL);
    5119       426753 :     scev_initialize ();
    5120       426753 :     need_loop_finalize = true;
    5121              :   }
    5122              : 
    5123      5710318 :   calculate_dominance_info (CDI_DOMINATORS);
    5124      5710318 :   mark_ssa_maybe_undefs ();
    5125              : 
    5126      9231340 :   auto phiopt_exec = [&] (basic_block bb, basic_block bb1,
    5127              :                           basic_block bb2, edge e1, edge e2,
    5128              :                           bool diamond_p, gcond *cond_stmt)
    5129              :     {
    5130      3521022 :       if (diamond_p)
    5131              :         {
    5132      1126776 :           basic_block bb3 = e1->dest;
    5133              : 
    5134      1126776 :           if (!single_pred_p (bb1)
    5135      2192658 :               || !single_pred_p (bb2))
    5136      3521022 :             return;
    5137              : 
    5138      1007070 :           if (do_hoist_loads
    5139       791327 :               && !FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond_stmt)))
    5140       783182 :               && EDGE_COUNT (bb->succs) == 2
    5141       783182 :               && EDGE_COUNT (bb3->preds) == 2
    5142              :               /* If one edge or the other is dominant, a conditional move
    5143              :                  is likely to perform worse than the well-predicted branch.  */
    5144       606530 :               && !predictable_edge_p (EDGE_SUCC (bb, 0))
    5145      1608991 :               && !predictable_edge_p (EDGE_SUCC (bb, 1)))
    5146       601921 :             hoist_adjacent_loads (bb, bb1, bb2, bb3);
    5147              :         }
    5148              : 
    5149      1007070 :       gimple_stmt_iterator gsi;
    5150              : 
    5151              :       /* Check that we're looking for nested phis.  */
    5152      1007070 :       basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
    5153              : 
    5154              :       /* Factor out operations from the phi if possible. */
    5155      3401316 :       if (EDGE_COUNT (merge->preds) == 2
    5156      3401316 :           && !optimize_debug && factor_out_all (e1, e2, merge, cond_stmt, diamond_p, early_p))
    5157        43134 :         cfgchanged = true;
    5158              : 
    5159      3401316 :       gimple_seq phis = phi_nodes (merge);
    5160              : 
    5161      3401316 :       if (gimple_seq_empty_p (phis))
    5162              :         return;
    5163              : 
    5164              :       /* Value replacement can work with more than one PHI
    5165              :          so try that first. */
    5166      3387034 :       if (!early_p && !diamond_p)
    5167      4241701 :         for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
    5168              :           {
    5169      2475691 :             gphi *phi = as_a <gphi *> (gsi_stmt (gsi));
    5170      2475691 :             tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
    5171      2475691 :             tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
    5172      2475691 :             if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1) == 2)
    5173              :               {
    5174         2011 :                 cfgchanged = true;
    5175         2011 :                 return;
    5176              :               }
    5177              :           }
    5178              : 
    5179      3385023 :       gphi *phi = single_non_singleton_phi_for_edges (phis, e1, e2);
    5180      3385023 :       if (!phi)
    5181              :         return;
    5182              : 
    5183       858172 :       tree arg0 = gimple_phi_arg_def (phi, e1->dest_idx);
    5184       858172 :       tree arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
    5185              : 
    5186              :       /* Something is wrong if we cannot find the arguments in the PHI
    5187              :           node.  */
    5188       858172 :       gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
    5189              : 
    5190              : 
    5191              :       /* Do the replacement of conditional if it can be done.  */
    5192       858172 :       if (match_simplify_replacement (bb, bb1, bb2, e1, e2, phi,
    5193              :                                       arg0, arg1, early_p, diamond_p))
    5194        95764 :         cfgchanged = true;
    5195       762408 :       else if (comparison_combine (bb, bb1, bb2, e1, e2, phi,
    5196              :                                    arg0, arg1, diamond_p))
    5197           16 :         cfgchanged = true;
    5198       762392 :       else if (!early_p
    5199       500010 :                && !diamond_p
    5200       466771 :                && single_pred_p (bb1)
    5201      1208385 :                && cond_removal_in_builtin_zero_pattern (bb, bb1, e1, e2,
    5202              :                                                         phi, arg0, arg1))
    5203           13 :         cfgchanged = true;
    5204       762379 :       else if (single_pred_p (bb1)
    5205       711015 :                && !diamond_p
    5206      1410592 :                && spaceship_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
    5207         2364 :         cfgchanged = true;
    5208      5710318 :     };
    5209              : 
    5210      5710318 :   execute_over_cond_phis (phiopt_exec);
    5211              : 
    5212      5710318 :   if (need_loop_finalize)
    5213              :     {
    5214       426753 :       loop_optimizer_finalize ();
    5215       426753 :       scev_finalize ();
    5216              :     }
    5217      5710318 :   if (replicate_conds_over_phis ())
    5218              :     {
    5219        25457 :       free_dominance_info (CDI_DOMINATORS);
    5220        25457 :       return TODO_cleanup_cfg | TODO_update_ssa;
    5221              :     }
    5222              : 
    5223      5684861 :   if (cfgchanged)
    5224        85270 :     return TODO_cleanup_cfg;
    5225              :   return 0;
    5226              : }
    5227              : 
    5228              : /* This pass tries to transform conditional stores into unconditional
    5229              :    ones, enabling further simplifications with the simpler then and else
    5230              :    blocks.  In particular it replaces this:
    5231              : 
    5232              :      bb0:
    5233              :        if (cond) goto bb2; else goto bb1;
    5234              :      bb1:
    5235              :        *p = RHS;
    5236              :      bb2:
    5237              : 
    5238              :    with
    5239              : 
    5240              :      bb0:
    5241              :        if (cond) goto bb1; else goto bb2;
    5242              :      bb1:
    5243              :        condtmp' = *p;
    5244              :      bb2:
    5245              :        condtmp = PHI <RHS, condtmp'>
    5246              :        *p = condtmp;
    5247              : 
    5248              :    This transformation can only be done under several constraints,
    5249              :    documented below.  It also replaces:
    5250              : 
    5251              :      bb0:
    5252              :        if (cond) goto bb2; else goto bb1;
    5253              :      bb1:
    5254              :        *p = RHS1;
    5255              :        goto bb3;
    5256              :      bb2:
    5257              :        *p = RHS2;
    5258              :      bb3:
    5259              : 
    5260              :    with
    5261              : 
    5262              :      bb0:
    5263              :        if (cond) goto bb3; else goto bb1;
    5264              :      bb1:
    5265              :      bb3:
    5266              :        condtmp = PHI <RHS1, RHS2>
    5267              :        *p = condtmp;  */
    5268              : 
    5269              : namespace {
    5270              : 
    5271              : const pass_data pass_data_cselim =
    5272              : {
    5273              :   GIMPLE_PASS, /* type */
    5274              :   "cselim", /* name */
    5275              :   OPTGROUP_NONE, /* optinfo_flags */
    5276              :   TV_TREE_PHIOPT, /* tv_id */
    5277              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    5278              :   0, /* properties_provided */
    5279              :   0, /* properties_destroyed */
    5280              :   0, /* todo_flags_start */
    5281              :   0, /* todo_flags_finish */
    5282              : };
    5283              : 
    5284              : class pass_cselim : public gimple_opt_pass
    5285              : {
    5286              : public:
    5287       297180 :   pass_cselim (gcc::context *ctxt)
    5288       594360 :     : gimple_opt_pass (pass_data_cselim, ctxt)
    5289              :   {}
    5290              : 
    5291              :   /* opt_pass methods: */
    5292      1063018 :   bool gate (function *) final override { return flag_tree_cselim; }
    5293              :   unsigned int execute (function *) final override;
    5294              : 
    5295              : }; // class pass_cselim
    5296              : 
    5297              : } // anon namespace
    5298              : 
    5299              : gimple_opt_pass *
    5300       297180 : make_pass_cselim (gcc::context *ctxt)
    5301              : {
    5302       297180 :   return new pass_cselim (ctxt);
    5303              : }
    5304              : 
    5305              : unsigned int
    5306      1062856 : pass_cselim::execute (function *)
    5307              : {
    5308      1062856 :   bool cfgchanged = false;
    5309      1062856 :   hash_set<tree> *nontrap = 0;
    5310      1062856 :   unsigned todo = 0;
    5311              : 
    5312              :   /* ???  We are not interested in loop related info, but the following
    5313              :      will create it, ICEing as we didn't init loops with pre-headers.
    5314              :      An interfacing issue of find_data_references_in_bb.  */
    5315      1062856 :   loop_optimizer_init (LOOPS_NORMAL);
    5316      1062856 :   scev_initialize ();
    5317              : 
    5318      1062856 :   calculate_dominance_info (CDI_DOMINATORS);
    5319              : 
    5320              :   /* Calculate the set of non-trapping memory accesses.  */
    5321      1062856 :   nontrap = get_non_trapping ();
    5322              : 
    5323      1994599 :   auto cselim_exec = [&] (basic_block bb, basic_block bb1,
    5324              :                           basic_block bb2, edge e1, edge e2,
    5325              :                           bool diamond_p, gcond *)
    5326              :     {
    5327       931743 :       if (diamond_p)
    5328              :         {
    5329       325998 :           basic_block bb3 = e1->dest;
    5330              : 
    5331              :           /* Only handle sinking of store from 2 bbs only,
    5332              :              The middle bbs don't need to come from the
    5333              :              if always since we are sinking rather than
    5334              :              hoisting. */
    5335       325998 :           if (EDGE_COUNT (bb3->preds) != 2)
    5336              :             return;
    5337       241252 :           if (cond_if_else_store_replacement (bb1, bb2, bb3))
    5338          789 :             cfgchanged = true;
    5339              :           return;
    5340              :         }
    5341              : 
    5342              :       /* Also make sure that bb1 only have one predecessor and that it
    5343              :          is bb.  */
    5344       605745 :       if (!single_pred_p (bb1)
    5345      1163588 :           || single_pred (bb1) != bb)
    5346              :         return;
    5347              : 
    5348              :       /* bb1 is the middle block, bb2 the join block, bb the split block,
    5349              :          e1 the fallthrough edge from bb1 to bb2.  We can't do the
    5350              :          optimization if the join block has more than two predecessors.  */
    5351       557843 :       if (EDGE_COUNT (bb2->preds) > 2)
    5352              :         return;
    5353              : 
    5354       431645 :       if (cond_store_replacement_limited (bb1, bb2, bb, e1, e2, true))
    5355              :         {
    5356          963 :           cfgchanged = true;
    5357          963 :           return;
    5358              :         }
    5359       430682 :       gimple *assign = cselim_candidate (bb1, bb2, e1);
    5360       430682 :       if (cond_store_replacement (bb1, bb2, e1, e2, assign, nontrap))
    5361          178 :         cfgchanged = true;
    5362      1062856 :     };
    5363              : 
    5364      1062856 :   execute_over_cond_phis (cselim_exec);
    5365              : 
    5366      2125712 :   delete nontrap;
    5367              :   /* If the CFG has changed, we should cleanup the CFG.  */
    5368      1062856 :   if (cfgchanged)
    5369              :     {
    5370         1420 :       gsi_commit_edge_inserts ();
    5371         1420 :       todo = TODO_cleanup_cfg;
    5372              :     }
    5373      1062856 :   scev_finalize ();
    5374      1062856 :   loop_optimizer_finalize ();
    5375      1062856 :   return todo;
    5376              : }
        

Generated by: LCOV version 2.5.0-beta

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