LCOV - code coverage report
Current view: top level - gcc - tree-if-conv.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.2 % 1840 1771
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 71 71
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* If-conversion for vectorizer.
       2              :    Copyright (C) 2004-2026 Free Software Foundation, Inc.
       3              :    Contributed by Devang Patel <dpatel@apple.com>
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it under
       8              : the terms of the GNU General Public License as published by the Free
       9              : Software Foundation; either version 3, or (at your option) any later
      10              : version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15              : for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not see
      19              : <http://www.gnu.org/licenses/>.  */
      20              : 
      21              : /* This pass implements a tree level if-conversion of loops.  Its
      22              :    initial goal is to help the vectorizer to vectorize loops with
      23              :    conditions.
      24              : 
      25              :    A short description of if-conversion:
      26              : 
      27              :      o Decide if a loop is if-convertible or not.
      28              :      o Walk all loop basic blocks in breadth first order (BFS order).
      29              :        o Remove conditional statements (at the end of basic block)
      30              :          and propagate condition into destination basic blocks'
      31              :          predicate list.
      32              :        o Replace modify expression with conditional modify expression
      33              :          using current basic block's condition.
      34              :      o Merge all basic blocks
      35              :        o Replace phi nodes with conditional modify expr
      36              :        o Merge all basic blocks into header
      37              : 
      38              :      Sample transformation:
      39              : 
      40              :      INPUT
      41              :      -----
      42              : 
      43              :      # i_23 = PHI <0(0), i_18(10)>;
      44              :      <L0>:;
      45              :      j_15 = A[i_23];
      46              :      if (j_15 > 41) goto <L1>; else goto <L17>;
      47              : 
      48              :      <L17>:;
      49              :      goto <bb 3> (<L3>);
      50              : 
      51              :      <L1>:;
      52              : 
      53              :      # iftmp.2_4 = PHI <0(8), 42(2)>;
      54              :      <L3>:;
      55              :      A[i_23] = iftmp.2_4;
      56              :      i_18 = i_23 + 1;
      57              :      if (i_18 <= 15) goto <L19>; else goto <L18>;
      58              : 
      59              :      <L19>:;
      60              :      goto <bb 1> (<L0>);
      61              : 
      62              :      <L18>:;
      63              : 
      64              :      OUTPUT
      65              :      ------
      66              : 
      67              :      # i_23 = PHI <0(0), i_18(10)>;
      68              :      <L0>:;
      69              :      j_15 = A[i_23];
      70              : 
      71              :      <L3>:;
      72              :      iftmp.2_4 = j_15 > 41 ? 42 : 0;
      73              :      A[i_23] = iftmp.2_4;
      74              :      i_18 = i_23 + 1;
      75              :      if (i_18 <= 15) goto <L19>; else goto <L18>;
      76              : 
      77              :      <L19>:;
      78              :      goto <bb 1> (<L0>);
      79              : 
      80              :      <L18>:;
      81              : */
      82              : 
      83              : #include "config.h"
      84              : #include "system.h"
      85              : #include "coretypes.h"
      86              : #include "backend.h"
      87              : #include "rtl.h"
      88              : #include "tree.h"
      89              : #include "gimple.h"
      90              : #include "cfghooks.h"
      91              : #include "tree-pass.h"
      92              : #include "ssa.h"
      93              : #include "expmed.h"
      94              : #include "expr.h"
      95              : #include "optabs-tree.h"
      96              : #include "gimple-pretty-print.h"
      97              : #include "alias.h"
      98              : #include "fold-const.h"
      99              : #include "stor-layout.h"
     100              : #include "gimple-iterator.h"
     101              : #include "gimple-fold.h"
     102              : #include "gimplify.h"
     103              : #include "gimplify-me.h"
     104              : #include "tree-cfg.h"
     105              : #include "tree-into-ssa.h"
     106              : #include "tree-ssa.h"
     107              : #include "cfgloop.h"
     108              : #include "tree-data-ref.h"
     109              : #include "tree-scalar-evolution.h"
     110              : #include "tree-ssa-loop.h"
     111              : #include "tree-ssa-loop-niter.h"
     112              : #include "tree-ssa-loop-ivopts.h"
     113              : #include "tree-ssa-address.h"
     114              : #include "dbgcnt.h"
     115              : #include "tree-hash-traits.h"
     116              : #include "varasm.h"
     117              : #include "builtins.h"
     118              : #include "cfganal.h"
     119              : #include "internal-fn.h"
     120              : #include "tree-ssa-sccvn.h"
     121              : #include "tree-cfgcleanup.h"
     122              : #include "tree-ssa-dse.h"
     123              : #include "tree-vectorizer.h"
     124              : #include "tree-eh.h"
     125              : #include "cgraph.h"
     126              : 
     127              : /* For lang_hooks.types.type_for_mode.  */
     128              : #include "langhooks.h"
     129              : 
     130              : /* Only handle PHIs with no more arguments unless we are asked to by
     131              :    simd pragma.  */
     132              : #define MAX_PHI_ARG_NUM \
     133              :   ((unsigned) param_max_tree_if_conversion_phi_args)
     134              : 
     135              : /* True if we've converted a statement that was only executed when some
     136              :    condition C was true, and if for correctness we need to predicate the
     137              :    statement to ensure that it is a no-op when C is false.  See
     138              :    predicate_statements for the kinds of predication we support.  */
     139              : static bool need_to_predicate;
     140              : 
     141              : /* True if we have to rewrite stmts that may invoke undefined behavior
     142              :    when a condition C was false so it doesn't if it is always executed.
     143              :    See predicate_statements for the kinds of predication we support.  */
     144              : static bool need_to_rewrite_undefined;
     145              : 
     146              : /* Indicate if there are any complicated PHIs that need to be handled in
     147              :    if-conversion.  Complicated PHI has more than two arguments and can't
     148              :    be degenerated to two arguments PHI.  See more information in comment
     149              :    before phi_convertible_by_degenerating_args.  */
     150              : static bool any_complicated_phi;
     151              : 
     152              : /* True if we have bitfield accesses we can lower.  */
     153              : static bool need_to_lower_bitfields;
     154              : 
     155              : /* True if there is any ifcvting to be done.  */
     156              : static bool need_to_ifcvt;
     157              : 
     158              : /* Hash for struct innermost_loop_behavior.  It depends on the user to
     159              :    free the memory.  */
     160              : 
     161              : struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
     162              : {
     163              :   static inline hashval_t hash (const value_type &);
     164              :   static inline bool equal (const value_type &,
     165              :                             const compare_type &);
     166              : };
     167              : 
     168              : inline hashval_t
     169       401554 : innermost_loop_behavior_hash::hash (const value_type &e)
     170              : {
     171       401554 :   hashval_t hash;
     172              : 
     173       401554 :   hash = iterative_hash_expr (e->base_address, 0);
     174       401554 :   hash = iterative_hash_expr (e->offset, hash);
     175       401554 :   hash = iterative_hash_expr (e->init, hash);
     176       401554 :   return iterative_hash_expr (e->step, hash);
     177              : }
     178              : 
     179              : inline bool
     180       288849 : innermost_loop_behavior_hash::equal (const value_type &e1,
     181              :                                      const compare_type &e2)
     182              : {
     183       288849 :   if ((e1->base_address && !e2->base_address)
     184       288849 :       || (!e1->base_address && e2->base_address)
     185       288849 :       || (!e1->offset && e2->offset)
     186       273129 :       || (e1->offset && !e2->offset)
     187       244768 :       || (!e1->init && e2->init)
     188       244768 :       || (e1->init && !e2->init)
     189       244768 :       || (!e1->step && e2->step)
     190       244768 :       || (e1->step && !e2->step))
     191              :     return false;
     192              : 
     193       244768 :   if (e1->base_address && e2->base_address
     194       489536 :       && !operand_equal_p (e1->base_address, e2->base_address, 0))
     195              :     return false;
     196        47446 :   if (e1->offset && e2->offset
     197       125427 :       && !operand_equal_p (e1->offset, e2->offset, 0))
     198              :     return false;
     199        47184 :   if (e1->init && e2->init
     200       124903 :       && !operand_equal_p (e1->init, e2->init, 0))
     201              :     return false;
     202        17679 :   if (e1->step && e2->step
     203        65893 :       && !operand_equal_p (e1->step, e2->step, 0))
     204              :     return false;
     205              : 
     206              :   return true;
     207              : }
     208              : 
     209              : /* List of basic blocks in if-conversion-suitable order.  */
     210              : static basic_block *ifc_bbs;
     211              : 
     212              : /* Hash table to store <DR's innermost loop behavior, DR> pairs.  */
     213              : static hash_map<innermost_loop_behavior_hash,
     214              :                 data_reference_p> *innermost_DR_map;
     215              : 
     216              : /* Hash table to store <base reference, DR> pairs.  */
     217              : static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;
     218              : 
     219              : /* List of redundant SSA names: the first should be replaced by the second.  */
     220              : static vec< std::pair<tree, tree> > redundant_ssa_names;
     221              : 
     222              : /* Structure used to predicate basic blocks.  This is attached to the
     223              :    ->aux field of the BBs in the loop to be if-converted.  */
     224              : struct bb_predicate {
     225              : 
     226              :   /* The condition under which this basic block is executed.  */
     227              :   tree predicate;
     228              : 
     229              :   /* PREDICATE is gimplified, and the sequence of statements is
     230              :      recorded here, in order to avoid the duplication of computations
     231              :      that occur in previous conditions.  See PR44483.  */
     232              :   gimple_seq predicate_gimplified_stmts;
     233              : 
     234              :   /* Records the number of statements recorded into
     235              :      PREDICATE_GIMPLIFIED_STMTS.   */
     236              :   unsigned no_predicate_stmts;
     237              : };
     238              : 
     239              : /* Returns true when the basic block BB has a predicate.  */
     240              : 
     241              : static inline bool
     242      1970138 : bb_has_predicate (basic_block bb)
     243              : {
     244      1970138 :   return bb->aux != NULL;
     245              : }
     246              : 
     247              : /* Returns the gimplified predicate for basic block BB.  */
     248              : 
     249              : static inline tree
     250       919307 : bb_predicate (basic_block bb)
     251              : {
     252       919307 :   return ((struct bb_predicate *) bb->aux)->predicate;
     253              : }
     254              : 
     255              : /* Sets the gimplified predicate COND for basic block BB.  */
     256              : 
     257              : static inline void
     258       494200 : set_bb_predicate (basic_block bb, tree cond)
     259              : {
     260       494200 :   auto aux = (struct bb_predicate *) bb->aux;
     261       494200 :   gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
     262              :                && is_gimple_val (TREE_OPERAND (cond, 0)))
     263              :               || is_gimple_val (cond));
     264       494200 :   aux->predicate = cond;
     265       494200 :   aux->no_predicate_stmts++;
     266              : 
     267       494200 :   if (dump_file && (dump_flags & TDF_DETAILS))
     268          378 :     fprintf (dump_file, "Recording block %d value %d\n", bb->index,
     269              :              aux->no_predicate_stmts);
     270       494200 : }
     271              : 
     272              : /* Returns the sequence of statements of the gimplification of the
     273              :    predicate for basic block BB.  */
     274              : 
     275              : static inline gimple_seq
     276       608212 : bb_predicate_gimplified_stmts (basic_block bb)
     277              : {
     278       608212 :   return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
     279              : }
     280              : 
     281              : /* Sets the sequence of statements STMTS of the gimplification of the
     282              :    predicate for basic block BB.  If PRESERVE_COUNTS then don't clear the predicate
     283              :    counts.  */
     284              : 
     285              : static inline void
     286       293510 : set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts,
     287              :                                    bool preserve_counts)
     288              : {
     289       293510 :   ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
     290       293510 :   if (stmts == NULL && !preserve_counts)
     291       240009 :     ((struct bb_predicate *) bb->aux)->no_predicate_stmts = 0;
     292              : }
     293              : 
     294              : /* Adds the sequence of statements STMTS to the sequence of statements
     295              :    of the predicate for basic block BB.  */
     296              : 
     297              : static inline void
     298        89571 : add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
     299              : {
     300              :   /* We might have updated some stmts in STMTS via force_gimple_operand
     301              :      calling fold_stmt and that producing multiple stmts.  Delink immediate
     302              :      uses so update_ssa after loop versioning doesn't get confused for
     303              :      the not yet inserted predicates.
     304              :      ???  This should go away once we reliably avoid updating stmts
     305              :      not in any BB.  */
     306        89571 :   for (gimple_stmt_iterator gsi = gsi_start (stmts);
     307       220852 :        !gsi_end_p (gsi); gsi_next (&gsi))
     308              :     {
     309       131281 :       gimple *stmt = gsi_stmt (gsi);
     310       131281 :       delink_stmt_imm_use (stmt);
     311       131281 :       gimple_set_modified (stmt, true);
     312       131281 :       ((struct bb_predicate *) bb->aux)->no_predicate_stmts++;
     313              :     }
     314        89571 :   gimple_seq_add_seq_without_update
     315        89571 :     (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
     316        89571 : }
     317              : 
     318              : /* Return the number of statements the predicate of the basic block consists
     319              :    of.  */
     320              : 
     321              : static inline unsigned
     322        16292 : get_bb_num_predicate_stmts (basic_block bb)
     323              : {
     324        16292 :   return ((struct bb_predicate *) bb->aux)->no_predicate_stmts;
     325              : }
     326              : 
     327              : /* Initializes to TRUE the predicate of basic block BB.  */
     328              : 
     329              : static inline void
     330       206098 : init_bb_predicate (basic_block bb)
     331              : {
     332       206098 :   bb->aux = XNEW (struct bb_predicate);
     333       206098 :   set_bb_predicate_gimplified_stmts (bb, NULL, false);
     334       206098 :   set_bb_predicate (bb, boolean_true_node);
     335       206098 : }
     336              : 
     337              : /* Release the SSA_NAMEs associated with the predicate of basic block BB.  */
     338              : 
     339              : static inline void
     340       398771 : release_bb_predicate (basic_block bb)
     341              : {
     342       398771 :   gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
     343       398771 :   if (stmts)
     344              :     {
     345              :       /* Ensure that these stmts haven't yet been added to a bb.  */
     346        33911 :       if (flag_checking)
     347        94234 :         for (gimple_stmt_iterator i = gsi_start (stmts);
     348        94234 :              !gsi_end_p (i); gsi_next (&i))
     349        60323 :           gcc_assert (! gimple_bb (gsi_stmt (i)));
     350              : 
     351              :       /* Discard them.  */
     352        33911 :       gimple_seq_discard (stmts);
     353        33911 :       set_bb_predicate_gimplified_stmts (bb, NULL, false);
     354              :     }
     355       398771 : }
     356              : 
     357              : /* Free the predicate of basic block BB.  */
     358              : 
     359              : static inline void
     360      1777465 : free_bb_predicate (basic_block bb)
     361              : {
     362      1777465 :   if (!bb_has_predicate (bb))
     363              :     return;
     364              : 
     365       206098 :   release_bb_predicate (bb);
     366       206098 :   free (bb->aux);
     367       206098 :   bb->aux = NULL;
     368              : }
     369              : 
     370              : /* Reinitialize predicate of BB with the true predicate.  */
     371              : 
     372              : static inline void
     373       192673 : reset_bb_predicate (basic_block bb)
     374              : {
     375       192673 :   if (!bb_has_predicate (bb))
     376            0 :     init_bb_predicate (bb);
     377              :   else
     378              :     {
     379       192673 :       release_bb_predicate (bb);
     380       192673 :       set_bb_predicate (bb, boolean_true_node);
     381              :     }
     382       192673 : }
     383              : 
     384              : /* Returns a new SSA_NAME of type TYPE that is assigned the value of
     385              :    the expression EXPR.  Inserts the statement created for this
     386              :    computation before GSI and leaves the iterator GSI at the same
     387              :    statement.  */
     388              : 
     389              : static tree
     390         5377 : ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
     391              : {
     392         5377 :   tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
     393         5377 :   gimple *stmt = gimple_build_assign (new_name, expr);
     394        10754 :   gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
     395         5377 :   gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
     396         5377 :   return new_name;
     397              : }
     398              : 
     399              : /* Return true when COND is a false predicate.  */
     400              : 
     401              : static inline bool
     402        92118 : is_false_predicate (tree cond)
     403              : {
     404        92118 :   return (cond != NULL_TREE
     405        92118 :           && (cond == boolean_false_node
     406        92118 :               || integer_zerop (cond)));
     407              : }
     408              : 
     409              : /* Return true when COND is a true predicate.  */
     410              : 
     411              : static inline bool
     412      1043705 : is_true_predicate (tree cond)
     413              : {
     414      1043705 :   return (cond == NULL_TREE
     415      1043705 :           || cond == boolean_true_node
     416      1513991 :           || integer_onep (cond));
     417              : }
     418              : 
     419              : /* Returns true when BB has a predicate that is not trivial: true or
     420              :    NULL_TREE.  */
     421              : 
     422              : static inline bool
     423       511429 : is_predicated (basic_block bb)
     424              : {
     425        14609 :   return !is_true_predicate (bb_predicate (bb));
     426              : }
     427              : 
     428              : /* Parses the predicate COND and returns its comparison code and
     429              :    operands OP0 and OP1.  */
     430              : 
     431              : static enum tree_code
     432       399806 : parse_predicate (tree cond, tree *op0, tree *op1)
     433              : {
     434       399806 :   gimple *s;
     435              : 
     436       399806 :   if (TREE_CODE (cond) == SSA_NAME
     437       399806 :       && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
     438              :     {
     439        63617 :       if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
     440              :         {
     441        32290 :           *op0 = gimple_assign_rhs1 (s);
     442        32290 :           *op1 = gimple_assign_rhs2 (s);
     443        32290 :           return gimple_assign_rhs_code (s);
     444              :         }
     445              : 
     446        31327 :       else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
     447              :         {
     448            0 :           tree op = gimple_assign_rhs1 (s);
     449            0 :           tree type = TREE_TYPE (op);
     450            0 :           enum tree_code code = parse_predicate (op, op0, op1);
     451              : 
     452            0 :           return code == ERROR_MARK ? ERROR_MARK
     453            0 :             : invert_tree_comparison (code, HONOR_NANS (type));
     454              :         }
     455              : 
     456              :       return ERROR_MARK;
     457              :     }
     458              : 
     459       336189 :   if (COMPARISON_CLASS_P (cond))
     460              :     {
     461          483 :       *op0 = TREE_OPERAND (cond, 0);
     462          483 :       *op1 = TREE_OPERAND (cond, 1);
     463          483 :       return TREE_CODE (cond);
     464              :     }
     465              : 
     466              :   return ERROR_MARK;
     467              : }
     468              : 
     469              : /* Returns the fold of predicate C1 OR C2 at location LOC.  */
     470              : 
     471              : static tree
     472       199903 : fold_or_predicates (location_t loc, tree c1, tree c2)
     473              : {
     474       199903 :   tree op1a, op1b, op2a, op2b;
     475       199903 :   enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
     476       199903 :   enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
     477              : 
     478       199903 :   if (code1 != ERROR_MARK && code2 != ERROR_MARK)
     479              :     {
     480         2273 :       tree t = maybe_fold_or_comparisons (boolean_type_node, TRUTH_OR_EXPR,
     481              :                                           code1, op1a, op1b, code2, op2a, op2b);
     482         2273 :       if (t)
     483              :         return t;
     484              :     }
     485              : 
     486       197725 :   return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
     487              : }
     488              : 
     489              : /* Returns either a COND_EXPR or the folded expression if the folded
     490              :    expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
     491              :    a constant or a SSA_NAME. */
     492              : 
     493              : static tree
     494        51824 : fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
     495              : {
     496              :   /* Short cut the case where both rhs and lhs are the same. */
     497        51824 :   if (operand_equal_p (rhs, lhs))
     498              :     return rhs;
     499              : 
     500              :   /* If COND is comparison r != 0 and r has boolean type, convert COND
     501              :      to SSA_NAME to accept by vect bool pattern.  */
     502        51824 :   if (TREE_CODE (cond) == NE_EXPR)
     503              :     {
     504            0 :       tree op0 = TREE_OPERAND (cond, 0);
     505            0 :       tree op1 = TREE_OPERAND (cond, 1);
     506            0 :       if (TREE_CODE (op0) == SSA_NAME
     507            0 :           && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
     508            0 :           && (integer_zerop (op1)))
     509              :         cond = op0;
     510              :     }
     511              : 
     512        51824 :   gimple_match_op cexpr (gimple_match_cond::UNCOND, COND_EXPR,
     513        51824 :                          type, cond, rhs, lhs);
     514        51824 :   if (cexpr.resimplify (NULL, follow_all_ssa_edges))
     515              :     {
     516         6743 :       if (gimple_simplified_result_is_gimple_val (&cexpr))
     517          567 :         return cexpr.ops[0];
     518         6176 :       else if (cexpr.code == ABS_EXPR)
     519            2 :         return build1 (ABS_EXPR, type, cexpr.ops[0]);
     520         6174 :       else if (cexpr.code == MIN_EXPR
     521         6174 :                || cexpr.code == MAX_EXPR)
     522         3322 :         return build2 ((tree_code)cexpr.code, type, cexpr.ops[0], cexpr.ops[1]);
     523              :     }
     524              : 
     525        47933 :   return build3 (COND_EXPR, type, cond, rhs, lhs);
     526              : }
     527              : 
     528              : /* Add condition NC to the predicate list of basic block BB.  LOOP is
     529              :    the loop to be if-converted. Use predicate of cd-equivalent block
     530              :    for join bb if it exists: we call basic blocks bb1 and bb2
     531              :    cd-equivalent if they are executed under the same condition.  */
     532              : 
     533              : static inline void
     534       165019 : add_to_predicate_list (class loop *loop, basic_block bb, tree nc)
     535              : {
     536       165019 :   tree bc, *tp;
     537       165019 :   basic_block dom_bb;
     538              : 
     539       165019 :   if (is_true_predicate (nc))
     540        73676 :     return;
     541              : 
     542              :   /* If dominance tells us this basic block is always executed,
     543              :      don't record any predicates for it.  */
     544       165007 :   if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
     545              :     return;
     546              : 
     547        95429 :   dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
     548              :   /* We use notion of cd equivalence to get simpler predicate for
     549              :      join block, e.g. if join block has 2 predecessors with predicates
     550              :      p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
     551              :      p1 & p2 | p1 & !p2.  */
     552        95429 :   if (dom_bb != loop->header
     553        95429 :       && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
     554              :     {
     555         4086 :       gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
     556         4086 :       bc = bb_predicate (dom_bb);
     557         4086 :       if (!is_true_predicate (bc))
     558         4086 :         set_bb_predicate (bb, bc);
     559              :       else
     560            0 :         gcc_assert (is_true_predicate (bb_predicate (bb)));
     561         4086 :       if (dump_file && (dump_flags & TDF_DETAILS))
     562            4 :         fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
     563              :                  dom_bb->index, bb->index);
     564              :       return;
     565              :     }
     566              : 
     567        91343 :   if (!is_predicated (bb))
     568        87412 :     bc = nc;
     569              :   else
     570              :     {
     571         3931 :       bc = bb_predicate (bb);
     572         3931 :       bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
     573         3931 :       if (is_true_predicate (bc))
     574              :         {
     575            0 :           reset_bb_predicate (bb);
     576            0 :           return;
     577              :         }
     578              :     }
     579              : 
     580              :   /* Allow a TRUTH_NOT_EXPR around the main predicate.  */
     581        91343 :   if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
     582        32978 :     tp = &TREE_OPERAND (bc, 0);
     583              :   else
     584              :     tp = &bc;
     585        91343 :   if (!is_gimple_val (*tp))
     586              :     {
     587        89571 :       gimple_seq stmts;
     588        89571 :       *tp = force_gimple_operand (*tp, &stmts, true, NULL_TREE);
     589        89571 :       add_bb_predicate_gimplified_stmts (bb, stmts);
     590              :     }
     591        91343 :   set_bb_predicate (bb, bc);
     592              : }
     593              : 
     594              : /* Add the condition COND to the previous condition PREV_COND, and add
     595              :    this to the predicate list of the destination of edge E.  LOOP is
     596              :    the loop to be if-converted.  */
     597              : 
     598              : static void
     599       107358 : add_to_dst_predicate_list (class loop *loop, edge e,
     600              :                            tree prev_cond, tree cond)
     601              : {
     602       107358 :   if (!flow_bb_inside_loop_p (loop, e->dest))
     603              :     return;
     604              : 
     605       107358 :   if (!is_true_predicate (prev_cond))
     606        22580 :     cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
     607              :                         prev_cond, cond);
     608              : 
     609       107358 :   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
     610        86882 :     add_to_predicate_list (loop, e->dest, cond);
     611              : }
     612              : 
     613              : /* Return true if one of the successor edges of BB exits LOOP.  */
     614              : 
     615              : static bool
     616      3438210 : bb_with_exit_edge_p (const class loop *loop, basic_block bb)
     617              : {
     618      3438210 :   edge e;
     619      3438210 :   edge_iterator ei;
     620              : 
     621      6943394 :   FOR_EACH_EDGE (e, ei, bb->succs)
     622      4896566 :     if (loop_exit_edge_p (loop, e))
     623              :       return true;
     624              : 
     625              :   return false;
     626              : }
     627              : 
     628              : /* Given PHI which has more than two arguments, this function checks if
     629              :    it's if-convertible by degenerating its arguments.  Specifically, if
     630              :    below two conditions are satisfied:
     631              : 
     632              :      1) Number of PHI arguments with different values equals to 2 and one
     633              :         argument has the only occurrence.
     634              :      2) The edge corresponding to the unique argument isn't critical edge.
     635              : 
     636              :    Such PHI can be handled as PHIs have only two arguments.  For example,
     637              :    below PHI:
     638              : 
     639              :      res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
     640              : 
     641              :    can be transformed into:
     642              : 
     643              :      res = (predicate of e3) ? A_2 : A_1;
     644              : 
     645              :    Return TRUE if it is the case, FALSE otherwise.  */
     646              : 
     647              : static bool
     648         5539 : phi_convertible_by_degenerating_args (gphi *phi)
     649              : {
     650         5539 :   edge e;
     651         5539 :   tree arg, t1 = NULL, t2 = NULL;
     652         5539 :   unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
     653         5539 :   unsigned int num_args = gimple_phi_num_args (phi);
     654              : 
     655         5539 :   gcc_assert (num_args > 2);
     656              : 
     657        20116 :   for (i = 0; i < num_args; i++)
     658              :     {
     659        16803 :       arg = gimple_phi_arg_def (phi, i);
     660        16803 :       if (t1 == NULL || operand_equal_p (t1, arg, 0))
     661              :         {
     662         7615 :           n1++;
     663         7615 :           i1 = i;
     664         7615 :           t1 = arg;
     665              :         }
     666         9188 :       else if (t2 == NULL || operand_equal_p (t2, arg, 0))
     667              :         {
     668         6962 :           n2++;
     669         6962 :           i2 = i;
     670         6962 :           t2 = arg;
     671              :         }
     672              :       else
     673              :         return false;
     674              :     }
     675              : 
     676         3313 :   if (n1 != 1 && n2 != 1)
     677              :     return false;
     678              : 
     679              :   /* Check if the edge corresponding to the unique arg is critical.  */
     680         3253 :   e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
     681         3253 :   if (EDGE_COUNT (e->src->succs) > 1)
     682            0 :     return false;
     683              : 
     684              :   return true;
     685              : }
     686              : 
     687              : /* Return true when PHI is if-convertible.  PHI is part of loop LOOP
     688              :    and it belongs to basic block BB.  Note at this point, it is sure
     689              :    that PHI is if-convertible.  This function updates global variable
     690              :    ANY_COMPLICATED_PHI if PHI is complicated.  */
     691              : 
     692              : static bool
     693       130013 : if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi)
     694              : {
     695       130013 :   if (dump_file && (dump_flags & TDF_DETAILS))
     696              :     {
     697          103 :       fprintf (dump_file, "-------------------------\n");
     698          103 :       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
     699              :     }
     700              : 
     701       130013 :   if (bb != loop->header
     702        52070 :       && gimple_phi_num_args (phi) > 2
     703       135552 :       && !phi_convertible_by_degenerating_args (phi))
     704         2286 :     any_complicated_phi = true;
     705              : 
     706       130013 :   return true;
     707              : }
     708              : 
     709              : /* Records the status of a data reference.  This struct is attached to
     710              :    each DR->aux field.  */
     711              : 
     712              : struct ifc_dr {
     713              :   bool rw_unconditionally;
     714              :   bool w_unconditionally;
     715              :   bool written_at_least_once;
     716              : 
     717              :   tree rw_predicate;
     718              :   tree w_predicate;
     719              :   tree base_w_predicate;
     720              : };
     721              : 
     722              : #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
     723              : #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
     724              : #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
     725              : #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
     726              : 
     727              : /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
     728              :    HASH tables.  While storing them in HASH table, it checks if the
     729              :    reference is unconditionally read or written and stores that as a flag
     730              :    information.  For base reference it checks if it is written atlest once
     731              :    unconditionally and stores it as flag information along with DR.
     732              :    In other words for every data reference A in STMT there exist other
     733              :    accesses to a data reference with the same base with predicates that
     734              :    add up (OR-up) to the true predicate: this ensures that the data
     735              :    reference A is touched (read or written) on every iteration of the
     736              :    if-converted loop.  */
     737              : static void
     738       120228 : hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
     739              : {
     740              : 
     741       120228 :   data_reference_p *master_dr, *base_master_dr;
     742       120228 :   tree base_ref = DR_BASE_OBJECT (a);
     743       120228 :   innermost_loop_behavior *innermost = &DR_INNERMOST (a);
     744       120228 :   tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
     745       120228 :   bool exist1, exist2;
     746              : 
     747       120228 :   master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
     748       120228 :   if (!exist1)
     749        92273 :     *master_dr = a;
     750              : 
     751       120228 :   if (DR_IS_WRITE (a))
     752              :     {
     753        37843 :       IFC_DR (*master_dr)->w_predicate
     754        75686 :         = fold_or_predicates (UNKNOWN_LOCATION, ca,
     755        37843 :                               IFC_DR (*master_dr)->w_predicate);
     756        37843 :       if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
     757        21851 :         DR_W_UNCONDITIONALLY (*master_dr) = true;
     758              :     }
     759       120228 :   IFC_DR (*master_dr)->rw_predicate
     760       240456 :     = fold_or_predicates (UNKNOWN_LOCATION, ca,
     761       120228 :                           IFC_DR (*master_dr)->rw_predicate);
     762       120228 :   if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
     763        84317 :     DR_RW_UNCONDITIONALLY (*master_dr) = true;
     764              : 
     765       120228 :   if (DR_IS_WRITE (a))
     766              :     {
     767        37843 :       base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
     768        37843 :       if (!exist2)
     769        27693 :         *base_master_dr = a;
     770        37843 :       IFC_DR (*base_master_dr)->base_w_predicate
     771        75686 :         = fold_or_predicates (UNKNOWN_LOCATION, ca,
     772        37843 :                               IFC_DR (*base_master_dr)->base_w_predicate);
     773        37843 :       if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
     774        22114 :         DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
     775              :     }
     776       120228 : }
     777              : 
     778              : /* Return TRUE if can prove the index IDX of an array reference REF is
     779              :    within array bound.  Return false otherwise.  */
     780              : 
     781              : static bool
     782       269593 : idx_within_array_bound (tree ref, tree *idx, void *dta)
     783              : {
     784       269593 :   wi::overflow_type overflow;
     785       269593 :   widest_int niter, valid_niter, delta, wi_step;
     786       269593 :   tree ev, init, step;
     787       269593 :   tree low, high;
     788       269593 :   class loop *loop = (class loop*) dta;
     789              : 
     790              :   /* Only support within-bound access for array references.  */
     791       269593 :   if (TREE_CODE (ref) != ARRAY_REF)
     792              :     return false;
     793              : 
     794              :   /* For arrays that might have flexible sizes, it is not guaranteed that they
     795              :      do not extend over their declared size.  */
     796       150013 :   if (array_ref_flexible_size_p (ref))
     797              :     return false;
     798              : 
     799        96823 :   ev = analyze_scalar_evolution (loop, *idx);
     800        96823 :   ev = instantiate_parameters (loop, ev);
     801        96823 :   init = initial_condition (ev);
     802        96823 :   step = evolution_part_in_loop_num (ev, loop->num);
     803              : 
     804        96823 :   if (!init || TREE_CODE (init) != INTEGER_CST
     805        84453 :       || (step && TREE_CODE (step) != INTEGER_CST))
     806              :     return false;
     807              : 
     808        84447 :   low = array_ref_low_bound (ref);
     809        84447 :   high = array_ref_up_bound (ref);
     810              : 
     811              :   /* The case of nonconstant bounds could be handled, but it would be
     812              :      complicated.  */
     813        84447 :   if (TREE_CODE (low) != INTEGER_CST
     814        84447 :       || !high || TREE_CODE (high) != INTEGER_CST)
     815              :     return false;
     816              : 
     817              :   /* Check if the initial idx is within bound.  */
     818        84379 :   if (wi::to_widest (init) < wi::to_widest (low)
     819       168750 :       || wi::to_widest (init) > wi::to_widest (high))
     820              :     return false;
     821              : 
     822              :   /* The idx is always within bound.  */
     823        84363 :   if (!step || integer_zerop (step))
     824              :     return true;
     825              : 
     826        82285 :   if (!max_loop_iterations (loop, &niter))
     827              :     return false;
     828              : 
     829        82285 :   if (wi::to_widest (step) < 0)
     830              :     {
     831          303 :       delta = wi::to_widest (init) - wi::to_widest (low);
     832          303 :       wi_step = -wi::to_widest (step);
     833              :     }
     834              :   else
     835              :     {
     836        81982 :       delta = wi::to_widest (high) - wi::to_widest (init);
     837        81982 :       wi_step = wi::to_widest (step);
     838              :     }
     839              : 
     840        82285 :   valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
     841              :   /* The iteration space of idx is within array bound.  */
     842       164570 :   if (!overflow && niter <= valid_niter)
     843        81804 :     return true;
     844              : 
     845              :   return false;
     846       269593 : }
     847              : 
     848              : /* Return TRUE if ref is a within bound array reference.  */
     849              : 
     850              : bool
     851       262577 : ref_within_array_bound (gimple *stmt, tree ref)
     852              : {
     853       262577 :   class loop *loop = loop_containing_stmt (stmt);
     854              : 
     855       262577 :   gcc_assert (loop != NULL);
     856       262577 :   return for_each_index (&ref, idx_within_array_bound, loop);
     857              : }
     858              : 
     859              : 
     860              : /* Given a memory reference expression T, return TRUE if base object
     861              :    it refers to is writable.  The base object of a memory reference
     862              :    is the main object being referenced, which is returned by function
     863              :    get_base_address.  */
     864              : 
     865              : static bool
     866         2353 : base_object_writable (tree ref)
     867              : {
     868         2353 :   tree base_tree = get_base_address (ref);
     869              : 
     870         2353 :   return (base_tree
     871         2353 :           && DECL_P (base_tree)
     872         1459 :           && decl_binds_to_current_def_p (base_tree)
     873         3808 :           && !TREE_READONLY (base_tree));
     874              : }
     875              : 
     876              : /* Return true when the memory references of STMT won't trap in the
     877              :    if-converted code.  There are two things that we have to check for:
     878              : 
     879              :    - writes to memory occur to writable memory: if-conversion of
     880              :    memory writes transforms the conditional memory writes into
     881              :    unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
     882              :    into "A[i] = cond ? foo : A[i]", and as the write to memory may not
     883              :    be executed at all in the original code, it may be a readonly
     884              :    memory.  To check that A is not const-qualified, we check that
     885              :    there exists at least an unconditional write to A in the current
     886              :    function.
     887              : 
     888              :    - reads or writes to memory are valid memory accesses for every
     889              :    iteration.  To check that the memory accesses are correctly formed
     890              :    and that we are allowed to read and write in these locations, we
     891              :    check that the memory accesses to be if-converted occur at every
     892              :    iteration unconditionally.
     893              : 
     894              :    Returns true for the memory reference in STMT, same memory reference
     895              :    is read or written unconditionally at least once and the base memory
     896              :    reference is written unconditionally once.  This is to check reference
     897              :    will not write fault.  Also returns true if the memory reference is
     898              :    unconditionally read once then we are conditionally writing to memory
     899              :    which is defined as read and write and is bound to the definition
     900              :    we are seeing.  */
     901              : static bool
     902        20079 : ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
     903              : {
     904              :   /* If DR didn't see a reference here we can't use it to tell
     905              :      whether the ref traps or not.  */
     906        20079 :   if (gimple_uid (stmt) == 0)
     907              :     return false;
     908              : 
     909        20078 :   data_reference_p *master_dr, *base_master_dr;
     910        20078 :   data_reference_p a = drs[gimple_uid (stmt) - 1];
     911              : 
     912        20078 :   tree base = DR_BASE_OBJECT (a);
     913        20078 :   innermost_loop_behavior *innermost = &DR_INNERMOST (a);
     914              : 
     915        20078 :   gcc_assert (DR_STMT (a) == stmt);
     916        20078 :   gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
     917              :               || DR_INIT (a) || DR_STEP (a));
     918              : 
     919        20078 :   master_dr = innermost_DR_map->get (innermost);
     920        20078 :   gcc_assert (master_dr != NULL);
     921              : 
     922        20078 :   base_master_dr = baseref_DR_map->get (base);
     923              : 
     924              :   /* If a is unconditionally written to it doesn't trap.  */
     925        20078 :   if (DR_W_UNCONDITIONALLY (*master_dr))
     926              :     return true;
     927              : 
     928              :   /* If a is unconditionally accessed then ...
     929              : 
     930              :      Even a is conditional access, we can treat it as an unconditional
     931              :      one if it's an array reference and all its index are within array
     932              :      bound.  */
     933        18215 :   if (DR_RW_UNCONDITIONALLY (*master_dr)
     934        18215 :       || ref_within_array_bound (stmt, DR_REF (a)))
     935              :     {
     936              :       /* an unconditional read won't trap.  */
     937         6586 :       if (DR_IS_READ (a))
     938              :         return true;
     939              : 
     940              :       /* an unconditionally write won't trap if the base is written
     941              :          to unconditionally.  */
     942         2390 :       if ((base_master_dr
     943         2390 :            && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
     944              :           /* or the base is known to be not readonly.  */
     945         4743 :           || base_object_writable (DR_REF (a)))
     946         1492 :         return !ref_can_have_store_data_races (base);
     947              :     }
     948              : 
     949              :   return false;
     950              : }
     951              : 
     952              : /* Return true if STMT could be converted into a masked load or store
     953              :    (conditional load or store based on a mask computed from bb predicate).  */
     954              : 
     955              : static bool
     956        11939 : ifcvt_can_use_mask_load_store (gimple *stmt)
     957              : {
     958              :   /* Check whether this is a load or store.  */
     959        11939 :   tree lhs = gimple_assign_lhs (stmt);
     960        11939 :   bool is_load;
     961        11939 :   tree ref;
     962        11939 :   if (gimple_store_p (stmt))
     963              :     {
     964         2780 :       if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
     965              :         return false;
     966              :       is_load = false;
     967              :       ref = lhs;
     968              :     }
     969         9159 :   else if (gimple_assign_load_p (stmt))
     970              :     {
     971         9158 :       is_load = true;
     972         9158 :       ref = gimple_assign_rhs1 (stmt);
     973              :     }
     974              :   else
     975              :     return false;
     976              : 
     977        11938 :   if (may_be_nonaddressable_p (ref))
     978              :     return false;
     979              : 
     980              :   /* Mask should be integer mode of the same size as the load/store
     981              :      mode.  */
     982        11879 :   machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
     983        11879 :   if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode))
     984              :     return false;
     985              : 
     986        11848 :   if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
     987              :     return true;
     988              : 
     989              :   return false;
     990              : }
     991              : 
     992              : /* Return true if STMT could be converted from an operation that is
     993              :    unconditional to one that is conditional on a bb predicate mask.  */
     994              : 
     995              : static bool
     996        13935 : ifcvt_can_predicate (gimple *stmt)
     997              : {
     998        13935 :   basic_block bb = gimple_bb (stmt);
     999              : 
    1000          285 :   if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
    1001        13935 :       || bb->loop_father->dont_vectorize
    1002        27870 :       || gimple_has_volatile_ops (stmt))
    1003              :     return false;
    1004              : 
    1005        13935 :   if (gimple_assign_single_p (stmt))
    1006        11939 :     return ifcvt_can_use_mask_load_store (stmt);
    1007              : 
    1008         1996 :   tree callee;
    1009         1996 :   if (gimple_call_builtin_p (stmt))
    1010          155 :     if ((callee = gimple_call_fndecl (stmt))
    1011          155 :         && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
    1012              :       {
    1013          149 :         auto ifn = associated_internal_fn (callee);
    1014          149 :         auto cond_ifn = get_conditional_internal_fn (ifn);
    1015          149 :         tree type = TREE_TYPE (gimple_call_fntype (stmt));
    1016          149 :         return (cond_ifn != IFN_LAST
    1017          149 :                 && vectorized_internal_fn_supported_p (cond_ifn, type));
    1018              :       }
    1019              : 
    1020         1847 :   if (!is_gimple_assign (stmt))
    1021              :     return false;
    1022              : 
    1023         1841 :   tree_code code = gimple_assign_rhs_code (stmt);
    1024         1841 :   tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
    1025         1841 :   tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
    1026         1841 :   if (!types_compatible_p (lhs_type, rhs_type))
    1027              :     return false;
    1028         1181 :   internal_fn cond_fn = get_conditional_internal_fn (code);
    1029         1181 :   return (cond_fn != IFN_LAST
    1030         1181 :           && vectorized_internal_fn_supported_p (cond_fn, lhs_type));
    1031              : }
    1032              : 
    1033              : /* Return true when STMT is if-convertible.
    1034              : 
    1035              :    GIMPLE_ASSIGN statement is not if-convertible if,
    1036              :    - it is not movable,
    1037              :    - it could trap,
    1038              :    - LHS is not var decl.  */
    1039              : 
    1040              : static bool
    1041        77777 : if_convertible_gimple_assign_stmt_p (gimple *stmt,
    1042              :                                      vec<data_reference_p> refs)
    1043              : {
    1044        77777 :   tree lhs = gimple_assign_lhs (stmt);
    1045              : 
    1046        77777 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1047              :     {
    1048           38 :       fprintf (dump_file, "-------------------------\n");
    1049           38 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1050              :     }
    1051              : 
    1052        77777 :   if (!is_gimple_reg_type (TREE_TYPE (lhs)))
    1053              :     return false;
    1054              : 
    1055              :   /* Some of these constrains might be too conservative.  */
    1056        77504 :   if (stmt_ends_bb_p (stmt)
    1057        77504 :       || gimple_has_volatile_ops (stmt)
    1058        77429 :       || (TREE_CODE (lhs) == SSA_NAME
    1059        73126 :           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
    1060       154933 :       || gimple_has_side_effects (stmt))
    1061              :     {
    1062           75 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1063            0 :         fprintf (dump_file, "stmt not suitable for ifcvt\n");
    1064              :       return false;
    1065              :     }
    1066              : 
    1067              :   /* tree-into-ssa.cc uses GF_PLF_1, so avoid it, because
    1068              :      in between if_convertible_loop_p and combine_blocks
    1069              :      we can perform loop versioning.  */
    1070        77429 :   gimple_set_plf (stmt, GF_PLF_2, false);
    1071              : 
    1072        77429 :   if ((! gimple_vuse (stmt)
    1073        20079 :        || gimple_could_trap_p_1 (stmt, false, false)
    1074        20079 :        || ! ifcvt_memrefs_wont_trap (stmt, refs))
    1075        90268 :       && gimple_could_trap_p (stmt))
    1076              :     {
    1077        13780 :       if (ifcvt_can_predicate (stmt))
    1078              :         {
    1079         2768 :           gimple_set_plf (stmt, GF_PLF_2, true);
    1080         2768 :           need_to_predicate = true;
    1081         2768 :           return true;
    1082              :         }
    1083        11012 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1084            0 :         fprintf (dump_file, "tree could trap...\n");
    1085              :       return false;
    1086              :     }
    1087        63649 :   else if (gimple_needing_rewrite_undefined (stmt))
    1088              :     /* We have to rewrite stmts with undefined overflow.  */
    1089        28628 :     need_to_rewrite_undefined = true;
    1090              : 
    1091              :   /* When if-converting stores force versioning, likewise if we
    1092              :      ended up generating store data races.  */
    1093       127298 :   if (gimple_vdef (stmt))
    1094         1523 :     need_to_predicate = true;
    1095              : 
    1096              :   return true;
    1097              : }
    1098              : 
    1099              : /* Return true when SW switch statement is equivalent to cond, that
    1100              :    all non default labels point to the same label.
    1101              : 
    1102              :    Fallthrough is not checked for and could even happen
    1103              :    with cond (using goto), so is handled.
    1104              : 
    1105              :    This is intended for switches created by the if-switch-conversion
    1106              :    pass, but can handle some programmer supplied cases too. */
    1107              : 
    1108              : static bool
    1109           70 : if_convertible_switch_p (gswitch *sw)
    1110              : {
    1111           70 :   if (gimple_switch_num_labels (sw) <= 1)
    1112              :     return false;
    1113           70 :   tree label = CASE_LABEL (gimple_switch_label (sw, 1));
    1114          762 :   for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++)
    1115              :     {
    1116          698 :       if (CASE_LABEL (gimple_switch_label (sw, i)) != label)
    1117              :         return false;
    1118              :     }
    1119              :   return true;
    1120              : }
    1121              : 
    1122              : /* Return true when STMT is an if-convertible SIMD clone stmts.
    1123              : 
    1124              :    A SIMD clone statement is if-convertible if:
    1125              :     - it is an GIMPLE_CALL,
    1126              :     - it has a FNDECL,
    1127              :     - it has SIMD clones,
    1128              :     - it has at least one inbranch clone.  */
    1129              : static bool
    1130         1622 : if_convertible_simdclone_stmt_p (gimple *stmt)
    1131              : {
    1132         1622 :   if (!is_gimple_call (stmt))
    1133              :     return false;
    1134              : 
    1135         1622 :   tree fndecl = gimple_call_fndecl (stmt);
    1136         1622 :   if (fndecl)
    1137              :     {
    1138              :       /* We can vectorize some builtins and functions with SIMD "inbranch"
    1139              :          clones.  */
    1140         1342 :       struct cgraph_node *node = cgraph_node::get (fndecl);
    1141         1342 :       if (node && node->simd_clones != NULL)
    1142              :         /* Ensure that at least one clone can be "inbranch".  */
    1143         1972 :         for (struct cgraph_node *n = node->simd_clones; n != NULL;
    1144          963 :              n = n->simdclone->next_clone)
    1145         1970 :           if (n->simdclone->inbranch)
    1146              :             return true;
    1147              :     }
    1148              : 
    1149              :   return false;
    1150              : }
    1151              : 
    1152              : /* Return true when STMT is if-convertible.
    1153              : 
    1154              :    A statement is if-convertible if:
    1155              :    - it is an if-convertible GIMPLE_ASSIGN,
    1156              :    - it is a GIMPLE_LABEL or a GIMPLE_COND,
    1157              :    - it is a switch equivalent to COND
    1158              :    - it is builtins call,
    1159              :    - it is a call to a function with a SIMD clone.  */
    1160              : 
    1161              : static bool
    1162       169077 : if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
    1163              : {
    1164       169077 :   switch (gimple_code (stmt))
    1165              :     {
    1166              :     case GIMPLE_LABEL:
    1167              :     case GIMPLE_DEBUG:
    1168              :     case GIMPLE_COND:
    1169              :       return true;
    1170              : 
    1171              :     case GIMPLE_SWITCH:
    1172              :       /* Checked elsewhere.  */
    1173              :       return true;
    1174              : 
    1175        77777 :     case GIMPLE_ASSIGN:
    1176        77777 :       return if_convertible_gimple_assign_stmt_p (stmt, refs);
    1177              : 
    1178         1514 :     case GIMPLE_CALL:
    1179         1514 :       {
    1180              :         /* Check if stmt is a simd clone first.  */
    1181         1514 :         if (if_convertible_simdclone_stmt_p (stmt))
    1182              :           {
    1183         1007 :             gimple_set_plf (stmt, GF_PLF_2, true);
    1184         1007 :             need_to_predicate = true;
    1185         1007 :             return true;
    1186              :           }
    1187              : 
    1188              :         /* Check if the call can trap and if so require predication.  */
    1189          507 :         if (gimple_could_trap_p (stmt))
    1190              :           {
    1191          155 :             if (ifcvt_can_predicate (stmt))
    1192              :               {
    1193          108 :                 gimple_set_plf (stmt, GF_PLF_2, true);
    1194          108 :                 need_to_predicate = true;
    1195          108 :                 return true;
    1196              :               }
    1197              :             else
    1198              :               {
    1199           47 :                 if (dump_file && (dump_flags & TDF_DETAILS))
    1200            0 :                   fprintf (dump_file, "stmt could trap...\n");
    1201              :                 return false;
    1202              :               }
    1203              :           }
    1204              : 
    1205              :         /* Check if it's a prefetch.  Many ISAs contain vectorized and/or
    1206              :            conditional prefetches so if-convert should convert them or remove
    1207              :            them.  Mark them as supported.  */
    1208          352 :         if (gimple_call_builtin_p (stmt, BUILT_IN_PREFETCH))
    1209              :           return true;
    1210              : 
    1211              :         /* There are some IFN_s that are used to replace builtins but have the
    1212              :            same semantics.  Even if MASK_CALL cannot handle them vectorable_call
    1213              :            will insert the proper selection, so do not block conversion.  */
    1214          350 :         int flags = gimple_call_flags (stmt);
    1215          350 :         if ((flags & ECF_CONST)
    1216          350 :             && !(flags & ECF_LOOPING_CONST_OR_PURE)
    1217          700 :             && gimple_call_combined_fn (stmt) != CFN_LAST)
    1218          336 :           return true;
    1219              : 
    1220              :         return false;
    1221              :       }
    1222              : 
    1223            0 :     default:
    1224              :       /* Don't know what to do with 'em so don't do anything.  */
    1225            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1226              :         {
    1227            0 :           fprintf (dump_file, "don't know what to do\n");
    1228            0 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1229              :         }
    1230              :       return false;
    1231              :     }
    1232              : }
    1233              : 
    1234              : /* Assumes that BB has more than 1 predecessors.
    1235              :    Returns false if at least one successor is not on critical edge
    1236              :    and true otherwise.  */
    1237              : 
    1238              : static inline bool
    1239        81693 : all_preds_critical_p (basic_block bb)
    1240              : {
    1241        81693 :   edge e;
    1242        81693 :   edge_iterator ei;
    1243              : 
    1244       160134 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1245       141074 :     if (EDGE_COUNT (e->src->succs) == 1)
    1246              :       return false;
    1247              :   return true;
    1248              : }
    1249              : 
    1250              : /* Return true when BB is if-convertible.  This routine does not check
    1251              :    basic block's statements and phis.
    1252              : 
    1253              :    A basic block is not if-convertible if:
    1254              :    - it is non-empty and it is after the exit block (in BFS order),
    1255              :    - it is after the exit block but before the latch,
    1256              :    - its edges are not normal.
    1257              : 
    1258              :    EXIT_BB is the basic block containing the exit of the LOOP.  BB is
    1259              :    inside LOOP.  */
    1260              : 
    1261              : static bool
    1262       211909 : if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb)
    1263              : {
    1264       211909 :   edge e;
    1265       211909 :   edge_iterator ei;
    1266              : 
    1267       211909 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1268          146 :     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
    1269              : 
    1270       211909 :   if (EDGE_COUNT (bb->succs) > 2)
    1271              :     return false;
    1272              : 
    1273       423690 :   if (gcall *call = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
    1274          202 :     if (gimple_call_ctrl_altering_p (call))
    1275              :       return false;
    1276              : 
    1277       211845 :   if (exit_bb)
    1278              :     {
    1279        38335 :       if (bb != loop->latch)
    1280              :         {
    1281          538 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1282            0 :             fprintf (dump_file, "basic block after exit bb but before latch\n");
    1283              :           return false;
    1284              :         }
    1285        37797 :       else if (!empty_block_p (bb))
    1286              :         {
    1287          645 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1288            0 :             fprintf (dump_file, "non empty basic block after exit bb\n");
    1289              :           return false;
    1290              :         }
    1291        37152 :       else if (bb == loop->latch
    1292        37152 :                && bb != exit_bb
    1293        74304 :                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
    1294              :           {
    1295           11 :             if (dump_file && (dump_flags & TDF_DETAILS))
    1296            0 :               fprintf (dump_file, "latch is not dominated by exit_block\n");
    1297              :             return false;
    1298              :           }
    1299              :     }
    1300              : 
    1301              :   /* Be less adventurous and handle only normal edges.  */
    1302       514975 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1303       304336 :     if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
    1304              :       {
    1305           12 :         if (dump_file && (dump_flags & TDF_DETAILS))
    1306            0 :           fprintf (dump_file, "Difficult to handle edges\n");
    1307              :         return false;
    1308              :       }
    1309              : 
    1310              :   return true;
    1311              : }
    1312              : 
    1313              : /* Return true when all predecessor blocks of BB are visited.  The
    1314              :    VISITED bitmap keeps track of the visited blocks.  */
    1315              : 
    1316              : static bool
    1317      2330839 : pred_blocks_visited_p (basic_block bb, bitmap *visited)
    1318              : {
    1319      2330839 :   edge e;
    1320      2330839 :   edge_iterator ei;
    1321      4015680 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1322      2639263 :     if (!bitmap_bit_p (*visited, e->src->index))
    1323              :       return false;
    1324              : 
    1325              :   return true;
    1326              : }
    1327              : 
    1328              : /* Get body of a LOOP in suitable order for if-conversion.  It is
    1329              :    caller's responsibility to deallocate basic block list.
    1330              :    If-conversion suitable order is, breadth first sort (BFS) order
    1331              :    with an additional constraint: select a block only if all its
    1332              :    predecessors are already selected.  */
    1333              : 
    1334              : static basic_block *
    1335       414581 : get_loop_body_in_if_conv_order (const class loop *loop)
    1336              : {
    1337       414581 :   basic_block *blocks, *blocks_in_bfs_order;
    1338       414581 :   basic_block bb;
    1339       414581 :   bitmap visited;
    1340       414581 :   unsigned int index = 0;
    1341       414581 :   unsigned int visited_count = 0;
    1342              : 
    1343       414581 :   gcc_assert (loop->num_nodes);
    1344       414581 :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
    1345              : 
    1346       414581 :   blocks = XCNEWVEC (basic_block, loop->num_nodes);
    1347       414581 :   visited = BITMAP_ALLOC (NULL);
    1348              : 
    1349       414581 :   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
    1350              : 
    1351       414581 :   index = 0;
    1352      4060438 :   while (index < loop->num_nodes)
    1353              :     {
    1354      3231328 :       bb = blocks_in_bfs_order [index];
    1355              : 
    1356      3231328 :       if (bb->flags & BB_IRREDUCIBLE_LOOP)
    1357              :         {
    1358           52 :           free (blocks_in_bfs_order);
    1359           52 :           BITMAP_FREE (visited);
    1360           52 :           free (blocks);
    1361           52 :           return NULL;
    1362              :         }
    1363              : 
    1364      3231276 :       if (!bitmap_bit_p (visited, bb->index))
    1365              :         {
    1366      2330839 :           if (pred_blocks_visited_p (bb, &visited)
    1367      2330839 :               || bb == loop->header)
    1368              :             {
    1369              :               /* This block is now visited.  */
    1370      1790998 :               bitmap_set_bit (visited, bb->index);
    1371      1790998 :               blocks[visited_count++] = bb;
    1372              :             }
    1373              :         }
    1374              : 
    1375      3231276 :       index++;
    1376              : 
    1377      3231276 :       if (index == loop->num_nodes
    1378       477266 :           && visited_count != loop->num_nodes)
    1379              :         /* Not done yet.  */
    1380      3231276 :         index = 0;
    1381              :     }
    1382       414529 :   free (blocks_in_bfs_order);
    1383       414529 :   BITMAP_FREE (visited);
    1384              : 
    1385              :   /* Go through loop and reject if-conversion or lowering of bitfields if we
    1386              :      encounter statements we do not believe the vectorizer will be able to
    1387              :      handle.  If adding a new type of statement here, make sure
    1388              :      'ifcvt_local_dce' is also able to handle it properly.  */
    1389      2607906 :   for (index = 0; index < loop->num_nodes; index++)
    1390              :     {
    1391      1781443 :       basic_block bb = blocks[index];
    1392      1781443 :       gimple_stmt_iterator gsi;
    1393              : 
    1394      1781443 :       bool may_have_nonlocal_labels
    1395      1781443 :         = bb_with_exit_edge_p (loop, bb) || bb == loop->latch;
    1396     16589331 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1397     13029040 :         switch (gimple_code (gsi_stmt (gsi)))
    1398              :           {
    1399        41226 :           case GIMPLE_LABEL:
    1400        41226 :             if (!may_have_nonlocal_labels)
    1401              :               {
    1402         6916 :                 tree label
    1403         6916 :                   = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi)));
    1404        13832 :                 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
    1405              :                   {
    1406           49 :                     free (blocks);
    1407           49 :                     return NULL;
    1408              :                   }
    1409              :               }
    1410              :             /* Fallthru.  */
    1411     13026445 :           case GIMPLE_ASSIGN:
    1412     13026445 :           case GIMPLE_CALL:
    1413     13026445 :           case GIMPLE_DEBUG:
    1414     13026445 :           case GIMPLE_COND:
    1415     13026445 :           case GIMPLE_SWITCH:
    1416     13026445 :             gimple_set_uid (gsi_stmt (gsi), 0);
    1417     13026445 :             break;
    1418         2546 :           default:
    1419         2546 :             free (blocks);
    1420         2546 :             return NULL;
    1421              :           }
    1422              :     }
    1423              :   return blocks;
    1424              : }
    1425              : 
    1426              : /* Returns true when the analysis of the predicates for all the basic
    1427              :    blocks in LOOP succeeded.
    1428              : 
    1429              :    predicate_bbs first allocates the predicates of the basic blocks.
    1430              :    These fields are then initialized with the tree expressions
    1431              :    representing the predicates under which a basic block is executed
    1432              :    in the LOOP.  As the loop->header is executed at each iteration, it
    1433              :    has the "true" predicate.  Other statements executed under a
    1434              :    condition are predicated with that condition, for example
    1435              : 
    1436              :    | if (x)
    1437              :    |   S1;
    1438              :    | else
    1439              :    |   S2;
    1440              : 
    1441              :    S1 will be predicated with "x", and
    1442              :    S2 will be predicated with "!x".  */
    1443              : 
    1444              : static void
    1445        37141 : predicate_bbs (loop_p loop)
    1446              : {
    1447        37141 :   unsigned int i;
    1448              : 
    1449       243239 :   for (i = 0; i < loop->num_nodes; i++)
    1450       206098 :     init_bb_predicate (ifc_bbs[i]);
    1451              : 
    1452       243239 :   for (i = 0; i < loop->num_nodes; i++)
    1453              :     {
    1454       206098 :       basic_block bb = ifc_bbs[i];
    1455       206098 :       tree cond;
    1456              : 
    1457              :       /* The loop latch and loop exit block are always executed and
    1458              :          have no extra conditions to be processed: skip them.  */
    1459       280380 :       if (bb == loop->latch
    1460       206098 :           || bb_with_exit_edge_p (loop, bb))
    1461              :         {
    1462        74282 :           reset_bb_predicate (bb);
    1463        74282 :           continue;
    1464              :         }
    1465              : 
    1466       131816 :       cond = bb_predicate (bb);
    1467       263632 :       if (gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
    1468              :         {
    1469        53600 :           tree c2;
    1470        53600 :           edge true_edge, false_edge;
    1471        53600 :           location_t loc = gimple_location (stmt);
    1472        53600 :           tree c;
    1473              :           /* gcc.dg/fold-bopcond-1.c shows that despite all forwprop passes
    1474              :              conditions can remain unfolded because of multiple uses so
    1475              :              try to re-fold here, especially to get precision changing
    1476              :              conversions sorted out.  Do not simply fold the stmt since
    1477              :              this is analysis only.  When conditions were embedded in
    1478              :              COND_EXPRs those were folded separately before folding the
    1479              :              COND_EXPR but as they are now outside we have to make sure
    1480              :              to fold them.  Do it here - another opportunity would be to
    1481              :              fold predicates as they are inserted.  */
    1482        53600 :           gimple_match_op cexpr (gimple_match_cond::UNCOND,
    1483        53600 :                                  gimple_cond_code (stmt),
    1484              :                                  boolean_type_node,
    1485              :                                  gimple_cond_lhs (stmt),
    1486        53600 :                                  gimple_cond_rhs (stmt));
    1487        53600 :           if (cexpr.resimplify (NULL, follow_all_ssa_edges)
    1488         4096 :               && cexpr.code.is_tree_code ()
    1489        57696 :               && TREE_CODE_CLASS ((tree_code)cexpr.code) == tcc_comparison)
    1490          560 :             c = build2_loc (loc, (tree_code)cexpr.code, boolean_type_node,
    1491              :                             cexpr.ops[0], cexpr.ops[1]);
    1492              :           else
    1493        53040 :             c = build2_loc (loc, gimple_cond_code (stmt),
    1494              :                             boolean_type_node,
    1495              :                             gimple_cond_lhs (stmt),
    1496              :                             gimple_cond_rhs (stmt));
    1497              : 
    1498              :           /* Add new condition into destination's predicate list.  */
    1499        53600 :           extract_true_false_edges_from_block (gimple_bb (stmt),
    1500              :                                                &true_edge, &false_edge);
    1501              : 
    1502              :           /* If C is true, then TRUE_EDGE is taken.  */
    1503        53600 :           add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
    1504              :                                      unshare_expr (c));
    1505              : 
    1506              :           /* If C is false, then FALSE_EDGE is taken.  */
    1507        53600 :           c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
    1508              :                            unshare_expr (c));
    1509        53600 :           add_to_dst_predicate_list (loop, false_edge,
    1510              :                                      unshare_expr (cond), c2);
    1511              : 
    1512        53600 :           cond = NULL_TREE;
    1513              :         }
    1514              : 
    1515              :       /* Assumes the limited COND like switches checked for earlier.  */
    1516        78216 :       else if (gswitch *sw = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
    1517              :         {
    1518           79 :           location_t loc = gimple_location (*gsi_last_bb (bb));
    1519              : 
    1520           79 :           tree default_label = CASE_LABEL (gimple_switch_default_label (sw));
    1521           79 :           tree cond_label = CASE_LABEL (gimple_switch_label (sw, 1));
    1522              : 
    1523           79 :           edge false_edge = find_edge (bb, label_to_block (cfun, default_label));
    1524           79 :           edge true_edge = find_edge (bb, label_to_block (cfun, cond_label));
    1525              : 
    1526              :           /* Create chain of switch tests for each case.  */
    1527           79 :           tree switch_cond = NULL_TREE;
    1528           79 :           tree index = gimple_switch_index (sw);
    1529          802 :           for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++)
    1530              :             {
    1531          723 :               tree label = gimple_switch_label (sw, i);
    1532          723 :               tree case_cond;
    1533          723 :               if (CASE_HIGH (label))
    1534              :                 {
    1535            7 :                   tree low = build2_loc (loc, GE_EXPR,
    1536              :                                          boolean_type_node,
    1537            7 :                                          index, fold_convert_loc (loc, TREE_TYPE (index),
    1538            7 :                                                  CASE_LOW (label)));
    1539           14 :                   tree high = build2_loc (loc, LE_EXPR,
    1540              :                                           boolean_type_node,
    1541            7 :                                           index, fold_convert_loc (loc, TREE_TYPE (index),
    1542            7 :                                                   CASE_HIGH (label)));
    1543            7 :                   case_cond = build2_loc (loc, TRUTH_AND_EXPR,
    1544              :                                           boolean_type_node,
    1545              :                                           low, high);
    1546              :                 }
    1547              :               else
    1548          716 :                 case_cond = build2_loc (loc, EQ_EXPR,
    1549              :                                         boolean_type_node,
    1550              :                                         index,
    1551          716 :                                         fold_convert_loc (loc, TREE_TYPE (index),
    1552          716 :                                                           CASE_LOW (label)));
    1553          723 :               if (i > 1)
    1554          644 :                 switch_cond = build2_loc (loc, TRUTH_OR_EXPR,
    1555              :                                           boolean_type_node,
    1556              :                                           case_cond, switch_cond);
    1557              :               else
    1558              :                 switch_cond = case_cond;
    1559              :             }
    1560              : 
    1561           79 :           add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
    1562              :                                      unshare_expr (switch_cond));
    1563           79 :           switch_cond = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
    1564              :                                     unshare_expr (switch_cond));
    1565           79 :           add_to_dst_predicate_list (loop, false_edge,
    1566              :                                      unshare_expr (cond), switch_cond);
    1567           79 :           cond = NULL_TREE;
    1568              :         }
    1569              : 
    1570              :       /* If current bb has only one successor, then consider it as an
    1571              :          unconditional goto.  */
    1572       284235 :       if (single_succ_p (bb))
    1573              :         {
    1574        78137 :           basic_block bb_n = single_succ (bb);
    1575              : 
    1576              :           /* The successor bb inherits the predicate of its
    1577              :              predecessor.  If there is no predicate in the predecessor
    1578              :              bb, then consider the successor bb as always executed.  */
    1579        78137 :           if (cond == NULL_TREE)
    1580            0 :             cond = boolean_true_node;
    1581              : 
    1582        78137 :           add_to_predicate_list (loop, bb_n, cond);
    1583              :         }
    1584              :     }
    1585              : 
    1586              :   /* The loop header is always executed.  */
    1587        37141 :   reset_bb_predicate (loop->header);
    1588        37141 :   gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
    1589              :               && bb_predicate_gimplified_stmts (loop->latch) == NULL);
    1590        37141 : }
    1591              : 
    1592              : /* Build region by adding loop pre-header and post-header blocks.  */
    1593              : 
    1594              : static vec<basic_block>
    1595        37141 : build_region (class loop *loop)
    1596              : {
    1597        37141 :   vec<basic_block> region = vNULL;
    1598        37141 :   basic_block exit_bb = NULL;
    1599              : 
    1600        37141 :   gcc_assert (ifc_bbs);
    1601              :   /* The first element is loop pre-header.  */
    1602        37141 :   region.safe_push (loop_preheader_edge (loop)->src);
    1603              : 
    1604       280380 :   for (unsigned int i = 0; i < loop->num_nodes; i++)
    1605              :     {
    1606       206098 :       basic_block bb = ifc_bbs[i];
    1607       206098 :       region.safe_push (bb);
    1608              :       /* Find loop postheader.  */
    1609       206098 :       edge e;
    1610       206098 :       edge_iterator ei;
    1611       457262 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1612       288305 :         if (loop_exit_edge_p (loop, e))
    1613              :           {
    1614        37141 :               exit_bb = e->dest;
    1615        37141 :               break;
    1616              :           }
    1617              :     }
    1618              :   /* The last element is loop post-header.  */
    1619        37141 :   gcc_assert (exit_bb);
    1620        37141 :   region.safe_push (exit_bb);
    1621        37141 :   return region;
    1622              : }
    1623              : 
    1624              : /* Return true when LOOP is if-convertible.  This is a helper function
    1625              :    for if_convertible_loop_p.  REFS and DDRS are initialized and freed
    1626              :    in if_convertible_loop_p.  */
    1627              : 
    1628              : static bool
    1629        38411 : if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs)
    1630              : {
    1631        38411 :   unsigned int i;
    1632        38411 :   basic_block exit_bb = NULL;
    1633        38411 :   vec<basic_block> region;
    1634              : 
    1635        38411 :   calculate_dominance_info (CDI_DOMINATORS);
    1636              : 
    1637       287461 :   for (i = 0; i < loop->num_nodes; i++)
    1638              :     {
    1639       211909 :       basic_block bb = ifc_bbs[i];
    1640              : 
    1641       211909 :       if (!if_convertible_bb_p (loop, bb, exit_bb))
    1642              :         return false;
    1643              : 
    1644       210639 :       if (bb_with_exit_edge_p (loop, bb))
    1645        38335 :         exit_bb = bb;
    1646              :     }
    1647              : 
    1648        37141 :   data_reference_p dr;
    1649              : 
    1650        37141 :   innermost_DR_map
    1651        37141 :           = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
    1652        37141 :   baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
    1653              : 
    1654              :   /* Compute post-dominator tree locally.  */
    1655        37141 :   region = build_region (loop);
    1656        37141 :   calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);
    1657              : 
    1658        37141 :   predicate_bbs (loop);
    1659              : 
    1660              :   /* Free post-dominator tree since it is not used after predication.  */
    1661        37141 :   free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
    1662        37141 :   region.release ();
    1663              : 
    1664       194510 :   for (i = 0; refs->iterate (i, &dr); i++)
    1665              :     {
    1666       120228 :       tree ref = DR_REF (dr);
    1667              : 
    1668       120228 :       dr->aux = XNEW (struct ifc_dr);
    1669       120228 :       DR_BASE_W_UNCONDITIONALLY (dr) = false;
    1670       120228 :       DR_RW_UNCONDITIONALLY (dr) = false;
    1671       120228 :       DR_W_UNCONDITIONALLY (dr) = false;
    1672       120228 :       IFC_DR (dr)->rw_predicate = boolean_false_node;
    1673       120228 :       IFC_DR (dr)->w_predicate = boolean_false_node;
    1674       120228 :       IFC_DR (dr)->base_w_predicate = boolean_false_node;
    1675       120228 :       if (gimple_uid (DR_STMT (dr)) == 0)
    1676       119545 :         gimple_set_uid (DR_STMT (dr), i + 1);
    1677              : 
    1678              :       /* If DR doesn't have innermost loop behavior or it's a compound
    1679              :          memory reference, we synthesize its innermost loop behavior
    1680              :          for hashing.  */
    1681       120228 :       if (TREE_CODE (ref) == COMPONENT_REF
    1682              :           || TREE_CODE (ref) == IMAGPART_EXPR
    1683              :           || TREE_CODE (ref) == REALPART_EXPR
    1684        83179 :           || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
    1685        26534 :                || DR_INIT (dr) || DR_STEP (dr)))
    1686              :         {
    1687       108667 :           while (TREE_CODE (ref) == COMPONENT_REF
    1688        64742 :                  || TREE_CODE (ref) == IMAGPART_EXPR
    1689       172831 :                  || TREE_CODE (ref) == REALPART_EXPR)
    1690        45084 :             ref = TREE_OPERAND (ref, 0);
    1691              : 
    1692        63583 :           memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr)));
    1693        63583 :           DR_BASE_ADDRESS (dr) = ref;
    1694              :         }
    1695       120228 :       hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
    1696              :     }
    1697              : 
    1698       186363 :   for (i = 0; i < loop->num_nodes; i++)
    1699              :     {
    1700       160643 :       basic_block bb = ifc_bbs[i];
    1701       160643 :       gimple_stmt_iterator itr;
    1702              : 
    1703              :       /* Check the if-convertibility of statements in predicated BBs.  */
    1704       160643 :       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    1705       293430 :         for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
    1706       169077 :           if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
    1707        38411 :             return false;
    1708              :     }
    1709              : 
    1710              :   /* Checking PHIs needs to be done after stmts, as the fact whether there
    1711              :      are any masked loads or stores affects the tests.  Also check switch
    1712              :      stmts for supported shape as that cannot be skipped for always
    1713              :      executed blocks.  */
    1714       160879 :   for (i = 0; i < loop->num_nodes; i++)
    1715              :     {
    1716       135165 :       basic_block bb = ifc_bbs[i];
    1717       135165 :       gphi_iterator itr;
    1718              : 
    1719       265178 :       for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
    1720       130013 :         if (!if_convertible_phi_p (loop, bb, itr.phi ()))
    1721            6 :           return false;
    1722       352643 :       if (gswitch *s = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
    1723           70 :         if (!if_convertible_switch_p (s))
    1724            6 :           return false;
    1725              :     }
    1726              : 
    1727        25714 :   if (dump_file)
    1728           42 :     fprintf (dump_file, "Applying if-conversion\n");
    1729              : 
    1730              :   return true;
    1731              : }
    1732              : 
    1733              : /* Return true when LOOP is if-convertible.
    1734              :    LOOP is if-convertible if:
    1735              :    - it is innermost,
    1736              :    - it has two or more basic blocks,
    1737              :    - it has only one exit,
    1738              :    - loop header is not the exit edge,
    1739              :    - if its basic blocks and phi nodes are if convertible.  */
    1740              : 
    1741              : static bool
    1742        38552 : if_convertible_loop_p (class loop *loop, vec<data_reference_p> *refs)
    1743              : {
    1744        38552 :   edge e;
    1745        38552 :   edge_iterator ei;
    1746        38552 :   bool res = false;
    1747              : 
    1748              :   /* Handle only innermost loop.  */
    1749        38552 :   if (!loop || loop->inner)
    1750              :     {
    1751            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1752            0 :         fprintf (dump_file, "not innermost loop\n");
    1753              :       return false;
    1754              :     }
    1755              : 
    1756              :   /* If only one block, no need for if-conversion.  */
    1757        38552 :   if (loop->num_nodes <= 2)
    1758              :     {
    1759            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1760            0 :         fprintf (dump_file, "less than 2 basic blocks\n");
    1761              :       return false;
    1762              :     }
    1763              : 
    1764              :   /* If one of the loop header's edge is an exit edge then do not
    1765              :      apply if-conversion.  */
    1766       115536 :   FOR_EACH_EDGE (e, ei, loop->header->succs)
    1767        77125 :     if (loop_exit_edge_p (loop, e))
    1768              :       return false;
    1769              : 
    1770        38411 :   res = if_convertible_loop_p_1 (loop, refs);
    1771              : 
    1772        75552 :   delete innermost_DR_map;
    1773        38411 :   innermost_DR_map = NULL;
    1774              : 
    1775        75552 :   delete baseref_DR_map;
    1776        38411 :   baseref_DR_map = NULL;
    1777              : 
    1778        38411 :   return res;
    1779              : }
    1780              : 
    1781              : /* Return reduc_1 if has_nop.
    1782              : 
    1783              :    if (...)
    1784              :      tmp1 = (unsigned type) reduc_1;
    1785              :      tmp2 = tmp1 + rhs2;
    1786              :      reduc_3 = (signed type) tmp2.  */
    1787              : static tree
    1788        11654 : strip_nop_cond_scalar_reduction (bool has_nop, tree op)
    1789              : {
    1790        11654 :   if (!has_nop)
    1791              :     return op;
    1792              : 
    1793          414 :   if (TREE_CODE (op) != SSA_NAME)
    1794              :     return NULL_TREE;
    1795              : 
    1796          368 :   gassign *stmt = safe_dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op));
    1797          368 :   if (!stmt
    1798          368 :       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
    1799          230 :       || !tree_nop_conversion_p (TREE_TYPE (op), TREE_TYPE
    1800              :                                  (gimple_assign_rhs1 (stmt))))
    1801              :     return NULL_TREE;
    1802              : 
    1803          219 :   return gimple_assign_rhs1 (stmt);
    1804              : }
    1805              : 
    1806              : /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
    1807              :    which is in predicated basic block.
    1808              :    In fact, the following PHI pattern is searching:
    1809              :       loop-header:
    1810              :         reduc_1 = PHI <..., reduc_2>
    1811              :       ...
    1812              :         if (...)
    1813              :           reduc_3 = ...
    1814              :         reduc_2 = PHI <reduc_1, reduc_3>
    1815              : 
    1816              :    ARG_0 and ARG_1 are correspondent PHI arguments.
    1817              :    REDUC, OP0 and OP1 contain reduction stmt and its operands.
    1818              :    INTERMEDIATE is true if PHI does not directly feed the loop-header PHI.
    1819              :    EXTENDED is true if PHI has > 2 arguments.  */
    1820              : 
    1821              : static bool
    1822        47533 : is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
    1823              :                           tree *op0, tree *op1, bool extended, bool* has_nop,
    1824              :                           gimple **nop_reduc, bool *intermediate)
    1825              : {
    1826        47533 :   tree lhs, r_op1, r_op2, r_nop1, r_nop2;
    1827        47533 :   gimple *stmt;
    1828        47533 :   gimple *header_phi = NULL;
    1829        47533 :   enum tree_code reduction_op;
    1830        47533 :   basic_block bb = gimple_bb (phi);
    1831        47533 :   class loop *loop = bb->loop_father;
    1832        47533 :   edge latch_e = loop_latch_edge (loop);
    1833        47533 :   imm_use_iterator imm_iter;
    1834        47533 :   use_operand_p use_p;
    1835        47533 :   edge e;
    1836        47533 :   edge_iterator ei;
    1837        47533 :   bool result = *has_nop = *intermediate = false;
    1838        47533 :   if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
    1839              :     return false;
    1840              : 
    1841        34851 :   if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
    1842              :     {
    1843         8756 :       lhs = arg_1;
    1844         8756 :       header_phi = SSA_NAME_DEF_STMT (arg_0);
    1845         8756 :       stmt = SSA_NAME_DEF_STMT (arg_1);
    1846              :     }
    1847        26095 :   else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
    1848              :     {
    1849        11461 :       lhs = arg_0;
    1850        11461 :       header_phi = SSA_NAME_DEF_STMT (arg_1);
    1851        11461 :       stmt = SSA_NAME_DEF_STMT (arg_0);
    1852              :     }
    1853              :   else
    1854              :     return false;
    1855        20217 :   if (gimple_bb (header_phi) != loop->header)
    1856              :     return false;
    1857              : 
    1858        19331 :   tree latch_value = PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e);
    1859        19331 :   *intermediate = latch_value != PHI_RESULT (phi);
    1860              : 
    1861        19331 :   if (gimple_code (stmt) != GIMPLE_ASSIGN
    1862        19331 :       || gimple_has_volatile_ops (stmt))
    1863              :     return false;
    1864              : 
    1865        14714 :   if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
    1866              :     return false;
    1867              : 
    1868        14609 :   if (!is_predicated (gimple_bb (stmt)))
    1869              :     return false;
    1870              : 
    1871              :   /* Check that stmt-block is predecessor of phi-block.  */
    1872        11610 :   FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
    1873        11357 :     if (e->dest == bb)
    1874              :       {
    1875              :         result = true;
    1876              :         break;
    1877              :       }
    1878        11104 :   if (!result)
    1879              :     return false;
    1880              : 
    1881        10851 :   if (!has_single_use (lhs))
    1882              :     return false;
    1883              : 
    1884        10781 :   reduction_op = gimple_assign_rhs_code (stmt);
    1885              : 
    1886              :     /* Catch something like below
    1887              : 
    1888              :      loop-header:
    1889              :      reduc_1 = PHI <..., reduc_2>
    1890              :      ...
    1891              :      if (...)
    1892              :      tmp1 = (unsigned type) reduc_1;
    1893              :      tmp2 = tmp1 + rhs2;
    1894              :      reduc_3 = (signed type) tmp2;
    1895              : 
    1896              :      reduc_2 = PHI <reduc_1, reduc_3>
    1897              : 
    1898              :      and convert to
    1899              : 
    1900              :      reduc_2 = PHI <0, reduc_1>
    1901              :      tmp1 = (unsigned type)reduc_1;
    1902              :      ifcvt = cond_expr ? rhs2 : 0
    1903              :      tmp2 = tmp1 +/- ifcvt;
    1904              :      reduc_1 = (signed type)tmp2;  */
    1905              : 
    1906        10781 :   if (CONVERT_EXPR_CODE_P (reduction_op))
    1907              :     {
    1908          449 :       lhs = gimple_assign_rhs1 (stmt);
    1909          449 :       if (TREE_CODE (lhs) != SSA_NAME
    1910          449 :           || !has_single_use (lhs))
    1911              :         return false;
    1912              : 
    1913          255 :       *nop_reduc = stmt;
    1914          255 :       stmt = SSA_NAME_DEF_STMT (lhs);
    1915          255 :       if (gimple_bb (stmt) != gimple_bb (*nop_reduc)
    1916          255 :           || !is_gimple_assign (stmt))
    1917              :         return false;
    1918              : 
    1919          246 :       *has_nop = true;
    1920          246 :       reduction_op = gimple_assign_rhs_code (stmt);
    1921              :     }
    1922              : 
    1923              :   /* A reduction with a further latch update must keep the PLUS outside
    1924              :      the conditional expression.  The no-op conversion case is not needed
    1925              :      for this form.  */
    1926        10578 :   if (*intermediate && (*has_nop || reduction_op != PLUS_EXPR))
    1927              :     return false;
    1928              : 
    1929        10346 :   if (reduction_op != PLUS_EXPR
    1930              :       && reduction_op != MINUS_EXPR
    1931        10346 :       && reduction_op != MULT_EXPR
    1932        10346 :       && reduction_op != BIT_IOR_EXPR
    1933              :       && reduction_op != BIT_XOR_EXPR
    1934         4639 :       && reduction_op != BIT_AND_EXPR)
    1935              :     return false;
    1936         5827 :   r_op1 = gimple_assign_rhs1 (stmt);
    1937         5827 :   r_op2 = gimple_assign_rhs2 (stmt);
    1938              : 
    1939         5827 :   r_nop1 = strip_nop_cond_scalar_reduction (*has_nop, r_op1);
    1940         5827 :   r_nop2 = strip_nop_cond_scalar_reduction (*has_nop, r_op2);
    1941              : 
    1942              :   /* Make R_OP1 to hold reduction variable.  */
    1943         5827 :   if (r_nop2 == PHI_RESULT (header_phi)
    1944         5827 :       && commutative_tree_code (reduction_op))
    1945              :     {
    1946              :       std::swap (r_op1, r_op2);
    1947              :       std::swap (r_nop1, r_nop2);
    1948              :     }
    1949         4665 :   else if (r_nop1 != PHI_RESULT (header_phi))
    1950              :     return false;
    1951              : 
    1952         5501 :   if (*intermediate)
    1953              :     {
    1954          120 :       tree type = TREE_TYPE (gimple_assign_lhs (stmt));
    1955          120 :       if (!SCALAR_FLOAT_TYPE_P (type)
    1956          120 :           && (!INTEGRAL_TYPE_P (type) || TYPE_OVERFLOW_TRAPS (type)))
    1957              :         return false;
    1958              : 
    1959          120 :       tree zero = neutral_op_for_reduction (type, PLUS_EXPR, NULL_TREE,
    1960              :                                             false);
    1961              :       /* The inactive addend must leave the reduction value unchanged.  */
    1962          120 :       if (SCALAR_FLOAT_TYPE_P (type)
    1963          120 :           && !fold_real_zero_addition_p (type, r_op1, zero, 0))
    1964              :         return false;
    1965              :     }
    1966              : 
    1967         5499 :   if (*has_nop)
    1968              :     {
    1969              :       /* Check that R_NOP1 is used in nop_stmt or in PHI only.  */
    1970          430 :       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_nop1)
    1971              :         {
    1972          304 :           gimple *use_stmt = USE_STMT (use_p);
    1973          304 :           if (is_gimple_debug (use_stmt))
    1974            0 :             continue;
    1975          304 :           if (use_stmt == SSA_NAME_DEF_STMT (r_op1))
    1976          126 :             continue;
    1977          178 :           if (use_stmt != phi)
    1978           42 :             return false;
    1979          168 :         }
    1980              :     }
    1981              : 
    1982              :   /* Check that R_OP1 is used in reduction stmt or in PHI only.  */
    1983        16891 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
    1984              :     {
    1985        11702 :       gimple *use_stmt = USE_STMT (use_p);
    1986        11702 :       if (is_gimple_debug (use_stmt))
    1987           29 :         continue;
    1988        11673 :       if (use_stmt == stmt)
    1989         5214 :         continue;
    1990         6459 :       if (gimple_code (use_stmt) != GIMPLE_PHI)
    1991          268 :         return false;
    1992          268 :     }
    1993              : 
    1994         5189 :   *op0 = r_op1; *op1 = r_op2;
    1995         5189 :   *reduc = stmt;
    1996         5189 :   return true;
    1997              : }
    1998              : 
    1999              : /* Converts conditional scalar reduction into unconditional form, e.g.
    2000              :      bb_4
    2001              :        if (_5 != 0) goto bb_5 else goto bb_6
    2002              :      end_bb_4
    2003              :      bb_5
    2004              :        res_6 = res_13 + 1;
    2005              :      end_bb_5
    2006              :      bb_6
    2007              :        # res_2 = PHI <res_13(4), res_6(5)>
    2008              :      end_bb_6
    2009              : 
    2010              :    will be converted into sequence
    2011              :     _ifc__1 = _5 != 0 ? 1 : 0;
    2012              :     res_2 = res_13 + _ifc__1;
    2013              :   Argument SWAP tells that arguments of conditional expression should be
    2014              :   swapped.  INTERMEDIATE says that this is not the latch value, so the
    2015              :   PLUS must remain unconditional.
    2016              :   We can assume that we versioned the loop for vectorization, so can
    2017              :   create a COND_OP.
    2018              :   Returns rhs of resulting PHI assignment.  */
    2019              : 
    2020              : static tree
    2021         5189 : convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
    2022              :                                tree cond, tree op0, tree op1, bool swap,
    2023              :                                bool has_nop, gimple* nop_reduc,
    2024              :                                bool intermediate)
    2025              : {
    2026         5189 :   gimple_stmt_iterator stmt_it;
    2027         5189 :   gimple *new_assign;
    2028         5189 :   tree rhs;
    2029         5189 :   tree rhs1 = gimple_assign_rhs1 (reduc);
    2030         5189 :   tree lhs = gimple_assign_lhs (reduc);
    2031         5189 :   tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
    2032         5189 :   tree c;
    2033         5189 :   enum tree_code reduction_op  = gimple_assign_rhs_code (reduc);
    2034         5189 :   tree op_nochange = neutral_op_for_reduction (TREE_TYPE (rhs1), reduction_op,
    2035              :                                                NULL, false);
    2036         5189 :   gimple_seq stmts = NULL;
    2037              : 
    2038         5189 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2039              :     {
    2040           12 :       fprintf (dump_file, "Found cond scalar reduction.\n");
    2041           12 :       print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
    2042              :     }
    2043              : 
    2044              :   /* If possible create a COND_OP instead of a COND_EXPR and an OP_EXPR.
    2045              :      The COND_OP will have a neutral_op else value.  */
    2046         5189 :   internal_fn ifn;
    2047         5189 :   ifn = get_conditional_internal_fn (reduction_op);
    2048         5189 :   if (!intermediate
    2049         5189 :       && ifn != IFN_LAST
    2050         5080 :       && vectorized_internal_fn_supported_p (ifn, TREE_TYPE (lhs))
    2051         1363 :       && !VECTOR_TYPE_P (TREE_TYPE (lhs))
    2052         6552 :       && !swap)
    2053              :     {
    2054         1343 :       gcall *cond_call = gimple_build_call_internal (ifn, 4,
    2055              :                                                      unshare_expr (cond),
    2056              :                                                      op0, op1, op0);
    2057         1343 :       gsi_insert_before (gsi, cond_call, GSI_SAME_STMT);
    2058         1343 :       gimple_call_set_lhs (cond_call, tmp);
    2059              :       rhs = tmp;
    2060              :     }
    2061              :   else
    2062              :     {
    2063              :       /* Build cond expression using COND and constant operand
    2064              :          of reduction rhs.  */
    2065         7427 :       c = fold_build_cond_expr (TREE_TYPE (rhs1),
    2066              :                                 unshare_expr (cond),
    2067              :                                 swap ? op_nochange : op1,
    2068              :                                 swap ? op1 : op_nochange);
    2069              :       /* Create assignment stmt and insert it at GSI.  */
    2070         3846 :       new_assign = gimple_build_assign (tmp, c);
    2071         3846 :       gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
    2072              :       /* Build rhs for unconditional increment/decrement/logic_operation.  */
    2073         3846 :       rhs = gimple_build (&stmts, reduction_op,
    2074         3846 :                           TREE_TYPE (rhs1), op0, tmp);
    2075              :     }
    2076              : 
    2077         5189 :   if (has_nop)
    2078              :     {
    2079          126 :       rhs = gimple_convert (&stmts,
    2080          126 :                             TREE_TYPE (gimple_assign_lhs (nop_reduc)), rhs);
    2081          126 :       stmt_it = gsi_for_stmt (nop_reduc);
    2082          126 :       gsi_remove (&stmt_it, true);
    2083          126 :       release_defs (nop_reduc);
    2084              :     }
    2085         5189 :   gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
    2086              : 
    2087              :   /* Delete original reduction stmt.  */
    2088         5189 :   stmt_it = gsi_for_stmt (reduc);
    2089         5189 :   gsi_remove (&stmt_it, true);
    2090         5189 :   release_defs (reduc);
    2091         5189 :   return rhs;
    2092              : }
    2093              : 
    2094              : /* Generate a simplified conditional.  */
    2095              : 
    2096              : static tree
    2097        53823 : gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set)
    2098              : {
    2099              :   /* Check if the value is already live in a previous branch.  This resolves
    2100              :      nested conditionals from diamond PHI reductions.  */
    2101        53823 :   if (TREE_CODE (cond) == SSA_NAME)
    2102              :     {
    2103        53815 :       gimple *stmt = SSA_NAME_DEF_STMT (cond);
    2104        53815 :       gassign *assign = NULL;
    2105        53815 :       if ((assign = as_a <gassign *> (stmt))
    2106        53815 :            && gimple_assign_rhs_code (assign) == BIT_AND_EXPR)
    2107              :         {
    2108         3573 :           tree arg1 = gimple_assign_rhs1 (assign);
    2109         3573 :           tree arg2 = gimple_assign_rhs2 (assign);
    2110         3573 :           if (cond_set.contains ({ arg1, 1 }))
    2111          162 :             arg1 = boolean_true_node;
    2112              :           else
    2113         3411 :             arg1 = gen_simplified_condition (arg1, cond_set);
    2114              : 
    2115         3573 :           if (cond_set.contains ({ arg2, 1 }))
    2116         1788 :             arg2 = boolean_true_node;
    2117              :           else
    2118         1785 :             arg2 = gen_simplified_condition (arg2, cond_set);
    2119              : 
    2120         3573 :           cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, arg1, arg2);
    2121              :         }
    2122              :     }
    2123        53823 :   return cond;
    2124              : }
    2125              : 
    2126              : /* Structure used to track meta-data on PHI arguments used to generate
    2127              :    most efficient comparison sequence to slatten a PHI node.  */
    2128              : 
    2129              : typedef struct ifcvt_arg_entry
    2130              : {
    2131              :   /* The PHI node argument value.  */
    2132              :   tree arg;
    2133              : 
    2134              :   /* The number of compares required to reach this PHI node from start of the
    2135              :      BB being if-converted.  */
    2136              :   unsigned num_compares;
    2137              : 
    2138              :   /* The number of times this PHI node argument appears in the current PHI
    2139              :      node.  */
    2140              :   unsigned occurs;
    2141              : 
    2142              :   /* The indices at which this PHI arg occurs inside the PHI node.  */
    2143              :   vec <int> *indexes;
    2144              : } ifcvt_arg_entry_t;
    2145              : 
    2146              : /* Produce condition for all occurrences of ARG in PHI node.  Set *INVERT
    2147              :    as to whether the condition is inverted.  */
    2148              : 
    2149              : static tree
    2150         4253 : gen_phi_arg_condition (gphi *phi, ifcvt_arg_entry_t &arg,
    2151              :                        gimple_stmt_iterator *gsi,
    2152              :                        scalar_cond_masked_set_type &cond_set, bool *invert)
    2153              : {
    2154         4253 :   int len;
    2155         4253 :   int i;
    2156         4253 :   tree cond = NULL_TREE;
    2157         4253 :   tree c;
    2158         4253 :   edge e;
    2159              : 
    2160         4253 :   *invert = false;
    2161         4253 :   len = arg.indexes->length ();
    2162         4253 :   gcc_assert (len > 0);
    2163         8564 :   for (i = 0; i < len; i++)
    2164              :     {
    2165         4311 :       e = gimple_phi_arg_edge (phi, (*arg.indexes)[i]);
    2166         4311 :       c = bb_predicate (e->src);
    2167         4311 :       if (is_true_predicate (c))
    2168              :         {
    2169            0 :           cond = c;
    2170            0 :           break;
    2171              :         }
    2172              :       /* If we have just a single inverted predicate, signal that and
    2173              :          instead invert the COND_EXPR arms.  */
    2174         4311 :       if (len == 1 && TREE_CODE (c) == TRUTH_NOT_EXPR)
    2175              :         {
    2176           93 :           c = TREE_OPERAND (c, 0);
    2177           93 :           *invert = true;
    2178              :         }
    2179              : 
    2180         4311 :       c = gen_simplified_condition (c, cond_set);
    2181         4311 :       c = force_gimple_operand_gsi (gsi, unshare_expr (c),
    2182              :                                     true, NULL_TREE, true, GSI_SAME_STMT);
    2183         4311 :       if (cond != NULL_TREE)
    2184              :         {
    2185              :           /* Must build OR expression.  */
    2186           58 :           cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
    2187           58 :           cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
    2188              :                                            NULL_TREE, true, GSI_SAME_STMT);
    2189              :         }
    2190              :       else
    2191              :         cond = c;
    2192              : 
    2193              :       /* Register the new possibly simplified conditional.  When more than 2
    2194              :          entries in a phi node we chain entries in the false branch, so the
    2195              :          inverted condition is active.  */
    2196         4311 :       scalar_cond_masked_key pred_cond ({ cond, 1 });
    2197         4311 :       if (!*invert)
    2198         4218 :         pred_cond.inverted_p = !pred_cond.inverted_p;
    2199         4311 :       cond_set.add (pred_cond);
    2200              :     }
    2201         4253 :   gcc_assert (cond != NULL_TREE);
    2202         4253 :   return cond;
    2203              : }
    2204              : 
    2205              : /* Factors out an operation from *ARG0 and *ARG1 and
    2206              :    create the new statement at GSI. *RES is the
    2207              :    result of that new statement. Update *ARG0 and *ARG1
    2208              :    and *RES to the new values if the factoring happened.
    2209              :    Loops until all of the factoring is completed.  */
    2210              : 
    2211              : static void
    2212        44316 : factor_out_operators (tree *res, gimple_stmt_iterator *gsi,
    2213              :                       tree *arg0, tree *arg1, gphi *phi)
    2214              : {
    2215        44316 :   gimple_match_op arg0_op, arg1_op;
    2216        44316 :   bool repeated = false;
    2217              : 
    2218        44909 : again:
    2219        44909 :   if (TREE_CODE (*arg0) != SSA_NAME || TREE_CODE (*arg1) != SSA_NAME)
    2220              :     return;
    2221              : 
    2222        33228 :   if (operand_equal_p (*arg0, *arg1))
    2223              :     return;
    2224              : 
    2225              :   /* If either args have > 1 use, then this transformation actually
    2226              :      increases the number of expressions evaluated at runtime.  */
    2227        33228 :   if (repeated
    2228        33228 :       ? (!has_zero_uses (*arg0) || !has_zero_uses (*arg1))
    2229        32687 :       : (!has_single_use (*arg0) || !has_single_use (*arg1)))
    2230              :     return;
    2231              : 
    2232         5291 :   gimple *arg0_def_stmt = SSA_NAME_DEF_STMT (*arg0);
    2233         5291 :   if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
    2234              :     return;
    2235              : 
    2236              :   /* Might pick up abnormals from previous bbs so stop the loop.  */
    2237         2013 :   if (arg0_op.operands_occurs_in_abnormal_phi ())
    2238              :     return;
    2239              : 
    2240         2011 :   gimple *arg1_def_stmt = SSA_NAME_DEF_STMT (*arg1);
    2241         2011 :   if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
    2242              :     return;
    2243              : 
    2244              :   /* Might pick up abnormals from previous bbs so stop the loop.  */
    2245         1692 :   if (arg1_op.operands_occurs_in_abnormal_phi ())
    2246              :     return;
    2247              : 
    2248              :   /* No factoring can happen if the codes are different
    2249              :      or the number operands.  */
    2250         1692 :   if (arg1_op.code != arg0_op.code
    2251         1692 :       || arg1_op.num_ops != arg0_op.num_ops)
    2252              :     return;
    2253              : 
    2254          723 :   tree new_arg0, new_arg1;
    2255          723 :   int opnum = find_different_opnum (arg0_op, arg1_op, &new_arg0, &new_arg1);
    2256          723 :   if (opnum == -1)
    2257              :     return;
    2258              : 
    2259          614 :   tree args[2] = { new_arg0, new_arg1 };
    2260          614 :   location_t locs[2];
    2261          614 :   locs[0] = gimple_location (arg0_def_stmt);
    2262          614 :   locs[1] = gimple_location (arg1_def_stmt);
    2263          614 :   if (!factor_operation_ok (arg1_op.code, opnum, args, locs, 2, true, true))
    2264              :     return;
    2265              : 
    2266          593 :   tree new_res = make_ssa_name (TREE_TYPE (new_arg0), NULL);
    2267              : 
    2268              :   /* Create the operation stmt if possible and insert it.  */
    2269              : 
    2270          593 :   gimple_match_op new_op = arg0_op;
    2271          593 :   new_op.ops[opnum] = new_res;
    2272          593 :   gimple_seq seq = NULL;
    2273          593 :   tree result = *res;
    2274          593 :   result = maybe_push_res_to_seq (&new_op, &seq, result);
    2275              : 
    2276              :   /* If we can't create the new statement, release the temp name
    2277              :      and return back.  */
    2278          593 :   if (!result)
    2279              :     {
    2280            0 :       release_ssa_name (new_res);
    2281            0 :       return;
    2282              :     }
    2283          593 :   gsi_insert_seq_before (gsi, seq, GSI_CONTINUE_LINKING);
    2284              : 
    2285          593 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2286              :     {
    2287            1 :       fprintf (dump_file, "PHI ");
    2288            1 :       print_generic_expr (dump_file, gimple_phi_result (phi));
    2289            1 :       fprintf (dump_file,
    2290              :                " changed to factor operation out from COND_EXPR.\n");
    2291            1 :       fprintf (dump_file, "New stmt with OPERATION that defines ");
    2292            1 :       print_generic_expr (dump_file, result);
    2293            1 :       fprintf (dump_file, ".\n");
    2294              :     }
    2295              : 
    2296              :   /* Remove the old operation(s) that has single use.  */
    2297          593 :   gimple_stmt_iterator gsi_for_def;
    2298              : 
    2299          593 :   gsi_for_def = gsi_for_stmt (arg0_def_stmt);
    2300          593 :   gsi_remove (&gsi_for_def, true);
    2301          593 :   release_defs (arg0_def_stmt);
    2302          593 :   gsi_for_def = gsi_for_stmt (arg1_def_stmt);
    2303          593 :   gsi_remove (&gsi_for_def, true);
    2304          593 :   release_defs (arg1_def_stmt);
    2305              : 
    2306              :   /* Update the arguments and try again.  */
    2307          593 :   *arg0 = new_arg0;
    2308          593 :   *arg1 = new_arg1;
    2309          593 :   *res = new_res;
    2310              : 
    2311              :   /* Update the phi node too. */
    2312          593 :   gimple_phi_set_result (phi, new_res);
    2313          593 :   SET_PHI_ARG_DEF (phi, 0, new_arg0);
    2314          593 :   SET_PHI_ARG_DEF (phi, 1, new_arg1);
    2315          593 :   update_stmt (phi);
    2316              : 
    2317          593 :   repeated = true;
    2318          593 :   goto again;
    2319              : }
    2320              : 
    2321              : /* Create the smallest nested conditional possible.  On pre-order we record
    2322              :    which conditionals are live, and on post-order rewrite the chain by removing
    2323              :    already active conditions.
    2324              : 
    2325              :    As an example we simplify:
    2326              : 
    2327              :   _7 = a_10 < 0;
    2328              :   _21 = a_10 >= 0;
    2329              :   _22 = a_10 < e_11(D);
    2330              :   _23 = _21 & _22;
    2331              :   _ifc__42 = _23 ? t_13 : 0;
    2332              :   t_6 = _7 ? 1 : _ifc__42
    2333              : 
    2334              :   into
    2335              : 
    2336              :   _7 = a_10 < 0;
    2337              :   _22 = a_10 < e_11(D);
    2338              :   _ifc__42 = _22 ? t_13 : 0;
    2339              :   t_6 = _7 ? 1 : _ifc__42;
    2340              : 
    2341              :   which produces better code.  */
    2342              : 
    2343              : static tree
    2344         6377 : gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi,
    2345              :                         scalar_cond_masked_set_type &cond_set, tree type,
    2346              :                         gimple **res_stmt, tree lhs0,
    2347              :                         vec<struct ifcvt_arg_entry> &args, unsigned idx)
    2348              : {
    2349        12754 :   if (idx == args.length ())
    2350         2124 :     return args[idx - 1].arg;
    2351              : 
    2352         4253 :   bool invert;
    2353         4253 :   tree cond = gen_phi_arg_condition (phi, args[idx - 1], gsi, cond_set,
    2354              :                                      &invert);
    2355         4253 :   tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, res_stmt, lhs0,
    2356              :                                       args, idx + 1);
    2357              : 
    2358         4253 :   unsigned prev = idx;
    2359         4253 :   unsigned curr = prev - 1;
    2360         4253 :   tree arg0 = args[curr].arg;
    2361         4253 :   tree rhs, lhs;
    2362         4253 :   if (idx > 1)
    2363         2129 :     lhs = make_temp_ssa_name (type, NULL, "_ifc_");
    2364              :   else
    2365              :     lhs = lhs0;
    2366              : 
    2367         4253 :   if (invert)
    2368           93 :     rhs = fold_build_cond_expr (type, unshare_expr (cond),
    2369              :                                 arg1, arg0);
    2370              :   else
    2371         4160 :     rhs = fold_build_cond_expr (type, unshare_expr (cond),
    2372              :                                 arg0, arg1);
    2373         4253 :   gassign *new_stmt = gimple_build_assign (lhs, rhs);
    2374         4253 :   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    2375         4253 :   update_stmt (new_stmt);
    2376         4253 :   *res_stmt = new_stmt;
    2377         4253 :   return lhs;
    2378              : }
    2379              : 
    2380              : /* When flattening a PHI node we have a choice of which conditions to test to
    2381              :    for all the paths from the start of the dominator block of the BB with the
    2382              :    PHI node.  If the PHI node has X arguments we have to only test X - 1
    2383              :    conditions as the last one is implicit.  It does matter which conditions we
    2384              :    test first.  We should test the shortest condition first (distance here is
    2385              :    measures in the number of logical operators in the condition) and the
    2386              :    longest one last.  This allows us to skip testing the most expensive
    2387              :    condition.  To accomplish this we need to sort the conditions.  P1 and P2
    2388              :    are sorted first based on the number of logical operations (num_compares)
    2389              :    and then by how often they occur in the PHI node.  */
    2390              : 
    2391              : static int
    2392        36416 : cmp_arg_entry (const void *p1, const void *p2, void * /* data.  */)
    2393              : {
    2394        36416 :   const ifcvt_arg_entry sval1 = *(const ifcvt_arg_entry *)p1;
    2395        36416 :   const ifcvt_arg_entry sval2 = *(const ifcvt_arg_entry *)p2;
    2396              : 
    2397        36416 :   if (sval1.num_compares < sval2.num_compares)
    2398              :     return -1;
    2399        12360 :   else if (sval1.num_compares > sval2.num_compares)
    2400              :     return 1;
    2401              : 
    2402          648 :   if (sval1.occurs < sval2.occurs)
    2403              :     return -1;
    2404          648 :   else if (sval1.occurs > sval2.occurs)
    2405            0 :     return 1;
    2406              : 
    2407              :   return 0;
    2408              : }
    2409              : 
    2410              : /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
    2411              :    This routine can handle PHI nodes with more than two arguments.
    2412              : 
    2413              :    For example,
    2414              :      S1: A = PHI <x1(1), x2(5)>
    2415              :    is converted into,
    2416              :      S2: A = cond ? x1 : x2;
    2417              : 
    2418              :    The generated code is inserted at GSI that points to the top of
    2419              :    basic block's statement list.
    2420              :    If PHI node has more than two arguments a chain of conditional
    2421              :    expression is produced.  */
    2422              : 
    2423              : 
    2424              : static void
    2425        49716 : predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
    2426              : {
    2427        49716 :   gimple *new_stmt = NULL, *reduc, *nop_reduc;
    2428        49716 :   tree rhs, res, arg0, arg1, op0, op1, scev;
    2429        49716 :   tree cond;
    2430        49716 :   unsigned int index0;
    2431        49716 :   edge e;
    2432        49716 :   basic_block bb;
    2433        49716 :   unsigned int i;
    2434        49716 :   bool has_nop, intermediate;
    2435              : 
    2436        49716 :   res = gimple_phi_result (phi);
    2437        99432 :   if (virtual_operand_p (res))
    2438        44375 :     return;
    2439              : 
    2440        49716 :   if ((rhs = degenerate_phi_result (phi))
    2441        49716 :       || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
    2442              :                                             res))
    2443        49674 :           && !chrec_contains_undetermined (scev)
    2444        49674 :           && scev != res
    2445           17 :           && (rhs = gimple_phi_arg_def (phi, 0))))
    2446              :     {
    2447           59 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2448              :         {
    2449            0 :           fprintf (dump_file, "Degenerate phi!\n");
    2450            0 :           print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    2451              :         }
    2452           59 :       new_stmt = gimple_build_assign (res, rhs);
    2453           59 :       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    2454           59 :       update_stmt (new_stmt);
    2455           59 :       return;
    2456              :     }
    2457              : 
    2458        49657 :   bb = gimple_bb (phi);
    2459              :   /* Keep track of conditionals already seen.  */
    2460        49657 :   scalar_cond_masked_set_type cond_set;
    2461        49657 :   if (EDGE_COUNT (bb->preds) == 2)
    2462              :     {
    2463              :       /* Predicate ordinary PHI node with 2 arguments.  */
    2464        44316 :       edge first_edge, second_edge;
    2465        44316 :       basic_block true_bb;
    2466        44316 :       first_edge = EDGE_PRED (bb, 0);
    2467        44316 :       second_edge = EDGE_PRED (bb, 1);
    2468        44316 :       cond = bb_predicate (first_edge->src);
    2469        44316 :       cond_set.add ({ cond, 1 });
    2470        44316 :       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    2471        22853 :         std::swap (first_edge, second_edge);
    2472        44316 :       if (EDGE_COUNT (first_edge->src->succs) > 1)
    2473              :         {
    2474        19675 :           cond = bb_predicate (second_edge->src);
    2475        19675 :           if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    2476        10489 :             cond = TREE_OPERAND (cond, 0);
    2477              :           else
    2478              :             first_edge = second_edge;
    2479              :         }
    2480              :       else
    2481        24641 :         cond = bb_predicate (first_edge->src);
    2482              : 
    2483              :       /* Gimplify the condition to a valid cond-expr conditional operand.  */
    2484        44316 :       cond = gen_simplified_condition (cond, cond_set);
    2485        44316 :       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
    2486              :                                        NULL_TREE, true, GSI_SAME_STMT);
    2487        44316 :       true_bb = first_edge->src;
    2488        44316 :       if (EDGE_PRED (bb, 1)->src == true_bb)
    2489              :         {
    2490        32039 :           arg0 = gimple_phi_arg_def (phi, 1);
    2491        32039 :           arg1 = gimple_phi_arg_def (phi, 0);
    2492              :         }
    2493              :       else
    2494              :         {
    2495        12277 :           arg0 = gimple_phi_arg_def (phi, 0);
    2496        12277 :           arg1 = gimple_phi_arg_def (phi, 1);
    2497              :         }
    2498              : 
    2499              :       /* Factor out operand if possible. This can only be done easily
    2500              :          for PHI with 2 elements.  */
    2501        44316 :       factor_out_operators (&res, gsi, &arg0, &arg1, phi);
    2502              : 
    2503        44316 :       if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
    2504              :                                     &op0, &op1, false, &has_nop,
    2505              :                                     &nop_reduc, &intermediate))
    2506              :         {
    2507              :           /* Convert reduction stmt into vectorizable form.  */
    2508         8462 :           rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
    2509         4231 :                                                true_bb != gimple_bb (reduc),
    2510              :                                                has_nop, nop_reduc, intermediate);
    2511         4231 :           redundant_ssa_names.safe_push (std::make_pair (res, rhs));
    2512              :         }
    2513              :       else
    2514              :         /* Build new RHS using selected condition and arguments.  */
    2515        40085 :         rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
    2516              :                                     arg0, arg1);
    2517        44316 :       new_stmt = gimple_build_assign (res, rhs);
    2518        44316 :       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    2519        44316 :       gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
    2520        44316 :       if (fold_stmt (&new_gsi, follow_all_ssa_edges))
    2521              :         {
    2522         1559 :           new_stmt = gsi_stmt (new_gsi);
    2523         1559 :           update_stmt (new_stmt);
    2524              :         }
    2525              : 
    2526        44316 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2527              :         {
    2528           28 :           fprintf (dump_file, "new phi replacement stmt\n");
    2529           28 :           print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    2530              :         }
    2531        44316 :       return;
    2532              :     }
    2533              : 
    2534              :   /* Create hashmap for PHI node which contain vector of argument indexes
    2535              :      having the same value.  */
    2536         5341 :   bool swap = false;
    2537         5341 :   hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
    2538         5341 :   unsigned int num_args = gimple_phi_num_args (phi);
    2539              :   /* Vector of different PHI argument values.  */
    2540         5341 :   auto_vec<ifcvt_arg_entry_t> args;
    2541              : 
    2542              :   /* Compute phi_arg_map, determine the list of unique PHI args and the indices
    2543              :      where they are in the PHI node.  The indices will be used to determine
    2544              :      the conditions to apply and their complexity.  */
    2545        21633 :   for (i = 0; i < num_args; i++)
    2546              :     {
    2547        16292 :       tree arg;
    2548              : 
    2549        16292 :       arg = gimple_phi_arg_def (phi, i);
    2550        16292 :       if (!phi_arg_map.get (arg))
    2551        12811 :         args.safe_push ({ arg, 0, 0, NULL });
    2552        16292 :       phi_arg_map.get_or_insert (arg).safe_push (i);
    2553              :     }
    2554              : 
    2555              :   /* Determine element with max number of occurrences and complexity.  Looking
    2556              :      at only number of occurrences as a measure for complexity isn't enough as
    2557              :      all usages can be unique but the comparisons to reach the PHI node differ
    2558              :      per branch.  */
    2559        18152 :   for (unsigned i = 0; i < args.length (); i++)
    2560              :     {
    2561        12811 :       unsigned int len = 0;
    2562        12811 :       vec<int> *indices = phi_arg_map.get (args[i].arg);
    2563        54725 :       for (int index : *indices)
    2564              :         {
    2565        16292 :           edge e = gimple_phi_arg_edge (phi, index);
    2566        16292 :           len += get_bb_num_predicate_stmts (e->src);
    2567              :         }
    2568              : 
    2569        12811 :       unsigned occur = indices->length ();
    2570        12811 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2571            7 :         fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur);
    2572        12811 :       args[i].num_compares = len;
    2573        12811 :       args[i].occurs = occur;
    2574        12811 :       args[i].indexes = indices;
    2575              :     }
    2576              : 
    2577              :   /* Sort elements based on rankings ARGS.  */
    2578         5341 :   args.stablesort (cmp_arg_entry, NULL);
    2579              : 
    2580              :   /* Handle one special case when number of arguments with different values
    2581              :      is equal 2 and one argument has the only occurrence.  Such PHI can be
    2582              :      handled as if would have only 2 arguments.  */
    2583         5341 :   if (args.length () == 2
    2584         8616 :       && args[0].indexes->length () == 1)
    2585              :     {
    2586         3217 :       index0 = (*args[0].indexes)[0];
    2587         3217 :       arg0 = args[0].arg;
    2588         3217 :       arg1 = args[1].arg;
    2589         3217 :       e = gimple_phi_arg_edge (phi, index0);
    2590         3217 :       cond = bb_predicate (e->src);
    2591         3217 :       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    2592              :         {
    2593           36 :           swap = true;
    2594           36 :           cond = TREE_OPERAND (cond, 0);
    2595              :         }
    2596              :       /* Gimplify the condition to a valid cond-expr conditional operand.  */
    2597         3217 :       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
    2598              :                                        NULL_TREE, true, GSI_SAME_STMT);
    2599         3217 :       if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
    2600              :                                       &op0, &op1, true, &has_nop, &nop_reduc,
    2601              :                                       &intermediate)))
    2602         4484 :         rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
    2603              :                                     swap ? arg1 : arg0,
    2604              :                                     swap ? arg0 : arg1);
    2605              :       else
    2606              :         {
    2607              :           /* Convert reduction stmt into vectorizable form.  */
    2608          958 :           rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
    2609              :                                                swap, has_nop, nop_reduc,
    2610              :                                                intermediate);
    2611          958 :           redundant_ssa_names.safe_push (std::make_pair (res, rhs));
    2612              :         }
    2613         3217 :       new_stmt = gimple_build_assign (res, rhs);
    2614         3217 :       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    2615         3217 :       update_stmt (new_stmt);
    2616              :     }
    2617              :   else
    2618              :     {
    2619              :       /* Common case.  */
    2620         2124 :       tree type = TREE_TYPE (gimple_phi_result (phi));
    2621         2124 :       gen_phi_nest_statement (phi, gsi, cond_set, type, &new_stmt, res,
    2622              :                               args, 1);
    2623              :     }
    2624              : 
    2625         5341 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2626              :     {
    2627            3 :       fprintf (dump_file, "new extended phi replacement stmt\n");
    2628            3 :       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    2629              :     }
    2630        49657 : }
    2631              : 
    2632              : /* Replaces in LOOP all the scalar phi nodes other than those in the
    2633              :    LOOP->header block with conditional modify expressions.  */
    2634              : 
    2635              : static void
    2636        25714 : predicate_all_scalar_phis (class loop *loop)
    2637              : {
    2638        25714 :   basic_block bb;
    2639        25714 :   unsigned int orig_loop_num_nodes = loop->num_nodes;
    2640        25714 :   unsigned int i;
    2641              : 
    2642       135159 :   for (i = 1; i < orig_loop_num_nodes; i++)
    2643              :     {
    2644       109445 :       gphi *phi;
    2645       109445 :       gimple_stmt_iterator gsi;
    2646       109445 :       gphi_iterator phi_gsi;
    2647       109445 :       bb = ifc_bbs[i];
    2648              : 
    2649       109445 :       if (bb == loop->header)
    2650        78608 :         continue;
    2651              : 
    2652       109445 :       phi_gsi = gsi_start_phis (bb);
    2653       109445 :       if (gsi_end_p (phi_gsi))
    2654        78608 :         continue;
    2655              : 
    2656        30837 :       gsi = gsi_after_labels (bb);
    2657        82907 :       while (!gsi_end_p (phi_gsi))
    2658              :         {
    2659        52070 :           phi = phi_gsi.phi ();
    2660       104140 :           if (virtual_operand_p (gimple_phi_result (phi)))
    2661         2354 :             gsi_next (&phi_gsi);
    2662              :           else
    2663              :             {
    2664        49716 :               predicate_scalar_phi (phi, &gsi);
    2665        49716 :               remove_phi_node (&phi_gsi, false);
    2666              :             }
    2667              :         }
    2668              :     }
    2669        25714 : }
    2670              : 
    2671              : /* Insert in each basic block of LOOP the statements produced by the
    2672              :    gimplification of the predicates.  */
    2673              : 
    2674              : static void
    2675        25714 : insert_gimplified_predicates (loop_p loop)
    2676              : {
    2677        25714 :   unsigned int i;
    2678              : 
    2679       160873 :   for (i = 0; i < loop->num_nodes; i++)
    2680              :     {
    2681       135159 :       basic_block bb = ifc_bbs[i];
    2682       135159 :       gimple_seq stmts;
    2683       135159 :       if (!is_predicated (bb))
    2684        81250 :         gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
    2685       135159 :       if (!is_predicated (bb))
    2686              :         {
    2687              :           /* Do not insert statements for a basic block that is not
    2688              :              predicated.  Also make sure that the predicate of the
    2689              :              basic block is set to true.  */
    2690        81250 :           reset_bb_predicate (bb);
    2691        81250 :           continue;
    2692              :         }
    2693              : 
    2694        53909 :       stmts = bb_predicate_gimplified_stmts (bb);
    2695        53909 :       if (stmts)
    2696              :         {
    2697        53501 :           if (need_to_predicate)
    2698              :             {
    2699              :               /* Insert the predicate of the BB just after the label,
    2700              :                  as the if-conversion of memory writes will use this
    2701              :                  predicate.  */
    2702         5783 :               gimple_stmt_iterator gsi = gsi_after_labels (bb);
    2703         5783 :               gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    2704              :             }
    2705              :           else
    2706              :             {
    2707              :               /* Insert the predicate of the BB at the end of the BB
    2708              :                  as this would reduce the register pressure: the only
    2709              :                  use of this predicate will be in successor BBs.  */
    2710        47718 :               gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2711              : 
    2712        47718 :               if (gsi_end_p (gsi)
    2713        47718 :                   || stmt_ends_bb_p (gsi_stmt (gsi)))
    2714        25386 :                 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    2715              :               else
    2716        22332 :                 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
    2717              :             }
    2718              : 
    2719              :           /* Once the sequence is code generated, set it to NULL.  */
    2720       135159 :           set_bb_predicate_gimplified_stmts (bb, NULL, true);
    2721              :         }
    2722              :     }
    2723        25714 : }
    2724              : 
    2725              : /* Helper function for predicate_statements. Returns index of existent
    2726              :    mask if it was created for given SIZE and -1 otherwise.  */
    2727              : 
    2728              : static int
    2729          966 : mask_exists (int size, const vec<int> &vec)
    2730              : {
    2731          966 :   unsigned int ix;
    2732          966 :   int v;
    2733         1055 :   FOR_EACH_VEC_ELT (vec, ix, v)
    2734          994 :     if (v == size)
    2735          905 :       return (int) ix;
    2736              :   return -1;
    2737              : }
    2738              : 
    2739              : /* Helper function for predicate_statements.  STMT is a memory read or
    2740              :    write and it needs to be predicated by MASK.  Return a statement
    2741              :    that does so.  */
    2742              : 
    2743              : static gimple *
    2744         2002 : predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask)
    2745              : {
    2746         2002 :   gcall *new_stmt;
    2747              : 
    2748         2002 :   tree lhs = gimple_assign_lhs (stmt);
    2749         2002 :   tree rhs = gimple_assign_rhs1 (stmt);
    2750         2002 :   tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
    2751         2002 :   mark_addressable (ref);
    2752         2002 :   tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref),
    2753              :                                         true, NULL_TREE, true, GSI_SAME_STMT);
    2754         2002 :   tree ptr = build_int_cst (reference_alias_ptr_type (ref),
    2755         2002 :                             get_object_alignment (ref));
    2756              :   /* Copy points-to info if possible.  */
    2757         3403 :   if (TREE_CODE (addr) == SSA_NAME && !ssa_name_pt_solution (addr))
    2758          600 :     copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
    2759              :                    ref);
    2760         2002 :   if (TREE_CODE (lhs) == SSA_NAME)
    2761              :     {
    2762              :       /* Get a zero else value.  This might not be what a target actually uses
    2763              :          but we cannot be sure about which vector mode the vectorizer will
    2764              :          choose.  Therefore, leave the decision whether we need to force the
    2765              :          inactive elements to zero to the vectorizer.  */
    2766         1161 :       tree els = vect_get_mask_load_else (MASK_LOAD_ELSE_ZERO,
    2767         1161 :                                           TREE_TYPE (lhs));
    2768              : 
    2769         1161 :       new_stmt
    2770         1161 :         = gimple_build_call_internal (IFN_MASK_LOAD, 4, addr,
    2771              :                                       ptr, mask, els);
    2772              : 
    2773         1161 :       gimple_call_set_lhs (new_stmt, lhs);
    2774         2322 :       gimple_set_vuse (new_stmt, gimple_vuse (stmt));
    2775              :     }
    2776              :   else
    2777              :     {
    2778          841 :       new_stmt
    2779          841 :         = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
    2780              :                                       mask, rhs);
    2781          841 :       gimple_move_vops (new_stmt, stmt);
    2782              :     }
    2783         2002 :   gimple_call_set_nothrow (new_stmt, true);
    2784         2002 :   return new_stmt;
    2785              : }
    2786              : 
    2787              : /* STMT uses OP_LHS.  Check whether it is equivalent to:
    2788              : 
    2789              :      ... = OP_MASK ? OP_LHS : X;
    2790              : 
    2791              :    Return X if so, otherwise return null.  OP_MASK is an SSA_NAME that is
    2792              :    known to have value OP_COND.  */
    2793              : 
    2794              : static tree
    2795          879 : check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond,
    2796              :                            tree op_lhs)
    2797              : {
    2798          879 :   gassign *assign = dyn_cast <gassign *> (stmt);
    2799         1089 :   if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR)
    2800              :     return NULL_TREE;
    2801              : 
    2802          230 :   tree use_cond = gimple_assign_rhs1 (assign);
    2803          230 :   tree if_true = gimple_assign_rhs2 (assign);
    2804          230 :   tree if_false = gimple_assign_rhs3 (assign);
    2805              : 
    2806           71 :   if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0))
    2807          230 :       && if_true == op_lhs)
    2808              :     return if_false;
    2809              : 
    2810           71 :   if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs)
    2811            0 :     return if_true;
    2812              : 
    2813              :   return NULL_TREE;
    2814              : }
    2815              : 
    2816              : /* Return true if VALUE is available for use at STMT.  SSA_NAMES is
    2817              :    the set of SSA names defined earlier in STMT's block.  */
    2818              : 
    2819              : static bool
    2820          159 : value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names,
    2821              :                    tree value)
    2822              : {
    2823          159 :   if (is_gimple_min_invariant (value))
    2824              :     return true;
    2825              : 
    2826          115 :   if (TREE_CODE (value) == SSA_NAME)
    2827              :     {
    2828          115 :       if (SSA_NAME_IS_DEFAULT_DEF (value))
    2829              :         return true;
    2830              : 
    2831          107 :       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
    2832          107 :       basic_block use_bb = gimple_bb (stmt);
    2833          107 :       return (def_bb == use_bb
    2834          107 :               ? ssa_names->contains (value)
    2835          107 :               : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
    2836              :     }
    2837              : 
    2838              :   return false;
    2839              : }
    2840              : 
    2841              : /* Helper function for predicate_statements.  STMT is a potentially-trapping
    2842              :    arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
    2843              :    has value COND.  Return a statement that does so.  SSA_NAMES is the set of
    2844              :    SSA names defined earlier in STMT's block.  */
    2845              : 
    2846              : static gimple *
    2847          674 : predicate_rhs_code (gimple *stmt, tree mask, tree cond,
    2848              :                     hash_set<tree_ssa_name_hash> *ssa_names)
    2849              : {
    2850          674 :   internal_fn cond_fn;
    2851          674 :   if (is_gimple_assign (stmt))
    2852              :     {
    2853          566 :       tree_code code = gimple_assign_rhs_code (stmt);
    2854          566 :       cond_fn = get_conditional_internal_fn (code);
    2855              :     }
    2856          108 :   else if (tree callee = gimple_call_fndecl (stmt))
    2857              :     {
    2858          108 :       auto ifn = associated_internal_fn (callee);
    2859          108 :       cond_fn = get_conditional_internal_fn (ifn);
    2860              :     }
    2861              :   else
    2862              :     return NULL;
    2863              : 
    2864          674 :   if (cond_fn == IFN_LAST)
    2865              :     {
    2866            0 :       gcc_assert (!gimple_could_trap_p (stmt));
    2867              :       return NULL;
    2868              :     }
    2869              : 
    2870          674 :   tree lhs = gimple_get_lhs (stmt);
    2871          674 :   unsigned int nops = gimple_num_args (stmt) + 1;
    2872              : 
    2873              :   /* Construct the arguments to the conditional internal function.   */
    2874          674 :   auto_vec<tree, 8> args;
    2875          674 :   args.safe_grow (nops + 1, true);
    2876          674 :   args[0] = mask;
    2877         2130 :   for (unsigned int i = 0; i < nops - 1; ++i)
    2878         1456 :     args[i+1] = gimple_arg (stmt, i);
    2879          674 :   args[nops] = NULL_TREE;
    2880              : 
    2881              :   /* Look for uses of the result to see whether they are COND_EXPRs that can
    2882              :      be folded into the conditional call.  */
    2883          674 :   imm_use_iterator imm_iter;
    2884          674 :   gimple *use_stmt;
    2885         1553 :   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
    2886              :     {
    2887          879 :       tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs);
    2888          879 :       if (new_else && value_available_p (stmt, ssa_names, new_else))
    2889              :         {
    2890          138 :           if (!args[nops])
    2891          138 :             args[nops] = new_else;
    2892          138 :           if (operand_equal_p (new_else, args[nops], 0))
    2893              :             {
    2894              :               /* We have:
    2895              : 
    2896              :                    LHS = IFN_COND (MASK, ..., ELSE);
    2897              :                    X = MASK ? LHS : ELSE;
    2898              : 
    2899              :                  which makes X equivalent to LHS.  */
    2900          138 :               tree use_lhs = gimple_assign_lhs (use_stmt);
    2901          138 :               redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs));
    2902              :             }
    2903              :         }
    2904          674 :     }
    2905          674 :   if (!args[nops])
    2906         1072 :     args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs),
    2907          536 :                                                nops - 1, &args[1]);
    2908              : 
    2909              :   /* Create and insert the call.  */
    2910          674 :   gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args);
    2911          674 :   gimple_call_set_lhs (new_stmt, lhs);
    2912          674 :   gimple_call_set_nothrow (new_stmt, true);
    2913              : 
    2914          674 :   return new_stmt;
    2915          674 : }
    2916              : 
    2917              : /* Predicate each write to memory in LOOP.
    2918              : 
    2919              :    This function transforms control flow constructs containing memory
    2920              :    writes of the form:
    2921              : 
    2922              :    | for (i = 0; i < N; i++)
    2923              :    |   if (cond)
    2924              :    |     A[i] = expr;
    2925              : 
    2926              :    into the following form that does not contain control flow:
    2927              : 
    2928              :    | for (i = 0; i < N; i++)
    2929              :    |   A[i] = cond ? expr : A[i];
    2930              : 
    2931              :    The original CFG looks like this:
    2932              : 
    2933              :    | bb_0
    2934              :    |   i = 0
    2935              :    | end_bb_0
    2936              :    |
    2937              :    | bb_1
    2938              :    |   if (i < N) goto bb_5 else goto bb_2
    2939              :    | end_bb_1
    2940              :    |
    2941              :    | bb_2
    2942              :    |   cond = some_computation;
    2943              :    |   if (cond) goto bb_3 else goto bb_4
    2944              :    | end_bb_2
    2945              :    |
    2946              :    | bb_3
    2947              :    |   A[i] = expr;
    2948              :    |   goto bb_4
    2949              :    | end_bb_3
    2950              :    |
    2951              :    | bb_4
    2952              :    |   goto bb_1
    2953              :    | end_bb_4
    2954              : 
    2955              :    insert_gimplified_predicates inserts the computation of the COND
    2956              :    expression at the beginning of the destination basic block:
    2957              : 
    2958              :    | bb_0
    2959              :    |   i = 0
    2960              :    | end_bb_0
    2961              :    |
    2962              :    | bb_1
    2963              :    |   if (i < N) goto bb_5 else goto bb_2
    2964              :    | end_bb_1
    2965              :    |
    2966              :    | bb_2
    2967              :    |   cond = some_computation;
    2968              :    |   if (cond) goto bb_3 else goto bb_4
    2969              :    | end_bb_2
    2970              :    |
    2971              :    | bb_3
    2972              :    |   cond = some_computation;
    2973              :    |   A[i] = expr;
    2974              :    |   goto bb_4
    2975              :    | end_bb_3
    2976              :    |
    2977              :    | bb_4
    2978              :    |   goto bb_1
    2979              :    | end_bb_4
    2980              : 
    2981              :    predicate_statements is then predicating the memory write as follows:
    2982              : 
    2983              :    | bb_0
    2984              :    |   i = 0
    2985              :    | end_bb_0
    2986              :    |
    2987              :    | bb_1
    2988              :    |   if (i < N) goto bb_5 else goto bb_2
    2989              :    | end_bb_1
    2990              :    |
    2991              :    | bb_2
    2992              :    |   if (cond) goto bb_3 else goto bb_4
    2993              :    | end_bb_2
    2994              :    |
    2995              :    | bb_3
    2996              :    |   cond = some_computation;
    2997              :    |   A[i] = cond ? expr : A[i];
    2998              :    |   goto bb_4
    2999              :    | end_bb_3
    3000              :    |
    3001              :    | bb_4
    3002              :    |   goto bb_1
    3003              :    | end_bb_4
    3004              : 
    3005              :    and finally combine_blocks removes the basic block boundaries making
    3006              :    the loop vectorizable:
    3007              : 
    3008              :    | bb_0
    3009              :    |   i = 0
    3010              :    |   if (i < N) goto bb_5 else goto bb_1
    3011              :    | end_bb_0
    3012              :    |
    3013              :    | bb_1
    3014              :    |   cond = some_computation;
    3015              :    |   A[i] = cond ? expr : A[i];
    3016              :    |   if (i < N) goto bb_5 else goto bb_4
    3017              :    | end_bb_1
    3018              :    |
    3019              :    | bb_4
    3020              :    |   goto bb_1
    3021              :    | end_bb_4
    3022              : */
    3023              : 
    3024              : static void
    3025        12179 : predicate_statements (loop_p loop)
    3026              : {
    3027        12179 :   unsigned int i, orig_loop_num_nodes = loop->num_nodes;
    3028        12179 :   auto_vec<int, 1> vect_sizes;
    3029        12179 :   auto_vec<tree, 1> vect_masks;
    3030        12179 :   hash_set<tree_ssa_name_hash> ssa_names;
    3031              : 
    3032        76015 :   for (i = 1; i < orig_loop_num_nodes; i++)
    3033              :     {
    3034        51657 :       gimple_stmt_iterator gsi;
    3035        51657 :       basic_block bb = ifc_bbs[i];
    3036        51657 :       tree cond = bb_predicate (bb);
    3037        51657 :       bool swap;
    3038        51657 :       int index;
    3039              : 
    3040        51657 :       if (is_true_predicate (cond))
    3041        25680 :         continue;
    3042              : 
    3043        25977 :       swap = false;
    3044        25977 :       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    3045              :         {
    3046         9913 :           swap = true;
    3047         9913 :           cond = TREE_OPERAND (cond, 0);
    3048              :         }
    3049              : 
    3050        25977 :       vect_sizes.truncate (0);
    3051        25977 :       vect_masks.truncate (0);
    3052              : 
    3053       201986 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    3054              :         {
    3055       150032 :           gimple *stmt = gsi_stmt (gsi);
    3056       150032 :           if (!is_gimple_assign (stmt)
    3057       150032 :               && !gimple_call_builtin_p (stmt))
    3058              :             ;
    3059        92118 :           else if (is_false_predicate (cond)
    3060        92118 :                    && gimple_vdef (stmt))
    3061              :             {
    3062            0 :               unlink_stmt_vdef (stmt);
    3063            0 :               gsi_remove (&gsi, true);
    3064            0 :               release_defs (stmt);
    3065            2 :               continue;
    3066              :             }
    3067              :           /* For now, just drop prefetches.  Do it now to remove any possible
    3068              :              aliasing check failures from the address calculations of the
    3069              :              prefetch.  Vect would be too late in that regard.  */
    3070        92118 :           else if (gimple_call_builtin_p (stmt, BUILT_IN_PREFETCH))
    3071              :             {
    3072            2 :               unlink_stmt_vdef (stmt);
    3073            2 :               gsi_remove (&gsi, true);
    3074            2 :               release_defs (stmt);
    3075            2 :               continue;
    3076              :             }
    3077        92116 :           else if (gimple_plf (stmt, GF_PLF_2)
    3078        92116 :                    && (is_gimple_assign (stmt)
    3079          108 :                        || (gimple_call_builtin_p (stmt)
    3080          108 :                            && !if_convertible_simdclone_stmt_p (stmt))))
    3081              :             {
    3082         2676 :               tree lhs = gimple_get_lhs (stmt);
    3083              :               /* ?? Assume that calls without an LHS are not data processing
    3084              :                  and so no issues with traps.  */
    3085         2676 :               if (!lhs)
    3086            0 :                 continue;
    3087         2676 :               tree mask;
    3088         2676 :               gimple *new_stmt;
    3089         2676 :               gimple_seq stmts = NULL;
    3090         2676 :               machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
    3091              :               /* We checked before setting GF_PLF_2 that an equivalent
    3092              :                  integer mode exists.  */
    3093         2676 :               int bitsize = GET_MODE_BITSIZE (mode).to_constant ();
    3094         2676 :               if (!vect_sizes.is_empty ()
    3095          966 :                   && (index = mask_exists (bitsize, vect_sizes)) != -1)
    3096              :                 /* Use created mask.  */
    3097          905 :                 mask = vect_masks[index];
    3098              :               else
    3099              :                 {
    3100         1771 :                   if (COMPARISON_CLASS_P (cond))
    3101            0 :                     mask = gimple_build (&stmts, TREE_CODE (cond),
    3102              :                                          boolean_type_node,
    3103            0 :                                          TREE_OPERAND (cond, 0),
    3104            0 :                                          TREE_OPERAND (cond, 1));
    3105              :                   else
    3106              :                     mask = cond;
    3107              : 
    3108         1771 :                   if (swap)
    3109              :                     {
    3110          391 :                       tree true_val
    3111          391 :                         = constant_boolean_node (true, TREE_TYPE (mask));
    3112          391 :                       mask = gimple_build (&stmts, BIT_XOR_EXPR,
    3113          391 :                                            TREE_TYPE (mask), mask, true_val);
    3114              :                     }
    3115         1771 :                   gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    3116              : 
    3117              :                   /* Save mask and its size for further use.  */
    3118         1771 :                   vect_sizes.safe_push (bitsize);
    3119         1771 :                   vect_masks.safe_push (mask);
    3120              :                 }
    3121         2676 :               if (gimple_assign_single_p (stmt))
    3122         2002 :                 new_stmt = predicate_load_or_store (&gsi,
    3123              :                                                     as_a <gassign *> (stmt),
    3124              :                                                     mask);
    3125              :               else
    3126          674 :                 new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names);
    3127              : 
    3128         2676 :               if (new_stmt)
    3129         2676 :                 gsi_replace (&gsi, new_stmt, true);
    3130              :             }
    3131        89440 :           else if (gimple_needing_rewrite_undefined (stmt))
    3132        18536 :             rewrite_to_defined_unconditional (&gsi);
    3133       141808 :           else if (gimple_vdef (stmt))
    3134              :             {
    3135         1381 :               tree lhs = gimple_assign_lhs (stmt);
    3136         1381 :               tree rhs = gimple_assign_rhs1 (stmt);
    3137         1381 :               tree type = TREE_TYPE (lhs);
    3138              : 
    3139         1381 :               lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
    3140         1381 :               rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
    3141         1381 :               if (swap)
    3142          481 :                 std::swap (lhs, rhs);
    3143         1381 :               cond = force_gimple_operand_gsi (&gsi, unshare_expr (cond), true,
    3144              :                                                NULL_TREE, true, GSI_SAME_STMT);
    3145         1381 :               rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
    3146         1381 :               gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
    3147         1381 :               update_stmt (stmt);
    3148              :             }
    3149              : 
    3150       150030 :           if (gimple_plf (gsi_stmt (gsi), GF_PLF_2)
    3151       150030 :               && is_gimple_call (gsi_stmt (gsi)))
    3152              :             {
    3153              :               /* Convert functions that have a SIMD clone to IFN_MASK_CALL.
    3154              :                  This will cause the vectorizer to match the "in branch"
    3155              :                  clone variants, and serves to build the mask vector
    3156              :                  in a natural way.  */
    3157         1007 :               tree mask = cond;
    3158         1007 :               gcall *call = dyn_cast <gcall *> (gsi_stmt (gsi));
    3159         1007 :               tree orig_fn = gimple_call_fn (call);
    3160         1007 :               int orig_nargs = gimple_call_num_args (call);
    3161         1007 :               auto_vec<tree> args;
    3162         1007 :               args.safe_push (orig_fn);
    3163         3036 :               for (int i = 0; i < orig_nargs; i++)
    3164         1022 :                 args.safe_push (gimple_call_arg (call, i));
    3165              :               /* If `swap', we invert the mask used for the if branch for use
    3166              :                  when masking the function call.  */
    3167         1007 :               if (swap)
    3168              :                 {
    3169          948 :                   gimple_seq stmts = NULL;
    3170          948 :                   tree true_val
    3171          948 :                     = constant_boolean_node (true, TREE_TYPE (mask));
    3172          948 :                   mask = gimple_build (&stmts, BIT_XOR_EXPR,
    3173          948 :                                        TREE_TYPE (mask), mask, true_val);
    3174          948 :                   gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    3175              :                 }
    3176         1007 :               args.safe_push (mask);
    3177              : 
    3178              :               /* Replace the call with a IFN_MASK_CALL that has the extra
    3179              :                  condition parameter. */
    3180         1007 :               gcall *new_call = gimple_build_call_internal_vec (IFN_MASK_CALL,
    3181              :                                                                 args);
    3182         1007 :               gimple_call_set_lhs (new_call, gimple_call_lhs (call));
    3183         1007 :               gsi_replace (&gsi, new_call, true);
    3184         1007 :             }
    3185              : 
    3186       150030 :           tree lhs = gimple_get_lhs (gsi_stmt (gsi));
    3187       150030 :           if (lhs && TREE_CODE (lhs) == SSA_NAME)
    3188        90003 :             ssa_names.add (lhs);
    3189       150030 :           gsi_next (&gsi);
    3190              :         }
    3191        51932 :       ssa_names.empty ();
    3192              :     }
    3193        12179 : }
    3194              : 
    3195              : /* Remove all GIMPLE_CONDs and GIMPLE_LABELs and GIMPLE_SWITCH of all
    3196              :    the basic blocks other than the exit and latch of the LOOP.  Also
    3197              :    resets the GIMPLE_DEBUG information.  */
    3198              : 
    3199              : static void
    3200        25714 : remove_conditions_and_labels (loop_p loop)
    3201              : {
    3202        25714 :   gimple_stmt_iterator gsi;
    3203        25714 :   unsigned int i;
    3204              : 
    3205       160873 :   for (i = 0; i < loop->num_nodes; i++)
    3206              :     {
    3207       135159 :       basic_block bb = ifc_bbs[i];
    3208              : 
    3209       135159 :       if (bb_with_exit_edge_p (loop, bb)
    3210       135159 :           || bb == loop->latch)
    3211        51428 :         continue;
    3212              : 
    3213       713488 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
    3214       546026 :         switch (gimple_code (gsi_stmt (gsi)))
    3215              :           {
    3216        33793 :           case GIMPLE_COND:
    3217        33793 :           case GIMPLE_LABEL:
    3218        33793 :           case GIMPLE_SWITCH:
    3219        33793 :             gsi_remove (&gsi, true);
    3220        33793 :             break;
    3221              : 
    3222       345137 :           case GIMPLE_DEBUG:
    3223              :             /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
    3224       345137 :             if (gimple_debug_bind_p (gsi_stmt (gsi)))
    3225              :               {
    3226       276027 :                 gimple_debug_bind_reset_value (gsi_stmt (gsi));
    3227       276027 :                 update_stmt (gsi_stmt (gsi));
    3228              :               }
    3229       345137 :             gsi_next (&gsi);
    3230       345137 :             break;
    3231              : 
    3232       167096 :           default:
    3233       167096 :             gsi_next (&gsi);
    3234              :           }
    3235              :     }
    3236        25714 : }
    3237              : 
    3238              : /* Combine all the basic blocks from LOOP into one or two super basic
    3239              :    blocks.  Replace PHI nodes with conditional modify expressions.  */
    3240              : 
    3241              : static void
    3242        25714 : combine_blocks (class loop *loop)
    3243              : {
    3244        25714 :   basic_block bb, exit_bb, merge_target_bb;
    3245        25714 :   unsigned int orig_loop_num_nodes = loop->num_nodes;
    3246        25714 :   unsigned int i;
    3247        25714 :   edge e;
    3248        25714 :   edge_iterator ei;
    3249              : 
    3250              :   /* Reset flow-sensitive info before predicating stmts or PHIs we
    3251              :      might fold.  */
    3252       160873 :   for (i = 0; i < orig_loop_num_nodes; i++)
    3253              :     {
    3254       135159 :       bb = ifc_bbs[i];
    3255       135159 :       if (is_predicated (bb))
    3256              :         {
    3257        53909 :           for (auto gsi = gsi_start_phis (bb);
    3258        55471 :                !gsi_end_p (gsi); gsi_next (&gsi))
    3259         1562 :             reset_flow_sensitive_info (gimple_phi_result (*gsi));
    3260       228051 :           for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3261              :             {
    3262       120233 :               gimple *stmt = gsi_stmt (gsi);
    3263       120233 :               ssa_op_iter i;
    3264       120233 :               tree op;
    3265       171805 :               FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
    3266        51572 :                 reset_flow_sensitive_info (op);
    3267              :             }
    3268              :         }
    3269              :     }
    3270              : 
    3271        25714 :   remove_conditions_and_labels (loop);
    3272        25714 :   insert_gimplified_predicates (loop);
    3273        25714 :   predicate_all_scalar_phis (loop);
    3274              : 
    3275        25714 :   if (need_to_predicate || need_to_rewrite_undefined)
    3276        12179 :     predicate_statements (loop);
    3277              : 
    3278              :   /* Merge basic blocks.  */
    3279        25714 :   exit_bb = single_exit (loop)->src;
    3280        25714 :   gcc_assert (exit_bb != loop->latch);
    3281       160873 :   for (i = 0; i < orig_loop_num_nodes; i++)
    3282              :     {
    3283       135159 :       bb = ifc_bbs[i];
    3284       135159 :       free_bb_predicate (bb);
    3285              :     }
    3286              : 
    3287        25714 :   merge_target_bb = loop->header;
    3288              : 
    3289              :   /* Get at the virtual def valid for uses starting at the first block
    3290              :      we merge into the header.  Without a virtual PHI the loop has the
    3291              :      same virtual use on all stmts.  */
    3292        25714 :   gphi *vphi = get_virtual_phi (loop->header);
    3293        25714 :   tree last_vdef = NULL_TREE;
    3294        25714 :   if (vphi)
    3295              :     {
    3296        13805 :       last_vdef = gimple_phi_result (vphi);
    3297        27610 :       for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
    3298       237291 :            ! gsi_end_p (gsi); gsi_next (&gsi))
    3299       287548 :         if (gimple_vdef (gsi_stmt (gsi)))
    3300       223486 :           last_vdef = gimple_vdef (gsi_stmt (gsi));
    3301              :     }
    3302       135159 :   for (i = 1; i < orig_loop_num_nodes; i++)
    3303              :     {
    3304       109445 :       gimple_stmt_iterator gsi;
    3305       109445 :       gimple_stmt_iterator last;
    3306              : 
    3307       109445 :       bb = ifc_bbs[i];
    3308              : 
    3309       109445 :       if (bb == exit_bb || bb == loop->latch)
    3310        51428 :         continue;
    3311              : 
    3312              :       /* We release virtual PHIs late because we have to propagate them
    3313              :          out using the current VUSE.  The def might be the one used
    3314              :          after the loop.  */
    3315        58017 :       vphi = get_virtual_phi (bb);
    3316        58017 :       if (vphi)
    3317              :         {
    3318              :           /* When there's just loads inside the loop a stray virtual
    3319              :              PHI merging the uses can appear, update last_vdef from
    3320              :              it.  */
    3321          674 :           if (!last_vdef)
    3322            0 :             last_vdef = gimple_phi_arg_def (vphi, 0);
    3323          674 :           imm_use_iterator iter;
    3324          674 :           use_operand_p use_p;
    3325          674 :           gimple *use_stmt;
    3326         2349 :           FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
    3327              :             {
    3328         3356 :               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    3329         1678 :                 SET_USE (use_p, last_vdef);
    3330          674 :             }
    3331          674 :           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
    3332            0 :             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
    3333          674 :           gsi = gsi_for_stmt (vphi);
    3334          674 :           remove_phi_node (&gsi, true);
    3335              :         }
    3336              : 
    3337              :       /* Make stmts member of loop->header and clear range info from all stmts
    3338              :          in BB which is now no longer executed conditional on a predicate we
    3339              :          could have derived it from.  */
    3340       381522 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3341              :         {
    3342       265488 :           gimple *stmt = gsi_stmt (gsi);
    3343       265488 :           gimple_set_bb (stmt, merge_target_bb);
    3344              :           /* Update virtual operands.  */
    3345       265488 :           if (last_vdef)
    3346              :             {
    3347       204930 :               use_operand_p use_p = ssa_vuse_operand (stmt);
    3348        14426 :               if (use_p
    3349        14426 :                   && USE_FROM_PTR (use_p) != last_vdef)
    3350          522 :                 SET_USE (use_p, last_vdef);
    3351       617039 :               if (gimple_vdef (stmt))
    3352              :                 last_vdef = gimple_vdef (stmt);
    3353              :             }
    3354              :           else
    3355              :             /* If this is the first load we arrive at update last_vdef
    3356              :                so we handle stray PHIs correctly.  */
    3357       306584 :             last_vdef = gimple_vuse (stmt);
    3358              :         }
    3359              : 
    3360              :       /* Update stmt list.  */
    3361        58017 :       last = gsi_last_bb (merge_target_bb);
    3362       116034 :       gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
    3363        58017 :       set_bb_seq (bb, NULL);
    3364              :     }
    3365              : 
    3366              :   /* Fixup virtual operands in the exit block.  */
    3367        25714 :   if (exit_bb
    3368        25714 :       && exit_bb != loop->header)
    3369              :     {
    3370              :       /* We release virtual PHIs late because we have to propagate them
    3371              :          out using the current VUSE.  The def might be the one used
    3372              :          after the loop.  */
    3373        25714 :       vphi = get_virtual_phi (exit_bb);
    3374        25714 :       if (vphi)
    3375              :         {
    3376              :           /* When there's just loads inside the loop a stray virtual
    3377              :              PHI merging the uses can appear, update last_vdef from
    3378              :              it.  */
    3379         1680 :           if (!last_vdef)
    3380            0 :             last_vdef = gimple_phi_arg_def (vphi, 0);
    3381         1680 :           imm_use_iterator iter;
    3382         1680 :           use_operand_p use_p;
    3383         1680 :           gimple *use_stmt;
    3384         5034 :           FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
    3385              :             {
    3386         6708 :               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    3387         3354 :                 SET_USE (use_p, last_vdef);
    3388         1680 :             }
    3389         1680 :           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
    3390            0 :             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
    3391         1680 :           gimple_stmt_iterator gsi = gsi_for_stmt (vphi);
    3392         1680 :           remove_phi_node (&gsi, true);
    3393              :         }
    3394              :     }
    3395              : 
    3396              :   /* Now remove all the edges in the loop, except for those from the exit
    3397              :      block and delete the blocks we elided.  */
    3398       135159 :   for (i = 1; i < orig_loop_num_nodes; i++)
    3399              :     {
    3400       109445 :       bb = ifc_bbs[i];
    3401              : 
    3402       252301 :       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
    3403              :         {
    3404       142856 :           if (e->src == exit_bb)
    3405        25714 :             ei_next (&ei);
    3406              :           else
    3407       117142 :             remove_edge (e);
    3408              :         }
    3409              :     }
    3410       135159 :   for (i = 1; i < orig_loop_num_nodes; i++)
    3411              :     {
    3412       109445 :       bb = ifc_bbs[i];
    3413              : 
    3414       109445 :       if (bb == exit_bb || bb == loop->latch)
    3415        51428 :         continue;
    3416              : 
    3417        58017 :       delete_basic_block (bb);
    3418              :     }
    3419              : 
    3420              :   /* Re-connect the exit block.  */
    3421        25714 :   if (exit_bb != NULL)
    3422              :     {
    3423        25714 :       if (exit_bb != loop->header)
    3424              :         {
    3425              :           /* Connect this node to loop header.  */
    3426        25714 :           make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU);
    3427        25714 :           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
    3428              :         }
    3429              : 
    3430              :       /* Redirect non-exit edges to loop->latch.  */
    3431        77142 :       FOR_EACH_EDGE (e, ei, exit_bb->succs)
    3432              :         {
    3433        51428 :           if (!loop_exit_edge_p (loop, e))
    3434        25714 :             redirect_edge_and_branch (e, loop->latch);
    3435              :         }
    3436        25714 :       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
    3437              :     }
    3438              :   else
    3439              :     {
    3440              :       /* If the loop does not have an exit, reconnect header and latch.  */
    3441            0 :       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
    3442            0 :       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
    3443              :     }
    3444              : 
    3445              :   /* If possible, merge loop header to the block with the exit edge.
    3446              :      This reduces the number of basic blocks to two, to please the
    3447              :      vectorizer that handles only loops with two nodes.  */
    3448        25714 :   if (exit_bb
    3449        25714 :       && exit_bb != loop->header)
    3450              :     {
    3451        25714 :       if (can_merge_blocks_p (loop->header, exit_bb))
    3452        25712 :         merge_blocks (loop->header, exit_bb);
    3453              :     }
    3454              : 
    3455        25714 :   free (ifc_bbs);
    3456        25714 :   ifc_bbs = NULL;
    3457        25714 : }
    3458              : 
    3459              : /* Version LOOP before if-converting it; the original loop
    3460              :    will be if-converted, the new copy of the loop will not,
    3461              :    and the LOOP_VECTORIZED internal call will be guarding which
    3462              :    loop to execute.  The vectorizer pass will fold this
    3463              :    internal call into either true or false.
    3464              : 
    3465              :    Note that this function intentionally invalidates profile.  Both edges
    3466              :    out of LOOP_VECTORIZED must have 100% probability so the profile remains
    3467              :    consistent after the condition is folded in the vectorizer.  */
    3468              : 
    3469              : static class loop *
    3470        25979 : version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
    3471              : {
    3472        25979 :   basic_block cond_bb;
    3473        25979 :   tree cond = make_ssa_name (boolean_type_node);
    3474        25979 :   class loop *new_loop;
    3475        25979 :   gimple *g;
    3476        25979 :   gimple_stmt_iterator gsi;
    3477        25979 :   unsigned int save_length = 0;
    3478              : 
    3479        25979 :   g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
    3480        25979 :                                   build_int_cst (integer_type_node, loop->num),
    3481              :                                   integer_zero_node);
    3482        25979 :   gimple_call_set_lhs (g, cond);
    3483              : 
    3484        25979 :   void **saved_preds = NULL;
    3485        25979 :   if (any_complicated_phi || need_to_predicate)
    3486              :     {
    3487              :       /* Save BB->aux around loop_version as that uses the same field.  */
    3488         3424 :       save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
    3489         3424 :       saved_preds = XALLOCAVEC (void *, save_length);
    3490        26037 :       for (unsigned i = 0; i < save_length; i++)
    3491        22613 :         saved_preds[i] = ifc_bbs[i]->aux;
    3492              :     }
    3493              : 
    3494        25979 :   initialize_original_copy_tables ();
    3495              :   /* At this point we invalidate profile consistency until IFN_LOOP_VECTORIZED
    3496              :      is re-merged in the vectorizer.  */
    3497        25979 :   new_loop = loop_version (loop, cond, &cond_bb,
    3498              :                            profile_probability::always (),
    3499              :                            profile_probability::always (),
    3500              :                            profile_probability::always (),
    3501              :                            profile_probability::always (), true);
    3502        25979 :   free_original_copy_tables ();
    3503              : 
    3504        25979 :   if (any_complicated_phi || need_to_predicate)
    3505        26037 :     for (unsigned i = 0; i < save_length; i++)
    3506        22613 :       ifc_bbs[i]->aux = saved_preds[i];
    3507              : 
    3508        25979 :   if (new_loop == NULL)
    3509              :     return NULL;
    3510              : 
    3511        25979 :   new_loop->dont_vectorize = true;
    3512        25979 :   new_loop->force_vectorize = false;
    3513        25979 :   gsi = gsi_last_bb (cond_bb);
    3514        25979 :   gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
    3515        25979 :   if (preds)
    3516        25979 :     preds->safe_push (g);
    3517        25979 :   gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    3518        25979 :   update_ssa (TODO_update_ssa_no_phi);
    3519        25979 :   return new_loop;
    3520              : }
    3521              : 
    3522              : /* Return true when LOOP satisfies the follow conditions that will
    3523              :    allow it to be recognized by the vectorizer for outer-loop
    3524              :    vectorization:
    3525              :     - The loop is not the root node of the loop tree.
    3526              :     - The loop has exactly one inner loop.
    3527              :     - The loop has a single exit.
    3528              :     - The loop header has a single successor, which is the inner
    3529              :       loop header.
    3530              :     - Each of the inner and outer loop latches have a single
    3531              :       predecessor.
    3532              :     - The loop exit block has a single predecessor, which is the
    3533              :       inner loop's exit block.  */
    3534              : 
    3535              : static bool
    3536        25979 : versionable_outer_loop_p (class loop *loop)
    3537              : {
    3538        25979 :   if (!loop_outer (loop)
    3539         8089 :       || loop->dont_vectorize
    3540         7105 :       || !loop->inner
    3541         7105 :       || loop->inner->next
    3542         2943 :       || !single_exit (loop)
    3543         2248 :       || !single_succ_p (loop->header)
    3544          934 :       || single_succ (loop->header) != loop->inner->header
    3545          934 :       || !single_pred_p (loop->latch)
    3546        26913 :       || !single_pred_p (loop->inner->latch))
    3547              :     return false;
    3548              : 
    3549          934 :   basic_block outer_exit = single_pred (loop->latch);
    3550          934 :   basic_block inner_exit = single_pred (loop->inner->latch);
    3551              : 
    3552         1859 :   if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
    3553              :     return false;
    3554              : 
    3555          924 :   if (dump_file)
    3556            0 :     fprintf (dump_file, "Found vectorizable outer loop for versioning\n");
    3557              : 
    3558              :   return true;
    3559              : }
    3560              : 
    3561              : /* Performs splitting of critical edges.  Skip splitting and return false
    3562              :    if LOOP will not be converted because:
    3563              : 
    3564              :      - LOOP is not well formed.
    3565              :      - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
    3566              : 
    3567              :    Last restriction is valid only if AGGRESSIVE_IF_CONV is false.  */
    3568              : 
    3569              : static bool
    3570       321471 : ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv)
    3571              : {
    3572       321471 :   basic_block *body;
    3573       321471 :   basic_block bb;
    3574       321471 :   unsigned int num = loop->num_nodes;
    3575       321471 :   unsigned int i;
    3576       321471 :   edge e;
    3577       321471 :   edge_iterator ei;
    3578       321471 :   auto_vec<edge> critical_edges;
    3579              : 
    3580              :   /* Loop is not well formed.  */
    3581       321471 :   if (loop->inner)
    3582              :     return false;
    3583              : 
    3584       229630 :   body = get_loop_body (loop);
    3585      1829602 :   for (i = 0; i < num; i++)
    3586              :     {
    3587      1376897 :       bb = body[i];
    3588      1376897 :       if (!aggressive_if_conv
    3589      1368708 :           && phi_nodes (bb)
    3590      1805446 :           && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
    3591              :         {
    3592         6555 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3593            0 :             fprintf (dump_file,
    3594              :                      "BB %d has complicated PHI with more than %u args.\n",
    3595              :                      bb->index, MAX_PHI_ARG_NUM);
    3596              : 
    3597         6555 :           free (body);
    3598         6555 :           return false;
    3599              :         }
    3600      1370342 :       if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
    3601       783591 :         continue;
    3602              : 
    3603              :       /* Skip basic blocks not ending with conditional branch.  */
    3604      1406192 :       if (!safe_is_a <gcond *> (*gsi_last_bb (bb))
    3605       586751 :           && !safe_is_a <gswitch *> (*gsi_last_bb (bb)))
    3606       325291 :         continue;
    3607              : 
    3608       796442 :       FOR_EACH_EDGE (e, ei, bb->succs)
    3609       658702 :         if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
    3610       123720 :           critical_edges.safe_push (e);
    3611              :     }
    3612       223075 :   free (body);
    3613              : 
    3614       441076 :   while (critical_edges.length () > 0)
    3615              :     {
    3616       119605 :       e = critical_edges.pop ();
    3617              :       /* Don't split if bb can be predicated along non-critical edge.  */
    3618       119605 :       if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
    3619        56972 :         split_edge (e);
    3620              :     }
    3621              : 
    3622              :   return true;
    3623       321471 : }
    3624              : 
    3625              : /* Delete redundant statements produced by predication which prevents
    3626              :    loop vectorization.  */
    3627              : 
    3628              : static void
    3629        25979 : ifcvt_local_dce (class loop *loop)
    3630              : {
    3631        25979 :   gimple *stmt;
    3632        25979 :   gimple *stmt1;
    3633        25979 :   gimple *phi;
    3634        25979 :   gimple_stmt_iterator gsi;
    3635        25979 :   auto_vec<gimple *> worklist;
    3636        25979 :   enum gimple_code code;
    3637        25979 :   use_operand_p use_p;
    3638        25979 :   imm_use_iterator imm_iter;
    3639              : 
    3640              :   /* The loop has a single BB only.  */
    3641        25979 :   basic_block bb = loop->header;
    3642        25979 :   tree latch_vdef = NULL_TREE;
    3643              : 
    3644        25979 :   worklist.create (64);
    3645              :   /* Consider all phi as live statements.  */
    3646       104698 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3647              :     {
    3648        78719 :       phi = gsi_stmt (gsi);
    3649        78719 :       gimple_set_plf (phi, GF_PLF_2, true);
    3650        78719 :       worklist.safe_push (phi);
    3651       171441 :       if (virtual_operand_p (gimple_phi_result (phi)))
    3652        14003 :         latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
    3653              :     }
    3654              :   /* Consider load/store statements, CALL and COND as live.  */
    3655       875917 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3656              :     {
    3657       823959 :       stmt = gsi_stmt (gsi);
    3658       823959 :       if (is_gimple_debug (stmt))
    3659              :         {
    3660       442494 :           gimple_set_plf (stmt, GF_PLF_2, true);
    3661       442494 :           continue;
    3662              :         }
    3663       381465 :       if (gimple_store_p (stmt) || gimple_assign_load_p (stmt))
    3664              :         {
    3665        59328 :           gimple_set_plf (stmt, GF_PLF_2, true);
    3666        59328 :           worklist.safe_push (stmt);
    3667        59328 :           continue;
    3668              :         }
    3669       322137 :       code = gimple_code (stmt);
    3670       322137 :       if (code == GIMPLE_COND || code == GIMPLE_CALL || code == GIMPLE_SWITCH)
    3671              :         {
    3672        31528 :           gimple_set_plf (stmt, GF_PLF_2, true);
    3673        31528 :           worklist.safe_push (stmt);
    3674        31528 :           continue;
    3675              :         }
    3676       290609 :       gimple_set_plf (stmt, GF_PLF_2, false);
    3677              : 
    3678       290609 :       if (code == GIMPLE_ASSIGN)
    3679              :         {
    3680       290600 :           tree lhs = gimple_assign_lhs (stmt);
    3681       673541 :           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
    3682              :             {
    3683       402878 :               stmt1 = USE_STMT (use_p);
    3684       402878 :               if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb)
    3685              :                 {
    3686        19937 :                   gimple_set_plf (stmt, GF_PLF_2, true);
    3687        19937 :                   worklist.safe_push (stmt);
    3688        19937 :                   break;
    3689              :                 }
    3690       290600 :             }
    3691              :         }
    3692              :     }
    3693              :   /* Propagate liveness through arguments of live stmt.  */
    3694       473789 :   while (worklist.length () > 0)
    3695              :     {
    3696       447810 :       ssa_op_iter iter;
    3697       447810 :       use_operand_p use_p;
    3698       447810 :       tree use;
    3699              : 
    3700       447810 :       stmt = worklist.pop ();
    3701      1575739 :       FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
    3702              :         {
    3703       680119 :           use = USE_FROM_PTR (use_p);
    3704       680119 :           if (TREE_CODE (use) != SSA_NAME)
    3705        43391 :             continue;
    3706       636728 :           stmt1 = SSA_NAME_DEF_STMT (use);
    3707       636728 :           if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2))
    3708       378430 :             continue;
    3709       258298 :           gimple_set_plf (stmt1, GF_PLF_2, true);
    3710       258298 :           worklist.safe_push (stmt1);
    3711              :         }
    3712              :     }
    3713              :   /* Delete dead statements.  */
    3714        25979 :   gsi = gsi_last_bb (bb);
    3715       849938 :   while (!gsi_end_p (gsi))
    3716              :     {
    3717       823959 :       gimple_stmt_iterator gsiprev = gsi;
    3718       823959 :       gsi_prev (&gsiprev);
    3719       823959 :       stmt = gsi_stmt (gsi);
    3720       823959 :       if (!gimple_has_volatile_ops (stmt)
    3721       823814 :           && gimple_store_p (stmt)
    3722       381569 :           && gimple_vdef (stmt))
    3723              :         {
    3724        13044 :           tree lhs = gimple_get_lhs (stmt);
    3725        13044 :           ao_ref write;
    3726        13044 :           ao_ref_init (&write, lhs);
    3727              : 
    3728        13044 :           if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef)
    3729              :               == DSE_STORE_DEAD)
    3730          270 :             delete_dead_or_redundant_assignment (&gsi, "dead");
    3731        13044 :           gsi = gsiprev;
    3732        13044 :           continue;
    3733        13044 :         }
    3734              : 
    3735       810915 :       if (gimple_plf (stmt, GF_PLF_2))
    3736              :         {
    3737       798541 :           gsi = gsiprev;
    3738       798541 :           continue;
    3739              :         }
    3740        12374 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3741              :         {
    3742           28 :           fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
    3743           28 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    3744              :         }
    3745        12374 :       gsi_remove (&gsi, true);
    3746        12374 :       release_defs (stmt);
    3747        12374 :       gsi = gsiprev;
    3748              :     }
    3749        25979 : }
    3750              : 
    3751              : /* Return true if VALUE is already available on edge PE.  */
    3752              : 
    3753              : static bool
    3754       250798 : ifcvt_available_on_edge_p (edge pe, tree value)
    3755              : {
    3756       250798 :   if (is_gimple_min_invariant (value))
    3757              :     return true;
    3758              : 
    3759       244220 :   if (TREE_CODE (value) == SSA_NAME)
    3760              :     {
    3761       242989 :       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
    3762       242989 :       if (!def_bb || dominated_by_p (CDI_DOMINATORS, pe->dest, def_bb))
    3763        27030 :         return true;
    3764              :     }
    3765              : 
    3766              :   return false;
    3767              : }
    3768              : 
    3769              : /* Return true if STMT can be hoisted from if-converted loop LOOP to
    3770              :    edge PE.  */
    3771              : 
    3772              : static bool
    3773       811315 : ifcvt_can_hoist (class loop *loop, edge pe, gimple *stmt)
    3774              : {
    3775       811315 :   if (auto *call = dyn_cast<gcall *> (stmt))
    3776              :     {
    3777         5555 :       if (gimple_call_internal_p (call)
    3778         5555 :           && internal_fn_mask_index (gimple_call_internal_fn (call)) >= 0)
    3779              :         return false;
    3780              :     }
    3781       805760 :   else if (auto *assign = dyn_cast<gassign *> (stmt))
    3782              :     {
    3783       397690 :       if (gimple_assign_rhs_code (assign) == COND_EXPR)
    3784              :         return false;
    3785              :     }
    3786              :   else
    3787              :     return false;
    3788              : 
    3789       293214 :   if (gimple_has_side_effects (stmt)
    3790       292030 :       || gimple_could_trap_p (stmt)
    3791       229985 :       || stmt_could_throw_p (cfun, stmt)
    3792       229983 :       || gimple_vdef (stmt)
    3793       522699 :       || gimple_vuse (stmt))
    3794              :     return false;
    3795              : 
    3796       228574 :   int num_args = gimple_num_args (stmt);
    3797       228574 :   if (pe != loop_preheader_edge (loop))
    3798              :     {
    3799       255713 :       for (int i = 0; i < num_args; ++i)
    3800       250798 :         if (!ifcvt_available_on_edge_p (pe, gimple_arg (stmt, i)))
    3801              :           return false;
    3802              :     }
    3803              :   else
    3804              :     {
    3805         8052 :       for (int i = 0; i < num_args; ++i)
    3806         7860 :         if (!expr_invariant_in_loop_p (loop, gimple_arg (stmt, i)))
    3807              :           return false;
    3808              :     }
    3809              : 
    3810              :   return true;
    3811              : }
    3812              : 
    3813              : /* Hoist invariant statements from LOOP to edge PE.  */
    3814              : 
    3815              : static void
    3816        25979 : ifcvt_hoist_invariants (class loop *loop, edge pe)
    3817              : {
    3818              :   /* Only hoist from the now unconditionally executed part of the loop.  */
    3819        25979 :   basic_block bb = loop->header;
    3820        25979 :   gimple_stmt_iterator hoist_gsi = {};
    3821       863273 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    3822              :     {
    3823       811315 :       gimple *stmt = gsi_stmt (gsi);
    3824       811315 :       if (ifcvt_can_hoist (loop, pe, stmt))
    3825              :         {
    3826              :           /* Once we've hoisted one statement, insert other statements
    3827              :              after it.  */
    3828         5107 :           gsi_remove (&gsi, false);
    3829         5107 :           if (hoist_gsi.ptr)
    3830         2699 :             gsi_insert_after (&hoist_gsi, stmt, GSI_NEW_STMT);
    3831              :           else
    3832              :             {
    3833         2408 :               gsi_insert_on_edge_immediate (pe, stmt);
    3834         2408 :               hoist_gsi = gsi_for_stmt (stmt);
    3835              :             }
    3836         5107 :           continue;
    3837              :         }
    3838       806208 :       gsi_next (&gsi);
    3839              :     }
    3840        25979 : }
    3841              : 
    3842              : /* Returns the DECL_FIELD_BIT_OFFSET of the bitfield accesse in stmt iff its
    3843              :    type mode is not BLKmode.  If BITPOS is not NULL it will hold the poly_int64
    3844              :    value of the DECL_FIELD_BIT_OFFSET of the bitfield access and STRUCT_EXPR,
    3845              :    if not NULL, will hold the tree representing the base struct of this
    3846              :    bitfield.  */
    3847              : 
    3848              : static tree
    3849         1251 : get_bitfield_rep (gassign *stmt, bool write, tree *bitpos,
    3850              :                   tree *struct_expr)
    3851              : {
    3852         1251 :   tree comp_ref = write ? gimple_assign_lhs (stmt)
    3853          384 :                         : gimple_assign_rhs1 (stmt);
    3854              : 
    3855         1251 :   tree field_decl = TREE_OPERAND (comp_ref, 1);
    3856         1251 :   tree ref_offset = component_ref_field_offset (comp_ref);
    3857         1251 :   tree rep_decl = DECL_BIT_FIELD_REPRESENTATIVE (field_decl);
    3858              : 
    3859              :   /* Bail out if the representative is not a suitable type for a scalar
    3860              :      register variable.  */
    3861         1251 :   if (!is_gimple_reg_type (TREE_TYPE (rep_decl)))
    3862              :     return NULL_TREE;
    3863              : 
    3864              :   /* Bail out if the DECL_SIZE of the field_decl isn't the same as the BF's
    3865              :      precision.  */
    3866         1236 :   unsigned HOST_WIDE_INT bf_prec
    3867         1236 :     = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)));
    3868         1236 :   if (compare_tree_int (DECL_SIZE (field_decl), bf_prec) != 0)
    3869              :     return NULL_TREE;
    3870              : 
    3871         1236 :   if (TREE_CODE (DECL_FIELD_OFFSET (rep_decl)) != INTEGER_CST
    3872         1236 :       || TREE_CODE (ref_offset) != INTEGER_CST)
    3873              :     {
    3874            2 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3875            2 :         fprintf (dump_file, "\t Bitfield NOT OK to lower,"
    3876              :                             " offset is non-constant.\n");
    3877              :       return NULL_TREE;
    3878              :     }
    3879              : 
    3880         1234 :   if (struct_expr)
    3881          617 :     *struct_expr = TREE_OPERAND (comp_ref, 0);
    3882              : 
    3883         1234 :   if (bitpos)
    3884              :     {
    3885              :       /* To calculate the bitposition of the BITFIELD_REF we have to determine
    3886              :          where our bitfield starts in relation to the container REP_DECL. The
    3887              :          DECL_FIELD_OFFSET of the original bitfield's member FIELD_DECL tells
    3888              :          us how many bytes from the start of the structure there are until the
    3889              :          start of the group of bitfield members the FIELD_DECL belongs to,
    3890              :          whereas DECL_FIELD_BIT_OFFSET will tell us how many bits from that
    3891              :          position our actual bitfield member starts.  For the container
    3892              :          REP_DECL adding DECL_FIELD_OFFSET and DECL_FIELD_BIT_OFFSET will tell
    3893              :          us the distance between the start of the structure and the start of
    3894              :          the container, though the first is in bytes and the later other in
    3895              :          bits.  With this in mind we calculate the bit position of our new
    3896              :          BITFIELD_REF by subtracting the number of bits between the start of
    3897              :          the structure and the container from the number of bits from the start
    3898              :          of the structure and the actual bitfield member. */
    3899          617 :       tree bf_pos = fold_build2 (MULT_EXPR, bitsizetype,
    3900              :                                  ref_offset,
    3901              :                                  build_int_cst (bitsizetype, BITS_PER_UNIT));
    3902          617 :       bf_pos = fold_build2 (PLUS_EXPR, bitsizetype, bf_pos,
    3903              :                             DECL_FIELD_BIT_OFFSET (field_decl));
    3904          617 :       tree rep_pos = fold_build2 (MULT_EXPR, bitsizetype,
    3905              :                                   DECL_FIELD_OFFSET (rep_decl),
    3906              :                                   build_int_cst (bitsizetype, BITS_PER_UNIT));
    3907          617 :       rep_pos = fold_build2 (PLUS_EXPR, bitsizetype, rep_pos,
    3908              :                              DECL_FIELD_BIT_OFFSET (rep_decl));
    3909              : 
    3910          617 :       *bitpos = fold_build2 (MINUS_EXPR, bitsizetype, bf_pos, rep_pos);
    3911              :     }
    3912              : 
    3913              :   return rep_decl;
    3914              : 
    3915              : }
    3916              : 
    3917              : /* Lowers the bitfield described by DATA.
    3918              :    For a write like:
    3919              : 
    3920              :    struct.bf = _1;
    3921              : 
    3922              :    lower to:
    3923              : 
    3924              :    __ifc_1 = struct.<representative>;
    3925              :    __ifc_2 = BIT_INSERT_EXPR (__ifc_1, _1, bitpos);
    3926              :    struct.<representative> = __ifc_2;
    3927              : 
    3928              :    For a read:
    3929              : 
    3930              :    _1 = struct.bf;
    3931              : 
    3932              :     lower to:
    3933              : 
    3934              :     __ifc_1 = struct.<representative>;
    3935              :     _1 =  BIT_FIELD_REF (__ifc_1, bitsize, bitpos);
    3936              : 
    3937              :     where representative is a legal load that contains the bitfield value,
    3938              :     bitsize is the size of the bitfield and bitpos the offset to the start of
    3939              :     the bitfield within the representative.  */
    3940              : 
    3941              : static void
    3942          617 : lower_bitfield (gassign *stmt, bool write)
    3943              : {
    3944          617 :   tree struct_expr;
    3945          617 :   tree bitpos;
    3946          617 :   tree rep_decl = get_bitfield_rep (stmt, write, &bitpos, &struct_expr);
    3947          617 :   tree rep_type = TREE_TYPE (rep_decl);
    3948          617 :   tree bf_type = TREE_TYPE (gimple_assign_lhs (stmt));
    3949              : 
    3950          617 :   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
    3951          617 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3952              :     {
    3953            9 :       fprintf (dump_file, "Lowering:\n");
    3954            9 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    3955            9 :       fprintf (dump_file, "to:\n");
    3956              :     }
    3957              : 
    3958              :   /* REP_COMP_REF is a COMPONENT_REF for the representative.  NEW_VAL is it's
    3959              :      defining SSA_NAME.  */
    3960          617 :   tree rep_comp_ref = build3 (COMPONENT_REF, rep_type, struct_expr, rep_decl,
    3961              :                               NULL_TREE);
    3962          617 :   tree new_val = ifc_temp_var (rep_type, rep_comp_ref, &gsi);
    3963              : 
    3964          617 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3965            9 :     print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
    3966              : 
    3967          617 :   if (write)
    3968              :     {
    3969          429 :       new_val = ifc_temp_var (rep_type,
    3970              :                               build3 (BIT_INSERT_EXPR, rep_type, new_val,
    3971              :                                       unshare_expr (gimple_assign_rhs1 (stmt)),
    3972              :                                       bitpos), &gsi);
    3973              : 
    3974          429 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3975            0 :         print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
    3976              : 
    3977          429 :       gimple *new_stmt = gimple_build_assign (unshare_expr (rep_comp_ref),
    3978              :                                               new_val);
    3979          429 :       gimple_move_vops (new_stmt, stmt);
    3980          429 :       gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
    3981              : 
    3982          429 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3983            0 :         print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    3984              :     }
    3985              :   else
    3986              :     {
    3987          188 :       tree bfr = build3 (BIT_FIELD_REF, bf_type, new_val,
    3988          188 :                          build_int_cst (bitsizetype, TYPE_PRECISION (bf_type)),
    3989              :                          bitpos);
    3990          188 :       new_val = ifc_temp_var (bf_type, bfr, &gsi);
    3991              : 
    3992          188 :       gimple *new_stmt = gimple_build_assign (gimple_assign_lhs (stmt),
    3993              :                                               new_val);
    3994          188 :       gimple_move_vops (new_stmt, stmt);
    3995          188 :       gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
    3996              : 
    3997          188 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3998            9 :         print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    3999              :     }
    4000              : 
    4001          617 :   gsi_remove (&gsi, true);
    4002          617 : }
    4003              : 
    4004              : /* Return TRUE if there are bitfields to lower in this LOOP.  Fill TO_LOWER
    4005              :    with data structures representing these bitfields.  */
    4006              : 
    4007              : static bool
    4008       247871 : bitfields_to_lower_p (class loop *loop,
    4009              :                       vec <gassign *> &reads_to_lower,
    4010              :                       vec <gassign *> &writes_to_lower)
    4011              : {
    4012       247871 :   gimple_stmt_iterator gsi;
    4013              : 
    4014       247871 :   if (dump_file && (dump_flags & TDF_DETAILS))
    4015              :     {
    4016           40 :       fprintf (dump_file, "Analyzing loop %d for bitfields:\n", loop->num);
    4017              :     }
    4018              : 
    4019      1038160 :   for (unsigned i = 0; i < loop->num_nodes; ++i)
    4020              :     {
    4021       790313 :       basic_block bb = ifc_bbs[i];
    4022      6849846 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    4023              :         {
    4024      5269244 :           gassign *stmt = dyn_cast<gassign*> (gsi_stmt (gsi));
    4025      5269244 :           if (!stmt)
    4026      5141227 :             continue;
    4027              : 
    4028      2095032 :           tree op = gimple_assign_lhs (stmt);
    4029      2095032 :           bool write = TREE_CODE (op) == COMPONENT_REF;
    4030              : 
    4031      2095032 :           if (!write)
    4032      2063222 :             op = gimple_assign_rhs1 (stmt);
    4033              : 
    4034      2095032 :           if (TREE_CODE (op) != COMPONENT_REF)
    4035      1967015 :             continue;
    4036              : 
    4037       128017 :           if (DECL_BIT_FIELD_TYPE (TREE_OPERAND (op, 1)))
    4038              :             {
    4039          641 :               if (dump_file && (dump_flags & TDF_DETAILS))
    4040           11 :                 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    4041              : 
    4042          641 :               if (TREE_THIS_VOLATILE (op)
    4043          641 :                   || reverse_storage_order_for_component_p (op))
    4044              :                 {
    4045            7 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    4046            0 :                     fprintf (dump_file, "\t Bitfield NO OK to lower,"
    4047              :                                         " the access is volatile or"
    4048              :                                         " has reverse storage-order.\n");
    4049           24 :                   return false;
    4050              :                 }
    4051              : 
    4052          634 :               if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
    4053              :                 {
    4054            0 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    4055            0 :                     fprintf (dump_file, "\t Bitfield NO OK to lower,"
    4056              :                                         " field type is not Integral.\n");
    4057              :                   return false;
    4058              :                 }
    4059              : 
    4060          634 :               if (!get_bitfield_rep (stmt, write, NULL, NULL))
    4061              :                 {
    4062           17 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    4063            2 :                     fprintf (dump_file, "\t Bitfield NOT OK to lower,"
    4064              :                                         " representative is BLKmode.\n");
    4065              :                   return false;
    4066              :                 }
    4067              : 
    4068          617 :               if (dump_file && (dump_flags & TDF_DETAILS))
    4069            9 :                 fprintf (dump_file, "\tBitfield OK to lower.\n");
    4070          617 :               if (write)
    4071          429 :                 writes_to_lower.safe_push (stmt);
    4072              :               else
    4073          188 :                 reads_to_lower.safe_push (stmt);
    4074              :             }
    4075              :         }
    4076              :     }
    4077       495559 :   return !reads_to_lower.is_empty () || !writes_to_lower.is_empty ();
    4078              : }
    4079              : 
    4080              : 
    4081              : /* If-convert LOOP when it is legal.  For the moment this pass has no
    4082              :    profitability analysis.  Returns non-zero todo flags when something
    4083              :    changed.  */
    4084              : 
    4085              : unsigned int
    4086       512053 : tree_if_conversion (class loop *loop, vec<gimple *> *preds)
    4087              : {
    4088       512053 :   unsigned int todo = 0;
    4089       512053 :   bool aggressive_if_conv;
    4090       512053 :   class loop *rloop;
    4091       512053 :   auto_vec <gassign *, 4> reads_to_lower;
    4092       512053 :   auto_vec <gassign *, 4> writes_to_lower;
    4093       512053 :   bitmap exit_bbs;
    4094       512053 :   edge pe;
    4095       512053 :   auto_vec<data_reference_p, 10> refs;
    4096       512977 :   class loop *vloop, *nloop;
    4097              : 
    4098       512977 :  again:
    4099       512977 :   rloop = NULL;
    4100       512977 :   ifc_bbs = NULL;
    4101       512977 :   need_to_lower_bitfields = false;
    4102       512977 :   need_to_ifcvt = false;
    4103       512977 :   need_to_predicate = false;
    4104       512977 :   need_to_rewrite_undefined = false;
    4105       512977 :   any_complicated_phi = false;
    4106              : 
    4107              :   /* Apply more aggressive if-conversion when loop or its outer loop were
    4108              :      marked with simd pragma.  When that's the case, we try to if-convert
    4109              :      loop containing PHIs with more than MAX_PHI_ARG_NUM arguments.  */
    4110       512977 :   aggressive_if_conv = loop->force_vectorize;
    4111       512977 :   if (!aggressive_if_conv)
    4112              :     {
    4113       504537 :       class loop *outer_loop = loop_outer (loop);
    4114       504537 :       if (outer_loop && outer_loop->force_vectorize)
    4115         8696 :         aggressive_if_conv = true;
    4116              :     }
    4117              : 
    4118              :   /* If there are more than two BBs in the loop then there is at least one if
    4119              :      to convert.  */
    4120       512977 :   if (loop->num_nodes > 2
    4121       512977 :       && !ifcvt_split_critical_edges (loop, aggressive_if_conv))
    4122        98396 :     goto cleanup;
    4123              : 
    4124       414581 :   ifc_bbs = get_loop_body_in_if_conv_order (loop);
    4125       414581 :   if (!ifc_bbs)
    4126              :     {
    4127         2647 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4128            3 :         fprintf (dump_file, "Irreducible loop\n");
    4129         2647 :       goto cleanup;
    4130              :     }
    4131              : 
    4132       411934 :   if (find_data_references_in_loop (loop, &refs) == chrec_dont_know)
    4133       151225 :     goto cleanup;
    4134              : 
    4135       260709 :   if (loop->num_nodes > 2)
    4136              :     {
    4137              :       /* More than one loop exit is too much to handle.  */
    4138       138132 :       if (!single_exit (loop))
    4139              :         {
    4140        99580 :           if (dump_file && (dump_flags & TDF_DETAILS))
    4141           10 :             fprintf (dump_file, "Can not ifcvt due to multiple exits\n");
    4142              :         }
    4143              :       else
    4144              :         {
    4145        38552 :           need_to_ifcvt = true;
    4146              : 
    4147        38552 :           if (!if_convertible_loop_p (loop, &refs)
    4148        38552 :               || !dbg_cnt (if_conversion_tree))
    4149        12838 :             goto cleanup;
    4150              :         }
    4151              :     }
    4152              : 
    4153       247871 :   need_to_lower_bitfields = bitfields_to_lower_p (loop, reads_to_lower,
    4154              :                                                   writes_to_lower);
    4155              : 
    4156       247871 :   if (!need_to_ifcvt && !need_to_lower_bitfields)
    4157       221892 :     goto cleanup;
    4158              : 
    4159              :   /* The edge to insert invariant stmts on.  */
    4160        25979 :   pe = loop_preheader_edge (loop);
    4161              : 
    4162              :   /* Since we have no cost model, always version loops.
    4163              :      Either version this loop, or if the pattern is right for outer-loop
    4164              :      vectorization, version the outer loop.  In the latter case we will
    4165              :      still if-convert the original inner loop.  */
    4166        25979 :   vloop = (versionable_outer_loop_p (loop_outer (loop))
    4167        25979 :            ? loop_outer (loop) : loop);
    4168        25979 :   nloop = version_loop_for_if_conversion (vloop, preds);
    4169        25979 :   if (nloop == NULL)
    4170            0 :     goto cleanup;
    4171        25979 :   if (vloop != loop)
    4172              :     {
    4173              :       /* If versionable_outer_loop_p decided to version the
    4174              :          outer loop, version also the inner loop of the non-vectorized
    4175              :          loop copy.  So we transform:
    4176              :              loop1
    4177              :                 loop2
    4178              :              into:
    4179              :               if (LOOP_VECTORIZED (1, 3))
    4180              :                 {
    4181              :                   loop1
    4182              :                     loop2
    4183              :                 }
    4184              :               else
    4185              :                 loop3 (copy of loop1)
    4186              :                   if (LOOP_VECTORIZED (4, 5))
    4187              :                     loop4 (copy of loop2)
    4188              :                   else
    4189              :                     loop5 (copy of loop4)  */
    4190          924 :       gcc_assert (nloop->inner && nloop->inner->next == NULL);
    4191              :       rloop = nloop->inner;
    4192              :     }
    4193              :   else
    4194              :     /* If we versioned loop then make sure to insert invariant
    4195              :        stmts before the .LOOP_VECTORIZED check since the vectorizer
    4196              :        will re-use that for things like runtime alias versioning
    4197              :        whose condition can end up using those invariants.  */
    4198        25055 :     pe = single_pred_edge (gimple_bb (preds->last ()));
    4199              : 
    4200        25979 :   if (need_to_lower_bitfields)
    4201              :     {
    4202          266 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4203              :         {
    4204            9 :           fprintf (dump_file, "-------------------------\n");
    4205            9 :           fprintf (dump_file, "Start lowering bitfields\n");
    4206              :         }
    4207          454 :       while (!reads_to_lower.is_empty ())
    4208          188 :         lower_bitfield (reads_to_lower.pop (), false);
    4209          695 :       while (!writes_to_lower.is_empty ())
    4210          429 :         lower_bitfield (writes_to_lower.pop (), true);
    4211              : 
    4212          266 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4213              :         {
    4214            9 :           fprintf (dump_file, "Done lowering bitfields\n");
    4215            9 :           fprintf (dump_file, "-------------------------\n");
    4216              :         }
    4217              :     }
    4218        25979 :   if (need_to_ifcvt)
    4219              :     {
    4220              :       /* Before we rewrite edges we'll record their original position in the
    4221              :          edge map such that we can map the edges between the ifcvt and the
    4222              :          non-ifcvt loop during peeling.  */
    4223        25714 :       uintptr_t idx = 0;
    4224       102856 :       for (edge exit : get_loop_exit_edges (loop))
    4225        25714 :         exit->aux = (void*)idx++;
    4226              : 
    4227              :       /* Now all statements are if-convertible.  Combine all the basic
    4228              :          blocks into one huge basic block doing the if-conversion
    4229              :          on-the-fly.  */
    4230        25714 :       combine_blocks (loop);
    4231              :     }
    4232              : 
    4233        25979 :   std::pair <tree, tree> *name_pair;
    4234        25979 :   unsigned ssa_names_idx;
    4235        31306 :   FOR_EACH_VEC_ELT (redundant_ssa_names, ssa_names_idx, name_pair)
    4236         5327 :     replace_uses_by (name_pair->first, name_pair->second);
    4237        25979 :   redundant_ssa_names.release ();
    4238              : 
    4239              :   /* Perform local CSE, this esp. helps the vectorizer analysis if loads
    4240              :      and stores are involved.  CSE only the loop body, not the entry
    4241              :      PHIs, those are to be kept in sync with the non-if-converted copy.
    4242              :      ???  We'll still keep dead stores though.  */
    4243        25979 :   exit_bbs = BITMAP_ALLOC (NULL);
    4244       104098 :   for (edge exit : get_loop_exit_edges (loop))
    4245        26179 :     bitmap_set_bit (exit_bbs, exit->dest->index);
    4246        25979 :   todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs,
    4247              :                      false, true, true);
    4248              : 
    4249              :   /* Delete dead predicate computations.  */
    4250        25979 :   ifcvt_local_dce (loop);
    4251        25979 :   BITMAP_FREE (exit_bbs);
    4252              : 
    4253        25979 :   ifcvt_hoist_invariants (loop, pe);
    4254              : 
    4255        25979 :   todo |= TODO_cleanup_cfg;
    4256              : 
    4257       512977 :  cleanup:
    4258       512977 :   data_reference_p dr;
    4259       512977 :   unsigned int i;
    4260      1685435 :   for (i = 0; refs.iterate (i, &dr); i++)
    4261              :     {
    4262      1172458 :       free (dr->aux);
    4263      1172458 :       free_data_ref (dr);
    4264              :     }
    4265       512977 :   refs.truncate (0);
    4266              : 
    4267       512977 :   if (ifc_bbs)
    4268              :     {
    4269              :       unsigned int i;
    4270              : 
    4271      2028526 :       for (i = 0; i < loop->num_nodes; i++)
    4272      1642306 :         free_bb_predicate (ifc_bbs[i]);
    4273              : 
    4274       386220 :       free (ifc_bbs);
    4275       386220 :       ifc_bbs = NULL;
    4276              :     }
    4277       512977 :   if (rloop != NULL)
    4278              :     {
    4279          924 :       loop = rloop;
    4280          924 :       reads_to_lower.truncate (0);
    4281          924 :       writes_to_lower.truncate (0);
    4282          924 :       goto again;
    4283              :     }
    4284              : 
    4285       512053 :   return todo;
    4286       512053 : }
    4287              : 
    4288              : /* Tree if-conversion pass management.  */
    4289              : 
    4290              : namespace {
    4291              : 
    4292              : const pass_data pass_data_if_conversion =
    4293              : {
    4294              :   GIMPLE_PASS, /* type */
    4295              :   "ifcvt", /* name */
    4296              :   OPTGROUP_NONE, /* optinfo_flags */
    4297              :   TV_TREE_LOOP_IFCVT, /* tv_id */
    4298              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    4299              :   0, /* properties_provided */
    4300              :   0, /* properties_destroyed */
    4301              :   0, /* todo_flags_start */
    4302              :   0, /* todo_flags_finish */
    4303              : };
    4304              : 
    4305              : class pass_if_conversion : public gimple_opt_pass
    4306              : {
    4307              : public:
    4308       297180 :   pass_if_conversion (gcc::context *ctxt)
    4309       594360 :     : gimple_opt_pass (pass_data_if_conversion, ctxt)
    4310              :   {}
    4311              : 
    4312              :   /* opt_pass methods: */
    4313              :   bool gate (function *) final override;
    4314              :   unsigned int execute (function *) final override;
    4315              : 
    4316              : }; // class pass_if_conversion
    4317              : 
    4318              : bool
    4319       248475 : pass_if_conversion::gate (function *fun)
    4320              : {
    4321       248475 :   return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
    4322              : }
    4323              : 
    4324              : unsigned int
    4325       214144 : pass_if_conversion::execute (function *fun)
    4326              : {
    4327       214144 :   unsigned todo = 0;
    4328              : 
    4329       428288 :   if (number_of_loops (fun) <= 1)
    4330              :     return 0;
    4331              : 
    4332       214144 :   auto_vec<gimple *> preds;
    4333      1162116 :   for (auto loop : loops_list (cfun, 0))
    4334       519684 :     if ((flag_tree_loop_vectorize || loop->force_vectorize)
    4335       516820 :         && !loop->dont_vectorize)
    4336       512053 :       todo |= tree_if_conversion (loop, &preds);
    4337              : 
    4338       214144 :   if (todo)
    4339              :     {
    4340        17757 :       free_numbers_of_iterations_estimates (fun);
    4341        17757 :       scev_reset ();
    4342              :     }
    4343              : 
    4344       214144 :   if (flag_checking)
    4345              :     {
    4346       214140 :       basic_block bb;
    4347      7208183 :       FOR_EACH_BB_FN (bb, fun)
    4348      6994043 :         gcc_assert (!bb->aux);
    4349              :     }
    4350              : 
    4351              :   /* Perform IL update now, it might elide some loops.  */
    4352       214144 :   if (todo & TODO_cleanup_cfg)
    4353              :     {
    4354        17757 :       cleanup_tree_cfg ();
    4355        17757 :       if (need_ssa_update_p (fun))
    4356            0 :         todo |= TODO_update_ssa;
    4357              :     }
    4358       214144 :   if (todo & TODO_update_ssa_any)
    4359            0 :     update_ssa (todo & TODO_update_ssa_any);
    4360              : 
    4361              :   /* If if-conversion elided the loop fall back to the original one.  Likewise
    4362              :      if the loops are not nested in the same outer loop.  */
    4363       240123 :   for (unsigned i = 0; i < preds.length (); ++i)
    4364              :     {
    4365        25979 :       gimple *g = preds[i];
    4366        25979 :       if (!gimple_bb (g))
    4367            0 :         continue;
    4368        25979 :       auto ifcvt_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 0)));
    4369        25979 :       auto orig_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 1)));
    4370        25979 :       if (!ifcvt_loop || !orig_loop)
    4371              :         {
    4372            2 :           if (dump_file)
    4373            0 :             fprintf (dump_file, "If-converted loop vanished\n");
    4374            2 :           fold_loop_internal_call (g, boolean_false_node);
    4375              :         }
    4376        25977 :       else if (loop_outer (ifcvt_loop) != loop_outer (orig_loop))
    4377              :         {
    4378            0 :           if (dump_file)
    4379            0 :             fprintf (dump_file, "If-converted loop in different outer loop\n");
    4380            0 :           fold_loop_internal_call (g, boolean_false_node);
    4381              :         }
    4382              :     }
    4383              : 
    4384       214144 :   return 0;
    4385       214144 : }
    4386              : 
    4387              : } // anon namespace
    4388              : 
    4389              : gimple_opt_pass *
    4390       297180 : make_pass_if_conversion (gcc::context *ctxt)
    4391              : {
    4392       297180 :   return new pass_if_conversion (ctxt);
    4393              : }
        

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.