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