LCOV - code coverage report
Current view: top level - gcc - tree-if-conv.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1252 1367 91.6 %
Date: 2020-03-28 11:57:23 Functions: 52 56 92.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* If-conversion for vectorizer.
       2                 :            :    Copyright (C) 2004-2020 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 "optabs-query.h"
      95                 :            : #include "gimple-pretty-print.h"
      96                 :            : #include "alias.h"
      97                 :            : #include "fold-const.h"
      98                 :            : #include "stor-layout.h"
      99                 :            : #include "gimple-fold.h"
     100                 :            : #include "gimplify.h"
     101                 :            : #include "gimple-iterator.h"
     102                 :            : #include "gimplify-me.h"
     103                 :            : #include "tree-cfg.h"
     104                 :            : #include "tree-into-ssa.h"
     105                 :            : #include "tree-ssa.h"
     106                 :            : #include "cfgloop.h"
     107                 :            : #include "tree-data-ref.h"
     108                 :            : #include "tree-scalar-evolution.h"
     109                 :            : #include "tree-ssa-loop.h"
     110                 :            : #include "tree-ssa-loop-niter.h"
     111                 :            : #include "tree-ssa-loop-ivopts.h"
     112                 :            : #include "tree-ssa-address.h"
     113                 :            : #include "dbgcnt.h"
     114                 :            : #include "tree-hash-traits.h"
     115                 :            : #include "varasm.h"
     116                 :            : #include "builtins.h"
     117                 :            : #include "cfganal.h"
     118                 :            : #include "internal-fn.h"
     119                 :            : #include "fold-const.h"
     120                 :            : #include "tree-ssa-sccvn.h"
     121                 :            : #include "tree-cfgcleanup.h"
     122                 :            : #include "tree-ssa-dse.h"
     123                 :            : 
     124                 :            : /* Only handle PHIs with no more arguments unless we are asked to by
     125                 :            :    simd pragma.  */
     126                 :            : #define MAX_PHI_ARG_NUM \
     127                 :            :   ((unsigned) param_max_tree_if_conversion_phi_args)
     128                 :            : 
     129                 :            : /* True if we've converted a statement that was only executed when some
     130                 :            :    condition C was true, and if for correctness we need to predicate the
     131                 :            :    statement to ensure that it is a no-op when C is false.  See
     132                 :            :    predicate_statements for the kinds of predication we support.  */
     133                 :            : static bool need_to_predicate;
     134                 :            : 
     135                 :            : /* Indicate if there are any complicated PHIs that need to be handled in
     136                 :            :    if-conversion.  Complicated PHI has more than two arguments and can't
     137                 :            :    be degenerated to two arguments PHI.  See more information in comment
     138                 :            :    before phi_convertible_by_degenerating_args.  */
     139                 :            : static bool any_complicated_phi;
     140                 :            : 
     141                 :            : /* Hash for struct innermost_loop_behavior.  It depends on the user to
     142                 :            :    free the memory.  */
     143                 :            : 
     144                 :            : struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
     145                 :            : {
     146                 :            :   static inline hashval_t hash (const value_type &);
     147                 :            :   static inline bool equal (const value_type &,
     148                 :            :                             const compare_type &);
     149                 :            : };
     150                 :            : 
     151                 :            : inline hashval_t
     152                 :      45857 : innermost_loop_behavior_hash::hash (const value_type &e)
     153                 :            : {
     154                 :      45857 :   hashval_t hash;
     155                 :            : 
     156                 :      45857 :   hash = iterative_hash_expr (e->base_address, 0);
     157                 :      45857 :   hash = iterative_hash_expr (e->offset, hash);
     158                 :      45857 :   hash = iterative_hash_expr (e->init, hash);
     159                 :      45857 :   return iterative_hash_expr (e->step, hash);
     160                 :            : }
     161                 :            : 
     162                 :            : inline bool
     163                 :      33453 : innermost_loop_behavior_hash::equal (const value_type &e1,
     164                 :            :                                      const compare_type &e2)
     165                 :            : {
     166                 :      33453 :   if ((e1->base_address && !e2->base_address)
     167                 :      33453 :       || (!e1->base_address && e2->base_address)
     168                 :      33453 :       || (!e1->offset && e2->offset)
     169                 :      31864 :       || (e1->offset && !e2->offset)
     170                 :      28852 :       || (!e1->init && e2->init)
     171                 :      28852 :       || (e1->init && !e2->init)
     172                 :      28852 :       || (!e1->step && e2->step)
     173                 :      28852 :       || (e1->step && !e2->step))
     174                 :            :     return false;
     175                 :            : 
     176                 :      28852 :   if (e1->base_address && e2->base_address
     177                 :      57704 :       && !operand_equal_p (e1->base_address, e2->base_address, 0))
     178                 :            :     return false;
     179                 :       9381 :   if (e1->offset && e2->offset
     180                 :      20357 :       && !operand_equal_p (e1->offset, e2->offset, 0))
     181                 :            :     return false;
     182                 :       9221 :   if (e1->init && e2->init
     183                 :      20037 :       && !operand_equal_p (e1->init, e2->init, 0))
     184                 :            :     return false;
     185                 :       3019 :   if (e1->step && e2->step
     186                 :       7633 :       && !operand_equal_p (e1->step, e2->step, 0))
     187                 :          0 :     return false;
     188                 :            : 
     189                 :            :   return true;
     190                 :            : }
     191                 :            : 
     192                 :            : /* List of basic blocks in if-conversion-suitable order.  */
     193                 :            : static basic_block *ifc_bbs;
     194                 :            : 
     195                 :            : /* Hash table to store <DR's innermost loop behavior, DR> pairs.  */
     196                 :            : static hash_map<innermost_loop_behavior_hash,
     197                 :            :                 data_reference_p> *innermost_DR_map;
     198                 :            : 
     199                 :            : /* Hash table to store <base reference, DR> pairs.  */
     200                 :            : static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;
     201                 :            : 
     202                 :            : /* List of redundant SSA names: the first should be replaced by the second.  */
     203                 :            : static vec< std::pair<tree, tree> > redundant_ssa_names;
     204                 :            : 
     205                 :            : /* Structure used to predicate basic blocks.  This is attached to the
     206                 :            :    ->aux field of the BBs in the loop to be if-converted.  */
     207                 :            : struct bb_predicate {
     208                 :            : 
     209                 :            :   /* The condition under which this basic block is executed.  */
     210                 :            :   tree predicate;
     211                 :            : 
     212                 :            :   /* PREDICATE is gimplified, and the sequence of statements is
     213                 :            :      recorded here, in order to avoid the duplication of computations
     214                 :            :      that occur in previous conditions.  See PR44483.  */
     215                 :            :   gimple_seq predicate_gimplified_stmts;
     216                 :            : };
     217                 :            : 
     218                 :            : /* Returns true when the basic block BB has a predicate.  */
     219                 :            : 
     220                 :            : static inline bool
     221                 :      53090 : bb_has_predicate (basic_block bb)
     222                 :            : {
     223                 :      53090 :   return bb->aux != NULL;
     224                 :            : }
     225                 :            : 
     226                 :            : /* Returns the gimplified predicate for basic block BB.  */
     227                 :            : 
     228                 :            : static inline tree
     229                 :     112497 : bb_predicate (basic_block bb)
     230                 :            : {
     231                 :     112497 :   return ((struct bb_predicate *) bb->aux)->predicate;
     232                 :            : }
     233                 :            : 
     234                 :            : /* Sets the gimplified predicate COND for basic block BB.  */
     235                 :            : 
     236                 :            : static inline void
     237                 :            : set_bb_predicate (basic_block bb, tree cond)
     238                 :            : {
     239                 :            :   gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
     240                 :            :                && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
     241                 :            :               || is_gimple_condexpr (cond));
     242                 :            :   ((struct bb_predicate *) bb->aux)->predicate = cond;
     243                 :            : }
     244                 :            : 
     245                 :            : /* Returns the sequence of statements of the gimplification of the
     246                 :            :    predicate for basic block BB.  */
     247                 :            : 
     248                 :            : static inline gimple_seq
     249                 :      79743 : bb_predicate_gimplified_stmts (basic_block bb)
     250                 :            : {
     251                 :      79743 :   return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
     252                 :            : }
     253                 :            : 
     254                 :            : /* Sets the sequence of statements STMTS of the gimplification of the
     255                 :            :    predicate for basic block BB.  */
     256                 :            : 
     257                 :            : static inline void
     258                 :      30814 : set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
     259                 :            : {
     260                 :      30814 :   ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
     261                 :       3077 : }
     262                 :            : 
     263                 :            : /* Adds the sequence of statements STMTS to the sequence of statements
     264                 :            :    of the predicate for basic block BB.  */
     265                 :            : 
     266                 :            : static inline void
     267                 :            : add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
     268                 :            : {
     269                 :            :   /* We might have updated some stmts in STMTS via force_gimple_operand
     270                 :            :      calling fold_stmt and that producing multiple stmts.  Delink immediate
     271                 :            :      uses so update_ssa after loop versioning doesn't get confused for
     272                 :            :      the not yet inserted predicates.
     273                 :            :      ???  This should go away once we reliably avoid updating stmts
     274                 :            :      not in any BB.  */
     275                 :            :   for (gimple_stmt_iterator gsi = gsi_start (stmts);
     276                 :            :        !gsi_end_p (gsi); gsi_next (&gsi))
     277                 :            :     {
     278                 :            :       gimple *stmt = gsi_stmt (gsi);
     279                 :            :       delink_stmt_imm_use (stmt);
     280                 :            :       gimple_set_modified (stmt, true);
     281                 :            :     }
     282                 :            :   gimple_seq_add_seq_without_update
     283                 :            :     (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
     284                 :            : }
     285                 :            : 
     286                 :            : /* Initializes to TRUE the predicate of basic block BB.  */
     287                 :            : 
     288                 :            : static inline void
     289                 :      27737 : init_bb_predicate (basic_block bb)
     290                 :            : {
     291                 :      27737 :   bb->aux = XNEW (struct bb_predicate);
     292                 :      27737 :   set_bb_predicate_gimplified_stmts (bb, NULL);
     293                 :      27737 :   set_bb_predicate (bb, boolean_true_node);
     294                 :      27737 : }
     295                 :            : 
     296                 :            : /* Release the SSA_NAMEs associated with the predicate of basic block BB.  */
     297                 :            : 
     298                 :            : static inline void
     299                 :      52155 : release_bb_predicate (basic_block bb)
     300                 :            : {
     301                 :      52155 :   gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
     302                 :      52155 :   if (stmts)
     303                 :            :     {
     304                 :            :       /* Ensure that these stmts haven't yet been added to a bb.  */
     305                 :       1293 :       if (flag_checking)
     306                 :       5835 :         for (gimple_stmt_iterator i = gsi_start (stmts);
     307                 :       5835 :              !gsi_end_p (i); gsi_next (&i))
     308                 :       4542 :           gcc_assert (! gimple_bb (gsi_stmt (i)));
     309                 :            : 
     310                 :            :       /* Discard them.  */
     311                 :       1293 :       gimple_seq_discard (stmts);
     312                 :       1293 :       set_bb_predicate_gimplified_stmts (bb, NULL);
     313                 :            :     }
     314                 :      52155 : }
     315                 :            : 
     316                 :            : /* Free the predicate of basic block BB.  */
     317                 :            : 
     318                 :            : static inline void
     319                 :      28672 : free_bb_predicate (basic_block bb)
     320                 :            : {
     321                 :      28672 :   if (!bb_has_predicate (bb))
     322                 :            :     return;
     323                 :            : 
     324                 :      27737 :   release_bb_predicate (bb);
     325                 :      27737 :   free (bb->aux);
     326                 :      27737 :   bb->aux = NULL;
     327                 :            : }
     328                 :            : 
     329                 :            : /* Reinitialize predicate of BB with the true predicate.  */
     330                 :            : 
     331                 :            : static inline void
     332                 :      24418 : reset_bb_predicate (basic_block bb)
     333                 :            : {
     334                 :      24418 :   if (!bb_has_predicate (bb))
     335                 :          0 :     init_bb_predicate (bb);
     336                 :            :   else
     337                 :            :     {
     338                 :      24418 :       release_bb_predicate (bb);
     339                 :      24418 :       set_bb_predicate (bb, boolean_true_node);
     340                 :            :     }
     341                 :      24418 : }
     342                 :            : 
     343                 :            : /* Returns a new SSA_NAME of type TYPE that is assigned the value of
     344                 :            :    the expression EXPR.  Inserts the statement created for this
     345                 :            :    computation before GSI and leaves the iterator GSI at the same
     346                 :            :    statement.  */
     347                 :            : 
     348                 :            : static tree
     349                 :        582 : ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
     350                 :            : {
     351                 :        582 :   tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
     352                 :        582 :   gimple *stmt = gimple_build_assign (new_name, expr);
     353                 :       1164 :   gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
     354                 :        582 :   gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
     355                 :        582 :   return new_name;
     356                 :            : }
     357                 :            : 
     358                 :            : /* Return true when COND is a false predicate.  */
     359                 :            : 
     360                 :            : static inline bool
     361                 :       2159 : is_false_predicate (tree cond)
     362                 :            : {
     363                 :       2159 :   return (cond != NULL_TREE
     364                 :       2159 :           && (cond == boolean_false_node
     365                 :       2159 :               || integer_zerop (cond)));
     366                 :            : }
     367                 :            : 
     368                 :            : /* Return true when COND is a true predicate.  */
     369                 :            : 
     370                 :            : static inline bool
     371                 :     131007 : is_true_predicate (tree cond)
     372                 :            : {
     373                 :     131007 :   return (cond == NULL_TREE
     374                 :     131007 :           || cond == boolean_true_node
     375                 :      60652 :           || integer_onep (cond));
     376                 :            : }
     377                 :            : 
     378                 :            : /* Returns true when BB has a predicate that is not trivial: true or
     379                 :            :    NULL_TREE.  */
     380                 :            : 
     381                 :            : static inline bool
     382                 :      50005 : is_predicated (basic_block bb)
     383                 :            : {
     384                 :      50005 :   return !is_true_predicate (bb_predicate (bb));
     385                 :            : }
     386                 :            : 
     387                 :            : /* Parses the predicate COND and returns its comparison code and
     388                 :            :    operands OP0 and OP1.  */
     389                 :            : 
     390                 :            : static enum tree_code
     391                 :      46048 : parse_predicate (tree cond, tree *op0, tree *op1)
     392                 :            : {
     393                 :      46048 :   gimple *s;
     394                 :            : 
     395                 :      46048 :   if (TREE_CODE (cond) == SSA_NAME
     396                 :      46048 :       && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
     397                 :            :     {
     398                 :       1977 :       if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
     399                 :            :         {
     400                 :          0 :           *op0 = gimple_assign_rhs1 (s);
     401                 :          0 :           *op1 = gimple_assign_rhs2 (s);
     402                 :          0 :           return gimple_assign_rhs_code (s);
     403                 :            :         }
     404                 :            : 
     405                 :       1977 :       else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
     406                 :            :         {
     407                 :          0 :           tree op = gimple_assign_rhs1 (s);
     408                 :          0 :           tree type = TREE_TYPE (op);
     409                 :          0 :           enum tree_code code = parse_predicate (op, op0, op1);
     410                 :            : 
     411                 :          0 :           return code == ERROR_MARK ? ERROR_MARK
     412                 :          0 :             : invert_tree_comparison (code, HONOR_NANS (type));
     413                 :            :         }
     414                 :            : 
     415                 :            :       return ERROR_MARK;
     416                 :            :     }
     417                 :            : 
     418                 :      44071 :   if (COMPARISON_CLASS_P (cond))
     419                 :            :     {
     420                 :       5318 :       *op0 = TREE_OPERAND (cond, 0);
     421                 :       5318 :       *op1 = TREE_OPERAND (cond, 1);
     422                 :       5318 :       return TREE_CODE (cond);
     423                 :            :     }
     424                 :            : 
     425                 :            :   return ERROR_MARK;
     426                 :            : }
     427                 :            : 
     428                 :            : /* Returns the fold of predicate C1 OR C2 at location LOC.  */
     429                 :            : 
     430                 :            : static tree
     431                 :      23024 : fold_or_predicates (location_t loc, tree c1, tree c2)
     432                 :            : {
     433                 :      23024 :   tree op1a, op1b, op2a, op2b;
     434                 :      23024 :   enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
     435                 :      23024 :   enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
     436                 :            : 
     437                 :      23024 :   if (code1 != ERROR_MARK && code2 != ERROR_MARK)
     438                 :            :     {
     439                 :        326 :       tree t = maybe_fold_or_comparisons (boolean_type_node, code1, op1a, op1b,
     440                 :            :                                           code2, op2a, op2b);
     441                 :        326 :       if (t)
     442                 :            :         return t;
     443                 :            :     }
     444                 :            : 
     445                 :      22738 :   return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
     446                 :            : }
     447                 :            : 
     448                 :            : /* Returns either a COND_EXPR or the folded expression if the folded
     449                 :            :    expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
     450                 :            :    a constant or a SSA_NAME. */
     451                 :            : 
     452                 :            : static tree
     453                 :       5225 : fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
     454                 :            : {
     455                 :       5225 :   tree rhs1, lhs1, cond_expr;
     456                 :            : 
     457                 :            :   /* If COND is comparison r != 0 and r has boolean type, convert COND
     458                 :            :      to SSA_NAME to accept by vect bool pattern.  */
     459                 :       5225 :   if (TREE_CODE (cond) == NE_EXPR)
     460                 :            :     {
     461                 :       1931 :       tree op0 = TREE_OPERAND (cond, 0);
     462                 :       1931 :       tree op1 = TREE_OPERAND (cond, 1);
     463                 :       1931 :       if (TREE_CODE (op0) == SSA_NAME
     464                 :       1931 :           && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
     465                 :       2454 :           && (integer_zerop (op1)))
     466                 :            :         cond = op0;
     467                 :            :     }
     468                 :       5225 :   cond_expr = fold_ternary (COND_EXPR, type, cond, rhs, lhs);
     469                 :            : 
     470                 :       5225 :   if (cond_expr == NULL_TREE)
     471                 :       3519 :     return build3 (COND_EXPR, type, cond, rhs, lhs);
     472                 :            : 
     473                 :       1706 :   STRIP_USELESS_TYPE_CONVERSION (cond_expr);
     474                 :            : 
     475                 :       1706 :   if (is_gimple_val (cond_expr))
     476                 :            :     return cond_expr;
     477                 :            : 
     478                 :       1652 :   if (TREE_CODE (cond_expr) == ABS_EXPR)
     479                 :            :     {
     480                 :          0 :       rhs1 = TREE_OPERAND (cond_expr, 1);
     481                 :          0 :       STRIP_USELESS_TYPE_CONVERSION (rhs1);
     482                 :          0 :       if (is_gimple_val (rhs1))
     483                 :          0 :         return build1 (ABS_EXPR, type, rhs1);
     484                 :            :     }
     485                 :            : 
     486                 :       1652 :   if (TREE_CODE (cond_expr) == MIN_EXPR
     487                 :       1652 :       || TREE_CODE (cond_expr) == MAX_EXPR)
     488                 :            :     {
     489                 :         58 :       lhs1 = TREE_OPERAND (cond_expr, 0);
     490                 :         58 :       STRIP_USELESS_TYPE_CONVERSION (lhs1);
     491                 :         58 :       rhs1 = TREE_OPERAND (cond_expr, 1);
     492                 :         58 :       STRIP_USELESS_TYPE_CONVERSION (rhs1);
     493                 :         58 :       if (is_gimple_val (rhs1) && is_gimple_val (lhs1))
     494                 :         58 :         return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
     495                 :            :     }
     496                 :       1594 :   return build3 (COND_EXPR, type, cond, rhs, lhs);
     497                 :            : }
     498                 :            : 
     499                 :            : /* Add condition NC to the predicate list of basic block BB.  LOOP is
     500                 :            :    the loop to be if-converted. Use predicate of cd-equivalent block
     501                 :            :    for join bb if it exists: we call basic blocks bb1 and bb2 
     502                 :            :    cd-equivalent if they are executed under the same condition.  */
     503                 :            : 
     504                 :            : static inline void
     505                 :      23102 : add_to_predicate_list (class loop *loop, basic_block bb, tree nc)
     506                 :            : {
     507                 :      23102 :   tree bc, *tp;
     508                 :      23102 :   basic_block dom_bb;
     509                 :            : 
     510                 :      23102 :   if (is_true_predicate (nc))
     511                 :      10272 :     return;
     512                 :            : 
     513                 :            :   /* If dominance tells us this basic block is always executed,
     514                 :            :      don't record any predicates for it.  */
     515                 :      23102 :   if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
     516                 :            :     return;
     517                 :            : 
     518                 :      13122 :   dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
     519                 :            :   /* We use notion of cd equivalence to get simpler predicate for
     520                 :            :      join block, e.g. if join block has 2 predecessors with predicates
     521                 :            :      p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
     522                 :            :      p1 & p2 | p1 & !p2.  */
     523                 :      13122 :   if (dom_bb != loop->header
     524                 :      13122 :       && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
     525                 :            :     {
     526                 :        292 :       gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
     527                 :        292 :       bc = bb_predicate (dom_bb);
     528                 :        292 :       if (!is_true_predicate (bc))
     529                 :        292 :         set_bb_predicate (bb, bc);
     530                 :            :       else
     531                 :          0 :         gcc_assert (is_true_predicate (bb_predicate (bb)));
     532                 :        292 :       if (dump_file && (dump_flags & TDF_DETAILS))
     533                 :          4 :         fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
     534                 :            :                  dom_bb->index, bb->index);
     535                 :        292 :       return;
     536                 :            :     }
     537                 :            : 
     538                 :      12830 :   if (!is_predicated (bb))
     539                 :      12288 :     bc = nc;
     540                 :            :   else
     541                 :            :     {
     542                 :        542 :       bc = bb_predicate (bb);
     543                 :        542 :       bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
     544                 :        542 :       if (is_true_predicate (bc))
     545                 :            :         {
     546                 :          0 :           reset_bb_predicate (bb);
     547                 :          0 :           return;
     548                 :            :         }
     549                 :            :     }
     550                 :            : 
     551                 :            :   /* Allow a TRUTH_NOT_EXPR around the main predicate.  */
     552                 :      12830 :   if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
     553                 :       4234 :     tp = &TREE_OPERAND (bc, 0);
     554                 :            :   else
     555                 :            :     tp = &bc;
     556                 :      12830 :   if (!is_gimple_condexpr (*tp))
     557                 :            :     {
     558                 :       3288 :       gimple_seq stmts;
     559                 :       3288 :       *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
     560                 :       3288 :       add_bb_predicate_gimplified_stmts (bb, stmts);
     561                 :            :     }
     562                 :      12830 :   set_bb_predicate (bb, bc);
     563                 :            : }
     564                 :            : 
     565                 :            : /* Add the condition COND to the previous condition PREV_COND, and add
     566                 :            :    this to the predicate list of the destination of edge E.  LOOP is
     567                 :            :    the loop to be if-converted.  */
     568                 :            : 
     569                 :            : static void
     570                 :      14552 : add_to_dst_predicate_list (class loop *loop, edge e,
     571                 :            :                            tree prev_cond, tree cond)
     572                 :            : {
     573                 :      14552 :   if (!flow_bb_inside_loop_p (loop, e->dest))
     574                 :            :     return;
     575                 :            : 
     576                 :      14552 :   if (!is_true_predicate (prev_cond))
     577                 :       2920 :     cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
     578                 :            :                         prev_cond, cond);
     579                 :            : 
     580                 :      14552 :   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
     581                 :      12125 :     add_to_predicate_list (loop, e->dest, cond);
     582                 :            : }
     583                 :            : 
     584                 :            : /* Return true if one of the successor edges of BB exits LOOP.  */
     585                 :            : 
     586                 :            : static bool
     587                 :     121488 : bb_with_exit_edge_p (class loop *loop, basic_block bb)
     588                 :            : {
     589                 :     121488 :   edge e;
     590                 :     121488 :   edge_iterator ei;
     591                 :            : 
     592                 :     271025 :   FOR_EACH_EDGE (e, ei, bb->succs)
     593                 :     172371 :     if (loop_exit_edge_p (loop, e))
     594                 :            :       return true;
     595                 :            : 
     596                 :            :   return false;
     597                 :            : }
     598                 :            : 
     599                 :            : /* Given PHI which has more than two arguments, this function checks if
     600                 :            :    it's if-convertible by degenerating its arguments.  Specifically, if
     601                 :            :    below two conditions are satisfied:
     602                 :            : 
     603                 :            :      1) Number of PHI arguments with different values equals to 2 and one
     604                 :            :         argument has the only occurrence.
     605                 :            :      2) The edge corresponding to the unique argument isn't critical edge.
     606                 :            : 
     607                 :            :    Such PHI can be handled as PHIs have only two arguments.  For example,
     608                 :            :    below PHI:
     609                 :            : 
     610                 :            :      res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
     611                 :            : 
     612                 :            :    can be transformed into:
     613                 :            : 
     614                 :            :      res = (predicate of e3) ? A_2 : A_1;
     615                 :            : 
     616                 :            :    Return TRUE if it is the case, FALSE otherwise.  */
     617                 :            : 
     618                 :            : static bool
     619                 :        638 : phi_convertible_by_degenerating_args (gphi *phi)
     620                 :            : {
     621                 :        638 :   edge e;
     622                 :        638 :   tree arg, t1 = NULL, t2 = NULL;
     623                 :        638 :   unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
     624                 :        638 :   unsigned int num_args = gimple_phi_num_args (phi);
     625                 :            : 
     626                 :        638 :   gcc_assert (num_args > 2);
     627                 :            : 
     628                 :       2525 :   for (i = 0; i < num_args; i++)
     629                 :            :     {
     630                 :       2042 :       arg = gimple_phi_arg_def (phi, i);
     631                 :       2042 :       if (t1 == NULL || operand_equal_p (t1, arg, 0))
     632                 :            :         {
     633                 :       1086 :           n1++;
     634                 :       1086 :           i1 = i;
     635                 :       1086 :           t1 = arg;
     636                 :            :         }
     637                 :        956 :       else if (t2 == NULL || operand_equal_p (t2, arg, 0))
     638                 :            :         {
     639                 :        801 :           n2++;
     640                 :        801 :           i2 = i;
     641                 :        801 :           t2 = arg;
     642                 :            :         }
     643                 :            :       else
     644                 :            :         return false;
     645                 :            :     }
     646                 :            : 
     647                 :        483 :   if (n1 != 1 && n2 != 1)
     648                 :            :     return false;
     649                 :            : 
     650                 :            :   /* Check if the edge corresponding to the unique arg is critical.  */
     651                 :        463 :   e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
     652                 :        463 :   if (EDGE_COUNT (e->src->succs) > 1)
     653                 :          0 :     return false;
     654                 :            : 
     655                 :            :   return true;
     656                 :            : }
     657                 :            : 
     658                 :            : /* Return true when PHI is if-convertible.  PHI is part of loop LOOP
     659                 :            :    and it belongs to basic block BB.  Note at this point, it is sure
     660                 :            :    that PHI is if-convertible.  This function updates global variable
     661                 :            :    ANY_COMPLICATED_PHI if PHI is complicated.  */
     662                 :            : 
     663                 :            : static bool
     664                 :      15475 : if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi)
     665                 :            : {
     666                 :      15475 :   if (dump_file && (dump_flags & TDF_DETAILS))
     667                 :            :     {
     668                 :         61 :       fprintf (dump_file, "-------------------------\n");
     669                 :         61 :       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
     670                 :            :     }
     671                 :            : 
     672                 :      15475 :   if (bb != loop->header
     673                 :       5300 :       && gimple_phi_num_args (phi) > 2
     674                 :      16113 :       && !phi_convertible_by_degenerating_args (phi))
     675                 :        175 :     any_complicated_phi = true;
     676                 :            : 
     677                 :      15475 :   return true;
     678                 :            : }
     679                 :            : 
     680                 :            : /* Records the status of a data reference.  This struct is attached to
     681                 :            :    each DR->aux field.  */
     682                 :            : 
     683                 :            : struct ifc_dr {
     684                 :            :   bool rw_unconditionally;
     685                 :            :   bool w_unconditionally;
     686                 :            :   bool written_at_least_once;
     687                 :            : 
     688                 :            :   tree rw_predicate;
     689                 :            :   tree w_predicate;
     690                 :            :   tree base_w_predicate;
     691                 :            : };
     692                 :            : 
     693                 :            : #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
     694                 :            : #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
     695                 :            : #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
     696                 :            : #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
     697                 :            : 
     698                 :            : /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
     699                 :            :    HASH tables.  While storing them in HASH table, it checks if the
     700                 :            :    reference is unconditionally read or written and stores that as a flag
     701                 :            :    information.  For base reference it checks if it is written atlest once
     702                 :            :    unconditionally and stores it as flag information along with DR.
     703                 :            :    In other words for every data reference A in STMT there exist other
     704                 :            :    accesses to a data reference with the same base with predicates that
     705                 :            :    add up (OR-up) to the true predicate: this ensures that the data
     706                 :            :    reference A is touched (read or written) on every iteration of the
     707                 :            :    if-converted loop.  */
     708                 :            : static void
     709                 :      14652 : hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
     710                 :            : {
     711                 :            : 
     712                 :      14652 :   data_reference_p *master_dr, *base_master_dr;
     713                 :      14652 :   tree base_ref = DR_BASE_OBJECT (a);
     714                 :      14652 :   innermost_loop_behavior *innermost = &DR_INNERMOST (a);
     715                 :      14652 :   tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
     716                 :      14652 :   bool exist1, exist2;
     717                 :            : 
     718                 :      14652 :   master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
     719                 :      14652 :   if (!exist1)
     720                 :      12944 :     *master_dr = a;
     721                 :            : 
     722                 :      14652 :   if (DR_IS_WRITE (a))
     723                 :            :     {
     724                 :       3879 :       IFC_DR (*master_dr)->w_predicate
     725                 :       7758 :         = fold_or_predicates (UNKNOWN_LOCATION, ca,
     726                 :       3879 :                               IFC_DR (*master_dr)->w_predicate);
     727                 :       3879 :       if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
     728                 :       2129 :         DR_W_UNCONDITIONALLY (*master_dr) = true;
     729                 :            :     }
     730                 :      14652 :   IFC_DR (*master_dr)->rw_predicate
     731                 :      29304 :     = fold_or_predicates (UNKNOWN_LOCATION, ca,
     732                 :      14652 :                           IFC_DR (*master_dr)->rw_predicate);
     733                 :      14652 :   if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
     734                 :      10343 :     DR_RW_UNCONDITIONALLY (*master_dr) = true;
     735                 :            : 
     736                 :      14652 :   if (DR_IS_WRITE (a))
     737                 :            :     {
     738                 :       3879 :       base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
     739                 :       3879 :       if (!exist2)
     740                 :       2928 :         *base_master_dr = a;
     741                 :       3879 :       IFC_DR (*base_master_dr)->base_w_predicate
     742                 :       7758 :         = fold_or_predicates (UNKNOWN_LOCATION, ca,
     743                 :       3879 :                               IFC_DR (*base_master_dr)->base_w_predicate);
     744                 :       3879 :       if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
     745                 :       2128 :         DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
     746                 :            :     }
     747                 :      14652 : }
     748                 :            : 
     749                 :            : /* Return TRUE if can prove the index IDX of an array reference REF is
     750                 :            :    within array bound.  Return false otherwise.  */
     751                 :            : 
     752                 :            : static bool
     753                 :       2403 : idx_within_array_bound (tree ref, tree *idx, void *dta)
     754                 :            : {
     755                 :       2403 :   wi::overflow_type overflow;
     756                 :       2403 :   widest_int niter, valid_niter, delta, wi_step;
     757                 :       2403 :   tree ev, init, step;
     758                 :       2403 :   tree low, high;
     759                 :       2403 :   class loop *loop = (class loop*) dta;
     760                 :            : 
     761                 :            :   /* Only support within-bound access for array references.  */
     762                 :       2403 :   if (TREE_CODE (ref) != ARRAY_REF)
     763                 :            :     return false;
     764                 :            : 
     765                 :            :   /* For arrays at the end of the structure, we are not guaranteed that they
     766                 :            :      do not really extend over their declared size.  However, for arrays of
     767                 :            :      size greater than one, this is unlikely to be intended.  */
     768                 :       1677 :   if (array_at_struct_end_p (ref))
     769                 :            :     return false;
     770                 :            : 
     771                 :       1249 :   ev = analyze_scalar_evolution (loop, *idx);
     772                 :       1249 :   ev = instantiate_parameters (loop, ev);
     773                 :       1249 :   init = initial_condition (ev);
     774                 :       1249 :   step = evolution_part_in_loop_num (ev, loop->num);
     775                 :            : 
     776                 :       1249 :   if (!init || TREE_CODE (init) != INTEGER_CST
     777                 :        836 :       || (step && TREE_CODE (step) != INTEGER_CST))
     778                 :            :     return false;
     779                 :            : 
     780                 :        836 :   low = array_ref_low_bound (ref);
     781                 :        836 :   high = array_ref_up_bound (ref);
     782                 :            : 
     783                 :            :   /* The case of nonconstant bounds could be handled, but it would be
     784                 :            :      complicated.  */
     785                 :        836 :   if (TREE_CODE (low) != INTEGER_CST
     786                 :        836 :       || !high || TREE_CODE (high) != INTEGER_CST)
     787                 :            :     return false;
     788                 :            : 
     789                 :            :   /* Check if the intial idx is within bound.  */
     790                 :        836 :   if (wi::to_widest (init) < wi::to_widest (low)
     791                 :       1672 :       || wi::to_widest (init) > wi::to_widest (high))
     792                 :          0 :     return false;
     793                 :            : 
     794                 :            :   /* The idx is always within bound.  */
     795                 :        836 :   if (!step || integer_zerop (step))
     796                 :          3 :     return true;
     797                 :            : 
     798                 :        833 :   if (!max_loop_iterations (loop, &niter))
     799                 :            :     return false;
     800                 :            : 
     801                 :        833 :   if (wi::to_widest (step) < 0)
     802                 :            :     {
     803                 :          8 :       delta = wi::to_widest (init) - wi::to_widest (low);
     804                 :          8 :       wi_step = -wi::to_widest (step);
     805                 :            :     }
     806                 :            :   else
     807                 :            :     {
     808                 :        825 :       delta = wi::to_widest (high) - wi::to_widest (init);
     809                 :        825 :       wi_step = wi::to_widest (step);
     810                 :            :     }
     811                 :            : 
     812                 :        833 :   valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
     813                 :            :   /* The iteration space of idx is within array bound.  */
     814                 :       1666 :   if (!overflow && niter <= valid_niter)
     815                 :        824 :     return true;
     816                 :            : 
     817                 :            :   return false;
     818                 :            : }
     819                 :            : 
     820                 :            : /* Return TRUE if ref is a within bound array reference.  */
     821                 :            : 
     822                 :            : static bool
     823                 :       2419 : ref_within_array_bound (gimple *stmt, tree ref)
     824                 :            : {
     825                 :       2419 :   class loop *loop = loop_containing_stmt (stmt);
     826                 :            : 
     827                 :       2419 :   gcc_assert (loop != NULL);
     828                 :       2419 :   return for_each_index (&ref, idx_within_array_bound, loop);
     829                 :            : }
     830                 :            : 
     831                 :            : 
     832                 :            : /* Given a memory reference expression T, return TRUE if base object
     833                 :            :    it refers to is writable.  The base object of a memory reference
     834                 :            :    is the main object being referenced, which is returned by function
     835                 :            :    get_base_address.  */
     836                 :            : 
     837                 :            : static bool
     838                 :        345 : base_object_writable (tree ref)
     839                 :            : {
     840                 :        345 :   tree base_tree = get_base_address (ref);
     841                 :            : 
     842                 :        345 :   return (base_tree
     843                 :        345 :           && DECL_P (base_tree)
     844                 :        276 :           && decl_binds_to_current_def_p (base_tree)
     845                 :        621 :           && !TREE_READONLY (base_tree));
     846                 :            : }
     847                 :            : 
     848                 :            : /* Return true when the memory references of STMT won't trap in the
     849                 :            :    if-converted code.  There are two things that we have to check for:
     850                 :            : 
     851                 :            :    - writes to memory occur to writable memory: if-conversion of
     852                 :            :    memory writes transforms the conditional memory writes into
     853                 :            :    unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
     854                 :            :    into "A[i] = cond ? foo : A[i]", and as the write to memory may not
     855                 :            :    be executed at all in the original code, it may be a readonly
     856                 :            :    memory.  To check that A is not const-qualified, we check that
     857                 :            :    there exists at least an unconditional write to A in the current
     858                 :            :    function.
     859                 :            : 
     860                 :            :    - reads or writes to memory are valid memory accesses for every
     861                 :            :    iteration.  To check that the memory accesses are correctly formed
     862                 :            :    and that we are allowed to read and write in these locations, we
     863                 :            :    check that the memory accesses to be if-converted occur at every
     864                 :            :    iteration unconditionally.
     865                 :            : 
     866                 :            :    Returns true for the memory reference in STMT, same memory reference
     867                 :            :    is read or written unconditionally atleast once and the base memory
     868                 :            :    reference is written unconditionally once.  This is to check reference
     869                 :            :    will not write fault.  Also retuns true if the memory reference is
     870                 :            :    unconditionally read once then we are conditionally writing to memory
     871                 :            :    which is defined as read and write and is bound to the definition
     872                 :            :    we are seeing.  */
     873                 :            : static bool
     874                 :       2906 : ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
     875                 :            : {
     876                 :            :   /* If DR didn't see a reference here we can't use it to tell
     877                 :            :      whether the ref traps or not.  */
     878                 :       2906 :   if (gimple_uid (stmt) == 0)
     879                 :            :     return false;
     880                 :            : 
     881                 :       2906 :   data_reference_p *master_dr, *base_master_dr;
     882                 :       2906 :   data_reference_p a = drs[gimple_uid (stmt) - 1];
     883                 :            : 
     884                 :       2906 :   tree base = DR_BASE_OBJECT (a);
     885                 :       2906 :   innermost_loop_behavior *innermost = &DR_INNERMOST (a);
     886                 :            : 
     887                 :       2906 :   gcc_assert (DR_STMT (a) == stmt);
     888                 :       2906 :   gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
     889                 :            :               || DR_INIT (a) || DR_STEP (a));
     890                 :            : 
     891                 :       2906 :   master_dr = innermost_DR_map->get (innermost);
     892                 :       2906 :   gcc_assert (master_dr != NULL);
     893                 :            : 
     894                 :       2906 :   base_master_dr = baseref_DR_map->get (base);
     895                 :            : 
     896                 :            :   /* If a is unconditionally written to it doesn't trap.  */
     897                 :       2906 :   if (DR_W_UNCONDITIONALLY (*master_dr))
     898                 :            :     return true;
     899                 :            : 
     900                 :            :   /* If a is unconditionally accessed then ...
     901                 :            : 
     902                 :            :      Even a is conditional access, we can treat it as an unconditional
     903                 :            :      one if it's an array reference and all its index are within array
     904                 :            :      bound.  */
     905                 :       2660 :   if (DR_RW_UNCONDITIONALLY (*master_dr)
     906                 :       2660 :       || ref_within_array_bound (stmt, DR_REF (a)))
     907                 :            :     {
     908                 :            :       /* an unconditional read won't trap.  */
     909                 :       1084 :       if (DR_IS_READ (a))
     910                 :            :         return true;
     911                 :            : 
     912                 :            :       /* an unconditionaly write won't trap if the base is written
     913                 :            :          to unconditionally.  */
     914                 :        346 :       if (base_master_dr
     915                 :        346 :           && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
     916                 :          1 :         return flag_store_data_races;
     917                 :            :       /* or the base is known to be not readonly.  */
     918                 :        345 :       else if (base_object_writable (DR_REF (a)))
     919                 :        276 :         return flag_store_data_races;
     920                 :            :     }
     921                 :            : 
     922                 :            :   return false;
     923                 :            : }
     924                 :            : 
     925                 :            : /* Return true if STMT could be converted into a masked load or store
     926                 :            :    (conditional load or store based on a mask computed from bb predicate).  */
     927                 :            : 
     928                 :            : static bool
     929                 :       1826 : ifcvt_can_use_mask_load_store (gimple *stmt)
     930                 :            : {
     931                 :            :   /* Check whether this is a load or store.  */
     932                 :       1826 :   tree lhs = gimple_assign_lhs (stmt);
     933                 :       1826 :   bool is_load;
     934                 :       1826 :   tree ref;
     935                 :       1826 :   if (gimple_store_p (stmt))
     936                 :            :     {
     937                 :        525 :       if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
     938                 :            :         return false;
     939                 :            :       is_load = false;
     940                 :            :       ref = lhs;
     941                 :            :     }
     942                 :       1301 :   else if (gimple_assign_load_p (stmt))
     943                 :            :     {
     944                 :       1301 :       is_load = true;
     945                 :       1301 :       ref = gimple_assign_rhs1 (stmt);
     946                 :            :     }
     947                 :            :   else
     948                 :            :     return false;
     949                 :            : 
     950                 :       1826 :   if (may_be_nonaddressable_p (ref))
     951                 :            :     return false;
     952                 :            : 
     953                 :            :   /* Mask should be integer mode of the same size as the load/store
     954                 :            :      mode.  */
     955                 :       1826 :   machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
     956                 :       1826 :   if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode))
     957                 :          0 :     return false;
     958                 :            : 
     959                 :       1826 :   if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
     960                 :        752 :     return true;
     961                 :            : 
     962                 :            :   return false;
     963                 :            : }
     964                 :            : 
     965                 :            : /* Return true if STMT could be converted from an operation that is
     966                 :            :    unconditional to one that is conditional on a bb predicate mask.  */
     967                 :            : 
     968                 :            : static bool
     969                 :       2320 : ifcvt_can_predicate (gimple *stmt)
     970                 :            : {
     971                 :       2320 :   basic_block bb = gimple_bb (stmt);
     972                 :            : 
     973                 :        400 :   if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
     974                 :       2320 :       || bb->loop_father->dont_vectorize
     975                 :       4640 :       || gimple_has_volatile_ops (stmt))
     976                 :            :     return false;
     977                 :            : 
     978                 :       2320 :   if (gimple_assign_single_p (stmt))
     979                 :       1826 :     return ifcvt_can_use_mask_load_store (stmt);
     980                 :            : 
     981                 :        494 :   tree_code code = gimple_assign_rhs_code (stmt);
     982                 :        494 :   tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
     983                 :        494 :   tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
     984                 :        494 :   if (!types_compatible_p (lhs_type, rhs_type))
     985                 :            :     return false;
     986                 :        284 :   internal_fn cond_fn = get_conditional_internal_fn (code);
     987                 :        284 :   return (cond_fn != IFN_LAST
     988                 :        284 :           && vectorized_internal_fn_supported_p (cond_fn, lhs_type));
     989                 :            : }
     990                 :            : 
     991                 :            : /* Return true when STMT is if-convertible.
     992                 :            : 
     993                 :            :    GIMPLE_ASSIGN statement is not if-convertible if,
     994                 :            :    - it is not movable,
     995                 :            :    - it could trap,
     996                 :            :    - LHS is not var decl.  */
     997                 :            : 
     998                 :            : static bool
     999                 :       9572 : if_convertible_gimple_assign_stmt_p (gimple *stmt,
    1000                 :            :                                      vec<data_reference_p> refs)
    1001                 :            : {
    1002                 :       9572 :   tree lhs = gimple_assign_lhs (stmt);
    1003                 :            : 
    1004                 :       9572 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1005                 :            :     {
    1006                 :         30 :       fprintf (dump_file, "-------------------------\n");
    1007                 :         30 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1008                 :            :     }
    1009                 :            : 
    1010                 :       9572 :   if (!is_gimple_reg_type (TREE_TYPE (lhs)))
    1011                 :            :     return false;
    1012                 :            : 
    1013                 :            :   /* Some of these constrains might be too conservative.  */
    1014                 :       9570 :   if (stmt_ends_bb_p (stmt)
    1015                 :       9570 :       || gimple_has_volatile_ops (stmt)
    1016                 :       9557 :       || (TREE_CODE (lhs) == SSA_NAME
    1017                 :       8822 :           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
    1018                 :      19127 :       || gimple_has_side_effects (stmt))
    1019                 :            :     {
    1020                 :         13 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1021                 :          0 :         fprintf (dump_file, "stmt not suitable for ifcvt\n");
    1022                 :         13 :       return false;
    1023                 :            :     }
    1024                 :            : 
    1025                 :            :   /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
    1026                 :            :      in between if_convertible_loop_p and combine_blocks
    1027                 :            :      we can perform loop versioning.  */
    1028                 :       9557 :   gimple_set_plf (stmt, GF_PLF_2, false);
    1029                 :            : 
    1030                 :       9557 :   if ((! gimple_vuse (stmt)
    1031                 :       2906 :        || gimple_could_trap_p_1 (stmt, false, false)
    1032                 :       2906 :        || ! ifcvt_memrefs_wont_trap (stmt, refs))
    1033                 :      11468 :       && gimple_could_trap_p (stmt))
    1034                 :            :     {
    1035                 :       2320 :       if (ifcvt_can_predicate (stmt))
    1036                 :            :         {
    1037                 :        752 :           gimple_set_plf (stmt, GF_PLF_2, true);
    1038                 :        752 :           need_to_predicate = true;
    1039                 :        752 :           return true;
    1040                 :            :         }
    1041                 :       1568 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1042                 :          0 :         fprintf (dump_file, "tree could trap...\n");
    1043                 :       1568 :       return false;
    1044                 :            :     }
    1045                 :            : 
    1046                 :            :   /* When if-converting stores force versioning, likewise if we
    1047                 :            :      ended up generating store data races.  */
    1048                 :      14474 :   if (gimple_vdef (stmt))
    1049                 :        210 :     need_to_predicate = true;
    1050                 :            : 
    1051                 :            :   return true;
    1052                 :            : }
    1053                 :            : 
    1054                 :            : /* Return true when STMT is if-convertible.
    1055                 :            : 
    1056                 :            :    A statement is if-convertible if:
    1057                 :            :    - it is an if-convertible GIMPLE_ASSIGN,
    1058                 :            :    - it is a GIMPLE_LABEL or a GIMPLE_COND,
    1059                 :            :    - it is builtins call.  */
    1060                 :            : 
    1061                 :            : static bool
    1062                 :      12437 : if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
    1063                 :            : {
    1064                 :      12437 :   switch (gimple_code (stmt))
    1065                 :            :     {
    1066                 :            :     case GIMPLE_LABEL:
    1067                 :            :     case GIMPLE_DEBUG:
    1068                 :            :     case GIMPLE_COND:
    1069                 :            :       return true;
    1070                 :            : 
    1071                 :       9572 :     case GIMPLE_ASSIGN:
    1072                 :       9572 :       return if_convertible_gimple_assign_stmt_p (stmt, refs);
    1073                 :            : 
    1074                 :         47 :     case GIMPLE_CALL:
    1075                 :         47 :       {
    1076                 :         47 :         tree fndecl = gimple_call_fndecl (stmt);
    1077                 :         47 :         if (fndecl)
    1078                 :            :           {
    1079                 :         47 :             int flags = gimple_call_flags (stmt);
    1080                 :         47 :             if ((flags & ECF_CONST)
    1081                 :         47 :                 && !(flags & ECF_LOOPING_CONST_OR_PURE)
    1082                 :            :                 /* We can only vectorize some builtins at the moment,
    1083                 :            :                    so restrict if-conversion to those.  */
    1084                 :         47 :                 && fndecl_built_in_p (fndecl))
    1085                 :         20 :               return true;
    1086                 :            :           }
    1087                 :            :         return false;
    1088                 :            :       }
    1089                 :            : 
    1090                 :          0 :     default:
    1091                 :            :       /* Don't know what to do with 'em so don't do anything.  */
    1092                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1093                 :            :         {
    1094                 :          0 :           fprintf (dump_file, "don't know what to do\n");
    1095                 :          0 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1096                 :            :         }
    1097                 :            :       return false;
    1098                 :            :     }
    1099                 :            : 
    1100                 :            :   return true;
    1101                 :            : }
    1102                 :            : 
    1103                 :            : /* Assumes that BB has more than 1 predecessors.
    1104                 :            :    Returns false if at least one successor is not on critical edge
    1105                 :            :    and true otherwise.  */
    1106                 :            : 
    1107                 :            : static inline bool
    1108                 :       4224 : all_preds_critical_p (basic_block bb)
    1109                 :            : {
    1110                 :       4224 :   edge e;
    1111                 :       4224 :   edge_iterator ei;
    1112                 :            : 
    1113                 :       5584 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1114                 :       5467 :     if (EDGE_COUNT (e->src->succs) == 1)
    1115                 :            :       return false;
    1116                 :            :   return true;
    1117                 :            : }
    1118                 :            : 
    1119                 :            : /* Return true when BB is if-convertible.  This routine does not check
    1120                 :            :    basic block's statements and phis.
    1121                 :            : 
    1122                 :            :    A basic block is not if-convertible if:
    1123                 :            :    - it is non-empty and it is after the exit block (in BFS order),
    1124                 :            :    - it is after the exit block but before the latch,
    1125                 :            :    - its edges are not normal.
    1126                 :            : 
    1127                 :            :    EXIT_BB is the basic block containing the exit of the LOOP.  BB is
    1128                 :            :    inside LOOP.  */
    1129                 :            : 
    1130                 :            : static bool
    1131                 :      28345 : if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb)
    1132                 :            : {
    1133                 :      28345 :   edge e;
    1134                 :      28345 :   edge_iterator ei;
    1135                 :            : 
    1136                 :      28345 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1137                 :         80 :     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
    1138                 :            : 
    1139                 :      28345 :   if (EDGE_COUNT (bb->succs) > 2)
    1140                 :            :     return false;
    1141                 :            : 
    1142                 :      28322 :   if (exit_bb)
    1143                 :            :     {
    1144                 :       4822 :       if (bb != loop->latch)
    1145                 :            :         {
    1146                 :         66 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1147                 :          0 :             fprintf (dump_file, "basic block after exit bb but before latch\n");
    1148                 :         66 :           return false;
    1149                 :            :         }
    1150                 :       4756 :       else if (!empty_block_p (bb))
    1151                 :            :         {
    1152                 :         12 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1153                 :          0 :             fprintf (dump_file, "non empty basic block after exit bb\n");
    1154                 :         12 :           return false;
    1155                 :            :         }
    1156                 :       4744 :       else if (bb == loop->latch
    1157                 :       4744 :                && bb != exit_bb
    1158                 :       9488 :                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
    1159                 :            :           {
    1160                 :          2 :             if (dump_file && (dump_flags & TDF_DETAILS))
    1161                 :          0 :               fprintf (dump_file, "latch is not dominated by exit_block\n");
    1162                 :          2 :             return false;
    1163                 :            :           }
    1164                 :            :     }
    1165                 :            : 
    1166                 :            :   /* Be less adventurous and handle only normal edges.  */
    1167                 :      68761 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1168                 :      40535 :     if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
    1169                 :            :       {
    1170                 :         16 :         if (dump_file && (dump_flags & TDF_DETAILS))
    1171                 :          0 :           fprintf (dump_file, "Difficult to handle edges\n");
    1172                 :         16 :         return false;
    1173                 :            :       }
    1174                 :            : 
    1175                 :            :   return true;
    1176                 :            : }
    1177                 :            : 
    1178                 :            : /* Return true when all predecessor blocks of BB are visited.  The
    1179                 :            :    VISITED bitmap keeps track of the visited blocks.  */
    1180                 :            : 
    1181                 :            : static bool
    1182                 :      33025 : pred_blocks_visited_p (basic_block bb, bitmap *visited)
    1183                 :            : {
    1184                 :      33025 :   edge e;
    1185                 :      33025 :   edge_iterator ei;
    1186                 :      65263 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1187                 :      41448 :     if (!bitmap_bit_p (*visited, e->src->index))
    1188                 :            :       return false;
    1189                 :            : 
    1190                 :            :   return true;
    1191                 :            : }
    1192                 :            : 
    1193                 :            : /* Get body of a LOOP in suitable order for if-conversion.  It is
    1194                 :            :    caller's responsibility to deallocate basic block list.
    1195                 :            :    If-conversion suitable order is, breadth first sort (BFS) order
    1196                 :            :    with an additional constraint: select a block only if all its
    1197                 :            :    predecessors are already selected.  */
    1198                 :            : 
    1199                 :            : static basic_block *
    1200                 :       4863 : get_loop_body_in_if_conv_order (const class loop *loop)
    1201                 :            : {
    1202                 :       4863 :   basic_block *blocks, *blocks_in_bfs_order;
    1203                 :       4863 :   basic_block bb;
    1204                 :       4863 :   bitmap visited;
    1205                 :       4863 :   unsigned int index = 0;
    1206                 :       4863 :   unsigned int visited_count = 0;
    1207                 :            : 
    1208                 :       4863 :   gcc_assert (loop->num_nodes);
    1209                 :       4863 :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
    1210                 :            : 
    1211                 :       4863 :   blocks = XCNEWVEC (basic_block, loop->num_nodes);
    1212                 :       4863 :   visited = BITMAP_ALLOC (NULL);
    1213                 :            : 
    1214                 :       4863 :   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
    1215                 :            : 
    1216                 :       4863 :   index = 0;
    1217                 :      43807 :   while (index < loop->num_nodes)
    1218                 :            :     {
    1219                 :      38946 :       bb = blocks_in_bfs_order [index];
    1220                 :            : 
    1221                 :      38946 :       if (bb->flags & BB_IRREDUCIBLE_LOOP)
    1222                 :            :         {
    1223                 :          2 :           free (blocks_in_bfs_order);
    1224                 :          2 :           BITMAP_FREE (visited);
    1225                 :          2 :           free (blocks);
    1226                 :          2 :           return NULL;
    1227                 :            :         }
    1228                 :            : 
    1229                 :      38944 :       if (!bitmap_bit_p (visited, bb->index))
    1230                 :            :         {
    1231                 :      33025 :           if (pred_blocks_visited_p (bb, &visited)
    1232                 :      33025 :               || bb == loop->header)
    1233                 :            :             {
    1234                 :            :               /* This block is now visited.  */
    1235                 :      28678 :               bitmap_set_bit (visited, bb->index);
    1236                 :      28678 :               blocks[visited_count++] = bb;
    1237                 :            :             }
    1238                 :            :         }
    1239                 :            : 
    1240                 :      38944 :       index++;
    1241                 :            : 
    1242                 :      38944 :       if (index == loop->num_nodes
    1243                 :       6001 :           && visited_count != loop->num_nodes)
    1244                 :            :         /* Not done yet.  */
    1245                 :       1140 :         index = 0;
    1246                 :            :     }
    1247                 :       4861 :   free (blocks_in_bfs_order);
    1248                 :       4861 :   BITMAP_FREE (visited);
    1249                 :       4861 :   return blocks;
    1250                 :            : }
    1251                 :            : 
    1252                 :            : /* Returns true when the analysis of the predicates for all the basic
    1253                 :            :    blocks in LOOP succeeded.
    1254                 :            : 
    1255                 :            :    predicate_bbs first allocates the predicates of the basic blocks.
    1256                 :            :    These fields are then initialized with the tree expressions
    1257                 :            :    representing the predicates under which a basic block is executed
    1258                 :            :    in the LOOP.  As the loop->header is executed at each iteration, it
    1259                 :            :    has the "true" predicate.  Other statements executed under a
    1260                 :            :    condition are predicated with that condition, for example
    1261                 :            : 
    1262                 :            :    | if (x)
    1263                 :            :    |   S1;
    1264                 :            :    | else
    1265                 :            :    |   S2;
    1266                 :            : 
    1267                 :            :    S1 will be predicated with "x", and
    1268                 :            :    S2 will be predicated with "!x".  */
    1269                 :            : 
    1270                 :            : static void
    1271                 :       4742 : predicate_bbs (loop_p loop)
    1272                 :            : {
    1273                 :       4742 :   unsigned int i;
    1274                 :            : 
    1275                 :      32479 :   for (i = 0; i < loop->num_nodes; i++)
    1276                 :      27737 :     init_bb_predicate (ifc_bbs[i]);
    1277                 :            : 
    1278                 :      32479 :   for (i = 0; i < loop->num_nodes; i++)
    1279                 :            :     {
    1280                 :      27737 :       basic_block bb = ifc_bbs[i];
    1281                 :      27737 :       tree cond;
    1282                 :      27737 :       gimple *stmt;
    1283                 :            : 
    1284                 :            :       /* The loop latch and loop exit block are always executed and
    1285                 :            :          have no extra conditions to be processed: skip them.  */
    1286                 :      37221 :       if (bb == loop->latch
    1287                 :      27737 :           || bb_with_exit_edge_p (loop, bb))
    1288                 :            :         {
    1289                 :       9484 :           reset_bb_predicate (bb);
    1290                 :       9484 :           continue;
    1291                 :            :         }
    1292                 :            : 
    1293                 :      18253 :       cond = bb_predicate (bb);
    1294                 :      18253 :       stmt = last_stmt (bb);
    1295                 :      18253 :       if (stmt && gimple_code (stmt) == GIMPLE_COND)
    1296                 :            :         {
    1297                 :       7276 :           tree c2;
    1298                 :       7276 :           edge true_edge, false_edge;
    1299                 :       7276 :           location_t loc = gimple_location (stmt);
    1300                 :       7276 :           tree c = build2_loc (loc, gimple_cond_code (stmt),
    1301                 :            :                                     boolean_type_node,
    1302                 :            :                                     gimple_cond_lhs (stmt),
    1303                 :            :                                     gimple_cond_rhs (stmt));
    1304                 :            : 
    1305                 :            :           /* Add new condition into destination's predicate list.  */
    1306                 :       7276 :           extract_true_false_edges_from_block (gimple_bb (stmt),
    1307                 :            :                                                &true_edge, &false_edge);
    1308                 :            : 
    1309                 :            :           /* If C is true, then TRUE_EDGE is taken.  */
    1310                 :       7276 :           add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
    1311                 :            :                                      unshare_expr (c));
    1312                 :            : 
    1313                 :            :           /* If C is false, then FALSE_EDGE is taken.  */
    1314                 :       7276 :           c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
    1315                 :            :                            unshare_expr (c));
    1316                 :       7276 :           add_to_dst_predicate_list (loop, false_edge,
    1317                 :            :                                      unshare_expr (cond), c2);
    1318                 :            : 
    1319                 :       7276 :           cond = NULL_TREE;
    1320                 :            :         }
    1321                 :            : 
    1322                 :            :       /* If current bb has only one successor, then consider it as an
    1323                 :            :          unconditional goto.  */
    1324                 :      18253 :       if (single_succ_p (bb))
    1325                 :            :         {
    1326                 :      10977 :           basic_block bb_n = single_succ (bb);
    1327                 :            : 
    1328                 :            :           /* The successor bb inherits the predicate of its
    1329                 :            :              predecessor.  If there is no predicate in the predecessor
    1330                 :            :              bb, then consider the successor bb as always executed.  */
    1331                 :      10977 :           if (cond == NULL_TREE)
    1332                 :          0 :             cond = boolean_true_node;
    1333                 :            : 
    1334                 :      10977 :           add_to_predicate_list (loop, bb_n, cond);
    1335                 :            :         }
    1336                 :            :     }
    1337                 :            : 
    1338                 :            :   /* The loop header is always executed.  */
    1339                 :       4742 :   reset_bb_predicate (loop->header);
    1340                 :       4742 :   gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
    1341                 :            :               && bb_predicate_gimplified_stmts (loop->latch) == NULL);
    1342                 :       4742 : }
    1343                 :            : 
    1344                 :            : /* Build region by adding loop pre-header and post-header blocks.  */
    1345                 :            : 
    1346                 :            : static vec<basic_block>
    1347                 :       4742 : build_region (class loop *loop)
    1348                 :            : {
    1349                 :       4742 :   vec<basic_block> region = vNULL;
    1350                 :       4742 :   basic_block exit_bb = NULL;
    1351                 :            : 
    1352                 :       4742 :   gcc_assert (ifc_bbs);
    1353                 :            :   /* The first element is loop pre-header.  */
    1354                 :       4742 :   region.safe_push (loop_preheader_edge (loop)->src);
    1355                 :            : 
    1356                 :      32479 :   for (unsigned int i = 0; i < loop->num_nodes; i++)
    1357                 :            :     {
    1358                 :      27737 :       basic_block bb = ifc_bbs[i];
    1359                 :      27737 :       region.safe_push (bb);
    1360                 :            :       /* Find loop postheader.  */
    1361                 :      27737 :       edge e;
    1362                 :      27737 :       edge_iterator ei;
    1363                 :      61164 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1364                 :      38169 :         if (loop_exit_edge_p (loop, e))
    1365                 :            :           {
    1366                 :       4742 :               exit_bb = e->dest;
    1367                 :       4742 :               break;
    1368                 :            :           }
    1369                 :            :     }
    1370                 :            :   /* The last element is loop post-header.  */
    1371                 :       4742 :   gcc_assert (exit_bb);
    1372                 :       4742 :   region.safe_push (exit_bb);
    1373                 :       4742 :   return region;
    1374                 :            : }
    1375                 :            : 
    1376                 :            : /* Return true when LOOP is if-convertible.  This is a helper function
    1377                 :            :    for if_convertible_loop_p.  REFS and DDRS are initialized and freed
    1378                 :            :    in if_convertible_loop_p.  */
    1379                 :            : 
    1380                 :            : static bool
    1381                 :       6988 : if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs)
    1382                 :            : {
    1383                 :       6988 :   unsigned int i;
    1384                 :       6988 :   basic_block exit_bb = NULL;
    1385                 :       6988 :   vec<basic_block> region;
    1386                 :            : 
    1387                 :       6988 :   if (find_data_references_in_loop (loop, refs) == chrec_dont_know)
    1388                 :            :     return false;
    1389                 :            : 
    1390                 :       4863 :   calculate_dominance_info (CDI_DOMINATORS);
    1391                 :            : 
    1392                 :            :   /* Allow statements that can be handled during if-conversion.  */
    1393                 :       4863 :   ifc_bbs = get_loop_body_in_if_conv_order (loop);
    1394                 :       4863 :   if (!ifc_bbs)
    1395                 :            :     {
    1396                 :          2 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1397                 :          0 :         fprintf (dump_file, "Irreducible loop\n");
    1398                 :          2 :       return false;
    1399                 :            :     }
    1400                 :            : 
    1401                 :      33087 :   for (i = 0; i < loop->num_nodes; i++)
    1402                 :            :     {
    1403                 :      28345 :       basic_block bb = ifc_bbs[i];
    1404                 :            : 
    1405                 :      28345 :       if (!if_convertible_bb_p (loop, bb, exit_bb))
    1406                 :            :         return false;
    1407                 :            : 
    1408                 :      28226 :       if (bb_with_exit_edge_p (loop, bb))
    1409                 :       4822 :         exit_bb = bb;
    1410                 :            :     }
    1411                 :            : 
    1412                 :      32479 :   for (i = 0; i < loop->num_nodes; i++)
    1413                 :            :     {
    1414                 :      27737 :       basic_block bb = ifc_bbs[i];
    1415                 :      27737 :       gimple_stmt_iterator gsi;
    1416                 :            : 
    1417                 :     129067 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1418                 :      73593 :         switch (gimple_code (gsi_stmt (gsi)))
    1419                 :            :           {
    1420                 :      73593 :           case GIMPLE_LABEL:
    1421                 :      73593 :           case GIMPLE_ASSIGN:
    1422                 :      73593 :           case GIMPLE_CALL:
    1423                 :      73593 :           case GIMPLE_DEBUG:
    1424                 :      73593 :           case GIMPLE_COND:
    1425                 :      73593 :             gimple_set_uid (gsi_stmt (gsi), 0);
    1426                 :      73593 :             break;
    1427                 :            :           default:
    1428                 :       6988 :             return false;
    1429                 :            :           }
    1430                 :            :     }
    1431                 :            : 
    1432                 :       4742 :   data_reference_p dr;
    1433                 :            : 
    1434                 :       4742 :   innermost_DR_map
    1435                 :       4742 :           = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
    1436                 :       4742 :   baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
    1437                 :            : 
    1438                 :            :   /* Compute post-dominator tree locally.  */
    1439                 :       4742 :   region = build_region (loop);
    1440                 :       4742 :   calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);
    1441                 :            : 
    1442                 :       4742 :   predicate_bbs (loop);
    1443                 :            : 
    1444                 :            :   /* Free post-dominator tree since it is not used after predication.  */
    1445                 :       4742 :   free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
    1446                 :       4742 :   region.release ();
    1447                 :            : 
    1448                 :      19394 :   for (i = 0; refs->iterate (i, &dr); i++)
    1449                 :            :     {
    1450                 :      14652 :       tree ref = DR_REF (dr);
    1451                 :            : 
    1452                 :      14652 :       dr->aux = XNEW (struct ifc_dr);
    1453                 :      14652 :       DR_BASE_W_UNCONDITIONALLY (dr) = false;
    1454                 :      14652 :       DR_RW_UNCONDITIONALLY (dr) = false;
    1455                 :      14652 :       DR_W_UNCONDITIONALLY (dr) = false;
    1456                 :      14652 :       IFC_DR (dr)->rw_predicate = boolean_false_node;
    1457                 :      14652 :       IFC_DR (dr)->w_predicate = boolean_false_node;
    1458                 :      14652 :       IFC_DR (dr)->base_w_predicate = boolean_false_node;
    1459                 :      14652 :       if (gimple_uid (DR_STMT (dr)) == 0)
    1460                 :      14648 :         gimple_set_uid (DR_STMT (dr), i + 1);
    1461                 :            : 
    1462                 :            :       /* If DR doesn't have innermost loop behavior or it's a compound
    1463                 :            :          memory reference, we synthesize its innermost loop behavior
    1464                 :            :          for hashing.  */
    1465                 :      14652 :       if (TREE_CODE (ref) == COMPONENT_REF
    1466                 :      13835 :           || TREE_CODE (ref) == IMAGPART_EXPR
    1467                 :      13781 :           || TREE_CODE (ref) == REALPART_EXPR
    1468                 :      13727 :           || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
    1469                 :       1953 :                || DR_INIT (dr) || DR_STEP (dr)))
    1470                 :            :         {
    1471                 :       3981 :           while (TREE_CODE (ref) == COMPONENT_REF
    1472                 :       2986 :                  || TREE_CODE (ref) == IMAGPART_EXPR
    1473                 :       6913 :                  || TREE_CODE (ref) == REALPART_EXPR)
    1474                 :       1103 :             ref = TREE_OPERAND (ref, 0);
    1475                 :            : 
    1476                 :       2878 :           memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr)));
    1477                 :       2878 :           DR_BASE_ADDRESS (dr) = ref;
    1478                 :            :         }
    1479                 :      14652 :       hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
    1480                 :            :     }
    1481                 :            : 
    1482                 :      24752 :   for (i = 0; i < loop->num_nodes; i++)
    1483                 :            :     {
    1484                 :      21620 :       basic_block bb = ifc_bbs[i];
    1485                 :      21620 :       gimple_stmt_iterator itr;
    1486                 :            : 
    1487                 :            :       /* Check the if-convertibility of statements in predicated BBs.  */
    1488                 :      21620 :       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    1489                 :      30425 :         for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
    1490                 :      12437 :           if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
    1491                 :       6988 :             return false;
    1492                 :            :     }
    1493                 :            : 
    1494                 :            :   /* Checking PHIs needs to be done after stmts, as the fact whether there
    1495                 :            :      are any masked loads or stores affects the tests.  */
    1496                 :      21249 :   for (i = 0; i < loop->num_nodes; i++)
    1497                 :            :     {
    1498                 :      18117 :       basic_block bb = ifc_bbs[i];
    1499                 :      18117 :       gphi_iterator itr;
    1500                 :            : 
    1501                 :      33592 :       for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
    1502                 :      15475 :         if (!if_convertible_phi_p (loop, bb, itr.phi ()))
    1503                 :          0 :           return false;
    1504                 :            :     }
    1505                 :            : 
    1506                 :       3132 :   if (dump_file)
    1507                 :         25 :     fprintf (dump_file, "Applying if-conversion\n");
    1508                 :            : 
    1509                 :            :   return true;
    1510                 :            : }
    1511                 :            : 
    1512                 :            : /* Return true when LOOP is if-convertible.
    1513                 :            :    LOOP is if-convertible if:
    1514                 :            :    - it is innermost,
    1515                 :            :    - it has two or more basic blocks,
    1516                 :            :    - it has only one exit,
    1517                 :            :    - loop header is not the exit edge,
    1518                 :            :    - if its basic blocks and phi nodes are if convertible.  */
    1519                 :            : 
    1520                 :            : static bool
    1521                 :       7003 : if_convertible_loop_p (class loop *loop)
    1522                 :            : {
    1523                 :       7003 :   edge e;
    1524                 :       7003 :   edge_iterator ei;
    1525                 :       7003 :   bool res = false;
    1526                 :       7003 :   vec<data_reference_p> refs;
    1527                 :            : 
    1528                 :            :   /* Handle only innermost loop.  */
    1529                 :       7003 :   if (!loop || loop->inner)
    1530                 :            :     {
    1531                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1532                 :          0 :         fprintf (dump_file, "not innermost loop\n");
    1533                 :          0 :       return false;
    1534                 :            :     }
    1535                 :            : 
    1536                 :            :   /* If only one block, no need for if-conversion.  */
    1537                 :       7003 :   if (loop->num_nodes <= 2)
    1538                 :            :     {
    1539                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1540                 :          0 :         fprintf (dump_file, "less than 2 basic blocks\n");
    1541                 :          0 :       return false;
    1542                 :            :     }
    1543                 :            : 
    1544                 :            :   /* More than one loop exit is too much to handle.  */
    1545                 :       7003 :   if (!single_exit (loop))
    1546                 :            :     {
    1547                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1548                 :          0 :         fprintf (dump_file, "multiple exits\n");
    1549                 :          0 :       return false;
    1550                 :            :     }
    1551                 :            : 
    1552                 :            :   /* If one of the loop header's edge is an exit edge then do not
    1553                 :            :      apply if-conversion.  */
    1554                 :      21018 :   FOR_EACH_EDGE (e, ei, loop->header->succs)
    1555                 :      14030 :     if (loop_exit_edge_p (loop, e))
    1556                 :            :       return false;
    1557                 :            : 
    1558                 :       6988 :   refs.create (5);
    1559                 :       6988 :   res = if_convertible_loop_p_1 (loop, &refs);
    1560                 :            : 
    1561                 :       6988 :   data_reference_p dr;
    1562                 :       6988 :   unsigned int i;
    1563                 :      29229 :   for (i = 0; refs.iterate (i, &dr); i++)
    1564                 :      22241 :     free (dr->aux);
    1565                 :            : 
    1566                 :       6988 :   free_data_refs (refs);
    1567                 :            : 
    1568                 :      11730 :   delete innermost_DR_map;
    1569                 :       6988 :   innermost_DR_map = NULL;
    1570                 :            : 
    1571                 :      11730 :   delete baseref_DR_map;
    1572                 :       6988 :   baseref_DR_map = NULL;
    1573                 :            : 
    1574                 :       6988 :   return res;
    1575                 :            : }
    1576                 :            : 
    1577                 :            : /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
    1578                 :            :    which is in predicated basic block.
    1579                 :            :    In fact, the following PHI pattern is searching:
    1580                 :            :       loop-header:
    1581                 :            :         reduc_1 = PHI <..., reduc_2>
    1582                 :            :       ...
    1583                 :            :         if (...)
    1584                 :            :           reduc_3 = ...
    1585                 :            :         reduc_2 = PHI <reduc_1, reduc_3>
    1586                 :            : 
    1587                 :            :    ARG_0 and ARG_1 are correspondent PHI arguments.
    1588                 :            :    REDUC, OP0 and OP1 contain reduction stmt and its operands.
    1589                 :            :    EXTENDED is true if PHI has > 2 arguments.  */
    1590                 :            : 
    1591                 :            : static bool
    1592                 :       4537 : is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
    1593                 :            :                           tree *op0, tree *op1, bool extended)
    1594                 :            : {
    1595                 :       4537 :   tree lhs, r_op1, r_op2;
    1596                 :       4537 :   gimple *stmt;
    1597                 :       4537 :   gimple *header_phi = NULL;
    1598                 :       4537 :   enum tree_code reduction_op;
    1599                 :       4537 :   basic_block bb = gimple_bb (phi);
    1600                 :       4537 :   class loop *loop = bb->loop_father;
    1601                 :       4537 :   edge latch_e = loop_latch_edge (loop);
    1602                 :       4537 :   imm_use_iterator imm_iter;
    1603                 :       4537 :   use_operand_p use_p;
    1604                 :       4537 :   edge e;
    1605                 :       4537 :   edge_iterator ei;
    1606                 :       4537 :   bool result = false;
    1607                 :       4537 :   if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
    1608                 :            :     return false;
    1609                 :            : 
    1610                 :       2807 :   if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
    1611                 :            :     {
    1612                 :        618 :       lhs = arg_1;
    1613                 :        618 :       header_phi = SSA_NAME_DEF_STMT (arg_0);
    1614                 :        618 :       stmt = SSA_NAME_DEF_STMT (arg_1);
    1615                 :            :     }
    1616                 :       2189 :   else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
    1617                 :            :     {
    1618                 :        969 :       lhs = arg_0;
    1619                 :        969 :       header_phi = SSA_NAME_DEF_STMT (arg_1);
    1620                 :        969 :       stmt = SSA_NAME_DEF_STMT (arg_0);
    1621                 :            :     }
    1622                 :            :   else
    1623                 :            :     return false;
    1624                 :       1587 :   if (gimple_bb (header_phi) != loop->header)
    1625                 :            :     return false;
    1626                 :            : 
    1627                 :       1583 :   if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
    1628                 :            :     return false;
    1629                 :            : 
    1630                 :       1056 :   if (gimple_code (stmt) != GIMPLE_ASSIGN
    1631                 :       1056 :       || gimple_has_volatile_ops (stmt))
    1632                 :            :     return false;
    1633                 :            : 
    1634                 :        990 :   if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
    1635                 :            :     return false;
    1636                 :            : 
    1637                 :        967 :   if (!is_predicated (gimple_bb (stmt)))
    1638                 :            :     return false;
    1639                 :            : 
    1640                 :            :   /* Check that stmt-block is predecessor of phi-block.  */
    1641                 :        549 :   FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
    1642                 :        513 :     if (e->dest == bb)
    1643                 :            :       {
    1644                 :            :         result = true;
    1645                 :            :         break;
    1646                 :            :       }
    1647                 :        477 :   if (!result)
    1648                 :            :     return false;
    1649                 :            : 
    1650                 :        441 :   if (!has_single_use (lhs))
    1651                 :            :     return false;
    1652                 :            : 
    1653                 :        439 :   reduction_op = gimple_assign_rhs_code (stmt);
    1654                 :        439 :   if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
    1655                 :            :     return false;
    1656                 :        301 :   r_op1 = gimple_assign_rhs1 (stmt);
    1657                 :        301 :   r_op2 = gimple_assign_rhs2 (stmt);
    1658                 :            : 
    1659                 :            :   /* Make R_OP1 to hold reduction variable.  */
    1660                 :        301 :   if (r_op2 == PHI_RESULT (header_phi)
    1661                 :        301 :       && reduction_op == PLUS_EXPR)
    1662                 :        266 :     std::swap (r_op1, r_op2);
    1663                 :        281 :   else if (r_op1 != PHI_RESULT (header_phi))
    1664                 :            :     return false;
    1665                 :            : 
    1666                 :            :   /* Check that R_OP1 is used in reduction stmt or in PHI only.  */
    1667                 :        813 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
    1668                 :            :     {
    1669                 :        555 :       gimple *use_stmt = USE_STMT (use_p);
    1670                 :        555 :       if (is_gimple_debug (use_stmt))
    1671                 :          0 :         continue;
    1672                 :        555 :       if (use_stmt == stmt)
    1673                 :        258 :         continue;
    1674                 :        297 :       if (gimple_code (use_stmt) != GIMPLE_PHI)
    1675                 :            :         return false;
    1676                 :            :     }
    1677                 :            : 
    1678                 :        258 :   *op0 = r_op1; *op1 = r_op2;
    1679                 :        258 :   *reduc = stmt;
    1680                 :        258 :   return true;
    1681                 :            : }
    1682                 :            : 
    1683                 :            : /* Converts conditional scalar reduction into unconditional form, e.g.
    1684                 :            :      bb_4
    1685                 :            :        if (_5 != 0) goto bb_5 else goto bb_6
    1686                 :            :      end_bb_4
    1687                 :            :      bb_5
    1688                 :            :        res_6 = res_13 + 1;
    1689                 :            :      end_bb_5
    1690                 :            :      bb_6
    1691                 :            :        # res_2 = PHI <res_13(4), res_6(5)>
    1692                 :            :      end_bb_6
    1693                 :            : 
    1694                 :            :    will be converted into sequence
    1695                 :            :     _ifc__1 = _5 != 0 ? 1 : 0;
    1696                 :            :     res_2 = res_13 + _ifc__1;
    1697                 :            :   Argument SWAP tells that arguments of conditional expression should be
    1698                 :            :   swapped.
    1699                 :            :   Returns rhs of resulting PHI assignment.  */
    1700                 :            : 
    1701                 :            : static tree
    1702                 :        258 : convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
    1703                 :            :                                tree cond, tree op0, tree op1, bool swap)
    1704                 :            : {
    1705                 :        258 :   gimple_stmt_iterator stmt_it;
    1706                 :        258 :   gimple *new_assign;
    1707                 :        258 :   tree rhs;
    1708                 :        258 :   tree rhs1 = gimple_assign_rhs1 (reduc);
    1709                 :        258 :   tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
    1710                 :        258 :   tree c;
    1711                 :        258 :   tree zero = build_zero_cst (TREE_TYPE (rhs1));
    1712                 :            : 
    1713                 :        258 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1714                 :            :     {
    1715                 :          2 :       fprintf (dump_file, "Found cond scalar reduction.\n");
    1716                 :          2 :       print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
    1717                 :            :     }
    1718                 :            : 
    1719                 :            :   /* Build cond expression using COND and constant operand
    1720                 :            :      of reduction rhs.  */
    1721                 :        764 :   c = fold_build_cond_expr (TREE_TYPE (rhs1),
    1722                 :            :                             unshare_expr (cond),
    1723                 :            :                             swap ? zero : op1,
    1724                 :            :                             swap ? op1 : zero);
    1725                 :            : 
    1726                 :            :   /* Create assignment stmt and insert it at GSI.  */
    1727                 :        258 :   new_assign = gimple_build_assign (tmp, c);
    1728                 :        258 :   gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
    1729                 :            :   /* Build rhs for unconditional increment/decrement.  */
    1730                 :        258 :   rhs = fold_build2 (gimple_assign_rhs_code (reduc),
    1731                 :            :                      TREE_TYPE (rhs1), op0, tmp);
    1732                 :            : 
    1733                 :            :   /* Delete original reduction stmt.  */
    1734                 :        258 :   stmt_it = gsi_for_stmt (reduc);
    1735                 :        258 :   gsi_remove (&stmt_it, true);
    1736                 :        258 :   release_defs (reduc);
    1737                 :        258 :   return rhs;
    1738                 :            : }
    1739                 :            : 
    1740                 :            : /* Produce condition for all occurrences of ARG in PHI node.  */
    1741                 :            : 
    1742                 :            : static tree
    1743                 :        494 : gen_phi_arg_condition (gphi *phi, vec<int> *occur,
    1744                 :            :                        gimple_stmt_iterator *gsi)
    1745                 :            : {
    1746                 :        494 :   int len;
    1747                 :        494 :   int i;
    1748                 :        494 :   tree cond = NULL_TREE;
    1749                 :        494 :   tree c;
    1750                 :        494 :   edge e;
    1751                 :            : 
    1752                 :        494 :   len = occur->length ();
    1753                 :        494 :   gcc_assert (len > 0);
    1754                 :       1060 :   for (i = 0; i < len; i++)
    1755                 :            :     {
    1756                 :        566 :       e = gimple_phi_arg_edge (phi, (*occur)[i]);
    1757                 :        566 :       c = bb_predicate (e->src);
    1758                 :        566 :       if (is_true_predicate (c))
    1759                 :            :         {
    1760                 :            :           cond = c;
    1761                 :            :           break;
    1762                 :            :         }
    1763                 :        566 :       c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
    1764                 :            :                                       is_gimple_condexpr, NULL_TREE,
    1765                 :            :                                       true, GSI_SAME_STMT);
    1766                 :        566 :       if (cond != NULL_TREE)
    1767                 :            :         {
    1768                 :            :           /* Must build OR expression.  */
    1769                 :         72 :           cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
    1770                 :         72 :           cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
    1771                 :            :                                              is_gimple_condexpr, NULL_TREE,
    1772                 :            :                                              true, GSI_SAME_STMT);
    1773                 :            :         }
    1774                 :            :       else
    1775                 :            :         cond = c;
    1776                 :            :     }
    1777                 :        494 :   gcc_assert (cond != NULL_TREE);
    1778                 :        494 :   return cond;
    1779                 :            : }
    1780                 :            : 
    1781                 :            : /* Local valueization callback that follows all-use SSA edges.  */
    1782                 :            : 
    1783                 :            : static tree
    1784                 :      87490 : ifcvt_follow_ssa_use_edges (tree val)
    1785                 :            : {
    1786                 :      87490 :   return val;
    1787                 :            : }
    1788                 :            : 
    1789                 :            : /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
    1790                 :            :    This routine can handle PHI nodes with more than two arguments.
    1791                 :            : 
    1792                 :            :    For example,
    1793                 :            :      S1: A = PHI <x1(1), x2(5)>
    1794                 :            :    is converted into,
    1795                 :            :      S2: A = cond ? x1 : x2;
    1796                 :            : 
    1797                 :            :    The generated code is inserted at GSI that points to the top of
    1798                 :            :    basic block's statement list.
    1799                 :            :    If PHI node has more than two arguments a chain of conditional
    1800                 :            :    expression is produced.  */
    1801                 :            : 
    1802                 :            : 
    1803                 :            : static void
    1804                 :       4702 : predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
    1805                 :            : {
    1806                 :       4702 :   gimple *new_stmt = NULL, *reduc;
    1807                 :       4702 :   tree rhs, res, arg0, arg1, op0, op1, scev;
    1808                 :       4702 :   tree cond;
    1809                 :       4702 :   unsigned int index0;
    1810                 :       4702 :   unsigned int max, args_len;
    1811                 :       4702 :   edge e;
    1812                 :       4702 :   basic_block bb;
    1813                 :       4702 :   unsigned int i;
    1814                 :            : 
    1815                 :       4702 :   res = gimple_phi_result (phi);
    1816                 :       9404 :   if (virtual_operand_p (res))
    1817                 :       4113 :     return;
    1818                 :            : 
    1819                 :       4702 :   if ((rhs = degenerate_phi_result (phi))
    1820                 :       4702 :       || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
    1821                 :            :                                             res))
    1822                 :       4702 :           && !chrec_contains_undetermined (scev)
    1823                 :       4702 :           && scev != res
    1824                 :          1 :           && (rhs = gimple_phi_arg_def (phi, 0))))
    1825                 :            :     {
    1826                 :          1 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1827                 :            :         {
    1828                 :          0 :           fprintf (dump_file, "Degenerate phi!\n");
    1829                 :          0 :           print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    1830                 :            :         }
    1831                 :          1 :       new_stmt = gimple_build_assign (res, rhs);
    1832                 :          1 :       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    1833                 :          1 :       update_stmt (new_stmt);
    1834                 :          1 :       return;
    1835                 :            :     }
    1836                 :            : 
    1837                 :       4701 :   bb = gimple_bb (phi);
    1838                 :       4701 :   if (EDGE_COUNT (bb->preds) == 2)
    1839                 :            :     {
    1840                 :            :       /* Predicate ordinary PHI node with 2 arguments.  */
    1841                 :       4112 :       edge first_edge, second_edge;
    1842                 :       4112 :       basic_block true_bb;
    1843                 :       4112 :       first_edge = EDGE_PRED (bb, 0);
    1844                 :       4112 :       second_edge = EDGE_PRED (bb, 1);
    1845                 :       4112 :       cond = bb_predicate (first_edge->src);
    1846                 :       4112 :       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    1847                 :        956 :         std::swap (first_edge, second_edge);
    1848                 :       4112 :       if (EDGE_COUNT (first_edge->src->succs) > 1)
    1849                 :            :         {
    1850                 :       1284 :           cond = bb_predicate (second_edge->src);
    1851                 :       1284 :           if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    1852                 :       1068 :             cond = TREE_OPERAND (cond, 0);
    1853                 :            :           else
    1854                 :            :             first_edge = second_edge;
    1855                 :            :         }
    1856                 :            :       else
    1857                 :       2828 :         cond = bb_predicate (first_edge->src);
    1858                 :            :       /* Gimplify the condition to a valid cond-expr conditonal operand.  */
    1859                 :       4112 :       cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
    1860                 :            :                                          is_gimple_condexpr, NULL_TREE,
    1861                 :            :                                          true, GSI_SAME_STMT);
    1862                 :       4112 :       true_bb = first_edge->src;
    1863                 :       4112 :       if (EDGE_PRED (bb, 1)->src == true_bb)
    1864                 :            :         {
    1865                 :       1172 :           arg0 = gimple_phi_arg_def (phi, 1);
    1866                 :       1172 :           arg1 = gimple_phi_arg_def (phi, 0);
    1867                 :            :         }
    1868                 :            :       else
    1869                 :            :         {
    1870                 :       2940 :           arg0 = gimple_phi_arg_def (phi, 0);
    1871                 :       2940 :           arg1 = gimple_phi_arg_def (phi, 1);
    1872                 :            :         }
    1873                 :       4112 :       if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
    1874                 :            :                                     &op0, &op1, false))
    1875                 :            :         /* Convert reduction stmt into vectorizable form.  */
    1876                 :        233 :         rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
    1877                 :        233 :                                              true_bb != gimple_bb (reduc));
    1878                 :            :       else
    1879                 :            :         /* Build new RHS using selected condition and arguments.  */
    1880                 :       3879 :         rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
    1881                 :            :                                     arg0, arg1);
    1882                 :       4112 :       new_stmt = gimple_build_assign (res, rhs);
    1883                 :       4112 :       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    1884                 :       4112 :       gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
    1885                 :       4112 :       if (fold_stmt (&new_gsi, ifcvt_follow_ssa_use_edges))
    1886                 :            :         {
    1887                 :       1515 :           new_stmt = gsi_stmt (new_gsi);
    1888                 :       1515 :           update_stmt (new_stmt);
    1889                 :            :         }
    1890                 :            : 
    1891                 :       4112 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1892                 :            :         {
    1893                 :         14 :           fprintf (dump_file, "new phi replacement stmt\n");
    1894                 :         14 :           print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    1895                 :            :         }
    1896                 :       4112 :       return;
    1897                 :            :     }
    1898                 :            : 
    1899                 :            :   /* Create hashmap for PHI node which contain vector of argument indexes
    1900                 :            :      having the same value.  */
    1901                 :        589 :   bool swap = false;
    1902                 :       1178 :   hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
    1903                 :        589 :   unsigned int num_args = gimple_phi_num_args (phi);
    1904                 :        589 :   int max_ind = -1;
    1905                 :            :   /* Vector of different PHI argument values.  */
    1906                 :       1178 :   auto_vec<tree> args (num_args);
    1907                 :            : 
    1908                 :            :   /* Compute phi_arg_map.  */
    1909                 :       2526 :   for (i = 0; i < num_args; i++)
    1910                 :            :     {
    1911                 :       1937 :       tree arg;
    1912                 :            : 
    1913                 :       1937 :       arg = gimple_phi_arg_def (phi, i);
    1914                 :       1937 :       if (!phi_arg_map.get (arg))
    1915                 :       1344 :         args.quick_push (arg);
    1916                 :       1937 :       phi_arg_map.get_or_insert (arg).safe_push (i);
    1917                 :            :     }
    1918                 :            : 
    1919                 :            :   /* Determine element with max number of occurrences.  */
    1920                 :        589 :   max_ind = -1;
    1921                 :        589 :   max = 1;
    1922                 :        589 :   args_len = args.length ();
    1923                 :       1933 :   for (i = 0; i < args_len; i++)
    1924                 :            :     {
    1925                 :       1344 :       unsigned int len;
    1926                 :       2688 :       if ((len = phi_arg_map.get (args[i])->length ()) > max)
    1927                 :            :         {
    1928                 :        477 :           max_ind = (int) i;
    1929                 :        477 :           max = len;
    1930                 :            :         }
    1931                 :            :     }
    1932                 :            : 
    1933                 :            :   /* Put element with max number of occurences to the end of ARGS.  */
    1934                 :        589 :   if (max_ind != -1 && max_ind +1 != (int) args_len)
    1935                 :        363 :     std::swap (args[args_len - 1], args[max_ind]);
    1936                 :            : 
    1937                 :            :   /* Handle one special case when number of arguments with different values
    1938                 :            :      is equal 2 and one argument has the only occurrence.  Such PHI can be
    1939                 :            :      handled as if would have only 2 arguments.  */
    1940                 :        589 :   if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
    1941                 :            :     {
    1942                 :        425 :       vec<int> *indexes;
    1943                 :        425 :       indexes = phi_arg_map.get (args[0]);
    1944                 :        425 :       index0 = (*indexes)[0];
    1945                 :        425 :       arg0 = args[0];
    1946                 :        425 :       arg1 = args[1];
    1947                 :        425 :       e = gimple_phi_arg_edge (phi, index0);
    1948                 :        425 :       cond = bb_predicate (e->src);
    1949                 :        425 :       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    1950                 :            :         {
    1951                 :         17 :           swap = true;
    1952                 :         17 :           cond = TREE_OPERAND (cond, 0);
    1953                 :            :         }
    1954                 :            :       /* Gimplify the condition to a valid cond-expr conditonal operand.  */
    1955                 :        425 :       cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
    1956                 :            :                                          is_gimple_condexpr, NULL_TREE,
    1957                 :            :                                          true, GSI_SAME_STMT);
    1958                 :        425 :       if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
    1959                 :            :                                       &op0, &op1, true)))
    1960                 :       1168 :         rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
    1961                 :            :                                     swap? arg1 : arg0,
    1962                 :            :                                     swap? arg0 : arg1);
    1963                 :            :       else
    1964                 :            :         /* Convert reduction stmt into vectorizable form.  */
    1965                 :         25 :         rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
    1966                 :            :                                              swap);
    1967                 :        425 :       new_stmt = gimple_build_assign (res, rhs);
    1968                 :        425 :       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    1969                 :        425 :       update_stmt (new_stmt);
    1970                 :            :     }
    1971                 :            :   else
    1972                 :            :     {
    1973                 :            :       /* Common case.  */
    1974                 :        164 :       vec<int> *indexes;
    1975                 :        164 :       tree type = TREE_TYPE (gimple_phi_result (phi));
    1976                 :        164 :       tree lhs;
    1977                 :        164 :       arg1 = args[1];
    1978                 :        658 :       for (i = 0; i < args_len; i++)
    1979                 :            :         {
    1980                 :        494 :           arg0 = args[i];
    1981                 :        494 :           indexes = phi_arg_map.get (args[i]);
    1982                 :        494 :           if (i != args_len - 1)
    1983                 :        330 :             lhs = make_temp_ssa_name (type, NULL, "_ifc_");
    1984                 :            :           else
    1985                 :            :             lhs = res;
    1986                 :        494 :           cond = gen_phi_arg_condition (phi, indexes, gsi);
    1987                 :        494 :           rhs = fold_build_cond_expr (type, unshare_expr (cond),
    1988                 :            :                                       arg0, arg1);
    1989                 :        494 :           new_stmt = gimple_build_assign (lhs, rhs);
    1990                 :        494 :           gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
    1991                 :        494 :           update_stmt (new_stmt);
    1992                 :        494 :           arg1 = lhs;
    1993                 :            :         }
    1994                 :            :     }
    1995                 :            : 
    1996                 :        589 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1997                 :            :     {
    1998                 :          3 :       fprintf (dump_file, "new extended phi replacement stmt\n");
    1999                 :          3 :       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    2000                 :            :     }
    2001                 :            : }
    2002                 :            : 
    2003                 :            : /* Replaces in LOOP all the scalar phi nodes other than those in the
    2004                 :            :    LOOP->header block with conditional modify expressions.  */
    2005                 :            : 
    2006                 :            : static void
    2007                 :       3131 : predicate_all_scalar_phis (class loop *loop)
    2008                 :            : {
    2009                 :       3131 :   basic_block bb;
    2010                 :       3131 :   unsigned int orig_loop_num_nodes = loop->num_nodes;
    2011                 :       3131 :   unsigned int i;
    2012                 :            : 
    2013                 :      18104 :   for (i = 1; i < orig_loop_num_nodes; i++)
    2014                 :            :     {
    2015                 :      14973 :       gphi *phi;
    2016                 :      14973 :       gimple_stmt_iterator gsi;
    2017                 :      14973 :       gphi_iterator phi_gsi;
    2018                 :      14973 :       bb = ifc_bbs[i];
    2019                 :            : 
    2020                 :      14973 :       if (bb == loop->header)
    2021                 :      10730 :         continue;
    2022                 :            : 
    2023                 :      14973 :       phi_gsi = gsi_start_phis (bb);
    2024                 :      14973 :       if (gsi_end_p (phi_gsi))
    2025                 :      10730 :         continue;
    2026                 :            : 
    2027                 :       8486 :       gsi = gsi_after_labels (bb);
    2028                 :       9539 :       while (!gsi_end_p (phi_gsi))
    2029                 :            :         {
    2030                 :       5296 :           phi = phi_gsi.phi ();
    2031                 :      10592 :           if (virtual_operand_p (gimple_phi_result (phi)))
    2032                 :        594 :             gsi_next (&phi_gsi);
    2033                 :            :           else
    2034                 :            :             {
    2035                 :       4702 :               predicate_scalar_phi (phi, &gsi);
    2036                 :       4702 :               remove_phi_node (&phi_gsi, false);
    2037                 :            :             }
    2038                 :            :         }
    2039                 :            :     }
    2040                 :       3131 : }
    2041                 :            : 
    2042                 :            : /* Insert in each basic block of LOOP the statements produced by the
    2043                 :            :    gimplification of the predicates.  */
    2044                 :            : 
    2045                 :            : static void
    2046                 :       3131 : insert_gimplified_predicates (loop_p loop)
    2047                 :            : {
    2048                 :       3131 :   unsigned int i;
    2049                 :            : 
    2050                 :      21235 :   for (i = 0; i < loop->num_nodes; i++)
    2051                 :            :     {
    2052                 :      18104 :       basic_block bb = ifc_bbs[i];
    2053                 :      18104 :       gimple_seq stmts;
    2054                 :      18104 :       if (!is_predicated (bb))
    2055                 :      10192 :         gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
    2056                 :      18104 :       if (!is_predicated (bb))
    2057                 :            :         {
    2058                 :            :           /* Do not insert statements for a basic block that is not
    2059                 :            :              predicated.  Also make sure that the predicate of the
    2060                 :            :              basic block is set to true.  */
    2061                 :      10192 :           reset_bb_predicate (bb);
    2062                 :      10192 :           continue;
    2063                 :            :         }
    2064                 :            : 
    2065                 :       7912 :       stmts = bb_predicate_gimplified_stmts (bb);
    2066                 :       7912 :       if (stmts)
    2067                 :            :         {
    2068                 :       1784 :           if (need_to_predicate)
    2069                 :            :             {
    2070                 :            :               /* Insert the predicate of the BB just after the label,
    2071                 :            :                  as the if-conversion of memory writes will use this
    2072                 :            :                  predicate.  */
    2073                 :         68 :               gimple_stmt_iterator gsi = gsi_after_labels (bb);
    2074                 :         68 :               gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    2075                 :            :             }
    2076                 :            :           else
    2077                 :            :             {
    2078                 :            :               /* Insert the predicate of the BB at the end of the BB
    2079                 :            :                  as this would reduce the register pressure: the only
    2080                 :            :                  use of this predicate will be in successor BBs.  */
    2081                 :       1716 :               gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2082                 :            : 
    2083                 :       1716 :               if (gsi_end_p (gsi)
    2084                 :       1716 :                   || stmt_ends_bb_p (gsi_stmt (gsi)))
    2085                 :       1465 :                 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    2086                 :            :               else
    2087                 :        251 :                 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
    2088                 :            :             }
    2089                 :            : 
    2090                 :            :           /* Once the sequence is code generated, set it to NULL.  */
    2091                 :      18104 :           set_bb_predicate_gimplified_stmts (bb, NULL);
    2092                 :            :         }
    2093                 :            :     }
    2094                 :       3131 : }
    2095                 :            : 
    2096                 :            : /* Helper function for predicate_statements. Returns index of existent
    2097                 :            :    mask if it was created for given SIZE and -1 otherwise.  */
    2098                 :            : 
    2099                 :            : static int
    2100                 :          0 : mask_exists (int size, vec<int> vec)
    2101                 :            : {
    2102                 :          0 :   unsigned int ix;
    2103                 :          0 :   int v;
    2104                 :         73 :   FOR_EACH_VEC_ELT (vec, ix, v)
    2105                 :        284 :     if (v == size)
    2106                 :        211 :       return (int) ix;
    2107                 :            :   return -1;
    2108                 :            : }
    2109                 :            : 
    2110                 :            : /* Helper function for predicate_statements.  STMT is a memory read or
    2111                 :            :    write and it needs to be predicated by MASK.  Return a statement
    2112                 :            :    that does so.  */
    2113                 :            : 
    2114                 :            : static gimple *
    2115                 :        569 : predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask)
    2116                 :            : {
    2117                 :        569 :   gcall *new_stmt;
    2118                 :            : 
    2119                 :        569 :   tree lhs = gimple_assign_lhs (stmt);
    2120                 :        569 :   tree rhs = gimple_assign_rhs1 (stmt);
    2121                 :        569 :   tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
    2122                 :        569 :   mark_addressable (ref);
    2123                 :        569 :   tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref),
    2124                 :            :                                         true, NULL_TREE, true, GSI_SAME_STMT);
    2125                 :        569 :   tree ptr = build_int_cst (reference_alias_ptr_type (ref),
    2126                 :        569 :                             get_object_alignment (ref));
    2127                 :            :   /* Copy points-to info if possible.  */
    2128                 :        569 :   if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
    2129                 :        224 :     copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
    2130                 :            :                    ref);
    2131                 :        569 :   if (TREE_CODE (lhs) == SSA_NAME)
    2132                 :            :     {
    2133                 :        292 :       new_stmt
    2134                 :        292 :         = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
    2135                 :            :                                       ptr, mask);
    2136                 :        292 :       gimple_call_set_lhs (new_stmt, lhs);
    2137                 :        584 :       gimple_set_vuse (new_stmt, gimple_vuse (stmt));
    2138                 :            :     }
    2139                 :            :   else
    2140                 :            :     {
    2141                 :        277 :       new_stmt
    2142                 :        277 :         = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
    2143                 :            :                                       mask, rhs);
    2144                 :        277 :       gimple_move_vops (new_stmt, stmt);
    2145                 :            :     }
    2146                 :        569 :   gimple_call_set_nothrow (new_stmt, true);
    2147                 :        569 :   return new_stmt;
    2148                 :            : }
    2149                 :            : 
    2150                 :            : /* STMT uses OP_LHS.  Check whether it is equivalent to:
    2151                 :            : 
    2152                 :            :      ... = OP_MASK ? OP_LHS : X;
    2153                 :            : 
    2154                 :            :    Return X if so, otherwise return null.  OP_MASK is an SSA_NAME that is
    2155                 :            :    known to have value OP_COND.  */
    2156                 :            : 
    2157                 :            : static tree
    2158                 :          0 : check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond,
    2159                 :            :                            tree op_lhs)
    2160                 :            : {
    2161                 :          0 :   gassign *assign = dyn_cast <gassign *> (stmt);
    2162                 :          0 :   if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR)
    2163                 :            :     return NULL_TREE;
    2164                 :            : 
    2165                 :          0 :   tree use_cond = gimple_assign_rhs1 (assign);
    2166                 :          0 :   tree if_true = gimple_assign_rhs2 (assign);
    2167                 :          0 :   tree if_false = gimple_assign_rhs3 (assign);
    2168                 :            : 
    2169                 :          0 :   if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0))
    2170                 :          0 :       && if_true == op_lhs)
    2171                 :            :     return if_false;
    2172                 :            : 
    2173                 :          0 :   if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs)
    2174                 :          0 :     return if_true;
    2175                 :            : 
    2176                 :            :   return NULL_TREE;
    2177                 :            : }
    2178                 :            : 
    2179                 :            : /* Return true if VALUE is available for use at STMT.  SSA_NAMES is
    2180                 :            :    the set of SSA names defined earlier in STMT's block.  */
    2181                 :            : 
    2182                 :            : static bool
    2183                 :          0 : value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names,
    2184                 :            :                    tree value)
    2185                 :            : {
    2186                 :          0 :   if (is_gimple_min_invariant (value))
    2187                 :            :     return true;
    2188                 :            : 
    2189                 :          0 :   if (TREE_CODE (value) == SSA_NAME)
    2190                 :            :     {
    2191                 :          0 :       if (SSA_NAME_IS_DEFAULT_DEF (value))
    2192                 :            :         return true;
    2193                 :            : 
    2194                 :          0 :       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
    2195                 :          0 :       basic_block use_bb = gimple_bb (stmt);
    2196                 :          0 :       return (def_bb == use_bb
    2197                 :          0 :               ? ssa_names->contains (value)
    2198                 :          0 :               : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
    2199                 :            :     }
    2200                 :            : 
    2201                 :            :   return false;
    2202                 :            : }
    2203                 :            : 
    2204                 :            : /* Helper function for predicate_statements.  STMT is a potentially-trapping
    2205                 :            :    arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
    2206                 :            :    has value COND.  Return a statement that does so.  SSA_NAMES is the set of
    2207                 :            :    SSA names defined earlier in STMT's block.  */
    2208                 :            : 
    2209                 :            : static gimple *
    2210                 :          0 : predicate_rhs_code (gassign *stmt, tree mask, tree cond,
    2211                 :            :                     hash_set<tree_ssa_name_hash> *ssa_names)
    2212                 :            : {
    2213                 :          0 :   tree lhs = gimple_assign_lhs (stmt);
    2214                 :          0 :   tree_code code = gimple_assign_rhs_code (stmt);
    2215                 :          0 :   unsigned int nops = gimple_num_ops (stmt);
    2216                 :          0 :   internal_fn cond_fn = get_conditional_internal_fn (code);
    2217                 :            : 
    2218                 :            :   /* Construct the arguments to the conditional internal function.   */
    2219                 :          0 :   auto_vec<tree, 8> args;
    2220                 :          0 :   args.safe_grow (nops + 1);
    2221                 :          0 :   args[0] = mask;
    2222                 :          0 :   for (unsigned int i = 1; i < nops; ++i)
    2223                 :          0 :     args[i] = gimple_op (stmt, i);
    2224                 :          0 :   args[nops] = NULL_TREE;
    2225                 :            : 
    2226                 :            :   /* Look for uses of the result to see whether they are COND_EXPRs that can
    2227                 :            :      be folded into the conditional call.  */
    2228                 :          0 :   imm_use_iterator imm_iter;
    2229                 :          0 :   gimple *use_stmt;
    2230                 :          0 :   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
    2231                 :            :     {
    2232                 :          0 :       tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs);
    2233                 :          0 :       if (new_else && value_available_p (stmt, ssa_names, new_else))
    2234                 :            :         {
    2235                 :          0 :           if (!args[nops])
    2236                 :          0 :             args[nops] = new_else;
    2237                 :          0 :           if (operand_equal_p (new_else, args[nops], 0))
    2238                 :            :             {
    2239                 :            :               /* We have:
    2240                 :            : 
    2241                 :            :                    LHS = IFN_COND (MASK, ..., ELSE);
    2242                 :            :                    X = MASK ? LHS : ELSE;
    2243                 :            : 
    2244                 :            :                  which makes X equivalent to LHS.  */
    2245                 :          0 :               tree use_lhs = gimple_assign_lhs (use_stmt);
    2246                 :          0 :               redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs));
    2247                 :            :             }
    2248                 :            :         }
    2249                 :            :     }
    2250                 :          0 :   if (!args[nops])
    2251                 :          0 :     args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs),
    2252                 :          0 :                                                nops - 1, &args[1]);
    2253                 :            : 
    2254                 :            :   /* Create and insert the call.  */
    2255                 :          0 :   gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args);
    2256                 :          0 :   gimple_call_set_lhs (new_stmt, lhs);
    2257                 :          0 :   gimple_call_set_nothrow (new_stmt, true);
    2258                 :            : 
    2259                 :          0 :   return new_stmt;
    2260                 :            : }
    2261                 :            : 
    2262                 :            : /* Predicate each write to memory in LOOP.
    2263                 :            : 
    2264                 :            :    This function transforms control flow constructs containing memory
    2265                 :            :    writes of the form:
    2266                 :            : 
    2267                 :            :    | for (i = 0; i < N; i++)
    2268                 :            :    |   if (cond)
    2269                 :            :    |     A[i] = expr;
    2270                 :            : 
    2271                 :            :    into the following form that does not contain control flow:
    2272                 :            : 
    2273                 :            :    | for (i = 0; i < N; i++)
    2274                 :            :    |   A[i] = cond ? expr : A[i];
    2275                 :            : 
    2276                 :            :    The original CFG looks like this:
    2277                 :            : 
    2278                 :            :    | bb_0
    2279                 :            :    |   i = 0
    2280                 :            :    | end_bb_0
    2281                 :            :    |
    2282                 :            :    | bb_1
    2283                 :            :    |   if (i < N) goto bb_5 else goto bb_2
    2284                 :            :    | end_bb_1
    2285                 :            :    |
    2286                 :            :    | bb_2
    2287                 :            :    |   cond = some_computation;
    2288                 :            :    |   if (cond) goto bb_3 else goto bb_4
    2289                 :            :    | end_bb_2
    2290                 :            :    |
    2291                 :            :    | bb_3
    2292                 :            :    |   A[i] = expr;
    2293                 :            :    |   goto bb_4
    2294                 :            :    | end_bb_3
    2295                 :            :    |
    2296                 :            :    | bb_4
    2297                 :            :    |   goto bb_1
    2298                 :            :    | end_bb_4
    2299                 :            : 
    2300                 :            :    insert_gimplified_predicates inserts the computation of the COND
    2301                 :            :    expression at the beginning of the destination basic block:
    2302                 :            : 
    2303                 :            :    | bb_0
    2304                 :            :    |   i = 0
    2305                 :            :    | end_bb_0
    2306                 :            :    |
    2307                 :            :    | bb_1
    2308                 :            :    |   if (i < N) goto bb_5 else goto bb_2
    2309                 :            :    | end_bb_1
    2310                 :            :    |
    2311                 :            :    | bb_2
    2312                 :            :    |   cond = some_computation;
    2313                 :            :    |   if (cond) goto bb_3 else goto bb_4
    2314                 :            :    | end_bb_2
    2315                 :            :    |
    2316                 :            :    | bb_3
    2317                 :            :    |   cond = some_computation;
    2318                 :            :    |   A[i] = expr;
    2319                 :            :    |   goto bb_4
    2320                 :            :    | end_bb_3
    2321                 :            :    |
    2322                 :            :    | bb_4
    2323                 :            :    |   goto bb_1
    2324                 :            :    | end_bb_4
    2325                 :            : 
    2326                 :            :    predicate_statements is then predicating the memory write as follows:
    2327                 :            : 
    2328                 :            :    | bb_0
    2329                 :            :    |   i = 0
    2330                 :            :    | end_bb_0
    2331                 :            :    |
    2332                 :            :    | bb_1
    2333                 :            :    |   if (i < N) goto bb_5 else goto bb_2
    2334                 :            :    | end_bb_1
    2335                 :            :    |
    2336                 :            :    | bb_2
    2337                 :            :    |   if (cond) goto bb_3 else goto bb_4
    2338                 :            :    | end_bb_2
    2339                 :            :    |
    2340                 :            :    | bb_3
    2341                 :            :    |   cond = some_computation;
    2342                 :            :    |   A[i] = cond ? expr : A[i];
    2343                 :            :    |   goto bb_4
    2344                 :            :    | end_bb_3
    2345                 :            :    |
    2346                 :            :    | bb_4
    2347                 :            :    |   goto bb_1
    2348                 :            :    | end_bb_4
    2349                 :            : 
    2350                 :            :    and finally combine_blocks removes the basic block boundaries making
    2351                 :            :    the loop vectorizable:
    2352                 :            : 
    2353                 :            :    | bb_0
    2354                 :            :    |   i = 0
    2355                 :            :    |   if (i < N) goto bb_5 else goto bb_1
    2356                 :            :    | end_bb_0
    2357                 :            :    |
    2358                 :            :    | bb_1
    2359                 :            :    |   cond = some_computation;
    2360                 :            :    |   A[i] = cond ? expr : A[i];
    2361                 :            :    |   if (i < N) goto bb_5 else goto bb_4
    2362                 :            :    | end_bb_1
    2363                 :            :    |
    2364                 :            :    | bb_4
    2365                 :            :    |   goto bb_1
    2366                 :            :    | end_bb_4
    2367                 :            : */
    2368                 :            : 
    2369                 :            : static void
    2370                 :        379 : predicate_statements (loop_p loop)
    2371                 :            : {
    2372                 :        379 :   unsigned int i, orig_loop_num_nodes = loop->num_nodes;
    2373                 :        379 :   auto_vec<int, 1> vect_sizes;
    2374                 :        379 :   auto_vec<tree, 1> vect_masks;
    2375                 :        758 :   hash_set<tree_ssa_name_hash> ssa_names;
    2376                 :            : 
    2377                 :       1813 :   for (i = 1; i < orig_loop_num_nodes; i++)
    2378                 :            :     {
    2379                 :       1434 :       gimple_stmt_iterator gsi;
    2380                 :       1434 :       basic_block bb = ifc_bbs[i];
    2381                 :       1434 :       tree cond = bb_predicate (bb);
    2382                 :       1434 :       bool swap;
    2383                 :       1434 :       int index;
    2384                 :            : 
    2385                 :       1434 :       if (is_true_predicate (cond))
    2386                 :        769 :         continue;
    2387                 :            : 
    2388                 :        665 :       swap = false;
    2389                 :        665 :       if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    2390                 :            :         {
    2391                 :        201 :           swap = true;
    2392                 :        201 :           cond = TREE_OPERAND (cond, 0);
    2393                 :            :         }
    2394                 :            : 
    2395                 :        665 :       vect_sizes.truncate (0);
    2396                 :        665 :       vect_masks.truncate (0);
    2397                 :            : 
    2398                 :       3678 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    2399                 :            :         {
    2400                 :       2348 :           gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi));
    2401                 :       2159 :           if (!stmt)
    2402                 :            :             ;
    2403                 :       4318 :           else if (is_false_predicate (cond)
    2404                 :          0 :                    && gimple_vdef (stmt))
    2405                 :            :             {
    2406                 :          0 :               unlink_stmt_vdef (stmt);
    2407                 :          0 :               gsi_remove (&gsi, true);
    2408                 :          0 :               release_defs (stmt);
    2409                 :          0 :               continue;
    2410                 :            :             }
    2411                 :       2159 :           else if (gimple_plf (stmt, GF_PLF_2))
    2412                 :            :             {
    2413                 :        569 :               tree lhs = gimple_assign_lhs (stmt);
    2414                 :        569 :               tree mask;
    2415                 :        569 :               gimple *new_stmt;
    2416                 :        569 :               gimple_seq stmts = NULL;
    2417                 :        569 :               machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
    2418                 :            :               /* We checked before setting GF_PLF_2 that an equivalent
    2419                 :            :                  integer mode exists.  */
    2420                 :       1138 :               int bitsize = GET_MODE_BITSIZE (mode).to_constant ();
    2421                 :        569 :               if (!vect_sizes.is_empty ()
    2422                 :        544 :                   && (index = mask_exists (bitsize, vect_sizes)) != -1)
    2423                 :            :                 /* Use created mask.  */
    2424                 :        211 :                 mask = vect_masks[index];
    2425                 :            :               else
    2426                 :            :                 {
    2427                 :        358 :                   if (COMPARISON_CLASS_P (cond))
    2428                 :        340 :                     mask = gimple_build (&stmts, TREE_CODE (cond),
    2429                 :            :                                          boolean_type_node,
    2430                 :        340 :                                          TREE_OPERAND (cond, 0),
    2431                 :        340 :                                          TREE_OPERAND (cond, 1));
    2432                 :            :                   else
    2433                 :         18 :                     mask = cond;
    2434                 :            : 
    2435                 :        358 :                   if (swap)
    2436                 :            :                     {
    2437                 :        109 :                       tree true_val
    2438                 :        109 :                         = constant_boolean_node (true, TREE_TYPE (mask));
    2439                 :        109 :                       mask = gimple_build (&stmts, BIT_XOR_EXPR,
    2440                 :        109 :                                            TREE_TYPE (mask), mask, true_val);
    2441                 :            :                     }
    2442                 :        358 :                   gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    2443                 :            : 
    2444                 :            :                   /* Save mask and its size for further use.  */
    2445                 :        358 :                   vect_sizes.safe_push (bitsize);
    2446                 :        358 :                   vect_masks.safe_push (mask);
    2447                 :            :                 }
    2448                 :        569 :               if (gimple_assign_single_p (stmt))
    2449                 :        569 :                 new_stmt = predicate_load_or_store (&gsi, stmt, mask);
    2450                 :            :               else
    2451                 :          0 :                 new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names);
    2452                 :            : 
    2453                 :        569 :               gsi_replace (&gsi, new_stmt, true);
    2454                 :            :             }
    2455                 :       3180 :           else if (gimple_vdef (stmt))
    2456                 :            :             {
    2457                 :        194 :               tree lhs = gimple_assign_lhs (stmt);
    2458                 :        194 :               tree rhs = gimple_assign_rhs1 (stmt);
    2459                 :        194 :               tree type = TREE_TYPE (lhs);
    2460                 :            : 
    2461                 :        194 :               lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
    2462                 :        194 :               rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
    2463                 :        194 :               if (swap)
    2464                 :         42 :                 std::swap (lhs, rhs);
    2465                 :        194 :               cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
    2466                 :            :                                                  is_gimple_condexpr, NULL_TREE,
    2467                 :            :                                                  true, GSI_SAME_STMT);
    2468                 :        194 :               rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
    2469                 :        194 :               gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
    2470                 :       2542 :               update_stmt (stmt);
    2471                 :            :             }
    2472                 :       2348 :           tree lhs = gimple_get_lhs (gsi_stmt (gsi));
    2473                 :       2348 :           if (lhs && TREE_CODE (lhs) == SSA_NAME)
    2474                 :       1690 :             ssa_names.add (lhs);
    2475                 :       2348 :           gsi_next (&gsi);
    2476                 :            :         }
    2477                 :       1105 :       ssa_names.empty ();
    2478                 :            :     }
    2479                 :        379 : }
    2480                 :            : 
    2481                 :            : /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
    2482                 :            :    other than the exit and latch of the LOOP.  Also resets the
    2483                 :            :    GIMPLE_DEBUG information.  */
    2484                 :            : 
    2485                 :            : static void
    2486                 :       3131 : remove_conditions_and_labels (loop_p loop)
    2487                 :            : {
    2488                 :       3131 :   gimple_stmt_iterator gsi;
    2489                 :       3131 :   unsigned int i;
    2490                 :            : 
    2491                 :      21235 :   for (i = 0; i < loop->num_nodes; i++)
    2492                 :            :     {
    2493                 :      18104 :       basic_block bb = ifc_bbs[i];
    2494                 :            : 
    2495                 :      18104 :       if (bb_with_exit_edge_p (loop, bb)
    2496                 :      18104 :         || bb == loop->latch)
    2497                 :       6262 :       continue;
    2498                 :            : 
    2499                 :      56456 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
    2500                 :      32772 :         switch (gimple_code (gsi_stmt (gsi)))
    2501                 :            :           {
    2502                 :       4716 :           case GIMPLE_COND:
    2503                 :       4716 :           case GIMPLE_LABEL:
    2504                 :       4716 :             gsi_remove (&gsi, true);
    2505                 :       4716 :             break;
    2506                 :            : 
    2507                 :       7717 :           case GIMPLE_DEBUG:
    2508                 :            :             /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
    2509                 :       7717 :             if (gimple_debug_bind_p (gsi_stmt (gsi)))
    2510                 :            :               {
    2511                 :       5393 :                 gimple_debug_bind_reset_value (gsi_stmt (gsi));
    2512                 :       5393 :                 update_stmt (gsi_stmt (gsi));
    2513                 :            :               }
    2514                 :       7717 :             gsi_next (&gsi);
    2515                 :            :             break;
    2516                 :            : 
    2517                 :      20339 :           default:
    2518                 :      20339 :             gsi_next (&gsi);
    2519                 :            :           }
    2520                 :            :     }
    2521                 :       3131 : }
    2522                 :            : 
    2523                 :            : /* Combine all the basic blocks from LOOP into one or two super basic
    2524                 :            :    blocks.  Replace PHI nodes with conditional modify expressions.  */
    2525                 :            : 
    2526                 :            : static void
    2527                 :       3131 : combine_blocks (class loop *loop)
    2528                 :            : {
    2529                 :       3131 :   basic_block bb, exit_bb, merge_target_bb;
    2530                 :       3131 :   unsigned int orig_loop_num_nodes = loop->num_nodes;
    2531                 :       3131 :   unsigned int i;
    2532                 :       3131 :   edge e;
    2533                 :       3131 :   edge_iterator ei;
    2534                 :            : 
    2535                 :       3131 :   remove_conditions_and_labels (loop);
    2536                 :       3131 :   insert_gimplified_predicates (loop);
    2537                 :       3131 :   predicate_all_scalar_phis (loop);
    2538                 :            : 
    2539                 :       3131 :   if (need_to_predicate)
    2540                 :        379 :     predicate_statements (loop);
    2541                 :            : 
    2542                 :            :   /* Merge basic blocks: first remove all the edges in the loop,
    2543                 :            :      except for those from the exit block.  */
    2544                 :       3131 :   exit_bb = NULL;
    2545                 :       3131 :   bool *predicated = XNEWVEC (bool, orig_loop_num_nodes);
    2546                 :      21235 :   for (i = 0; i < orig_loop_num_nodes; i++)
    2547                 :            :     {
    2548                 :      18104 :       bb = ifc_bbs[i];
    2549                 :      18104 :       predicated[i] = !is_true_predicate (bb_predicate (bb));
    2550                 :      18104 :       free_bb_predicate (bb);
    2551                 :      18104 :       if (bb_with_exit_edge_p (loop, bb))
    2552                 :            :         {
    2553                 :       3131 :           gcc_assert (exit_bb == NULL);
    2554                 :            :           exit_bb = bb;
    2555                 :            :         }
    2556                 :            :     }
    2557                 :       3131 :   gcc_assert (exit_bb != loop->latch);
    2558                 :            : 
    2559                 :      18104 :   for (i = 1; i < orig_loop_num_nodes; i++)
    2560                 :            :     {
    2561                 :      14973 :       bb = ifc_bbs[i];
    2562                 :            : 
    2563                 :      34662 :       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
    2564                 :            :         {
    2565                 :      19689 :           if (e->src == exit_bb)
    2566                 :       3131 :             ei_next (&ei);
    2567                 :            :           else
    2568                 :      16558 :             remove_edge (e);
    2569                 :            :         }
    2570                 :            :     }
    2571                 :            : 
    2572                 :       3131 :   if (exit_bb != NULL)
    2573                 :            :     {
    2574                 :       3131 :       if (exit_bb != loop->header)
    2575                 :            :         {
    2576                 :            :           /* Connect this node to loop header.  */
    2577                 :       3131 :           make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU);
    2578                 :       3131 :           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
    2579                 :            :         }
    2580                 :            : 
    2581                 :            :       /* Redirect non-exit edges to loop->latch.  */
    2582                 :       9393 :       FOR_EACH_EDGE (e, ei, exit_bb->succs)
    2583                 :            :         {
    2584                 :       6262 :           if (!loop_exit_edge_p (loop, e))
    2585                 :       3131 :             redirect_edge_and_branch (e, loop->latch);
    2586                 :            :         }
    2587                 :       3131 :       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
    2588                 :            :     }
    2589                 :            :   else
    2590                 :            :     {
    2591                 :            :       /* If the loop does not have an exit, reconnect header and latch.  */
    2592                 :          0 :       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
    2593                 :          0 :       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
    2594                 :            :     }
    2595                 :            : 
    2596                 :       3131 :   merge_target_bb = loop->header;
    2597                 :            : 
    2598                 :            :   /* Get at the virtual def valid for uses starting at the first block
    2599                 :            :      we merge into the header.  Without a virtual PHI the loop has the
    2600                 :            :      same virtual use on all stmts.  */
    2601                 :       3131 :   gphi *vphi = get_virtual_phi (loop->header);
    2602                 :       3131 :   tree last_vdef = NULL_TREE;
    2603                 :       3131 :   if (vphi)
    2604                 :            :     {
    2605                 :       1631 :       last_vdef = gimple_phi_result (vphi);
    2606                 :       1631 :       for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
    2607                 :      12805 :            ! gsi_end_p (gsi); gsi_next (&gsi))
    2608                 :      17842 :         if (gimple_vdef (gsi_stmt (gsi)))
    2609                 :        164 :           last_vdef = gimple_vdef (gsi_stmt (gsi));
    2610                 :            :     }
    2611                 :      18104 :   for (i = 1; i < orig_loop_num_nodes; i++)
    2612                 :            :     {
    2613                 :      14973 :       gimple_stmt_iterator gsi;
    2614                 :      14973 :       gimple_stmt_iterator last;
    2615                 :            : 
    2616                 :      14973 :       bb = ifc_bbs[i];
    2617                 :            : 
    2618                 :      14973 :       if (bb == exit_bb || bb == loop->latch)
    2619                 :       6262 :         continue;
    2620                 :            : 
    2621                 :            :       /* We release virtual PHIs late because we have to propagate them
    2622                 :            :          out using the current VUSE.  The def might be the one used
    2623                 :            :          after the loop.  */
    2624                 :       8711 :       vphi = get_virtual_phi (bb);
    2625                 :       8711 :       if (vphi)
    2626                 :            :         {
    2627                 :            :           /* When there's just loads inside the loop a stray virtual
    2628                 :            :              PHI merging the uses can appear, update last_vdef from
    2629                 :            :              it.  */
    2630                 :        156 :           if (!last_vdef)
    2631                 :          0 :             last_vdef = gimple_phi_arg_def (vphi, 0);
    2632                 :        156 :           imm_use_iterator iter;
    2633                 :        156 :           use_operand_p use_p;
    2634                 :        156 :           gimple *use_stmt;
    2635                 :        203 :           FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
    2636                 :            :             {
    2637                 :        141 :               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    2638                 :         47 :                 SET_USE (use_p, last_vdef);
    2639                 :            :             }
    2640                 :        156 :           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
    2641                 :          0 :             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
    2642                 :        156 :           gsi = gsi_for_stmt (vphi); 
    2643                 :        156 :           remove_phi_node (&gsi, true);
    2644                 :            :         }
    2645                 :            : 
    2646                 :            :       /* Make stmts member of loop->header and clear range info from all stmts
    2647                 :            :          in BB which is now no longer executed conditional on a predicate we
    2648                 :            :          could have derived it from.  */
    2649                 :      36272 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2650                 :            :         {
    2651                 :      18850 :           gimple *stmt = gsi_stmt (gsi);
    2652                 :      18850 :           gimple_set_bb (stmt, merge_target_bb);
    2653                 :            :           /* Update virtual operands.  */
    2654                 :      18850 :           if (last_vdef)
    2655                 :            :             {
    2656                 :      16040 :               use_operand_p use_p = ssa_vuse_operand (stmt);
    2657                 :       2890 :               if (use_p
    2658                 :       2890 :                   && USE_FROM_PTR (use_p) != last_vdef)
    2659                 :         93 :                 SET_USE (use_p, last_vdef);
    2660                 :      29907 :               if (gimple_vdef (stmt))
    2661                 :        722 :                 last_vdef = gimple_vdef (stmt);
    2662                 :            :             }
    2663                 :            :           else
    2664                 :            :             /* If this is the first load we arrive at update last_vdef
    2665                 :            :                so we handle stray PHIs correctly.  */
    2666                 :      21361 :             last_vdef = gimple_vuse (stmt);
    2667                 :      18850 :           if (predicated[i])
    2668                 :            :             {
    2669                 :      14264 :               ssa_op_iter i;
    2670                 :      14264 :               tree op;
    2671                 :      26301 :               FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
    2672                 :      12037 :                 reset_flow_sensitive_info (op);
    2673                 :            :             }
    2674                 :            :         }
    2675                 :            : 
    2676                 :            :       /* Update stmt list.  */
    2677                 :       8711 :       last = gsi_last_bb (merge_target_bb);
    2678                 :      17422 :       gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
    2679                 :       8711 :       set_bb_seq (bb, NULL);
    2680                 :            : 
    2681                 :       8711 :       delete_basic_block (bb);
    2682                 :            :     }
    2683                 :            : 
    2684                 :            :   /* If possible, merge loop header to the block with the exit edge.
    2685                 :            :      This reduces the number of basic blocks to two, to please the
    2686                 :            :      vectorizer that handles only loops with two nodes.  */
    2687                 :       3131 :   if (exit_bb
    2688                 :       3131 :       && exit_bb != loop->header)
    2689                 :            :     {
    2690                 :            :       /* We release virtual PHIs late because we have to propagate them
    2691                 :            :          out using the current VUSE.  The def might be the one used
    2692                 :            :          after the loop.  */
    2693                 :       3131 :       vphi = get_virtual_phi (exit_bb);
    2694                 :       3131 :       if (vphi)
    2695                 :            :         {
    2696                 :        438 :           imm_use_iterator iter;
    2697                 :        438 :           use_operand_p use_p;
    2698                 :        438 :           gimple *use_stmt;
    2699                 :       1331 :           FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
    2700                 :            :             {
    2701                 :       2711 :               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    2702                 :        909 :                 SET_USE (use_p, last_vdef);
    2703                 :            :             }
    2704                 :        438 :           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
    2705                 :          0 :             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
    2706                 :        438 :           gimple_stmt_iterator gsi = gsi_for_stmt (vphi); 
    2707                 :        438 :           remove_phi_node (&gsi, true);
    2708                 :            :         }
    2709                 :            : 
    2710                 :       3131 :       if (can_merge_blocks_p (loop->header, exit_bb))
    2711                 :       3131 :         merge_blocks (loop->header, exit_bb);
    2712                 :            :     }
    2713                 :            : 
    2714                 :       3131 :   free (ifc_bbs);
    2715                 :       3131 :   ifc_bbs = NULL;
    2716                 :       3131 :   free (predicated);
    2717                 :       3131 : }
    2718                 :            : 
    2719                 :            : /* Version LOOP before if-converting it; the original loop
    2720                 :            :    will be if-converted, the new copy of the loop will not,
    2721                 :            :    and the LOOP_VECTORIZED internal call will be guarding which
    2722                 :            :    loop to execute.  The vectorizer pass will fold this
    2723                 :            :    internal call into either true or false. 
    2724                 :            : 
    2725                 :            :    Note that this function intentionally invalidates profile.  Both edges
    2726                 :            :    out of LOOP_VECTORIZED must have 100% probability so the profile remains
    2727                 :            :    consistent after the condition is folded in the vectorizer.  */
    2728                 :            : 
    2729                 :            : static class loop *
    2730                 :       3064 : version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
    2731                 :            : {
    2732                 :       3064 :   basic_block cond_bb;
    2733                 :       3064 :   tree cond = make_ssa_name (boolean_type_node);
    2734                 :       3064 :   class loop *new_loop;
    2735                 :       3064 :   gimple *g;
    2736                 :       3064 :   gimple_stmt_iterator gsi;
    2737                 :       3064 :   unsigned int save_length;
    2738                 :            : 
    2739                 :       3064 :   g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
    2740                 :       3064 :                                   build_int_cst (integer_type_node, loop->num),
    2741                 :            :                                   integer_zero_node);
    2742                 :       3064 :   gimple_call_set_lhs (g, cond);
    2743                 :            : 
    2744                 :            :   /* Save BB->aux around loop_version as that uses the same field.  */
    2745                 :       3064 :   save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
    2746                 :       3064 :   void **saved_preds = XALLOCAVEC (void *, save_length);
    2747                 :      20624 :   for (unsigned i = 0; i < save_length; i++)
    2748                 :      17560 :     saved_preds[i] = ifc_bbs[i]->aux;
    2749                 :            : 
    2750                 :       3064 :   initialize_original_copy_tables ();
    2751                 :            :   /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
    2752                 :            :      is re-merged in the vectorizer.  */
    2753                 :       3064 :   new_loop = loop_version (loop, cond, &cond_bb,
    2754                 :            :                            profile_probability::always (),
    2755                 :            :                            profile_probability::always (),
    2756                 :            :                            profile_probability::always (),
    2757                 :            :                            profile_probability::always (), true);
    2758                 :       3064 :   free_original_copy_tables ();
    2759                 :            : 
    2760                 :      20624 :   for (unsigned i = 0; i < save_length; i++)
    2761                 :      17560 :     ifc_bbs[i]->aux = saved_preds[i];
    2762                 :            : 
    2763                 :       3064 :   if (new_loop == NULL)
    2764                 :            :     return NULL;
    2765                 :            : 
    2766                 :       3064 :   new_loop->dont_vectorize = true;
    2767                 :       3064 :   new_loop->force_vectorize = false;
    2768                 :       3064 :   gsi = gsi_last_bb (cond_bb);
    2769                 :       3064 :   gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
    2770                 :       3064 :   if (preds)
    2771                 :       3064 :     preds->safe_push (g);
    2772                 :       3064 :   gsi_insert_before (&gsi, g, GSI_SAME_STMT);
    2773                 :       3064 :   update_ssa (TODO_update_ssa);
    2774                 :       3064 :   return new_loop;
    2775                 :            : }
    2776                 :            : 
    2777                 :            : /* Return true when LOOP satisfies the follow conditions that will
    2778                 :            :    allow it to be recognized by the vectorizer for outer-loop
    2779                 :            :    vectorization:
    2780                 :            :     - The loop is not the root node of the loop tree.
    2781                 :            :     - The loop has exactly one inner loop.
    2782                 :            :     - The loop has a single exit.
    2783                 :            :     - The loop header has a single successor, which is the inner
    2784                 :            :       loop header.
    2785                 :            :     - Each of the inner and outer loop latches have a single
    2786                 :            :       predecessor.
    2787                 :            :     - The loop exit block has a single predecessor, which is the
    2788                 :            :       inner loop's exit block.  */
    2789                 :            : 
    2790                 :            : static bool
    2791                 :       3064 : versionable_outer_loop_p (class loop *loop)
    2792                 :            : {
    2793                 :       3064 :   if (!loop_outer (loop)
    2794                 :        490 :       || loop->dont_vectorize
    2795                 :        437 :       || !loop->inner
    2796                 :        437 :       || loop->inner->next
    2797                 :        132 :       || !single_exit (loop)
    2798                 :        111 :       || !single_succ_p (loop->header)
    2799                 :         53 :       || single_succ (loop->header) != loop->inner->header
    2800                 :         53 :       || !single_pred_p (loop->latch)
    2801                 :        543 :       || !single_pred_p (loop->inner->latch))
    2802                 :       3011 :     return false;
    2803                 :            : 
    2804                 :         53 :   basic_block outer_exit = single_pred (loop->latch);
    2805                 :         53 :   basic_block inner_exit = single_pred (loop->inner->latch);
    2806                 :            : 
    2807                 :        106 :   if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
    2808                 :            :     return false;
    2809                 :            : 
    2810                 :         53 :   if (dump_file)
    2811                 :          0 :     fprintf (dump_file, "Found vectorizable outer loop for versioning\n");
    2812                 :            : 
    2813                 :            :   return true;
    2814                 :            : }
    2815                 :            : 
    2816                 :            : /* Performs splitting of critical edges.  Skip splitting and return false
    2817                 :            :    if LOOP will not be converted because:
    2818                 :            : 
    2819                 :            :      - LOOP is not well formed.
    2820                 :            :      - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
    2821                 :            : 
    2822                 :            :    Last restriction is valid only if AGGRESSIVE_IF_CONV is false.  */
    2823                 :            : 
    2824                 :            : static bool
    2825                 :      72598 : ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv)
    2826                 :            : {
    2827                 :      72598 :   basic_block *body;
    2828                 :      72598 :   basic_block bb;
    2829                 :      72598 :   unsigned int num = loop->num_nodes;
    2830                 :      72598 :   unsigned int i;
    2831                 :      72598 :   gimple *stmt;
    2832                 :      72598 :   edge e;
    2833                 :      72598 :   edge_iterator ei;
    2834                 :      72598 :   auto_vec<edge> critical_edges;
    2835                 :            : 
    2836                 :            :   /* Loop is not well formed.  */
    2837                 :      72598 :   if (num <= 2 || loop->inner || !single_exit (loop))
    2838                 :      65433 :     return false;
    2839                 :            : 
    2840                 :       7165 :   body = get_loop_body (loop);
    2841                 :      48382 :   for (i = 0; i < num; i++)
    2842                 :            :     {
    2843                 :      41379 :       bb = body[i];
    2844                 :      41379 :       if (!aggressive_if_conv
    2845                 :      36640 :           && phi_nodes (bb)
    2846                 :      71739 :           && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
    2847                 :            :         {
    2848                 :        162 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2849                 :          0 :             fprintf (dump_file,
    2850                 :            :                      "BB %d has complicated PHI with more than %u args.\n",
    2851                 :            :                      bb->index, MAX_PHI_ARG_NUM);
    2852                 :            : 
    2853                 :        162 :           free (body);
    2854                 :        162 :           return false;
    2855                 :            :         }
    2856                 :      41217 :       if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
    2857                 :      14166 :         continue;
    2858                 :            : 
    2859                 :      27051 :       stmt = last_stmt (bb);
    2860                 :            :       /* Skip basic blocks not ending with conditional branch.  */
    2861                 :      27051 :       if (!stmt || gimple_code (stmt) != GIMPLE_COND)
    2862                 :      15550 :         continue;
    2863                 :            : 
    2864                 :      34503 :       FOR_EACH_EDGE (e, ei, bb->succs)
    2865                 :      28851 :         if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
    2866                 :       5849 :           critical_edges.safe_push (e);
    2867                 :            :     }
    2868                 :       7003 :   free (body);
    2869                 :            : 
    2870                 :      12841 :   while (critical_edges.length () > 0)
    2871                 :            :     {
    2872                 :       5838 :       e = critical_edges.pop ();
    2873                 :            :       /* Don't split if bb can be predicated along non-critical edge.  */
    2874                 :       5838 :       if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
    2875                 :       1731 :         split_edge (e);
    2876                 :            :     }
    2877                 :            : 
    2878                 :            :   return true;
    2879                 :            : }
    2880                 :            : 
    2881                 :            : /* Delete redundant statements produced by predication which prevents
    2882                 :            :    loop vectorization.  */
    2883                 :            : 
    2884                 :            : static void
    2885                 :       3131 : ifcvt_local_dce (class loop *loop)
    2886                 :            : {
    2887                 :       3131 :   gimple *stmt;
    2888                 :       3131 :   gimple *stmt1;
    2889                 :       3131 :   gimple *phi;
    2890                 :       3131 :   gimple_stmt_iterator gsi;
    2891                 :       3131 :   auto_vec<gimple *> worklist;
    2892                 :       3131 :   enum gimple_code code;
    2893                 :       3131 :   use_operand_p use_p;
    2894                 :       3131 :   imm_use_iterator imm_iter;
    2895                 :       3131 :   std::pair <tree, tree> *name_pair;
    2896                 :       3131 :   unsigned int i;
    2897                 :            : 
    2898                 :       3131 :   FOR_EACH_VEC_ELT (redundant_ssa_names, i, name_pair)
    2899                 :          0 :     replace_uses_by (name_pair->first, name_pair->second);
    2900                 :       3131 :   redundant_ssa_names.release ();
    2901                 :            : 
    2902                 :            :   /* The loop has a single BB only.  */
    2903                 :       3131 :   basic_block bb = loop->header;
    2904                 :       3131 :   tree latch_vdef = NULL_TREE;
    2905                 :            : 
    2906                 :       3131 :   worklist.create (64);
    2907                 :            :   /* Consider all phi as live statements.  */
    2908                 :      13302 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2909                 :            :     {
    2910                 :      10171 :       phi = gsi_stmt (gsi);
    2911                 :      10171 :       gimple_set_plf (phi, GF_PLF_2, true);
    2912                 :      10171 :       worklist.safe_push (phi);
    2913                 :      21973 :       if (virtual_operand_p (gimple_phi_result (phi)))
    2914                 :       1631 :         latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
    2915                 :            :     }
    2916                 :            :   /* Consider load/store statements, CALL and COND as live.  */
    2917                 :      57491 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2918                 :            :     {
    2919                 :      51229 :       stmt = gsi_stmt (gsi);
    2920                 :      51229 :       if (is_gimple_debug (stmt))
    2921                 :            :         {
    2922                 :       9759 :           gimple_set_plf (stmt, GF_PLF_2, true);
    2923                 :       9759 :           continue;
    2924                 :            :         }
    2925                 :      41470 :       if (gimple_store_p (stmt) || gimple_assign_load_p (stmt))
    2926                 :            :         {
    2927                 :       7812 :           gimple_set_plf (stmt, GF_PLF_2, true);
    2928                 :       7812 :           worklist.safe_push (stmt);
    2929                 :       7812 :           continue;
    2930                 :            :         }
    2931                 :      33658 :       code = gimple_code (stmt);
    2932                 :      33658 :       if (code == GIMPLE_COND || code == GIMPLE_CALL)
    2933                 :            :         {
    2934                 :       3811 :           gimple_set_plf (stmt, GF_PLF_2, true);
    2935                 :       3811 :           worklist.safe_push (stmt);
    2936                 :       3811 :           continue;
    2937                 :            :         }
    2938                 :      29847 :       gimple_set_plf (stmt, GF_PLF_2, false);
    2939                 :            : 
    2940                 :      29847 :       if (code == GIMPLE_ASSIGN)
    2941                 :            :         {
    2942                 :      29847 :           tree lhs = gimple_assign_lhs (stmt);
    2943                 :      68609 :           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
    2944                 :            :             {
    2945                 :      41046 :               stmt1 = USE_STMT (use_p);
    2946                 :      41046 :               if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb)
    2947                 :            :                 {
    2948                 :       2284 :                   gimple_set_plf (stmt, GF_PLF_2, true);
    2949                 :       2284 :                   worklist.safe_push (stmt);
    2950                 :       2284 :                   break;
    2951                 :            :                 }
    2952                 :            :             }
    2953                 :            :         }
    2954                 :            :     }
    2955                 :            :   /* Propagate liveness through arguments of live stmt.  */
    2956                 :      54012 :   while (worklist.length () > 0)
    2957                 :            :     {
    2958                 :      50881 :       ssa_op_iter iter;
    2959                 :      50881 :       use_operand_p use_p;
    2960                 :      50881 :       tree use;
    2961                 :            : 
    2962                 :      50881 :       stmt = worklist.pop ();
    2963                 :     179211 :       FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
    2964                 :            :         {
    2965                 :      77449 :           use = USE_FROM_PTR (use_p);
    2966                 :      77449 :           if (TREE_CODE (use) != SSA_NAME)
    2967                 :       6733 :             continue;
    2968                 :      70716 :           stmt1 = SSA_NAME_DEF_STMT (use);
    2969                 :      70716 :           if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2))
    2970                 :      43913 :             continue;
    2971                 :      26803 :           gimple_set_plf (stmt1, GF_PLF_2, true);
    2972                 :      26803 :           worklist.safe_push (stmt1);
    2973                 :            :         }
    2974                 :            :     }
    2975                 :            :   /* Delete dead statements.  */
    2976                 :       6262 :   gsi = gsi_last_bb (bb);
    2977                 :      54360 :   while (!gsi_end_p (gsi))
    2978                 :            :     {
    2979                 :      51229 :       gimple_stmt_iterator gsiprev = gsi;
    2980                 :      51229 :       gsi_prev (&gsiprev);
    2981                 :      51229 :       stmt = gsi_stmt (gsi);
    2982                 :      51229 :       if (gimple_store_p (stmt))
    2983                 :            :         {
    2984                 :       1808 :           tree lhs = gimple_get_lhs (stmt);
    2985                 :       1808 :           ao_ref write;
    2986                 :       1808 :           ao_ref_init (&write, lhs);
    2987                 :            : 
    2988                 :       1808 :           if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef)
    2989                 :            :               == DSE_STORE_DEAD)
    2990                 :         47 :             delete_dead_or_redundant_assignment (&gsi, "dead");
    2991                 :       1808 :           gsi = gsiprev;
    2992                 :       1808 :           continue;
    2993                 :            :         }
    2994                 :            : 
    2995                 :      49421 :       if (gimple_plf (stmt, GF_PLF_2))
    2996                 :            :         {
    2997                 :      48661 :           gsi = gsiprev;
    2998                 :      48661 :           continue;
    2999                 :            :         }
    3000                 :        760 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3001                 :            :         {
    3002                 :          5 :           fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
    3003                 :          5 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    3004                 :            :         }
    3005                 :        760 :       gsi_remove (&gsi, true);
    3006                 :        760 :       release_defs (stmt);
    3007                 :        760 :       gsi = gsiprev;
    3008                 :            :     }
    3009                 :       3131 : }
    3010                 :            : 
    3011                 :            : /* If-convert LOOP when it is legal.  For the moment this pass has no
    3012                 :            :    profitability analysis.  Returns non-zero todo flags when something
    3013                 :            :    changed.  */
    3014                 :            : 
    3015                 :            : unsigned int
    3016                 :      72545 : tree_if_conversion (class loop *loop, vec<gimple *> *preds)
    3017                 :            : {
    3018                 :      72545 :   unsigned int todo = 0;
    3019                 :      72598 :   bool aggressive_if_conv;
    3020                 :      72598 :   class loop *rloop;
    3021                 :      72598 :   bitmap exit_bbs;
    3022                 :            : 
    3023                 :      72598 :  again:
    3024                 :      72598 :   rloop = NULL;
    3025                 :      72598 :   ifc_bbs = NULL;
    3026                 :      72598 :   need_to_predicate = false;
    3027                 :      72598 :   any_complicated_phi = false;
    3028                 :            : 
    3029                 :            :   /* Apply more aggressive if-conversion when loop or its outer loop were
    3030                 :            :      marked with simd pragma.  When that's the case, we try to if-convert
    3031                 :            :      loop containing PHIs with more than MAX_PHI_ARG_NUM arguments.  */
    3032                 :      72598 :   aggressive_if_conv = loop->force_vectorize;
    3033                 :      72598 :   if (!aggressive_if_conv)
    3034                 :            :     {
    3035                 :      66015 :       class loop *outer_loop = loop_outer (loop);
    3036                 :      66015 :       if (outer_loop && outer_loop->force_vectorize)
    3037                 :        101 :         aggressive_if_conv = true;
    3038                 :            :     }
    3039                 :            : 
    3040                 :      72598 :   if (!ifcvt_split_critical_edges (loop, aggressive_if_conv))
    3041                 :      65595 :     goto cleanup;
    3042                 :            : 
    3043                 :       7003 :   if (!if_convertible_loop_p (loop)
    3044                 :       7003 :       || !dbg_cnt (if_conversion_tree))
    3045                 :       3871 :     goto cleanup;
    3046                 :            : 
    3047                 :       3132 :   if ((need_to_predicate || any_complicated_phi)
    3048                 :        470 :       && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
    3049                 :        469 :           || loop->dont_vectorize))
    3050                 :          1 :     goto cleanup;
    3051                 :            : 
    3052                 :            :   /* Since we have no cost model, always version loops unless the user
    3053                 :            :      specified -ftree-loop-if-convert or unless versioning is required.
    3054                 :            :      Either version this loop, or if the pattern is right for outer-loop
    3055                 :            :      vectorization, version the outer loop.  In the latter case we will
    3056                 :            :      still if-convert the original inner loop.  */
    3057                 :       3131 :   if (need_to_predicate
    3058                 :       2752 :       || any_complicated_phi
    3059                 :       2662 :       || flag_tree_loop_if_convert != 1)
    3060                 :            :     {
    3061                 :       3064 :       class loop *vloop
    3062                 :       6128 :         = (versionable_outer_loop_p (loop_outer (loop))
    3063                 :       3064 :            ? loop_outer (loop) : loop);
    3064                 :       3064 :       class loop *nloop = version_loop_for_if_conversion (vloop, preds);
    3065                 :       3064 :       if (nloop == NULL)
    3066                 :          0 :         goto cleanup;
    3067                 :       3064 :       if (vloop != loop)
    3068                 :            :         {
    3069                 :            :           /* If versionable_outer_loop_p decided to version the
    3070                 :            :              outer loop, version also the inner loop of the non-vectorized
    3071                 :            :              loop copy.  So we transform:
    3072                 :            :               loop1
    3073                 :            :                 loop2
    3074                 :            :              into:
    3075                 :            :               if (LOOP_VECTORIZED (1, 3))
    3076                 :            :                 {
    3077                 :            :                   loop1
    3078                 :            :                     loop2
    3079                 :            :                 }
    3080                 :            :               else
    3081                 :            :                 loop3 (copy of loop1)
    3082                 :            :                   if (LOOP_VECTORIZED (4, 5))
    3083                 :            :                     loop4 (copy of loop2)
    3084                 :            :                   else
    3085                 :            :                     loop5 (copy of loop4)  */
    3086                 :         53 :           gcc_assert (nloop->inner && nloop->inner->next == NULL);
    3087                 :            :           rloop = nloop->inner;
    3088                 :            :         }
    3089                 :            :     }
    3090                 :            : 
    3091                 :            :   /* Now all statements are if-convertible.  Combine all the basic
    3092                 :            :      blocks into one huge basic block doing the if-conversion
    3093                 :            :      on-the-fly.  */
    3094                 :       3131 :   combine_blocks (loop);
    3095                 :            : 
    3096                 :            :   /* Perform local CSE, this esp. helps the vectorizer analysis if loads
    3097                 :            :      and stores are involved.  CSE only the loop body, not the entry
    3098                 :            :      PHIs, those are to be kept in sync with the non-if-converted copy.
    3099                 :            :      ???  We'll still keep dead stores though.  */
    3100                 :       3131 :   exit_bbs = BITMAP_ALLOC (NULL);
    3101                 :       3131 :   bitmap_set_bit (exit_bbs, single_exit (loop)->dest->index);
    3102                 :       3131 :   bitmap_set_bit (exit_bbs, loop->latch->index);
    3103                 :       3131 :   todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs);
    3104                 :            : 
    3105                 :            :   /* Delete dead predicate computations.  */
    3106                 :       3131 :   ifcvt_local_dce (loop);
    3107                 :       3131 :   BITMAP_FREE (exit_bbs);
    3108                 :            : 
    3109                 :       3131 :   todo |= TODO_cleanup_cfg;
    3110                 :            : 
    3111                 :      72598 :  cleanup:
    3112                 :      72598 :   if (ifc_bbs)
    3113                 :            :     {
    3114                 :            :       unsigned int i;
    3115                 :            : 
    3116                 :      12298 :       for (i = 0; i < loop->num_nodes; i++)
    3117                 :      10568 :         free_bb_predicate (ifc_bbs[i]);
    3118                 :            : 
    3119                 :       1730 :       free (ifc_bbs);
    3120                 :       1730 :       ifc_bbs = NULL;
    3121                 :            :     }
    3122                 :      72598 :   if (rloop != NULL)
    3123                 :            :     {
    3124                 :         53 :       loop = rloop;
    3125                 :         53 :       goto again;
    3126                 :            :     }
    3127                 :            : 
    3128                 :      72545 :   return todo;
    3129                 :            : }
    3130                 :            : 
    3131                 :            : /* Tree if-conversion pass management.  */
    3132                 :            : 
    3133                 :            : namespace {
    3134                 :            : 
    3135                 :            : const pass_data pass_data_if_conversion =
    3136                 :            : {
    3137                 :            :   GIMPLE_PASS, /* type */
    3138                 :            :   "ifcvt", /* name */
    3139                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    3140                 :            :   TV_TREE_LOOP_IFCVT, /* tv_id */
    3141                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    3142                 :            :   0, /* properties_provided */
    3143                 :            :   0, /* properties_destroyed */
    3144                 :            :   0, /* todo_flags_start */
    3145                 :            :   0, /* todo_flags_finish */
    3146                 :            : };
    3147                 :            : 
    3148                 :            : class pass_if_conversion : public gimple_opt_pass
    3149                 :            : {
    3150                 :            : public:
    3151                 :     200540 :   pass_if_conversion (gcc::context *ctxt)
    3152                 :     401080 :     : gimple_opt_pass (pass_data_if_conversion, ctxt)
    3153                 :            :   {}
    3154                 :            : 
    3155                 :            :   /* opt_pass methods: */
    3156                 :            :   virtual bool gate (function *);
    3157                 :            :   virtual unsigned int execute (function *);
    3158                 :            : 
    3159                 :            : }; // class pass_if_conversion
    3160                 :            : 
    3161                 :            : bool
    3162                 :     157439 : pass_if_conversion::gate (function *fun)
    3163                 :            : {
    3164                 :     131554 :   return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
    3165                 :      33919 :            && flag_tree_loop_if_convert != 0)
    3166                 :     280965 :           || flag_tree_loop_if_convert == 1);
    3167                 :            : }
    3168                 :            : 
    3169                 :            : unsigned int
    3170                 :      33945 : pass_if_conversion::execute (function *fun)
    3171                 :            : {
    3172                 :      33945 :   class loop *loop;
    3173                 :      33945 :   unsigned todo = 0;
    3174                 :            : 
    3175                 :      67890 :   if (number_of_loops (fun) <= 1)
    3176                 :            :     return 0;
    3177                 :            : 
    3178                 :      33945 :   auto_vec<gimple *> preds;
    3179                 :     110987 :   FOR_EACH_LOOP (loop, 0)
    3180                 :      77042 :     if (flag_tree_loop_if_convert == 1
    3181                 :      76767 :         || ((flag_tree_loop_vectorize || loop->force_vectorize)
    3182                 :      72422 :             && !loop->dont_vectorize))
    3183                 :      72545 :       todo |= tree_if_conversion (loop, &preds);
    3184                 :            : 
    3185                 :      33945 :   if (todo)
    3186                 :            :     {
    3187                 :       1848 :       free_numbers_of_iterations_estimates (fun);
    3188                 :       1848 :       scev_reset ();
    3189                 :            :     }
    3190                 :            : 
    3191                 :      33945 :   if (flag_checking)
    3192                 :            :     {
    3193                 :      33943 :       basic_block bb;
    3194                 :     626663 :       FOR_EACH_BB_FN (bb, fun)
    3195                 :     592720 :         gcc_assert (!bb->aux);
    3196                 :            :     }
    3197                 :            : 
    3198                 :            :   /* Perform IL update now, it might elide some loops.  */
    3199                 :      33945 :   if (todo & TODO_cleanup_cfg)
    3200                 :            :     {
    3201                 :       1848 :       cleanup_tree_cfg ();
    3202                 :       1848 :       if (need_ssa_update_p (fun))
    3203                 :          0 :         todo |= TODO_update_ssa;
    3204                 :            :     }
    3205                 :      33945 :   if (todo & TODO_update_ssa_any)
    3206                 :          0 :     update_ssa (todo & TODO_update_ssa_any);
    3207                 :            : 
    3208                 :            :   /* If if-conversion elided the loop fall back to the original one.  */
    3209                 :      41863 :   for (unsigned i = 0; i < preds.length (); ++i)
    3210                 :            :     {
    3211                 :       3064 :       gimple *g = preds[i];
    3212                 :       3064 :       if (!gimple_bb (g))
    3213                 :          1 :         continue;
    3214                 :       3063 :       unsigned ifcvt_loop = tree_to_uhwi (gimple_call_arg (g, 0));
    3215                 :       3063 :       if (!get_loop (fun, ifcvt_loop))
    3216                 :            :         {
    3217                 :          0 :           if (dump_file)
    3218                 :          0 :             fprintf (dump_file, "If-converted loop vanished\n");
    3219                 :          0 :           fold_loop_internal_call (g, boolean_false_node);
    3220                 :            :         }
    3221                 :            :     }
    3222                 :            : 
    3223                 :      33945 :   return 0;
    3224                 :            : }
    3225                 :            : 
    3226                 :            : } // anon namespace
    3227                 :            : 
    3228                 :            : gimple_opt_pass *
    3229                 :     200540 : make_pass_if_conversion (gcc::context *ctxt)
    3230                 :            : {
    3231                 :     200540 :   return new pass_if_conversion (ctxt);
    3232                 :            : }

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.