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