1 /* Loop optimizations over tree-ssa. 2 Copyright (C) 2003-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 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY 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 "tree.h" 25 #include "tm_p.h" 26 #include "basic-block.h" 27 #include "tree-flow.h" 28 #include "tree-pass.h" 29 #include "cfgloop.h" 30 #include "flags.h" 31 #include "tree-inline.h" 32 #include "tree-scalar-evolution.h" 33 #include "diagnostic-core.h" 34 #include "tree-vectorizer.h" 35 36 /* The loop superpass. */ 37 38 static bool 39 gate_tree_loop (void) 40 { 41 return flag_tree_loop_optimize != 0; 42 } 43 44 struct gimple_opt_pass pass_tree_loop = 45 { 46 { 47 GIMPLE_PASS, 48 "loop", /* name */ 49 OPTGROUP_LOOP, /* optinfo_flags */ 50 gate_tree_loop, /* gate */ 51 NULL, /* execute */ 52 NULL, /* sub */ 53 NULL, /* next */ 54 0, /* static_pass_number */ 55 TV_TREE_LOOP, /* tv_id */ 56 PROP_cfg, /* properties_required */ 57 0, /* properties_provided */ 58 0, /* properties_destroyed */ 59 TODO_ggc_collect, /* todo_flags_start */ 60 TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */ 61 } 62 }; 63 64 /* Loop optimizer initialization. */ 65 66 static unsigned int 67 tree_ssa_loop_init (void) 68 { 69 loop_optimizer_init (LOOPS_NORMAL 70 | LOOPS_HAVE_RECORDED_EXITS); 71 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 72 73 /* We might discover new loops, e.g. when turning irreducible 74 regions into reducible. */ 75 scev_initialize (); 76 77 if (number_of_loops () <= 1) 78 return 0; 79 80 return 0; 81 } 82 83 struct gimple_opt_pass pass_tree_loop_init = 84 { 85 { 86 GIMPLE_PASS, 87 "loopinit", /* name */ 88 OPTGROUP_LOOP, /* optinfo_flags */ 89 NULL, /* gate */ 90 tree_ssa_loop_init, /* execute */ 91 NULL, /* sub */ 92 NULL, /* next */ 93 0, /* static_pass_number */ 94 TV_NONE, /* tv_id */ 95 PROP_cfg, /* properties_required */ 96 PROP_loops, /* properties_provided */ 97 0, /* properties_destroyed */ 98 0, /* todo_flags_start */ 99 0 /* todo_flags_finish */ 100 } 101 }; 102 103 /* Loop invariant motion pass. */ 104 105 static unsigned int 106 tree_ssa_loop_im (void) 107 { 108 if (number_of_loops () <= 1) 109 return 0; 110 111 return tree_ssa_lim (); 112 } 113 114 static bool 115 gate_tree_ssa_loop_im (void) 116 { 117 return flag_tree_loop_im != 0; 118 } 119 120 struct gimple_opt_pass pass_lim = 121 { 122 { 123 GIMPLE_PASS, 124 "lim", /* name */ 125 OPTGROUP_LOOP, /* optinfo_flags */ 126 gate_tree_ssa_loop_im, /* gate */ 127 tree_ssa_loop_im, /* execute */ 128 NULL, /* sub */ 129 NULL, /* next */ 130 0, /* static_pass_number */ 131 TV_LIM, /* tv_id */ 132 PROP_cfg, /* properties_required */ 133 0, /* properties_provided */ 134 0, /* properties_destroyed */ 135 0, /* todo_flags_start */ 136 0 /* todo_flags_finish */ 137 } 138 }; 139 140 /* Loop unswitching pass. */ 141 142 static unsigned int 143 tree_ssa_loop_unswitch (void) 144 { 145 if (number_of_loops () <= 1) 146 return 0; 147 148 return tree_ssa_unswitch_loops (); 149 } 150 151 static bool 152 gate_tree_ssa_loop_unswitch (void) 153 { 154 return flag_unswitch_loops != 0; 155 } 156 157 struct gimple_opt_pass pass_tree_unswitch = 158 { 159 { 160 GIMPLE_PASS, 161 "unswitch", /* name */ 162 OPTGROUP_LOOP, /* optinfo_flags */ 163 gate_tree_ssa_loop_unswitch, /* gate */ 164 tree_ssa_loop_unswitch, /* execute */ 165 NULL, /* sub */ 166 NULL, /* next */ 167 0, /* static_pass_number */ 168 TV_TREE_LOOP_UNSWITCH, /* tv_id */ 169 PROP_cfg, /* properties_required */ 170 0, /* properties_provided */ 171 0, /* properties_destroyed */ 172 0, /* todo_flags_start */ 173 TODO_ggc_collect /* todo_flags_finish */ 174 } 175 }; 176 177 /* Predictive commoning. */ 178 179 static unsigned 180 run_tree_predictive_commoning (void) 181 { 182 if (!current_loops) 183 return 0; 184 185 return tree_predictive_commoning (); 186 } 187 188 static bool 189 gate_tree_predictive_commoning (void) 190 { 191 return flag_predictive_commoning != 0; 192 } 193 194 struct gimple_opt_pass pass_predcom = 195 { 196 { 197 GIMPLE_PASS, 198 "pcom", /* name */ 199 OPTGROUP_LOOP, /* optinfo_flags */ 200 gate_tree_predictive_commoning, /* gate */ 201 run_tree_predictive_commoning, /* execute */ 202 NULL, /* sub */ 203 NULL, /* next */ 204 0, /* static_pass_number */ 205 TV_PREDCOM, /* tv_id */ 206 PROP_cfg, /* properties_required */ 207 0, /* properties_provided */ 208 0, /* properties_destroyed */ 209 0, /* todo_flags_start */ 210 TODO_update_ssa_only_virtuals /* todo_flags_finish */ 211 } 212 }; 213 214 /* Loop autovectorization. */ 215 216 static unsigned int 217 tree_vectorize (void) 218 { 219 if (number_of_loops () <= 1) 220 return 0; 221 222 return vectorize_loops (); 223 } 224 225 static bool 226 gate_tree_vectorize (void) 227 { 228 return flag_tree_vectorize; 229 } 230 231 struct gimple_opt_pass pass_vectorize = 232 { 233 { 234 GIMPLE_PASS, 235 "vect", /* name */ 236 OPTGROUP_LOOP 237 | OPTGROUP_VEC, /* optinfo_flags */ 238 gate_tree_vectorize, /* gate */ 239 tree_vectorize, /* execute */ 240 NULL, /* sub */ 241 NULL, /* next */ 242 0, /* static_pass_number */ 243 TV_TREE_VECTORIZATION, /* tv_id */ 244 PROP_cfg | PROP_ssa, /* properties_required */ 245 0, /* properties_provided */ 246 0, /* properties_destroyed */ 247 0, /* todo_flags_start */ 248 TODO_update_ssa 249 | TODO_ggc_collect /* todo_flags_finish */ 250 } 251 }; 252 253 /* GRAPHITE optimizations. */ 254 255 static unsigned int 256 graphite_transforms (void) 257 { 258 if (!current_loops) 259 return 0; 260 261 graphite_transform_loops (); 262 263 return 0; 264 } 265 266 static bool 267 gate_graphite_transforms (void) 268 { 269 /* Enable -fgraphite pass if any one of the graphite optimization flags 270 is turned on. */ 271 if (flag_loop_block 272 || flag_loop_interchange 273 || flag_loop_strip_mine 274 || flag_graphite_identity 275 || flag_loop_parallelize_all 276 || flag_loop_optimize_isl) 277 flag_graphite = 1; 278 279 return flag_graphite != 0; 280 } 281 282 struct gimple_opt_pass pass_graphite = 283 { 284 { 285 GIMPLE_PASS, 286 "graphite0", /* name */ 287 OPTGROUP_LOOP, /* optinfo_flags */ 288 gate_graphite_transforms, /* gate */ 289 NULL, /* execute */ 290 NULL, /* sub */ 291 NULL, /* next */ 292 0, /* static_pass_number */ 293 TV_GRAPHITE, /* tv_id */ 294 PROP_cfg | PROP_ssa, /* properties_required */ 295 0, /* properties_provided */ 296 0, /* properties_destroyed */ 297 0, /* todo_flags_start */ 298 0 /* todo_flags_finish */ 299 } 300 }; 301 302 struct gimple_opt_pass pass_graphite_transforms = 303 { 304 { 305 GIMPLE_PASS, 306 "graphite", /* name */ 307 OPTGROUP_LOOP, /* optinfo_flags */ 308 gate_graphite_transforms, /* gate */ 309 graphite_transforms, /* execute */ 310 NULL, /* sub */ 311 NULL, /* next */ 312 0, /* static_pass_number */ 313 TV_GRAPHITE_TRANSFORMS, /* tv_id */ 314 PROP_cfg | PROP_ssa, /* properties_required */ 315 0, /* properties_provided */ 316 0, /* properties_destroyed */ 317 0, /* todo_flags_start */ 318 0 /* todo_flags_finish */ 319 } 320 }; 321 322 /* Check the correctness of the data dependence analyzers. */ 323 324 static unsigned int 325 check_data_deps (void) 326 { 327 if (number_of_loops () <= 1) 328 return 0; 329 330 tree_check_data_deps (); 331 return 0; 332 } 333 334 static bool 335 gate_check_data_deps (void) 336 { 337 return flag_check_data_deps != 0; 338 } 339 340 struct gimple_opt_pass pass_check_data_deps = 341 { 342 { 343 GIMPLE_PASS, 344 "ckdd", /* name */ 345 OPTGROUP_LOOP, /* optinfo_flags */ 346 gate_check_data_deps, /* gate */ 347 check_data_deps, /* execute */ 348 NULL, /* sub */ 349 NULL, /* next */ 350 0, /* static_pass_number */ 351 TV_CHECK_DATA_DEPS, /* tv_id */ 352 PROP_cfg | PROP_ssa, /* properties_required */ 353 0, /* properties_provided */ 354 0, /* properties_destroyed */ 355 0, /* todo_flags_start */ 356 0 /* todo_flags_finish */ 357 } 358 }; 359 360 /* Canonical induction variable creation pass. */ 361 362 static unsigned int 363 tree_ssa_loop_ivcanon (void) 364 { 365 if (number_of_loops () <= 1) 366 return 0; 367 368 return canonicalize_induction_variables (); 369 } 370 371 static bool 372 gate_tree_ssa_loop_ivcanon (void) 373 { 374 return flag_tree_loop_ivcanon != 0; 375 } 376 377 struct gimple_opt_pass pass_iv_canon = 378 { 379 { 380 GIMPLE_PASS, 381 "ivcanon", /* name */ 382 OPTGROUP_LOOP, /* optinfo_flags */ 383 gate_tree_ssa_loop_ivcanon, /* gate */ 384 tree_ssa_loop_ivcanon, /* execute */ 385 NULL, /* sub */ 386 NULL, /* next */ 387 0, /* static_pass_number */ 388 TV_TREE_LOOP_IVCANON, /* tv_id */ 389 PROP_cfg | PROP_ssa, /* properties_required */ 390 0, /* properties_provided */ 391 0, /* properties_destroyed */ 392 0, /* todo_flags_start */ 393 0 /* todo_flags_finish */ 394 } 395 }; 396 397 /* Propagation of constants using scev. */ 398 399 static bool 400 gate_scev_const_prop (void) 401 { 402 return flag_tree_scev_cprop; 403 } 404 405 struct gimple_opt_pass pass_scev_cprop = 406 { 407 { 408 GIMPLE_PASS, 409 "sccp", /* name */ 410 OPTGROUP_LOOP, /* optinfo_flags */ 411 gate_scev_const_prop, /* gate */ 412 scev_const_prop, /* execute */ 413 NULL, /* sub */ 414 NULL, /* next */ 415 0, /* static_pass_number */ 416 TV_SCEV_CONST, /* tv_id */ 417 PROP_cfg | PROP_ssa, /* properties_required */ 418 0, /* properties_provided */ 419 0, /* properties_destroyed */ 420 0, /* todo_flags_start */ 421 TODO_cleanup_cfg 422 | TODO_update_ssa_only_virtuals 423 /* todo_flags_finish */ 424 } 425 }; 426 427 /* Record bounds on numbers of iterations of loops. */ 428 429 static unsigned int 430 tree_ssa_loop_bounds (void) 431 { 432 if (number_of_loops () <= 1) 433 return 0; 434 435 estimate_numbers_of_iterations (); 436 scev_reset (); 437 return 0; 438 } 439 440 struct gimple_opt_pass pass_record_bounds = 441 { 442 { 443 GIMPLE_PASS, 444 "*record_bounds", /* name */ 445 OPTGROUP_NONE, /* optinfo_flags */ 446 NULL, /* gate */ 447 tree_ssa_loop_bounds, /* execute */ 448 NULL, /* sub */ 449 NULL, /* next */ 450 0, /* static_pass_number */ 451 TV_TREE_LOOP_BOUNDS, /* tv_id */ 452 PROP_cfg | PROP_ssa, /* properties_required */ 453 0, /* properties_provided */ 454 0, /* properties_destroyed */ 455 0, /* todo_flags_start */ 456 0 /* todo_flags_finish */ 457 } 458 }; 459 460 /* Complete unrolling of loops. */ 461 462 static unsigned int 463 tree_complete_unroll (void) 464 { 465 if (number_of_loops () <= 1) 466 return 0; 467 468 return tree_unroll_loops_completely (flag_unroll_loops 469 || flag_peel_loops 470 || optimize >= 3, true); 471 } 472 473 static bool 474 gate_tree_complete_unroll (void) 475 { 476 return true; 477 } 478 479 struct gimple_opt_pass pass_complete_unroll = 480 { 481 { 482 GIMPLE_PASS, 483 "cunroll", /* name */ 484 OPTGROUP_LOOP, /* optinfo_flags */ 485 gate_tree_complete_unroll, /* gate */ 486 tree_complete_unroll, /* execute */ 487 NULL, /* sub */ 488 NULL, /* next */ 489 0, /* static_pass_number */ 490 TV_COMPLETE_UNROLL, /* tv_id */ 491 PROP_cfg | PROP_ssa, /* properties_required */ 492 0, /* properties_provided */ 493 0, /* properties_destroyed */ 494 0, /* todo_flags_start */ 495 TODO_ggc_collect /* todo_flags_finish */ 496 } 497 }; 498 499 /* Complete unrolling of inner loops. */ 500 501 static unsigned int 502 tree_complete_unroll_inner (void) 503 { 504 unsigned ret = 0; 505 506 loop_optimizer_init (LOOPS_NORMAL 507 | LOOPS_HAVE_RECORDED_EXITS); 508 if (number_of_loops () > 1) 509 { 510 scev_initialize (); 511 ret = tree_unroll_loops_completely (optimize >= 3, false); 512 free_numbers_of_iterations_estimates (); 513 scev_finalize (); 514 } 515 loop_optimizer_finalize (); 516 517 return ret; 518 } 519 520 static bool 521 gate_tree_complete_unroll_inner (void) 522 { 523 return optimize >= 2; 524 } 525 526 struct gimple_opt_pass pass_complete_unrolli = 527 { 528 { 529 GIMPLE_PASS, 530 "cunrolli", /* name */ 531 OPTGROUP_LOOP, /* optinfo_flags */ 532 gate_tree_complete_unroll_inner, /* gate */ 533 tree_complete_unroll_inner, /* execute */ 534 NULL, /* sub */ 535 NULL, /* next */ 536 0, /* static_pass_number */ 537 TV_COMPLETE_UNROLL, /* tv_id */ 538 PROP_cfg | PROP_ssa, /* properties_required */ 539 0, /* properties_provided */ 540 0, /* properties_destroyed */ 541 0, /* todo_flags_start */ 542 TODO_verify_flow 543 | TODO_ggc_collect /* todo_flags_finish */ 544 } 545 }; 546 547 /* Parallelization. */ 548 549 static bool 550 gate_tree_parallelize_loops (void) 551 { 552 return flag_tree_parallelize_loops > 1; 553 } 554 555 static unsigned 556 tree_parallelize_loops (void) 557 { 558 if (number_of_loops () <= 1) 559 return 0; 560 561 if (parallelize_loops ()) 562 return TODO_cleanup_cfg | TODO_rebuild_alias; 563 return 0; 564 } 565 566 struct gimple_opt_pass pass_parallelize_loops = 567 { 568 { 569 GIMPLE_PASS, 570 "parloops", /* name */ 571 OPTGROUP_LOOP, /* optinfo_flags */ 572 gate_tree_parallelize_loops, /* gate */ 573 tree_parallelize_loops, /* execute */ 574 NULL, /* sub */ 575 NULL, /* next */ 576 0, /* static_pass_number */ 577 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */ 578 PROP_cfg | PROP_ssa, /* properties_required */ 579 0, /* properties_provided */ 580 0, /* properties_destroyed */ 581 0, /* todo_flags_start */ 582 0 /* todo_flags_finish */ 583 } 584 }; 585 586 /* Prefetching. */ 587 588 static unsigned int 589 tree_ssa_loop_prefetch (void) 590 { 591 if (number_of_loops () <= 1) 592 return 0; 593 594 return tree_ssa_prefetch_arrays (); 595 } 596 597 static bool 598 gate_tree_ssa_loop_prefetch (void) 599 { 600 return flag_prefetch_loop_arrays > 0; 601 } 602 603 struct gimple_opt_pass pass_loop_prefetch = 604 { 605 { 606 GIMPLE_PASS, 607 "aprefetch", /* name */ 608 OPTGROUP_LOOP, /* optinfo_flags */ 609 gate_tree_ssa_loop_prefetch, /* gate */ 610 tree_ssa_loop_prefetch, /* execute */ 611 NULL, /* sub */ 612 NULL, /* next */ 613 0, /* static_pass_number */ 614 TV_TREE_PREFETCH, /* tv_id */ 615 PROP_cfg | PROP_ssa, /* properties_required */ 616 0, /* properties_provided */ 617 0, /* properties_destroyed */ 618 0, /* todo_flags_start */ 619 0 /* todo_flags_finish */ 620 } 621 }; 622 623 /* Induction variable optimizations. */ 624 625 static unsigned int 626 tree_ssa_loop_ivopts (void) 627 { 628 if (number_of_loops () <= 1) 629 return 0; 630 631 tree_ssa_iv_optimize (); 632 return 0; 633 } 634 635 static bool 636 gate_tree_ssa_loop_ivopts (void) 637 { 638 return flag_ivopts != 0; 639 } 640 641 struct gimple_opt_pass pass_iv_optimize = 642 { 643 { 644 GIMPLE_PASS, 645 "ivopts", /* name */ 646 OPTGROUP_LOOP, /* optinfo_flags */ 647 gate_tree_ssa_loop_ivopts, /* gate */ 648 tree_ssa_loop_ivopts, /* execute */ 649 NULL, /* sub */ 650 NULL, /* next */ 651 0, /* static_pass_number */ 652 TV_TREE_LOOP_IVOPTS, /* tv_id */ 653 PROP_cfg | PROP_ssa, /* properties_required */ 654 0, /* properties_provided */ 655 0, /* properties_destroyed */ 656 0, /* todo_flags_start */ 657 TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */ 658 } 659 }; 660 661 /* Loop optimizer finalization. */ 662 663 static unsigned int 664 tree_ssa_loop_done (void) 665 { 666 free_numbers_of_iterations_estimates (); 667 scev_finalize (); 668 loop_optimizer_finalize (); 669 return 0; 670 } 671 672 struct gimple_opt_pass pass_tree_loop_done = 673 { 674 { 675 GIMPLE_PASS, 676 "loopdone", /* name */ 677 OPTGROUP_LOOP, /* optinfo_flags */ 678 NULL, /* gate */ 679 tree_ssa_loop_done, /* execute */ 680 NULL, /* sub */ 681 NULL, /* next */ 682 0, /* static_pass_number */ 683 TV_NONE, /* tv_id */ 684 PROP_cfg, /* properties_required */ 685 0, /* properties_provided */ 686 0, /* properties_destroyed */ 687 0, /* todo_flags_start */ 688 TODO_cleanup_cfg 689 | TODO_verify_flow /* todo_flags_finish */ 690 } 691 }; 692