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   0,                                    /* todo_flags_start */
  60   TODO_verify_ssa                       /* 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 (cfun) <= 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   0,                                    /* 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 (cfun) <= 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 (cfun) <= 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   0                                     /* 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 (cfun) <= 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   0                                     /* todo_flags_finish */
 249  }
 250 };
 251
 252 /* GRAPHITE optimizations.  */
 253
 254 static unsigned int
 255 graphite_transforms (void)
 256 {
 257   if (!current_loops)
 258     return 0;
 259
 260   graphite_transform_loops ();
 261
 262   return 0;
 263 }
 264
 265 static bool
 266 gate_graphite_transforms (void)
 267 {
 268   /* Enable -fgraphite pass if any one of the graphite optimization flags
 269      is turned on.  */
 270   if (flag_loop_block
 271       || flag_loop_interchange
 272       || flag_loop_strip_mine
 273       || flag_graphite_identity
 274       || flag_loop_parallelize_all
 275       || flag_loop_optimize_isl)
 276     flag_graphite = 1;
 277
 278   return flag_graphite != 0;
 279 }
 280
 281 struct gimple_opt_pass pass_graphite =
 282 {
 283  {
 284   GIMPLE_PASS,
 285   "graphite0",                          /* name */
 286   OPTGROUP_LOOP,                        /* optinfo_flags */
 287   gate_graphite_transforms,             /* gate */
 288   NULL,                                 /* execute */
 289   NULL,                                 /* sub */
 290   NULL,                                 /* next */
 291   0,                                    /* static_pass_number */
 292   TV_GRAPHITE,                          /* tv_id */
 293   PROP_cfg | PROP_ssa,                  /* properties_required */
 294   0,                                    /* properties_provided */
 295   0,                                    /* properties_destroyed */
 296   0,                                    /* todo_flags_start */
 297   0                                     /* todo_flags_finish */
 298  }
 299 };
 300
 301 struct gimple_opt_pass pass_graphite_transforms =
 302 {
 303  {
 304   GIMPLE_PASS,
 305   "graphite",                           /* name */
 306   OPTGROUP_LOOP,                        /* optinfo_flags */
 307   gate_graphite_transforms,             /* gate */
 308   graphite_transforms,                  /* execute */
 309   NULL,                                 /* sub */
 310   NULL,                                 /* next */
 311   0,                                    /* static_pass_number */
 312   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
 313   PROP_cfg | PROP_ssa,                  /* properties_required */
 314   0,                                    /* properties_provided */
 315   0,                                    /* properties_destroyed */
 316   0,                                    /* todo_flags_start */
 317   0                                     /* todo_flags_finish */
 318  }
 319 };
 320
 321 /* Check the correctness of the data dependence analyzers.  */
 322
 323 static unsigned int
 324 check_data_deps (void)
 325 {
 326   if (number_of_loops (cfun) <= 1)
 327     return 0;
 328
 329   tree_check_data_deps ();
 330   return 0;
 331 }
 332
 333 static bool
 334 gate_check_data_deps (void)
 335 {
 336   return flag_check_data_deps != 0;
 337 }
 338
 339 struct gimple_opt_pass pass_check_data_deps =
 340 {
 341  {
 342   GIMPLE_PASS,
 343   "ckdd",                               /* name */
 344   OPTGROUP_LOOP,                        /* optinfo_flags */
 345   gate_check_data_deps,                 /* gate */
 346   check_data_deps,                      /* execute */
 347   NULL,                                 /* sub */
 348   NULL,                                 /* next */
 349   0,                                    /* static_pass_number */
 350   TV_CHECK_DATA_DEPS,                   /* tv_id */
 351   PROP_cfg | PROP_ssa,                  /* properties_required */
 352   0,                                    /* properties_provided */
 353   0,                                    /* properties_destroyed */
 354   0,                                    /* todo_flags_start */
 355   0                                     /* todo_flags_finish */
 356  }
 357 };
 358
 359 /* Canonical induction variable creation pass.  */
 360
 361 static unsigned int
 362 tree_ssa_loop_ivcanon (void)
 363 {
 364   if (number_of_loops (cfun) <= 1)
 365     return 0;
 366
 367   return canonicalize_induction_variables ();
 368 }
 369
 370 static bool
 371 gate_tree_ssa_loop_ivcanon (void)
 372 {
 373   return flag_tree_loop_ivcanon != 0;
 374 }
 375
 376 struct gimple_opt_pass pass_iv_canon =
 377 {
 378  {
 379   GIMPLE_PASS,
 380   "ivcanon",                            /* name */
 381   OPTGROUP_LOOP,                        /* optinfo_flags */
 382   gate_tree_ssa_loop_ivcanon,           /* gate */
 383   tree_ssa_loop_ivcanon,                /* execute */
 384   NULL,                                 /* sub */
 385   NULL,                                 /* next */
 386   0,                                    /* static_pass_number */
 387   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 388   PROP_cfg | PROP_ssa,                  /* properties_required */
 389   0,                                    /* properties_provided */
 390   0,                                    /* properties_destroyed */
 391   0,                                    /* todo_flags_start */
 392   0                                     /* todo_flags_finish */
 393  }
 394 };
 395
 396 /* Propagation of constants using scev.  */
 397
 398 static bool
 399 gate_scev_const_prop (void)
 400 {
 401   return flag_tree_scev_cprop;
 402 }
 403
 404 struct gimple_opt_pass pass_scev_cprop =
 405 {
 406  {
 407   GIMPLE_PASS,
 408   "sccp",                               /* name */
 409   OPTGROUP_LOOP,                        /* optinfo_flags */
 410   gate_scev_const_prop,                 /* gate */
 411   scev_const_prop,                      /* execute */
 412   NULL,                                 /* sub */
 413   NULL,                                 /* next */
 414   0,                                    /* static_pass_number */
 415   TV_SCEV_CONST,                        /* tv_id */
 416   PROP_cfg | PROP_ssa,                  /* properties_required */
 417   0,                                    /* properties_provided */
 418   0,                                    /* properties_destroyed */
 419   0,                                    /* todo_flags_start */
 420   TODO_cleanup_cfg
 421     | TODO_update_ssa_only_virtuals
 422                                         /* todo_flags_finish */
 423  }
 424 };
 425
 426 /* Record bounds on numbers of iterations of loops.  */
 427
 428 static unsigned int
 429 tree_ssa_loop_bounds (void)
 430 {
 431   if (number_of_loops (cfun) <= 1)
 432     return 0;
 433
 434   estimate_numbers_of_iterations ();
 435   scev_reset ();
 436   return 0;
 437 }
 438
 439 struct gimple_opt_pass pass_record_bounds =
 440 {
 441  {
 442   GIMPLE_PASS,
 443   "*record_bounds",                     /* name */
 444   OPTGROUP_NONE,                        /* optinfo_flags */
 445   NULL,                                 /* gate */
 446   tree_ssa_loop_bounds,                 /* execute */
 447   NULL,                                 /* sub */
 448   NULL,                                 /* next */
 449   0,                                    /* static_pass_number */
 450   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 451   PROP_cfg | PROP_ssa,                  /* properties_required */
 452   0,                                    /* properties_provided */
 453   0,                                    /* properties_destroyed */
 454   0,                                    /* todo_flags_start */
 455   0                                     /* todo_flags_finish */
 456  }
 457 };
 458
 459 /* Complete unrolling of loops.  */
 460
 461 static unsigned int
 462 tree_complete_unroll (void)
 463 {
 464   if (number_of_loops (cfun) <= 1)
 465     return 0;
 466
 467   return tree_unroll_loops_completely (flag_unroll_loops
 468                                        || flag_peel_loops
 469                                        || optimize >= 3, true);
 470 }
 471
 472 static bool
 473 gate_tree_complete_unroll (void)
 474 {
 475   return true;
 476 }
 477
 478 struct gimple_opt_pass pass_complete_unroll =
 479 {
 480  {
 481   GIMPLE_PASS,
 482   "cunroll",                            /* name */
 483   OPTGROUP_LOOP,                        /* optinfo_flags */
 484   gate_tree_complete_unroll,            /* gate */
 485   tree_complete_unroll,                 /* execute */
 486   NULL,                                 /* sub */
 487   NULL,                                 /* next */
 488   0,                                    /* static_pass_number */
 489   TV_COMPLETE_UNROLL,                   /* tv_id */
 490   PROP_cfg | PROP_ssa,                  /* properties_required */
 491   0,                                    /* properties_provided */
 492   0,                                    /* properties_destroyed */
 493   0,                                    /* todo_flags_start */
 494   0                                     /* todo_flags_finish */
 495  }
 496 };
 497
 498 /* Complete unrolling of inner loops.  */
 499
 500 static unsigned int
 501 tree_complete_unroll_inner (void)
 502 {
 503   unsigned ret = 0;
 504
 505   loop_optimizer_init (LOOPS_NORMAL
 506                        | LOOPS_HAVE_RECORDED_EXITS);
 507   if (number_of_loops (cfun) > 1)
 508     {
 509       scev_initialize ();
 510       ret = tree_unroll_loops_completely (optimize >= 3, false);
 511       free_numbers_of_iterations_estimates ();
 512       scev_finalize ();
 513     }
 514   loop_optimizer_finalize ();
 515
 516   return ret;
 517 }
 518
 519 static bool
 520 gate_tree_complete_unroll_inner (void)
 521 {
 522   return optimize >= 2;
 523 }
 524
 525 struct gimple_opt_pass pass_complete_unrolli =
 526 {
 527  {
 528   GIMPLE_PASS,
 529   "cunrolli",                           /* name */
 530   OPTGROUP_LOOP,                        /* optinfo_flags */
 531   gate_tree_complete_unroll_inner,      /* gate */
 532   tree_complete_unroll_inner,           /* execute */
 533   NULL,                                 /* sub */
 534   NULL,                                 /* next */
 535   0,                                    /* static_pass_number */
 536   TV_COMPLETE_UNROLL,                   /* tv_id */
 537   PROP_cfg | PROP_ssa,                  /* properties_required */
 538   0,                                    /* properties_provided */
 539   0,                                    /* properties_destroyed */
 540   0,                                    /* todo_flags_start */
 541   TODO_verify_flow                      /* 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 (cfun) <= 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   TODO_verify_flow                      /* 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 (cfun) <= 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 (cfun) <= 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_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 };