gcc/loop-unroll.c

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