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