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 "output.h"
  29 #include "tree-flow.h"
  30 #include "tree-dump.h"
  31 #include "tree-pass.h"
  32 #include "timevar.h"
  33 #include "cfgloop.h"
  34 #include "flags.h"
  35 #include "tree-inline.h"
  36 #include "tree-scalar-evolution.h"
  37 #include "diagnostic-core.h"
  38 #include "tree-vectorizer.h"
  39
  40 /* The loop superpass.  */
  41
  42 static bool
  43 gate_tree_loop (void)
  44 {
  45   return flag_tree_loop_optimize != 0;
  46 }
  47
  48 struct gimple_opt_pass pass_tree_loop =
  49 {
  50  {
  51   GIMPLE_PASS,
  52   "loop",                               /* name */
  53   gate_tree_loop,                       /* gate */
  54   NULL,                                 /* execute */
  55   NULL,                                 /* sub */
  56   NULL,                                 /* next */
  57   0,                                    /* static_pass_number */
  58   TV_TREE_LOOP,                         /* tv_id */
  59   PROP_cfg,                             /* properties_required */
  60   0,                                    /* properties_provided */
  61   0,                                    /* properties_destroyed */
  62   TODO_ggc_collect,                     /* todo_flags_start */
  63   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect   /* todo_flags_finish */
  64  }
  65 };
  66
  67 /* Loop optimizer initialization.  */
  68
  69 static unsigned int
  70 tree_ssa_loop_init (void)
  71 {
  72   loop_optimizer_init (LOOPS_NORMAL
  73                        | LOOPS_HAVE_RECORDED_EXITS);
  74   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
  75
  76   if (number_of_loops () <= 1)
  77     return 0;
  78
  79   scev_initialize ();
  80   return 0;
  81 }
  82
  83 struct gimple_opt_pass pass_tree_loop_init =
  84 {
  85  {
  86   GIMPLE_PASS,
  87   "loopinit",                           /* name */
  88   NULL,                                 /* gate */
  89   tree_ssa_loop_init,                   /* execute */
  90   NULL,                                 /* sub */
  91   NULL,                                 /* next */
  92   0,                                    /* static_pass_number */
  93   TV_TREE_LOOP_INIT,                    /* tv_id */
  94   PROP_cfg,                             /* properties_required */
  95   0,                                    /* properties_provided */
  96   0,                                    /* properties_destroyed */
  97   0,                                    /* todo_flags_start */
  98   TODO_dump_func                        /* todo_flags_finish */
  99  }
 100 };
 101
 102 /* Loop invariant motion pass.  */
 103
 104 static unsigned int
 105 tree_ssa_loop_im (void)
 106 {
 107   if (number_of_loops () <= 1)
 108     return 0;
 109
 110   return tree_ssa_lim ();
 111 }
 112
 113 static bool
 114 gate_tree_ssa_loop_im (void)
 115 {
 116   return flag_tree_loop_im != 0;
 117 }
 118
 119 struct gimple_opt_pass pass_lim =
 120 {
 121  {
 122   GIMPLE_PASS,
 123   "lim",                                /* name */
 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   TODO_dump_func                        /* 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   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_dump_func     /* 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   tree_predictive_commoning ();
 183   return 0;
 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   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_dump_func
 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   gate_tree_vectorize,                  /* gate */
 235   tree_vectorize,                       /* execute */
 236   NULL,                                 /* sub */
 237   NULL,                                 /* next */
 238   0,                                    /* static_pass_number */
 239   TV_TREE_VECTORIZATION,                /* tv_id */
 240   PROP_cfg | PROP_ssa,                  /* properties_required */
 241   0,                                    /* properties_provided */
 242   0,                                    /* properties_destroyed */
 243   0,                                    /* todo_flags_start */
 244   TODO_dump_func | TODO_update_ssa
 245     | TODO_ggc_collect                  /* todo_flags_finish */
 246  }
 247 };
 248
 249 /* GRAPHITE optimizations.  */
 250
 251 static unsigned int
 252 graphite_transforms (void)
 253 {
 254   if (!current_loops)
 255     return 0;
 256
 257   graphite_transform_loops ();
 258
 259   return 0;
 260 }
 261
 262 static bool
 263 gate_graphite_transforms (void)
 264 {
 265   /* Enable -fgraphite pass if any one of the graphite optimization flags
 266      is turned on.  */
 267   if (flag_loop_block
 268       || flag_loop_interchange
 269       || flag_tree_loop_linear
 270       || flag_loop_strip_mine
 271       || flag_graphite_identity
 272       || flag_loop_parallelize_all
 273       || flag_loop_flatten
 274       || flag_graphite_opencl)
 275     flag_graphite = 1;
 276
 277   /* Make flag_tree_loop_linear an alias of flag_loop_interchange.  */
 278   if (flag_tree_loop_linear)
 279     flag_loop_interchange = flag_tree_loop_linear;
 280
 281   return flag_graphite != 0;
 282 }
 283
 284 struct gimple_opt_pass pass_graphite =
 285 {
 286  {
 287   GIMPLE_PASS,
 288   "graphite0",                          /* name */
 289   gate_graphite_transforms,             /* gate */
 290   NULL,                                 /* execute */
 291   NULL,                                 /* sub */
 292   NULL,                                 /* next */
 293   0,                                    /* static_pass_number */
 294   TV_GRAPHITE,                          /* tv_id */
 295   PROP_cfg | PROP_ssa,                  /* properties_required */
 296   0,                                    /* properties_provided */
 297   0,                                    /* properties_destroyed */
 298   0,                                    /* todo_flags_start */
 299   0                                     /* todo_flags_finish */
 300  }
 301 };
 302
 303 struct gimple_opt_pass pass_graphite_transforms =
 304 {
 305  {
 306   GIMPLE_PASS,
 307   "graphite",                           /* name */
 308   gate_graphite_transforms,             /* gate */
 309   graphite_transforms,                  /* execute */
 310   NULL,                                 /* sub */
 311   NULL,                                 /* next */
 312   0,                                    /* static_pass_number */
 313   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
 314   PROP_cfg | PROP_ssa,                  /* properties_required */
 315   0,                                    /* properties_provided */
 316   0,                                    /* properties_destroyed */
 317   0,                                    /* todo_flags_start */
 318   0                                     /* todo_flags_finish */
 319  }
 320 };
 321
 322 /* Check the correctness of the data dependence analyzers.  */
 323
 324 static unsigned int
 325 check_data_deps (void)
 326 {
 327   if (number_of_loops () <= 1)
 328     return 0;
 329
 330   tree_check_data_deps ();
 331   return 0;
 332 }
 333
 334 static bool
 335 gate_check_data_deps (void)
 336 {
 337   return flag_check_data_deps != 0;
 338 }
 339
 340 struct gimple_opt_pass pass_check_data_deps =
 341 {
 342  {
 343   GIMPLE_PASS,
 344   "ckdd",                               /* name */
 345   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   TODO_dump_func                        /* 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 () <= 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   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   TODO_dump_func                        /* 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   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_dump_func | 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 (true);
 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   NULL,                                 /* gate */
 443   tree_ssa_loop_bounds,                 /* execute */
 444   NULL,                                 /* sub */
 445   NULL,                                 /* next */
 446   0,                                    /* static_pass_number */
 447   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 448   PROP_cfg | PROP_ssa,                  /* properties_required */
 449   0,                                    /* properties_provided */
 450   0,                                    /* properties_destroyed */
 451   0,                                    /* todo_flags_start */
 452   0                                     /* todo_flags_finish */
 453  }
 454 };
 455
 456 /* Complete unrolling of loops.  */
 457
 458 static unsigned int
 459 tree_complete_unroll (void)
 460 {
 461   if (number_of_loops () <= 1)
 462     return 0;
 463
 464   return tree_unroll_loops_completely (flag_unroll_loops
 465                                        || flag_peel_loops
 466                                        || optimize >= 3, true);
 467 }
 468
 469 static bool
 470 gate_tree_complete_unroll (void)
 471 {
 472   return true;
 473 }
 474
 475 struct gimple_opt_pass pass_complete_unroll =
 476 {
 477  {
 478   GIMPLE_PASS,
 479   "cunroll",                            /* name */
 480   gate_tree_complete_unroll,            /* gate */
 481   tree_complete_unroll,                 /* execute */
 482   NULL,                                 /* sub */
 483   NULL,                                 /* next */
 484   0,                                    /* static_pass_number */
 485   TV_COMPLETE_UNROLL,                   /* tv_id */
 486   PROP_cfg | PROP_ssa,                  /* properties_required */
 487   0,                                    /* properties_provided */
 488   0,                                    /* properties_destroyed */
 489   0,                                    /* todo_flags_start */
 490   TODO_dump_func
 491     | TODO_ggc_collect                  /* todo_flags_finish */
 492  }
 493 };
 494
 495 /* Complete unrolling of inner loops.  */
 496
 497 static unsigned int
 498 tree_complete_unroll_inner (void)
 499 {
 500   unsigned ret = 0;
 501
 502   loop_optimizer_init (LOOPS_NORMAL
 503                        | LOOPS_HAVE_RECORDED_EXITS);
 504   if (number_of_loops () > 1)
 505     {
 506       scev_initialize ();
 507       ret = tree_unroll_loops_completely (optimize >= 3, false);
 508       free_numbers_of_iterations_estimates ();
 509       scev_finalize ();
 510     }
 511   loop_optimizer_finalize ();
 512
 513   return ret;
 514 }
 515
 516 static bool
 517 gate_tree_complete_unroll_inner (void)
 518 {
 519   return optimize >= 2;
 520 }
 521
 522 struct gimple_opt_pass pass_complete_unrolli =
 523 {
 524  {
 525   GIMPLE_PASS,
 526   "cunrolli",                           /* name */
 527   gate_tree_complete_unroll_inner,      /* gate */
 528   tree_complete_unroll_inner,           /* execute */
 529   NULL,                                 /* sub */
 530   NULL,                                 /* next */
 531   0,                                    /* static_pass_number */
 532   TV_COMPLETE_UNROLL,                   /* tv_id */
 533   PROP_cfg | PROP_ssa,                  /* properties_required */
 534   0,                                    /* properties_provided */
 535   0,                                    /* properties_destroyed */
 536   0,                                    /* todo_flags_start */
 537   TODO_dump_func
 538     | TODO_ggc_collect                  /* todo_flags_finish */
 539  }
 540 };
 541
 542 /* Parallelization.  */
 543
 544 static bool
 545 gate_tree_parallelize_loops (void)
 546 {
 547   return flag_tree_parallelize_loops > 1;
 548 }
 549
 550 static unsigned
 551 tree_parallelize_loops (void)
 552 {
 553   if (number_of_loops () <= 1)
 554     return 0;
 555
 556   if (parallelize_loops ())
 557     return TODO_cleanup_cfg | TODO_rebuild_alias;
 558   return 0;
 559 }
 560
 561 struct gimple_opt_pass pass_parallelize_loops =
 562 {
 563  {
 564   GIMPLE_PASS,
 565   "parloops",                           /* name */
 566   gate_tree_parallelize_loops,          /* gate */
 567   tree_parallelize_loops,               /* execute */
 568   NULL,                                 /* sub */
 569   NULL,                                 /* next */
 570   0,                                    /* static_pass_number */
 571   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
 572   PROP_cfg | PROP_ssa,                  /* properties_required */
 573   0,                                    /* properties_provided */
 574   0,                                    /* properties_destroyed */
 575   0,                                    /* todo_flags_start */
 576   TODO_dump_func                        /* todo_flags_finish */
 577  }
 578 };
 579
 580 /* Prefetching.  */
 581
 582 static unsigned int
 583 tree_ssa_loop_prefetch (void)
 584 {
 585   if (number_of_loops () <= 1)
 586     return 0;
 587
 588   return tree_ssa_prefetch_arrays ();
 589 }
 590
 591 static bool
 592 gate_tree_ssa_loop_prefetch (void)
 593 {
 594   return flag_prefetch_loop_arrays > 0;
 595 }
 596
 597 struct gimple_opt_pass pass_loop_prefetch =
 598 {
 599  {
 600   GIMPLE_PASS,
 601   "aprefetch",                          /* name */
 602   gate_tree_ssa_loop_prefetch,          /* gate */
 603   tree_ssa_loop_prefetch,               /* execute */
 604   NULL,                                 /* sub */
 605   NULL,                                 /* next */
 606   0,                                    /* static_pass_number */
 607   TV_TREE_PREFETCH,                     /* tv_id */
 608   PROP_cfg | PROP_ssa,                  /* properties_required */
 609   0,                                    /* properties_provided */
 610   0,                                    /* properties_destroyed */
 611   0,                                    /* todo_flags_start */
 612   TODO_dump_func                        /* todo_flags_finish */
 613  }
 614 };
 615
 616 /* Induction variable optimizations.  */
 617
 618 static unsigned int
 619 tree_ssa_loop_ivopts (void)
 620 {
 621   if (number_of_loops () <= 1)
 622     return 0;
 623
 624   tree_ssa_iv_optimize ();
 625   return 0;
 626 }
 627
 628 static bool
 629 gate_tree_ssa_loop_ivopts (void)
 630 {
 631   return flag_ivopts != 0;
 632 }
 633
 634 struct gimple_opt_pass pass_iv_optimize =
 635 {
 636  {
 637   GIMPLE_PASS,
 638   "ivopts",                             /* name */
 639   gate_tree_ssa_loop_ivopts,            /* gate */
 640   tree_ssa_loop_ivopts,                 /* execute */
 641   NULL,                                 /* sub */
 642   NULL,                                 /* next */
 643   0,                                    /* static_pass_number */
 644   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 645   PROP_cfg | PROP_ssa,                  /* properties_required */
 646   0,                                    /* properties_provided */
 647   0,                                    /* properties_destroyed */
 648   0,                                    /* todo_flags_start */
 649   TODO_dump_func | TODO_update_ssa | TODO_ggc_collect   /* todo_flags_finish */
 650  }
 651 };
 652
 653 /* Loop optimizer finalization.  */
 654
 655 static unsigned int
 656 tree_ssa_loop_done (void)
 657 {
 658   free_numbers_of_iterations_estimates ();
 659   scev_finalize ();
 660   loop_optimizer_finalize ();
 661   return 0;
 662 }
 663
 664 struct gimple_opt_pass pass_tree_loop_done =
 665 {
 666  {
 667   GIMPLE_PASS,
 668   "loopdone",                           /* name */
 669   NULL,                                 /* gate */
 670   tree_ssa_loop_done,                   /* execute */
 671   NULL,                                 /* sub */
 672   NULL,                                 /* next */
 673   0,                                    /* static_pass_number */
 674   TV_TREE_LOOP_FINI,                    /* tv_id */
 675   PROP_cfg,                             /* properties_required */
 676   0,                                    /* properties_provided */
 677   0,                                    /* properties_destroyed */
 678   0,                                    /* todo_flags_start */
 679   TODO_cleanup_cfg | TODO_dump_func     /* todo_flags_finish */
 680  }
 681 };