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