gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002-2013 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 (bb)
 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 (bb)
 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 (bb)
 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 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 291    See passes.c for more on that.  */
 292
 293 static bool
 294 gate_handle_loop2 (void)
 295 {
 296   if (optimize > 0
 297       && (flag_move_loop_invariants
 298           || flag_unswitch_loops
 299           || flag_peel_loops
 300           || flag_unroll_loops
 301 #ifdef HAVE_doloop_end
 302           || (flag_branch_on_count_reg && HAVE_doloop_end)
 303 #endif
 304          ))
 305     return true;
 306   else
 307     {
 308       /* No longer preserve loops, remove them now.  */
 309       cfun->curr_properties &= ~PROP_loops;
 310       if (current_loops)
 311         loop_optimizer_finalize ();
 312       return false;
 313     }
 314 }
 315
 316 namespace {
 317
 318 const pass_data pass_data_loop2 =
 319 {
 320   RTL_PASS, /* type */
 321   "loop2", /* name */
 322   OPTGROUP_LOOP, /* optinfo_flags */
 323   true, /* has_gate */
 324   false, /* has_execute */
 325   TV_LOOP, /* tv_id */
 326   0, /* properties_required */
 327   0, /* properties_provided */
 328   0, /* properties_destroyed */
 329   0, /* todo_flags_start */
 330   0, /* todo_flags_finish */
 331 };
 332
 333 class pass_loop2 : public rtl_opt_pass
 334 {
 335 public:
 336   pass_loop2 (gcc::context *ctxt)
 337     : rtl_opt_pass (pass_data_loop2, ctxt)
 338   {}
 339
 340   /* opt_pass methods: */
 341   bool gate () { return gate_handle_loop2 (); }
 342
 343 }; // class pass_loop2
 344
 345 } // anon namespace
 346
 347 rtl_opt_pass *
 348 make_pass_loop2 (gcc::context *ctxt)
 349 {
 350   return new pass_loop2 (ctxt);
 351 }
 352
 353 \f
 354 /* Initialization of the RTL loop passes.  */
 355 static unsigned int
 356 rtl_loop_init (void)
 357 {
 358   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 359
 360   if (dump_file)
 361     {
 362       dump_reg_info (dump_file);
 363       dump_flow_info (dump_file, dump_flags);
 364     }
 365
 366   loop_optimizer_init (LOOPS_NORMAL);
 367   return 0;
 368 }
 369
 370 namespace {
 371
 372 const pass_data pass_data_rtl_loop_init =
 373 {
 374   RTL_PASS, /* type */
 375   "loop2_init", /* name */
 376   OPTGROUP_LOOP, /* optinfo_flags */
 377   false, /* has_gate */
 378   true, /* has_execute */
 379   TV_LOOP, /* tv_id */
 380   0, /* properties_required */
 381   0, /* properties_provided */
 382   0, /* properties_destroyed */
 383   0, /* todo_flags_start */
 384   TODO_verify_rtl_sharing, /* todo_flags_finish */
 385 };
 386
 387 class pass_rtl_loop_init : public rtl_opt_pass
 388 {
 389 public:
 390   pass_rtl_loop_init (gcc::context *ctxt)
 391     : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
 392   {}
 393
 394   /* opt_pass methods: */
 395   unsigned int execute () { return rtl_loop_init (); }
 396
 397 }; // class pass_rtl_loop_init
 398
 399 } // anon namespace
 400
 401 rtl_opt_pass *
 402 make_pass_rtl_loop_init (gcc::context *ctxt)
 403 {
 404   return new pass_rtl_loop_init (ctxt);
 405 }
 406
 407 \f
 408 /* Finalization of the RTL loop passes.  */
 409
 410 static unsigned int
 411 rtl_loop_done (void)
 412 {
 413   /* No longer preserve loops, remove them now.  */
 414   cfun->curr_properties &= ~PROP_loops;
 415   loop_optimizer_finalize ();
 416   free_dominance_info (CDI_DOMINATORS);
 417
 418   cleanup_cfg (0);
 419   if (dump_file)
 420     {
 421       dump_reg_info (dump_file);
 422       dump_flow_info (dump_file, dump_flags);
 423     }
 424
 425   return 0;
 426 }
 427
 428 namespace {
 429
 430 const pass_data pass_data_rtl_loop_done =
 431 {
 432   RTL_PASS, /* type */
 433   "loop2_done", /* name */
 434   OPTGROUP_LOOP, /* optinfo_flags */
 435   false, /* has_gate */
 436   true, /* has_execute */
 437   TV_LOOP, /* tv_id */
 438   0, /* properties_required */
 439   0, /* properties_provided */
 440   PROP_loops, /* properties_destroyed */
 441   0, /* todo_flags_start */
 442   ( TODO_verify_flow | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 443 };
 444
 445 class pass_rtl_loop_done : public rtl_opt_pass
 446 {
 447 public:
 448   pass_rtl_loop_done (gcc::context *ctxt)
 449     : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
 450   {}
 451
 452   /* opt_pass methods: */
 453   unsigned int execute () { return rtl_loop_done (); }
 454
 455 }; // class pass_rtl_loop_done
 456
 457 } // anon namespace
 458
 459 rtl_opt_pass *
 460 make_pass_rtl_loop_done (gcc::context *ctxt)
 461 {
 462   return new pass_rtl_loop_done (ctxt);
 463 }
 464
 465 \f
 466 /* Loop invariant code motion.  */
 467 static bool
 468 gate_rtl_move_loop_invariants (void)
 469 {
 470   return flag_move_loop_invariants;
 471 }
 472
 473 static unsigned int
 474 rtl_move_loop_invariants (void)
 475 {
 476   if (number_of_loops (cfun) > 1)
 477     move_loop_invariants ();
 478   return 0;
 479 }
 480
 481 namespace {
 482
 483 const pass_data pass_data_rtl_move_loop_invariants =
 484 {
 485   RTL_PASS, /* type */
 486   "loop2_invariant", /* name */
 487   OPTGROUP_LOOP, /* optinfo_flags */
 488   true, /* has_gate */
 489   true, /* has_execute */
 490   TV_LOOP_MOVE_INVARIANTS, /* tv_id */
 491   0, /* properties_required */
 492   0, /* properties_provided */
 493   0, /* properties_destroyed */
 494   0, /* todo_flags_start */
 495   ( TODO_df_verify | TODO_df_finish
 496     | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 497 };
 498
 499 class pass_rtl_move_loop_invariants : public rtl_opt_pass
 500 {
 501 public:
 502   pass_rtl_move_loop_invariants (gcc::context *ctxt)
 503     : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
 504   {}
 505
 506   /* opt_pass methods: */
 507   bool gate () { return gate_rtl_move_loop_invariants (); }
 508   unsigned int execute () { return rtl_move_loop_invariants (); }
 509
 510 }; // class pass_rtl_move_loop_invariants
 511
 512 } // anon namespace
 513
 514 rtl_opt_pass *
 515 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
 516 {
 517   return new pass_rtl_move_loop_invariants (ctxt);
 518 }
 519
 520 \f
 521 /* Loop unswitching for RTL.  */
 522 static bool
 523 gate_rtl_unswitch (void)
 524 {
 525   return flag_unswitch_loops;
 526 }
 527
 528 static unsigned int
 529 rtl_unswitch (void)
 530 {
 531   if (number_of_loops (cfun) > 1)
 532     unswitch_loops ();
 533   return 0;
 534 }
 535
 536 namespace {
 537
 538 const pass_data pass_data_rtl_unswitch =
 539 {
 540   RTL_PASS, /* type */
 541   "loop2_unswitch", /* name */
 542   OPTGROUP_LOOP, /* optinfo_flags */
 543   true, /* has_gate */
 544   true, /* has_execute */
 545   TV_LOOP_UNSWITCH, /* tv_id */
 546   0, /* properties_required */
 547   0, /* properties_provided */
 548   0, /* properties_destroyed */
 549   0, /* todo_flags_start */
 550   TODO_verify_rtl_sharing, /* todo_flags_finish */
 551 };
 552
 553 class pass_rtl_unswitch : public rtl_opt_pass
 554 {
 555 public:
 556   pass_rtl_unswitch (gcc::context *ctxt)
 557     : rtl_opt_pass (pass_data_rtl_unswitch, ctxt)
 558   {}
 559
 560   /* opt_pass methods: */
 561   bool gate () { return gate_rtl_unswitch (); }
 562   unsigned int execute () { return rtl_unswitch (); }
 563
 564 }; // class pass_rtl_unswitch
 565
 566 } // anon namespace
 567
 568 rtl_opt_pass *
 569 make_pass_rtl_unswitch (gcc::context *ctxt)
 570 {
 571   return new pass_rtl_unswitch (ctxt);
 572 }
 573
 574 \f
 575 /* Loop unswitching for RTL.  */
 576 static bool
 577 gate_rtl_unroll_and_peel_loops (void)
 578 {
 579   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 580 }
 581
 582 static unsigned int
 583 rtl_unroll_and_peel_loops (void)
 584 {
 585   if (number_of_loops (cfun) > 1)
 586     {
 587       int flags = 0;
 588       if (dump_file)
 589         df_dump (dump_file);
 590
 591       if (flag_peel_loops)
 592         flags |= UAP_PEEL;
 593       if (flag_unroll_loops)
 594         flags |= UAP_UNROLL;
 595       if (flag_unroll_all_loops)
 596         flags |= UAP_UNROLL_ALL;
 597
 598       unroll_and_peel_loops (flags);
 599     }
 600   return 0;
 601 }
 602
 603 namespace {
 604
 605 const pass_data pass_data_rtl_unroll_and_peel_loops =
 606 {
 607   RTL_PASS, /* type */
 608   "loop2_unroll", /* name */
 609   OPTGROUP_LOOP, /* optinfo_flags */
 610   true, /* has_gate */
 611   true, /* has_execute */
 612   TV_LOOP_UNROLL, /* tv_id */
 613   0, /* properties_required */
 614   0, /* properties_provided */
 615   0, /* properties_destroyed */
 616   0, /* todo_flags_start */
 617   TODO_verify_rtl_sharing, /* todo_flags_finish */
 618 };
 619
 620 class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
 621 {
 622 public:
 623   pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 624     : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops, ctxt)
 625   {}
 626
 627   /* opt_pass methods: */
 628   bool gate () { return gate_rtl_unroll_and_peel_loops (); }
 629   unsigned int execute () { return rtl_unroll_and_peel_loops (); }
 630
 631 }; // class pass_rtl_unroll_and_peel_loops
 632
 633 } // anon namespace
 634
 635 rtl_opt_pass *
 636 make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
 637 {
 638   return new pass_rtl_unroll_and_peel_loops (ctxt);
 639 }
 640
 641 \f
 642 /* The doloop optimization.  */
 643 static bool
 644 gate_rtl_doloop (void)
 645 {
 646 #ifdef HAVE_doloop_end
 647   return (flag_branch_on_count_reg && HAVE_doloop_end);
 648 #else
 649   return 0;
 650 #endif
 651 }
 652
 653 static unsigned int
 654 rtl_doloop (void)
 655 {
 656 #ifdef HAVE_doloop_end
 657   if (number_of_loops (cfun) > 1)
 658     doloop_optimize_loops ();
 659 #endif
 660   return 0;
 661 }
 662
 663 namespace {
 664
 665 const pass_data pass_data_rtl_doloop =
 666 {
 667   RTL_PASS, /* type */
 668   "loop2_doloop", /* name */
 669   OPTGROUP_LOOP, /* optinfo_flags */
 670   true, /* has_gate */
 671   true, /* has_execute */
 672   TV_LOOP_DOLOOP, /* tv_id */
 673   0, /* properties_required */
 674   0, /* properties_provided */
 675   0, /* properties_destroyed */
 676   0, /* todo_flags_start */
 677   TODO_verify_rtl_sharing, /* todo_flags_finish */
 678 };
 679
 680 class pass_rtl_doloop : public rtl_opt_pass
 681 {
 682 public:
 683   pass_rtl_doloop (gcc::context *ctxt)
 684     : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
 685   {}
 686
 687   /* opt_pass methods: */
 688   bool gate () { return gate_rtl_doloop (); }
 689   unsigned int execute () { return rtl_doloop (); }
 690
 691 }; // class pass_rtl_doloop
 692
 693 } // anon namespace
 694
 695 rtl_opt_pass *
 696 make_pass_rtl_doloop (gcc::context *ctxt)
 697 {
 698   return new pass_rtl_doloop (ctxt);
 699 }