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