LCOV - code coverage report
Current view: top level - gcc - loop-unroll.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 91.1 % 901 821
Test Date: 2025-02-01 13:18:56 Functions: 89.7 % 29 26
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Loop unrolling.
       2                 :             :    Copyright (C) 2002-2025 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it under
       7                 :             : the terms of the GNU General Public License as published by the Free
       8                 :             : Software Foundation; either version 3, or (at your option) any later
       9                 :             : version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : #include "config.h"
      21                 :             : #include "system.h"
      22                 :             : #include "coretypes.h"
      23                 :             : #include "backend.h"
      24                 :             : #include "target.h"
      25                 :             : #include "rtl.h"
      26                 :             : #include "tree.h"
      27                 :             : #include "cfghooks.h"
      28                 :             : #include "memmodel.h"
      29                 :             : #include "optabs.h"
      30                 :             : #include "emit-rtl.h"
      31                 :             : #include "recog.h"
      32                 :             : #include "profile.h"
      33                 :             : #include "cfgrtl.h"
      34                 :             : #include "cfgloop.h"
      35                 :             : #include "dojump.h"
      36                 :             : #include "expr.h"
      37                 :             : #include "dumpfile.h"
      38                 :             : 
      39                 :             : /* This pass performs loop unrolling.  We only perform this
      40                 :             :    optimization on innermost loops (with single exception) because
      41                 :             :    the impact on performance is greatest here, and we want to avoid
      42                 :             :    unnecessary code size growth.  The gain is caused by greater sequentiality
      43                 :             :    of code, better code to optimize for further passes and in some cases
      44                 :             :    by fewer testings of exit conditions.  The main problem is code growth,
      45                 :             :    that impacts performance negatively due to effect of caches.
      46                 :             : 
      47                 :             :    What we do:
      48                 :             : 
      49                 :             :    -- unrolling of loops that roll constant times; this is almost always
      50                 :             :       win, as we get rid of exit condition tests.
      51                 :             :    -- unrolling of loops that roll number of times that we can compute
      52                 :             :       in runtime; we also get rid of exit condition tests here, but there
      53                 :             :       is the extra expense for calculating the number of iterations
      54                 :             :    -- simple unrolling of remaining loops; this is performed only if we
      55                 :             :       are asked to, as the gain is questionable in this case and often
      56                 :             :       it may even slow down the code
      57                 :             :    For more detailed descriptions of each of those, see comments at
      58                 :             :    appropriate function below.
      59                 :             : 
      60                 :             :    There is a lot of parameters (defined and described in params.def) that
      61                 :             :    control how much we unroll.
      62                 :             : 
      63                 :             :    ??? A great problem is that we don't have a good way how to determine
      64                 :             :    how many times we should unroll the loop; the experiments I have made
      65                 :             :    showed that this choice may affect performance in order of several %.
      66                 :             :    */
      67                 :             : 
      68                 :             : /* Information about induction variables to split.  */
      69                 :             : 
      70                 :             : struct iv_to_split
      71                 :             : {
      72                 :             :   rtx_insn *insn;       /* The insn in that the induction variable occurs.  */
      73                 :             :   rtx orig_var;         /* The variable (register) for the IV before split.  */
      74                 :             :   rtx base_var;         /* The variable on that the values in the further
      75                 :             :                            iterations are based.  */
      76                 :             :   rtx step;             /* Step of the induction variable.  */
      77                 :             :   struct iv_to_split *next; /* Next entry in walking order.  */
      78                 :             : };
      79                 :             : 
      80                 :             : /* Information about accumulators to expand.  */
      81                 :             : 
      82                 :             : struct var_to_expand
      83                 :             : {
      84                 :             :   rtx_insn *insn;                  /* The insn in that the variable expansion occurs.  */
      85                 :             :   rtx reg;                         /* The accumulator which is expanded.  */
      86                 :             :   vec<rtx> var_expansions;   /* The copies of the accumulator which is expanded.  */
      87                 :             :   struct var_to_expand *next;      /* Next entry in walking order.  */
      88                 :             :   enum rtx_code op;                /* The type of the accumulation - addition, subtraction
      89                 :             :                                       or multiplication.  */
      90                 :             :   int expansion_count;             /* Count the number of expansions generated so far.  */
      91                 :             :   int reuse_expansion;             /* The expansion we intend to reuse to expand
      92                 :             :                                       the accumulator.  If REUSE_EXPANSION is 0 reuse
      93                 :             :                                       the original accumulator.  Else use
      94                 :             :                                       var_expansions[REUSE_EXPANSION - 1].  */
      95                 :             : };
      96                 :             : 
      97                 :             : /* Hashtable helper for iv_to_split.  */
      98                 :             : 
      99                 :             : struct iv_split_hasher : free_ptr_hash <iv_to_split>
     100                 :             : {
     101                 :             :   static inline hashval_t hash (const iv_to_split *);
     102                 :             :   static inline bool equal (const iv_to_split *, const iv_to_split *);
     103                 :             : };
     104                 :             : 
     105                 :             : 
     106                 :             : /* A hash function for information about insns to split.  */
     107                 :             : 
     108                 :             : inline hashval_t
     109                 :   217754285 : iv_split_hasher::hash (const iv_to_split *ivts)
     110                 :             : {
     111                 :   217754285 :   return (hashval_t) INSN_UID (ivts->insn);
     112                 :             : }
     113                 :             : 
     114                 :             : /* An equality functions for information about insns to split.  */
     115                 :             : 
     116                 :             : inline bool
     117                 :   102287076 : iv_split_hasher::equal (const iv_to_split *i1, const iv_to_split *i2)
     118                 :             : {
     119                 :   102287076 :   return i1->insn == i2->insn;
     120                 :             : }
     121                 :             : 
     122                 :             : /* Hashtable helper for iv_to_split.  */
     123                 :             : 
     124                 :             : struct var_expand_hasher : free_ptr_hash <var_to_expand>
     125                 :             : {
     126                 :             :   static inline hashval_t hash (const var_to_expand *);
     127                 :             :   static inline bool equal (const var_to_expand *, const var_to_expand *);
     128                 :             : };
     129                 :             : 
     130                 :             : /* Return a hash for VES.  */
     131                 :             : 
     132                 :             : inline hashval_t
     133                 :         360 : var_expand_hasher::hash (const var_to_expand *ves)
     134                 :             : {
     135                 :         360 :   return (hashval_t) INSN_UID (ves->insn);
     136                 :             : }
     137                 :             : 
     138                 :             : /* Return true if I1 and I2 refer to the same instruction.  */
     139                 :             : 
     140                 :             : inline bool
     141                 :          84 : var_expand_hasher::equal (const var_to_expand *i1, const var_to_expand *i2)
     142                 :             : {
     143                 :          84 :   return i1->insn == i2->insn;
     144                 :             : }
     145                 :             : 
     146                 :             : /* Information about optimization applied in
     147                 :             :    the unrolled loop.  */
     148                 :             : 
     149                 :             : struct opt_info
     150                 :             : {
     151                 :             :   hash_table<iv_split_hasher> *insns_to_split; /* A hashtable of insns to
     152                 :             :                                                   split.  */
     153                 :             :   struct iv_to_split *iv_to_split_head; /* The first iv to split.  */
     154                 :             :   struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list.  */
     155                 :             :   hash_table<var_expand_hasher> *insns_with_var_to_expand; /* A hashtable of
     156                 :             :                                         insns with accumulators to expand.  */
     157                 :             :   struct var_to_expand *var_to_expand_head; /* The first var to expand.  */
     158                 :             :   struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list.  */
     159                 :             :   unsigned first_new_block;        /* The first basic block that was
     160                 :             :                                       duplicated.  */
     161                 :             :   basic_block loop_exit;           /* The loop exit basic block.  */
     162                 :             :   basic_block loop_preheader;      /* The loop preheader basic block.  */
     163                 :             : };
     164                 :             : 
     165                 :             : static void decide_unroll_stupid (class loop *, int);
     166                 :             : static void decide_unroll_constant_iterations (class loop *, int);
     167                 :             : static void decide_unroll_runtime_iterations (class loop *, int);
     168                 :             : static void unroll_loop_stupid (class loop *);
     169                 :             : static void decide_unrolling (int);
     170                 :             : static void unroll_loop_constant_iterations (class loop *);
     171                 :             : static void unroll_loop_runtime_iterations (class loop *);
     172                 :             : static struct opt_info *analyze_insns_in_loop (class loop *);
     173                 :             : static void opt_info_start_duplication (struct opt_info *);
     174                 :             : static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
     175                 :             : static void free_opt_info (struct opt_info *);
     176                 :             : static struct var_to_expand *analyze_insn_to_expand_var (class loop*, rtx_insn *);
     177                 :             : static bool referenced_in_one_insn_in_loop_p (class loop *, rtx, int *);
     178                 :             : static struct iv_to_split *analyze_iv_to_split_insn (rtx_insn *);
     179                 :             : static void expand_var_during_unrolling (struct var_to_expand *, rtx_insn *);
     180                 :             : static void insert_var_expansion_initialization (struct var_to_expand *,
     181                 :             :                                                  basic_block);
     182                 :             : static void combine_var_copies_in_loop_exit (struct var_to_expand *,
     183                 :             :                                              basic_block);
     184                 :             : static rtx get_expansion (struct var_to_expand *);
     185                 :             : 
     186                 :             : /* Emit a message summarizing the unroll that will be
     187                 :             :    performed for LOOP, along with the loop's location LOCUS, if
     188                 :             :    appropriate given the dump or -fopt-info settings.  */
     189                 :             : 
     190                 :             : static void
     191                 :      376190 : report_unroll (class loop *loop, dump_location_t locus)
     192                 :             : {
     193                 :      376190 :   dump_flags_t report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS;
     194                 :             : 
     195                 :      376190 :   if (loop->lpt_decision.decision == LPT_NONE)
     196                 :      376116 :     return;
     197                 :             : 
     198                 :       48010 :   if (!dump_enabled_p ())
     199                 :             :     return;
     200                 :             : 
     201                 :          74 :   dump_metadata_t metadata (report_flags, locus.get_impl_location ());
     202                 :          74 :   dump_printf_loc (metadata, locus.get_user_location (),
     203                 :             :                    "loop unrolled %d times",
     204                 :             :                    loop->lpt_decision.times);
     205                 :          74 :   if (profile_info && loop->header->count.initialized_p ())
     206                 :           1 :     dump_printf (metadata,
     207                 :             :                  " (header execution count %d)",
     208                 :           1 :                  (int)loop->header->count.to_gcov_type ());
     209                 :             : 
     210                 :          74 :   dump_printf (metadata, "\n");
     211                 :             : }
     212                 :             : 
     213                 :             : /* Decide whether unroll loops and how much.  */
     214                 :             : static void
     215                 :      205556 : decide_unrolling (int flags)
     216                 :             : {
     217                 :             :   /* Scan the loops, inner ones first.  */
     218                 :     1155656 :   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
     219                 :             :     {
     220                 :      538988 :       loop->lpt_decision.decision = LPT_NONE;
     221                 :      538988 :       dump_user_location_t locus = get_loop_location (loop);
     222                 :             : 
     223                 :      538988 :       if (dump_enabled_p ())
     224                 :         450 :         dump_printf_loc (MSG_NOTE, locus,
     225                 :             :                          "considering unrolling loop %d at BB %d\n",
     226                 :         450 :                          loop->num, loop->header->index);
     227                 :             : 
     228                 :      538988 :       if (loop->unroll == 1)
     229                 :             :         {
     230                 :          35 :           if (dump_file)
     231                 :          13 :             fprintf (dump_file,
     232                 :             :                      ";; Not unrolling loop, user didn't want it unrolled\n");
     233                 :      162798 :           continue;
     234                 :             :         }
     235                 :             : 
     236                 :             :       /* Do not peel cold areas.  */
     237                 :      538953 :       if (optimize_loop_for_size_p (loop))
     238                 :             :         {
     239                 :       69220 :           if (dump_file)
     240                 :           0 :             fprintf (dump_file, ";; Not considering loop, cold area\n");
     241                 :       69220 :           continue;
     242                 :             :         }
     243                 :             : 
     244                 :             :       /* Can the loop be manipulated?  */
     245                 :      469733 :       if (!can_duplicate_loop_p (loop))
     246                 :             :         {
     247                 :       10995 :           if (dump_file)
     248                 :           0 :             fprintf (dump_file,
     249                 :             :                      ";; Not considering loop, cannot duplicate\n");
     250                 :       10995 :           continue;
     251                 :             :         }
     252                 :             : 
     253                 :             :       /* Skip non-innermost loops.  */
     254                 :      458738 :       if (loop->inner)
     255                 :             :         {
     256                 :       82548 :           if (dump_file)
     257                 :           0 :             fprintf (dump_file, ";; Not considering loop, is not innermost\n");
     258                 :       82548 :           continue;
     259                 :             :         }
     260                 :             : 
     261                 :      376190 :       loop->ninsns = num_loop_insns (loop);
     262                 :      376190 :       loop->av_ninsns = average_num_loop_insns (loop);
     263                 :             : 
     264                 :             :       /* Try transformations one by one in decreasing order of priority.  */
     265                 :      376190 :       decide_unroll_constant_iterations (loop, flags);
     266                 :      376190 :       if (loop->lpt_decision.decision == LPT_NONE)
     267                 :      347601 :         decide_unroll_runtime_iterations (loop, flags);
     268                 :      376190 :       if (loop->lpt_decision.decision == LPT_NONE)
     269                 :      328284 :         decide_unroll_stupid (loop, flags);
     270                 :             : 
     271                 :      376190 :       report_unroll (loop, locus);
     272                 :      205556 :     }
     273                 :      205556 : }
     274                 :             : 
     275                 :             : /* Unroll LOOPS.  */
     276                 :             : void
     277                 :      205556 : unroll_loops (int flags)
     278                 :             : {
     279                 :      205556 :   bool changed = false;
     280                 :             : 
     281                 :             :   /* Now decide rest of unrolling.  */
     282                 :      205556 :   decide_unrolling (flags);
     283                 :             : 
     284                 :             :   /* Scan the loops, inner ones first.  */
     285                 :     1155656 :   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
     286                 :             :     {
     287                 :             :       /* And perform the appropriate transformations.  */
     288                 :      538988 :       switch (loop->lpt_decision.decision)
     289                 :             :         {
     290                 :       28589 :         case LPT_UNROLL_CONSTANT:
     291                 :       28589 :           unroll_loop_constant_iterations (loop);
     292                 :       28589 :           changed = true;
     293                 :       28589 :           break;
     294                 :       19317 :         case LPT_UNROLL_RUNTIME:
     295                 :       19317 :           unroll_loop_runtime_iterations (loop);
     296                 :       19317 :           changed = true;
     297                 :       19317 :           break;
     298                 :         104 :         case LPT_UNROLL_STUPID:
     299                 :         104 :           unroll_loop_stupid (loop);
     300                 :         104 :           changed = true;
     301                 :         104 :           break;
     302                 :             :         case LPT_NONE:
     303                 :             :           break;
     304                 :           0 :         default:
     305                 :           0 :           gcc_unreachable ();
     306                 :             :         }
     307                 :      205556 :     }
     308                 :             : 
     309                 :      205556 :     if (changed)
     310                 :             :       {
     311                 :       17903 :         calculate_dominance_info (CDI_DOMINATORS);
     312                 :       17903 :         fix_loop_structure (NULL);
     313                 :             :       }
     314                 :             : 
     315                 :      205556 :   iv_analysis_done ();
     316                 :      205556 : }
     317                 :             : 
     318                 :             : /* Check whether exit of the LOOP is at the end of loop body.  */
     319                 :             : 
     320                 :             : static bool
     321                 :      226683 : loop_exit_at_end_p (class loop *loop)
     322                 :             : {
     323                 :      226683 :   class niter_desc *desc = get_simple_loop_desc (loop);
     324                 :      226683 :   rtx_insn *insn;
     325                 :             : 
     326                 :             :   /* We should never have conditional in latch block.  */
     327                 :      226683 :   gcc_assert (desc->in_edge->dest != loop->header);
     328                 :             : 
     329                 :      226683 :   if (desc->in_edge->dest != loop->latch)
     330                 :             :     return false;
     331                 :             : 
     332                 :             :   /* Check that the latch is empty.  */
     333                 :      674542 :   FOR_BB_INSNS (loop->latch, insn)
     334                 :             :     {
     335                 :      449380 :       if (INSN_P (insn) && active_insn_p (insn))
     336                 :             :         return false;
     337                 :             :     }
     338                 :             : 
     339                 :             :   return true;
     340                 :             : }
     341                 :             : 
     342                 :             : /* Decide whether to unroll LOOP iterating constant number of times
     343                 :             :    and how much.  */
     344                 :             : 
     345                 :             : static void
     346                 :      376190 : decide_unroll_constant_iterations (class loop *loop, int flags)
     347                 :             : {
     348                 :      376190 :   unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
     349                 :      376190 :   class niter_desc *desc;
     350                 :      376190 :   widest_int iterations;
     351                 :             : 
     352                 :             :   /* If we were not asked to unroll this loop, just return back silently.  */
     353                 :      376190 :   if (!(flags & UAP_UNROLL) && !loop->unroll)
     354                 :             :     return;
     355                 :             : 
     356                 :      376113 :   if (dump_enabled_p ())
     357                 :         399 :     dump_printf (MSG_NOTE,
     358                 :             :                  "considering unrolling loop with constant "
     359                 :             :                  "number of iterations\n");
     360                 :             : 
     361                 :             :   /* nunroll = total number of copies of the original loop body in
     362                 :             :      unrolled loop (i.e. if it is 2, we have to duplicate loop body once).  */
     363                 :      376113 :   nunroll = param_max_unrolled_insns / loop->ninsns;
     364                 :      376113 :   nunroll_by_av
     365                 :      376113 :     = param_max_average_unrolled_insns / loop->av_ninsns;
     366                 :      376113 :   if (nunroll > nunroll_by_av)
     367                 :             :     nunroll = nunroll_by_av;
     368                 :      376113 :   if (nunroll > (unsigned) param_max_unroll_times)
     369                 :             :     nunroll = param_max_unroll_times;
     370                 :             : 
     371                 :      376113 :   if (targetm.loop_unroll_adjust)
     372                 :      376113 :     nunroll = targetm.loop_unroll_adjust (nunroll, loop);
     373                 :             : 
     374                 :             :   /* Skip big loops.  */
     375                 :      376113 :   if (nunroll <= 1
     376                 :      308694 :       && !(loop->unroll > 1 && loop->unroll < USHRT_MAX))
     377                 :             :     {
     378                 :      308694 :       if (dump_file)
     379                 :           8 :         fprintf (dump_file, ";; Not considering loop, is too big\n");
     380                 :      308694 :       return;
     381                 :             :     }
     382                 :             : 
     383                 :             :   /* Check for simple loops.  */
     384                 :       67419 :   desc = get_simple_loop_desc (loop);
     385                 :             : 
     386                 :             :   /* Check number of iterations.  */
     387                 :       67419 :   if (!desc->simple_p || !desc->const_iter || desc->assumptions)
     388                 :             :     {
     389                 :       36954 :       if (dump_file)
     390                 :          39 :         fprintf (dump_file,
     391                 :             :                  ";; Unable to prove that the loop iterates constant times\n");
     392                 :       36954 :       return;
     393                 :             :     }
     394                 :             : 
     395                 :             :   /* Check for an explicit unrolling factor.  */
     396                 :       30465 :   if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
     397                 :             :     {
     398                 :             :       /* However we cannot unroll completely at the RTL level a loop with
     399                 :             :          constant number of iterations; it should have been peeled instead.  */
     400                 :         288 :       if (desc->niter == 0 || (unsigned) loop->unroll > desc->niter - 1)
     401                 :             :         {
     402                 :          17 :           if (dump_file)
     403                 :           9 :             fprintf (dump_file, ";; Loop should have been peeled\n");
     404                 :             :         }
     405                 :             :       else
     406                 :             :         {
     407                 :         271 :           loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
     408                 :         271 :           loop->lpt_decision.times = loop->unroll - 1;
     409                 :             :         }
     410                 :         288 :       return;
     411                 :             :     }
     412                 :             : 
     413                 :             :   /* Check whether the loop rolls enough to consider.
     414                 :             :      Consult also loop bounds and profile; in the case the loop has more
     415                 :             :      than one exit it may well loop less than determined maximal number
     416                 :             :      of iterations.  */
     417                 :       30177 :   if (desc->niter < 2 * nunroll
     418                 :       30177 :       || ((get_estimated_loop_iterations (loop, &iterations)
     419                 :         547 :            || get_likely_max_loop_iterations (loop, &iterations))
     420                 :       28320 :           && wi::ltu_p (iterations, 2 * nunroll)))
     421                 :             :     {
     422                 :        1859 :       if (dump_file)
     423                 :           1 :         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
     424                 :        1859 :       return;
     425                 :             :     }
     426                 :             : 
     427                 :             :   /* Success; now compute number of iterations to unroll.  We alter
     428                 :             :      nunroll so that as few as possible copies of loop body are
     429                 :             :      necessary, while still not decreasing the number of unrollings
     430                 :             :      too much (at most by 1).  */
     431                 :       28318 :   best_copies = 2 * nunroll + 10;
     432                 :             : 
     433                 :       28318 :   i = 2 * nunroll + 2;
     434                 :       28318 :   if (i > desc->niter - 2)
     435                 :         473 :     i = desc->niter - 2;
     436                 :             : 
     437                 :      207095 :   for (; i >= nunroll - 1; i--)
     438                 :             :     {
     439                 :      178777 :       unsigned exit_mod = desc->niter % (i + 1);
     440                 :             : 
     441                 :      178777 :       if (!loop_exit_at_end_p (loop))
     442                 :         762 :         n_copies = exit_mod + i + 1;
     443                 :      178015 :       else if (exit_mod != (unsigned) i
     444                 :       70439 :                || desc->noloop_assumptions != NULL_RTX)
     445                 :      107576 :         n_copies = exit_mod + i + 2;
     446                 :             :       else
     447                 :             :         n_copies = i + 1;
     448                 :             : 
     449                 :      178777 :       if (n_copies < best_copies)
     450                 :             :         {
     451                 :      135699 :           best_copies = n_copies;
     452                 :      135699 :           best_unroll = i;
     453                 :             :         }
     454                 :             :     }
     455                 :             : 
     456                 :       28318 :   loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
     457                 :       28318 :   loop->lpt_decision.times = best_unroll;
     458                 :      376190 : }
     459                 :             : 
     460                 :             : /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
     461                 :             :    The transformation does this:
     462                 :             : 
     463                 :             :    for (i = 0; i < 102; i++)
     464                 :             :      body;
     465                 :             : 
     466                 :             :    ==>  (LOOP->LPT_DECISION.TIMES == 3)
     467                 :             : 
     468                 :             :    i = 0;
     469                 :             :    body; i++;
     470                 :             :    body; i++;
     471                 :             :    while (i < 102)
     472                 :             :      {
     473                 :             :        body; i++;
     474                 :             :        body; i++;
     475                 :             :        body; i++;
     476                 :             :        body; i++;
     477                 :             :      }
     478                 :             :   */
     479                 :             : static void
     480                 :       28589 : unroll_loop_constant_iterations (class loop *loop)
     481                 :             : {
     482                 :       28589 :   unsigned HOST_WIDE_INT niter;
     483                 :       28589 :   unsigned exit_mod;
     484                 :       28589 :   unsigned i;
     485                 :       28589 :   edge e;
     486                 :       28589 :   unsigned max_unroll = loop->lpt_decision.times;
     487                 :       28589 :   class niter_desc *desc = get_simple_loop_desc (loop);
     488                 :       28589 :   bool exit_at_end = loop_exit_at_end_p (loop);
     489                 :       28589 :   struct opt_info *opt_info = NULL;
     490                 :       28589 :   bool ok;
     491                 :       28589 :   bool flat = maybe_flat_loop_profile (loop);
     492                 :       28589 :   profile_count orig_exit_count = desc->out_edge->count ();
     493                 :             : 
     494                 :       28589 :   niter = desc->niter;
     495                 :             : 
     496                 :             :   /* Should not get here (such loop should be peeled instead).  */
     497                 :       28589 :   gcc_assert (niter > max_unroll + 1);
     498                 :             : 
     499                 :       28589 :   exit_mod = niter % (max_unroll + 1);
     500                 :             : 
     501                 :       28589 :   auto_sbitmap wont_exit (max_unroll + 2);
     502                 :       28589 :   bitmap_ones (wont_exit);
     503                 :             : 
     504                 :       28589 :   auto_vec<edge> remove_edges;
     505                 :       28589 :   if (flag_split_ivs_in_unroller
     506                 :           0 :       || flag_variable_expansion_in_unroller)
     507                 :       28589 :     opt_info = analyze_insns_in_loop (loop);
     508                 :             : 
     509                 :       28589 :   if (!exit_at_end)
     510                 :             :     {
     511                 :             :       /* The exit is not at the end of the loop; leave exit test
     512                 :             :          in the first copy, so that the loops that start with test
     513                 :             :          of exit condition have continuous body after unrolling.  */
     514                 :             : 
     515                 :          84 :       if (dump_file)
     516                 :           0 :         fprintf (dump_file, ";; Condition at beginning of loop.\n");
     517                 :             : 
     518                 :             :       /* Peel exit_mod iterations.  */
     519                 :          84 :       bitmap_clear_bit (wont_exit, 0);
     520                 :          84 :       if (desc->noloop_assumptions)
     521                 :           0 :         bitmap_clear_bit (wont_exit, 1);
     522                 :             : 
     523                 :          84 :       if (exit_mod)
     524                 :             :         {
     525                 :          90 :           opt_info_start_duplication (opt_info);
     526                 :          30 :           ok = duplicate_loop_body_to_header_edge (
     527                 :             :             loop, loop_preheader_edge (loop), exit_mod, wont_exit,
     528                 :             :             desc->out_edge, &remove_edges,
     529                 :             :             DLTHE_FLAG_UPDATE_FREQ
     530                 :          30 :               | (opt_info && exit_mod > 1 ? DLTHE_RECORD_COPY_NUMBER : 0));
     531                 :          30 :           gcc_assert (ok);
     532                 :             : 
     533                 :          30 :           if (opt_info && exit_mod > 1)
     534                 :          16 :             apply_opt_in_copies (opt_info, exit_mod, false, false);
     535                 :             : 
     536                 :          30 :           desc->noloop_assumptions = NULL_RTX;
     537                 :          30 :           desc->niter -= exit_mod;
     538                 :          30 :           loop->nb_iterations_upper_bound -= exit_mod;
     539                 :          30 :           if (loop->any_estimate
     540                 :          30 :               && wi::leu_p (exit_mod, loop->nb_iterations_estimate))
     541                 :          18 :             loop->nb_iterations_estimate -= exit_mod;
     542                 :             :           else
     543                 :          12 :             loop->any_estimate = false;
     544                 :          30 :           if (loop->any_likely_upper_bound
     545                 :          30 :               && wi::leu_p (exit_mod, loop->nb_iterations_likely_upper_bound))
     546                 :          30 :             loop->nb_iterations_likely_upper_bound -= exit_mod;
     547                 :             :           else
     548                 :           0 :             loop->any_likely_upper_bound = false;
     549                 :             :         }
     550                 :             : 
     551                 :          84 :       bitmap_set_bit (wont_exit, 1);
     552                 :             :     }
     553                 :             :   else
     554                 :             :     {
     555                 :             :       /* Leave exit test in last copy, for the same reason as above if
     556                 :             :          the loop tests the condition at the end of loop body.  */
     557                 :             : 
     558                 :       28505 :       if (dump_file)
     559                 :          33 :         fprintf (dump_file, ";; Condition at end of loop.\n");
     560                 :             : 
     561                 :             :       /* We know that niter >= max_unroll + 2; so we do not need to care of
     562                 :             :          case when we would exit before reaching the loop.  So just peel
     563                 :             :          exit_mod + 1 iterations.  */
     564                 :       28505 :       if (exit_mod != max_unroll
     565                 :       26955 :           || desc->noloop_assumptions)
     566                 :             :         {
     567                 :        1550 :           bitmap_clear_bit (wont_exit, 0);
     568                 :        1550 :           if (desc->noloop_assumptions)
     569                 :           0 :             bitmap_clear_bit (wont_exit, 1);
     570                 :             : 
     571                 :        4650 :           opt_info_start_duplication (opt_info);
     572                 :        1550 :           ok = duplicate_loop_body_to_header_edge (
     573                 :             :             loop, loop_preheader_edge (loop), exit_mod + 1, wont_exit,
     574                 :             :             desc->out_edge, &remove_edges,
     575                 :             :             DLTHE_FLAG_UPDATE_FREQ
     576                 :        1550 :               | (opt_info && exit_mod > 0 ? DLTHE_RECORD_COPY_NUMBER : 0));
     577                 :        1550 :           gcc_assert (ok);
     578                 :             : 
     579                 :        1550 :           if (opt_info && exit_mod > 0)
     580                 :         461 :             apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
     581                 :             : 
     582                 :        1550 :           desc->niter -= exit_mod + 1;
     583                 :        1550 :           loop->nb_iterations_upper_bound -= exit_mod + 1;
     584                 :        1550 :           if (loop->any_estimate
     585                 :        1550 :               && wi::leu_p (exit_mod + 1, loop->nb_iterations_estimate))
     586                 :        1066 :             loop->nb_iterations_estimate -= exit_mod + 1;
     587                 :             :           else
     588                 :         484 :             loop->any_estimate = false;
     589                 :        1550 :           if (loop->any_likely_upper_bound
     590                 :        1550 :               && wi::leu_p (exit_mod + 1, loop->nb_iterations_likely_upper_bound))
     591                 :        1550 :             loop->nb_iterations_likely_upper_bound -= exit_mod + 1;
     592                 :             :           else
     593                 :           0 :             loop->any_likely_upper_bound = false;
     594                 :        1550 :           desc->noloop_assumptions = NULL_RTX;
     595                 :             : 
     596                 :        1550 :           bitmap_set_bit (wont_exit, 0);
     597                 :        1550 :           bitmap_set_bit (wont_exit, 1);
     598                 :             :         }
     599                 :             : 
     600                 :       28505 :       bitmap_clear_bit (wont_exit, max_unroll);
     601                 :             :     }
     602                 :             : 
     603                 :             :   /* Now unroll the loop.  */
     604                 :             : 
     605                 :       85767 :   opt_info_start_duplication (opt_info);
     606                 :       28589 :   ok = duplicate_loop_body_to_header_edge (
     607                 :             :     loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge,
     608                 :             :     &remove_edges,
     609                 :             :     DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0)
     610                 :       28589 :     | (flat ? DLTHE_FLAG_FLAT_PROFILE : 0));
     611                 :       28589 :   gcc_assert (ok);
     612                 :             : 
     613                 :       28589 :   edge exit = update_loop_exit_probability_scale_dom_bbs
     614                 :       28589 :           (loop, desc->out_edge, orig_exit_count);
     615                 :       28589 :   if (exit)
     616                 :       28583 :     update_br_prob_note (exit->src);
     617                 :             : 
     618                 :       28589 :   if (opt_info)
     619                 :             :     {
     620                 :       28589 :       apply_opt_in_copies (opt_info, max_unroll, true, true);
     621                 :       28589 :       free_opt_info (opt_info);
     622                 :             :     }
     623                 :             : 
     624                 :       28589 :   if (exit_at_end)
     625                 :             :     {
     626                 :       28505 :       basic_block exit_block = get_bb_copy (desc->in_edge->src);
     627                 :             :       /* Find a new in and out edge; they are in the last copy we have made.  */
     628                 :             : 
     629                 :       28505 :       if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
     630                 :             :         {
     631                 :        1388 :           desc->out_edge = EDGE_SUCC (exit_block, 0);
     632                 :        1388 :           desc->in_edge = EDGE_SUCC (exit_block, 1);
     633                 :             :         }
     634                 :             :       else
     635                 :             :         {
     636                 :       27117 :           desc->out_edge = EDGE_SUCC (exit_block, 1);
     637                 :       27117 :           desc->in_edge = EDGE_SUCC (exit_block, 0);
     638                 :             :         }
     639                 :             :     }
     640                 :             : 
     641                 :       28589 :   desc->niter /= max_unroll + 1;
     642                 :       28589 :   loop->nb_iterations_upper_bound
     643                 :       28589 :     = wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
     644                 :       28589 :   if (loop->any_estimate)
     645                 :       27823 :     loop->nb_iterations_estimate
     646                 :       27823 :       = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
     647                 :       28589 :   if (loop->any_likely_upper_bound)
     648                 :       28589 :     loop->nb_iterations_likely_upper_bound
     649                 :       28589 :       = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1);
     650                 :       28589 :   desc->niter_expr = gen_int_mode (desc->niter, desc->mode);
     651                 :             : 
     652                 :             :   /* Remove the edges.  */
     653                 :       71920 :   FOR_EACH_VEC_ELT (remove_edges, i, e)
     654                 :       43331 :     remove_path (e);
     655                 :             : 
     656                 :       28589 :   if (dump_file)
     657                 :          33 :     fprintf (dump_file,
     658                 :             :              ";; Unrolled loop %d times, constant # of iterations %i insns\n",
     659                 :             :              max_unroll, num_loop_insns (loop));
     660                 :       28589 : }
     661                 :             : 
     662                 :             : /* Decide whether to unroll LOOP iterating runtime computable number of times
     663                 :             :    and how much.  */
     664                 :             : static void
     665                 :      347601 : decide_unroll_runtime_iterations (class loop *loop, int flags)
     666                 :             : {
     667                 :      347601 :   unsigned nunroll, nunroll_by_av, i;
     668                 :      347601 :   class niter_desc *desc;
     669                 :      347601 :   widest_int iterations;
     670                 :             : 
     671                 :             :   /* If we were not asked to unroll this loop, just return back silently.  */
     672                 :      347601 :   if (!(flags & UAP_UNROLL) && !loop->unroll)
     673                 :             :     return;
     674                 :             : 
     675                 :      347524 :   if (dump_enabled_p ())
     676                 :         366 :     dump_printf (MSG_NOTE,
     677                 :             :                  "considering unrolling loop with runtime-"
     678                 :             :                  "computable number of iterations\n");
     679                 :             : 
     680                 :             :   /* nunroll = total number of copies of the original loop body in
     681                 :             :      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
     682                 :      347524 :   nunroll = param_max_unrolled_insns / loop->ninsns;
     683                 :      347524 :   nunroll_by_av = param_max_average_unrolled_insns / loop->av_ninsns;
     684                 :      347524 :   if (nunroll > nunroll_by_av)
     685                 :             :     nunroll = nunroll_by_av;
     686                 :      347524 :   if (nunroll > (unsigned) param_max_unroll_times)
     687                 :             :     nunroll = param_max_unroll_times;
     688                 :             : 
     689                 :      347524 :   if (targetm.loop_unroll_adjust)
     690                 :      347524 :     nunroll = targetm.loop_unroll_adjust (nunroll, loop);
     691                 :             : 
     692                 :      347524 :   if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
     693                 :         698 :     nunroll = loop->unroll;
     694                 :             : 
     695                 :             :   /* Skip big loops.  */
     696                 :      347524 :   if (nunroll <= 1)
     697                 :             :     {
     698                 :      308694 :       if (dump_file)
     699                 :           8 :         fprintf (dump_file, ";; Not considering loop, is too big\n");
     700                 :      308694 :       return;
     701                 :             :     }
     702                 :             : 
     703                 :             :   /* Check for simple loops.  */
     704                 :       38830 :   desc = get_simple_loop_desc (loop);
     705                 :             : 
     706                 :             :   /* Check simpleness.  */
     707                 :       38830 :   if (!desc->simple_p || desc->assumptions)
     708                 :             :     {
     709                 :       16464 :       if (dump_file)
     710                 :          24 :         fprintf (dump_file,
     711                 :             :                  ";; Unable to prove that the number of iterations "
     712                 :             :                  "can be counted in runtime\n");
     713                 :       16464 :       return;
     714                 :             :     }
     715                 :             : 
     716                 :       22366 :   if (desc->const_iter)
     717                 :             :     {
     718                 :        1876 :       if (dump_file)
     719                 :          10 :         fprintf (dump_file, ";; Loop iterates constant times\n");
     720                 :        1876 :       return;
     721                 :             :     }
     722                 :             : 
     723                 :             :   /* Check whether the loop rolls.  */
     724                 :       20490 :   if ((get_estimated_loop_iterations (loop, &iterations)
     725                 :       19296 :        || get_likely_max_loop_iterations (loop, &iterations))
     726                 :       39786 :       && wi::ltu_p (iterations, 2 * nunroll))
     727                 :             :     {
     728                 :        1173 :       if (dump_file)
     729                 :           1 :         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
     730                 :        1173 :       return;
     731                 :             :     }
     732                 :             : 
     733                 :             :   /* Success; now force nunroll to be power of 2, as code-gen
     734                 :             :      requires it, we are unable to cope with overflows in
     735                 :             :      computation of number of iterations.  */
     736                 :       53180 :   for (i = 1; 2 * i <= nunroll; i *= 2)
     737                 :       33863 :     continue;
     738                 :             : 
     739                 :       19317 :   loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
     740                 :       19317 :   loop->lpt_decision.times = i - 1;
     741                 :      347601 : }
     742                 :             : 
     743                 :             : /* Splits edge E and inserts the sequence of instructions INSNS on it, and
     744                 :             :    returns the newly created block.  If INSNS is NULL_RTX, nothing is changed
     745                 :             :    and NULL is returned instead.  */
     746                 :             : 
     747                 :             : basic_block
     748                 :       76896 : split_edge_and_insert (edge e, rtx_insn *insns)
     749                 :             : {
     750                 :       76896 :   basic_block bb;
     751                 :             : 
     752                 :       76896 :   if (!insns)
     753                 :             :     return NULL;
     754                 :       76896 :   bb = split_edge (e);
     755                 :       76896 :   emit_insn_after (insns, BB_END (bb));
     756                 :             : 
     757                 :             :   /* ??? We used to assume that INSNS can contain control flow insns, and
     758                 :             :      that we had to try to find sub basic blocks in BB to maintain a valid
     759                 :             :      CFG.  For this purpose we used to set the BB_SUPERBLOCK flag on BB
     760                 :             :      and call break_superblocks when going out of cfglayout mode.  But it
     761                 :             :      turns out that this never happens; and that if it does ever happen,
     762                 :             :      the verify_flow_info at the end of the RTL loop passes would fail.
     763                 :             : 
     764                 :             :      There are two reasons why we expected we could have control flow insns
     765                 :             :      in INSNS.  The first is when a comparison has to be done in parts, and
     766                 :             :      the second is when the number of iterations is computed for loops with
     767                 :             :      the number of iterations known at runtime.  In both cases, test cases
     768                 :             :      to get control flow in INSNS appear to be impossible to construct:
     769                 :             : 
     770                 :             :       * If do_compare_rtx_and_jump needs several branches to do comparison
     771                 :             :         in a mode that needs comparison by parts, we cannot analyze the
     772                 :             :         number of iterations of the loop, and we never get to unrolling it.
     773                 :             : 
     774                 :             :       * The code in expand_divmod that was suspected to cause creation of
     775                 :             :         branching code seems to be only accessed for signed division.  The
     776                 :             :         divisions used by # of iterations analysis are always unsigned.
     777                 :             :         Problems might arise on architectures that emits branching code
     778                 :             :         for some operations that may appear in the unroller (especially
     779                 :             :         for division), but we have no such architectures.
     780                 :             : 
     781                 :             :      Considering all this, it was decided that we should for now assume
     782                 :             :      that INSNS can in theory contain control flow insns, but in practice
     783                 :             :      it never does.  So we don't handle the theoretical case, and should
     784                 :             :      a real failure ever show up, we have a pretty good clue for how to
     785                 :             :      fix it.  */
     786                 :             : 
     787                 :       76896 :   return bb;
     788                 :             : }
     789                 :             : 
     790                 :             : /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
     791                 :             :    true, with probability PROB.  If CINSN is not NULL, it is the insn to copy
     792                 :             :    in order to create a jump.  */
     793                 :             : 
     794                 :             : static rtx_insn *
     795                 :       57579 : compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp,
     796                 :             :                       rtx_code_label *label, profile_probability prob,
     797                 :             :                       rtx_insn *cinsn)
     798                 :             : {
     799                 :       57579 :   rtx_insn *seq;
     800                 :       57579 :   rtx_jump_insn *jump;
     801                 :       57579 :   rtx cond;
     802                 :       57579 :   machine_mode mode;
     803                 :             : 
     804                 :       57579 :   mode = GET_MODE (op0);
     805                 :       57579 :   if (mode == VOIDmode)
     806                 :           0 :     mode = GET_MODE (op1);
     807                 :             : 
     808                 :       57579 :   start_sequence ();
     809                 :       57579 :   if (GET_MODE_CLASS (mode) == MODE_CC)
     810                 :             :     {
     811                 :             :       /* A hack -- there seems to be no easy generic way how to make a
     812                 :             :          conditional jump from a ccmode comparison.  */
     813                 :           0 :       gcc_assert (cinsn);
     814                 :           0 :       cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
     815                 :           0 :       gcc_assert (GET_CODE (cond) == comp);
     816                 :           0 :       gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
     817                 :           0 :       gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
     818                 :           0 :       emit_jump_insn (copy_insn (PATTERN (cinsn)));
     819                 :           0 :       jump = as_a <rtx_jump_insn *> (get_last_insn ());
     820                 :           0 :       JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
     821                 :           0 :       LABEL_NUSES (JUMP_LABEL (jump))++;
     822                 :           0 :       redirect_jump (jump, label, 0);
     823                 :             :     }
     824                 :             :   else
     825                 :             :     {
     826                 :       57579 :       gcc_assert (!cinsn);
     827                 :             : 
     828                 :       57579 :       op0 = force_operand (op0, NULL_RTX);
     829                 :       57579 :       op1 = force_operand (op1, NULL_RTX);
     830                 :       57579 :       do_compare_rtx_and_jump (op0, op1, comp, 0,
     831                 :             :                                mode, NULL_RTX, NULL, label,
     832                 :             :                                profile_probability::uninitialized ());
     833                 :       57579 :       jump = as_a <rtx_jump_insn *> (get_last_insn ());
     834                 :       57579 :       jump->set_jump_target (label);
     835                 :       57579 :       LABEL_NUSES (label)++;
     836                 :             :     }
     837                 :       57579 :   if (prob.initialized_p ())
     838                 :       57579 :     add_reg_br_prob_note (jump, prob);
     839                 :             : 
     840                 :       57579 :   seq = get_insns ();
     841                 :       57579 :   end_sequence ();
     842                 :             : 
     843                 :       57579 :   return seq;
     844                 :             : }
     845                 :             : 
     846                 :             : /* Unroll LOOP for which we are able to count number of iterations in
     847                 :             :    runtime LOOP->LPT_DECISION.TIMES times.  The times value must be a
     848                 :             :    power of two.  The transformation does this (with some extra care
     849                 :             :    for case n < 0):
     850                 :             : 
     851                 :             :    for (i = 0; i < n; i++)
     852                 :             :      body;
     853                 :             : 
     854                 :             :    ==>  (LOOP->LPT_DECISION.TIMES == 3)
     855                 :             : 
     856                 :             :    i = 0;
     857                 :             :    mod = n % 4;
     858                 :             : 
     859                 :             :    switch (mod)
     860                 :             :      {
     861                 :             :        case 3:
     862                 :             :          body; i++;
     863                 :             :        case 2:
     864                 :             :          body; i++;
     865                 :             :        case 1:
     866                 :             :          body; i++;
     867                 :             :        case 0: ;
     868                 :             :      }
     869                 :             : 
     870                 :             :    while (i < n)
     871                 :             :      {
     872                 :             :        body; i++;
     873                 :             :        body; i++;
     874                 :             :        body; i++;
     875                 :             :        body; i++;
     876                 :             :      }
     877                 :             :    */
     878                 :             : static void
     879                 :       19317 : unroll_loop_runtime_iterations (class loop *loop)
     880                 :             : {
     881                 :       19317 :   rtx old_niter, niter, tmp;
     882                 :       19317 :   rtx_insn *init_code, *branch_code;
     883                 :       19317 :   unsigned i;
     884                 :       19317 :   profile_probability p;
     885                 :       19317 :   basic_block preheader, *body, swtch, ezc_swtch = NULL;
     886                 :       19317 :   int may_exit_copy;
     887                 :       19317 :   profile_count iter_count, new_count;
     888                 :       19317 :   unsigned n_peel;
     889                 :       19317 :   edge e;
     890                 :       19317 :   bool extra_zero_check, last_may_exit;
     891                 :       19317 :   unsigned max_unroll = loop->lpt_decision.times;
     892                 :       19317 :   class niter_desc *desc = get_simple_loop_desc (loop);
     893                 :       19317 :   bool exit_at_end = loop_exit_at_end_p (loop);
     894                 :       19317 :   struct opt_info *opt_info = NULL;
     895                 :       19317 :   bool ok;
     896                 :             : 
     897                 :       19317 :   if (flag_split_ivs_in_unroller
     898                 :           0 :       || flag_variable_expansion_in_unroller)
     899                 :       19317 :     opt_info = analyze_insns_in_loop (loop);
     900                 :             : 
     901                 :             :   /* Remember blocks whose dominators will have to be updated.  */
     902                 :       19317 :   auto_vec<basic_block> dom_bbs;
     903                 :             : 
     904                 :       19317 :   body = get_loop_body (loop);
     905                 :       64494 :   for (i = 0; i < loop->num_nodes; i++)
     906                 :             :     {
     907                 :      142191 :       for (basic_block bb : get_dominated_by (CDI_DOMINATORS, body[i]))
     908                 :       46808 :         if (!flow_bb_inside_loop_p (loop, bb))
     909                 :       66125 :           dom_bbs.safe_push (bb);
     910                 :             :     }
     911                 :       19317 :   free (body);
     912                 :             : 
     913                 :       19317 :   if (!exit_at_end)
     914                 :             :     {
     915                 :             :       /* Leave exit in first copy (for explanation why see comment in
     916                 :             :          unroll_loop_constant_iterations).  */
     917                 :         675 :       may_exit_copy = 0;
     918                 :         675 :       n_peel = max_unroll - 1;
     919                 :         675 :       extra_zero_check = true;
     920                 :         675 :       last_may_exit = false;
     921                 :             :     }
     922                 :             :   else
     923                 :             :     {
     924                 :             :       /* Leave exit in last copy (for explanation why see comment in
     925                 :             :          unroll_loop_constant_iterations).  */
     926                 :       18642 :       may_exit_copy = max_unroll;
     927                 :       18642 :       n_peel = max_unroll;
     928                 :       18642 :       extra_zero_check = false;
     929                 :       18642 :       last_may_exit = true;
     930                 :             :     }
     931                 :             : 
     932                 :             :   /* Get expression for number of iterations.  */
     933                 :       19317 :   start_sequence ();
     934                 :       19317 :   old_niter = niter = gen_reg_rtx (desc->mode);
     935                 :       19317 :   tmp = force_operand (copy_rtx (desc->niter_expr), niter);
     936                 :       19317 :   if (tmp != niter)
     937                 :         443 :     emit_move_insn (niter, tmp);
     938                 :             : 
     939                 :             :   /* For loops that exit at end and whose number of iterations is reliable,
     940                 :             :      add one to niter to account for first pass through loop body before
     941                 :             :      reaching exit test. */
     942                 :       19317 :   if (exit_at_end && !desc->noloop_assumptions)
     943                 :             :     {
     944                 :       12887 :       niter = expand_simple_binop (desc->mode, PLUS,
     945                 :             :                                    niter, const1_rtx,
     946                 :             :                                    NULL_RTX, 0, OPTAB_LIB_WIDEN);
     947                 :       12887 :       old_niter = niter;
     948                 :             :     }
     949                 :             : 
     950                 :             :   /* Count modulo by ANDing it with max_unroll; we use the fact that
     951                 :             :      the number of unrollings is a power of two, and thus this is correct
     952                 :             :      even if there is overflow in the computation.  */
     953                 :       19317 :   niter = expand_simple_binop (desc->mode, AND,
     954                 :       19317 :                                niter, gen_int_mode (max_unroll, desc->mode),
     955                 :             :                                NULL_RTX, 0, OPTAB_LIB_WIDEN);
     956                 :             : 
     957                 :       19317 :   init_code = get_insns ();
     958                 :       19317 :   end_sequence ();
     959                 :       19317 :   unshare_all_rtl_in_chain (init_code);
     960                 :             : 
     961                 :             :   /* Precondition the loop.  */
     962                 :       19317 :   split_edge_and_insert (loop_preheader_edge (loop), init_code);
     963                 :             : 
     964                 :       19317 :   auto_vec<edge> remove_edges;
     965                 :             : 
     966                 :       19317 :   auto_sbitmap wont_exit (max_unroll + 2);
     967                 :             : 
     968                 :       19317 :   if (extra_zero_check || desc->noloop_assumptions)
     969                 :             :     {
     970                 :             :       /* Peel the first copy of loop body.  Leave the exit test if the number
     971                 :             :          of iterations is not reliable.  Also record the place of the extra zero
     972                 :             :          check.  */
     973                 :        6430 :       bitmap_clear (wont_exit);
     974                 :        6430 :       if (!desc->noloop_assumptions)
     975                 :         509 :         bitmap_set_bit (wont_exit, 1);
     976                 :        6430 :       ezc_swtch = loop_preheader_edge (loop)->src;
     977                 :        6430 :       ok = duplicate_loop_body_to_header_edge (loop, loop_preheader_edge (loop),
     978                 :             :                                                1, wont_exit, desc->out_edge,
     979                 :             :                                                &remove_edges,
     980                 :             :                                                DLTHE_FLAG_UPDATE_FREQ);
     981                 :        6430 :       gcc_assert (ok);
     982                 :             :     }
     983                 :             : 
     984                 :             :   /* Record the place where switch will be built for preconditioning.  */
     985                 :       19317 :   swtch = split_edge (loop_preheader_edge (loop));
     986                 :             : 
     987                 :             :   /* Compute count increments for each switch block and initialize
     988                 :             :      innermost switch block.  Switch blocks and peeled loop copies are built
     989                 :             :      from innermost outward.  */
     990                 :       19317 :   iter_count = new_count = swtch->count / (max_unroll + 1);
     991                 :       19317 :   swtch->count = new_count;
     992                 :             : 
     993                 :       76221 :   for (i = 0; i < n_peel; i++)
     994                 :             :     {
     995                 :             :       /* Peel the copy.  */
     996                 :       56904 :       bitmap_clear (wont_exit);
     997                 :       56904 :       if (i != n_peel - 1 || !last_may_exit)
     998                 :       38262 :         bitmap_set_bit (wont_exit, 1);
     999                 :       56904 :       ok = duplicate_loop_body_to_header_edge (loop, loop_preheader_edge (loop),
    1000                 :             :                                                1, wont_exit, desc->out_edge,
    1001                 :             :                                                &remove_edges,
    1002                 :             :                                                DLTHE_FLAG_UPDATE_FREQ);
    1003                 :       56904 :       gcc_assert (ok);
    1004                 :             : 
    1005                 :             :       /* Create item for switch.  */
    1006                 :       56904 :       unsigned j = n_peel - i - (extra_zero_check ? 0 : 1);
    1007                 :       56904 :       p = profile_probability::always () / (i + 2);
    1008                 :             : 
    1009                 :       56904 :       preheader = split_edge (loop_preheader_edge (loop));
    1010                 :             :       /* Add in count of edge from switch block.  */
    1011                 :       56904 :       preheader->count += iter_count;
    1012                 :       56904 :       branch_code = compare_and_jump_seq (copy_rtx (niter),
    1013                 :       56904 :                                           gen_int_mode (j, desc->mode), EQ,
    1014                 :             :                                           block_label (preheader), p, NULL);
    1015                 :             : 
    1016                 :             :       /* We rely on the fact that the compare and jump cannot be optimized out,
    1017                 :             :          and hence the cfg we create is correct.  */
    1018                 :       56904 :       gcc_assert (branch_code != NULL_RTX);
    1019                 :             : 
    1020                 :       56904 :       swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
    1021                 :       56904 :       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
    1022                 :       56904 :       single_succ_edge (swtch)->probability = p.invert ();
    1023                 :       56904 :       new_count += iter_count;
    1024                 :       56904 :       swtch->count = new_count;
    1025                 :      170712 :       e = make_edge (swtch, preheader,
    1026                 :       56904 :                      single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
    1027                 :       56904 :       e->probability = p;
    1028                 :             :     }
    1029                 :             : 
    1030                 :       19317 :   if (extra_zero_check)
    1031                 :             :     {
    1032                 :             :       /* Add branch for zero iterations.  */
    1033                 :         675 :       p = profile_probability::always () / (max_unroll + 1);
    1034                 :         675 :       swtch = ezc_swtch;
    1035                 :         675 :       preheader = split_edge (loop_preheader_edge (loop));
    1036                 :             :       /* Recompute count adjustments since initial peel copy may
    1037                 :             :          have exited and reduced those values that were computed above.  */
    1038                 :         675 :       iter_count = swtch->count / (max_unroll + 1);
    1039                 :             :       /* Add in count of edge from switch block.  */
    1040                 :         675 :       preheader->count += iter_count;
    1041                 :         675 :       branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
    1042                 :             :                                           block_label (preheader), p,
    1043                 :             :                                           NULL);
    1044                 :         675 :       gcc_assert (branch_code != NULL_RTX);
    1045                 :             : 
    1046                 :         675 :       swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
    1047                 :         675 :       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
    1048                 :         675 :       single_succ_edge (swtch)->probability = p.invert ();
    1049                 :        2025 :       e = make_edge (swtch, preheader,
    1050                 :         675 :                      single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
    1051                 :         675 :       e->probability = p;
    1052                 :             :     }
    1053                 :             : 
    1054                 :             :   /* Recount dominators for outer blocks.  */
    1055                 :       19317 :   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
    1056                 :             : 
    1057                 :             :   /* And unroll loop.  */
    1058                 :             : 
    1059                 :       19317 :   bitmap_ones (wont_exit);
    1060                 :       19317 :   bitmap_clear_bit (wont_exit, may_exit_copy);
    1061                 :       57951 :   opt_info_start_duplication (opt_info);
    1062                 :             : 
    1063                 :       19317 :   ok = duplicate_loop_body_to_header_edge (
    1064                 :             :     loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge,
    1065                 :             :     &remove_edges,
    1066                 :             :     DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0));
    1067                 :       19317 :   gcc_assert (ok);
    1068                 :             : 
    1069                 :       19317 :   if (opt_info)
    1070                 :             :     {
    1071                 :       19317 :       apply_opt_in_copies (opt_info, max_unroll, true, true);
    1072                 :       19317 :       free_opt_info (opt_info);
    1073                 :             :     }
    1074                 :             : 
    1075                 :       19317 :   if (exit_at_end)
    1076                 :             :     {
    1077                 :       18642 :       basic_block exit_block = get_bb_copy (desc->in_edge->src);
    1078                 :             :       /* Find a new in and out edge; they are in the last copy we have
    1079                 :             :          made.  */
    1080                 :             : 
    1081                 :       18642 :       if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
    1082                 :             :         {
    1083                 :        3600 :           desc->out_edge = EDGE_SUCC (exit_block, 0);
    1084                 :        3600 :           desc->in_edge = EDGE_SUCC (exit_block, 1);
    1085                 :             :         }
    1086                 :             :       else
    1087                 :             :         {
    1088                 :       15042 :           desc->out_edge = EDGE_SUCC (exit_block, 1);
    1089                 :       15042 :           desc->in_edge = EDGE_SUCC (exit_block, 0);
    1090                 :             :         }
    1091                 :             :     }
    1092                 :             : 
    1093                 :             :   /* Remove the edges.  */
    1094                 :      115667 :   FOR_EACH_VEC_ELT (remove_edges, i, e)
    1095                 :       96350 :     remove_path (e);
    1096                 :             : 
    1097                 :             :   /* We must be careful when updating the number of iterations due to
    1098                 :             :      preconditioning and the fact that the value must be valid at entry
    1099                 :             :      of the loop.  After passing through the above code, we see that
    1100                 :             :      the correct new number of iterations is this:  */
    1101                 :       19317 :   gcc_assert (!desc->const_iter);
    1102                 :       38634 :   desc->niter_expr =
    1103                 :       19317 :     simplify_gen_binary (UDIV, desc->mode, old_niter,
    1104                 :       19317 :                          gen_int_mode (max_unroll + 1, desc->mode));
    1105                 :       19317 :   loop->nb_iterations_upper_bound
    1106                 :       19317 :     = wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
    1107                 :       19317 :   if (loop->any_estimate)
    1108                 :         672 :     loop->nb_iterations_estimate
    1109                 :         672 :       = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
    1110                 :       19317 :   if (loop->any_likely_upper_bound)
    1111                 :       18192 :     loop->nb_iterations_likely_upper_bound
    1112                 :       18192 :       = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1);
    1113                 :       19317 :   if (exit_at_end)
    1114                 :             :     {
    1115                 :       37284 :       desc->niter_expr =
    1116                 :       18642 :         simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
    1117                 :       18642 :       desc->noloop_assumptions = NULL_RTX;
    1118                 :       18642 :       --loop->nb_iterations_upper_bound;
    1119                 :       18642 :       if (loop->any_estimate
    1120                 :       18642 :           && loop->nb_iterations_estimate != 0)
    1121                 :         671 :         --loop->nb_iterations_estimate;
    1122                 :             :       else
    1123                 :       17971 :         loop->any_estimate = false;
    1124                 :       18642 :       if (loop->any_likely_upper_bound
    1125                 :       18642 :           && loop->nb_iterations_likely_upper_bound != 0)
    1126                 :       17549 :         --loop->nb_iterations_likely_upper_bound;
    1127                 :             :       else
    1128                 :        1093 :         loop->any_likely_upper_bound = false;
    1129                 :             :     }
    1130                 :             : 
    1131                 :       19317 :   if (dump_file)
    1132                 :          14 :     fprintf (dump_file,
    1133                 :             :              ";; Unrolled loop %d times, counting # of iterations "
    1134                 :             :              "in runtime, %i insns\n",
    1135                 :             :              max_unroll, num_loop_insns (loop));
    1136                 :       19317 : }
    1137                 :             : 
    1138                 :             : /* Decide whether to unroll LOOP stupidly and how much.  */
    1139                 :             : static void
    1140                 :      328284 : decide_unroll_stupid (class loop *loop, int flags)
    1141                 :             : {
    1142                 :      328284 :   unsigned nunroll, nunroll_by_av, i;
    1143                 :      328284 :   class niter_desc *desc;
    1144                 :      328284 :   widest_int iterations;
    1145                 :             : 
    1146                 :             :   /* If we were not asked to unroll this loop, just return back silently.  */
    1147                 :      328284 :   if (!(flags & UAP_UNROLL_ALL) && !loop->unroll)
    1148                 :             :     return;
    1149                 :             : 
    1150                 :         150 :   if (dump_enabled_p ())
    1151                 :          33 :     dump_printf (MSG_NOTE, "considering unrolling loop stupidly\n");
    1152                 :             : 
    1153                 :             :   /* nunroll = total number of copies of the original loop body in
    1154                 :             :      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
    1155                 :         150 :   nunroll = param_max_unrolled_insns / loop->ninsns;
    1156                 :         150 :   nunroll_by_av
    1157                 :         150 :     = param_max_average_unrolled_insns / loop->av_ninsns;
    1158                 :         150 :   if (nunroll > nunroll_by_av)
    1159                 :             :     nunroll = nunroll_by_av;
    1160                 :         150 :   if (nunroll > (unsigned) param_max_unroll_times)
    1161                 :             :     nunroll = param_max_unroll_times;
    1162                 :             : 
    1163                 :         150 :   if (targetm.loop_unroll_adjust)
    1164                 :         150 :     nunroll = targetm.loop_unroll_adjust (nunroll, loop);
    1165                 :             : 
    1166                 :         150 :   if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
    1167                 :         131 :     nunroll = loop->unroll;
    1168                 :             : 
    1169                 :             :   /* Skip big loops.  */
    1170                 :         150 :   if (nunroll <= 1)
    1171                 :             :     {
    1172                 :           1 :       if (dump_file)
    1173                 :           0 :         fprintf (dump_file, ";; Not considering loop, is too big\n");
    1174                 :           1 :       return;
    1175                 :             :     }
    1176                 :             : 
    1177                 :             :   /* Check for simple loops.  */
    1178                 :         149 :   desc = get_simple_loop_desc (loop);
    1179                 :             : 
    1180                 :             :   /* Check simpleness.  */
    1181                 :         149 :   if (desc->simple_p && !desc->assumptions)
    1182                 :             :     {
    1183                 :          27 :       if (dump_file)
    1184                 :           9 :         fprintf (dump_file, ";; Loop is simple\n");
    1185                 :          27 :       return;
    1186                 :             :     }
    1187                 :             : 
    1188                 :             :   /* Do not unroll loops with branches inside -- it increases number
    1189                 :             :      of mispredicts.
    1190                 :             :      TODO: this heuristic needs tunning; call inside the loop body
    1191                 :             :      is also relatively good reason to not unroll.  */
    1192                 :         122 :   if (num_loop_branches (loop) > 1)
    1193                 :             :     {
    1194                 :          18 :       if (dump_file)
    1195                 :           0 :         fprintf (dump_file, ";; Not unrolling, contains branches\n");
    1196                 :          18 :       return;
    1197                 :             :     }
    1198                 :             : 
    1199                 :             :   /* Check whether the loop rolls.  */
    1200                 :         104 :   if ((get_estimated_loop_iterations (loop, &iterations)
    1201                 :         104 :        || get_likely_max_loop_iterations (loop, &iterations))
    1202                 :         208 :       && wi::ltu_p (iterations, 2 * nunroll))
    1203                 :             :     {
    1204                 :           0 :       if (dump_file)
    1205                 :           0 :         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
    1206                 :           0 :       return;
    1207                 :             :     }
    1208                 :             : 
    1209                 :             :   /* Success.  Now force nunroll to be power of 2, as it seems that this
    1210                 :             :      improves results (partially because of better alignments, partially
    1211                 :             :      because of some dark magic).  */
    1212                 :         288 :   for (i = 1; 2 * i <= nunroll; i *= 2)
    1213                 :         184 :     continue;
    1214                 :             : 
    1215                 :         104 :   loop->lpt_decision.decision = LPT_UNROLL_STUPID;
    1216                 :         104 :   loop->lpt_decision.times = i - 1;
    1217                 :      328284 : }
    1218                 :             : 
    1219                 :             : /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times.  The transformation does this:
    1220                 :             : 
    1221                 :             :    while (cond)
    1222                 :             :      body;
    1223                 :             : 
    1224                 :             :    ==>  (LOOP->LPT_DECISION.TIMES == 3)
    1225                 :             : 
    1226                 :             :    while (cond)
    1227                 :             :      {
    1228                 :             :        body;
    1229                 :             :        if (!cond) break;
    1230                 :             :        body;
    1231                 :             :        if (!cond) break;
    1232                 :             :        body;
    1233                 :             :        if (!cond) break;
    1234                 :             :        body;
    1235                 :             :      }
    1236                 :             :    */
    1237                 :             : static void
    1238                 :         104 : unroll_loop_stupid (class loop *loop)
    1239                 :             : {
    1240                 :         104 :   unsigned nunroll = loop->lpt_decision.times;
    1241                 :         104 :   class niter_desc *desc = get_simple_loop_desc (loop);
    1242                 :         104 :   struct opt_info *opt_info = NULL;
    1243                 :         104 :   bool ok;
    1244                 :             : 
    1245                 :         104 :   if (flag_split_ivs_in_unroller
    1246                 :           0 :       || flag_variable_expansion_in_unroller)
    1247                 :         104 :     opt_info = analyze_insns_in_loop (loop);
    1248                 :             : 
    1249                 :         104 :   auto_sbitmap wont_exit (nunroll + 1);
    1250                 :         104 :   bitmap_clear (wont_exit);
    1251                 :         312 :   opt_info_start_duplication (opt_info);
    1252                 :             : 
    1253                 :         104 :   ok = duplicate_loop_body_to_header_edge (
    1254                 :             :     loop, loop_latch_edge (loop), nunroll, wont_exit, NULL, NULL,
    1255                 :             :     DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0));
    1256                 :         104 :   gcc_assert (ok);
    1257                 :             : 
    1258                 :         104 :   if (opt_info)
    1259                 :             :     {
    1260                 :         104 :       apply_opt_in_copies (opt_info, nunroll, true, true);
    1261                 :         104 :       free_opt_info (opt_info);
    1262                 :             :     }
    1263                 :             : 
    1264                 :         104 :   if (desc->simple_p)
    1265                 :             :     {
    1266                 :             :       /* We indeed may get here provided that there are nontrivial assumptions
    1267                 :             :          for a loop to be really simple.  We could update the counts, but the
    1268                 :             :          problem is that we are unable to decide which exit will be taken
    1269                 :             :          (not really true in case the number of iterations is constant,
    1270                 :             :          but no one will do anything with this information, so we do not
    1271                 :             :          worry about it).  */
    1272                 :           0 :       desc->simple_p = false;
    1273                 :             :     }
    1274                 :             : 
    1275                 :         104 :   if (dump_file)
    1276                 :          24 :     fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
    1277                 :             :              nunroll, num_loop_insns (loop));
    1278                 :         104 : }
    1279                 :             : 
    1280                 :             : /* Returns true if REG is referenced in one nondebug insn in LOOP.
    1281                 :             :    Set *DEBUG_USES to the number of debug insns that reference the
    1282                 :             :    variable.  */
    1283                 :             : 
    1284                 :             : static bool
    1285                 :           3 : referenced_in_one_insn_in_loop_p (class loop *loop, rtx reg,
    1286                 :             :                                   int *debug_uses)
    1287                 :             : {
    1288                 :           3 :   basic_block *body, bb;
    1289                 :           3 :   unsigned i;
    1290                 :           3 :   int count_ref = 0;
    1291                 :           3 :   rtx_insn *insn;
    1292                 :             : 
    1293                 :           3 :   body = get_loop_body (loop);
    1294                 :          12 :   for (i = 0; i < loop->num_nodes; i++)
    1295                 :             :     {
    1296                 :           6 :       bb = body[i];
    1297                 :             : 
    1298                 :          30 :       FOR_BB_INSNS (bb, insn)
    1299                 :          24 :         if (!rtx_referenced_p (reg, insn))
    1300                 :          21 :           continue;
    1301                 :           3 :         else if (DEBUG_INSN_P (insn))
    1302                 :           0 :           ++*debug_uses;
    1303                 :           3 :         else if (++count_ref > 1)
    1304                 :             :           break;
    1305                 :             :     }
    1306                 :           3 :   free (body);
    1307                 :           3 :   return (count_ref  == 1);
    1308                 :             : }
    1309                 :             : 
    1310                 :             : /* Reset the DEBUG_USES debug insns in LOOP that reference REG.  */
    1311                 :             : 
    1312                 :             : static void
    1313                 :           0 : reset_debug_uses_in_loop (class loop *loop, rtx reg, int debug_uses)
    1314                 :             : {
    1315                 :           0 :   basic_block *body, bb;
    1316                 :           0 :   unsigned i;
    1317                 :           0 :   rtx_insn *insn;
    1318                 :             : 
    1319                 :           0 :   body = get_loop_body (loop);
    1320                 :           0 :   for (i = 0; debug_uses && i < loop->num_nodes; i++)
    1321                 :             :     {
    1322                 :           0 :       bb = body[i];
    1323                 :             : 
    1324                 :           0 :       FOR_BB_INSNS (bb, insn)
    1325                 :           0 :         if (!DEBUG_INSN_P (insn) || !rtx_referenced_p (reg, insn))
    1326                 :           0 :           continue;
    1327                 :             :         else
    1328                 :             :           {
    1329                 :           0 :             validate_change (insn, &INSN_VAR_LOCATION_LOC (insn),
    1330                 :             :                              gen_rtx_UNKNOWN_VAR_LOC (), 0);
    1331                 :           0 :             if (!--debug_uses)
    1332                 :             :               break;
    1333                 :             :           }
    1334                 :             :     }
    1335                 :           0 :   free (body);
    1336                 :           0 : }
    1337                 :             : 
    1338                 :             : /* Determine whether INSN contains an accumulator
    1339                 :             :    which can be expanded into separate copies,
    1340                 :             :    one for each copy of the LOOP body.
    1341                 :             : 
    1342                 :             :    for (i = 0 ; i < n; i++)
    1343                 :             :      sum += a[i];
    1344                 :             : 
    1345                 :             :    ==>
    1346                 :             : 
    1347                 :             :    sum += a[i]
    1348                 :             :    ....
    1349                 :             :    i = i+1;
    1350                 :             :    sum1 += a[i]
    1351                 :             :    ....
    1352                 :             :    i = i+1
    1353                 :             :    sum2 += a[i];
    1354                 :             :    ....
    1355                 :             : 
    1356                 :             :    Return NULL if INSN contains no opportunity for expansion of accumulator.
    1357                 :             :    Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
    1358                 :             :    information and return a pointer to it.
    1359                 :             : */
    1360                 :             : 
    1361                 :             : static struct var_to_expand *
    1362                 :          33 : analyze_insn_to_expand_var (class loop *loop, rtx_insn *insn)
    1363                 :             : {
    1364                 :          33 :   rtx set, dest, src;
    1365                 :          33 :   struct var_to_expand *ves;
    1366                 :          33 :   unsigned accum_pos;
    1367                 :          33 :   enum rtx_code code;
    1368                 :          33 :   int debug_uses = 0;
    1369                 :             : 
    1370                 :          33 :   set = single_set (insn);
    1371                 :          33 :   if (!set)
    1372                 :             :     return NULL;
    1373                 :             : 
    1374                 :          22 :   dest = SET_DEST (set);
    1375                 :          22 :   src = SET_SRC (set);
    1376                 :          22 :   code = GET_CODE (src);
    1377                 :             : 
    1378                 :          22 :   if (code != PLUS && code != MINUS && code != MULT && code != FMA)
    1379                 :             :     return NULL;
    1380                 :             : 
    1381                 :           5 :   if (FLOAT_MODE_P (GET_MODE (dest)))
    1382                 :             :     {
    1383                 :           2 :       if (!flag_associative_math)
    1384                 :             :         return NULL;
    1385                 :             :       /* In the case of FMA, we're also changing the rounding.  */
    1386                 :           2 :       if (code == FMA && !flag_unsafe_math_optimizations)
    1387                 :             :         return NULL;
    1388                 :             :     }
    1389                 :             : 
    1390                 :             :   /* Hmm, this is a bit paradoxical.  We know that INSN is a valid insn
    1391                 :             :      in MD.  But if there is no optab to generate the insn, we cannot
    1392                 :             :      perform the variable expansion.  This can happen if an MD provides
    1393                 :             :      an insn but not a named pattern to generate it, for example to avoid
    1394                 :             :      producing code that needs additional mode switches like for x87/mmx.
    1395                 :             : 
    1396                 :             :      So we check have_insn_for which looks for an optab for the operation
    1397                 :             :      in SRC.  If it doesn't exist, we can't perform the expansion even
    1398                 :             :      though INSN is valid.  */
    1399                 :           5 :   if (!have_insn_for (code, GET_MODE (src)))
    1400                 :             :     return NULL;
    1401                 :             : 
    1402                 :           5 :   if (!REG_P (dest)
    1403                 :           0 :       && !(GET_CODE (dest) == SUBREG
    1404                 :           0 :            && REG_P (SUBREG_REG (dest))))
    1405                 :             :     return NULL;
    1406                 :             : 
    1407                 :             :   /* Find the accumulator use within the operation.  */
    1408                 :           5 :   if (code == FMA)
    1409                 :             :     {
    1410                 :             :       /* We only support accumulation via FMA in the ADD position.  */
    1411                 :           0 :       if (!rtx_equal_p  (dest, XEXP (src, 2)))
    1412                 :             :         return NULL;
    1413                 :             :       accum_pos = 2;
    1414                 :             :     }
    1415                 :           5 :   else if (rtx_equal_p (dest, XEXP (src, 0)))
    1416                 :             :     accum_pos = 0;
    1417                 :           2 :   else if (rtx_equal_p (dest, XEXP (src, 1)))
    1418                 :             :     {
    1419                 :             :       /* The method of expansion that we are using; which includes the
    1420                 :             :          initialization of the expansions with zero and the summation of
    1421                 :             :          the expansions at the end of the computation will yield wrong
    1422                 :             :          results for (x = something - x) thus avoid using it in that case.  */
    1423                 :           0 :       if (code == MINUS)
    1424                 :             :         return NULL;
    1425                 :             :       accum_pos = 1;
    1426                 :             :     }
    1427                 :             :   else
    1428                 :             :     return NULL;
    1429                 :             : 
    1430                 :             :   /* It must not otherwise be used.  */
    1431                 :           3 :   if (code == FMA)
    1432                 :             :     {
    1433                 :           0 :       if (rtx_referenced_p (dest, XEXP (src, 0))
    1434                 :           0 :           || rtx_referenced_p (dest, XEXP (src, 1)))
    1435                 :           0 :         return NULL;
    1436                 :             :     }
    1437                 :           3 :   else if (rtx_referenced_p (dest, XEXP (src, 1 - accum_pos)))
    1438                 :             :     return NULL;
    1439                 :             : 
    1440                 :             :   /* It must be used in exactly one insn.  */
    1441                 :           3 :   if (!referenced_in_one_insn_in_loop_p (loop, dest, &debug_uses))
    1442                 :             :     return NULL;
    1443                 :             : 
    1444                 :           3 :   if (dump_file)
    1445                 :             :     {
    1446                 :           1 :       fprintf (dump_file, "\n;; Expanding Accumulator ");
    1447                 :           1 :       print_rtl (dump_file, dest);
    1448                 :           1 :       fprintf (dump_file, "\n");
    1449                 :             :     }
    1450                 :             : 
    1451                 :           3 :   if (debug_uses)
    1452                 :             :     /* Instead of resetting the debug insns, we could replace each
    1453                 :             :        debug use in the loop with the sum or product of all expanded
    1454                 :             :        accumulators.  Since we'll only know of all expansions at the
    1455                 :             :        end, we'd have to keep track of which vars_to_expand a debug
    1456                 :             :        insn in the loop references, take note of each copy of the
    1457                 :             :        debug insn during unrolling, and when it's all done, compute
    1458                 :             :        the sum or product of each variable and adjust the original
    1459                 :             :        debug insn and each copy thereof.  What a pain!  */
    1460                 :           0 :     reset_debug_uses_in_loop (loop, dest, debug_uses);
    1461                 :             : 
    1462                 :             :   /* Record the accumulator to expand.  */
    1463                 :           3 :   ves = XNEW (struct var_to_expand);
    1464                 :           3 :   ves->insn = insn;
    1465                 :           3 :   ves->reg = copy_rtx (dest);
    1466                 :           3 :   ves->var_expansions.create (1);
    1467                 :           3 :   ves->next = NULL;
    1468                 :           3 :   ves->op = GET_CODE (src);
    1469                 :           3 :   ves->expansion_count = 0;
    1470                 :           3 :   ves->reuse_expansion = 0;
    1471                 :           3 :   return ves;
    1472                 :             : }
    1473                 :             : 
    1474                 :             : /* Determine whether there is an induction variable in INSN that
    1475                 :             :    we would like to split during unrolling.
    1476                 :             : 
    1477                 :             :    I.e. replace
    1478                 :             : 
    1479                 :             :    i = i + 1;
    1480                 :             :    ...
    1481                 :             :    i = i + 1;
    1482                 :             :    ...
    1483                 :             :    i = i + 1;
    1484                 :             :    ...
    1485                 :             : 
    1486                 :             :    type chains by
    1487                 :             : 
    1488                 :             :    i0 = i + 1
    1489                 :             :    ...
    1490                 :             :    i = i0 + 1
    1491                 :             :    ...
    1492                 :             :    i = i0 + 2
    1493                 :             :    ...
    1494                 :             : 
    1495                 :             :    Return NULL if INSN contains no interesting IVs.  Otherwise, allocate
    1496                 :             :    an IV_TO_SPLIT structure, fill it with the relevant information and return a
    1497                 :             :    pointer to it.  */
    1498                 :             : 
    1499                 :             : static struct iv_to_split *
    1500                 :      409407 : analyze_iv_to_split_insn (rtx_insn *insn)
    1501                 :             : {
    1502                 :      409407 :   rtx set, dest;
    1503                 :      409407 :   class rtx_iv iv;
    1504                 :      409407 :   struct iv_to_split *ivts;
    1505                 :      409407 :   scalar_int_mode mode;
    1506                 :      409407 :   bool ok;
    1507                 :             : 
    1508                 :             :   /* For now we just split the basic induction variables.  Later this may be
    1509                 :             :      extended for example by selecting also addresses of memory references.  */
    1510                 :      409407 :   set = single_set (insn);
    1511                 :      409407 :   if (!set)
    1512                 :             :     return NULL;
    1513                 :             : 
    1514                 :      266813 :   dest = SET_DEST (set);
    1515                 :      444805 :   if (!REG_P (dest) || !is_a <scalar_int_mode> (GET_MODE (dest), &mode))
    1516                 :             :     return NULL;
    1517                 :             : 
    1518                 :       85982 :   if (!biv_p (insn, mode, dest))
    1519                 :             :     return NULL;
    1520                 :             : 
    1521                 :       50589 :   ok = iv_analyze_result (insn, dest, &iv);
    1522                 :             : 
    1523                 :             :   /* This used to be an assert under the assumption that if biv_p returns
    1524                 :             :      true that iv_analyze_result must also return true.  However, that
    1525                 :             :      assumption is not strictly correct as evidenced by pr25569.
    1526                 :             : 
    1527                 :             :      Returning NULL when iv_analyze_result returns false is safe and
    1528                 :             :      avoids the problems in pr25569 until the iv_analyze_* routines
    1529                 :             :      can be fixed, which is apparently hard and time consuming
    1530                 :             :      according to their author.  */
    1531                 :       50589 :   if (! ok)
    1532                 :             :     return NULL;
    1533                 :             : 
    1534                 :       50589 :   if (iv.step == const0_rtx
    1535                 :       50589 :       || iv.mode != iv.extend_mode)
    1536                 :             :     return NULL;
    1537                 :             : 
    1538                 :             :   /* Record the insn to split.  */
    1539                 :       50584 :   ivts = XNEW (struct iv_to_split);
    1540                 :       50584 :   ivts->insn = insn;
    1541                 :       50584 :   ivts->orig_var = dest;
    1542                 :       50584 :   ivts->base_var = NULL_RTX;
    1543                 :       50584 :   ivts->step = iv.step;
    1544                 :       50584 :   ivts->next = NULL;
    1545                 :             : 
    1546                 :       50584 :   return ivts;
    1547                 :             : }
    1548                 :             : 
    1549                 :             : /* Determines which of insns in LOOP can be optimized.
    1550                 :             :    Return a OPT_INFO struct with the relevant hash tables filled
    1551                 :             :    with all insns to be optimized.  The FIRST_NEW_BLOCK field
    1552                 :             :    is undefined for the return value.  */
    1553                 :             : 
    1554                 :             : static struct opt_info *
    1555                 :       48010 : analyze_insns_in_loop (class loop *loop)
    1556                 :             : {
    1557                 :       48010 :   basic_block *body, bb;
    1558                 :       48010 :   unsigned i;
    1559                 :       48010 :   struct opt_info *opt_info = XCNEW (struct opt_info);
    1560                 :       48010 :   rtx_insn *insn;
    1561                 :       48010 :   struct iv_to_split *ivts = NULL;
    1562                 :       48010 :   struct var_to_expand *ves = NULL;
    1563                 :       48010 :   iv_to_split **slot1;
    1564                 :       48010 :   var_to_expand **slot2;
    1565                 :       48010 :   auto_vec<edge> edges = get_loop_exit_edges (loop);
    1566                 :       48010 :   edge exit;
    1567                 :       48010 :   bool can_apply = false;
    1568                 :             : 
    1569                 :       48010 :   iv_analysis_loop_init (loop);
    1570                 :             : 
    1571                 :       48010 :   body = get_loop_body (loop);
    1572                 :             : 
    1573                 :       48010 :   if (flag_split_ivs_in_unroller)
    1574                 :             :     {
    1575                 :       48010 :       opt_info->insns_to_split
    1576                 :       48010 :         = new hash_table<iv_split_hasher> (5 * loop->num_nodes);
    1577                 :       48010 :       opt_info->iv_to_split_head = NULL;
    1578                 :       48010 :       opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
    1579                 :             :     }
    1580                 :             : 
    1581                 :             :   /* Record the loop exit bb and loop preheader before the unrolling.  */
    1582                 :       48010 :   opt_info->loop_preheader = loop_preheader_edge (loop)->src;
    1583                 :             : 
    1584                 :       48010 :   if (edges.length () == 1)
    1585                 :             :     {
    1586                 :       42964 :       exit = edges[0];
    1587                 :       42964 :       if (!(exit->flags & EDGE_COMPLEX))
    1588                 :             :         {
    1589                 :       42964 :           opt_info->loop_exit = split_edge (exit);
    1590                 :       42964 :           can_apply = true;
    1591                 :             :         }
    1592                 :             :     }
    1593                 :             : 
    1594                 :       48010 :   if (flag_variable_expansion_in_unroller
    1595                 :           6 :       && can_apply)
    1596                 :             :     {
    1597                 :           6 :       opt_info->insns_with_var_to_expand
    1598                 :           6 :         = new hash_table<var_expand_hasher> (5 * loop->num_nodes);
    1599                 :           6 :       opt_info->var_to_expand_head = NULL;
    1600                 :           6 :       opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
    1601                 :             :     }
    1602                 :             : 
    1603                 :      153297 :   for (i = 0; i < loop->num_nodes; i++)
    1604                 :             :     {
    1605                 :      105287 :       bb = body[i];
    1606                 :      105287 :       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    1607                 :        2389 :         continue;
    1608                 :             : 
    1609                 :      711920 :       FOR_BB_INSNS (bb, insn)
    1610                 :             :       {
    1611                 :      609022 :         if (!INSN_P (insn))
    1612                 :      199615 :           continue;
    1613                 :             : 
    1614                 :      409407 :         if (opt_info->insns_to_split)
    1615                 :      409407 :           ivts = analyze_iv_to_split_insn (insn);
    1616                 :             : 
    1617                 :      409407 :         if (ivts)
    1618                 :             :           {
    1619                 :       50584 :             slot1 = opt_info->insns_to_split->find_slot (ivts, INSERT);
    1620                 :       50584 :             gcc_assert (*slot1 == NULL);
    1621                 :       50584 :             *slot1 = ivts;
    1622                 :       50584 :             *opt_info->iv_to_split_tail = ivts;
    1623                 :       50584 :             opt_info->iv_to_split_tail = &ivts->next;
    1624                 :       50584 :             continue;
    1625                 :             :           }
    1626                 :             : 
    1627                 :      358823 :         if (opt_info->insns_with_var_to_expand)
    1628                 :          33 :           ves = analyze_insn_to_expand_var (loop, insn);
    1629                 :             : 
    1630                 :      358823 :         if (ves)
    1631                 :             :           {
    1632                 :           3 :             slot2 = opt_info->insns_with_var_to_expand->find_slot (ves, INSERT);
    1633                 :           3 :             gcc_assert (*slot2 == NULL);
    1634                 :           3 :             *slot2 = ves;
    1635                 :           3 :             *opt_info->var_to_expand_tail = ves;
    1636                 :           3 :             opt_info->var_to_expand_tail = &ves->next;
    1637                 :             :           }
    1638                 :             :       }
    1639                 :             :     }
    1640                 :             : 
    1641                 :       48010 :   free (body);
    1642                 :       48010 :   return opt_info;
    1643                 :       48010 : }
    1644                 :             : 
    1645                 :             : /* Called just before loop duplication.  Records start of duplicated area
    1646                 :             :    to OPT_INFO.  */
    1647                 :             : 
    1648                 :             : static void
    1649                 :       49590 : opt_info_start_duplication (struct opt_info *opt_info)
    1650                 :             : {
    1651                 :       49590 :   if (opt_info)
    1652                 :       49590 :     opt_info->first_new_block = last_basic_block_for_fn (cfun);
    1653                 :           0 : }
    1654                 :             : 
    1655                 :             : /* Determine the number of iterations between initialization of the base
    1656                 :             :    variable and the current copy (N_COPY).  N_COPIES is the total number
    1657                 :             :    of newly created copies.  UNROLLING is true if we are unrolling
    1658                 :             :    (not peeling) the loop.  */
    1659                 :             : 
    1660                 :             : static unsigned
    1661                 :      341980 : determine_split_iv_delta (unsigned n_copy, unsigned n_copies, bool unrolling)
    1662                 :             : {
    1663                 :           0 :   if (unrolling)
    1664                 :             :     {
    1665                 :             :       /* If we are unrolling, initialization is done in the original loop
    1666                 :             :          body (number 0).  */
    1667                 :             :       return n_copy;
    1668                 :             :     }
    1669                 :             :   else
    1670                 :             :     {
    1671                 :             :       /* If we are peeling, the copy in that the initialization occurs has
    1672                 :             :          number 1.  The original loop (number 0) is the last.  */
    1673                 :        3601 :       if (n_copy)
    1674                 :        3601 :         return n_copy - 1;
    1675                 :             :       else
    1676                 :             :         return n_copies;
    1677                 :             :     }
    1678                 :             : }
    1679                 :             : 
    1680                 :             : /* Allocate basic variable for the induction variable chain.  */
    1681                 :             : 
    1682                 :             : static void
    1683                 :       51075 : allocate_basic_variable (struct iv_to_split *ivts)
    1684                 :             : {
    1685                 :       51075 :   rtx expr = SET_SRC (single_set (ivts->insn));
    1686                 :             : 
    1687                 :       51075 :   ivts->base_var = gen_reg_rtx (GET_MODE (expr));
    1688                 :       51075 : }
    1689                 :             : 
    1690                 :             : /* Insert initialization of basic variable of IVTS before INSN, taking
    1691                 :             :    the initial value from INSN.  */
    1692                 :             : 
    1693                 :             : static void
    1694                 :       61076 : insert_base_initialization (struct iv_to_split *ivts, rtx_insn *insn)
    1695                 :             : {
    1696                 :       61076 :   rtx expr = copy_rtx (SET_SRC (single_set (insn)));
    1697                 :       61076 :   rtx_insn *seq;
    1698                 :             : 
    1699                 :       61076 :   start_sequence ();
    1700                 :       61076 :   expr = force_operand (expr, ivts->base_var);
    1701                 :       61076 :   if (expr != ivts->base_var)
    1702                 :         236 :     emit_move_insn (ivts->base_var, expr);
    1703                 :       61076 :   seq = get_insns ();
    1704                 :       61076 :   end_sequence ();
    1705                 :             : 
    1706                 :       61076 :   emit_insn_before (seq, insn);
    1707                 :       61076 : }
    1708                 :             : 
    1709                 :             : /* Replace the use of induction variable described in IVTS in INSN
    1710                 :             :    by base variable + DELTA * step.  */
    1711                 :             : 
    1712                 :             : static void
    1713                 :      169113 : split_iv (struct iv_to_split *ivts, rtx_insn *insn, unsigned delta)
    1714                 :             : {
    1715                 :      169113 :   rtx expr, *loc, incr, var;
    1716                 :      169113 :   rtx_insn *seq;
    1717                 :      169113 :   machine_mode mode = GET_MODE (ivts->base_var);
    1718                 :      169113 :   rtx src, dest, set;
    1719                 :             : 
    1720                 :             :   /* Construct base + DELTA * step.  */
    1721                 :      169113 :   if (!delta)
    1722                 :             :     expr = ivts->base_var;
    1723                 :             :   else
    1724                 :             :     {
    1725                 :      108037 :       incr = simplify_gen_binary (MULT, mode,
    1726                 :             :                                   copy_rtx (ivts->step),
    1727                 :      108037 :                                   gen_int_mode (delta, mode));
    1728                 :      108037 :       expr = simplify_gen_binary (PLUS, GET_MODE (ivts->base_var),
    1729                 :             :                                   ivts->base_var, incr);
    1730                 :             :     }
    1731                 :             : 
    1732                 :             :   /* Figure out where to do the replacement.  */
    1733                 :      169113 :   loc = &SET_SRC (single_set (insn));
    1734                 :             : 
    1735                 :             :   /* If we can make the replacement right away, we're done.  */
    1736                 :      169113 :   if (validate_change (insn, loc, expr, 0))
    1737                 :             :     return;
    1738                 :             : 
    1739                 :             :   /* Otherwise, force EXPR into a register and try again.  */
    1740                 :         256 :   start_sequence ();
    1741                 :         256 :   var = gen_reg_rtx (mode);
    1742                 :         256 :   expr = force_operand (expr, var);
    1743                 :         256 :   if (expr != var)
    1744                 :           0 :     emit_move_insn (var, expr);
    1745                 :         256 :   seq = get_insns ();
    1746                 :         256 :   end_sequence ();
    1747                 :         256 :   emit_insn_before (seq, insn);
    1748                 :             : 
    1749                 :         256 :   if (validate_change (insn, loc, var, 0))
    1750                 :             :     return;
    1751                 :             : 
    1752                 :             :   /* The last chance.  Try recreating the assignment in insn
    1753                 :             :      completely from scratch.  */
    1754                 :           0 :   set = single_set (insn);
    1755                 :           0 :   gcc_assert (set);
    1756                 :             : 
    1757                 :           0 :   start_sequence ();
    1758                 :           0 :   *loc = var;
    1759                 :           0 :   src = copy_rtx (SET_SRC (set));
    1760                 :           0 :   dest = copy_rtx (SET_DEST (set));
    1761                 :           0 :   src = force_operand (src, dest);
    1762                 :           0 :   if (src != dest)
    1763                 :           0 :     emit_move_insn (dest, src);
    1764                 :           0 :   seq = get_insns ();
    1765                 :           0 :   end_sequence ();
    1766                 :             : 
    1767                 :           0 :   emit_insn_before (seq, insn);
    1768                 :           0 :   delete_insn (insn);
    1769                 :             : }
    1770                 :             : 
    1771                 :             : 
    1772                 :             : /* Return one expansion of the accumulator recorded in struct VE.  */
    1773                 :             : 
    1774                 :             : static rtx
    1775                 :          18 : get_expansion (struct var_to_expand *ve)
    1776                 :             : {
    1777                 :          18 :   rtx reg;
    1778                 :             : 
    1779                 :          18 :   if (ve->reuse_expansion == 0)
    1780                 :           9 :     reg = ve->reg;
    1781                 :             :   else
    1782                 :           9 :     reg = ve->var_expansions[ve->reuse_expansion - 1];
    1783                 :             : 
    1784                 :          36 :   if (ve->var_expansions.length () == (unsigned) ve->reuse_expansion)
    1785                 :           9 :     ve->reuse_expansion = 0;
    1786                 :             :   else
    1787                 :           9 :     ve->reuse_expansion++;
    1788                 :             : 
    1789                 :          18 :   return reg;
    1790                 :             : }
    1791                 :             : 
    1792                 :             : 
    1793                 :             : /* Given INSN replace the uses of the accumulator recorded in VE
    1794                 :             :    with a new register.  */
    1795                 :             : 
    1796                 :             : static void
    1797                 :          21 : expand_var_during_unrolling (struct var_to_expand *ve, rtx_insn *insn)
    1798                 :             : {
    1799                 :          21 :   rtx new_reg, set;
    1800                 :          21 :   bool really_new_expansion = false;
    1801                 :             : 
    1802                 :          21 :   set = single_set (insn);
    1803                 :          21 :   gcc_assert (set);
    1804                 :             : 
    1805                 :             :   /* Generate a new register only if the expansion limit has not been
    1806                 :             :      reached.  Else reuse an already existing expansion.  */
    1807                 :          21 :   if (param_max_variable_expansions > ve->expansion_count)
    1808                 :             :     {
    1809                 :           3 :       really_new_expansion = true;
    1810                 :           3 :       new_reg = gen_reg_rtx (GET_MODE (ve->reg));
    1811                 :             :     }
    1812                 :             :   else
    1813                 :          18 :     new_reg = get_expansion (ve);
    1814                 :             : 
    1815                 :          21 :   validate_replace_rtx_group (SET_DEST (set), new_reg, insn);
    1816                 :          21 :   if (apply_change_group ())
    1817                 :          21 :     if (really_new_expansion)
    1818                 :             :       {
    1819                 :           3 :         ve->var_expansions.safe_push (new_reg);
    1820                 :           3 :         ve->expansion_count++;
    1821                 :             :       }
    1822                 :          21 : }
    1823                 :             : 
    1824                 :             : /* Initialize the variable expansions in loop preheader.  PLACE is the
    1825                 :             :    loop-preheader basic block where the initialization of the
    1826                 :             :    expansions should take place.  The expansions are initialized with
    1827                 :             :    (-0) when the operation is plus or minus to honor sign zero.  This
    1828                 :             :    way we can prevent cases where the sign of the final result is
    1829                 :             :    effected by the sign of the expansion.  Here is an example to
    1830                 :             :    demonstrate this:
    1831                 :             : 
    1832                 :             :    for (i = 0 ; i < n; i++)
    1833                 :             :      sum += something;
    1834                 :             : 
    1835                 :             :    ==>
    1836                 :             : 
    1837                 :             :    sum += something
    1838                 :             :    ....
    1839                 :             :    i = i+1;
    1840                 :             :    sum1 += something
    1841                 :             :    ....
    1842                 :             :    i = i+1
    1843                 :             :    sum2 += something;
    1844                 :             :    ....
    1845                 :             : 
    1846                 :             :    When SUM is initialized with -zero and SOMETHING is also -zero; the
    1847                 :             :    final result of sum should be -zero thus the expansions sum1 and sum2
    1848                 :             :    should be initialized with -zero as well (otherwise we will get +zero
    1849                 :             :    as the final result).  */
    1850                 :             : 
    1851                 :             : static void
    1852                 :           3 : insert_var_expansion_initialization (struct var_to_expand *ve,
    1853                 :             :                                      basic_block place)
    1854                 :             : {
    1855                 :           3 :   rtx_insn *seq;
    1856                 :           3 :   rtx var, zero_init;
    1857                 :           3 :   unsigned i;
    1858                 :           3 :   machine_mode mode = GET_MODE (ve->reg);
    1859                 :           9 :   bool has_signed_zero_p = MODE_HAS_SIGNED_ZEROS (mode);
    1860                 :             : 
    1861                 :           3 :   if (ve->var_expansions.length () == 0)
    1862                 :           3 :     return;
    1863                 :             : 
    1864                 :           3 :   start_sequence ();
    1865                 :           3 :   switch (ve->op)
    1866                 :             :     {
    1867                 :             :     case FMA:
    1868                 :             :       /* Note that we only accumulate FMA via the ADD operand.  */
    1869                 :             :     case PLUS:
    1870                 :             :     case MINUS:
    1871                 :           6 :       FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
    1872                 :             :         {
    1873                 :           3 :           if (has_signed_zero_p)
    1874                 :           2 :             zero_init = simplify_gen_unary (NEG, mode, CONST0_RTX (mode), mode);
    1875                 :             :           else
    1876                 :           1 :             zero_init = CONST0_RTX (mode);
    1877                 :           3 :           emit_move_insn (var, zero_init);
    1878                 :             :         }
    1879                 :             :       break;
    1880                 :             : 
    1881                 :             :     case MULT:
    1882                 :           0 :       FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
    1883                 :             :         {
    1884                 :           0 :           zero_init = CONST1_RTX (GET_MODE (var));
    1885                 :           0 :           emit_move_insn (var, zero_init);
    1886                 :             :         }
    1887                 :             :       break;
    1888                 :             : 
    1889                 :           0 :     default:
    1890                 :           0 :       gcc_unreachable ();
    1891                 :             :     }
    1892                 :             : 
    1893                 :           3 :   seq = get_insns ();
    1894                 :           3 :   end_sequence ();
    1895                 :             : 
    1896                 :           3 :   emit_insn_after (seq, BB_END (place));
    1897                 :             : }
    1898                 :             : 
    1899                 :             : /* Combine the variable expansions at the loop exit.  PLACE is the
    1900                 :             :    loop exit basic block where the summation of the expansions should
    1901                 :             :    take place.  */
    1902                 :             : 
    1903                 :             : static void
    1904                 :           3 : combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
    1905                 :             : {
    1906                 :           3 :   rtx sum = ve->reg;
    1907                 :           3 :   rtx expr, var;
    1908                 :           3 :   rtx_insn *seq, *insn;
    1909                 :           3 :   unsigned i;
    1910                 :             : 
    1911                 :           3 :   if (ve->var_expansions.length () == 0)
    1912                 :           3 :     return;
    1913                 :             : 
    1914                 :             :   /* ve->reg might be SUBREG or some other non-shareable RTL, and we use
    1915                 :             :      it both here and as the destination of the assignment.  */
    1916                 :           3 :   sum = copy_rtx (sum);
    1917                 :           3 :   start_sequence ();
    1918                 :           3 :   switch (ve->op)
    1919                 :             :     {
    1920                 :             :     case FMA:
    1921                 :             :       /* Note that we only accumulate FMA via the ADD operand.  */
    1922                 :             :     case PLUS:
    1923                 :             :     case MINUS:
    1924                 :           6 :       FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
    1925                 :           3 :         sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg), var, sum);
    1926                 :             :       break;
    1927                 :             : 
    1928                 :             :     case MULT:
    1929                 :           0 :       FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
    1930                 :           0 :         sum = simplify_gen_binary (MULT, GET_MODE (ve->reg), var, sum);
    1931                 :             :       break;
    1932                 :             : 
    1933                 :           0 :     default:
    1934                 :           0 :       gcc_unreachable ();
    1935                 :             :     }
    1936                 :             : 
    1937                 :           3 :   expr = force_operand (sum, ve->reg);
    1938                 :           3 :   if (expr != ve->reg)
    1939                 :           0 :     emit_move_insn (ve->reg, expr);
    1940                 :           3 :   seq = get_insns ();
    1941                 :           3 :   end_sequence ();
    1942                 :             : 
    1943                 :           3 :   insn = BB_HEAD (place);
    1944                 :           3 :   while (!NOTE_INSN_BASIC_BLOCK_P (insn))
    1945                 :           0 :     insn = NEXT_INSN (insn);
    1946                 :             : 
    1947                 :           3 :   emit_insn_after (seq, insn);
    1948                 :             : }
    1949                 :             : 
    1950                 :             : /* Strip away REG_EQUAL notes for IVs we're splitting.
    1951                 :             : 
    1952                 :             :    Updating REG_EQUAL notes for IVs we split is tricky: We
    1953                 :             :    cannot tell until after unrolling, DF-rescanning, and liveness
    1954                 :             :    updating, whether an EQ_USE is reached by the split IV while
    1955                 :             :    the IV reg is still live.  See PR55006.
    1956                 :             : 
    1957                 :             :    ??? We cannot use remove_reg_equal_equiv_notes_for_regno,
    1958                 :             :    because RTL loop-iv requires us to defer rescanning insns and
    1959                 :             :    any notes attached to them.  So resort to old techniques...  */
    1960                 :             : 
    1961                 :             : static void
    1962                 :   124309479 : maybe_strip_eq_note_for_split_iv (struct opt_info *opt_info, rtx_insn *insn)
    1963                 :             : {
    1964                 :   124309479 :   struct iv_to_split *ivts;
    1965                 :   124309479 :   rtx note = find_reg_equal_equiv_note (insn);
    1966                 :   124309479 :   if (! note)
    1967                 :             :     return;
    1968                 :     8111210 :   for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
    1969                 :     4162386 :     if (reg_mentioned_p (ivts->orig_var, note))
    1970                 :             :       {
    1971                 :       21807 :         remove_note (insn, note);
    1972                 :       21807 :         return;
    1973                 :             :       }
    1974                 :             : }
    1975                 :             : 
    1976                 :             : /* Apply loop optimizations in loop copies using the
    1977                 :             :    data which gathered during the unrolling.  Structure
    1978                 :             :    OPT_INFO record that data.
    1979                 :             : 
    1980                 :             :    UNROLLING is true if we unrolled (not peeled) the loop.
    1981                 :             :    REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
    1982                 :             :    the loop (as it should happen in complete unrolling, but not in ordinary
    1983                 :             :    peeling of the loop).  */
    1984                 :             : 
    1985                 :             : static void
    1986                 :       48487 : apply_opt_in_copies (struct opt_info *opt_info,
    1987                 :             :                      unsigned n_copies, bool unrolling,
    1988                 :             :                      bool rewrite_original_loop)
    1989                 :             : {
    1990                 :       48487 :   unsigned i, delta;
    1991                 :       48487 :   basic_block bb, orig_bb;
    1992                 :       48487 :   rtx_insn *insn, *orig_insn, *next;
    1993                 :       48487 :   struct iv_to_split ivts_templ, *ivts;
    1994                 :       48487 :   struct var_to_expand ve_templ, *ves;
    1995                 :             : 
    1996                 :             :   /* Sanity check -- we need to put initialization in the original loop
    1997                 :             :      body.  */
    1998                 :       48487 :   gcc_assert (!unrolling || rewrite_original_loop);
    1999                 :             : 
    2000                 :             :   /* Allocate the basic variables (i0).  */
    2001                 :       48487 :   if (opt_info->insns_to_split)
    2002                 :       99562 :     for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
    2003                 :       51075 :       allocate_basic_variable (ivts);
    2004                 :             : 
    2005                 :      285180 :   for (i = opt_info->first_new_block;
    2006                 :      285180 :        i < (unsigned) last_basic_block_for_fn (cfun);
    2007                 :             :        i++)
    2008                 :             :     {
    2009                 :      236693 :       bb = BASIC_BLOCK_FOR_FN (cfun, i);
    2010                 :      236693 :       orig_bb = get_bb_original (bb);
    2011                 :             : 
    2012                 :             :       /* bb->aux holds position in copy sequence initialized by
    2013                 :             :          duplicate_loop_body_to_header_edge.  */
    2014                 :      236693 :       delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
    2015                 :             :                                         unrolling);
    2016                 :      236693 :       bb->aux = 0;
    2017                 :      236693 :       orig_insn = BB_HEAD (orig_bb);
    2018                 :     3199964 :       FOR_BB_INSNS_SAFE (bb, insn, next)
    2019                 :             :         {
    2020                 :     1702856 :           if (!INSN_P (insn)
    2021                 :     1363289 :               || (DEBUG_BIND_INSN_P (insn)
    2022                 :      229684 :                   && INSN_VAR_LOCATION_DECL (insn)
    2023                 :      229684 :                   && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL))
    2024                 :      339567 :             continue;
    2025                 :             : 
    2026                 :     1281328 :           while (!INSN_P (orig_insn)
    2027                 :     1281328 :                  || (DEBUG_BIND_INSN_P (orig_insn)
    2028                 :      229696 :                      && INSN_VAR_LOCATION_DECL (orig_insn)
    2029                 :      229696 :                      && (TREE_CODE (INSN_VAR_LOCATION_DECL (orig_insn))
    2030                 :             :                          == LABEL_DECL)))
    2031                 :      257606 :             orig_insn = NEXT_INSN (orig_insn);
    2032                 :             : 
    2033                 :     1023722 :           ivts_templ.insn = orig_insn;
    2034                 :     1023722 :           ve_templ.insn = orig_insn;
    2035                 :             : 
    2036                 :             :           /* Apply splitting iv optimization.  */
    2037                 :     1023722 :           if (opt_info->insns_to_split)
    2038                 :             :             {
    2039                 :     1023722 :               maybe_strip_eq_note_for_split_iv (opt_info, insn);
    2040                 :             : 
    2041                 :     1023722 :               ivts = opt_info->insns_to_split->find (&ivts_templ);
    2042                 :             : 
    2043                 :     1023722 :               if (ivts)
    2044                 :             :                 {
    2045                 :      108528 :                   gcc_assert (GET_CODE (PATTERN (insn))
    2046                 :             :                               == GET_CODE (PATTERN (orig_insn)));
    2047                 :             : 
    2048                 :      108528 :                   if (!delta)
    2049                 :         491 :                     insert_base_initialization (ivts, insn);
    2050                 :      108528 :                   split_iv (ivts, insn, delta);
    2051                 :             :                 }
    2052                 :             :             }
    2053                 :             :           /* Apply variable expansion optimization.  */
    2054                 :     1023722 :           if (unrolling && opt_info->insns_with_var_to_expand)
    2055                 :             :             {
    2056                 :         546 :               ves = (struct var_to_expand *)
    2057                 :         273 :                 opt_info->insns_with_var_to_expand->find (&ve_templ);
    2058                 :         273 :               if (ves)
    2059                 :             :                 {
    2060                 :          21 :                   gcc_assert (GET_CODE (PATTERN (insn))
    2061                 :             :                               == GET_CODE (PATTERN (orig_insn)));
    2062                 :          21 :                   expand_var_during_unrolling (ves, insn);
    2063                 :             :                 }
    2064                 :             :             }
    2065                 :     1023722 :           orig_insn = NEXT_INSN (orig_insn);
    2066                 :             :         }
    2067                 :             :     }
    2068                 :             : 
    2069                 :       48487 :   if (!rewrite_original_loop)
    2070                 :         477 :     return;
    2071                 :             : 
    2072                 :             :   /* Initialize the variable expansions in the loop preheader
    2073                 :             :      and take care of combining them at the loop exit.  */
    2074                 :       48010 :   if (opt_info->insns_with_var_to_expand)
    2075                 :             :     {
    2076                 :           9 :       for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
    2077                 :           3 :         insert_var_expansion_initialization (ves, opt_info->loop_preheader);
    2078                 :           9 :       for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
    2079                 :           3 :         combine_var_copies_in_loop_exit (ves, opt_info->loop_exit);
    2080                 :             :     }
    2081                 :             : 
    2082                 :             :   /* Rewrite also the original loop body.  Find them as originals of the blocks
    2083                 :             :      in the last copied iteration, i.e. those that have
    2084                 :             :      get_bb_copy (get_bb_original (bb)) == bb.  */
    2085                 :      281102 :   for (i = opt_info->first_new_block;
    2086                 :      281102 :        i < (unsigned) last_basic_block_for_fn (cfun);
    2087                 :             :        i++)
    2088                 :             :     {
    2089                 :      233092 :       bb = BASIC_BLOCK_FOR_FN (cfun, i);
    2090                 :      233092 :       orig_bb = get_bb_original (bb);
    2091                 :      233092 :       if (get_bb_copy (orig_bb) != bb)
    2092                 :      127805 :         continue;
    2093                 :             : 
    2094                 :      105287 :       delta = determine_split_iv_delta (0, n_copies, unrolling);
    2095                 :      105287 :       for (orig_insn = BB_HEAD (orig_bb);
    2096                 :   166491280 :            orig_insn != NEXT_INSN (BB_END (bb));
    2097                 :             :            orig_insn = next)
    2098                 :             :         {
    2099                 :   166385993 :           next = NEXT_INSN (orig_insn);
    2100                 :             : 
    2101                 :   166385993 :           if (!INSN_P (orig_insn))
    2102                 :    43100236 :             continue;
    2103                 :             : 
    2104                 :   123285757 :           ivts_templ.insn = orig_insn;
    2105                 :   123285757 :           if (opt_info->insns_to_split)
    2106                 :             :             {
    2107                 :   123285757 :               maybe_strip_eq_note_for_split_iv (opt_info, orig_insn);
    2108                 :             : 
    2109                 :   246571514 :               ivts = (struct iv_to_split *)
    2110                 :   123285757 :                 opt_info->insns_to_split->find (&ivts_templ);
    2111                 :   123285757 :               if (ivts)
    2112                 :             :                 {
    2113                 :       60585 :                   if (!delta)
    2114                 :       60585 :                     insert_base_initialization (ivts, orig_insn);
    2115                 :       60585 :                   split_iv (ivts, orig_insn, delta);
    2116                 :       60585 :                   continue;
    2117                 :             :                 }
    2118                 :             :             }
    2119                 :             : 
    2120                 :             :         }
    2121                 :             :     }
    2122                 :             : }
    2123                 :             : 
    2124                 :             : /* Release OPT_INFO.  */
    2125                 :             : 
    2126                 :             : static void
    2127                 :       48010 : free_opt_info (struct opt_info *opt_info)
    2128                 :             : {
    2129                 :       48010 :   delete opt_info->insns_to_split;
    2130                 :       48010 :   opt_info->insns_to_split = NULL;
    2131                 :       48010 :   if (opt_info->insns_with_var_to_expand)
    2132                 :             :     {
    2133                 :           6 :       struct var_to_expand *ves;
    2134                 :             : 
    2135                 :           9 :       for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
    2136                 :           3 :         ves->var_expansions.release ();
    2137                 :           6 :       delete opt_info->insns_with_var_to_expand;
    2138                 :           6 :       opt_info->insns_with_var_to_expand = NULL;
    2139                 :             :     }
    2140                 :       48010 :   free (opt_info);
    2141                 :       48010 : }
        

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.