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