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 "target.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "cfghooks.h"
  28 #include "df.h"
  29 #include "regs.h"
  30 #include "alias.h"
  31 #include "cfgcleanup.h"
  32 #include "cfgloop.h"
  33 #include "tree-pass.h"
  34 #include "flags.h"
  35 #include "tree-ssa-loop-niter.h"
  36 #include "loop-unroll.h"
  37 #include "tree-scalar-evolution.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       if (!needs_fixup)
 108         checking_verify_loop_structure ();
 109
 110       /* Clear all flags.  */
 111       if (recorded_exits)
 112         release_recorded_exits (cfun);
 113       loops_state_clear (~0U);
 114
 115       if (needs_fixup)
 116         {
 117           /* Apply LOOPS_MAY_HAVE_MULTIPLE_LATCHES early as fix_loop_structure
 118              re-applies flags.  */
 119           loops_state_set (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 120           fix_loop_structure (NULL);
 121         }
 122     }
 123
 124   /* Apply flags to loops.  */
 125   apply_loop_flags (flags);
 126
 127   /* Dump loops.  */
 128   flow_loops_dump (dump_file, NULL, 1);
 129
 130   checking_verify_loop_structure ();
 131
 132   timevar_pop (TV_LOOP_INIT);
 133 }
 134
 135 /* Finalize loop structures.  */
 136
 137 void
 138 loop_optimizer_finalize (struct function *fn)
 139 {
 140   struct loop *loop;
 141   basic_block bb;
 142
 143   timevar_push (TV_LOOP_FINI);
 144
 145   if (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS))
 146     release_recorded_exits (fn);
 147
 148   free_numbers_of_iterations_estimates (fn);
 149
 150   /* If we should preserve loop structure, do not free it but clear
 151      flags that advanced properties are there as we are not preserving
 152      that in full.  */
 153   if (fn->curr_properties & PROP_loops)
 154     {
 155       loops_state_clear (fn, LOOP_CLOSED_SSA
 156                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 157                          | LOOPS_HAVE_PREHEADERS
 158                          | LOOPS_HAVE_SIMPLE_LATCHES
 159                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 160       loops_state_set (fn, LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 161       goto loop_fini_done;
 162     }
 163
 164   FOR_EACH_LOOP_FN (fn, loop, 0)
 165     free_simple_loop_desc (loop);
 166
 167   /* Clean up.  */
 168   flow_loops_free (loops_for_fn (fn));
 169   ggc_free (loops_for_fn (fn));
 170   set_loops_for_fn (fn, NULL);
 171
 172   FOR_ALL_BB_FN (bb, fn)
 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   if (dump_file && (dump_flags & TDF_DETAILS))
 205     fprintf (dump_file, "fix_loop_structure: fixing up loops for function\n");
 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 (cfun);
 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   bool any_deleted = false;
 277   FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
 278     if (loop && loop->header == NULL)
 279       {
 280         if (dump_file
 281             && ((unsigned) loop->former_header->index
 282                 < basic_block_info_for_fn (cfun)->length ()))
 283           {
 284             basic_block former_header
 285               = BASIC_BLOCK_FOR_FN (cfun, loop->former_header->index);
 286             /* If the old header still exists we want to check if the
 287                original loop is re-discovered or the old header is now
 288                part of a newly discovered loop.
 289                In both cases we should have avoided removing the loop.  */
 290             if (former_header == loop->former_header)
 291               {
 292                 if (former_header->loop_father->header == former_header)
 293                   fprintf (dump_file, "fix_loop_structure: rediscovered "
 294                            "removed loop %d as loop %d with old header %d\n",
 295                            loop->num, former_header->loop_father->num,
 296                            former_header->index);
 297                 else if ((unsigned) former_header->loop_father->num
 298                          >= old_nloops)
 299                   fprintf (dump_file, "fix_loop_structure: header %d of "
 300                            "removed loop %d is part of the newly "
 301                            "discovered loop %d with header %d\n",
 302                            former_header->index, loop->num,
 303                            former_header->loop_father->num,
 304                            former_header->loop_father->header->index);
 305               }
 306           }
 307         (*get_loops (cfun))[i] = NULL;
 308         flow_loop_free (loop);
 309         any_deleted = true;
 310       }
 311
 312   /* If we deleted loops then the cached scalar evolutions refering to
 313      those loops become invalid.  */
 314   if (any_deleted && scev_initialized_p ())
 315     scev_reset_htab ();
 316
 317   loops_state_clear (LOOPS_NEED_FIXUP);
 318
 319   /* Apply flags to loops.  */
 320   apply_loop_flags (current_loops->state | record_exits);
 321
 322   checking_verify_loop_structure ();
 323
 324   timevar_pop (TV_LOOP_INIT);
 325
 326   return number_of_loops (cfun) - old_nloops;
 327 }
 328 \f
 329 /* The RTL loop superpass.  The actual passes are subpasses.  See passes.c for
 330    more on that.  */
 331
 332 namespace {
 333
 334 const pass_data pass_data_loop2 =
 335 {
 336   RTL_PASS, /* type */
 337   "loop2", /* name */
 338   OPTGROUP_LOOP, /* optinfo_flags */
 339   TV_LOOP, /* tv_id */
 340   0, /* properties_required */
 341   0, /* properties_provided */
 342   0, /* properties_destroyed */
 343   0, /* todo_flags_start */
 344   0, /* todo_flags_finish */
 345 };
 346
 347 class pass_loop2 : public rtl_opt_pass
 348 {
 349 public:
 350   pass_loop2 (gcc::context *ctxt)
 351     : rtl_opt_pass (pass_data_loop2, ctxt)
 352   {}
 353
 354   /* opt_pass methods: */
 355   virtual bool gate (function *);
 356
 357 }; // class pass_loop2
 358
 359 bool
 360 pass_loop2::gate (function *fun)
 361 {
 362   if (optimize > 0
 363       && (flag_move_loop_invariants
 364           || flag_unswitch_loops
 365           || flag_unroll_loops
 366           || (flag_branch_on_count_reg
 367               && targetm.have_doloop_end ())))
 368     return true;
 369   else
 370     {
 371       /* No longer preserve loops, remove them now.  */
 372       fun->curr_properties &= ~PROP_loops;
 373       if (current_loops)
 374         loop_optimizer_finalize ();
 375       return false;
 376     }
 377 }
 378
 379 } // anon namespace
 380
 381 rtl_opt_pass *
 382 make_pass_loop2 (gcc::context *ctxt)
 383 {
 384   return new pass_loop2 (ctxt);
 385 }
 386
 387 \f
 388 /* Initialization of the RTL loop passes.  */
 389 static unsigned int
 390 rtl_loop_init (void)
 391 {
 392   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 393
 394   if (dump_file)
 395     {
 396       dump_reg_info (dump_file);
 397       dump_flow_info (dump_file, dump_flags);
 398     }
 399
 400   loop_optimizer_init (LOOPS_NORMAL);
 401   return 0;
 402 }
 403
 404 namespace {
 405
 406 const pass_data pass_data_rtl_loop_init =
 407 {
 408   RTL_PASS, /* type */
 409   "loop2_init", /* name */
 410   OPTGROUP_LOOP, /* optinfo_flags */
 411   TV_LOOP, /* tv_id */
 412   0, /* properties_required */
 413   0, /* properties_provided */
 414   0, /* properties_destroyed */
 415   0, /* todo_flags_start */
 416   0, /* todo_flags_finish */
 417 };
 418
 419 class pass_rtl_loop_init : public rtl_opt_pass
 420 {
 421 public:
 422   pass_rtl_loop_init (gcc::context *ctxt)
 423     : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
 424   {}
 425
 426   /* opt_pass methods: */
 427   virtual unsigned int execute (function *) { return rtl_loop_init (); }
 428
 429 }; // class pass_rtl_loop_init
 430
 431 } // anon namespace
 432
 433 rtl_opt_pass *
 434 make_pass_rtl_loop_init (gcc::context *ctxt)
 435 {
 436   return new pass_rtl_loop_init (ctxt);
 437 }
 438
 439 \f
 440 /* Finalization of the RTL loop passes.  */
 441
 442 namespace {
 443
 444 const pass_data pass_data_rtl_loop_done =
 445 {
 446   RTL_PASS, /* type */
 447   "loop2_done", /* name */
 448   OPTGROUP_LOOP, /* optinfo_flags */
 449   TV_LOOP, /* tv_id */
 450   0, /* properties_required */
 451   0, /* properties_provided */
 452   PROP_loops, /* properties_destroyed */
 453   0, /* todo_flags_start */
 454   0, /* todo_flags_finish */
 455 };
 456
 457 class pass_rtl_loop_done : public rtl_opt_pass
 458 {
 459 public:
 460   pass_rtl_loop_done (gcc::context *ctxt)
 461     : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
 462   {}
 463
 464   /* opt_pass methods: */
 465   virtual unsigned int execute (function *);
 466
 467 }; // class pass_rtl_loop_done
 468
 469 unsigned int
 470 pass_rtl_loop_done::execute (function *fun)
 471 {
 472   /* No longer preserve loops, remove them now.  */
 473   fun->curr_properties &= ~PROP_loops;
 474   loop_optimizer_finalize ();
 475   free_dominance_info (CDI_DOMINATORS);
 476
 477   cleanup_cfg (0);
 478   if (dump_file)
 479     {
 480       dump_reg_info (dump_file);
 481       dump_flow_info (dump_file, dump_flags);
 482     }
 483
 484   return 0;
 485 }
 486
 487 } // anon namespace
 488
 489 rtl_opt_pass *
 490 make_pass_rtl_loop_done (gcc::context *ctxt)
 491 {
 492   return new pass_rtl_loop_done (ctxt);
 493 }
 494
 495 \f
 496 /* Loop invariant code motion.  */
 497
 498 namespace {
 499
 500 const pass_data pass_data_rtl_move_loop_invariants =
 501 {
 502   RTL_PASS, /* type */
 503   "loop2_invariant", /* name */
 504   OPTGROUP_LOOP, /* optinfo_flags */
 505   TV_LOOP_MOVE_INVARIANTS, /* tv_id */
 506   0, /* properties_required */
 507   0, /* properties_provided */
 508   0, /* properties_destroyed */
 509   0, /* todo_flags_start */
 510   ( TODO_df_verify | TODO_df_finish ), /* todo_flags_finish */
 511 };
 512
 513 class pass_rtl_move_loop_invariants : public rtl_opt_pass
 514 {
 515 public:
 516   pass_rtl_move_loop_invariants (gcc::context *ctxt)
 517     : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
 518   {}
 519
 520   /* opt_pass methods: */
 521   virtual bool gate (function *) { return flag_move_loop_invariants; }
 522   virtual unsigned int execute (function *fun)
 523     {
 524       if (number_of_loops (fun) > 1)
 525         move_loop_invariants ();
 526       return 0;
 527     }
 528
 529 }; // class pass_rtl_move_loop_invariants
 530
 531 } // anon namespace
 532
 533 rtl_opt_pass *
 534 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
 535 {
 536   return new pass_rtl_move_loop_invariants (ctxt);
 537 }
 538
 539 \f
 540 namespace {
 541
 542 const pass_data pass_data_rtl_unroll_loops =
 543 {
 544   RTL_PASS, /* type */
 545   "loop2_unroll", /* name */
 546   OPTGROUP_LOOP, /* optinfo_flags */
 547   TV_LOOP_UNROLL, /* tv_id */
 548   0, /* properties_required */
 549   0, /* properties_provided */
 550   0, /* properties_destroyed */
 551   0, /* todo_flags_start */
 552   0, /* todo_flags_finish */
 553 };
 554
 555 class pass_rtl_unroll_loops : public rtl_opt_pass
 556 {
 557 public:
 558   pass_rtl_unroll_loops (gcc::context *ctxt)
 559     : rtl_opt_pass (pass_data_rtl_unroll_loops, ctxt)
 560   {}
 561
 562   /* opt_pass methods: */
 563   virtual bool gate (function *)
 564     {
 565       return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 566     }
 567
 568   virtual unsigned int execute (function *);
 569
 570 }; // class pass_rtl_unroll_loops
 571
 572 unsigned int
 573 pass_rtl_unroll_loops::execute (function *fun)
 574 {
 575   if (number_of_loops (fun) > 1)
 576     {
 577       int flags = 0;
 578       if (dump_file)
 579         df_dump (dump_file);
 580
 581       if (flag_unroll_loops)
 582         flags |= UAP_UNROLL;
 583       if (flag_unroll_all_loops)
 584         flags |= UAP_UNROLL_ALL;
 585
 586       unroll_loops (flags);
 587     }
 588   return 0;
 589 }
 590
 591 } // anon namespace
 592
 593 rtl_opt_pass *
 594 make_pass_rtl_unroll_loops (gcc::context *ctxt)
 595 {
 596   return new pass_rtl_unroll_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   return (flag_branch_on_count_reg && targetm.have_doloop_end ());
 632 }
 633
 634 unsigned int
 635 pass_rtl_doloop::execute (function *fun)
 636 {
 637   if (number_of_loops (fun) > 1)
 638     doloop_optimize_loops ();
 639   return 0;
 640 }
 641
 642 } // anon namespace
 643
 644 rtl_opt_pass *
 645 make_pass_rtl_doloop (gcc::context *ctxt)
 646 {
 647   return new pass_rtl_doloop (ctxt);
 648 }