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