gcc/tree-ssa-loop.c

   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   /* Disable Graphite passes at -O1 and below.  */
 315   if (optimize < 2)
 316     flag_graphite = 0;
 317
 318   return flag_graphite != 0;
 319 }
 320
 321 struct gimple_opt_pass pass_graphite_transforms =
 322 {
 323  {
 324   GIMPLE_PASS,
 325   "graphite",                           /* name */
 326   gate_graphite_transforms,             /* gate */
 327   graphite_transforms,                  /* execute */
 328   NULL,                                 /* sub */
 329   NULL,                                 /* next */
 330   0,                                    /* static_pass_number */
 331   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
 332   PROP_cfg | PROP_ssa,                  /* properties_required */
 333   0,                                    /* properties_provided */
 334   0,                                    /* properties_destroyed */
 335   0,                                    /* todo_flags_start */
 336   TODO_verify_loops                     /* todo_flags_finish */
 337  }
 338 };
 339
 340 /* Check the correctness of the data dependence analyzers.  */
 341
 342 static unsigned int
 343 check_data_deps (void)
 344 {
 345   if (number_of_loops () <= 1)
 346     return 0;
 347
 348   tree_check_data_deps ();
 349   return 0;
 350 }
 351
 352 static bool
 353 gate_check_data_deps (void)
 354 {
 355   return flag_check_data_deps != 0;
 356 }
 357
 358 struct gimple_opt_pass pass_check_data_deps =
 359 {
 360  {
 361   GIMPLE_PASS,
 362   "ckdd",                               /* name */
 363   gate_check_data_deps,                 /* gate */
 364   check_data_deps,                      /* execute */
 365   NULL,                                 /* sub */
 366   NULL,                                 /* next */
 367   0,                                    /* static_pass_number */
 368   TV_CHECK_DATA_DEPS,                   /* tv_id */
 369   PROP_cfg | PROP_ssa,                  /* properties_required */
 370   0,                                    /* properties_provided */
 371   0,                                    /* properties_destroyed */
 372   0,                                    /* todo_flags_start */
 373   TODO_dump_func                        /* todo_flags_finish */
 374  }
 375 };
 376
 377 /* Canonical induction variable creation pass.  */
 378
 379 static unsigned int
 380 tree_ssa_loop_ivcanon (void)
 381 {
 382   if (number_of_loops () <= 1)
 383     return 0;
 384
 385   return canonicalize_induction_variables ();
 386 }
 387
 388 static bool
 389 gate_tree_ssa_loop_ivcanon (void)
 390 {
 391   return flag_tree_loop_ivcanon != 0;
 392 }
 393
 394 struct gimple_opt_pass pass_iv_canon =
 395 {
 396  {
 397   GIMPLE_PASS,
 398   "ivcanon",                            /* name */
 399   gate_tree_ssa_loop_ivcanon,           /* gate */
 400   tree_ssa_loop_ivcanon,                /* execute */
 401   NULL,                                 /* sub */
 402   NULL,                                 /* next */
 403   0,                                    /* static_pass_number */
 404   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 405   PROP_cfg | PROP_ssa,                  /* properties_required */
 406   0,                                    /* properties_provided */
 407   0,                                    /* properties_destroyed */
 408   0,                                    /* todo_flags_start */
 409   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 410  }
 411 };
 412
 413 /* Propagation of constants using scev.  */
 414
 415 static bool
 416 gate_scev_const_prop (void)
 417 {
 418   return flag_tree_scev_cprop;
 419 }
 420
 421 struct gimple_opt_pass pass_scev_cprop =
 422 {
 423  {
 424   GIMPLE_PASS,
 425   "sccp",                               /* name */
 426   gate_scev_const_prop,                 /* gate */
 427   scev_const_prop,                      /* execute */
 428   NULL,                                 /* sub */
 429   NULL,                                 /* next */
 430   0,                                    /* static_pass_number */
 431   TV_SCEV_CONST,                        /* tv_id */
 432   PROP_cfg | PROP_ssa,                  /* properties_required */
 433   0,                                    /* properties_provided */
 434   0,                                    /* properties_destroyed */
 435   0,                                    /* todo_flags_start */
 436   TODO_dump_func | TODO_cleanup_cfg
 437     | TODO_update_ssa_only_virtuals
 438                                         /* todo_flags_finish */
 439  }
 440 };
 441
 442 /* Record bounds on numbers of iterations of loops.  */
 443
 444 static unsigned int
 445 tree_ssa_loop_bounds (void)
 446 {
 447   if (number_of_loops () <= 1)
 448     return 0;
 449
 450   estimate_numbers_of_iterations ();
 451   scev_reset ();
 452   return 0;
 453 }
 454
 455 struct gimple_opt_pass pass_record_bounds =
 456 {
 457  {
 458   GIMPLE_PASS,
 459   NULL,                                 /* name */
 460   NULL,                                 /* gate */
 461   tree_ssa_loop_bounds,                 /* execute */
 462   NULL,                                 /* sub */
 463   NULL,                                 /* next */
 464   0,                                    /* static_pass_number */
 465   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 466   PROP_cfg | PROP_ssa,                  /* properties_required */
 467   0,                                    /* properties_provided */
 468   0,                                    /* properties_destroyed */
 469   0,                                    /* todo_flags_start */
 470   0                                     /* todo_flags_finish */
 471  }
 472 };
 473
 474 /* Complete unrolling of loops.  */
 475
 476 static unsigned int
 477 tree_complete_unroll (void)
 478 {
 479   if (number_of_loops () <= 1)
 480     return 0;
 481
 482   return tree_unroll_loops_completely (flag_unroll_loops
 483                                        || flag_peel_loops
 484                                        || optimize >= 3, true);
 485 }
 486
 487 static bool
 488 gate_tree_complete_unroll (void)
 489 {
 490   return true;
 491 }
 492
 493 struct gimple_opt_pass pass_complete_unroll =
 494 {
 495  {
 496   GIMPLE_PASS,
 497   "cunroll",                            /* name */
 498   gate_tree_complete_unroll,            /* gate */
 499   tree_complete_unroll,                 /* execute */
 500   NULL,                                 /* sub */
 501   NULL,                                 /* next */
 502   0,                                    /* static_pass_number */
 503   TV_COMPLETE_UNROLL,                   /* tv_id */
 504   PROP_cfg | PROP_ssa,                  /* properties_required */
 505   0,                                    /* properties_provided */
 506   0,                                    /* properties_destroyed */
 507   0,                                    /* todo_flags_start */
 508   TODO_dump_func | TODO_verify_loops
 509     | TODO_ggc_collect                  /* todo_flags_finish */
 510  }
 511 };
 512
 513 /* Complete unrolling of inner loops.  */
 514
 515 static unsigned int
 516 tree_complete_unroll_inner (void)
 517 {
 518   unsigned ret = 0;
 519
 520   loop_optimizer_init (LOOPS_NORMAL
 521                        | LOOPS_HAVE_RECORDED_EXITS);
 522   if (number_of_loops () > 1)
 523     {
 524       scev_initialize ();
 525       ret = tree_unroll_loops_completely (optimize >= 3, false);
 526       free_numbers_of_iterations_estimates ();
 527       scev_finalize ();
 528     }
 529   loop_optimizer_finalize ();
 530
 531   return ret;
 532 }
 533
 534 static bool
 535 gate_tree_complete_unroll_inner (void)
 536 {
 537   return optimize >= 2;
 538 }
 539
 540 struct gimple_opt_pass pass_complete_unrolli =
 541 {
 542  {
 543   GIMPLE_PASS,
 544   "cunrolli",                           /* name */
 545   gate_tree_complete_unroll_inner,      /* gate */
 546   tree_complete_unroll_inner,           /* execute */
 547   NULL,                                 /* sub */
 548   NULL,                                 /* next */
 549   0,                                    /* static_pass_number */
 550   TV_COMPLETE_UNROLL,                   /* tv_id */
 551   PROP_cfg | PROP_ssa,                  /* properties_required */
 552   0,                                    /* properties_provided */
 553   0,                                    /* properties_destroyed */
 554   0,                                    /* todo_flags_start */
 555   TODO_dump_func | TODO_verify_loops
 556     | TODO_ggc_collect                  /* todo_flags_finish */
 557  }
 558 };
 559
 560 /* Parallelization.  */
 561
 562 static bool
 563 gate_tree_parallelize_loops (void)
 564 {
 565   return flag_tree_parallelize_loops > 1;
 566 }
 567
 568 static unsigned
 569 tree_parallelize_loops (void)
 570 {
 571   if (number_of_loops () <= 1)
 572     return 0;
 573
 574   if (parallelize_loops ())
 575     return TODO_cleanup_cfg | TODO_rebuild_alias;
 576   return 0;
 577 }
 578
 579 struct gimple_opt_pass pass_parallelize_loops =
 580 {
 581  {
 582   GIMPLE_PASS,
 583   "parloops",                           /* name */
 584   gate_tree_parallelize_loops,          /* gate */
 585   tree_parallelize_loops,               /* execute */
 586   NULL,                                 /* sub */
 587   NULL,                                 /* next */
 588   0,                                    /* static_pass_number */
 589   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
 590   PROP_cfg | PROP_ssa,                  /* properties_required */
 591   0,                                    /* properties_provided */
 592   0,                                    /* properties_destroyed */
 593   0,                                    /* todo_flags_start */
 594   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 595  }
 596 };
 597
 598 /* Prefetching.  */
 599
 600 static unsigned int
 601 tree_ssa_loop_prefetch (void)
 602 {
 603   if (number_of_loops () <= 1)
 604     return 0;
 605
 606   return tree_ssa_prefetch_arrays ();
 607 }
 608
 609 static bool
 610 gate_tree_ssa_loop_prefetch (void)
 611 {
 612   return flag_prefetch_loop_arrays != 0;
 613 }
 614
 615 struct gimple_opt_pass pass_loop_prefetch =
 616 {
 617  {
 618   GIMPLE_PASS,
 619   "aprefetch",                          /* name */
 620   gate_tree_ssa_loop_prefetch,          /* gate */
 621   tree_ssa_loop_prefetch,               /* execute */
 622   NULL,                                 /* sub */
 623   NULL,                                 /* next */
 624   0,                                    /* static_pass_number */
 625   TV_TREE_PREFETCH,                     /* tv_id */
 626   PROP_cfg | PROP_ssa,                  /* properties_required */
 627   0,                                    /* properties_provided */
 628   0,                                    /* properties_destroyed */
 629   0,                                    /* todo_flags_start */
 630   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 631  }
 632 };
 633
 634 /* Induction variable optimizations.  */
 635
 636 static unsigned int
 637 tree_ssa_loop_ivopts (void)
 638 {
 639   if (number_of_loops () <= 1)
 640     return 0;
 641
 642   tree_ssa_iv_optimize ();
 643   return 0;
 644 }
 645
 646 static bool
 647 gate_tree_ssa_loop_ivopts (void)
 648 {
 649   return flag_ivopts != 0;
 650 }
 651
 652 struct gimple_opt_pass pass_iv_optimize =
 653 {
 654  {
 655   GIMPLE_PASS,
 656   "ivopts",                             /* name */
 657   gate_tree_ssa_loop_ivopts,            /* gate */
 658   tree_ssa_loop_ivopts,                 /* execute */
 659   NULL,                                 /* sub */
 660   NULL,                                 /* next */
 661   0,                                    /* static_pass_number */
 662   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 663   PROP_cfg | PROP_ssa,                  /* properties_required */
 664   0,                                    /* properties_provided */
 665   0,                                    /* properties_destroyed */
 666   0,                                    /* todo_flags_start */
 667   TODO_dump_func | TODO_verify_loops
 668   | TODO_update_ssa | TODO_ggc_collect  /* todo_flags_finish */
 669  }
 670 };
 671
 672 /* Loop optimizer finalization.  */
 673
 674 static unsigned int
 675 tree_ssa_loop_done (void)
 676 {
 677   free_numbers_of_iterations_estimates ();
 678   scev_finalize ();
 679   loop_optimizer_finalize ();
 680   return 0;
 681 }
 682
 683 struct gimple_opt_pass pass_tree_loop_done =
 684 {
 685  {
 686   GIMPLE_PASS,
 687   "loopdone",                           /* name */
 688   NULL,                                 /* gate */
 689   tree_ssa_loop_done,                   /* execute */
 690   NULL,                                 /* sub */
 691   NULL,                                 /* next */
 692   0,                                    /* static_pass_number */
 693   TV_TREE_LOOP_FINI,                    /* tv_id */
 694   PROP_cfg,                             /* properties_required */
 695   0,                                    /* properties_provided */
 696   0,                                    /* properties_destroyed */
 697   0,                                    /* todo_flags_start */
 698   TODO_cleanup_cfg | TODO_dump_func     /* todo_flags_finish */
 699  }
 700 };