gcc/tree-ssa-loop.c

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