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