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