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