gcc/loop-unroll.c

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