gcc/tree-ssa-loop.c

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