gcc/tree-ssa-loop.c

   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 };