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 "regs.h" 26 #include "obstack.h" 27 #include "basic-block.h" 28 #include "cfgloop.h" 29 #include "tree-pass.h" 30 #include "flags.h" 31 #include "df.h" 32 #include "ggc.h" 33 34 35 /* Apply FLAGS to the loop state. */ 36 37 static void 38 apply_loop_flags (unsigned flags) 39 { 40 if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES) 41 { 42 /* If the loops may have multiple latches, we cannot canonicalize 43 them further (and most of the loop manipulation functions will 44 not work). However, we avoid modifying cfg, which some 45 passes may want. */ 46 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES 47 | LOOPS_HAVE_RECORDED_EXITS)) == 0); 48 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES); 49 } 50 else 51 disambiguate_loops_with_multiple_latches (); 52 53 /* Create pre-headers. */ 54 if (flags & LOOPS_HAVE_PREHEADERS) 55 { 56 int cp_flags = CP_SIMPLE_PREHEADERS; 57 58 if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS) 59 cp_flags |= CP_FALLTHRU_PREHEADERS; 60 61 create_preheaders (cp_flags); 62 } 63 64 /* Force all latches to have only single successor. */ 65 if (flags & LOOPS_HAVE_SIMPLE_LATCHES) 66 force_single_succ_latches (); 67 68 /* Mark irreducible loops. */ 69 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 70 mark_irreducible_loops (); 71 72 if (flags & LOOPS_HAVE_RECORDED_EXITS) 73 record_loop_exits (); 74 } 75 76 /* Initialize loop structures. This is used by the tree and RTL loop 77 optimizers. FLAGS specify what properties to compute and/or ensure for 78 loops. */ 79 80 void 81 loop_optimizer_init (unsigned flags) 82 { 83 timevar_push (TV_LOOP_INIT); 84 85 if (!current_loops) 86 { 87 gcc_assert (!(cfun->curr_properties & PROP_loops)); 88 89 /* Find the loops. */ 90 current_loops = flow_loops_find (NULL); 91 } 92 else 93 { 94 gcc_assert (cfun->curr_properties & PROP_loops); 95 96 /* Ensure that the dominators are computed, like flow_loops_find does. */ 97 calculate_dominance_info (CDI_DOMINATORS); 98 99 #ifdef ENABLE_CHECKING 100 verify_loop_structure (); 101 #endif 102 103 /* Clear all flags. */ 104 loops_state_clear (~0U); 105 } 106 107 /* Apply flags to loops. */ 108 apply_loop_flags (flags); 109 110 /* Dump loops. */ 111 flow_loops_dump (dump_file, NULL, 1); 112 113 #ifdef ENABLE_CHECKING 114 verify_loop_structure (); 115 #endif 116 117 timevar_pop (TV_LOOP_INIT); 118 } 119 120 /* Finalize loop structures. */ 121 122 void 123 loop_optimizer_finalize (void) 124 { 125 loop_iterator li; 126 struct loop *loop; 127 basic_block bb; 128 129 timevar_push (TV_LOOP_FINI); 130 131 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 132 release_recorded_exits (); 133 134 /* If we should preserve loop structure, do not free it but clear 135 flags that advanced properties are there as we are not preserving 136 that in full. */ 137 if (cfun->curr_properties & PROP_loops) 138 { 139 loops_state_clear (LOOP_CLOSED_SSA 140 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS 141 | LOOPS_HAVE_PREHEADERS 142 | LOOPS_HAVE_SIMPLE_LATCHES 143 | LOOPS_HAVE_FALLTHRU_PREHEADERS); 144 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES); 145 goto loop_fini_done; 146 } 147 148 gcc_assert (current_loops != NULL); 149 150 FOR_EACH_LOOP (li, loop, 0) 151 { 152 free_simple_loop_desc (loop); 153 } 154 155 /* Clean up. */ 156 flow_loops_free (current_loops); 157 ggc_free (current_loops); 158 current_loops = NULL; 159 160 FOR_ALL_BB (bb) 161 { 162 bb->loop_father = NULL; 163 } 164 165 loop_fini_done: 166 timevar_pop (TV_LOOP_FINI); 167 } 168 169 /* The structure of loops might have changed. Some loops might get removed 170 (and their headers and latches were set to NULL), loop exists might get 171 removed (thus the loop nesting may be wrong), and some blocks and edges 172 were changed (so the information about bb --> loop mapping does not have 173 to be correct). But still for the remaining loops the header dominates 174 the latch, and loops did not get new subloops (new loops might possibly 175 get created, but we are not interested in them). Fix up the mess. 176 177 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are 178 marked in it. 179 180 Returns the number of new discovered loops. */ 181 182 unsigned 183 fix_loop_structure (bitmap changed_bbs) 184 { 185 basic_block bb; 186 int record_exits = 0; 187 loop_iterator li; 188 struct loop *loop; 189 unsigned old_nloops, i; 190 191 timevar_push (TV_LOOP_INIT); 192 193 /* We need exact and fast dominance info to be available. */ 194 gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK); 195 196 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 197 { 198 release_recorded_exits (); 199 record_exits = LOOPS_HAVE_RECORDED_EXITS; 200 } 201 202 /* Remember the depth of the blocks in the loop hierarchy, so that we can 203 recognize blocks whose loop nesting relationship has changed. */ 204 if (changed_bbs) 205 FOR_EACH_BB (bb) 206 bb->aux = (void *) (size_t) loop_depth (bb->loop_father); 207 208 /* Remove the dead loops from structures. We start from the innermost 209 loops, so that when we remove the loops, we know that the loops inside 210 are preserved, and do not waste time relinking loops that will be 211 removed later. */ 212 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) 213 { 214 /* Detect the case that the loop is no longer present even though 215 it wasn't marked for removal. 216 ??? If we do that we can get away with not marking loops for 217 removal at all. And possibly avoid some spurious removals. */ 218 if (loop->header 219 && bb_loop_header_p (loop->header)) 220 continue; 221 222 if (dump_file && (dump_flags & TDF_DETAILS)) 223 fprintf (dump_file, "fix_loop_structure: removing loop %d\n", 224 loop->num); 225 226 while (loop->inner) 227 { 228 struct loop *ploop = loop->inner; 229 flow_loop_tree_node_remove (ploop); 230 flow_loop_tree_node_add (loop_outer (loop), ploop); 231 } 232 233 /* Remove the loop. */ 234 loop->header = NULL; 235 flow_loop_tree_node_remove (loop); 236 } 237 238 /* Remember the number of loops so we can return how many new loops 239 flow_loops_find discovered. */ 240 old_nloops = number_of_loops (); 241 242 /* Re-compute loop structure in-place. */ 243 flow_loops_find (current_loops); 244 245 /* Mark the blocks whose loop has changed. */ 246 if (changed_bbs) 247 { 248 FOR_EACH_BB (bb) 249 { 250 if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux) 251 bitmap_set_bit (changed_bbs, bb->index); 252 253 bb->aux = NULL; 254 } 255 } 256 257 /* Finally free deleted loops. */ 258 FOR_EACH_VEC_ELT (*get_loops (), i, loop) 259 if (loop && loop->header == NULL) 260 { 261 (*get_loops ())[i] = NULL; 262 flow_loop_free (loop); 263 } 264 265 loops_state_clear (LOOPS_NEED_FIXUP); 266 267 /* Apply flags to loops. */ 268 apply_loop_flags (current_loops->state | record_exits); 269 270 #ifdef ENABLE_CHECKING 271 verify_loop_structure (); 272 #endif 273 274 timevar_pop (TV_LOOP_INIT); 275 276 return number_of_loops () - old_nloops; 277 } 278 279 /* Gate for the RTL loop superpass. The actual passes are subpasses. 280 See passes.c for more on that. */ 281 282 static bool 283 gate_handle_loop2 (void) 284 { 285 if (optimize > 0 286 && (flag_move_loop_invariants 287 || flag_unswitch_loops 288 || flag_peel_loops 289 || flag_unroll_loops 290 #ifdef HAVE_doloop_end 291 || (flag_branch_on_count_reg && HAVE_doloop_end) 292 #endif 293 )) 294 return true; 295 else 296 { 297 /* No longer preserve loops, remove them now. */ 298 cfun->curr_properties &= ~PROP_loops; 299 if (current_loops) 300 loop_optimizer_finalize (); 301 return false; 302 } 303 } 304 305 struct rtl_opt_pass pass_loop2 = 306 { 307 { 308 RTL_PASS, 309 "loop2", /* name */ 310 OPTGROUP_LOOP, /* optinfo_flags */ 311 gate_handle_loop2, /* gate */ 312 NULL, /* execute */ 313 NULL, /* sub */ 314 NULL, /* next */ 315 0, /* static_pass_number */ 316 TV_LOOP, /* tv_id */ 317 0, /* properties_required */ 318 0, /* properties_provided */ 319 0, /* properties_destroyed */ 320 0, /* todo_flags_start */ 321 TODO_ggc_collect /* todo_flags_finish */ 322 } 323 }; 324 325 326 /* Initialization of the RTL loop passes. */ 327 static unsigned int 328 rtl_loop_init (void) 329 { 330 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); 331 332 if (dump_file) 333 { 334 dump_reg_info (dump_file); 335 dump_flow_info (dump_file, dump_flags); 336 } 337 338 loop_optimizer_init (LOOPS_NORMAL); 339 return 0; 340 } 341 342 struct rtl_opt_pass pass_rtl_loop_init = 343 { 344 { 345 RTL_PASS, 346 "loop2_init", /* name */ 347 OPTGROUP_LOOP, /* optinfo_flags */ 348 NULL, /* gate */ 349 rtl_loop_init, /* execute */ 350 NULL, /* sub */ 351 NULL, /* next */ 352 0, /* static_pass_number */ 353 TV_LOOP, /* tv_id */ 354 0, /* properties_required */ 355 0, /* properties_provided */ 356 0, /* properties_destroyed */ 357 0, /* todo_flags_start */ 358 TODO_verify_rtl_sharing /* todo_flags_finish */ 359 } 360 }; 361 362 363 /* Finalization of the RTL loop passes. */ 364 365 static unsigned int 366 rtl_loop_done (void) 367 { 368 /* No longer preserve loops, remove them now. */ 369 cfun->curr_properties &= ~PROP_loops; 370 loop_optimizer_finalize (); 371 free_dominance_info (CDI_DOMINATORS); 372 373 cleanup_cfg (0); 374 if (dump_file) 375 { 376 dump_reg_info (dump_file); 377 dump_flow_info (dump_file, dump_flags); 378 } 379 380 return 0; 381 } 382 383 struct rtl_opt_pass pass_rtl_loop_done = 384 { 385 { 386 RTL_PASS, 387 "loop2_done", /* name */ 388 OPTGROUP_LOOP, /* optinfo_flags */ 389 NULL, /* gate */ 390 rtl_loop_done, /* execute */ 391 NULL, /* sub */ 392 NULL, /* next */ 393 0, /* static_pass_number */ 394 TV_LOOP, /* tv_id */ 395 0, /* properties_required */ 396 0, /* properties_provided */ 397 PROP_loops, /* properties_destroyed */ 398 0, /* todo_flags_start */ 399 TODO_verify_flow 400 | TODO_verify_rtl_sharing /* todo_flags_finish */ 401 } 402 }; 403 404 405 /* Loop invariant code motion. */ 406 static bool 407 gate_rtl_move_loop_invariants (void) 408 { 409 return flag_move_loop_invariants; 410 } 411 412 static unsigned int 413 rtl_move_loop_invariants (void) 414 { 415 if (number_of_loops () > 1) 416 move_loop_invariants (); 417 return 0; 418 } 419 420 struct rtl_opt_pass pass_rtl_move_loop_invariants = 421 { 422 { 423 RTL_PASS, 424 "loop2_invariant", /* name */ 425 OPTGROUP_LOOP, /* optinfo_flags */ 426 gate_rtl_move_loop_invariants, /* gate */ 427 rtl_move_loop_invariants, /* execute */ 428 NULL, /* sub */ 429 NULL, /* next */ 430 0, /* static_pass_number */ 431 TV_LOOP_MOVE_INVARIANTS, /* tv_id */ 432 0, /* properties_required */ 433 0, /* properties_provided */ 434 0, /* properties_destroyed */ 435 0, /* todo_flags_start */ 436 TODO_df_verify | 437 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */ 438 } 439 }; 440 441 442 /* Loop unswitching for RTL. */ 443 static bool 444 gate_rtl_unswitch (void) 445 { 446 return flag_unswitch_loops; 447 } 448 449 static unsigned int 450 rtl_unswitch (void) 451 { 452 if (number_of_loops () > 1) 453 unswitch_loops (); 454 return 0; 455 } 456 457 struct rtl_opt_pass pass_rtl_unswitch = 458 { 459 { 460 RTL_PASS, 461 "loop2_unswitch", /* name */ 462 OPTGROUP_LOOP, /* optinfo_flags */ 463 gate_rtl_unswitch, /* gate */ 464 rtl_unswitch, /* execute */ 465 NULL, /* sub */ 466 NULL, /* next */ 467 0, /* static_pass_number */ 468 TV_LOOP_UNSWITCH, /* tv_id */ 469 0, /* properties_required */ 470 0, /* properties_provided */ 471 0, /* properties_destroyed */ 472 0, /* todo_flags_start */ 473 TODO_verify_rtl_sharing, /* todo_flags_finish */ 474 } 475 }; 476 477 478 /* Loop unswitching for RTL. */ 479 static bool 480 gate_rtl_unroll_and_peel_loops (void) 481 { 482 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 483 } 484 485 static unsigned int 486 rtl_unroll_and_peel_loops (void) 487 { 488 if (number_of_loops () > 1) 489 { 490 int flags = 0; 491 if (dump_file) 492 df_dump (dump_file); 493 494 if (flag_peel_loops) 495 flags |= UAP_PEEL; 496 if (flag_unroll_loops) 497 flags |= UAP_UNROLL; 498 if (flag_unroll_all_loops) 499 flags |= UAP_UNROLL_ALL; 500 501 unroll_and_peel_loops (flags); 502 } 503 return 0; 504 } 505 506 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops = 507 { 508 { 509 RTL_PASS, 510 "loop2_unroll", /* name */ 511 OPTGROUP_LOOP, /* optinfo_flags */ 512 gate_rtl_unroll_and_peel_loops, /* gate */ 513 rtl_unroll_and_peel_loops, /* execute */ 514 NULL, /* sub */ 515 NULL, /* next */ 516 0, /* static_pass_number */ 517 TV_LOOP_UNROLL, /* 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 526 527 /* The doloop optimization. */ 528 static bool 529 gate_rtl_doloop (void) 530 { 531 #ifdef HAVE_doloop_end 532 return (flag_branch_on_count_reg && HAVE_doloop_end); 533 #else 534 return 0; 535 #endif 536 } 537 538 static unsigned int 539 rtl_doloop (void) 540 { 541 #ifdef HAVE_doloop_end 542 if (number_of_loops () > 1) 543 doloop_optimize_loops (); 544 #endif 545 return 0; 546 } 547 548 struct rtl_opt_pass pass_rtl_doloop = 549 { 550 { 551 RTL_PASS, 552 "loop2_doloop", /* name */ 553 OPTGROUP_LOOP, /* optinfo_flags */ 554 gate_rtl_doloop, /* gate */ 555 rtl_doloop, /* execute */ 556 NULL, /* sub */ 557 NULL, /* next */ 558 0, /* static_pass_number */ 559 TV_LOOP_DOLOOP, /* tv_id */ 560 0, /* properties_required */ 561 0, /* properties_provided */ 562 0, /* properties_destroyed */ 563 0, /* todo_flags_start */ 564 TODO_verify_rtl_sharing /* todo_flags_finish */ 565 } 566 }; 567