LCOV - code coverage report
Current view: top level - gcc - tree-parloops.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 92.1 % 1873 1725
Test Date: 2024-09-28 13:20:55 Functions: 98.4 % 61 60
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Loop autoparallelization.
       2                 :             :    Copyright (C) 2006-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by Sebastian Pop <pop@cri.ensmp.fr> 
       4                 :             :    Zdenek Dvorak <dvorakz@suse.cz> and Razya Ladelsky <razya@il.ibm.com>.
       5                 :             : 
       6                 :             : This file is part of GCC.
       7                 :             : 
       8                 :             : GCC is free software; you can redistribute it and/or modify it under
       9                 :             : the terms of the GNU General Public License as published by the Free
      10                 :             : Software Foundation; either version 3, or (at your option) any later
      11                 :             : version.
      12                 :             : 
      13                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      14                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      15                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      16                 :             : for more details.
      17                 :             : 
      18                 :             : You should have received a copy of the GNU General Public License
      19                 :             : along with GCC; see the file COPYING3.  If not see
      20                 :             : <http://www.gnu.org/licenses/>.  */
      21                 :             : 
      22                 :             : #include "config.h"
      23                 :             : #define INCLUDE_MEMORY
      24                 :             : #include "system.h"
      25                 :             : #include "coretypes.h"
      26                 :             : #include "backend.h"
      27                 :             : #include "tree.h"
      28                 :             : #include "gimple.h"
      29                 :             : #include "cfghooks.h"
      30                 :             : #include "tree-pass.h"
      31                 :             : #include "ssa.h"
      32                 :             : #include "cgraph.h"
      33                 :             : #include "gimple-pretty-print.h"
      34                 :             : #include "fold-const.h"
      35                 :             : #include "gimplify.h"
      36                 :             : #include "gimple-iterator.h"
      37                 :             : #include "gimplify-me.h"
      38                 :             : #include "gimple-walk.h"
      39                 :             : #include "stor-layout.h"
      40                 :             : #include "tree-nested.h"
      41                 :             : #include "tree-cfg.h"
      42                 :             : #include "tree-ssa-loop-ivopts.h"
      43                 :             : #include "tree-ssa-loop-manip.h"
      44                 :             : #include "tree-ssa-loop-niter.h"
      45                 :             : #include "tree-ssa-loop.h"
      46                 :             : #include "tree-into-ssa.h"
      47                 :             : #include "cfgloop.h"
      48                 :             : #include "tree-scalar-evolution.h"
      49                 :             : #include "langhooks.h"
      50                 :             : #include "tree-vectorizer.h"
      51                 :             : #include "tree-hasher.h"
      52                 :             : #include "tree-parloops.h"
      53                 :             : #include "omp-general.h"
      54                 :             : #include "omp-low.h"
      55                 :             : #include "tree-ssa.h"
      56                 :             : #include "tree-ssa-alias.h"
      57                 :             : #include "tree-eh.h"
      58                 :             : #include "gomp-constants.h"
      59                 :             : #include "tree-dfa.h"
      60                 :             : #include "stringpool.h"
      61                 :             : #include "attribs.h"
      62                 :             : 
      63                 :             : /* This pass tries to distribute iterations of loops into several threads.
      64                 :             :    The implementation is straightforward -- for each loop we test whether its
      65                 :             :    iterations are independent, and if it is the case (and some additional
      66                 :             :    conditions regarding profitability and correctness are satisfied), we
      67                 :             :    add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
      68                 :             :    machinery do its job.
      69                 :             : 
      70                 :             :    The most of the complexity is in bringing the code into shape expected
      71                 :             :    by the omp expanders:
      72                 :             :    -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
      73                 :             :       variable and that the exit test is at the start of the loop body
      74                 :             :    -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
      75                 :             :       variables by accesses through pointers, and breaking up ssa chains
      76                 :             :       by storing the values incoming to the parallelized loop to a structure
      77                 :             :       passed to the new function as an argument (something similar is done
      78                 :             :       in omp gimplification, unfortunately only a small part of the code
      79                 :             :       can be shared).
      80                 :             : 
      81                 :             :    TODO:
      82                 :             :    -- if there are several parallelizable loops in a function, it may be
      83                 :             :       possible to generate the threads just once (using synchronization to
      84                 :             :       ensure that cross-loop dependences are obeyed).
      85                 :             :    -- handling of common reduction patterns for outer loops.  
      86                 :             :     
      87                 :             :    More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC  */
      88                 :             : /*
      89                 :             :   Reduction handling:
      90                 :             :   currently we use code inspired by vect_force_simple_reduction to detect
      91                 :             :   reduction patterns.
      92                 :             :   The code transformation will be introduced by an example.
      93                 :             : 
      94                 :             : 
      95                 :             : parloop
      96                 :             : {
      97                 :             :   int sum=1;
      98                 :             : 
      99                 :             :   for (i = 0; i < N; i++)
     100                 :             :    {
     101                 :             :     x[i] = i + 3;
     102                 :             :     sum+=x[i];
     103                 :             :    }
     104                 :             : }
     105                 :             : 
     106                 :             : gimple-like code:
     107                 :             : header_bb:
     108                 :             : 
     109                 :             :   # sum_29 = PHI <sum_11(5), 1(3)>
     110                 :             :   # i_28 = PHI <i_12(5), 0(3)>
     111                 :             :   D.1795_8 = i_28 + 3;
     112                 :             :   x[i_28] = D.1795_8;
     113                 :             :   sum_11 = D.1795_8 + sum_29;
     114                 :             :   i_12 = i_28 + 1;
     115                 :             :   if (N_6(D) > i_12)
     116                 :             :     goto header_bb;
     117                 :             : 
     118                 :             : 
     119                 :             : exit_bb:
     120                 :             : 
     121                 :             :   # sum_21 = PHI <sum_11(4)>
     122                 :             :   printf (&"%d"[0], sum_21);
     123                 :             : 
     124                 :             : 
     125                 :             : after reduction transformation (only relevant parts):
     126                 :             : 
     127                 :             : parloop
     128                 :             : {
     129                 :             : 
     130                 :             : ....
     131                 :             : 
     132                 :             : 
     133                 :             :   # Storing the initial value given by the user.  #
     134                 :             : 
     135                 :             :   .paral_data_store.32.sum.27 = 1;
     136                 :             : 
     137                 :             :   #pragma omp parallel num_threads(4)
     138                 :             : 
     139                 :             :   #pragma omp for schedule(static)
     140                 :             : 
     141                 :             :   # The neutral element corresponding to the particular
     142                 :             :   reduction's operation, e.g. 0 for PLUS_EXPR,
     143                 :             :   1 for MULT_EXPR, etc. replaces the user's initial value.  #
     144                 :             : 
     145                 :             :   # sum.27_29 = PHI <sum.27_11, 0>
     146                 :             : 
     147                 :             :   sum.27_11 = D.1827_8 + sum.27_29;
     148                 :             : 
     149                 :             :   GIMPLE_OMP_CONTINUE
     150                 :             : 
     151                 :             :   # Adding this reduction phi is done at create_phi_for_local_result() #
     152                 :             :   # sum.27_56 = PHI <sum.27_11, 0>
     153                 :             :   GIMPLE_OMP_RETURN
     154                 :             : 
     155                 :             :   # Creating the atomic operation is done at
     156                 :             :   create_call_for_reduction_1()  #
     157                 :             : 
     158                 :             :   #pragma omp atomic_load
     159                 :             :   D.1839_59 = *&.paral_data_load.33_51->reduction.23;
     160                 :             :   D.1840_60 = sum.27_56 + D.1839_59;
     161                 :             :   #pragma omp atomic_store (D.1840_60);
     162                 :             : 
     163                 :             :   GIMPLE_OMP_RETURN
     164                 :             : 
     165                 :             :  # collecting the result after the join of the threads is done at
     166                 :             :   create_loads_for_reductions().
     167                 :             :   The value computed by the threads is loaded from the
     168                 :             :   shared struct.  #
     169                 :             : 
     170                 :             : 
     171                 :             :   .paral_data_load.33_52 = &.paral_data_store.32;
     172                 :             :   sum_37 =  .paral_data_load.33_52->sum.27;
     173                 :             :   sum_43 = D.1795_41 + sum_37;
     174                 :             : 
     175                 :             :   exit bb:
     176                 :             :   # sum_21 = PHI <sum_43, sum_26>
     177                 :             :   printf (&"%d"[0], sum_21);
     178                 :             : 
     179                 :             : ...
     180                 :             : 
     181                 :             : }
     182                 :             : 
     183                 :             : */
     184                 :             : 
     185                 :             : /* Error reporting helper for parloops_is_simple_reduction below.  GIMPLE
     186                 :             :    statement STMT is printed with a message MSG. */
     187                 :             : 
     188                 :             : static void
     189                 :          69 : report_ploop_op (dump_flags_t msg_type, gimple *stmt, const char *msg)
     190                 :             : {
     191                 :          69 :   dump_printf_loc (msg_type, vect_location, "%s%G", msg, stmt);
     192                 :          69 : }
     193                 :             : 
     194                 :             : /* DEF_STMT_INFO occurs in a loop that contains a potential reduction
     195                 :             :    operation.  Return true if the results of DEF_STMT_INFO are something
     196                 :             :    that can be accumulated by such a reduction.  */
     197                 :             : 
     198                 :             : static bool
     199                 :          84 : parloops_valid_reduction_input_p (stmt_vec_info def_stmt_info)
     200                 :             : {
     201                 :          84 :   return (is_gimple_assign (def_stmt_info->stmt)
     202                 :           2 :           || is_gimple_call (def_stmt_info->stmt)
     203                 :           2 :           || STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_induction_def
     204                 :          86 :           || (gimple_code (def_stmt_info->stmt) == GIMPLE_PHI
     205                 :           2 :               && STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_internal_def
     206                 :           2 :               && !is_loop_header_bb_p (gimple_bb (def_stmt_info->stmt))));
     207                 :             : }
     208                 :             : 
     209                 :             : /* Detect SLP reduction of the form:
     210                 :             : 
     211                 :             :    #a1 = phi <a5, a0>
     212                 :             :    a2 = operation (a1)
     213                 :             :    a3 = operation (a2)
     214                 :             :    a4 = operation (a3)
     215                 :             :    a5 = operation (a4)
     216                 :             : 
     217                 :             :    #a = phi <a5>
     218                 :             : 
     219                 :             :    PHI is the reduction phi node (#a1 = phi <a5, a0> above)
     220                 :             :    FIRST_STMT is the first reduction stmt in the chain
     221                 :             :    (a2 = operation (a1)).
     222                 :             : 
     223                 :             :    Return TRUE if a reduction chain was detected.  */
     224                 :             : 
     225                 :             : static bool
     226                 :           1 : parloops_is_slp_reduction (loop_vec_info loop_info, gimple *phi,
     227                 :             :                            gimple *first_stmt)
     228                 :             : {
     229                 :           1 :   class loop *loop = (gimple_bb (phi))->loop_father;
     230                 :           1 :   class loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
     231                 :           1 :   enum tree_code code;
     232                 :           1 :   gimple *loop_use_stmt = NULL;
     233                 :           1 :   stmt_vec_info use_stmt_info;
     234                 :           1 :   tree lhs;
     235                 :           1 :   imm_use_iterator imm_iter;
     236                 :           1 :   use_operand_p use_p;
     237                 :           1 :   int nloop_uses, size = 0, n_out_of_loop_uses;
     238                 :           1 :   bool found = false;
     239                 :             : 
     240                 :           1 :   if (loop != vect_loop)
     241                 :             :     return false;
     242                 :             : 
     243                 :           1 :   auto_vec<stmt_vec_info, 8> reduc_chain;
     244                 :           1 :   lhs = PHI_RESULT (phi);
     245                 :           1 :   code = gimple_assign_rhs_code (first_stmt);
     246                 :           5 :   while (1)
     247                 :             :     {
     248                 :           3 :       nloop_uses = 0;
     249                 :           3 :       n_out_of_loop_uses = 0;
     250                 :           6 :       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
     251                 :             :         {
     252                 :           4 :           gimple *use_stmt = USE_STMT (use_p);
     253                 :           4 :           if (is_gimple_debug (use_stmt))
     254                 :           0 :             continue;
     255                 :             : 
     256                 :             :           /* Check if we got back to the reduction phi.  */
     257                 :           4 :           if (use_stmt == phi)
     258                 :             :             {
     259                 :             :               loop_use_stmt = use_stmt;
     260                 :             :               found = true;
     261                 :             :               break;
     262                 :             :             }
     263                 :             : 
     264                 :           3 :           if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
     265                 :             :             {
     266                 :           2 :               loop_use_stmt = use_stmt;
     267                 :           2 :               nloop_uses++;
     268                 :             :             }
     269                 :             :            else
     270                 :           1 :              n_out_of_loop_uses++;
     271                 :             : 
     272                 :             :            /* There are can be either a single use in the loop or two uses in
     273                 :             :               phi nodes.  */
     274                 :           3 :            if (nloop_uses > 1 || (n_out_of_loop_uses && nloop_uses))
     275                 :             :              return false;
     276                 :             :         }
     277                 :             : 
     278                 :           3 :       if (found)
     279                 :             :         break;
     280                 :             : 
     281                 :             :       /* We reached a statement with no loop uses.  */
     282                 :           2 :       if (nloop_uses == 0)
     283                 :             :         return false;
     284                 :             : 
     285                 :             :       /* This is a loop exit phi, and we haven't reached the reduction phi.  */
     286                 :           2 :       if (gimple_code (loop_use_stmt) == GIMPLE_PHI)
     287                 :             :         return false;
     288                 :             : 
     289                 :           2 :       if (!is_gimple_assign (loop_use_stmt)
     290                 :           2 :           || code != gimple_assign_rhs_code (loop_use_stmt)
     291                 :           4 :           || !flow_bb_inside_loop_p (loop, gimple_bb (loop_use_stmt)))
     292                 :           0 :         return false;
     293                 :             : 
     294                 :             :       /* Insert USE_STMT into reduction chain.  */
     295                 :           2 :       use_stmt_info = loop_info->lookup_stmt (loop_use_stmt);
     296                 :           2 :       reduc_chain.safe_push (use_stmt_info);
     297                 :             : 
     298                 :           2 :       lhs = gimple_assign_lhs (loop_use_stmt);
     299                 :           2 :       size++;
     300                 :           2 :    }
     301                 :             : 
     302                 :           1 :   if (!found || loop_use_stmt != phi || size < 2)
     303                 :             :     return false;
     304                 :             : 
     305                 :             :   /* Swap the operands, if needed, to make the reduction operand be the second
     306                 :             :      operand.  */
     307                 :           1 :   lhs = PHI_RESULT (phi);
     308                 :           6 :   for (unsigned i = 0; i < reduc_chain.length (); ++i)
     309                 :             :     {
     310                 :           2 :       gassign *next_stmt = as_a <gassign *> (reduc_chain[i]->stmt);
     311                 :           4 :       if (gimple_assign_rhs2 (next_stmt) == lhs)
     312                 :             :         {
     313                 :           2 :           tree op = gimple_assign_rhs1 (next_stmt);
     314                 :           2 :           stmt_vec_info def_stmt_info = loop_info->lookup_def (op);
     315                 :             : 
     316                 :             :           /* Check that the other def is either defined in the loop
     317                 :             :              ("vect_internal_def"), or it's an induction (defined by a
     318                 :             :              loop-header phi-node).  */
     319                 :           4 :           if (def_stmt_info
     320                 :           2 :               && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt))
     321                 :           4 :               && parloops_valid_reduction_input_p (def_stmt_info))
     322                 :             :             {
     323                 :           2 :               lhs = gimple_assign_lhs (next_stmt);
     324                 :           2 :               continue;
     325                 :             :             }
     326                 :             : 
     327                 :           0 :           return false;
     328                 :             :         }
     329                 :             :       else
     330                 :             :         {
     331                 :           0 :           tree op = gimple_assign_rhs2 (next_stmt);
     332                 :           0 :           stmt_vec_info def_stmt_info = loop_info->lookup_def (op);
     333                 :             : 
     334                 :             :           /* Check that the other def is either defined in the loop
     335                 :             :             ("vect_internal_def"), or it's an induction (defined by a
     336                 :             :             loop-header phi-node).  */
     337                 :           0 :           if (def_stmt_info
     338                 :           0 :               && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt))
     339                 :           0 :               && parloops_valid_reduction_input_p (def_stmt_info))
     340                 :             :             {
     341                 :           0 :               if (dump_enabled_p ())
     342                 :           0 :                 dump_printf_loc (MSG_NOTE, vect_location,
     343                 :             :                                  "swapping oprnds: %G", (gimple *) next_stmt);
     344                 :             : 
     345                 :           0 :               swap_ssa_operands (next_stmt,
     346                 :             :                                  gimple_assign_rhs1_ptr (next_stmt),
     347                 :             :                                  gimple_assign_rhs2_ptr (next_stmt));
     348                 :           0 :               update_stmt (next_stmt);
     349                 :             :             }
     350                 :             :           else
     351                 :           0 :             return false;
     352                 :             :         }
     353                 :             : 
     354                 :           0 :       lhs = gimple_assign_lhs (next_stmt);
     355                 :             :     }
     356                 :             : 
     357                 :             :   /* Build up the actual chain.  */
     358                 :           2 :   for (unsigned i = 0; i < reduc_chain.length () - 1; ++i)
     359                 :             :     {
     360                 :           1 :       REDUC_GROUP_FIRST_ELEMENT (reduc_chain[i]) = reduc_chain[0];
     361                 :           1 :       REDUC_GROUP_NEXT_ELEMENT (reduc_chain[i]) = reduc_chain[i+1];
     362                 :             :     }
     363                 :           1 :   REDUC_GROUP_FIRST_ELEMENT (reduc_chain.last ()) = reduc_chain[0];
     364                 :           1 :   REDUC_GROUP_NEXT_ELEMENT (reduc_chain.last ()) = NULL;
     365                 :             : 
     366                 :             :   /* Save the chain for further analysis in SLP detection.  */
     367                 :           1 :   LOOP_VINFO_REDUCTION_CHAINS (loop_info).safe_push (reduc_chain[0]);
     368                 :           1 :   REDUC_GROUP_SIZE (reduc_chain[0]) = size;
     369                 :             : 
     370                 :           1 :   return true;
     371                 :           1 : }
     372                 :             : 
     373                 :             : /* Return true if we need an in-order reduction for operation CODE
     374                 :             :    on type TYPE.  NEED_WRAPPING_INTEGRAL_OVERFLOW is true if integer
     375                 :             :    overflow must wrap.  */
     376                 :             : 
     377                 :             : static bool
     378                 :         106 : parloops_needs_fold_left_reduction_p (tree type, tree_code code,
     379                 :             :                                       bool need_wrapping_integral_overflow)
     380                 :             : {
     381                 :             :   /* CHECKME: check for !flag_finite_math_only too?  */
     382                 :         106 :   if (SCALAR_FLOAT_TYPE_P (type))
     383                 :          27 :     switch (code)
     384                 :             :       {
     385                 :             :       case MIN_EXPR:
     386                 :             :       case MAX_EXPR:
     387                 :             :         return false;
     388                 :             : 
     389                 :          27 :       default:
     390                 :          27 :         return !flag_associative_math;
     391                 :             :       }
     392                 :             : 
     393                 :          79 :   if (INTEGRAL_TYPE_P (type))
     394                 :             :     {
     395                 :          75 :       if (!operation_no_trapping_overflow (type, code))
     396                 :             :         return true;
     397                 :          75 :       if (need_wrapping_integral_overflow
     398                 :          75 :           && !TYPE_OVERFLOW_WRAPS (type)
     399                 :         100 :           && operation_can_overflow (code))
     400                 :             :         return true;
     401                 :          58 :       return false;
     402                 :             :     }
     403                 :             : 
     404                 :           4 :   if (SAT_FIXED_POINT_TYPE_P (type))
     405                 :             :     return true;
     406                 :             : 
     407                 :             :   return false;
     408                 :             : }
     409                 :             : 
     410                 :             : 
     411                 :             : /* Function parloops_is_simple_reduction
     412                 :             : 
     413                 :             :    (1) Detect a cross-iteration def-use cycle that represents a simple
     414                 :             :    reduction computation.  We look for the following pattern:
     415                 :             : 
     416                 :             :    loop_header:
     417                 :             :      a1 = phi < a0, a2 >
     418                 :             :      a3 = ...
     419                 :             :      a2 = operation (a3, a1)
     420                 :             : 
     421                 :             :    or
     422                 :             : 
     423                 :             :    a3 = ...
     424                 :             :    loop_header:
     425                 :             :      a1 = phi < a0, a2 >
     426                 :             :      a2 = operation (a3, a1)
     427                 :             : 
     428                 :             :    such that:
     429                 :             :    1. operation is commutative and associative and it is safe to
     430                 :             :       change the order of the computation
     431                 :             :    2. no uses for a2 in the loop (a2 is used out of the loop)
     432                 :             :    3. no uses of a1 in the loop besides the reduction operation
     433                 :             :    4. no uses of a1 outside the loop.
     434                 :             : 
     435                 :             :    Conditions 1,4 are tested here.
     436                 :             :    Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
     437                 :             : 
     438                 :             :    (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
     439                 :             :    nested cycles.
     440                 :             : 
     441                 :             :    (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
     442                 :             :    reductions:
     443                 :             : 
     444                 :             :      a1 = phi < a0, a2 >
     445                 :             :      inner loop (def of a3)
     446                 :             :      a2 = phi < a3 >
     447                 :             : 
     448                 :             :    (4) Detect condition expressions, ie:
     449                 :             :      for (int i = 0; i < N; i++)
     450                 :             :        if (a[i] < val)
     451                 :             :         ret_val = a[i];
     452                 :             : 
     453                 :             : */
     454                 :             : 
     455                 :             : static stmt_vec_info
     456                 :         135 : parloops_is_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
     457                 :             :                           bool *double_reduc,
     458                 :             :                           bool need_wrapping_integral_overflow,
     459                 :             :                           enum vect_reduction_type *v_reduc_type)
     460                 :             : {
     461                 :         135 :   gphi *phi = as_a <gphi *> (phi_info->stmt);
     462                 :         135 :   class loop *loop = (gimple_bb (phi))->loop_father;
     463                 :         135 :   class loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
     464                 :         135 :   bool nested_in_vect_loop = flow_loop_nested_p (vect_loop, loop);
     465                 :         135 :   gimple *phi_use_stmt = NULL;
     466                 :         135 :   enum tree_code orig_code, code;
     467                 :         135 :   tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
     468                 :         135 :   tree type;
     469                 :         135 :   tree name;
     470                 :         135 :   imm_use_iterator imm_iter;
     471                 :         135 :   use_operand_p use_p;
     472                 :         135 :   bool phi_def;
     473                 :             : 
     474                 :         135 :   *double_reduc = false;
     475                 :         135 :   *v_reduc_type = TREE_CODE_REDUCTION;
     476                 :             : 
     477                 :         135 :   tree phi_name = PHI_RESULT (phi);
     478                 :             :   /* ???  If there are no uses of the PHI result the inner loop reduction
     479                 :             :      won't be detected as possibly double-reduction by vectorizable_reduction
     480                 :             :      because that tries to walk the PHI arg from the preheader edge which
     481                 :             :      can be constant.  See PR60382.  */
     482                 :         135 :   if (has_zero_uses (phi_name))
     483                 :             :     return NULL;
     484                 :         135 :   unsigned nphi_def_loop_uses = 0;
     485                 :         285 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, phi_name)
     486                 :             :     {
     487                 :         150 :       gimple *use_stmt = USE_STMT (use_p);
     488                 :         150 :       if (is_gimple_debug (use_stmt))
     489                 :           3 :         continue;
     490                 :             : 
     491                 :         147 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
     492                 :             :         {
     493                 :           0 :           if (dump_enabled_p ())
     494                 :           0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
     495                 :             :                              "intermediate value used outside loop.\n");
     496                 :             : 
     497                 :           0 :           return NULL;
     498                 :             :         }
     499                 :             : 
     500                 :         147 :       nphi_def_loop_uses++;
     501                 :         147 :       phi_use_stmt = use_stmt;
     502                 :             :     }
     503                 :             : 
     504                 :         135 :   edge latch_e = loop_latch_edge (loop);
     505                 :         135 :   tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
     506                 :         135 :   if (TREE_CODE (loop_arg) != SSA_NAME)
     507                 :             :     {
     508                 :           0 :       if (dump_enabled_p ())
     509                 :           0 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
     510                 :             :                          "reduction: not ssa_name: %T\n", loop_arg);
     511                 :           0 :       return NULL;
     512                 :             :     }
     513                 :             : 
     514                 :         135 :   stmt_vec_info def_stmt_info = loop_info->lookup_def (loop_arg);
     515                 :         135 :   if (!def_stmt_info
     516                 :         135 :       || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt)))
     517                 :           0 :     return NULL;
     518                 :             : 
     519                 :         135 :   if (gassign *def_stmt = dyn_cast <gassign *> (def_stmt_info->stmt))
     520                 :             :     {
     521                 :         120 :       name = gimple_assign_lhs (def_stmt);
     522                 :         120 :       phi_def = false;
     523                 :             :     }
     524                 :          15 :   else if (gphi *def_stmt = dyn_cast <gphi *> (def_stmt_info->stmt))
     525                 :             :     {
     526                 :          15 :       name = PHI_RESULT (def_stmt);
     527                 :          15 :       phi_def = true;
     528                 :             :     }
     529                 :             :   else
     530                 :             :     {
     531                 :           0 :       if (dump_enabled_p ())
     532                 :           0 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
     533                 :             :                          "reduction: unhandled reduction operation: %G",
     534                 :             :                          def_stmt_info->stmt);
     535                 :           0 :       return NULL;
     536                 :             :     }
     537                 :             : 
     538                 :         135 :   unsigned nlatch_def_loop_uses = 0;
     539                 :         135 :   auto_vec<gphi *, 3> lcphis;
     540                 :         135 :   bool inner_loop_of_double_reduc = false;
     541                 :         408 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
     542                 :             :     {
     543                 :         273 :       gimple *use_stmt = USE_STMT (use_p);
     544                 :         273 :       if (is_gimple_debug (use_stmt))
     545                 :           6 :         continue;
     546                 :         267 :       if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
     547                 :         139 :         nlatch_def_loop_uses++;
     548                 :             :       else
     549                 :             :         {
     550                 :             :           /* We can have more than one loop-closed PHI.  */
     551                 :         128 :           lcphis.safe_push (as_a <gphi *> (use_stmt));
     552                 :         128 :           if (nested_in_vect_loop
     553                 :         128 :               && (STMT_VINFO_DEF_TYPE (loop_info->lookup_stmt (use_stmt))
     554                 :             :                   == vect_double_reduction_def))
     555                 :             :             inner_loop_of_double_reduc = true;
     556                 :             :         }
     557                 :             :     }
     558                 :             : 
     559                 :             :   /* If this isn't a nested cycle or if the nested cycle reduction value
     560                 :             :      is used ouside of the inner loop we cannot handle uses of the reduction
     561                 :             :      value.  */
     562                 :         135 :   if ((!nested_in_vect_loop || inner_loop_of_double_reduc)
     563                 :         135 :       && (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1))
     564                 :             :     {
     565                 :          12 :       if (dump_enabled_p ())
     566                 :          12 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
     567                 :             :                          "reduction used in loop.\n");
     568                 :          12 :       return NULL;
     569                 :             :     }
     570                 :             : 
     571                 :             :   /* If DEF_STMT is a phi node itself, we expect it to have a single argument
     572                 :             :      defined in the inner loop.  */
     573                 :         123 :   if (phi_def)
     574                 :             :     {
     575                 :          15 :       gphi *def_stmt = as_a <gphi *> (def_stmt_info->stmt);
     576                 :          15 :       op1 = PHI_ARG_DEF (def_stmt, 0);
     577                 :             : 
     578                 :          15 :       if (gimple_phi_num_args (def_stmt) != 1
     579                 :          15 :           || TREE_CODE (op1) != SSA_NAME)
     580                 :             :         {
     581                 :           0 :           if (dump_enabled_p ())
     582                 :           0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
     583                 :             :                              "unsupported phi node definition.\n");
     584                 :             : 
     585                 :           0 :           return NULL;
     586                 :             :         }
     587                 :             : 
     588                 :          15 :       gimple *def1 = SSA_NAME_DEF_STMT (op1);
     589                 :          15 :       if (gimple_bb (def1)
     590                 :          15 :           && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
     591                 :          15 :           && loop->inner
     592                 :          15 :           && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
     593                 :          15 :           && is_gimple_assign (def1)
     594                 :          15 :           && is_a <gphi *> (phi_use_stmt)
     595                 :          30 :           && flow_bb_inside_loop_p (loop->inner, gimple_bb (phi_use_stmt)))
     596                 :             :         {
     597                 :          15 :           if (dump_enabled_p ())
     598                 :          14 :             report_ploop_op (MSG_NOTE, def_stmt,
     599                 :             :                              "detected double reduction: ");
     600                 :             : 
     601                 :          15 :           *double_reduc = true;
     602                 :          15 :           return def_stmt_info;
     603                 :             :         }
     604                 :             : 
     605                 :           0 :       return NULL;
     606                 :             :     }
     607                 :             : 
     608                 :             :   /* If we are vectorizing an inner reduction we are executing that
     609                 :             :      in the original order only in case we are not dealing with a
     610                 :             :      double reduction.  */
     611                 :         108 :   bool check_reduction = true;
     612                 :         108 :   if (flow_loop_nested_p (vect_loop, loop))
     613                 :             :     {
     614                 :             :       gphi *lcphi;
     615                 :             :       unsigned i;
     616                 :             :       check_reduction = false;
     617                 :           0 :       FOR_EACH_VEC_ELT (lcphis, i, lcphi)
     618                 :           0 :         FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (lcphi))
     619                 :             :           {
     620                 :           0 :             gimple *use_stmt = USE_STMT (use_p);
     621                 :           0 :             if (is_gimple_debug (use_stmt))
     622                 :           0 :               continue;
     623                 :           0 :             if (! flow_bb_inside_loop_p (vect_loop, gimple_bb (use_stmt)))
     624                 :           0 :               check_reduction = true;
     625                 :             :           }
     626                 :             :     }
     627                 :             : 
     628                 :         108 :   gassign *def_stmt = as_a <gassign *> (def_stmt_info->stmt);
     629                 :         108 :   code = orig_code = gimple_assign_rhs_code (def_stmt);
     630                 :             : 
     631                 :         108 :   if (nested_in_vect_loop && !check_reduction)
     632                 :             :     {
     633                 :             :       /* FIXME: Even for non-reductions code generation is funneled
     634                 :             :          through vectorizable_reduction for the stmt defining the
     635                 :             :          PHI latch value.  So we have to artificially restrict ourselves
     636                 :             :          for the supported operations.  */
     637                 :           0 :       switch (get_gimple_rhs_class (code))
     638                 :             :         {
     639                 :           0 :         case GIMPLE_BINARY_RHS:
     640                 :           0 :         case GIMPLE_TERNARY_RHS:
     641                 :           0 :           break;
     642                 :           0 :         default:
     643                 :             :           /* Not supported by vectorizable_reduction.  */
     644                 :           0 :           if (dump_enabled_p ())
     645                 :           0 :             report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
     646                 :             :                              "nested cycle: not handled operation: ");
     647                 :           0 :           return NULL;
     648                 :             :         }
     649                 :           0 :       if (dump_enabled_p ())
     650                 :           0 :         report_ploop_op (MSG_NOTE, def_stmt, "detected nested cycle: ");
     651                 :           0 :       return def_stmt_info;
     652                 :             :     }
     653                 :             : 
     654                 :             :   /* We can handle "res -= x[i]", which is non-associative by
     655                 :             :      simply rewriting this into "res += -x[i]".  Avoid changing
     656                 :             :      gimple instruction for the first simple tests and only do this
     657                 :             :      if we're allowed to change code at all.  */
     658                 :         128 :   if (code == MINUS_EXPR && gimple_assign_rhs2 (def_stmt) != phi_name)
     659                 :             :     code = PLUS_EXPR;
     660                 :             : 
     661                 :          88 :   if (code == COND_EXPR)
     662                 :             :     {
     663                 :           0 :       if (! nested_in_vect_loop)
     664                 :           0 :         *v_reduc_type = COND_REDUCTION;
     665                 :             : 
     666                 :           0 :       op3 = gimple_assign_rhs1 (def_stmt);
     667                 :           0 :       if (COMPARISON_CLASS_P (op3))
     668                 :             :         {
     669                 :           0 :           op4 = TREE_OPERAND (op3, 1);
     670                 :           0 :           op3 = TREE_OPERAND (op3, 0);
     671                 :             :         }
     672                 :           0 :       if (op3 == phi_name || op4 == phi_name)
     673                 :             :         {
     674                 :           0 :           if (dump_enabled_p ())
     675                 :           0 :             report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
     676                 :             :                              "reduction: condition depends on previous"
     677                 :             :                              " iteration: ");
     678                 :           0 :           return NULL;
     679                 :             :         }
     680                 :             : 
     681                 :           0 :       op1 = gimple_assign_rhs2 (def_stmt);
     682                 :           0 :       op2 = gimple_assign_rhs3 (def_stmt);
     683                 :             :     }
     684                 :         108 :   else if (!commutative_tree_code (code) || !associative_tree_code (code))
     685                 :             :     {
     686                 :           2 :       if (dump_enabled_p ())
     687                 :           2 :         report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
     688                 :             :                          "reduction: not commutative/associative: ");
     689                 :           2 :       return NULL;
     690                 :             :     }
     691                 :         106 :   else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
     692                 :             :     {
     693                 :         106 :       op1 = gimple_assign_rhs1 (def_stmt);
     694                 :         106 :       op2 = gimple_assign_rhs2 (def_stmt);
     695                 :             :     }
     696                 :             :   else
     697                 :             :     {
     698                 :           0 :       if (dump_enabled_p ())
     699                 :           0 :         report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
     700                 :             :                          "reduction: not handled operation: ");
     701                 :           0 :       return NULL;
     702                 :             :     }
     703                 :             : 
     704                 :         106 :   if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
     705                 :             :     {
     706                 :           0 :       if (dump_enabled_p ())
     707                 :           0 :         report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
     708                 :             :                          "reduction: both uses not ssa_names: ");
     709                 :             : 
     710                 :           0 :       return NULL;
     711                 :             :     }
     712                 :             : 
     713                 :         106 :   type = TREE_TYPE (gimple_assign_lhs (def_stmt));
     714                 :         106 :   if ((TREE_CODE (op1) == SSA_NAME
     715                 :         106 :        && !types_compatible_p (type,TREE_TYPE (op1)))
     716                 :         106 :       || (TREE_CODE (op2) == SSA_NAME
     717                 :         103 :           && !types_compatible_p (type, TREE_TYPE (op2)))
     718                 :         106 :       || (op3 && TREE_CODE (op3) == SSA_NAME
     719                 :           0 :           && !types_compatible_p (type, TREE_TYPE (op3)))
     720                 :         212 :       || (op4 && TREE_CODE (op4) == SSA_NAME
     721                 :           0 :           && !types_compatible_p (type, TREE_TYPE (op4))))
     722                 :             :     {
     723                 :           0 :       if (dump_enabled_p ())
     724                 :             :         {
     725                 :           0 :           dump_printf_loc (MSG_NOTE, vect_location,
     726                 :             :                            "reduction: multiple types: operation type: "
     727                 :             :                            "%T, operands types: %T,%T",
     728                 :           0 :                            type,  TREE_TYPE (op1), TREE_TYPE (op2));
     729                 :           0 :           if (op3)
     730                 :           0 :             dump_printf (MSG_NOTE, ",%T", TREE_TYPE (op3));
     731                 :             : 
     732                 :           0 :           if (op4)
     733                 :           0 :             dump_printf (MSG_NOTE, ",%T", TREE_TYPE (op4));
     734                 :           0 :           dump_printf (MSG_NOTE, "\n");
     735                 :             :         }
     736                 :             : 
     737                 :           0 :       return NULL;
     738                 :             :     }
     739                 :             : 
     740                 :             :   /* Check whether it's ok to change the order of the computation.
     741                 :             :      Generally, when vectorizing a reduction we change the order of the
     742                 :             :      computation.  This may change the behavior of the program in some
     743                 :             :      cases, so we need to check that this is ok.  One exception is when
     744                 :             :      vectorizing an outer-loop: the inner-loop is executed sequentially,
     745                 :             :      and therefore vectorizing reductions in the inner-loop during
     746                 :             :      outer-loop vectorization is safe.  */
     747                 :         106 :   if (check_reduction
     748                 :         106 :       && *v_reduc_type == TREE_CODE_REDUCTION
     749                 :         212 :       && parloops_needs_fold_left_reduction_p (type, code,
     750                 :             :                                                need_wrapping_integral_overflow))
     751                 :          19 :     *v_reduc_type = FOLD_LEFT_REDUCTION;
     752                 :             : 
     753                 :             :   /* Reduction is safe. We're dealing with one of the following:
     754                 :             :      1) integer arithmetic and no trapv
     755                 :             :      2) floating point arithmetic, and special flags permit this optimization
     756                 :             :      3) nested cycle (i.e., outer loop vectorization).  */
     757                 :         106 :   stmt_vec_info def1_info = loop_info->lookup_def (op1);
     758                 :         106 :   stmt_vec_info def2_info = loop_info->lookup_def (op2);
     759                 :         106 :   if (code != COND_EXPR && !def1_info && !def2_info)
     760                 :             :     {
     761                 :           0 :       if (dump_enabled_p ())
     762                 :           0 :         report_ploop_op (MSG_NOTE, def_stmt,
     763                 :             :                          "reduction: no defs for operands: ");
     764                 :           0 :       return NULL;
     765                 :             :     }
     766                 :             : 
     767                 :             :   /* Check that one def is the reduction def, defined by PHI,
     768                 :             :      the other def is either defined in the loop ("vect_internal_def"),
     769                 :             :      or it's an induction (defined by a loop-header phi-node).  */
     770                 :             : 
     771                 :         106 :   if (def2_info
     772                 :         103 :       && def2_info->stmt == phi
     773                 :         106 :       && (code == COND_EXPR
     774                 :          78 :           || !def1_info
     775                 :          78 :           || !flow_bb_inside_loop_p (loop, gimple_bb (def1_info->stmt))
     776                 :          78 :           || parloops_valid_reduction_input_p (def1_info)))
     777                 :             :     {
     778                 :          78 :       if (dump_enabled_p ())
     779                 :          49 :         report_ploop_op (MSG_NOTE, def_stmt, "detected reduction: ");
     780                 :          78 :       return def_stmt_info;
     781                 :             :     }
     782                 :             : 
     783                 :          28 :   if (def1_info
     784                 :          28 :       && def1_info->stmt == phi
     785                 :          28 :       && (code == COND_EXPR
     786                 :           7 :           || !def2_info
     787                 :           4 :           || !flow_bb_inside_loop_p (loop, gimple_bb (def2_info->stmt))
     788                 :           4 :           || parloops_valid_reduction_input_p (def2_info)))
     789                 :             :     {
     790                 :           7 :       if (! nested_in_vect_loop && orig_code != MINUS_EXPR)
     791                 :             :         {
     792                 :             :           /* Check if we can swap operands (just for simplicity - so that
     793                 :             :              the rest of the code can assume that the reduction variable
     794                 :             :              is always the last (second) argument).  */
     795                 :           7 :           if (code == COND_EXPR)
     796                 :             :             {
     797                 :             :               /* Swap cond_expr by inverting the condition.  */
     798                 :           0 :               tree cond_expr = gimple_assign_rhs1 (def_stmt);
     799                 :           0 :               enum tree_code invert_code = ERROR_MARK;
     800                 :           0 :               enum tree_code cond_code = TREE_CODE (cond_expr);
     801                 :             : 
     802                 :           0 :               if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
     803                 :             :                 {
     804                 :           0 :                   bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0));
     805                 :           0 :                   invert_code = invert_tree_comparison (cond_code, honor_nans);
     806                 :             :                 }
     807                 :           0 :               if (invert_code != ERROR_MARK)
     808                 :             :                 {
     809                 :           0 :                   TREE_SET_CODE (cond_expr, invert_code);
     810                 :           0 :                   swap_ssa_operands (def_stmt,
     811                 :             :                                      gimple_assign_rhs2_ptr (def_stmt),
     812                 :             :                                      gimple_assign_rhs3_ptr (def_stmt));
     813                 :             :                 }
     814                 :             :               else
     815                 :             :                 {
     816                 :           0 :                   if (dump_enabled_p ())
     817                 :           0 :                     report_ploop_op (MSG_NOTE, def_stmt,
     818                 :             :                                      "detected reduction: cannot swap operands "
     819                 :             :                                      "for cond_expr");
     820                 :           0 :                   return NULL;
     821                 :             :                 }
     822                 :             :             }
     823                 :             :           else
     824                 :           7 :             swap_ssa_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
     825                 :             :                                gimple_assign_rhs2_ptr (def_stmt));
     826                 :             : 
     827                 :           7 :           if (dump_enabled_p ())
     828                 :           4 :             report_ploop_op (MSG_NOTE, def_stmt,
     829                 :             :                              "detected reduction: need to swap operands: ");
     830                 :             :         }
     831                 :             :       else
     832                 :             :         {
     833                 :           0 :           if (dump_enabled_p ())
     834                 :           0 :             report_ploop_op (MSG_NOTE, def_stmt, "detected reduction: ");
     835                 :             :         }
     836                 :             : 
     837                 :           7 :       return def_stmt_info;
     838                 :             :     }
     839                 :             : 
     840                 :             :   /* Try to find SLP reduction chain.  */
     841                 :          21 :   if (! nested_in_vect_loop
     842                 :          21 :       && code != COND_EXPR
     843                 :          21 :       && orig_code != MINUS_EXPR
     844                 :          22 :       && parloops_is_slp_reduction (loop_info, phi, def_stmt))
     845                 :             :     {
     846                 :           1 :       if (dump_enabled_p ())
     847                 :           0 :         report_ploop_op (MSG_NOTE, def_stmt,
     848                 :             :                          "reduction: detected reduction chain: ");
     849                 :             : 
     850                 :           1 :       return def_stmt_info;
     851                 :             :     }
     852                 :             : 
     853                 :             :   /* Look for the expression computing loop_arg from loop PHI result.  */
     854                 :          20 :   if (check_reduction_path (vect_location, loop, phi, loop_arg, code))
     855                 :             :     return def_stmt_info;
     856                 :             : 
     857                 :           0 :   if (dump_enabled_p ())
     858                 :             :     {
     859                 :           0 :       report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
     860                 :             :                        "reduction: unknown pattern: ");
     861                 :             :     }
     862                 :             : 
     863                 :             :   return NULL;
     864                 :         135 : }
     865                 :             : 
     866                 :             : /* Wrapper around vect_is_simple_reduction, which will modify code
     867                 :             :    in-place if it enables detection of more reductions.  Arguments
     868                 :             :    as there.  */
     869                 :             : 
     870                 :             : stmt_vec_info
     871                 :         135 : parloops_force_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
     872                 :             :                              bool *double_reduc,
     873                 :             :                              bool need_wrapping_integral_overflow)
     874                 :             : {
     875                 :         135 :   enum vect_reduction_type v_reduc_type;
     876                 :         135 :   stmt_vec_info def_info
     877                 :         135 :     = parloops_is_simple_reduction (loop_info, phi_info, double_reduc,
     878                 :             :                                 need_wrapping_integral_overflow,
     879                 :             :                                 &v_reduc_type);
     880                 :         135 :   if (def_info)
     881                 :             :     {
     882                 :         121 :       STMT_VINFO_REDUC_TYPE (phi_info) = v_reduc_type;
     883                 :         121 :       STMT_VINFO_REDUC_DEF (phi_info) = def_info;
     884                 :         121 :       STMT_VINFO_REDUC_TYPE (def_info) = v_reduc_type;
     885                 :         121 :       STMT_VINFO_REDUC_DEF (def_info) = phi_info;
     886                 :             :     }
     887                 :         135 :   return def_info;
     888                 :             : }
     889                 :             : 
     890                 :             : /* Minimal number of iterations of a loop that should be executed in each
     891                 :             :    thread.  */
     892                 :             : #define MIN_PER_THREAD param_parloops_min_per_thread
     893                 :             : 
     894                 :             : /* Element of the hashtable, representing a
     895                 :             :    reduction in the current loop.  */
     896                 :             : struct reduction_info
     897                 :             : {
     898                 :             :   gimple *reduc_stmt;           /* reduction statement.  */
     899                 :             :   gimple *reduc_phi;            /* The phi node defining the reduction.  */
     900                 :             :   enum tree_code reduction_code;/* code for the reduction operation.  */
     901                 :             :   unsigned reduc_version;       /* SSA_NAME_VERSION of original reduc_phi
     902                 :             :                                    result.  */
     903                 :             :   gphi *keep_res;               /* The PHI_RESULT of this phi is the resulting value
     904                 :             :                                    of the reduction variable when existing the loop. */
     905                 :             :   tree initial_value;           /* The initial value of the reduction var before entering the loop.  */
     906                 :             :   tree field;                   /*  the name of the field in the parloop data structure intended for reduction.  */
     907                 :             :   tree reduc_addr;              /* The address of the reduction variable for
     908                 :             :                                    openacc reductions.  */
     909                 :             :   tree init;                    /* reduction initialization value.  */
     910                 :             :   gphi *new_phi;                /* (helper field) Newly created phi node whose result
     911                 :             :                                    will be passed to the atomic operation.  Represents
     912                 :             :                                    the local result each thread computed for the reduction
     913                 :             :                                    operation.  */
     914                 :             : };
     915                 :             : 
     916                 :             : /* Reduction info hashtable helpers.  */
     917                 :             : 
     918                 :             : struct reduction_hasher : free_ptr_hash <reduction_info>
     919                 :             : {
     920                 :             :   static inline hashval_t hash (const reduction_info *);
     921                 :             :   static inline bool equal (const reduction_info *, const reduction_info *);
     922                 :             : };
     923                 :             : 
     924                 :             : /* Equality and hash functions for hashtab code.  */
     925                 :             : 
     926                 :             : inline bool
     927                 :         410 : reduction_hasher::equal (const reduction_info *a, const reduction_info *b)
     928                 :             : {
     929                 :         410 :   return (a->reduc_phi == b->reduc_phi);
     930                 :             : }
     931                 :             : 
     932                 :             : inline hashval_t
     933                 :         331 : reduction_hasher::hash (const reduction_info *a)
     934                 :             : {
     935                 :         331 :   return a->reduc_version;
     936                 :             : }
     937                 :             : 
     938                 :             : typedef hash_table<reduction_hasher> reduction_info_table_type;
     939                 :             : 
     940                 :             : 
     941                 :             : static struct reduction_info *
     942                 :        1402 : reduction_phi (reduction_info_table_type *reduction_list, gimple *phi)
     943                 :             : {
     944                 :        1402 :   struct reduction_info tmpred, *red;
     945                 :             : 
     946                 :        1402 :   if (reduction_list->is_empty () || phi == NULL)
     947                 :             :     return NULL;
     948                 :             : 
     949                 :         436 :   if (gimple_uid (phi) == (unsigned int)-1
     950                 :         436 :       || gimple_uid (phi) == 0)
     951                 :             :     return NULL;
     952                 :             : 
     953                 :         347 :   tmpred.reduc_phi = phi;
     954                 :         347 :   tmpred.reduc_version = gimple_uid (phi);
     955                 :         347 :   red = reduction_list->find (&tmpred);
     956                 :         347 :   gcc_assert (red == NULL || red->reduc_phi == phi);
     957                 :             : 
     958                 :             :   return red;
     959                 :             : }
     960                 :             : 
     961                 :             : /* Element of hashtable of names to copy.  */
     962                 :             : 
     963                 :             : struct name_to_copy_elt
     964                 :             : {
     965                 :             :   unsigned version;     /* The version of the name to copy.  */
     966                 :             :   tree new_name;        /* The new name used in the copy.  */
     967                 :             :   tree field;           /* The field of the structure used to pass the
     968                 :             :                            value.  */
     969                 :             : };
     970                 :             : 
     971                 :             : /* Name copies hashtable helpers.  */
     972                 :             : 
     973                 :             : struct name_to_copy_hasher : free_ptr_hash <name_to_copy_elt>
     974                 :             : {
     975                 :             :   static inline hashval_t hash (const name_to_copy_elt *);
     976                 :             :   static inline bool equal (const name_to_copy_elt *, const name_to_copy_elt *);
     977                 :             : };
     978                 :             : 
     979                 :             : /* Equality and hash functions for hashtab code.  */
     980                 :             : 
     981                 :             : inline bool
     982                 :        6211 : name_to_copy_hasher::equal (const name_to_copy_elt *a, const name_to_copy_elt *b)
     983                 :             : {
     984                 :        6211 :   return a->version == b->version;
     985                 :             : }
     986                 :             : 
     987                 :             : inline hashval_t
     988                 :        5645 : name_to_copy_hasher::hash (const name_to_copy_elt *a)
     989                 :             : {
     990                 :        5645 :   return (hashval_t) a->version;
     991                 :             : }
     992                 :             : 
     993                 :             : typedef hash_table<name_to_copy_hasher> name_to_copy_table_type;
     994                 :             : 
     995                 :             : /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
     996                 :             :    matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
     997                 :             :    represents the denominator for every element in the matrix.  */
     998                 :             : typedef struct lambda_trans_matrix_s
     999                 :             : {
    1000                 :             :   lambda_matrix matrix;
    1001                 :             :   int rowsize;
    1002                 :             :   int colsize;
    1003                 :             :   int denominator;
    1004                 :             : } *lambda_trans_matrix;
    1005                 :             : #define LTM_MATRIX(T) ((T)->matrix)
    1006                 :             : #define LTM_ROWSIZE(T) ((T)->rowsize)
    1007                 :             : #define LTM_COLSIZE(T) ((T)->colsize)
    1008                 :             : #define LTM_DENOMINATOR(T) ((T)->denominator)
    1009                 :             : 
    1010                 :             : /* Allocate a new transformation matrix.  */
    1011                 :             : 
    1012                 :             : static lambda_trans_matrix
    1013                 :         710 : lambda_trans_matrix_new (int colsize, int rowsize,
    1014                 :             :                          struct obstack * lambda_obstack)
    1015                 :             : {
    1016                 :         710 :   lambda_trans_matrix ret;
    1017                 :             : 
    1018                 :        1420 :   ret = (lambda_trans_matrix)
    1019                 :         710 :     obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
    1020                 :         710 :   LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
    1021                 :         710 :   LTM_ROWSIZE (ret) = rowsize;
    1022                 :         710 :   LTM_COLSIZE (ret) = colsize;
    1023                 :         710 :   LTM_DENOMINATOR (ret) = 1;
    1024                 :         710 :   return ret;
    1025                 :             : }
    1026                 :             : 
    1027                 :             : /* Multiply a vector VEC by a matrix MAT.
    1028                 :             :    MAT is an M*N matrix, and VEC is a vector with length N.  The result
    1029                 :             :    is stored in DEST which must be a vector of length M.  */
    1030                 :             : 
    1031                 :             : static void
    1032                 :         636 : lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
    1033                 :             :                            lambda_vector vec, lambda_vector dest)
    1034                 :             : {
    1035                 :         636 :   int i, j;
    1036                 :             : 
    1037                 :         636 :   lambda_vector_clear (dest, m);
    1038                 :        1272 :   for (i = 0; i < m; i++)
    1039                 :        1272 :     for (j = 0; j < n; j++)
    1040                 :         636 :       dest[i] += matrix[i][j] * vec[j];
    1041                 :         636 : }
    1042                 :             : 
    1043                 :             : /* Return true if TRANS is a legal transformation matrix that respects
    1044                 :             :    the dependence vectors in DISTS and DIRS.  The conservative answer
    1045                 :             :    is false.
    1046                 :             : 
    1047                 :             :    "Wolfe proves that a unimodular transformation represented by the
    1048                 :             :    matrix T is legal when applied to a loop nest with a set of
    1049                 :             :    lexicographically non-negative distance vectors RDG if and only if
    1050                 :             :    for each vector d in RDG, (T.d >= 0) is lexicographically positive.
    1051                 :             :    i.e.: if and only if it transforms the lexicographically positive
    1052                 :             :    distance vectors to lexicographically positive vectors.  Note that
    1053                 :             :    a unimodular matrix must transform the zero vector (and only it) to
    1054                 :             :    the zero vector." S.Muchnick.  */
    1055                 :             : 
    1056                 :             : static bool
    1057                 :         710 : lambda_transform_legal_p (lambda_trans_matrix trans,
    1058                 :             :                           int nb_loops,
    1059                 :             :                           vec<ddr_p> dependence_relations)
    1060                 :             : {
    1061                 :         710 :   unsigned int i, j;
    1062                 :         710 :   lambda_vector distres;
    1063                 :         710 :   struct data_dependence_relation *ddr;
    1064                 :             : 
    1065                 :         710 :   gcc_assert (LTM_COLSIZE (trans) == nb_loops
    1066                 :             :               && LTM_ROWSIZE (trans) == nb_loops);
    1067                 :             : 
    1068                 :             :   /* When there are no dependences, the transformation is correct.  */
    1069                 :        1233 :   if (dependence_relations.length () == 0)
    1070                 :             :     return true;
    1071                 :             : 
    1072                 :         667 :   ddr = dependence_relations[0];
    1073                 :         667 :   if (ddr == NULL)
    1074                 :             :     return true;
    1075                 :             : 
    1076                 :             :   /* When there is an unknown relation in the dependence_relations, we
    1077                 :             :      know that it is no worth looking at this loop nest: give up.  */
    1078                 :         667 :   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
    1079                 :             :     return false;
    1080                 :             : 
    1081                 :         552 :   distres = lambda_vector_new (nb_loops);
    1082                 :             : 
    1083                 :             :   /* For each distance vector in the dependence graph.  */
    1084                 :        3283 :   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
    1085                 :             :     {
    1086                 :             :       /* Don't care about relations for which we know that there is no
    1087                 :             :          dependence, nor about read-read (aka. output-dependences):
    1088                 :             :          these data accesses can happen in any order.  */
    1089                 :        2208 :       if (DDR_ARE_DEPENDENT (ddr) == chrec_known
    1090                 :        1280 :           || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
    1091                 :        1564 :         continue;
    1092                 :             : 
    1093                 :             :       /* Conservatively answer: "this transformation is not valid".  */
    1094                 :         644 :       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
    1095                 :             :         return false;
    1096                 :             : 
    1097                 :             :       /* If the dependence could not be captured by a distance vector,
    1098                 :             :          conservatively answer that the transform is not valid.  */
    1099                 :         629 :       if (DDR_NUM_DIST_VECTS (ddr) == 0)
    1100                 :             :         return false;
    1101                 :             : 
    1102                 :             :       /* Compute trans.dist_vect */
    1103                 :        1251 :       for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
    1104                 :             :         {
    1105                 :        1272 :           lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
    1106                 :         636 :                                      DDR_DIST_VECT (ddr, j), distres);
    1107                 :             : 
    1108                 :        1404 :           if (!lambda_vector_lexico_pos (distres, nb_loops))
    1109                 :             :             return false;
    1110                 :             :         }
    1111                 :             :     }
    1112                 :             :   return true;
    1113                 :             : }
    1114                 :             : 
    1115                 :             : /* Data dependency analysis. Returns true if the iterations of LOOP
    1116                 :             :    are independent on each other (that is, if we can execute them
    1117                 :             :    in parallel).  */
    1118                 :             : 
    1119                 :             : static bool
    1120                 :        1108 : loop_parallel_p (class loop *loop, struct obstack * parloop_obstack)
    1121                 :             : {
    1122                 :        1108 :   vec<ddr_p> dependence_relations;
    1123                 :        1108 :   vec<data_reference_p> datarefs;
    1124                 :        1108 :   lambda_trans_matrix trans;
    1125                 :        1108 :   bool ret = false;
    1126                 :             : 
    1127                 :        1108 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1128                 :             :   {
    1129                 :         234 :     fprintf (dump_file, "Considering loop %d\n", loop->num);
    1130                 :         234 :     if (!loop->inner)
    1131                 :         204 :       fprintf (dump_file, "loop is innermost\n");
    1132                 :             :     else
    1133                 :          30 :       fprintf (dump_file, "loop NOT innermost\n");
    1134                 :             :    }
    1135                 :             : 
    1136                 :             :   /* Check for problems with dependences.  If the loop can be reversed,
    1137                 :             :      the iterations are independent.  */
    1138                 :        1108 :   auto_vec<loop_p, 3> loop_nest;
    1139                 :        1108 :   datarefs.create (10);
    1140                 :        1108 :   dependence_relations.create (100);
    1141                 :        1108 :   if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
    1142                 :             :                                            &dependence_relations))
    1143                 :             :     {
    1144                 :         398 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1145                 :          14 :         fprintf (dump_file, "  FAILED: cannot analyze data dependencies\n");
    1146                 :         398 :       ret = false;
    1147                 :         398 :       goto end;
    1148                 :             :     }
    1149                 :         710 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1150                 :         220 :     dump_data_dependence_relations (dump_file, dependence_relations);
    1151                 :             : 
    1152                 :         710 :   trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
    1153                 :         710 :   LTM_MATRIX (trans)[0][0] = -1;
    1154                 :             : 
    1155                 :         710 :   if (lambda_transform_legal_p (trans, 1, dependence_relations))
    1156                 :             :     {
    1157                 :         566 :       ret = true;
    1158                 :         566 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1159                 :         203 :         fprintf (dump_file, "  SUCCESS: may be parallelized\n");
    1160                 :             :     }
    1161                 :         144 :   else if (dump_file && (dump_flags & TDF_DETAILS))
    1162                 :          17 :     fprintf (dump_file,
    1163                 :             :              "  FAILED: data dependencies exist across iterations\n");
    1164                 :             : 
    1165                 :        1108 :  end:
    1166                 :        1108 :   free_dependence_relations (dependence_relations);
    1167                 :        1108 :   free_data_refs (datarefs);
    1168                 :             : 
    1169                 :        1108 :   return ret;
    1170                 :        1108 : }
    1171                 :             : 
    1172                 :             : /* Return true when LOOP contains basic blocks marked with the
    1173                 :             :    BB_IRREDUCIBLE_LOOP flag.  */
    1174                 :             : 
    1175                 :             : static inline bool
    1176                 :        1914 : loop_has_blocks_with_irreducible_flag (class loop *loop)
    1177                 :             : {
    1178                 :        1914 :   unsigned i;
    1179                 :        1914 :   basic_block *bbs = get_loop_body_in_dom_order (loop);
    1180                 :        1914 :   bool res = true;
    1181                 :             : 
    1182                 :       12807 :   for (i = 0; i < loop->num_nodes; i++)
    1183                 :        8979 :     if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
    1184                 :           0 :       goto end;
    1185                 :             : 
    1186                 :             :   res = false;
    1187                 :        1914 :  end:
    1188                 :        1914 :   free (bbs);
    1189                 :        1914 :   return res;
    1190                 :             : }
    1191                 :             : 
    1192                 :             : /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
    1193                 :             :    The assignment statement is placed on edge ENTRY.  DECL_ADDRESS maps decls
    1194                 :             :    to their addresses that can be reused.  The address of OBJ is known to
    1195                 :             :    be invariant in the whole function.  Other needed statements are placed
    1196                 :             :    right before GSI.  */
    1197                 :             : 
    1198                 :             : static tree
    1199                 :         252 : take_address_of (tree obj, tree type, edge entry,
    1200                 :             :                  int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
    1201                 :             : {
    1202                 :         252 :   int uid;
    1203                 :         252 :   tree *var_p, name, addr;
    1204                 :         252 :   gassign *stmt;
    1205                 :         252 :   gimple_seq stmts;
    1206                 :             : 
    1207                 :             :   /* Since the address of OBJ is invariant, the trees may be shared.
    1208                 :             :      Avoid rewriting unrelated parts of the code.  */
    1209                 :         252 :   obj = unshare_expr (obj);
    1210                 :         252 :   for (var_p = &obj;
    1211                 :         254 :        handled_component_p (*var_p);
    1212                 :           2 :        var_p = &TREE_OPERAND (*var_p, 0))
    1213                 :           2 :     continue;
    1214                 :             : 
    1215                 :             :   /* Canonicalize the access to base on a MEM_REF.  */
    1216                 :         252 :   if (DECL_P (*var_p))
    1217                 :         252 :     *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));
    1218                 :             : 
    1219                 :             :   /* Assign a canonical SSA name to the address of the base decl used
    1220                 :             :      in the address and share it for all accesses and addresses based
    1221                 :             :      on it.  */
    1222                 :         252 :   uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
    1223                 :         252 :   int_tree_map elt;
    1224                 :         252 :   elt.uid = uid;
    1225                 :         504 :   int_tree_map *slot = decl_address->find_slot (elt,
    1226                 :             :                                                 gsi == NULL
    1227                 :         252 :                                                 ? NO_INSERT
    1228                 :             :                                                 : INSERT);
    1229                 :         252 :   if (!slot || !slot->to)
    1230                 :             :     {
    1231                 :         201 :       if (gsi == NULL)
    1232                 :             :         return NULL;
    1233                 :         200 :       addr = TREE_OPERAND (*var_p, 0);
    1234                 :         200 :       const char *obj_name
    1235                 :         200 :         = get_name (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
    1236                 :         200 :       if (obj_name)
    1237                 :         200 :         name = make_temp_ssa_name (TREE_TYPE (addr), NULL, obj_name);
    1238                 :             :       else
    1239                 :           0 :         name = make_ssa_name (TREE_TYPE (addr));
    1240                 :         200 :       stmt = gimple_build_assign (name, addr);
    1241                 :         200 :       gsi_insert_on_edge_immediate (entry, stmt);
    1242                 :             : 
    1243                 :         200 :       slot->uid = uid;
    1244                 :         200 :       slot->to = name;
    1245                 :         200 :     }
    1246                 :             :   else
    1247                 :             :     name = slot->to;
    1248                 :             : 
    1249                 :             :   /* Express the address in terms of the canonical SSA name.  */
    1250                 :         251 :   TREE_OPERAND (*var_p, 0) = name;
    1251                 :         251 :   if (gsi == NULL)
    1252                 :           4 :     return build_fold_addr_expr_with_type (obj, type);
    1253                 :             : 
    1254                 :         247 :   name = force_gimple_operand (build_addr (obj),
    1255                 :             :                                &stmts, true, NULL_TREE);
    1256                 :         247 :   if (!gimple_seq_empty_p (stmts))
    1257                 :           1 :     gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
    1258                 :             : 
    1259                 :         247 :   if (!useless_type_conversion_p (type, TREE_TYPE (name)))
    1260                 :             :     {
    1261                 :           0 :       name = force_gimple_operand (fold_convert (type, name), &stmts, true,
    1262                 :             :                                    NULL_TREE);
    1263                 :           0 :       if (!gimple_seq_empty_p (stmts))
    1264                 :           0 :         gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
    1265                 :             :     }
    1266                 :             : 
    1267                 :             :   return name;
    1268                 :           2 : }
    1269                 :             : 
    1270                 :             : static tree
    1271                 :         270 : reduc_stmt_res (gimple *stmt)
    1272                 :             : {
    1273                 :         270 :   return (gimple_code (stmt) == GIMPLE_PHI
    1274                 :         286 :           ? gimple_phi_result (stmt)
    1275                 :         254 :           : gimple_assign_lhs (stmt));
    1276                 :             : }
    1277                 :             : 
    1278                 :             : /* Callback for htab_traverse.  Create the initialization statement
    1279                 :             :    for reduction described in SLOT, and place it at the preheader of
    1280                 :             :    the loop described in DATA.  */
    1281                 :             : 
    1282                 :             : int
    1283                 :          78 : initialize_reductions (reduction_info **slot, class loop *loop)
    1284                 :             : {
    1285                 :          78 :   tree init;
    1286                 :          78 :   tree type, arg;
    1287                 :          78 :   edge e;
    1288                 :             : 
    1289                 :          78 :   struct reduction_info *const reduc = *slot;
    1290                 :             : 
    1291                 :             :   /* Create initialization in preheader:
    1292                 :             :      reduction_variable = initialization value of reduction.  */
    1293                 :             : 
    1294                 :             :   /* In the phi node at the header, replace the argument coming
    1295                 :             :      from the preheader with the reduction initialization value.  */
    1296                 :             : 
    1297                 :             :   /* Initialize the reduction.  */
    1298                 :          78 :   type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
    1299                 :          78 :   init = omp_reduction_init_op (gimple_location (reduc->reduc_stmt),
    1300                 :             :                                 reduc->reduction_code, type);
    1301                 :          78 :   reduc->init = init;
    1302                 :             : 
    1303                 :             :   /* Replace the argument representing the initialization value
    1304                 :             :      with the initialization value for the reduction (neutral
    1305                 :             :      element for the particular operation, e.g. 0 for PLUS_EXPR,
    1306                 :             :      1 for MULT_EXPR, etc).
    1307                 :             :      Keep the old value in a new variable "reduction_initial",
    1308                 :             :      that will be taken in consideration after the parallel
    1309                 :             :      computing is done.  */
    1310                 :             : 
    1311                 :          78 :   e = loop_preheader_edge (loop);
    1312                 :          78 :   arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
    1313                 :             :   /* Create new variable to hold the initial value.  */
    1314                 :             : 
    1315                 :          78 :   SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
    1316                 :             :            (reduc->reduc_phi, loop_preheader_edge (loop)), init);
    1317                 :          78 :   reduc->initial_value = arg;
    1318                 :          78 :   return 1;
    1319                 :             : }
    1320                 :             : 
    1321                 :             : struct elv_data
    1322                 :             : {
    1323                 :             :   struct walk_stmt_info info;
    1324                 :             :   edge entry;
    1325                 :             :   int_tree_htab_type *decl_address;
    1326                 :             :   gimple_stmt_iterator *gsi;
    1327                 :             :   bool changed;
    1328                 :             :   bool reset;
    1329                 :             : };
    1330                 :             : 
    1331                 :             : /* Eliminates references to local variables in *TP out of the single
    1332                 :             :    entry single exit region starting at DTA->ENTRY.
    1333                 :             :    DECL_ADDRESS contains addresses of the references that had their
    1334                 :             :    address taken already.  If the expression is changed, CHANGED is
    1335                 :             :    set to true.  Callback for walk_tree.  */
    1336                 :             : 
    1337                 :             : static tree
    1338                 :        6122 : eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
    1339                 :             : {
    1340                 :        6122 :   struct elv_data *const dta = (struct elv_data *) data;
    1341                 :        6122 :   tree t = *tp, var, addr, addr_type, type, obj;
    1342                 :             : 
    1343                 :        6122 :   if (DECL_P (t))
    1344                 :             :     {
    1345                 :         268 :       *walk_subtrees = 0;
    1346                 :             : 
    1347                 :         268 :       if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
    1348                 :             :         return NULL_TREE;
    1349                 :             : 
    1350                 :         224 :       type = TREE_TYPE (t);
    1351                 :         224 :       addr_type = build_pointer_type (type);
    1352                 :         224 :       addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
    1353                 :             :                               dta->gsi);
    1354                 :         224 :       if (dta->gsi == NULL && addr == NULL_TREE)
    1355                 :             :         {
    1356                 :           0 :           dta->reset = true;
    1357                 :           0 :           return NULL_TREE;
    1358                 :             :         }
    1359                 :             : 
    1360                 :         224 :       *tp = build_simple_mem_ref (addr);
    1361                 :             : 
    1362                 :         224 :       dta->changed = true;
    1363                 :         224 :       return NULL_TREE;
    1364                 :             :     }
    1365                 :             : 
    1366                 :        5854 :   if (TREE_CODE (t) == ADDR_EXPR)
    1367                 :             :     {
    1368                 :             :       /* ADDR_EXPR may appear in two contexts:
    1369                 :             :          -- as a gimple operand, when the address taken is a function invariant
    1370                 :             :          -- as gimple rhs, when the resulting address in not a function
    1371                 :             :             invariant
    1372                 :             :          We do not need to do anything special in the latter case (the base of
    1373                 :             :          the memory reference whose address is taken may be replaced in the
    1374                 :             :          DECL_P case).  The former case is more complicated, as we need to
    1375                 :             :          ensure that the new address is still a gimple operand.  Thus, it
    1376                 :             :          is not sufficient to replace just the base of the memory reference --
    1377                 :             :          we need to move the whole computation of the address out of the
    1378                 :             :          loop.  */
    1379                 :          33 :       if (!is_gimple_val (t))
    1380                 :             :         return NULL_TREE;
    1381                 :             : 
    1382                 :          33 :       *walk_subtrees = 0;
    1383                 :          33 :       obj = TREE_OPERAND (t, 0);
    1384                 :          33 :       var = get_base_address (obj);
    1385                 :          33 :       if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
    1386                 :             :         return NULL_TREE;
    1387                 :             : 
    1388                 :          28 :       addr_type = TREE_TYPE (t);
    1389                 :          28 :       addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
    1390                 :             :                               dta->gsi);
    1391                 :          28 :       if (dta->gsi == NULL && addr == NULL_TREE)
    1392                 :             :         {
    1393                 :           1 :           dta->reset = true;
    1394                 :           1 :           return NULL_TREE;
    1395                 :             :         }
    1396                 :          27 :       *tp = addr;
    1397                 :             : 
    1398                 :          27 :       dta->changed = true;
    1399                 :          27 :       return NULL_TREE;
    1400                 :             :     }
    1401                 :             : 
    1402                 :        5821 :   if (!EXPR_P (t))
    1403                 :        5319 :     *walk_subtrees = 0;
    1404                 :             : 
    1405                 :             :   return NULL_TREE;
    1406                 :             : }
    1407                 :             : 
    1408                 :             : /* Moves the references to local variables in STMT at *GSI out of the single
    1409                 :             :    entry single exit region starting at ENTRY.  DECL_ADDRESS contains
    1410                 :             :    addresses of the references that had their address taken
    1411                 :             :    already.  */
    1412                 :             : 
    1413                 :             : static void
    1414                 :        2131 : eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
    1415                 :             :                                 int_tree_htab_type *decl_address)
    1416                 :             : {
    1417                 :        2131 :   struct elv_data dta;
    1418                 :        2131 :   gimple *stmt = gsi_stmt (*gsi);
    1419                 :             : 
    1420                 :        2131 :   memset (&dta.info, '\0', sizeof (dta.info));
    1421                 :        2131 :   dta.entry = entry;
    1422                 :        2131 :   dta.decl_address = decl_address;
    1423                 :        2131 :   dta.changed = false;
    1424                 :        2131 :   dta.reset = false;
    1425                 :             : 
    1426                 :        2131 :   if (gimple_debug_bind_p (stmt))
    1427                 :             :     {
    1428                 :         116 :       dta.gsi = NULL;
    1429                 :         116 :       walk_tree (gimple_debug_bind_get_value_ptr (stmt),
    1430                 :             :                  eliminate_local_variables_1, &dta.info, NULL);
    1431                 :         116 :       if (dta.reset)
    1432                 :             :         {
    1433                 :           1 :           gimple_debug_bind_reset_value (stmt);
    1434                 :           1 :           dta.changed = true;
    1435                 :             :         }
    1436                 :             :     }
    1437                 :        2015 :   else if (gimple_clobber_p (stmt))
    1438                 :             :     {
    1439                 :           0 :       unlink_stmt_vdef (stmt);
    1440                 :           0 :       stmt = gimple_build_nop ();
    1441                 :           0 :       gsi_replace (gsi, stmt, false);
    1442                 :           0 :       dta.changed = true;
    1443                 :             :     }
    1444                 :             :   else
    1445                 :             :     {
    1446                 :        2015 :       dta.gsi = gsi;
    1447                 :        2015 :       walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
    1448                 :             :     }
    1449                 :             : 
    1450                 :        2131 :   if (dta.changed)
    1451                 :         252 :     update_stmt (stmt);
    1452                 :        2131 : }
    1453                 :             : 
    1454                 :             : /* Eliminates the references to local variables from the single entry
    1455                 :             :    single exit region between the ENTRY and EXIT edges.
    1456                 :             : 
    1457                 :             :    This includes:
    1458                 :             :    1) Taking address of a local variable -- these are moved out of the
    1459                 :             :    region (and temporary variable is created to hold the address if
    1460                 :             :    necessary).
    1461                 :             : 
    1462                 :             :    2) Dereferencing a local variable -- these are replaced with indirect
    1463                 :             :    references.  */
    1464                 :             : 
    1465                 :             : static void
    1466                 :         203 : eliminate_local_variables (edge entry, edge exit)
    1467                 :             : {
    1468                 :         203 :   basic_block bb;
    1469                 :         203 :   auto_vec<basic_block, 3> body;
    1470                 :         203 :   unsigned i;
    1471                 :         203 :   gimple_stmt_iterator gsi;
    1472                 :         203 :   bool has_debug_stmt = false;
    1473                 :         203 :   int_tree_htab_type decl_address (10);
    1474                 :         203 :   basic_block entry_bb = entry->src;
    1475                 :         203 :   basic_block exit_bb = exit->dest;
    1476                 :             : 
    1477                 :         203 :   gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
    1478                 :             : 
    1479                 :        1332 :   FOR_EACH_VEC_ELT (body, i, bb)
    1480                 :         926 :     if (bb != entry_bb && bb != exit_bb)
    1481                 :             :       {
    1482                 :        3675 :         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1483                 :        2229 :           if (is_gimple_debug (gsi_stmt (gsi)))
    1484                 :             :             {
    1485                 :         214 :               if (gimple_debug_bind_p (gsi_stmt (gsi)))
    1486                 :        2229 :                 has_debug_stmt = true;
    1487                 :             :             }
    1488                 :             :           else
    1489                 :        2015 :             eliminate_local_variables_stmt (entry, &gsi, &decl_address);
    1490                 :             :       }
    1491                 :             : 
    1492                 :         203 :   if (has_debug_stmt)
    1493                 :         106 :     FOR_EACH_VEC_ELT (body, i, bb)
    1494                 :          86 :       if (bb != entry_bb && bb != exit_bb)
    1495                 :         503 :         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1496                 :         487 :           if (gimple_debug_bind_p (gsi_stmt (gsi)))
    1497                 :         116 :             eliminate_local_variables_stmt (entry, &gsi, &decl_address);
    1498                 :         203 : }
    1499                 :             : 
    1500                 :             : /* Returns true if expression EXPR is not defined between ENTRY and
    1501                 :             :    EXIT, i.e. if all its operands are defined outside of the region.  */
    1502                 :             : 
    1503                 :             : static bool
    1504                 :        3425 : expr_invariant_in_region_p (edge entry, edge exit, tree expr)
    1505                 :             : {
    1506                 :        3425 :   basic_block entry_bb = entry->src;
    1507                 :        3425 :   basic_block exit_bb = exit->dest;
    1508                 :        3425 :   basic_block def_bb;
    1509                 :             : 
    1510                 :        3425 :   if (is_gimple_min_invariant (expr))
    1511                 :             :     return true;
    1512                 :             : 
    1513                 :        3425 :   if (TREE_CODE (expr) == SSA_NAME)
    1514                 :             :     {
    1515                 :        3425 :       def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
    1516                 :        3425 :       if (def_bb
    1517                 :        3312 :           && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
    1518                 :        6339 :           && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
    1519                 :             :         return false;
    1520                 :             : 
    1521                 :         511 :       return true;
    1522                 :             :     }
    1523                 :             : 
    1524                 :             :   return false;
    1525                 :             : }
    1526                 :             : 
    1527                 :             : /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
    1528                 :             :    The copies are stored to NAME_COPIES, if NAME was already duplicated,
    1529                 :             :    its duplicate stored in NAME_COPIES is returned.
    1530                 :             : 
    1531                 :             :    Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
    1532                 :             :    duplicated, storing the copies in DECL_COPIES.  */
    1533                 :             : 
    1534                 :             : static tree
    1535                 :        5610 : separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
    1536                 :             :                                int_tree_htab_type *decl_copies,
    1537                 :             :                                bool copy_name_p)
    1538                 :             : {
    1539                 :        5610 :   tree copy, var, var_copy;
    1540                 :        5610 :   unsigned idx, uid, nuid;
    1541                 :        5610 :   struct int_tree_map ielt;
    1542                 :        5610 :   struct name_to_copy_elt elt, *nelt;
    1543                 :        5610 :   name_to_copy_elt **slot;
    1544                 :        5610 :   int_tree_map *dslot;
    1545                 :             : 
    1546                 :        5610 :   if (TREE_CODE (name) != SSA_NAME)
    1547                 :             :     return name;
    1548                 :             : 
    1549                 :        5610 :   idx = SSA_NAME_VERSION (name);
    1550                 :        5610 :   elt.version = idx;
    1551                 :       10709 :   slot = name_copies->find_slot_with_hash (&elt, idx,
    1552                 :             :                                            copy_name_p ? INSERT : NO_INSERT);
    1553                 :        5610 :   if (slot && *slot)
    1554                 :          78 :     return (*slot)->new_name;
    1555                 :             : 
    1556                 :        5532 :   if (copy_name_p)
    1557                 :             :     {
    1558                 :         433 :       copy = duplicate_ssa_name (name, NULL);
    1559                 :         433 :       nelt = XNEW (struct name_to_copy_elt);
    1560                 :         433 :       nelt->version = idx;
    1561                 :         433 :       nelt->new_name = copy;
    1562                 :         433 :       nelt->field = NULL_TREE;
    1563                 :         433 :       *slot = nelt;
    1564                 :             :     }
    1565                 :             :   else
    1566                 :             :     {
    1567                 :        5099 :       gcc_assert (!slot);
    1568                 :             :       copy = name;
    1569                 :             :     }
    1570                 :             : 
    1571                 :        7181 :   var = SSA_NAME_VAR (name);
    1572                 :        1649 :   if (!var)
    1573                 :             :     return copy;
    1574                 :             : 
    1575                 :        1649 :   uid = DECL_UID (var);
    1576                 :        1649 :   ielt.uid = uid;
    1577                 :        1649 :   dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
    1578                 :        1649 :   if (!dslot->to)
    1579                 :             :     {
    1580                 :         404 :       var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
    1581                 :         404 :       DECL_NOT_GIMPLE_REG_P (var_copy) = DECL_NOT_GIMPLE_REG_P (var);
    1582                 :         404 :       dslot->uid = uid;
    1583                 :         404 :       dslot->to = var_copy;
    1584                 :             : 
    1585                 :             :       /* Ensure that when we meet this decl next time, we won't duplicate
    1586                 :             :          it again.  */
    1587                 :         404 :       nuid = DECL_UID (var_copy);
    1588                 :         404 :       ielt.uid = nuid;
    1589                 :         404 :       dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
    1590                 :         404 :       gcc_assert (!dslot->to);
    1591                 :         404 :       dslot->uid = nuid;
    1592                 :         404 :       dslot->to = var_copy;
    1593                 :             :     }
    1594                 :             :   else
    1595                 :             :     var_copy = dslot->to;
    1596                 :             : 
    1597                 :        1649 :   replace_ssa_name_symbol (copy, var_copy);
    1598                 :        1649 :   return copy;
    1599                 :             : }
    1600                 :             : 
    1601                 :             : /* Finds the ssa names used in STMT that are defined outside the
    1602                 :             :    region between ENTRY and EXIT and replaces such ssa names with
    1603                 :             :    their duplicates.  The duplicates are stored to NAME_COPIES.  Base
    1604                 :             :    decls of all ssa names used in STMT (including those defined in
    1605                 :             :    LOOP) are replaced with the new temporary variables; the
    1606                 :             :    replacement decls are stored in DECL_COPIES.  */
    1607                 :             : 
    1608                 :             : static void
    1609                 :        2894 : separate_decls_in_region_stmt (edge entry, edge exit, gimple *stmt,
    1610                 :             :                                name_to_copy_table_type *name_copies,
    1611                 :             :                                int_tree_htab_type *decl_copies)
    1612                 :             : {
    1613                 :        2894 :   use_operand_p use;
    1614                 :        2894 :   def_operand_p def;
    1615                 :        2894 :   ssa_op_iter oi;
    1616                 :        2894 :   tree name, copy;
    1617                 :        2894 :   bool copy_name_p;
    1618                 :             : 
    1619                 :        7973 :   FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
    1620                 :             :   {
    1621                 :        2185 :     name = DEF_FROM_PTR (def);
    1622                 :        2185 :     gcc_assert (TREE_CODE (name) == SSA_NAME);
    1623                 :        2185 :     copy = separate_decls_in_region_name (name, name_copies, decl_copies,
    1624                 :             :                                           false);
    1625                 :        2185 :     gcc_assert (copy == name);
    1626                 :             :   }
    1627                 :             : 
    1628                 :        9510 :   FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
    1629                 :             :   {
    1630                 :        3722 :     name = USE_FROM_PTR (use);
    1631                 :        3722 :     if (TREE_CODE (name) != SSA_NAME)
    1632                 :         297 :       continue;
    1633                 :             : 
    1634                 :        3425 :     copy_name_p = expr_invariant_in_region_p (entry, exit, name);
    1635                 :        3425 :     copy = separate_decls_in_region_name (name, name_copies, decl_copies,
    1636                 :             :                                           copy_name_p);
    1637                 :        3425 :     SET_USE (use, copy);
    1638                 :             :   }
    1639                 :        2894 : }
    1640                 :             : 
    1641                 :             : /* Finds the ssa names used in STMT that are defined outside the
    1642                 :             :    region between ENTRY and EXIT and replaces such ssa names with
    1643                 :             :    their duplicates.  The duplicates are stored to NAME_COPIES.  Base
    1644                 :             :    decls of all ssa names used in STMT (including those defined in
    1645                 :             :    LOOP) are replaced with the new temporary variables; the
    1646                 :             :    replacement decls are stored in DECL_COPIES.  */
    1647                 :             : 
    1648                 :             : static bool
    1649                 :         214 : separate_decls_in_region_debug (gimple *stmt,
    1650                 :             :                                 name_to_copy_table_type *name_copies,
    1651                 :             :                                 int_tree_htab_type *decl_copies)
    1652                 :             : {
    1653                 :         214 :   use_operand_p use;
    1654                 :         214 :   ssa_op_iter oi;
    1655                 :         214 :   tree var, name;
    1656                 :         214 :   struct int_tree_map ielt;
    1657                 :         214 :   struct name_to_copy_elt elt;
    1658                 :         214 :   name_to_copy_elt **slot;
    1659                 :         214 :   int_tree_map *dslot;
    1660                 :             : 
    1661                 :         214 :   if (gimple_debug_bind_p (stmt))
    1662                 :         116 :     var = gimple_debug_bind_get_var (stmt);
    1663                 :         132 :   else if (gimple_debug_source_bind_p (stmt))
    1664                 :           0 :     var = gimple_debug_source_bind_get_var (stmt);
    1665                 :             :   else
    1666                 :             :     return true;
    1667                 :         116 :   if (TREE_CODE (var) == DEBUG_EXPR_DECL || TREE_CODE (var) == LABEL_DECL)
    1668                 :             :     return true;
    1669                 :          95 :   gcc_assert (DECL_P (var) && SSA_VAR_P (var));
    1670                 :          95 :   ielt.uid = DECL_UID (var);
    1671                 :          95 :   dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
    1672                 :          95 :   if (!dslot)
    1673                 :             :     return true;
    1674                 :          82 :   if (gimple_debug_bind_p (stmt))
    1675                 :          82 :     gimple_debug_bind_set_var (stmt, dslot->to);
    1676                 :           0 :   else if (gimple_debug_source_bind_p (stmt))
    1677                 :           0 :     gimple_debug_source_bind_set_var (stmt, dslot->to);
    1678                 :             : 
    1679                 :         164 :   FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
    1680                 :             :   {
    1681                 :          70 :     name = USE_FROM_PTR (use);
    1682                 :          70 :     if (TREE_CODE (name) != SSA_NAME)
    1683                 :           0 :       continue;
    1684                 :             : 
    1685                 :          70 :     elt.version = SSA_NAME_VERSION (name);
    1686                 :          70 :     slot = name_copies->find_slot_with_hash (&elt, elt.version, NO_INSERT);
    1687                 :          70 :     if (!slot)
    1688                 :             :       {
    1689                 :          70 :         gimple_debug_bind_reset_value (stmt);
    1690                 :          70 :         update_stmt (stmt);
    1691                 :          70 :         break;
    1692                 :             :       }
    1693                 :             : 
    1694                 :           0 :     SET_USE (use, (*slot)->new_name);
    1695                 :             :   }
    1696                 :             : 
    1697                 :             :   return false;
    1698                 :             : }
    1699                 :             : 
    1700                 :             : /* Callback for htab_traverse.  Adds a field corresponding to the reduction
    1701                 :             :    specified in SLOT. The type is passed in DATA.  */
    1702                 :             : 
    1703                 :             : int
    1704                 :          64 : add_field_for_reduction (reduction_info **slot, tree type)
    1705                 :             : {
    1706                 :             : 
    1707                 :          64 :   struct reduction_info *const red = *slot;
    1708                 :          64 :   tree var = reduc_stmt_res (red->reduc_stmt);
    1709                 :         128 :   tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL,
    1710                 :         128 :                            SSA_NAME_IDENTIFIER (var), TREE_TYPE (var));
    1711                 :             : 
    1712                 :          64 :   insert_field_into_struct (type, field);
    1713                 :             : 
    1714                 :          64 :   red->field = field;
    1715                 :             : 
    1716                 :          64 :   return 1;
    1717                 :             : }
    1718                 :             : 
    1719                 :             : /* Callback for htab_traverse.  Adds a field corresponding to a ssa name
    1720                 :             :    described in SLOT. The type is passed in DATA.  */
    1721                 :             : 
    1722                 :             : int
    1723                 :         433 : add_field_for_name (name_to_copy_elt **slot, tree type)
    1724                 :             : {
    1725                 :         433 :   struct name_to_copy_elt *const elt = *slot;
    1726                 :         433 :   tree name = ssa_name (elt->version);
    1727                 :         866 :   tree field = build_decl (UNKNOWN_LOCATION,
    1728                 :         433 :                            FIELD_DECL, SSA_NAME_IDENTIFIER (name),
    1729                 :         433 :                            TREE_TYPE (name));
    1730                 :             : 
    1731                 :         433 :   insert_field_into_struct (type, field);
    1732                 :         433 :   elt->field = field;
    1733                 :             : 
    1734                 :         433 :   return 1;
    1735                 :             : }
    1736                 :             : 
    1737                 :             : /* Callback for htab_traverse.  A local result is the intermediate result
    1738                 :             :    computed by a single
    1739                 :             :    thread, or the initial value in case no iteration was executed.
    1740                 :             :    This function creates a phi node reflecting these values.
    1741                 :             :    The phi's result will be stored in NEW_PHI field of the
    1742                 :             :    reduction's data structure.  */
    1743                 :             : 
    1744                 :             : int
    1745                 :          78 : create_phi_for_local_result (reduction_info **slot, class loop *loop)
    1746                 :             : {
    1747                 :          78 :   struct reduction_info *const reduc = *slot;
    1748                 :          78 :   edge e;
    1749                 :          78 :   gphi *new_phi;
    1750                 :          78 :   basic_block store_bb, continue_bb;
    1751                 :          78 :   tree local_res;
    1752                 :          78 :   location_t locus;
    1753                 :             : 
    1754                 :             :   /* STORE_BB is the block where the phi
    1755                 :             :      should be stored.  It is the destination of the loop exit.
    1756                 :             :      (Find the fallthru edge from GIMPLE_OMP_CONTINUE).  */
    1757                 :          78 :   continue_bb = single_pred (loop->latch);
    1758                 :          78 :   store_bb = FALLTHRU_EDGE (continue_bb)->dest;
    1759                 :             : 
    1760                 :             :   /* STORE_BB has two predecessors.  One coming from  the loop
    1761                 :             :      (the reduction's result is computed at the loop),
    1762                 :             :      and another coming from a block preceding the loop,
    1763                 :             :      when no iterations
    1764                 :             :      are executed (the initial value should be taken).  */
    1765                 :          78 :   if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (continue_bb))
    1766                 :          78 :     e = EDGE_PRED (store_bb, 1);
    1767                 :             :   else
    1768                 :             :     e = EDGE_PRED (store_bb, 0);
    1769                 :          78 :   tree lhs = reduc_stmt_res (reduc->reduc_stmt);
    1770                 :          78 :   local_res = copy_ssa_name (lhs);
    1771                 :          78 :   locus = gimple_location (reduc->reduc_stmt);
    1772                 :          78 :   new_phi = create_phi_node (local_res, store_bb);
    1773                 :          78 :   add_phi_arg (new_phi, reduc->init, e, locus);
    1774                 :          78 :   add_phi_arg (new_phi, lhs, FALLTHRU_EDGE (continue_bb), locus);
    1775                 :          78 :   reduc->new_phi = new_phi;
    1776                 :             : 
    1777                 :          78 :   return 1;
    1778                 :             : }
    1779                 :             : 
    1780                 :             : struct clsn_data
    1781                 :             : {
    1782                 :             :   tree store;
    1783                 :             :   tree load;
    1784                 :             : 
    1785                 :             :   basic_block store_bb;
    1786                 :             :   basic_block load_bb;
    1787                 :             : };
    1788                 :             : 
    1789                 :             : /* Callback for htab_traverse.  Create an atomic instruction for the
    1790                 :             :    reduction described in SLOT.
    1791                 :             :    DATA annotates the place in memory the atomic operation relates to,
    1792                 :             :    and the basic block it needs to be generated in.  */
    1793                 :             : 
    1794                 :             : int
    1795                 :          78 : create_call_for_reduction_1 (reduction_info **slot, struct clsn_data *clsn_data)
    1796                 :             : {
    1797                 :          78 :   struct reduction_info *const reduc = *slot;
    1798                 :          78 :   gimple_stmt_iterator gsi;
    1799                 :          78 :   tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
    1800                 :          78 :   tree load_struct;
    1801                 :          78 :   basic_block bb;
    1802                 :          78 :   basic_block new_bb;
    1803                 :          78 :   edge e;
    1804                 :          78 :   tree t, addr, ref, x;
    1805                 :          78 :   tree tmp_load, name;
    1806                 :          78 :   gimple *load;
    1807                 :             : 
    1808                 :          78 :   if (reduc->reduc_addr == NULL_TREE)
    1809                 :             :     {
    1810                 :          64 :       load_struct = build_simple_mem_ref (clsn_data->load);
    1811                 :          64 :       t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
    1812                 :             : 
    1813                 :          64 :       addr = build_addr (t);
    1814                 :             :     }
    1815                 :             :   else
    1816                 :             :     {
    1817                 :             :       /* Set the address for the atomic store.  */
    1818                 :          14 :       addr = reduc->reduc_addr;
    1819                 :             : 
    1820                 :             :       /* Remove the non-atomic store '*addr = sum'.  */
    1821                 :          14 :       tree res = PHI_RESULT (reduc->keep_res);
    1822                 :          14 :       use_operand_p use_p;
    1823                 :          14 :       gimple *stmt;
    1824                 :          14 :       bool single_use_p = single_imm_use (res, &use_p, &stmt);
    1825                 :          14 :       gcc_assert (single_use_p);
    1826                 :          42 :       replace_uses_by (gimple_vdef (stmt),
    1827                 :             :                        gimple_vuse (stmt));
    1828                 :          14 :       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
    1829                 :          14 :       gsi_remove (&gsi, true);
    1830                 :             :     }
    1831                 :             : 
    1832                 :             :   /* Create phi node.  */
    1833                 :          78 :   bb = clsn_data->load_bb;
    1834                 :             : 
    1835                 :          78 :   gsi = gsi_last_bb (bb);
    1836                 :          78 :   e = split_block (bb, gsi_stmt (gsi));
    1837                 :          78 :   new_bb = e->dest;
    1838                 :             : 
    1839                 :          78 :   tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
    1840                 :          78 :   tmp_load = make_ssa_name (tmp_load);
    1841                 :          78 :   load = gimple_build_omp_atomic_load (tmp_load, addr,
    1842                 :             :                                        OMP_MEMORY_ORDER_RELAXED);
    1843                 :          78 :   SSA_NAME_DEF_STMT (tmp_load) = load;
    1844                 :          78 :   gsi = gsi_start_bb (new_bb);
    1845                 :          78 :   gsi_insert_after (&gsi, load, GSI_NEW_STMT);
    1846                 :             : 
    1847                 :          78 :   e = split_block (new_bb, load);
    1848                 :          78 :   new_bb = e->dest;
    1849                 :          78 :   gsi = gsi_start_bb (new_bb);
    1850                 :          78 :   ref = tmp_load;
    1851                 :          78 :   x = fold_build2 (reduc->reduction_code,
    1852                 :             :                    TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
    1853                 :             :                    PHI_RESULT (reduc->new_phi));
    1854                 :             : 
    1855                 :          78 :   name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
    1856                 :             :                                    GSI_CONTINUE_LINKING);
    1857                 :             : 
    1858                 :          78 :   gimple *store = gimple_build_omp_atomic_store (name,
    1859                 :             :                                                  OMP_MEMORY_ORDER_RELAXED);
    1860                 :          78 :   gsi_insert_after (&gsi, store, GSI_NEW_STMT);
    1861                 :          78 :   return 1;
    1862                 :             : }
    1863                 :             : 
    1864                 :             : /* Create the atomic operation at the join point of the threads.
    1865                 :             :    REDUCTION_LIST describes the reductions in the LOOP.
    1866                 :             :    LD_ST_DATA describes the shared data structure where
    1867                 :             :    shared data is stored in and loaded from.  */
    1868                 :             : static void
    1869                 :          71 : create_call_for_reduction (class loop *loop,
    1870                 :             :                            reduction_info_table_type *reduction_list,
    1871                 :             :                            struct clsn_data *ld_st_data)
    1872                 :             : {
    1873                 :          71 :   reduction_list->traverse <class loop *, create_phi_for_local_result> (loop);
    1874                 :             :   /* Find the fallthru edge from GIMPLE_OMP_CONTINUE.  */
    1875                 :          71 :   basic_block continue_bb = single_pred (loop->latch);
    1876                 :          71 :   ld_st_data->load_bb = FALLTHRU_EDGE (continue_bb)->dest;
    1877                 :          71 :   reduction_list
    1878                 :          71 :     ->traverse <struct clsn_data *, create_call_for_reduction_1> (ld_st_data);
    1879                 :          71 : }
    1880                 :             : 
    1881                 :             : /* Callback for htab_traverse.  Loads the final reduction value at the
    1882                 :             :    join point of all threads, and inserts it in the right place.  */
    1883                 :             : 
    1884                 :             : int
    1885                 :          64 : create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data)
    1886                 :             : {
    1887                 :          64 :   struct reduction_info *const red = *slot;
    1888                 :          64 :   gimple *stmt;
    1889                 :          64 :   gimple_stmt_iterator gsi;
    1890                 :          64 :   tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
    1891                 :          64 :   tree load_struct;
    1892                 :          64 :   tree name;
    1893                 :          64 :   tree x;
    1894                 :             : 
    1895                 :             :   /* If there's no exit phi, the result of the reduction is unused.  */
    1896                 :          64 :   if (red->keep_res == NULL)
    1897                 :             :     return 1;
    1898                 :             : 
    1899                 :          63 :   gsi = gsi_after_labels (clsn_data->load_bb);
    1900                 :          63 :   load_struct = build_simple_mem_ref (clsn_data->load);
    1901                 :          63 :   load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
    1902                 :             :                         NULL_TREE);
    1903                 :             : 
    1904                 :          63 :   x = load_struct;
    1905                 :          63 :   name = PHI_RESULT (red->keep_res);
    1906                 :          63 :   stmt = gimple_build_assign (name, x);
    1907                 :             : 
    1908                 :          63 :   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    1909                 :             : 
    1910                 :          63 :   for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
    1911                 :          71 :        !gsi_end_p (gsi); gsi_next (&gsi))
    1912                 :          71 :     if (gsi_stmt (gsi) == red->keep_res)
    1913                 :             :       {
    1914                 :          63 :         remove_phi_node (&gsi, false);
    1915                 :          63 :         return 1;
    1916                 :             :       }
    1917                 :           0 :   gcc_unreachable ();
    1918                 :             : }
    1919                 :             : 
    1920                 :             : /* Load the reduction result that was stored in LD_ST_DATA.
    1921                 :             :    REDUCTION_LIST describes the list of reductions that the
    1922                 :             :    loads should be generated for.  */
    1923                 :             : static void
    1924                 :          57 : create_final_loads_for_reduction (reduction_info_table_type *reduction_list,
    1925                 :             :                                   struct clsn_data *ld_st_data)
    1926                 :             : {
    1927                 :          57 :   gimple_stmt_iterator gsi;
    1928                 :          57 :   tree t;
    1929                 :          57 :   gimple *stmt;
    1930                 :             : 
    1931                 :          57 :   gsi = gsi_after_labels (ld_st_data->load_bb);
    1932                 :          57 :   t = build_fold_addr_expr (ld_st_data->store);
    1933                 :          57 :   stmt = gimple_build_assign (ld_st_data->load, t);
    1934                 :             : 
    1935                 :          57 :   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
    1936                 :             : 
    1937                 :          57 :   reduction_list
    1938                 :          57 :     ->traverse <struct clsn_data *, create_loads_for_reductions> (ld_st_data);
    1939                 :             : 
    1940                 :          57 : }
    1941                 :             : 
    1942                 :             : /* Callback for htab_traverse.  Store the neutral value for the
    1943                 :             :   particular reduction's operation, e.g. 0 for PLUS_EXPR,
    1944                 :             :   1 for MULT_EXPR, etc. into the reduction field.
    1945                 :             :   The reduction is specified in SLOT. The store information is
    1946                 :             :   passed in DATA.  */
    1947                 :             : 
    1948                 :             : int
    1949                 :          64 : create_stores_for_reduction (reduction_info **slot, struct clsn_data *clsn_data)
    1950                 :             : {
    1951                 :          64 :   struct reduction_info *const red = *slot;
    1952                 :          64 :   tree t;
    1953                 :          64 :   gimple *stmt;
    1954                 :          64 :   gimple_stmt_iterator gsi;
    1955                 :          64 :   tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
    1956                 :             : 
    1957                 :          64 :   gsi = gsi_last_bb (clsn_data->store_bb);
    1958                 :          64 :   t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
    1959                 :          64 :   stmt = gimple_build_assign (t, red->initial_value);
    1960                 :          64 :   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    1961                 :             : 
    1962                 :          64 :   return 1;
    1963                 :             : }
    1964                 :             : 
    1965                 :             : /* Callback for htab_traverse.  Creates loads to a field of LOAD in LOAD_BB and
    1966                 :             :    store to a field of STORE in STORE_BB for the ssa name and its duplicate
    1967                 :             :    specified in SLOT.  */
    1968                 :             : 
    1969                 :             : int
    1970                 :         433 : create_loads_and_stores_for_name (name_to_copy_elt **slot,
    1971                 :             :                                   struct clsn_data *clsn_data)
    1972                 :             : {
    1973                 :         433 :   struct name_to_copy_elt *const elt = *slot;
    1974                 :         433 :   tree t;
    1975                 :         433 :   gimple *stmt;
    1976                 :         433 :   gimple_stmt_iterator gsi;
    1977                 :         433 :   tree type = TREE_TYPE (elt->new_name);
    1978                 :         433 :   tree load_struct;
    1979                 :             : 
    1980                 :         433 :   gsi = gsi_last_bb (clsn_data->store_bb);
    1981                 :         433 :   t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
    1982                 :         433 :   stmt = gimple_build_assign (t, ssa_name (elt->version));
    1983                 :         433 :   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    1984                 :             : 
    1985                 :         433 :   gsi = gsi_last_bb (clsn_data->load_bb);
    1986                 :         433 :   load_struct = build_simple_mem_ref (clsn_data->load);
    1987                 :         433 :   t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
    1988                 :         433 :   stmt = gimple_build_assign (elt->new_name, t);
    1989                 :         433 :   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    1990                 :             : 
    1991                 :         433 :   return 1;
    1992                 :             : }
    1993                 :             : 
    1994                 :             : /* Moves all the variables used in LOOP and defined outside of it (including
    1995                 :             :    the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
    1996                 :             :    name) to a structure created for this purpose.  The code
    1997                 :             : 
    1998                 :             :    while (1)
    1999                 :             :      {
    2000                 :             :        use (a);
    2001                 :             :        use (b);
    2002                 :             :      }
    2003                 :             : 
    2004                 :             :    is transformed this way:
    2005                 :             : 
    2006                 :             :    bb0:
    2007                 :             :    old.a = a;
    2008                 :             :    old.b = b;
    2009                 :             : 
    2010                 :             :    bb1:
    2011                 :             :    a' = new->a;
    2012                 :             :    b' = new->b;
    2013                 :             :    while (1)
    2014                 :             :      {
    2015                 :             :        use (a');
    2016                 :             :        use (b');
    2017                 :             :      }
    2018                 :             : 
    2019                 :             :    `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT.  The
    2020                 :             :    pointer `new' is intentionally not initialized (the loop will be split to a
    2021                 :             :    separate function later, and `new' will be initialized from its arguments).
    2022                 :             :    LD_ST_DATA holds information about the shared data structure used to pass
    2023                 :             :    information among the threads.  It is initialized here, and
    2024                 :             :    gen_parallel_loop will pass it to create_call_for_reduction that
    2025                 :             :    needs this information.  REDUCTION_LIST describes the reductions
    2026                 :             :    in LOOP.  */
    2027                 :             : 
    2028                 :             : static void
    2029                 :         203 : separate_decls_in_region (edge entry, edge exit,
    2030                 :             :                           reduction_info_table_type *reduction_list,
    2031                 :             :                           tree *arg_struct, tree *new_arg_struct,
    2032                 :             :                           struct clsn_data *ld_st_data)
    2033                 :             : 
    2034                 :             : {
    2035                 :         203 :   basic_block bb1 = split_edge (entry);
    2036                 :         203 :   basic_block bb0 = single_pred (bb1);
    2037                 :         203 :   name_to_copy_table_type name_copies (10);
    2038                 :         203 :   int_tree_htab_type decl_copies (10);
    2039                 :         203 :   unsigned i;
    2040                 :         203 :   tree type, type_name, nvar;
    2041                 :         203 :   gimple_stmt_iterator gsi;
    2042                 :         203 :   struct clsn_data clsn_data;
    2043                 :         203 :   auto_vec<basic_block, 3> body;
    2044                 :         203 :   basic_block bb;
    2045                 :         203 :   basic_block entry_bb = bb1;
    2046                 :         203 :   basic_block exit_bb = exit->dest;
    2047                 :         203 :   bool has_debug_stmt = false;
    2048                 :             : 
    2049                 :         203 :   entry = single_succ_edge (entry_bb);
    2050                 :         203 :   gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
    2051                 :             : 
    2052                 :        1129 :   FOR_EACH_VEC_ELT (body, i, bb)
    2053                 :             :     {
    2054                 :         926 :       if (bb != entry_bb && bb != exit_bb)
    2055                 :             :         {
    2056                 :        1601 :           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2057                 :         878 :             separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
    2058                 :             :                                            &name_copies, &decl_copies);
    2059                 :             : 
    2060                 :        3676 :           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2061                 :             :             {
    2062                 :        2230 :               gimple *stmt = gsi_stmt (gsi);
    2063                 :             : 
    2064                 :        2230 :               if (is_gimple_debug (stmt))
    2065                 :             :                 has_debug_stmt = true;
    2066                 :             :               else
    2067                 :        2016 :                 separate_decls_in_region_stmt (entry, exit, stmt,
    2068                 :             :                                                &name_copies, &decl_copies);
    2069                 :             :             }
    2070                 :             :         }
    2071                 :             :     }
    2072                 :             : 
    2073                 :             :   /* Now process debug bind stmts.  We must not create decls while
    2074                 :             :      processing debug stmts, so we defer their processing so as to
    2075                 :             :      make sure we will have debug info for as many variables as
    2076                 :             :      possible (all of those that were dealt with in the loop above),
    2077                 :             :      and discard those for which we know there's nothing we can
    2078                 :             :      do.  */
    2079                 :         203 :   if (has_debug_stmt)
    2080                 :         151 :     FOR_EACH_VEC_ELT (body, i, bb)
    2081                 :         122 :       if (bb != entry_bb && bb != exit_bb)
    2082                 :             :         {
    2083                 :         604 :           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    2084                 :             :             {
    2085                 :         418 :               gimple *stmt = gsi_stmt (gsi);
    2086                 :             : 
    2087                 :         418 :               if (is_gimple_debug (stmt))
    2088                 :             :                 {
    2089                 :         214 :                   if (separate_decls_in_region_debug (stmt, &name_copies,
    2090                 :             :                                                       &decl_copies))
    2091                 :             :                     {
    2092                 :         132 :                       gsi_remove (&gsi, true);
    2093                 :         132 :                       continue;
    2094                 :             :                     }
    2095                 :             :                 }
    2096                 :             : 
    2097                 :         286 :               gsi_next (&gsi);
    2098                 :             :             }
    2099                 :             :         }
    2100                 :             : 
    2101                 :         203 :   if (name_copies.is_empty () && reduction_list->is_empty ())
    2102                 :             :     {
    2103                 :             :       /* It may happen that there is nothing to copy (if there are only
    2104                 :             :          loop carried and external variables in the loop).  */
    2105                 :          12 :       *arg_struct = NULL;
    2106                 :          12 :       *new_arg_struct = NULL;
    2107                 :             :     }
    2108                 :             :   else
    2109                 :             :     {
    2110                 :             :       /* Create the type for the structure to store the ssa names to.  */
    2111                 :         191 :       type = lang_hooks.types.make_type (RECORD_TYPE);
    2112                 :         191 :       type_name = build_decl (UNKNOWN_LOCATION,
    2113                 :             :                               TYPE_DECL, create_tmp_var_name (".paral_data"),
    2114                 :             :                               type);
    2115                 :         191 :       TYPE_NAME (type) = type_name;
    2116                 :             : 
    2117                 :         191 :       name_copies.traverse <tree, add_field_for_name> (type);
    2118                 :         191 :       if (reduction_list && !reduction_list->is_empty ())
    2119                 :             :         {
    2120                 :             :           /* Create the fields for reductions.  */
    2121                 :          57 :           reduction_list->traverse <tree, add_field_for_reduction> (type);
    2122                 :             :         }
    2123                 :         191 :       layout_type (type);
    2124                 :             : 
    2125                 :             :       /* Create the loads and stores.  */
    2126                 :         191 :       *arg_struct = create_tmp_var (type, ".paral_data_store");
    2127                 :         191 :       nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
    2128                 :         191 :       *new_arg_struct = make_ssa_name (nvar);
    2129                 :             : 
    2130                 :         191 :       ld_st_data->store = *arg_struct;
    2131                 :         191 :       ld_st_data->load = *new_arg_struct;
    2132                 :         191 :       ld_st_data->store_bb = bb0;
    2133                 :         191 :       ld_st_data->load_bb = bb1;
    2134                 :             : 
    2135                 :         191 :       name_copies
    2136                 :             :         .traverse <struct clsn_data *, create_loads_and_stores_for_name>
    2137                 :         191 :                   (ld_st_data);
    2138                 :             : 
    2139                 :             :       /* Load the calculation from memory (after the join of the threads).  */
    2140                 :             : 
    2141                 :         191 :       if (reduction_list && !reduction_list->is_empty ())
    2142                 :             :         {
    2143                 :          57 :           reduction_list
    2144                 :             :             ->traverse <struct clsn_data *, create_stores_for_reduction>
    2145                 :          57 :             (ld_st_data);
    2146                 :          57 :           clsn_data.load = make_ssa_name (nvar);
    2147                 :          57 :           clsn_data.load_bb = exit->dest;
    2148                 :          57 :           clsn_data.store = ld_st_data->store;
    2149                 :          57 :           create_final_loads_for_reduction (reduction_list, &clsn_data);
    2150                 :             :         }
    2151                 :             :     }
    2152                 :         203 : }
    2153                 :             : 
    2154                 :             : /* Returns true if FN was created to run in parallel.  */
    2155                 :             : 
    2156                 :             : bool
    2157                 :        1232 : parallelized_function_p (tree fndecl)
    2158                 :             : {
    2159                 :        1232 :   cgraph_node *node = cgraph_node::get (fndecl);
    2160                 :        1232 :   gcc_assert (node != NULL);
    2161                 :        1232 :   return node->parallelized_function;
    2162                 :             : }
    2163                 :             : 
    2164                 :             : /* Creates and returns an empty function that will receive the body of
    2165                 :             :    a parallelized loop.  */
    2166                 :             : 
    2167                 :             : static tree
    2168                 :         585 : create_loop_fn (location_t loc)
    2169                 :             : {
    2170                 :         585 :   char buf[100];
    2171                 :         585 :   char *tname;
    2172                 :         585 :   tree decl, type, name, t;
    2173                 :         585 :   struct function *act_cfun = cfun;
    2174                 :         585 :   static unsigned loopfn_num;
    2175                 :             : 
    2176                 :         585 :   loc = LOCATION_LOCUS (loc);
    2177                 :         585 :   snprintf (buf, 100, "%s.$loopfn", current_function_name ());
    2178                 :         585 :   ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
    2179                 :         585 :   clean_symbol_name (tname);
    2180                 :         585 :   name = get_identifier (tname);
    2181                 :         585 :   type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
    2182                 :             : 
    2183                 :         585 :   decl = build_decl (loc, FUNCTION_DECL, name, type);
    2184                 :         585 :   TREE_STATIC (decl) = 1;
    2185                 :         585 :   TREE_USED (decl) = 1;
    2186                 :         585 :   DECL_ARTIFICIAL (decl) = 1;
    2187                 :         585 :   DECL_IGNORED_P (decl) = 0;
    2188                 :         585 :   TREE_PUBLIC (decl) = 0;
    2189                 :         585 :   DECL_UNINLINABLE (decl) = 1;
    2190                 :         585 :   DECL_EXTERNAL (decl) = 0;
    2191                 :         585 :   DECL_CONTEXT (decl) = NULL_TREE;
    2192                 :         585 :   DECL_INITIAL (decl) = make_node (BLOCK);
    2193                 :         585 :   BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl;
    2194                 :             : 
    2195                 :         585 :   t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
    2196                 :         585 :   DECL_ARTIFICIAL (t) = 1;
    2197                 :         585 :   DECL_IGNORED_P (t) = 1;
    2198                 :         585 :   DECL_RESULT (decl) = t;
    2199                 :             : 
    2200                 :         585 :   t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
    2201                 :             :                   ptr_type_node);
    2202                 :         585 :   DECL_ARTIFICIAL (t) = 1;
    2203                 :         585 :   DECL_ARG_TYPE (t) = ptr_type_node;
    2204                 :         585 :   DECL_CONTEXT (t) = decl;
    2205                 :         585 :   TREE_USED (t) = 1;
    2206                 :         585 :   DECL_ARGUMENTS (decl) = t;
    2207                 :        1170 :   DECL_FUNCTION_SPECIFIC_TARGET (decl)
    2208                 :         585 :     = DECL_FUNCTION_SPECIFIC_TARGET (act_cfun->decl);
    2209                 :        1170 :   DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl)
    2210                 :         585 :     = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (act_cfun->decl);
    2211                 :             : 
    2212                 :             : 
    2213                 :         585 :   allocate_struct_function (decl, false);
    2214                 :             : 
    2215                 :             :   /* The call to allocate_struct_function clobbers CFUN, so we need to restore
    2216                 :             :      it.  */
    2217                 :         585 :   set_cfun (act_cfun);
    2218                 :             : 
    2219                 :         585 :   return decl;
    2220                 :             : }
    2221                 :             : 
    2222                 :             : /* Replace uses of NAME by VAL in block BB.  */
    2223                 :             : 
    2224                 :             : static void
    2225                 :        2236 : replace_uses_in_bb_by (tree name, tree val, basic_block bb)
    2226                 :             : {
    2227                 :        2236 :   gimple *use_stmt;
    2228                 :        2236 :   imm_use_iterator imm_iter;
    2229                 :             : 
    2230                 :        5793 :   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
    2231                 :             :     {
    2232                 :        3557 :       if (gimple_bb (use_stmt) != bb)
    2233                 :        2441 :         continue;
    2234                 :             : 
    2235                 :        1116 :       use_operand_p use_p;
    2236                 :        4464 :       FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
    2237                 :        1116 :         SET_USE (use_p, val);
    2238                 :        2236 :     }
    2239                 :        2236 : }
    2240                 :             : 
    2241                 :             : /* Do transformation from:
    2242                 :             : 
    2243                 :             :      <bb preheader>:
    2244                 :             :      ...
    2245                 :             :      goto <bb header>
    2246                 :             : 
    2247                 :             :      <bb header>:
    2248                 :             :      ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
    2249                 :             :      sum_a = PHI <sum_init (preheader), sum_b (latch)>
    2250                 :             :      ...
    2251                 :             :      use (ivtmp_a)
    2252                 :             :      ...
    2253                 :             :      sum_b = sum_a + sum_update
    2254                 :             :      ...
    2255                 :             :      if (ivtmp_a < n)
    2256                 :             :        goto <bb latch>;
    2257                 :             :      else
    2258                 :             :        goto <bb exit>;
    2259                 :             : 
    2260                 :             :      <bb latch>:
    2261                 :             :      ivtmp_b = ivtmp_a + 1;
    2262                 :             :      goto <bb header>
    2263                 :             : 
    2264                 :             :      <bb exit>:
    2265                 :             :      sum_z = PHI <sum_b (cond[1]), ...>
    2266                 :             : 
    2267                 :             :      [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
    2268                 :             :          that's <bb header>.
    2269                 :             : 
    2270                 :             :    to:
    2271                 :             : 
    2272                 :             :      <bb preheader>:
    2273                 :             :      ...
    2274                 :             :      goto <bb newheader>
    2275                 :             : 
    2276                 :             :      <bb header>:
    2277                 :             :      ivtmp_a = PHI <ivtmp_c (latch)>
    2278                 :             :      sum_a = PHI <sum_c (latch)>
    2279                 :             :      ...
    2280                 :             :      use (ivtmp_a)
    2281                 :             :      ...
    2282                 :             :      sum_b = sum_a + sum_update
    2283                 :             :      ...
    2284                 :             :      goto <bb latch>;
    2285                 :             : 
    2286                 :             :      <bb newheader>:
    2287                 :             :      ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
    2288                 :             :      sum_c = PHI <sum_init (preheader), sum_b (latch)>
    2289                 :             :      if (ivtmp_c < n + 1)
    2290                 :             :        goto <bb header>;
    2291                 :             :      else
    2292                 :             :        goto <bb newexit>;
    2293                 :             : 
    2294                 :             :      <bb latch>:
    2295                 :             :      ivtmp_b = ivtmp_a + 1;
    2296                 :             :      goto <bb newheader>
    2297                 :             : 
    2298                 :             :      <bb newexit>:
    2299                 :             :      sum_y = PHI <sum_c (newheader)>
    2300                 :             : 
    2301                 :             :      <bb exit>:
    2302                 :             :      sum_z = PHI <sum_y (newexit), ...>
    2303                 :             : 
    2304                 :             : 
    2305                 :             :    In unified diff format:
    2306                 :             : 
    2307                 :             :       <bb preheader>:
    2308                 :             :       ...
    2309                 :             : -     goto <bb header>
    2310                 :             : +     goto <bb newheader>
    2311                 :             : 
    2312                 :             :       <bb header>:
    2313                 :             : -     ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
    2314                 :             : -     sum_a = PHI <sum_init (preheader), sum_b (latch)>
    2315                 :             : +     ivtmp_a = PHI <ivtmp_c (latch)>
    2316                 :             : +     sum_a = PHI <sum_c (latch)>
    2317                 :             :       ...
    2318                 :             :       use (ivtmp_a)
    2319                 :             :       ...
    2320                 :             :       sum_b = sum_a + sum_update
    2321                 :             :       ...
    2322                 :             : -     if (ivtmp_a < n)
    2323                 :             : -       goto <bb latch>;
    2324                 :             : +     goto <bb latch>;
    2325                 :             : +
    2326                 :             : +     <bb newheader>:
    2327                 :             : +     ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
    2328                 :             : +     sum_c = PHI <sum_init (preheader), sum_b (latch)>
    2329                 :             : +     if (ivtmp_c < n + 1)
    2330                 :             : +       goto <bb header>;
    2331                 :             :       else
    2332                 :             :         goto <bb exit>;
    2333                 :             : 
    2334                 :             :       <bb latch>:
    2335                 :             :       ivtmp_b = ivtmp_a + 1;
    2336                 :             : -     goto <bb header>
    2337                 :             : +     goto <bb newheader>
    2338                 :             : 
    2339                 :             : +    <bb newexit>:
    2340                 :             : +    sum_y = PHI <sum_c (newheader)>
    2341                 :             : 
    2342                 :             :       <bb exit>:
    2343                 :             : -     sum_z = PHI <sum_b (cond[1]), ...>
    2344                 :             : +     sum_z = PHI <sum_y (newexit), ...>
    2345                 :             : 
    2346                 :             :    Note: the example does not show any virtual phis, but these are handled more
    2347                 :             :    or less as reductions.
    2348                 :             : 
    2349                 :             : 
    2350                 :             :    Moves the exit condition of LOOP to the beginning of its header.
    2351                 :             :    REDUCTION_LIST describes the reductions in LOOP.  BOUND is the new loop
    2352                 :             :    bound.  */
    2353                 :             : 
    2354                 :             : static void
    2355                 :         561 : transform_to_exit_first_loop_alt (class loop *loop,
    2356                 :             :                                   reduction_info_table_type *reduction_list,
    2357                 :             :                                   tree bound)
    2358                 :             : {
    2359                 :         561 :   basic_block header = loop->header;
    2360                 :         561 :   basic_block latch = loop->latch;
    2361                 :         561 :   edge exit = single_dom_exit (loop);
    2362                 :         561 :   basic_block exit_block = exit->dest;
    2363                 :        1122 :   gcond *cond_stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
    2364                 :         561 :   tree control = gimple_cond_lhs (cond_stmt);
    2365                 :         561 :   edge e;
    2366                 :             : 
    2367                 :             :   /* Create the new_header block.  */
    2368                 :         561 :   basic_block new_header = split_block_before_cond_jump (exit->src);
    2369                 :         561 :   edge edge_at_split = single_pred_edge (new_header);
    2370                 :             : 
    2371                 :             :   /* Redirect entry edge to new_header.  */
    2372                 :         561 :   edge entry = loop_preheader_edge (loop);
    2373                 :         561 :   e = redirect_edge_and_branch (entry, new_header);
    2374                 :         561 :   gcc_assert (e == entry);
    2375                 :             : 
    2376                 :             :   /* Redirect post_inc_edge to new_header.  */
    2377                 :         561 :   edge post_inc_edge = single_succ_edge (latch);
    2378                 :         561 :   e = redirect_edge_and_branch (post_inc_edge, new_header);
    2379                 :         561 :   gcc_assert (e == post_inc_edge);
    2380                 :             : 
    2381                 :             :   /* Redirect post_cond_edge to header.  */
    2382                 :         561 :   edge post_cond_edge = single_pred_edge (latch);
    2383                 :         561 :   e = redirect_edge_and_branch (post_cond_edge, header);
    2384                 :         561 :   gcc_assert (e == post_cond_edge);
    2385                 :             : 
    2386                 :             :   /* Redirect edge_at_split to latch.  */
    2387                 :         561 :   e = redirect_edge_and_branch (edge_at_split, latch);
    2388                 :         561 :   gcc_assert (e == edge_at_split);
    2389                 :             : 
    2390                 :             :   /* Set the new loop bound.  */
    2391                 :         561 :   gimple_cond_set_rhs (cond_stmt, bound);
    2392                 :         561 :   update_stmt (cond_stmt);
    2393                 :             : 
    2394                 :             :   /* Repair the ssa.  */
    2395                 :         561 :   vec<edge_var_map> *v = redirect_edge_var_map_vector (post_inc_edge);
    2396                 :         561 :   edge_var_map *vm;
    2397                 :         561 :   gphi_iterator gsi;
    2398                 :         561 :   int i;
    2399                 :         561 :   for (gsi = gsi_start_phis (header), i = 0;
    2400                 :        1679 :        !gsi_end_p (gsi) && v->iterate (i, &vm);
    2401                 :        1118 :        gsi_next (&gsi), i++)
    2402                 :             :     {
    2403                 :        1118 :       gphi *phi = gsi.phi ();
    2404                 :        1118 :       tree res_a = PHI_RESULT (phi);
    2405                 :             : 
    2406                 :             :       /* Create new phi.  */
    2407                 :        1118 :       tree res_c = copy_ssa_name (res_a, phi);
    2408                 :        1118 :       gphi *nphi = create_phi_node (res_c, new_header);
    2409                 :             : 
    2410                 :             :       /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'.  */
    2411                 :        1118 :       replace_uses_in_bb_by (res_a, res_c, new_header);
    2412                 :             : 
    2413                 :             :       /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi.  */
    2414                 :        1118 :       add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION);
    2415                 :             : 
    2416                 :             :       /* Replace sum_b with sum_c in exit phi.  */
    2417                 :        1118 :       tree res_b = redirect_edge_var_map_def (vm);
    2418                 :        1118 :       replace_uses_in_bb_by (res_b, res_c, exit_block);
    2419                 :             : 
    2420                 :        1118 :       struct reduction_info *red = reduction_phi (reduction_list, phi);
    2421                 :        2236 :       gcc_assert (virtual_operand_p (res_a)
    2422                 :             :                   || res_a == control
    2423                 :             :                   || red != NULL);
    2424                 :             : 
    2425                 :        1118 :       if (red)
    2426                 :             :         {
    2427                 :             :           /* Register the new reduction phi.  */
    2428                 :          77 :           red->reduc_phi = nphi;
    2429                 :          77 :           gimple_set_uid (red->reduc_phi, red->reduc_version);
    2430                 :             :         }
    2431                 :             :     }
    2432                 :         561 :   gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm));
    2433                 :             : 
    2434                 :             :   /* Set the preheader argument of the new phis to ivtmp/sum_init.  */
    2435                 :         561 :   flush_pending_stmts (entry);
    2436                 :             : 
    2437                 :             :   /* Set the latch arguments of the new phis to ivtmp/sum_b.  */
    2438                 :         561 :   flush_pending_stmts (post_inc_edge);
    2439                 :             : 
    2440                 :             : 
    2441                 :         561 :   basic_block new_exit_block = NULL;
    2442                 :        1122 :   if (!single_pred_p (exit->dest))
    2443                 :             :     {
    2444                 :             :       /* Create a new empty exit block, inbetween the new loop header and the
    2445                 :             :          old exit block.  The function separate_decls_in_region needs this block
    2446                 :             :          to insert code that is active on loop exit, but not any other path.  */
    2447                 :         179 :       new_exit_block = split_edge (exit);
    2448                 :             :     }
    2449                 :             : 
    2450                 :             :   /* Insert and register the reduction exit phis.  */
    2451                 :         561 :   for (gphi_iterator gsi = gsi_start_phis (exit_block);
    2452                 :        1116 :        !gsi_end_p (gsi);
    2453                 :         555 :        gsi_next (&gsi))
    2454                 :             :     {
    2455                 :         555 :       gphi *phi = gsi.phi ();
    2456                 :         555 :       gphi *nphi = NULL;
    2457                 :         555 :       tree res_z = PHI_RESULT (phi);
    2458                 :         555 :       tree res_c;
    2459                 :             : 
    2460                 :         555 :       if (new_exit_block != NULL)
    2461                 :             :         {
    2462                 :             :           /* Now that we have a new exit block, duplicate the phi of the old
    2463                 :             :              exit block in the new exit block to preserve loop-closed ssa.  */
    2464                 :         169 :           edge succ_new_exit_block = single_succ_edge (new_exit_block);
    2465                 :         169 :           edge pred_new_exit_block = single_pred_edge (new_exit_block);
    2466                 :         169 :           tree res_y = copy_ssa_name (res_z, phi);
    2467                 :         169 :           nphi = create_phi_node (res_y, new_exit_block);
    2468                 :         169 :           res_c = PHI_ARG_DEF_FROM_EDGE (phi, succ_new_exit_block);
    2469                 :         169 :           add_phi_arg (nphi, res_c, pred_new_exit_block, UNKNOWN_LOCATION);
    2470                 :         169 :           add_phi_arg (phi, res_y, succ_new_exit_block, UNKNOWN_LOCATION);
    2471                 :             :         }
    2472                 :             :       else
    2473                 :         386 :         res_c = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    2474                 :             : 
    2475                 :        1110 :       if (virtual_operand_p (res_z))
    2476                 :         479 :         continue;
    2477                 :             : 
    2478                 :          76 :       gimple *reduc_phi = SSA_NAME_DEF_STMT (res_c);
    2479                 :          76 :       struct reduction_info *red = reduction_phi (reduction_list, reduc_phi);
    2480                 :          76 :       if (red != NULL)
    2481                 :          76 :         red->keep_res = (nphi != NULL
    2482                 :          76 :                          ? nphi
    2483                 :             :                          : phi);
    2484                 :             :     }
    2485                 :             : 
    2486                 :             :   /* We're going to cancel the loop at the end of gen_parallel_loop, but until
    2487                 :             :      then we're still using some fields, so only bother about fields that are
    2488                 :             :      still used: header and latch.
    2489                 :             :      The loop has a new header bb, so we update it.  The latch bb stays the
    2490                 :             :      same.  */
    2491                 :         561 :   loop->header = new_header;
    2492                 :             : 
    2493                 :             :   /* Recalculate dominance info.  */
    2494                 :         561 :   free_dominance_info (CDI_DOMINATORS);
    2495                 :         561 :   calculate_dominance_info (CDI_DOMINATORS);
    2496                 :         561 : }
    2497                 :             : 
    2498                 :             : /* Tries to moves the exit condition of LOOP to the beginning of its header
    2499                 :             :    without duplication of the loop body.  NIT is the number of iterations of the
    2500                 :             :    loop.  REDUCTION_LIST describes the reductions in LOOP.  Return true if
    2501                 :             :    transformation is successful.  */
    2502                 :             : 
    2503                 :             : static bool
    2504                 :         585 : try_transform_to_exit_first_loop_alt (class loop *loop,
    2505                 :             :                                       reduction_info_table_type *reduction_list,
    2506                 :             :                                       tree nit)
    2507                 :             : {
    2508                 :             :   /* Check whether the latch contains a single statement.  */
    2509                 :        1170 :   if (!gimple_seq_nondebug_singleton_p (bb_seq (loop->latch)))
    2510                 :             :     return false;
    2511                 :             : 
    2512                 :             :   /* Check whether the latch contains no phis.  */
    2513                 :         581 :   if (phi_nodes (loop->latch) != NULL)
    2514                 :             :     return false;
    2515                 :             : 
    2516                 :             :   /* Check whether the latch contains the loop iv increment.  */
    2517                 :         581 :   edge back = single_succ_edge (loop->latch);
    2518                 :         581 :   edge exit = single_dom_exit (loop);
    2519                 :        1162 :   gcond *cond_stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
    2520                 :         581 :   tree control = gimple_cond_lhs (cond_stmt);
    2521                 :         581 :   gphi *phi = as_a <gphi *> (SSA_NAME_DEF_STMT (control));
    2522                 :         581 :   tree inc_res = gimple_phi_arg_def (phi, back->dest_idx);
    2523                 :         581 :   if (gimple_bb (SSA_NAME_DEF_STMT (inc_res)) != loop->latch)
    2524                 :             :     return false;
    2525                 :             : 
    2526                 :             :   /* Check whether there's no code between the loop condition and the latch.  */
    2527                 :         581 :   if (!single_pred_p (loop->latch)
    2528                 :         581 :       || single_pred (loop->latch) != exit->src)
    2529                 :             :     return false;
    2530                 :             : 
    2531                 :         581 :   tree alt_bound = NULL_TREE;
    2532                 :         581 :   tree nit_type = TREE_TYPE (nit);
    2533                 :             : 
    2534                 :             :   /* Figure out whether nit + 1 overflows.  */
    2535                 :         581 :   if (poly_int_tree_p (nit))
    2536                 :             :     {
    2537                 :         431 :       if (!tree_int_cst_equal (nit, TYPE_MAX_VALUE (nit_type)))
    2538                 :             :         {
    2539                 :         431 :           alt_bound = fold_build2_loc (UNKNOWN_LOCATION, PLUS_EXPR, nit_type,
    2540                 :             :                                        nit, build_one_cst (nit_type));
    2541                 :             : 
    2542                 :         431 :           gcc_assert (TREE_CODE (alt_bound) == INTEGER_CST
    2543                 :             :                       || TREE_CODE (alt_bound) == POLY_INT_CST);
    2544                 :         431 :           transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
    2545                 :         431 :           return true;
    2546                 :             :         }
    2547                 :             :       else
    2548                 :             :         {
    2549                 :             :           /* Todo: Figure out if we can trigger this, if it's worth to handle
    2550                 :             :              optimally, and if we can handle it optimally.  */
    2551                 :             :           return false;
    2552                 :             :         }
    2553                 :             :     }
    2554                 :             : 
    2555                 :         150 :   gcc_assert (TREE_CODE (nit) == SSA_NAME);
    2556                 :             : 
    2557                 :             :   /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
    2558                 :             :      iv with base 0 and step 1 that is incremented in the latch, like this:
    2559                 :             : 
    2560                 :             :      <bb header>:
    2561                 :             :      # iv_1 = PHI <0 (preheader), iv_2 (latch)>
    2562                 :             :      ...
    2563                 :             :      if (iv_1 < nit)
    2564                 :             :        goto <bb latch>;
    2565                 :             :      else
    2566                 :             :        goto <bb exit>;
    2567                 :             : 
    2568                 :             :      <bb latch>:
    2569                 :             :      iv_2 = iv_1 + 1;
    2570                 :             :      goto <bb header>;
    2571                 :             : 
    2572                 :             :      The range of iv_1 is [0, nit].  The latch edge is taken for
    2573                 :             :      iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit.  So the
    2574                 :             :      number of latch executions is equal to nit.
    2575                 :             : 
    2576                 :             :      The function max_loop_iterations gives us the maximum number of latch
    2577                 :             :      executions, so it gives us the maximum value of nit.  */
    2578                 :         150 :   widest_int nit_max;
    2579                 :         150 :   if (!max_loop_iterations (loop, &nit_max))
    2580                 :             :     return false;
    2581                 :             : 
    2582                 :             :   /* Check if nit + 1 overflows.  */
    2583                 :         150 :   widest_int type_max = wi::to_widest (TYPE_MAX_VALUE (nit_type));
    2584                 :         150 :   if (nit_max >= type_max)
    2585                 :             :     return false;
    2586                 :             : 
    2587                 :         130 :   gimple *def = SSA_NAME_DEF_STMT (nit);
    2588                 :             : 
    2589                 :             :   /* Try to find nit + 1, in the form of n in an assignment nit = n - 1.  */
    2590                 :         130 :   if (def
    2591                 :         130 :       && is_gimple_assign (def)
    2592                 :         259 :       && gimple_assign_rhs_code (def) == PLUS_EXPR)
    2593                 :             :     {
    2594                 :          23 :       tree op1 = gimple_assign_rhs1 (def);
    2595                 :          23 :       tree op2 = gimple_assign_rhs2 (def);
    2596                 :          23 :       if (integer_minus_onep (op1))
    2597                 :             :         alt_bound = op2;
    2598                 :          23 :       else if (integer_minus_onep (op2))
    2599                 :             :         alt_bound = op1;
    2600                 :             :     }
    2601                 :             : 
    2602                 :             :   /* If not found, insert nit + 1.  */
    2603                 :          23 :   if (alt_bound == NULL_TREE)
    2604                 :             :     {
    2605                 :         107 :       alt_bound = fold_build2 (PLUS_EXPR, nit_type, nit,
    2606                 :             :                                build_int_cst_type (nit_type, 1));
    2607                 :             : 
    2608                 :         107 :       gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
    2609                 :             : 
    2610                 :         107 :       alt_bound
    2611                 :         107 :         = force_gimple_operand_gsi (&gsi, alt_bound, true, NULL_TREE, false,
    2612                 :             :                                     GSI_CONTINUE_LINKING);
    2613                 :             :     }
    2614                 :             : 
    2615                 :         130 :   transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
    2616                 :         130 :   return true;
    2617                 :         300 : }
    2618                 :             : 
    2619                 :             : /* Moves the exit condition of LOOP to the beginning of its header.  NIT is the
    2620                 :             :    number of iterations of the loop.  REDUCTION_LIST describes the reductions in
    2621                 :             :    LOOP.  */
    2622                 :             : 
    2623                 :             : static void
    2624                 :          24 : transform_to_exit_first_loop (class loop *loop,
    2625                 :             :                               reduction_info_table_type *reduction_list,
    2626                 :             :                               tree nit)
    2627                 :             : {
    2628                 :          24 :   basic_block *bbs, *nbbs, ex_bb, orig_header;
    2629                 :          24 :   unsigned n;
    2630                 :          24 :   bool ok;
    2631                 :          24 :   edge exit = single_dom_exit (loop), hpred;
    2632                 :          24 :   tree control, control_name, res, t;
    2633                 :          24 :   gphi *phi, *nphi;
    2634                 :          24 :   gassign *stmt;
    2635                 :          24 :   gcond *cond_stmt, *cond_nit;
    2636                 :          24 :   tree nit_1;
    2637                 :             : 
    2638                 :          24 :   split_block_after_labels (loop->header);
    2639                 :          24 :   orig_header = single_succ (loop->header);
    2640                 :          24 :   hpred = single_succ_edge (loop->header);
    2641                 :             : 
    2642                 :          48 :   cond_stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
    2643                 :          24 :   control = gimple_cond_lhs (cond_stmt);
    2644                 :          24 :   gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
    2645                 :             : 
    2646                 :             :   /* Make sure that we have phi nodes on exit for all loop header phis
    2647                 :             :      (create_parallel_loop requires that).  */
    2648                 :          24 :   for (gphi_iterator gsi = gsi_start_phis (loop->header);
    2649                 :          63 :        !gsi_end_p (gsi);
    2650                 :          39 :        gsi_next (&gsi))
    2651                 :             :     {
    2652                 :          39 :       phi = gsi.phi ();
    2653                 :          39 :       res = PHI_RESULT (phi);
    2654                 :          39 :       t = copy_ssa_name (res, phi);
    2655                 :          39 :       SET_PHI_RESULT (phi, t);
    2656                 :          39 :       nphi = create_phi_node (res, orig_header);
    2657                 :          39 :       add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
    2658                 :             : 
    2659                 :          39 :       if (res == control)
    2660                 :             :         {
    2661                 :          24 :           gimple_cond_set_lhs (cond_stmt, t);
    2662                 :          24 :           update_stmt (cond_stmt);
    2663                 :          24 :           control = t;
    2664                 :             :         }
    2665                 :             :     }
    2666                 :             : 
    2667                 :          24 :   bbs = get_loop_body_in_dom_order (loop);
    2668                 :             : 
    2669                 :          74 :   for (n = 0; bbs[n] != exit->src; n++)
    2670                 :          26 :    continue;
    2671                 :          24 :   nbbs = XNEWVEC (basic_block, n);
    2672                 :          24 :   ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
    2673                 :             :                                    bbs + 1, n, nbbs);
    2674                 :          24 :   gcc_assert (ok);
    2675                 :          24 :   free (bbs);
    2676                 :          24 :   ex_bb = nbbs[0];
    2677                 :          24 :   free (nbbs);
    2678                 :             : 
    2679                 :             :   /* Other than reductions, the only gimple reg that should be copied
    2680                 :             :      out of the loop is the control variable.  */
    2681                 :          24 :   exit = single_dom_exit (loop);
    2682                 :          24 :   control_name = NULL_TREE;
    2683                 :          24 :   for (gphi_iterator gsi = gsi_start_phis (ex_bb);
    2684                 :          63 :        !gsi_end_p (gsi); )
    2685                 :             :     {
    2686                 :          39 :       phi = gsi.phi ();
    2687                 :          39 :       res = PHI_RESULT (phi);
    2688                 :          78 :       if (virtual_operand_p (res))
    2689                 :             :         {
    2690                 :          14 :           gsi_next (&gsi);
    2691                 :          14 :           continue;
    2692                 :             :         }
    2693                 :             : 
    2694                 :             :       /* Check if it is a part of reduction.  If it is,
    2695                 :             :          keep the phi at the reduction's keep_res field.  The
    2696                 :             :          PHI_RESULT of this phi is the resulting value of the reduction
    2697                 :             :          variable when exiting the loop.  */
    2698                 :             : 
    2699                 :          25 :       if (!reduction_list->is_empty ())
    2700                 :             :         {
    2701                 :           2 :           struct reduction_info *red;
    2702                 :             : 
    2703                 :           2 :           tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    2704                 :           2 :           red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
    2705                 :           2 :           if (red)
    2706                 :             :             {
    2707                 :           1 :               red->keep_res = phi;
    2708                 :           1 :               gsi_next (&gsi);
    2709                 :           1 :               continue;
    2710                 :             :             }
    2711                 :             :         }
    2712                 :          96 :       gcc_assert (control_name == NULL_TREE
    2713                 :             :                   && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
    2714                 :          24 :       control_name = res;
    2715                 :          24 :       remove_phi_node (&gsi, false);
    2716                 :             :     }
    2717                 :          24 :   gcc_assert (control_name != NULL_TREE);
    2718                 :             : 
    2719                 :             :   /* Initialize the control variable to number of iterations
    2720                 :             :      according to the rhs of the exit condition.  */
    2721                 :          24 :   gimple_stmt_iterator gsi = gsi_after_labels (ex_bb);
    2722                 :          48 :   cond_nit = as_a <gcond *> (*gsi_last_bb (exit->src));
    2723                 :          24 :   nit_1 =  gimple_cond_rhs (cond_nit);
    2724                 :          24 :   nit_1 = force_gimple_operand_gsi (&gsi,
    2725                 :          24 :                                   fold_convert (TREE_TYPE (control_name), nit_1),
    2726                 :             :                                   false, NULL_TREE, false, GSI_SAME_STMT);
    2727                 :          24 :   stmt = gimple_build_assign (control_name, nit_1);
    2728                 :          24 :   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
    2729                 :          26 : }
    2730                 :             : 
    2731                 :             : /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
    2732                 :             :    LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
    2733                 :             :    NEW_DATA is the variable that should be initialized from the argument
    2734                 :             :    of LOOP_FN.  N_THREADS is the requested number of threads, which can be 0 if
    2735                 :             :    that number is to be determined later.  */
    2736                 :             : 
    2737                 :             : static void
    2738                 :         585 : create_parallel_loop (class loop *loop, tree loop_fn, tree data,
    2739                 :             :                       tree new_data, unsigned n_threads, location_t loc,
    2740                 :             :                       bool oacc_kernels_p)
    2741                 :             : {
    2742                 :         585 :   gimple_stmt_iterator gsi;
    2743                 :         585 :   basic_block for_bb, ex_bb, continue_bb;
    2744                 :         585 :   tree t, param;
    2745                 :         585 :   gomp_parallel *omp_par_stmt;
    2746                 :         585 :   gimple *omp_return_stmt1, *omp_return_stmt2;
    2747                 :         585 :   gimple *phi;
    2748                 :         585 :   gcond *cond_stmt;
    2749                 :         585 :   gomp_for *for_stmt;
    2750                 :         585 :   gomp_continue *omp_cont_stmt;
    2751                 :         585 :   tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
    2752                 :         585 :   edge exit, nexit, guard, end, e;
    2753                 :             : 
    2754                 :         585 :   if (oacc_kernels_p)
    2755                 :             :     {
    2756                 :         382 :       gcc_checking_assert (lookup_attribute ("oacc kernels",
    2757                 :             :                                              DECL_ATTRIBUTES (cfun->decl)));
    2758                 :             :       /* Indicate to later processing that this is a parallelized OpenACC
    2759                 :             :          kernels construct.  */
    2760                 :         382 :       DECL_ATTRIBUTES (cfun->decl)
    2761                 :         764 :         = tree_cons (get_identifier ("oacc kernels parallelized"),
    2762                 :         382 :                      NULL_TREE, DECL_ATTRIBUTES (cfun->decl));
    2763                 :             :     }
    2764                 :             :   else
    2765                 :             :     {
    2766                 :             :       /* Prepare the GIMPLE_OMP_PARALLEL statement.  */
    2767                 :             : 
    2768                 :         203 :       basic_block bb = loop_preheader_edge (loop)->src;
    2769                 :         203 :       basic_block paral_bb = single_pred (bb);
    2770                 :         203 :       gsi = gsi_last_bb (paral_bb);
    2771                 :             : 
    2772                 :         203 :       gcc_checking_assert (n_threads != 0);
    2773                 :         203 :       t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
    2774                 :         203 :       OMP_CLAUSE_NUM_THREADS_EXPR (t)
    2775                 :         203 :         = build_int_cst (integer_type_node, n_threads);
    2776                 :         203 :       omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
    2777                 :         203 :       gimple_set_location (omp_par_stmt, loc);
    2778                 :             : 
    2779                 :         203 :       gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
    2780                 :             : 
    2781                 :             :       /* Initialize NEW_DATA.  */
    2782                 :         203 :       if (data)
    2783                 :             :         {
    2784                 :         191 :           gassign *assign_stmt;
    2785                 :             : 
    2786                 :         191 :           gsi = gsi_after_labels (bb);
    2787                 :             : 
    2788                 :         191 :           param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
    2789                 :         191 :           assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
    2790                 :         191 :           gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
    2791                 :             : 
    2792                 :         191 :           assign_stmt = gimple_build_assign (new_data,
    2793                 :         191 :                                              fold_convert (TREE_TYPE (new_data), param));
    2794                 :         191 :           gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
    2795                 :             :         }
    2796                 :             : 
    2797                 :             :       /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL.  */
    2798                 :         203 :       bb = split_loop_exit_edge (single_dom_exit (loop));
    2799                 :         203 :       gsi = gsi_last_bb (bb);
    2800                 :         203 :       omp_return_stmt1 = gimple_build_omp_return (false);
    2801                 :         203 :       gimple_set_location (omp_return_stmt1, loc);
    2802                 :         203 :       gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
    2803                 :             :     }
    2804                 :             : 
    2805                 :             :   /* Extract data for GIMPLE_OMP_FOR.  */
    2806                 :         585 :   gcc_assert (loop->header == single_dom_exit (loop)->src);
    2807                 :        1170 :   cond_stmt = as_a <gcond *> (*gsi_last_bb (loop->header));
    2808                 :             : 
    2809                 :         585 :   cvar = gimple_cond_lhs (cond_stmt);
    2810                 :         585 :   cvar_base = SSA_NAME_VAR (cvar);
    2811                 :         585 :   phi = SSA_NAME_DEF_STMT (cvar);
    2812                 :         585 :   cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
    2813                 :         585 :   initvar = copy_ssa_name (cvar);
    2814                 :         585 :   SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
    2815                 :             :            initvar);
    2816                 :         585 :   cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
    2817                 :             : 
    2818                 :         585 :   gsi = gsi_last_nondebug_bb (loop->latch);
    2819                 :         585 :   gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
    2820                 :         585 :   gsi_remove (&gsi, true);
    2821                 :             : 
    2822                 :             :   /* Prepare cfg.  */
    2823                 :         585 :   for_bb = split_edge (loop_preheader_edge (loop));
    2824                 :         585 :   ex_bb = split_loop_exit_edge (single_dom_exit (loop));
    2825                 :         585 :   extract_true_false_edges_from_block (loop->header, &nexit, &exit);
    2826                 :         585 :   gcc_assert (exit == single_dom_exit (loop));
    2827                 :             : 
    2828                 :         585 :   guard = make_edge (for_bb, ex_bb, 0);
    2829                 :             :   /* FIXME: What is the probability?  */
    2830                 :         585 :   guard->probability = profile_probability::guessed_never ();
    2831                 :             :   /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid.  */
    2832                 :         585 :   loop->latch = split_edge (single_succ_edge (loop->latch));
    2833                 :         585 :   single_pred_edge (loop->latch)->flags = 0;
    2834                 :         585 :   end = make_single_succ_edge (single_pred (loop->latch), ex_bb, EDGE_FALLTHRU);
    2835                 :         585 :   rescan_loop_exit (end, true, false);
    2836                 :             : 
    2837                 :         585 :   for (gphi_iterator gpi = gsi_start_phis (ex_bb);
    2838                 :        1092 :        !gsi_end_p (gpi); gsi_next (&gpi))
    2839                 :             :     {
    2840                 :         507 :       location_t locus;
    2841                 :         507 :       gphi *phi = gpi.phi ();
    2842                 :         507 :       tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    2843                 :         507 :       gimple *def_stmt = SSA_NAME_DEF_STMT (def);
    2844                 :             : 
    2845                 :             :       /* If the exit phi is not connected to a header phi in the same loop, this
    2846                 :             :          value is not modified in the loop, and we're done with this phi.  */
    2847                 :         507 :       if (!(gimple_code (def_stmt) == GIMPLE_PHI
    2848                 :         507 :             && gimple_bb (def_stmt) == loop->header))
    2849                 :             :         {
    2850                 :           0 :           locus = gimple_phi_arg_location_from_edge (phi, exit);
    2851                 :           0 :           add_phi_arg (phi, def, guard, locus);
    2852                 :           0 :           add_phi_arg (phi, def, end, locus);
    2853                 :           0 :           continue;
    2854                 :             :         }
    2855                 :             : 
    2856                 :         507 :       gphi *stmt = as_a <gphi *> (def_stmt);
    2857                 :         507 :       def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
    2858                 :         507 :       locus = gimple_phi_arg_location_from_edge (stmt,
    2859                 :             :                                                  loop_preheader_edge (loop));
    2860                 :         507 :       add_phi_arg (phi, def, guard, locus);
    2861                 :             : 
    2862                 :         507 :       def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
    2863                 :         507 :       locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
    2864                 :         507 :       add_phi_arg (phi, def, end, locus);
    2865                 :             :     }
    2866                 :         585 :   e = redirect_edge_and_branch (exit, nexit->dest);
    2867                 :         585 :   PENDING_STMT (e) = NULL;
    2868                 :             : 
    2869                 :             :   /* Emit GIMPLE_OMP_FOR.  */
    2870                 :         585 :   if (oacc_kernels_p)
    2871                 :             :     /* Parallelized OpenACC kernels constructs use gang parallelism.  See also
    2872                 :             :        omp-offload.cc:execute_oacc_loop_designation.  */
    2873                 :         382 :     t = build_omp_clause (loc, OMP_CLAUSE_GANG);
    2874                 :             :   else
    2875                 :             :     {
    2876                 :         203 :       t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
    2877                 :         203 :       int chunk_size = param_parloops_chunk_size;
    2878                 :         203 :       switch (param_parloops_schedule)
    2879                 :             :         {
    2880                 :         189 :         case PARLOOPS_SCHEDULE_STATIC:
    2881                 :         189 :           OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
    2882                 :         189 :           break;
    2883                 :           6 :         case PARLOOPS_SCHEDULE_DYNAMIC:
    2884                 :           6 :           OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_DYNAMIC;
    2885                 :           6 :           break;
    2886                 :           4 :         case PARLOOPS_SCHEDULE_GUIDED:
    2887                 :           4 :           OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_GUIDED;
    2888                 :           4 :           break;
    2889                 :           2 :         case PARLOOPS_SCHEDULE_AUTO:
    2890                 :           2 :           OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_AUTO;
    2891                 :           2 :           chunk_size = 0;
    2892                 :           2 :           break;
    2893                 :           2 :         case PARLOOPS_SCHEDULE_RUNTIME:
    2894                 :           2 :           OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_RUNTIME;
    2895                 :           2 :           chunk_size = 0;
    2896                 :           2 :           break;
    2897                 :           0 :         default:
    2898                 :           0 :           gcc_unreachable ();
    2899                 :             :         }
    2900                 :         203 :       if (chunk_size != 0)
    2901                 :          16 :         OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t)
    2902                 :          32 :           = build_int_cst (integer_type_node, chunk_size);
    2903                 :             :     }
    2904                 :             : 
    2905                 :         788 :   for_stmt = gimple_build_omp_for (NULL,
    2906                 :             :                                    (oacc_kernels_p
    2907                 :             :                                     ? GF_OMP_FOR_KIND_OACC_LOOP
    2908                 :             :                                     : GF_OMP_FOR_KIND_FOR),
    2909                 :             :                                    t, 1, NULL);
    2910                 :             : 
    2911                 :         585 :   gimple_cond_set_lhs (cond_stmt, cvar_base);
    2912                 :         585 :   type = TREE_TYPE (cvar);
    2913                 :         585 :   gimple_set_location (for_stmt, loc);
    2914                 :         585 :   gimple_omp_for_set_index (for_stmt, 0, initvar);
    2915                 :         585 :   gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
    2916                 :         585 :   gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
    2917                 :         585 :   gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
    2918                 :         585 :   gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
    2919                 :             :                                                 cvar_base,
    2920                 :         585 :                                                 build_int_cst (type, 1)));
    2921                 :             : 
    2922                 :         585 :   gsi = gsi_last_bb (for_bb);
    2923                 :         585 :   gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
    2924                 :         585 :   SSA_NAME_DEF_STMT (initvar) = for_stmt;
    2925                 :             : 
    2926                 :             :   /* Emit GIMPLE_OMP_CONTINUE.  */
    2927                 :         585 :   continue_bb = single_pred (loop->latch);
    2928                 :         585 :   gsi = gsi_last_bb (continue_bb);
    2929                 :         585 :   omp_cont_stmt = gimple_build_omp_continue (cvar_next, cvar);
    2930                 :         585 :   gimple_set_location (omp_cont_stmt, loc);
    2931                 :         585 :   gsi_insert_after (&gsi, omp_cont_stmt, GSI_NEW_STMT);
    2932                 :         585 :   SSA_NAME_DEF_STMT (cvar_next) = omp_cont_stmt;
    2933                 :             : 
    2934                 :             :   /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR.  */
    2935                 :         585 :   gsi = gsi_last_bb (ex_bb);
    2936                 :         585 :   omp_return_stmt2 = gimple_build_omp_return (true);
    2937                 :         585 :   gimple_set_location (omp_return_stmt2, loc);
    2938                 :         585 :   gsi_insert_after (&gsi, omp_return_stmt2, GSI_NEW_STMT);
    2939                 :             : 
    2940                 :             :   /* After the above dom info is hosed.  Re-compute it.  */
    2941                 :         585 :   free_dominance_info (CDI_DOMINATORS);
    2942                 :         585 :   calculate_dominance_info (CDI_DOMINATORS);
    2943                 :         585 : }
    2944                 :             : 
    2945                 :             : /* Return number of phis in bb.  If COUNT_VIRTUAL_P is false, don't count the
    2946                 :             :    virtual phi.  */
    2947                 :             : 
    2948                 :             : static unsigned int
    2949                 :         586 : num_phis (basic_block bb, bool count_virtual_p)
    2950                 :             : {
    2951                 :         586 :   unsigned int nr_phis = 0;
    2952                 :         586 :   gphi_iterator gsi;
    2953                 :        1746 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2954                 :             :     {
    2955                 :        3480 :       if (!count_virtual_p && virtual_operand_p (PHI_RESULT (gsi.phi ())))
    2956                 :         494 :         continue;
    2957                 :             : 
    2958                 :         666 :       nr_phis++;
    2959                 :             :     }
    2960                 :             : 
    2961                 :         586 :   return nr_phis;
    2962                 :             : }
    2963                 :             : 
    2964                 :             : /* Generates code to execute the iterations of LOOP in N_THREADS
    2965                 :             :    threads in parallel, which can be 0 if that number is to be determined
    2966                 :             :    later.
    2967                 :             : 
    2968                 :             :    NITER describes number of iterations of LOOP.
    2969                 :             :    REDUCTION_LIST describes the reductions existent in the LOOP.  */
    2970                 :             : 
    2971                 :             : static void
    2972                 :         586 : gen_parallel_loop (class loop *loop,
    2973                 :             :                    reduction_info_table_type *reduction_list,
    2974                 :             :                    unsigned n_threads, class tree_niter_desc *niter,
    2975                 :             :                    bool oacc_kernels_p)
    2976                 :             : {
    2977                 :         586 :   tree many_iterations_cond, type, nit;
    2978                 :         586 :   tree arg_struct, new_arg_struct;
    2979                 :         586 :   gimple_seq stmts;
    2980                 :         586 :   edge entry, exit;
    2981                 :         586 :   struct clsn_data clsn_data;
    2982                 :         586 :   location_t loc;
    2983                 :         586 :   gimple *cond_stmt;
    2984                 :         586 :   unsigned int m_p_thread=2;
    2985                 :             : 
    2986                 :             :   /* From
    2987                 :             : 
    2988                 :             :      ---------------------------------------------------------------------
    2989                 :             :      loop
    2990                 :             :        {
    2991                 :             :          IV = phi (INIT, IV + STEP)
    2992                 :             :          BODY1;
    2993                 :             :          if (COND)
    2994                 :             :            break;
    2995                 :             :          BODY2;
    2996                 :             :        }
    2997                 :             :      ---------------------------------------------------------------------
    2998                 :             : 
    2999                 :             :      with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
    3000                 :             :      we generate the following code:
    3001                 :             : 
    3002                 :             :      ---------------------------------------------------------------------
    3003                 :             : 
    3004                 :             :      if (MAY_BE_ZERO
    3005                 :             :      || NITER < MIN_PER_THREAD * N_THREADS)
    3006                 :             :      goto original;
    3007                 :             : 
    3008                 :             :      BODY1;
    3009                 :             :      store all local loop-invariant variables used in body of the loop to DATA.
    3010                 :             :      GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
    3011                 :             :      load the variables from DATA.
    3012                 :             :      GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
    3013                 :             :      BODY2;
    3014                 :             :      BODY1;
    3015                 :             :      GIMPLE_OMP_CONTINUE;
    3016                 :             :      GIMPLE_OMP_RETURN         -- GIMPLE_OMP_FOR
    3017                 :             :      GIMPLE_OMP_RETURN         -- GIMPLE_OMP_PARALLEL
    3018                 :             :      goto end;
    3019                 :             : 
    3020                 :             :      original:
    3021                 :             :      loop
    3022                 :             :        {
    3023                 :             :          IV = phi (INIT, IV + STEP)
    3024                 :             :          BODY1;
    3025                 :             :          if (COND)
    3026                 :             :            break;
    3027                 :             :          BODY2;
    3028                 :             :        }
    3029                 :             : 
    3030                 :             :      end:
    3031                 :             : 
    3032                 :             :    */
    3033                 :             : 
    3034                 :             :   /* Create two versions of the loop -- in the old one, we know that the
    3035                 :             :      number of iterations is large enough, and we will transform it into the
    3036                 :             :      loop that will be split to loop_fn, the new one will be used for the
    3037                 :             :      remaining iterations.  */
    3038                 :             : 
    3039                 :             :   /* We should compute a better number-of-iterations value for outer loops.
    3040                 :             :      That is, if we have
    3041                 :             :  
    3042                 :             :     for (i = 0; i < n; ++i)
    3043                 :             :       for (j = 0; j < m; ++j)
    3044                 :             :         ...
    3045                 :             : 
    3046                 :             :     we should compute nit = n * m, not nit = n.  
    3047                 :             :     Also may_be_zero handling would need to be adjusted.  */
    3048                 :             : 
    3049                 :         586 :   type = TREE_TYPE (niter->niter);
    3050                 :         586 :   nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
    3051                 :             :                               NULL_TREE);
    3052                 :         586 :   if (stmts)
    3053                 :         150 :     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    3054                 :             : 
    3055                 :         586 :   if (!oacc_kernels_p)
    3056                 :             :     {
    3057                 :         204 :       if (loop->inner)
    3058                 :             :         m_p_thread=2;
    3059                 :             :       else
    3060                 :         183 :         m_p_thread=MIN_PER_THREAD;
    3061                 :             : 
    3062                 :         204 :       gcc_checking_assert (n_threads != 0);
    3063                 :         204 :       many_iterations_cond =
    3064                 :         204 :         fold_build2 (GE_EXPR, boolean_type_node,
    3065                 :             :                      nit, build_int_cst (type, m_p_thread * n_threads - 1));
    3066                 :             : 
    3067                 :         204 :       many_iterations_cond
    3068                 :         204 :         = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
    3069                 :             :                        invert_truthvalue (unshare_expr (niter->may_be_zero)),
    3070                 :             :                        many_iterations_cond);
    3071                 :         204 :       many_iterations_cond
    3072                 :         204 :         = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
    3073                 :         204 :       if (stmts)
    3074                 :           7 :         gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    3075                 :         204 :       if (!is_gimple_condexpr_for_cond (many_iterations_cond))
    3076                 :             :         {
    3077                 :           7 :           many_iterations_cond
    3078                 :           7 :             = force_gimple_operand (many_iterations_cond, &stmts,
    3079                 :             :                                     true, NULL_TREE);
    3080                 :           7 :           if (stmts)
    3081                 :           7 :             gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop),
    3082                 :             :                                               stmts);
    3083                 :             :         }
    3084                 :             : 
    3085                 :         204 :       initialize_original_copy_tables ();
    3086                 :             : 
    3087                 :             :       /* We assume that the loop usually iterates a lot.  */
    3088                 :         204 :       loop_version (loop, many_iterations_cond, NULL,
    3089                 :             :                     profile_probability::likely (),
    3090                 :             :                     profile_probability::unlikely (),
    3091                 :             :                     profile_probability::likely (),
    3092                 :             :                     profile_probability::unlikely (), true);
    3093                 :         204 :       update_ssa (TODO_update_ssa_no_phi);
    3094                 :         204 :       free_original_copy_tables ();
    3095                 :             :     }
    3096                 :             : 
    3097                 :             :   /* Base all the induction variables in LOOP on a single control one.  */
    3098                 :         586 :   canonicalize_loop_ivs (loop, &nit, true);
    3099                 :         586 :   if (num_phis (loop->header, false) != reduction_list->elements () + 1)
    3100                 :             :     {
    3101                 :             :       /* The call to canonicalize_loop_ivs above failed to "base all the
    3102                 :             :          induction variables in LOOP on a single control one".  Do damage
    3103                 :             :          control.  */
    3104                 :           1 :       basic_block preheader = loop_preheader_edge (loop)->src;
    3105                 :           1 :       basic_block cond_bb = single_pred (preheader);
    3106                 :           2 :       gcond *cond = as_a <gcond *> (gsi_stmt (gsi_last_bb (cond_bb)));
    3107                 :           1 :       gimple_cond_make_true (cond);
    3108                 :           1 :       update_stmt (cond);
    3109                 :             :       /* We've gotten rid of the duplicate loop created by loop_version, but
    3110                 :             :          we can't undo whatever canonicalize_loop_ivs has done.
    3111                 :             :          TODO: Fix this properly by ensuring that the call to
    3112                 :             :          canonicalize_loop_ivs succeeds.  */
    3113                 :           1 :       if (dump_file
    3114                 :           1 :           && (dump_flags & TDF_DETAILS))
    3115                 :           0 :         fprintf (dump_file, "canonicalize_loop_ivs failed for loop %d,"
    3116                 :             :                  " aborting transformation\n", loop->num);
    3117                 :           1 :       return;
    3118                 :             :     }
    3119                 :             : 
    3120                 :             :   /* Ensure that the exit condition is the first statement in the loop.
    3121                 :             :      The common case is that latch of the loop is empty (apart from the
    3122                 :             :      increment) and immediately follows the loop exit test.  Attempt to move the
    3123                 :             :      entry of the loop directly before the exit check and increase the number of
    3124                 :             :      iterations of the loop by one.  */
    3125                 :         585 :   if (try_transform_to_exit_first_loop_alt (loop, reduction_list, nit))
    3126                 :             :     {
    3127                 :         561 :       if (dump_file
    3128                 :         561 :           && (dump_flags & TDF_DETAILS))
    3129                 :         218 :         fprintf (dump_file,
    3130                 :             :                  "alternative exit-first loop transform succeeded"
    3131                 :             :                  " for loop %d\n", loop->num);
    3132                 :             :     }
    3133                 :             :   else
    3134                 :             :     {
    3135                 :          24 :       if (oacc_kernels_p)
    3136                 :           0 :         n_threads = 1;
    3137                 :             : 
    3138                 :             :       /* Fall back on the method that handles more cases, but duplicates the
    3139                 :             :          loop body: move the exit condition of LOOP to the beginning of its
    3140                 :             :          header, and duplicate the part of the last iteration that gets disabled
    3141                 :             :          to the exit of the loop.  */
    3142                 :          24 :       transform_to_exit_first_loop (loop, reduction_list, nit);
    3143                 :             :     }
    3144                 :         585 :   update_ssa (TODO_update_ssa_no_phi);
    3145                 :             : 
    3146                 :             :   /* Generate initializations for reductions.  */
    3147                 :         585 :   if (!reduction_list->is_empty ())
    3148                 :          71 :     reduction_list->traverse <class loop *, initialize_reductions> (loop);
    3149                 :             : 
    3150                 :             :   /* Eliminate the references to local variables from the loop.  */
    3151                 :         585 :   gcc_assert (single_exit (loop));
    3152                 :         585 :   entry = loop_preheader_edge (loop);
    3153                 :         585 :   exit = single_dom_exit (loop);
    3154                 :             : 
    3155                 :             :   /* This rewrites the body in terms of new variables.  This has already
    3156                 :             :      been done for oacc_kernels_p in pass_lower_omp/lower_omp ().  */
    3157                 :         585 :   if (!oacc_kernels_p)
    3158                 :             :     {
    3159                 :         203 :       eliminate_local_variables (entry, exit);
    3160                 :             :       /* In the old loop, move all variables non-local to the loop to a
    3161                 :             :          structure and back, and create separate decls for the variables used in
    3162                 :             :          loop.  */
    3163                 :         203 :       separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
    3164                 :             :                                 &new_arg_struct, &clsn_data);
    3165                 :             :     }
    3166                 :             :   else
    3167                 :             :     {
    3168                 :         382 :       arg_struct = NULL_TREE;
    3169                 :         382 :       new_arg_struct = NULL_TREE;
    3170                 :         382 :       clsn_data.load = NULL_TREE;
    3171                 :         382 :       clsn_data.load_bb = exit->dest;
    3172                 :         382 :       clsn_data.store = NULL_TREE;
    3173                 :         382 :       clsn_data.store_bb = NULL;
    3174                 :             :     }
    3175                 :             : 
    3176                 :             :   /* Create the parallel constructs.  */
    3177                 :         585 :   loc = UNKNOWN_LOCATION;
    3178                 :         585 :   cond_stmt = last_nondebug_stmt (loop->header);
    3179                 :         585 :   if (cond_stmt)
    3180                 :         585 :     loc = gimple_location (cond_stmt);
    3181                 :         585 :   create_parallel_loop (loop, create_loop_fn (loc), arg_struct, new_arg_struct,
    3182                 :             :                         n_threads, loc, oacc_kernels_p);
    3183                 :         585 :   if (!reduction_list->is_empty ())
    3184                 :          71 :     create_call_for_reduction (loop, reduction_list, &clsn_data);
    3185                 :             : 
    3186                 :         585 :   scev_reset ();
    3187                 :             : 
    3188                 :             :   /* Free loop bound estimations that could contain references to
    3189                 :             :      removed statements.  */
    3190                 :         585 :   free_numbers_of_iterations_estimates (cfun);
    3191                 :             : }
    3192                 :             : 
    3193                 :             : /* Returns true when LOOP contains vector phi nodes.  */
    3194                 :             : 
    3195                 :             : static bool
    3196                 :        1914 : loop_has_vector_phi_nodes (class loop *loop ATTRIBUTE_UNUSED)
    3197                 :             : {
    3198                 :        1914 :   unsigned i;
    3199                 :        1914 :   basic_block *bbs = get_loop_body_in_dom_order (loop);
    3200                 :        1914 :   gphi_iterator gsi;
    3201                 :        1914 :   bool res = true;
    3202                 :             : 
    3203                 :       12807 :   for (i = 0; i < loop->num_nodes; i++)
    3204                 :       17282 :     for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
    3205                 :        8303 :       if (VECTOR_TYPE_P (TREE_TYPE (PHI_RESULT (gsi.phi ()))))
    3206                 :           0 :         goto end;
    3207                 :             : 
    3208                 :             :   res = false;
    3209                 :        1914 :  end:
    3210                 :        1914 :   free (bbs);
    3211                 :        1914 :   return res;
    3212                 :             : }
    3213                 :             : 
    3214                 :             : /* Create a reduction_info struct, initialize it with REDUC_STMT
    3215                 :             :    and PHI, insert it to the REDUCTION_LIST.  */
    3216                 :             : 
    3217                 :             : static void
    3218                 :          87 : build_new_reduction (reduction_info_table_type *reduction_list,
    3219                 :             :                      gimple *reduc_stmt, gphi *phi)
    3220                 :             : {
    3221                 :          87 :   reduction_info **slot;
    3222                 :          87 :   struct reduction_info *new_reduction;
    3223                 :          87 :   enum tree_code reduction_code;
    3224                 :             : 
    3225                 :          87 :   gcc_assert (reduc_stmt);
    3226                 :             : 
    3227                 :          87 :   if (gimple_code (reduc_stmt) == GIMPLE_PHI)
    3228                 :             :     {
    3229                 :          14 :       tree op1 = PHI_ARG_DEF (reduc_stmt, 0);
    3230                 :          14 :       gimple *def1 = SSA_NAME_DEF_STMT (op1);
    3231                 :          14 :       reduction_code = gimple_assign_rhs_code (def1);
    3232                 :             :     }
    3233                 :             :   else
    3234                 :          73 :     reduction_code = gimple_assign_rhs_code (reduc_stmt);
    3235                 :             :   /* Check for OpenMP supported reduction.  */
    3236                 :          87 :   switch (reduction_code)
    3237                 :             :     {
    3238                 :          20 :     case MINUS_EXPR:
    3239                 :          20 :       reduction_code = PLUS_EXPR;
    3240                 :             :       /* Fallthru.  */
    3241                 :          87 :     case PLUS_EXPR:
    3242                 :          87 :     case MULT_EXPR:
    3243                 :          87 :     case MAX_EXPR:
    3244                 :          87 :     case MIN_EXPR:
    3245                 :          87 :     case BIT_IOR_EXPR:
    3246                 :          87 :     case BIT_XOR_EXPR:
    3247                 :          87 :     case BIT_AND_EXPR:
    3248                 :          87 :     case TRUTH_OR_EXPR:
    3249                 :          87 :     case TRUTH_XOR_EXPR:
    3250                 :          87 :     case TRUTH_AND_EXPR:
    3251                 :          87 :       break;
    3252                 :           0 :     default:
    3253                 :           0 :       return;
    3254                 :             :     }
    3255                 :             : 
    3256                 :          87 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3257                 :             :     {
    3258                 :          43 :       fprintf (dump_file,
    3259                 :             :                "Detected reduction. reduction stmt is:\n");
    3260                 :          43 :       print_gimple_stmt (dump_file, reduc_stmt, 0);
    3261                 :          43 :       fprintf (dump_file, "\n");
    3262                 :             :     }
    3263                 :             : 
    3264                 :          87 :   new_reduction = XCNEW (struct reduction_info);
    3265                 :             : 
    3266                 :          87 :   new_reduction->reduc_stmt = reduc_stmt;
    3267                 :          87 :   new_reduction->reduc_phi = phi;
    3268                 :          87 :   new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
    3269                 :          87 :   new_reduction->reduction_code = reduction_code;
    3270                 :          87 :   slot = reduction_list->find_slot (new_reduction, INSERT);
    3271                 :          87 :   *slot = new_reduction;
    3272                 :             : }
    3273                 :             : 
    3274                 :             : /* Callback for htab_traverse.  Sets gimple_uid of reduc_phi stmts.  */
    3275                 :             : 
    3276                 :             : int
    3277                 :          87 : set_reduc_phi_uids (reduction_info **slot, void *data ATTRIBUTE_UNUSED)
    3278                 :             : {
    3279                 :          87 :   struct reduction_info *const red = *slot;
    3280                 :          87 :   gimple_set_uid (red->reduc_phi, red->reduc_version);
    3281                 :          87 :   return 1;
    3282                 :             : }
    3283                 :             : 
    3284                 :             : /* Return true if the type of reduction performed by STMT_INFO is suitable
    3285                 :             :    for this pass.  */
    3286                 :             : 
    3287                 :             : static bool
    3288                 :         121 : valid_reduction_p (stmt_vec_info stmt_info)
    3289                 :             : {
    3290                 :             :   /* Parallelization would reassociate the operation, which isn't
    3291                 :             :      allowed for in-order reductions.  */
    3292                 :         121 :   vect_reduction_type reduc_type = STMT_VINFO_REDUC_TYPE (stmt_info);
    3293                 :         121 :   return reduc_type != FOLD_LEFT_REDUCTION;
    3294                 :             : }
    3295                 :             : 
    3296                 :             : /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST.  */
    3297                 :             : 
    3298                 :             : static void
    3299                 :        1211 : gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
    3300                 :             : {
    3301                 :        1211 :   gphi_iterator gsi;
    3302                 :        1211 :   loop_vec_info simple_loop_info;
    3303                 :        1211 :   auto_vec<gphi *, 4> double_reduc_phis;
    3304                 :        1211 :   auto_vec<gimple *, 4> double_reduc_stmts;
    3305                 :             : 
    3306                 :        1211 :   vec_info_shared shared;
    3307                 :        1211 :   vect_loop_form_info info;
    3308                 :        1211 :   if (!vect_analyze_loop_form (loop, &info))
    3309                 :         505 :     goto gather_done;
    3310                 :             : 
    3311                 :         706 :   simple_loop_info = vect_create_loop_vinfo (loop, &shared, &info);
    3312                 :        2390 :   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
    3313                 :             :     {
    3314                 :        1684 :       gphi *phi = gsi.phi ();
    3315                 :        1684 :       affine_iv iv;
    3316                 :        1684 :       tree res = PHI_RESULT (phi);
    3317                 :        1684 :       bool double_reduc;
    3318                 :             : 
    3319                 :        3368 :       if (virtual_operand_p (res))
    3320                 :        1611 :         continue;
    3321                 :             : 
    3322                 :        1089 :       if (simple_iv (loop, loop, res, &iv, true))
    3323                 :         969 :         continue;
    3324                 :             : 
    3325                 :         120 :       stmt_vec_info reduc_stmt_info
    3326                 :         120 :         = parloops_force_simple_reduction (simple_loop_info,
    3327                 :             :                                            simple_loop_info->lookup_stmt (phi),
    3328                 :             :                                            &double_reduc, true);
    3329                 :         120 :       if (!reduc_stmt_info || !valid_reduction_p (reduc_stmt_info))
    3330                 :          32 :         continue;
    3331                 :             : 
    3332                 :          88 :       if (double_reduc)
    3333                 :             :         {
    3334                 :          15 :           if (loop->inner->inner != NULL)
    3335                 :           0 :             continue;
    3336                 :             : 
    3337                 :          15 :           double_reduc_phis.safe_push (phi);
    3338                 :          15 :           double_reduc_stmts.safe_push (reduc_stmt_info->stmt);
    3339                 :          15 :           continue;
    3340                 :             :         }
    3341                 :             : 
    3342                 :          73 :       build_new_reduction (reduction_list, reduc_stmt_info->stmt, phi);
    3343                 :             :     }
    3344                 :         706 :   delete simple_loop_info;
    3345                 :             : 
    3346                 :         706 :   if (!double_reduc_phis.is_empty ())
    3347                 :             :     {
    3348                 :          15 :       vec_info_shared shared;
    3349                 :          15 :       vect_loop_form_info info;
    3350                 :          15 :       if (vect_analyze_loop_form (loop->inner, &info))
    3351                 :             :         {
    3352                 :          15 :           simple_loop_info
    3353                 :          15 :             = vect_create_loop_vinfo (loop->inner, &shared, &info);
    3354                 :          15 :           gphi *phi;
    3355                 :          15 :           unsigned int i;
    3356                 :             : 
    3357                 :          30 :           FOR_EACH_VEC_ELT (double_reduc_phis, i, phi)
    3358                 :             :             {
    3359                 :          15 :               affine_iv iv;
    3360                 :          15 :               tree res = PHI_RESULT (phi);
    3361                 :          15 :               bool double_reduc;
    3362                 :             : 
    3363                 :          15 :               use_operand_p use_p;
    3364                 :          15 :               gimple *inner_stmt;
    3365                 :          15 :               bool single_use_p = single_imm_use (res, &use_p, &inner_stmt);
    3366                 :          15 :               gcc_assert (single_use_p);
    3367                 :          15 :               if (gimple_code (inner_stmt) != GIMPLE_PHI)
    3368                 :           1 :                 continue;
    3369                 :          15 :               gphi *inner_phi = as_a <gphi *> (inner_stmt);
    3370                 :          15 :               if (simple_iv (loop->inner, loop->inner, PHI_RESULT (inner_phi),
    3371                 :             :                              &iv, true))
    3372                 :           0 :                 continue;
    3373                 :             : 
    3374                 :          15 :               stmt_vec_info inner_phi_info
    3375                 :          15 :                 = simple_loop_info->lookup_stmt (inner_phi);
    3376                 :          15 :               stmt_vec_info inner_reduc_stmt_info
    3377                 :          15 :                 = parloops_force_simple_reduction (simple_loop_info,
    3378                 :             :                                                    inner_phi_info,
    3379                 :             :                                                    &double_reduc, true);
    3380                 :          15 :               gcc_assert (!double_reduc);
    3381                 :          16 :               if (!inner_reduc_stmt_info
    3382                 :          15 :                   || !valid_reduction_p (inner_reduc_stmt_info))
    3383                 :           1 :                 continue;
    3384                 :             : 
    3385                 :          14 :               build_new_reduction (reduction_list, double_reduc_stmts[i], phi);
    3386                 :             :             }
    3387                 :          15 :           delete simple_loop_info;
    3388                 :             :         }
    3389                 :          15 :     }
    3390                 :             : 
    3391                 :        1211 :  gather_done:
    3392                 :        1211 :   if (reduction_list->is_empty ())
    3393                 :        1131 :     return;
    3394                 :             : 
    3395                 :             :   /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
    3396                 :             :      and delete simple_loop_info, we can set gimple_uid of reduc_phi stmts only
    3397                 :             :      now.  */
    3398                 :          80 :   basic_block bb;
    3399                 :        1123 :   FOR_EACH_BB_FN (bb, cfun)
    3400                 :        2039 :     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3401                 :         996 :       gimple_set_uid (gsi_stmt (gsi), (unsigned int)-1);
    3402                 :          80 :   reduction_list->traverse <void *, set_reduc_phi_uids> (NULL);
    3403                 :        1211 : }
    3404                 :             : 
    3405                 :             : /* Try to initialize NITER for code generation part.  */
    3406                 :             : 
    3407                 :             : static bool
    3408                 :        1785 : try_get_loop_niter (loop_p loop, class tree_niter_desc *niter)
    3409                 :             : {
    3410                 :        1785 :   edge exit = single_dom_exit (loop);
    3411                 :             : 
    3412                 :        1785 :   gcc_assert (exit);
    3413                 :             : 
    3414                 :             :   /* We need to know # of iterations, and there should be no uses of values
    3415                 :             :      defined inside loop outside of it, unless the values are invariants of
    3416                 :             :      the loop.  */
    3417                 :        1785 :   if (!number_of_iterations_exit (loop, exit, niter, false))
    3418                 :             :     {
    3419                 :         574 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3420                 :          10 :         fprintf (dump_file, "  FAILED: number of iterations not known\n");
    3421                 :         574 :       return false;
    3422                 :             :     }
    3423                 :             : 
    3424                 :             :   return true;
    3425                 :             : }
    3426                 :             : 
    3427                 :             : /* Return the default def of the first function argument.  */
    3428                 :             : 
    3429                 :             : static tree
    3430                 :         400 : get_omp_data_i_param (void)
    3431                 :             : {
    3432                 :         400 :   tree decl = DECL_ARGUMENTS (cfun->decl);
    3433                 :         400 :   gcc_assert (DECL_CHAIN (decl) == NULL_TREE);
    3434                 :         400 :   return ssa_default_def (cfun, decl);
    3435                 :             : }
    3436                 :             : 
    3437                 :             : /* For PHI in loop header of LOOP, look for pattern:
    3438                 :             : 
    3439                 :             :    <bb preheader>
    3440                 :             :    .omp_data_i = &.omp_data_arr;
    3441                 :             :    addr = .omp_data_i->sum;
    3442                 :             :    sum_a = *addr;
    3443                 :             : 
    3444                 :             :    <bb header>:
    3445                 :             :    sum_b = PHI <sum_a (preheader), sum_c (latch)>
    3446                 :             : 
    3447                 :             :    and return addr.  Otherwise, return NULL_TREE.  */
    3448                 :             : 
    3449                 :             : static tree
    3450                 :          14 : find_reduc_addr (class loop *loop, gphi *phi)
    3451                 :             : {
    3452                 :          14 :   edge e = loop_preheader_edge (loop);
    3453                 :          14 :   tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
    3454                 :          14 :   gimple *stmt = SSA_NAME_DEF_STMT (arg);
    3455                 :          14 :   if (!gimple_assign_single_p (stmt))
    3456                 :             :     return NULL_TREE;
    3457                 :          14 :   tree memref = gimple_assign_rhs1 (stmt);
    3458                 :          14 :   if (TREE_CODE (memref) != MEM_REF)
    3459                 :             :     return NULL_TREE;
    3460                 :          14 :   tree addr = TREE_OPERAND (memref, 0);
    3461                 :             : 
    3462                 :          14 :   gimple *stmt2 = SSA_NAME_DEF_STMT (addr);
    3463                 :          14 :   if (!gimple_assign_single_p (stmt2))
    3464                 :             :     return NULL_TREE;
    3465                 :          14 :   tree compref = gimple_assign_rhs1 (stmt2);
    3466                 :          14 :   if (TREE_CODE (compref) != COMPONENT_REF)
    3467                 :             :     return NULL_TREE;
    3468                 :          14 :   tree addr2 = TREE_OPERAND (compref, 0);
    3469                 :          14 :   if (TREE_CODE (addr2) != MEM_REF)
    3470                 :             :     return NULL_TREE;
    3471                 :          14 :   addr2 = TREE_OPERAND (addr2, 0);
    3472                 :          14 :   if (TREE_CODE (addr2) != SSA_NAME
    3473                 :          14 :       || addr2 != get_omp_data_i_param ())
    3474                 :           0 :     return NULL_TREE;
    3475                 :             : 
    3476                 :             :   return addr;
    3477                 :             : }
    3478                 :             : 
    3479                 :             : /* Try to initialize REDUCTION_LIST for code generation part.
    3480                 :             :    REDUCTION_LIST describes the reductions.  */
    3481                 :             : 
    3482                 :             : static bool
    3483                 :        1211 : try_create_reduction_list (loop_p loop,
    3484                 :             :                            reduction_info_table_type *reduction_list,
    3485                 :             :                            bool oacc_kernels_p)
    3486                 :             : {
    3487                 :        1211 :   edge exit = single_dom_exit (loop);
    3488                 :        1211 :   gphi_iterator gsi;
    3489                 :             : 
    3490                 :        1211 :   gcc_assert (exit);
    3491                 :             : 
    3492                 :             :   /* Try to get rid of exit phis.  */
    3493                 :        1211 :   final_value_replacement_loop (loop);
    3494                 :             : 
    3495                 :        1211 :   gather_scalar_reductions (loop, reduction_list);
    3496                 :             : 
    3497                 :             : 
    3498                 :        2305 :   for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
    3499                 :             :     {
    3500                 :        1162 :       gphi *phi = gsi.phi ();
    3501                 :        1162 :       struct reduction_info *red;
    3502                 :        1162 :       imm_use_iterator imm_iter;
    3503                 :        1162 :       use_operand_p use_p;
    3504                 :        1162 :       gimple *reduc_phi;
    3505                 :        1162 :       tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    3506                 :             : 
    3507                 :        2324 :       if (!virtual_operand_p (val))
    3508                 :             :         {
    3509                 :         154 :           if (TREE_CODE (val) != SSA_NAME)
    3510                 :             :             {
    3511                 :           0 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3512                 :           0 :                 fprintf (dump_file,
    3513                 :             :                          "  FAILED: exit PHI argument invariant.\n");
    3514                 :          68 :               return false;
    3515                 :             :             }
    3516                 :             : 
    3517                 :         154 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3518                 :             :             {
    3519                 :          56 :               fprintf (dump_file, "phi is ");
    3520                 :          56 :               print_gimple_stmt (dump_file, phi, 0);
    3521                 :          56 :               fprintf (dump_file, "arg of phi to exit:   value ");
    3522                 :          56 :               print_generic_expr (dump_file, val);
    3523                 :          56 :               fprintf (dump_file, " used outside loop\n");
    3524                 :          56 :               fprintf (dump_file,
    3525                 :             :                        "  checking if it is part of reduction pattern:\n");
    3526                 :             :             }
    3527                 :         154 :           if (reduction_list->is_empty ())
    3528                 :             :             {
    3529                 :          66 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3530                 :          13 :                 fprintf (dump_file,
    3531                 :             :                          "  FAILED: it is not a part of reduction.\n");
    3532                 :          66 :               return false;
    3533                 :             :             }
    3534                 :          88 :           reduc_phi = NULL;
    3535                 :         159 :           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
    3536                 :             :             {
    3537                 :         159 :               if (!gimple_debug_bind_p (USE_STMT (use_p))
    3538                 :         159 :                   && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
    3539                 :             :                 {
    3540                 :          88 :                   reduc_phi = USE_STMT (use_p);
    3541                 :          88 :                   break;
    3542                 :             :                 }
    3543                 :             :             }
    3544                 :          88 :           red = reduction_phi (reduction_list, reduc_phi);
    3545                 :          88 :           if (red == NULL)
    3546                 :             :             {
    3547                 :           2 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3548                 :           0 :                 fprintf (dump_file,
    3549                 :             :                          "  FAILED: it is not a part of reduction.\n");
    3550                 :           2 :               return false;
    3551                 :             :             }
    3552                 :          86 :           if (red->keep_res != NULL)
    3553                 :             :             {
    3554                 :           0 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3555                 :           0 :                 fprintf (dump_file,
    3556                 :             :                          "  FAILED: reduction has multiple exit phis.\n");
    3557                 :           0 :               return false;
    3558                 :             :             }
    3559                 :          86 :           red->keep_res = phi;
    3560                 :          86 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3561                 :             :             {
    3562                 :          43 :               fprintf (dump_file, "reduction phi is  ");
    3563                 :          43 :               print_gimple_stmt (dump_file, red->reduc_phi, 0);
    3564                 :          43 :               fprintf (dump_file, "reduction stmt is  ");
    3565                 :          43 :               print_gimple_stmt (dump_file, red->reduc_stmt, 0);
    3566                 :             :             }
    3567                 :             :         }
    3568                 :             :     }
    3569                 :             : 
    3570                 :             :   /* The iterations of the loop may communicate only through bivs whose
    3571                 :             :      iteration space can be distributed efficiently.  */
    3572                 :        3563 :   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
    3573                 :             :     {
    3574                 :        2431 :       gphi *phi = gsi.phi ();
    3575                 :        2431 :       tree def = PHI_RESULT (phi);
    3576                 :        2431 :       affine_iv iv;
    3577                 :             : 
    3578                 :        4862 :       if (!virtual_operand_p (def) && !simple_iv (loop, loop, def, &iv, true))
    3579                 :             :         {
    3580                 :          90 :           struct reduction_info *red;
    3581                 :             : 
    3582                 :          90 :           red = reduction_phi (reduction_list, phi);
    3583                 :          90 :           if (red == NULL)
    3584                 :             :             {
    3585                 :          11 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3586                 :           0 :                 fprintf (dump_file,
    3587                 :             :                          "  FAILED: scalar dependency between iterations\n");
    3588                 :          11 :               return false;
    3589                 :             :             }
    3590                 :             :         }
    3591                 :             :     }
    3592                 :             : 
    3593                 :        1132 :   if (oacc_kernels_p)
    3594                 :             :     {
    3595                 :        2468 :       for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi);
    3596                 :        1663 :            gsi_next (&gsi))
    3597                 :             :         {
    3598                 :        1663 :           gphi *phi = gsi.phi ();
    3599                 :        1663 :           tree def = PHI_RESULT (phi);
    3600                 :        1663 :           affine_iv iv;
    3601                 :             : 
    3602                 :        1663 :           if (!virtual_operand_p (def)
    3603                 :        1663 :               && !simple_iv (loop, loop, def, &iv, true))
    3604                 :             :             {
    3605                 :          14 :               tree addr = find_reduc_addr (loop, phi);
    3606                 :          14 :               if (addr == NULL_TREE)
    3607                 :           0 :                 return false;
    3608                 :          14 :               struct reduction_info *red = reduction_phi (reduction_list, phi);
    3609                 :          14 :               red->reduc_addr = addr;
    3610                 :             :             }
    3611                 :             :         }
    3612                 :             :     }
    3613                 :             : 
    3614                 :             :   return true;
    3615                 :             : }
    3616                 :             : 
    3617                 :             : /* Return true if LOOP contains phis with ADDR_EXPR in args.  */
    3618                 :             : 
    3619                 :             : static bool
    3620                 :        1132 : loop_has_phi_with_address_arg (class loop *loop)
    3621                 :             : {
    3622                 :        1132 :   basic_block *bbs = get_loop_body (loop);
    3623                 :        1132 :   bool res = false;
    3624                 :             : 
    3625                 :        1132 :   unsigned i, j;
    3626                 :        1132 :   gphi_iterator gsi;
    3627                 :        6174 :   for (i = 0; i < loop->num_nodes; i++)
    3628                 :        9367 :     for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
    3629                 :             :       {
    3630                 :        4325 :         gphi *phi = gsi.phi ();
    3631                 :       12763 :         for (j = 0; j < gimple_phi_num_args (phi); j++)
    3632                 :             :           {
    3633                 :        8438 :             tree arg = gimple_phi_arg_def (phi, j);
    3634                 :        8438 :             if (TREE_CODE (arg) == ADDR_EXPR)
    3635                 :             :               {
    3636                 :             :                 /* This should be handled by eliminate_local_variables, but that
    3637                 :             :                    function currently ignores phis.  */
    3638                 :           0 :                 res = true;
    3639                 :           0 :                 goto end;
    3640                 :             :               }
    3641                 :             :           }
    3642                 :             :       }
    3643                 :        1132 :  end:
    3644                 :        1132 :   free (bbs);
    3645                 :             : 
    3646                 :        1132 :   return res;
    3647                 :             : }
    3648                 :             : 
    3649                 :             : /* Return true if memory ref REF (corresponding to the stmt at GSI in
    3650                 :             :    REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
    3651                 :             :    or the statements in REGIONS_BB[I + n].  REF_IS_STORE indicates if REF is a
    3652                 :             :    store.  Ignore conflicts with SKIP_STMT.  */
    3653                 :             : 
    3654                 :             : static bool
    3655                 :         558 : ref_conflicts_with_region (gimple_stmt_iterator gsi, ao_ref *ref,
    3656                 :             :                            bool ref_is_store, vec<basic_block> region_bbs,
    3657                 :             :                            unsigned int i, gimple *skip_stmt)
    3658                 :             : {
    3659                 :         558 :   basic_block bb = region_bbs[i];
    3660                 :         558 :   gsi_next (&gsi);
    3661                 :             : 
    3662                 :        1526 :   while (true)
    3663                 :             :     {
    3664                 :        7225 :       for (; !gsi_end_p (gsi);
    3665                 :        5141 :            gsi_next (&gsi))
    3666                 :             :         {
    3667                 :        5145 :           gimple *stmt = gsi_stmt (gsi);
    3668                 :        5145 :           if (stmt == skip_stmt)
    3669                 :             :             {
    3670                 :          14 :               if (dump_file)
    3671                 :             :                 {
    3672                 :          12 :                   fprintf (dump_file, "skipping reduction store: ");
    3673                 :          12 :                   print_gimple_stmt (dump_file, stmt, 0);
    3674                 :             :                 }
    3675                 :          14 :               continue;
    3676                 :             :             }
    3677                 :             : 
    3678                 :        8928 :           if (!gimple_vdef (stmt)
    3679                 :        8374 :               && !gimple_vuse (stmt))
    3680                 :        2729 :             continue;
    3681                 :             : 
    3682                 :        2402 :           if (gimple_code (stmt) == GIMPLE_RETURN)
    3683                 :         538 :             continue;
    3684                 :             : 
    3685                 :        1864 :           if (ref_is_store)
    3686                 :             :             {
    3687                 :         768 :               if (ref_maybe_used_by_stmt_p (stmt, ref))
    3688                 :             :                 {
    3689                 :           0 :                   if (dump_file)
    3690                 :             :                     {
    3691                 :           0 :                       fprintf (dump_file, "Stmt ");
    3692                 :           0 :                       print_gimple_stmt (dump_file, stmt, 0);
    3693                 :             :                     }
    3694                 :           0 :                   return true;
    3695                 :             :                 }
    3696                 :             :             }
    3697                 :             :           else
    3698                 :             :             {
    3699                 :        1096 :               if (stmt_may_clobber_ref_p_1 (stmt, ref))
    3700                 :             :                 {
    3701                 :           4 :                   if (dump_file)
    3702                 :             :                     {
    3703                 :           1 :                       fprintf (dump_file, "Stmt ");
    3704                 :           1 :                       print_gimple_stmt (dump_file, stmt, 0);
    3705                 :             :                     }
    3706                 :           4 :                   return true;
    3707                 :             :                 }
    3708                 :             :             }
    3709                 :             :         }
    3710                 :        2080 :       i++;
    3711                 :        2080 :       if (i == region_bbs.length ())
    3712                 :             :         break;
    3713                 :        1526 :       bb = region_bbs[i];
    3714                 :        1526 :       gsi = gsi_start_bb (bb);
    3715                 :        1526 :     }
    3716                 :             : 
    3717                 :             :   return false;
    3718                 :             : }
    3719                 :             : 
    3720                 :             : /* Return true if the bbs in REGION_BBS but not in in_loop_bbs can be executed
    3721                 :             :    in parallel with REGION_BBS containing the loop.  Return the stores of
    3722                 :             :    reduction results in REDUCTION_STORES.  */
    3723                 :             : 
    3724                 :             : static bool
    3725                 :         386 : oacc_entry_exit_ok_1 (bitmap in_loop_bbs, const vec<basic_block> &region_bbs,
    3726                 :             :                       reduction_info_table_type *reduction_list,
    3727                 :             :                       bitmap reduction_stores)
    3728                 :             : {
    3729                 :         386 :   tree omp_data_i = get_omp_data_i_param ();
    3730                 :             : 
    3731                 :         386 :   unsigned i;
    3732                 :         386 :   basic_block bb;
    3733                 :        2610 :   FOR_EACH_VEC_ELT (region_bbs, i, bb)
    3734                 :             :     {
    3735                 :        2228 :       if (bitmap_bit_p (in_loop_bbs, bb->index))
    3736                 :         962 :         continue;
    3737                 :             : 
    3738                 :        1266 :       gimple_stmt_iterator gsi;
    3739                 :        4690 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    3740                 :        2158 :            gsi_next (&gsi))
    3741                 :             :         {
    3742                 :        2162 :           gimple *stmt = gsi_stmt (gsi);
    3743                 :        2162 :           gimple *skip_stmt = NULL;
    3744                 :             : 
    3745                 :        2162 :           if (is_gimple_debug (stmt)
    3746                 :        2162 :               || gimple_code (stmt) == GIMPLE_COND)
    3747                 :        1604 :             continue;
    3748                 :             : 
    3749                 :        2070 :           ao_ref ref;
    3750                 :        2070 :           bool ref_is_store = false;
    3751                 :        2070 :           if (gimple_assign_load_p (stmt))
    3752                 :             :             {
    3753                 :        1192 :               tree rhs = gimple_assign_rhs1 (stmt);
    3754                 :        1192 :               tree base = get_base_address (rhs);
    3755                 :        2124 :               if (TREE_CODE (base) == MEM_REF
    3756                 :        1192 :                   && operand_equal_p (TREE_OPERAND (base, 0), omp_data_i, 0))
    3757                 :         932 :                 continue;
    3758                 :             : 
    3759                 :         260 :               tree lhs = gimple_assign_lhs (stmt);
    3760                 :         260 :               if (TREE_CODE (lhs) == SSA_NAME
    3761                 :         260 :                   && has_single_use (lhs))
    3762                 :             :                 {
    3763                 :         152 :                   use_operand_p use_p;
    3764                 :         152 :                   gimple *use_stmt;
    3765                 :         152 :                   struct reduction_info *red;
    3766                 :         152 :                   single_imm_use (lhs, &use_p, &use_stmt);
    3767                 :         152 :                   if (gimple_code (use_stmt) == GIMPLE_PHI
    3768                 :         152 :                       && (red = reduction_phi (reduction_list, use_stmt)))
    3769                 :             :                     {
    3770                 :          14 :                       tree val = PHI_RESULT (red->keep_res);
    3771                 :          14 :                       if (has_single_use (val))
    3772                 :             :                         {
    3773                 :          14 :                           single_imm_use (val, &use_p, &use_stmt);
    3774                 :          14 :                           if (gimple_store_p (use_stmt))
    3775                 :             :                             {
    3776                 :          14 :                               unsigned int id
    3777                 :          28 :                                 = SSA_NAME_VERSION (gimple_vdef (use_stmt));
    3778                 :          14 :                               bitmap_set_bit (reduction_stores, id);
    3779                 :          14 :                               skip_stmt = use_stmt;
    3780                 :          14 :                               if (dump_file)
    3781                 :             :                                 {
    3782                 :          12 :                                   fprintf (dump_file, "found reduction load: ");
    3783                 :          12 :                                   print_gimple_stmt (dump_file, stmt, 0);
    3784                 :             :                                 }
    3785                 :             :                             }
    3786                 :             :                         }
    3787                 :             :                     }
    3788                 :             :                 }
    3789                 :             : 
    3790                 :         260 :               ao_ref_init (&ref, rhs);
    3791                 :             :             }
    3792                 :         878 :           else if (gimple_store_p (stmt))
    3793                 :             :             {
    3794                 :         298 :               ao_ref_init (&ref, gimple_assign_lhs (stmt));
    3795                 :         298 :               ref_is_store = true;
    3796                 :             :             }
    3797                 :         580 :           else if (gimple_code (stmt) == GIMPLE_OMP_RETURN)
    3798                 :           0 :             continue;
    3799                 :         580 :           else if (!gimple_has_side_effects (stmt)
    3800                 :         580 :                    && !gimple_could_trap_p (stmt)
    3801                 :         580 :                    && !stmt_could_throw_p (cfun, stmt)
    3802                 :         580 :                    && !gimple_vdef (stmt)
    3803                 :        1160 :                    && !gimple_vuse (stmt))
    3804                 :         198 :             continue;
    3805                 :         382 :           else if (gimple_call_internal_p (stmt, IFN_GOACC_DIM_POS))
    3806                 :           0 :             continue;
    3807                 :         382 :           else if (gimple_code (stmt) == GIMPLE_RETURN)
    3808                 :         382 :             continue;
    3809                 :             :           else
    3810                 :             :             {
    3811                 :           0 :               if (dump_file)
    3812                 :             :                 {
    3813                 :           0 :                   fprintf (dump_file, "Unhandled stmt in entry/exit: ");
    3814                 :           0 :                   print_gimple_stmt (dump_file, stmt, 0);
    3815                 :             :                 }
    3816                 :           4 :               return false;
    3817                 :             :             }
    3818                 :             : 
    3819                 :         558 :           if (ref_conflicts_with_region (gsi, &ref, ref_is_store, region_bbs,
    3820                 :             :                                          i, skip_stmt))
    3821                 :             :             {
    3822                 :           4 :               if (dump_file)
    3823                 :             :                 {
    3824                 :           1 :                   fprintf (dump_file, "conflicts with entry/exit stmt: ");
    3825                 :           1 :                   print_gimple_stmt (dump_file, stmt, 0);
    3826                 :             :                 }
    3827                 :           4 :               return false;
    3828                 :             :             }
    3829                 :             :         }
    3830                 :             :     }
    3831                 :             : 
    3832                 :             :   return true;
    3833                 :             : }
    3834                 :             : 
    3835                 :             : /* Find stores inside REGION_BBS and outside IN_LOOP_BBS, and guard them with
    3836                 :             :    gang_pos == 0, except when the stores are REDUCTION_STORES.  Return true
    3837                 :             :    if any changes were made.  */
    3838                 :             : 
    3839                 :             : static bool
    3840                 :         382 : oacc_entry_exit_single_gang (bitmap in_loop_bbs,
    3841                 :             :                              const vec<basic_block> &region_bbs,
    3842                 :             :                              bitmap reduction_stores)
    3843                 :             : {
    3844                 :         382 :   tree gang_pos = NULL_TREE;
    3845                 :         382 :   bool changed = false;
    3846                 :             : 
    3847                 :         382 :   unsigned i;
    3848                 :         382 :   basic_block bb;
    3849                 :        2602 :   FOR_EACH_VEC_ELT (region_bbs, i, bb)
    3850                 :             :     {
    3851                 :        2220 :       if (bitmap_bit_p (in_loop_bbs, bb->index))
    3852                 :         962 :         continue;
    3853                 :             : 
    3854                 :        1258 :       gimple_stmt_iterator gsi;
    3855                 :        4666 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    3856                 :             :         {
    3857                 :        2150 :           gimple *stmt = gsi_stmt (gsi);
    3858                 :             : 
    3859                 :        2150 :           if (!gimple_store_p (stmt))
    3860                 :             :             {
    3861                 :             :               /* Update gsi to point to next stmt.  */
    3862                 :        1852 :               gsi_next (&gsi);
    3863                 :        1852 :               continue;
    3864                 :             :             }
    3865                 :             : 
    3866                 :         596 :           if (bitmap_bit_p (reduction_stores,
    3867                 :         298 :                             SSA_NAME_VERSION (gimple_vdef (stmt))))
    3868                 :             :             {
    3869                 :          14 :               if (dump_file)
    3870                 :             :                 {
    3871                 :          12 :                   fprintf (dump_file,
    3872                 :             :                            "skipped reduction store for single-gang"
    3873                 :             :                            " neutering: ");
    3874                 :          12 :                   print_gimple_stmt (dump_file, stmt, 0);
    3875                 :             :                 }
    3876                 :             : 
    3877                 :             :               /* Update gsi to point to next stmt.  */
    3878                 :          14 :               gsi_next (&gsi);
    3879                 :          14 :               continue;
    3880                 :             :             }
    3881                 :             : 
    3882                 :         284 :           changed = true;
    3883                 :             : 
    3884                 :         284 :           if (gang_pos == NULL_TREE)
    3885                 :             :             {
    3886                 :         138 :               tree arg = build_int_cst (integer_type_node, GOMP_DIM_GANG);
    3887                 :         138 :               gcall *gang_single
    3888                 :         138 :                 = gimple_build_call_internal (IFN_GOACC_DIM_POS, 1, arg);
    3889                 :         138 :               gang_pos = make_ssa_name (integer_type_node);
    3890                 :         138 :               gimple_call_set_lhs (gang_single, gang_pos);
    3891                 :         138 :               gimple_stmt_iterator start
    3892                 :         138 :                 = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
    3893                 :         138 :               tree vuse = ssa_default_def (cfun, gimple_vop (cfun));
    3894                 :         138 :               gimple_set_vuse (gang_single, vuse);
    3895                 :         138 :               gsi_insert_before (&start, gang_single, GSI_SAME_STMT);
    3896                 :             :             }
    3897                 :             : 
    3898                 :         284 :           if (dump_file)
    3899                 :             :             {
    3900                 :         112 :               fprintf (dump_file,
    3901                 :             :                        "found store that needs single-gang neutering: ");
    3902                 :         112 :               print_gimple_stmt (dump_file, stmt, 0);
    3903                 :             :             }
    3904                 :             : 
    3905                 :         284 :           {
    3906                 :             :             /* Split block before store.  */
    3907                 :         284 :             gimple_stmt_iterator gsi2 = gsi;
    3908                 :         284 :             gsi_prev (&gsi2);
    3909                 :         284 :             edge e;
    3910                 :         284 :             if (gsi_end_p (gsi2))
    3911                 :             :               {
    3912                 :           8 :                 e = split_block_after_labels (bb);
    3913                 :          16 :                 gsi2 = gsi_last_bb (bb);
    3914                 :             :               }
    3915                 :             :             else
    3916                 :         276 :               e = split_block (bb, gsi_stmt (gsi2));
    3917                 :         284 :             basic_block bb2 = e->dest;
    3918                 :             : 
    3919                 :             :             /* Split block after store.  */
    3920                 :         284 :             gimple_stmt_iterator gsi3 = gsi_start_bb (bb2);
    3921                 :         284 :             edge e2 = split_block (bb2, gsi_stmt (gsi3));
    3922                 :         284 :             basic_block bb3 = e2->dest;
    3923                 :             : 
    3924                 :         284 :             gimple *cond
    3925                 :         284 :               = gimple_build_cond (EQ_EXPR, gang_pos, integer_zero_node,
    3926                 :             :                                    NULL_TREE, NULL_TREE);
    3927                 :         284 :             gsi_insert_after (&gsi2, cond, GSI_NEW_STMT);
    3928                 :             : 
    3929                 :         284 :             edge e3 = make_edge (bb, bb3, EDGE_FALSE_VALUE);
    3930                 :             :             /* FIXME: What is the probability?  */
    3931                 :         284 :             e3->probability = profile_probability::guessed_never ();
    3932                 :         284 :             e->flags = EDGE_TRUE_VALUE;
    3933                 :             : 
    3934                 :         284 :             tree vdef = gimple_vdef (stmt);
    3935                 :         284 :             tree vuse = gimple_vuse (stmt);
    3936                 :             : 
    3937                 :         284 :             tree phi_res = copy_ssa_name (vdef);
    3938                 :         284 :             gphi *new_phi = create_phi_node (phi_res, bb3);
    3939                 :         284 :             replace_uses_by (vdef, phi_res);
    3940                 :         284 :             add_phi_arg (new_phi, vuse, e3, UNKNOWN_LOCATION);
    3941                 :         284 :             add_phi_arg (new_phi, vdef, e2, UNKNOWN_LOCATION);
    3942                 :             : 
    3943                 :             :             /* Update gsi to point to next stmt.  */
    3944                 :         284 :             bb = bb3;
    3945                 :         568 :             gsi = gsi_start_bb (bb);
    3946                 :             :           }
    3947                 :             :         }
    3948                 :             :     }
    3949                 :             : 
    3950                 :         382 :   return changed;
    3951                 :             : }
    3952                 :             : 
    3953                 :             : /* Return true if the statements before and after the LOOP can be executed in
    3954                 :             :    parallel with the function containing the loop.  Resolve conflicting stores
    3955                 :             :    outside LOOP by guarding them such that only a single gang executes them.  */
    3956                 :             : 
    3957                 :             : static bool
    3958                 :         386 : oacc_entry_exit_ok (class loop *loop,
    3959                 :             :                     reduction_info_table_type *reduction_list)
    3960                 :             : {
    3961                 :         386 :   basic_block *loop_bbs = get_loop_body_in_dom_order (loop);
    3962                 :         386 :   auto_vec<basic_block> region_bbs
    3963                 :         386 :     = get_all_dominated_blocks (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun));
    3964                 :             : 
    3965                 :         386 :   bitmap in_loop_bbs = BITMAP_ALLOC (NULL);
    3966                 :         386 :   bitmap_clear (in_loop_bbs);
    3967                 :        1356 :   for (unsigned int i = 0; i < loop->num_nodes; i++)
    3968                 :         970 :     bitmap_set_bit (in_loop_bbs, loop_bbs[i]->index);
    3969                 :             : 
    3970                 :         386 :   bitmap reduction_stores = BITMAP_ALLOC (NULL);
    3971                 :         386 :   bool res = oacc_entry_exit_ok_1 (in_loop_bbs, region_bbs, reduction_list,
    3972                 :             :                                    reduction_stores);
    3973                 :             : 
    3974                 :         386 :   if (res)
    3975                 :             :     {
    3976                 :         382 :       bool changed = oacc_entry_exit_single_gang (in_loop_bbs, region_bbs,
    3977                 :             :                                                   reduction_stores);
    3978                 :         382 :       if (changed)
    3979                 :             :         {
    3980                 :         138 :           free_dominance_info (CDI_DOMINATORS);
    3981                 :         138 :           calculate_dominance_info (CDI_DOMINATORS);
    3982                 :             :         }
    3983                 :             :     }
    3984                 :             : 
    3985                 :         386 :   free (loop_bbs);
    3986                 :             : 
    3987                 :         386 :   BITMAP_FREE (in_loop_bbs);
    3988                 :         386 :   BITMAP_FREE (reduction_stores);
    3989                 :             : 
    3990                 :         386 :   return res;
    3991                 :         386 : }
    3992                 :             : 
    3993                 :             : /* Detect parallel loops and generate parallel code using libgomp
    3994                 :             :    primitives.  Returns true if some loop was parallelized, false
    3995                 :             :    otherwise.  */
    3996                 :             : 
    3997                 :             : static bool
    3998                 :        1684 : parallelize_loops (bool oacc_kernels_p)
    3999                 :             : {
    4000                 :        1684 :   unsigned n_threads;
    4001                 :        1684 :   bool changed = false;
    4002                 :        1684 :   class loop *skip_loop = NULL;
    4003                 :        1684 :   class tree_niter_desc niter_desc;
    4004                 :        1684 :   struct obstack parloop_obstack;
    4005                 :        1684 :   HOST_WIDE_INT estimated;
    4006                 :             : 
    4007                 :             :   /* Do not parallelize loops in the functions created by parallelization.  */
    4008                 :        1684 :   if (!oacc_kernels_p
    4009                 :        1684 :       && parallelized_function_p (cfun->decl))
    4010                 :             :     return false;
    4011                 :             : 
    4012                 :             :   /* Do not parallelize loops in offloaded functions.  */
    4013                 :        1481 :   if (!oacc_kernels_p
    4014                 :        1481 :       && oacc_get_fn_attrib (cfun->decl) != NULL)
    4015                 :             :      return false;
    4016                 :             : 
    4017                 :        1481 :   if (cfun->has_nonlocal_label)
    4018                 :             :     return false;
    4019                 :             : 
    4020                 :             :   /* For OpenACC kernels, n_threads will be determined later; otherwise, it's
    4021                 :             :      the argument to -ftree-parallelize-loops.  */
    4022                 :        1481 :   if (oacc_kernels_p)
    4023                 :             :     n_threads = 0;
    4024                 :             :   else
    4025                 :         437 :     n_threads = flag_tree_parallelize_loops;
    4026                 :             : 
    4027                 :        1481 :   gcc_obstack_init (&parloop_obstack);
    4028                 :        1481 :   reduction_info_table_type reduction_list (10);
    4029                 :             : 
    4030                 :        1481 :   calculate_dominance_info (CDI_DOMINATORS);
    4031                 :             : 
    4032                 :        7293 :   for (auto loop : loops_list (cfun, 0))
    4033                 :             :     {
    4034                 :        2850 :       if (loop == skip_loop)
    4035                 :             :         {
    4036                 :         632 :           if (!loop->in_oacc_kernels_region
    4037                 :         632 :               && dump_file && (dump_flags & TDF_DETAILS))
    4038                 :          17 :             fprintf (dump_file,
    4039                 :             :                      "Skipping loop %d as inner loop of parallelized loop\n",
    4040                 :             :                      loop->num);
    4041                 :             : 
    4042                 :         632 :           skip_loop = loop->inner;
    4043                 :         632 :           continue;
    4044                 :             :         }
    4045                 :             :       else
    4046                 :        2218 :         skip_loop = NULL;
    4047                 :             : 
    4048                 :        2218 :       reduction_list.empty ();
    4049                 :             : 
    4050                 :        2218 :       if (oacc_kernels_p)
    4051                 :             :         {
    4052                 :        1044 :           if (!loop->in_oacc_kernels_region)
    4053                 :           0 :             continue;
    4054                 :             : 
    4055                 :             :           /* Don't try to parallelize inner loops in an oacc kernels region.  */
    4056                 :        1044 :           if (loop->inner)
    4057                 :             :             skip_loop = loop->inner;
    4058                 :             : 
    4059                 :        1044 :           if (dump_file && (dump_flags & TDF_DETAILS))
    4060                 :         165 :             fprintf (dump_file,
    4061                 :             :                      "Trying loop %d with header bb %d in oacc kernels"
    4062                 :         165 :                      " region\n", loop->num, loop->header->index);
    4063                 :             :         }
    4064                 :             : 
    4065                 :        2218 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4066                 :             :       {
    4067                 :         298 :         fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
    4068                 :         298 :         if (loop->inner)
    4069                 :          52 :           fprintf (dump_file, "loop %d is not innermost\n",loop->num);
    4070                 :             :         else
    4071                 :         246 :           fprintf (dump_file, "loop %d is innermost\n",loop->num);
    4072                 :             :       }
    4073                 :             : 
    4074                 :        2218 :       if (!single_dom_exit (loop))
    4075                 :             :       {
    4076                 :             : 
    4077                 :         304 :         if (dump_file && (dump_flags & TDF_DETAILS))
    4078                 :          21 :           fprintf (dump_file, "loop is !single_dom_exit\n");
    4079                 :             : 
    4080                 :         304 :         continue;
    4081                 :             :       }
    4082                 :             : 
    4083                 :        1914 :       if (/* And of course, the loop must be parallelizable.  */
    4084                 :        1914 :           !can_duplicate_loop_p (loop)
    4085                 :        1914 :           || loop_has_blocks_with_irreducible_flag (loop)
    4086                 :        1914 :           || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
    4087                 :             :           /* FIXME: the check for vector phi nodes could be removed.  */
    4088                 :        3828 :           || loop_has_vector_phi_nodes (loop))
    4089                 :           0 :         continue;
    4090                 :             : 
    4091                 :        1914 :       estimated = estimated_loop_iterations_int (loop);
    4092                 :        1914 :       if (estimated == -1)
    4093                 :        1208 :         estimated = get_likely_max_loop_iterations_int (loop);
    4094                 :             :       /* FIXME: Bypass this check as graphite doesn't update the
    4095                 :             :          count and frequency correctly now.  */
    4096                 :        2043 :       if (!flag_loop_parallelize_all
    4097                 :        1823 :           && !oacc_kernels_p
    4098                 :        2693 :           && ((estimated != -1
    4099                 :         431 :                && (estimated
    4100                 :         431 :                    < ((HOST_WIDE_INT) n_threads
    4101                 :         431 :                       * (loop->inner ? 2 : MIN_PER_THREAD) - 1)))
    4102                 :             :               /* Do not bother with loops in cold areas.  */
    4103                 :         658 :               || optimize_loop_nest_for_size_p (loop)))
    4104                 :         129 :         continue;
    4105                 :             : 
    4106                 :        1785 :       if (!try_get_loop_niter (loop, &niter_desc))
    4107                 :         574 :         continue;
    4108                 :             : 
    4109                 :        1211 :       if (!try_create_reduction_list (loop, &reduction_list, oacc_kernels_p))
    4110                 :          79 :         continue;
    4111                 :             : 
    4112                 :        1132 :       if (loop_has_phi_with_address_arg (loop))
    4113                 :           0 :         continue;
    4114                 :             : 
    4115                 :        1674 :       if (!loop->can_be_parallel
    4116                 :        1132 :           && !loop_parallel_p (loop, &parloop_obstack))
    4117                 :         542 :         continue;
    4118                 :             : 
    4119                 :         594 :       if (oacc_kernels_p
    4120                 :         590 :         && !oacc_entry_exit_ok (loop, &reduction_list))
    4121                 :             :         {
    4122                 :           4 :           if (dump_file)
    4123                 :           1 :             fprintf (dump_file, "entry/exit not ok: FAILED\n");
    4124                 :           4 :           continue;
    4125                 :             :         }
    4126                 :             : 
    4127                 :         586 :       changed = true;
    4128                 :         586 :       skip_loop = loop->inner;
    4129                 :             : 
    4130                 :         586 :       if (dump_enabled_p ())
    4131                 :             :         {
    4132                 :         226 :           dump_user_location_t loop_loc = find_loop_location (loop);
    4133                 :         226 :           if (loop->inner)
    4134                 :          26 :             dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
    4135                 :             :                              "parallelizing outer loop %d\n", loop->num);
    4136                 :             :           else
    4137                 :         200 :             dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
    4138                 :             :                              "parallelizing inner loop %d\n", loop->num);
    4139                 :             :         }
    4140                 :             : 
    4141                 :         586 :       gen_parallel_loop (loop, &reduction_list,
    4142                 :             :                          n_threads, &niter_desc, oacc_kernels_p);
    4143                 :        1481 :     }
    4144                 :             : 
    4145                 :        1481 :   obstack_free (&parloop_obstack, NULL);
    4146                 :             : 
    4147                 :             :   /* Parallelization will cause new function calls to be inserted through
    4148                 :             :      which local variables will escape.  Reset the points-to solution
    4149                 :             :      for ESCAPED.  */
    4150                 :        1481 :   if (changed)
    4151                 :             :     {
    4152                 :         554 :       pt_solution_reset (&cfun->gimple_df->escaped);
    4153                 :         554 :       pt_solution_reset (&cfun->gimple_df->escaped_return);
    4154                 :             :     }
    4155                 :             : 
    4156                 :        1481 :   return changed;
    4157                 :        1481 : }
    4158                 :             : 
    4159                 :             : /* Parallelization.  */
    4160                 :             : 
    4161                 :             : namespace {
    4162                 :             : 
    4163                 :             : const pass_data pass_data_parallelize_loops =
    4164                 :             : {
    4165                 :             :   GIMPLE_PASS, /* type */
    4166                 :             :   "parloops", /* name */
    4167                 :             :   OPTGROUP_LOOP, /* optinfo_flags */
    4168                 :             :   TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
    4169                 :             :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    4170                 :             :   0, /* properties_provided */
    4171                 :             :   0, /* properties_destroyed */
    4172                 :             :   0, /* todo_flags_start */
    4173                 :             :   0, /* todo_flags_finish */
    4174                 :             : };
    4175                 :             : 
    4176                 :             : class pass_parallelize_loops : public gimple_opt_pass
    4177                 :             : {
    4178                 :             : public:
    4179                 :      546392 :   pass_parallelize_loops (gcc::context *ctxt)
    4180                 :      546392 :     : gimple_opt_pass (pass_data_parallelize_loops, ctxt),
    4181                 :     1092784 :       oacc_kernels_p (false)
    4182                 :             :   {}
    4183                 :             : 
    4184                 :             :   /* opt_pass methods: */
    4185                 :      222808 :   bool gate (function *) final override
    4186                 :             :   {
    4187                 :      222808 :     if (oacc_kernels_p)
    4188                 :        1049 :       return flag_openacc;
    4189                 :             :     else
    4190                 :      221759 :       return flag_tree_parallelize_loops > 1;
    4191                 :             :   }
    4192                 :             :   unsigned int execute (function *) final override;
    4193                 :      273196 :   opt_pass * clone () final override
    4194                 :             :   {
    4195                 :      273196 :     return new pass_parallelize_loops (m_ctxt);
    4196                 :             :   }
    4197                 :      546392 :   void set_pass_param (unsigned int n, bool param) final override
    4198                 :             :     {
    4199                 :      546392 :       gcc_assert (n == 0);
    4200                 :      546392 :       oacc_kernels_p = param;
    4201                 :      546392 :     }
    4202                 :             : 
    4203                 :             :  private:
    4204                 :             :   bool oacc_kernels_p;
    4205                 :             : }; // class pass_parallelize_loops
    4206                 :             : 
    4207                 :             : unsigned
    4208                 :        1684 : pass_parallelize_loops::execute (function *fun)
    4209                 :             : {
    4210                 :        1684 :   tree nthreads = builtin_decl_explicit (BUILT_IN_OMP_GET_NUM_THREADS);
    4211                 :        1684 :   if (nthreads == NULL_TREE)
    4212                 :             :     return 0;
    4213                 :             : 
    4214                 :        1684 :   bool in_loop_pipeline = scev_initialized_p ();
    4215                 :        1684 :   if (!in_loop_pipeline)
    4216                 :        1044 :     loop_optimizer_init (LOOPS_NORMAL
    4217                 :             :                          | LOOPS_HAVE_RECORDED_EXITS);
    4218                 :             : 
    4219                 :        3368 :   if (number_of_loops (fun) <= 1)
    4220                 :             :     return 0;
    4221                 :             : 
    4222                 :        1684 :   if (!in_loop_pipeline)
    4223                 :             :     {
    4224                 :        1044 :       rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    4225                 :        1044 :       scev_initialize ();
    4226                 :             :     }
    4227                 :             : 
    4228                 :        1684 :   unsigned int todo = 0;
    4229                 :        1684 :   if (parallelize_loops (oacc_kernels_p))
    4230                 :             :     {
    4231                 :         554 :       fun->curr_properties &= ~(PROP_gimple_eomp);
    4232                 :             : 
    4233                 :         554 :       checking_verify_loop_structure ();
    4234                 :             : 
    4235                 :             :       /* ???  Intermediate SSA updates with no PHIs might have lost
    4236                 :             :          the virtual operand renaming needed by separate_decls_in_region,
    4237                 :             :          make sure to rename them again.  */
    4238                 :         554 :       mark_virtual_operands_for_renaming (fun);
    4239                 :         554 :       update_ssa (TODO_update_ssa);
    4240                 :         554 :       if (in_loop_pipeline)
    4241                 :         172 :         rewrite_into_loop_closed_ssa (NULL, 0);
    4242                 :             :     }
    4243                 :             : 
    4244                 :        1302 :   if (!in_loop_pipeline)
    4245                 :             :     {
    4246                 :        1044 :       scev_finalize ();
    4247                 :        1044 :       loop_optimizer_finalize ();
    4248                 :             :     }
    4249                 :             : 
    4250                 :             :   return todo;
    4251                 :             : }
    4252                 :             : 
    4253                 :             : } // anon namespace
    4254                 :             : 
    4255                 :             : gimple_opt_pass *
    4256                 :      273196 : make_pass_parallelize_loops (gcc::context *ctxt)
    4257                 :             : {
    4258                 :      273196 :   return new pass_parallelize_loops (ctxt);
    4259                 :             : }
        

Generated by: LCOV version 2.1-beta

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