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