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

Generated by: LCOV version 1.0

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