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