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