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