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   false, /* has_execute */
 304   TV_LOOP, /* tv_id */
 305   0, /* properties_required */
 306   0, /* properties_provided */
 307   0, /* properties_destroyed */
 308   0, /* todo_flags_start */
 309   0, /* todo_flags_finish */
 310 };
 311
 312 class pass_loop2 : public rtl_opt_pass
 313 {
 314 public:
 315   pass_loop2 (gcc::context *ctxt)
 316     : rtl_opt_pass (pass_data_loop2, ctxt)
 317   {}
 318
 319   /* opt_pass methods: */
 320   virtual bool gate (function *);
 321
 322 }; // class pass_loop2
 323
 324 bool
 325 pass_loop2::gate (function *fun)
 326 {
 327   if (optimize > 0
 328       && (flag_move_loop_invariants
 329           || flag_unswitch_loops
 330           || flag_peel_loops
 331           || flag_unroll_loops
 332 #ifdef HAVE_doloop_end
 333           || (flag_branch_on_count_reg && HAVE_doloop_end)
 334 #endif
 335       ))
 336     return true;
 337   else
 338     {
 339       /* No longer preserve loops, remove them now.  */
 340       fun->curr_properties &= ~PROP_loops;
 341       if (current_loops)
 342         loop_optimizer_finalize ();
 343       return false;
 344     }
 345 }
 346
 347 } // anon namespace
 348
 349 rtl_opt_pass *
 350 make_pass_loop2 (gcc::context *ctxt)
 351 {
 352   return new pass_loop2 (ctxt);
 353 }
 354
 355 \f
 356 /* Initialization of the RTL loop passes.  */
 357 static unsigned int
 358 rtl_loop_init (void)
 359 {
 360   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 361
 362   if (dump_file)
 363     {
 364       dump_reg_info (dump_file);
 365       dump_flow_info (dump_file, dump_flags);
 366     }
 367
 368   loop_optimizer_init (LOOPS_NORMAL);
 369   return 0;
 370 }
 371
 372 namespace {
 373
 374 const pass_data pass_data_rtl_loop_init =
 375 {
 376   RTL_PASS, /* type */
 377   "loop2_init", /* name */
 378   OPTGROUP_LOOP, /* optinfo_flags */
 379   true, /* has_execute */
 380   TV_LOOP, /* tv_id */
 381   0, /* properties_required */
 382   0, /* properties_provided */
 383   0, /* properties_destroyed */
 384   0, /* todo_flags_start */
 385   TODO_verify_rtl_sharing, /* todo_flags_finish */
 386 };
 387
 388 class pass_rtl_loop_init : public rtl_opt_pass
 389 {
 390 public:
 391   pass_rtl_loop_init (gcc::context *ctxt)
 392     : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
 393   {}
 394
 395   /* opt_pass methods: */
 396   virtual unsigned int execute (function *) { return rtl_loop_init (); }
 397
 398 }; // class pass_rtl_loop_init
 399
 400 } // anon namespace
 401
 402 rtl_opt_pass *
 403 make_pass_rtl_loop_init (gcc::context *ctxt)
 404 {
 405   return new pass_rtl_loop_init (ctxt);
 406 }
 407
 408 \f
 409 /* Finalization of the RTL loop passes.  */
 410
 411 namespace {
 412
 413 const pass_data pass_data_rtl_loop_done =
 414 {
 415   RTL_PASS, /* type */
 416   "loop2_done", /* name */
 417   OPTGROUP_LOOP, /* optinfo_flags */
 418   true, /* has_execute */
 419   TV_LOOP, /* tv_id */
 420   0, /* properties_required */
 421   0, /* properties_provided */
 422   PROP_loops, /* properties_destroyed */
 423   0, /* todo_flags_start */
 424   ( TODO_verify_flow | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 425 };
 426
 427 class pass_rtl_loop_done : public rtl_opt_pass
 428 {
 429 public:
 430   pass_rtl_loop_done (gcc::context *ctxt)
 431     : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
 432   {}
 433
 434   /* opt_pass methods: */
 435   virtual unsigned int execute (function *);
 436
 437 }; // class pass_rtl_loop_done
 438
 439 unsigned int
 440 pass_rtl_loop_done::execute (function *fun)
 441 {
 442   /* No longer preserve loops, remove them now.  */
 443   fun->curr_properties &= ~PROP_loops;
 444   loop_optimizer_finalize ();
 445   free_dominance_info (CDI_DOMINATORS);
 446
 447   cleanup_cfg (0);
 448   if (dump_file)
 449     {
 450       dump_reg_info (dump_file);
 451       dump_flow_info (dump_file, dump_flags);
 452     }
 453
 454   return 0;
 455 }
 456
 457 } // anon namespace
 458
 459 rtl_opt_pass *
 460 make_pass_rtl_loop_done (gcc::context *ctxt)
 461 {
 462   return new pass_rtl_loop_done (ctxt);
 463 }
 464
 465 \f
 466 /* Loop invariant code motion.  */
 467
 468 namespace {
 469
 470 const pass_data pass_data_rtl_move_loop_invariants =
 471 {
 472   RTL_PASS, /* type */
 473   "loop2_invariant", /* name */
 474   OPTGROUP_LOOP, /* optinfo_flags */
 475   true, /* has_execute */
 476   TV_LOOP_MOVE_INVARIANTS, /* tv_id */
 477   0, /* properties_required */
 478   0, /* properties_provided */
 479   0, /* properties_destroyed */
 480   0, /* todo_flags_start */
 481   ( TODO_df_verify | TODO_df_finish
 482     | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 483 };
 484
 485 class pass_rtl_move_loop_invariants : public rtl_opt_pass
 486 {
 487 public:
 488   pass_rtl_move_loop_invariants (gcc::context *ctxt)
 489     : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
 490   {}
 491
 492   /* opt_pass methods: */
 493   virtual bool gate (function *) { return flag_move_loop_invariants; }
 494   virtual unsigned int execute (function *fun)
 495     {
 496       if (number_of_loops (fun) > 1)
 497         move_loop_invariants ();
 498       return 0;
 499     }
 500
 501 }; // class pass_rtl_move_loop_invariants
 502
 503 } // anon namespace
 504
 505 rtl_opt_pass *
 506 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
 507 {
 508   return new pass_rtl_move_loop_invariants (ctxt);
 509 }
 510
 511 \f
 512 namespace {
 513
 514 const pass_data pass_data_rtl_unroll_and_peel_loops =
 515 {
 516   RTL_PASS, /* type */
 517   "loop2_unroll", /* name */
 518   OPTGROUP_LOOP, /* optinfo_flags */
 519   true, /* has_execute */
 520   TV_LOOP_UNROLL, /* tv_id */
 521   0, /* properties_required */
 522   0, /* properties_provided */
 523   0, /* properties_destroyed */
 524   0, /* todo_flags_start */
 525   TODO_verify_rtl_sharing, /* todo_flags_finish */
 526 };
 527
 528 class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
 529 {
 530 public:
 531   pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 532     : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops, ctxt)
 533   {}
 534
 535   /* opt_pass methods: */
 536   virtual bool gate (function *)
 537     {
 538       return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 539     }
 540
 541   virtual unsigned int execute (function *);
 542
 543 }; // class pass_rtl_unroll_and_peel_loops
 544
 545 unsigned int
 546 pass_rtl_unroll_and_peel_loops::execute (function *fun)
 547 {
 548   if (number_of_loops (fun) > 1)
 549     {
 550       int flags = 0;
 551       if (dump_file)
 552         df_dump (dump_file);
 553
 554       if (flag_peel_loops)
 555         flags |= UAP_PEEL;
 556       if (flag_unroll_loops)
 557         flags |= UAP_UNROLL;
 558       if (flag_unroll_all_loops)
 559         flags |= UAP_UNROLL_ALL;
 560
 561       unroll_and_peel_loops (flags);
 562     }
 563   return 0;
 564 }
 565
 566 } // anon namespace
 567
 568 rtl_opt_pass *
 569 make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 570 {
 571   return new pass_rtl_unroll_and_peel_loops (ctxt);
 572 }
 573
 574 \f
 575 namespace {
 576
 577 const pass_data pass_data_rtl_doloop =
 578 {
 579   RTL_PASS, /* type */
 580   "loop2_doloop", /* name */
 581   OPTGROUP_LOOP, /* optinfo_flags */
 582   true, /* has_execute */
 583   TV_LOOP_DOLOOP, /* tv_id */
 584   0, /* properties_required */
 585   0, /* properties_provided */
 586   0, /* properties_destroyed */
 587   0, /* todo_flags_start */
 588   TODO_verify_rtl_sharing, /* todo_flags_finish */
 589 };
 590
 591 class pass_rtl_doloop : public rtl_opt_pass
 592 {
 593 public:
 594   pass_rtl_doloop (gcc::context *ctxt)
 595     : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
 596   {}
 597
 598   /* opt_pass methods: */
 599   virtual bool gate (function *);
 600   virtual unsigned int execute (function *);
 601
 602 }; // class pass_rtl_doloop
 603
 604 bool
 605 pass_rtl_doloop::gate (function *)
 606 {
 607 #ifdef HAVE_doloop_end
 608   return (flag_branch_on_count_reg && HAVE_doloop_end);
 609 #else
 610   return false;
 611 #endif
 612 }
 613
 614 unsigned int
 615 pass_rtl_doloop::execute (function *fun ATTRIBUTE_UNUSED)
 616 {
 617 #ifdef HAVE_doloop_end
 618   if (number_of_loops (fun) > 1)
 619     doloop_optimize_loops ();
 620 #endif
 621   return 0;
 622 }
 623
 624 } // anon namespace
 625
 626 rtl_opt_pass *
 627 make_pass_rtl_doloop (gcc::context *ctxt)
 628 {
 629   return new pass_rtl_doloop (ctxt);
 630 }