1/* Loop optimizations over tree-ssa. 2 Copyright (C) 2003, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 3, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; 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 "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 44static bool 45gate_tree_loop (void) 46{ 47 return flag_tree_loop_optimize != 0; 48} 49 50struct 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 71static unsigned int 72tree_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 85struct 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 106static unsigned int 107tree_ssa_loop_im (void) 108{ 109 if (number_of_loops () <= 1) 110 return 0; 111 112 tree_ssa_lim (); 113 return 0; 114} 115 116static bool 117gate_tree_ssa_loop_im (void) 118{ 119 return flag_tree_loop_im != 0; 120} 121 122struct 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 143static unsigned int 144tree_ssa_loop_unswitch (void) 145{ 146 if (number_of_loops () <= 1) 147 return 0; 148 149 return tree_ssa_unswitch_loops (); 150} 151 152static bool 153gate_tree_ssa_loop_unswitch (void) 154{ 155 return flag_unswitch_loops != 0; 156} 157 158struct 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 180static unsigned 181run_tree_predictive_commoning (void) 182{ 183 if (!current_loops) 184 return 0; 185 186 tree_predictive_commoning (); 187 return 0; 188} 189 190static bool 191gate_tree_predictive_commoning (void) 192{ 193 return flag_predictive_commoning != 0; 194} 195 196struct 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 218static unsigned int 219tree_vectorize (void) 220{ 221 if (number_of_loops () <= 1) 222 return 0; 223 224 return vectorize_loops (); 225} 226 227static bool 228gate_tree_vectorize (void) 229{ 230 return flag_tree_vectorize; 231} 232 233struct 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 255static unsigned int 256tree_linear_transform (void) 257{ 258 if (number_of_loops () <= 1) 259 return 0; 260 261 linear_transform_loops (); 262 return 0; 263} 264 265static bool 266gate_tree_linear_transform (void) 267{ 268 return flag_tree_loop_linear != 0; 269} 270 271struct 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 294static unsigned int 295graphite_transforms (void) 296{ 297 if (!current_loops) 298 return 0; 299 300 graphite_transform_loops (); 301 302 return 0; 303} 304 305static bool 306gate_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 317struct 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 338static unsigned int 339check_data_deps (void) 340{ 341 if (number_of_loops () <= 1) 342 return 0; 343 344 tree_check_data_deps (); 345 return 0; 346} 347 348static bool 349gate_check_data_deps (void) 350{ 351 return flag_check_data_deps != 0; 352} 353 354struct 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 375static unsigned int 376tree_ssa_loop_ivcanon (void) 377{ 378 if (number_of_loops () <= 1) 379 return 0; 380 381 return canonicalize_induction_variables (); 382} 383 384static bool 385gate_tree_ssa_loop_ivcanon (void) 386{ 387 return flag_tree_loop_ivcanon != 0; 388} 389 390struct 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 411static bool 412gate_scev_const_prop (void) 413{ 414 return flag_tree_scev_cprop; 415} 416 417struct 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 440static unsigned int 441tree_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 451struct 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 472static unsigned int 473tree_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 483static bool 484gate_tree_complete_unroll (void) 485{ 486 return true; 487} 488 489struct 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 511static unsigned int 512tree_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 530static bool 531gate_tree_complete_unroll_inner (void) 532{ 533 return optimize >= 2; 534} 535 536struct 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 558static bool 559gate_tree_parallelize_loops (void) 560{ 561 return flag_tree_parallelize_loops > 1; 562} 563 564static unsigned 565tree_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 575struct 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 596static unsigned int 597tree_ssa_loop_prefetch (void) 598{ 599 if (number_of_loops () <= 1) 600 return 0; 601 602 return tree_ssa_prefetch_arrays (); 603} 604 605static bool 606gate_tree_ssa_loop_prefetch (void) 607{ 608 return flag_prefetch_loop_arrays != 0; 609} 610 611struct 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 632static unsigned int 633tree_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 642static bool 643gate_tree_ssa_loop_ivopts (void) 644{ 645 return flag_ivopts != 0; 646} 647 648struct 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 670static unsigned int 671tree_ssa_loop_done (void) 672{ 673 free_numbers_of_iterations_estimates (); 674 scev_finalize (); 675 loop_optimizer_finalize (); 676 return 0; 677} 678 679struct 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