gcc/tree-ssa-loop.c

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