gcc/loop-unroll.c

   1 /* Loop unrolling and peeling.
   2    Copyright (C) 2002, 2003, 2004 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "params.h"
  31 #include "output.h"
  32 #include "expr.h"
  33
  34 /* This pass performs loop unrolling and peeling.  We only perform these
  35    optimizations on innermost loops (with single exception) because
  36    the impact on performance is greatest here, and we want to avoid
  37    unnecessary code size growth.  The gain is caused by greater sequentiality
  38    of code, better code to optimize for further passes and in some cases
  39    by fewer testings of exit conditions.  The main problem is code growth,
  40    that impacts performance negatively due to effect of caches.
  41
  42    What we do:
  43
  44    -- complete peeling of once-rolling loops; this is the above mentioned
  45       exception, as this causes loop to be cancelled completely and
  46       does not cause code growth
  47    -- complete peeling of loops that roll (small) constant times.
  48    -- simple peeling of first iterations of loops that do not roll much
  49       (according to profile feedback)
  50    -- unrolling of loops that roll constant times; this is almost always
  51       win, as we get rid of exit condition tests.
  52    -- unrolling of loops that roll number of times that we can compute
  53       in runtime; we also get rid of exit condition tests here, but there
  54       is the extra expense for calculating the number of iterations
  55    -- simple unrolling of remaining loops; this is performed only if we
  56       are asked to, as the gain is questionable in this case and often
  57       it may even slow down the code
  58    For more detailed descriptions of each of those, see comments at
  59    appropriate function below.
  60
  61    There is a lot of parameters (defined and described in params.def) that
  62    control how much we unroll/peel.
  63
  64    ??? A great problem is that we don't have a good way how to determine
  65    how many times we should unroll the loop; the experiments I have made
  66    showed that this choice may affect performance in order of several %.
  67    */
  68
  69 static void decide_unrolling_and_peeling (struct loops *, int);
  70 static void peel_loops_completely (struct loops *, int);
  71 static void decide_peel_simple (struct loop *, int);
  72 static void decide_peel_once_rolling (struct loop *, int);
  73 static void decide_peel_completely (struct loop *, int);
  74 static void decide_unroll_stupid (struct loop *, int);
  75 static void decide_unroll_constant_iterations (struct loop *, int);
  76 static void decide_unroll_runtime_iterations (struct loop *, int);
  77 static void peel_loop_simple (struct loops *, struct loop *);
  78 static void peel_loop_completely (struct loops *, struct loop *);
  79 static void unroll_loop_stupid (struct loops *, struct loop *);
  80 static void unroll_loop_constant_iterations (struct loops *, struct loop *);
  81 static void unroll_loop_runtime_iterations (struct loops *, struct loop *);
  82
  83 /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
  84 void
  85 unroll_and_peel_loops (struct loops *loops, int flags)
  86 {
  87   struct loop *loop, *next;
  88   bool check;
  89
  90   /* First perform complete loop peeling (it is almost surely a win,
  91      and affects parameters for further decision a lot).  */
  92   peel_loops_completely (loops, flags);
  93
  94   /* Now decide rest of unrolling and peeling.  */
  95   decide_unrolling_and_peeling (loops, flags);
  96
  97   loop = loops->tree_root;
  98   while (loop->inner)
  99     loop = loop->inner;
 100
 101   /* Scan the loops, inner ones first.  */
 102   while (loop != loops->tree_root)
 103     {
 104       if (loop->next)
 105         {
 106           next = loop->next;
 107           while (next->inner)
 108             next = next->inner;
 109         }
 110       else
 111         next = loop->outer;
 112
 113       check = true;
 114       /* And perform the appropriate transformations.  */
 115       switch (loop->lpt_decision.decision)
 116         {
 117         case LPT_PEEL_COMPLETELY:
 118           /* Already done.  */
 119           gcc_unreachable ();
 120         case LPT_PEEL_SIMPLE:
 121           peel_loop_simple (loops, loop);
 122           break;
 123         case LPT_UNROLL_CONSTANT:
 124           unroll_loop_constant_iterations (loops, loop);
 125           break;
 126         case LPT_UNROLL_RUNTIME:
 127           unroll_loop_runtime_iterations (loops, loop);
 128           break;
 129         case LPT_UNROLL_STUPID:
 130           unroll_loop_stupid (loops, loop);
 131           break;
 132         case LPT_NONE:
 133           check = false;
 134           break;
 135         default:
 136           gcc_unreachable ();
 137         }
 138       if (check)
 139         {
 140 #ifdef ENABLE_CHECKING
 141           verify_dominators (CDI_DOMINATORS);
 142           verify_loop_structure (loops);
 143 #endif
 144         }
 145       loop = next;
 146     }
 147
 148   iv_analysis_done ();
 149 }
 150
 151 /* Check whether exit of the LOOP is at the end of loop body.  */
 152
 153 static bool
 154 loop_exit_at_end_p (struct loop *loop)
 155 {
 156   struct niter_desc *desc = get_simple_loop_desc (loop);
 157   rtx insn;
 158
 159   if (desc->in_edge->dest != loop->latch)
 160     return false;
 161
 162   /* Check that the latch is empty.  */
 163   FOR_BB_INSNS (loop->latch, insn)
 164     {
 165       if (INSN_P (insn))
 166         return false;
 167     }
 168
 169   return true;
 170 }
 171
 172 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so.  */
 173 static void
 174 peel_loops_completely (struct loops *loops, int flags)
 175 {
 176   struct loop *loop, *next;
 177
 178   loop = loops->tree_root;
 179   while (loop->inner)
 180     loop = loop->inner;
 181
 182   while (loop != loops->tree_root)
 183     {
 184       if (loop->next)
 185         {
 186           next = loop->next;
 187           while (next->inner)
 188             next = next->inner;
 189         }
 190       else
 191         next = loop->outer;
 192
 193       loop->lpt_decision.decision = LPT_NONE;
 194
 195       if (dump_file)
 196         fprintf (dump_file,
 197                  "\n;; *** Considering loop %d for complete peeling ***\n",
 198                  loop->num);
 199
 200       loop->ninsns = num_loop_insns (loop);
 201
 202       decide_peel_once_rolling (loop, flags);
 203       if (loop->lpt_decision.decision == LPT_NONE)
 204         decide_peel_completely (loop, flags);
 205
 206       if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
 207         {
 208           peel_loop_completely (loops, loop);
 209 #ifdef ENABLE_CHECKING
 210           verify_dominators (CDI_DOMINATORS);
 211           verify_loop_structure (loops);
 212 #endif
 213         }
 214       loop = next;
 215     }
 216 }
 217
 218 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much.  */
 219 static void
 220 decide_unrolling_and_peeling (struct loops *loops, int flags)
 221 {
 222   struct loop *loop = loops->tree_root, *next;
 223
 224   while (loop->inner)
 225     loop = loop->inner;
 226
 227   /* Scan the loops, inner ones first.  */
 228   while (loop != loops->tree_root)
 229     {
 230       if (loop->next)
 231         {
 232           next = loop->next;
 233           while (next->inner)
 234             next = next->inner;
 235         }
 236       else
 237         next = loop->outer;
 238
 239       loop->lpt_decision.decision = LPT_NONE;
 240
 241       if (dump_file)
 242         fprintf (dump_file, "\n;; *** Considering loop %d ***\n", loop->num);
 243
 244       /* Do not peel cold areas.  */
 245       if (!maybe_hot_bb_p (loop->header))
 246         {
 247           if (dump_file)
 248             fprintf (dump_file, ";; Not considering loop, cold area\n");
 249           loop = next;
 250           continue;
 251         }
 252
 253       /* Can the loop be manipulated?  */
 254       if (!can_duplicate_loop_p (loop))
 255         {
 256           if (dump_file)
 257             fprintf (dump_file,
 258                      ";; Not considering loop, cannot duplicate\n");
 259           loop = next;
 260           continue;
 261         }
 262
 263       /* Skip non-innermost loops.  */
 264       if (loop->inner)
 265         {
 266           if (dump_file)
 267             fprintf (dump_file, ";; Not considering loop, is not innermost\n");
 268           loop = next;
 269           continue;
 270         }
 271
 272       loop->ninsns = num_loop_insns (loop);
 273       loop->av_ninsns = average_num_loop_insns (loop);
 274
 275       /* Try transformations one by one in decreasing order of
 276          priority.  */
 277
 278       decide_unroll_constant_iterations (loop, flags);
 279       if (loop->lpt_decision.decision == LPT_NONE)
 280         decide_unroll_runtime_iterations (loop, flags);
 281       if (loop->lpt_decision.decision == LPT_NONE)
 282         decide_unroll_stupid (loop, flags);
 283       if (loop->lpt_decision.decision == LPT_NONE)
 284         decide_peel_simple (loop, flags);
 285
 286       loop = next;
 287     }
 288 }
 289
 290 /* Decide whether the LOOP is once rolling and suitable for complete
 291    peeling.  */
 292 static void
 293 decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
 294 {
 295   struct niter_desc *desc;
 296
 297   if (dump_file)
 298     fprintf (dump_file, "\n;; Considering peeling once rolling loop\n");
 299
 300   /* Is the loop small enough?  */
 301   if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS) < loop->ninsns)
 302     {
 303       if (dump_file)
 304         fprintf (dump_file, ";; Not considering loop, is too big\n");
 305       return;
 306     }
 307
 308   /* Check for simple loops.  */
 309   desc = get_simple_loop_desc (loop);
 310
 311   /* Check number of iterations.  */
 312   if (!desc->simple_p
 313       || desc->assumptions
 314       || !desc->const_iter
 315       || desc->niter != 0)
 316     {
 317       if (dump_file)
 318         fprintf (dump_file,
 319                  ";; Unable to prove that the loop rolls exactly once\n");
 320       return;
 321     }
 322
 323   /* Success.  */
 324   if (dump_file)
 325     fprintf (dump_file, ";; Decided to peel exactly once rolling loop\n");
 326   loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
 327 }
 328
 329 /* Decide whether the LOOP is suitable for complete peeling.  */
 330 static void
 331 decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
 332 {
 333   unsigned npeel;
 334   struct niter_desc *desc;
 335
 336   if (dump_file)
 337     fprintf (dump_file, "\n;; Considering peeling completely\n");
 338
 339   /* Skip non-innermost loops.  */
 340   if (loop->inner)
 341     {
 342       if (dump_file)
 343         fprintf (dump_file, ";; Not considering loop, is not innermost\n");
 344       return;
 345     }
 346
 347   /* Do not peel cold areas.  */
 348   if (!maybe_hot_bb_p (loop->header))
 349     {
 350       if (dump_file)
 351         fprintf (dump_file, ";; Not considering loop, cold area\n");
 352       return;
 353     }
 354
 355   /* Can the loop be manipulated?  */
 356   if (!can_duplicate_loop_p (loop))
 357     {
 358       if (dump_file)
 359         fprintf (dump_file,
 360                  ";; Not considering loop, cannot duplicate\n");
 361       return;
 362     }
 363
 364   /* npeel = number of iterations to peel.  */
 365   npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns;
 366   if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
 367     npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
 368
 369   /* Is the loop small enough?  */
 370   if (!npeel)
 371     {
 372       if (dump_file)
 373         fprintf (dump_file, ";; Not considering loop, is too big\n");
 374       return;
 375     }
 376
 377   /* Check for simple loops.  */
 378   desc = get_simple_loop_desc (loop);
 379
 380   /* Check number of iterations.  */
 381   if (!desc->simple_p
 382       || desc->assumptions
 383       || !desc->const_iter)
 384     {
 385       if (dump_file)
 386         fprintf (dump_file,
 387                  ";; Unable to prove that the loop iterates constant times\n");
 388       return;
 389     }
 390
 391   if (desc->niter > npeel - 1)
 392     {
 393       if (dump_file)
 394         {
 395           fprintf (dump_file,
 396                    ";; Not peeling loop completely, rolls too much (");
 397           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
 398           fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel);
 399         }
 400       return;
 401     }
 402
 403   /* Success.  */
 404   if (dump_file)
 405     fprintf (dump_file, ";; Decided to peel loop completely\n");
 406   loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
 407 }
 408
 409 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
 410    completely.  The transformation done:
 411
 412    for (i = 0; i < 4; i++)
 413      body;
 414
 415    ==>
 416
 417    i = 0;
 418    body; i++;
 419    body; i++;
 420    body; i++;
 421    body; i++;
 422    */
 423 static void
 424 peel_loop_completely (struct loops *loops, struct loop *loop)
 425 {
 426   sbitmap wont_exit;
 427   unsigned HOST_WIDE_INT npeel;
 428   unsigned n_remove_edges, i;
 429   edge *remove_edges, ei;
 430   struct niter_desc *desc = get_simple_loop_desc (loop);
 431
 432   npeel = desc->niter;
 433
 434   if (npeel)
 435     {
 436       int ok;
 437
 438       wont_exit = sbitmap_alloc (npeel + 1);
 439       sbitmap_ones (wont_exit);
 440       RESET_BIT (wont_exit, 0);
 441       if (desc->noloop_assumptions)
 442         RESET_BIT (wont_exit, 1);
 443
 444       remove_edges = xcalloc (npeel, sizeof (edge));
 445       n_remove_edges = 0;
 446
 447       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 448                                           loops, npeel,
 449                                           wont_exit, desc->out_edge,
 450                                           remove_edges, &n_remove_edges,
 451                                           DLTHE_FLAG_UPDATE_FREQ);
 452       gcc_assert (ok);
 453
 454       free (wont_exit);
 455
 456       /* Remove the exit edges.  */
 457       for (i = 0; i < n_remove_edges; i++)
 458         remove_path (loops, remove_edges[i]);
 459       free (remove_edges);
 460     }
 461
 462   ei = desc->in_edge;
 463   free_simple_loop_desc (loop);
 464
 465   /* Now remove the unreachable part of the last iteration and cancel
 466      the loop.  */
 467   remove_path (loops, ei);
 468
 469   if (dump_file)
 470     fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
 471 }
 472
 473 /* Decide whether to unroll LOOP iterating constant number of times
 474    and how much.  */
 475
 476 static void
 477 decide_unroll_constant_iterations (struct loop *loop, int flags)
 478 {
 479   unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
 480   struct niter_desc *desc;
 481
 482   if (!(flags & UAP_UNROLL))
 483     {
 484       /* We were not asked to, just return back silently.  */
 485       return;
 486     }
 487
 488   if (dump_file)
 489     fprintf (dump_file,
 490              "\n;; Considering unrolling loop with constant "
 491              "number of iterations\n");
 492
 493   /* nunroll = total number of copies of the original loop body in
 494      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
 495   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
 496   nunroll_by_av
 497     = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
 498   if (nunroll > nunroll_by_av)
 499     nunroll = nunroll_by_av;
 500   if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
 501     nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
 502
 503   /* Skip big loops.  */
 504   if (nunroll <= 1)
 505     {
 506       if (dump_file)
 507         fprintf (dump_file, ";; Not considering loop, is too big\n");
 508       return;
 509     }
 510
 511   /* Check for simple loops.  */
 512   desc = get_simple_loop_desc (loop);
 513
 514   /* Check number of iterations.  */
 515   if (!desc->simple_p || !desc->const_iter || desc->assumptions)
 516     {
 517       if (dump_file)
 518         fprintf (dump_file,
 519                  ";; Unable to prove that the loop iterates constant times\n");
 520       return;
 521     }
 522
 523   /* Check whether the loop rolls enough to consider.  */
 524   if (desc->niter < 2 * nunroll)
 525     {
 526       if (dump_file)
 527         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
 528       return;
 529     }
 530
 531   /* Success; now compute number of iterations to unroll.  We alter
 532      nunroll so that as few as possible copies of loop body are
 533      necessary, while still not decreasing the number of unrollings
 534      too much (at most by 1).  */
 535   best_copies = 2 * nunroll + 10;
 536
 537   i = 2 * nunroll + 2;
 538   if (i - 1 >= desc->niter)
 539     i = desc->niter - 2;
 540
 541   for (; i >= nunroll - 1; i--)
 542     {
 543       unsigned exit_mod = desc->niter % (i + 1);
 544
 545       if (!loop_exit_at_end_p (loop))
 546         n_copies = exit_mod + i + 1;
 547       else if (exit_mod != (unsigned) i
 548                || desc->noloop_assumptions != NULL_RTX)
 549         n_copies = exit_mod + i + 2;
 550       else
 551         n_copies = i + 1;
 552
 553       if (n_copies < best_copies)
 554         {
 555           best_copies = n_copies;
 556           best_unroll = i;
 557         }
 558     }
 559
 560   if (dump_file)
 561     fprintf (dump_file, ";; max_unroll %d (%d copies, initial %d).\n",
 562              best_unroll + 1, best_copies, nunroll);
 563
 564   loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
 565   loop->lpt_decision.times = best_unroll;
 566
 567   if (dump_file)
 568     fprintf (dump_file,
 569              ";; Decided to unroll the constant times rolling loop, %d times.\n",
 570              loop->lpt_decision.times);
 571 }
 572
 573 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
 574    times.  The transformation does this:
 575
 576    for (i = 0; i < 102; i++)
 577      body;
 578
 579    ==>
 580
 581    i = 0;
 582    body; i++;
 583    body; i++;
 584    while (i < 102)
 585      {
 586        body; i++;
 587        body; i++;
 588        body; i++;
 589        body; i++;
 590      }
 591   */
 592 static void
 593 unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
 594 {
 595   unsigned HOST_WIDE_INT niter;
 596   unsigned exit_mod;
 597   sbitmap wont_exit;
 598   unsigned n_remove_edges, i;
 599   edge *remove_edges;
 600   unsigned max_unroll = loop->lpt_decision.times;
 601   struct niter_desc *desc = get_simple_loop_desc (loop);
 602   bool exit_at_end = loop_exit_at_end_p (loop);
 603   int ok;
 604
 605   niter = desc->niter;
 606
 607   /* Should not assert out here (such loop should be peeled instead).  */
 608   gcc_assert (niter > max_unroll + 1);
 609
 610   exit_mod = niter % (max_unroll + 1);
 611
 612   wont_exit = sbitmap_alloc (max_unroll + 1);
 613   sbitmap_ones (wont_exit);
 614
 615   remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
 616   n_remove_edges = 0;
 617
 618   if (!exit_at_end)
 619     {
 620       /* The exit is not at the end of the loop; leave exit test
 621          in the first copy, so that the loops that start with test
 622          of exit condition have continuous body after unrolling.  */
 623
 624       if (dump_file)
 625         fprintf (dump_file, ";; Condition on beginning of loop.\n");
 626
 627       /* Peel exit_mod iterations.  */
 628       RESET_BIT (wont_exit, 0);
 629       if (desc->noloop_assumptions)
 630         RESET_BIT (wont_exit, 1);
 631
 632       if (exit_mod)
 633         {
 634           int ok;
 635
 636           ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 637                                               loops, exit_mod,
 638                                               wont_exit, desc->out_edge,
 639                                               remove_edges, &n_remove_edges,
 640                                               DLTHE_FLAG_UPDATE_FREQ);
 641           gcc_assert (ok);
 642
 643           desc->noloop_assumptions = NULL_RTX;
 644           desc->niter -= exit_mod;
 645           desc->niter_max -= exit_mod;
 646         }
 647
 648       SET_BIT (wont_exit, 1);
 649     }
 650   else
 651     {
 652       /* Leave exit test in last copy, for the same reason as above if
 653          the loop tests the condition at the end of loop body.  */
 654
 655       if (dump_file)
 656         fprintf (dump_file, ";; Condition on end of loop.\n");
 657
 658       /* We know that niter >= max_unroll + 2; so we do not need to care of
 659          case when we would exit before reaching the loop.  So just peel
 660          exit_mod + 1 iterations.  */
 661       if (exit_mod != max_unroll
 662           || desc->noloop_assumptions)
 663         {
 664           int ok;
 665
 666           RESET_BIT (wont_exit, 0);
 667           if (desc->noloop_assumptions)
 668             RESET_BIT (wont_exit, 1);
 669
 670           ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 671                                               loops, exit_mod + 1,
 672                                               wont_exit, desc->out_edge,
 673                                               remove_edges, &n_remove_edges,
 674                                               DLTHE_FLAG_UPDATE_FREQ);
 675           gcc_assert (ok);
 676
 677           desc->niter -= exit_mod + 1;
 678           desc->niter_max -= exit_mod + 1;
 679           desc->noloop_assumptions = NULL_RTX;
 680
 681           SET_BIT (wont_exit, 0);
 682           SET_BIT (wont_exit, 1);
 683         }
 684
 685       RESET_BIT (wont_exit, max_unroll);
 686     }
 687
 688   /* Now unroll the loop.  */
 689   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
 690                                       loops, max_unroll,
 691                                       wont_exit, desc->out_edge,
 692                                       remove_edges, &n_remove_edges,
 693                                       DLTHE_FLAG_UPDATE_FREQ);
 694   gcc_assert (ok);
 695
 696   free (wont_exit);
 697
 698   if (exit_at_end)
 699     {
 700       basic_block exit_block = desc->in_edge->src->rbi->copy;
 701       /* Find a new in and out edge; they are in the last copy we have made.  */
 702
 703       if (exit_block->succ->dest == desc->out_edge->dest)
 704         {
 705           desc->out_edge = exit_block->succ;
 706           desc->in_edge = exit_block->succ->succ_next;
 707         }
 708       else
 709         {
 710           desc->out_edge = exit_block->succ->succ_next;
 711           desc->in_edge = exit_block->succ;
 712         }
 713     }
 714
 715   desc->niter /= max_unroll + 1;
 716   desc->niter_max /= max_unroll + 1;
 717   desc->niter_expr = GEN_INT (desc->niter);
 718
 719   /* Remove the edges.  */
 720   for (i = 0; i < n_remove_edges; i++)
 721     remove_path (loops, remove_edges[i]);
 722   free (remove_edges);
 723
 724   if (dump_file)
 725     fprintf (dump_file,
 726              ";; Unrolled loop %d times, constant # of iterations %i insns\n",
 727              max_unroll, num_loop_insns (loop));
 728 }
 729
 730 /* Decide whether to unroll LOOP iterating runtime computable number of times
 731    and how much.  */
 732 static void
 733 decide_unroll_runtime_iterations (struct loop *loop, int flags)
 734 {
 735   unsigned nunroll, nunroll_by_av, i;
 736   struct niter_desc *desc;
 737
 738   if (!(flags & UAP_UNROLL))
 739     {
 740       /* We were not asked to, just return back silently.  */
 741       return;
 742     }
 743
 744   if (dump_file)
 745     fprintf (dump_file,
 746              "\n;; Considering unrolling loop with runtime "
 747              "computable number of iterations\n");
 748
 749   /* nunroll = total number of copies of the original loop body in
 750      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
 751   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
 752   nunroll_by_av = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
 753   if (nunroll > nunroll_by_av)
 754     nunroll = nunroll_by_av;
 755   if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
 756     nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
 757
 758   /* Skip big loops.  */
 759   if (nunroll <= 1)
 760     {
 761       if (dump_file)
 762         fprintf (dump_file, ";; Not considering loop, is too big\n");
 763       return;
 764     }
 765
 766   /* Check for simple loops.  */
 767   desc = get_simple_loop_desc (loop);
 768
 769   /* Check simpleness.  */
 770   if (!desc->simple_p || desc->assumptions)
 771     {
 772       if (dump_file)
 773         fprintf (dump_file,
 774                  ";; Unable to prove that the number of iterations "
 775                  "can be counted in runtime\n");
 776       return;
 777     }
 778
 779   if (desc->const_iter)
 780     {
 781       if (dump_file)
 782         fprintf (dump_file, ";; Loop iterates constant times\n");
 783       return;
 784     }
 785
 786   /* If we have profile feedback, check whether the loop rolls.  */
 787   if (loop->header->count && expected_loop_iterations (loop) < 2 * nunroll)
 788     {
 789       if (dump_file)
 790         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
 791       return;
 792     }
 793
 794   /* Success; now force nunroll to be power of 2, as we are unable to
 795      cope with overflows in computation of number of iterations.  */
 796   for (i = 1; 2 * i <= nunroll; i *= 2)
 797     continue;
 798
 799   loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
 800   loop->lpt_decision.times = i - 1;
 801
 802   if (dump_file)
 803     fprintf (dump_file,
 804              ";; Decided to unroll the runtime computable "
 805              "times rolling loop, %d times.\n",
 806              loop->lpt_decision.times);
 807 }
 808
 809 /* Unroll LOOP for that we are able to count number of iterations in runtime
 810    LOOP->LPT_DECISION.TIMES + 1 times.  The transformation does this (with some
 811    extra care for case n < 0):
 812
 813    for (i = 0; i < n; i++)
 814      body;
 815
 816    ==>
 817
 818    i = 0;
 819    mod = n % 4;
 820
 821    switch (mod)
 822      {
 823        case 3:
 824          body; i++;
 825        case 2:
 826          body; i++;
 827        case 1:
 828          body; i++;
 829        case 0: ;
 830      }
 831
 832    while (i < n)
 833      {
 834        body; i++;
 835        body; i++;
 836        body; i++;
 837        body; i++;
 838      }
 839    */
 840 static void
 841 unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
 842 {
 843   rtx old_niter, niter, init_code, branch_code, tmp;
 844   unsigned i, j, p;
 845   basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
 846   unsigned n_dom_bbs;
 847   sbitmap wont_exit;
 848   int may_exit_copy;
 849   unsigned n_peel, n_remove_edges;
 850   edge *remove_edges, e;
 851   bool extra_zero_check, last_may_exit;
 852   unsigned max_unroll = loop->lpt_decision.times;
 853   struct niter_desc *desc = get_simple_loop_desc (loop);
 854   bool exit_at_end = loop_exit_at_end_p (loop);
 855   int ok;
 856
 857   /* Remember blocks whose dominators will have to be updated.  */
 858   dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
 859   n_dom_bbs = 0;
 860
 861   body = get_loop_body (loop);
 862   for (i = 0; i < loop->num_nodes; i++)
 863     {
 864       unsigned nldom;
 865       basic_block *ldom;
 866
 867       nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
 868       for (j = 0; j < nldom; j++)
 869         if (!flow_bb_inside_loop_p (loop, ldom[j]))
 870           dom_bbs[n_dom_bbs++] = ldom[j];
 871
 872       free (ldom);
 873     }
 874   free (body);
 875
 876   if (!exit_at_end)
 877     {
 878       /* Leave exit in first copy (for explanation why see comment in
 879          unroll_loop_constant_iterations).  */
 880       may_exit_copy = 0;
 881       n_peel = max_unroll - 1;
 882       extra_zero_check = true;
 883       last_may_exit = false;
 884     }
 885   else
 886     {
 887       /* Leave exit in last copy (for explanation why see comment in
 888          unroll_loop_constant_iterations).  */
 889       may_exit_copy = max_unroll;
 890       n_peel = max_unroll;
 891       extra_zero_check = false;
 892       last_may_exit = true;
 893     }
 894
 895   /* Get expression for number of iterations.  */
 896   start_sequence ();
 897   old_niter = niter = gen_reg_rtx (desc->mode);
 898   tmp = force_operand (copy_rtx (desc->niter_expr), niter);
 899   if (tmp != niter)
 900     emit_move_insn (niter, tmp);
 901
 902   /* Count modulo by ANDing it with max_unroll; we use the fact that
 903      the number of unrollings is a power of two, and thus this is correct
 904      even if there is overflow in the computation.  */
 905   niter = expand_simple_binop (desc->mode, AND,
 906                                niter,
 907                                GEN_INT (max_unroll),
 908                                NULL_RTX, 0, OPTAB_LIB_WIDEN);
 909
 910   init_code = get_insns ();
 911   end_sequence ();
 912
 913   /* Precondition the loop.  */
 914   loop_split_edge_with (loop_preheader_edge (loop), init_code);
 915
 916   remove_edges = xcalloc (max_unroll + n_peel + 1, sizeof (edge));
 917   n_remove_edges = 0;
 918
 919   wont_exit = sbitmap_alloc (max_unroll + 2);
 920
 921   /* Peel the first copy of loop body (almost always we must leave exit test
 922      here; the only exception is when we have extra zero check and the number
 923      of iterations is reliable.  Also record the place of (possible) extra
 924      zero check.  */
 925   sbitmap_zero (wont_exit);
 926   if (extra_zero_check
 927       && !desc->noloop_assumptions)
 928     SET_BIT (wont_exit, 1);
 929   ezc_swtch = loop_preheader_edge (loop)->src;
 930   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 931                                       loops, 1,
 932                                       wont_exit, desc->out_edge,
 933                                       remove_edges, &n_remove_edges,
 934                                       DLTHE_FLAG_UPDATE_FREQ);
 935   gcc_assert (ok);
 936
 937   /* Record the place where switch will be built for preconditioning.  */
 938   swtch = loop_split_edge_with (loop_preheader_edge (loop),
 939                                 NULL_RTX);
 940
 941   for (i = 0; i < n_peel; i++)
 942     {
 943       /* Peel the copy.  */
 944       sbitmap_zero (wont_exit);
 945       if (i != n_peel - 1 || !last_may_exit)
 946         SET_BIT (wont_exit, 1);
 947       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 948                                           loops, 1,
 949                                           wont_exit, desc->out_edge,
 950                                           remove_edges, &n_remove_edges,
 951                                           DLTHE_FLAG_UPDATE_FREQ);
 952       gcc_assert (ok);
 953
 954       /* Create item for switch.  */
 955       j = n_peel - i - (extra_zero_check ? 0 : 1);
 956       p = REG_BR_PROB_BASE / (i + 2);
 957
 958       preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 959       branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
 960                                           block_label (preheader), p, NULL_RTX);
 961
 962       swtch = loop_split_edge_with (swtch->pred, branch_code);
 963       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
 964       swtch->succ->probability = REG_BR_PROB_BASE - p;
 965       e = make_edge (swtch, preheader,
 966                      swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
 967       e->probability = p;
 968     }
 969
 970   if (extra_zero_check)
 971     {
 972       /* Add branch for zero iterations.  */
 973       p = REG_BR_PROB_BASE / (max_unroll + 1);
 974       swtch = ezc_swtch;
 975       preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
 976       branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
 977                                           block_label (preheader), p, NULL_RTX);
 978
 979       swtch = loop_split_edge_with (swtch->succ, branch_code);
 980       set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
 981       swtch->succ->probability = REG_BR_PROB_BASE - p;
 982       e = make_edge (swtch, preheader,
 983                      swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
 984       e->probability = p;
 985     }
 986
 987   /* Recount dominators for outer blocks.  */
 988   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
 989
 990   /* And unroll loop.  */
 991
 992   sbitmap_ones (wont_exit);
 993   RESET_BIT (wont_exit, may_exit_copy);
 994
 995   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
 996                                       loops, max_unroll,
 997                                       wont_exit, desc->out_edge,
 998                                       remove_edges, &n_remove_edges,
 999                                       DLTHE_FLAG_UPDATE_FREQ);
