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   PROP_loops,                           /* 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_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 };