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