gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002-2014 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       bool needs_fixup = loops_state_satisfies_p (LOOPS_NEED_FIXUP);
  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 #ifdef ENABLE_CHECKING
 105       if (!needs_fixup)
 106         verify_loop_structure ();
 107 #endif
 108
 109       /* Clear all flags.  */
 110       if (recorded_exits)
 111         release_recorded_exits ();
 112       loops_state_clear (~0U);
 113
 114       if (needs_fixup)
 115         {
 116           /* Apply LOOPS_MAY_HAVE_MULTIPLE_LATCHES early as fix_loop_structure
 117              re-applies flags.  */
 118           loops_state_set (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 119           fix_loop_structure (NULL);
 120         }
 121     }
 122
 123   /* Apply flags to loops.  */
 124   apply_loop_flags (flags);
 125
 126   /* Dump loops.  */
 127   flow_loops_dump (dump_file, NULL, 1);
 128
 129 #ifdef ENABLE_CHECKING
 130   verify_loop_structure ();
 131 #endif
 132
 133   timevar_pop (TV_LOOP_INIT);
 134 }
 135
 136 /* Finalize loop structures.  */
 137
 138 void
 139 loop_optimizer_finalize (void)
 140 {
 141   struct loop *loop;
 142   basic_block bb;
 143
 144   timevar_push (TV_LOOP_FINI);
 145
 146   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 147     release_recorded_exits ();
 148
 149   free_numbers_of_iterations_estimates ();
 150
 151   /* If we should preserve loop structure, do not free it but clear
 152      flags that advanced properties are there as we are not preserving
 153      that in full.  */
 154   if (cfun->curr_properties & PROP_loops)
 155     {
 156       loops_state_clear (LOOP_CLOSED_SSA
 157                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 158                          | LOOPS_HAVE_PREHEADERS
 159                          | LOOPS_HAVE_SIMPLE_LATCHES
 160                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 161       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 162       goto loop_fini_done;
 163     }
 164
 165   gcc_assert (current_loops != NULL);
 166
 167   FOR_EACH_LOOP (loop, 0)
 168     free_simple_loop_desc (loop);
 169
 170   /* Clean up.  */
 171   flow_loops_free (current_loops);
 172   ggc_free (current_loops);
 173   current_loops = NULL;
 174
 175   FOR_ALL_BB_FN (bb, cfun)
 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   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_FN (bb, cfun)
 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 (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_FN (bb, cfun)
 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 /* The RTL loop superpass.  The actual passes are subpasses.  See passes.c for
 294    more on that.  */
 295
 296 namespace {
 297
 298 const pass_data pass_data_loop2 =
 299 {
 300   RTL_PASS, /* type */
 301   "loop2", /* name */
 302   OPTGROUP_LOOP, /* optinfo_flags */
 303   TV_LOOP, /* tv_id */
 304   0, /* properties_required */
 305   0, /* properties_provided */
 306   0, /* properties_destroyed */
 307   0, /* todo_flags_start */
 308   0, /* todo_flags_finish */
 309 };
 310
 311 class pass_loop2 : public rtl_opt_pass
 312 {
 313 public:
 314   pass_loop2 (gcc::context *ctxt)
 315     : rtl_opt_pass (pass_data_loop2, ctxt)
 316   {}
 317
 318   /* opt_pass methods: */
 319   virtual bool gate (function *);
 320
 321 }; // class pass_loop2
 322
 323 bool
 324 pass_loop2::gate (function *fun)
 325 {
 326   if (optimize > 0
 327       && (flag_move_loop_invariants
 328           || flag_unswitch_loops
 329           || flag_peel_loops
 330           || flag_unroll_loops
 331 #ifdef HAVE_doloop_end
 332           || (flag_branch_on_count_reg && HAVE_doloop_end)
 333 #endif
 334       ))
 335     return true;
 336   else
 337     {
 338       /* No longer preserve loops, remove them now.  */
 339       fun->curr_properties &= ~PROP_loops;
 340       if (current_loops)
 341         loop_optimizer_finalize ();
 342       return false;
 343     }
 344 }
 345
 346 } // anon namespace
 347
 348 rtl_opt_pass *
 349 make_pass_loop2 (gcc::context *ctxt)
 350 {
 351   return new pass_loop2 (ctxt);
 352 }
 353
 354 \f
 355 /* Initialization of the RTL loop passes.  */
 356 static unsigned int
 357 rtl_loop_init (void)
 358 {
 359   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 360
 361   if (dump_file)
 362     {
 363       dump_reg_info (dump_file);
 364       dump_flow_info (dump_file, dump_flags);
 365     }
 366
 367   loop_optimizer_init (LOOPS_NORMAL);
 368   return 0;
 369 }
 370
 371 namespace {
 372
 373 const pass_data pass_data_rtl_loop_init =
 374 {
 375   RTL_PASS, /* type */
 376   "loop2_init", /* name */
 377   OPTGROUP_LOOP, /* optinfo_flags */
 378   TV_LOOP, /* tv_id */
 379   0, /* properties_required */
 380   0, /* properties_provided */
 381   0, /* properties_destroyed */
 382   0, /* todo_flags_start */
 383   0, /* todo_flags_finish */
 384 };
 385
 386 class pass_rtl_loop_init : public rtl_opt_pass
 387 {
 388 public:
 389   pass_rtl_loop_init (gcc::context *ctxt)
 390     : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
 391   {}
 392
 393   /* opt_pass methods: */
 394   virtual unsigned int execute (function *) { return rtl_loop_init (); }
 395
 396 }; // class pass_rtl_loop_init
 397
 398 } // anon namespace
 399
 400 rtl_opt_pass *
 401 make_pass_rtl_loop_init (gcc::context *ctxt)
 402 {
 403   return new pass_rtl_loop_init (ctxt);
 404 }
 405
 406 \f
 407 /* Finalization of the RTL loop passes.  */
 408
 409 namespace {
 410
 411 const pass_data pass_data_rtl_loop_done =
 412 {
 413   RTL_PASS, /* type */
 414   "loop2_done", /* name */
 415   OPTGROUP_LOOP, /* optinfo_flags */
 416   TV_LOOP, /* tv_id */
 417   0, /* properties_required */
 418   0, /* properties_provided */
 419   PROP_loops, /* properties_destroyed */
 420   0, /* todo_flags_start */
 421   0, /* todo_flags_finish */
 422 };
 423
 424 class pass_rtl_loop_done : public rtl_opt_pass
 425 {
 426 public:
 427   pass_rtl_loop_done (gcc::context *ctxt)
 428     : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
 429   {}
 430
 431   /* opt_pass methods: */
 432   virtual unsigned int execute (function *);
 433
 434 }; // class pass_rtl_loop_done
 435
 436 unsigned int
 437 pass_rtl_loop_done::execute (function *fun)
 438 {
 439   /* No longer preserve loops, remove them now.  */
 440   fun->curr_properties &= ~PROP_loops;
 441   loop_optimizer_finalize ();
 442   free_dominance_info (CDI_DOMINATORS);
 443
 444   cleanup_cfg (0);
 445   if (dump_file)
 446     {
 447       dump_reg_info (dump_file);
 448       dump_flow_info (dump_file, dump_flags);
 449     }
 450
 451   return 0;
 452 }
 453
 454 } // anon namespace
 455
 456 rtl_opt_pass *
 457 make_pass_rtl_loop_done (gcc::context *ctxt)
 458 {
 459   return new pass_rtl_loop_done (ctxt);
 460 }
 461
 462 \f
 463 /* Loop invariant code motion.  */
 464
 465 namespace {
 466
 467 const pass_data pass_data_rtl_move_loop_invariants =
 468 {
 469   RTL_PASS, /* type */
 470   "loop2_invariant", /* name */
 471   OPTGROUP_LOOP, /* optinfo_flags */
 472   TV_LOOP_MOVE_INVARIANTS, /* tv_id */
 473   0, /* properties_required */
 474   0, /* properties_provided */
 475   0, /* properties_destroyed */
 476   0, /* todo_flags_start */
 477   ( TODO_df_verify | TODO_df_finish ), /* todo_flags_finish */
 478 };
 479
 480 class pass_rtl_move_loop_invariants : public rtl_opt_pass
 481 {
 482 public:
 483   pass_rtl_move_loop_invariants (gcc::context *ctxt)
 484     : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
 485   {}
 486
 487   /* opt_pass methods: */
 488   virtual bool gate (function *) { return flag_move_loop_invariants; }
 489   virtual unsigned int execute (function *fun)
 490     {
 491       if (number_of_loops (fun) > 1)
 492         move_loop_invariants ();
 493       return 0;
 494     }
 495
 496 }; // class pass_rtl_move_loop_invariants
 497
 498 } // anon namespace
 499
 500 rtl_opt_pass *
 501 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
 502 {
 503   return new pass_rtl_move_loop_invariants (ctxt);
 504 }
 505
 506 \f
 507 namespace {
 508
 509 const pass_data pass_data_rtl_unroll_and_peel_loops =
 510 {
 511   RTL_PASS, /* type */
 512   "loop2_unroll", /* name */
 513   OPTGROUP_LOOP, /* optinfo_flags */
 514   TV_LOOP_UNROLL, /* tv_id */
 515   0, /* properties_required */
 516   0, /* properties_provided */
 517   0, /* properties_destroyed */
 518   0, /* todo_flags_start */
 519   0, /* todo_flags_finish */
 520 };
 521
 522 class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
 523 {
 524 public:
 525   pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 526     : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops, ctxt)
 527   {}
 528
 529   /* opt_pass methods: */
 530   virtual bool gate (function *)
 531     {
 532       return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 533     }
 534
 535   virtual unsigned int execute (function *);
 536
 537 }; // class pass_rtl_unroll_and_peel_loops
 538
 539 unsigned int
 540 pass_rtl_unroll_and_peel_loops::execute (function *fun)
 541 {
 542   if (number_of_loops (fun) > 1)
 543     {
 544       int flags = 0;
 545       if (dump_file)
 546         df_dump (dump_file);
 547
 548       if (flag_peel_loops)
 549         flags |= UAP_PEEL;
 550       if (flag_unroll_loops)
 551         flags |= UAP_UNROLL;
 552       if (flag_unroll_all_loops)
 553         flags |= UAP_UNROLL_ALL;
 554
 555       unroll_and_peel_loops (flags);
 556     }
 557   return 0;
 558 }
 559
 560 } // anon namespace
 561
 562 rtl_opt_pass *
 563 make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 564 {
 565   return new pass_rtl_unroll_and_peel_loops (ctxt);
 566 }
 567
 568 \f
 569 namespace {
 570
 571 const pass_data pass_data_rtl_doloop =
 572 {
 573   RTL_PASS, /* type */
 574   "loop2_doloop", /* name */
 575   OPTGROUP_LOOP, /* optinfo_flags */
 576   TV_LOOP_DOLOOP, /* tv_id */
 577   0, /* properties_required */
 578   0, /* properties_provided */
 579   0, /* properties_destroyed */
 580   0, /* todo_flags_start */
 581   0, /* todo_flags_finish */
 582 };
 583
 584 class pass_rtl_doloop : public rtl_opt_pass
 585 {
 586 public:
 587   pass_rtl_doloop (gcc::context *ctxt)
 588     : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
 589   {}
 590
 591   /* opt_pass methods: */
 592   virtual bool gate (function *);
 593   virtual unsigned int execute (function *);
 594
 595 }; // class pass_rtl_doloop
 596
 597 bool
 598 pass_rtl_doloop::gate (function *)
 599 {
 600 #ifdef HAVE_doloop_end
 601   return (flag_branch_on_count_reg && HAVE_doloop_end);
 602 #else
 603   return false;
 604 #endif
 605 }
 606
 607 unsigned int
 608 pass_rtl_doloop::execute (function *fun ATTRIBUTE_UNUSED)
 609 {
 610 #ifdef HAVE_doloop_end
 611   if (number_of_loops (fun) > 1)
 612     doloop_optimize_loops ();
 613 #endif
 614   return 0;
 615 }
 616
 617 } // anon namespace
 618
 619 rtl_opt_pass *
 620 make_pass_rtl_doloop (gcc::context *ctxt)
 621 {
 622   return new pass_rtl_doloop (ctxt);
 623 }