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