gcc/loop-init.c

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