gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002-2013 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "rtl.h"
  25 #include "tree.h"
  26 #include "regs.h"
  27 #include "obstack.h"
  28 #include "basic-block.h"
  29 #include "cfgloop.h"
  30 #include "tree-pass.h"
  31 #include "flags.h"
  32 #include "df.h"
  33 #include "ggc.h"
  34 #include "gimple.h"
  35 #include "tree-ssa-loop-niter.h"
  36
  37 \f
  38 /* Apply FLAGS to the loop state.  */
  39
  40 static void
  41 apply_loop_flags (unsigned flags)
  42 {
  43   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  44     {
  45       /* If the loops may have multiple latches, we cannot canonicalize
  46          them further (and most of the loop manipulation functions will
  47          not work).  However, we avoid modifying cfg, which some
  48          passes may want.  */
  49       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  50                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  51       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
  52     }
  53   else
  54     disambiguate_loops_with_multiple_latches ();
  55
  56   /* Create pre-headers.  */
  57   if (flags & LOOPS_HAVE_PREHEADERS)
  58     {
  59       int cp_flags = CP_SIMPLE_PREHEADERS;
  60
  61       if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
  62         cp_flags |= CP_FALLTHRU_PREHEADERS;
  63
  64       create_preheaders (cp_flags);
  65     }
  66
  67   /* Force all latches to have only single successor.  */
  68   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  69     force_single_succ_latches ();
  70
  71   /* Mark irreducible loops.  */
  72   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  73     mark_irreducible_loops ();
  74
  75   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  76     record_loop_exits ();
  77 }
  78
  79 /* Initialize loop structures.  This is used by the tree and RTL loop
  80    optimizers.  FLAGS specify what properties to compute and/or ensure for
  81    loops.  */
  82
  83 void
  84 loop_optimizer_init (unsigned flags)
  85 {
  86   timevar_push (TV_LOOP_INIT);
  87
  88   if (!current_loops)
  89     {
  90       gcc_assert (!(cfun->curr_properties & PROP_loops));
  91
  92       /* Find the loops.  */
  93       current_loops = flow_loops_find (NULL);
  94     }
  95   else
  96     {
  97       bool recorded_exits = loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS);
  98
  99       gcc_assert (cfun->curr_properties & PROP_loops);
 100
 101       /* Ensure that the dominators are computed, like flow_loops_find does.  */
 102       calculate_dominance_info (CDI_DOMINATORS);
 103
 104       if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
 105         {
 106           loops_state_clear (~0U);
 107           fix_loop_structure (NULL);
 108         }
 109
 110 #ifdef ENABLE_CHECKING
 111       else
 112         verify_loop_structure ();
 113 #endif
 114
 115       /* Clear all flags.  */
 116       if (recorded_exits)
 117         release_recorded_exits ();
 118       loops_state_clear (~0U);
 119     }
 120
 121   /* Apply flags to loops.  */
 122   apply_loop_flags (flags);
 123
 124   /* Dump loops.  */
 125   flow_loops_dump (dump_file, NULL, 1);
 126
 127 #ifdef ENABLE_CHECKING
 128   verify_loop_structure ();
 129 #endif
 130
 131   timevar_pop (TV_LOOP_INIT);
 132 }
 133
 134 /* Finalize loop structures.  */
 135
 136 void
 137 loop_optimizer_finalize (void)
 138 {
 139   loop_iterator li;
 140   struct loop *loop;
 141   basic_block bb;
 142
 143   timevar_push (TV_LOOP_FINI);
 144
 145   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 146     release_recorded_exits ();
 147
 148   free_numbers_of_iterations_estimates ();
 149
 150   /* If we should preserve loop structure, do not free it but clear
 151      flags that advanced properties are there as we are not preserving
 152      that in full.  */
 153   if (cfun->curr_properties & PROP_loops)
 154     {
 155       loops_state_clear (LOOP_CLOSED_SSA
 156                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 157                          | LOOPS_HAVE_PREHEADERS
 158                          | LOOPS_HAVE_SIMPLE_LATCHES
 159                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 160       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 161       goto loop_fini_done;
 162     }
 163
 164   gcc_assert (current_loops != NULL);
 165
 166   FOR_EACH_LOOP (li, loop, 0)
 167     {
 168       free_simple_loop_desc (loop);
 169     }
 170
 171   /* Clean up.  */
 172   flow_loops_free (current_loops);
 173   ggc_free (current_loops);
 174   current_loops = NULL;
 175
 176   FOR_ALL_BB (bb)
 177     {
 178       bb->loop_father = NULL;
 179     }
 180
 181 loop_fini_done:
 182   timevar_pop (TV_LOOP_FINI);
 183 }
 184
 185 /* The structure of loops might have changed.  Some loops might get removed
 186    (and their headers and latches were set to NULL), loop exists might get
 187    removed (thus the loop nesting may be wrong), and some blocks and edges
 188    were changed (so the information about bb --> loop mapping does not have
 189    to be correct).  But still for the remaining loops the header dominates
 190    the latch, and loops did not get new subloops (new loops might possibly
 191    get created, but we are not interested in them).  Fix up the mess.
 192
 193    If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
 194    marked in it.
 195
 196    Returns the number of new discovered loops.  */
 197
 198 unsigned
 199 fix_loop_structure (bitmap changed_bbs)
 200 {
 201   basic_block bb;
 202   int record_exits = 0;
 203   loop_iterator li;
 204   struct loop *loop;
 205   unsigned old_nloops, i;
 206
 207   timevar_push (TV_LOOP_INIT);
 208
 209   /* We need exact and fast dominance info to be available.  */
 210   gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
 211
 212   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 213     {
 214       release_recorded_exits ();
 215       record_exits = LOOPS_HAVE_RECORDED_EXITS;
 216     }
 217
 218   /* Remember the depth of the blocks in the loop hierarchy, so that we can
 219      recognize blocks whose loop nesting relationship has changed.  */
 220   if (changed_bbs)
 221     FOR_EACH_BB (bb)
 222       bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
 223
 224   /* Remove the dead loops from structures.  We start from the innermost
 225      loops, so that when we remove the loops, we know that the loops inside
 226      are preserved, and do not waste time relinking loops that will be
 227      removed later.  */
 228   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
 229     {
 230       /* Detect the case that the loop is no longer present even though
 231          it wasn't marked for removal.
 232          ???  If we do that we can get away with not marking loops for
 233          removal at all.  And possibly avoid some spurious removals.  */
 234       if (loop->header
 235           && bb_loop_header_p (loop->header))
 236         continue;
 237
 238       if (dump_file && (dump_flags & TDF_DETAILS))
 239         fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
 240                  loop->num);
 241
 242       while (loop->inner)
 243         {
 244           struct loop *ploop = loop->inner;
 245           flow_loop_tree_node_remove (ploop);
 246           flow_loop_tree_node_add (loop_outer (loop), ploop);
 247         }
 248
 249       /* Remove the loop.  */
 250       loop->header = NULL;
 251       flow_loop_tree_node_remove (loop);
 252     }
 253
 254   /* Remember the number of loops so we can return how many new loops
 255      flow_loops_find discovered.  */
 256   old_nloops = number_of_loops (cfun);
 257
 258   /* Re-compute loop structure in-place.  */
 259   flow_loops_find (current_loops);
 260
 261   /* Mark the blocks whose loop has changed.  */
 262   if (changed_bbs)
 263     {
 264       FOR_EACH_BB (bb)
 265         {
 266           if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
 267             bitmap_set_bit (changed_bbs, bb->index);
 268
 269           bb->aux = NULL;
 270         }
 271     }
 272
 273   /* Finally free deleted loops.  */
 274   FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
 275     if (loop && loop->header == NULL)
 276       {
 277         (*get_loops (cfun))[i] = NULL;
 278         flow_loop_free (loop);
 279       }
 280
 281   loops_state_clear (LOOPS_NEED_FIXUP);
 282
 283   /* Apply flags to loops.  */
 284   apply_loop_flags (current_loops->state | record_exits);
 285
 286 #ifdef ENABLE_CHECKING
 287   verify_loop_structure ();
 288 #endif
 289
 290   timevar_pop (TV_LOOP_INIT);
 291
 292   return number_of_loops (cfun) - old_nloops;
 293 }
 294 \f
 295 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 296    See passes.c for more on that.  */
 297
 298 static bool
 299 gate_handle_loop2 (void)
 300 {
 301   if (optimize > 0
 302       && (flag_move_loop_invariants
 303           || flag_unswitch_loops
 304           || flag_peel_loops
 305           || flag_unroll_loops
 306 #ifdef HAVE_doloop_end
 307           || (flag_branch_on_count_reg && HAVE_doloop_end)
 308 #endif
 309          ))
 310     return true;
 311   else
 312     {
 313       /* No longer preserve loops, remove them now.  */
 314       cfun->curr_properties &= ~PROP_loops;
 315       if (current_loops)
 316         loop_optimizer_finalize ();
 317       return false;
 318     }
 319 }
 320
 321 namespace {
 322
 323 const pass_data pass_data_loop2 =
 324 {
 325   RTL_PASS, /* type */
 326   "loop2", /* name */
 327   OPTGROUP_LOOP, /* optinfo_flags */
 328   true, /* has_gate */
 329   false, /* has_execute */
 330   TV_LOOP, /* tv_id */
 331   0, /* properties_required */
 332   0, /* properties_provided */
 333   0, /* properties_destroyed */
 334   0, /* todo_flags_start */
 335   0, /* todo_flags_finish */
 336 };
 337
 338 class pass_loop2 : public rtl_opt_pass
 339 {
 340 public:
 341   pass_loop2 (gcc::context *ctxt)
 342     : rtl_opt_pass (pass_data_loop2, ctxt)
 343   {}
 344
 345   /* opt_pass methods: */
 346   bool gate () { return gate_handle_loop2 (); }
 347
 348 }; // class pass_loop2
 349
 350 } // anon namespace
 351
 352 rtl_opt_pass *
 353 make_pass_loop2 (gcc::context *ctxt)
 354 {
 355   return new pass_loop2 (ctxt);
 356 }
 357
 358 \f
 359 /* Initialization of the RTL loop passes.  */
 360 static unsigned int
 361 rtl_loop_init (void)
 362 {
 363   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 364
 365   if (dump_file)
 366     {
 367       dump_reg_info (dump_file);
 368       dump_flow_info (dump_file, dump_flags);
 369     }
 370
 371   loop_optimizer_init (LOOPS_NORMAL);
 372   return 0;
 373 }
 374
 375 namespace {
 376
 377 const pass_data pass_data_rtl_loop_init =
 378 {
 379   RTL_PASS, /* type */
 380   "loop2_init", /* name */
 381   OPTGROUP_LOOP, /* optinfo_flags */
 382   false, /* has_gate */
 383   true, /* has_execute */
 384   TV_LOOP, /* tv_id */
 385   0, /* properties_required */
 386   0, /* properties_provided */
 387   0, /* properties_destroyed */
 388   0, /* todo_flags_start */
 389   TODO_verify_rtl_sharing, /* todo_flags_finish */
 390 };
 391
 392 class pass_rtl_loop_init : public rtl_opt_pass
 393 {
 394 public:
 395   pass_rtl_loop_init (gcc::context *ctxt)
 396     : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
 397   {}
 398
 399   /* opt_pass methods: */
 400   unsigned int execute () { return rtl_loop_init (); }
 401
 402 }; // class pass_rtl_loop_init
 403
 404 } // anon namespace
 405
 406 rtl_opt_pass *
 407 make_pass_rtl_loop_init (gcc::context *ctxt)
 408 {
 409   return new pass_rtl_loop_init (ctxt);
 410 }
 411
 412 \f
 413 /* Finalization of the RTL loop passes.  */
 414
 415 static unsigned int
 416 rtl_loop_done (void)
 417 {
 418   /* No longer preserve loops, remove them now.  */
 419   cfun->curr_properties &= ~PROP_loops;
 420   loop_optimizer_finalize ();
 421   free_dominance_info (CDI_DOMINATORS);
 422
 423   cleanup_cfg (0);
 424   if (dump_file)
 425     {
 426       dump_reg_info (dump_file);
 427       dump_flow_info (dump_file, dump_flags);
 428     }
 429
 430   return 0;
 431 }
 432
 433 namespace {
 434
 435 const pass_data pass_data_rtl_loop_done =
 436 {
 437   RTL_PASS, /* type */
 438   "loop2_done", /* name */
 439   OPTGROUP_LOOP, /* optinfo_flags */
 440   false, /* has_gate */
 441   true, /* has_execute */
 442   TV_LOOP, /* tv_id */
 443   0, /* properties_required */
 444   0, /* properties_provided */
 445   PROP_loops, /* properties_destroyed */
 446   0, /* todo_flags_start */
 447   ( TODO_verify_flow | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 448 };
 449
 450 class pass_rtl_loop_done : public rtl_opt_pass
 451 {
 452 public:
 453   pass_rtl_loop_done (gcc::context *ctxt)
 454     : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
 455   {}
 456
 457   /* opt_pass methods: */
 458   unsigned int execute () { return rtl_loop_done (); }
 459
 460 }; // class pass_rtl_loop_done
 461
 462 } // anon namespace
 463
 464 rtl_opt_pass *
 465 make_pass_rtl_loop_done (gcc::context *ctxt)
 466 {
 467   return new pass_rtl_loop_done (ctxt);
 468 }
 469
 470 \f
 471 /* Loop invariant code motion.  */
 472 static bool
 473 gate_rtl_move_loop_invariants (void)
 474 {
 475   return flag_move_loop_invariants;
 476 }
 477
 478 static unsigned int
 479 rtl_move_loop_invariants (void)
 480 {
 481   if (number_of_loops (cfun) > 1)
 482     move_loop_invariants ();
 483   return 0;
 484 }
 485
 486 namespace {
 487
 488 const pass_data pass_data_rtl_move_loop_invariants =
 489 {
 490   RTL_PASS, /* type */
 491   "loop2_invariant", /* name */
 492   OPTGROUP_LOOP, /* optinfo_flags */
 493   true, /* has_gate */
 494   true, /* has_execute */
 495   TV_LOOP_MOVE_INVARIANTS, /* tv_id */
 496   0, /* properties_required */
 497   0, /* properties_provided */
 498   0, /* properties_destroyed */
 499   0, /* todo_flags_start */
 500   ( TODO_df_verify | TODO_df_finish
 501     | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 502 };
 503
 504 class pass_rtl_move_loop_invariants : public rtl_opt_pass
 505 {
 506 public:
 507   pass_rtl_move_loop_invariants (gcc::context *ctxt)
 508     : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
 509   {}
 510
 511   /* opt_pass methods: */
 512   bool gate () { return gate_rtl_move_loop_invariants (); }
 513   unsigned int execute () { return rtl_move_loop_invariants (); }
 514
 515 }; // class pass_rtl_move_loop_invariants
 516
 517 } // anon namespace
 518
 519 rtl_opt_pass *
 520 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
 521 {
 522   return new pass_rtl_move_loop_invariants (ctxt);
 523 }
 524
 525 \f
 526 /* Loop unswitching for RTL.  */
 527 static bool
 528 gate_rtl_unswitch (void)
 529 {
 530   return flag_unswitch_loops;
 531 }
 532
 533 static unsigned int
 534 rtl_unswitch (void)
 535 {
 536   if (number_of_loops (cfun) > 1)
 537     unswitch_loops ();
 538   return 0;
 539 }
 540
 541 namespace {
 542
 543 const pass_data pass_data_rtl_unswitch =
 544 {
 545   RTL_PASS, /* type */
 546   "loop2_unswitch", /* name */
 547   OPTGROUP_LOOP, /* optinfo_flags */
 548   true, /* has_gate */
 549   true, /* has_execute */
 550   TV_LOOP_UNSWITCH, /* tv_id */
 551   0, /* properties_required */
 552   0, /* properties_provided */
 553   0, /* properties_destroyed */
 554   0, /* todo_flags_start */
 555   TODO_verify_rtl_sharing, /* todo_flags_finish */
 556 };
 557
 558 class pass_rtl_unswitch : public rtl_opt_pass
 559 {
 560 public:
 561   pass_rtl_unswitch (gcc::context *ctxt)
 562     : rtl_opt_pass (pass_data_rtl_unswitch, ctxt)
 563   {}
 564
 565   /* opt_pass methods: */
 566   bool gate () { return gate_rtl_unswitch (); }
 567   unsigned int execute () { return rtl_unswitch (); }
 568
 569 }; // class pass_rtl_unswitch
 570
 571 } // anon namespace
 572
 573 rtl_opt_pass *
 574 make_pass_rtl_unswitch (gcc::context *ctxt)
 575 {
 576   return new pass_rtl_unswitch (ctxt);
 577 }
 578
 579 \f
 580 /* Loop unswitching for RTL.  */
 581 static bool
 582 gate_rtl_unroll_and_peel_loops (void)
 583 {
 584   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 585 }
 586
 587 static unsigned int
 588 rtl_unroll_and_peel_loops (void)
 589 {
 590   if (number_of_loops (cfun) > 1)
 591     {
 592       int flags = 0;
 593       if (dump_file)
 594         df_dump (dump_file);
 595
 596       if (flag_peel_loops)
 597         flags |= UAP_PEEL;
 598       if (flag_unroll_loops)
 599         flags |= UAP_UNROLL;
 600       if (flag_unroll_all_loops)
 601         flags |= UAP_UNROLL_ALL;
 602
 603       unroll_and_peel_loops (flags);
 604     }
 605   return 0;
 606 }
 607
 608 namespace {
 609
 610 const pass_data pass_data_rtl_unroll_and_peel_loops =
 611 {
 612   RTL_PASS, /* type */
 613   "loop2_unroll", /* name */
 614   OPTGROUP_LOOP, /* optinfo_flags */
 615   true, /* has_gate */
 616   true, /* has_execute */
 617   TV_LOOP_UNROLL, /* tv_id */
 618   0, /* properties_required */
 619   0, /* properties_provided */
 620   0, /* properties_destroyed */
 621   0, /* todo_flags_start */
 622   TODO_verify_rtl_sharing, /* todo_flags_finish */
 623 };
 624
 625 class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
 626 {
 627 public:
 628   pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 629     : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops, ctxt)
 630   {}
 631
 632   /* opt_pass methods: */
 633   bool gate () { return gate_rtl_unroll_and_peel_loops (); }
 634   unsigned int execute () { return rtl_unroll_and_peel_loops (); }
 635
 636 }; // class pass_rtl_unroll_and_peel_loops
 637
 638 } // anon namespace
 639
 640 rtl_opt_pass *
 641 make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 642 {
 643   return new pass_rtl_unroll_and_peel_loops (ctxt);
 644 }
 645
 646 \f
 647 /* The doloop optimization.  */
 648 static bool
 649 gate_rtl_doloop (void)
 650 {
 651 #ifdef HAVE_doloop_end
 652   return (flag_branch_on_count_reg && HAVE_doloop_end);
 653 #else
 654   return 0;
 655 #endif
 656 }
 657
 658 static unsigned int
 659 rtl_doloop (void)
 660 {
 661 #ifdef HAVE_doloop_end
 662   if (number_of_loops (cfun) > 1)
 663     doloop_optimize_loops ();
 664 #endif
 665   return 0;
 666 }
 667
 668 namespace {
 669
 670 const pass_data pass_data_rtl_doloop =
 671 {
 672   RTL_PASS, /* type */
 673   "loop2_doloop", /* name */
 674   OPTGROUP_LOOP, /* optinfo_flags */
 675   true, /* has_gate */
 676   true, /* has_execute */
 677   TV_LOOP_DOLOOP, /* tv_id */
 678   0, /* properties_required */
 679   0, /* properties_provided */
 680   0, /* properties_destroyed */
 681   0, /* todo_flags_start */
 682   TODO_verify_rtl_sharing, /* todo_flags_finish */
 683 };
 684
 685 class pass_rtl_doloop : public rtl_opt_pass
 686 {
 687 public:
 688   pass_rtl_doloop (gcc::context *ctxt)
 689     : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
 690   {}
 691
 692   /* opt_pass methods: */
 693   bool gate () { return gate_rtl_doloop (); }
 694   unsigned int execute () { return rtl_doloop (); }
 695
 696 }; // class pass_rtl_doloop
 697
 698 } // anon namespace
 699
 700 rtl_opt_pass *
 701 make_pass_rtl_doloop (gcc::context *ctxt)
 702 {
 703   return new pass_rtl_doloop (ctxt);
 704 }