1000   gcc_assert (ok);
1001
1002   free (wont_exit);
1003
1004   if (exit_at_end)
1005     {
1006       basic_block exit_block = desc->in_edge->src->rbi->copy;
1007       /* Find a new in and out edge; they are in the last copy we have made.  */
1008
1009       if (exit_block->succ->dest == desc->out_edge->dest)
1010         {
1011           desc->out_edge = exit_block->succ;
1012           desc->in_edge = exit_block->succ->succ_next;
1013         }
1014       else
1015         {
1016           desc->out_edge = exit_block->succ->succ_next;
1017           desc->in_edge = exit_block->succ;
1018         }
1019     }
1020
1021   /* Remove the edges.  */
1022   for (i = 0; i < n_remove_edges; i++)
1023     remove_path (loops, remove_edges[i]);
1024   free (remove_edges);
1025
1026   /* We must be careful when updating the number of iterations due to
1027      preconditioning and the fact that the value must be valid at entry
1028      of the loop.  After passing through the above code, we see that
1029      the correct new number of iterations is this:  */
1030   gcc_assert (!desc->const_iter);
1031   desc->niter_expr =
1032     simplify_gen_binary (UDIV, desc->mode, old_niter, GEN_INT (max_unroll + 1));
1033   desc->niter_max /= max_unroll + 1;
1034   if (exit_at_end)
1035     {
1036       desc->niter_expr =
1037         simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
1038       desc->noloop_assumptions = NULL_RTX;
1039       desc->niter_max--;
1040     }
1041
1042   if (dump_file)
1043     fprintf (dump_file,
1044              ";; Unrolled loop %d times, counting # of iterations "
1045              "in runtime, %i insns\n",
1046              max_unroll, num_loop_insns (loop));
1047 }
1048
1049 /* Decide whether to simply peel LOOP and how much.  */
1050 static void
1051 decide_peel_simple (struct loop *loop, int flags)
1052 {
1053   unsigned npeel;
1054   struct niter_desc *desc;
1055
1056   if (!(flags & UAP_PEEL))
1057     {
1058       /* We were not asked to, just return back silently.  */
1059       return;
1060     }
1061
1062   if (dump_file)
1063     fprintf (dump_file, "\n;; Considering simply peeling loop\n");
1064
1065   /* npeel = number of iterations to peel.  */
1066   npeel = PARAM_VALUE (PARAM_MAX_PEELED_INSNS) / loop->ninsns;
1067   if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES))
1068     npeel = PARAM_VALUE (PARAM_MAX_PEEL_TIMES);
1069
1070   /* Skip big loops.  */
1071   if (!npeel)
1072     {
1073       if (dump_file)
1074         fprintf (dump_file, ";; Not considering loop, is too big\n");
1075       return;
1076     }
1077
1078   /* Check for simple loops.  */
1079   desc = get_simple_loop_desc (loop);
1080
1081   /* Check number of iterations.  */
1082   if (desc->simple_p && !desc->assumptions && desc->const_iter)
1083     {
1084       if (dump_file)
1085         fprintf (dump_file, ";; Loop iterates constant times\n");
1086       return;
1087     }
1088
1089   /* Do not simply peel loops with branches inside -- it increases number
1090      of mispredicts.  */
1091   if (num_loop_branches (loop) > 1)
1092     {
1093       if (dump_file)
1094         fprintf (dump_file, ";; Not peeling, contains branches\n");
1095       return;
1096     }
1097
1098   if (loop->header->count)
1099     {
1100       unsigned niter = expected_loop_iterations (loop);
1101       if (niter + 1 > npeel)
1102         {
1103           if (dump_file)
1104             {
1105               fprintf (dump_file, ";; Not peeling loop, rolls too much (");
1106               fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1107                        (HOST_WIDEST_INT) (niter + 1));
1108               fprintf (dump_file, " iterations > %d [maximum peelings])\n",
1109                        npeel);
1110             }
1111           return;
1112         }
1113       npeel = niter + 1;
1114     }
1115   else
1116     {
1117       /* For now we have no good heuristics to decide whether loop peeling
1118          will be effective, so disable it.  */
1119       if (dump_file)
1120         fprintf (dump_file,
1121                  ";; Not peeling loop, no evidence it will be profitable\n");
1122       return;
1123     }
1124
1125   /* Success.  */
1126   loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
1127   loop->lpt_decision.times = npeel;
1128
1129   if (dump_file)
1130     fprintf (dump_file, ";; Decided to simply peel the loop, %d times.\n",
1131              loop->lpt_decision.times);
1132 }
1133
1134 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times.  The transformation:
1135    while (cond)
1136      body;
1137
1138    ==>
1139
1140    if (!cond) goto end;
1141    body;
1142    if (!cond) goto end;
1143    body;
1144    while (cond)
1145      body;
1146    end: ;
1147    */
1148 static void
1149 peel_loop_simple (struct loops *loops, struct loop *loop)
1150 {
1151   sbitmap wont_exit;
1152   unsigned npeel = loop->lpt_decision.times;
1153   struct niter_desc *desc = get_simple_loop_desc (loop);
1154   int ok;
1155
1156   wont_exit = sbitmap_alloc (npeel + 1);
1157   sbitmap_zero (wont_exit);
1158
1159   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1160                                       loops, npeel, wont_exit,
1161                                       NULL, NULL, NULL,
1162                                       DLTHE_FLAG_UPDATE_FREQ);
1163   gcc_assert (ok);
1164
1165   free (wont_exit);
1166
1167   if (desc->simple_p)
1168     {
1169       if (desc->const_iter)
1170         {
1171           desc->niter -= npeel;
1172           desc->niter_expr = GEN_INT (desc->niter);
1173           desc->noloop_assumptions = NULL_RTX;
1174         }
1175       else
1176         {
1177           /* We cannot just update niter_expr, as its value might be clobbered
1178              inside loop.  We could handle this by counting the number into
1179              temporary just like we do in runtime unrolling, but it does not
1180              seem worthwhile.  */
1181           free_simple_loop_desc (loop);
1182         }
1183     }
1184   if (dump_file)
1185     fprintf (dump_file, ";; Peeling loop %d times\n", npeel);
1186 }
1187
1188 /* Decide whether to unroll LOOP stupidly and how much.  */
1189 static void
1190 decide_unroll_stupid (struct loop *loop, int flags)
1191 {
1192   unsigned nunroll, nunroll_by_av, i;
1193   struct niter_desc *desc;
1194
1195   if (!(flags & UAP_UNROLL_ALL))
1196     {
1197       /* We were not asked to, just return back silently.  */
1198       return;
1199     }
1200
1201   if (dump_file)
1202     fprintf (dump_file, "\n;; Considering unrolling loop stupidly\n");
1203
1204   /* nunroll = total number of copies of the original loop body in
1205      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
1206   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
1207   nunroll_by_av
1208     = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
1209   if (nunroll > nunroll_by_av)
1210     nunroll = nunroll_by_av;
1211   if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
1212     nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1213
1214   /* Skip big loops.  */
1215   if (nunroll <= 1)
1216     {
1217       if (dump_file)
1218         fprintf (dump_file, ";; Not considering loop, is too big\n");
1219       return;
1220     }
1221
1222   /* Check for simple loops.  */
1223   desc = get_simple_loop_desc (loop);
1224
1225   /* Check simpleness.  */
1226   if (desc->simple_p && !desc->assumptions)
1227     {
1228       if (dump_file)
1229         fprintf (dump_file, ";; The loop is simple\n");
1230       return;
1231     }
1232
1233   /* Do not unroll loops with branches inside -- it increases number
1234      of mispredicts.  */
1235   if (num_loop_branches (loop) > 1)
1236     {
1237       if (dump_file)
1238         fprintf (dump_file, ";; Not unrolling, contains branches\n");
1239       return;
1240     }
1241
1242   /* If we have profile feedback, check whether the loop rolls.  */
1243   if (loop->header->count
1244       && expected_loop_iterations (loop) < 2 * nunroll)
1245     {
1246       if (dump_file)
1247         fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
1248       return;
1249     }
1250
1251   /* Success.  Now force nunroll to be power of 2, as it seems that this
1252      improves results (partially because of better alignments, partially
1253      because of some dark magic).  */
1254   for (i = 1; 2 * i <= nunroll; i *= 2)
1255     continue;
1256
1257   loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1258   loop->lpt_decision.times = i - 1;
1259
1260   if (dump_file)
1261     fprintf (dump_file,
1262              ";; Decided to unroll the loop stupidly, %d times.\n",
1263              loop->lpt_decision.times);
1264 }
1265
1266 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times.  The transformation:
1267    while (cond)
1268      body;
1269
1270    ==>
1271
1272    while (cond)
1273      {
1274        body;
1275        if (!cond) break;
1276        body;
1277        if (!cond) break;
1278        body;
1279        if (!cond) break;
1280        body;
1281      }
1282    */
1283 static void
1284 unroll_loop_stupid (struct loops *loops, struct loop *loop)
1285 {
1286   sbitmap wont_exit;
1287   unsigned nunroll = loop->lpt_decision.times;
1288   struct niter_desc *desc = get_simple_loop_desc (loop);
1289   int ok;
1290
1291   wont_exit = sbitmap_alloc (nunroll + 1);
1292   sbitmap_zero (wont_exit);
1293
1294   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1295                                       loops, nunroll, wont_exit,
1296                                       NULL, NULL, NULL,
1297                                       DLTHE_FLAG_UPDATE_FREQ);
1298   gcc_assert (ok);
1299
1300   free (wont_exit);
1301
1302   if (desc->simple_p)
1303     {
1304       /* We indeed may get here provided that there are nontrivial assumptions
1305          for a loop to be really simple.  We could update the counts, but the
1306          problem is that we are unable to decide which exit will be taken
1307          (not really true in case the number of iterations is constant,
1308          but noone will do anything with this information, so we do not
1309          worry about it).  */
1310       desc->simple_p = false;
1311     }
1312
1313   if (dump_file)
1314     fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
1315              nunroll, num_loop_insns (loop));
1316 }