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
  36 \f
  37 /* Apply FLAGS to the loop state.  */
  38
  39 static void
  40 apply_loop_flags (unsigned flags)
  41 {
  42   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  43     {
  44       /* If the loops may have multiple latches, we cannot canonicalize
  45          them further (and most of the loop manipulation functions will
  46          not work).  However, we avoid modifying cfg, which some
  47          passes may want.  */
  48       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  49                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  50       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
  51     }
  52   else
  53     disambiguate_loops_with_multiple_latches ();
  54
  55   /* Create pre-headers.  */
  56   if (flags & LOOPS_HAVE_PREHEADERS)
  57     {
  58       int cp_flags = CP_SIMPLE_PREHEADERS;
  59
  60       if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
  61         cp_flags |= CP_FALLTHRU_PREHEADERS;
  62
  63       create_preheaders (cp_flags);
  64     }
  65
  66   /* Force all latches to have only single successor.  */
  67   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  68     force_single_succ_latches ();
  69
  70   /* Mark irreducible loops.  */
  71   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  72     mark_irreducible_loops ();
  73
  74   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  75     record_loop_exits ();
  76 }
  77
  78 /* Initialize loop structures.  This is used by the tree and RTL loop
  79    optimizers.  FLAGS specify what properties to compute and/or ensure for
  80    loops.  */
  81
  82 void
  83 loop_optimizer_init (unsigned flags)
  84 {
  85   timevar_push (TV_LOOP_INIT);
  86
  87   if (!current_loops)
  88     {
  89       gcc_assert (!(cfun->curr_properties & PROP_loops));
  90
  91       /* Find the loops.  */
  92       current_loops = flow_loops_find (NULL);
  93     }
  94   else
  95     {
  96       bool recorded_exits = loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS);
  97       bool needs_fixup = loops_state_satisfies_p (LOOPS_NEED_FIXUP);
  98
  99       gcc_assert (cfun->curr_properties & PROP_loops);
 100
 101       /* Ensure that the dominators are computed, like flow_loops_find does.  */
 102       calculate_dominance_info (CDI_DOMINATORS);
 103
 104 #ifdef ENABLE_CHECKING
 105       if (!needs_fixup)
 106         verify_loop_structure ();
 107 #endif
 108
 109       /* Clear all flags.  */
 110       if (recorded_exits)
 111         release_recorded_exits ();
 112       loops_state_clear (~0U);
 113
 114       if (needs_fixup)
 115         {
 116           /* Apply LOOPS_MAY_HAVE_MULTIPLE_LATCHES early as fix_loop_structure
 117              re-applies flags.  */
 118           loops_state_set (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 119           fix_loop_structure (NULL);
 120         }
 121     }
 122
 123   /* Apply flags to loops.  */
 124   apply_loop_flags (flags);
 125
 126   /* Dump loops.  */
 127   flow_loops_dump (dump_file, NULL, 1);
 128
 129 #ifdef ENABLE_CHECKING
 130   verify_loop_structure ();
 131 #endif
 132
 133   timevar_pop (TV_LOOP_INIT);
 134 }
 135
 136 /* Finalize loop structures.  */
 137
 138 void
 139 loop_optimizer_finalize (void)
 140 {
 141   struct loop *loop;
 142   basic_block bb;
 143
 144   timevar_push (TV_LOOP_FINI);
 145
 146   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 147     release_recorded_exits ();
 148
 149   free_numbers_of_iterations_estimates ();
 150
 151   /* If we should preserve loop structure, do not free it but clear
 152      flags that advanced properties are there as we are not preserving
 153      that in full.  */
 154   if (cfun->curr_properties & PROP_loops)
 155     {
 156       loops_state_clear (LOOP_CLOSED_SSA
 157                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 158                          | LOOPS_HAVE_PREHEADERS
 159                          | LOOPS_HAVE_SIMPLE_LATCHES
 160                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 161       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 162       goto loop_fini_done;
 163     }
 164
 165   gcc_assert (current_loops != NULL);
 166
 167   FOR_EACH_LOOP (loop, 0)
 168     free_simple_loop_desc (loop);
 169
 170   /* Clean up.  */
 171   flow_loops_free (current_loops);
 172   ggc_free (current_loops);
 173   current_loops = NULL;
 174
 175   FOR_ALL_BB_FN (bb, cfun)
 176     {
 177       bb->loop_father = NULL;
 178     }
 179
 180 loop_fini_done:
 181   timevar_pop (TV_LOOP_FINI);
 182 }
 183
 184 /* The structure of loops might have changed.  Some loops might get removed
 185    (and their headers and latches were set to NULL), loop exists might get
 186    removed (thus the loop nesting may be wrong), and some blocks and edges
 187    were changed (so the information about bb --> loop mapping does not have
 188    to be correct).  But still for the remaining loops the header dominates
 189    the latch, and loops did not get new subloops (new loops might possibly
 190    get created, but we are not interested in them).  Fix up the mess.
 191
 192    If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
 193    marked in it.
 194
 195    Returns the number of new discovered loops.  */
 196
 197 unsigned
 198 fix_loop_structure (bitmap changed_bbs)
 199 {
 200   basic_block bb;
 201   int record_exits = 0;
 202   struct loop *loop;
 203   unsigned old_nloops, i;
 204
 205   timevar_push (TV_LOOP_INIT);
 206
 207   /* We need exact and fast dominance info to be available.  */
 208   gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
 209
 210   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 211     {
 212       release_recorded_exits ();
 213       record_exits = LOOPS_HAVE_RECORDED_EXITS;
 214     }
 215
 216   /* Remember the depth of the blocks in the loop hierarchy, so that we can
 217      recognize blocks whose loop nesting relationship has changed.  */
 218   if (changed_bbs)
 219     FOR_EACH_BB_FN (bb, cfun)
 220       bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
 221
 222   /* Remove the dead loops from structures.  We start from the innermost
 223      loops, so that when we remove the loops, we know that the loops inside
 224      are preserved, and do not waste time relinking loops that will be
 225      removed later.  */
 226   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
 227     {
 228       /* Detect the case that the loop is no longer present even though
 229          it wasn't marked for removal.
 230          ???  If we do that we can get away with not marking loops for
 231          removal at all.  And possibly avoid some spurious removals.  */
 232       if (loop->header
 233           && bb_loop_header_p (loop->header))
 234         continue;
 235
 236       if (dump_file && (dump_flags & TDF_DETAILS))
 237         fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
 238                  loop->num);
 239
 240       while (loop->inner)
 241         {
 242           struct loop *ploop = loop->inner;
 243           flow_loop_tree_node_remove (ploop);
 244           flow_loop_tree_node_add (loop_outer (loop), ploop);
 245         }
 246
 247       /* Remove the loop.  */
 248       if (loop->header)
 249         loop->former_header = loop->header;
 250       else
 251         gcc_assert (loop->former_header != NULL);
 252       loop->header = NULL;
 253       flow_loop_tree_node_remove (loop);
 254     }
 255
 256   /* Remember the number of loops so we can return how many new loops
 257      flow_loops_find discovered.  */
 258   old_nloops = number_of_loops (cfun);
 259
 260   /* Re-compute loop structure in-place.  */
 261   flow_loops_find (current_loops);
 262
 263   /* Mark the blocks whose loop has changed.  */
 264   if (changed_bbs)
 265     {
 266       FOR_EACH_BB_FN (bb, cfun)
 267         {
 268           if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
 269             bitmap_set_bit (changed_bbs, bb->index);
 270
 271           bb->aux = NULL;
 272         }
 273     }
 274
 275   /* Finally free deleted loops.  */
 276   FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
 277     if (loop && loop->header == NULL)
 278       {
 279         if (dump_file
 280             && ((unsigned) loop->former_header->index
 281                 < basic_block_info_for_fn (cfun)->length ()))
 282           {
 283             basic_block former_header
 284               = BASIC_BLOCK_FOR_FN (cfun, loop->former_header->index);
 285             /* If the old header still exists we want to check if the
 286                original loop is re-discovered or the old header is now
 287                part of a newly discovered loop.
 288                In both cases we should have avoided removing the loop.  */
 289             if (former_header == loop->former_header)
 290               {
 291                 if (former_header->loop_father->header == former_header)
 292                   fprintf (dump_file, "fix_loop_structure: rediscovered "
 293                            "removed loop %d as loop %d with old header %d\n",
 294                            loop->num, former_header->loop_father->num,
 295                            former_header->index);
 296                 else if ((unsigned) former_header->loop_father->num
 297                          >= old_nloops)
 298                   fprintf (dump_file, "fix_loop_structure: header %d of "
 299                            "removed loop %d is part of the newly "
 300                            "discovered loop %d with header %d\n",
 301                            former_header->index, loop->num,
 302                            former_header->loop_father->num,
 303                            former_header->loop_father->header->index);
 304               }
 305           }
 306         (*get_loops (cfun))[i] = NULL;
 307         flow_loop_free (loop);
 308       }
 309
 310   loops_state_clear (LOOPS_NEED_FIXUP);
 311
 312   /* Apply flags to loops.  */
 313   apply_loop_flags (current_loops->state | record_exits);
 314
 315 #ifdef ENABLE_CHECKING
 316   verify_loop_structure ();
 317 #endif
 318
 319   timevar_pop (TV_LOOP_INIT);
 320
 321   return number_of_loops (cfun) - old_nloops;
 322 }
 323 \f
 324 /* The RTL loop superpass.  The actual passes are subpasses.  See passes.c for
 325    more on that.  */
 326
 327 namespace {
 328
 329 const pass_data pass_data_loop2 =
 330 {
 331   RTL_PASS, /* type */
 332   "loop2", /* name */
 333   OPTGROUP_LOOP, /* optinfo_flags */
 334   TV_LOOP, /* tv_id */
 335   0, /* properties_required */
 336   0, /* properties_provided */
 337   0, /* properties_destroyed */
 338   0, /* todo_flags_start */
 339   0, /* todo_flags_finish */
 340 };
 341
 342 class pass_loop2 : public rtl_opt_pass
 343 {
 344 public:
 345   pass_loop2 (gcc::context *ctxt)
 346     : rtl_opt_pass (pass_data_loop2, ctxt)
 347   {}
 348
 349   /* opt_pass methods: */
 350   virtual bool gate (function *);
 351
 352 }; // class pass_loop2
 353
 354 bool
 355 pass_loop2::gate (function *fun)
 356 {
 357   if (optimize > 0
 358       && (flag_move_loop_invariants
 359           || flag_unswitch_loops
 360           || flag_peel_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_and_peel_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_and_peel_loops : public rtl_opt_pass
 554 {
 555 public:
 556   pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 557     : rtl_opt_pass (pass_data_rtl_unroll_and_peel_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_and_peel_loops
 569
 570 unsigned int
 571 pass_rtl_unroll_and_peel_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_peel_loops)
 580         flags |= UAP_PEEL;
 581       if (flag_unroll_loops)
 582         flags |= UAP_UNROLL;
 583       if (flag_unroll_all_loops)
 584         flags |= UAP_UNROLL_ALL;
 585
 586       unroll_and_peel_loops (flags);
 587     }
 588   return 0;
 589 }
 590
 591 } // anon namespace
 592
 593 rtl_opt_pass *
 594 make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 595 {
 596   return new pass_rtl_unroll_and_peel_loops (ctxt);
 597 }
 598
 599 \f
 600 namespace {
 601
 602 const pass_data pass_data_rtl_doloop =
 603 {
 604   RTL_PASS, /* type */
 605   "loop2_doloop", /* name */
 606   OPTGROUP_LOOP, /* optinfo_flags */
 607   TV_LOOP_DOLOOP, /* tv_id */
 608   0, /* properties_required */
 609   0, /* properties_provided */
 610   0, /* properties_destroyed */
 611   0, /* todo_flags_start */
 612   0, /* todo_flags_finish */
 613 };
 614
 615 class pass_rtl_doloop : public rtl_opt_pass
 616 {
 617 public:
 618   pass_rtl_doloop (gcc::context *ctxt)
 619     : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
 620   {}
 621
 622   /* opt_pass methods: */
 623   virtual bool gate (function *);
 624   virtual unsigned int execute (function *);
 625
 626 }; // class pass_rtl_doloop
 627
 628 bool
 629 pass_rtl_doloop::gate (function *)
 630 {
 631 #ifdef HAVE_doloop_end
 632   return (flag_branch_on_count_reg && HAVE_doloop_end);
 633 #else
 634   return false;
 635 #endif
 636 }
 637
 638 unsigned int
 639 pass_rtl_doloop::execute (function *fun ATTRIBUTE_UNUSED)
 640 {
 641 #ifdef HAVE_doloop_end
 642   if (number_of_loops (fun) > 1)
 643     doloop_optimize_loops ();
 644 #endif
 645   return 0;
 646 }
 647
 648 } // anon namespace
 649
 650 rtl_opt_pass *
 651 make_pass_rtl_doloop (gcc::context *ctxt)
 652 {
 653   return new pass_rtl_doloop (ctxt);
 654 }